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?
Hi John, David, I'm ping'ing you two because this came up while reviewing the radix tree thread you've been working on [1], it got me thinking. So I dove in and measured it. I was going to post into your thread but because there is a prototype patch that resulted from my investigation, I thought I'd start a new thread. A bitmap heap scan over many pages spends much of its time in the kernel when many backends run it at once. The TIDBitmap pagetable is a simplehash that starts at 256 slots and doubles until it fits. For a bitmap of about 17k heap pages that is seven grows, from a 12 kB array up to a 1.5 MB one, about 2.9 MB of zeroed allocations per query. Each array goes to malloc, and with glibc's default settings the heap grows with brk for each step and is trimmed back to the kernel at ExecutorEnd. The next query faults the same pages in again, about 730 page faults per query. With many backends doing this at once, the faults and the trims contend in the kernel. On a 96-thread host at 96 clients, 27% of all cycles are in native_queued_spin_lock_slowpath under folio_lruvec_lock_irqsave (all backends in one memory cgroup), and a third of the CPU is system time. David, I think you saw the same growth cost and measured presizing the table: 3,034 page faults down to 0, and a bitmap index scan from 193 to 139 ms [2]. Presizing from the planner's estimate only helps where the estimate is right, though. For "ga @> ARRAY[a, b]" on an int4[] GIN index the estimate here is 4 rows against 17k, so the table grows from 256 slots as before. And under the two most common libc implementations for Linux (musl, glibc) with a low mmap threshold, every array over 128 kB is mapped and unmapped each time. In a prototype I tried presizing to the right size, but that took musl only from 768 to 424 faults per query. The attached prototype patches try a different approach, they keep and reuse the allocated memory instead. 0001 adds src/test/modules/test_tidbitmap. It builds up to 32 bitmaps at once from synthetic block numbers, checks each one's contents by iterating it, and raises errors while they are being built. The SQL part compares BitmapAnd, BitmapOr, GIN prefix matches, rescans, an open cursor, an error, a cancel, work_mem changes and a parallel bitmap heap scan against a plan with no bitmap. It passes without 0002. 0002 keeps the pagetable array and the sorted page list of up to two large private bitmaps per backend, in a memory context named "TIDBitmap cache". A bitmap whose table reaches 2048 slots takes a free entry and switches to the entry's array in one step. Bitmaps that find no free entry work as before, and so do small bitmaps and shared ones. The arrays are allocated in the cache context, and a reset callback on the bitmap's own context gives the entry back, so an error that skips tbm_free() neither frees them nor leaves a dangling owner. Two entries is the smallest number that covers BitmapAnd, which holds the result and one input at a time; with one entry, the second bitmap still faulted. The threshold is 2048 slots because simplehash grows a large table from inside the insert when its probe chains get long, so the cache has to be taken before the next grow can happen, and a 2048-slot array (96 kB) is the largest that stays under the 128 kB mmap threshold. Benchmark numbers: c7i.metal-24xl (Xeon 8488C, 48 cores / 96 threads, one socket), Fedora 44, turbo off, THP off, shared_buffers 16 GB on huge pages, all data cached. 16M rows, ~17k rows per value scattered over ~16k heap pages, so each bitmap is ~17k exact pages. pgbench -M prepared, fixed transactions per client, stock and patched interleaved ABBA, each built twice with different code layouts (mold --shuffle-sections), steady-state TPS. An A/A pair put the noise floor at 2.5%. Faults are system-wide, per query. 96 clients, glibc defaults, TPS (page faults per query): btree g = v 2,756 (734) -> 4,321 (0) +56.8% GIN g = v (btree_gin) 2,816 (724) -> 4,081 (0) +44.9% GIN ga @> ARRAY[v, w] 2,926 (711) -> 3,944 (0) +34.8% BitmapAnd btree AND GIN 2,213 (1,092) -> 3,648 (0) +64.9% Under musl, btree goes from 2,569 to 4,207 TPS (+63.8%) and BitmapAnd from 1,838 to 3,472 (+88.9%), with 43 and 102 faults per query left. Under jemalloc, which never faulted much, the gain is +4.7% to +11.9%: that part is the doubling's rehash and copy. What a backend keeps is at most work_mem in total, so 4 MB at the default, and it shows in pg_backend_memory_contexts as "TIDBitmap cache". A bitmap created with a smaller work_mem frees idle entries that don't fit. There is no idle release, the memory is retained until such a bitmap scan or backend exit. Freeing it at ReadyForQuery would bring the faults back for every query, and catching a backend that sits idle would need a timer. If large work_mem settings make this a problem, a fixed cap below work_mem is the simple alternative. The reproducer (table setup, pgbench scripts, measurement scripts) is small; I can post it if anyone wants to run it. John, I'll follow up in that thread on how the two relate. best. -greg [1] https://postgr.es/m/6a55187b-8b27-41a8-bef1-ef7259dccf8d%40gmail.com [2] https://postgr.es/m/[email protected]
v1-0001-Add-test-module-for-TIDBitmap.patch.gz
Description: application/gzip
v1-0002-Keep-TIDBitmap-pagetable-memory-for-the-next-bitm.patch.gz
Description: application/gzip
