Re: [PATCH v1] Batch B-tree TIDs when building a bitmap

[David Geier]

Hi Tomas,

> I would like review of this B-tree bitmap-scan patch. Perfloop's agent
> found and implemented it; the patch and submission packet used AI
> assistance. I am the contact.
> 
> btgetbitmap calls tbm_add_tuples once per matching TID. The patch batches
> saved leaf-page spans to reuse that API's within-call heap-block cache [1].

Good find but the code is AI slop at its best. The same goes for the
repro steps. A simple .sql file would have been much easier to work with
for others.

I found the finding relevant enough to re-implement the patch myself
properly. While being at it, I've simplified the control flow
significantly. See attached patched.
The same optimization can be applied, by the way, to at least the GIST,
the GIN and the HASH index implementations. I'll do that the next days
when I find some time.

I tested the patch with a simple query that puts pressure on the Bitmap
Index Scan (BIS) by scanning through a lot of index pages and finding a
lot of matches.

CREATE TABLE table3 (col0 bigint, col1 bigint, filler char(80));
INSERT INTO table3 SELECT g, g FROM generate_series(0, 9999999) AS g;
CREATE INDEX idx_table3_col0 ON table3(col0);
VACUUM ANALYZE table3;
SET max_parallel_workers_per_gather = 0;
SET enable_seqscan = false;
SET enable_indexscan = false;
SELECT sum(col1) from table3 where col0 < 10000000;

The result is quite impressive. For that query we save ~1/3rd of the
execution time of the BIS (164 ms -> 110 ms).

master

->  Bitmap Index Scan on idx_table3_col0 (actual time=164.878..164.878
rows=10000000.00 loops=1)
         Index Cond: (col0 < 10000000)
         Index Searches: 1
         Buffers: shared hit=1 read=27324

patched

->  Bitmap Index Scan on idx_table3_col0 (actual time=110.669..110.670
rows=10000000.00 loops=1)
         Index Cond: (col0 < 10000000)
         Index Searches: 1
         Buffers: shared hit=1 read=27324

The patch shouldn't regress anything. If we only find a single match in
a block, the only thing we do extra is allocating some stack memory and
copying the TID. Both operations are basically free compared to all the
rest that is happening.

--
David Geier
From 6904be530a804d830d10be86e31768e6d51aa15d Mon Sep 17 00:00:00 2001
From: David Geier <geidav...@gmail.com>
Date: Wed, 7 Oct 2026 16:26:52 +0200
Subject: [PATCH v1] btgetbitmap() inserts TIDs in batches

Changed btgetbitmap() to collect all TIDs from a B-tree page into
an array and add them to the TIDBitmap in a single tbm_add_tuples()
call, rather than adding each TID individually. This reduces the
number of hash map lookups needed to process one page.

Also simplified the control flow by using a for loop with
_bt_first() / _bt_next() instead of nested do-while loops.
---
 src/backend/access/nbtree/nbtree.c | 37 ++++++++----------------------
 1 file changed, 9 insertions(+), 28 deletions(-)

diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.c
index 0abdd7b49f5..90192b789cc 100644
--- a/src/backend/access/nbtree/nbtree.c
+++ b/src/backend/access/nbtree/nbtree.c
@@ -291,45 +291,26 @@ int64
 btgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
 {
 	BTScanOpaque so = (BTScanOpaque) scan->opaque;
-	int64		ntids = 0;
-	ItemPointer heapTid;
+	int64		 ntids_total = 0;
 
 	Assert(scan->heapRelation == NULL);
 
-	/* Each loop iteration performs another primitive index scan */
 	do
 	{
-		/* Fetch the first page & tuple */
-		if (_bt_first(scan, ForwardScanDirection))
+		for (bool more = _bt_first(scan, ForwardScanDirection); more; more =_bt_next(scan, ForwardScanDirection))
 		{
-			/* Save tuple ID, and continue scanning */
-			heapTid = &scan->xs_heaptid;
-			tbm_add_tuples(tbm, heapTid, 1, false);
-			ntids++;
+			ItemPointerData tids[MaxTIDsPerBTreePage];
+			int				ntids_page = 0;
 
-			for (;;)
-			{
-				/*
-				 * Advance to next tuple within page.  This is the same as the
-				 * easy case in _bt_next().
-				 */
-				if (++so->currPos.itemIndex > so->currPos.lastItem)
-				{
-					/* let _bt_next do the heavy lifting */
-					if (!_bt_next(scan, ForwardScanDirection))
-						break;
-				}
+			while (so->currPos.itemIndex <= so->currPos.lastItem)
+				tids[ntids_page++] = so->currPos.items[so->currPos.itemIndex++].heapTid;
 
-				/* Save tuple ID, and continue scanning */
-				heapTid = &so->currPos.items[so->currPos.itemIndex].heapTid;
-				tbm_add_tuples(tbm, heapTid, 1, false);
-				ntids++;
-			}
+			tbm_add_tuples(tbm, tids, ntids_page, false);
+			ntids_total += ntids_page;
 		}
-		/* Now see if we need another primitive index scan */
 	} while (so->numArrayKeys && _bt_start_prim_scan(scan));
 
-	return ntids;
+	return ntids_total;
 }
 
 /*
-- 
2.53.0