Hi Haibo! Thanks for your review.
> One B-tree implementation detail still seems worth changing. The copy
> loop updates so->currPos.itemIndex for every TID. Using a local index
> and updating itemIndex once after the copy improved the 10M-row
> workload by another 2.24% in my tests. The new hash code uses the same
> pattern and could use the same cleanup.
Good point. The compiler loaded and stored itemIndex every single loop
iteration instead of keeping it in a register.
I've improved the code in v2.
> I also measured a small regression for a B-tree scan returning ten
> widely spaced keys:
>
> baseline: 33.195 us
> patched: 33.569 us
> delta: +0.85%
>
> I do not consider that a blocker, but it shows that copying into a
> batch is not free for tiny sparse scans.
The delta is very small. Are these results stable? If so, how did you
collect them? Can you share your benchmark?
I've included your example of 10 sparsely spaces TIDs in my benchmark
but cannot see a regression. Key idea of using sparse keys is that the
B-tree will do separate index searches for each key, which results in
the worst case for the optimization: each index search returns a single
row for which we pay the extra cost of the mempcpy() without saving any
hash map lookup.
I'm doubtful that you can actually measure the extra TID memcpy()
operation given all the other things going on. I've attached my extended
benchmark script.
> The main new aspect of v2 is that batching is now applied to hash,
> GiST, GIN, SP-GiST, and bloom as well. I do not see an obvious
> semantic problem with separating exact and recheck batches, since the
> TIDBitmap recheck flag is maintained at page level.
>
> However, my measurements demonstrate the benefit for B-tree, not
> necessarily for all of the newly covered access methods. Their result
> ordering and heap-page locality can be quite different. I think those
> additions need targeted measurements, or could be split into follow-up
> patches.
I've included all other changed index types (GIN, GIST, SP-GIST, HASH,
BLOOM) in my benchmark script. The case with few TIDs isn't that useful
for all index types. For example GIN won't do separate index searches
because the index is inverted. That means we gain for any TID count > 1.
The same for some of the other index types. But it's certainly good to test.
Here are the results for just the Bitmap Index Scan plan node. The
relative saving varies because it depends on the total runtime of the
specific index AM but the absolute savings are give or take constant
across all index AMs. This makes sense as all "many TIDs" queries match
roughly the same number of rows and hence save the same number of hash
map lookups.
query | ms_master_bis | ms_patched_bis | speedup
-------------+---------------+----------------+---------
btree-many | 170.372 | 115.071 | 1.48
btree-few | 0.006 | 0.006 | 1.00
gin-many | 342.281 | 285.198 | 1.20
gin-few | 0.001 | 0.001 | 1.00
gist-many | 827.222 | 758.613 | 1.09
gist-few | 0.449 | 0.452 | 0.99
hash-many | 296.819 | 251.802 | 1.17
hash-few | 0.004 | 0.004 | 1.00
bloom-many | 3743.758 | 3707.017 | 1.00
bloom-few | 43.989 | 42.358 | 1.03
spgist-many | 572.892 | 518.730 | 1.10
spgist-few | 0.003 | 0.003 | 1.00
And these are the results for the entire query:
query | ms_master | ms_patched | speedup
-------------+-----------+------------+---------
btree-many | 807.545 | 728.455 | 1.10
btree-few | 0.031 | 0.030 | 1.03
gin-many | 1063.716 | 971.578 | 1.09
gin-few | 0.013 | 0.013 | 1.00
gist-many | 1427.066 | 1355.651 | 1.05
gist-few | 0.470 | 0.471 | 0.99
hash-many | 1169.467 | 1127.259 | 1.03
hash-few | 0.026 | 0.026 | 1.00
bloom-many | 3961.366 | 3931.871 | 1.00
bloom-few | 49.171 | 46.512 | 1.05
spgist-many | 1196.306 | 1130.279 | 1.05
spgist-few | 0.018 | 0.017 | 1.05
Despite configuring the system for stable results, there's some noise
which is visible in the "few rows" queries but only when looking at
total query runtime. The results for just the BIS are pretty stable and
show no regression which is not within noise.
> A couple of smaller points:
>
> gistScanPage() allocates both page-sized arrays even for non-bitmap
> scans.
> The SP-GiST buffers enlarge every scan opaque, including tuple scans.
I think that's fine. Do you mean to imply that we should allocate these
buffers dynamically? If we think they're too big, I would rather reduce
the batch size than allocating them dynamically.
> A comment explaining the B-tree primitive-scan loop and the
> BTScanPosItem copy would help.
Added to explain when _bt_next() will advance to the next page. Is there
something else you had in mind?
> The B-tree batching approach still looks worthwhile to me. I would
> apply the local-index cleanup there, but I would want some performance
> evidence for the newly added access methods before treating the whole
> v2 patch as ready.
What do you mean by "local-index cleanup"?
The only other change in v2, not yet discussed in this mail, is moving
the call to tbm_add_tuples() for the residual batch to after the outer
loop in blgetbitmap(). It was incorrectly placed after the block. But if
a block has few matches there's no need to flush the batch each time.
The patch passes all tests.
--
David Geier
getbitmap_batching_benchmark.sql
Description: application/sql
From 0dc5c661cf2c00b435818ce91c8a159ca5faabcd Mon Sep 17 00:00:00 2001 From: David Geier <[email protected]> Date: Wed, 7 Oct 2026 16:26:52 +0200 Subject: [PATCH v3] 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 | 23 ++++++++++------- src/backend/access/nbtree/nbtree.c | 40 +++++++++-------------------- src/backend/access/spgist/spgscan.c | 16 +++++++++++- src/include/access/spgist_private.h | 5 ++++ 7 files changed, 116 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 b2e34d2d45e..1cc0b2fdc8b 100644 --- a/src/backend/access/hash/hash.c +++ b/src/backend/access/hash/hash.c @@ -356,21 +356,26 @@ 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; - /* - * _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++; + while (so->currPos.itemIndex <= so->currPos.lastItem) + tids[ntids_page++] = so->currPos.items[so->currPos.itemIndex++].heapTid; + + 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.53.0
