Support deferrable uniqueness constraints.

The current implementation fires an AFTER ROW trigger for each tuple that
looks like it might be non-unique according to the index contents at the
time of insertion.  This works well as long as there aren't many conflicts,
but won't scale to massive unique-key reassignments.  Improving that case
is a TODO item.

Dean Rasheed

12 files changed, 92 insertions, 45 deletions

diff --git a/src/include/access/genam.h b/src/include/access/genam.h
index bf3fe96e26..a8c0e02929 100644
--- a/src/include/access/genam.h
+++ b/src/include/access/genam.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/access/genam.h,v 1.78 2009/06/11 14:49:08 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/access/genam.h,v 1.79 2009/07/29 20:56:19 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -85,6 +85,34 @@ typedef bool (*IndexBulkDeleteCallback) (ItemPointer itemptr, void *state);
 typedef struct IndexScanDescData *IndexScanDesc;
 typedef struct SysScanDescData *SysScanDesc;
 
+/*
+ * Enumeration specifying the type of uniqueness check to perform in
+ * index_insert().
+ *
+ * UNIQUE_CHECK_YES is the traditional Postgres immediate check, possibly
+ * blocking to see if a conflicting transaction commits.
+ *
+ * For deferrable unique constraints, UNIQUE_CHECK_PARTIAL is specified at
+ * insertion time.  The index AM should test if the tuple is unique, but
+ * should not throw error, block, or prevent the insertion if the tuple
+ * appears not to be unique.  We'll recheck later when it is time for the
+ * constraint to be enforced.  The AM must return true if the tuple is
+ * known unique, false if it is possibly non-unique.  In the "true" case
+ * it is safe to omit the later recheck.
+ *
+ * When it is time to recheck the deferred constraint, a pseudo-insertion
+ * call is made with UNIQUE_CHECK_EXISTING.  The tuple is already in the
+ * index in this case, so it should not be inserted again.  Rather, just
+ * check for conflicting live tuples (possibly blocking).
+ */
+typedef enum IndexUniqueCheck
+{
+	UNIQUE_CHECK_NO,			/* Don't do any uniqueness checking */
+	UNIQUE_CHECK_YES,			/* Enforce uniqueness at insertion time */
+	UNIQUE_CHECK_PARTIAL,		/* Test uniqueness, but no error */
+	UNIQUE_CHECK_EXISTING		/* Check if existing tuple is unique */
+} IndexUniqueCheck;
+
 
 /*
  * generalized index_ interface routines (in indexam.c)
@@ -103,7 +131,7 @@ extern bool index_insert(Relation indexRelation,
 			 Datum *values, bool *isnull,
 			 ItemPointer heap_t_ctid,
 			 Relation heapRelation,
-			 bool check_uniqueness);
+			 IndexUniqueCheck checkUnique);
 
 extern IndexScanDesc index_beginscan(Relation heapRelation,
 				Relation indexRelation,
diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index 1d3e42d99b..ed5ec57e47 100644
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/access/nbtree.h,v 1.124 2009/06/11 14:49:08 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/access/nbtree.h,v 1.125 2009/07/29 20:56:19 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -517,8 +517,8 @@ extern Datum btoptions(PG_FUNCTION_ARGS);
 /*
  * prototypes for functions in nbtinsert.c
  */
-extern void _bt_doinsert(Relation rel, IndexTuple itup,
-			 bool index_is_unique, Relation heapRel);
+extern bool _bt_doinsert(Relation rel, IndexTuple itup,
+			 IndexUniqueCheck checkUnique, Relation heapRel);
 extern Buffer _bt_getstackbuf(Relation rel, BTStack stack, int access);
 extern void _bt_insert_parent(Relation rel, Buffer buf, Buffer rbuf,
 				  BTStack stack, bool is_root, bool is_only);
diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h
index ecbf105606..847362ad27 100644
--- a/src/include/catalog/catversion.h
+++ b/src/include/catalog/catversion.h
@@ -37,7 +37,7 @@
  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/catalog/catversion.h,v 1.533 2009/07/28 02:56:30 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/catalog/catversion.h,v 1.534 2009/07/29 20:56:19 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -53,6 +53,6 @@
  */
 
 /*							yyyymmddN */
