Improving scalability of Parallel Bitmap Heap/Index Scan

On Thu, Jul 14, 2022 at 5:13 PM David Geier <geidav.pg@gmail.com> wrote:

optimizing the PagetableEntry data structure for size and using a faster

sorting algorithm like e.g. radix sort

On this note, there has been a proposed (but as far as I know untested)
patch to speed up this sort in a much simpler way, in this thread

/messages/by-id/CA+hUKGKztHEWm676csTFjYzortziWmOcf8HDss2Zr0muZ2xfEg@mail.gmail.com

where you may find this patch

/messages/by-id/attachment/120560/0007-Specialize-pagetable-sort-routines-in-tidbitmap.c.patch

and see if it helps.

--
John Naylor
EDB: http://www.enterprisedb.com

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]/messages/by-id/CANWCAZaKLii6bDV_ZBP05jQLdFVD0d0Yjrfp6c9a6THFfXiKAg@mail.gmail.com, [2]/messages/by-id/CAFBsxsFhMdC8dsYiupad24c952DX0B8K5msTvi7s4sxvTmep4Q@mail.gmail.com) 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]/messages/by-id/CA+hUKGKztHEWm676csTFjYzortziWmOcf8HDss2Zr0muZ2xfEg@mail.gmail.com) 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]/messages/by-id/b3d80961-c2e5-38cc-6a32-61886cdf766d@gmail.com.

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]: /messages/by-id/CANWCAZaKLii6bDV_ZBP05jQLdFVD0d0Yjrfp6c9a6THFfXiKAg@mail.gmail.com
/messages/by-id/CANWCAZaKLii6bDV_ZBP05jQLdFVD0d0Yjrfp6c9a6THFfXiKAg@mail.gmail.com
[2]: /messages/by-id/CAFBsxsFhMdC8dsYiupad24c952DX0B8K5msTvi7s4sxvTmep4Q@mail.gmail.com
/messages/by-id/CAFBsxsFhMdC8dsYiupad24c952DX0B8K5msTvi7s4sxvTmep4Q@mail.gmail.com
[3]: /messages/by-id/CA+hUKGKztHEWm676csTFjYzortziWmOcf8HDss2Zr0muZ2xfEg@mail.gmail.com
/messages/by-id/CA+hUKGKztHEWm676csTFjYzortziWmOcf8HDss2Zr0muZ2xfEg@mail.gmail.com
[4]: /messages/by-id/b3d80961-c2e5-38cc-6a32-61886cdf766d@gmail.com
/messages/by-id/b3d80961-c2e5-38cc-6a32-61886cdf766d@gmail.com

Hi John,

On this note, there has been a proposed (but as far as I know untested)
patch to speed up this sort in a much simpler way, in this thread

https://www.postgresql.org/message-id/
CA%2BhUKGKztHEWm676csTFjYzortziWmOcf8HDss2Zr0muZ2xfEg%40mail.gmail.com
<https://www.postgresql.org/message-id/
CA%2BhUKGKztHEWm676csTFjYzortziWmOcf8HDss2Zr0muZ2xfEg%40mail.gmail.com>

where you may find this patch

/messages/by-id/attachment/120560/0007-Specialize-
pagetable-sort-routines-in-tidbitmap.c.patch <https://
www.postgresql.org/message-id/attachment/120560/0007-Specialize-
pagetable-sort-routines-in-tidbitmap.c.patch>

Thanks for the pointer. I've applied that change to my patch set. See
other mail. It helped a lot further reducing the sort time in each
parallel worker.

--
David Geier

Hi David,

My name is Osama Abdul Qader, I'm interested to work with you, I'm a little
busy with my chores right now and I'll review the patches that is attached
to this email.

More information about me: linkedin.com/in/oa-qader

With regards.
Osama Abdul Qader

On Mon, 5 Oct, 2026, 2:23 pm David Geier, <geidav.pg@gmail.com> wrote:

On Mon, Oct 5, 2026 at 3:52 PM David Geier <geidav.pg@gmail.com> wrote:

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.

Interesting. What's the unit of work for each worker? Can you describe
how and when repartitioning works? Let's say you have an "And" node
for two indexes.

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

It's not currently optimized for concurrency, so it would depend a lot
on the ordering of the input and could actually be worse especially
for e.g. a uuid index -- both cache misses and higher constant
overheads than a hash table. The advantage of the radix tree is that
1) iteration is automatically ordered so no sorting step, and 2) the
page table entries can be variable length, probably using less net
memory, and allowing the max number of TIDs per page to be decoupled
from the max number of tuples, and 3) easier to be smart about
lossification.

I have made progress this summer, but there are still a lot of finicky
details to get right.

--
John Naylor
Amazon Web Services

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.

Interesting. What's the unit of work for each worker? Can you describe
how and when repartitioning works? Let's say you have an "And" node
for two indexes.

Above the BIS, the unit of work is a disjoint partition of the
TIDBitmap, i.e. a non-overlapping set of HEAP blocks (and their TIDs in
non-lossy mode). This allows every operation above the BIS — Bitmap And,
Bitmap Or, and the Bitmap Heap Scan — to run locally in each worker
without any synchronization.

