v12-0002-Don-t-allocate-_bt_search-stack.patch

From 3fdba29cd024a4813e4cdf4611305cf46b333aa2 Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <pg@bowt.ie>
Date: Thu, 12 Feb 2026 14:06:47 -0500
Subject: [PATCH v12 02/23] Don't allocate _bt_search stack

---
 src/include/access/nbtree.h           |  3 +--
 src/backend/access/nbtree/nbtinsert.c | 19 +++++++++++++-
 src/backend/access/nbtree/nbtpage.c   |  2 +-
 src/backend/access/nbtree/nbtsearch.c | 36 ++++++++++++++-------------
 src/backend/access/nbtree/nbtutils.c  | 16 ------------
 contrib/amcheck/verify_nbtree.c       |  4 +--
 6 files changed, 40 insertions(+), 40 deletions(-)

diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index 772248596..da7503c57 100644
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.h
@@ -1284,7 +1284,7 @@ extern int	_bt_binsrch_array_skey(FmgrInfo *orderproc,
  * prototypes for functions in nbtsearch.c
  */
 extern BTStack _bt_search(Relation rel, Relation heaprel, BTScanInsert key,
-						  Buffer *bufP, int access);
+						  Buffer *bufP, int access, bool returnstack);
 extern OffsetNumber _bt_binsrch_insert(Relation rel, BTInsertState insertstate);
 extern int32 _bt_compare(Relation rel, BTScanInsert key, Page page, OffsetNumber offnum);
 extern bool _bt_first(IndexScanDesc scan, ScanDirection dir);
@@ -1295,7 +1295,6 @@ extern Buffer _bt_get_endpoint(Relation rel, uint32 level, bool rightmost);
  * prototypes for functions in nbtutils.c
  */
 extern BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup);
-extern void _bt_freestack(BTStack stack);
 extern void _bt_killitems(IndexScanDesc scan);
 extern BTCycleId _bt_vacuum_cycleid(Relation rel);
 extern BTCycleId _bt_start_vacuum(Relation rel);
diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c
index d17aaa5aa..65dfb8dd4 100644
--- a/src/backend/access/nbtree/nbtinsert.c
+++ b/src/backend/access/nbtree/nbtinsert.c
@@ -61,6 +61,7 @@ static Buffer _bt_split(Relation rel, Relation heaprel, BTScanInsert itup_key,
 						IndexTuple nposting, uint16 postingoff);
 static void _bt_insert_parent(Relation rel, Relation heaprel, Buffer buf,
 							  Buffer rbuf, BTStack stack, bool isroot, bool isonly);
+static void _bt_freestack(BTStack stack);
 static Buffer _bt_newlevel(Relation rel, Relation heaprel, Buffer lbuf, Buffer rbuf);
 static inline bool _bt_pgaddtup(Page page, Size itemsize, const IndexTupleData *itup,
 								OffsetNumber itup_off, bool newfirstdataitem);
@@ -380,7 +381,7 @@ _bt_search_insert(Relation rel, Relation heaprel, BTInsertState insertstate)
 
 	/* Cannot use optimization -- descend tree, return proper descent stack */
 	return _bt_search(rel, heaprel, insertstate->itup_key, &insertstate->buf,
-					  BT_WRITE);
+					  BT_WRITE, true);
 }
 
 /*
@@ -2438,6 +2439,22 @@ _bt_getstackbuf(Relation rel, Relation heaprel, BTStack stack, BlockNumber child
 	}
 }
 
+/*
+ * _bt_freestack() -- free a retracement stack made by _bt_search_insert.
+ */
+static void
+_bt_freestack(BTStack stack)
+{
+	BTStack		ostack;
+
+	while (stack != NULL)
+	{
+		ostack = stack;
+		stack = stack->bts_parent;
+		pfree(ostack);
+	}
+}
+
 /*
  *	_bt_newlevel() -- Create a new level above root page.
  *
diff --git a/src/backend/access/nbtree/nbtpage.c b/src/backend/access/nbtree/nbtpage.c
index 4125c185e..9aa78068a 100644
--- a/src/backend/access/nbtree/nbtpage.c
+++ b/src/backend/access/nbtree/nbtpage.c
@@ -1966,7 +1966,7 @@ _bt_pagedel(Relation rel, Buffer leafbuf, BTVacState *vstate)
 				/* Set up a BTLessStrategyNumber-like insertion scan key */
 				itup_key->nextkey = false;
 				itup_key->backward = true;
-				stack = _bt_search(rel, NULL, itup_key, &sleafbuf, BT_READ);
+				stack = _bt_search(rel, NULL, itup_key, &sleafbuf, BT_READ, true);
 				/* won't need a second lock or pin on leafbuf */
 				_bt_relbuf(rel, sleafbuf);
 
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index 32ae0bda8..bfaaf1f01 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -80,10 +80,13 @@ _bt_drop_lock_and_maybe_pin(Relation rel, BTScanOpaque so)
  * The passed scankey is an insertion-type scankey (see nbtree/README),
  * but it can omit the rightmost column(s) of the index.
  *
