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

22 files changed, 749 insertions, 30 deletions

diff --git a/src/include/access/tupmacs.h b/src/include/access/tupmacs.h
index 70157cf90ab..c262265b951 100644
--- a/src/include/access/tupmacs.h
+++ b/src/include/access/tupmacs.h
@@ -139,8 +139,8 @@
  *	* we need to estimate alignment padding cost abstractly, ie without
  *	  reference to a real tuple.  We must assume the worst case that
  *	  all varlenas are aligned.
- *	* within arrays, we unconditionally align varlenas (XXX this should be
- *	  revisited, probably).
+ *	* within arrays and multiranges, we unconditionally align varlenas (XXX this
+ *	  should be revisited, probably).
  *
  * The attalign cases are tested in what is hopefully something like their
  * frequency of occurrence.
diff --git a/src/include/catalog/binary_upgrade.h b/src/include/catalog/binary_upgrade.h
index 02fecb90f79..1ff62e9f8e6 100644
--- a/src/include/catalog/binary_upgrade.h
+++ b/src/include/catalog/binary_upgrade.h
@@ -16,6 +16,8 @@
 
 extern PGDLLIMPORT Oid binary_upgrade_next_pg_type_oid;
 extern PGDLLIMPORT Oid binary_upgrade_next_array_pg_type_oid;
+extern PGDLLIMPORT Oid binary_upgrade_next_mrng_pg_type_oid;
+extern PGDLLIMPORT Oid binary_upgrade_next_mrng_array_pg_type_oid;
 
 extern PGDLLIMPORT Oid binary_upgrade_next_heap_pg_class_oid;
 extern PGDLLIMPORT Oid binary_upgrade_next_index_pg_class_oid;
diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h
index 7ca030d4600..40fd5d43475 100644
--- a/src/include/catalog/catversion.h
+++ b/src/include/catalog/catversion.h
@@ -53,6 +53,6 @@
  */
 
 /*							yyyymmddN */
-#define CATALOG_VERSION_NO	202012091
+#define CATALOG_VERSION_NO	202012201
 
 #endif
diff --git a/src/include/catalog/pg_aggregate.dat b/src/include/catalog/pg_aggregate.dat
index ffabe275c00..03bab74253d 100644
--- a/src/include/catalog/pg_aggregate.dat
+++ b/src/include/catalog/pg_aggregate.dat
@@ -538,6 +538,17 @@
   aggtransfn => 'bytea_string_agg_transfn',
   aggfinalfn => 'bytea_string_agg_finalfn', aggtranstype => 'internal' },
 
+# range
+{ aggfnoid => 'range_intersect_agg(anyrange)',
+  aggtransfn => 'range_intersect_agg_transfn',
+  aggcombinefn => 'range_intersect_agg_transfn', aggtranstype => 'anyrange' },
+{ aggfnoid => 'range_intersect_agg(anymultirange)',
+  aggtransfn => 'multirange_intersect_agg_transfn',
+  aggcombinefn => 'multirange_intersect_agg_transfn', aggtranstype => 'anymultirange' },
+{ aggfnoid => 'range_agg(anyrange)', aggtransfn => 'range_agg_transfn',
+  aggfinalfn => 'range_agg_finalfn', aggfinalextra => 't',
+  aggtranstype => 'internal' },
+
 # json
 { aggfnoid => 'json_agg', aggtransfn => 'json_agg_transfn',
   aggfinalfn => 'json_agg_finalfn', aggtranstype => 'internal' },
diff --git a/src/include/catalog/pg_amop.dat b/src/include/catalog/pg_amop.dat
index 2c899f19d92..78d7d2c5232 100644
--- a/src/include/catalog/pg_amop.dat
+++ b/src/include/catalog/pg_amop.dat
@@ -1374,6 +1374,28 @@
   amoprighttype => 'anyrange', amopstrategy => '18',
   amopopr => '=(anyrange,anyrange)', amopmethod => 'gist' },
 
+# btree multirange_ops
+{ amopfamily => 'btree/multirange_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '1',
+  amopopr => '<(anymultirange,anymultirange)', amopmethod => 'btree' },
+{ amopfamily => 'btree/multirange_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '2',
+  amopopr => '<=(anymultirange,anymultirange)', amopmethod => 'btree' },
+{ amopfamily => 'btree/multirange_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '3',
+  amopopr => '=(anymultirange,anymultirange)', amopmethod => 'btree' },
+{ amopfamily => 'btree/multirange_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '4',
+  amopopr => '>=(anymultirange,anymultirange)', amopmethod => 'btree' },
+{ amopfamily => 'btree/multirange_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '5',
+  amopopr => '>(anymultirange,anymultirange)', amopmethod => 'btree' },
+
+# hash multirange_ops
+{ amopfamily => 'hash/multirange_ops', amoplefttype => 'anymultirange',
+  amoprighttype => 'anymultirange', amopstrategy => '1',
+  amopopr => '=(anymultirange,anymultirange)', amopmethod => 'hash' },
+
 # SP-GiST quad_point_ops
 { amopfamily => 'spgist/quad_point_ops', amoplefttype => 'point',
   amoprighttype => 'point', amopstrategy => '11', amopopr => '|>>(point,point)',
diff --git a/src/include/catalog/pg_amproc.dat b/src/include/catalog/pg_amproc.dat
index db3e8c2d01a..9d423d535cd 100644
--- a/src/include/catalog/pg_amproc.dat
+++ b/src/include/catalog/pg_amproc.dat
@@ -285,6 +285,8 @@
   amprocrighttype => 'tsquery', amprocnum => '1', amproc => 'tsquery_cmp' },
 { amprocfamily => 'btree/range_ops', amproclefttype => 'anyrange',
   amprocrighttype => 'anyrange', amprocnum => '1', amproc => 'range_cmp' },
