operator exclusion constraints [was: generalized index constraints]

Update on operator exclusion constraints (OXC for short):

After a lot of discussion, I think a lot of progress has been made. Here
is my summary, please let me know if I've left anything out or not
addressed some concern.

1. Constraint syntax, part of CREATE/ALTER TABLE:

[CONSTRAINT <name>] EXCLUSION (<expr> OPERATOR <op>, ...)
USING <method>
[ DEFERRABLE | NOT DEFERRABLE ]
[ INITIALLY DEFERRED | INITIALLY IMMEDIATE ];

Table constraint syntax was chosen because of the ability to support
DEFERRABLE[1] and the interest in a more declarative syntax[2].

We omitted the [INDEX <indexname>] clause because the usefulness of
defining multiple constraints using one index or defining the constraint
separately from the index was judged to be too marginal[3][4][5]. Some
brief benchmarks showed some promise[6], perhaps interesting to explore
later.

Also, we introduce the OPERATOR keyword in between the expression and
the operator to disambiguate the syntax[5]. Nobody has affirmed the use
of OPERATOR for the disambiguation, but it seems like the obvious choice
to me.

2. information_schema

We omit operator exclusion constraints from the information schema, on
the grounds that there is no way to represent them usefully there[7][8].

3. Simplify the constraint checking procedure itself

Tom suggested a simpler constraint-checking procedure[9]. It introduces
the rare possibility of deadlocks[10], but that possibility exists for
other constraints anyway[11]. My scheme for avoiding deadlocks was
significantly more complex, and would become even more complex for
deferrable constraints.

4. <expr> is an expression over the table's attributes and will be used
to generate a functional index with the same expression to enforce the
constraint.

5. We reject non-symmetric operators[12], like >, but allow
non-reflexive operators[13] like <>.

6. Semantics of constraint[14] are such that for any two tuples A and B,
and for a constraint:

EXCLUSION (e1 OPERATOR <op1>, ..., eN OPERATOR <opN>)

the constraint is violated if:

A.e1 <op1> B.e1 AND
... AND
A.eN <opN> B.eN

7. LIKE is still unresolved. I don't have a strong opinion here.

When INCLUDING CONSTRAINTS and INCLUDING INDEXES are both specified:
a. copy all OXCs and indexes
b. copy no OXCs or indexes
When INCLUDING CONSTRAINTS is specified but not INCLUDING INDEXES:
a. copy all OXCs and indexes
b. copy no OXCs or indexes
When INCLUDING INDEXES is specified but not INCLUDING CONSTRAINTS:
a. copy all OXCs, including indexes
b. copy all indexes created implicitly for OXCs, but not the
constraints themselves
c. copy no OXCs or indexes

We can also emit various types of messages if we think the user is
making a mistake.

UNIQUE behavior here doesn't provide a good cue, because the constraint
is implemented inside the index, so copying the index does copy the
constraint. Brendan made a strong argument[15] that the behavior of LIKE
with UNIQUE is wrong, but I don't know if we want to try to fix that
now. I'd like some more input before I actually take care of this item.

The rest of the issues were mostly non-controversial. I will start
making some of these changes and post an updated patch and TODO list.

Regards,
Jeff Davis

[1] http://archives.postgresql.org/pgsql-hackers/2009-09/msg01352.php
[2] http://archives.postgresql.org/pgsql-hackers/2009-09/msg01018.php
[3] http://archives.postgresql.org/pgsql-hackers/2009-09/msg01348.php
[4] http://archives.postgresql.org/pgsql-hackers/2009-09/msg01355.php
[5] http://archives.postgresql.org/pgsql-hackers/2009-09/msg01360.php
[6] http://archives.postgresql.org/pgsql-hackers/2009-09/msg01369.php
[7] http://archives.postgresql.org/pgsql-hackers/2009-09/msg01310.php
[8] http://archives.postgresql.org/pgsql-hackers/2009-09/msg01356.php
[9] http://archives.postgresql.org/pgsql-hackers/2009-09/msg01315.php
[10] http://archives.postgresql.org/pgsql-hackers/2009-09/msg01317.php
[11] http://archives.postgresql.org/pgsql-hackers/2009-09/msg01347.php
[12] http://archives.postgresql.org/pgsql-hackers/2009-09/msg00977.php
[13] http://archives.postgresql.org/pgsql-hackers/2009-09/msg01039.php
[14] http://archives.postgresql.org/pgsql-hackers/2009-09/msg00971.php
[15] http://archives.postgresql.org/pgsql-hackers/2009-09/msg00755.php