The unit of work inside the BIS is different: each worker scans a
portion of the index and builds a private TIDBitmap that may contain
TIDs of arbitrary HEAP blocks.

Repartitioning happens at the end of the BIS, after the index has been
read to completion by all participants. At that point, each participant
has a private TIDBitmap covering arbitrary HEAP pages that it shares
with the others through DSA. Then each participant create a new
TIDBitmap containing only the pages assigned to it, by scanning the
bitmaps of all other participants with the following condition to decide
if the block belongs to it or not:

murmurhash32(blockno / 256) % nparticipants == my_id

Dividing by 256 keeps runs of 256 consecutive HEAP pages together in one
participant, which is important for TIDBitmap efficiency. Because every
participant uses the same hash function and the same participant count,
the resulting partitions are identical across workers. The exchange uses
an unordered iterator, since order does not matter for this assignment.

For your Bitmap And example:

-> Bitmap Heap Scan
-> Bitmap And
-> Bitmap Index Scan(index_a)
-> Bitmap Index Scan(index_b)

Both leaf scans are parallel-aware and are run by every participant.
Worker i first executes the scan on index_a, repartitions the result
into partition A_i, then does the same for index_b to get partition B_i.
Since both scans use the same partitioning scheme, A_i and B_i cover
exactly the same set of HEAP pages. The Bitmap And node just intersects
A_i and B_i locally with tbm_intersect(); no locks, no shared iteration
state. The result is still partition i, which the Bitmap Heap Scan then
consumes.

So the only synchronization points are the two barriers inside each BIS
(one after sharing the local bitmaps, one after everyone has finished
reading the shared bitmaps). After that, the whole bitmap plan tree
above the BIS is embarrassingly parallel.

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

It's not currently optimized for concurrency, so it would depend a lot
on the ordering of the input and could actually be worse especially
for e.g. a uuid index -- both cache misses and higher constant
overheads than a hash table. The advantage of the radix tree is that
1) iteration is automatically ordered so no sorting step, and 2) the

For that to pay off, the increased cost for inserting must be reasonably
low. Is that the case?

page table entries can be variable length, probably using less net
memory, and allowing the max number of TIDs per page to be decoupled
from the max number of tuples,

Is this about wasting less memory for PagetableEntries that only contain
very few TIDs?

and 3) easier to be smart about lossification.

Can you share what ideas exist at this point?

I have made progress this summer, but there are still a lot of finicky
details to get right.

The even better implementation, that would keep the advantages of the
partitioning scheme while avoiding increased memory consumption and
rereading all bitmaps by all participants, is to keep the partitions in
shared memory from the staert and having each participant directly
insert the TIDs into the right partition, e.g.

BlockNumber blockno = ItemPointerGetBlockNumber(cur_tid);
uint32 p = murmurhash32(blockno / 256) % nparticipants;
tbm_add_tuple(tidbitmaps[p], cur_tid);

If we use enough partitions, say 8 per participant, then we might get
away with locking the entire tbm_add_tuple() operation, hoping that the
TIDs distribute more or less uniformly across all partitions. Now when
thinking about it, that might be the better approach, also for the
TIDBitmap-based variant.

If we do it this way, integrating the TID radix tree would actually be
straightforward.

--
David Geier

The even better implementation, that would keep the advantages of the
partitioning scheme while avoiding increased memory consumption and
rereading all bitmaps by all participants, is to keep the partitions in
shared memory from the staert and having each participant directly
insert the TIDs into the right partition, e.g.

BlockNumber blockno = ItemPointerGetBlockNumber(cur_tid);
uint32 p = murmurhash32(blockno / 256) % nparticipants;
tbm_add_tuple(tidbitmaps[p], cur_tid);

If we use enough partitions, say 8 per participant, then we might get
away with locking the entire tbm_add_tuple() operation, hoping that the
TIDs distribute more or less uniformly across all partitions. Now when
thinking about it, that might be the better approach, also for the
TIDBitmap-based variant.

I just remembered why I didn't go for this variant: TIDBitmap uses
simplehash.h which cannot easily live in shared memory. The hash map
array itself can by using a custom allocator (TIDBitmap does that
already) but the control struct that contains the size, etc. currently
cannot.

If we do it this way, integrating the TID radix tree would actually be
straightforward.

If the TID radix tree can live in shared memory we could first go with
my variant that repartitions and then later swap that part out with one
TID radix tree per partition stored in shared memory and updated by all
participants as described in my previous mail.

--
David Geier

On Tue, Oct 6, 2026 at 11:28 PM David Geier <geidav.pg@gmail.com> wrote:

Interesting. What's the unit of work for each worker? Can you describe
how and when repartitioning works? Let's say you have an "And" node
for two indexes.

Above the BIS, the unit of work is a disjoint partition of the
TIDBitmap, i.e. a non-overlapping set of HEAP blocks (and their TIDs in
non-lossy mode). This allows every operation above the BIS — Bitmap And,
Bitmap Or, and the Bitmap Heap Scan — to run locally in each worker
without any synchronization.

The unit of work inside the BIS is different: each worker scans a
portion of the index and builds a private TIDBitmap that may contain
TIDs of arbitrary HEAP blocks.

