Add temporal PRIMARY KEY and UNIQUE constraints

Add WITHOUT OVERLAPS clause to PRIMARY KEY and UNIQUE constraints.
These are backed by GiST indexes instead of B-tree indexes, since they
are essentially exclusion constraints with = for the scalar parts of
the key and && for the temporal part.

Author: Paul A. Jungwirth <pj@illuminatedcomputing.com>
Reviewed-by: Peter Eisentraut <peter@eisentraut.org>
Reviewed-by: jian he <jian.universality@gmail.com>
Discussion: https://www.postgresql.org/message-id/flat/CA+renyUApHgSZF9-nd-a0+OPGharLQLO=mDHcY4_qQ0+noCUVg@mail.gmail.com

3 files changed, 59 insertions, 10 deletions

diff --git a/doc/src/sgml/catalogs.sgml b/doc/src/sgml/catalogs.sgml
index c15d861e823..16b94461b2c 100644
--- a/doc/src/sgml/catalogs.sgml
+++ b/doc/src/sgml/catalogs.sgml
@@ -2711,6 +2711,16 @@ SCRAM-SHA-256$<replaceable>&lt;iteration count&gt;</replaceable>:<replaceable>&l
 
      <row>
       <entry role="catalog_table_entry"><para role="column_definition">
+       <structfield>conwithoutoverlaps</structfield> <type>bool</type>
+      </para>
+      <para>
+       This constraint is defined with <literal>WITHOUT OVERLAPS</literal>
+       (for primary keys and unique constraints).
+      </para></entry>
+     </row>
+
+     <row>
+      <entry role="catalog_table_entry"><para role="column_definition">
        <structfield>conkey</structfield> <type>int2[]</type>
        (references <link linkend="catalog-pg-attribute"><structname>pg_attribute</structname></link>.<structfield>attnum</structfield>)
       </para>
diff --git a/doc/src/sgml/gist.sgml b/doc/src/sgml/gist.sgml
index 7c20f8467b4..8a19f156d83 100644
--- a/doc/src/sgml/gist.sgml
+++ b/doc/src/sgml/gist.sgml
@@ -298,7 +298,8 @@ CREATE INDEX ON my_table USING GIST (my_inet_column inet_ops);
    The optional twelfth method <function>stratnum</function> is used to
    translate well-known <literal>RT*StrategyNumber</literal>s (from
    <filename>src/include/access/stratnum.h</filename>) into strategy numbers
-   used by the operator class.
+   used by the operator class.  This lets the core code look up operators for
+   temporal constraint indexes.
  </para>
 
  <variablelist>
@@ -1186,6 +1187,17 @@ my_sortsupport(PG_FUNCTION_ARGS)
       </para>
 
       <para>
+       This is used for temporal index constraints (i.e., <literal>PRIMARY
+       KEY</literal> and <literal>UNIQUE</literal>).  If the operator class
+       provides this function and it returns results for
+       <literal>RTEqualStrategyNumber</literal>, it can be used in the
+       non-<literal>WITHOUT OVERLAPS</literal> part(s) of an index constraint.
+       If it returns results for <literal>RTOverlapStrategyNumber</literal>,
+       the operator class can be used in the <literal>WITHOUT
+       OVERLAPS</literal> part of an index constraint.
+      </para>
+
+      <para>
        The <acronym>SQL</acronym> declaration of the function must look like
        this:
 