+{ amprocfamily => 'btree/multirange_ops', amproclefttype => 'anymultirange',
+  amprocrighttype => 'anymultirange', amprocnum => '1', amproc => 'multirange_cmp' },
 { amprocfamily => 'btree/jsonb_ops', amproclefttype => 'jsonb',
   amprocrighttype => 'jsonb', amprocnum => '1', amproc => 'jsonb_cmp' },
 { amprocfamily => 'btree/xid8_ops', amproclefttype => 'xid8',
@@ -457,6 +459,11 @@
 { amprocfamily => 'hash/range_ops', amproclefttype => 'anyrange',
   amprocrighttype => 'anyrange', amprocnum => '2',
   amproc => 'hash_range_extended' },
+{ amprocfamily => 'hash/multirange_ops', amproclefttype => 'anymultirange',
+  amprocrighttype => 'anymultirange', amprocnum => '1', amproc => 'hash_multirange' },
+{ amprocfamily => 'hash/multirange_ops', amproclefttype => 'anymultirange',
+  amprocrighttype => 'anymultirange', amprocnum => '2',
+  amproc => 'hash_multirange_extended' },
 { amprocfamily => 'hash/jsonb_ops', amproclefttype => 'jsonb',
   amprocrighttype => 'jsonb', amprocnum => '1', amproc => 'jsonb_hash' },
 { amprocfamily => 'hash/jsonb_ops', amproclefttype => 'jsonb',
@@ -1280,12 +1287,13 @@
   amprocrighttype => 'anyrange', amprocnum => '4',
   amproc => 'brin_inclusion_union' },
 { amprocfamily => 'brin/range_inclusion_ops', amproclefttype => 'anyrange',
-  amprocrighttype => 'anyrange', amprocnum => '11', amproc => 'range_merge' },
+  amprocrighttype => 'anyrange', amprocnum => '11',
+  amproc => 'range_merge(anyrange,anyrange)' },
 { amprocfamily => 'brin/range_inclusion_ops', amproclefttype => 'anyrange',
   amprocrighttype => 'anyrange', amprocnum => '13',
   amproc => 'range_contains' },
 { amprocfamily => 'brin/range_inclusion_ops', amproclefttype => 'anyrange',
-  amprocrighttype => 'anyrange', amprocnum => '14', amproc => 'isempty' },
+  amprocrighttype => 'anyrange', amprocnum => '14', amproc => 'isempty(anyrange)' },
 
 # minmax pg_lsn
 { amprocfamily => 'brin/pg_lsn_minmax_ops', amproclefttype => 'pg_lsn',
diff --git a/src/include/catalog/pg_cast.dat b/src/include/catalog/pg_cast.dat
index 5a58f50fbb2..d6ca624addc 100644
--- a/src/include/catalog/pg_cast.dat
+++ b/src/include/catalog/pg_cast.dat
@@ -530,4 +530,17 @@
 { castsource => 'jsonb', casttarget => 'float8', castfunc => 'float8(jsonb)',
   castcontext => 'e', castmethod => 'f' },
 
+# range to multirange
+{ castsource => 'int4range', casttarget => 'int4multirange', castfunc => 'int4multirange(int4range)',
+  castcontext => 'e', castmethod => 'f' },
+{ castsource => 'int8range', casttarget => 'int8multirange', castfunc => 'int8multirange(int8range)',
+  castcontext => 'e', castmethod => 'f' },
+{ castsource => 'numrange', casttarget => 'nummultirange', castfunc => 'nummultirange(numrange)',
+  castcontext => 'e', castmethod => 'f' },
+{ castsource => 'daterange', casttarget => 'datemultirange', castfunc => 'datemultirange(daterange)',
+  castcontext => 'e', castmethod => 'f' },
+{ castsource => 'tsrange', casttarget => 'tsmultirange', castfunc => 'tsmultirange(tsrange)',
+  castcontext => 'e', castmethod => 'f' },
+{ castsource => 'tstzrange', casttarget => 'tstzmultirange', castfunc => 'tstzmultirange(tstzrange)',
+  castcontext => 'e', castmethod => 'f' },
 ]
diff --git a/src/include/catalog/pg_opclass.dat b/src/include/catalog/pg_opclass.dat
index be5712692fe..4c5e475ff7b 100644
--- a/src/include/catalog/pg_opclass.dat
+++ b/src/include/catalog/pg_opclass.dat
@@ -232,6 +232,10 @@
   opcintype => 'anyrange' },
 { opcmethod => 'spgist', opcname => 'range_ops',
   opcfamily => 'spgist/range_ops', opcintype => 'anyrange' },
+{ opcmethod => 'btree', opcname => 'multirange_ops', opcfamily => 'btree/multirange_ops',
+  opcintype => 'anymultirange' },
+{ opcmethod => 'hash', opcname => 'multirange_ops', opcfamily => 'hash/multirange_ops',
+  opcintype => 'anymultirange' },
 { opcmethod => 'spgist', opcname => 'box_ops', opcfamily => 'spgist/box_ops',
   opcintype => 'box' },
 { opcmethod => 'spgist', opcname => 'quad_point_ops',
diff --git a/src/include/catalog/pg_operator.dat b/src/include/catalog/pg_operator.dat
index 7ae19235ee2..bd0c3d0f81a 100644
--- a/src/include/catalog/pg_operator.dat
+++ b/src/include/catalog/pg_operator.dat
@@ -3277,5 +3277,174 @@
   oprname => '@@', oprleft => 'jsonb', oprright => 'jsonpath',
   oprresult => 'bool', oprcode => 'jsonb_path_match_opr(jsonb,jsonpath)',
   oprrest => 'matchingsel', oprjoin => 'matchingjoinsel' },
