Re: use radix tree for bitmap heap scan

On 9/24/25 11:30, John Naylor wrote:
> Attached is PoC v2, which fully replaces the hash table with radix
> tree and passes regression tests.

Cool!

> The architecture is still one of tidbitmap.c having it's own tree of
> (fixed length) PagetableEntries. The eventual goal is for vacuum and
> tidbitmap to both use TID store in some form, but there are some
> architectural issues to work out first.

That sounds reasonable.

> 0001 temporarily gets rid of the tidbitmap one-page cache so I could
> always count on the hash table and radix tree having matching contents
> during development, barring bugs. I'm curious how important it is, so
> it doesn't yet get put back in this patch set.
> 0002 temporarily gets turns off page lossification for the same reason
> of matching contents. (Still not reimplemented)
> 0003 makes some radix tree APIs more similar to simplehash, in a
> backward compatible way.
> 0004 is a step towards putting allocation of tree values in the
> caller's hands. This will be even more necessary when doing unions and
> intersections with variable-length bitmaps (not yet implemented).
> 0005 make it easier to add new tree APIs that aren't used everywhere.
> 0006 RT_BEGIN_ITERATE_AT, similar to simplehash. This is a
> prerequisite for 0007, and could also be used for shared iteration.
> This implementation is naive and may slow down iteration, but that can
> easily be fixed.
>
> On Thu, Jul 3, 2025 at 3:43 PM I wrote:
>> Second issue: TBM intersection
>> 1) Radix tree iteration assumes that no one will delete keys out from
>> under it. That includes the caller itself! This is not sufficient for
>> intersecting bitmaps. I kluged around it by saving
>> blocks-to-be-deleted in a stack array, but a proper solution could be
>> to (vigorous handwaving)

I'm not familiar with the radix tree code, but why does specifically
intersection need deletion? You could also create a new radix tree and
only enter TIDs present in both inputs?

I guess lossification will need deletions though?

> With some cleanups, restoring lossification, and maybe performance
> work, the above could be the basis of a viable commit, since it has a
> fairly small blast radius and gets rid of the qsort steps. However, I
> believe it won't quite be enough on its own for a major release. For
> that, we'd want
> * variable-length keys to save memory, which would add some complexity
> to union and intersection steps
> * probably direct iteration over the tree, rather than via reference
> arrays, which add memory and are no longer as useful because we don't
> need a separate sorting step
> * integration with TID store in some form
> * adjustments to costing?
Before spending more time on getting the details right, I would be
interested in some performance numbers about raw insert / construction
performance without lossification. Saving the sort (which is parallel
with [1]) and being better in the lossy-case is great but only as long
as we don't regress the common case.

One more property of the hash map based TIDBitmap to consider is its
incremental growth:

So I'm wondering: what is the (re-)allocation pattern of the radix tree?
Is it incrementally resized, e.g. node by node? If so, the amortized
insertion cost might be lower than we think with increasing number of TIDs.

This is because today, a major cost of large BitmapIndexScans is
repeatedly growing the simplehash.h-based hash table backing TIDBitmap
from initially 128 elements to its final size.

It would be great if we could overcome this bottleneck as well with the
radix tree approach. Together with [1] and [2] this would further close
the gap compared to plain vanilla index scan.

--
David Geier

[1]
https://www.postgresql.org/message-id/flat/CAPsAnrn5yWsoWs8GhqwbwAJx1SeLxLntV54Biq0Z-J_E86Fnng%40mail.gmail.com
[2]
https://www.postgresql.org/message-id/29f27b97-b3d7-476b-acae-832b3443b0c4%40gmail.com