Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit3bc7daf

Browse files
committed
Consider parallel merge joins.
Commit45be99f took the positionthat performing a merge join in parallel was not likely to work outwell, but this conclusion was greeted with skepticism even at thetime. Whether it was true then or not, it's clearly not true anymore now that we have parallel index scan.Dilip Kumar, reviewed by Amit Kapila and by me.Discussion:http://postgr.es/m/CAFiTN-v3=cM6nyFwFGp0fmvY4=kk79Hq9Fgu0u8CSJ-EEq1Tiw@mail.gmail.com
1 parentef26623 commit3bc7daf

File tree

3 files changed

+275
-19
lines changed

3 files changed

+275
-19
lines changed

‎src/backend/optimizer/path/joinpath.c‎

Lines changed: 240 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,16 @@ set_join_pathlist_hook_type set_join_pathlist_hook = NULL;
2828
#definePATH_PARAM_BY_REL(path,rel) \
2929
((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), (rel)->relids))
3030

31+
staticvoidtry_partial_mergejoin_path(PlannerInfo*root,
32+
RelOptInfo*joinrel,
33+
Path*outer_path,
34+
Path*inner_path,
35+
List*pathkeys,
36+
List*mergeclauses,
37+
List*outersortkeys,
38+
List*innersortkeys,
39+
JoinTypejointype,
40+
JoinPathExtraData*extra);
3141
staticvoidsort_inner_and_outer(PlannerInfo*root,RelOptInfo*joinrel,
3242
RelOptInfo*outerrel,RelOptInfo*innerrel,
3343
JoinTypejointype,JoinPathExtraData*extra);
@@ -40,6 +50,13 @@ static void consider_parallel_nestloop(PlannerInfo *root,
4050
RelOptInfo*innerrel,
4151
JoinTypejointype,
4252
JoinPathExtraData*extra);
53+
staticvoidconsider_parallel_mergejoin(PlannerInfo*root,
54+
RelOptInfo*joinrel,
55+
RelOptInfo*outerrel,
56+
RelOptInfo*innerrel,
57+
JoinTypejointype,
58+
JoinPathExtraData*extra,
59+
Path*inner_cheapest_total);
4360
staticvoidhash_inner_and_outer(PlannerInfo*root,RelOptInfo*joinrel,
4461
RelOptInfo*outerrel,RelOptInfo*innerrel,
4562
JoinTypejointype,JoinPathExtraData*extra);
@@ -58,7 +75,8 @@ static void generate_mergejoin_paths(PlannerInfo *root,
5875
JoinPathExtraData*extra,
5976
booluseallclauses,
6077
Path*inner_cheapest_total,
61-
List*merge_pathkeys);
78+
List*merge_pathkeys,
79+
boolis_partial);
6280

6381

