hint bit cache v5

diff --git a/src/backend/utils/time/tqual.c b/src/backend/utils/time/tqual.c
old mode 100644
new mode 100755
index 2fd32e0..d734626
--- a/src/backend/utils/time/tqual.c
+++ b/src/backend/utils/time/tqual.c
@@ -7,12 +7,27 @@
  * "hint" status bits if we see that the inserting or deleting transaction
  * has now committed or aborted (and it is safe to set the hint bits).
  * If the hint bits are changed, SetBufferCommitInfoNeedsSave is called on
  * the passed-in buffer.  The caller must hold not only a pin, but at least
  * shared buffer content lock on the buffer containing the tuple.
  *
+ * Hint bits are maintained directly on the tuple itself and on a separate
+ * in-memory cache.  If the hint bit is found from the cache, the hint bit
+ * is set on the tuple but the page is not marked dirty.  This is done to
+ * reduce i/o resulting from hint bit only changes.  The cache itself is
+ * exactly like the clog page, and uses a similar page size, but does not
+ * have to.  Cache maintenance occurs every Nth (typically 100) cache miss
+ * that successfully fetches the transaction status from clog.
+ *
+ * It's tempting to try and expand the simple last transaction status in
+ * transam.c but this check happens too late in the critical visibility
+ * routines to provide much benefit.  For the fastest possible cache
+ * performance with the least amount of impact on scan heavy cases, you have
+ * to maintain the cache here if you want to avoid dirtying the page
+ * based on interaction with the cache.
+ *
  * NOTE: must check TransactionIdIsInProgress (which looks in PGPROC array)
  * before TransactionIdDidCommit/TransactionIdDidAbort (which look in
  * pg_clog).  Otherwise we have a race condition: we might decide that a
  * just-committed transaction crashed, because none of the tests succeed.
  * xact.c is careful to record commit/abort in pg_clog before it unsets
  * MyProc->xid in PGPROC array.  That fixes that problem, but it also
@@ -69,26 +84,297 @@
 /* Static variables representing various special snapshot semantics */
 SnapshotData SnapshotNowData = {HeapTupleSatisfiesNow};
 SnapshotData SnapshotSelfData = {HeapTupleSatisfiesSelf};
 SnapshotData SnapshotAnyData = {HeapTupleSatisfiesAny};
 SnapshotData SnapshotToastData = {HeapTupleSatisfiesToast};
 
+/* hint bit cache definitions and structures */
+
+#define HBCACHE_PAGESZ 8192
+/* 8192 bytes of stororage in each hint bit cache page */
+#define HBCACHE_PAGE_COUNT 4		/* how many pages to keep */
+#define HBCACHE_ROLLUPSZ 100
+/* 100 cache misses are stored in array before re-filling cache */
+#define HBCACHE_HIT_THRESHOLD 5
+/* cache pagees with less than 5 interesting transactions per cache re-fill
+ * are not considered interesting
+ */
+
+#define HBCACHE_BITS_PER_XACT	2
+#define HBCACHE_XACTS_PER_BYTE	4
+#define HBCACHE_XACTS_PER_PAGE	(HBCACHE_PAGESZ * HBCACHE_XACTS_PER_BYTE)
+#define HBCACHE_XACT_BITMASK	((1 << HBCACHE_BITS_PER_XACT) - 1)
+
+#define HBCACHE_COMITTED 1
+#define HBCACHE_INVALID  2
+
+#define HBCache_TransactionIdToPage(xid)	((xid) / (TransactionId) HBCACHE_XACTS_PER_PAGE)
+#define HBCache_TransactionIdToPgIndex(xid) ((xid) % (TransactionId) HBCACHE_XACTS_PER_PAGE)
+#define HBCache_TransactionIdToByte(xid)	(HBCache_TransactionIdToPgIndex(xid) / HBCACHE_XACTS_PER_BYTE)
+#define HBCache_TransactionIdToBIndex(xid)	((xid) % (TransactionId) HBCACHE_XACTS_PER_BYTE)
+
+
+/* describes a hint bit page in memory */
+typedef struct
+{
+	int XidPage;  /* this page describes a range of transaction ids */
+	int HitCount;	/* number of cache hits on this page */
+	bool Clear;
+	/* during rollup, signals the page is changing and cache data needs to
+	 * be cleared
+	 */
+} HintBitCachePageHeader;
+
 /* local functions */
 static bool XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot);
 