-#define CATALOG_VERSION_NO	200907271
+#define CATALOG_VERSION_NO	200907291
 
 #endif
diff --git a/src/include/catalog/index.h b/src/include/catalog/index.h
index 18064889aa..a432260058 100644
--- a/src/include/catalog/index.h
+++ b/src/include/catalog/index.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/catalog/index.h,v 1.77 2009/01/01 17:23:56 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/catalog/index.h,v 1.78 2009/07/29 20:56:20 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -39,6 +39,8 @@ extern Oid index_create(Oid heapRelationId,
 			 Datum reloptions,
 			 bool isprimary,
 			 bool isconstraint,
+			 bool deferrable,
+			 bool initdeferred,
 			 bool allow_system_table_mods,
 			 bool skip_build,
 			 bool concurrent);
diff --git a/src/include/catalog/pg_attribute.h b/src/include/catalog/pg_attribute.h
index b852a28cd5..e1c6fc8373 100644
--- a/src/include/catalog/pg_attribute.h
+++ b/src/include/catalog/pg_attribute.h
@@ -8,7 +8,7 @@
  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/catalog/pg_attribute.h,v 1.148 2009/06/11 14:49:09 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/catalog/pg_attribute.h,v 1.149 2009/07/29 20:56:20 tgl Exp $
  *
  * NOTES
  *	  the genbki.sh script reads this file and generates .bki
@@ -469,14 +469,15 @@ DATA(insert ( 1259 tableoid			26 0  4  -7 0 -1 -1 t p i t f f t 0 _null_));
 { 0, {"indnatts"},			21, -1, 2, 3, 0, -1, -1, true, 'p', 's', true, false, false, true, 0, { 0 } }, \
 { 0, {"indisunique"},		16, -1, 1, 4, 0, -1, -1, true, 'p', 'c', true, false, false, true, 0, { 0 } }, \
 { 0, {"indisprimary"},		16, -1, 1, 5, 0, -1, -1, true, 'p', 'c', true, false, false, true, 0, { 0 } }, \
-{ 0, {"indisclustered"},	16, -1, 1, 6, 0, -1, -1, true, 'p', 'c', true, false, false, true, 0, { 0 } }, \
-{ 0, {"indisvalid"},		16, -1, 1, 7, 0, -1, -1, true, 'p', 'c', true, false, false, true, 0, { 0 } }, \
-{ 0, {"indcheckxmin"},		16, -1, 1, 8, 0, -1, -1, true, 'p', 'c', true, false, false, true, 0, { 0 } }, \
-{ 0, {"indisready"},		16, -1, 1, 9, 0, -1, -1, true, 'p', 'c', true, false, false, true, 0, { 0 } }, \
-{ 0, {"indkey"},			22, -1, -1, 10, 1, -1, -1, false, 'p', 'i', true, false, false, true, 0, { 0 } }, \
-{ 0, {"indclass"},			30, -1, -1, 11, 1, -1, -1, false, 'p', 'i', true, false, false, true, 0, { 0 } }, \
-{ 0, {"indoption"},			22, -1, -1, 12, 1, -1, -1, false, 'p', 'i', true, false, false, true, 0, { 0 } }, \
-{ 0, {"indexprs"},			25, -1, -1, 13, 0, -1, -1, false, 'x', 'i', false, false, false, true, 0, { 0 } }, \
-{ 0, {"indpred"},			25, -1, -1, 14, 0, -1, -1, false, 'x', 'i', false, false, false, true, 0, { 0 } }
+{ 0, {"indimmediate"},		16, -1, 1, 6, 0, -1, -1, true, 'p', 'c', true, false, false, true, 0, { 0 } }, \
+{ 0, {"indisclustered"},	16, -1, 1, 7, 0, -1, -1, true, 'p', 'c', true, false, false, true, 0, { 0 } }, \
+{ 0, {"indisvalid"},		16, -1, 1, 8, 0, -1, -1, true, 'p', 'c', true, false, false, true, 0, { 0 } }, \
+{ 0, {"indcheckxmin"},		16, -1, 1, 9, 0, -1, -1, true, 'p', 'c', true, false, false, true, 0, { 0 } }, \
+{ 0, {"indisready"},		16, -1, 1, 10, 0, -1, -1, true, 'p', 'c', true, false, false, true, 0, { 0 } }, \
+{ 0, {"indkey"},			22, -1, -1, 11, 1, -1, -1, false, 'p', 'i', true, false, false, true, 0, { 0 } }, \
+{ 0, {"indclass"},			30, -1, -1, 12, 1, -1, -1, false, 'p', 'i', true, false, false, true, 0, { 0 } }, \
+{ 0, {"indoption"},			22, -1, -1, 13, 1, -1, -1, false, 'p', 'i', true, false, false, true, 0, { 0 } }, \
+{ 0, {"indexprs"},			25, -1, -1, 14, 0, -1, -1, false, 'x', 'i', false, false, false, true, 0, { 0 } }, \
+{ 0, {"indpred"},			25, -1, -1, 15, 0, -1, -1, false, 'x', 'i', false, false, false, true, 0, { 0 } }
 
 #endif   /* PG_ATTRIBUTE_H */