6482
/*
@@ -416,11 +434,27 @@ try_mergejoin_path(PlannerInfo *root,
416434
List*outersortkeys,
417435
List*innersortkeys,
418436
JoinTypejointype,
419-
JoinPathExtraData*extra)
437+
JoinPathExtraData*extra,
438+
boolis_partial)
420439
{
421440
Relidsrequired_outer;
422441
JoinCostWorkspaceworkspace;
423442

443+
if (is_partial)
444+
{
445+
try_partial_mergejoin_path(root,
446+
joinrel,
447+
outer_path,
448+
inner_path,
449+
pathkeys,
450+
mergeclauses,
451+
outersortkeys,
452+
innersortkeys,
453+
jointype,
454+
extra);
455+
return;
456+
}
457+
424458
/*
425459
* Check to see if proposed path is still parameterized, and reject if the
426460
* parameterization wouldn't be sensible.
@@ -480,6 +514,76 @@ try_mergejoin_path(PlannerInfo *root,
480514
}
481515
}
482516

517+
/*
518+
* try_partial_mergejoin_path
519+
* Consider a partial merge join path; if it appears useful, push it into
520+
* the joinrel's pathlist via add_partial_path().
521+
*/
522+
staticvoid
523+
try_partial_mergejoin_path(PlannerInfo*root,
524+
RelOptInfo*joinrel,
525+
Path*outer_path,
526+
Path*inner_path,
527+
List*pathkeys,
528+
List*mergeclauses,
529+
List*outersortkeys,
530+
List*innersortkeys,
531+
JoinTypejointype,
532+
JoinPathExtraData*extra)
533+
{
534+
JoinCostWorkspaceworkspace;
535+
536+
/*
537+
* See comments in try_partial_hashjoin_path().
538+
*/
539+
Assert(bms_is_empty(joinrel->lateral_relids));
540+
if (inner_path->param_info!=NULL)
541+
{
542+
Relidsinner_paramrels=inner_path->param_info->ppi_req_outer;
543+
544+
if (!bms_is_empty(inner_paramrels))
545+
return;
546+
}
547+
548+
/*
549+
* If the given paths are already well enough ordered, we can skip doing
550+
* an explicit sort.
551+
*/
552+
if (outersortkeys&&
553+
pathkeys_contained_in(outersortkeys,outer_path->pathkeys))
554+
outersortkeys=NIL;
555+
if (innersortkeys&&
556+
pathkeys_contained_in(innersortkeys,inner_path->pathkeys))
557+
innersortkeys=NIL;
558+
559+
/*
560+
* See comments in try_partial_nestloop_path().
561+
*/
562+
initial_cost_mergejoin(root,&workspace,jointype,mergeclauses,
563+
outer_path,inner_path,
564+
outersortkeys,innersortkeys,
565+
extra->sjinfo);
566+
567+
if (!add_partial_path_precheck(joinrel,workspace.total_cost,pathkeys))
568+
return;
569+
570+
/* Might be good enough to be worth trying, so let's try it. */
571+
add_partial_path(joinrel, (Path*)
572+
create_mergejoin_path(root,
573+
joinrel,
574+
jointype,
575+
&workspace,
576+
extra->sjinfo,
577+
outer_path,
578+
inner_path,
579+
extra->restrictlist,
580+
pathkeys,
581+
NULL,
582+
mergeclauses,
583+
outersortkeys,
584+
innersortkeys));
585+
}
586+
483587
/*
484588
* try_hashjoin_path
485589
* Consider a hash join path; if it appears useful, push it into
@@ -649,8 +753,11 @@ sort_inner_and_outer(PlannerInfo *root,
649753
JoinTypejointype,
650754
JoinPathExtraData*extra)
651755
{
756+
JoinTypesave_jointype=jointype;
652757
Path*outer_path;
653758
Path*inner_path;
759+
Path*cheapest_partial_outer;
760+
Path*cheapest_safe_inner=NULL;
654761
List*all_pathkeys;
655762
ListCell*l;
656763

@@ -699,6 +806,30 @@ sort_inner_and_outer(PlannerInfo *root,
699806
jointype=JOIN_INNER;
700807
}
701808

809+
/*
810+
* If the joinrel is parallel-safe, we may be able to consider a partial
811+
* merge join. However, we can't handle JOIN_UNIQUE_OUTER, because the
812+
* outer path will be partial, and therefore we won't be able to properly
813+
* guarantee uniqueness. Similarly, we can't handle JOIN_FULL and
814+
* JOIN_RIGHT, because they can produce false null extended rows. Also,
815+
* the resulting path must not be parameterized.
816+
*/
817+
if (joinrel->consider_parallel&&
818+
save_jointype!=JOIN_UNIQUE_OUTER&&
819+
save_jointype!=JOIN_FULL&&
820+
save_jointype!=JOIN_RIGHT&&
821+
outerrel->partial_pathlist!=NIL&&
822+
bms_is_empty(joinrel->lateral_relids))
823+
{
824+
cheapest_partial_outer= (Path*)linitial(outerrel->partial_pathlist);
825+
826+
if (inner_path->parallel_safe)
827+
cheapest_safe_inner=inner_path;
828+
elseif (save_jointype!=JOIN_UNIQUE_INNER)
829+
cheapest_safe_inner=
830+
get_cheapest_parallel_safe_total_inner(innerrel->pathlist);
831+
}
832+
702833
/*
703834
* Each possible ordering of the available mergejoin clauses will generate
704835
* a differently-sorted result path at essentially the same cost. We have
@@ -781,7 +912,24 @@ sort_inner_and_outer(PlannerInfo *root,
781912
outerkeys,
782913
innerkeys,
783914
jointype,
784-
extra);
915+
extra,
916+
false);
917+
918+
/*
919+
* If we have partial outer and parallel safe inner path then try
920+
* partial mergejoin path.
921+
*/
922+
if (cheapest_partial_outer&&cheapest_safe_inner)
923+
try_partial_mergejoin_path(root,
924+
joinrel,
925+
cheapest_partial_outer,
926+
cheapest_safe_inner,
927+
merge_pathkeys,
928+
cur_mergeclauses,
929+
outerkeys,
930+
innerkeys,
931+
jointype,
932+
extra);
785933
}
786934
}
787935