+static HintBitCachePageHeader HintbitCachePageList[HBCACHE_PAGE_COUNT]
+	= {{-1, 0, false}, {-1, 0, false}, {-1, 0, false}, {-1, 0, false}};
+static char HintBitCachePageList[HBCACHE_PAGE_COUNT][HBCACHE_PAGESZ];
+static int HintBitCachePageRollupList[HBCACHE_ROLLUPSZ];
+static int HintBitCacheMissCount = 0;
+
+/* qsort comparison function */
+static int
+int_cmp(const void *p1, const void *p2)
+{
+	int v1 = *((const int *) p1);
+	int v2 = *((const int *) p2);
+
+	if (v1 < v2)
+		return -1;
+	if (v1 > v2)
+		return 1;
+	return 0;
+}
+
+/*
+ * RollUpHintBitCache()
+ *
+ * Whenever a transaction is checked against the hint bit cache and the status
+ * is not there (a cache miss), the transaction's page is added to the
+ * rollup array. When that array fills, the rollup array is processed into
+ * a new set of cache pages.
+ *
+ * The algorithm is to sort the rollup array and iterate it counting the
+ * number of identical pages as we go.  When we hit a new page (or the
+ * end of the array) and the number of counted pages is over a minimum
+ * threshold, the page is moved into the cache if it has more cache hits
+ * than any page that is already in the cache.
+ */
+static void RollUpHintBitCache()
+{
+	TransactionId LastPage = HintBitCachePageRollupList[0];
+	/* The page we are duplicate tracking. */
+
+	int PageIdx;
+	int HitCount = 0;
+	/* effectively initializes to 1: the first iteration of the loop will
+	 * always match LastPage and increment this value
+	 */
+
+	int Page;
+	int PageMinHits = HBCACHE_ROLLUPSZ + 1;
+	/* The smallest number of hits for a page currently in the cache. It's
+	 * scanned comparing as we go, so initialize it to an impossibly high
+	 * value here */
+
+	int PageMinIdx;
+	/* The cache page index of the page with the smallest number of hits.
+	 * if a new cache page higher number of hits with this one, it is
+	 * swapped in its place.
+	 */
+	int XidPage;
+
+	bool AlreadyInCache;
+
+	/* sort the list in order to make counting identical pages easier */
+	qsort(HintBitCachePageRollupList, HBCACHE_ROLLUPSZ, sizeof(int), int_cmp);
+
+	for (PageIdx = 0; PageIdx < HBCACHE_ROLLUPSZ; PageIdx++)
+	{
+		/* If page is the same as the last one, increment the hitcount
+		 * or reset it and do cache management based on the number of hits
+		 */
+		XidPage = HintBitCachePageRollupList[PageIdx];
+
+		if(XidPage == LastPage)
+		        HitCount++;
+		else
+		{
+			/* Now check the page represented by LastPage to see if its
+			 * interesting for cache purposes.  To avoid thrashing cache pages
+			 * in and out, a minimum threshold of hits has to be met before
+			 * putting a page in the cache.
+			 */
+			if (HitCount >= HBCACHE_HIT_THRESHOLD)
+			{
+CheckLastXidBlock:
+				/* Look through the pages, find the one with the smallest
+				 * hit count, and save off the index.
+				 */
+				AlreadyInCache = false;
+
+				for (Page = 0; Page < HBCACHE_PAGE_COUNT; Page++)
+				{
+					if (HintbitCachePageList[Page].HitCount < PageMinHits)
+					{
+						PageMinIdx = Page;
+						PageMinHits = HintbitCachePageList[Page].HitCount;
+					}
+
+					/* If this page is alredy in the cache, we can leave it
+					 * an without clearing it.
+					 */
+					if (HintbitCachePageList[Page].XidPage == LastPage)
+						AlreadyInCache = true;
+				}
+
+				/* does the page we are examining have a higher number of
+				 * cache hits than any page currently in the cache?
+				 */
+				if (!AlreadyInCache && HitCount > PageMinHits)
+				{
+					/* mark the cache buffer with the new page, hint count
+					 * and clear flag.
+					 */
+					HintbitCachePageList[PageMinIdx].XidPage = LastPage;
+					HintbitCachePageList[PageMinIdx].HitCount = HitCount;
+					HintbitCachePageList[PageMinIdx].Clear = true;
+				}
+			}
+
+			/* reset the hit count, since we've already technically already
+			 * seen this page in this iteration, HitCount is initialized
+			 * to 1, and this page is now the one tracked via LastPage.
+			 */
+			HitCount = 1;
+			LastPage = XidPage;
+		}
+	}
+
+	/* When the loop is exited, the last block of identical pages may have
+	 * never gotten checked via the XidPage == LastPage condition.
+	 * Sneakily jump back into the loop if necessary.
+	 *
+	 * jump back into the loop to check it but decrement PageIdx first so
+	 * that the final LastPage assignment does't look outside the array.
+	 */
+	if(HitCount >= HBCACHE_HIT_THRESHOLD)
+	{
+		/* Since HitCount is reset when a page is processed, checking it
+		 * is enough to guarantee the last page in the loop was never
+		 * processed.
+		 */
+		goto CheckLastXidBlock;
+	}
+
+	/* Cache pages that are new have to be cleared.  Look for ones marked as
+	 * such and reset the hit count for all pages.
+	 */
+	for (Page = 0; Page < HBCACHE_PAGE_COUNT; Page++)
+	{
+		if(HintbitCachePageList[PageMinIdx].Clear)
+			memset(HintBitCachePageList[Page], 0, HBCACHE_PAGESZ);
+
+		HintbitCachePageList[PageMinIdx].Clear = 0;
+		HintbitCachePageList[PageMinIdx].HitCount = 0;
+	}
+
+	HintBitCacheMissCount = 0;
+	return;
+}
+
+/*
+ * HintBitCacheXidStatus()
+ *
+ * Compute the page for a TransactionId, and compare it against the pages
+ * currently in the cache.  If the page is found, resolve the hint bit
+ * status's position in the block and return it.
+ */
+static inline int
+HintBitCacheXidStatus(TransactionId xid)
+{
+	int XidPage = HBCache_TransactionIdToPage(xid);
+	int Page;
+
+	for(Page = 0; Page < HBCACHE_PAGE_COUNT; Page++)
+	{
+		/* is the transaction status in the range defined by the page? */
+		if(HintbitCachePageList[Page].XidPage == XidPage)
+		{
+			int	byteno = HBCache_TransactionIdToByte(xid);
+			int bshift = HBCache_TransactionIdToBIndex(xid) * HBCACHE_BITS_PER_XACT;
+			char *byteptr = HintBitCachePageList[Page] + byteno;
+
+			return (*byteptr >> bshift) & HBCACHE_XACT_BITMASK;
+		}
+	}
+
+	return 0;
+}
+
+/*
+ * SetXidInHintBitCache()
+ *
+ * Compute the page for a TransactionId, and compare it against the pages
+ * currently in the cache.  If the page is found, compute the bit position
+ * and set it to 1 (true).  If it is not found, put the TransactionId in the
+ * array that holds cache misses.  If that array fills, rebuild the cache.
+ */
+static inline void
+SetXidInHintBitCache(TransactionId xid, int hbcache_status)
+{
+	int XidPage = HBCache_TransactionIdToPage(xid);
+	int Page;
+
+	for(Page = 0; Page < HBCACHE_PAGE_COUNT; Page++)
+	{
+	    if(XidPage == HintbitCachePageList[Page].XidPage)
+	    {
+			int	byteno = HBCache_TransactionIdToByte(xid);
+			int bshift = HBCache_TransactionIdToBIndex(xid) * HBCACHE_BITS_PER_XACT;
+			char *byteptr = HintBitCachePageList[Page] + byteno;
+			char byteval = *byteptr;
+
+			byteval &= ~(((1 << HBCACHE_BITS_PER_XACT) - 1) << bshift);
+			byteval |= (hbcache_status << bshift);
+			*byteptr = byteval;
+
+			/* there is a minute chance of overflow here, but it doesn't
+			 * seem worthwhile to test for it
+			 */
+			HintbitCachePageList[Page].HitCount++;
+			break;
+		}
+	}
+
+	HintBitCachePageRollupList[HintBitCacheMissCount++] = XidPage;
+
+	/* Enough transactions have fallen through the cache that it's time to
+	 * rebuild it.  Hopefully we don't have to do this too often
+	 */
+	if (HintBitCacheMissCount == HBCACHE_ROLLUPSZ)
+		RollUpHintBitCache();
+
+	return;
+}
+
 
 /*
  * SetHintBits()
  *
  * Set commit/abort hint bits on a tuple, if appropriate at this time.
  *
  * It is only safe to set a transaction-committed hint bit if we know the
  * transaction's commit record has been flushed to disk.  We cannot change
  * the LSN of the page here because we may hold only a share lock on the
  * buffer, so we can't use the LSN to interlock this; we have to just refrain
  * from setting the hint bit until some future re-examination of the tuple.
+ * The ability of the hint bit to be set is returned to the caller (the hint
+ * bit cache only saves safe bits in the cache to avoid repeated checks).
  *
  * We can always set hint bits when marking a transaction aborted.	(Some
  * code in heapam.c relies on that!)
  *
  * Also, if we are cleaning up HEAP_MOVED_IN or HEAP_MOVED_OFF entries, then
  * we can always set the hint bits, since pre-9.0 VACUUM FULL always used
@@ -101,27 +387,35 @@ static bool XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot);
  * Normal commits may be asynchronous, so for those we need to get the LSN
  * of the transaction and then check whether this is flushed.
  *
  * The caller should pass xid as the XID of the transaction to check, or
  * InvalidTransactionId if no check is needed.
  */
