Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
James Coleman writes: > On Mon, Apr 19, 2021 at 7:10 PM Tom Lane wrote: >> After some more testing, that seems like a good thing to do, >> so here's a v4. > This all looks good to me. Pushed, thanks for reviewing! regards, tom lane
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
ilm...@ilmari.org (Dagfinn Ilmari =?utf-8?Q?Manns=C3=A5ker?=) writes: > ilm...@ilmari.org (Dagfinn Ilmari Mannsåker) writes: >> There are 10 instances of this exact loop scattered around the codebase. >> Is it worth it turning it into a static inline function? > Something like the attached, maybe? Meh. The trouble with this is that the call sites don't all declare the pointer variable the same way. While the written-out loops can look the same regardless, a function can only accommodate one choice without messy casts. For my money, the notational savings here is small enough that the casts really discourage doing anything. So if we wanted to do this, I'd think about using a macro: #define strip_relabeltype(nodeptr) \ while (nodeptr && IsA(nodeptr, RelabelType)) nodeptr = ((RelabelType *) nodeptr)->arg ... strip_relabeltype(em_expr); ... Since the argument would have to be a variable, the usual multiple-reference hazards of using a macro don't seem to apply. (Probably the macro could do with "do ... while" decoration to discourage any syntactic oddities, but you get the idea.) regards, tom lane
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
On Tue, Apr 20, 2021 at 7:11 AM Dagfinn Ilmari Mannsåker wrote: > > ilm...@ilmari.org (Dagfinn Ilmari Mannsåker) writes: > > > Tom Lane writes: > > > >> +/* We ignore binary-compatible relabeling on both ends */ > >> +while (expr && IsA(expr, RelabelType)) > >> +expr = ((RelabelType *) expr)->arg; > > > > There are 10 instances of this exact loop scattered around the codebase. > > Is it worth it turning it into a static inline function? > > Something like the attached, maybe? I'm not opposed to this, but I think it should go in a separate thread since it's orthogonal to the bugfix there and also will confuse cfbot. James
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
ilm...@ilmari.org (Dagfinn Ilmari Mannsåker) writes:
> Tom Lane writes:
>
>> +/* We ignore binary-compatible relabeling on both ends */
>> +while (expr && IsA(expr, RelabelType))
>> +expr = ((RelabelType *) expr)->arg;
>
> There are 10 instances of this exact loop scattered around the codebase.
> Is it worth it turning it into a static inline function?
Something like the attached, maybe?
- ilmari
--
"A disappointingly low fraction of the human race is,
at any given time, on fire." - Stig Sandbeck Mathisen
>From b481a41e494f169765ee204aa17ba60c16950455 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Dagfinn=20Ilmari=20Manns=C3=A5ker?=
Date: Tue, 20 Apr 2021 12:08:46 +0100
Subject: [PATCH] Create a function for stripping RelabelType nodes off an
expression
The exact same while loop was repeated 10 times across the codebase,
which makes it smell like time to refactor.
---
contrib/postgres_fdw/postgres_fdw.c | 7 ++-
src/backend/nodes/nodeFuncs.c | 3 +--
src/backend/optimizer/path/equivclass.c | 4 +---
src/backend/optimizer/plan/createplan.c | 8 ++--
src/backend/optimizer/plan/initsplan.c | 12 +---
src/backend/optimizer/util/tlist.c | 8 ++--
src/include/nodes/nodeFuncs.h | 9 +
7 files changed, 22 insertions(+), 29 deletions(-)
diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index c590f374c6..5c45b2b087 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -7203,8 +7203,7 @@ find_em_expr_for_input_target(PlannerInfo *root,
}
/* We ignore binary-compatible relabeling on both ends */
- while (expr && IsA(expr, RelabelType))
- expr = ((RelabelType *) expr)->arg;
+ expr = (Expr *) strip_relabeltype(expr);
/* Locate an EquivalenceClass member matching this expr, if any */
foreach(lc2, ec->ec_members)
@@ -7221,9 +7220,7 @@ find_em_expr_for_input_target(PlannerInfo *root,
continue;
/* Match if same expression (after stripping relabel) */
- em_expr = em->em_expr;
- while (em_expr && IsA(em_expr, RelabelType))
-em_expr = ((RelabelType *) em_expr)->arg;
+ em_expr = (Expr *) strip_relabeltype(em->em_expr);
if (equal(em_expr, expr))
return em->em_expr;
diff --git a/src/backend/nodes/nodeFuncs.c b/src/backend/nodes/nodeFuncs.c
index ff3dcc7b18..9918a4c12e 100644
--- a/src/backend/nodes/nodeFuncs.c
+++ b/src/backend/nodes/nodeFuncs.c
@@ -587,8 +587,7 @@ applyRelabelType(Node *arg, Oid rtype, int32 rtypmod, Oid rcollid,
* all but the top one, and must do so to ensure that semantically
* equivalent expressions are equal().
*/
- while (arg && IsA(arg, RelabelType))
- arg = (Node *) ((RelabelType *) arg)->arg;
+ arg = strip_relabeltype(arg);
if (arg && IsA(arg, Const))
{
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 0188c1e9a1..2f78998a82 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -2307,9 +2307,7 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
continue; /* ignore children here */
/* EM must be a Var, possibly with RelabelType */
- var = (Var *) em->em_expr;
- while (var && IsA(var, RelabelType))
-var = (Var *) ((RelabelType *) var)->arg;
+ var = (Var *) strip_relabeltype(em->em_expr);
if (!(var && IsA(var, Var)))
continue;
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 22f10fa339..b13aa65244 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -6257,9 +6257,7 @@ find_ec_member_for_tle(EquivalenceClass *ec,
ListCell *lc;
/* We ignore binary-compatible relabeling on both ends */
- tlexpr = tle->expr;
- while (tlexpr && IsA(tlexpr, RelabelType))
- tlexpr = ((RelabelType *) tlexpr)->arg;
+ tlexpr = (Expr *) strip_relabeltype(tle->expr);
foreach(lc, ec->ec_members)
{
@@ -6281,9 +6279,7 @@ find_ec_member_for_tle(EquivalenceClass *ec,
continue;
/* Match if same expression (after stripping relabel) */
- emexpr = em->em_expr;
- while (emexpr && IsA(emexpr, RelabelType))
- emexpr = ((RelabelType *) emexpr)->arg;
+ emexpr = (Expr *) strip_relabeltype(em->em_expr);
if (equal(emexpr, tlexpr))
return em;
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index 3ac853d9ef..84805906e4 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -2566,16 +2566,14 @@ match_foreign_keys_to_quals(PlannerInfo *root)
if (!IsA(clause, OpExpr) ||
list_length(clause->args) != 2)
continue;
-leftvar = (Var *) get_leftop((Expr *) clause);
-rightvar = (Var *) get_rightop((Expr *) clause);
-/* Operands must be Vars, possibly with RelabelType */
-while (leftvar && IsA(leftvar, RelabelType))
- leftvar = (Var *)
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
Tom Lane writes: > + /* We ignore binary-compatible relabeling on both ends */ > + while (expr && IsA(expr, RelabelType)) > + expr = ((RelabelType *) expr)->arg; There are 10 instances of this exact loop scattered around the codebase. Is it worth it turning it into a static inline function? - ilmari -- - Twitter seems more influential [than blogs] in the 'gets reported in the mainstream press' sense at least. - Matt McLeod - That'd be because the content of a tweet is easier to condense down to a mainstream media article. - Calle Dybedahl
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
On Mon, Apr 19, 2021 at 7:10 PM Tom Lane wrote: > > I wrote: > > Anyway I'm now inclined to remove that behavior from > > find_computable_ec_member, and adjust comments accordingly. > > After some more testing, that seems like a good thing to do, > so here's a v4. This all looks good to me. James Coleman
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
I wrote:
> Anyway I'm now inclined to remove that behavior from
> find_computable_ec_member, and adjust comments accordingly.
After some more testing, that seems like a good thing to do,
so here's a v4.
regards, tom lane
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 0188c1e9a1..6e87fba2aa 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -35,6 +35,7 @@
static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
Expr *expr, Relids relids, Relids nullable_relids,
bool is_child, Oid datatype);
+static bool is_exprlist_member(Expr *node, List *exprs);
static void generate_base_implied_equalities_const(PlannerInfo *root,
EquivalenceClass *ec);
static void generate_base_implied_equalities_no_const(PlannerInfo *root,
@@ -769,6 +770,167 @@ get_eclass_for_sort_expr(PlannerInfo *root,
return newec;
}
+/*
+ * find_ec_member_matching_expr
+ * Locate an EquivalenceClass member matching the given expr, if any;
+ * return NULL if no match.
+ *
+ * "Matching" is defined as "equal after stripping RelabelTypes".
+ * This is used for identifying sort expressions, and we need to allow
+ * binary-compatible relabeling for some cases involving binary-compatible
+ * sort operators.
+ *
+ * Child EC members are ignored unless they belong to given 'relids'.
+ */
+EquivalenceMember *
+find_ec_member_matching_expr(EquivalenceClass *ec,
+ Expr *expr,
+ Relids relids)
+{
+ ListCell *lc;
+
+ /* We ignore binary-compatible relabeling on both ends */
+ while (expr && IsA(expr, RelabelType))
+ expr = ((RelabelType *) expr)->arg;
+
+ foreach(lc, ec->ec_members)
+ {
+ EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+ Expr *emexpr;
+
+ /*
+ * 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;
+
+ /*
+ * Ignore child members unless they belong to the requested rel.
+ */
+ if (em->em_is_child &&
+ !bms_is_subset(em->em_relids, relids))
+ continue;
+
+ /*
+ * Match if same expression (after stripping relabel).
+ */
+ emexpr = em->em_expr;
+ while (emexpr && IsA(emexpr, RelabelType))
+ emexpr = ((RelabelType *) emexpr)->arg;
+
+ if (equal(emexpr, expr))
+ return em;
+ }
+
+ return NULL;
+}
+
+/*
+ * find_computable_ec_member
+ * Locate an EquivalenceClass member that can be computed from the
+ * expressions appearing in "exprs"; return NULL if no match.
+ *
+ * "exprs" can be either a list of bare expression trees, or a list of
+ * TargetEntry nodes. Either way, it should contain Vars and possibly
+ * Aggrefs and WindowFuncs, which are matched to the corresponding elements
+ * of the EquivalenceClass's expressions.
+ *
+ * Unlike find_ec_member_matching_expr, there's no special provision here
+ * for binary-compatible relabeling. This is intentional: if we have to
+ * compute an expression in this way, setrefs.c is going to insist on exact
+ * matches of Vars to the source tlist.
+ *
+ * Child EC members are ignored unless they belong to given 'relids'.
+ * Also, non-parallel-safe expressions are ignored if 'require_parallel_safe'.
+ *
+ * Note: some callers pass root == NULL for notational reasons. This is OK
+ * when require_parallel_safe is false.
+ */
+EquivalenceMember *
+find_computable_ec_member(PlannerInfo *root,
+ EquivalenceClass *ec,
+ List *exprs,
+ Relids relids,
+ bool require_parallel_safe)
+{
+ ListCell *lc;
+
+ foreach(lc, ec->ec_members)
+ {
+ EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+ List *exprvars;
+ ListCell *lc2;
+
+ /*
+ * 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;
+
+ /*
+ * Ignore child members unless they belong to the requested rel.
+ */
+ if (em->em_is_child &&
+ !bms_is_subset(em->em_relids, relids))
+ continue;
+
+ /*
+ * Match if all Vars and quasi-Vars are available in "exprs".
+ */
+ exprvars = pull_var_clause((Node *) em->em_expr,
+ PVC_INCLUDE_AGGREGATES |
+ PVC_INCLUDE_WINDOWFUNCS |
+ PVC_INCLUDE_PLACEHOLDERS);
+ foreach(lc2, exprvars)
+ {
+ if (!is_exprlist_member(lfirst(lc2), exprs))
+break;
+ }
+ list_free(exprvars);
+ if (lc2)
+ continue; /* we hit a non-available Var */
+
+ /*
+ * If requested, reject expressions that are not parallel-safe. We
+ * check this last because it's a rather expensive test.
+ */
+ if (require_parallel_safe &&
+ !is_parallel_safe(root, (Node *) em->em_expr))
+ continue;
+
+ return em;/* found usable expression */
+ }
+
+ return NULL;
+}
+
+/*
+ * is_exprlist_member
+ * Subroutine for find_computable_ec_member: is "node" in "exprs"?
+ *
+ *
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
James Coleman writes: > Two things I wonder: > 1. Should we add tests for the relabel code path? As far as that goes, the Relabel-stripping loops in find_ec_member_matching_expr are already exercised in the core regression tests (I didn't bother to discover exactly where, but a quick coverage test run says that they're hit). The ones in exprlist_member_ignore_relabel are not iterated though. On reflection, the first loop stripping the input node is visibly unreachable by the sole caller, since everything in the exprvars list will be a Var, Aggref, WindowFunc, or PlaceHolderVar. I'm less sure about what is possible in the targetlist that we're referencing, but it strikes me that ignoring relabel on that side is probably functionally wrong: if we have say "f(textcol)" as an expression to be sorted on, but what is in the tlist is textcol::varchar or the like, I do not think setrefs.c will consider that an acceptable match. So now that's seeming like an actual bug --- although the lack of field reports suggests that it's unreachable, most likely because if we do have "f(textcol)" as a sort candidate, we'll have made sure to emit plain "textcol" from the source relation, regardless of whether there might also be a reason to emit textcol::varchar. Anyway I'm now inclined to remove that behavior from find_computable_ec_member, and adjust comments accordingly. > 2. It'd be nice not to have the IS_SRF_CALL duplicated, but that might > add enough complexity that it's not worth it. Yeah, I'd messed around with variants that put more smarts into the bottom-level functions, and decided that it wasn't a net improvement. regards, tom lane
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
I wrote: > I'm not wedded to that name, certainly, but it seems like neither > of these is quite getting at the issue. An EC can be sorted on, > by definition, but there are some things we don't want to sort > on till the final output step. I was trying to think of something > using the terminology "early sort", but didn't much like > "relation_has_early_sortable_ec_member" or obvious variants of that. ... or, as long as it's returning a boolean, maybe it could be "relation_can_be_sorted_early" ? regards, tom lane
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
James Coleman writes: > I forgot to comment on this in my previous email, but it seems to me > that relation_has_safe_ec_member, while less wordy, isn't quite > descriptive enough. Perhaps something like > relation_has_sort_safe_ec_member? I'm not wedded to that name, certainly, but it seems like neither of these is quite getting at the issue. An EC can be sorted on, by definition, but there are some things we don't want to sort on till the final output step. I was trying to think of something using the terminology "early sort", but didn't much like "relation_has_early_sortable_ec_member" or obvious variants of that. regards, tom lane
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
On Sat, Apr 17, 2021 at 3:39 PM Tom Lane wrote: > ... > Also, I don't much care for either the name or API of > find_em_expr_usable_for_sorting_rel. The sole current caller only > really needs a boolean result, and if it did need more than that > it'd likely need the whole EquivalenceMember not just the em_expr > (certainly createplan.c does). So 0002 attached is some bikeshedding > on that. I kept that separate because it might be wise to do it only > in HEAD, just in case somebody out there is calling the function from > an extension. I forgot to comment on this in my previous email, but it seems to me that relation_has_safe_ec_member, while less wordy, isn't quite descriptive enough. Perhaps something like relation_has_sort_safe_ec_member? James Coleman
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
On Sun, Apr 18, 2021 at 1:21 PM Tom Lane wrote: > > I wrote: > > I think it's time for some refactoring of this code so that we can > > actually share the logic. Accordingly, I propose the attached. > > After sleeping on it, here's an improved version that gets rid of > an unnecessary assumption about ECs usually not containing both > parallel-safe and parallel-unsafe members. I'd tried to do this > yesterday but didn't like the amount of side-effects on createplan.c > (caused by the direct call sites not being passed the "root" pointer). > However, we can avoid refactoring createplan.c APIs by saying that it's > okay to pass root = NULL to find_computable_ec_member if you're not > asking it to check parallel safety. And there's not really a need to > put a parallel-safety check into find_ec_member_matching_expr at all; > that task can be left with the one caller that cares. I like the refactoring here. Two things I wonder: 1. Should we add tests for the relabel code path? 2. It'd be nice not to have the IS_SRF_CALL duplicated, but that might add enough complexity that it's not worth it. Thanks, James Coleman
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
I wrote:
> I think it's time for some refactoring of this code so that we can
> actually share the logic. Accordingly, I propose the attached.
After sleeping on it, here's an improved version that gets rid of
an unnecessary assumption about ECs usually not containing both
parallel-safe and parallel-unsafe members. I'd tried to do this
yesterday but didn't like the amount of side-effects on createplan.c
(caused by the direct call sites not being passed the "root" pointer).
However, we can avoid refactoring createplan.c APIs by saying that it's
okay to pass root = NULL to find_computable_ec_member if you're not
asking it to check parallel safety. And there's not really a need to
put a parallel-safety check into find_ec_member_matching_expr at all;
that task can be left with the one caller that cares.
regards, tom lane
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 0188c1e9a1..6627491519 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -35,6 +35,7 @@
static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
Expr *expr, Relids relids, Relids nullable_relids,
bool is_child, Oid datatype);
+static bool exprlist_member_ignore_relabel(Expr *node, List *exprs);
static void generate_base_implied_equalities_const(PlannerInfo *root,
EquivalenceClass *ec);
static void generate_base_implied_equalities_no_const(PlannerInfo *root,
@@ -769,6 +770,169 @@ get_eclass_for_sort_expr(PlannerInfo *root,
return newec;
}
+/*
+ * find_ec_member_matching_expr
+ * Locate an EquivalenceClass member matching the given expr, if any;
+ * return NULL if no match.
+ *
+ * "Matching" is defined as "equal after stripping RelabelTypes".
+ * This is used for identifying sort expressions, and we need to allow
+ * binary-compatible relabeling for some cases involving binary-compatible
+ * sort operators.
+ *
+ * Child EC members are ignored unless they belong to given 'relids'.
+ */
+EquivalenceMember *
+find_ec_member_matching_expr(EquivalenceClass *ec,
+ Expr *expr,
+ Relids relids)
+{
+ ListCell *lc;
+
+ /* We ignore binary-compatible relabeling on both ends */
+ while (expr && IsA(expr, RelabelType))
+ expr = ((RelabelType *) expr)->arg;
+
+ foreach(lc, ec->ec_members)
+ {
+ EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+ Expr *emexpr;
+
+ /*
+ * 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;
+
+ /*
+ * Ignore child members unless they belong to the requested rel.
+ */
+ if (em->em_is_child &&
+ !bms_is_subset(em->em_relids, relids))
+ continue;
+
+ /*
+ * Match if same expression (after stripping relabel).
+ */
+ emexpr = em->em_expr;
+ while (emexpr && IsA(emexpr, RelabelType))
+ emexpr = ((RelabelType *) emexpr)->arg;
+
+ if (equal(emexpr, expr))
+ return em;
+ }
+
+ return NULL;
+}
+
+/*
+ * find_computable_ec_member
+ * Locate an EquivalenceClass member that can be computed from the
+ * expressions appearing in "exprs"; return NULL if no match.
+ *
+ * "exprs" can be either a list of bare expression trees, or a list of
+ * TargetEntry nodes. Either way, it should contain Vars and possibly
+ * Aggrefs and WindowFuncs, which are matched to the corresponding elements
+ * of the EquivalenceClass's expressions. As in find_ec_member_matching_expr,
+ * we ignore binary-compatible relabeling.
+ *
+ * Child EC members are ignored unless they belong to given 'relids'.
+ * Also, non-parallel-safe expressions are ignored if 'require_parallel_safe'.
+ *
+ * Note: some callers pass root == NULL for notational reasons. This is OK
+ * when require_parallel_safe is false.
+ */
+EquivalenceMember *
+find_computable_ec_member(PlannerInfo *root,
+ EquivalenceClass *ec,
+ List *exprs,
+ Relids relids,
+ bool require_parallel_safe)
+{
+ ListCell *lc;
+
+ foreach(lc, ec->ec_members)
+ {
+ EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+ List *exprvars;
+ ListCell *lc2;
+
+ /*
+ * 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;
+
+ /*
+ * Ignore child members unless they belong to the requested rel.
+ */
+ if (em->em_is_child &&
+ !bms_is_subset(em->em_relids, relids))
+ continue;
+
+ /*
+ * Match if all Vars and quasi-Vars are available in "exprs".
+ */
+ exprvars = pull_var_clause((Node *) em->em_expr,
+ PVC_INCLUDE_AGGREGATES |
+ PVC_INCLUDE_WINDOWFUNCS |
+ PVC_INCLUDE_PLACEHOLDERS);
+ foreach(lc2, exprvars)
+ {
+ if (!exprlist_member_ignore_relabel(lfirst(lc2), exprs))
+break;
+ }
+ list_free(exprvars);
+ if (lc2)
+ continue; /* we hit a
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
[ sorry for not getting to this thread till now ]
Tomas Vondra writes:
> 3) Shouldn't find_em_expr_usable_for_sorting_rel now mostly mimic what
> prepare_sort_from_pathkeys does? That is, try to match the entries
> directly first, before the new pull_vars() business?
Yeah. I concur that the problem here is that
find_em_expr_usable_for_sorting_rel isn't fully accounting for what
prepare_sort_from_pathkeys can and can't do. However, I don't like this
patch much:
* As written, I think it may just move the pain somewhere else. The point
of the logic in prepare_sort_from_pathkeys is to handle either full
expression matches (e.g. sort by "A+B" when "A+B" is an expression in
the input tlist) or computable expressions (sort by "A+B" when A and B
are individually available). I think you've fixed the second case and
broken the first one. Now it's possible that the case never arises,
and certainly failing to generate an early sort isn't catastrophic anyway.
But we ought to get it right.
* If the goal is to match what prepare_sort_from_pathkeys can do, I
think that doubling down on the strategy of having a duplicate copy
is not the path to a maintainable fix.
I think it's time for some refactoring of this code so that we can
actually share the logic. Accordingly, I propose the attached.
It's really not that hard to share, as long as you accept the idea
that the list passed to the shared subroutine can be either a list of
TargetEntries or of bare expressions.
Also, I don't much care for either the name or API of
find_em_expr_usable_for_sorting_rel. The sole current caller only
really needs a boolean result, and if it did need more than that
it'd likely need the whole EquivalenceMember not just the em_expr
(certainly createplan.c does). So 0002 attached is some bikeshedding
on that. I kept that separate because it might be wise to do it only
in HEAD, just in case somebody out there is calling the function from
an extension.
(BTW, responding to an upthread question: I think the looping to
remove multiple levels of RelabelType is probably now redundant,
but I didn't remove it. If we want to do that there are more
places to touch than just this code.)
regards, tom lane
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 0188c1e9a1..5f7e505950 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -35,6 +35,7 @@
static EquivalenceMember *add_eq_member(EquivalenceClass *ec,
Expr *expr, Relids relids, Relids nullable_relids,
bool is_child, Oid datatype);
+static bool exprlist_member_ignore_relabel(Expr *node, List *exprs);
static void generate_base_implied_equalities_const(PlannerInfo *root,
EquivalenceClass *ec);
static void generate_base_implied_equalities_no_const(PlannerInfo *root,
@@ -769,6 +770,149 @@ get_eclass_for_sort_expr(PlannerInfo *root,
return newec;
}
+/*
+ * find_ec_member_matching_expr
+ * Locate an EquivalenceClass member matching the given expr, if any;
+ * return NULL if no match.
+ *
+ * "Matching" is defined as "equal after stripping RelabelTypes".
+ * This is used for identifying sort expressions, and we need to allow
+ * binary-compatible relabeling for some cases involving binary-compatible
+ * sort operators.
+ *
+ * Child EC members are ignored unless they belong to given 'relids'.
+ */
+EquivalenceMember *
+find_ec_member_matching_expr(EquivalenceClass *ec,
+ Expr *expr,
+ Relids relids)
+{
+ ListCell *lc;
+
+ /* We ignore binary-compatible relabeling on both ends */
+ while (expr && IsA(expr, RelabelType))
+ expr = ((RelabelType *) expr)->arg;
+
+ foreach(lc, ec->ec_members)
+ {
+ EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
+ Expr *emexpr;
+
+ /*
+ * 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;
+
+ /*
+ * Ignore child members unless they belong to the requested rel.
+ */
+ if (em->em_is_child &&
+ !bms_is_subset(em->em_relids, relids))
+ continue;
+
+ /* Match if same expression (after stripping relabel) */
+ emexpr = em->em_expr;
+ while (emexpr && IsA(emexpr, RelabelType))
+ emexpr = ((RelabelType *) emexpr)->arg;
+
+ if (equal(emexpr, expr))
+ return em;
+ }
+
+ return NULL;
+}
+
+/*
+ * find_computable_ec_member
+ * Locate an EquivalenceClass member that can be computed from the
+ * expressions appearing in "exprs"; return NULL if no match.
+ *
+ * "exprs" can be either a list of bare expression trees, or a list of
+ * TargetEntry nodes. Either way, it should contain Vars and possibly
+ * Aggrefs and WindowFuncs, which are matched to the corresponding elements
+ * of the EquivalenceClass's expressions. As in find_ec_member_matching_expr,
+ * we ignore binary-compatible relabeling.
+ *
+ * Child EC members are ignored
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
On Thu, Apr 15, 2021 at 6:27 PM Tomas Vondra wrote: > > > On 4/15/21 7:35 PM, James Coleman wrote: > > On Thu, Apr 15, 2021 at 5:33 AM Luc Vlaming wrote: > >> > >> On 15-04-2021 04:01, James Coleman wrote: > >>> On Wed, Apr 14, 2021 at 5:42 PM James Coleman > wrote: > > On Mon, Apr 12, 2021 at 8:37 AM Tomas Vondra > wrote: > > > > On 4/12/21 2:24 PM, Luc Vlaming wrote: > >> Hi, > >> > >> When trying to run on master (but afaik also PG-13) TPC-DS queries > 94, > >> 95 and 96 on a SF10 I get the error "could not find pathkey item to > sort". > >> When I disable enable_gathermerge the problem goes away and then the > >> plan for query 94 looks like below. I tried figuring out what the > >> problem is but to be honest I would need some pointers as the code > that > >> tries to matching equivalence members in prepare_sort_from_pathkeys > is > >> something i'm really not familiar with. > >> > > > > Could be related to incremental sort, which allowed some gather merge > > paths that were impossible before. We had a couple issues related to > > that fixed in November, IIRC. > > > >> To reproduce you can either ingest and test using the toolkit I > used too > >> (see https://github.com/swarm64/s64da-benchmark-toolkit/), or > >> alternatively just use the schema (see > >> > https://github.com/swarm64/s64da-benchmark-toolkit/tree/master/benchmarks/tpcds/schemas/psql_native > ) > >> > > > > Thanks, I'll see if I can reproduce that with your schema. > > > > > > regards > > > > -- > > Tomas Vondra > > EnterpriseDB: http://www.enterprisedb.com > > The Enterprise PostgreSQL Company > > The query in question is: > > select count(*) > from store_sales > ,household_demographics > ,time_dim, store > where ss_sold_time_sk = time_dim.t_time_sk > and ss_hdemo_sk = household_demographics.hd_demo_sk > and ss_store_sk = s_store_sk > and time_dim.t_hour = 15 > and time_dim.t_minute >= 30 > and household_demographics.hd_dep_count = 7 > and store.s_store_name = 'ese' > order by count(*) > limit 100; > > From debugging output it looks like this is the plan being chosen > (cheapest total path): > Gather(store_sales household_demographics time_dim) > rows=60626 > cost=3145.73..699910.15 > HashJoin(store_sales household_demographics time_dim) > rows=25261 cost=2145.73..692847.55 > clauses: store_sales.ss_hdemo_sk = > household_demographics.hd_demo_sk > HashJoin(store_sales time_dim) rows=252609 > cost=1989.73..692028.08 > clauses: store_sales.ss_sold_time_sk = > time_dim.t_time_sk > SeqScan(store_sales) rows=11998564 > cost=0.00..658540.64 > SeqScan(time_dim) rows=1070 > cost=0.00..1976.35 > SeqScan(household_demographics) rows=720 > cost=0.00..147.00 > > prepare_sort_from_pathkeys fails to find a pathkey because > tlist_member_ignore_relabel returns null -- which seemed weird because > the sortexpr is an Aggref (in a single member equivalence class) and > the tlist contains a single member that's also an Aggref. It turns out > that the only difference between the two Aggrefs is that the tlist > entry has "aggsplit = AGGSPLIT_INITIAL_SERIAL" while the sortexpr has > aggsplit = AGGSPLIT_SIMPLE. > > That's as far as I've gotten so far, but I figured I'd get that info > out to see if it means anything obvious to anyone else. > >>> > >>> This really goes back to [1] where we fixed a similar issue by making > >>> find_em_expr_usable_for_sorting_rel parallel the rules in > >>> prepare_sort_from_pathkeys. > >>> > >>> Most of those conditions got copied, and the case we were trying to > >>> handle is the fact that prepare_sort_from_pathkeys can generate a > >>> target list entry under those conditions if one doesn't exist. However > >>> there's a further restriction there I don't remember looking at: it > >>> uses pull_var_clause and tlist_member_ignore_relabel to ensure that > >>> all of the vars that feed into the sort expression are found in the > >>> target list. As I understand it, that is: it will build a target list > >>> entry for something like "md5(column)" if "column" (and that was one > >>> of our test cases for the previous fix) is in the target list already. > >>> > >>> But there's an additional detail here: the call to pull_var_clause > >>> requests aggregates, window functions, and placeholders be treated as > >>> vars. That means for
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
On 4/15/21 7:35 PM, James Coleman wrote: > On Thu, Apr 15, 2021 at 5:33 AM Luc Vlaming wrote: >> >> On 15-04-2021 04:01, James Coleman wrote: >>> On Wed, Apr 14, 2021 at 5:42 PM James Coleman wrote: On Mon, Apr 12, 2021 at 8:37 AM Tomas Vondra wrote: > > On 4/12/21 2:24 PM, Luc Vlaming wrote: >> Hi, >> >> When trying to run on master (but afaik also PG-13) TPC-DS queries 94, >> 95 and 96 on a SF10 I get the error "could not find pathkey item to >> sort". >> When I disable enable_gathermerge the problem goes away and then the >> plan for query 94 looks like below. I tried figuring out what the >> problem is but to be honest I would need some pointers as the code that >> tries to matching equivalence members in prepare_sort_from_pathkeys is >> something i'm really not familiar with. >> > > Could be related to incremental sort, which allowed some gather merge > paths that were impossible before. We had a couple issues related to > that fixed in November, IIRC. > >> To reproduce you can either ingest and test using the toolkit I used too >> (see https://github.com/swarm64/s64da-benchmark-toolkit/), or >> alternatively just use the schema (see >> https://github.com/swarm64/s64da-benchmark-toolkit/tree/master/benchmarks/tpcds/schemas/psql_native) >> > > Thanks, I'll see if I can reproduce that with your schema. > > > regards > > -- > Tomas Vondra > EnterpriseDB: http://www.enterprisedb.com > The Enterprise PostgreSQL Company The query in question is: select count(*) from store_sales ,household_demographics ,time_dim, store where ss_sold_time_sk = time_dim.t_time_sk and ss_hdemo_sk = household_demographics.hd_demo_sk and ss_store_sk = s_store_sk and time_dim.t_hour = 15 and time_dim.t_minute >= 30 and household_demographics.hd_dep_count = 7 and store.s_store_name = 'ese' order by count(*) limit 100; From debugging output it looks like this is the plan being chosen (cheapest total path): Gather(store_sales household_demographics time_dim) rows=60626 cost=3145.73..699910.15 HashJoin(store_sales household_demographics time_dim) rows=25261 cost=2145.73..692847.55 clauses: store_sales.ss_hdemo_sk = household_demographics.hd_demo_sk HashJoin(store_sales time_dim) rows=252609 cost=1989.73..692028.08 clauses: store_sales.ss_sold_time_sk = time_dim.t_time_sk SeqScan(store_sales) rows=11998564 cost=0.00..658540.64 SeqScan(time_dim) rows=1070 cost=0.00..1976.35 SeqScan(household_demographics) rows=720 cost=0.00..147.00 prepare_sort_from_pathkeys fails to find a pathkey because tlist_member_ignore_relabel returns null -- which seemed weird because the sortexpr is an Aggref (in a single member equivalence class) and the tlist contains a single member that's also an Aggref. It turns out that the only difference between the two Aggrefs is that the tlist entry has "aggsplit = AGGSPLIT_INITIAL_SERIAL" while the sortexpr has aggsplit = AGGSPLIT_SIMPLE. That's as far as I've gotten so far, but I figured I'd get that info out to see if it means anything obvious to anyone else. >>> >>> This really goes back to [1] where we fixed a similar issue by making >>> find_em_expr_usable_for_sorting_rel parallel the rules in >>> prepare_sort_from_pathkeys. >>> >>> Most of those conditions got copied, and the case we were trying to >>> handle is the fact that prepare_sort_from_pathkeys can generate a >>> target list entry under those conditions if one doesn't exist. However >>> there's a further restriction there I don't remember looking at: it >>> uses pull_var_clause and tlist_member_ignore_relabel to ensure that >>> all of the vars that feed into the sort expression are found in the >>> target list. As I understand it, that is: it will build a target list >>> entry for something like "md5(column)" if "column" (and that was one >>> of our test cases for the previous fix) is in the target list already. >>> >>> But there's an additional detail here: the call to pull_var_clause >>> requests aggregates, window functions, and placeholders be treated as >>> vars. That means for our Aggref case it would require that the two >>> Aggrefs be fully equal, so the differing aggsplit member would cause a >>> target list entry not to be built, hence our error here. >>> >>> I've attached a quick and dirty patch that encodes that final rule >>> from
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
On 4/15/21 2:21 AM, Robert Haas wrote: > On Wed, Apr 14, 2021 at 8:20 PM James Coleman wrote: >>> Hmm, could be. Although, the stack trace at issue doesn't seem to show >>> a call to create_incrementalsort_plan(). >> >> The changes to gather merge path generation made it possible to use >> those paths in more cases for both incremental sort and regular sort, >> so by "incremental sort" I read Tomas as saying "the patches that >> brought in incremental sort" not specifically "incremental sort >> itself". > > I agree. That's why I said "hmm, could be" even though the plan > doesn't involve one. > Yeah, that's what I meant. The difference to pre-13 behavior is that we now call generate_useful_gather_paths, which also considers adding extra sort (unlike plain generate_gather_paths). So now we can end up with "Gather Merge -> Sort" paths that would not be considered before. regards -- Tomas Vondra EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
On Thu, Apr 15, 2021 at 5:33 AM Luc Vlaming wrote: > > On 15-04-2021 04:01, James Coleman wrote: > > On Wed, Apr 14, 2021 at 5:42 PM James Coleman wrote: > >> > >> On Mon, Apr 12, 2021 at 8:37 AM Tomas Vondra > >> wrote: > >>> > >>> On 4/12/21 2:24 PM, Luc Vlaming wrote: > Hi, > > When trying to run on master (but afaik also PG-13) TPC-DS queries 94, > 95 and 96 on a SF10 I get the error "could not find pathkey item to > sort". > When I disable enable_gathermerge the problem goes away and then the > plan for query 94 looks like below. I tried figuring out what the > problem is but to be honest I would need some pointers as the code that > tries to matching equivalence members in prepare_sort_from_pathkeys is > something i'm really not familiar with. > > >>> > >>> Could be related to incremental sort, which allowed some gather merge > >>> paths that were impossible before. We had a couple issues related to > >>> that fixed in November, IIRC. > >>> > To reproduce you can either ingest and test using the toolkit I used too > (see https://github.com/swarm64/s64da-benchmark-toolkit/), or > alternatively just use the schema (see > https://github.com/swarm64/s64da-benchmark-toolkit/tree/master/benchmarks/tpcds/schemas/psql_native) > > >>> > >>> Thanks, I'll see if I can reproduce that with your schema. > >>> > >>> > >>> regards > >>> > >>> -- > >>> Tomas Vondra > >>> EnterpriseDB: http://www.enterprisedb.com > >>> The Enterprise PostgreSQL Company > >> > >> The query in question is: > >> > >> select count(*) > >> from store_sales > >> ,household_demographics > >> ,time_dim, store > >> where ss_sold_time_sk = time_dim.t_time_sk > >> and ss_hdemo_sk = household_demographics.hd_demo_sk > >> and ss_store_sk = s_store_sk > >> and time_dim.t_hour = 15 > >> and time_dim.t_minute >= 30 > >> and household_demographics.hd_dep_count = 7 > >> and store.s_store_name = 'ese' > >> order by count(*) > >> limit 100; > >> > >> From debugging output it looks like this is the plan being chosen > >> (cheapest total path): > >> Gather(store_sales household_demographics time_dim) rows=60626 > >> cost=3145.73..699910.15 > >> HashJoin(store_sales household_demographics time_dim) > >> rows=25261 cost=2145.73..692847.55 > >>clauses: store_sales.ss_hdemo_sk = > >> household_demographics.hd_demo_sk > >> HashJoin(store_sales time_dim) rows=252609 > >> cost=1989.73..692028.08 > >>clauses: store_sales.ss_sold_time_sk = > >> time_dim.t_time_sk > >> SeqScan(store_sales) rows=11998564 > >> cost=0.00..658540.64 > >> SeqScan(time_dim) rows=1070 > >> cost=0.00..1976.35 > >> SeqScan(household_demographics) rows=720 > >> cost=0.00..147.00 > >> > >> prepare_sort_from_pathkeys fails to find a pathkey because > >> tlist_member_ignore_relabel returns null -- which seemed weird because > >> the sortexpr is an Aggref (in a single member equivalence class) and > >> the tlist contains a single member that's also an Aggref. It turns out > >> that the only difference between the two Aggrefs is that the tlist > >> entry has "aggsplit = AGGSPLIT_INITIAL_SERIAL" while the sortexpr has > >> aggsplit = AGGSPLIT_SIMPLE. > >> > >> That's as far as I've gotten so far, but I figured I'd get that info > >> out to see if it means anything obvious to anyone else. > > > > This really goes back to [1] where we fixed a similar issue by making > > find_em_expr_usable_for_sorting_rel parallel the rules in > > prepare_sort_from_pathkeys. > > > > Most of those conditions got copied, and the case we were trying to > > handle is the fact that prepare_sort_from_pathkeys can generate a > > target list entry under those conditions if one doesn't exist. However > > there's a further restriction there I don't remember looking at: it > > uses pull_var_clause and tlist_member_ignore_relabel to ensure that > > all of the vars that feed into the sort expression are found in the > > target list. As I understand it, that is: it will build a target list > > entry for something like "md5(column)" if "column" (and that was one > > of our test cases for the previous fix) is in the target list already. > > > > But there's an additional detail here: the call to pull_var_clause > > requests aggregates, window functions, and placeholders be treated as > > vars. That means for our Aggref case it would require that the two > > Aggrefs be fully equal, so the differing aggsplit member would cause a > > target list entry not to be built, hence our error here. > > > > I've attached a quick and dirty patch that encodes that final rule > > from prepare_sort_from_pathkeys into > >
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
On 15-04-2021 04:01, James Coleman wrote: On Wed, Apr 14, 2021 at 5:42 PM James Coleman wrote: On Mon, Apr 12, 2021 at 8:37 AM Tomas Vondra wrote: On 4/12/21 2:24 PM, Luc Vlaming wrote: Hi, When trying to run on master (but afaik also PG-13) TPC-DS queries 94, 95 and 96 on a SF10 I get the error "could not find pathkey item to sort". When I disable enable_gathermerge the problem goes away and then the plan for query 94 looks like below. I tried figuring out what the problem is but to be honest I would need some pointers as the code that tries to matching equivalence members in prepare_sort_from_pathkeys is something i'm really not familiar with. Could be related to incremental sort, which allowed some gather merge paths that were impossible before. We had a couple issues related to that fixed in November, IIRC. To reproduce you can either ingest and test using the toolkit I used too (see https://github.com/swarm64/s64da-benchmark-toolkit/), or alternatively just use the schema (see https://github.com/swarm64/s64da-benchmark-toolkit/tree/master/benchmarks/tpcds/schemas/psql_native) Thanks, I'll see if I can reproduce that with your schema. regards -- Tomas Vondra EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company The query in question is: select count(*) from store_sales ,household_demographics ,time_dim, store where ss_sold_time_sk = time_dim.t_time_sk and ss_hdemo_sk = household_demographics.hd_demo_sk and ss_store_sk = s_store_sk and time_dim.t_hour = 15 and time_dim.t_minute >= 30 and household_demographics.hd_dep_count = 7 and store.s_store_name = 'ese' order by count(*) limit 100; From debugging output it looks like this is the plan being chosen (cheapest total path): Gather(store_sales household_demographics time_dim) rows=60626 cost=3145.73..699910.15 HashJoin(store_sales household_demographics time_dim) rows=25261 cost=2145.73..692847.55 clauses: store_sales.ss_hdemo_sk = household_demographics.hd_demo_sk HashJoin(store_sales time_dim) rows=252609 cost=1989.73..692028.08 clauses: store_sales.ss_sold_time_sk = time_dim.t_time_sk SeqScan(store_sales) rows=11998564 cost=0.00..658540.64 SeqScan(time_dim) rows=1070 cost=0.00..1976.35 SeqScan(household_demographics) rows=720 cost=0.00..147.00 prepare_sort_from_pathkeys fails to find a pathkey because tlist_member_ignore_relabel returns null -- which seemed weird because the sortexpr is an Aggref (in a single member equivalence class) and the tlist contains a single member that's also an Aggref. It turns out that the only difference between the two Aggrefs is that the tlist entry has "aggsplit = AGGSPLIT_INITIAL_SERIAL" while the sortexpr has aggsplit = AGGSPLIT_SIMPLE. That's as far as I've gotten so far, but I figured I'd get that info out to see if it means anything obvious to anyone else. This really goes back to [1] where we fixed a similar issue by making find_em_expr_usable_for_sorting_rel parallel the rules in prepare_sort_from_pathkeys. Most of those conditions got copied, and the case we were trying to handle is the fact that prepare_sort_from_pathkeys can generate a target list entry under those conditions if one doesn't exist. However there's a further restriction there I don't remember looking at: it uses pull_var_clause and tlist_member_ignore_relabel to ensure that all of the vars that feed into the sort expression are found in the target list. As I understand it, that is: it will build a target list entry for something like "md5(column)" if "column" (and that was one of our test cases for the previous fix) is in the target list already. But there's an additional detail here: the call to pull_var_clause requests aggregates, window functions, and placeholders be treated as vars. That means for our Aggref case it would require that the two Aggrefs be fully equal, so the differing aggsplit member would cause a target list entry not to be built, hence our error here. I've attached a quick and dirty patch that encodes that final rule from prepare_sort_from_pathkeys into find_em_expr_usable_for_sorting_rel. I can't help but think that there's a cleaner way to do with this with less code duplication, but hindering that is that prepare_sort_from_pathkeys is working with a TargetList while find_em_expr_usable_for_sorting_rel is working with a list of expressions. James 1: https://www.postgresql.org/message-id/CAAaqYe9C3f6A_tZCRfr9Dm7hPpgGwpp4i-K_%3DNS9GWXuNiFANg%40mail.gmail.com Hi, The patch seems to make the planner proceed and not error out anymore. Cannot judge if it's doing the right thing however or if its enough :) It works for me for all reported
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
On Wed, Apr 14, 2021 at 5:42 PM James Coleman wrote: > > On Mon, Apr 12, 2021 at 8:37 AM Tomas Vondra > wrote: > > > > On 4/12/21 2:24 PM, Luc Vlaming wrote: > > > Hi, > > > > > > When trying to run on master (but afaik also PG-13) TPC-DS queries 94, > > > 95 and 96 on a SF10 I get the error "could not find pathkey item to sort". > > > When I disable enable_gathermerge the problem goes away and then the > > > plan for query 94 looks like below. I tried figuring out what the > > > problem is but to be honest I would need some pointers as the code that > > > tries to matching equivalence members in prepare_sort_from_pathkeys is > > > something i'm really not familiar with. > > > > > > > Could be related to incremental sort, which allowed some gather merge > > paths that were impossible before. We had a couple issues related to > > that fixed in November, IIRC. > > > > > To reproduce you can either ingest and test using the toolkit I used too > > > (see https://github.com/swarm64/s64da-benchmark-toolkit/), or > > > alternatively just use the schema (see > > > https://github.com/swarm64/s64da-benchmark-toolkit/tree/master/benchmarks/tpcds/schemas/psql_native) > > > > > > > Thanks, I'll see if I can reproduce that with your schema. > > > > > > regards > > > > -- > > Tomas Vondra > > EnterpriseDB: http://www.enterprisedb.com > > The Enterprise PostgreSQL Company > > The query in question is: > > select count(*) > from store_sales > ,household_demographics > ,time_dim, store > where ss_sold_time_sk = time_dim.t_time_sk > and ss_hdemo_sk = household_demographics.hd_demo_sk > and ss_store_sk = s_store_sk > and time_dim.t_hour = 15 > and time_dim.t_minute >= 30 > and household_demographics.hd_dep_count = 7 > and store.s_store_name = 'ese' > order by count(*) > limit 100; > > From debugging output it looks like this is the plan being chosen > (cheapest total path): > Gather(store_sales household_demographics time_dim) rows=60626 > cost=3145.73..699910.15 > HashJoin(store_sales household_demographics time_dim) > rows=25261 cost=2145.73..692847.55 > clauses: store_sales.ss_hdemo_sk = > household_demographics.hd_demo_sk > HashJoin(store_sales time_dim) rows=252609 > cost=1989.73..692028.08 > clauses: store_sales.ss_sold_time_sk = > time_dim.t_time_sk > SeqScan(store_sales) rows=11998564 > cost=0.00..658540.64 > SeqScan(time_dim) rows=1070 > cost=0.00..1976.35 > SeqScan(household_demographics) rows=720 > cost=0.00..147.00 > > prepare_sort_from_pathkeys fails to find a pathkey because > tlist_member_ignore_relabel returns null -- which seemed weird because > the sortexpr is an Aggref (in a single member equivalence class) and > the tlist contains a single member that's also an Aggref. It turns out > that the only difference between the two Aggrefs is that the tlist > entry has "aggsplit = AGGSPLIT_INITIAL_SERIAL" while the sortexpr has > aggsplit = AGGSPLIT_SIMPLE. > > That's as far as I've gotten so far, but I figured I'd get that info > out to see if it means anything obvious to anyone else. This really goes back to [1] where we fixed a similar issue by making find_em_expr_usable_for_sorting_rel parallel the rules in prepare_sort_from_pathkeys. Most of those conditions got copied, and the case we were trying to handle is the fact that prepare_sort_from_pathkeys can generate a target list entry under those conditions if one doesn't exist. However there's a further restriction there I don't remember looking at: it uses pull_var_clause and tlist_member_ignore_relabel to ensure that all of the vars that feed into the sort expression are found in the target list. As I understand it, that is: it will build a target list entry for something like "md5(column)" if "column" (and that was one of our test cases for the previous fix) is in the target list already. But there's an additional detail here: the call to pull_var_clause requests aggregates, window functions, and placeholders be treated as vars. That means for our Aggref case it would require that the two Aggrefs be fully equal, so the differing aggsplit member would cause a target list entry not to be built, hence our error here. I've attached a quick and dirty patch that encodes that final rule from prepare_sort_from_pathkeys into find_em_expr_usable_for_sorting_rel. I can't help but think that there's a cleaner way to do with this with less code duplication, but hindering that is that prepare_sort_from_pathkeys is working with a TargetList while find_em_expr_usable_for_sorting_rel is working with a list of expressions. James 1: https://www.postgresql.org/message-id/CAAaqYe9C3f6A_tZCRfr9Dm7hPpgGwpp4i-K_%3DNS9GWXuNiFANg%40mail.gmail.com
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
On Wed, Apr 14, 2021 at 8:21 PM Robert Haas wrote: > > On Wed, Apr 14, 2021 at 5:43 PM James Coleman wrote: > > The query in question is: > > select count(*) > > from store_sales > > ,household_demographics > > ,time_dim, store > > where ss_sold_time_sk = time_dim.t_time_sk > > and ss_hdemo_sk = household_demographics.hd_demo_sk > > and ss_store_sk = s_store_sk > > and time_dim.t_hour = 15 > > and time_dim.t_minute >= 30 > > and household_demographics.hd_dep_count = 7 > > and store.s_store_name = 'ese' > > order by count(*) > > limit 100; > > > > From debugging output it looks like this is the plan being chosen > > (cheapest total path): > > Gather(store_sales household_demographics time_dim) rows=60626 > > cost=3145.73..699910.15 > > HashJoin(store_sales household_demographics time_dim) > > rows=25261 cost=2145.73..692847.55 > > clauses: store_sales.ss_hdemo_sk = > > household_demographics.hd_demo_sk > > HashJoin(store_sales time_dim) rows=252609 > > cost=1989.73..692028.08 > > clauses: store_sales.ss_sold_time_sk = > > time_dim.t_time_sk > > SeqScan(store_sales) rows=11998564 > > cost=0.00..658540.64 > > SeqScan(time_dim) rows=1070 > > cost=0.00..1976.35 > > SeqScan(household_demographics) rows=720 > > cost=0.00..147.00 > > This doesn't really make sense to me given the strack trace in the OP. > That seems to go Limit -> Sort -> Agg -> NestLoop -> NestLoop -> > NestLoop -> GatherMerge -> Sort. If the plan were as you have it here, > there would be no Sort and no Gather Merge, so where would be getting > a failure related to pathkeys? Also I just realized why this didn't make sense -- I'm not sure what the above path is. It'd gotten logged as part of the debug options I have configured, but it must be 1.) incomplete (perhaps at a lower level of path generation) and/or not the final path selected. My apologies for the confusion. James
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
On Wed, Apr 14, 2021 at 8:21 PM Robert Haas wrote: > > On Wed, Apr 14, 2021 at 5:43 PM James Coleman wrote: > > The query in question is: > > select count(*) > > from store_sales > > ,household_demographics > > ,time_dim, store > > where ss_sold_time_sk = time_dim.t_time_sk > > and ss_hdemo_sk = household_demographics.hd_demo_sk > > and ss_store_sk = s_store_sk > > and time_dim.t_hour = 15 > > and time_dim.t_minute >= 30 > > and household_demographics.hd_dep_count = 7 > > and store.s_store_name = 'ese' > > order by count(*) > > limit 100; > > > > From debugging output it looks like this is the plan being chosen > > (cheapest total path): > > Gather(store_sales household_demographics time_dim) rows=60626 > > cost=3145.73..699910.15 > > HashJoin(store_sales household_demographics time_dim) > > rows=25261 cost=2145.73..692847.55 > > clauses: store_sales.ss_hdemo_sk = > > household_demographics.hd_demo_sk > > HashJoin(store_sales time_dim) rows=252609 > > cost=1989.73..692028.08 > > clauses: store_sales.ss_sold_time_sk = > > time_dim.t_time_sk > > SeqScan(store_sales) rows=11998564 > > cost=0.00..658540.64 > > SeqScan(time_dim) rows=1070 > > cost=0.00..1976.35 > > SeqScan(household_demographics) rows=720 > > cost=0.00..147.00 > > This doesn't really make sense to me given the strack trace in the OP. > That seems to go Limit -> Sort -> Agg -> NestLoop -> NestLoop -> > NestLoop -> GatherMerge -> Sort. If the plan were as you have it here, > there would be no Sort and no Gather Merge, so where would be getting > a failure related to pathkeys? Ah, yeah, I'm not sure where the original stacktrace came from, but here's the stack for the query I reproduced it with (perhaps it does so on different queries or there was some other GUC change in the reported plan): #0 errfinish (filename=filename@entry=0x56416eefa845 "createplan.c", lineno=lineno@entry=6186, funcname=funcname@entry=0x56416eefb660 <__func__.24872> "prepare_sort_from_pathkeys") at elog.c:514 #1 0x56416eb6ed52 in prepare_sort_from_pathkeys (lefttree=0x564170552658, pathkeys=0x5641704f2640, relids=0x0, reqColIdx=reqColIdx@entry=0x0, adjust_tlist_in_place=adjust_tlist_in_place@entry=false, p_numsortkeys=p_numsortkeys@entry=0x7fff1252817c, p_sortColIdx=0x7fff12528170, p_sortOperators=0x7fff12528168, p_collations=0x7fff12528160, p_nullsFirst=0x7fff12528158) at createplan.c:6186 #2 0x56416eb6ee69 in make_sort_from_pathkeys (lefttree=, pathkeys=, relids=) at createplan.c:6313 #3 0x56416eb71fc7 in create_sort_plan (root=root@entry=0x564170511a70, best_path=best_path@entry=0x56417054f650, flags=flags@entry=1) at createplan.c:2118 #4 0x56416eb6f638 in create_plan_recurse (root=root@entry=0x564170511a70, best_path=0x56417054f650, flags=flags@entry=1) at createplan.c:489 #5 0x56416eb72e06 in create_gather_merge_plan (root=root@entry=0x564170511a70, best_path=best_path@entry=0x56417054f6e8) at createplan.c:1885 #6 0x56416eb6f723 in create_plan_recurse (root=root@entry=0x564170511a70, best_path=0x56417054f6e8, flags=flags@entry=4) at createplan.c:541 #7 0x56416eb726fb in create_agg_plan (root=root@entry=0x564170511a70, best_path=best_path@entry=0x56417054f8c8) at createplan.c:2238 #8 0x56416eb6f67b in create_plan_recurse (root=root@entry=0x564170511a70, best_path=0x56417054f8c8, flags=flags@entry=3) at createplan.c:509 #9 0x56416eb71f8e in create_sort_plan (root=root@entry=0x564170511a70, best_path=best_path@entry=0x56417054f560, flags=flags@entry=1) at createplan.c:2109 #10 0x56416eb6f638 in create_plan_recurse (root=root@entry=0x564170511a70, best_path=0x56417054f560, flags=flags@entry=1) at createplan.c:489 #11 0x56416eb72c83 in create_limit_plan (root=root@entry=0x564170511a70, best_path=best_path@entry=0x56417054ffa0, flags=flags@entry=1) at createplan.c:2784 #12 0x56416eb6f713 in create_plan_recurse (root=root@entry=0x564170511a70, best_path=0x56417054ffa0, flags=flags@entry=1) at createplan.c:536 #13 0x56416eb6f79d in create_plan (root=root@entry=0x564170511a70, best_path=) at createplan.c:349 #14 0x56416eb7fe93 in standard_planner (parse=0x564170437268, query_string=, cursorOptions=2048, boundParams=) at planner.c:407 > I think if we can get the correct plan the thing to look at would be > the tlists at the relevant levels of the plan. Does the information in [1] help at all? The tlist does have an Aggref, as expected, but its aggsplit value doesn't match the pathkey's Aggref's aggsplit value. James 1: https://www.postgresql.org/message-id/CAAaqYe_NU4hO9COoJdcXWqjtH%3DdGMknYdsSdJjZ%3DJOHPTea-Nw%40mail.gmail.com
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
On Wed, Apr 14, 2021 at 8:20 PM James Coleman wrote: > > Hmm, could be. Although, the stack trace at issue doesn't seem to show > > a call to create_incrementalsort_plan(). > > The changes to gather merge path generation made it possible to use > those paths in more cases for both incremental sort and regular sort, > so by "incremental sort" I read Tomas as saying "the patches that > brought in incremental sort" not specifically "incremental sort > itself". I agree. That's why I said "hmm, could be" even though the plan doesn't involve one. -- Robert Haas EDB: http://www.enterprisedb.com
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
On Wed, Apr 14, 2021 at 5:43 PM James Coleman wrote: > The query in question is: > select count(*) > from store_sales > ,household_demographics > ,time_dim, store > where ss_sold_time_sk = time_dim.t_time_sk > and ss_hdemo_sk = household_demographics.hd_demo_sk > and ss_store_sk = s_store_sk > and time_dim.t_hour = 15 > and time_dim.t_minute >= 30 > and household_demographics.hd_dep_count = 7 > and store.s_store_name = 'ese' > order by count(*) > limit 100; > > From debugging output it looks like this is the plan being chosen > (cheapest total path): > Gather(store_sales household_demographics time_dim) rows=60626 > cost=3145.73..699910.15 > HashJoin(store_sales household_demographics time_dim) > rows=25261 cost=2145.73..692847.55 > clauses: store_sales.ss_hdemo_sk = > household_demographics.hd_demo_sk > HashJoin(store_sales time_dim) rows=252609 > cost=1989.73..692028.08 > clauses: store_sales.ss_sold_time_sk = > time_dim.t_time_sk > SeqScan(store_sales) rows=11998564 > cost=0.00..658540.64 > SeqScan(time_dim) rows=1070 > cost=0.00..1976.35 > SeqScan(household_demographics) rows=720 > cost=0.00..147.00 This doesn't really make sense to me given the strack trace in the OP. That seems to go Limit -> Sort -> Agg -> NestLoop -> NestLoop -> NestLoop -> GatherMerge -> Sort. If the plan were as you have it here, there would be no Sort and no Gather Merge, so where would be getting a failure related to pathkeys? I think if we can get the correct plan the thing to look at would be the tlists at the relevant levels of the plan. -- Robert Haas EDB: http://www.enterprisedb.com
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
On Wed, Apr 14, 2021 at 8:16 PM Robert Haas wrote: > > On Mon, Apr 12, 2021 at 8:37 AM Tomas Vondra > wrote: > > Could be related to incremental sort, which allowed some gather merge > > paths that were impossible before. We had a couple issues related to > > that fixed in November, IIRC. > > Hmm, could be. Although, the stack trace at issue doesn't seem to show > a call to create_incrementalsort_plan(). The changes to gather merge path generation made it possible to use those paths in more cases for both incremental sort and regular sort, so by "incremental sort" I read Tomas as saying "the patches that brought in incremental sort" not specifically "incremental sort itself". James
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
On Mon, Apr 12, 2021 at 8:37 AM Tomas Vondra wrote: > Could be related to incremental sort, which allowed some gather merge > paths that were impossible before. We had a couple issues related to > that fixed in November, IIRC. Hmm, could be. Although, the stack trace at issue doesn't seem to show a call to create_incrementalsort_plan(). -- Robert Haas EDB: http://www.enterprisedb.com
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
On Mon, Apr 12, 2021 at 8:37 AM Tomas Vondra wrote: > > On 4/12/21 2:24 PM, Luc Vlaming wrote: > > Hi, > > > > When trying to run on master (but afaik also PG-13) TPC-DS queries 94, > > 95 and 96 on a SF10 I get the error "could not find pathkey item to sort". > > When I disable enable_gathermerge the problem goes away and then the > > plan for query 94 looks like below. I tried figuring out what the > > problem is but to be honest I would need some pointers as the code that > > tries to matching equivalence members in prepare_sort_from_pathkeys is > > something i'm really not familiar with. > > > > Could be related to incremental sort, which allowed some gather merge > paths that were impossible before. We had a couple issues related to > that fixed in November, IIRC. > > > To reproduce you can either ingest and test using the toolkit I used too > > (see https://github.com/swarm64/s64da-benchmark-toolkit/), or > > alternatively just use the schema (see > > https://github.com/swarm64/s64da-benchmark-toolkit/tree/master/benchmarks/tpcds/schemas/psql_native) > > > > Thanks, I'll see if I can reproduce that with your schema. > > > regards > > -- > Tomas Vondra > EnterpriseDB: http://www.enterprisedb.com > The Enterprise PostgreSQL Company The query in question is: select count(*) from store_sales ,household_demographics ,time_dim, store where ss_sold_time_sk = time_dim.t_time_sk and ss_hdemo_sk = household_demographics.hd_demo_sk and ss_store_sk = s_store_sk and time_dim.t_hour = 15 and time_dim.t_minute >= 30 and household_demographics.hd_dep_count = 7 and store.s_store_name = 'ese' order by count(*) limit 100; >From debugging output it looks like this is the plan being chosen (cheapest total path): Gather(store_sales household_demographics time_dim) rows=60626 cost=3145.73..699910.15 HashJoin(store_sales household_demographics time_dim) rows=25261 cost=2145.73..692847.55 clauses: store_sales.ss_hdemo_sk = household_demographics.hd_demo_sk HashJoin(store_sales time_dim) rows=252609 cost=1989.73..692028.08 clauses: store_sales.ss_sold_time_sk = time_dim.t_time_sk SeqScan(store_sales) rows=11998564 cost=0.00..658540.64 SeqScan(time_dim) rows=1070 cost=0.00..1976.35 SeqScan(household_demographics) rows=720 cost=0.00..147.00 prepare_sort_from_pathkeys fails to find a pathkey because tlist_member_ignore_relabel returns null -- which seemed weird because the sortexpr is an Aggref (in a single member equivalence class) and the tlist contains a single member that's also an Aggref. It turns out that the only difference between the two Aggrefs is that the tlist entry has "aggsplit = AGGSPLIT_INITIAL_SERIAL" while the sortexpr has aggsplit = AGGSPLIT_SIMPLE. That's as far as I've gotten so far, but I figured I'd get that info out to see if it means anything obvious to anyone else. James
Re: "could not find pathkey item to sort" for TPC-DS queries 94-96
On 4/12/21 2:24 PM, Luc Vlaming wrote: > Hi, > > When trying to run on master (but afaik also PG-13) TPC-DS queries 94, > 95 and 96 on a SF10 I get the error "could not find pathkey item to sort". > When I disable enable_gathermerge the problem goes away and then the > plan for query 94 looks like below. I tried figuring out what the > problem is but to be honest I would need some pointers as the code that > tries to matching equivalence members in prepare_sort_from_pathkeys is > something i'm really not familiar with. > Could be related to incremental sort, which allowed some gather merge paths that were impossible before. We had a couple issues related to that fixed in November, IIRC. > To reproduce you can either ingest and test using the toolkit I used too > (see https://github.com/swarm64/s64da-benchmark-toolkit/), or > alternatively just use the schema (see > https://github.com/swarm64/s64da-benchmark-toolkit/tree/master/benchmarks/tpcds/schemas/psql_native) > Thanks, I'll see if I can reproduce that with your schema. regards -- Tomas Vondra EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
"could not find pathkey item to sort" for TPC-DS queries 94-96
Hi, When trying to run on master (but afaik also PG-13) TPC-DS queries 94, 95 and 96 on a SF10 I get the error "could not find pathkey item to sort". When I disable enable_gathermerge the problem goes away and then the plan for query 94 looks like below. I tried figuring out what the problem is but to be honest I would need some pointers as the code that tries to matching equivalence members in prepare_sort_from_pathkeys is something i'm really not familiar with. To reproduce you can either ingest and test using the toolkit I used too (see https://github.com/swarm64/s64da-benchmark-toolkit/), or alternatively just use the schema (see https://github.com/swarm64/s64da-benchmark-toolkit/tree/master/benchmarks/tpcds/schemas/psql_native) Best, Luc Limit (cost=229655.62..229655.63 rows=1 width=72) -> Sort (cost=229655.62..229655.63 rows=1 width=72) Sort Key: (count(DISTINCT ws1.ws_order_number)) -> Aggregate (cost=229655.60..229655.61 rows=1 width=72) -> Nested Loop Semi Join (cost=1012.65..229655.59 rows=1 width=16) -> Nested Loop (cost=1012.22..229653.73 rows=1 width=20) Join Filter: (ws1.ws_web_site_sk = web_site.web_site_sk) -> Nested Loop (cost=1012.22..229651.08 rows=1 width=24) -> Gather (cost=1011.80..229650.64 rows=1 width=28) Workers Planned: 2 -> Nested Loop Anti Join (cost=11.80..228650.54 rows=1 width=28) -> Hash Join (cost=11.37..227438.35 rows=2629 width=28) Hash Cond: (ws1.ws_ship_date_sk = date_dim.d_date_sk) -> Parallel Seq Scan on web_sales ws1 (cost=0.00..219548.92 rows=3000992 width=32) -> Hash (cost=10.57..10.57 rows=64 width=4) -> Index Scan using idx_d_date on date_dim (cost=0.29..10.57 rows=64 width=4) Index Cond: ((d_date >= '2000-03-01'::date) AND (d_date <= '2000-04-30'::date)) -> Index Only Scan using idx_wr_order_number on web_returns wr1 (cost=0.42..0.46 rows=2 width=4) Index Cond: (wr_order_number = ws1.ws_order_number) -> Index Scan using customer_address_pkey on customer_address (cost=0.42..0.44 rows=1 width=4) Index Cond: (ca_address_sk = ws1.ws_ship_addr_sk) Filter: ((ca_state)::text = 'GA'::text) -> Seq Scan on web_site (cost=0.00..2.52 rows=10 width=4) Filter: ((web_company_name)::text = 'pri'::text) -> Index Scan using idx_ws_order_number on web_sales ws2 (cost=0.43..1.84 rows=59 width=8) Index Cond: (ws_order_number = ws1.ws_order_number) Filter: (ws1.ws_warehouse_sk <> ws_warehouse_sk) The top of the stacktrace is: #0 errfinish (filename=0x5562dc1a5125 "createplan.c", lineno=6186, funcname=0x5562dc1a54d0 <__func__.14> "prepare_sort_from_pathkeys") at elog.c:514 #1 0x5562dbc2d7de in prepare_sort_from_pathkeys (lefttree=0x5562dc5a2f58, pathkeys=0x5562dc4eabc8, relids=0x0, reqColIdx=0x0, adjust_tlist_in_place=, p_numsortkeys=0x7ffc0b8cda84, p_sortColIdx=0x7ffc0b8cda88, p_sortOperators=0x7ffc0b8cda90, p_collations=0x7ffc0b8cda98, p_nullsFirst=0x7ffc0b8cdaa0) at createplan.c:6186 #2 0x5562dbe8d695 in make_sort_from_pathkeys (lefttree=out>, pathkeys=, relids=) at createplan.c:6313 #3 0x5562dbe8eba3 in create_sort_plan (flags=1, best_path=0x5562dc548d68, root=0x5562dc508cf8) at createplan.c:2118 #4 create_plan_recurse (root=0x5562dc508cf8, best_path=0x5562dc548d68, flags=1) at createplan.c:489 #5 0x5562dbe8f315 in create_gather_merge_plan (best_path=0x5562dc5782f8, root=0x5562dc508cf8) at createplan.c:1885 #6 create_plan_recurse (root=0x5562dc508cf8, best_path=0x5562dc5782f8, flags=) at createplan.c:541 #7 0x5562dbe8ddad in create_nestloop_plan (best_path=0x5562dc585668, root=0x5562dc508cf8) at createplan.c:4237 #8 create_join_plan (best_path=0x5562dc585668, root=0x5562dc508cf8) at createplan.c:1062 #9 create_plan_recurse (root=0x5562dc508cf8, best_path=0x5562dc585668, flags=) at createplan.c:418 #10 0x5562dbe8ddad in create_nestloop_plan (best_path=0x5562dc5c4428, root=0x5562dc508cf8) at createplan.c:4237 #11 create_join_plan (best_path=0x5562dc5c4428,