Repartitioning happens at the end of the BIS, after the index has been
read to completion by all participants. At that point, each participant
has a private TIDBitmap covering arbitrary HEAP pages that it shares
with the others through DSA. Then each participant create a new
TIDBitmap containing only the pages assigned to it, by scanning the
bitmaps of all other participants with the following condition to decide
if the block belongs to it or not:

I have not done a full review of the patch, but the approach seems
promising. The devil's in the details, of course.

Okay, so worst case N workers will use N times more memory. (not
counting transient use during repartitioning)

One mitigation could be to use hash_mem_multiplier to expand work_mem,
and divide that by the number of workers. (I'm not sure why we don't
do that already; seems like a natural use for it). This will need
testing.

Dividing by 256 keeps runs of 256 consecutive HEAP pages together in one

Does this need to be PAGES_PER_CHUNK?

participant, which is important for TIDBitmap efficiency. Because every
participant uses the same hash function and the same participant count,
the resulting partitions are identical across workers. The exchange uses
an unordered iterator, since order does not matter for this assignment.

For your Bitmap And example:

-> Bitmap Heap Scan
-> Bitmap And
-> Bitmap Index Scan(index_a)
-> Bitmap Index Scan(index_b)

Both leaf scans are parallel-aware and are run by every participant.

+ /*
+ * All leaves in a partial bitmap qual must be parallel scans so that
+ * each worker produces a disjoint partition of the same TIDBitmap.
+ */
+ if (!ipath->indexinfo->amcanparallel)
+   return NULL;

This disallows bitmap heap scans for non-btree indexes where they were
allowed before, doesn't it?

It seems it should be not too much additional work to allow one worker
to scan an index serially, and then publish it for repartitioning.

Worker i first executes the scan on index_a, repartitions the result
into partition A_i, then does the same for index_b to get partition B_i.
Since both scans use the same partitioning scheme, A_i and B_i cover
exactly the same set of HEAP pages. The Bitmap And node just intersects
A_i and B_i locally with tbm_intersect(); no locks, no shared iteration
state. The result is still partition i, which the Bitmap Heap Scan then
consumes.

So the only synchronization points are the two barriers inside each BIS
(one after sharing the local bitmaps, one after everyone has finished
reading the shared bitmaps). After that, the whole bitmap plan tree
above the BIS is embarrassingly parallel.

Sounds good in principle (BTW, for that to work the workers need to
keep the same my_id across index scans, but that's computed inside
BitmapIndexScanPartition, so that seems broken unless I'm missing
something)

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

It's not currently optimized for concurrency, so it would depend a lot
on the ordering of the input and could actually be worse especially
for e.g. a uuid index -- both cache misses and higher constant
overheads than a hash table. The advantage of the radix tree is that
1) iteration is automatically ordered so no sorting step, and 2) the

For that to pay off, the increased cost for inserting must be reasonably
low. Is that the case?

Actually, no, I just reminded myself that in shared memory, the node
pointers use DSA pointers, and dereferencing them requires a function
call.

page table entries can be variable length, probably using less net
memory, and allowing the max number of TIDs per page to be decoupled
from the max number of tuples,

Is this about wasting less memory for PagetableEntries that only contain
very few TIDs?

It's not about the number of TIDs, it's the largest offset for a given
page. Real life tables don't have a single int, they may have say
30-50 columns -- you don't need 291 bits available to store any TID
from such a page. With less memory, there's less chance of regression
with workers getting a fraction of the memory. My patch has to invent
shared disjoint iteration under a lock during the heap scan phase, but
with your architecture, it wouldn't need that.

and 3) easier to be smart about lossification.

Can you share what ideas exist at this point?

a) Since iteration is ordered, chunks are only created for a whole
range, not at random.
b) Once a whole range has been lossified, you can "close" that range
and any new page in that range will just go in the chunk.
c) You could decide a range is not worth lossifying

The even better implementation, that would keep the advantages of the
partitioning scheme while avoiding increased memory consumption and
rereading all bitmaps by all participants, is to keep the partitions in
shared memory from the staert and having each participant directly
insert the TIDs into the right partition, e.g.

BlockNumber blockno = ItemPointerGetBlockNumber(cur_tid);
uint32 p = murmurhash32(blockno / 256) % nparticipants;
tbm_add_tuple(tidbitmaps[p], cur_tid);

If we use enough partitions, say 8 per participant, then we might get
away with locking the entire tbm_add_tuple() operation, hoping that the
TIDs distribute more or less uniformly across all partitions. Now when
thinking about it, that might be the better approach, also for the
TIDBitmap-based variant.

Parallel index scan with shared partitioned hash table has been tried
before without success, I believe.

--
John Naylor
Amazon Web Services

John, thanks for taking a closer look at the patch! Your input is very
helpful.

Repartitioning happens at the end of the BIS, after the index has been
read to completion by all participants. At that point, each participant
has a private TIDBitmap covering arbitrary HEAP pages that it shares
with the others through DSA. Then each participant create a new
TIDBitmap containing only the pages assigned to it, by scanning the
bitmaps of all other participants with the following condition to decide
if the block belongs to it or not:

