Re: use radix tree for bitmap heap scan

Hi Greg!

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

Hah, I knew I saw it show up in a production instance. Hadn't realized
it came from running many queries concurrently. Cool you found that.

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

A shot into the dark: sbrk() can only shrink if there's no allocation
sticking around after the freed memory. Maybe that causes the virtual
memory to not be returned in some cases?

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

Replying to that part in the other thread.

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

Yeah, writing just the status byte vs zeroing everything shouldn't make
much of a difference. The majority of the cost is the page fault. But
it's curious that calloc() didn't help. Did you remove writing to the
status byte after changing to calloc()?

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

The more important part is that the radix tree grows incrementally while
the hash map needs to double in size and then be rehashed. That lowers
the number of page faults considerably.

--
David Geier