+{ oid => '2860', descr => 'equal',
+  oprname => '=', oprcanmerge => 't', oprcanhash => 't', oprleft => 'anymultirange',
+  oprright => 'anymultirange', oprresult => 'bool', oprcom => '=(anymultirange,anymultirange)',
+  oprnegate => '<>(anymultirange,anymultirange)', oprcode => 'multirange_eq',
+  oprrest => 'eqsel', oprjoin => 'eqjoinsel' },
+{ oid => '2861', descr => 'not equal',
+  oprname => '<>', oprleft => 'anymultirange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcom => '<>(anymultirange,anymultirange)',
+  oprnegate => '=(anymultirange,anymultirange)', oprcode => 'multirange_ne',
+  oprrest => 'neqsel', oprjoin => 'neqjoinsel' },
+{ oid => '2862', oid_symbol => 'OID_MULTIRANGE_LESS_OP', descr => 'less than',
+  oprname => '<', oprleft => 'anymultirange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcom => '>(anymultirange,anymultirange)',
+  oprnegate => '>=(anymultirange,anymultirange)', oprcode => 'multirange_lt',
+  oprrest => 'multirangesel', oprjoin => 'scalarltjoinsel' },
+{ oid => '2863', oid_symbol => 'OID_MULTIRANGE_LESS_EQUAL_OP',
+  descr => 'less than or equal',
+  oprname => '<=', oprleft => 'anymultirange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcom => '>=(anymultirange,anymultirange)',
+  oprnegate => '>(anymultirange,anymultirange)', oprcode => 'multirange_le',
+  oprrest => 'multirangesel', oprjoin => 'scalarlejoinsel' },
+{ oid => '2864', oid_symbol => 'OID_MULTIRANGE_GREATER_EQUAL_OP',
+  descr => 'greater than or equal',
+  oprname => '>=', oprleft => 'anymultirange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcom => '<=(anymultirange,anymultirange)',
+  oprnegate => '<(anymultirange,anymultirange)', oprcode => 'multirange_ge',
+  oprrest => 'multirangesel', oprjoin => 'scalargejoinsel' },
+{ oid => '2865', oid_symbol => 'OID_MULTIRANGE_GREATER_OP',
+  descr => 'greater than',
+  oprname => '>', oprleft => 'anymultirange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcom => '<(anymultirange,anymultirange)',
+  oprnegate => '<=(anymultirange,anymultirange)', oprcode => 'multirange_gt',
+  oprrest => 'multirangesel', oprjoin => 'scalargtjoinsel' },
+{ oid => '2866', oid_symbol => 'OID_RANGE_OVERLAPS_MULTIRANGE_OP',
+  descr => 'overlaps',
+  oprname => '&&', oprleft => 'anyrange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcom => '&&(anymultirange,anyrange)',
+  oprcode => 'range_overlaps_multirange', oprrest => 'multirangesel',
+  oprjoin => 'areajoinsel' },
+{ oid => '2867', oid_symbol => 'OID_MULTIRANGE_OVERLAPS_RANGE_OP', descr => 'contains',
+  oprname => '&&', oprleft => 'anymultirange', oprright => 'anyrange',
+  oprresult => 'bool', oprcom => '&&(anyrange,anymultirange)',
+  oprcode => 'multirange_overlaps_range', oprrest => 'multirangesel',
+  oprjoin => 'areajoinsel' },
+{ oid => '2868', oid_symbol => 'OID_MULTIRANGE_OVERLAPS_MULTIRANGE_OP', descr => 'contains',
+  oprname => '&&', oprleft => 'anymultirange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcom => '&&(anymultirange,anymultirange)',
+  oprcode => 'multirange_overlaps_multirange', oprrest => 'multirangesel',
+  oprjoin => 'areajoinsel' },
+{ oid => '2869', oid_symbol => 'OID_MULTIRANGE_CONTAINS_ELEM_OP',
+  descr => 'contains',
+  oprname => '@>', oprleft => 'anymultirange', oprright => 'anyelement',
+  oprresult => 'bool', oprcom => '<@(anyelement,anymultirange)',
+  oprcode => 'multirange_contains_elem', oprrest => 'multirangesel',
+  oprjoin => 'contjoinsel' },
+{ oid => '2870', oid_symbol => 'OID_MULTIRANGE_CONTAINS_RANGE_OP', descr => 'contains',
+  oprname => '@>', oprleft => 'anymultirange', oprright => 'anyrange',
+  oprresult => 'bool', oprcom => '<@(anyrange,anymultirange)',
+  oprcode => 'multirange_contains_range', oprrest => 'multirangesel',
+  oprjoin => 'contjoinsel' },
+{ oid => '2871', oid_symbol => 'OID_MULTIRANGE_CONTAINS_MULTIRANGE_OP', descr => 'contains',
+  oprname => '@>', oprleft => 'anymultirange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcom => '<@(anymultirange,anymultirange)',
+  oprcode => 'multirange_contains_multirange', oprrest => 'multirangesel',
+  oprjoin => 'contjoinsel' },
+{ oid => '2872', oid_symbol => 'OID_MULTIRANGE_ELEM_CONTAINED_OP',
+  descr => 'is contained by',
+  oprname => '<@', oprleft => 'anyelement', oprright => 'anymultirange',
+  oprresult => 'bool', oprcom => '@>(anymultirange,anyelement)',
+  oprcode => 'elem_contained_by_multirange', oprrest => 'multirangesel',
+  oprjoin => 'contjoinsel' },
+{ oid => '2873', oid_symbol => 'OID_MULTIRANGE_RANGE_CONTAINED_OP',
+  descr => 'is contained by',
+  oprname => '<@', oprleft => 'anyrange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcom => '@>(anymultirange,anyrange)',
+  oprcode => 'range_contained_by_multirange', oprrest => 'multirangesel',
+  oprjoin => 'contjoinsel' },
+{ oid => '2874', oid_symbol => 'OID_MULTIRANGE_MULTIRANGE_CONTAINED_OP',
+  descr => 'is contained by',
+  oprname => '<@', oprleft => 'anymultirange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcom => '@>(anymultirange,anymultirange)',
+  oprcode => 'multirange_contained_by_multirange', oprrest => 'multirangesel',
+  oprjoin => 'contjoinsel' },
+{ oid => '2875', oid_symbol => 'OID_RANGE_OVERLAPS_LEFT_MULTIRANGE_OP',
+  descr => 'overlaps or is left of',
+  oprname => '&<', oprleft => 'anyrange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcode => 'range_overleft_multirange', oprrest => 'multirangesel',
+  oprjoin => 'scalarltjoinsel' },
+{ oid => '2876', oid_symbol => 'OID_MULTIRANGE_OVERLAPS_LEFT_RANGE_OP',
+  descr => 'overlaps or is left of',
+  oprname => '&<', oprleft => 'anymultirange', oprright => 'anyrange',
+  oprresult => 'bool', oprcode => 'multirange_overleft_range', oprrest => 'multirangesel',
+  oprjoin => 'scalarltjoinsel' },
+{ oid => '2877', oid_symbol => 'OID_MULTIRANGE_OVERLAPS_LEFT_MULTIRANGE_OP',
+  descr => 'overlaps or is left of',
+  oprname => '&<', oprleft => 'anymultirange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcode => 'multirange_overleft_multirange', oprrest => 'multirangesel',
+  oprjoin => 'scalargtjoinsel' },
+{ oid => '3585', oid_symbol => 'OID_RANGE_OVERLAPS_RIGHT_MULTIRANGE_OP',
+  descr => 'overlaps or is right of',
+  oprname => '&>', oprleft => 'anyrange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcode => 'range_overright_multirange', oprrest => 'multirangesel',
+  oprjoin => 'scalargtjoinsel' },
+{ oid => '4035', oid_symbol => 'OID_MULTIRANGE_OVERLAPS_RIGHT_RANGE_OP',
+  descr => 'overlaps or is right of',
+  oprname => '&>', oprleft => 'anymultirange', oprright => 'anyrange',
+  oprresult => 'bool', oprcode => 'multirange_overright_range', oprrest => 'multirangesel',
+  oprjoin => 'scalargtjoinsel' },
+{ oid => '4142', oid_symbol => 'OID_MULTIRANGE_OVERLAPS_RIGHT_MULTIRANGE_OP',
+  descr => 'overlaps or is right of',
+  oprname => '&>', oprleft => 'anymultirange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcode => 'multirange_overright_multirange', oprrest => 'multirangesel',
+  oprjoin => 'scalargtjoinsel' },
+{ oid => '4179', oid_symbol => 'OID_RANGE_ADJACENT_MULTIRANGE_OP', descr => 'is adjacent to',
+  oprname => '-|-', oprleft => 'anyrange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcom => '-|-(anymultirange,anyrange)',
+  oprcode => 'range_adjacent_multirange', oprrest => 'matchingsel',
+  oprjoin => 'matchingjoinsel' },
+{ oid => '4180', oid_symbol => 'OID_MULTIRANGE_ADJACENT_RANGE_OP', descr => 'is adjacent to',
+  oprname => '-|-', oprleft => 'anymultirange', oprright => 'anyrange',
+  oprresult => 'bool', oprcom => '-|-(anyrange,anymultirange)',
+  oprcode => 'multirange_adjacent_range', oprrest => 'matchingsel',
+  oprjoin => 'matchingjoinsel' },
+{ oid => '4198', oid_symbol => 'OID_MULTIRANGE_ADJACENT_MULTIRANGE_OP', descr => 'is adjacent to',
+  oprname => '-|-', oprleft => 'anymultirange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcom => '-|-(anymultirange,anymultirange)',
+  oprcode => 'multirange_adjacent_multirange', oprrest => 'matchingsel',
+  oprjoin => 'matchingjoinsel' },
+{ oid => '4392', descr => 'multirange union',
+  oprname => '+', oprleft => 'anymultirange', oprright => 'anymultirange',
+  oprresult => 'anymultirange', oprcom => '+(anymultirange,anymultirange)',
+  oprcode => 'multirange_union' },
+{ oid => '4393', descr => 'multirange minus',
+  oprname => '-', oprleft => 'anymultirange', oprright => 'anymultirange',
+  oprresult => 'anymultirange', oprcode => 'multirange_minus' },
+{ oid => '4394', descr => 'multirange intersect',
+  oprname => '*', oprleft => 'anymultirange', oprright => 'anymultirange',
+  oprresult => 'anymultirange', oprcom => '*(anymultirange,anymultirange)',
+  oprcode => 'multirange_intersect' },
+{ oid => '4395', oid_symbol => 'OID_RANGE_LEFT_MULTIRANGE_OP', descr => 'is left of',
+  oprname => '<<', oprleft => 'anyrange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcom => '>>(anymultirange,anyrange)',
+  oprcode => 'range_before_multirange', oprrest => 'multirangesel',
+  oprjoin => 'scalarltjoinsel' },
+{ oid => '4396', oid_symbol => 'OID_MULTIRANGE_LEFT_RANGE_OP', descr => 'is left of',
+  oprname => '<<', oprleft => 'anymultirange', oprright => 'anyrange',
+  oprresult => 'bool', oprcom => '>>(anyrange,anymultirange)',
+  oprcode => 'multirange_before_range', oprrest => 'multirangesel',
+  oprjoin => 'scalarltjoinsel' },
+{ oid => '4397', oid_symbol => 'OID_MULTIRANGE_LEFT_MULTIRANGE_OP', descr => 'is left of',
+  oprname => '<<', oprleft => 'anymultirange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcom => '>>(anymultirange,anymultirange)',
+  oprcode => 'multirange_before_multirange', oprrest => 'multirangesel',
+  oprjoin => 'scalarltjoinsel' },
+{ oid => '4398', oid_symbol => 'OID_RANGE_RIGHT_MULTIRANGE_OP', descr => 'is right of',
+  oprname => '>>', oprleft => 'anyrange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcom => '<<(anymultirange,anyrange)',
+  oprcode => 'range_after_multirange', oprrest => 'multirangesel',
+  oprjoin => 'scalargtjoinsel' },
+{ oid => '4399', oid_symbol => 'OID_MULTIRANGE_RIGHT_RANGE_OP', descr => 'is right of',
+  oprname => '>>', oprleft => 'anymultirange', oprright => 'anyrange',
+  oprresult => 'bool', oprcom => '<<(anyrange,anymultirange)',
+  oprcode => 'multirange_after_range', oprrest => 'multirangesel',
+  oprjoin => 'scalargtjoinsel' },
+{ oid => '4400', oid_symbol => 'OID_MULTIRANGE_RIGHT_MULTIRANGE_OP', descr => 'is right of',
+  oprname => '>>', oprleft => 'anymultirange', oprright => 'anymultirange',
+  oprresult => 'bool', oprcom => '<<(anymultirange,anymultirange)',
+  oprcode => 'multirange_after_multirange', oprrest => 'multirangesel',
+  oprjoin => 'scalargtjoinsel' },
 
 ]
