Multirange datatypes

Multiranges are basically sorted arrays of non-overlapping ranges with
set-theoretic operations defined over them.

Since v14, each range type automatically gets a corresponding multirange
datatype.  There are both manual and automatic mechanisms for naming multirange
types.  Once can specify multirange type name using multirange_type_name
attribute in CREATE TYPE.  Otherwise, a multirange type name is generated
automatically.  If the range type name contains "range" then we change that to
"multirange".  Otherwise, we add "_multirange" to the end.

Implementation of multiranges comes with a space-efficient internal
representation format, which evades extra paddings and duplicated storage of
oids.  Altogether this format allows fetching a particular range by its index
in O(n).

Statistic gathering and selectivity estimation are implemented for multiranges.
For this purpose, stored multirange is approximated as union range without gaps.
This field will likely need improvements in the future.

Catversion is bumped.

Discussion: https://postgr.es/m/CALNJ-vSUpQ_Y%3DjXvTxt1VYFztaBSsWVXeF1y6gTYQ4bOiWDLgQ%40mail.gmail.com
Discussion: https://postgr.es/m/a0b8026459d1e6167933be2104a6174e7d40d0ab.camel%40j-davis.com#fe7218c83b08068bfffb0c5293eceda0
Author: Paul Jungwirth, revised by me
Reviewed-by: David Fetter, Corey Huinker, Jeff Davis, Pavel Stehule
Reviewed-by: Alvaro Herrera, Tom Lane, Isaac Morland, David G. Johnston
Reviewed-by: Zhihong Yu, Alexander Korotkov

6 files changed, 157 insertions, 16 deletions

diff --git a/src/include/utils/lsyscache.h b/src/include/utils/lsyscache.h
index a990d11ea86..e5ad7b95d17 100644
--- a/src/include/utils/lsyscache.h
+++ b/src/include/utils/lsyscache.h
@@ -161,6 +161,7 @@ extern char get_typtype(Oid typid);
 extern bool type_is_rowtype(Oid typid);
 extern bool type_is_enum(Oid typid);
 extern bool type_is_range(Oid typid);
+extern bool type_is_multirange(Oid typid);
 extern void get_type_category_preferred(Oid typid,
 										char *typcategory,
 										bool *typispreferred);
@@ -190,6 +191,8 @@ extern char *get_namespace_name(Oid nspid);
 extern char *get_namespace_name_or_temp(Oid nspid);
 extern Oid	get_range_subtype(Oid rangeOid);
 extern Oid	get_range_collation(Oid rangeOid);
+extern Oid	get_range_multirange(Oid rangeOid);
+extern Oid	get_multirange_range(Oid multirangeOid);
 extern Oid	get_index_column_opclass(Oid index_oid, int attno);
 extern bool get_index_isreplident(Oid index_oid);
 extern bool get_index_isvalid(Oid index_oid);
