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

Commit828e94c

Browse files
author
Richard Guo
committed
Consider explicit incremental sort for mergejoins
For a mergejoin, if the given outer path or inner path is not alreadywell enough ordered, we need to do an explicit sort. Currently, weonly consider explicit full sort and do not account for incrementalsort.In this patch, for the outer path of a mergejoin, we choose to useexplicit incremental sort if it is enabled and there are presortedkeys. For the inner path, though, we cannot use incremental sortbecause it does not support mark/restore at present.The rationale is based on the assumption that incremental sort isalways faster than full sort when there are presorted keys, a premisethat has been applied in various parts of the code. In addition, thecurrent cost model tends to favor incremental sort as being cheaperthan full sort in the presence of presorted keys, making it reasonablenot to consider full sort in such cases.It could be argued that what if a mergejoin with an incremental sortas the outer path is selected as the inner path of another mergejoin.However, this should not be a problem, because mergejoin itself doesnot support mark/restore either, and we will add a Material node ontop of it anyway in this case (see final_cost_mergejoin).There is one ensuing plan change in the regression tests, and we haveto modify that test case to ensure that it continues to test what itis intended to.No backpatch as this could result in plan changes.Author: Richard GuoReviewed-by: David Rowley, Tomas VondraDiscussion:https://postgr.es/m/CAMbWs49x425QrX7h=Ux05WEnt8GS757H-jOP3_xsX5t1FoUsZw@mail.gmail.com
1 parentc4528fd commit828e94c

File tree

6 files changed

+184
-41
lines changed

6 files changed

+184
-41
lines changed

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

