Keep TIDBitmap pagetable memory across bitmap scans

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/6193bdf3-218e-4cbc-b369-d964c52af4e0@gmail.com