I have not done a full review of the patch, but the approach seems
promising. The devil's in the details, of course.

Okay, so worst case N workers will use N times more memory. (not
counting transient use during repartitioning)

Yes, but only temporarily and only in the BIS. The per-worker memory
consumption also stays the same. It's just that there are more workers
now that each can encounter the same TIDs / blocks. And once the
repartitioning step is complete, the old TIDBitmaps are freed and the
memory consumption is as before because now every participant holds a
TIDBitmap containing only 1/nth of the total set of TIDs / blocks.

One mitigation could be to use hash_mem_multiplier to expand work_mem,
and divide that by the number of workers.

I thought work_mem is per-node, per-worker. Given that the per-node,
per-worker memory consumption doesn't change, things should be fine?

(I'm not sure why we don't
do that already; seems like a natural use for it). This will need
testing.

Using hash_mem_multiplier in TIDBitmap makes sense, given that TIDBitmap
is hash-based. I'll add that.

Additionally, we could improve on the increased memory consumption by
having the participants feed the found TIDs into lock-free ring buffers,
one per partition. The participants would alternate between reading from
the index to feed the ring buffers and pulling data out from their
assigned ring buffer to store it in their local partition TIDBitmap.

That's for sure less work than making TIDBitmap parallel-safe for insert
(which includes lossification), should be on-par performance-wise and
avoids the increase in memory consumption.

Dividing by 256 keeps runs of 256 consecutive HEAP pages together in one

Does this need to be PAGES_PER_CHUNK?

Yes. I didn't use that because it's defined in tidbitmap.c. I'll move it
to tidbitmap.h and rename it to TBM_MAX_PAGES_PER_CHUNK, right next to
TBM_MAX_TUPLES_PER_PAGE.

participant, which is important for TIDBitmap efficiency. Because every
participant uses the same hash function and the same participant count,
the resulting partitions are identical across workers. The exchange uses
an unordered iterator, since order does not matter for this assignment.

For your Bitmap And example:

-> Bitmap Heap Scan
-> Bitmap And
-> Bitmap Index Scan(index_a)
-> Bitmap Index Scan(index_b)

Both leaf scans are parallel-aware and are run by every participant.

+ /*
+ * All leaves in a partial bitmap qual must be parallel scans so that
+ * each worker produces a disjoint partition of the same TIDBitmap.
+ */
+ if (!ipath->indexinfo->amcanparallel)
+   return NULL;

This disallows bitmap heap scans for non-btree indexes where they were
allowed before, doesn't it?

Will check and fix if needed. pg_regress tests are also not passing at
the moment. Will get them to work as well.

It seems it should be not too much additional work to allow one worker
to scan an index serially, and then publish it for repartitioning.

Indeed. Will do.

So the only synchronization points are the two barriers inside each BIS
(one after sharing the local bitmaps, one after everyone has finished
reading the shared bitmaps). After that, the whole bitmap plan tree
above the BIS is embarrassingly parallel.

Sounds good in principle (BTW, for that to work the workers need to
keep the same my_id across index scans, but that's computed inside
BitmapIndexScanPartition, so that seems broken unless I'm missing
something)

Good catch. I haven't tested (much) yet with Bitmap And/Or. I'll add
parallel bitmap queries to the pg_regress tests to cover these cases.

It's not currently optimized for concurrency, so it would depend a lot
on the ordering of the input and could actually be worse especially
for e.g. a uuid index -- both cache misses and higher constant
overheads than a hash table. The advantage of the radix tree is that
1) iteration is automatically ordered so no sorting step, and 2) the

For that to pay off, the increased cost for inserting must be reasonably
low. Is that the case?

Actually, no, I just reminded myself that in shared memory, the node
pointers use DSA pointers, and dereferencing them requires a function
call.

That makes sense: for what I understood, in parallel VACUUM the TidStore
is filled by a single leader but then read by multiple per-index workers.

Then using the partitioned architecture is actually making it easier to
replace TIDBitmap with the radix tree.

page table entries can be variable length, probably using less net
memory, and allowing the max number of TIDs per page to be decoupled
from the max number of tuples,

Is this about wasting less memory for PagetableEntries that only contain
very few TIDs?

It's not about the number of TIDs, it's the largest offset for a given
page. Real life tables don't have a single int, they may have say
30-50 columns -- you don't need 291 bits available to store any TID
from such a page. With less memory, there's less chance of regression
with workers getting a fraction of the memory.

Got it.

My patch has to invent
shared disjoint iteration under a lock during the heap scan phase, but
with your architecture, it wouldn't need that.

Makes sense.

and 3) easier to be smart about lossification.

Can you share what ideas exist at this point?

a) Since iteration is ordered, chunks are only created for a whole
range, not at random.
b) Once a whole range has been lossified, you can "close" that range
and any new page in that range will just go in the chunk.
c) You could decide a range is not worth lossifying

Good ideas. Regarding (c): TIDBitmap could also be smarter about that
today already. Currently, it eagerly lossifies any PagetableEntry which
wouldn't turn into a chunk (is not a multiple of PAGES_PER_CHUNK).
Instead we should lossify based on the number of TIDs. I'll code that up
and add it as a separate patch.

