Proposal : Parallel Merge Join

On Sat, Dec 10, 2016 at 4:59 AM, Dilip Kumar <dilipbalaut@gmail.com> wrote:

3. 20_patch.out : Explain analyze output with patch (median of 3 runs)

I noticed that the partially parallelized Merge Join EXPLAIN ANALYZE
that you attach has a big misestimation:

-> Merge Join (cost=3405052.45..3676948.66 rows=320 width=32)
(actual time=21165.849..37814.551 rows=1357812 loops=4)

Is this the best test case to show off the patch? This node is the
immediate outer child of a Nested Loop Semi Join, and so I'm concerned
that we measuring the wrong thing.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Sun, Dec 11, 2016 at 8:14 AM, Peter Geoghegan <pg@heroku.com> wrote:

I noticed that the partially parallelized Merge Join EXPLAIN ANALYZE
that you attach has a big misestimation:

-> Merge Join (cost=3405052.45..3676948.66 rows=320 width=32)
(actual time=21165.849..37814.551 rows=1357812 loops=4)

Is this the best test case to show off the patch? This node is the
immediate outer child of a Nested Loop Semi Join, and so I'm concerned
that we measuring the wrong thing.

Actually main purpose of showing this example is that, by enabling
parallelism with merge join we can enable the parallelism in complete
tree, and we can get completely different kind of plan which is way
cheaper.

But I completely agree with your point that, in this particular
example estimation is wrong and may be with correct estimation plan
can be entirely different. I am planning to test this with more self
generated test case where first we can guarantee that our estimation
is almost correct and see the impact of the patch.

Here is one such example, this time I tested my patch with Amit's
parallel index scan patch [1]/messages/by-id/CAA4eK1KA4LwTYXZG=k3J2bA+ZOEYnz2gkyWBKgY=_q0xJRBMDw@mail.gmail.com, just to enable more scope for parallel
merge join.

All configurations and machines are same what I mentioned up thread.

create table test1(a, b) as select generate_series(1,
10000000),generate_series(1, 10000000);
create table test2(a, b) as select generate_series(1,
10000000),generate_series(1, 10000000);
create index idx1 on test1(a);
create index idx2 on test2(a);

Query:
explain analyze select * from test1, test2 where test1.a=test2.a and
test1.b = test2.b and test1.a+test2.b < 3 and test1.a < 3000000 and
test2.a < 3000000;

On Head:

Merge Join (cost=6.92..228073.90 rows=1 width=16) (actual
time=0.033..3123.400 rows=1 loops=1)
Merge Cond: (test1.a = test2.a)
Join Filter: ((test1.b = test2.b) AND ((test1.a + test2.b) < 3))
Rows Removed by Join Filter: 2999998
-> Index Scan using idx1 on test1 (cost=0.43..98626.90
rows=2998198 width=8) (actual time=0.013..746.382 rows=2999999
loops=1)
Index Cond: (a < 3000000)
-> Index Scan using idx2 on test2 (cost=0.43..98708.62
rows=3000639 width=8) (actual time=0.012..751.558 rows=2999999
loops=1)
Index Cond: (a < 3000000)
Planning time: 0.604 ms
Execution time: 3123.442 ms

With Patch:

Gather (cost=1005.46..193001.64 rows=1 width=16) (actual
time=0.244..1883.087 rows=1 loops=1)
Workers Planned: 3
Workers Launched: 3
-> Merge Join (cost=5.46..192000.64 rows=1 width=16) (actual
time=1409.686..1880.394 rows=0 loops=4)
Merge Cond: (test2.a = test1.a)
Join Filter: ((test1.b = test2.b) AND ((test1.a + test2.b) < 3))
Rows Removed by Join Filter: 750000
-> Parallel Index Scan using idx2 on test2
(cost=0.43..78381.71 rows=967948 width=8) (actual time=0.023..221.172
rows=750000 loops=4)
Index Cond: (a < 3000000)
-> Index Scan using idx1 on test1 (cost=0.43..98626.90
rows=2998198 width=8) (actual time=0.024..893.081 rows=2999254
loops=4)
Index Cond: (a < 3000000)
Planning time: 0.281 ms
Execution time: 1888.750 ms

