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.

3 files changed, 31 insertions, 18 deletions

diff --git a/src/backend/executor/README b/src/backend/executor/README
index 0d3e16b6d9a..00e503744e4 100644
--- a/src/backend/executor/README
+++ b/src/backend/executor/README
@@ -1,4 +1,4 @@
-$PostgreSQL: pgsql/src/backend/executor/README,v 1.4 2003/11/29 19:51:48 pgsql Exp $
+$PostgreSQL: pgsql/src/backend/executor/README,v 1.5 2005/04/28 21:47:12 tgl Exp $
 
 The Postgres Executor
 ---------------------
@@ -154,8 +154,8 @@ committed by the concurrent transaction (after waiting for it to commit,
 if need be) and re-evaluate the query qualifications to see if it would
 still meet the quals.  If so, we regenerate the updated tuple (if we are
 doing an UPDATE) from the modified tuple, and finally update/delete the
-modified tuple.  SELECT FOR UPDATE behaves similarly, except that its action
-is just to mark the modified tuple for update by the current transaction.
+modified tuple.  SELECT FOR UPDATE/SHARE behaves similarly, except that its
+action is just to lock the modified tuple.
 
 To implement this checking, we actually re-run the entire query from scratch
 for each modified tuple, but with the scan node that sourced the original
@@ -184,14 +184,14 @@ that while we are executing a recheck query for one modified tuple, we will
 hit another modified tuple in another relation.  In this case we "stack up"
 recheck queries: a sub-recheck query is spawned in which both the first and
 second modified tuples will be returned as the only components of their
-relations.  (In event of success, all these modified tuples will be marked
-for update.)  Again, this isn't necessarily quite the right thing ... but in
-simple cases it works.  Potentially, recheck queries could get nested to the
-depth of the number of FOR UPDATE relations in the query.
+relations.  (In event of success, all these modified tuples will be locked.)
+Again, this isn't necessarily quite the right thing ... but in simple cases
+it works.  Potentially, recheck queries could get nested to the depth of the
+number of FOR UPDATE/SHARE relations in the query.
 
 It should be noted also that UPDATE/DELETE expect at most one tuple to
 result from the modified query, whereas in the FOR UPDATE case it's possible
 for multiple tuples to result (since we could be dealing with a join in
 which multiple tuples join to the modified tuple).  We want FOR UPDATE to
-mark all relevant tuples, so we pass all tuples output by all the stacked
-recheck queries back to the executor toplevel for marking.
+lock all relevant tuples, so we pass all tuples output by all the stacked
+recheck queries back to the executor toplevel for locking.
diff --git a/src/backend/executor/execMain.c b/src/backend/executor/execMain.c
index 8facabbadad..3e2b986034c 100644
--- a/src/backend/executor/execMain.c
+++ b/src/backend/executor/execMain.c
@@ -26,7 +26,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/executor/execMain.c,v 1.246 2005/04/14 01:38:17 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/executor/execMain.c,v 1.247 2005/04/28 21:47:12 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -560,9 +560,10 @@ InitPlan(QueryDesc *queryDesc, bool explainOnly)
 	}
 
 	/*
-	 * Have to lock relations selected for update
+	 * Have to lock relations selected FOR UPDATE/FOR SHARE
 	 */
 	estate->es_rowMark = NIL;
+	estate->es_forUpdate = parseTree->forUpdate;
 	if (parseTree->rowMarks != NIL)
 	{
 		ListCell   *l;
@@ -986,7 +987,7 @@ ExecEndPlan(PlanState *planstate, EState *estate)
 		heap_close(estate->es_into_relation_descriptor, NoLock);
 
 	/*
-	 * close any relations selected FOR UPDATE, again keeping locks
+	 * close any relations selected FOR UPDATE/FOR SHARE, again keeping locks
 	 */
 	foreach(l, estate->es_rowMark)
 	{
@@ -1126,6 +1127,9 @@ lnext:	;
 										 * ctid!! */
 				tupleid = &tuple_ctid;
 			}
+			/*
+			 * Process any FOR UPDATE or FOR SHARE locking requested.
+			 */
 			else if (estate->es_rowMark != NIL)
 			{
 				ListCell   *l;
@@ -1137,6 +1141,7 @@ lnext:	;
 					Buffer		buffer;
 					HeapTupleData tuple;
 					TupleTableSlot *newSlot;
+					LockTupleMode	lockmode;
 					HTSU_Result		test;
 
 					if (!ExecGetJunkAttribute(junkfilter,
@@ -1151,9 +1156,15 @@ lnext:	;
 					if (isNull)
 						elog(ERROR, "\"%s\" is NULL", erm->resname);
 
+					if (estate->es_forUpdate)
+						lockmode = LockTupleExclusive;
+					else
+						lockmode = LockTupleShared;
+
 					tuple.t_self = *((ItemPointer) DatumGetPointer(datum));
-					test = heap_mark4update(erm->relation, &tuple, &buffer,
-											estate->es_snapshot->curcid);
+					test = heap_lock_tuple(erm->relation, &tuple, &buffer,
+										  estate->es_snapshot->curcid,
+										  lockmode);
 					ReleaseBuffer(buffer);
 					switch (test)
 					{
@@ -1189,7 +1200,7 @@ lnext:	;
 							goto lnext;
 
 						default:
-							elog(ERROR, "unrecognized heap_mark4update status: %u",
+							elog(ERROR, "unrecognized heap_lock_tuple status: %u",
 								 test);
 							return (NULL);
 					}
@@ -1574,8 +1585,8 @@ ExecUpdate(TupleTableSlot *slot,
 	 * If we generate a new candidate tuple after EvalPlanQual testing, we
 	 * must loop back here and recheck constraints.  (We don't need to
 	 * redo triggers, however.	If there are any BEFORE triggers then
-	 * trigger.c will have done mark4update to lock the correct tuple, so
-	 * there's no need to do them again.)
+	 * trigger.c will have done heap_lock_tuple to lock the correct tuple,
+	 * so there's no need to do them again.)
 	 */
 lreplace:;
 	if (resultRelationDesc->rd_att->constr)
@@ -2088,6 +2099,7 @@ EvalPlanQualStart(evalPlanQual *epq, EState *estate, evalPlanQual *priorepq)
 		epqstate->es_param_exec_vals = (ParamExecData *)
 			palloc0(estate->es_topPlan->nParamExec * sizeof(ParamExecData));
 	epqstate->es_rowMark = estate->es_rowMark;
+	epqstate->es_forUpdate = estate->es_forUpdate;
 	epqstate->es_instrument = estate->es_instrument;
 	epqstate->es_select_into = estate->es_select_into;
 	epqstate->es_into_oids = estate->es_into_oids;
diff --git a/src/backend/executor/execUtils.c b/src/backend/executor/execUtils.c
index 905c7f89f61..133bf57bca2 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.122 2005/04/23 21:32:34 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/executor/execUtils.c,v 1.123 2005/04/28 21:47:12 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -198,6 +198,7 @@ CreateExecutorState(void)
 	estate->es_processed = 0;
 	estate->es_lastoid = InvalidOid;
 	estate->es_rowMark = NIL;
+	estate->es_forUpdate = false;
 
 	estate->es_instrument = false;
 	estate->es_select_into = false;