Skip to content

Commit c06e909

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 to decide 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. It can be considered a complement to the changes in commit 828e94c. 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 parent 773db22 commit c06e909

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+
int outer_presorted_keys,
35563558
JoinPathExtraData *extra)
35573559
{
35583560
int disabled_nodes;
@@ -3683,27 +3685,33 @@ initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace,
36833685

36843686
if (outersortkeys) /* do we need to sort outer? */
36853687
{
3686-
bool use_incremental_sort = false;
3687-
int presorted_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-
bool is_sorted PG_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
bool is_partial)
10431043
{
10441044
Relids required_outer;
1045+
int outer_presorted_keys = 0;
10451046
JoinCostWorkspace workspace;
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
JoinType jointype,
11471157
JoinPathExtraData *extra)
11481158
{
1159+
int outer_presorted_keys = 0;
11491160
JoinCostWorkspace workspace;
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
Relids outer_relids = outer_path->parent->relids;
45234523
Plan *sort_plan;
4524-
bool use_incremental_sort = false;
4525-
int presorted_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-
bool is_sorted PG_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
Relids inner_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
Relids required_outer,
26412642
List *mergeclauses,
26422643
List *outersortkeys,
2643-
List *innersortkeys)
2644+
List *innersortkeys,
2645+
int outer_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+
int outer_presorted_keys; /* number of presorted keys of the
2280+
* outer path */
22732281
bool skip_mark_restore; /* can executor skip mark/restore? */
22742282
bool materialize_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+
int outer_presorted_keys,
163164
JoinPathExtraData *extra);
164165
extern void final_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
Relids required_outer,
180180
List *mergeclauses,
181181
List *outersortkeys,
182-
List *innersortkeys);
182+
List *innersortkeys,
183+
int outer_presorted_keys);
183184

184185
extern HashPath *create_hashjoin_path(PlannerInfo *root,
185186
RelOptInfo *joinrel,

0 commit comments

Comments
 (0)