This example shows direct improvement with merge join, but IMHO the
main value of this patch is that we can parallelize multi level join
query, where parallelism is not used becuase of merge join at some
level.

[1]: /messages/by-id/CAA4eK1KA4LwTYXZG=k3J2bA+ZOEYnz2gkyWBKgY=_q0xJRBMDw@mail.gmail.com

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

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Sat, Dec 10, 2016 at 7:59 AM, Dilip Kumar <dilipbalaut@gmail.com> wrote:

I would like to propose a patch for parallelizing merge join path.
This idea is derived by analyzing TPCH results.

I have done this analysis along with my colleagues Rafia sabih and Amit kaplia.

Currently we already have infrastructure for executing parallel join,
so we don't need any change at executor level. Only in path
generation, we need to add partial paths for merge join, like we do
for nest loop and hash join.

Hmm, so it seems my initial guess that we didn't need to bother
generating such paths was wrong. Oops.

This patch is hard to read because it is reorganizing a bunch of code
as well as adding new functionality. Perhaps you could separate it
into two patches, one with the refactoring and then the other with the
new functionality. Actually, though, I don't understand why you need
so much rearrangement....

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Dec 13, 2016 at 12:11 AM, Robert Haas <robertmhaas@gmail.com> wrote:

Hmm, so it seems my initial guess that we didn't need to bother
generating such paths was wrong. Oops.

This patch is hard to read because it is reorganizing a bunch of code
as well as adding new functionality. Perhaps you could separate it
into two patches, one with the refactoring and then the other with the
new functionality.

Okay, I can do that.

Actually, though, I don't understand why you need
so much rearrangement....

Actually match_unsorted_outer is quite complex function and
considering merge join path for many cases, And In my opinion those
all paths should be considered for partial outer as well.

So one option was to duplicate that part of code. But I chose to move
all that code from match_unsorted_outer (which is related to
generating various merge join path) to new function called
generate_mergejoin_path. And, use it for normal outer path as well as
for partial outer path.

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

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Dec 13, 2016 at 6:42 AM, Dilip Kumar <dilipbalaut@gmail.com> wrote:

This patch is hard to read because it is reorganizing a bunch of code
as well as adding new functionality. Perhaps you could separate it
into two patches, one with the refactoring and then the other with the
new functionality.

Okay, I can do that.

I have created two patches as per the suggestion.

1. mergejoin_refactoring_v2.patch --> Move functionality of
considering various merge join path into new function.
2. parallel_mergejoin_v2.patch -> This adds the functionality of
supporting partial mergejoin paths. This will apply on top of
mergejoin_refactoring_v2.patch.

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

On Tue, Dec 13, 2016 at 8:34 PM, Dilip Kumar <dilipbalaut@gmail.com> wrote:

I have created two patches as per the suggestion.

1. mergejoin_refactoring_v2.patch --> Move functionality of
considering various merge join path into new function.
2. parallel_mergejoin_v2.patch -> This adds the functionality of
supporting partial mergejoin paths. This will apply on top of
mergejoin_refactoring_v2.patch.

We have done further analysis of the performance with TPCH benchmark
at higher scale factor. I have tested parallel merge join patch along
with parallel index scan[1]/messages/by-id/CAA4eK1KA4LwTYXZG=k3J2bA+ZOEYnz2gkyWBKgY=_q0xJRBMDw@mail.gmail.com

I have observed that with query3, we are getting linear scalability
('explain analyze' results are attached).

Test Setup:
---------------
TPCH 300 scale factor
work_mem = 1GB
shared_buffer = 1GB
random_page_cost=seq_page_cost=0.1
max_parallel_workers_per_gather=4 (warm cache ensured)
The median of 3 runs (reading are quite stable).

On Head: 2702568.099 ms
With Patch: 547363.164 ms

Other Experiments:

* I have also verified reading on the head, without modifying
random_page_cost=seq_page_cost, but there is no change in plan or
execution time.

* I have tried to increase the max_parallel_workers_per_gather to 8
but I did not observe further scaling.

[1]: /messages/by-id/CAA4eK1KA4LwTYXZG=k3J2bA+ZOEYnz2gkyWBKgY=_q0xJRBMDw@mail.gmail.com

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

On Tue, Dec 13, 2016 at 10:04 AM, Dilip Kumar <dilipbalaut@gmail.com> wrote:

On Tue, Dec 13, 2016 at 6:42 AM, Dilip Kumar <dilipbalaut@gmail.com> wrote:

This patch is hard to read because it is reorganizing a bunch of code
as well as adding new functionality. Perhaps you could separate it
into two patches, one with the refactoring and then the other with the
new functionality.

Okay, I can do that.

I have created two patches as per the suggestion.

1. mergejoin_refactoring_v2.patch --> Move functionality of
considering various merge join path into new function.
2. parallel_mergejoin_v2.patch -> This adds the functionality of
supporting partial mergejoin paths. This will apply on top of
mergejoin_refactoring_v2.patch.

Committed the refactoring patch with some mild cosmetic adjustments.

As to the second patch:

+        if (jointype == JOIN_UNIQUE_INNER)
+            jointype = JOIN_INNER;

Isn't this dead code? save_jointype might that value, but jointype won't.

Apart from that and some cosmetic issues it looks basically OK to me
on a first read-through.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Dec 21, 2016 at 8:39 PM, Robert Haas <robertmhaas@gmail.com> wrote:

Committed the refactoring patch with some mild cosmetic adjustments.

Thanks..

As to the second patch:

+        if (jointype == JOIN_UNIQUE_INNER)
+            jointype = JOIN_INNER;

Isn't this dead code? save_jointype might that value, but jointype won't.

Yes, it is.

I have fixed this, and also observed that comment for
try_partial_mergejoin_path header was having some problem, fixed that
too.

Apart from that and some cosmetic issues it looks basically OK to me
on a first read-through.

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

Hi,

On 12/21/2016 04:53 PM, Dilip Kumar wrote:

On Wed, Dec 21, 2016 at 8:39 PM, Robert Haas <robertmhaas@gmail.com> wrote:

Committed the refactoring patch with some mild cosmetic adjustments.

Thanks..

As to the second patch:

+        if (jointype == JOIN_UNIQUE_INNER)
+            jointype = JOIN_INNER;

Isn't this dead code? save_jointype might that value, but jointype won't.

Yes, it is.

I have fixed this, and also observed that comment for
try_partial_mergejoin_path header was having some problem, fixed that
too.

FWIW, I've done quite a bit of testing on this patch, and also on the
other patches adding parallel index scans and bitmap heap scan. I've
been running TPC-H and TPC-DS on 16GB data sets with each patch, looking
for regressions or crashes.

I haven't found any of that so far, which is good of course. It however
seems the plan changes only for very few queries in those benchmarks
with any of the patches, even after tweaking the costs to make parallel
plans more likely.

I'm going to try with larger scales and also --enable-cassert and post
the results during CF 2017-1.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Thu, Dec 29, 2016 at 3:15 AM, Tomas Vondra
<tomas.vondra@2ndquadrant.com> wrote:

FWIW, I've done quite a bit of testing on this patch, and also on the other
patches adding parallel index scans and bitmap heap scan. I've been running
TPC-H and TPC-DS on 16GB data sets with each patch, looking for regressions
or crashes.

Thanks for looking into this.

I haven't found any of that so far, which is good of course. It however
seems the plan changes only for very few queries in those benchmarks with
any of the patches, even after tweaking the costs to make parallel plans
more likely.

You can also try with reducing random_page_cost (that will help
parallel merge join with index scan), in case your data fits in memory
and you are ensuring warm cache environment.

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

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Dec 21, 2016 at 9:23 PM, Dilip Kumar <dilipbalaut@gmail.com> wrote:

On Wed, Dec 21, 2016 at 8:39 PM, Robert Haas <robertmhaas@gmail.com> wrote:

Committed the refactoring patch with some mild cosmetic adjustments.

Thanks..

As to the second patch:

+        if (jointype == JOIN_UNIQUE_INNER)
+            jointype = JOIN_INNER;

Isn't this dead code? save_jointype might that value, but jointype won't.

Yes, it is.

I have fixed this, and also observed that comment for
try_partial_mergejoin_path header was having some problem, fixed that
too.

Review comments:
1.
+ bool is_partial);
+

Seems additional new line is not required.

2.
+ * try_partial_mergejoin_path
+ *  Consider a partial merge join path; if it appears useful,
push it into
+ *  the joinrel's pathlist via add_path().
+ */