The even better implementation, that would keep the advantages of the
partitioning scheme while avoiding increased memory consumption and
rereading all bitmaps by all participants, is to keep the partitions in
shared memory from the staert and having each participant directly
insert the TIDs into the right partition, e.g.

BlockNumber blockno = ItemPointerGetBlockNumber(cur_tid);
uint32 p = murmurhash32(blockno / 256) % nparticipants;
tbm_add_tuple(tidbitmaps[p], cur_tid);

If we use enough partitions, say 8 per participant, then we might get
away with locking the entire tbm_add_tuple() operation, hoping that the
TIDs distribute more or less uniformly across all partitions. Now when
thinking about it, that might be the better approach, also for the
TIDBitmap-based variant.

As I shared in my other mail: this approach doesn't fly because it
requires simplehash.h to work in shared memory. I think the better
approach is what I described above: lock-free, per-partition ring
buffers. I'll give this a try.

Parallel index scan with shared partitioned hash table has been tried
before without success, I believe.

Do you have any pointers to mailing list discussions or similar?

I'll share an updated patch the next days.

--
David Geier

It seems it should be not too much additional work to allow one worker
to scan an index serially, and then publish it for repartitioning.

Indeed. Will do.

That made me think what the best way of integrating the repartitioning
step would be: for a parallel BIS doing it as part of the BIS plan node
is still somewhat reasonable but for serial BIS it becomes awkward
because the BIS plan node is serially scanning the index but then
repartitioning in parallel.

How about introducing a new plan node "Parallel Bitmap Partition" which
could look like this in the EXPLAIN output:

