Re: use radix tree for bitmap heap scan

On Wed, Oct 14, 2026 at 6:14 AM David Geier <geidav(dot)pg(at)gmail(dot)com> wrote:
>
> On 9/24/25 11:30, John Naylor wrote:

> > 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?

Currently, tbm_intersect_page() already reports that a page can be
deleted so that the caller can delete it, so I was just continuing
that practice.

BTW, my local branch has deletion-during-iteration working, and it's
not too ugly.

> You could also create a new radix tree and
> only enter TIDs present in both inputs?
>
> I guess lossification will need deletions though?

Right.

> 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.

Already on my get-back-to list, maybe in November. (note for would-be
volunteers: the latest patch in this thread is _not_ ready for
testing.)

> 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.

How much of a major cost?

Related: I do suspect the lossification threshold is broken: With 4MB
work_mem, the hash table grows from 3MB to 6MB, but the max entries
number is computed from 4MB (accounting for the iteration arrays), so
I believe (but haven't verified) that it starts lossifying when the
hash table is not even close to full. But if we tried to account for
that somehow, then we still risk the table growing from 6MB to 12MB
because of the linear probe length threshold. That is to say, yes,
there are multiple reasons to switch to radix tree if the challenges
can be overcome, and I think they can.

--
John Naylor
Amazon Web Services