-static inline void
+static inline bool
 SetHintBits(HeapTupleHeader tuple, Buffer buffer,
 			uint16 infomask, TransactionId xid)
 {
 	if (TransactionIdIsValid(xid))
 	{
 		/* NB: xid must be known committed here! */
 		XLogRecPtr	commitLSN = TransactionIdGetCommitLSN(xid);
 
 		if (XLogNeedsFlush(commitLSN))
-			return;				/* not flushed yet, so don't set hint */
+			return false;			/* not flushed yet, so don't set hint */
 	}
 
 	tuple->t_infomask |= infomask;
 	SetBufferCommitInfoNeedsSave(buffer);
+	return true;
+}
+
+static inline void
+SetHintBitsCache(HeapTupleHeader tuple, Buffer buffer,
+				uint16 infomask, TransactionId xid)
+{
+	tuple->t_infomask |= infomask;
 }
 
 /*
  * HeapTupleSetHintBits --- exported version of SetHintBits()
  *
  * This must be separate because of C99's brain-dead notions about how to
@@ -911,91 +1205,127 @@ HeapTupleSatisfiesDirty(HeapTupleHeader tuple, Snapshot snapshot,
 bool
 HeapTupleSatisfiesMVCC(HeapTupleHeader tuple, Snapshot snapshot,
 					   Buffer buffer)
 {
 	if (!(tuple->t_infomask & HEAP_XMIN_COMMITTED))
 	{
+		int hbcache_status;
+
 		if (tuple->t_infomask & HEAP_XMIN_INVALID)
 			return false;
 
-		/* Used by pre-9.0 binary upgrades */
-		if (tuple->t_infomask & HEAP_MOVED_OFF)
-		{
-			TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
+		hbcache_status = HintBitCacheXidStatus(HeapTupleHeaderGetXmin(tuple));
 
-			if (TransactionIdIsCurrentTransactionId(xvac))
-				return false;
-			if (!TransactionIdIsInProgress(xvac))
-			{
-				if (TransactionIdDidCommit(xvac))
-				{
-					SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
-								InvalidTransactionId);
-					return false;
-				}
-				SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
-							InvalidTransactionId);
-			}
+		if (hbcache_status == HBCACHE_COMITTED)
+		{
+			/* The hint bit was not set on the tuple, but it was set in the
+			 * cache.  Since cache bits are only set if the transaction's
+			 * commit record has been flushed to disk, we can call a quicker
+			 * version of SetHintBits that does not check the commit record
+			 * and, because the page is not marked dirty, does not have to
+			 * lock the buffer.
+			 */
+	        SetHintBitsCache(tuple, buffer, HEAP_XMIN_COMMITTED,
+                                HeapTupleHeaderGetXmin(tuple));
 		}
