optimize_transactionidiscurrent.v1.patch

diff --git a/src/backend/access/transam/xact.c b/src/backend/access/transam/xact.c
index a36c806..83913de 100644
--- a/src/backend/access/transam/xact.c
+++ b/src/backend/access/transam/xact.c
@@ -662,6 +662,15 @@ TransactionIdIsCurrentTransactionId(TransactionId xid)
 	TransactionState s;
 
 	/*
+	 * Optimise for read only transactions. This test gives an O(1)
+	 * response for virtual transactions that haven't yet assigned an xid,
+	 * no matter how deep the tree of subtransactions goes. We reuse the
+	 * PgXact data again later, so the extra memory fetch is amortised.
+	 */
+	if (!TransactionIdIsValid(MyPgXact->xid))
+		return false;
+
+	/*
 	 * We always say that BootstrapTransactionId is "not my transaction ID"
 	 * even when it is (ie, during bootstrap).	Along with the fact that
 	 * transam.c always treats BootstrapTransactionId as already committed,
@@ -673,8 +682,18 @@ TransactionIdIsCurrentTransactionId(TransactionId xid)
 	 * Likewise, InvalidTransactionId and FrozenTransactionId are certainly
 	 * not my transaction ID, so we can just return "false" immediately for
 	 * any non-normal XID.
-	 */
-	if (!TransactionIdIsNormal(xid))
+	 *
+	 * But rather than test specifically for non-normal XIDs we just test
+	 * whether the tested xid is less than our top-level xid. Again, this
+	 * is an O(1) test in case of a deep tree of subtransactions and just
+	 * reuses the data we just cached from the above test. You might think
+	 * this test would remove about 50% of xids from search space, but
+	 * fast transactions are short lived, so this removes a greater proportion
+	 * of the search space in a fast transaction. For longer running trans-
+	 * actions the test reduces in effectiveness, eventually falling back to
+	 * being equivalent to just !TransactionIdIsNormal(xid)
+	 */
+	if (TransactionIdPrecedes(xid, MyPgXact->xid))
 		return false;
 
 	/*
@@ -682,20 +701,26 @@ TransactionIdIsCurrentTransactionId(TransactionId xid)
 	 * its subcommitted children, any of its parents, or any of their
 	 * previously subcommitted children.  However, a transaction being aborted
 	 * is no longer "current", even though it may still have an entry on the
-	 * state stack.
+	 * state stack. Walk the tree upwards from current subtransaction.
 	 */
 	for (s = CurrentTransactionState; s != NULL; s = s->parent)
 	{
 		int			low,
 					high;
 
-		if (s->state == TRANS_ABORT)
-			continue;
 		if (!TransactionIdIsValid(s->transactionId))
 			continue;			/* it can't have any child XIDs either */
+		if (s->state == TRANS_ABORT)
+			continue;			/* make unlikely test for correctness later */
 		if (TransactionIdEquals(xid, s->transactionId))
 			return true;
-		/* As the childXids array is ordered, we can use binary search */
+		/*
+		 * Search through the array of committed child subtransactions.
+		 * As the childXids array is ordered, we can use binary search.
+		 * By their nature, these xids are earlier work in an extended
+		 * transaction, so they likely span most of the remaining search
+		 * space, leaving little room for specific optimisations here.
+		 */
 		low = 0;
 		high = s->nChildXids - 1;
 		while (low <= high)