Improving scalability of Parallel Bitmap Heap/Index Scan

Hi hackers,

While debugging some slow queries containing Bitmap Heap/Index Scans (in
short BHS / BIS), we observed a few issues regarding scalability:

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

The EXPLAIN ANALYZE output below shows (1) to (3) happening in action for
different numbers of workers. I had to obfuscate the query slightly. The
difference between the startup time of the BHS and the BIS is the time it
takes to sort the TID list. The self time of the BHS is just the time spent
on processing the shared TID list and processing the pages. That part runs
in parallel but does not scale.

Workers | Total runtime | Startup time BIS | Startup time BHS | Self time
BHS (excl. sorting)
-------------------------------------------|------------------|------------------------------
2 | 15322 ms | 3107 ms | 5912 ms | 9269 ms
4 | 13277 ms | 3094 ms | 5869 ms | 7260 ms
8 | 14628 ms | 3106 ms | 5882 ms | 8598 ms

None of this is really new and some of it is even documented. So, what I am
more wondering about is why things are the way they are and how hard it
would be to change them. I am especially curious about:

- What stops us from extending the BIS to run in parallel? Parallel
Bitmap Index Scans are also supported.
- What about reducing the sort time by, e.g.
- dividing TIDs across workers, ending up with N parallely sorted
streams,
- cooperatively sorting the TIDs with multiple workers using barriers
for synchronization,
- optimizing the PagetableEntry data structure for size and using a
faster sorting algorithm like e.g. radix sort
- a combination of the first three options
- With separate TID lists per worker process the iteration problem would
be solved. Otherwise, we could
- optimize the iteration code and thereby minimize the duration of
the critical section,
- have worker processes acquire chunks of TIDs / page bits to reduce
locking.

Is there interest in patches improving on the above mentioned shortcomings?
If so, which options do you deem best?

--
David Geier
(ServiceNow)

-- 2 workers

Finalize Aggregate (actual time=15228.937..15321.356 rows=1 loops=1)
Output: count(*)
-> Gather (actual time=15187.942..15321.345 rows=2 loops=1)
Output: (PARTIAL count(*))
Workers Planned: 2
Workers Launched: 2
-> Partial Aggregate (actual time=15181.486..15181.488 rows=1
loops=2)
Output: PARTIAL count(*)
Worker 0: actual time=15181.364..15181.366 rows=1 loops=1
Worker 1: actual time=15181.608..15181.610 rows=1 loops=1
-> Parallel Bitmap Heap Scan on foo (actual
time=5912.731..15166.992 rows=269713 loops=2)
Filter: ...
Rows Removed by Filter: 4020149
Worker 0: actual time=5912.498..15166.936 rows=269305
loops=1
Worker 1: actual time=5912.963..15167.048 rows=270121
loops=1
-> Bitmap Index Scan on foo_idx (actual
time=3107.947..3107.948 rows=8579724 loops=1)
Index Cond: -
Worker 1: actual time=3107.947..3107.948
rows=8579724 loops=1
Planning Time: 0.167 ms
Execution Time: 15322.081 ms

-- 4 workers

Finalize Aggregate (actual time=13175.765..13276.415 rows=1 loops=1)
Output: count(*)
-> Gather (actual time=13137.981..13276.403 rows=4 loops=1)
Output: (PARTIAL count(*))
Workers Planned: 4
Workers Launched: 4
-> Partial Aggregate (actual time=13130.344..13130.346 rows=1
loops=4)
Output: PARTIAL count(*)
Worker 0: actual time=13129.363..13129.365 rows=1 loops=1
Worker 1: actual time=13130.085..13130.087 rows=1 loops=1
Worker 2: actual time=13130.634..13130.635 rows=1 loops=1
Worker 3: actual time=13131.295..13131.298 rows=1 loops=1
-> Parallel Bitmap Heap Scan on foo (actual
time=5870.026..13120.579 rows=134856 loops=4)
Filter: ...
Rows Removed by Filter: 2010074
Worker 0: actual time=5869.033..13120.453 rows=128270
loops=1
Worker 1: actual time=5869.698..13118.811 rows=135333
loops=1
Worker 2: actual time=5870.465..13121.189 rows=137695
loops=1
Worker 3: actual time=5870.907..13121.864 rows=138128
loops=1
-> Bitmap Index Scan on foo_idx (actual
time=3094.585..3094.586 rows=8579724 loops=1)
Index Cond: -
Worker 3: actual time=3094.585..3094.586
rows=8579724 loops=1
Planning Time: 0.146 ms
Execution Time: 13277.315 ms

-- 8 workers

Finalize Aggregate (actual time=14533.688..14627.962 rows=1 loops=1)
Output: count(*)
-> Gather (actual time=14492.463..14627.950 rows=8 loops=1)
Output: (PARTIAL count(*))
Workers Planned: 8
Workers Launched: 8
-> Partial Aggregate (actual time=14483.059..14483.061 rows=1
loops=8)
Output: PARTIAL count(*)
Worker 0: actual time=14480.058..14480.061 rows=1 loops=1
Worker 1: actual time=14480.948..14480.950 rows=1 loops=1
Worker 2: actual time=14481.668..14481.670 rows=1 loops=1
Worker 3: actual time=14482.829..14482.832 rows=1 loops=1
Worker 4: actual time=14483.695..14483.697 rows=1 loops=1
Worker 5: actual time=14484.290..14484.293 rows=1 loops=1
Worker 6: actual time=14485.166..14485.168 rows=1 loops=1
Worker 7: actual time=14485.819..14485.821 rows=1 loops=1
-> Parallel Bitmap Heap Scan on foo (actual
time=5886.191..14477.239 rows=67428 loops=8)
Filter: ...
Rows Removed by Filter: 1005037
Worker 0: actual time=5882.909..14474.627 rows=60325
loops=1
Worker 1: actual time=5883.788..14474.945 rows=69459
loops=1
Worker 2: actual time=5884.475..14475.735 rows=69686
loops=1
Worker 3: actual time=5886.149..14477.162 rows=64680
loops=1
Worker 4: actual time=5886.987..14477.653 rows=71034
loops=1
Worker 5: actual time=5887.347..14478.667 rows=65836
loops=1
Worker 6: actual time=5888.978..14479.239 rows=67755
loops=1
Worker 7: actual time=5888.896..14479.886 rows=70651
loops=1
-> Bitmap Index Scan on foo_idx (actual
time=3106.840..3106.840 rows=8579724 loops=1)
Index Cond: -
Worker 7: actual time=3106.840..3106.840
rows=8579724 loops=1
Planning Time: 0.150 ms
Execution Time: 14628.648 ms