Add exclusion constraints, which generalize the concept of uniqueness to

support any indexable commutative operator, not just equality.  Two rows
violate the exclusion constraint if "row1.col OP row2.col" is TRUE for
each of the columns in the constraint.

Jeff Davis, reviewed by Robert Haas

1 files changed, 255 insertions, 9 deletions

diff --git a/src/backend/executor/execUtils.c b/src/backend/executor/execUtils.c
index e1aa8ce8ac9..ac993465a51 100644
--- a/src/backend/executor/execUtils.c
+++ b/src/backend/executor/execUtils.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/executor/execUtils.c,v 1.166 2009/11/20 20:38:10 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/executor/execUtils.c,v 1.167 2009/12/07 05:22:22 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -44,16 +44,22 @@
 
 #include "access/genam.h"
 #include "access/heapam.h"
+#include "access/relscan.h"
+#include "access/transam.h"
 #include "catalog/index.h"
 #include "executor/execdebug.h"
 #include "nodes/nodeFuncs.h"
 #include "parser/parsetree.h"
+#include "storage/lmgr.h"
 #include "utils/memutils.h"
 #include "utils/relcache.h"
 #include "utils/tqual.h"
 
 
 static bool get_last_attnums(Node *node, ProjectionInfo *projInfo);
+static bool index_recheck_constraint(Relation index, Oid *constr_procs,
+						 Datum *existing_values, bool *existing_isnull,
+						 Datum *new_values);
 static void ShutdownExprContext(ExprContext *econtext, bool isCommit);
 
 
@@ -959,8 +965,8 @@ ExecCloseIndices(ResultRelInfo *resultRelInfo)
  *		doesn't provide the functionality needed by the
  *		executor.. -cim 9/27/89
  *
- *		This returns a list of OIDs for any unique indexes
- *		whose constraint check was deferred and which had
+ *		This returns a list of index OIDs for any unique or exclusion
+ *		constraints that are deferred and that had
  *		potential (unconfirmed) conflicts.
  *
  *		CAUTION: this must not be called for a HOT update.