-		/* Used by pre-9.0 binary upgrades */
-		else if (tuple->t_infomask & HEAP_MOVED_IN)
+		else if (hbcache_status == HBCACHE_INVALID)
 		{
-			TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
+	        SetHintBitsCache(tuple, buffer, HEAP_XMIN_INVALID,
+                                HeapTupleHeaderGetXmin(tuple));
 
-			if (!TransactionIdIsCurrentTransactionId(xvac))
+			return false;
+		}
+		else
+		{
+			/* Used by pre-9.0 binary upgrades */
+			if (tuple->t_infomask & HEAP_MOVED_OFF)
 			{
-				if (TransactionIdIsInProgress(xvac))
+				TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
+
+				if (TransactionIdIsCurrentTransactionId(xvac))
 					return false;
-				if (TransactionIdDidCommit(xvac))
+				if (!TransactionIdIsInProgress(xvac))
+				{
+					if (TransactionIdDidCommit(xvac))
+					{
+						SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
+									InvalidTransactionId);
+						return false;
+					}
 					SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
 								InvalidTransactionId);
-				else
+				}
+			}
+			/* Used by pre-9.0 binary upgrades */
+			else if (tuple->t_infomask & HEAP_MOVED_IN)
+			{
+				TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
+
+				if (!TransactionIdIsCurrentTransactionId(xvac))
 				{
-					SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
-								InvalidTransactionId);
-					return false;
+					if (TransactionIdIsInProgress(xvac))
+						return false;
+					if (TransactionIdDidCommit(xvac))
+						SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
+									InvalidTransactionId);
+					else
+					{
+						SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
+									InvalidTransactionId);
+						return false;
+					}
 				}
 			}