@@ -808,7 +956,8 @@ generate_mergejoin_paths(PlannerInfo *root,
808956
JoinPathExtraData*extra,
809957
booluseallclauses,
810958
Path*inner_cheapest_total,
811-
List*merge_pathkeys)
959+
List*merge_pathkeys,
960+
boolis_partial)
812961
{
813962
List*mergeclauses;
814963
List*innersortkeys;
@@ -868,7 +1017,8 @@ generate_mergejoin_paths(PlannerInfo *root,
8681017
NIL,
8691018
innersortkeys,
8701019
jointype,
871-
extra);
1020+
extra,
1021+
is_partial);
8721022

8731023
/* Can't do anything else if inner path needs to be unique'd */
8741024
if (save_jointype==JOIN_UNIQUE_INNER)
@@ -937,7 +1087,7 @@ generate_mergejoin_paths(PlannerInfo *root,
9371087
trialsortkeys,
9381088
NULL,
9391089
TOTAL_COST,
940-
false);
1090+
is_partial);
9411091
if (innerpath!=NULL&&
9421092
(cheapest_total_inner==NULL||
9431093
compare_path_costs(innerpath,cheapest_total_inner,
@@ -965,15 +1115,16 @@ generate_mergejoin_paths(PlannerInfo *root,
9651115
NIL,
9661116
NIL,
9671117
jointype,
968-
extra);
1118+
extra,
1119+
is_partial);
9691120
cheapest_total_inner=innerpath;
9701121
}
9711122
/* Same on the basis of cheapest startup cost ... */
9721123
innerpath=get_cheapest_path_for_pathkeys(innerrel->pathlist,
9731124
trialsortkeys,
9741125
NULL,
9751126
STARTUP_COST,
976-
false);
1127+
is_partial);
9771128
if (innerpath!=NULL&&
9781129
(cheapest_startup_inner==NULL||
9791130
compare_path_costs(innerpath,cheapest_startup_inner,
@@ -1009,7 +1160,8 @@ generate_mergejoin_paths(PlannerInfo *root,
10091160
NIL,
10101161
NIL,
10111162
jointype,
1012-
extra);
1163+
extra,
1164+
is_partial);
10131165
}
10141166
cheapest_startup_inner=innerpath;
10151167
}
@@ -1221,22 +1373,91 @@ match_unsorted_outer(PlannerInfo *root,
12211373
/* Generate merge join paths */
12221374
generate_mergejoin_paths(root,joinrel,innerrel,outerpath,
12231375
save_jointype,extra,useallclauses,
1224-
inner_cheapest_total,merge_pathkeys);
1376+
inner_cheapest_total,merge_pathkeys,
1377+
false);
12251378
}
12261379

