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

Commitc06e909

Browse files
author
Richard Guo
committed
Track the number of presorted outer pathkeys in MergePath
When creating an explicit Sort node for the outer path of a mergejoin,we need to determine the number of presorted keys of the outer path todecide whether explicit incremental sort can be applied. Currently,this is done by repeatedly calling pathkeys_count_contained_in.This patch caches the number of presorted outer pathkeys in MergePath,allowing us to save several calls to pathkeys_count_contained_in. Itcan be considered a complement to the changes in commit828e94c.Reported-by: David Rowley <dgrowleyml@gmail.com>Author: Richard Guo <guofenglinux@gmail.com>Reviewed-by: Tender Wang <tndrwang@gmail.com>Discussion:https://postgr.es/m/CAApHDvqvBireB_w6x8BN5txdvBEHxVgZBt=rUnpf5ww5P_E_ww@mail.gmail.com
1 parent773db22 commitc06e909

File tree

8 files changed

+104
-66
lines changed

8 files changed

+104
-66
lines changed

‎src/backend/foreign/foreign.c

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -821,8 +821,9 @@ GetExistingLocalJoinPath(RelOptInfo *joinrel)
821821
* for the mergejoin, we can skip doing an explicit sort.
822822
*/
823823
if (merge_path->outersortkeys&&
824-
pathkeys_contained_in(merge_path->outersortkeys,
825-
joinpath->outerjoinpath->pathkeys))
824+
pathkeys_count_contained_in(merge_path->outersortkeys,
825+
joinpath->outerjoinpath->pathkeys,
826+
&merge_path->outer_presorted_keys))
826827
merge_path->outersortkeys=NIL;
827828
}
828829
}

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

