On Mon, Oct 5, 2026 at 3:52 PM David Geier <[email protected]> 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
