Re: use radix tree for bitmap heap scan

On Tuesday, November 10th, 2026 at 11:38 AM, David Geier <geidav(dot)pg(at)gmail(dot)com> wrote:

> Hi Greg!

Hey David. :)

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

Glad I could solve that mystery for you.

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

That's as good a guess as any at this point. I could keep digging, but is
there a point to it now? I do like allocators [1] so it's not like I'm
not interested...

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

Saw that, thanks!

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

I'll have to go back and look, I don't recall off hand. I agree about the
page fault.

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

That is true, and should help (or hide?) the issue.

> --
> David Geier

best.

-greg

[1] https://codeberg.org/gregburd/libumem