Date: Sat, 13 Jul 2013 14:41:57 +0530
From: Abhijit Menon-Sen <ams@2ndQuadrant.com>
To: Jeff Janes <jeff.janes@gmail.com>
Cc: Josh Berkus <josh@agliodbs.com>, Simon Riggs <simon@2ndquadrant.com>,
 Mark Kirkwood <mark.kirkwood@catalyst.net.nz>,
 Tom Lane <tgl@sss.pgh.pa.us>, Gavin Flower <gavinflower@archidevsys.co.nz>,
 pgsql-hackers@postgresql.org
Subject: Re: [PERFORM] In progress INSERT wrecks plans on table
Message-ID: <20130713091157.GB1011@toroid.org>
References: <51870CB6.6090404@catalyst.net.nz>
 <CA+U5nMJHgHczmWrKzst=PJeP+9BHJAsTgRNXyVZX5Oyys2zn_g@mail.gmail.com>
 <20130624044350.GA32322@toroid.org>
 <WM!ecf8a06e8ffb427fca7f6e0f4ff5638515a78282eced37d2e4f9981c1e769de67caec13f84aa60888557e9af7b43dca1!@asav-2.01.com>
 <51DAF2C8.6010705@agliodbs.com>
 <WM!26a3c5a0f97d399bf3d258d64ee1eee5843f0b45f9801c411e8f5e0770f3c25a892f527c93229c57bfa8f0f3eb6066dc!@asav-2.01.com>
 <51DD9026.2030107@agliodbs.com> <20130711050958.GA23755@toroid.org>
 <CAMkU=1z8iyZ6ajtBHVGcZ05fMUhu3HCekqqsT6BKnksAzmk8fA@mail.gmail.com>
 <20130713084923.GA1011@toroid.org>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="tThc/1wpZn/ma/RB"
Content-Disposition: inline
In-Reply-To: <20130713084923.GA1011@toroid.org>
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org


--tThc/1wpZn/ma/RB
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

At 2013-07-13 14:19:23 +0530, ams@2ndQuadrant.com wrote:
>
> The timings above are with both xid_in_snapshot_cache.v1.patch and
> cache_TransactionIdInProgress.v2.patch applied

For anyone who wants to try to reproduce the results, here's the patch I
used, which is both patches above plus some typo fixes in comments.

-- Abhijit

--tThc/1wpZn/ma/RB
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment; filename="inprogress.diff"

diff --git a/src/backend/storage/ipc/procarray.c b/src/backend/storage/ipc/procarray.c
index c2f86ff..660fab0 100644
--- a/src/backend/storage/ipc/procarray.c
+++ b/src/backend/storage/ipc/procarray.c
@@ -840,6 +840,9 @@ TransactionIdIsInProgress(TransactionId xid)
 	TransactionId topxid;
 	int			i,
 				j;
+	static	int	pgprocno = -1;	/* cached last pgprocno */
+	static TransactionId pxid;	/* cached last parent xid */
+	static TransactionId cxid;	/* cached last child xid */
 
 	/*
 	 * Don't bother checking a transaction older than RecentXmin; it could not
@@ -875,6 +878,60 @@ TransactionIdIsInProgress(TransactionId xid)
 	}
 
 	/*
+	 * Check to see if we have cached the pgprocno for the xid we seek.
+	 * We will have cached either pxid only or both pxid and cxid.
+	 * So we check to see whether pxid or cxid matches the xid we seek,
+	 * but then re-check just the parent pxid. If the PGXACT doesn't
+	 * match then the transaction must be complete because an xid is
+	 * only associated with one PGPROC/PGXACT during its lifetime
+	 * except when we are using prepared transactions.
+	 * Transaction wraparound is not a concern because we are checking
+	 * the status of an xid we see in data and that might be running;
+	 * anything very old will already be deleted or frozen. So stale
+	 * cached values for pxid and cxid don't affect the correctness
+	 * of the result.
+	 */
+	if (max_prepared_xacts == 0 && pgprocno >= 0 &&
+		(TransactionIdEquals(xid, pxid) || TransactionIdEquals(xid, cxid)))
+	{
+		volatile PGXACT *pgxact;
+
+		pgxact = &allPgXact[pgprocno];
+
+		pxid = pgxact->xid;
+
+		/*
+		 * XXX Can we test without the lock first? If the values don't
+		 * match without the lock they never will match...
+		 */
+
+		/*
+		 * xid matches, so wait for the lock and re-check.
+		 */
+		LWLockAcquire(ProcArrayLock, LW_SHARED);
+
+		pxid = pgxact->xid;
+
+		if (TransactionIdIsValid(pxid) && TransactionIdEquals(pxid, xid))
+		{
+			LWLockRelease(ProcArrayLock);
+			return true;
+		}
+
+		LWLockRelease(ProcArrayLock);
+
+		pxid = cxid = InvalidTransactionId;
+		return false;
+	}
+
+	/*
+	 * Our cache didn't match, so zero the cxid so that when we reset pxid
+	 * we don't become confused that the cxid and pxid still relate.
+	 * cxid will be reset to something useful later, if approproate.
+	 */
+	cxid = InvalidTransactionId;
+
+	/*
 	 * If first time through, get workspace to remember main XIDs in. We
 	 * malloc it permanently to avoid repeated palloc/pfree overhead.
 	 */