Lines changed: 30 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -3542,6 +3542,7 @@ final_cost_nestloop(PlannerInfo *root, NestPath *path,
35423542
* 'inner_path' is the inner input to the join
35433543
* 'outersortkeys' is the list of sort keys for the outer path
35443544
* 'innersortkeys' is the list of sort keys for the inner path
3545+
* 'outer_presorted_keys' is the number of presorted keys of the outer path
35453546
* 'extra' contains miscellaneous information about the join
35463547
*
35473548
* Note: outersortkeys and innersortkeys should be NIL if no explicit
@@ -3553,6 +3554,7 @@ initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace,
35533554
List*mergeclauses,
35543555
Path*outer_path,Path*inner_path,
35553556
List*outersortkeys,List*innersortkeys,
3557+
intouter_presorted_keys,
35563558
JoinPathExtraData*extra)
35573559
{
35583560
intdisabled_nodes;
@@ -3683,27 +3685,33 @@ initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace,
36833685

36843686
if (outersortkeys)/* do we need to sort outer? */
36853687
{
3686-
booluse_incremental_sort= false;
3687-
intpresorted_keys;
3688+
/*
3689+
* We can assert that the outer path is not already ordered
3690+
* appropriately for the mergejoin; otherwise, outersortkeys would
3691+
* have been set to NIL.
3692+
*/
3693+
Assert(!pathkeys_contained_in(outersortkeys,outer_path->pathkeys));
36883694

36893695
/*
36903696
* We choose to use incremental sort if it is enabled and there are
36913697
* presorted keys; otherwise we use full sort.
36923698
*/
3693-
if (enable_incremental_sort)
3699+
if (enable_incremental_sort&&outer_presorted_keys>0)
36943700
{
3695-
boolis_sortedPG_USED_FOR_ASSERTS_ONLY;
3696-
3697-
is_sorted=pathkeys_count_contained_in(outersortkeys,
3698-
outer_path->pathkeys,
3699-
&presorted_keys);
3700-
Assert(!is_sorted);
3701-
3702-
if (presorted_keys>0)
3703-
use_incremental_sort= true;
3701+
cost_incremental_sort(&sort_path,
3702+
root,
3703+
outersortkeys,
3704+
outer_presorted_keys,
3705+
outer_path->disabled_nodes,
3706+
outer_path->startup_cost,
3707+
outer_path->total_cost,
3708+
outer_path_rows,
3709+
outer_path->pathtarget->width,
3710+
0.0,
3711+
work_mem,
3712+
-1.0);
37043713
}
3705-
3706-
if (!use_incremental_sort)
3714+
else
37073715
{
37083716
cost_sort(&sort_path,
37093717
root,
@@ -3716,21 +3724,7 @@ initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace,
37163724
work_mem,
37173725
-1.0);
37183726
}
3719-
else
3720-
{
3721-
cost_incremental_sort(&sort_path,
3722-
root,
3723-
outersortkeys,
3724-
presorted_keys,
3725-
outer_path->disabled_nodes,
3726-
outer_path->startup_cost,
3727-
outer_path->total_cost,
3728-
outer_path_rows,
3729-
outer_path->pathtarget->width,
3730-
0.0,
3731-
work_mem,
3732-
-1.0);
3733-
}
3727+
37343728
disabled_nodes+=sort_path.disabled_nodes;
37353729
startup_cost+=sort_path.startup_cost;
37363730
startup_cost+= (sort_path.total_cost-sort_path.startup_cost)
@@ -3750,6 +3744,13 @@ initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace,
37503744

37513745
if (innersortkeys)/* do we need to sort inner? */
37523746
{
3747+
/*
3748+
* We can assert that the inner path is not already ordered
3749+
* appropriately for the mergejoin; otherwise, innersortkeys would
3750+
* have been set to NIL.
3751+
*/
3752+
Assert(!pathkeys_contained_in(innersortkeys,inner_path->pathkeys));
3753+
37533754
/*
37543755
* We do not consider incremental sort for inner path, because
37553756
* incremental sort does not support mark/restore.

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

Lines changed: 24 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1042,6 +1042,7 @@ try_mergejoin_path(PlannerInfo *root,
10421042
boolis_partial)
10431043
{
10441044
Relidsrequired_outer;
1045+
intouter_presorted_keys=0;
10451046
JoinCostWorkspaceworkspace;
10461047

10471048
if (is_partial)
@@ -1087,9 +1088,16 @@ try_mergejoin_path(PlannerInfo *root,
10871088
/*
10881089
* If the given paths are already well enough ordered, we can skip doing
10891090
* an explicit sort.
1091+
*
1092+
* We need to determine the number of presorted keys of the outer path to
1093+
* decide whether explicit incremental sort can be applied when
1094+
* outersortkeys is not NIL. We do not need to do the same for the inner
1095+
* path though, as incremental sort currently does not support
1096+
* mark/restore.
10901097
*/
10911098
if (outersortkeys&&
1092-
pathkeys_contained_in(outersortkeys,outer_path->pathkeys))
1099+
pathkeys_count_contained_in(outersortkeys,outer_path->pathkeys,
1100+
&outer_presorted_keys))
10931101
outersortkeys=NIL;
10941102
if (innersortkeys&&
10951103
pathkeys_contained_in(innersortkeys,inner_path->pathkeys))
@@ -1101,6 +1109,7 @@ try_mergejoin_path(PlannerInfo *root,
11011109
initial_cost_mergejoin(root,&workspace,jointype,mergeclauses,
11021110
outer_path,inner_path,
11031111
outersortkeys,innersortkeys,
1112+
outer_presorted_keys,
11041113
extra);
11051114

11061115
if (add_path_precheck(joinrel,workspace.disabled_nodes,
@@ -1120,7 +1129,8 @@ try_mergejoin_path(PlannerInfo *root,
11201129
required_outer,
11211130
mergeclauses,
11221131
outersortkeys,
1123-
innersortkeys));
1132+
innersortkeys,
1133+
outer_presorted_keys));
11241134
}
11251135
else
11261136
{
@@ -1146,6 +1156,7 @@ try_partial_mergejoin_path(PlannerInfo *root,
11461156
JoinTypejointype,
11471157
JoinPathExtraData*extra)
11481158
{
1159+
intouter_presorted_keys=0;
11491160
JoinCostWorkspaceworkspace;
11501161

11511162
/*
@@ -1159,9 +1170,16 @@ try_partial_mergejoin_path(PlannerInfo *root,
11591170
/*
11601171
* If the given paths are already well enough ordered, we can skip doing
11611172
* an explicit sort.
1173+
*
1174+
* We need to determine the number of presorted keys of the outer path to
1175+
* decide whether explicit incremental sort can be applied when
1176+
* outersortkeys is not NIL. We do not need to do the same for the inner
1177+
* path though, as incremental sort currently does not support
1178+
* mark/restore.
11621179
*/
11631180
if (outersortkeys&&
1164-
pathkeys_contained_in(outersortkeys,outer_path->pathkeys))
1181+
pathkeys_count_contained_in(outersortkeys,outer_path->pathkeys,
1182+
&outer_presorted_keys))
11651183
outersortkeys=NIL;
11661184
if (innersortkeys&&
11671185
pathkeys_contained_in(innersortkeys,inner_path->pathkeys))
@@ -1173,6 +1191,7 @@ try_partial_mergejoin_path(PlannerInfo *root,
11731191
initial_cost_mergejoin(root,&workspace,jointype,mergeclauses,
11741192
outer_path,inner_path,
11751193
outersortkeys,innersortkeys,
1194+
outer_presorted_keys,
11761195
extra);
11771196

11781197
if (!add_partial_path_precheck(joinrel,workspace.disabled_nodes,
@@ -1193,7 +1212,8 @@ try_partial_mergejoin_path(PlannerInfo *root,
11931212
NULL,
11941213
mergeclauses,
11951214
outersortkeys,
1196-
innersortkeys));
1215+
innersortkeys,
1216+
outer_presorted_keys));
11971217
}
11981218

11991219
/*

‎src/backend/optimizer/plan/createplan.c

Lines changed: 32 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -4521,48 +4521,41 @@ create_mergejoin_plan(PlannerInfo *root,
45214521
{
45224522
Relidsouter_relids=outer_path->parent->relids;
45234523
Plan*sort_plan;
4524-
booluse_incremental_sort= false;
4525-
intpresorted_keys;
4524+
4525+
/*
4526+
* We can assert that the outer path is not already ordered
4527+
* appropriately for the mergejoin; otherwise, outersortkeys would
4528+
* have been set to NIL.
4529+
*/
4530+
Assert(!pathkeys_contained_in(best_path->outersortkeys,
4531+
outer_path->pathkeys));
45264532

45274533
/*
45284534
* We choose to use incremental sort if it is enabled and there are
45294535
* presorted keys; otherwise we use full sort.
45304536
*/
4531-
if (enable_incremental_sort)
4532-
{
4533-
boolis_sortedPG_USED_FOR_ASSERTS_ONLY;
4534-
4535-
is_sorted=pathkeys_count_contained_in(best_path->outersortkeys,
4536-
outer_path->pathkeys,
4537-
&presorted_keys);
4538-
Assert(!is_sorted);
4539-
4540-
if (presorted_keys>0)
4541-
use_incremental_sort= true;
4542-
}
4543-
4544-
if (!use_incremental_sort)
4545-
{
4546-
sort_plan= (Plan*)
4547-
make_sort_from_pathkeys(outer_plan,
4548-
best_path->outersortkeys,
4549-
outer_relids);
4550-
4551-
label_sort_with_costsize(root, (Sort*)sort_plan,-1.0);
4552-
}
4553-
else
4537+
if (enable_incremental_sort&&best_path->outer_presorted_keys>0)
45544538
{
45554539
sort_plan= (Plan*)
45564540
make_incrementalsort_from_pathkeys(outer_plan,
45574541
best_path->outersortkeys,
45584542
outer_relids,
4559-
presorted_keys);
4543+
best_path->outer_presorted_keys);
45604544

45614545
label_incrementalsort_with_costsize(root,
45624546
(IncrementalSort*)sort_plan,
45634547
best_path->outersortkeys,
45644548
-1.0);
45654549
}
4550+
else
4551+
{
4552+
sort_plan= (Plan*)
4553+
make_sort_from_pathkeys(outer_plan,
4554+
best_path->outersortkeys,
4555+
outer_relids);
4556+
4557+
label_sort_with_costsize(root, (Sort*)sort_plan,-1.0);
4558+
}
45664559