Lines changed: 57 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -3532,7 +3532,8 @@ final_cost_nestloop(PlannerInfo *root, NestPath *path,
35323532
* join quals here, except for obtaining the scan selectivity estimate which
35333533
* is really essential (but fortunately, use of caching keeps the cost of
35343534
* getting that down to something reasonable).
3535-
* We also assume that cost_sort is cheap enough to use here.
3535+
* We also assume that cost_sort/cost_incremental_sort is cheap enough to use
3536+
* here.
35363537
*
35373538
* 'workspace' is to be filled with startup_cost, total_cost, and perhaps
35383539
*other data to be used by final_cost_mergejoin
@@ -3569,7 +3570,8 @@ initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace,
35693570
outerendsel,
35703571
innerstartsel,
35713572
innerendsel;
3572-
Pathsort_path;/* dummy for result of cost_sort */
3573+
Pathsort_path;/* dummy for result of
3574+
* cost_sort/cost_incremental_sort */
35733575

35743576
/* Protect some assumptions below that rowcounts aren't zero */
35753577
if (outer_path_rows <=0)
@@ -3682,16 +3684,54 @@ initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace,
36823684

36833685
if (outersortkeys)/* do we need to sort outer? */
36843686
{
3685-
cost_sort(&sort_path,
3686-
root,
3687-
outersortkeys,
3688-
outer_path->disabled_nodes,
3689-
outer_path->total_cost,
3690-
outer_path_rows,
3691-
outer_path->pathtarget->width,
3692-
0.0,
3693-
work_mem,
3694-
-1.0);
3687+
booluse_incremental_sort= false;
3688+
intpresorted_keys;
3689+
3690+
/*
3691+
* We choose to use incremental sort if it is enabled and there are
3692+
* presorted keys; otherwise we use full sort.
3693+
*/
3694+
if (enable_incremental_sort)
3695+
{
3696+
boolis_sortedPG_USED_FOR_ASSERTS_ONLY;
3697+
3698+
is_sorted=pathkeys_count_contained_in(outersortkeys,
3699+
outer_path->pathkeys,
3700+
&presorted_keys);
3701+
Assert(!is_sorted);
3702+
3703+
if (presorted_keys>0)
3704+
use_incremental_sort= true;
3705+
}
3706+
3707+
if (!use_incremental_sort)
3708+
{
3709+
cost_sort(&sort_path,
3710+
root,
3711+
outersortkeys,
3712+
outer_path->disabled_nodes,
3713+
outer_path->total_cost,
3714+
outer_path_rows,
3715+
outer_path->pathtarget->width,
3716+
0.0,
3717+
work_mem,
3718+
-1.0);
3719+
}
3720+
else
3721+
{
3722+
cost_incremental_sort(&sort_path,
3723+
root,
3724+
outersortkeys,
3725+
presorted_keys,
3726+
outer_path->disabled_nodes,
3727+
outer_path->startup_cost,
3728+
outer_path->total_cost,
3729+
outer_path_rows,
3730+
outer_path->pathtarget->width,
3731+
0.0,
3732+
work_mem,
3733+
-1.0);
3734+
}
36953735
disabled_nodes+=sort_path.disabled_nodes;
36963736
startup_cost+=sort_path.startup_cost;
36973737
startup_cost+= (sort_path.total_cost-sort_path.startup_cost)
@@ -3711,6 +3751,11 @@ initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace,
37113751

37123752
if (innersortkeys)/* do we need to sort inner? */
37133753
{
3754+
/*
3755+
* We do not consider incremental sort for inner path, because
3756+
* incremental sort does not support mark/restore.
3757+
*/
3758+
37143759
cost_sort(&sort_path,
37153760
root,
37163761
innersortkeys,

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

Lines changed: 81 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -179,6 +179,8 @@ static void copy_generic_path_info(Plan *dest, Path *src);
179179
staticvoidcopy_plan_costsize(Plan*dest,Plan*src);
180180
staticvoidlabel_sort_with_costsize(PlannerInfo*root,Sort*plan,
181181
doublelimit_tuples);
182+
staticvoidlabel_incrementalsort_with_costsize(PlannerInfo*root,IncrementalSort*plan,
183+
List*pathkeys,doublelimit_tuples);
182184
staticSeqScan*make_seqscan(List*qptlist,List*qpqual,Indexscanrelid);
183185
staticSampleScan*make_samplescan(List*qptlist,List*qpqual,Indexscanrelid,
184186
TableSampleClause*tsc);
@@ -4523,19 +4525,63 @@ create_mergejoin_plan(PlannerInfo *root,
45234525
if (best_path->outersortkeys)
45244526
{
45254527
Relidsouter_relids=outer_path->parent->relids;
4526-
Sort*sort=make_sort_from_pathkeys(outer_plan,
4528+
Plan*sort_plan;
4529+
booluse_incremental_sort= false;
4530+
intpresorted_keys;
4531+
4532+
/*
4533+
* We choose to use incremental sort if it is enabled and there are
4534+
* presorted keys; otherwise we use full sort.
4535+
*/
4536+
if (enable_incremental_sort)
4537+
{
4538+
boolis_sortedPG_USED_FOR_ASSERTS_ONLY;
4539+
4540+
is_sorted=pathkeys_count_contained_in(best_path->outersortkeys,
4541+
outer_path->pathkeys,
4542+
&presorted_keys);
4543+
Assert(!is_sorted);
4544+
4545+
if (presorted_keys>0)
4546+
use_incremental_sort= true;
4547+
}
4548+
4549+
if (!use_incremental_sort)
4550+
{
4551+
sort_plan= (Plan*)
4552+
make_sort_from_pathkeys(outer_plan,
4553+
best_path->outersortkeys,
4554+
outer_relids);
4555+
4556+
label_sort_with_costsize(root, (Sort*)sort_plan,-1.0);
4557+
}
4558+
else
4559+
{
4560+
sort_plan= (Plan*)
4561+
make_incrementalsort_from_pathkeys(outer_plan,
45274562
best_path->outersortkeys,
4528-
outer_relids);
4563+
outer_relids,
4564+
presorted_keys);
45294565

4530-
label_sort_with_costsize(root,sort,-1.0);
4531-
outer_plan= (Plan*)sort;
4566+
label_incrementalsort_with_costsize(root,
4567+
(IncrementalSort*)sort_plan,
4568+
best_path->outersortkeys,
4569+
-1.0);
4570+
}
4571+
4572+
outer_plan=sort_plan;
45324573
outerpathkeys=best_path->outersortkeys;
45334574
}
45344575
else
45354576
outerpathkeys=best_path->jpath.outerjoinpath->pathkeys;
45364577

45374578
if (best_path->innersortkeys)
45384579
{
4580+
/*
4581+
* We do not consider incremental sort for inner path, because
4582+
* incremental sort does not support mark/restore.
4583+
*/
4584+
45394585
Relidsinner_relids=inner_path->parent->relids;
45404586
Sort*sort=make_sort_from_pathkeys(inner_plan,
45414587
best_path->innersortkeys,
@@ -5447,10 +5493,6 @@ label_sort_with_costsize(PlannerInfo *root, Sort *plan, double limit_tuples)
54475493
Plan*lefttree=plan->plan.lefttree;
54485494
Pathsort_path;/* dummy for result of cost_sort */
54495495

5450-
/*
5451-
* This function shouldn't have to deal with IncrementalSort plans because
5452-
* they are only created from corresponding Path nodes.
5453-
*/
54545496
Assert(IsA(plan,Sort));
54555497

54565498
cost_sort(&sort_path,root,NIL,
@@ -5469,6 +5511,37 @@ label_sort_with_costsize(PlannerInfo *root, Sort *plan, double limit_tuples)
54695511
plan->plan.parallel_safe=lefttree->parallel_safe;
54705512
}
54715513

5514+
/*
5515+
* Same as label_sort_with_costsize, but labels the IncrementalSort node
5516+
* instead.
5517+
*/
5518+
staticvoid
5519+
label_incrementalsort_with_costsize(PlannerInfo*root,IncrementalSort*plan,
5520+
List*pathkeys,doublelimit_tuples)
5521+
{
5522+
Plan*lefttree=plan->sort.plan.lefttree;
5523+
Pathsort_path;/* dummy for result of cost_incremental_sort */
5524+
5525+
Assert(IsA(plan,IncrementalSort));
5526+
5527+
cost_incremental_sort(&sort_path,root,pathkeys,
5528+
plan->nPresortedCols,
5529+
plan->sort.plan.disabled_nodes,
5530+
lefttree->startup_cost,
5531+
lefttree->total_cost,
5532+
lefttree->plan_rows,
5533+
lefttree->plan_width,
5534+
0.0,
5535+
work_mem,
5536+
limit_tuples);
5537+
plan->sort.plan.startup_cost=sort_path.startup_cost;
5538+
plan->sort.plan.total_cost=sort_path.total_cost;
5539+
plan->sort.plan.plan_rows=lefttree->plan_rows;
5540+
plan->sort.plan.plan_width=lefttree->plan_width;
5541+
plan->sort.plan.parallel_aware= false;
5542+
plan->sort.plan.parallel_safe=lefttree->parallel_safe;
5543+
}
5544+
54725545
/*
54735546
* bitmap_subplan_mark_shared
54745547
* Set isshared flag in bitmap subplan so that it will be created in

‎src/test/regress/expected/aggregates.out

Lines changed: 16 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -2858,29 +2858,27 @@ GROUP BY w, x, z, y;
28582858
-> Index Scan using btg_x_y_idx on btg
28592859
(6 rows)
28602860

2861-
-- Utilize the ordering of merge join to avoid afullSort operation
2861+
-- Utilize the ordering of merge join to avoid a Sort operation
28622862
SET enable_hashjoin = off;
28632863
SET enable_nestloop = off;
28642864
EXPLAIN (COSTS OFF)
28652865
SELECT count(*)
2866-
FROM btg t1 JOIN btg t2 ON t1.z = t2.z AND t1.w = t2.w AND t1.x = t2.x
2867-
GROUP BY t1.x, t1.y, t1.z, t1.w;
2868-
QUERY PLAN
2869-
-------------------------------------------------------------------------------
2866+
FROM btg t1 JOIN btg t2 ON t1.w = t2.w AND t1.x = t2.x AND t1.z = t2.z
2867+
GROUP BY t1.w, t1.z, t1.x;
2868+
QUERY PLAN
2869+
-------------------------------------------------------------------------
28702870
GroupAggregate
2871-
Group Key: t1.z, t1.w, t1.x, t1.y
2872-
-> Incremental Sort
2873-
Sort Key: t1.z, t1.w, t1.x, t1.y
2874-
Presorted Key: t1.z, t1.w, t1.x
2875-
-> Merge Join
2876-
Merge Cond: ((t1.z = t2.z) AND (t1.w = t2.w) AND (t1.x = t2.x))
2877-
-> Sort
2878-
Sort Key: t1.z, t1.w, t1.x
2879-
-> Index Scan using btg_x_y_idx on btg t1
2880-
-> Sort
2881-
Sort Key: t2.z, t2.w, t2.x
2882-
-> Index Scan using btg_x_y_idx on btg t2
2883-
(13 rows)
2871+
Group Key: t1.x, t1.w, t1.z
2872+
-> Merge Join
2873+
Merge Cond: ((t1.x = t2.x) AND (t1.w = t2.w) AND (t1.z = t2.z))
2874+
-> Incremental Sort
2875+
Sort Key: t1.x, t1.w, t1.z
2876+
Presorted Key: t1.x
2877+
-> Index Scan using btg_x_y_idx on btg t1
2878+
-> Sort
2879+
Sort Key: t2.x, t2.w, t2.z
2880+
-> Index Scan using btg_x_y_idx on btg t2
2881+
(11 rows)
28842882

28852883
RESET enable_nestloop;
28862884
RESET enable_hashjoin;

‎src/test/regress/expected/incremental_sort.out

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1701,3 +1701,24 @@ explain (costs off) select a, b, a <-> point(5, 5) dist from point_table order b
17011701
Order By: (a <-> '(5,5)'::point)
17021702
(6 rows)
17031703

1704+
-- Ensure we get an incremental sort on the outer side of the mergejoin
1705+
explain (costs off)
1706+
select * from
1707+
(select * from tenk1 order by four) t1 join tenk1 t2 on t1.four = t2.four and t1.two = t2.two
1708+
order by t1.four, t1.two limit 1;
1709+
QUERY PLAN
1710+
-----------------------------------------------------------------------
1711+
Limit
1712+
-> Merge Join
1713+
Merge Cond: ((tenk1.four = t2.four) AND (tenk1.two = t2.two))
1714+
-> Incremental Sort
1715+
Sort Key: tenk1.four, tenk1.two
1716+
Presorted Key: tenk1.four
1717+
-> Sort
1718+
Sort Key: tenk1.four
1719+
-> Seq Scan on tenk1
1720+
-> Sort
1721+
Sort Key: t2.four, t2.two
1722+
-> Seq Scan on tenk1 t2
1723+
(12 rows)
1724+

‎src/test/regress/sql/aggregates.sql

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1232,13 +1232,13 @@ EXPLAIN (COSTS OFF) SELECT count(*)
12321232
FROM (SELECT*FROM btgORDER BY x, y, w, z)AS q1
12331233
GROUP BY w, x, z, y;
12341234

1235-
-- Utilize the ordering of merge join to avoid afullSort operation
1235+
-- Utilize the ordering of merge join to avoid a Sort operation
12361236
SET enable_hashjoin= off;
12371237
SET enable_nestloop= off;
12381238
EXPLAIN (COSTS OFF)
12391239
SELECTcount(*)
1240-
FROM btg t1JOIN btg t2ONt1.z=t2.zANDt1.w=t2.wANDt1.x=t2.x
1241-
GROUP BYt1.x,t1.y,t1.z,t1.w;
1240+
FROM btg t1JOIN btg t2ONt1.w=t2.wANDt1.x=t2.xANDt1.z=t2.z
1241+
GROUP BYt1.w,t1.z,t1.x;
12421242
RESET enable_nestloop;
12431243
RESET enable_hashjoin;
12441244

‎src/test/regress/sql/incremental_sort.sql

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -292,3 +292,9 @@ create index point_table_a_idx on point_table using gist(a);
292292
-- Ensure we get an incremental sort plan for both of the following queries
293293
explain (costs off)select a, b, a<->point(5,5) distfrom point_tableorder by dist, blimit1;
294294
explain (costs off)select a, b, a<->point(5,5) distfrom point_tableorder by dist, bdesclimit1;
295+
296+
-- Ensure we get an incremental sort on the outer side of the mergejoin
297+
explain (costs off)
298+
select*from
299+
(select*from tenk1order by four) t1join tenk1 t2ont1.four=t2.fourandt1.two=t2.two
300+
order byt1.four,t1.twolimit1;

0 commit comments

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