- * Return value is a stack of parent-page pointers (i.e. there is no entry for
- * the leaf level/page).  *bufP is set to the address of the leaf-page buffer,
- * which is locked and pinned.  No locks are held on the parent pages,
- * however!
+ * If returnstack is true, return value is a stack of parent-page pointers
+ * (i.e. there is no entry for the leaf level/page).  If returnstack is false,
+ * we just return NULL.  This scheme allows callers that don't need a descent
+ * stack to avoid palloc churn.
+ *
+ * When we return *bufP is set to the address of the leaf-page buffer, which
+ * is locked and pinned.  No locks are held on the parent pages, however!
  *
  * The returned buffer is locked according to access parameter.  Additionally,
  * access = BT_WRITE will allow an empty root page to be created and returned.
@@ -96,7 +99,7 @@ _bt_drop_lock_and_maybe_pin(Relation rel, BTScanOpaque so)
  */
 BTStack
 _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP,
-		   int access)
+		   int access, bool returnstack)
 {
 	BTStack		stack_in = NULL;
 	int			page_access = BT_READ;
@@ -160,10 +163,13 @@ _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP,
 		 * page one level down, it usually ends up inserting a new pivot
 		 * tuple/downlink immediately after the location recorded here.
 		 */
-		new_stack = (BTStack) palloc_object(BTStackData);
-		new_stack->bts_blkno = BufferGetBlockNumber(*bufP);
-		new_stack->bts_offset = offnum;
-		new_stack->bts_parent = stack_in;
+		if (returnstack)
+		{
+			new_stack = (BTStack) palloc_object(BTStackData);
+			new_stack->bts_blkno = BufferGetBlockNumber(*bufP);
+			new_stack->bts_offset = offnum;
+			new_stack->bts_parent = stack_in;
+		}
 
 		/*
 		 * Page level 1 is lowest non-leaf page level prior to leaves.  So, if
@@ -177,7 +183,8 @@ _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP,
 		*bufP = _bt_relandgetbuf(rel, *bufP, child, page_access);
 
 		/* okay, all set to move down a level */
-		stack_in = new_stack;
+		if (returnstack)
+			stack_in = new_stack;
 	}
 
 	/*
@@ -879,7 +886,6 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
 {
 	Relation	rel = scan->indexRelation;
 	BTScanOpaque so = (BTScanOpaque) scan->opaque;
-	BTStack		stack;
 	OffsetNumber offnum;
 	BTScanInsertData inskey;
 	ScanKey		startKeys[INDEX_MAX_KEYS];
@@ -1506,10 +1512,7 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
 	 * position ourselves on the target leaf page.
 	 */
 	Assert(ScanDirectionIsBackward(dir) == inskey.backward);
-	stack = _bt_search(rel, NULL, &inskey, &so->currPos.buf, BT_READ);
-
-	/* don't need to keep the stack around... */
-	_bt_freestack(stack);
+	_bt_search(rel, NULL, &inskey, &so->currPos.buf, BT_READ, false);
 
 	if (!BufferIsValid(so->currPos.buf))
 	{
@@ -1527,8 +1530,7 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
 		if (IsolationIsSerializable())
 		{
 			PredicateLockRelation(rel, scan->xs_snapshot);
-			stack = _bt_search(rel, NULL, &inskey, &so->currPos.buf, BT_READ);
-			_bt_freestack(stack);
+			_bt_search(rel, NULL, &inskey, &so->currPos.buf, BT_READ, false);
 		}
 
 		if (!BufferIsValid(so->currPos.buf))
diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index 5c50f0dd1..1b9f2aa10 100644
--- a/src/backend/access/nbtree/nbtutils.c
+++ b/src/backend/access/nbtree/nbtutils.c
@@ -144,22 +144,6 @@ _bt_mkscankey(Relation rel, IndexTuple itup)
 	return key;
 }
 
-/*
- * free a retracement stack made by _bt_search.
- */
-void
-_bt_freestack(BTStack stack)
-{
-	BTStack		ostack;
-
-	while (stack != NULL)
-	{
-		ostack = stack;
-		stack = stack->bts_parent;
-		pfree(ostack);
-	}
-}
-
 /*
  * qsort comparison function for int arrays
  */
diff --git a/contrib/amcheck/verify_nbtree.c b/contrib/amcheck/verify_nbtree.c
index e04b7ca69..b74ab5f7a 100644
--- a/contrib/amcheck/verify_nbtree.c
+++ b/contrib/amcheck/verify_nbtree.c
@@ -3009,7 +3009,6 @@ static bool
 bt_rootdescend(BtreeCheckState *state, IndexTuple itup)
 {
 	BTScanInsert key;
-	BTStack		stack;
 	Buffer		lbuf;
 	bool		exists;
 
@@ -3026,7 +3025,7 @@ bt_rootdescend(BtreeCheckState *state, IndexTuple itup)
 	 */
 	Assert(state->readonly && state->rootdescend);
 	exists = false;
-	stack = _bt_search(state->rel, NULL, key, &lbuf, BT_READ);
+	_bt_search(state->rel, NULL, key, &lbuf, BT_READ, false);
 
 	if (BufferIsValid(lbuf))
 	{
@@ -3053,7 +3052,6 @@ bt_rootdescend(BtreeCheckState *state, IndexTuple itup)
 		_bt_relbuf(state->rel, lbuf);
 	}
 
-	_bt_freestack(stack);
 	pfree(key);
 
 	return exists;
-- 
2.53.0