Re: use radix tree for bitmap heap scan

On Fri, Oct 16, 2026, John Naylor wrote:
> On Wed, Oct 14, 2026, David Geier wrote:
>> 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?

I measured this while chasing a many-client slowdown, and have posted a
patch for it in a new thread [1].

The short answer: on its own the growth is a few percent, and the page
faults it causes are the rest. The test was a count(*) whose bitmap
covers ~17k heap pages, glibc defaults, data cached. Removing most of
the growth and its page faults was worth +13.5% at 1 client and +56.8%
at 96 clients on a 96-thread host. Under jemalloc, where hardly
anything faults, only the rehash and copy of the doubling is left, and
removing it was worth +4.9% at 1 client and +6.3% at 96.

On Tue, Oct 20, 2026, David Geier wrote:
> 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().

I saw the same. Unpresized, each grow from 256 slots up is a fresh
malloc that glibc carves from the top of the heap with brk, and at
ExecutorEnd free() trims the heap back with brk, so the next query
faults the same pages in again. I counted about 5.7 brk calls and ~730
page faults per query. With the table presized there were no brk calls
at all, so glibc kept that memory between queries. I haven't worked out
from the glibc source why the one big allocation stays and the doubling
chain doesn't.

Under concurrency those faults are the expensive part: at 96 clients,
27% of all cycles were in native_queued_spin_lock_slowpath under
folio_lruvec_lock_irqsave. Presizing removes them only when the
estimate is right (4 rows estimated against 17k for "@>" on two int4[]
elements, in my test), and under musl, or glibc with a low mmap
threshold, it only roughly halved them. So the patch keeps the
pagetable memory per backend instead, bounded by work_mem. Details and
numbers are in the new thread.

On Tue, Oct 20, 2026, David Geier wrote:
> 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.

I tried that in a prototype last month. Allocating without
MCXT_ALLOC_ZERO and setting only each slot's status byte made no
difference to the faults (732 vs 732 per query): with 48-byte slots, one
status byte per slot touches every page anyway. The memset costs CPU,
not faults. calloc() was worse, 1,161 faults per query, which I did not
track down.

How this relates to the radix tree: the patch only changes how
tidbitmap.c allocates and frees the simplehash arrays and the sorted
page list, so the radix tree would replace most of it.

The question it might help answer is whether the tree's memory survives
from one query to the next. If the nodes come from a memory context
that is deleted at ExecutorEnd, whether glibc keeps or returns those
blocks depends on their sizes, so it needs measuring. If it does return
them, the same approach would carry over. Keep the tree's context per
backend, bounded by work_mem, and give it back with a reset callback. I
can run the same reproducer against a radix-tree patch once one is ready
for testing.

On the lossify threshold: the patch doesn't change it. At 4 MB
work_mem maxentries is 65,536, and a 65,536-slot table grows at 58,982
members, so the table still reaches 131,072 slots (6 MB) before lossify
starts. The patch never caches an array larger than work_mem, so a
table like that finishes the old way.

best.

-greg

[1] https://postgr.es/m/tidbitmap-cache-v1.20261108.b957201f%40burd.me