From fc869af55678eda29045190f735da98c4b6808d9 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas.vondra@postgresql.org>
Date: Thu, 15 Jun 2023 14:49:56 +0200
Subject: [PATCH 2/2] ignore seq patterns, add stats

---
 src/backend/access/index/indexam.c | 80 ++++++++++++++++++++++++++++++
 src/include/access/genam.h         | 16 ++++++
 2 files changed, 96 insertions(+)

diff --git a/src/backend/access/index/indexam.c b/src/backend/access/index/indexam.c
index 557267aced9..6ab977ca284 100644
--- a/src/backend/access/index/indexam.c
+++ b/src/backend/access/index/indexam.c
@@ -378,6 +378,16 @@ index_endscan(IndexScanDesc scan)
 	if (scan->xs_temp_snap)
 		UnregisterSnapshot(scan->xs_snapshot);
 
+	/* If prefetching enabled, log prefetch stats. */
+	if (scan->xs_prefetch)
+	{
+		IndexPrefetch prefetch = scan->xs_prefetch;
+
+		elog(LOG, "index prefetch stats: requests %lu prefetches %lu (%f)",
+			 prefetch->prefetchAll, prefetch->prefetchCount,
+			 prefetch->prefetchCount * 100.0 / prefetch->prefetchAll);
+	}
+
 	/* Release the scan data structure itself */
 	IndexScanEnd(scan);
 }
@@ -1028,6 +1038,57 @@ index_opclass_options(Relation indrel, AttrNumber attnum, Datum attoptions,
 	return build_local_reloptions(&relopts, attoptions, validate);
 }
 
+/*
+ * Add the block to the tiny top-level queue (LRU), and check if the block
+ * is in a sequential pattern.
+ */
+static bool
+index_prefetch_is_sequential(IndexPrefetch prefetch, BlockNumber block)
+{
+	bool	is_sequential = true;
+	int		idx;
+
+	/* no requests */
+	if (prefetch->queueIndex == 0)
+	{
+		idx = (prefetch->queueIndex++) % PREFETCH_QUEUE_SIZE;
+		prefetch->queueItems[idx] = block;
+		return false;
+	}
+
+	/* same as immediately preceding block? */
+	idx = (prefetch->queueIndex - 1) % PREFETCH_QUEUE_SIZE;
+	if (prefetch->queueItems[idx] == block)
+		return true;
+
+	idx = (prefetch->queueIndex++) % PREFETCH_QUEUE_SIZE;
+	prefetch->queueItems[idx] = block;
+
+	for (int i = 1; i < PREFETCH_SEQ_PATTERN_BLOCKS; i++)
+	{
+		/* not enough requests */
+		if (prefetch->queueIndex < i)
+		{
+			is_sequential = false;
+			break;
+		}
+
+		/*
+		 * -1, because we've already advanced the index, so it points to
+		 * the next slot at this point
+		 */
+		idx = (prefetch->queueIndex - i - 1) % PREFETCH_QUEUE_SIZE;
+
+		if ((block - i) != prefetch->queueItems[idx])
+		{
+			is_sequential = false;
+			break;
+		}
+	}
+
+	return is_sequential;
+}
+
 /*
  * index_prefetch_add_cache
  *		Add a block to the cache, return true if it was recently prefetched.
@@ -1081,6 +1142,19 @@ index_prefetch_add_cache(IndexPrefetch prefetch, BlockNumber block)
 	uint64		oldestRequest = PG_UINT64_MAX;
 	int			oldestIndex = -1;
 
+	/*
+	 * First add the block to the (tiny) top-level LRU cache and see if it's
+	 * part of a sequential pattern. In this case we just ignore the block
+	 * and don't prefetch it - we expect read-ahead to do a better job.
+	 *
+	 * XXX Maybe we should still add the block to the later cache, in case
+	 * we happen to access it later? That might help if we first scan a lot
+	 * of the table sequentially, and then randomly. Not sure that's very
+	 * likely with index access, though.
+	 */
+	if (index_prefetch_is_sequential(prefetch, block))
+		return true;
+
 	/* see if we already have prefetched this block (linear search of LRU) */
 	for (int i = 0; i < PREFETCH_LRU_SIZE; i++)
 	{
@@ -1206,6 +1280,8 @@ index_prefetch(IndexScanDesc scan, ScanDirection dir)
 	if (prefetch->prefetchTarget <= 0)
 		return;
 
+	prefetch->prefetchAll++;
+
 	/*
 	 * XXX I think we don't need to worry about direction here, that's handled
 	 * by how the AMs build the curPos etc. (see nbtsearch.c)
@@ -1256,6 +1332,8 @@ index_prefetch(IndexScanDesc scan, ScanDirection dir)
 			if (index_prefetch_add_cache(prefetch, block))
 				continue;
 
+			prefetch->prefetchCount++;
+
 			PrefetchBuffer(scan->heapRelation, MAIN_FORKNUM, block);
 			pgBufferUsage.blks_prefetches++;
 		}
@@ -1300,6 +1378,8 @@ index_prefetch(IndexScanDesc scan, ScanDirection dir)
 			if (index_prefetch_add_cache(prefetch, block))
 				continue;
 
+			prefetch->prefetchCount++;
+
 			PrefetchBuffer(scan->heapRelation, MAIN_FORKNUM, block);
 			pgBufferUsage.blks_prefetches++;
 		}
diff --git a/src/include/access/genam.h b/src/include/access/genam.h
index c01c37951ca..526f280a44d 100644
--- a/src/include/access/genam.h
+++ b/src/include/access/genam.h
@@ -276,6 +276,12 @@ typedef struct PrefetchCacheEntry {
 #define		PREFETCH_LRU_COUNT		128
 #define		PREFETCH_CACHE_SIZE		(PREFETCH_LRU_SIZE * PREFETCH_LRU_COUNT)
 
+/*
+ * Used to detect sequential patterns (and disable prefetching).
+ */
+#define		PREFETCH_QUEUE_SIZE				8
+#define		PREFETCH_SEQ_PATTERN_BLOCKS		4
+
 typedef struct IndexPrefetchData
 {
 	/*
@@ -291,6 +297,16 @@ typedef struct IndexPrefetchData
 	prefetcher_getblock_function	get_block;
 	prefetcher_getrange_function	get_range;
 
+	uint64		prefetchAll;
+	uint64		prefetchCount;
+
+	/*
+	 * Tiny queue of most recently prefetched blocks, used first for cheap
+	 * checks and also to identify (and ignore) sequential prefetches.
+	 */
+	uint64		queueIndex;
+	BlockNumber	queueItems[PREFETCH_QUEUE_SIZE];
+
 	/*
 	 * Cache of recently prefetched blocks, organized as a hash table of
 	 * small LRU caches.
-- 
2.40.1