diff --git a/src/include/catalog/pg_opfamily.dat b/src/include/catalog/pg_opfamily.dat
index 11c7ad2c145..fe42dfc0f8f 100644
--- a/src/include/catalog/pg_opfamily.dat
+++ b/src/include/catalog/pg_opfamily.dat
@@ -232,5 +232,9 @@
   opfmethod => 'spgist', opfname => 'box_ops' },
 { oid => '5008',
   opfmethod => 'spgist', opfname => 'poly_ops' },
+{ oid => '4199',
+  opfmethod => 'btree', opfname => 'multirange_ops' },
+{ oid => '4225',
+  opfmethod => 'hash', opfname => 'multirange_ops' },
 
 ]
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index e6c7b070f64..22970f46cd7 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -7253,6 +7253,14 @@
   proname => 'anycompatiblerange_out', provolatile => 's',
   prorettype => 'cstring', proargtypes => 'anycompatiblerange',
   prosrc => 'anycompatiblerange_out' },
+{ oid => '4226', descr => 'I/O',
+  proname => 'anycompatiblemultirange_in', provolatile => 's',
+  prorettype => 'anycompatiblemultirange', proargtypes => 'cstring oid int4',
+  prosrc => 'anycompatiblemultirange_in' },
+{ oid => '4227', descr => 'I/O',
+  proname => 'anycompatiblemultirange_out', provolatile => 's',
+  prorettype => 'cstring', proargtypes => 'anycompatiblemultirange',
+  prosrc => 'anycompatiblemultirange_out' },
 
 # tablesample method handlers
 { oid => '3313', descr => 'BERNOULLI tablesample method handler',
@@ -9873,6 +9881,10 @@
   descr => 'the smallest range which includes both of the given ranges',
   proname => 'range_merge', prorettype => 'anyrange',
   proargtypes => 'anyrange anyrange', prosrc => 'range_merge' },
+{ oid => '4228',
+  descr => 'the smallest range which includes the whole multirange',
+  proname => 'range_merge', prorettype => 'anyrange',
+  proargtypes => 'anymultirange', prosrc => 'range_merge_from_multirange' },
 { oid => '3868',
   proname => 'range_intersect', prorettype => 'anyrange',
   proargtypes => 'anyrange anyrange', prosrc => 'range_intersect' },
@@ -9922,6 +9934,13 @@
 { oid => '3169', descr => 'restriction selectivity for range operators',
   proname => 'rangesel', provolatile => 's', prorettype => 'float8',
   proargtypes => 'internal oid internal int4', prosrc => 'rangesel' },
+{ oid => '4401', descr => 'range aggregate by intersecting',
+  proname => 'range_intersect_agg_transfn', prorettype => 'anyrange',
+  proargtypes => 'anyrange anyrange', prosrc => 'range_intersect_agg_transfn'},
+{ oid => '4450', descr => 'range aggregate by intersecting',
+  proname => 'range_intersect_agg', prokind => 'a', proisstrict => 'f',
+  prorettype => 'anyrange', proargtypes => 'anyrange',
+  prosrc => 'aggregate_dummy'},
 
 { oid => '3914', descr => 'convert an int4 range to canonical form',
   proname => 'int4range_canonical', prorettype => 'int4range',
@@ -9990,6 +10009,261 @@
   proname => 'int8range', proisstrict => 'f', prorettype => 'int8range',
   proargtypes => 'int8 int8 text', prosrc => 'range_constructor3' },
 
