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, 810 insertions, 31 deletions

diff --git a/doc/src/sgml/catalogs.sgml b/doc/src/sgml/catalogs.sgml
index 89ca59b92b5..d9886360467 100644
--- a/doc/src/sgml/catalogs.sgml
+++ b/doc/src/sgml/catalogs.sgml
@@ -6239,6 +6239,16 @@ SCRAM-SHA-256$<replaceable>&lt;iteration count&gt;</replaceable>:<replaceable>&l
 
      <row>
       <entry role="catalog_table_entry"><para role="column_definition">
+       <structfield>rngmultitypid</structfield> <type>oid</type>
+       (references <link linkend="catalog-pg-type"><structname>pg_type</structname></link>.<structfield>oid</structfield>)
+      </para>
+      <para>
+       OID of the multirange type for this range type
+      </para></entry>
+     </row>
+
+     <row>
+      <entry role="catalog_table_entry"><para role="column_definition">
        <structfield>rngcollation</structfield> <type>oid</type>
        (references <link linkend="catalog-pg-collation"><structname>pg_collation</structname></link>.<structfield>oid</structfield>)
       </para>
@@ -8671,8 +8681,9 @@ SCRAM-SHA-256$<replaceable>&lt;iteration count&gt;</replaceable>:<replaceable>&l
        <literal>c</literal> for a composite type (e.g., a table's row type),
        <literal>d</literal> for a domain,
        <literal>e</literal> for an enum type,
-       <literal>p</literal> for a pseudo-type, or
-       <literal>r</literal> for a range type.
+       <literal>p</literal> for a pseudo-type,
+       <literal>r</literal> for a range type, or
+       <literal>m</literal> for a multirange type.
        See also <structfield>typrelid</structfield> and
        <structfield>typbasetype</structfield>.
       </para></entry>
diff --git a/doc/src/sgml/datatype.sgml b/doc/src/sgml/datatype.sgml
index 9eb19a1c616..58d168c763e 100644
--- a/doc/src/sgml/datatype.sgml
+++ b/doc/src/sgml/datatype.sgml
@@ -4908,6 +4908,10 @@ SELECT * FROM pg_attribute
    </indexterm>
 
    <indexterm zone="datatype-pseudo">
+    <primary>anymultirange</primary>
+   </indexterm>
+
+   <indexterm zone="datatype-pseudo">
     <primary>anycompatible</primary>
    </indexterm>
 
@@ -4924,6 +4928,10 @@ SELECT * FROM pg_attribute
    </indexterm>
 
    <indexterm zone="datatype-pseudo">
+    <primary>anycompatiblemultirange</primary>
+   </indexterm>
+
+   <indexterm zone="datatype-pseudo">
     <primary>void</primary>
    </indexterm>
 
@@ -5035,6 +5043,13 @@ SELECT * FROM pg_attribute
        </row>
 
        <row>
+        <entry><type>anymultirange</type></entry>
+        <entry>Indicates that a function accepts any multirange data type
+        (see <xref linkend="extend-types-polymorphic"/> and
+        <xref linkend="rangetypes"/>).</entry>
+       </row>
+
+       <row>
         <entry><type>anycompatible</type></entry>
         <entry>Indicates that a function accepts any data type,
         with automatic promotion of multiple arguments to a common data type
@@ -5064,6 +5079,14 @@ SELECT * FROM pg_attribute
        </row>
 
        <row>
+        <entry><type>anycompatiblemultirange</type></entry>
+        <entry>Indicates that a function accepts any multirange data type,
+        with automatic promotion of multiple arguments to a common data type
+        (see <xref linkend="extend-types-polymorphic"/> and
+        <xref linkend="rangetypes"/>).</entry>
+       </row>
+
+       <row>
         <entry><type>cstring</type></entry>
         <entry>Indicates that a function accepts or returns a null-terminated C string.</entry>
        </row>
diff --git a/doc/src/sgml/extend.sgml b/doc/src/sgml/extend.sgml
index 1c37026bb05..6e3d82b85b8 100644
--- a/doc/src/sgml/extend.sgml
+++ b/doc/src/sgml/extend.sgml
@@ -289,6 +289,14 @@
        </row>
 
        <row>
+        <entry><type>anymultirange</type></entry>
+        <entry>Simple</entry>
+        <entry>Indicates that a function accepts any multirange data type
+        (see <xref linkend="rangetypes"/>)
+        </entry>
+       </row>
+
+       <row>
         <entry><type>anycompatible</type></entry>
         <entry>Common</entry>
         <entry>Indicates that a function accepts any data type,
@@ -319,6 +327,14 @@
         with automatic promotion of multiple arguments to a common data type
         </entry>
        </row>
+
+       <row>
+        <entry><type>anycompatiblemultirange</type></entry>
+        <entry>Common</entry>
+        <entry>Indicates that a function accepts any multirange data type,
+        with automatic promotion of multiple arguments to a common data type
+        </entry>
+       </row>
       </tbody>
      </tgroup>
     </table>
@@ -346,17 +362,15 @@
      position declared as <type>anyarray</type> can have any array data type,
      but similarly they must all be the same type.  And similarly,
      positions declared as <type>anyrange</type> must all be the same range
-     type.  Furthermore, if there are
+     type.  Likewise for <type>anymultirange</type>.
+    </para>
+
+    <para>
+     Furthermore, if there are
      positions declared <type>anyarray</type> and others declared
      <type>anyelement</type>, the actual array type in the
      <type>anyarray</type> positions must be an array whose elements are
      the same type appearing in the <type>anyelement</type> positions.
-     Similarly, if there are positions declared <type>anyrange</type>
-     and others declared <type>anyelement</type> or <type>anyarray</type>,
-     the actual range type in the <type>anyrange</type> positions must be a
-     range whose subtype is the same type appearing in
-     the <type>anyelement</type> positions and the same as the element type
-     of the <type>anyarray</type> positions.
      <type>anynonarray</type> is treated exactly the same as <type>anyelement</type>,
      but adds the additional constraint that the actual type must not be
      an array type.
@@ -366,6 +380,19 @@
     </para>
 
     <para>
+     Similarly, if there are positions declared <type>anyrange</type>
+     and others declared <type>anyelement</type> or <type>anyarray</type>,
+     the actual range type in the <type>anyrange</type> positions must be a
+     range whose subtype is the same type appearing in
+     the <type>anyelement</type> positions and the same as the element type
+     of the <type>anyarray</type> positions.
+     If there are positions declared <type>anymultirange</type>,
+     their actual multirange type must contain ranges matching parameters declared
+     <type>anyrange</type> and base elements matching parameters declared
+     <type>anyelement</type> and <type>anyarray</type>.
+    </para>
+
+    <para>
      Thus, when more than one argument position is declared with a polymorphic
      type, the net effect is that only certain combinations of actual argument
      types are allowed.  For example, a function declared as
@@ -420,7 +447,8 @@
      Selection of the common type considers the actual types
      of <type>anycompatible</type> and <type>anycompatiblenonarray</type>
      inputs, the array element types of <type>anycompatiblearray</type>
-     inputs, and the range subtypes of <type>anycompatiblerange</type>
+     inputs, the range subtypes of <type>anycompatiblerange</type> inputs,
+     and the multirange subtypes of <type>anycompatiablemultirange</type>
      inputs.  If <type>anycompatiblenonarray</type> is present then the
      common type is required to be a non-array type.  Once a common type is
      identified, arguments in <type>anycompatible</type>
@@ -431,12 +459,15 @@
 
     <para>
      Since there is no way to select a range type knowing only its subtype,
-     use of <type>anycompatiblerange</type> requires that all arguments
-     declared with that type have the same actual range type, and that that
-     type's subtype agree with the selected common type, so that no casting
-     of the range values is required.  As with <type>anyrange</type>, use
-     of <type>anycompatiblerange</type> as a function result type requires
-     that there be an <type>anycompatiblerange</type> argument.
+     use of <type>anycompatiblerange</type> and/or
+     <type>anycompatiblemultirange</type> requires that all arguments declared
+     with that type have the same actual range and/or multirange type, and that
+     that type's subtype agree with the selected common type, so that no casting
+     of the range values is required.  As with <type>anyrange</type> and
+     <type>anymultirange</type>, use of <type>anycompatiblerange</type> and
+     <type>anymultirange</type> as a function result type requires that there be
+     an <type>anycompatiblerange</type> or <type>anycompatiblemultirange</type>
+     argument.
     </para>
 
     <para>
diff --git a/doc/src/sgml/func.sgml b/doc/src/sgml/func.sgml
index df29af6371a..d5cd705eebb 100644
--- a/doc/src/sgml/func.sgml
+++ b/doc/src/sgml/func.sgml
@@ -17884,12 +17884,15 @@ SELECT NULLIF(value, '(none)') ...
   <para>
    <xref linkend="range-operators-table"/> shows the specialized operators
    available for range types.
+   <xref linkend="multirange-operators-table"/> shows the specialized operators
+   available for multirange types.
    In addition to those, the usual comparison operators shown in
    <xref linkend="functions-comparison-op-table"/> are available for range
-   types.  The comparison operators order first by the range lower bounds, and
-   only if those are equal do they compare the upper bounds.  This does not
-   usually result in a useful overall ordering, but the operators are provided
-   to allow unique indexes to be constructed on ranges.
+   and multirange types.  The comparison operators order first by the range lower
+   bounds, and only if those are equal do they compare the upper bounds.  The
+   multirange operators compare each range until one is unequal. This
+   does not usually result in a useful overall ordering, but the operators are
+   provided to allow unique indexes to be constructed on ranges.
   </para>
 
    <table id="range-operators-table">
@@ -18099,15 +18102,449 @@ SELECT NULLIF(value, '(none)') ...
     </tgroup>
    </table>
 
+   <table id="multirange-operators-table">
+    <title>Multirange Operators</title>
+    <tgroup cols="1">
+     <thead>
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        Operator
+       </para>
+       <para>
+        Description
+       </para>
+       <para>
+        Example(s)
+       </para></entry>
+      </row>
+     </thead>
+
+     <tbody>
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>@&gt;</literal> <type>anymultirange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Does the first multirange contain the second?
+       </para>
+       <para>
+        <literal>'{[2,4)}'::int4multirange @&gt; '{[2,3)}'::int4multirange</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>@&gt;</literal> <type>anyrange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Does the multirange contain the range?
+       </para>
+       <para>
+        <literal>'{[2,4)}'::int4multirange @&gt; int4range(2,3)</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>@&gt;</literal> <type>anyelement</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Does the multirange contain the element?
+       </para>
+       <para>
+        <literal>'{[2011-01-01,2011-03-01)}'::tsmultirange @&gt; '2011-01-10'::timestamp</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>&lt;@</literal> <type>anymultirange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Is the first multirange contained by the second?
+       </para>
+       <para>
+        <literal>'{[2,4)}'::int4multirange &lt;@ '{[1,7)}'::int4multirange</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>&lt;@</literal> <type>anyrange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Is the multirange contained by the range?
+       </para>
+       <para>
+        <literal>'{[2,4)}'::int4multirange &lt;@ int4range(1,7)</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anyrange</type> <literal>&lt;@</literal> <type>anymultirange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Is the range contained by the multirange?
+       </para>
+       <para>
+        <literal>int4range(2,4) &lt;@ '{[1,7)}'::int4multirange</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anyelement</type> <literal>&lt;@</literal> <type>anymultirange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Is the element contained by the multirange?
+       </para>
+       <para>
+        <literal>42 &lt;@ '{[1,7)}'::int4multirange</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>&amp;&amp;</literal> <type>anymultirange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Do the multiranges overlap, that is, have any elements in common?
+       </para>
+       <para>
+        <literal>'{[3,7)}'::int8multirange &amp;&amp; '{[4,12)}'::int8multirange</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>&amp;&amp;</literal> <type>anyrange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Does the multirange overlap the range?
+       </para>
+       <para>
+        <literal>'{[3,7)}'::int8multirange &amp;&amp; int8range(4,12)</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anyrange</type> <literal>&amp;&amp;</literal> <type>anymultirange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Does the range overlap the multirange?
+       </para>
+       <para>
+        <literal>int8range(3,7) &amp;&amp; '{[4,12)}'::int8multirange</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>&lt;&lt;</literal> <type>anymultirange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Is the first multirange strictly left of the second?
+       </para>
+       <para>
+        <literal>'{[1,10)}'::int8multirange &lt;&lt; '{[100,110)}'::int8multirange</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>&lt;&lt;</literal> <type>anyrange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Is the multirange strictly left of the range?
+       </para>
+       <para>
+        <literal>'{[1,10)}'::int8multirange &lt;&lt; int8range(100,110)</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anyrange</type> <literal>&lt;&lt;</literal> <type>anymultirange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Is the range strictly left of the multirange?
+       </para>
+       <para>
+        <literal>int8range(1,10) &lt;&lt; '{[100,110)}'::int8multirange</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>&gt;&gt;</literal> <type>anymultirange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Is the first multirange strictly right of the second?
+       </para>
+       <para>
+        <literal>'{[50,60)}'::int8multirange &gt;&gt; '{[20,30)}'::int8multirange</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>&gt;&gt;</literal> <type>anyrange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Is the multirange strictly right of the range?
+       </para>
+       <para>
+        <literal>'{[50,60)}'::int8multirange &gt;&gt; int8range(20,30)</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anyrange</type> <literal>&gt;&gt;</literal> <type>anymultirange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Is the range strictly right of the multirange?
+       </para>
+       <para>
+        <literal>int8range(50,60) &gt;&gt; '{[20,30)}'::int8multirange</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>&amp;&lt;</literal> <type>anymultirange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Does the first multirange not extend to the right of the second?
+       </para>
+       <para>
+        <literal>'{[1,20)}'::int8multirange &amp;&lt; '{[18,20)}'::int8multirange</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>&amp;&lt;</literal> <type>anyrange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Does the multirange not extend to the right of the range?
+       </para>
+       <para>
+        <literal>'{[1,20)}'::int8multirange &amp;&lt; int8range(18,20)</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anyrange</type> <literal>&amp;&lt;</literal> <type>anymultirange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Does the range not extend to the right of the multirange?
+       </para>
+       <para>
+        <literal>int8range(1,20) &amp;&lt; '{[18,20)}'::int8multirange</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>&amp;&gt;</literal> <type>anymultirange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Does the first multirange not extend to the left of the second?
+       </para>
+       <para>
+        <literal>'{[7,20)}'::int8multirange &amp;&gt; '{[5,10)}'::int8multirange</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>&amp;&gt;</literal> <type>anyrange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Does the multirange not extend to the left of the range?
+       </para>
+       <para>
+        <literal>'{[7,20)}'::int8multirange &amp;&gt; int8range(5,10)</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anyrange</type> <literal>&amp;&gt;</literal> <type>anymultirange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Does the range not extend to the left of the multirange?
+       </para>
+       <para>
+        <literal>int8range(7,20) &amp;&gt; '{[5,10)}'::int8multirange</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>-|-</literal> <type>anymultirange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Are the multiranges adjacent?
+       </para>
+       <para>
+        <literal>'{[1.1,2.2)}'::nummultirange -|- '{[2.2,3.3)}'::nummultirange</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>-|-</literal> <type>anyrange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Is the multirange adjacent to the range?
+       </para>
+       <para>
+        <literal>'{[1.1,2.2)}'::nummultirange -|- numrange(2.2,3.3)</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anyrange</type> <literal>-|-</literal> <type>anymultirange</type>
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Is the range adjacent to the multirange?
+       </para>
+       <para>
+        <literal>numrange(1.1,2.2) -|- '{[2.2,3.3)}'::nummultirange</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>+</literal> <type>anymultirange</type>
+        <returnvalue>anymultirange</returnvalue>
+       </para>
+       <para>
+        Computes the union of the multiranges.  The multiranges need not overlap
+        or be adjacent.
+       </para>
+       <para>
+        <literal>'{[5,10)}'::nummultirange + '{[15,20)}'::nummultirange</literal>
+        <returnvalue>{[5,10), [15,20)}</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>*</literal> <type>anymultirange</type>
+        <returnvalue>anymultirange</returnvalue>
+       </para>
+       <para>
+        Computes the intersection of the multiranges.
+       </para>
+       <para>
+        <literal>'{[5,15)}'::int8multirange * '{[10,20)}'::int8multirange</literal>
+        <returnvalue>{[10,15)}</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <type>anymultirange</type> <literal>-</literal> <type>anymultirange</type>
+        <returnvalue>anymultirange</returnvalue>
+       </para>
+       <para>
+        Computes the difference of the multiranges.
+       </para>
+       <para>
+        <literal>'{[5,20)}'::int8multirange - '{[10,15)}'::int8multirange</literal>
+        <returnvalue>{[5,10), [15,20)}</returnvalue>
+       </para></entry>
+      </row>
+     </tbody>
+    </tgroup>
+   </table>
+
   <para>
    The left-of/right-of/adjacent operators always return false when an empty
-   range is involved; that is, an empty range is not considered to be either
-   before or after any other range.
+   range or multirange is involved; that is, an empty range is not considered to
+   be either before or after any other range.
+  </para>
+
+  <para>
+   Elsewhere empty ranges and multiranges are treated as the additive identity:
+   anything unioned with an empty value is itself. Anything minus an empty
+   value is itself. An empty multirange has exactly the same points as an empty
+   range. Every range contains the empty range. Every multirange contains as many
+   empty ranges as you like.
+  </para>
+
+  <para>
+   The range union and difference operators will fail if the resulting range would
+   need to contain two disjoint sub-ranges, as such a range cannot be
+   represented. There are separate operators for union and difference that take
+   multirange parameters and return a multirange, and they do not fail even if
+   their arguments are disjoint. So if you need a union or difference operation
+   for ranges that may be disjoint, you can avoid errors by first casting your
+   ranges to multiranges.
   </para>
 
   <para>
    <xref linkend="range-functions-table"/> shows the functions
    available for use with range types.
+   <xref linkend="multirange-functions-table"/> shows the functions
+   available for use with multirange types.
   </para>
 
    <table id="range-functions-table">
@@ -18269,10 +18706,185 @@ SELECT NULLIF(value, '(none)') ...
     </tgroup>
    </table>
 
+   <table id="multirange-functions-table">
+    <title>Multirange Functions</title>
+    <tgroup cols="1">
+     <thead>
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        Function
+       </para>
+       <para>
+        Description
+       </para>
+       <para>
+        Example(s)
+       </para></entry>
+      </row>
+     </thead>
+     <tbody>
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <indexterm>
+         <primary>lower</primary>
+        </indexterm>
+        <function>lower</function> ( <type>anymultirange</type> )
+        <returnvalue>anyelement</returnvalue>
+       </para>
+       <para>
+        Extracts the lower bound of the multirange (<literal>NULL</literal> if the
+        multirange is empty or the lower bound is infinite).
+       </para>
+       <para>
+        <literal>lower('{[1.1,2.2)}'::nummultirange)</literal>
+        <returnvalue>1.1</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <indexterm>
+         <primary>upper</primary>
+        </indexterm>
+        <function>upper</function> ( <type>anymultirange</type> )
+        <returnvalue>anyelement</returnvalue>
+       </para>
+       <para>
+        Extracts the upper bound of the multirange (<literal>NULL</literal> if the
+        multirange is empty or the upper bound is infinite).
+       </para>
+       <para>
+        <literal>upper('{[1.1,2.2)}'::nummultirange)</literal>
+        <returnvalue>2.2</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <indexterm>
+         <primary>isempty</primary>
+        </indexterm>
+        <function>isempty</function> ( <type>anymultirange</type> )
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Is the multirange empty?
+       </para>
+       <para>
+        <literal>isempty('{[1.1,2.2)}'::nummultirange)</literal>
+        <returnvalue>f</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <indexterm>
+         <primary>lower_inc</primary>
+        </indexterm>
+        <function>lower_inc</function> ( <type>anymultirange</type> )
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Is the multirange's lower bound inclusive?
+       </para>
+       <para>
+        <literal>lower_inc('{[1.1,2.2)}'::nummultirange)</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <indexterm>
+         <primary>upper_inc</primary>
+        </indexterm>
+        <function>upper_inc</function> ( <type>anymultirange</type> )
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Is the multirange's upper bound inclusive?
+       </para>
+       <para>
+        <literal>upper_inc('{[1.1,2.2)}'::nummultirange)</literal>
+        <returnvalue>f</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <indexterm>
+         <primary>lower_inf</primary>
+        </indexterm>
+        <function>lower_inf</function> ( <type>anymultirange</type> )
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Is the multirange's lower bound infinite?
+       </para>
+       <para>
+        <literal>lower_inf('{(,)}'::datemultirange)</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <indexterm>
+         <primary>upper_inf</primary>
+        </indexterm>
+        <function>upper_inf</function> ( <type>anymultirange</type> )
+        <returnvalue>boolean</returnvalue>
+       </para>
+       <para>
+        Is the multirange's upper bound infinite?
+       </para>
+       <para>
+        <literal>upper_inf('{(,)}'::datemultirange)</literal>
+        <returnvalue>t</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <indexterm>
+         <primary>range_merge</primary>
+        </indexterm>
+        <function>range_merge</function> ( <type>anymultirange</type> )
+        <returnvalue>anyrange</returnvalue>
+       </para>
+       <para>
+        Computes the smallest range that includes the entire multirange.
+       </para>
+       <para>
+        <literal>range_merge('{[1,2), [3,4)}'::int4multirange)</literal>
+        <returnvalue>[1,4)</returnvalue>
+       </para></entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <indexterm>
+         <primary>multirange</primary>
+        </indexterm>
+        <function>multirange</function> ( <type>anyrange</type> )
+        <returnvalue>anymultirange</returnvalue>
+       </para>
+       <para>
+        Returns a multirange containing just the given range.
+       </para>
+       <para>
+        <literal>multirange('[1,2)'::int4range)</literal>
+        <returnvalue>{[1,2)}</returnvalue>
+       </para></entry>
+      </row>
+     </tbody>
+    </tgroup>
+   </table>
+
   <para>
    The <function>lower_inc</function>, <function>upper_inc</function>,
    <function>lower_inf</function>, and <function>upper_inf</function>
-   functions all return false for an empty range.
+   functions all return false for an empty range or multirange.
   </para>
   </sect1>
 
@@ -18607,6 +19219,36 @@ SELECT NULLIF(value, '(none)') ...
       <row>
        <entry role="func_table_entry"><para role="func_signature">
         <indexterm>
+         <primary>range_agg</primary>
+        </indexterm>
+        <function>range_agg</function> ( <parameter>value</parameter>
+         <type>anyrange</type> )
+        <returnvalue>anymultirange</returnvalue>
+       </para>
+       <para>
+        Computes the union of the non-null input values.
+       </para></entry>
+       <entry>No</entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <indexterm>
+         <primary>range_intersect_agg</primary>
+        </indexterm>
+        <function>range_intersect_agg</function> ( <parameter>value</parameter>
+         <type>anyrange</type> )
+        <returnvalue>anymultirange</returnvalue>
+       </para>
+       <para>
+        Computes the intersection of the non-null input values.
+       </para></entry>
+       <entry>No</entry>
+      </row>
+
+      <row>
+       <entry role="func_table_entry"><para role="func_signature">
+        <indexterm>
          <primary>string_agg</primary>
         </indexterm>
         <function>string_agg</function> ( <parameter>value</parameter>
diff --git a/doc/src/sgml/rangetypes.sgml b/doc/src/sgml/rangetypes.sgml
index b75fb3a3929..83aa9bc4e9e 100644
--- a/doc/src/sgml/rangetypes.sgml
+++ b/doc/src/sgml/rangetypes.sgml
@@ -27,40 +27,53 @@
   ranges from an instrument, and so forth can also be useful.
  </para>
 
+ <para>
+  Every range type has a corresponding multirange type. A multirange is
+  an ordered list of non-continguous, non-empty, non-null ranges. Most
+  range operators also work on multiranges, and they have a few functions
+  of their own.
+ </para>
+
  <sect2 id="rangetypes-builtin">
-  <title>Built-in Range Types</title>
+  <title>Built-in Range and Multirange Types</title>
 
  <para>
   PostgreSQL comes with the following built-in range types:
   <itemizedlist>
     <listitem>
       <para>
-       <type>int4range</type> &mdash; Range of <type>integer</type>
+       <type>int4range</type> &mdash; Range of <type>integer</type>,
+       <type>int4multirange</type> &mdash; corresponding Multirange
       </para>
     </listitem>
     <listitem>
       <para>
-       <type>int8range</type> &mdash; Range of <type>bigint</type>
+       <type>int8range</type> &mdash; Range of <type>bigint</type>,
+       <type>int8multirange</type> &mdash; corresponding Multirange
       </para>
     </listitem>
     <listitem>
       <para>
-       <type>numrange</type> &mdash; Range of <type>numeric</type>
+       <type>numrange</type> &mdash; Range of <type>numeric</type>,
+       <type>nummultirange</type> &mdash; corresponding Multirange
       </para>
     </listitem>
     <listitem>
       <para>
-       <type>tsrange</type> &mdash; Range of <type>timestamp without time zone</type>
+       <type>tsrange</type> &mdash; Range of <type>timestamp without time zone</type>,
+       <type>tsmultirange</type> &mdash; corresponding Multirange
       </para>
     </listitem>
     <listitem>
       <para>
-       <type>tstzrange</type> &mdash; Range of <type>timestamp with time zone</type>
+       <type>tstzrange</type> &mdash; Range of <type>timestamp with time zone</type>,
+       <type>tstzmultirange</type> &mdash; corresponding Multirange
       </para>
     </listitem>
     <listitem>
       <para>
-       <type>daterange</type> &mdash; Range of <type>date</type>
+       <type>daterange</type> &mdash; Range of <type>date</type>,
+       <type>datemultirange</type> &mdash; corresponding Multirange
       </para>
     </listitem>
   </itemizedlist>
@@ -232,10 +245,30 @@ SELECT '[4,4]'::int4range;
 SELECT '[4,4)'::int4range;
 </programlisting>
   </para>
+
+  <para>
+   The input for a multirange is curly brackets (<literal>{</literal> and
+   <literal>}</literal>) containing zero or more valid ranges,
+   separated by commas. Whitespace is permitted around the brackets and
+   commas. This is intended to be reminiscent of array syntax, although
+   multiranges are much simpler: they have just one dimension and there is
+   no need to quote their contents. (The bounds of their ranges may be
+   quoted as above however.)
+  </para>
+
+  <para>
+  Examples:
+<programlisting>
+SELECT '{}'::int4multirange;
+SELECT '{[3,7)}'::int4multirange;
+SELECT '{[3,7), [8,9)}'::int4multirange;
+</programlisting>
+  </para>
+
  </sect2>
 
  <sect2 id="rangetypes-construct">
-  <title>Constructing Ranges</title>
+  <title>Constructing Ranges and Multiranges</title>
 
   <para>
    Each range type has a constructor function with the same name as the range
@@ -269,6 +302,19 @@ SELECT int8range(1, 14, '(]');
 SELECT numrange(NULL, 2.2);
 </programlisting>
   </para>
+
+  <para>
+   Each range type also has a multirange constructor with the same name as the
+   multirange type.  The constructor function takes zero or more arguments
+   which are all ranges of the appropriate type.
+   For example:
+
+<programlisting>
+SELECT nummultirange();
+SELECT nummultirange(numrange(1.0, 14.0));
+SELECT nummultirange(numrange(1.0, 14.0), numrange(20.0, 25.0));
+</programlisting>
+  </para>
  </sect2>
 
  <sect2 id="rangetypes-discrete">
@@ -342,6 +388,11 @@ SELECT '[1.234, 5.678]'::floatrange;
   </para>
 
   <para>
+   When you define your own range you automatically get a corresponding
+   multirange type.
+  </para>
+
+  <para>
    Defining your own range type also allows you to specify a different
    subtype B-tree operator class or collation to use, so as to change the sort
    ordering that determines which values fall into a given range.
diff --git a/doc/src/sgml/ref/create_type.sgml b/doc/src/sgml/ref/create_type.sgml
index d575f166142..7d2d6aa0af8 100644
--- a/doc/src/sgml/ref/create_type.sgml
+++ b/doc/src/sgml/ref/create_type.sgml
@@ -33,6 +33,7 @@ CREATE TYPE <replaceable class="parameter">name</replaceable> AS RANGE (
     [ , COLLATION = <replaceable class="parameter">collation</replaceable> ]
     [ , CANONICAL = <replaceable class="parameter">canonical_function</replaceable> ]
     [ , SUBTYPE_DIFF = <replaceable class="parameter">subtype_diff_function</replaceable> ]
+    [ , MULTIRANGE_TYPE_NAME = <replaceable class="parameter">multirange_type_name</replaceable> ]
 )
 
 CREATE TYPE <replaceable class="parameter">name</replaceable> (
@@ -174,6 +175,17 @@ CREATE TYPE <replaceable class="parameter">name</replaceable>
     the range type.  See <xref linkend="rangetypes-defining"/> for more
     information.
    </para>
+
+   <para>
+    The optional <replaceable class="parameter">multirange_type_name</replaceable>
+    parameter specifies the name of the corresponding multirange type.  If not
+    specified, this name is chosen automatically as follows.
+    If range type name contains <literal>range</literal> substring, then
+    multirange type name is formed by replacement of the <literal>range</literal>
+    substring with <literal>multirange</literal> substring in the range
+    type name.  Otherwise, multirange type name is formed by appending
+    <literal>_multirange</literal> suffix to the range type name.
+   </para>
   </refsect2>
 
   <refsect2>
@@ -631,6 +643,15 @@ CREATE TYPE <replaceable class="parameter">name</replaceable>
    </varlistentry>
 
    <varlistentry>
+    <term><replaceable class="parameter">multirange_type_name</replaceable></term>
+    <listitem>
+     <para>
+      The name of the corresponding multirange type.
+     </para>
+    </listitem>
+   </varlistentry>
+
+   <varlistentry>
     <term><replaceable class="parameter">input_function</replaceable></term>
     <listitem>
      <para>