Skip to content

Commit a65724d

Browse files
tglsfdctglsfdc
committed
Propagate pathkeys from CTEs up to the outer query.
If we know the sort order of a CTE's output, and it is relevant to the outer query, label the CTE's outer-query access path using those pathkeys. This may enable optimizations such as avoiding a sort in the outer query. The code for hoisting pathkeys into the outer query already exists for regular RTE_SUBQUERY subqueries, but it wasn't getting used for CTEs, possibly out of concern for maintaining an optimization fence between the CTE and the outer query. However, on the same arguments used for commit f7816ae, there seems no harm in letting the outer query know what the inner query decided to do. In support of this, we now remember the best Path as well as Plan for each subquery for the rest of the planner run. There may be future applications for having that at hand, and it surely costs little to build one more List. Richard Guo (minor mods by me) Discussion: https://postgr.es/m/CAMbWs49xYd3f8CrE8-WW3--dV1zH_sDSDn-vs2DzHj81Wcnsew@mail.gmail.com
1 parent e648e77 commit a65724d

File tree

8 files changed

+64
-15
lines changed

8 files changed

+64
-15
lines changed

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

Lines changed: 14 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2872,16 +2872,19 @@ set_tablefunc_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
28722872
static void
28732873
set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
28742874
{
2875+
Path *ctepath;
28752876
Plan *cteplan;
28762877
PlannerInfo *cteroot;
28772878
Index levelsup;
2879+
List *pathkeys;
28782880
int ndx;
28792881
ListCell *lc;
28802882
int plan_id;
28812883
Relids required_outer;
28822884

28832885
/*
2884-
* Find the referenced CTE, and locate the plan previously made for it.
2886+
* Find the referenced CTE, and locate the path and plan previously made
2887+
* for it.
28852888
*/
28862889
levelsup = rte->ctelevelsup;
28872890
cteroot = root;
@@ -2913,11 +2916,20 @@ set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
29132916
plan_id = list_nth_int(cteroot->cte_plan_ids, ndx);
29142917
if (plan_id <= 0)
29152918
elog(ERROR, "no plan was made for CTE \"%s\"", rte->ctename);
2919+
2920+
Assert(list_length(root->glob->subpaths) == list_length(root->glob->subplans));
2921+
ctepath = (Path *) list_nth(root->glob->subpaths, plan_id - 1);
29162922
cteplan = (Plan *) list_nth(root->glob->subplans, plan_id - 1);
29172923

29182924
/* Mark rel with estimated output rows, width, etc */
29192925
set_cte_size_estimates(root, rel, cteplan->plan_rows);
29202926

2927+
/* Convert the ctepath's pathkeys to outer query's representation */
2928+
pathkeys = convert_subquery_pathkeys(root,
2929+
rel,
2930+
ctepath->pathkeys,
2931+
cteplan->targetlist);
2932+
29212933
/*
29222934
* We don't support pushing join clauses into the quals of a CTE scan, but
29232935
* it could still have required parameterization due to LATERAL refs in
@@ -2926,7 +2938,7 @@ set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
29262938
required_outer = rel->lateral_relids;
29272939

29282940
/* Generate appropriate path */
2929-
add_path(rel, create_ctescan_path(root, rel, required_outer));
2941+
add_path(rel, create_ctescan_path(root, rel, pathkeys, required_outer));
29302942
}
29312943

