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

On Wed, Oct 14, 2026 at 2:58 AM David Geier <geidav(dot)pg(at)gmail(dot)com> wrote:
>
> 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

Hi David,

Thanks for the update and for extending the benchmarks.

The B-tree change is what I meant by the local-index cleanup. In v3
the copy loop now uses a local loop variable and updates itemIndex only
once afterwards. That addresses my concern there.

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.

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.

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.

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.

The bloom residual-batch change also looks right to me; carrying the
batch across index blocks avoids unnecessarily flushing small batches.

I noticed only a few formatting nits in v3, such as more =_bt_next,
the long GiST comment, and the indentation of the second ntbmTids
assignment in spggetbitmap(). Nothing substantive there.

With the corresponding local-index cleanup in hash, the patch looks
good to me.

Thanks,
Haibo