diff --git a/src/include/catalog/pg_index.h b/src/include/catalog/pg_index.h
index 1ec2e49a59..36ffef5ed8 100644
--- a/src/include/catalog/pg_index.h
+++ b/src/include/catalog/pg_index.h
@@ -8,7 +8,7 @@
  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/catalog/pg_index.h,v 1.47 2009/01/01 17:23:57 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/catalog/pg_index.h,v 1.48 2009/07/29 20:56:20 tgl Exp $
  *
  * NOTES
  *	  the genbki.sh script reads this file and generates .bki
@@ -35,6 +35,7 @@ CATALOG(pg_index,2610) BKI_WITHOUT_OIDS
 	int2		indnatts;		/* number of columns in index */
 	bool		indisunique;	/* is this a unique index? */
 	bool		indisprimary;	/* is this index for primary key? */
+	bool		indimmediate;	/* is uniqueness enforced immediately? */
 	bool		indisclustered; /* is this the index last clustered by? */
 	bool		indisvalid;		/* is this index valid for use by queries? */
 	bool		indcheckxmin;	/* must we wait for xmin to be old? */
@@ -62,21 +63,22 @@ typedef FormData_pg_index *Form_pg_index;
  *		compiler constants for pg_index
  * ----------------
  */
-#define Natts_pg_index					14
+#define Natts_pg_index					15
 #define Anum_pg_index_indexrelid		1
 #define Anum_pg_index_indrelid			2
 #define Anum_pg_index_indnatts			3
 #define Anum_pg_index_indisunique		4
 #define Anum_pg_index_indisprimary		5
-#define Anum_pg_index_indisclustered	6
-#define Anum_pg_index_indisvalid		7
-#define Anum_pg_index_indcheckxmin		8
-#define Anum_pg_index_indisready		9
-#define Anum_pg_index_indkey			10
-#define Anum_pg_index_indclass			11
-#define Anum_pg_index_indoption			12
-#define Anum_pg_index_indexprs			13
-#define Anum_pg_index_indpred			14
+#define Anum_pg_index_indimmediate		6
+#define Anum_pg_index_indisclustered	7
+#define Anum_pg_index_indisvalid		8
+#define Anum_pg_index_indcheckxmin		9
+#define Anum_pg_index_indisready		10
+#define Anum_pg_index_indkey			11
+#define Anum_pg_index_indclass			12
+#define Anum_pg_index_indoption			13
+#define Anum_pg_index_indexprs			14
+#define Anum_pg_index_indpred			15
 
 /*
  * Index AMs that support ordered scans must support these two indoption
diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.h
index 218ae74176..d5884faa4a 100644
--- a/src/include/catalog/pg_proc.h
+++ b/src/include/catalog/pg_proc.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/catalog/pg_proc.h,v 1.546 2009/07/07 18:49:16 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/catalog/pg_proc.h,v 1.547 2009/07/29 20:56:20 tgl Exp $
  *
  * NOTES
  *	  The script catalog/genbki.sh reads this file and generates .bki
@@ -2323,6 +2323,10 @@ DESCR("convert generic options array to name/value table");
 DATA(insert OID = 1619 (  pg_typeof				PGNSP PGUID 12 1 0 0 f f f f f s 1 0 2206 "2276" _null_ _null_ _null_ _null_  pg_typeof _null_ _null_ _null_ ));
 DESCR("returns the type of the argument");
 
+/* Deferrable unique constraint trigger */
+DATA(insert OID = 1250 (  unique_key_recheck	PGNSP PGUID 12 1 0 0 f f f t f v 0 0 2279 "" _null_ _null_ _null_ _null_ unique_key_recheck _null_ _null_ _null_ ));
+DESCR("deferred UNIQUE constraint check");
+
 /* Generic referential integrity constraint triggers */
 DATA(insert OID = 1644 (  RI_FKey_check_ins		PGNSP PGUID 12 1 0 0 f f f t f v 0 0 2279 "" _null_ _null_ _null_ _null_ RI_FKey_check_ins _null_ _null_ _null_ ));
 DESCR("referential integrity FOREIGN KEY ... REFERENCES");