@@ -1011,7 +1017,7 @@ ExecInsertIndexTuples(TupleTableSlot *slot,
 		Relation	indexRelation = relationDescs[i];
 		IndexInfo  *indexInfo;
 		IndexUniqueCheck checkUnique;
-		bool		isUnique;
+		bool		satisfiesConstraint;
 
 		if (indexRelation == NULL)
 			continue;
@@ -1056,7 +1062,7 @@ ExecInsertIndexTuples(TupleTableSlot *slot,
 					   isnull);
 
 		/*
-		 * The index AM does the rest, including uniqueness checking.
+		 * The index AM does the actual insertion, plus uniqueness checking.
 		 *
 		 * For an immediate-mode unique index, we just tell the index AM to
 		 * throw error if not unique.
@@ -1076,7 +1082,7 @@ ExecInsertIndexTuples(TupleTableSlot *slot,
 		else
 			checkUnique = UNIQUE_CHECK_PARTIAL;
 
-		isUnique =
+		satisfiesConstraint =
 			index_insert(indexRelation,	/* index relation */
 						 values,		/* array of index Datums */
 						 isnull,		/* null flags */
@@ -1084,11 +1090,36 @@ ExecInsertIndexTuples(TupleTableSlot *slot,
 						 heapRelation,	/* heap relation */
 						 checkUnique);	/* type of uniqueness check to do */
 
-		if (checkUnique == UNIQUE_CHECK_PARTIAL && !isUnique)
+		/*
+		 * If the index has an associated exclusion constraint, check that.
+		 * This is simpler than the process for uniqueness checks since we
+		 * always insert first and then check.  If the constraint is deferred,
+		 * we check now anyway, but don't throw error on violation; instead
+		 * we'll queue a recheck event.
+		 *
+		 * An index for an exclusion constraint can't also be UNIQUE (not an
+		 * essential property, we just don't allow it in the grammar), so no
+		 * need to preserve the prior state of satisfiesConstraint.
+		 */
+		if (indexInfo->ii_ExclusionOps != NULL)
+		{
+			bool errorOK = !indexRelation->rd_index->indimmediate;
+
+			satisfiesConstraint =
+				check_exclusion_constraint(heapRelation,
+										   indexRelation, indexInfo,
+										   tupleid, values, isnull,
+										   estate, false, errorOK);
+		}
+
+		if ((checkUnique == UNIQUE_CHECK_PARTIAL ||
+			 indexInfo->ii_ExclusionOps != NULL) &&
+			!satisfiesConstraint)
 		{
 			/*
-			 * The tuple potentially violates the uniqueness constraint,
-			 * so make a note of the index so that we can re-check it later.
+			 * The tuple potentially violates the uniqueness or exclusion
+			 * constraint, so make a note of the index so that we can re-check
+			 * it later.
 			 */
 			result = lappend_oid(result, RelationGetRelid(indexRelation));
 		}
@@ -1098,6 +1129,221 @@ ExecInsertIndexTuples(TupleTableSlot *slot,
 }
 
 /*
+ * Check for violation of an exclusion constraint
+ *
+ * heap: the table containing the new tuple
+ * index: the index supporting the exclusion constraint
+ * indexInfo: info about the index, including the exclusion properties
+ * tupleid: heap TID of the new tuple we have just inserted
+ * values, isnull: the *index* column values computed for the new tuple
+ * estate: an EState we can do evaluation in
+ * newIndex: if true, we are trying to build a new index (this affects
+ *		only the wording of error messages)
+ * errorOK: if true, don't throw error for violation
+ *
+ * Returns true if OK, false if actual or potential violation
+ *
+ * When errorOK is true, we report violation without waiting to see if any
+ * concurrent transaction has committed or not; so the violation is only
+ * potential, and the caller must recheck sometime later.  This behavior
+ * is convenient for deferred exclusion checks; we need not bother queuing
+ * a deferred event if there is definitely no conflict at insertion time.
+ *
+ * When errorOK is false, we'll throw error on violation, so a false result
+ * is impossible.
+ */
+bool
+check_exclusion_constraint(Relation heap, Relation index, IndexInfo *indexInfo,
+						   ItemPointer tupleid, Datum *values, bool *isnull,
+						   EState *estate, bool newIndex, bool errorOK)
+{
+	Oid			*constr_procs = indexInfo->ii_ExclusionProcs;
+	uint16		*constr_strats = indexInfo->ii_ExclusionStrats;
+	int			 index_natts = index->rd_index->indnatts;
+	IndexScanDesc	index_scan;
+	HeapTuple		tup;
+	ScanKeyData		scankeys[INDEX_MAX_KEYS];
+	SnapshotData	DirtySnapshot;
+	int				i;
+	bool			conflict;
+	bool			found_self;
+	TupleTableSlot *existing_slot;
+
+	/*
+	 * If any of the input values are NULL, the constraint check is assumed
+	 * to pass (i.e., we assume the operators are strict).
+	 */
+	for (i = 0; i < index_natts; i++)
+	{
+		if (isnull[i])
+			return true;
+	}
+
+	/*
+	 * Search the tuples that are in the index for any violations,
+	 * including tuples that aren't visible yet.
+	 */
+	InitDirtySnapshot(DirtySnapshot);
+
+	for (i = 0; i < index_natts; i++)
+	{
+		ScanKeyInit(&scankeys[i],
+					i + 1,
+					constr_strats[i],
+					constr_procs[i],
+					values[i]);
+	}
+
+	/* Need a TupleTableSlot to put existing tuples in */
+	existing_slot = MakeSingleTupleTableSlot(RelationGetDescr(heap));
+
+	/*
+	 * May have to restart scan from this point if a potential
+	 * conflict is found.
+	 */
+retry:
+	conflict = false;
+	found_self = false;
+	index_scan = index_beginscan(heap, index, &DirtySnapshot,
+								 index_natts, scankeys);
+
+	while ((tup = index_getnext(index_scan,
+								ForwardScanDirection)) != NULL)
+	{
+		TransactionId	 xwait;
+		Datum		existing_values[INDEX_MAX_KEYS];
+		bool		existing_isnull[INDEX_MAX_KEYS];
+		char		*error_new;
+		char		*error_existing;
+
+		/*
+		 * Ignore the entry for the tuple we're trying to check.
+		 */
+		if (ItemPointerEquals(tupleid, &tup->t_self))
+		{
+			if (found_self)		/* should not happen */
+				elog(ERROR, "found self tuple multiple times in index \"%s\"",
+					 RelationGetRelationName(index));
+			found_self = true;
+			continue;
+		}
+
+		/*
+		 * Extract the index column values and isnull flags from the existing
+		 * tuple.
+		 */
+		ExecStoreTuple(tup,	existing_slot, InvalidBuffer, false);
+		FormIndexDatum(indexInfo, existing_slot, estate,
+					   existing_values, existing_isnull);
+
+		/* If lossy indexscan, must recheck the condition */
+		if (index_scan->xs_recheck)
+		{
+			if (!index_recheck_constraint(index,
+										  constr_procs,
+										  existing_values,
+										  existing_isnull,
+										  values))
+				continue; /* tuple doesn't actually match, so no conflict */
+		}
+
+		/*
+		 * At this point we have either a conflict or a potential conflict.
+		 * If we're not supposed to raise error, just return the fact of the
+		 * potential conflict without waiting to see if it's real.
+		 */
+		if (errorOK)
+		{
+			conflict = true;
+			break;
+		}
+
+		/*
+		 * If an in-progress transaction is affecting the visibility of this
+		 * tuple, we need to wait for it to complete and then recheck.  For
+		 * simplicity we do rechecking by just restarting the whole scan ---
+		 * this case probably doesn't happen often enough to be worth trying
+		 * harder, and anyway we don't want to hold any index internal locks
+		 * while waiting.
+		 */
+		xwait = TransactionIdIsValid(DirtySnapshot.xmin) ?
+			DirtySnapshot.xmin : DirtySnapshot.xmax;
+
+		if (TransactionIdIsValid(xwait))
+		{
+			index_endscan(index_scan);
+			XactLockTableWait(xwait);
+			goto retry;
+		}
+
+		/*
+		 * We have a definite conflict.  Report it.
+		 */
+		error_new = BuildIndexValueDescription(index, values, isnull);
+		error_existing = BuildIndexValueDescription(index, existing_values,
+													existing_isnull);
+		if (newIndex)
+			ereport(ERROR,
+					(errcode(ERRCODE_EXCLUSION_VIOLATION),
+					 errmsg("could not create exclusion constraint \"%s\"",
+							RelationGetRelationName(index)),
+					 errdetail("Key %s conflicts with key %s.",
+							   error_new, error_existing)));
+		else
+			ereport(ERROR,
+					(errcode(ERRCODE_EXCLUSION_VIOLATION),
+					 errmsg("conflicting key value violates exclusion constraint \"%s\"",
+							RelationGetRelationName(index)),
+					 errdetail("Key %s conflicts with existing key %s.",
+							   error_new, error_existing)));
+	}
+
+	index_endscan(index_scan);
+
+	/*
+	 * We should have found our tuple in the index, unless we exited the
+	 * loop early because of conflict.  Complain if not.
+	 */
+	if (!found_self && !conflict)
+		ereport(ERROR,
+				(errcode(ERRCODE_INTERNAL_ERROR),
+				 errmsg("failed to re-find tuple within index \"%s\"",
+						RelationGetRelationName(index)),
+				 errhint("This may be because of a non-immutable index expression.")));
+
+	ExecDropSingleTupleTableSlot(existing_slot);
+
+	return !conflict;
+}
+
+/*
+ * Check existing tuple's index values to see if it really matches the
+ * exclusion condition against the new_values.  Returns true if conflict.
+ */
+static bool
+index_recheck_constraint(Relation index, Oid *constr_procs,
+						 Datum *existing_values, bool *existing_isnull,
+						 Datum *new_values)
+{
+	int			index_natts = index->rd_index->indnatts;
+	int			i;
+
+	for (i = 0; i < index_natts; i++)
+	{
+		/* Assume the exclusion operators are strict */
+		if (existing_isnull[i])
+			return false;
+
+		if (!DatumGetBool(OidFunctionCall2(constr_procs[i],
+										   existing_values[i],
+										   new_values[i])))
+			return false;
+	}
+
+	return true;
+}
+
+/*
  * UpdateChangedParamSet
  *		Add changed parameters to a plan node's chgParam set
  */