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

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