I think in above comment, you should say ".. joinrel's
partial_pathlist via add_partial_path()"

3.
+ /*
+ * See comments in try_partial_nestloop_path().
+ */
+ Assert(bms_is_empty
(joinrel->lateral_relids));
+ if (inner_path->param_info != NULL)
+ {
+ Relids
inner_paramrels = inner_path->param_info->ppi_req_outer;
+
+ if (!bms_is_subset
(inner_paramrels, outer_path->parent->relids))
+ return;
+ }

This same code exists in try_partial_nestloop_path() and
try_partial_hashjoin_path() with minor difference of code in
try_partial_hashjoin_path(). Can't we write a separate inline
function for this code and call from all the three places.

4.
+ /*
+ * See comments in try_nestloop_path().
+ */
+ initial_cost_mergejoin(root,
&workspace, jointype, mergeclauses,
+   outer_path,
inner_path,
+   outersortkeys, innersortkeys,
+
  extra->sjinfo);

I think in above comments, you want to say try_partial_nestloop_path().

5.
- if (joinrel->consider_parallel && nestjoinOK &&
- save_jointype != JOIN_UNIQUE_OUTER &&
- bms_is_empty(joinrel->lateral_relids))
+ if (!joinrel->consider_parallel ||
+ save_jointype == JOIN_UNIQUE_OUTER ||
+ !bms_is_empty(joinrel->lateral_relids) ||
+ jointype == JOIN_FULL ||
+ jointype == JOIN_RIGHT)
+ return;
+
+ if (nestjoinOK)

Here, we only want to create partial paths when
outerrel->partial_pathlist is not NILL, so I think you can include
that check as well. Another point to note is that in HEAD, we are not
checking for jointype as JOIN_RIGHT or JOIN_FULL for considering
parallel nestloop paths, whereas with your patch, it will do those
checks, is it a bug of HEAD or is there any other reason for including
those checks for parallel nestloop paths?

6.
+ /* Can't generate mergejoin path if inner rel is parameterized by outer */
+ if (inner_cheapest_total != NULL)
+ {
+ ListCell   *lc1;
+
+ /* generate merge join path for each partial outer path */
+ foreach(lc1, outerrel->partial_pathlist)
+ {
+ Path   *outerpath = (Path *) lfirst(lc1);
+ List   *merge_pathkeys;
+
+ /*
+ * Figure out what useful ordering any paths we create
+ * will have.
+ */
+ merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
+   outerpath->pathkeys);
+
+ generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
+ save_jointype, extra, false,
+ inner_cheapest_total, merge_pathkeys,
+ true);
+ }
+
+ }

Won't it be better if you encapsulate the above chunk of code in
function consider_parallel_merjejoin() similar to
consider_parallel_nestloop()? I think that way code will look
cleaner.

7.
+ /*
+ * Figure out what useful ordering any paths we create
+ * will have.
+ */
+ merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
+   outerpath->pathkeys);

indentation problem with variable outerpath->pathkeys.

8.
- try_mergejoin_path(root,
-   joinrel,
-   outerpath,
-   inner_cheapest_total,
-   merge_pathkeys,
-   mergeclauses,
-   NIL,
-   innersortkeys,
-   jointype,
-   extra);
+ if (!is_partial)
+ try_mergejoin_path(root,
+ joinrel,
+ outerpath,
+ inner_cheapest_total,
+ merge_pathkeys,
+ mergeclauses,
+ NIL,
+ innersortkeys,
+ jointype,
+ extra);
+
+ /* Generate partial path if inner is parallel safe. */
+ else if (inner_cheapest_total->parallel_safe)
+ try_partial_mergejoin_path(root,
+ joinrel,
+ outerpath,
+ inner_cheapest_total,
+ merge_pathkeys,
+ mergeclauses,
+ NIL,
+ innersortkeys,
+ jointype,
+ extra);

In above code indentation is broken, similarly, there is another code
in a patch where it is broken, try using pgindent.

--
With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Jan 4, 2017 at 12:02 PM, Amit Kapila <amit.kapila16@gmail.com> wrote:

Review comments:
1.
+ bool is_partial);
+

Seems additional new line is not required.