29322944
/*

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

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -306,6 +306,7 @@ standard_planner(Query *parse, const char *query_string, int cursorOptions,
306306

307307
glob->boundParams = boundParams;
308308
glob->subplans = NIL;
309+
glob->subpaths = NIL;
309310
glob->subroots = NIL;
310311
glob->rewindPlanIDs = NULL;
311312
glob->finalrtable = NIL;

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

Lines changed: 18 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -65,8 +65,8 @@ typedef struct inline_cte_walker_context
6565
} inline_cte_walker_context;
6666

6767

68-
static Node *build_subplan(PlannerInfo *root, Plan *plan, PlannerInfo *subroot,
69-
List *plan_params,
68+
static Node *build_subplan(PlannerInfo *root, Plan *plan, Path *path,
69+
PlannerInfo *subroot, List *plan_params,
7070
SubLinkType subLinkType, int subLinkId,
7171
Node *testexpr, List *testexpr_paramids,
7272
bool unknownEqFalse);
@@ -236,7 +236,8 @@ make_subplan(PlannerInfo *root, Query *orig_subquery,
236236
plan = create_plan(subroot, best_path);
237237

238238
/* And convert to SubPlan or InitPlan format. */
239-
result = build_subplan(root, plan, subroot, plan_params,
239+
result = build_subplan(root, plan, best_path,
240+
subroot, plan_params,
240241
subLinkType, subLinkId,
241242
testexpr, NIL, isTopQual);
242243

@@ -288,8 +289,8 @@ make_subplan(PlannerInfo *root, Query *orig_subquery,
288289

289290
/* ... and convert to SubPlan format */
290291
hashplan = castNode(SubPlan,
291-
build_subplan(root, plan, subroot,
292-
plan_params,
292+
build_subplan(root, plan, best_path,
293+
subroot, plan_params,
293294
ANY_SUBLINK, 0,
294295
newtestexpr,
295296
paramIds,
@@ -317,8 +318,8 @@ make_subplan(PlannerInfo *root, Query *orig_subquery,
317318
* make it an InitPlan, as explained in the comments for make_subplan.
318319
*/
319320
static Node *
320-
build_subplan(PlannerInfo *root, Plan *plan, PlannerInfo *subroot,
321-
List *plan_params,
321+
build_subplan(PlannerInfo *root, Plan *plan, Path *path,
322+
PlannerInfo *subroot, List *plan_params,
322323
SubLinkType subLinkType, int subLinkId,
323324
Node *testexpr, List *testexpr_paramids,
324325
bool unknownEqFalse)
@@ -539,9 +540,10 @@ build_subplan(PlannerInfo *root, Plan *plan, PlannerInfo *subroot,
539540
}
540541

541542
/*
542-
* Add the subplan and its PlannerInfo to the global lists.
543+
* Add the subplan, its path, and its PlannerInfo to the global lists.
543544
*/
544545
root->glob->subplans = lappend(root->glob->subplans, plan);
546+
root->glob->subpaths = lappend(root->glob->subpaths, path);
545547
root->glob->subroots = lappend(root->glob->subroots, subroot);
546548
splan->plan_id = list_length(root->glob->subplans);
547549

@@ -1029,9 +1031,10 @@ SS_process_ctes(PlannerInfo *root)
10291031
splan->setParam = list_make1_int(paramid);
10301032

10311033
/*
1032-
* Add the subplan and its PlannerInfo to the global lists.
1034+
* Add the subplan, its path, and its PlannerInfo to the global lists.
10331035
*/
10341036
root->glob->subplans = lappend(root->glob->subplans, plan);
1037+
root->glob->subpaths = lappend(root->glob->subpaths, best_path);
10351038
root->glob->subroots = lappend(root->glob->subroots, subroot);
10361039
splan->plan_id = list_length(root->glob->subplans);
10371040

@@ -3021,9 +3024,14 @@ SS_make_initplan_from_plan(PlannerInfo *root,
30213024
SubPlan *node;
30223025

30233026
/*
3024-
* Add the subplan and its PlannerInfo to the global lists.
3027+
* Add the subplan and its PlannerInfo, as well as a dummy path entry, to
3028+
* the global lists. Ideally we'd save a real path, but right now our
3029+
* sole caller doesn't build a path that exactly matches the plan. Since
3030+
* we're not currently going to need the path for an initplan, it's not
3031+
* worth requiring construction of such a path.
30253032
*/
30263033
root->glob->subplans = lappend(root->glob->subplans, plan);
3034+
root->glob->subpaths = lappend(root->glob->subpaths, NULL);
30273035
root->glob->subroots = lappend(root->glob->subroots, subroot);
30283036

30293037
/*

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

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2121,7 +2121,8 @@ create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel,
21212121
* returning the pathnode.
21222122
*/
21232123
Path *
2124-
create_ctescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer)
2124+
create_ctescan_path(PlannerInfo *root, RelOptInfo *rel,
2125+
List *pathkeys, Relids required_outer)
21252126
{
21262127
Path *pathnode = makeNode(Path);
21272128

@@ -2133,7 +2134,7 @@ create_ctescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer)
21332134
pathnode->parallel_aware = false;
21342135
pathnode->parallel_safe = rel->consider_parallel;
21352136
pathnode->parallel_workers = 0;
2136-
pathnode->pathkeys = NIL; /* XXX for now, result is always unordered */
2137+
pathnode->pathkeys = pathkeys;
21372138

21382139
cost_ctescan(pathnode, root, rel, pathnode->param_info);
21392140

‎src/include/nodes/pathnodes.h

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -104,6 +104,9 @@ typedef struct PlannerGlobal
104104
/* Plans for SubPlan nodes */
105105
List *subplans;
106106

107+
/* Paths from which the SubPlan Plans were made */
108+
List *subpaths;
109+
107110
/* PlannerInfos for SubPlan nodes */
108111
List *subroots pg_node_attr(read_write_ignore);
109112

‎src/include/optimizer/pathnode.h

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -115,7 +115,7 @@ extern Path *create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel,
115115
extern Path *create_tablefuncscan_path(PlannerInfo *root, RelOptInfo *rel,
116116
Relids required_outer);
117117
extern Path *create_ctescan_path(PlannerInfo *root, RelOptInfo *rel,
118-
Relids required_outer);
118+
List *pathkeys, Relids required_outer);
119119
extern Path *create_namedtuplestorescan_path(PlannerInfo *root, RelOptInfo *rel,
120120
Relids required_outer);
121121
extern Path *create_resultscan_path(PlannerInfo *root, RelOptInfo *rel,

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

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -672,6 +672,23 @@ select count(*) from tenk1 a
672672
Index Cond: (unique1 = x.unique1)
673673
(10 rows)
674674

675+
-- test that pathkeys from a materialized CTE are propagated up to the
676+
-- outer query
677+
explain (costs off)
678+
with x as materialized (select unique1 from tenk1 b order by unique1)
679+
select count(*) from tenk1 a
680+
where unique1 in (select * from x);
681+
QUERY PLAN
682+
------------------------------------------------------------
683+
Aggregate
684+
CTE x
685+
-> Index Only Scan using tenk1_unique1 on tenk1 b
686+
-> Merge Semi Join
687+
Merge Cond: (a.unique1 = x.unique1)
688+
-> Index Only Scan using tenk1_unique1 on tenk1 a
689+
-> CTE Scan on x
690+
(7 rows)
691+
675692
-- SEARCH clause
676693
create temp table graph0( f int, t int, label text );
677694
insert into graph0 values

‎src/test/regress/sql/with.sql

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -359,6 +359,13 @@ with x as materialized (insert into tenk1 default values returning unique1)
359359
select count(*) from tenk1 a
360360
where unique1 in (select * from x);
361361

362+
-- test that pathkeys from a materialized CTE are propagated up to the
363+
-- outer query
364+
explain (costs off)
365+
with x as materialized (select unique1 from tenk1 b order by unique1)
366+
select count(*) from tenk1 a
367+
where unique1 in (select * from x);
368+
362369
-- SEARCH clause
363370

364371
create temp table graph0( f int, t int, label text );

0 commit comments

Comments
 (0)