Re: Parallel bitmap heap scan - Mailing list pgsql-hackers

There is major chance in tidbitmap.c file after efficient hash table
commit [1] and my patch need to be rebased.

Only parallel-bitmap-heap-scan need to be rebased, all other patch can
be applied on head as is.
Rebased version (v2) of parallel-bitmap-heap-scan is attached.

[1] commit-http://git.postgresql.org/pg/commitdiff/75ae538bc3168bf44475240d4e0487ee2f3bb376


On Fri, Oct 7, 2016 at 11:46 AM, Dilip Kumar <dilipbalaut@gmail.com> wrote:
> Hi Hackers,
>
> I would like to propose parallel bitmap heap scan feature. After
> running TPCH benchmark, It was observed that many of TPCH queries are
> using bitmap scan (@TPCH_plan.tar.gz attached below). Keeping this
> point in mind we thought that many query will get benefited with
> parallel bitmap scan.
>
> Robert has also pointed out the same thing in his blog related to parallel query
> http://rhaas.blogspot.in/2016/04/postgresql-96-with-parallel-query-vs.html
>
> Currently Bitmap heap plan look like this :
> ------------------------------------------------------
> Bitmap Heap Scan
> -> Bitmap Index Scan
>
> After this patch :
> ---------------------
> Parallel Bitmap Heap Scan
> -> Bitmap Index Scan
>
> As part of this work I have implemented parallel processing in
> BitmapHeapScan node. BitmapIndexScan is still non parallel.
>
> Brief design idea:
> -----------------------
> #1. Shared TIDBitmap creation and initialization
>   First worker to see the state as parallel bitmap info as PBM_INITIAL
> become leader and set the state to PBM_INPROGRESS All other   workers
> see the state as PBM_INPROGRESS will wait for leader to complete the
> TIDBitmap.
>
> #2 At this level TIDBitmap is ready and all workers are awake.
>
> #3. Bitmap processing (Iterate and process the pages).
> In this phase each worker will iterate over page and chunk array and
> select heap pages one by one. If prefetch is enable then there will be
> two iterator. Since multiple worker are iterating over same page and
> chunk array we need to have a shared iterator, so we grab a spin lock
> and iterate within a lock, so that each worker get and different page
> to process.
>
> Note: For more detail on design, please refer comment of
> BitmapHeapNext API in "parallel-bitmap-heap-scan-v1.patch" file.
>
> Attached patch details:
> ------------------------------
> 1. parallel-bitmap-heap-scan-v1.patch: This is the main patch to make
> bitmap heap scan node parallel aware.
>
> 2. dht-return-dsa-v1.patch:  This patch will provide new API, where we
> can scan full DHT[1], and get the dsa_pointers (a relative pointer).
> The dsa_pointer values can be shared with other processes. We need
> this because, after TIDBitmap is created, only one worker will process
> whole TIDBitmap and convert it to a page and chunk array. So we need
> to store the generic pointer, so that later on each worker can convert
> those to their local pointer before start processing.
>
> My patch depends on following patches.
> ------------------------------------------------------
> 1. conditional_variable
> https://www.postgresql.org/message-id/CAEepm%3D0zshYwB6wDeJCkrRJeoBM%3DjPYBe%2B-k_VtKRU_8zMLEfA%40mail.gmail.com
>
> 2. dsa_area
> https://www.postgresql.org/message-id/CAEepm%3D024p-MeAsDmG%3DR3%2BtR4EGhuGJs_%2BrjFKF0eRoSTmMJnA%40mail.gmail.com
>
> 3. Creating a DSA area to provide work space for parallel execution
> https://www.postgresql.org/message-id/CAEepm%3D0HmRefi1%2BxDJ99Gj5APHr8Qr05KZtAxrMj8b%2Bay3o6sA%40mail.gmail.com
>
> 4. Hash table in dynamic shared memory (DHT) [1]
> https://www.postgresql.org/message-id/CAEepm%3D0VrMt3s_REDhQv6z1pHL7FETOD7Rt9V2MQ3r-2ss2ccA%40mail.gmail.com
>
> Order in which patches should be applied:
> --------------------------------------------------------
> 1. conditional_variable
> 2. dsa_area
> 3. Creating a DSA area to provide work space for parallel execution
> 4. Hash table in dynamic shared memory.
> 5. dht-return-dsa-v1.patch
> 6. parallel-bitmap-heap-scan-v1.patch
>
> Performance Results:
> -----------------------------
> Summary :
> 1. After this patch, I observed currently 4 queries are getting
> significant improvement (Q4, Q6, Q14, Q15).
>    - Q4, is converting from parallel seqscan to parallel bitmap heap scan.
>    - Other queries are converted from a regular bitmap heap scan to a
> parallel bitmap heap scan.
> 2. Benefit is more visible at lower workers (upto 4), after that some
> of the queries are selecting ParallelSeqScan over ParallelBitmapScan.
> And, I think this is expected, because so far we have only made
> BitmapHeap node as parallel whereas ParallelSeqScan is completely
> parallel so at higher worker count ParallelSeqScan is better choice.
> 3. Detailed result is attached  @TPCH_PBMS.pdf
> 4. Explain analyse output is attached @TPCH_plan.tar.gz  (for all
> changed queries at worker 2)
>
> TPCH query plan changed  example (TPCH Q6):
> ----------------------------------------------------------------
> On Head:
> -------------
>
>                                   QUERY PLAN
>
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>  Limit  (cost=1558475.95..1558475.96 rows=1 width=32) (actual
> time=40921.437..40921.438 rows=1 loops=1)
>    ->  Aggregate  (cost=1558475.95..1558475.96 rows=1 width=32)
> (actual time=40921.435..40921.435 rows=1 loops=1)
>          ->  Bitmap Heap Scan on lineitem  (cost=291783.32..1552956.39
> rows=1103911 width=12) (actual time=7032.075..38997.369 rows=1140434
> loops=1)
>                Recheck Cond: ((l_shipdate >= '1994-01-01'::date) AND
> (l_shipdate < '1995-01-01 00:00:00'::timestamp without time zone) AND
> (l_discount >= 0.01) AND (l_discount <= 0.03) AND (l_quantity <
> '24'::numeric))
>                Rows Removed by Index Recheck: 25284232
>                Heap Blocks: exact=134904 lossy=530579
>                ->  Bitmap Index Scan on idx_lineitem_shipdate
> (cost=0.00..291507.35 rows=1103911 width=0) (actual
> time=6951.408..6951.408 rows=1140434 loops=1)
>                      Index Cond: ((l_shipdate >= '1994-01-01'::date)
> AND (l_shipdate < '1995-01-01 00:00:00'::timestamp without time zone)
> AND (l_discount >= 0.01) AND (l_discount <= 0.03) AND (l_quantity <
> '24'::numeric))
>  Planning time: 1.126 ms
>  Execution time: 40922.569 ms
> (10 rows)
>
> After Patch:
> ----------------
>
>                                          QUERY PLAN
>
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>  Limit  (cost=1541767.60..1541767.61 rows=1 width=32) (actual
> time=21895.008..21895.009 rows=1 loops=1)
>    ->  Finalize Aggregate  (cost=1541767.60..1541767.61 rows=1
> width=32) (actual time=21895.006..21895.006 rows=1 loops=1)
>          ->  Gather  (cost=1541767.38..1541767.59 rows=2 width=32)
> (actual time=21894.341..21894.970 rows=3 loops=1)
>                Workers Planned: 2
>                Workers Launched: 2
>                ->  Partial Aggregate  (cost=1540767.38..1540767.39
> rows=1 width=32) (actual time=21890.990..21890.990 rows=1 loops=3)
>                      ->  Parallel Bitmap Heap Scan on lineitem
> (cost=291783.32..1538467.56 rows=459963 width=12) (actual
> time=8517.126..21215.469 rows=380145 loops=3)
>                            Recheck Cond: ((l_shipdate >=
> '1994-01-01'::date) AND (l_shipdate < '1995-01-01 00:00:00'::timestamp
> without time zone) AND (l_discount >= 0.01) AND (l_discount <= 0.03)
> AND (l_quantity < '24'::numeric))
>                            Rows Removed by Index Recheck: 8427921
>                            Heap Blocks: exact=47761 lossy=187096
>                            ->  Bitmap Index Scan on
> idx_lineitem_shipdate  (cost=0.00..291507.35 rows=1103911 width=0)
> (actual time=8307.291..8307.291 rows=1140434 loops=1)
>                                  Index Cond: ((l_shipdate >=
> '1994-01-01'::date) AND (l_shipdate < '1995-01-01 00:00:00'::timestamp
> without time zone) AND (l_discount >= 0.01) AND (l_discount <= 0.03)
> AND (l_quantity < '24'::numeric))
>  Planning time: 1.173 ms
>  Execution time: 21915.931 ms
> (14 rows)
>
>
> * Thanks to Robert Haas and Amit Kapila, for helping in design review
> (off list) and many valuable inputs.
> * Thanks to Thomas Munro for DSA and DHT work on which my patch is based on.
> * Thanks to Rafia sabih for helping with performance test.
>
> --
> Regards,
> Dilip Kumar
> EnterpriseDB: http://www.enterprisedb.com



--
Regards,
Dilip Kumar
EnterpriseDB: http://www.enterprisedb.com