Fixed

2.
+ * try_partial_mergejoin_path
+ *  Consider a partial merge join path; if it appears useful,
push it into
+ *  the joinrel's pathlist via add_path().
+ */

I think in above comment, you should say ".. joinrel's
partial_pathlist via add_partial_path()"

Fixed

3.
+ /*
+ * See comments in try_partial_nestloop_path().
+ */

This same code exists in try_partial_nestloop_path() and
try_partial_hashjoin_path() with minor difference of code in
try_partial_hashjoin_path(). Can't we write a separate inline
function for this code and call from all the three places.

It's a small check, is it ok to make it the separate function. I have
also observed similar kind of duplicate code in try_mergejoin_path and
try_hashjoin_path. However, if you think that it will be better to
move that check to an inline function I can submit a seperate patch in
this thread as a refactoring patch?

I observed one more issue that in case of partial merge join
inner_paramrels should be empty not subset of outer, so fixed the same
in the attached version. The code in the previous patch will also not
create any problem, because if the inner path is parameterized by
outerrel it will not create any merge join path.

4.
+ /*
+ * See comments in try_nestloop_path().
+ */
+ initial_cost_mergejoin(root,
&workspace, jointype, mergeclauses,
+   outer_path,
inner_path,
+   outersortkeys, innersortkeys,
+
extra->sjinfo);

I think in above comments, you want to say try_partial_nestloop_path().

Fixed

5.
- if (joinrel->consider_parallel && nestjoinOK &&
- save_jointype != JOIN_UNIQUE_OUTER &&
- bms_is_empty(joinrel->lateral_relids))
+ if (!joinrel->consider_parallel ||
+ save_jointype == JOIN_UNIQUE_OUTER ||
+ !bms_is_empty(joinrel->lateral_relids) ||
+ jointype == JOIN_FULL ||
+ jointype == JOIN_RIGHT)
+ return;
+
+ if (nestjoinOK)

Here, we only want to create partial paths when
outerrel->partial_pathlist is not NILL, so I think you can include
that check as well.

Done.

Another point to note is that in HEAD, we are not

checking for jointype as JOIN_RIGHT or JOIN_FULL for considering
parallel nestloop paths, whereas with your patch, it will do those

is al> checks, is it a bug of HEAD or is there any other reason for including

those checks for parallel nestloop paths?

Actually we can not create parallel join path in case of JOIN_RIGHT or
JOIN_FULL. nestjoinOK is marked false in case of JOIN_RIGHT or
JOIN_FULL. So it was not considered in base code as well. Now we have
mergejoin as well so it's better to keep a common check.

6.
+ /* Can't generate mergejoin path if inner rel is parameterized by outer */
+ if (inner_cheapest_total != NULL)
+ {
+ ListCell   *lc1;
+
+ /* generate merge join path for each partial outer path */
+ foreach(lc1, outerrel->partial_pathlist)
+ {
+ Path   *outerpath = (Path *) lfirst(lc1);
+ List   *merge_pathkeys;
+
+ /*
+ * Figure out what useful ordering any paths we create
+ * will have.
+ */
+ merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
+   outerpath->pathkeys);
+
+ generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
+ save_jointype, extra, false,
+ inner_cheapest_total, merge_pathkeys,
+ true);
+ }
+
+ }

Won't it be better if you encapsulate the above chunk of code in
function consider_parallel_merjejoin() similar to
consider_parallel_nestloop()? I think that way code will look
cleaner.

Done

7.
+ /*
+ * Figure out what useful ordering any paths we create
+ * will have.
+ */
+ merge_pathkeys = build_join_pathkeys(root, joinrel, jointype,
+   outerpath->pathkeys);

indentation problem with variable outerpath->pathkeys.

Fixed

8.
- try_mergejoin_path(root,
-   joinrel,
-   outerpath,
-   inner_cheapest_total,
-   merge_pathkeys,
-   mergeclauses,
-   NIL,
-   innersortkeys,
-   jointype,
-   extra);
+ if (!is_partial)
+ try_mergejoin_path(root,
+ joinrel,
+ outerpath,
+ inner_cheapest_total,
+ merge_pathkeys,
+ mergeclauses,
+ NIL,
+ innersortkeys,
+ jointype,
+ extra);
+
+ /* Generate partial path if inner is parallel safe. */
+ else if (inner_cheapest_total->parallel_safe)
+ try_partial_mergejoin_path(root,
+ joinrel,
+ outerpath,
+ inner_cheapest_total,
+ merge_pathkeys,
+ mergeclauses,
+ NIL,
+ innersortkeys,
+ jointype,
+ extra);

