Implement sharable row-level locks, and use them for foreign key references

to eliminate unnecessary deadlocks.  This commit adds SELECT ... FOR SHARE
paralleling SELECT ... FOR UPDATE.  The implementation uses a new SLRU
data structure (managed much like pg_subtrans) to represent multiple-
transaction-ID sets.  When more than one transaction is holding a shared
lock on a particular row, we create a MultiXactId representing that set
of transactions and store its ID in the row's XMAX.  This scheme allows
an effectively unlimited number of row locks, just as we did before,
while not costing any extra overhead except when a shared lock actually
has to be shared.   Still TODO: use the regular lock manager to control
the grant order when multiple backends are waiting for a row lock.

Alvaro Herrera and Tom Lane.

5 files changed, 30 insertions, 19 deletions

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 8675b6efd3c..84544a20115 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.128 2005/04/25 01:30:13 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.129 2005/04/28 21:47:13 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -214,13 +214,13 @@ set_inherited_rel_pathlist(Query *root, RelOptInfo *rel,
 	ListCell   *il;
 
 	/*
-	 * XXX for now, can't handle inherited expansion of FOR UPDATE; can we
-	 * do better?
+	 * XXX for now, can't handle inherited expansion of FOR UPDATE/SHARE;
+	 * can we do better?
 	 */
 	if (list_member_int(root->rowMarks, parentRTindex))
 		ereport(ERROR,
 				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
-				 errmsg("SELECT FOR UPDATE is not supported for inheritance queries")));
+				 errmsg("SELECT FOR UPDATE/SHARE is not supported for inheritance queries")));
 
 	/*
 	 * Initialize to compute size estimates for whole inheritance tree
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index 292b5503566..22878c0099e 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/initsplan.c,v 1.104 2004/12/31 22:00:09 pgsql Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/initsplan.c,v 1.105 2005/04/28 21:47:13 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -323,11 +323,11 @@ mark_baserels_for_outer_join(Query *root, Relids rels, Relids outerrels)
 		Assert(bms_is_subset(rel->outerjoinset, outerrels));
 
 		/*
-		 * Presently the executor cannot support FOR UPDATE marking of
+		 * Presently the executor cannot support FOR UPDATE/SHARE marking of
 		 * rels appearing on the nullable side of an outer join. (It's
 		 * somewhat unclear what that would mean, anyway: what should we
 		 * mark when a result row is generated from no element of the
-		 * nullable relation?)	So, complain if target rel is FOR UPDATE.
+		 * nullable relation?)	So, complain if target rel is FOR UPDATE/SHARE.
 		 * It's sufficient to make this check once per rel, so do it only
 		 * if rel wasn't already known nullable.
 		 */
@@ -336,7 +336,7 @@ mark_baserels_for_outer_join(Query *root, Relids rels, Relids outerrels)
 			if (list_member_int(root->rowMarks, relno))
 				ereport(ERROR,
 						(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
-						 errmsg("SELECT FOR UPDATE cannot be applied to the nullable side of an outer join")));
+						 errmsg("SELECT FOR UPDATE/SHARE cannot be applied to the nullable side of an outer join")));
 		}
 
 		rel->outerjoinset = outerrels;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index b542fef61e2..2e83a7417df 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/planner.c,v 1.184 2005/04/11 23:06:55 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/planner.c,v 1.185 2005/04/28 21:47:13 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -635,13 +635,13 @@ grouping_planner(Query *parse, double tuple_fraction)
 		tlist = postprocess_setop_tlist(result_plan->targetlist, tlist);
 
 		/*
-		 * Can't handle FOR UPDATE here (parser should have checked
+		 * Can't handle FOR UPDATE/SHARE here (parser should have checked
 		 * already, but let's make sure).
 		 */
 		if (parse->rowMarks)
 			ereport(ERROR,
 					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
-					 errmsg("SELECT FOR UPDATE is not allowed with UNION/INTERSECT/EXCEPT")));
+					 errmsg("SELECT FOR UPDATE/SHARE is not allowed with UNION/INTERSECT/EXCEPT")));
 
 		/*
 		 * Calculate pathkeys that represent result ordering requirements
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 603b8c43582..b5b658cf58a 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -16,7 +16,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/prep/prepjointree.c,v 1.26 2005/04/06 16:34:06 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/prep/prepjointree.c,v 1.27 2005/04/28 21:47:14 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -276,11 +276,22 @@ pull_up_subqueries(Query *parse, Node *jtnode, bool below_outer_join)
 			parse->rtable = list_concat(parse->rtable, subquery->rtable);
 
 			/*
-			 * Pull up any FOR UPDATE markers, too.  (OffsetVarNodes
+			 * Pull up any FOR UPDATE/SHARE markers, too.  (OffsetVarNodes
 			 * already adjusted the marker values, so just list_concat the
 			 * list.)
+			 *
+			 * Executor can't handle multiple FOR UPDATE/SHARE flags, so
+			 * complain if they are valid but different
 			 */
+			if (parse->rowMarks && subquery->rowMarks &&
+				parse->forUpdate != subquery->forUpdate)
+				ereport(ERROR,
+						(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+						 errmsg("cannot use both FOR UPDATE and FOR SHARE in one query")));
+
 			parse->rowMarks = list_concat(parse->rowMarks, subquery->rowMarks);
+			if (subquery->rowMarks)
+				parse->forUpdate = subquery->forUpdate;
 
 			/*
 			 * We also have to fix the relid sets of any parent
diff --git a/src/backend/optimizer/prep/preptlist.c b/src/backend/optimizer/prep/preptlist.c
index ac8dae65ce7..c4f31154437 100644
--- a/src/backend/optimizer/prep/preptlist.c
+++ b/src/backend/optimizer/prep/preptlist.c
@@ -15,7 +15,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/prep/preptlist.c,v 1.74 2005/04/06 16:34:06 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/prep/preptlist.c,v 1.75 2005/04/28 21:47:14 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -102,7 +102,7 @@ preprocess_targetlist(Query *parse, List *tlist)
 	}
 
 	/*
-	 * Add TID targets for rels selected FOR UPDATE.  The executor
+	 * Add TID targets for rels selected FOR UPDATE/SHARE.  The executor
 	 * uses the TID to know which rows to lock, much as for UPDATE or
 	 * DELETE.
 	 */
@@ -111,22 +111,22 @@ preprocess_targetlist(Query *parse, List *tlist)
 		ListCell   *l;
 
 		/*
-		 * We've got trouble if the FOR UPDATE appears inside
+		 * We've got trouble if the FOR UPDATE/SHARE appears inside
 		 * grouping, since grouping renders a reference to individual
 		 * tuple CTIDs invalid.  This is also checked at parse time,
 		 * but that's insufficient because of rule substitution, query
 		 * pullup, etc.
 		 */
-		CheckSelectForUpdate(parse);
+		CheckSelectLocking(parse, parse->forUpdate);
 
 		/*
-		 * Currently the executor only supports FOR UPDATE at top
+		 * Currently the executor only supports FOR UPDATE/SHARE at top
 		 * level
 		 */
 		if (PlannerQueryLevel > 1)
 			ereport(ERROR,
 					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
-					 errmsg("SELECT FOR UPDATE is not allowed in subqueries")));
+					 errmsg("SELECT FOR UPDATE/SHARE is not allowed in subqueries")));
 
 		foreach(l, parse->rowMarks)
 		{