Serial scan (e.g. for GIN index, parallel consumption:

-> Bitmap Heap Scan
-> Bitmap And
-> Parallel Bitmap Partition
-> Bitmap Index Scan (executed by single process)
-> Parallel Bitmap Partition
-> Bitmap Index Scan (executed by single process)

Parallel scan (for B-tree), parallel consumption:

-> Bitmap Heap Scan
-> Bitmap And
-> Parallel Bitmap Partition
-> Parallel Bitmap Index Scan
-> Parallel Bitmap Partition
-> Parallel Bitmap Index Scan

BHS and Bitmap And/Or would never be parallel because also in the
parallel case they just process their local partition.

--
David Geier

On Thu, Oct 8, 2026 at 2:52 PM David Geier <geidav.pg@gmail.com> wrote:

Okay, so worst case N workers will use N times more memory. (not
counting transient use during repartitioning)

Yes, but only temporarily and only in the BIS. The per-worker memory
consumption also stays the same. It's just that there are more workers
now that each can encounter the same TIDs / blocks. And once the
repartitioning step is complete, the old TIDBitmaps are freed and the
memory consumption is as before because now every participant holds a
TIDBitmap containing only 1/nth of the total set of TIDs / blocks.

Okay.

One mitigation could be to use hash_mem_multiplier to expand work_mem,
and divide that by the number of workers.

I thought work_mem is per-node, per-worker. Given that the per-node,
per-worker memory consumption doesn't change, things should be fine?

Right, although I'm anticipating complaints about more memory used. I
believe parallel hash join started with per-worker private hash
tables, so it's probably defensible to follow that precedent. My idea
didn't really fit with how things normally work...

(I'm not sure why we don't
do that already; seems like a natural use for it). This will need
testing.

Using hash_mem_multiplier in TIDBitmap makes sense, given that TIDBitmap
is hash-based. I'll add that.

I still think it makes sense in principle, but if we're keeping
work_mem per node as is customary, having two mechanisms to possibly
increase memory usage is a step two far, especially in the same patch.

Additionally, we could improve on the increased memory consumption by
having the participants feed the found TIDs into lock-free ring buffers,
one per partition. The participants would alternate between reading from
the index to feed the ring buffers and pulling data out from their
assigned ring buffer to store it in their local partition TIDBitmap.

That's for sure less work than making TIDBitmap parallel-safe for insert
(which includes lossification), should be on-par performance-wise and
avoids the increase in memory consumption.

That sounds difficult to review.

For that to pay off, the increased cost for inserting must be reasonably
low. Is that the case?

Actually, no, I just reminded myself that in shared memory, the node
pointers use DSA pointers, and dereferencing them requires a function
call.

That makes sense: for what I understood, in parallel VACUUM the TidStore
is filled by a single leader but then read by multiple per-index workers.

Right, and two total workers only shows a modest (still noticeable)
improvement over one because of the increased overhead.

Parallel index scan with shared partitioned hash table has been tried
before without success, I believe.

Do you have any pointers to mailing list discussions or similar?

I found this one, not sure if it's the only one:

/messages/by-id/CAFiTN-t4NtRzafw94x+Ub_gUqQsv=u9nK=OaJmS612M_bZv6+Q@mail.gmail.com

--
John Naylor
Amazon Web Services

On Thu, Oct 8, 2026 at 8:51 PM David Geier <geidav.pg@gmail.com> wrote:

Right, although I'm anticipating complaints about more memory used. I
believe parallel hash join started with per-worker private hash
tables, so it's probably defensible to follow that precedent. My idea
didn't really fit with how things normally work...

In that case your idea of dividing work_mem by the number of
participants might be a good one.

Well, by "didn't really fit", I was admitting the opposite might be true, but...

Looking at the hash join memory calculation, it has to worry about
different things (batching, skew etc), but it does have for the shared
hash table:

/*
* Parallel Hash tries to use the combined hash_mem of all workers to
* avoid the need to batch. If that won't work, it falls back to hash_mem
* per worker and tries to process batches in parallel.
*/
...
newlimit = (double) hash_table_bytes * (double) (parallel_workers + 1);

...so we can just do the same, although there's the question of the
two copies: I think we may have to treat memory accounting differently
before and after repartitioning. The latter can afford to be more
pessimistic because of non-overlap. In the former stage, we have to
worry about a page entry showing up in all workers' table, and we
don't that to force our hands with lossification.

Additionally, we could improve on the increased memory consumption by
having the participants feed the found TIDs into lock-free ring buffers,
one per partition. The participants would alternate between reading from
the index to feed the ring buffers and pulling data out from their
assigned ring buffer to store it in their local partition TIDBitmap.

That's for sure less work than making TIDBitmap parallel-safe for insert
(which includes lossification), should be on-par performance-wise and
avoids the increase in memory consumption.

That sounds difficult to review.

A lock-free ring buffer is not that complicated and it would avoid the
increase in memory usage. At the same time, it would also disallow
splitting out the partitioning step into a separate plan node because
the "on-the-fly" partitioning must happen prior to creating the
TIDBitmap. I'll give this a try to see how involved it gets.

I was trying to imply that I have zero interest in reviewing that.

Before going further, I want to see what we're losing in the worst
case of static partitioning: All pages happen to go to one worker
after repartitioning. So the next patch would be:

1. Simple and generous memory accounting for a start
2. Fix any bugs that would make performence testing a waste of time
3. Test the above worst case

If that doesn't prove to be too bad compared to dynamic work
portioning (i.e. does parallel index scan make up for the loss of
parallel heap scan), we can worry about the other details.

--
John Naylor
Amazon Web Services

On Mon, Oct 5, 2026 at 3:53 PM David Geier <geidav.pg@gmail.com> wrote:

On this note, there has been a proposed (but as far as I know untested)
patch to speed up this sort in a much simpler way, in this thread

https://www.postgresql.org/message-id/
CA%2BhUKGKztHEWm676csTFjYzortziWmOcf8HDss2Zr0muZ2xfEg%40mail.gmail.com
<https://www.postgresql.org/message-id/
CA%2BhUKGKztHEWm676csTFjYzortziWmOcf8HDss2Zr0muZ2xfEg%40mail.gmail.com>

where you may find this patch

/messages/by-id/attachment/120560/0007-Specialize-
pagetable-sort-routines-in-tidbitmap.c.patch <https://
www.postgresql.org/message-id/attachment/120560/0007-Specialize-
pagetable-sort-routines-in-tidbitmap.c.patch>

Thanks for the pointer. I've applied that change to my patch set. See
other mail. It helped a lot further reducing the sort time in each
parallel worker.

If that's the case, let's get that piece in committable shape first.
That will make sure PG20 gets some improvement regardless of what
happens with your other proposal, and allows us to isolate the effect
of the proposed architectural change.

--
John Naylor
Amazon Web Services

On this note, there has been a proposed (but as far as I know untested)
patch to speed up this sort in a much simpler way, in this thread

https://www.postgresql.org/message-id/
CA%2BhUKGKztHEWm676csTFjYzortziWmOcf8HDss2Zr0muZ2xfEg%40mail.gmail.com
<https://www.postgresql.org/message-id/
CA%2BhUKGKztHEWm676csTFjYzortziWmOcf8HDss2Zr0muZ2xfEg%40mail.gmail.com>

where you may find this patch

/messages/by-id/attachment/120560/0007-Specialize-
pagetable-sort-routines-in-tidbitmap.c.patch <https://
www.postgresql.org/message-id/attachment/120560/0007-Specialize-
pagetable-sort-routines-in-tidbitmap.c.patch>

Thanks for the pointer. I've applied that change to my patch set. See
other mail. It helped a lot further reducing the sort time in each
parallel worker.

If that's the case, let's get that piece in committable shape first.
That will make sure PG20 gets some improvement regardless of what
happens with your other proposal, and allows us to isolate the effect
of the proposed architectural change.

Attached is the patch for using sort_template.h in TIDBitmap based on
master. No other parallel BIS changes.

Here is a small test to show the gains. The relative savings increase
the more workers are used because the sorting is done serially.

create table test(col0 bigint, col1 bigint, filler char(5000));
insert into test select a, (random()*10000000)::bigint, 'test' from
generate_series(1, 10000000) a;
create index on test(col1);
vacuum analyze test;
set cpu_operator_cost = 2;
set max_parallel_workers_per_gather = 8;
explain analyze select count(col0) from test where col1 < 1000000;

Results (best of 5, settings for stable results enabled):

master: ~886 ms
patched: ~811 ms

The query plans are attached. The startup time of the parallel BHS
reduces significantly, which is were the serial sort takes place.

--
David Geier

Looking at the hash join memory calculation, it has to worry about
different things (batching, skew etc), but it does have for the shared
hash table:

/*
* Parallel Hash tries to use the combined hash_mem of all workers to
* avoid the need to batch. If that won't work, it falls back to hash_mem
* per worker and tries to process batches in parallel.
*/
...
newlimit = (double) hash_table_bytes * (double) (parallel_workers + 1);

...so we can just do the same, although there's the question of the
two copies: I think we may have to treat memory accounting differently
before and after repartitioning. The latter can afford to be more
pessimistic because of non-overlap. In the former stage, we have to
worry about a page entry showing up in all workers' table, and we
don't that to force our hands with lossification.

I changed the code such that the maximum TIDBitmap size during the index
scan phase is work_mem - work_mem / (max_participants + 1), and the
maximum TIDBitmap size during the partitioning phase is work_mem /
(max_participants + 1). This sums up to work_mem and takes care of the
two copies in the following way:

The split maximizes the memory we give to the index scan phase while
ensuring there's enough memory left to represent the same TIDBitmap in
its partitioned form during the partitioning phase.

During the index scan phase, each participant may encounter all matching
TIDs from the index. During the partitioning phase, each participant
only keeps the TIDs that hash to its partition, which is roughly
1/max_participants of the total TIDs.

Since the phases are sequential, each participant's total memory usage
stays within work_mem across both phases.

That's for sure less work than making TIDBitmap parallel-safe for insert>>>> (which includes lossification), should be on-par

performance-wise and

avoids the increase in memory consumption.

That sounds difficult to review.

A lock-free ring buffer is not that complicated and it would avoid the
increase in memory usage. At the same time, it would also disallow
splitting out the partitioning step into a separate plan node because
the "on-the-fly" partitioning must happen prior to creating the
TIDBitmap. I'll give this a try to see how involved it gets.

I was trying to imply that I have zero interest in reviewing that.

Fine by me. We can start with the current approach and always improve on
it later.

Before going further, I want to see what we're losing in the worst
case of static partitioning: All pages happen to go to one worker
after repartitioning.

With the hash-based partitioning scheme, the probability of all pages
ending up in a single participant depends on how many distinct 256-block
ranges the data spans. For K distinct ranges and N participants the
probability is (1/N)^(K-1), assuming a hash function which uniformly
distributes inputs over the key space. murmur hash has that property.
Some examples with 4 workers:

- 2 distinct ranges: (1/4)^1 = 25% chance they collide
- 3 distinct ranges: (1/4)^2 = 6.25% chance
- 10 distinct ranges: (1/4)^9 ≈ 0.0004% chance
- 100 distinct ranges: (1/4)^99 ≈ 10^-60% chance (practically zero)

The worst case can only realistically occur when the data spans few
block ranges, which are typically fast to process anyway, even with
single-threaded execution. Beyond that, when the planner expects the
index to only return little rows, Index Scan is typically costed cheaper
than BIS, so the planner avoids the BIS to begin with.

So the next patch would be:

1. Simple and generous memory accounting for a start

Done.

2. Fix any bugs that would make performence testing a waste of time

Passes all tests, also on CI. I fixed one issue worth mentioning which
is mapping from participant number to a dense partition ID, e.g. when
the leader doesn't participate or workers are late so that they don't
participate and thereby leave a gap. Previously this resulted in
unassigned partitions.

There's a lengthy comment in the top of nodeBitmapIndexscan.c which
explains the partition ID computation, also across parallel BIS siblings.

3. Test the above worst case

If that doesn't prove to be too bad compared to dynamic work
portioning (i.e. does parallel index scan make up for the loss of
parallel heap scan), we can worry about the other details.

See explanations above for why the worst-case with lots of data cannot
realistically happen. To create a test for the worstcase, I would have
to find block ranges for which murmurhash32() % nparticipants returns
the same value and then use a WHERE clause which only returns rows in
these block ranges. And that for a large number of block ranges.

Or did you have something else in mind here?

I tried testing the worst-case with little data where a single block
range ends up in the same participant. But with so little data I didn't
manage to trick the planner into choosing a parallel plan.

Beyond that there are the following changes:

1) I added the FastMod() function which avoids the costly modulo (=
division) operation for every single TID during partitioning. For
details see comments in the code.
2) Removed the sort_template.h optimization. It's shared in a separate
patch, see [1]/messages/by-id/29f27b97-b3d7-476b-acae-832b3443b0c4@gmail.com.
3) Drafted a proper commit message.