In above code indentation is broken, similarly, there is another code
in a patch where it is broken, try using pgindent.

Fixed with pgindent.

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

On Thu, Jan 5, 2017 at 12:57 AM, Dilip Kumar <dilipbalaut@gmail.com> wrote:

On Wed, Jan 4, 2017 at 12:02 PM, Amit Kapila <amit.kapila16@gmail.com> wrote:

Review comments:
1.
+ bool is_partial);
+

Seems additional new line is not required.

Fixed

This patch has a patch, no new reviews. Moved to CF 2017-03.
--
Michael

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Jan 4, 2017 at 9:27 PM, Dilip Kumar <dilipbalaut@gmail.com> wrote:

On Wed, Jan 4, 2017 at 12:02 PM, Amit Kapila <amit.kapila16@gmail.com> wrote:

3.
+ /*
+ * See comments in try_partial_nestloop_path().
+ */

This same code exists in try_partial_nestloop_path() and
try_partial_hashjoin_path() with minor difference of code in
try_partial_hashjoin_path(). Can't we write a separate inline
function for this code and call from all the three places.

It's a small check, is it ok to make it the separate function. I have
also observed similar kind of duplicate code in try_mergejoin_path and
try_hashjoin_path. However, if you think that it will be better to
move that check to an inline function I can submit a seperate patch in
this thread as a refactoring patch?

Let's keep that check unchanged.

Few review comments on the latest version of the patch:
1.
- if (joinrel->consider_parallel && nestjoinOK &&
- save_jointype != JOIN_UNIQUE_OUTER &&
- bms_is_empty(joinrel->lateral_relids))
+ if (outerrel->partial_pathlist == NIL ||
+ !joinrel->consider_parallel ||
+ save_jointype == JOIN_UNIQUE_OUTER ||
+ !bms_is_empty(joinrel->lateral_relids) ||
+ jointype == JOIN_FULL ||
+ jointype == JOIN_RIGHT)
+ return;

For the matter of consistency, I think the above checks should be in
same order as they are in function hash_inner_and_outer(). I wonder
why are you using jointype in above check instead of save_jointype, it
seems to me we can use save_jointype for all the cases.

2.
+ generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
+
jointype, extra, false,
+
inner_cheapest_total, merge_pathkeys,
+
true);

IIUC, the reason of passing a 7th parameter (useallclauses) as false
is that it can be true only for Right and Full joins and for both we
don't generate partial merge join paths. If so, then I think it is
better to add a comment about such an assumption, so that we don't
forget to update this code in future if we need to useallclauses for
something else. Another way to deal with this is that you can pass
the value of useallclauses to consider_parallel_mergejoin() and then
to generate_mergejoin_paths(). I feel second way is better, but if
for some reason you don't find it appropriate then at least add a
comment.

3.
generate_mergejoin_paths()
{
..
..
- try_mergejoin_path(root,
- joinrel,
- outerpath,
- innerpath,
- merge_pathkeys,
- newclauses,
- NIL,
- NIL,
- jointype,
- extra);

+ if (!is_partial)
+ try_mergejoin_path(root,
+   joinrel,
+   outerpath,
+   innerpath,
+   merge_pathkeys,
+   newclauses,
+   NIL,
+   NIL,
+   jointype,
+   extra);

+ /* Generate partial path only if innerpath is parallel safe. */
+ else if (innerpath->parallel_safe)
+ try_partial_mergejoin_path(root,
+   joinrel,
+   outerpath,
+   innerpath,
+   merge_pathkeys,
+   newclauses,
+   NIL,
+   NIL,
+   jointype,
+   extra);

..
}

The above and similar changes in generate_mergejoin_paths() doesn't
look good and in some cases when innerpath is *parallel-unsafe*, you
need to perform some extra computation which is not required. How
about writing a separate function generate_partial_mergejoin_paths()?
I think you can save some extra computation and it will look neat. I
understand that there will be some code duplication, but not sure if
there is any other better way.

