Re: Improving scalability of Parallel Bitmap Heap/Index Scan

Hi hackers,

This is a PoC patch set that makes Bitmap Index Scans (BIS), Bitmap Heap
Scans (BHS), and Bitmap And/Or plan nodes run truly in parallel by
distributing the bitmap build, the sort, and the HEAP scan across all
workers instead of leaving a single participant to do the heavy lifting.

The core idea is the following:

Each parallel BIS worker builds its own private TIDBitmap from the index
blocks it reads. Once all BIS participants finish, the bitmaps are
repartitioned by hash(pageno / 256) % nparticipants. This way every
worker ends up with roughly 1/N-th of the pages / TIDs, while keeping
runs of 256 local to one participant which is important to keep
TIDBitmap for working efficiently. From that point on, each participant
only processes its private partition. No shared iteration state exists
and hence no synchronization is needed above the BIS. This trades some
extra memory usage and the repartitioning step for simplicity and
"minimal" code changes. It would be much more invasive to change
TIDBitmap to be parallel-safe. It also has a nice side effect: ordered
iteration in BHS is now always process-local, so the complicated
shared-iteration code in tidbitmap.c almost completely disappears.
Shared iteration now only happens during the partitioning pass, which is
much simpler because it's unordered and synchronized with plain barriers
instead of a refcount.

One design aspect worth calling out: this diverges from the usual
PostgreSQL parallelism model, where workers cooperate on shared state
protected by locks or atomics. Here, each worker owns private state and
we repartition data between phases instead of synchronizing access
between them. I think this is a better fit for this particular problem —
it's what eliminates the per-TID lock contention, and it makes the
iteration code dramatically simpler — but it's a precedent worth
discussing explicitly.

There's also a forward-looking angle: ongoing work ([1], [2]) is
converting TIDBitmap from a hash table to a radix tree. Once that lands,
we could consider building a single cooperative bitmap rather than N
private ones — in case this structure lends itself better to shared
write access (which seems to be the case).

> 1. The BIS always only runs in a single process, also when the parent
> BHS is parallel. The first process arriving in the BHS serves as
> leader and executes the BIS.

Now truly parallel: BIS, BHS, and Bitmap And/Or all distribute work
across participants as described above.

> 2. As long as execution is "exact" (TIDs are stored instead of page
> bits), the parallel BHS sorts all TIDs to ensure pages are accessed
> sequentially. The sort is also performed just by a single worker.
> Already with a few tens of thousands of pages to scan, the sort time
> can make up a significant portion of the total runtime. Large page
> counts and the need for parallelism are not uncommon for BHS, as one
> use case is closing the gap between index and sequential scans. The
> BHS costing seems to not account for that.

Each worker now sorts only its own 1/N-th of the pages / TIDs, so the
sort is genuinely parallel too. I also applied sort_template.h (inspired
by [3]) to speed up the sort itself.

> 3. The BHS does not scale well with an increasing number of parallel
> workers, even when accounting for the sequential parts of execution.
> A perf profile shows that the TID list / bitmap iteration code
> heavily contents on a mutex taken for every single TID / page bit
> (see LWLockAcquire(&istate->lock, LW_EXCLUSIVE) in tidbitmap.c:1067).

Gone. Partitioned, private bitmaps need zero synchronization during the
scan/iteration.

> 4. The EXPLAIN ANALYZE statistics of the parallel BHS do not include
> the statistics of the parallel workers. For example the number of
> heap pages processed is what just the leader did. Similarly to other
> parallel plan nodes we should aggregate statistics across workers.

Already fixed in [4].

I've used two queries to test my changes: query 1 reads about 10% of the
table, BIS encounters each block once. Query 2 reads about 2.5% of the
table, but BIS encounters each block multiple times. The runtimes are in
milliseconds measured on a AMD Ryzen 7 9700X, configured for reliable
results (no turbo-boost, no frequency scaling, no ASLR, ...).

query | serial | parallel master | parallel patched | speedup
-------+--------+-----------------+------------------+---------
Q1 | 73 | 23 | 17 | 1.35
Q2 | 1907 | 689 | 433 | 1.59

These results show the lower end of possible gains. They are pessimistic
in the sense that the accessed HEAP pages fit into Linux page cache and
therefore the benefit of reading them in order / not rereading them
multiple times is far less than e.g. on slow network attached storage.

I'm planning to do more testing in a more realistic scenario to show the
upper end of possible gains.

--
David Geier

[1]
https://www.postgresql.org/message-id/flat/CANWCAZaKLii6bDV_ZBP05jQLdFVD0d0Yjrfp6c9a6THFfXiKAg%40mail.gmail.com
[2]
https://www.postgresql.org/message-id/flat/CAFBsxsFhMdC8dsYiupad24c952DX0B8K5msTvi7s4sxvTmep4Q%40mail.gmail.com
[3]
https://www.postgresql.org/message-id/CA+hUKGKztHEWm676csTFjYzortziWmOcf8HDss2Zr0muZ2xfEg@mail.gmail.com
[4]
https://www.postgresql.org/message-id/flat/b3d80961-c2e5-38cc-6a32-61886cdf766d%40gmail.com