+# functions for multiranges
+{ oid => '4229', descr => 'I/O',
+  proname => 'anymultirange_in', provolatile => 's', prorettype => 'anymultirange',
+  proargtypes => 'cstring oid int4', prosrc => 'anymultirange_in' },
+{ oid => '4230', descr => 'I/O',
+  proname => 'anymultirange_out', provolatile => 's', prorettype => 'cstring',
+  proargtypes => 'anymultirange', prosrc => 'anymultirange_out' },
+{ oid => '4231', descr => 'I/O',
+  proname => 'multirange_in', provolatile => 's', prorettype => 'anymultirange',
+  proargtypes => 'cstring oid int4', prosrc => 'multirange_in' },
+{ oid => '4232', descr => 'I/O',
+  proname => 'multirange_out', provolatile => 's', prorettype => 'cstring',
+  proargtypes => 'anymultirange', prosrc => 'multirange_out' },
+{ oid => '4233', descr => 'I/O',
+  proname => 'multirange_recv', provolatile => 's', prorettype => 'anymultirange',
+  proargtypes => 'internal oid int4', prosrc => 'multirange_recv' },
+{ oid => '4234', descr => 'I/O',
+  proname => 'multirange_send', provolatile => 's', prorettype => 'bytea',
+  proargtypes => 'anymultirange', prosrc => 'multirange_send' },
+{ oid => '4235', descr => 'lower bound of multirange',
+  proname => 'lower', prorettype => 'anyelement', proargtypes => 'anymultirange',
+  prosrc => 'multirange_lower' },
+{ oid => '4236', descr => 'upper bound of multirange',
+  proname => 'upper', prorettype => 'anyelement', proargtypes => 'anymultirange',
+  prosrc => 'multirange_upper' },
+{ oid => '4237', descr => 'is the multirange empty?',
+  proname => 'isempty', prorettype => 'bool',
+  proargtypes => 'anymultirange', prosrc => 'multirange_empty' },
+{ oid => '4238', descr => 'is the multirange\'s lower bound inclusive?',
+  proname => 'lower_inc', prorettype => 'bool', proargtypes => 'anymultirange',
+  prosrc => 'multirange_lower_inc' },
+{ oid => '4239', descr => 'is the multirange\'s upper bound inclusive?',
+  proname => 'upper_inc', prorettype => 'bool', proargtypes => 'anymultirange',
+  prosrc => 'multirange_upper_inc' },
+{ oid => '4240', descr => 'is the multirange\'s lower bound infinite?',
+  proname => 'lower_inf', prorettype => 'bool', proargtypes => 'anymultirange',
+  prosrc => 'multirange_lower_inf' },
+{ oid => '4241', descr => 'is the multirange\'s upper bound infinite?',
+  proname => 'upper_inf', prorettype => 'bool', proargtypes => 'anymultirange',
+  prosrc => 'multirange_upper_inf' },
+{ oid => '4242', descr => 'multirange typanalyze',
+  proname => 'multirange_typanalyze', provolatile => 's', prorettype => 'bool',
+  proargtypes => 'internal', prosrc => 'multirange_typanalyze' },
+{ oid => '4243', descr => 'restriction selectivity for multirange operators',
+  proname => 'multirangesel', provolatile => 's', prorettype => 'float8',
+  proargtypes => 'internal oid internal int4', prosrc => 'multirangesel' },
+{ oid => '4244',
+  proname => 'multirange_eq', prorettype => 'bool',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_eq' },
+{ oid => '4245',
+  proname => 'multirange_ne', prorettype => 'bool',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_ne' },
+{ oid => '4246',
+  proname => 'range_overlaps_multirange', prorettype => 'bool',
+  proargtypes => 'anyrange anymultirange', prosrc => 'range_overlaps_multirange' },
+{ oid => '4247',
+  proname => 'multirange_overlaps_range', prorettype => 'bool',
+  proargtypes => 'anymultirange anyrange', prosrc => 'multirange_overlaps_range' },
+{ oid => '4248',
+  proname => 'multirange_overlaps_multirange', prorettype => 'bool',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_overlaps_multirange' },
+{ oid => '4249',
+  proname => 'multirange_contains_elem', prorettype => 'bool',
+  proargtypes => 'anymultirange anyelement', prosrc => 'multirange_contains_elem' },
+{ oid => '4250',
+  proname => 'multirange_contains_range', prorettype => 'bool',
+  proargtypes => 'anymultirange anyrange', prosrc => 'multirange_contains_range' },
+{ oid => '4251',
+  proname => 'multirange_contains_multirange', prorettype => 'bool',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_contains_multirange' },
+{ oid => '4252',
+  proname => 'elem_contained_by_multirange', prorettype => 'bool',
+  proargtypes => 'anyelement anymultirange', prosrc => 'elem_contained_by_multirange' },
+{ oid => '4253',
+  proname => 'range_contained_by_multirange', prorettype => 'bool',
+  proargtypes => 'anyrange anymultirange', prosrc => 'range_contained_by_multirange' },
+{ oid => '4254',
+  proname => 'multirange_contained_by_multirange', prorettype => 'bool',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_contained_by_multirange' },
+{ oid => '4255',
+  proname => 'range_adjacent_multirange', prorettype => 'bool',
+  proargtypes => 'anyrange anymultirange', prosrc => 'range_adjacent_multirange' },
+{ oid => '4256',
+  proname => 'multirange_adjacent_multirange', prorettype => 'bool',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_adjacent_multirange' },
+{ oid => '4257',
+  proname => 'multirange_adjacent_range', prorettype => 'bool',
+  proargtypes => 'anymultirange anyrange', prosrc => 'multirange_adjacent_range' },
+{ oid => '4258',
+  proname => 'range_before_multirange', prorettype => 'bool',
+  proargtypes => 'anyrange anymultirange', prosrc => 'range_before_multirange' },
+{ oid => '4259',
+  proname => 'multirange_before_range', prorettype => 'bool',
+  proargtypes => 'anymultirange anyrange', prosrc => 'multirange_before_range' },
+{ oid => '4260',
+  proname => 'multirange_before_multirange', prorettype => 'bool',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_before_multirange' },
+{ oid => '4261',
+  proname => 'range_after_multirange', prorettype => 'bool',
+  proargtypes => 'anyrange anymultirange', prosrc => 'range_after_multirange' },
+{ oid => '4262',
+  proname => 'multirange_after_range', prorettype => 'bool',
+  proargtypes => 'anymultirange anyrange', prosrc => 'multirange_after_range' },
+{ oid => '4263',
+  proname => 'multirange_after_multirange', prorettype => 'bool',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_after_multirange' },
+{ oid => '4264',
+  proname => 'range_overleft_multirange', prorettype => 'bool',
+  proargtypes => 'anyrange anymultirange', prosrc => 'range_overleft_multirange' },
+{ oid => '4265',
+  proname => 'multirange_overleft_range', prorettype => 'bool',
+  proargtypes => 'anymultirange anyrange', prosrc => 'multirange_overleft_range' },
+{ oid => '4266',
+  proname => 'multirange_overleft_multirange', prorettype => 'bool',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_overleft_multirange' },
+{ oid => '4267',
+  proname => 'range_overright_multirange', prorettype => 'bool',
+  proargtypes => 'anyrange anymultirange', prosrc => 'range_overright_multirange' },
+{ oid => '4268',
+  proname => 'multirange_overright_range', prorettype => 'bool',
+  proargtypes => 'anymultirange anyrange', prosrc => 'multirange_overright_range' },
+{ oid => '4269',
+  proname => 'multirange_overright_multirange', prorettype => 'bool',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_overright_multirange' },
+{ oid => '4270',
+  proname => 'multirange_union', prorettype => 'anymultirange',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_union' },
+{ oid => '4271',
+  proname => 'multirange_minus', prorettype => 'anymultirange',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_minus' },
+{ oid => '4272',
+  proname => 'multirange_intersect', prorettype => 'anymultirange',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_intersect' },
+{ oid => '4273', descr => 'less-equal-greater',
+  proname => 'multirange_cmp', prorettype => 'int4',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_cmp' },
+{ oid => '4274',
+  proname => 'multirange_lt', prorettype => 'bool',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_lt' },
+{ oid => '4275',
+  proname => 'multirange_le', prorettype => 'bool',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_le' },
+{ oid => '4276',
+  proname => 'multirange_ge', prorettype => 'bool',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_ge' },
+{ oid => '4277',
+  proname => 'multirange_gt', prorettype => 'bool',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_gt' },
+{ oid => '4278', descr => 'hash a multirange',
+  proname => 'hash_multirange', prorettype => 'int4', proargtypes => 'anymultirange',
+  prosrc => 'hash_multirange' },
+{ oid => '4279', descr => 'hash a multirange',
+  proname => 'hash_multirange_extended', prorettype => 'int8',
+  proargtypes => 'anymultirange int8', prosrc => 'hash_multirange_extended' },
+
+{ oid => '4280', descr => 'int4multirange constructor',
+  proname => 'int4multirange', proisstrict => 'f',
+  prorettype => 'int4multirange', proargtypes => '',
+  prosrc => 'multirange_constructor0' },
+{ oid => '4281', descr => 'int4multirange constructor',
+  proname => 'int4multirange', proisstrict => 't',
+  prorettype => 'int4multirange', proargtypes => 'int4range',
+  prosrc => 'multirange_constructor1' },
+{ oid => '4282', descr => 'int4multirange constructor',
+  proname => 'int4multirange', provariadic => 'int4range', proisstrict => 'f',
+  prorettype => 'int4multirange', proargtypes => '_int4range',
+  proallargtypes => '{_int4range}', proargmodes => '{v}',
+  prosrc => 'multirange_constructor2' },
+{ oid => '4283', descr => 'nummultirange constructor',
+  proname => 'nummultirange', proisstrict => 'f',
+  prorettype => 'nummultirange', proargtypes => '',
+  prosrc => 'multirange_constructor0' },
+{ oid => '4284', descr => 'nummultirange constructor',
+  proname => 'nummultirange', proisstrict => 't',
+  prorettype => 'nummultirange', proargtypes => 'numrange',
+  prosrc => 'multirange_constructor1' },
+{ oid => '4285', descr => 'nummultirange constructor',
+  proname => 'nummultirange', provariadic => 'numrange', proisstrict => 'f',
+  prorettype => 'nummultirange', proargtypes => '_numrange',
+  proallargtypes => '{_numrange}', proargmodes => '{v}',
+  prosrc => 'multirange_constructor2' },
+{ oid => '4286', descr => 'tsmultirange constructor',
+  proname => 'tsmultirange', proisstrict => 'f',
+  prorettype => 'tsmultirange', proargtypes => '',
+  prosrc => 'multirange_constructor0' },
+{ oid => '4287', descr => 'tsmultirange constructor',
+  proname => 'tsmultirange', proisstrict => 't',
+  prorettype => 'tsmultirange', proargtypes => 'tsrange',
+  prosrc => 'multirange_constructor1' },
+{ oid => '4288', descr => 'tsmultirange constructor',
+  proname => 'tsmultirange', provariadic => 'tsrange', proisstrict => 'f',
+  prorettype => 'tsmultirange', proargtypes => '_tsrange',
+  proallargtypes => '{_tsrange}', proargmodes => '{v}',
+  prosrc => 'multirange_constructor2' },
+{ oid => '4289', descr => 'tstzmultirange constructor',
+  proname => 'tstzmultirange', proisstrict => 'f',
+  prorettype => 'tstzmultirange', proargtypes => '',
+  prosrc => 'multirange_constructor0' },
+{ oid => '4290', descr => 'tstzmultirange constructor',
+  proname => 'tstzmultirange', proisstrict => 't',
+  prorettype => 'tstzmultirange', proargtypes => 'tstzrange',
+  prosrc => 'multirange_constructor1' },
+{ oid => '4291', descr => 'tstzmultirange constructor',
+  proname => 'tstzmultirange', provariadic => 'tstzrange', proisstrict => 'f',
+  prorettype => 'tstzmultirange', proargtypes => '_tstzrange',
+  proallargtypes => '{_tstzrange}', proargmodes => '{v}',
+  prosrc => 'multirange_constructor2' },
+{ oid => '4292', descr => 'datemultirange constructor',
+  proname => 'datemultirange', proisstrict => 'f',
+  prorettype => 'datemultirange', proargtypes => '',
+  prosrc => 'multirange_constructor0' },
+{ oid => '4293', descr => 'datemultirange constructor',
+  proname => 'datemultirange', proisstrict => 't',
+  prorettype => 'datemultirange', proargtypes => 'daterange',
+  prosrc => 'multirange_constructor1' },
+{ oid => '4294', descr => 'datemultirange constructor',
+  proname => 'datemultirange', provariadic => 'daterange', proisstrict => 'f',
+  prorettype => 'datemultirange', proargtypes => '_daterange',
+  proallargtypes => '{_daterange}', proargmodes => '{v}',
+  prosrc => 'multirange_constructor2' },
+{ oid => '4295', descr => 'int8multirange constructor',
+  proname => 'int8multirange', proisstrict => 'f',
+  prorettype => 'int8multirange', proargtypes => '',
+  prosrc => 'multirange_constructor0' },
+{ oid => '4296', descr => 'int8multirange constructor',
+  proname => 'int8multirange', proisstrict => 't',
+  prorettype => 'int8multirange', proargtypes => 'int8range',
+  prosrc => 'multirange_constructor1' },
+{ oid => '4297', descr => 'int8multirange constructor',
+  proname => 'int8multirange', provariadic => 'int8range', proisstrict => 'f',
+  prorettype => 'int8multirange', proargtypes => '_int8range',
+  proallargtypes => '{_int8range}', proargmodes => '{v}',
+  prosrc => 'multirange_constructor2' },
+{ oid => '4298', descr => 'anymultirange cast',
+  proname => 'multirange', proisstrict => 't',
+  prorettype => 'anymultirange', proargtypes => 'anyrange',
+  prosrc => 'multirange_constructor1' },
+{ oid => '4299', descr => 'aggregate transition function',
+  proname => 'range_agg_transfn', proisstrict => 'f', prorettype => 'internal',
+  proargtypes => 'internal anyrange', prosrc => 'range_agg_transfn' },
+{ oid => '4300', descr => 'aggregate final function',
+  proname => 'range_agg_finalfn', proisstrict => 'f', prorettype => 'anymultirange',
+  proargtypes => 'internal anyrange', prosrc => 'range_agg_finalfn' },
+{ oid => '4301', descr => 'combine aggregate input into a multirange',
+  proname => 'range_agg', prokind => 'a', proisstrict => 'f',
+  prorettype => 'anymultirange', proargtypes => 'anyrange',
+  prosrc => 'aggregate_dummy' },
+{ oid => '4388', descr => 'range aggregate by intersecting',
+  proname => 'multirange_intersect_agg_transfn', prorettype => 'anymultirange',
+  proargtypes => 'anymultirange anymultirange', prosrc => 'multirange_intersect_agg_transfn'},
+{ oid => '4389', descr => 'range aggregate by intersecting',
+  proname => 'range_intersect_agg', prokind => 'a', proisstrict => 'f',
+  prorettype => 'anymultirange', proargtypes => 'anymultirange',
+  prosrc => 'aggregate_dummy'},
+
 # date, time, timestamp constructors
 { oid => '3846', descr => 'construct date',
   proname => 'make_date', prorettype => 'date', proargtypes => 'int4 int4 int4',
@@ -10372,6 +10646,14 @@
   proname => 'binary_upgrade_set_next_array_pg_type_oid', provolatile => 'v',
   proparallel => 'r', prorettype => 'void', proargtypes => 'oid',
   prosrc => 'binary_upgrade_set_next_array_pg_type_oid' },
+{ oid => '4390', descr => 'for use by pg_upgrade',
+  proname => 'binary_upgrade_set_next_multirange_pg_type_oid', provolatile => 'v',
+  proparallel => 'r', prorettype => 'void', proargtypes => 'oid',
+  prosrc => 'binary_upgrade_set_next_multirange_pg_type_oid' },
+{ oid => '4391', descr => 'for use by pg_upgrade',
+  proname => 'binary_upgrade_set_next_multirange_array_pg_type_oid', provolatile => 'v',
+  proparallel => 'r', prorettype => 'void', proargtypes => 'oid',
+  prosrc => 'binary_upgrade_set_next_multirange_array_pg_type_oid' },
 { oid => '3586', descr => 'for use by pg_upgrade',
   proname => 'binary_upgrade_set_next_heap_pg_class_oid', provolatile => 'v',
   proparallel => 'r', prorettype => 'void', proargtypes => 'oid',
diff --git a/src/include/catalog/pg_range.dat b/src/include/catalog/pg_range.dat
index 479754c2455..10060255c95 100644
--- a/src/include/catalog/pg_range.dat
+++ b/src/include/catalog/pg_range.dat
@@ -13,19 +13,22 @@
 [
 
 { rngtypid => 'int4range', rngsubtype => 'int4', rngsubopc => 'btree/int4_ops',
-  rngcanonical => 'int4range_canonical', rngsubdiff => 'int4range_subdiff' },
+  rngcanonical => 'int4range_canonical', rngsubdiff => 'int4range_subdiff',
+  rngmultitypid => 'int4multirange' },
 { rngtypid => 'numrange', rngsubtype => 'numeric',
   rngsubopc => 'btree/numeric_ops', rngcanonical => '-',
-  rngsubdiff => 'numrange_subdiff' },
+  rngsubdiff => 'numrange_subdiff', rngmultitypid => 'nummultirange' },
 { rngtypid => 'tsrange', rngsubtype => 'timestamp',
   rngsubopc => 'btree/timestamp_ops', rngcanonical => '-',
-  rngsubdiff => 'tsrange_subdiff' },
+  rngsubdiff => 'tsrange_subdiff', rngmultitypid => 'tsmultirange' },
 { rngtypid => 'tstzrange', rngsubtype => 'timestamptz',
   rngsubopc => 'btree/timestamptz_ops', rngcanonical => '-',
-  rngsubdiff => 'tstzrange_subdiff' },
+  rngsubdiff => 'tstzrange_subdiff', rngmultitypid => 'tstzmultirange' },
 { rngtypid => 'daterange', rngsubtype => 'date', rngsubopc => 'btree/date_ops',
-  rngcanonical => 'daterange_canonical', rngsubdiff => 'daterange_subdiff' },
+  rngcanonical => 'daterange_canonical', rngsubdiff => 'daterange_subdiff',
+  rngmultitypid => 'datemultirange' },
 { rngtypid => 'int8range', rngsubtype => 'int8', rngsubopc => 'btree/int8_ops',
-  rngcanonical => 'int8range_canonical', rngsubdiff => 'int8range_subdiff' },
+  rngcanonical => 'int8range_canonical', rngsubdiff => 'int8range_subdiff',
+  rngmultitypid => 'int8multirange' },
 
 ]
diff --git a/src/include/catalog/pg_range.h b/src/include/catalog/pg_range.h
index c28bb57b6c9..76ad4000bf7 100644
--- a/src/include/catalog/pg_range.h
+++ b/src/include/catalog/pg_range.h
@@ -34,6 +34,9 @@ CATALOG(pg_range,3541,RangeRelationId)
 	/* OID of range's element type (subtype) */
 	Oid			rngsubtype BKI_LOOKUP(pg_type);
 
+	/* OID of the range's multirange type */
+	Oid			rngmultitypid BKI_LOOKUP(pg_type);
+
 	/* collation for this range type, or 0 */
 	Oid			rngcollation BKI_DEFAULT(0);
 
@@ -57,13 +60,17 @@ typedef FormData_pg_range *Form_pg_range;
 DECLARE_UNIQUE_INDEX(pg_range_rngtypid_index, 3542, on pg_range using btree(rngtypid oid_ops));
 #define RangeTypidIndexId					3542
 
+DECLARE_UNIQUE_INDEX(pg_range_rngmultitypid_index, 2228, on pg_range using btree(rngmultitypid oid_ops));
+#define RangeMultirangeTypidIndexId			2228
+
+
 /*
  * prototypes for functions in pg_range.c
  */
 
 extern void RangeCreate(Oid rangeTypeOid, Oid rangeSubType, Oid rangeCollation,
 						Oid rangeSubOpclass, RegProcedure rangeCanonical,
-						RegProcedure rangeSubDiff);
+						RegProcedure rangeSubDiff, Oid multirangeTypeOid);
 extern void RangeDelete(Oid rangeTypeOid);
 
 #endif							/* PG_RANGE_H */
diff --git a/src/include/catalog/pg_type.dat b/src/include/catalog/pg_type.dat
index 28240bdce39..62018f063a8 100644
--- a/src/include/catalog/pg_type.dat
+++ b/src/include/catalog/pg_type.dat
@@ -496,6 +496,40 @@
   typreceive => 'range_recv', typsend => 'range_send',
   typanalyze => 'range_typanalyze', typalign => 'd', typstorage => 'x' },
 
+# multirange types
+{ oid => '4451', array_type_oid => '8010', descr => 'multirange of integers',
+  typname => 'int4multirange', typlen => '-1', typbyval => 'f', typtype => 'm',
+  typcategory => 'R', typinput => 'multirange_in', typoutput => 'multirange_out',
+  typreceive => 'multirange_recv', typsend => 'multirange_send',
+  typanalyze => 'multirange_typanalyze', typalign => 'i', typstorage => 'x' },
+{ oid => '4532', array_type_oid => '8012', descr => 'multirange of numerics',
+  typname => 'nummultirange', typlen => '-1', typbyval => 'f', typtype => 'm',
+  typcategory => 'R', typinput => 'multirange_in', typoutput => 'multirange_out',
+  typreceive => 'multirange_recv', typsend => 'multirange_send',
+  typanalyze => 'multirange_typanalyze', typalign => 'i', typstorage => 'x' },
+{ oid => '4533', array_type_oid => '8014',
+  descr => 'multirange of timestamps without time zone',
+  typname => 'tsmultirange', typlen => '-1', typbyval => 'f', typtype => 'm',
+  typcategory => 'R', typinput => 'multirange_in', typoutput => 'multirange_out',
+  typreceive => 'multirange_recv', typsend => 'multirange_send',
+  typanalyze => 'multirange_typanalyze', typalign => 'd', typstorage => 'x' },
+{ oid => '4534', array_type_oid => '8016',
+  descr => 'multirange of timestamps with time zone',
+  typname => 'tstzmultirange', typlen => '-1', typbyval => 'f', typtype => 'm',
+  typcategory => 'R', typinput => 'multirange_in', typoutput => 'multirange_out',
+  typreceive => 'multirange_recv', typsend => 'multirange_send',
+  typanalyze => 'multirange_typanalyze', typalign => 'd', typstorage => 'x' },
+{ oid => '4535', array_type_oid => '8018', descr => 'multirange of dates',
+  typname => 'datemultirange', typlen => '-1', typbyval => 'f', typtype => 'm',
+  typcategory => 'R', typinput => 'multirange_in', typoutput => 'multirange_out',
+  typreceive => 'multirange_recv', typsend => 'multirange_send',
+  typanalyze => 'multirange_typanalyze', typalign => 'i', typstorage => 'x' },
+{ oid => '4536', array_type_oid => '8020', descr => 'multirange of bigints',
+  typname => 'int8multirange', typlen => '-1', typbyval => 'f', typtype => 'm',
+  typcategory => 'R', typinput => 'multirange_in', typoutput => 'multirange_out',
+  typreceive => 'multirange_recv', typsend => 'multirange_send',
+  typanalyze => 'multirange_typanalyze', typalign => 'd', typstorage => 'x' },
+
 # pseudo-types
 # types with typtype='p' represent various special cases in the type system.
 # These cannot be used to define table columns, but are valid as function
@@ -626,5 +660,16 @@
   typtype => 'p', typcategory => 'P', typinput => 'anycompatiblerange_in',
   typoutput => 'anycompatiblerange_out', typreceive => '-', typsend => '-',
   typalign => 'd', typstorage => 'x' },
+{ oid => '4537',
+  descr => 'pseudo-type representing a polymorphic base type that is a multirange',
+  typname => 'anymultirange', typlen => '-1', typbyval => 'f', typtype => 'p',
+  typcategory => 'P', typinput => 'anymultirange_in', typoutput => 'anymultirange_out',
+  typreceive => '-', typsend => '-', typalign => 'd', typstorage => 'x' },
+{ oid => '4538',
+  descr => 'pseudo-type representing a multirange over a polymorphic common type',
+  typname => 'anycompatiblemultirange', typlen => '-1', typbyval => 'f',
+  typtype => 'p', typcategory => 'P', typinput => 'anycompatiblemultirange_in',
+  typoutput => 'anycompatiblemultirange_out', typreceive => '-', typsend => '-',
+  typalign => 'd', typstorage => 'x' },
 
 ]
diff --git a/src/include/catalog/pg_type.h b/src/include/catalog/pg_type.h
index 70563a6408b..545b789608a 100644
--- a/src/include/catalog/pg_type.h
+++ b/src/include/catalog/pg_type.h
@@ -276,6 +276,7 @@ DECLARE_UNIQUE_INDEX(pg_type_typname_nsp_index, 2704, on pg_type using btree(typ
 #define  TYPTYPE_COMPOSITE	'c' /* composite (e.g., table's rowtype) */
 #define  TYPTYPE_DOMAIN		'd' /* domain over another type */
 #define  TYPTYPE_ENUM		'e' /* enumerated type */
+#define  TYPTYPE_MULTIRANGE	'm' /* multirange type */
 #define  TYPTYPE_PSEUDO		'p' /* pseudo-type */
 #define  TYPTYPE_RANGE		'r' /* range type */
 
@@ -317,13 +318,15 @@ DECLARE_UNIQUE_INDEX(pg_type_typname_nsp_index, 2704, on pg_type using btree(typ
 	 (typid) == ANYARRAYOID || \
 	 (typid) == ANYNONARRAYOID || \
 	 (typid) == ANYENUMOID || \
-	 (typid) == ANYRANGEOID)
+	 (typid) == ANYRANGEOID || \
+	 (typid) == ANYMULTIRANGEOID)
 
 #define IsPolymorphicTypeFamily2(typid)  \
 	((typid) == ANYCOMPATIBLEOID || \
 	 (typid) == ANYCOMPATIBLEARRAYOID || \
 	 (typid) == ANYCOMPATIBLENONARRAYOID || \
-	 (typid) == ANYCOMPATIBLERANGEOID)
+	 (typid) == ANYCOMPATIBLERANGEOID || \
+	 (typid) == ANYCOMPATIBLEMULTIRANGEOID)
 
 /* Is this a "true" array type?  (Requires fmgroids.h) */
 #define IsTrueArrayType(typeForm)  \
@@ -397,4 +400,7 @@ extern char *makeArrayTypeName(const char *typeName, Oid typeNamespace);
 extern bool moveArrayTypeName(Oid typeOid, const char *typeName,
 							  Oid typeNamespace);
 
+extern char *makeMultirangeTypeName(const char *rangeTypeName,
+									Oid typeNamespace);
+
 #endif							/* PG_TYPE_H */
diff --git a/src/include/commands/typecmds.h b/src/include/commands/typecmds.h
index 23130895af4..989914dfe11 100644
--- a/src/include/commands/typecmds.h
+++ b/src/include/commands/typecmds.h
@@ -29,6 +29,8 @@ extern ObjectAddress DefineRange(CreateRangeStmt *stmt);
 extern ObjectAddress AlterEnum(AlterEnumStmt *stmt);
 extern ObjectAddress DefineCompositeType(RangeVar *typevar, List *coldeflist);
 extern Oid	AssignTypeArrayOid(void);
+extern Oid	AssignTypeMultirangeOid(void);
+extern Oid	AssignTypeMultirangeArrayOid(void);
 
 extern ObjectAddress AlterDomainDefault(List *names, Node *defaultRaw);
 extern ObjectAddress AlterDomainNotNull(List *names, bool notNull);
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)