12271380
/*
1228-
* If the joinrel is parallel-safe and the join type supports nested
1229-
* loops, we may be able to consider a partial nestloop plan. However, we
1230-
* can't handle JOIN_UNIQUE_OUTER, because the outer path will be partial,
1231-
* and therefore we won't be able to properly guarantee uniqueness. Nor
1232-
* can we handle extra_lateral_rels, since partial paths must not be
1233-
* parameterized.
1381+
* Consider partial nestloop and mergejoin plan if outerrel has any
1382+
* partial path and the joinrel is parallel-safe. However, we can't
1383+
* handle JOIN_UNIQUE_OUTER, because the outer path will be partial, and
1384+
* therefore we won't be able to properly guarantee uniqueness. Nor can
1385+
* we handle extra_lateral_rels, since partial paths must not be
1386+
* parameterized. Similarly, we can't handle JOIN_FULL and JOIN_RIGHT,
1387+
* because they can produce false null extended rows.
12341388
*/
1235-
if (joinrel->consider_parallel&&nestjoinOK&&
1389+
if (joinrel->consider_parallel&&
12361390
save_jointype!=JOIN_UNIQUE_OUTER&&
1391+
save_jointype!=JOIN_FULL&&
1392+
save_jointype!=JOIN_RIGHT&&
1393+
outerrel->partial_pathlist!=NIL&&
12371394
bms_is_empty(joinrel->lateral_relids))
1238-
consider_parallel_nestloop(root,joinrel,outerrel,innerrel,
1239-
save_jointype,extra);
1395+
{
1396+
if (nestjoinOK)
1397+
consider_parallel_nestloop(root,joinrel,outerrel,innerrel,
1398+
save_jointype,extra);
1399+
1400+
/*
1401+
* If inner_cheapest_total is NULL or non parallel-safe then find the
1402+
* cheapest total parallel safe path. If doing JOIN_UNIQUE_INNER, we
1403+
* can't use any alternative inner path.
1404+
*/
1405+
if (inner_cheapest_total==NULL||
1406+
!inner_cheapest_total->parallel_safe)
1407+
{
1408+
if (save_jointype==JOIN_UNIQUE_INNER)
1409+
return;
1410+
1411+
inner_cheapest_total=get_cheapest_parallel_safe_total_inner(
1412+
innerrel->pathlist);
1413+
}
1414+
1415+
if (inner_cheapest_total)
1416+
consider_parallel_mergejoin(root,joinrel,outerrel,innerrel,
1417+
save_jointype,extra,
1418+
inner_cheapest_total);
1419+
}
1420+
}
1421+
1422+
/*
1423+
* consider_parallel_mergejoin
1424+
* Try to build partial paths for a joinrel by joining a partial path
1425+
* for the outer relation to a complete path for the inner relation.
1426+
*
1427+
* 'joinrel' is the join relation
1428+
* 'outerrel' is the outer join relation
1429+
* 'innerrel' is the inner join relation
1430+
* 'jointype' is the type of join to do
1431+
* 'extra' contains additional input values
1432+
* 'inner_cheapest_total' cheapest total path for innerrel
1433+
*/
1434+
staticvoid
1435+
consider_parallel_mergejoin(PlannerInfo*root,
1436+
RelOptInfo*joinrel,
1437+
RelOptInfo*outerrel,
1438+
RelOptInfo*innerrel,
1439+
JoinTypejointype,
1440+
JoinPathExtraData*extra,
1441+
Path*inner_cheapest_total)
1442+
{
1443+
ListCell*lc1;
1444+
1445+
/* generate merge join path for each partial outer path */
1446+
foreach(lc1,outerrel->partial_pathlist)
1447+
{
1448+
Path*outerpath= (Path*)lfirst(lc1);
1449+
List*merge_pathkeys;
1450+
1451+
/*
1452+
* Figure out what useful ordering any paths we create will have.
1453+
*/
1454+
merge_pathkeys=build_join_pathkeys(root,joinrel,jointype,
1455+
outerpath->pathkeys);
1456+
1457+
generate_mergejoin_paths(root,joinrel,innerrel,outerpath,jointype,
1458+
extra, false,inner_cheapest_total,
1459+
merge_pathkeys, true);
1460+
}
12401461
}
12411462

12421463
/*

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp