rethink_subtrans.v4.patch

diff --git a/src/backend/access/transam/varsup.c b/src/backend/access/transam/varsup.c
index a22bf375f8..e2ff7b6f2d 100644
--- a/src/backend/access/transam/varsup.c
+++ b/src/backend/access/transam/varsup.c
@@ -172,7 +172,12 @@ GetNewTransactionId(bool isSubXact)
 	 * XID before we zero the page.  Fortunately, a page of the commit log
 	 * holds 32K or more transactions, so we don't have to do this very often.
 	 *
-	 * Extend pg_subtrans and pg_commit_ts too.
+	 * Extend pg_commit_ts too. We no longer extend pg_subtrans here because
+	 * subtransaction parents are only recorded if they overflow, or if they
+	 * are used in serializable transactions. Since that considerably reduces
+	 * the read/write traffic of the subtrans module, we expect to be able
+	 * to replace that module with a simple shmem hash table rather than SLRU,
+	 * since subtrans is not persistent.
 	 */
 	ExtendCLOG(xid);
 	ExtendCommitTs(xid);
diff --git a/src/backend/access/transam/xact.c b/src/backend/access/transam/xact.c
index ca6f6d57d3..9e0a42b2a6 100644
--- a/src/backend/access/transam/xact.c
+++ b/src/backend/access/transam/xact.c
@@ -247,6 +247,7 @@ static TransactionStateData TopTransactionStateData = {
  */
 static int	nUnreportedXids;
 static TransactionId unreportedXids[PGPROC_MAX_CACHED_SUBXIDS];
+static int	nAllocatedXids;
 
 static TransactionState CurrentTransactionState = &TopTransactionStateData;
 
@@ -640,7 +641,9 @@ AssignTransactionId(TransactionState s)
 	if (!isSubXact)
 		XactTopFullTransactionId = s->fullTransactionId;
 
-	if (isSubXact)
+	if (isSubXact &&
+		(nAllocatedXids++ >= PGPROC_MAX_CACHED_SUBXIDS ||
+		 IsolationIsSerializable()))
 		SubTransSetParent(XidFromFullTransactionId(s->fullTransactionId),
 						  XidFromFullTransactionId(s->parent->fullTransactionId));
 
@@ -1997,6 +2000,7 @@ StartTransaction(void)
 	 * initialize reported xid accounting
 	 */
 	nUnreportedXids = 0;
+	nAllocatedXids = 0;
 	s->didLogXid = false;
 
 	/*
diff --git a/src/backend/storage/ipc/procarray.c b/src/backend/storage/ipc/procarray.c
index 0ccfb3a20a..9a69eec6be 100644
--- a/src/backend/storage/ipc/procarray.c
+++ b/src/backend/storage/ipc/procarray.c
@@ -262,6 +262,9 @@ static ProcArrayStruct *procArray;
 
 static PGPROC *allProcs;
 
+static TransactionId CachedSubXid = InvalidTransactionId;
+static TransactionId CachedParentXid = InvalidTransactionId;
+
 /*
  * Bookkeeping for tracking emulated transactions in recovery
  */
@@ -1425,6 +1428,8 @@ TransactionIdIsInProgress(TransactionId xid)
 	other_xids = ProcGlobal->xids;
 	other_subxidstates = ProcGlobal->subxidStates;
 
+	CachedSubXid = CachedParentXid = InvalidTransactionId;
+
 	LWLockAcquire(ProcArrayLock, LW_SHARED);
 
 	/*
@@ -1493,6 +1498,15 @@ TransactionIdIsInProgress(TransactionId xid)
 			{
 				LWLockRelease(ProcArrayLock);
 				xc_by_child_xid_inc();
+
+				/*
+				 * Remember the parent xid, for use during XactLockTableWait().
+				 * We do this because it is cheaper than looking up pg_subtrans,
+				 * and also allows us to remove pg_subtrans completely.
+				 */
+				CachedSubXid = cxid;
+				CachedParentXid = pxid;
+
 				return true;
 			}
 		}
@@ -1579,6 +1593,25 @@ TransactionIdIsInProgress(TransactionId xid)
 	return false;
 }
 
+/*
+ * Allow the topmost xid to be accessed from the cache, in a prior call to
+ * TransactionIdIsInProgress(). Specifically designed for use in
+ * XactLockTableWait()
+ */
+bool
+GetTopmostTransactionIdFromProcArray(TransactionId xid, TransactionId *pxid)
+{
+	bool found = false;
+
+	if (CachedSubXid == xid)
+	{
+		*pxid = CachedParentXid;
+		found = true;
+	}
+
+	return found;
+}
+
 /*
  * TransactionIdIsActive -- is xid the top-level XID of an active backend?
  *
@@ -2354,8 +2387,7 @@ GetSnapshotData(Snapshot snapshot)
 			xip[count++] = xid;
 
 			/*
-			 * Save subtransaction XIDs if possible (if we've already
-			 * overflowed, there's no point).  Note that the subxact XIDs must
+			 * Save subtransaction XIDs, always. Note that the subxact XIDs must
 			 * be later than their parent, so no need to check them against
 			 * xmin.  We could filter against xmax, but it seems better not to
 			 * do that much work while holding the ProcArrayLock.
@@ -2368,27 +2400,23 @@ GetSnapshotData(Snapshot snapshot)
 			 *
 			 * Again, our own XIDs are not included in the snapshot.
 			 */
