Hi, I reviewed the patch series, tweaked a couple comments, added commit messages etc. Barring objections, I'll push this in a couple days.
One thing that annoys me is that it breaks ABI because it adds two new parameters to find_em_expr_usable_for_sorting_rel, but I don't think we can get around that. We could assume require_parallel_safe=true, but we still need to pass the PlannerInfo pointer. regards -- Tomas Vondra EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
>From 857e653607656d10586e2a0f1b936576513d4277 Mon Sep 17 00:00:00 2001 From: jcoleman <jtc...@gmail.com> Date: Fri, 20 Nov 2020 16:19:00 +0000 Subject: [PATCH 1/5] Consider unsorted paths in generate_useful_gather_paths generate_useful_gather_paths used to skip unsorted paths (without any pathkeys), but that is unnecessary - the later code actually can handle such paths just fine by adding a Sort node. This is clearly a thinko, preventing construction of useful plans. Backpatch to 13, where this code was introduced (for Incremental Sort). Author: James Coleman Reviewed-by: Tomas Vondra Backpatch-through: 13 Discussion: https://postgr.es/m/CAAaqYe8cK3g5CfLC4w7bs=hC0mSksZC=h5m8lschj5e5oxp...@mail.gmail.com --- src/backend/optimizer/path/allpaths.c | 8 -------- src/test/regress/expected/incremental_sort.out | 13 +++++++++++++ src/test/regress/sql/incremental_sort.sql | 4 ++++ 3 files changed, 17 insertions(+), 8 deletions(-) diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 84a69b064a..672a20760c 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -2914,14 +2914,6 @@ generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_r Path *subpath = (Path *) lfirst(lc2); GatherMergePath *path; - /* - * If the path has no ordering at all, then we can't use either - * incremental sort or rely on implicit sorting with a gather - * merge. - */ - if (subpath->pathkeys == NIL) - continue; - is_sorted = pathkeys_count_contained_in(useful_pathkeys, subpath->pathkeys, &presorted_keys); diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out index 7cf2eee7c1..51471ae92d 100644 --- a/src/test/regress/expected/incremental_sort.out +++ b/src/test/regress/expected/incremental_sort.out @@ -1468,6 +1468,19 @@ explain (costs off) select * from t union select * from t order by 1,3; -> Parallel Seq Scan on t t_1 (13 rows) +-- Full sort, not just incremental sort can be pushed below a gather merge path +-- by generate_useful_gather_paths. +explain (costs off) select distinct a,b from t; + QUERY PLAN +------------------------------------------ + Unique + -> Gather Merge + Workers Planned: 2 + -> Sort + Sort Key: a, b + -> Parallel Seq Scan on t +(6 rows) + drop table t; -- Sort pushdown can't go below where expressions are part of the rel target. -- In particular this is interesting for volatile expressions which have to diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql index 3ee11c394b..cb48f200ce 100644 --- a/src/test/regress/sql/incremental_sort.sql +++ b/src/test/regress/sql/incremental_sort.sql @@ -220,6 +220,10 @@ explain (costs off) select a,b,sum(c) from t group by 1,2 order by 1,2,3 limit 1 set enable_hashagg to off; explain (costs off) select * from t union select * from t order by 1,3; +-- Full sort, not just incremental sort can be pushed below a gather merge path +-- by generate_useful_gather_paths. +explain (costs off) select distinct a,b from t; + drop table t; -- Sort pushdown can't go below where expressions are part of the rel target. -- 2.26.2
>From 8ed86b447c07bdce8fafe95cdfb1e68286443274 Mon Sep 17 00:00:00 2001 From: James Coleman <jtc...@gmail.com> Date: Fri, 20 Nov 2020 20:29:51 -0500 Subject: [PATCH 2/5] Check parallel safety in generate_useful_gather_paths Commit ebb7ae839d ensured we ignore pathkeys with volatile expressions when considering adding a sort below a Gather Merge. Turns out we need to care about parallel safety of the pathkeys too, otherwise we might try sorting e.g. on results of a correlated subquery (as demonstrated by a report from Luis Roberto). Initial investigation by Tom Lane, patch by James Coleman. Backpatch to 13, where the code was instroduced (as part of Incremental Sort). Reported-by: Luis Roberto Author: James Coleman Reviewed-by: Tomas Vondra Backpatch-through: 13 Discussion: https://postgr.es/m/622580997.37108180.1604080457319.JavaMail.zimbra%40siscobra.com.br Discussion: https://postgr.es/m/CAAaqYe8cK3g5CfLC4w7bs=hC0mSksZC=h5m8lschj5e5oxp...@mail.gmail.com --- src/backend/optimizer/path/allpaths.c | 13 ++++-- src/backend/optimizer/path/equivclass.c | 9 ++++- src/include/optimizer/paths.h | 5 ++- .../regress/expected/incremental_sort.out | 40 +++++++++++++++++++ src/test/regress/sql/incremental_sort.sql | 11 +++++ 5 files changed, 73 insertions(+), 5 deletions(-) diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 672a20760c..df8d9309f9 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -2802,6 +2802,9 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows) * This allows us to do incremental sort on top of an index scan under a gather * merge node, i.e. parallelized. * + * If the require_parallel_safe is true, we also require the expressions to + * be parallel safe (which allows pushing the sort below Gather Merge). + * * XXX At the moment this can only ever return a list with a single element, * because it looks at query_pathkeys only. So we might return the pathkeys * directly, but it seems plausible we'll want to consider other orderings @@ -2809,7 +2812,8 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows) * merge joins. */ static List * -get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel) +get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel, + bool require_parallel_safe) { List *useful_pathkeys_list = NIL; @@ -2839,8 +2843,11 @@ get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel) * meet criteria of EC membership in the current relation, we * enable not just an incremental sort on the entirety of * query_pathkeys but also incremental sort below a JOIN. + * + * If requested, ensure the expression is parallel safe too. */ - if (!find_em_expr_usable_for_sorting_rel(pathkey_ec, rel)) + if (!find_em_expr_usable_for_sorting_rel(root, pathkey_ec, rel, + require_parallel_safe)) break; npathkeys++; @@ -2894,7 +2901,7 @@ generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_r generate_gather_paths(root, rel, override_rows); /* consider incremental sort for interesting orderings */ - useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel); + useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel, true); /* used for explicit (full) sort paths */ cheapest_partial_path = linitial(rel->partial_pathlist); diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c index f98fd7b3eb..b49ee52cba 100644 --- a/src/backend/optimizer/path/equivclass.c +++ b/src/backend/optimizer/path/equivclass.c @@ -803,7 +803,8 @@ find_em_expr_for_rel(EquivalenceClass *ec, RelOptInfo *rel) * applied in prepare_sort_from_pathkeys. */ Expr * -find_em_expr_usable_for_sorting_rel(EquivalenceClass *ec, RelOptInfo *rel) +find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec, + RelOptInfo *rel, bool require_parallel_safe) { ListCell *lc_em; @@ -833,6 +834,12 @@ find_em_expr_usable_for_sorting_rel(EquivalenceClass *ec, RelOptInfo *rel) if (!bms_is_subset(em->em_relids, rel->relids)) continue; + /* + * If requested, reject expressions that are not parallel-safe. + */ + if (require_parallel_safe && !is_parallel_safe(root, (Node *) em_expr)) + continue; + /* * As long as the expression isn't volatile then * prepare_sort_from_pathkeys is able to generate a new target entry, diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index 8a4c6f8b59..bf6c16b804 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -135,7 +135,10 @@ extern EquivalenceClass *get_eclass_for_sort_expr(PlannerInfo *root, Relids rel, bool create_it); extern Expr *find_em_expr_for_rel(EquivalenceClass *ec, RelOptInfo *rel); -extern Expr *find_em_expr_usable_for_sorting_rel(EquivalenceClass *ec, RelOptInfo *rel); +extern Expr *find_em_expr_usable_for_sorting_rel(PlannerInfo *root, + EquivalenceClass *ec, + RelOptInfo *rel, + bool require_parallel_safe); extern void generate_base_implied_equalities(PlannerInfo *root); extern List *generate_join_implied_equalities(PlannerInfo *root, Relids join_relids, diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out index 51471ae92d..d316a7c4b9 100644 --- a/src/test/regress/expected/incremental_sort.out +++ b/src/test/regress/expected/incremental_sort.out @@ -1551,6 +1551,46 @@ order by 1, 2; -> Function Scan on generate_series (7 rows) +-- Parallel sort but with expression (correlated subquery) that +-- is prohibited in parallel plans. +explain (costs off) select distinct + unique1, + (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1) +from tenk1 t, generate_series(1, 1000); + QUERY PLAN +--------------------------------------------------------------------------------- + Unique + -> Sort + Sort Key: t.unique1, ((SubPlan 1)) + -> Gather + Workers Planned: 2 + -> Nested Loop + -> Parallel Index Only Scan using tenk1_unique1 on tenk1 t + -> Function Scan on generate_series + SubPlan 1 + -> Index Only Scan using tenk1_unique1 on tenk1 + Index Cond: (unique1 = t.unique1) +(11 rows) + +explain (costs off) select + unique1, + (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1) +from tenk1 t, generate_series(1, 1000) +order by 1, 2; + QUERY PLAN +--------------------------------------------------------------------------- + Sort + Sort Key: t.unique1, ((SubPlan 1)) + -> Gather + Workers Planned: 2 + -> Nested Loop + -> Parallel Index Only Scan using tenk1_unique1 on tenk1 t + -> Function Scan on generate_series + SubPlan 1 + -> Index Only Scan using tenk1_unique1 on tenk1 + Index Cond: (unique1 = t.unique1) +(10 rows) + -- Parallel sort but with expression not available until the upper rel. explain (costs off) select distinct sub.unique1, stringu1 || random()::text from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub; diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql index cb48f200ce..ff3af0fd16 100644 --- a/src/test/regress/sql/incremental_sort.sql +++ b/src/test/regress/sql/incremental_sort.sql @@ -250,6 +250,17 @@ from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub; explain (costs off) select sub.unique1, md5(stringu1) from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub order by 1, 2; +-- Parallel sort but with expression (correlated subquery) that +-- is prohibited in parallel plans. +explain (costs off) select distinct + unique1, + (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1) +from tenk1 t, generate_series(1, 1000); +explain (costs off) select + unique1, + (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1) +from tenk1 t, generate_series(1, 1000) +order by 1, 2; -- Parallel sort but with expression not available until the upper rel. explain (costs off) select distinct sub.unique1, stringu1 || random()::text from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub; -- 2.26.2
>From 7e9502f88cf177fd4bd12b121b439dcb9cc39cf0 Mon Sep 17 00:00:00 2001 From: Tomas Vondra <to...@2ndquadrant.com> Date: Wed, 16 Dec 2020 00:18:40 +0100 Subject: [PATCH 3/5] Disallow SRFs when considering sorts below Gather Merge While we do allow SRFs in ORDER BY, but scan/join processing should not consider such cases - such sorts should only happen via final Sort atop a ProjectSet. So make sure we don't try adding such sorts below Gather Merge, just like we do for expressions that are volatile and/or not parallel safe. Backpatch to PostgreSQL 13, where this code was introduced as part of the Incremental Sort patch. Author: James Coleman Reviewed-by: Tomas Vondra Backpatch-through: 13 Discussion: https://postgr.es/m/CAAaqYe8cK3g5CfLC4w7bs=hC0mSksZC=h5m8lschj5e5oxp...@mail.gmail.com --- src/backend/optimizer/path/equivclass.c | 7 +++++++ src/backend/optimizer/util/tlist.c | 5 ----- src/include/optimizer/optimizer.h | 5 +++++ src/test/regress/expected/incremental_sort.out | 12 ++++++++++++ src/test/regress/sql/incremental_sort.sql | 2 ++ 5 files changed, 26 insertions(+), 5 deletions(-) diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c index b49ee52cba..0b2e212b2b 100644 --- a/src/backend/optimizer/path/equivclass.c +++ b/src/backend/optimizer/path/equivclass.c @@ -840,6 +840,13 @@ find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec, if (require_parallel_safe && !is_parallel_safe(root, (Node *) em_expr)) continue; + /* + * Disallow SRFs so that all of them can be evaluated at the correct + * time as determined by make_sort_input_target. + */ + if (IS_SRF_CALL((Node *) em_expr)) + continue; + /* * As long as the expression isn't volatile then * prepare_sort_from_pathkeys is able to generate a new target entry, diff --git a/src/backend/optimizer/util/tlist.c b/src/backend/optimizer/util/tlist.c index 02a3c6b165..01cea102ea 100644 --- a/src/backend/optimizer/util/tlist.c +++ b/src/backend/optimizer/util/tlist.c @@ -21,11 +21,6 @@ #include "optimizer/tlist.h" -/* Test if an expression node represents a SRF call. Beware multiple eval! */ -#define IS_SRF_CALL(node) \ - ((IsA(node, FuncExpr) && ((FuncExpr *) (node))->funcretset) || \ - (IsA(node, OpExpr) && ((OpExpr *) (node))->opretset)) - /* * Data structures for split_pathtarget_at_srfs(). To preserve the identity * of sortgroupref items even if they are textually equal(), what we track is diff --git a/src/include/optimizer/optimizer.h b/src/include/optimizer/optimizer.h index dea0e7338d..446071c554 100644 --- a/src/include/optimizer/optimizer.h +++ b/src/include/optimizer/optimizer.h @@ -24,6 +24,11 @@ #include "nodes/parsenodes.h" +/* Test if an expression node represents a SRF call. Beware multiple eval! */ +#define IS_SRF_CALL(node) \ + ((IsA(node, FuncExpr) && ((FuncExpr *) (node))->funcretset) || \ + (IsA(node, OpExpr) && ((OpExpr *) (node))->opretset)) + /* * We don't want to include nodes/pathnodes.h here, because non-planner * code should generally treat PlannerInfo as an opaque typedef. diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out index d316a7c4b9..a8cbfd9f5f 100644 --- a/src/test/regress/expected/incremental_sort.out +++ b/src/test/regress/expected/incremental_sort.out @@ -1620,3 +1620,15 @@ order by 1, 2; -> Function Scan on generate_series (7 rows) +-- Disallow pushing down sort when pathkey is an SRF. +explain (costs off) select unique1 from tenk1 order by unnest('{1,2}'::int[]); + QUERY PLAN +------------------------------------------------------------------------- + Sort + Sort Key: (unnest('{1,2}'::integer[])) + -> Gather + Workers Planned: 2 + -> ProjectSet + -> Parallel Index Only Scan using tenk1_unique1 on tenk1 +(6 rows) + diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql index ff3af0fd16..62a037b0cf 100644 --- a/src/test/regress/sql/incremental_sort.sql +++ b/src/test/regress/sql/incremental_sort.sql @@ -267,3 +267,5 @@ from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub; explain (costs off) select sub.unique1, stringu1 || random()::text from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub order by 1, 2; +-- Disallow pushing down sort when pathkey is an SRF. +explain (costs off) select unique1 from tenk1 order by unnest('{1,2}'::int[]); -- 2.26.2
>From 6c468c961a2a6b07833f1ce1dd22cddef32cc3e3 Mon Sep 17 00:00:00 2001 From: jcoleman <jtc...@gmail.com> Date: Wed, 25 Nov 2020 15:53:49 -0500 Subject: [PATCH 4/5] Don't search for volatile expr in find_em_expr_usable_for_sorting_rel While prepare_sort_from_pathkeys has to be concerned about matching up a volatile expression to the proper tlist entry, we don't need to do that in find_em_expr_usable_for_sorting_rel becausee such a sort will have to be postponed anyway. Author: James Coleman Reviewed-by: Tomas Vondra Backpatch-through: 13 Discussion: https://postgr.es/m/CAAaqYe8cK3g5CfLC4w7bs%3DhC0mSksZC%3DH5M8LSchj5e5OxpTAg%40mail.gmail.com --- src/backend/optimizer/path/equivclass.c | 27 +++++-------------------- 1 file changed, 5 insertions(+), 22 deletions(-) diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c index 0b2e212b2b..70499af2cf 100644 --- a/src/backend/optimizer/path/equivclass.c +++ b/src/backend/optimizer/path/equivclass.c @@ -817,7 +817,6 @@ find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec, EquivalenceMember *em = lfirst(lc_em); Expr *em_expr = em->em_expr; PathTarget *target = rel->reltarget; - ListCell *lc_target_expr; /* * We shouldn't be trying to sort by an equivalence class that @@ -851,30 +850,14 @@ find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec, * As long as the expression isn't volatile then * prepare_sort_from_pathkeys is able to generate a new target entry, * so there's no need to verify that one already exists. + * + * While prepare_sort_from_pathkeys has to be concerned about matching + * up a volatile expression to the proper tlist entry, it doesn't seem + * valuable here to expend the work trying to find a match in the + * target's exprs since such a sort will have to be postponed anyway. */ if (!ec->ec_has_volatile) return em->em_expr; - - /* - * If, however, it's volatile, we have to verify that the - * equivalence member's expr is already generated in the - * relation's target (we do strip relabels first from both - * expressions, which is cheap and might allow us to match - * more expressions). - */ - while (em_expr && IsA(em_expr, RelabelType)) - em_expr = ((RelabelType *) em_expr)->arg; - - foreach(lc_target_expr, target->exprs) - { - Expr *target_expr = lfirst(lc_target_expr); - - while (target_expr && IsA(target_expr, RelabelType)) - target_expr = ((RelabelType *) target_expr)->arg; - - if (equal(target_expr, em_expr)) - return em->em_expr; - } } /* We didn't find any suitable equivalence class expression */ -- 2.26.2
>From 1694a9dfb0f2c61aeb3b63e931edb7a16fb8acac Mon Sep 17 00:00:00 2001 From: Tomas Vondra <to...@2ndquadrant.com> Date: Wed, 16 Dec 2020 00:20:53 +0100 Subject: [PATCH 5/5] Improve find_em_expr_usable_for_sorting_rel comment Clarify the relationship between find_em_expr_usable_for_sorting_rel and prepare_sort_from_pathkeys, i.e. what restrictions need to be shared between those two places. Author: James Coleman Reviewed-by: Tomas Vondra Backpatch-through: 13 Discussion: https://postgr.es/m/CAAaqYe8cK3g5CfLC4w7bs%3DhC0mSksZC%3DH5M8LSchj5e5OxpTAg%40mail.gmail.com --- src/backend/optimizer/path/equivclass.c | 9 ++++++--- src/backend/optimizer/plan/createplan.c | 3 +++ 2 files changed, 9 insertions(+), 3 deletions(-) diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c index 70499af2cf..4466f880ee 100644 --- a/src/backend/optimizer/path/equivclass.c +++ b/src/backend/optimizer/path/equivclass.c @@ -798,9 +798,12 @@ find_em_expr_for_rel(EquivalenceClass *ec, RelOptInfo *rel) } /* - * Find an equivalence class member expression that can be safely used by a - * sort node on top of the provided relation. The rules here must match those - * applied in prepare_sort_from_pathkeys. + * Find an equivalence class member expression that can be safely used to build + * a sort node using the provided relation. The applied rules parallel those + * applied in prepare_sort_from_pathkeys but are a subset of that function since + * here we are concerned with proactive sorts while prepare_sort_from_pathkeys + * must deal with sorts that must be delayed until the last stages of query + * execution. */ Expr * find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec, diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index 5ecf9f4065..f7a8dae3c6 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -5850,6 +5850,9 @@ make_incrementalsort(Plan *lefttree, int numCols, int nPresortedCols, * * Returns the node which is to be the input to the Sort (either lefttree, * or a Result stacked atop lefttree). + * + * Note: Restrictions on what expressions are safely sortable may also need to + * be added to find_em_expr_usable_for_sorting_rel. */ static Plan * prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys, -- 2.26.2