-		}
-		else if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tuple)))
-		{
-			if (HeapTupleHeaderGetCmin(tuple) >= snapshot->curcid)
-				return false;	/* inserted after scan started */
+			else if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tuple)))
+			{
+				if (HeapTupleHeaderGetCmin(tuple) >= snapshot->curcid)
+					return false;	/* inserted after scan started */
 
-			if (tuple->t_infomask & HEAP_XMAX_INVALID)	/* xid invalid */
-				return true;
+				if (tuple->t_infomask & HEAP_XMAX_INVALID)	/* xid invalid */
+					return true;
 
-			if (tuple->t_infomask & HEAP_IS_LOCKED)		/* not deleter */
-				return true;
+				if (tuple->t_infomask & HEAP_IS_LOCKED)		/* not deleter */
+					return true;
 
-			Assert(!(tuple->t_infomask & HEAP_XMAX_IS_MULTI));
+				Assert(!(tuple->t_infomask & HEAP_XMAX_IS_MULTI));
 
-			if (!TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmax(tuple)))
-			{
-				/* deleting subtransaction must have aborted */
-				SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
-							InvalidTransactionId);
-				return true;
+				if (!TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmax(tuple)))
+				{
+					/* deleting subtransaction must have aborted */
+					SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
+								InvalidTransactionId);
+					return true;
+				}
+
+				if (HeapTupleHeaderGetCmax(tuple) >= snapshot->curcid)
+					return true;	/* deleted after scan started */
+				else
+					return false;	/* deleted before scan started */
 			}
+			else if (TransactionIdIsInProgress(HeapTupleHeaderGetXmin(tuple)))
+				return false;
+			else if (TransactionIdDidCommit(HeapTupleHeaderGetXmin(tuple)))
+			{
+				/* Set the hint bit on the tuple, and put it in the cache
+				 * if it was actually set.
+				 */
+				if(SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
+							HeapTupleHeaderGetXmin(tuple)))
+					SetXidInHintBitCache(HeapTupleHeaderGetXmin(tuple),
+								HBCACHE_COMITTED);
 
-			if (HeapTupleHeaderGetCmax(tuple) >= snapshot->curcid)
-				return true;	/* deleted after scan started */
+			}
 			else
-				return false;	/* deleted before scan started */
-		}
-		else if (TransactionIdIsInProgress(HeapTupleHeaderGetXmin(tuple)))
-			return false;
-		else if (TransactionIdDidCommit(HeapTupleHeaderGetXmin(tuple)))
-			SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
-						HeapTupleHeaderGetXmin(tuple));
-		else
-		{
-			/* it must have aborted or crashed */
-			SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
-						InvalidTransactionId);
-			return false;
+			{
+				/* it must have aborted or crashed */
+				if(SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
+							InvalidTransactionId))
+					SetXidInHintBitCache(HeapTupleHeaderGetXmin(tuple),
+								HBCACHE_INVALID);
+				return false;
+			}
 		}
 	}
 
 	/*
 	 * By here, the inserting transaction has committed - have to check
 	 * when...