diff --git a/src/include/commands/defrem.h b/src/include/commands/defrem.h
index 1d6ab7bbf4..4396a49738 100644
--- a/src/include/commands/defrem.h
+++ b/src/include/commands/defrem.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/commands/defrem.h,v 1.95 2009/07/16 06:33:45 petere Exp $
+ * $PostgreSQL: pgsql/src/include/commands/defrem.h,v 1.96 2009/07/29 20:56:20 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -29,6 +29,8 @@ extern void DefineIndex(RangeVar *heapRelation,
 			bool unique,
 			bool primary,
 			bool isconstraint,
+			bool deferrable,
+			bool initdeferred,
 			bool is_alter_table,
 			bool check_rights,
 			bool skip_build,
diff --git a/src/include/commands/trigger.h b/src/include/commands/trigger.h
index 3e14bbe3ba..c92337a5a1 100644
--- a/src/include/commands/trigger.h
+++ b/src/include/commands/trigger.h
@@ -6,7 +6,7 @@
  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/commands/trigger.h,v 1.74 2009/07/28 02:56:31 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/commands/trigger.h,v 1.75 2009/07/29 20:56:20 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -105,7 +105,7 @@ extern PGDLLIMPORT int SessionReplicationRole;
 #define TRIGGER_DISABLED					'D'
 
 extern Oid CreateTrigger(CreateTrigStmt *stmt,
-			  Oid constraintOid, Oid indexOid,
+			  Oid constraintOid, Oid indexOid, const char *prefix,
 			  bool checkPermissions);
 
 extern void DropTrigger(Oid relid, const char *trigname,
@@ -132,7 +132,8 @@ extern HeapTuple ExecBRInsertTriggers(EState *estate,
 					 HeapTuple trigtuple);
 extern void ExecARInsertTriggers(EState *estate,
 					 ResultRelInfo *relinfo,
-					 HeapTuple trigtuple);
+					 HeapTuple trigtuple,
+					 List *recheckIndexes);
 extern void ExecBSDeleteTriggers(EState *estate,
 					 ResultRelInfo *relinfo);
 extern void ExecASDeleteTriggers(EState *estate,
@@ -154,7 +155,8 @@ extern HeapTuple ExecBRUpdateTriggers(EState *estate,
 extern void ExecARUpdateTriggers(EState *estate,
 					 ResultRelInfo *relinfo,
 					 ItemPointer tupleid,
-					 HeapTuple newtuple);
+					 HeapTuple newtuple,
+					 List *recheckIndexes);
 extern void ExecBSTruncateTriggers(EState *estate,
 					   ResultRelInfo *relinfo);
 extern void ExecASTruncateTriggers(EState *estate,
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index 86148ed135..2ad1e26b2a 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/executor/executor.h,v 1.157 2009/07/22 17:00:23 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/executor/executor.h,v 1.158 2009/07/29 20:56:20 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -302,8 +302,8 @@ extern void ExecCloseScanRelation(Relation scanrel);
 
 extern void ExecOpenIndices(ResultRelInfo *resultRelInfo);
 extern void ExecCloseIndices(ResultRelInfo *resultRelInfo);
-extern void ExecInsertIndexTuples(TupleTableSlot *slot, ItemPointer tupleid,
-					  EState *estate, bool is_vacuum);
+extern List *ExecInsertIndexTuples(TupleTableSlot *slot, ItemPointer tupleid,
+					  EState *estate, bool is_vacuum_full);
 
 extern void RegisterExprContextCallback(ExprContext *econtext,
 							ExprContextCallbackFunction function,
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index 5947c6acc9..ae2f087360 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -13,7 +13,7 @@
  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/nodes/parsenodes.h,v 1.398 2009/07/26 23:34:18 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/parsenodes.h,v 1.399 2009/07/29 20:56:21 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -1355,7 +1355,7 @@ typedef struct CreateStmt
  * Constraint attributes (DEFERRABLE etc) are initially represented as
  * separate Constraint nodes for simplicity of parsing.  parse_utilcmd.c makes
  * a pass through the constraints list to attach the info to the appropriate
- * FkConstraint node (and, perhaps, someday to other kinds of constraints).
+ * Constraint and FkConstraint nodes.
  * ----------
  */
 
@@ -1385,6 +1385,8 @@ typedef struct Constraint
 	List	   *options;		/* options from WITH clause */
 	char	   *indexspace;		/* index tablespace for PKEY/UNIQUE
 								 * constraints; NULL for default */
+	bool		deferrable;		/* DEFERRABLE */
+	bool		initdeferred;	/* INITIALLY DEFERRED */
 } Constraint;
 
 /* ----------
@@ -1555,12 +1557,11 @@ typedef struct CreateTrigStmt
 	/* events uses the TRIGGER_TYPE bits defined in catalog/pg_trigger.h */
 	int16		events;			/* INSERT/UPDATE/DELETE/TRUNCATE */
 
-	/* The following are used for referential */
-	/* integrity constraint triggers */
-	bool		isconstraint;	/* This is an RI trigger */
+	/* The following are used for constraint triggers (RI and unique checks) */
+	bool		isconstraint;	/* This is a constraint trigger */
 	bool		deferrable;		/* [NOT] DEFERRABLE */
 	bool		initdeferred;	/* INITIALLY {DEFERRED|IMMEDIATE} */
-	RangeVar   *constrrel;		/* opposite relation */
+	RangeVar   *constrrel;		/* opposite relation, if RI trigger */
 } CreateTrigStmt;
 
 /* ----------------------
@@ -1864,6 +1865,8 @@ typedef struct IndexStmt
 	bool		unique;			/* is index unique? */
 	bool		primary;		/* is index on primary key? */
 	bool		isconstraint;	/* is it from a CONSTRAINT clause? */
+	bool		deferrable;		/* is the constraint DEFERRABLE? */
+	bool		initdeferred;	/* is the constraint INITIALLY DEFERRED? */
 	bool		concurrent;		/* should this be a concurrent index build? */
 } IndexStmt;
 
diff --git a/src/include/utils/builtins.h b/src/include/utils/builtins.h
index 5547b6c8c9..72b39f7068 100644
--- a/src/include/utils/builtins.h
+++ b/src/include/utils/builtins.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/utils/builtins.h,v 1.334 2009/07/16 06:33:46 petere Exp $
+ * $PostgreSQL: pgsql/src/include/utils/builtins.h,v 1.335 2009/07/29 20:56:21 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -1029,6 +1029,9 @@ extern Datum window_nth_value(PG_FUNCTION_ARGS);
 /* access/transam/twophase.c */
 extern Datum pg_prepared_xact(PG_FUNCTION_ARGS);
 
+/* commands/constraint.c */
+extern Datum unique_key_recheck(PG_FUNCTION_ARGS);
+
 /* commands/prepare.c */
 extern Datum pg_prepared_statement(PG_FUNCTION_ARGS);