diff --git a/src/include/utils/multirangetypes.h b/src/include/utils/multirangetypes.h
new file mode 100644
index 00000000000..4cf72415701
--- /dev/null
+++ b/src/include/utils/multirangetypes.h
@@ -0,0 +1,116 @@
+/*-------------------------------------------------------------------------
+ *
+ * multirangetypes.h
+ *	  Declarations for Postgres multirange types.
+ *
+ *
+ * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/include/utils/multirangetypes.h
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef MULTIRANGETYPES_H
+#define MULTIRANGETYPES_H
+
+#include "utils/typcache.h"
+#include "utils/expandeddatum.h"
+
+
+/*
+ * Multiranges are varlena objects, so must meet the varlena convention that
+ * the first int32 of the object contains the total object size in bytes.
+ * Be sure to use VARSIZE() and SET_VARSIZE() to access it, though!
+ */
+typedef struct
+{
+	int32		vl_len_;		/* varlena header (do not touch directly!) */
+	Oid			multirangetypid;	/* multirange type's own OID */
+	uint32		rangeCount;		/* the number of ranges */
+
+	/*
+	 * Following the count are the range objects themselves, as ShortRangeType
+	 * structs. Note that ranges are varlena too, depending on whether they
+	 * have lower/upper bounds and because even their base types can be
+	 * varlena. So we can't really index into this list.
+	 */
+} MultirangeType;
+
+/* Use these macros in preference to accessing these fields directly */
+#define MultirangeTypeGetOid(mr)	((mr)->multirangetypid)
+#define MultirangeIsEmpty(mr)  ((mr)->rangeCount == 0)
+
+/*
+ * fmgr macros for multirange type objects
+ */
+#define DatumGetMultirangeTypeP(X)		((MultirangeType *) PG_DETOAST_DATUM(X))
+#define DatumGetMultirangeTypePCopy(X)	((MultirangeType *) PG_DETOAST_DATUM_COPY(X))
+#define MultirangeTypePGetDatum(X)		PointerGetDatum(X)
+#define PG_GETARG_MULTIRANGE_P(n)		DatumGetMultirangeTypeP(PG_GETARG_DATUM(n))
+#define PG_GETARG_MULTIRANGE_P_COPY(n)	DatumGetMultirangeTypePCopy(PG_GETARG_DATUM(n))
+#define PG_RETURN_MULTIRANGE_P(x)		return MultirangeTypePGetDatum(x)
+
+/*
+ * prototypes for functions defined in multirangetypes.c
+ */
+
+/* internal versions of the above */
+extern bool multirange_eq_internal(TypeCacheEntry *typcache, MultirangeType *mr1,
+								   MultirangeType *mr2);
+extern bool multirange_ne_internal(TypeCacheEntry *typcache, MultirangeType *mr1,
+								   MultirangeType *mr2);
+extern bool multirange_contains_elem_internal(TypeCacheEntry *typcache, MultirangeType *mr,
+											  Datum elem);
+extern bool multirange_contains_range_internal(TypeCacheEntry *typcache, MultirangeType *mr,
+											   RangeType *r);
+extern bool multirange_contains_multirange_internal(TypeCacheEntry *typcache,
+													MultirangeType *mr1,
+													MultirangeType *mr2);
+extern bool range_overlaps_multirange_internal(TypeCacheEntry *typcache, RangeType *r,
+											   MultirangeType *mr);
+extern bool multirange_overlaps_multirange_internal(TypeCacheEntry *typcache,
+													MultirangeType *mr1,
+													MultirangeType *mr2);
+extern bool range_before_multirange_internal(TypeCacheEntry *typcache, RangeType *r,
+											 MultirangeType *mr);
+extern bool range_after_multirange_internal(TypeCacheEntry *typcache, RangeType *r,
+											MultirangeType *mr);
+extern bool range_adjacent_multirange_internal(TypeCacheEntry *typcache, RangeType *r,
+											MultirangeType *mr);
+extern bool multirange_before_multirange_internal(TypeCacheEntry *typcache,
+												  MultirangeType *mr1,
+												  MultirangeType *mr2);
+extern MultirangeType *multirange_minus_internal(Oid mltrngtypoid,
+												 TypeCacheEntry *rangetyp,
+												 int32 range_count1,
+												 RangeType **ranges1,
+												 int32 range_count2,
+												 RangeType **ranges2);
+extern MultirangeType *multirange_intersect_internal(Oid mltrngtypoid,
+													 TypeCacheEntry *rangetyp,
+													 int32 range_count1,
+													 RangeType **ranges1,
+													 int32 range_count2,
+													 RangeType **ranges2);
+
+/* assorted support functions */
+extern TypeCacheEntry *multirange_get_typcache(FunctionCallInfo fcinfo,
+											   Oid mltrngtypid);
+extern void multirange_deserialize(TypeCacheEntry *rangetyp,
+								   const MultirangeType *range,
+								   int32 *range_count,
+								   RangeType ***ranges);
+extern MultirangeType *make_multirange(Oid mltrngtypoid,
+									   TypeCacheEntry *typcache,
+									   int32 range_count, RangeType **ranges);
+extern MultirangeType *make_empty_multirange(Oid mltrngtypoid,
+											 TypeCacheEntry *rangetyp);
+extern void multirange_get_bounds(TypeCacheEntry *rangetyp,
+								  const MultirangeType *multirange,
+								  uint32 i,
+								  RangeBound *lower, RangeBound *upper);
+extern RangeType *multirange_get_range(TypeCacheEntry *rangetyp,
+									   const MultirangeType *multirange, int i);
+
+#endif							/* MULTIRANGETYPES_H */
diff --git a/src/include/utils/rangetypes.h b/src/include/utils/rangetypes.h
index b77c41cf1b8..8459a3d6e7a 100644
--- a/src/include/utils/rangetypes.h
+++ b/src/include/utils/rangetypes.h
@@ -29,6 +29,8 @@ typedef struct
 	/* Following the OID are zero to two bound values, then a flags byte */
 } RangeType;
 
+#define RANGE_EMPTY_LITERAL "empty"
+
 /* Use this macro in preference to fetching rangetypid field directly */
 #define RangeTypeGetOid(r)	((r)->rangetypid)
 
@@ -115,6 +117,12 @@ extern bool range_overleft_internal(TypeCacheEntry *typcache, const RangeType *r
 									const RangeType *r2);
 extern bool range_overright_internal(TypeCacheEntry *typcache, const RangeType *r1,
 									 const RangeType *r2);