45674560
outer_plan=sort_plan;
45684561
outerpathkeys=best_path->outersortkeys;
@@ -4578,9 +4571,19 @@ create_mergejoin_plan(PlannerInfo *root,
45784571
*/
45794572

45804573
Relidsinner_relids=inner_path->parent->relids;
4581-
Sort*sort=make_sort_from_pathkeys(inner_plan,
4582-
best_path->innersortkeys,
4583-
inner_relids);
4574+
Sort*sort;
4575+
4576+
/*
4577+
* We can assert that the inner path is not already ordered
4578+
* appropriately for the mergejoin; otherwise, innersortkeys would
4579+
* have been set to NIL.
4580+
*/
4581+
Assert(!pathkeys_contained_in(best_path->innersortkeys,
4582+
inner_path->pathkeys));
4583+
4584+
sort=make_sort_from_pathkeys(inner_plan,
4585+
best_path->innersortkeys,
4586+
inner_relids);
45844587

45854588
label_sort_with_costsize(root,sort,-1.0);
45864589
inner_plan= (Plan*)sort;

‎src/backend/optimizer/util/pathnode.c

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2626,6 +2626,7 @@ create_nestloop_path(PlannerInfo *root,
26262626
*(this should be a subset of the restrict_clauses list)
26272627
* 'outersortkeys' are the sort varkeys for the outer relation
26282628
* 'innersortkeys' are the sort varkeys for the inner relation
2629+
* 'outer_presorted_keys' is the number of presorted keys of the outer path
26292630
*/
26302631
MergePath*
26312632
create_mergejoin_path(PlannerInfo*root,
@@ -2640,7 +2641,8 @@ create_mergejoin_path(PlannerInfo *root,
26402641
Relidsrequired_outer,
26412642
List*mergeclauses,
26422643
List*outersortkeys,
2643-
List*innersortkeys)
2644+
List*innersortkeys,
2645+
intouter_presorted_keys)
26442646
{
26452647
MergePath*pathnode=makeNode(MergePath);
26462648

@@ -2669,6 +2671,7 @@ create_mergejoin_path(PlannerInfo *root,
26692671
pathnode->path_mergeclauses=mergeclauses;
26702672
pathnode->outersortkeys=outersortkeys;
26712673
pathnode->innersortkeys=innersortkeys;
2674+
pathnode->outer_presorted_keys=outer_presorted_keys;
26722675
/* pathnode->skip_mark_restore will be set by final_cost_mergejoin */
26732676
/* pathnode->materialize_inner will be set by final_cost_mergejoin */
26742677

‎src/include/nodes/pathnodes.h

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2253,6 +2253,12 @@ typedef struct NestPath
22532253
* mergejoin. If it is not NIL then it is a PathKeys list describing
22542254
* the ordering that must be created by an explicit Sort node.
22552255
*
2256+
* outer_presorted_keys is the number of presorted keys of the outer
2257+
* path that match outersortkeys. It is used to determine whether
2258+
* explicit incremental sort can be applied when outersortkeys is not
2259+
* NIL. We do not track the number of presorted keys of the inner
2260+
* path, as incremental sort currently does not support mark/restore.
2261+
*
22562262
* skip_mark_restore is true if the executor need not do mark/restore calls.
22572263
* Mark/restore overhead is usually required, but can be skipped if we know
22582264
* that the executor need find only one match per outer tuple, and that the
@@ -2270,6 +2276,8 @@ typedef struct MergePath
22702276
List*path_mergeclauses;/* join clauses to be used for merge */
22712277
List*outersortkeys;/* keys for explicit sort, if any */
22722278
List*innersortkeys;/* keys for explicit sort, if any */
2279+
intouter_presorted_keys;/* number of presorted keys of the
2280+
* outer path */
22732281
boolskip_mark_restore;/* can executor skip mark/restore? */
22742282
boolmaterialize_inner;/* add Materialize to inner? */
22752283
}MergePath;

‎src/include/optimizer/cost.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -160,6 +160,7 @@ extern void initial_cost_mergejoin(PlannerInfo *root,
160160
List*mergeclauses,
161161
Path*outer_path,Path*inner_path,
162162
List*outersortkeys,List*innersortkeys,
163+
intouter_presorted_keys,
163164
JoinPathExtraData*extra);
164165
externvoidfinal_cost_mergejoin(PlannerInfo*root,MergePath*path,
165166
JoinCostWorkspace*workspace,

‎src/include/optimizer/pathnode.h

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -179,7 +179,8 @@ extern MergePath *create_mergejoin_path(PlannerInfo *root,
179179
Relidsrequired_outer,
180180
List*mergeclauses,
181181
List*outersortkeys,
182-
List*innersortkeys);
182+
List*innersortkeys,
183+
intouter_presorted_keys);
183184

184185
externHashPath*create_hashjoin_path(PlannerInfo*root,
185186
RelOptInfo*joinrel,

0 commit comments

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