use radix tree for bitmap heap scan

Attached is PoC v2, which fully replaces the hash table with radix
tree and passes regression tests.

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.

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)
1) save per-leaf-node keys in the iterator
2) delete the keys when iteration leaves that node, possibly with a
bulk-delete mechanism
3) restart iteration from the top, at the next part of the key space

0007 implements the above (but no bulk deletion). It's so far only
used for intersection, but will also be the basis for page
lossification. Because latter requires inserts as well as deletes, it
could be tricky to do nicely. Compared to the hash table, retail
deletion is likely slower in general, but since they're batched per
leaf node it might be okay. 0006 and 0007 were tricky to get right,
and may contain bugs.

0008 is the main event. It's sloppy about memory management and
contains a kluge for the shared memory case: I was unable to quickly
adapt the existing relative pointer logic so I gave up and and
allocated a new DSA array, since it works and gets the point across.

There are new radix tree tests (separately, some of the existing ones
should be simplified to look more like the new bitmapset testing
module), but no new bitmap heap scan tests.

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?

--
John Naylor
Amazon Web Services

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]/messages/by-id/CAPsAnrn5yWsoWs8GhqwbwAJx1SeLxLntV54Biq0Z-J_E86Fnng@mail.gmail.com) 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]/messages/by-id/CAPsAnrn5yWsoWs8GhqwbwAJx1SeLxLntV54Biq0Z-J_E86Fnng@mail.gmail.com and [2]/messages/by-id/29f27b97-b3d7-476b-acae-832b3443b0c4@gmail.com this would further close
the gap compared to plain vanilla index scan.

--
David Geier

[1]: /messages/by-id/CAPsAnrn5yWsoWs8GhqwbwAJx1SeLxLntV54Biq0Z-J_E86Fnng@mail.gmail.com
/messages/by-id/CAPsAnrn5yWsoWs8GhqwbwAJx1SeLxLntV54Biq0Z-J_E86Fnng@mail.gmail.com
[2]: /messages/by-id/29f27b97-b3d7-476b-acae-832b3443b0c4@gmail.com
/messages/by-id/29f27b97-b3d7-476b-acae-832b3443b0c4@gmail.com

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.

[1]
/messages/by-id/CAPsAnrn5yWsoWs8GhqwbwAJx1SeLxLntV54Biq0Z-J_E86Fnng@mail.gmail.com
[2]
/messages/by-id/29f27b97-b3d7-476b-acae-832b3443b0c4@gmail.com

I missed [3]/messages/by-id/CAEEBa3U7QDChb=PjzQGHoie-tOnfr7dumhO12Tp=5o2iT4t_ug@mail.gmail.com which is yet another improvement to reduce the overhead of
BIS. For overview purposes we have:

1. Parallelizing Bitmap Index Scan and Bitmap And/Or
2. Optimizing the block sort via sort_template.h
3. Improving TID insertion performance by batching
4. Using radix tree instead of simplehash.h in TIDBitmap

--
David Geier

[3]: /messages/by-id/CAEEBa3U7QDChb=PjzQGHoie-tOnfr7dumhO12Tp=5o2iT4t_ug@mail.gmail.com
/messages/by-id/CAEEBa3U7QDChb=PjzQGHoie-tOnfr7dumhO12Tp=5o2iT4t_ug@mail.gmail.com

On Wed, Oct 14, 2026 at 6:14 AM David Geier <geidav.pg@gmail.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

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.

It seems like some of the TIDBitmap operations might be better
implemented differently on top of a radix tree. For example union and
intersection could profit from iterating both trees to compute the
intersection / union in the spirit of a merge sort.

But I can see the appeal to make TIDBitmap first work as is on top of
the radix tree, as long as it doesn't put hard-to-implement requirements
on the radix tree.

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

Nice!

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

I'm ready to help, once you have a patch that is ready for testing. Let
me know.

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?

The "actual time" of the BIS in my test query dropped from 193 ms to 139
ms when reserving all memory of the final hash table upfront by passing
its final size to pagetable_create() in tbm_create_pagetable().

Part of that time is spent on page faults because the allocations are
big enough for ASET to call malloc() and for malloc() to call sbrk(),
and then in the other direction for free() to call systrim() which calls
sbrk() to shrink the heap again.

This can be seen also from the perf stat output:

3,034 page-faults # 5114.8 faults/sec page_faults_per_second

vs when reserving enough memory to avoid resizing

0 page-faults # 0.0 faults/sec page_faults_per_second

I'm not entirely sure why it has 0 page faults for successive calls when
I reserve a big hash table. It should still have to fault when writing
to the pages of the initially reserved hash map. It seems to cache the
allocation somehow as I no longer see calls to sbrk().

My take away beyond the radix tree effort is that it would be useful if
we could allocate anonymous and shared memory backed by 2 MiB huge
pages. That would help for TIDBitmap but also for large sort buffers or
large hash join hash tables. Shared allocations can end up in the main
memory segment if dynamic_shared_memory_size is picked appropriately
but, FWIR, anonymous memory is always 4k-backed.

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.

Ahh, that's a good one. It makes sense because max entries is not
updated when simplehash.h grows. Then the lossification will start too
early.

What would be useful is a list of shortcomings of simplehash.h-based
TIDBitmap and how the radix tree would overcome those. It doesn't have
to complete but I feel like I'm not having the whole picture. We could
then see if there are more areas where a radix tree would help (e.g. how
certain TBMBitmap operations are implemented, etc.).

--
David Geier

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?

The "actual time" of the BIS in my test query dropped from 193 ms to 139
ms when reserving all memory of the final hash table upfront by passing
its final size to pagetable_create() in tbm_create_pagetable().

Part of that time is spent on page faults because the allocations are
big enough for ASET to call malloc() and for malloc() to call sbrk(),
and then in the other direction for free() to call systrim() which calls
sbrk() to shrink the heap again.

This can be seen also from the perf stat output:

3,034 page-faults # 5114.8 faults/sec page_faults_per_second

vs when reserving enough memory to avoid resizing

0 page-faults # 0.0 faults/sec page_faults_per_second

I'm not entirely sure why it has 0 page faults for successive calls when
I reserve a big hash table. It should still have to fault when writing
to the pages of the initially reserved hash map. It seems to cache the
allocation somehow as I no longer see calls to sbrk().

My take away beyond the radix tree effort is that it would be useful if
we could allocate anonymous and shared memory backed by 2 MiB huge
pages. That would help for TIDBitmap but also for large sort buffers or
large hash join hash tables. Shared allocations can end up in the main
memory segment if dynamic_shared_memory_size is picked appropriately
but, FWIR, anonymous memory is always 4k-backed.

Closer inspection revealed that all allocation functions that return
zeroed memory, such as palloc0(), palloc_extended(MCXT_ALLOC_ZERO),
repalloc0(), MemoryContextAllocZero(), etc., unconditionally call
memset() in the wrapper around the memory context, rather than leaving
that to the memory context.

Leaving the zeroing to the memory context would have the advantage of
the memory context being able to skip it, if it knows that the memory
it's going to return is already zeroed.

It would know that, for example, if we used calloc() to serve big zeroed
allocations. On Linux, calloc() skips zeroing the memory if it comes
fresh from sbrk or mmap (via the zero-fill-on-demand technique using a
zero page).

Performance is only one aspect here. The other aspect is memory
consumption: large zeroed allocations that is only sparsely written to
will unnecessarily get all pages faulted in which makes a difference
with vm.memory_overcommit = 0/1.

It could also prevent OOM situations: say we create a large simplehash.h
map, created based on estimated row count, but actual row count is much
lower.

--
David Geier