Re: Parallel bitmap heap scan

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(at)gmail(dot)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