How about adding one simple test case as I have kept for other
parallel patches like parallel index scan, parallel subplan, etc.?

--
With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Feb 14, 2017 at 12:25 PM, Amit Kapila <amit.kapila16@gmail.com> wrote:

Few review comments on the latest version of the patch:
1.
- if (joinrel->consider_parallel && nestjoinOK &&
- save_jointype != JOIN_UNIQUE_OUTER &&
- bms_is_empty(joinrel->lateral_relids))
+ if (outerrel->partial_pathlist == NIL ||
+ !joinrel->consider_parallel ||
+ save_jointype == JOIN_UNIQUE_OUTER ||
+ !bms_is_empty(joinrel->lateral_relids) ||
+ jointype == JOIN_FULL ||
+ jointype == JOIN_RIGHT)
+ return;

For the matter of consistency, I think the above checks should be in
same order as they are in function hash_inner_and_outer(). I wonder
why are you using jointype in above check instead of save_jointype, it
seems to me we can use save_jointype for all the cases.

Done

2.
+ generate_mergejoin_paths(root, joinrel, innerrel, outerpath,
+
jointype, extra, false,
+
inner_cheapest_total, merge_pathkeys,
+
true);

IIUC, the reason of passing a 7th parameter (useallclauses) as false
is that it can be true only for Right and Full joins and for both we
don't generate partial merge join paths. If so, then I think it is
better to add a comment about such an assumption, so that we don't
forget to update this code in future if we need to useallclauses for
something else. Another way to deal with this is that you can pass
the value of useallclauses to consider_parallel_mergejoin() and then
to generate_mergejoin_paths(). I feel second way is better, but if
for some reason you don't find it appropriate then at least add a
comment.

After fixing 3rd comments this will not be needed.

