v11-0005-Limit-get_actual_variable_range-to-scan-one-inde.patch

From 884286d5970dd501bdfae051058a7f0c291125d8 Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <pg@bowt.ie>
Date: Mon, 2 Feb 2026 23:34:36 -0500
Subject: [PATCH v11 05/12] Limit get_actual_variable_range to scan one index
 leaf page.

Replace VISITED_PAGES_LIMIT with a mechanism that limits
get_actual_variable_range to scanning only the extremal index leaf page,
rather than counting heap page visits.

get_actual_variable_range scans an index to find actual min/max values
for planner selectivity estimation.  Since this happens during planning,
we can't afford to spend too much time on it.  Commit 9c6ad5eaa9 added
VISITED_PAGES_LIMIT (a limit of 100 heap page visits) to bound the
amount of work performed, giving up and falling back to the pg_statistic
extremal value when the limit is exceeded.  But that isn't effective in
cases with more extreme concentrations of dead index tuples.

Recent benchmark results from Mark Callaghan show that
VISITED_PAGES_LIMIT isn't effective once the dead index tuple problem
gets out of hand (which is expected with queue-like tables that
continually delete older records and insert newer ones).  The root cause
is that VISITED_PAGES_LIMIT counts heap page visits, but when many index
tuples are marked LP_DEAD, _bt_readpage traverses arbitrarily many index
pages without returning any tuples -- the heap page counter in
selfuncs.c never gets a chance to increment, so VISITED_PAGES_LIMIT
never triggers.  Furthermore, the design of setting LP_DEAD bits to help
future calls is ultimately counterproductive: each LP_DEAD tuple is one
fewer that counts against VISITED_PAGES_LIMIT, so the more LP_DEAD bits
we set, the less effective the limit becomes at bailing out early.

Fix this by adding a new xs_read_extremal_only flag to IndexScanDesc.
When set, the scan stops after the first leaf page: _bt_readfirstpage
and _bt_readnextpage in nbtree treat it like end-of-scan, and
heapam_batch_getnext returns NULL after the first batch.  selfuncs.c
sets this flag before starting the scan.

This provides a hard guarantee on the maximum work per call.  Unlike
VISITED_PAGES_LIMIT, this limit cannot be eroded by LP_DEAD bits.

This approach is also compatible with index prefetching commit's new
table_index_getnext_slot() interface, which hides heap access details
from callers like selfuncs.c, making VISITED_PAGES_LIMIT impractical to
implement without pushing ad-hoc logic into the table AM layer.

Note: This is still a WIP.  There are perhaps still some cases that
we're not exactly handling perfectly, where (for example) the first
batch that the scan returns happens to not contain any matches due to
_bt_first landing right on the edge of values between two adjoining
pages (note that we use an IS NOT NULL scan key from selfuncs.c).  But
this seems to be roughly the right idea.
---
 src/include/access/relscan.h             |  7 +++++++
 src/backend/access/heap/heapam.c         |  3 ---
 src/backend/access/heap/heapam_handler.c | 11 +++++++++++
 src/backend/access/index/genam.c         |  1 +
 src/backend/access/nbtree/nbtsearch.c    | 10 +++++++---
 src/backend/utils/adt/selfuncs.c         | 16 ++++++++--------
 6 files changed, 34 insertions(+), 14 deletions(-)

diff --git a/src/include/access/relscan.h b/src/include/access/relscan.h
index c3b0464f3..f5050ed7f 100644
--- a/src/include/access/relscan.h
+++ b/src/include/access/relscan.h
@@ -370,6 +370,13 @@ typedef struct IndexScanDescData
 
 	/* parallel index scan information, in shared memory */
 	struct ParallelIndexScanDescData *parallel_scan;
+
+	/*
+	 * Flag to request early abort during get_actual_variable_range scans.
+	 * Such scans must end on the rightmost (or leftmost) index page, no
+	 * matter whether there are more matches in previous (or later) pages.
+	 */
+	bool		xs_read_extremal_only;
 } IndexScanDescData;
 
 /* Generic structure for parallel scans */
diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index 98d53caee..0bb23a72d 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -1883,9 +1883,6 @@ heap_hot_search_buffer(ItemPointer tid, Relation relation, Buffer buffer,
 		 * If we can't see it, maybe no one else can either.  At caller
 		 * request, check whether all chain members are dead to all
 		 * transactions.
-		 *
-		 * Note: if you change the criterion here for what is "dead", fix the
-		 * planner's get_actual_variable_range() function to match.
 		 */
 		if (all_dead && *all_dead)
 		{
diff --git a/src/backend/access/heap/heapam_handler.c b/src/backend/access/heap/heapam_handler.c
index d164b9920..da8d14939 100644
--- a/src/backend/access/heap/heapam_handler.c
+++ b/src/backend/access/heap/heapam_handler.c
@@ -442,6 +442,17 @@ heapam_batch_getnext(IndexScanDesc scan, ScanDirection direction,
 			ReleaseBuffer(batch->buf);
 			batch->buf = InvalidBuffer;
 		}
+
+		/*
+		 * xs_read_extremal_only scans are used by get_actual_variable_range
+		 * to find min/max values.  They only need the extremal (first or
+		 * last) index page, so once we have one batch, we give up completely.
+		 */
+		if (unlikely(scan->xs_read_extremal_only) && priorBatch)
+		{
+			Assert(scan->xs_want_itup);
+			return NULL;
+		}
 	}
 	else
 	{
diff --git a/src/backend/access/index/genam.c b/src/backend/access/index/genam.c
index 18dccd3c9..e8644c608 100644
--- a/src/backend/access/index/genam.c
+++ b/src/backend/access/index/genam.c
@@ -125,6 +125,7 @@ RelationGetIndexScan(Relation indexRelation, int nkeys, int norderbys)
 	scan->xs_itupdesc = NULL;
 	scan->xs_hitup = NULL;
 	scan->xs_hitupdesc = NULL;
+	scan->xs_read_extremal_only = false;
 
 	return scan;
 }
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index 441724c01..46db363f6 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -1667,14 +1667,18 @@ _bt_readfirstpage(IndexScanDesc scan, IndexScanBatch firstbatch,
 
 	Assert(firstbatch->dir == dir);
 
-	if (blkno == P_NONE ||
+	if (blkno == P_NONE || scan->xs_read_extremal_only ||
 		(ScanDirectionIsForward(dir) ?
 		 !firstbatch->moreRight : !firstbatch->moreLeft))
 	{
 		/*
 		 * firstbatch _bt_readpage call ended scan in this direction (though
-		 * if so->needPrimScan was set the scan will continue in _bt_first)
+		 * if so->needPrimScan was set the scan will continue in _bt_first).
+		 *
+		 * Also cut our losses during xs_read_extremal_only scans, which are
+		 * limited to scanning only the extremal leaf page in the index.
 		 */
+		Assert(!scan->xs_read_extremal_only || !so->needPrimScan);
 		indexam_util_batch_release(scan, firstbatch);
 		_bt_parallel_done(scan);
 		return NULL;
@@ -1792,7 +1796,7 @@ _bt_readnextpage(IndexScanDesc scan, BlockNumber blkno,
 		newbatch->buf = InvalidBuffer;
 
 		/* Continue the scan in this direction? */
-		if (blkno == P_NONE ||
+		if (blkno == P_NONE || scan->xs_read_extremal_only ||
 			(ScanDirectionIsForward(dir) ?
 			 !newbatch->moreRight : !newbatch->moreLeft))
 		{
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 616acfc95..6ba44fa46 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -7167,14 +7167,10 @@ get_actual_variable_endpoint(Relation heapRel,
 	 *
 	 * Despite all this care, there are situations where we might find many
 	 * non-visible tuples near the end of the index.  We don't want to expend
-	 * a huge amount of time here, so we give up once we've read too many heap
-	 * pages.  When we fail for that reason, the caller will end up using
-	 * whatever extremal value is recorded in pg_statistic.
-	 *
-	 * XXX This can't work with the new table_index_getnext_slot interface,
-	 * which simply won't return a tuple that isn't visible to our snapshot.
-	 * table_index_getnext_slot will need some kind of callback that provides
-	 * a way for the scan to give up when the costs start to get out of hand.
+	 * a huge amount of time here, so we give up the extremal index leaf page
+	 * has no matching items (generally only seen when the page has many index
+	 * tuples with set LP_DEAD bits).  When we give up the caller will end up
+	 * using whatever extremal value is recorded in pg_statistic.
 	 */
 	InitNonVacuumableSnapshot(SnapshotNonVacuumable,
 							  GlobalVisTestFor(heapRel));
@@ -7183,6 +7179,10 @@ get_actual_variable_endpoint(Relation heapRel,
 								 &SnapshotNonVacuumable, NULL,
 								 1, 0);
 	Assert(index_scan->xs_want_itup);
+
+	/* Set up our index-only scan to read at most one index leaf page */
+	index_scan->xs_read_extremal_only = true;
+
 	index_rescan(index_scan, scankeys, 1, NULL, 0);
 
 	/* Fetch first/next tuple in specified direction */
-- 
2.51.0