On Fri, Oct 30, 2020 at 5:03 PM Tomas Vondra
<tomas.von...@2ndquadrant.com> wrote:
>
> On Fri, Oct 30, 2020 at 01:26:08PM -0400, James Coleman wrote:
> >On Thu, Oct 29, 2020 at 6:06 PM Tomas Vondra
> ><tomas.von...@2ndquadrant.com> wrote:
> >>
> >> On Tue, Oct 06, 2020 at 09:37:31AM -0400, James Coleman wrote:
> >> >On Tue, Oct 6, 2020 at 9:28 AM Jaime Casanova
> >> ><jaime.casan...@2ndquadrant.com> wrote:
> >> >> Can you please create an entry in the commitfest for this one so we
> >> >> don't lose track of it?
> >> >
> >>
> >> We're not too far from the next minor release, so I've been looking at
> >> this fix again and I intend to get it committed shortly (on Monday or
> >> so). Attached is a slightly modified version of the v4 patch that:
> >>
> >> (a) Removes comments about projections added to code that is not
> >> directly related to the fix. I'm not against adding such comments
> >> separately.
> >
> >Seems fine. Do you want to commit them at the same time (just a
> >separate commit)? Or have a separate patch? It seems a bit overkill to
> >start a new thread just for those.
> >
>
> Probably sometime later, as a separate patch. I haven't thought very
> much about those comments, it just seemed unrelated to the fix so I've
> removed that for now. Let's not bother with this until after the minor
> release.
For whatever it's worth, I didn't originally consider them unrelated;
the purpose was to explain why those places were safe relative to the
same kinds of issues under discussion here: whether an expr will be in
the target and when it might need to be added.
EIther way I've split it into a separate patch in this series.
> >> (b) Fixes comment in expected output of incremental_sort test.
> >
> >Thanks.
> >
> >> (c) Removes else branch from find_em_expr_usable_for_sorting_rel. It's
> >> not quite needed thanks to the "return" in the "if" branch. IMO this
> >> makes it more elegant.
> >
> >No objection.
> >
> >> I do have two questions about find_em_expr_usable_for_sorting_rel.
> >>
> >> (a) Where does the em_is_const check come from? The comment claims we
> >> should not be trying to sort by equivalence class members, but I can't
> >> convince myself it's actually true and I don't see it discussed in this
> >> thread.
> >
> >That comes from find_ec_member_for_tle which is called by
> >prepare_sort_from_pathkeys which we note in the comments contains the
> >set of rules we need to mirror.
> >
>
> Thanks for the pointer. I'll take a look.
>
> >> (b) In find_em_expr_for_rel, which was what was used before, the
> >> condition on relids was this:
> >>
> >> if (bms_is_subset(em->em_relids, rel->relids) &&
> >> !bms_is_empty(em->em_relids))
> >> {
> >> return em->em_expr;
> >> }
> >>
> >> but here we're using only
> >>
> >> if (!bms_is_subset(em->em_relids, rel->relids))
> >> continue;
> >>
> >> Isn't this missing the second bms_is_empty condition?
> >
> >I definitely remember intentionally removing that condition. For one,
> >it's not present in prepare_sort_from_pathkeys. My memory is a bit
> >fuzzy on all of the whys, but isn't it the case that if we've already
> >excluded const expressions, that we must have vars (and therefore
> >rels) present, and therefore the relids bms must be non-empty?
> >Probably more importantly, we're going to check that an actual em expr
> >matches, which means the bms subset check is really just an
> >optimization to avoid unnecessarily scanning the exprs for equality.
> >Perhaps it's worth adding a comment saying as such?
> >
> >By the way, the fact that this is parallel to
> >prepare_sort_from_pathkeys is the reason the XXX comment is still
> >there about possibly needing to remove relabel types (since
> >prepare_sort_from_pathkeys does that). I don't think it's a hard
> >requirement: the worst case is that by not digging into relabel types
> >we're being unnecessarily strict.
> >
> >Both of these I can add if desired.
> >
>
> Yeah, it'd be good to explain the reasoning why it's fine to have the
> conditions like this. Thanks.
I was looking at this some more, and I'm still convinced that this is
correct, but I don't think a comment about it being an optimization
(though I suspect that that its major benefit), since it came from,
and must parallel, find_ec_member_for_tle, and there is no such
explanation there. I don't want to backfill reasoning onto that
decision, but I do think it's important to parallel it since it's
ultimately what is going to cause errors if we're out of sync with it.
As to why find_em_expr_for_rel is different, I think the answer is
that it's used by the FDW code, and it seems to me to make sense that
in that case we'd only send sort conditions to the foreign server if
the em actually contains rels.
The new series attached includes the primary fix for this issue, the
additional comments that could either go in at the same time or not,
and my patch with semi-related questions (which isn't intended to be
committed, but to keep track of the questions).
James
From b81e133200086058cf2c8f683e31a643cc32aea7 Mon Sep 17 00:00:00 2001
From: James Coleman <jtc...@gmail.com>
Date: Sat, 3 Oct 2020 22:05:08 -0400
Subject: [PATCH v6 3/3] questions
---
src/backend/optimizer/plan/planner.c | 16 ++++++++++++++++
1 file changed, 16 insertions(+)
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 6989c5c0e3..f78bbcec02 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -5018,6 +5018,10 @@ create_ordered_paths(PlannerInfo *root,
root->sort_pathkeys,
limit_tuples);
/* Add projection step if needed */
+ /* TODO: why don't we apply the projection to the path
+ * before sorting? Is it because it's already been done
+ * by apply_scanjoin_target_to_paths?
+ */
if (sorted_path->pathtarget != target)
sorted_path = apply_projection_to_path(root, ordered_rel,
sorted_path, target);
@@ -5048,6 +5052,10 @@ create_ordered_paths(PlannerInfo *root,
limit_tuples);
/* Add projection step if needed */
+ /* TODO: why don't we apply the projection to the path
+ * before sorting? Is it because it's already been done
+ * by apply_scanjoin_target_to_paths?
+ */
if (sorted_path->pathtarget != target)
sorted_path = apply_projection_to_path(root, ordered_rel,
sorted_path, target);
@@ -5099,6 +5107,10 @@ create_ordered_paths(PlannerInfo *root,
&total_groups);
/* Add projection step if needed */
+ /* TODO: why can't we apply the projection to the partial
+ * path? Is it because it's already been done if possible
+ * by apply_scanjoin_target_to_paths?
+ */
if (path->pathtarget != target)
path = apply_projection_to_path(root, ordered_rel,
path, target);
@@ -5160,6 +5172,10 @@ create_ordered_paths(PlannerInfo *root,
&total_groups);
/* Add projection step if needed */
+ /* TODO: why can't we apply the projection to the partial
+ * path? Is it because it's already been done if possible
+ * by apply_scanjoin_target_to_paths?
+ */
if (sorted_path->pathtarget != target)
sorted_path = apply_projection_to_path(root, ordered_rel,
sorted_path, target);
--
2.17.1
From c9ca57f75b6423916a63c2ddfddae9e00bbfef10 Mon Sep 17 00:00:00 2001
From: James Coleman <jtc...@gmail.com>
Date: Sat, 3 Oct 2020 10:35:47 -0400
Subject: [PATCH v6 1/3] Fix get_useful_pathkeys_for_relation for volatile
exprs below joins
It's not sufficient to find an ec member whose Vars are all in the rel
we're working with; volatile expressions in particular present a case
where we also need to know if the rel's target contains the expression
or not before we can assume the pathkey for that ec is safe to use at
this point in the query. If the pathkey expr is volatile and we're
below a join, then the expr can't appear in the target until we're above
the join, so we can't sort with it yet.
---
src/backend/optimizer/path/allpaths.c | 13 +--
src/backend/optimizer/path/equivclass.c | 67 +++++++++++++
src/include/optimizer/paths.h | 1 +
.../regress/expected/incremental_sort.out | 98 +++++++++++++++++++
src/test/regress/sql/incremental_sort.sql | 31 ++++++
5 files changed, 204 insertions(+), 6 deletions(-)
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index b399592ff8..3393e1d37a 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2760,7 +2760,8 @@ get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel)
/*
* Considering query_pathkeys is always worth it, because it might allow
* us to avoid a total sort when we have a partially presorted path
- * available.
+ * available or to push the total sort into the parallel portion of the
+ * query.
*/
if (root->query_pathkeys)
{
@@ -2773,17 +2774,17 @@ get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel)
EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
/*
- * We can only build an Incremental Sort for pathkeys which
- * contain an EC member in the current relation, so ignore any
- * suffix of the list as soon as we find a pathkey without an EC
- * member the relation.
+ * We can only build a sort for pathkeys which contain an EC
+ * member in the current relation's target, so ignore any suffix
+ * of the list as soon as we find a pathkey without an EC member
+ * in the relation.
*
* By still returning the prefix of the pathkeys list that does
* 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 (!find_em_expr_for_rel(pathkey_ec, rel))
+ if (!find_em_expr_usable_for_sorting_rel(pathkey_ec, rel))
break;
npathkeys++;
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index a21b3b4756..483e68780e 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -797,6 +797,73 @@ find_em_expr_for_rel(EquivalenceClass *ec, RelOptInfo *rel)
return NULL;
}
+/*
+ * 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.
+ */
+Expr *
+find_em_expr_usable_for_sorting_rel(EquivalenceClass *ec, RelOptInfo *rel)
+{
+ ListCell *lc_em;
+
+ /*
+ * If there is more than one equivalence member matching these
+ * requirements we'll be content to choose any one of them.
+ */
+ foreach(lc_em, ec->ec_members)
+ {
+ 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
+ * contains a constant, so no need to consider such cases any further.
+ */
+ if (em->em_is_const)
+ continue;
+
+ /*
+ * Any Vars in the equivalence class member need to come from this
+ * relation. This is a superset of prepare_sort_from_pathkeys ignoring
+ * child members unless they belong to the rel being sorted.
+ */
+ if (!bms_is_subset(em->em_relids, rel->relids))
+ continue;
+
+ /*
+ * 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.
+ */
+ 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 (but we can strip relabels).
+ */
+ 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 */
+ return NULL;
+}
+
/*
* generate_base_implied_equalities
* Generate any restriction clauses that we can deduce from equivalence
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 2134227ebc..8a4c6f8b59 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -135,6 +135,7 @@ 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 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 e376ea1276..7cf2eee7c1 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1469,3 +1469,101 @@ explain (costs off) select * from t union select * from t order by 1,3;
(13 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
+-- go above joins since otherwise we'll incorrectly use expression evaluations
+-- across multiple rows.
+set enable_hashagg=off;
+set enable_seqscan=off;
+set enable_incremental_sort = off;
+set parallel_tuple_cost=0;
+set parallel_setup_cost=0;
+set min_parallel_table_scan_size = 0;
+set min_parallel_index_scan_size = 0;
+-- Parallel sort below join.
+explain (costs off) select distinct sub.unique1, stringu1
+from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
+ QUERY PLAN
+--------------------------------------------------------------------------
+ Unique
+ -> Nested Loop
+ -> Gather Merge
+ Workers Planned: 2
+ -> Sort
+ Sort Key: tenk1.unique1, tenk1.stringu1
+ -> Parallel Index Scan using tenk1_unique1 on tenk1
+ -> Function Scan on generate_series
+(8 rows)
+
+explain (costs off) select sub.unique1, stringu1
+from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub
+order by 1, 2;
+ QUERY PLAN
+--------------------------------------------------------------------
+ Nested Loop
+ -> Gather Merge
+ Workers Planned: 2
+ -> Sort
+ Sort Key: tenk1.unique1, tenk1.stringu1
+ -> Parallel Index Scan using tenk1_unique1 on tenk1
+ -> Function Scan on generate_series
+(7 rows)
+
+-- Parallel sort but with expression that can be safely generated at the base rel.
+explain (costs off) select distinct sub.unique1, md5(stringu1)
+from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
+ QUERY PLAN
+----------------------------------------------------------------------------------------
+ Unique
+ -> Nested Loop
+ -> Gather Merge
+ Workers Planned: 2
+ -> Sort
+ Sort Key: tenk1.unique1, (md5((tenk1.stringu1)::text)) COLLATE "C"
+ -> Parallel Index Scan using tenk1_unique1 on tenk1
+ -> Function Scan on generate_series
+(8 rows)
+
+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;
+ QUERY PLAN
+----------------------------------------------------------------------------------
+ Nested Loop
+ -> Gather Merge
+ Workers Planned: 2
+ -> Sort
+ Sort Key: tenk1.unique1, (md5((tenk1.stringu1)::text)) COLLATE "C"
+ -> Parallel Index Scan using tenk1_unique1 on tenk1
+ -> Function Scan on generate_series
+(7 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;
+ QUERY PLAN
+---------------------------------------------------------------------------------------------
+ Unique
+ -> Sort
+ Sort Key: tenk1.unique1, (((tenk1.stringu1)::text || (random())::text)) COLLATE "C"
+ -> Gather
+ Workers Planned: 2
+ -> Nested Loop
+ -> Parallel Index Scan using tenk1_unique1 on tenk1
+ -> Function Scan on generate_series
+(8 rows)
+
+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;
+ QUERY PLAN
+---------------------------------------------------------------------------------------
+ Sort
+ Sort Key: tenk1.unique1, (((tenk1.stringu1)::text || (random())::text)) COLLATE "C"
+ -> Gather
+ Workers Planned: 2
+ -> Nested Loop
+ -> Parallel Index Scan using tenk1_unique1 on tenk1
+ -> Function Scan on generate_series
+(7 rows)
+
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index 9c040c90e6..3ee11c394b 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -221,3 +221,34 @@ set enable_hashagg to off;
explain (costs off) select * from t union select * from t order by 1,3;
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
+-- go above joins since otherwise we'll incorrectly use expression evaluations
+-- across multiple rows.
+set enable_hashagg=off;
+set enable_seqscan=off;
+set enable_incremental_sort = off;
+set parallel_tuple_cost=0;
+set parallel_setup_cost=0;
+set min_parallel_table_scan_size = 0;
+set min_parallel_index_scan_size = 0;
+
+-- Parallel sort below join.
+explain (costs off) select distinct sub.unique1, stringu1
+from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
+explain (costs off) select sub.unique1, stringu1
+from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub
+order by 1, 2;
+-- Parallel sort but with expression that can be safely generated at the base rel.
+explain (costs off) select distinct sub.unique1, md5(stringu1)
+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 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;
+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;
--
2.17.1
From 945cb596cc0e62780994bd084eaea5355af85554 Mon Sep 17 00:00:00 2001
From: James Coleman <jtc...@gmail.com>
Date: Fri, 30 Oct 2020 19:27:13 -0400
Subject: [PATCH v6 2/3] Add comments explaining where projections aren't
necessary
---
src/backend/optimizer/plan/planner.c | 9 +++++++--
1 file changed, 7 insertions(+), 2 deletions(-)
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 986d7a52e3..6989c5c0e3 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -7414,7 +7414,9 @@ apply_scanjoin_target_to_paths(PlannerInfo *root,
* current reltarget is. We don't do this in the case where the
* target is parallel-safe, since we will be able to generate superior
* paths by doing it after the final scan/join target has been
- * applied.
+ * applied. Since the target isn't parallel safe, we don't need to
+ * apply projections to the partial paths before building gather
+ * paths.
*/
generate_useful_gather_paths(root, rel, false);
@@ -7567,7 +7569,10 @@ apply_scanjoin_target_to_paths(PlannerInfo *root,
* if the relation is parallel safe, and we don't do it for child rels to
* avoid creating multiple Gather nodes within the same plan. We must do
* this after all paths have been generated and before set_cheapest, since
- * one of the generated paths may turn out to be the cheapest one.
+ * one of the generated paths may turn out to be the cheapest one. We've
+ * already applied any necessary projections to the partial paths above so
+ * any Gather Merge paths will be able to make use of path keys in
+ * requested target.
*/
if (rel->consider_parallel && !IS_OTHER_REL(rel))
generate_useful_gather_paths(root, rel, false);
--
2.17.1
