Re: Improving scalability of Parallel Bitmap Heap/Index Scan

On Mon, Oct 5, 2026 at 3:52 PM David Geier <geidav(dot)pg(at)gmail(dot)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