Re: Improving scalability of Parallel Bitmap Heap/Index Scan

Attached is v2 of the patch with the following changes:

1. Moved PAGES_PER_CHUNK to tidbitmap.h and renamed to
TBM_MAX_PAGES_PER_CHUNK.

2. BIS of non-B-tree indexes under a parallel BHS works again. See (3)
for details.

3. Built support for scanning an index serially and then sharing the
bitmap partitions with the other participants. That's also needed to not
regress compared to master. In master a parallel BHS can sit on top of a
serial BIS (e.g. for a GIN index). This no longer works with my patch
because the shared TIDBitmap iteration logic got removed. Everything
above the BIS is serial. I made this work by always emitting a parallel
BIS under a parallel BHS but the parallel BIS checks if the underlying
index AM can be scanned in parallel and if not scans it serially in one
worker to then share the TIDBitmap with all other participants.

4. Fixed TID sorting regressions in tidbitmap.c that I introduced when
switching to sort_template.h.

5. Fixed participant ID assignment so that it's stable across parallel
BIS belonging to the same Gather node.

6. Added tests to bitmapops.sql.

All pg_regress tests pass.

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

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

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

Ack!

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

>>> 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:
>
> https://www.postgresql.org/message-id/CAFiTN-t4NtRzafw94x%2BUb_gUqQsv%3Du9nK%3DOaJmS612M_bZv6%2BQ%40mail.gmail.com
Thanks.

--
David Geier