Last but not least, I realized that parallel BIS needs parallel
instrumentation support for EXPLAIN ANALYZE. I'll work on that next and
provide an updated patch the next days.

--
David Geier

[1]: /messages/by-id/29f27b97-b3d7-476b-acae-832b3443b0c4@gmail.com
/messages/by-id/29f27b97-b3d7-476b-acae-832b3443b0c4@gmail.com

On Wed, Oct 14, 2026 at 5:27 AM David Geier <geidav.pg@gmail.com> wrote:

If that's the case, let's get that piece in committable shape first.
That will make sure PG20 gets some improvement regardless of what
happens with your other proposal, and allows us to isolate the effect
of the proposed architectural change.

Attached is the patch for using sort_template.h in TIDBitmap based on
master. No other parallel BIS changes.

+/* Needed for sort template to work with pointers to PagetableEntry */
+typedef PagetableEntry *PagetableEntryPtr;

This is a workaround; let's fix it properly, like this:

ST_POINTER_TYPE *a = (ST_POINTER_TYPE *) data;
ST_POINTER_TYPE *pa;
ST_POINTER_TYPE *pb;
...

I see that Thomas already encountered that problem in the 0001 patch
of that series:

/messages/by-id/attachment/120554/0001-Add-bsearch-and-unique-templates-to-sort_template.h.patch