3.
generate_mergejoin_paths()
{

The above and similar changes in generate_mergejoin_paths() doesn't
look good and in some cases when innerpath is *parallel-unsafe*, you
need to perform some extra computation which is not required. How
about writing a separate function generate_partial_mergejoin_paths()?
I think you can save some extra computation and it will look neat. I
understand that there will be some code duplication, but not sure if
there is any other better way.

Okay, I have done as suggested.

Apart from this, there was one small problem in an earlier version
which I have corrected in this.

+ /* Consider only parallel safe inner path */
+ if (innerpath != NULL &&
+ innerpath->parallel_safe &&
+ (cheapest_total_inner == NULL ||
+ cheapest_total_inner->parallel_safe == false ||
+ compare_path_costs(innerpath, cheapest_total_inner,
+ TOTAL_COST) < 0))

In this comparison, we were only checking if innerpath is cheaper than
the cheapest_total_inner then generate path with this new inner path
as well. Now, I have added one more check if cheapest_total_inner was
not parallel safe then also consider a path with this new inner
(provided this inner is parallel safe).

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

On Tue, Feb 14, 2017 at 5:22 PM, Dilip Kumar <dilipbalaut@gmail.com> wrote:

On Tue, Feb 14, 2017 at 12:25 PM, Amit Kapila <amit.kapila16@gmail.com> wrote:
Apart from this, there was one small problem in an earlier version
which I have corrected in this.

+ /* Consider only parallel safe inner path */
+ if (innerpath != NULL &&
+ innerpath->parallel_safe &&
+ (cheapest_total_inner == NULL ||
+ cheapest_total_inner->parallel_safe == false ||
+ compare_path_costs(innerpath, cheapest_total_inner,
+ TOTAL_COST) < 0))

In this comparison, we were only checking if innerpath is cheaper than
the cheapest_total_inner then generate path with this new inner path
as well. Now, I have added one more check if cheapest_total_inner was
not parallel safe then also consider a path with this new inner
(provided this inner is parallel safe).

What advantage do you see for considering such a path when the cost of
innerpath is more than cheapest_total_inner? Remember the more paths
we try to consider, the more time we spend in the planner. By any
chance are you able to generate any query where it will give benefit
by considering costlier innerpath?

2.
+static void generate_parallel_mergejoin_paths(PlannerInfo *root,
+  RelOptInfo *joinrel,
+  RelOptInfo *innerrel,
+  Path *outerpath,
+  JoinType jointype,
+  JoinPathExtraData *extra,
+  Path *inner_cheapest_total,
+  List *merge_pathkeys);

It is better to name this function as
generate_partial_mergejoin_paths() as we are generating only partial
paths in this function and accordingly change the comment on top of
the function. I see that you might be naming it based on
consider_parallel_*, however, I think it is better to use partial in
the name as that is what we are doing inside that function. Also, I
think this function has removed/changed some handling related to
unique outer and full joins, so it is better to mention that in the
function comments, something like "unlike above function, this
function doesn't expect to handle join types JOIN_UNIQUE_OUTER or
JOIN_FULL" and add Assert for both of those types.

3.
A test case is still missing.

--
With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Feb 24, 2017 at 3:04 PM, Amit Kapila <amit.kapila16@gmail.com> wrote:

Thanks for the comments.

What advantage do you see for considering such a path when the cost of
innerpath is more than cheapest_total_inner? Remember the more paths
we try to consider, the more time we spend in the planner. By any
chance are you able to generate any query where it will give benefit
by considering costlier innerpath?

If inner_cheapest_total path is not parallel safe then I am trying to
find the cheapest parallel safe path and generate partial merge join.
I agree that it will consider one extra path while considering every
partial merge join path (I think with this addition we will not get
parallel merge path for the any more TPCH query). I feel in general
we can get some better plan by this especially when gather is the
cheapest path for inner relation(which is not parallel safe) but at
the cost of considering some extra paths. What is your thought on
this?

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

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Feb 24, 2017 at 3:42 PM, Dilip Kumar <dilipbalaut@gmail.com> wrote:

On Fri, Feb 24, 2017 at 3:04 PM, Amit Kapila <amit.kapila16@gmail.com> wrote:

Thanks for the comments.

What advantage do you see for considering such a path when the cost of
innerpath is more than cheapest_total_inner? Remember the more paths
we try to consider, the more time we spend in the planner. By any
chance are you able to generate any query where it will give benefit
by considering costlier innerpath?

If inner_cheapest_total path is not parallel safe then I am trying to
find the cheapest parallel safe path and generate partial merge join.

Not sure, if we can just ignore the cheapest inner path because it is
not parallel safe. It is also possible that you pick costly inner
path just because it is parallel safe and then, later on, you have to
discard it because the overall cost of partial merge join is much
more.

I agree that it will consider one extra path while considering every
partial merge join path

Hmm, AFAICS, it will consider two extra paths per sort key (the loop
around considering such paths is up to num_sortkeys)

(I think with this addition we will not get
parallel merge path for the any more TPCH query). I feel in general
we can get some better plan by this especially when gather is the
cheapest path for inner relation(which is not parallel safe) but at
the cost of considering some extra paths.

I agree in some cases it could be better, but I think benefits are not
completely clear, so probably we can leave it as of now and if later
any one comes with a clear use case or can see the benefits of such
path then we can include it.

--
With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Feb 24, 2017 at 3:04 PM, Amit Kapila <amit.kapila16@gmail.com> wrote:

What advantage do you see for considering such a path when the cost of
innerpath is more than cheapest_total_inner? Remember the more paths
we try to consider, the more time we spend in the planner. By any
chance are you able to generate any query where it will give benefit
by considering costlier innerpath?

Changed

2.
+static void generate_parallel_mergejoin_paths(PlannerInfo *root,
+  RelOptInfo *joinrel,
+  RelOptInfo *innerrel,
+  Path *outerpath,
+  JoinType jointype,
+  JoinPathExtraData *extra,
+  Path *inner_cheapest_total,
+  List *merge_pathkeys);

It is better to name this function as
generate_partial_mergejoin_paths() as we are generating only partial
paths in this function and accordingly change the comment on top of
the function. I see that you might be naming it based on
consider_parallel_*, however, I think it is better to use partial in
the name as that is what we are doing inside that function. Also, I
think this function has removed/changed some handling related to
unique outer and full joins, so it is better to mention that in the
function comments, something like "unlike above function, this
function doesn't expect to handle join types JOIN_UNIQUE_OUTER or
JOIN_FULL" and add Assert for both of those types.

Done

3.
A test case is still missing.

Added

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