> The hash path still appears to use the old pattern, though:
>
> while (so->currPos.itemIndex <= so->currPos.lastItem)
> tids[ntids_page++] =
> so->currPos.items[so->currPos.itemIndex++].heapTid;
>
> I meant applying the same idea there as in B-tree: iterate with a local
> index and update itemIndex once after copying the page.
Changed.
> On the small B-tree regression, I agree that the absolute difference
> is tiny. I measured it with a release build using 24 paired runs of
> the baseline and patched servers. The medians were:
>
> baseline 33.195 us
> patched 33.569 us
>
> The median paired increase was 0.283 us, and the patched version was
> slower in 19 of 24 pairs. The paired 95% interval for the relative
> difference was +0.55% to +1.28%.
>
> So it was repeatable on that machine, rather than a single timing
> sample, but I agree that attributing such a small difference
> specifically to the TID copy would be too strong. Since you don't
> reproduce it independently, I don't think it is actionable or a reason
> to change the patch.
Agreed.
> Thanks also for adding the other AMs to the benchmark. Those results
> address my concern about extending the optimization beyond B-tree. In
> particular, the GIN, GiST, hash, and SP-GiST results show useful
> Bitmap Index Scan savings even though their result streams have
> different locality characteristics.
It was useful not only as confirmation but it also made me find the
bloom residual-batch issue. So time well spent.
> And yes, I wasn't suggesting dynamic allocation for the GiST/SP-GiST
> buffers. Looking at their sizes again, I agree that fixed buffers are
> preferable to adding allocation/lifetime overhead.
OK.
> With the corresponding local-index cleanup in hash, the patch looks
> good to me.
Attached is v4.
The only change is using a local counter in hashgetbitmap(), instead of
updating so->currPos.itemIndex every loop iteration to save on
load/store instructions. Now the code is consistent with the btgetbitmap().
I also rebased on master.
--
David Geier
From cb065e674f3435275651e289588f3c034426b22b Mon Sep 17 00:00:00 2001
From: David Geier <[email protected]>
Date: Wed, 7 Oct 2026 16:26:52 +0200
Subject: [PATCH v4] Batch TIDBitmap insertions in index scans
Change the B-tree, hash, GiST, GIN, SP-GiST, and bloom index access
methods to collect matching TIDs into arrays and pass them to
tbm_add_tuples() in batches, rather than adding each TID individually.
tbm_add_tuples() reuses the TIDBitmap page entry while processing
consecutive TIDs from the same heap page. Larger batches therefore
reduce repeated hash table lookups and function call overhead.
Access methods that can return different recheck values use separate
batches for exact TIDs and TIDs requiring rechecks. Access methods
whose result streams are not bounded by an index page use fixed-size
batches that are flushed when full.
Also simplify the control flow in btgetbitmap() by using a for loop
with _bt_first() and _bt_next().
---
contrib/bloom/blscan.c | 14 +++++++++-
src/backend/access/gin/ginget.c | 39 +++++++++++++++++++++++++---
src/backend/access/gist/gistget.c | 23 +++++++++++++++--
src/backend/access/hash/hash.c | 26 ++++++++++++-------
src/backend/access/nbtree/nbtree.c | 40 +++++++++--------------------
src/backend/access/spgist/spgscan.c | 16 +++++++++++-
src/include/access/spgist_private.h | 5 ++++
7 files changed, 119 insertions(+), 44 deletions(-)
diff --git a/contrib/bloom/blscan.c b/contrib/bloom/blscan.c
index 1a0e42021ec..d22584ae173 100644
--- a/contrib/bloom/blscan.c
+++ b/contrib/bloom/blscan.c
@@ -20,6 +20,8 @@
#include "storage/bufmgr.h"
#include "storage/read_stream.h"
+#define BLOOM_TBM_BATCH_SIZE 256
+
/*
* Begin scan of bloom index.
*/
@@ -80,10 +82,12 @@ blgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
BlockNumber blkno,
npages;
int i;
+ int ntids_batch = 0;
BufferAccessStrategy bas;
BloomScanOpaque so = (BloomScanOpaque) scan->opaque;
BlockRangeReadStreamPrivate p;
ReadStream *stream;
+ ItemPointerData tids[BLOOM_TBM_BATCH_SIZE];
if (so->sign == NULL)
{
@@ -172,7 +176,13 @@ blgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
/* Add matching tuples to bitmap */
if (res)
{
- tbm_add_tuples(tbm, &itup->heapPtr, 1,
true);
+ if (ntids_batch == BLOOM_TBM_BATCH_SIZE)
+ {
+ tbm_add_tuples(tbm, tids,
ntids_batch, true);
+ ntids_batch = 0;
+ }
+
+ tids[ntids_batch++] = itup->heapPtr;
ntids++;
}
}
@@ -182,6 +192,8 @@ blgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
CHECK_FOR_INTERRUPTS();
}
+ tbm_add_tuples(tbm, tids, ntids_batch, true);
+
Assert(read_stream_next_buffer(stream, NULL) == InvalidBuffer);
read_stream_end(stream);
FreeAccessStrategy(bas);
diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c
index 2bcb32ca3d0..2c32a9e82e1 100644
--- a/src/backend/access/gin/ginget.c
+++ b/src/backend/access/gin/ginget.c
@@ -26,6 +26,8 @@
/* GUC parameter */
int GinFuzzySearchLimit = 0;
+#define GIN_TBM_BATCH_SIZE 256
+
typedef struct pendingPosition
{
Buffer pendingBuffer;
@@ -1842,6 +1844,8 @@ scanPendingInsert(IndexScanDesc scan, TIDBitmap *tbm,
int64 *ntids)
Buffer metabuffer = ReadBuffer(scan->indexRelation,
GIN_METAPAGE_BLKNO);
Page page;
BlockNumber blkno;
+ ItemPointerData tids[2][GIN_TBM_BATCH_SIZE];
+ int ntids_batch[2] = {0, 0};
*ntids = 0;
@@ -1913,11 +1917,22 @@ scanPendingInsert(IndexScanDesc scan, TIDBitmap *tbm,
int64 *ntids)
if (match)
{
- tbm_add_tuples(tbm, &pos.item, 1, recheck);
+ const int b = recheck ? 1 : 0;
+
+ if (ntids_batch[b] == GIN_TBM_BATCH_SIZE)
+ {
+ tbm_add_tuples(tbm, tids[b], ntids_batch[b],
recheck);
+ ntids_batch[b] = 0;
+ }
+
+ tids[b][ntids_batch[b]++] = pos.item;
(*ntids)++;
}
}
+ for (int i = 0; i < 2; i++)
+ tbm_add_tuples(tbm, tids[i], ntids_batch[i], i == 1);
+
pfree(pos.hasMatchKey);
}
@@ -1931,6 +1946,8 @@ gingetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
int64 ntids;
ItemPointerData iptr;
bool recheck;
+ ItemPointerData tids[2][GIN_TBM_BATCH_SIZE];
+ int ntids_batch[2] = {0, 0};
/*
* Set up the scan keys, and check for unsatisfiable query.
@@ -1969,11 +1986,27 @@ gingetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
break;
if (ItemPointerIsLossyPage(&iptr))
+ {
tbm_add_page(tbm, ItemPointerGetBlockNumber(&iptr));
+ ntids++;
+ }
else
- tbm_add_tuples(tbm, &iptr, 1, recheck);
- ntids++;
+ {
+ const int b = recheck ? 1 : 0;
+
+ if (ntids_batch[b] == GIN_TBM_BATCH_SIZE)
+ {
+ tbm_add_tuples(tbm, tids[b], ntids_batch[b],
recheck);
+ ntids_batch[b] = 0;
+ }
+
+ tids[b][ntids_batch[b]++] = iptr;
+ ntids++;
+ }
}
+ for (int i = 0; i < 2; i++)
+ tbm_add_tuples(tbm, tids[i], ntids_batch[i], i == 1);
+
return ntids;
}
diff --git a/src/backend/access/gist/gistget.c
b/src/backend/access/gist/gistget.c
index 111c310f9df..23f77d6841a 100644
--- a/src/backend/access/gist/gistget.c
+++ b/src/backend/access/gist/gistget.c
@@ -348,6 +348,10 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem,
OffsetNumber maxoff;
OffsetNumber i;
MemoryContext oldcxt;
+ ItemPointerData tids_match[MaxIndexTuplesPerPage];
+ ItemPointerData tids_recheck[MaxIndexTuplesPerPage];
+ int ntids_match = 0;
+ int ntids_recheck = 0;
Assert(!GISTSearchItemIsHeap(*pageItem));
@@ -464,9 +468,15 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem,
{
/*
* getbitmap scan, so just push heap tuple TIDs into
the bitmap
- * without worrying about ordering
+ * without worrying about ordering. Because
tbm_add_tuples
+ * takes a single recheck flag, we split matching TIDs
into two
+ * per-page batches based on the recheck value.
*/
- tbm_add_tuples(tbm, &it->t_tid, 1, recheck);
+ if (recheck)
+ tids_recheck[ntids_recheck++] = it->t_tid;
+ else
+ tids_match[ntids_match++] = it->t_tid;
+
(*ntids)++;
}
else if (scan->numberOfOrderBys == 0 && GistPageIsLeaf(page))
@@ -543,6 +553,15 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem,
}
}
+ /*
+ * For a getbitmap scan, flush all matching TIDs from this page into
the TIDBitmap.
+ */
+ if (tbm)
+ {
+ tbm_add_tuples(tbm, tids_match, ntids_match, false);
+ tbm_add_tuples(tbm, tids_recheck, ntids_recheck, true);
+ }
+
UnlockReleaseBuffer(buffer);
}
diff --git a/src/backend/access/hash/hash.c b/src/backend/access/hash/hash.c
index 63846c10840..3b8ad50bec1 100644
--- a/src/backend/access/hash/hash.c
+++ b/src/backend/access/hash/hash.c
@@ -356,21 +356,29 @@ hashgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
HashScanOpaque so = (HashScanOpaque) scan->opaque;
bool res;
int64 ntids = 0;
- HashScanPosItem *currItem;
res = _hash_first(scan, ForwardScanDirection);
+ /*
+ * Each iteration of this loop reads one index page worth of matching
+ * TIDs (already collected into so->currPos.items by _hash_first/
+ * _hash_next) and adds them to the TIDBitmap in a single batch. Dead
+ * index entries are handled by _hash_first/_hash_next whenever
+ * scan->ignore_killed_tuples is true, so there is nothing else to do.
+ */
while (res)
{
- currItem = &so->currPos.items[so->currPos.itemIndex];
+ ItemPointerData tids[MaxIndexTuplesPerPage];
+ int ntids_page = 0;
+ const int lastItem = so->currPos.lastItem;
- /*
- * _hash_first and _hash_next handle eliminate dead index
entries
- * whenever scan->ignore_killed_tuples is true. Therefore,
there's
- * nothing to do here except add the results to the TIDBitmap.
- */
- tbm_add_tuples(tbm, &(currItem->heapTid), 1, true);
- ntids++;
+ for (int i = so->currPos.firstItem; i <= lastItem; i++)
+ tids[ntids_page++] = so->currPos.items[i].heapTid;
+
+ /* _bt_next() advanced to the next page if itemIndex is past
lastItem. */
+ so->currPos.itemIndex = lastItem + 1;
+ tbm_add_tuples(tbm, tids, ntids_page, true);
+ ntids += ntids_page;
res = _hash_next(scan, ForwardScanDirection);
}
diff --git a/src/backend/access/nbtree/nbtree.c
b/src/backend/access/nbtree/nbtree.c
index 0abdd7b49f5..9fcb8d7d652 100644
--- a/src/backend/access/nbtree/nbtree.c
+++ b/src/backend/access/nbtree/nbtree.c
@@ -291,45 +291,29 @@ 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;
+ const int lastItem = so->currPos.lastItem;
- 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;
- }
+ for (int i = so->currPos.firstItem; i <= lastItem; i++)
+ tids[ntids_page++] =
so->currPos.items[i].heapTid;
- /* Save tuple ID, and continue scanning */
- heapTid =
&so->currPos.items[so->currPos.itemIndex].heapTid;
- tbm_add_tuples(tbm, heapTid, 1, false);
- ntids++;
- }
+ /* _bt_next() advanced to the next page if itemIndex is
past lastItem. */
+ so->currPos.itemIndex = lastItem + 1;
+ 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;
}
/*
diff --git a/src/backend/access/spgist/spgscan.c
b/src/backend/access/spgist/spgscan.c
index 2cc5f06f5d7..8ec4ef86b05 100644
--- a/src/backend/access/spgist/spgscan.c
+++ b/src/backend/access/spgist/spgscan.c
@@ -928,8 +928,17 @@ storeBitmap(SpGistScanOpaque so, ItemPointer heapPtr,
SpGistLeafTuple leafTuple, bool recheck,
bool recheckDistances, double *distances)
{
+ const int b = recheck ? 1 : 0;
+
Assert(!recheckDistances && !distances);
- tbm_add_tuples(so->tbm, heapPtr, 1, recheck);
+
+ if (so->ntbmTids[b] == SPGIST_TBM_BATCH_SIZE)
+ {
+ tbm_add_tuples(so->tbm, so->tbmTids[b], so->ntbmTids[b],
recheck);
+ so->ntbmTids[b] = 0;
+ }
+
+ so->tbmTids[b][so->ntbmTids[b]++] = *heapPtr;
so->ntids++;
}
@@ -943,9 +952,14 @@ spggetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
so->tbm = tbm;
so->ntids = 0;
+ so->ntbmTids[0] = 0;
+ so->ntbmTids[1] = 0;
spgWalk(scan->indexRelation, so, true, storeBitmap);
+ for (int i = 0; i < 2; i++)
+ tbm_add_tuples(so->tbm, so->tbmTids[i], so->ntbmTids[i], i ==
1);
+
return so->ntids;
}
diff --git a/src/include/access/spgist_private.h
b/src/include/access/spgist_private.h
index ec6d6f5f74d..42766341889 100644
--- a/src/include/access/spgist_private.h
+++ b/src/include/access/spgist_private.h
@@ -22,6 +22,8 @@
#include "utils/geo_decls.h"
#include "utils/relcache.h"
+#define SPGIST_TBM_BATCH_SIZE 256
+
typedef struct SpGistOptions
{
@@ -221,6 +223,9 @@ typedef struct SpGistScanOpaqueData
TIDBitmap *tbm; /* bitmap being filled */
int64 ntids; /* number of TIDs passed to
bitmap */
+ ItemPointerData tbmTids[2][SPGIST_TBM_BATCH_SIZE];
+ int ntbmTids[2]; /* number of buffered TIDs */
+
/* These fields are only used in amgettuple scans: */
bool want_itup; /* are we reconstructing
tuples? */
TupleDesc reconTupDesc; /* if so, descriptor for reconstructed
tuples */
--
2.55.0