+#define ST_COMPARE(a, b) pg_cmp_u32((*(a))->blockno, (*(b))->blockno)
...
+#define ST_COMPARE(a, b, base) pg_cmp_u32(base[*(a)].blockno,
base[*(b)].blockno)

There's a comment in common/int.h that says:

* NB: If the comparator function is inlined, some compilers may produce
* worse code with these helper functions than with code with the
* following form:
*
* if (a < b)
* return -1;
* if (a > b)
* return 1;
* return 0;

...and that's been true every time it's tried. It should be fine to
instead make the current comparators static inline and make both match
the above pattern. You might get a further speed-up.

--
John Naylor
Amazon Web Services

+/* Needed for sort template to work with pointers to PagetableEntry */
+typedef PagetableEntry *PagetableEntryPtr;

This is a workaround; let's fix it properly, like this:

ST_POINTER_TYPE *a = (ST_POINTER_TYPE *) data;
ST_POINTER_TYPE *pa;
ST_POINTER_TYPE *pb;
...

I see that Thomas already encountered that problem in the 0001 patch
of that series:

/messages/by-id/attachment/120554/0001-Add-bsearch-and-unique-templates-to-sort_template.h.patch

Makes sense. I should have done that right away. Done in patch v2-0001.

+#define ST_COMPARE(a, b) pg_cmp_u32((*(a))->blockno, (*(b))->blockno)
...
+#define ST_COMPARE(a, b, base) pg_cmp_u32(base[*(a)].blockno,
base[*(b)].blockno)

There's a comment in common/int.h that says:

* NB: If the comparator function is inlined, some compilers may produce
* worse code with these helper functions than with code with the
* following form:
*
* if (a < b)
* return -1;
* if (a > b)
* return 1;
* return 0;

...and that's been true every time it's tried. It should be fine to
instead make the current comparators static inline and make both match
the above pattern. You might get a further speed-up.

Oh, right. The qsort partitioning code does:

return DO_COMPARE(a, b) < 0 ?
(DO_COMPARE(b, c) < 0 ? b : (DO_COMPARE(a, c) < 0 ? c : a))
: (DO_COMPARE(b, c) > 0 ? b : (DO_COMPARE(a, c) < 0 ? a : c));

With the if-cascade the compiler can better optimize the expression in
DO_COMPARE().

I revived the original comparators with some minor modifications.
Runtimes of just the sorting now are:

master: 189 ms
patched v1: 136 ms
patched v2: 106 ms

Nice additional speedup!

--
David Geier

Last but not least, I realized that parallel BIS needs parallel
instrumentation support for EXPLAIN ANALYZE. I'll work on that next and
provide an updated patch the next days.

It turned out that this is not the case and parallel instrumentation for
BIS seems to be all there already. I got on the wrong track because e.g.
Parallel Index (Only) Scan and many other plan nodes estimate in two parts:

1. memory needed for parallel-aware execution state and
2. memory needed for instrumentation when under a Gather node. This is
also needed when the plan is ran by a parallel worker but the node
itself not parallal-aware.

For example IndexOnlyScanState:

if (planstate->plan->parallel_aware)
ExecIndexOnlyScanEstimate((IndexOnlyScanState *)ps, e->pcxt);

/* even when not parallel-aware, for EXPLAIN ANALYZE */
ExecIndexOnlyScanInstrumentEstimate((IndexOnlyScanState *)ps, e->pcxt);

While for parallel BIS/BHS scan we do:

ExecBitmapHeapInstrumentEstimate((BitmapHeapScanState *)ps, e->pcxt);
and
ExecBitmapIndexScanEstimate((BitmapIndexScanState *)ps, e->pcxt);

It turned out that the BIS / BHS functions do both inside a single
function, while other nodes have two functions for it. I think it would
be good to make this consistent across all nodes. This would include
renaming the functions that don't allocate any execution state but only
instrumentation state, e.g. rename

ExecAggEstimate() -> ExecAggInstrumentEstimate().

Obviously, as a separate patch.

--
David Geier

Hi David,

Great work, I like this idea a lot.

A few small things in 0002

1. With ST_COMPARE_RUNTIME_POINTER the typedef
uses const ST_ELEMENT_TYPE *, which for Item * becomes const Item **,
so a comparator taking Item *const * warns. ST_ELEMENT_TYPE const *
fixes it.

2. tbm_comparator() lost its const. It can take
PagetableEntry *const *.

3. The common/int.h include in tidbitmap.c is now unused.

4. tbm_shared_comparator() is missing inline in its definition.

Thanks,
Shihao