Re: Keep TIDBitmap pagetable memory across bitmap scans

Hi Greg!

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

Thanks for investigating this further.

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

It's actually curious that it's that bad. All processes are independent
so they have their own page tables, mm_struct lists, etc., all with
their own locks. The kernel's page allocator should scale well enough to
not cause that level of contention.

I believe the folio_lruvec_lock_irqsave() stems from protecting the
cgroup's memory accounting. Could you rerun your test without cgroups?
This is still a good finding but it would be interesting as well to see
how it performs without cgroups.

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

glibc's malloc uses sbrk() by default. I haven't looked into why causes
the documentation claims today it uses mmap(). Regardless, it causes the
same problem of repeatedly allocated and freed memory causing minor page
faults each time they're accessed the first time after being allocated
again.

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

While I think the direction of keeping the memory around is the right
one, I don't think we should do that at the Bitmap Index Scan (BIS)
level for two reasons:

1. A database with lots of connections could quickly spent gigabytes on
unused BIS buffers. Freeing the memory when unused quickly gets you
into memory allocator territory.
2. There are more places in the code where we double allocation sizes as
we go and hence cause avalanches of page faults repeatedly. It would
be good to fix them all in one go.

You showed already that the majority of the slowdown goes away by having
a memory allocator that less eagerly returns freed memory to the OS.

It seems like there's a threshold that controls how aggressively malloc
trims free memory that can be changed via mallopt(M_TRIM_THRESHOLD, -1).
How about giving this a try and thinking about using it to our advantage.

Is anyone aware of an effort to change PostgreSQL to use e.g. jemalloc
which better allows controlling when memory is returned?

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

That's quite impressive. Let's check how that looks without cgroups.

--
David Geier