+extern RangeType *range_union_internal(TypeCacheEntry *typcache, RangeType *r1,
+									   RangeType *r2, bool strict);
+extern RangeType *range_minus_internal(TypeCacheEntry *typcache, RangeType *r1,
+									   RangeType *r2);
+extern RangeType *range_intersect_internal(TypeCacheEntry *typcache, const RangeType *r1,
+										   const RangeType *r2);
 
 /* assorted support functions */
 extern TypeCacheEntry *range_get_typcache(FunctionCallInfo fcinfo,
@@ -132,8 +140,12 @@ extern int	range_cmp_bounds(TypeCacheEntry *typcache, const RangeBound *b1,
 							 const RangeBound *b2);
 extern int	range_cmp_bound_values(TypeCacheEntry *typcache, const RangeBound *b1,
 								   const RangeBound *b2);
+extern int	range_compare(const void *key1, const void *key2, void *arg);
 extern bool bounds_adjacent(TypeCacheEntry *typcache, RangeBound bound1,
 							RangeBound bound2);
 extern RangeType *make_empty_range(TypeCacheEntry *typcache);
+extern bool range_split_internal(TypeCacheEntry *typcache, const RangeType *r1,
+								 const RangeType *r2, RangeType **output1,
+								 RangeType **output2);
 
 #endif							/* RANGETYPES_H */
diff --git a/src/include/utils/selfuncs.h b/src/include/utils/selfuncs.h
index 3a2cfb7efa6..68ffd7761f1 100644
--- a/src/include/utils/selfuncs.h
+++ b/src/include/utils/selfuncs.h
@@ -39,6 +39,9 @@
 /* default selectivity estimate for range inequalities "A > b AND A < c" */
 #define DEFAULT_RANGE_INEQ_SEL	0.005
 
+/* default selectivity estimate for multirange inequalities "A > b AND A < c" */
+#define DEFAULT_MULTIRANGE_INEQ_SEL	0.005
+
 /* default selectivity estimate for pattern-match operators such as LIKE */
 #define DEFAULT_MATCH_SEL	0.005
 
diff --git a/src/include/utils/syscache.h b/src/include/utils/syscache.h
index f27b73d76d0..e8f393520a3 100644
--- a/src/include/utils/syscache.h
+++ b/src/include/utils/syscache.h
@@ -79,6 +79,7 @@ enum SysCacheIdentifier
 	PUBLICATIONOID,
 	PUBLICATIONREL,
 	PUBLICATIONRELMAP,
+	RANGEMULTIRANGE,
 	RANGETYPE,
 	RELNAMENSP,
 	RELOID,
diff --git a/src/include/utils/typcache.h b/src/include/utils/typcache.h
index 38c8fe01929..dd69a06342f 100644
--- a/src/include/utils/typcache.h
+++ b/src/include/utils/typcache.h
@@ -102,6 +102,11 @@ typedef struct TypeCacheEntry
 	FmgrInfo	rng_subdiff_finfo;	/* difference function, if any */
 
 	/*
+	 * Fields computed when TYPCACHE_MULTIRANGE_INFO is required.
+	 */
+	struct TypeCacheEntry *rngtype; /* multirange's range underlying type */
+
+	/*
 	 * Domain's base type and typmod if it's a domain type.  Zeroes if not
 	 * domain, or if information hasn't been requested.
 	 */
@@ -128,22 +133,23 @@ typedef struct TypeCacheEntry
 } TypeCacheEntry;
 
 /* Bit flags to indicate which fields a given caller needs to have set */
-#define TYPECACHE_EQ_OPR			0x0001
-#define TYPECACHE_LT_OPR			0x0002
-#define TYPECACHE_GT_OPR			0x0004
-#define TYPECACHE_CMP_PROC			0x0008
-#define TYPECACHE_HASH_PROC			0x0010
-#define TYPECACHE_EQ_OPR_FINFO		0x0020
-#define TYPECACHE_CMP_PROC_FINFO	0x0040
-#define TYPECACHE_HASH_PROC_FINFO	0x0080
-#define TYPECACHE_TUPDESC			0x0100
-#define TYPECACHE_BTREE_OPFAMILY	0x0200
-#define TYPECACHE_HASH_OPFAMILY		0x0400
-#define TYPECACHE_RANGE_INFO		0x0800
-#define TYPECACHE_DOMAIN_BASE_INFO			0x1000
-#define TYPECACHE_DOMAIN_CONSTR_INFO		0x2000
-#define TYPECACHE_HASH_EXTENDED_PROC		0x4000
-#define TYPECACHE_HASH_EXTENDED_PROC_FINFO	0x8000
+#define TYPECACHE_EQ_OPR			0x00001
+#define TYPECACHE_LT_OPR			0x00002
+#define TYPECACHE_GT_OPR			0x00004
+#define TYPECACHE_CMP_PROC			0x00008
+#define TYPECACHE_HASH_PROC			0x00010
+#define TYPECACHE_EQ_OPR_FINFO		0x00020
+#define TYPECACHE_CMP_PROC_FINFO	0x00040
+#define TYPECACHE_HASH_PROC_FINFO	0x00080
+#define TYPECACHE_TUPDESC			0x00100
+#define TYPECACHE_BTREE_OPFAMILY	0x00200
+#define TYPECACHE_HASH_OPFAMILY		0x00400
+#define TYPECACHE_RANGE_INFO		0x00800
+#define TYPECACHE_DOMAIN_BASE_INFO			0x01000
+#define TYPECACHE_DOMAIN_CONSTR_INFO		0x02000
+#define TYPECACHE_HASH_EXTENDED_PROC		0x04000
+#define TYPECACHE_HASH_EXTENDED_PROC_FINFO	0x08000
+#define TYPECACHE_MULTIRANGE_INFO			0x10000
 
 /* This value will not equal any valid tupledesc identifier, nor 0 */
 #define INVALID_TUPLEDESC_IDENTIFIER ((uint64) 1)