@@ -910,10 +967,12 @@ TransactionIdIsInProgress(TransactionId xid)
 	/* No shortcuts, gotta grovel through the array */
 	for (i = 0; i < arrayP->numProcs; i++)
 	{
-		int			pgprocno = arrayP->pgprocnos[i];
-		volatile PGPROC *proc = &allProcs[pgprocno];
-		volatile PGXACT *pgxact = &allPgXact[pgprocno];
-		TransactionId pxid;
+		volatile PGPROC *proc;
+		volatile PGXACT *pgxact;
+
+		pgprocno = arrayP->pgprocnos[i];
+		proc = &allProcs[pgprocno];
+		pgxact = &allPgXact[pgprocno];
 
 		/* Ignore my own proc --- dealt with it above */
 		if (proc == MyProc)
@@ -948,7 +1007,7 @@ TransactionIdIsInProgress(TransactionId xid)
 		for (j = pgxact->nxids - 1; j >= 0; j--)
 		{
 			/* Fetch xid just once - see GetNewTransactionId */
-			TransactionId cxid = proc->subxids.xids[j];
+			cxid = proc->subxids.xids[j];
 
 			if (TransactionIdEquals(cxid, xid))
 			{
@@ -975,6 +1034,14 @@ TransactionIdIsInProgress(TransactionId xid)
 	 */
 	if (RecoveryInProgress())
 	{
+		/*
+		 * Hot Standby doesn't use pgprocno, so we can clear the cache.
+		 *
+		 * XXX we could try to remember the offset into the KnownAssignedXids
+		 * array, which is a possibility for another day.
+		 */
+		pxid = cxid = InvalidTransactionId;
+
 		/* none of the PGXACT entries should have XIDs in hot standby mode */
 		Assert(nxids == 0);
 
@@ -999,6 +1066,12 @@ TransactionIdIsInProgress(TransactionId xid)
 	LWLockRelease(ProcArrayLock);
 
 	/*
+	 * After this point we don't remember pgprocno, so the cache is
+	 * no use to us anymore.
+	 */
+	pxid = cxid = InvalidTransactionId;
+
+	/*
 	 * If none of the relevant caches overflowed, we know the Xid is not
 	 * running without even looking at pg_subtrans.
 	 */
@@ -1509,6 +1582,9 @@ GetSnapshotData(Snapshot snapshot)
 
 	snapshot->curcid = GetCurrentCommandId(false);
 
+	/* Initialise the single xid cache for this snapshot */
+	snapshot->xid_in_snapshot = InvalidTransactionId;
+
 	/*
 	 * This is a new snapshot, so set both refcounts are zero, and mark it as
 	 * not copied in persistent memory.
diff --git a/src/backend/utils/time/tqual.c b/src/backend/utils/time/tqual.c
index 55563ea..dc4bf54 100644
--- a/src/backend/utils/time/tqual.c
+++ b/src/backend/utils/time/tqual.c
@@ -1533,6 +1533,25 @@ XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
 		return true;
 
 	/*
+	 * If we've seen this xid last time then we use our cached knowledge
+	 * to allow a fast path out.
+	 *
+	 * When XidInMVCCSnapshot is called repeatedly in a transaction it
+	 * is usually because we're viewing the results of large transactions.
+	 * Typically there will be just one big concurrent transaction and so
+	 * it's very fast to just remember that and be done. Lots of short
+	 * transactions don't cause problems because their xids quickly go
+	 * above the snapshot's xmax and get ignored before we get here.
+	 *
+	 * XXX If there were more big concurrent transactions then it would make
+	 * sense to remember a list of xids in an LRU scheme. For long lists it
+	 * would make better sense to sort the snapshot xids. Both of those
+	 * ideas have much more complex code and diminishing returns.
+	 */
+	if (TransactionIdEquals(xid, snapshot->xid_in_snapshot))
+		return true;
+
+	/*
 	 * Snapshot information is stored slightly differently in snapshots taken
 	 * during recovery.
 	 */
@@ -1553,7 +1572,10 @@ XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
 			for (j = 0; j < snapshot->subxcnt; j++)
 			{
 				if (TransactionIdEquals(xid, snapshot->subxip[j]))
+				{
+					snapshot->xid_in_snapshot = xid;
 					return true;
+				}
 			}
 
 			/* not there, fall through to search xip[] */
@@ -1575,7 +1597,10 @@ XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
 		for (i = 0; i < snapshot->xcnt; i++)
 		{
 			if (TransactionIdEquals(xid, snapshot->xip[i]))
+			{
+				snapshot->xid_in_snapshot = xid;
 				return true;
+			}
 		}
 	}
 	else
@@ -1611,7 +1636,10 @@ XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
 		for (j = 0; j < snapshot->subxcnt; j++)
 		{
 			if (TransactionIdEquals(xid, snapshot->subxip[j]))
+			{
+				snapshot->xid_in_snapshot = xid;
 				return true;
+			}
 		}
 	}
 
diff --git a/src/include/utils/snapshot.h b/src/include/utils/snapshot.h
index e747191..605895e 100644
--- a/src/include/utils/snapshot.h
+++ b/src/include/utils/snapshot.h
@@ -56,6 +56,12 @@ typedef struct SnapshotData
 	bool		copied;			/* false if it's a static snapshot */
 
 	/*
+	 * Single transaction cache. Keep track of common xid so we can respond
+	 * quickly when we keep seeing an xid while we use this snapshot.
+	 */
+	TransactionId xid_in_snapshot;
+
+	/*
 	 * note: all ids in subxip[] are >= xmin, but we don't bother filtering
 	 * out any that are >= xmax
 	 */

--tThc/1wpZn/ma/RB
Content-Type: text/plain
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
MIME-Version: 1.0


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

--tThc/1wpZn/ma/RB--