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
