Re: Improving scalability of Parallel Bitmap Heap/Index Scan

On Thu, Oct 8, 2026 at 8:51 PM David Geier <geidav(dot)pg(at)gmail(dot)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