diff --git a/doc/src/sgml/ref/create_table.sgml b/doc/src/sgml/ref/create_table.sgml
index e04a0692c4e..079af9126ad 100644
--- a/doc/src/sgml/ref/create_table.sgml
+++ b/doc/src/sgml/ref/create_table.sgml
@@ -78,8 +78,8 @@ CREATE [ [ GLOBAL | LOCAL ] { TEMPORARY | TEMP } | UNLOGGED ] TABLE [ IF NOT EXI
 [ CONSTRAINT <replaceable class="parameter">constraint_name</replaceable> ]
 { CHECK ( <replaceable class="parameter">expression</replaceable> ) [ NO INHERIT ] |
   NOT NULL <replaceable class="parameter">column_name</replaceable> [ NO INHERIT ] |
-  UNIQUE [ NULLS [ NOT ] DISTINCT ] ( <replaceable class="parameter">column_name</replaceable> [, ... ] ) <replaceable class="parameter">index_parameters</replaceable> |
-  PRIMARY KEY ( <replaceable class="parameter">column_name</replaceable> [, ... ] ) <replaceable class="parameter">index_parameters</replaceable> |
+  UNIQUE [ NULLS [ NOT ] DISTINCT ] ( <replaceable class="parameter">column_name</replaceable> [, ... ] [, <replaceable class="parameter">column_name</replaceable> WITHOUT OVERLAPS ] ) <replaceable class="parameter">index_parameters</replaceable> |
+  PRIMARY KEY ( <replaceable class="parameter">column_name</replaceable> [, ... ] [, <replaceable class="parameter">column_name</replaceable> WITHOUT OVERLAPS ] ) <replaceable class="parameter">index_parameters</replaceable> |
   EXCLUDE [ USING <replaceable class="parameter">index_method</replaceable> ] ( <replaceable class="parameter">exclude_element</replaceable> WITH <replaceable class="parameter">operator</replaceable> [, ... ] ) <replaceable class="parameter">index_parameters</replaceable> [ WHERE ( <replaceable class="parameter">predicate</replaceable> ) ] |
   FOREIGN KEY ( <replaceable class="parameter">column_name</replaceable> [, ... ] ) REFERENCES <replaceable class="parameter">reftable</replaceable> [ ( <replaceable class="parameter">refcolumn</replaceable> [, ... ] ) ]
     [ MATCH FULL | MATCH PARTIAL | MATCH SIMPLE ] [ ON DELETE <replaceable
@@ -965,7 +965,7 @@ WITH ( MODULUS <replaceable class="parameter">numeric_literal</replaceable>, REM
 
    <varlistentry id="sql-createtable-parms-unique">
     <term><literal>UNIQUE [ NULLS [ NOT ] DISTINCT ]</literal> (column constraint)</term>
-    <term><literal>UNIQUE [ NULLS [ NOT ] DISTINCT ] ( <replaceable class="parameter">column_name</replaceable> [, ... ] )</literal>
+    <term><literal>UNIQUE [ NULLS [ NOT ] DISTINCT ] ( <replaceable class="parameter">column_name</replaceable> [, ... ] [, <replaceable class="parameter">column_name</replaceable> WITHOUT OVERLAPS ] )</literal>
     <optional> <literal>INCLUDE ( <replaceable class="parameter">column_name</replaceable> [, ...])</literal> </optional> (table constraint)</term>
 
     <listitem>
@@ -980,6 +980,30 @@ WITH ( MODULUS <replaceable class="parameter">numeric_literal</replaceable>, REM
      </para>
 
      <para>
+      If the <literal>WITHOUT OVERLAPS</literal> option is specified for the
+      last column, then that column is checked for overlaps instead of
+      equality.  In that case, the other columns of the constraint will allow
+      duplicates so long as the duplicates don't overlap in the
+      <literal>WITHOUT OVERLAPS</literal> column.  (This is sometimes called a
+      temporal key, if the column is a range of dates or timestamps, but
+      PostgreSQL allows ranges over any base type.)  In effect, such a
+      constraint is enforced with an <literal>EXCLUDE</literal> constraint
+      rather than a <literal>UNIQUE</literal> constraint.  So for example
+      <literal>UNIQUE (id, valid_at WITHOUT OVERLAPS)</literal> behaves like
+      <literal>EXCLUDE USING GIST (id WITH =, valid_at WITH
+      &amp;&amp;)</literal>.  The <literal>WITHOUT OVERLAPS</literal> column
+      must have a range or multirange type.  (Technically, any type is allowed
+      whose default GiST opclass includes an overlaps operator.  See the
+      <literal>stratnum</literal> support function under <xref
+      linkend="gist-extensibility"/> for details.)  The non-<literal>WITHOUT
+      OVERLAPS</literal> columns of the constraint can be any type that can be
+      compared for equality in a GiST index.  By default, only range types are
+      supported, but you can use other types by adding the <xref
+      linkend="btree-gist"/> extension (which is the expected way to use this
+      feature).
+     </para>
+
+     <para>
       For the purpose of a unique constraint, null values are not
       considered equal, unless <literal>NULLS NOT DISTINCT</literal> is
       specified.
@@ -1000,8 +1024,10 @@ WITH ( MODULUS <replaceable class="parameter">numeric_literal</replaceable>, REM
      </para>
 
      <para>
-      Adding a unique constraint will automatically create a unique btree
-      index on the column or group of columns used in the constraint.
+      Adding a unique constraint will automatically create a unique B-tree
+      index on the column or group of columns used in the constraint.  But if
+      the constraint includes a <literal>WITHOUT OVERLAPS</literal> clause, it
+      will use a GiST index.
      </para>
 
      <para>
@@ -1019,7 +1045,7 @@ WITH ( MODULUS <replaceable class="parameter">numeric_literal</replaceable>, REM
 
    <varlistentry id="sql-createtable-parms-primary-key">
     <term><literal>PRIMARY KEY</literal> (column constraint)</term>
-    <term><literal>PRIMARY KEY ( <replaceable class="parameter">column_name</replaceable> [, ... ] )</literal>
+    <term><literal>PRIMARY KEY ( <replaceable class="parameter">column_name</replaceable> [, ... ] [, <replaceable class="parameter">column_name</replaceable> WITHOUT OVERLAPS ] )</literal>
     <optional> <literal>INCLUDE ( <replaceable class="parameter">column_name</replaceable> [, ...])</literal> </optional> (table constraint)</term>
     <listitem>
      <para>
@@ -1052,9 +1078,10 @@ WITH ( MODULUS <replaceable class="parameter">numeric_literal</replaceable>, REM
      </para>
 
      <para>
-      Adding a <literal>PRIMARY KEY</literal> constraint will automatically
-      create a unique btree index on the column or group of columns used in the
-      constraint.
+      As with a <literal>UNIQUE</literal> constraint, adding a
+      <literal>PRIMARY KEY</literal> constraint will automatically create a
+      unique B-tree index, or GiST if <literal>WITHOUT OVERLAPS</literal> was
+      specified, on the column or group of columns used in the constraint.
      </para>
 
      <para>