-			if (!suboverflowed)
+			if (subxidStates[pgxactoff].overflowed)
+				suboverflowed = true;
+
 			{
+				int			nsubxids = subxidStates[pgxactoff].count;
 
-				if (subxidStates[pgxactoff].overflowed)
-					suboverflowed = true;
-				else
+				if (nsubxids > 0)
 				{
-					int			nsubxids = subxidStates[pgxactoff].count;
-
-					if (nsubxids > 0)
-					{
-						int			pgprocno = pgprocnos[pgxactoff];
-						PGPROC	   *proc = &allProcs[pgprocno];
+					int			pgprocno = pgprocnos[pgxactoff];
+					PGPROC	   *proc = &allProcs[pgprocno];
 
-						pg_read_barrier();	/* pairs with GetNewTransactionId */
+					pg_read_barrier();	/* pairs with GetNewTransactionId */
 
-						memcpy(snapshot->subxip + subcount,
-							   (void *) proc->subxids.xids,
-							   nsubxids * sizeof(TransactionId));
-						subcount += nsubxids;
-					}
+					memcpy(snapshot->subxip + subcount,
+						   (void *) proc->subxids.xids,
+						   nsubxids * sizeof(TransactionId));
+					subcount += nsubxids;
 				}
 			}
 		}
diff --git a/src/backend/storage/lmgr/lmgr.c b/src/backend/storage/lmgr/lmgr.c
index 2db0424ad9..a7e3472191 100644
--- a/src/backend/storage/lmgr/lmgr.c
+++ b/src/backend/storage/lmgr/lmgr.c
@@ -666,6 +666,8 @@ XactLockTableWait(TransactionId xid, Relation rel, ItemPointer ctid,
 
 	for (;;)
 	{
+		TransactionId pxid = InvalidTransactionId;
+
 		Assert(TransactionIdIsValid(xid));
 		Assert(!TransactionIdEquals(xid, GetTopTransactionIdIfAny()));
 
@@ -675,6 +677,17 @@ XactLockTableWait(TransactionId xid, Relation rel, ItemPointer ctid,
 
 		LockRelease(&tag, ShareLock, false);
 
+		/*
+		 * If a transaction has no lock, it might be a top-level
+		 * transaction, in which case it will be no longer shown as in progress.
+		 *
+		 * If a transaction is a subtransaction, then it could have committed,
+		 * but the parent (sub)transaction might still be in progress. Since
+		 * we do not remove the subxid from procarray until top-level commit
+		 * we may find it still running with this check. If not, it could
+		 * be that it is an overflowed subtransaction, in which case we need
+		 * to discover if a parent is registered for it.
+		 */
 		if (!TransactionIdIsInProgress(xid))
 			break;
 
@@ -696,7 +709,18 @@ XactLockTableWait(TransactionId xid, Relation rel, ItemPointer ctid,
 		if (!first)
 			pg_usleep(1000L);
 		first = false;
-		xid = SubTransGetTopmostTransaction(xid);
+
+		/*
+		 * In most cases, we can get the parent xid from the cache we set
+		 * when we executed TransactionIdIsInProgress(). If not, we have
+		 * to ask subtrans for the parent.
+		 * This logic would be duplicated in ConditionalXactLockTableWait().
+		 */
+		if (GetTopmostTransactionIdFromProcArray(xid, &pxid) &&
+			TransactionIdIsValid(pxid))
+			xid = pxid;
+		else
+			xid = SubTransGetTopmostTransaction(xid);
 	}
 
 	if (oper != XLTW_None)
diff --git a/src/backend/utils/time/snapmgr.c b/src/backend/utils/time/snapmgr.c
index dca1bc8afc..5f95dcea74 100644
--- a/src/backend/utils/time/snapmgr.c
+++ b/src/backend/utils/time/snapmgr.c
@@ -2256,7 +2256,8 @@ RestoreTransactionSnapshot(Snapshot snapshot, void *source_pgproc)
 bool
 XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
 {
-	uint32		i;
+	uint32		i, j;
+	bool		parent = false;
 
 	/*
 	 * Make a quick range check to eliminate most XIDs without looking at the
@@ -2273,93 +2274,67 @@ XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
 	if (TransactionIdFollowsOrEquals(xid, snapshot->xmax))
 		return true;
 
+recheck_parent:
+
 	/*
 	 * Snapshot information is stored slightly differently in snapshots taken
-	 * during recovery.
+	 * during recovery. If xip is populated, search it first, since it is
+	 * smaller and thus we assume the best place to start.
 	 */
 	if (!snapshot->takenDuringRecovery)
 	{
-		/*
-		 * If the snapshot contains full subxact data, the fastest way to
-		 * check things is just to compare the given XID against both subxact
-		 * XIDs and top-level XIDs.  If the snapshot overflowed, we have to
-		 * use pg_subtrans to convert a subxact XID to its parent XID, but
-		 * then we need only look at top-level XIDs not subxacts.
-		 */
-		if (!snapshot->suboverflowed)
-		{
-			/* we have full data, so search subxip */
-			int32		j;
-
-			for (j = 0; j < snapshot->subxcnt; j++)
-			{
-				if (TransactionIdEquals(xid, snapshot->subxip[j]))
-					return true;
-			}
-
-			/* not there, fall through to search xip[] */
-		}
-		else
-		{
-			/*
-			 * Snapshot overflowed, so convert xid to top-level.  This is safe
-			 * because we eliminated too-old XIDs above.
-			 */
-			xid = SubTransGetTopmostTransaction(xid);
-
-			/*
-			 * If xid was indeed a subxact, we might now have an xid < xmin,
-			 * so recheck to avoid an array scan.  No point in rechecking
-			 * xmax.
-			 */
-			if (TransactionIdPrecedes(xid, snapshot->xmin))
-				return false;
-		}
-
 		for (i = 0; i < snapshot->xcnt; i++)
 		{
 			if (TransactionIdEquals(xid, snapshot->xip[i]))
 				return true;
 		}
+
+		/* If we didn't find the parent here, its definitely not in snapshot */
+		if (parent)
+			return false;
 	}
-	else
+
+	/*
+	 * If a top-level xid did not overflow then we will find its subxids here,
+	 * if it is present in the snapshot.
+	 */
+	for (j = 0; j < snapshot->subxcnt; j++)
 	{
-		int32		j;
+		if (TransactionIdEquals(xid, snapshot->subxip[j]))
+			return true;
+	}
 
+	/*
+	 * If we didn't find the xid yet it must either not be in snapshot, or
+	 * in the case that a toplevel xid overflowed, it might be stored in
+	 * subtrans. This logic is important because it means we don't need
+	 * to write to subtrans until we overflow the procarray cache, greatly
+	 * reducing the traffic into subtrans.
+	 */
+	if (!parent && snapshot->suboverflowed)
+	{
 		/*
-		 * In recovery we store all xids in the subxact array because it is by
-		 * far the bigger array, and we mostly don't know which xids are
-		 * top-level and which are subxacts. The xip array is empty.
-		 *
-		 * We start by searching subtrans, if we overflowed.
+		 * Snapshot overflowed, so convert xid to top-level.  This is safe
+		 * because we eliminated too-old XIDs above.
 		 */
-		if (snapshot->suboverflowed)
-		{
-			/*
-			 * Snapshot overflowed, so convert xid to top-level.  This is safe
-			 * because we eliminated too-old XIDs above.
-			 */
-			xid = SubTransGetTopmostTransaction(xid);
+		TransactionId pxid = SubTransGetTopmostTransaction(xid);
 
-			/*
-			 * If xid was indeed a subxact, we might now have an xid < xmin,
-			 * so recheck to avoid an array scan.  No point in rechecking
-			 * xmax.
-			 */
-			if (TransactionIdPrecedes(xid, snapshot->xmin))
-				return false;
-		}
+		/* If xid wasn't a subxact, then we're done */
+		if (pxid == xid)
+			return false;
+
+		xid = pxid;
 
 		/*
-		 * We now have either a top-level xid higher than xmin or an
-		 * indeterminate xid. We don't know whether it's top level or subxact
-		 * but it doesn't matter. If it's present, the xid is visible.
+		 * If xid was indeed a subxact, we might now have an xid < xmin,
+		 * so recheck to avoid an array scan.  No point in rechecking
+		 * xmax.
 		 */
-		for (j = 0; j < snapshot->subxcnt; j++)
-		{
-			if (TransactionIdEquals(xid, snapshot->subxip[j]))
-				return true;
-		}
+		if (TransactionIdPrecedes(xid, snapshot->xmin))
+			return false;
+
+		parent = true;
+		goto recheck_parent;
 	}
 
 	return false;
diff --git a/src/include/storage/procarray.h b/src/include/storage/procarray.h
index b01fa52139..210001cceb 100644
--- a/src/include/storage/procarray.h
+++ b/src/include/storage/procarray.h
@@ -52,6 +52,7 @@ extern bool ProcArrayInstallRestoredXmin(TransactionId xmin, PGPROC *proc);
 extern RunningTransactions GetRunningTransactionData(void);
 
 extern bool TransactionIdIsInProgress(TransactionId xid);
+extern bool GetTopmostTransactionIdFromProcArray(TransactionId xid, TransactionId *pxid);
 extern bool TransactionIdIsActive(TransactionId xid);
 extern TransactionId GetOldestNonRemovableTransactionId(Relation rel);
 extern TransactionId GetOldestTransactionIdConsideredRunning(void);