BUG #18652: Planner can not find pathkey item to sort for query with expression and expression index

PG Bug reporting form <noreply@postgresql.org> writes:

The following query:
CREATE TABLE t(i int, j int);
CREATE INDEX idx on t((i + 0));

SELECT * FROM t,
(SELECT i + 0 AS i FROM
(SELECT i FROM t UNION ALL SELECT i + 1 FROM t) AS t1
) AS t2
WHERE t2.i = t.j;

fails with:
ERROR: XX000: could not find pathkey item to sort
LOCATION: prepare_sort_from_pathkeys, createplan.c:6350

The error occurs only when the expression in SELECT i + 0 AS i FROM
matches the expression in an index.

Reproduced on REL_10_STABLE .. master.

Hm, this seems quite an old bug: I can reproduce it on 9.1 but
not 9.0. Unfortunately, that's too far back to build easily
on modern platforms, so I'm not seeing a way to "git bisect"
for more insight.

It looks like we are generating a Path tree in which one of the
inputs to a MergeAppend is a plain unsorted seqscan, which'd
be all right except it doesn't expose the required sort value
in its targetlist. More later.

regards, tom lane

On Thu, Oct 10, 2024 at 5:43 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

It looks like we are generating a Path tree in which one of the
inputs to a MergeAppend is a plain unsorted seqscan, which'd
be all right except it doesn't expose the required sort value
in its targetlist.

Correct. In addition, find_computable_ec_member() fails to find a
computable expression from its targetlist.

Here is a slightly simpler repro query.

SELECT i + 0 AS c FROM (SELECT i FROM t UNION ALL SELECT i + 1 FROM t)
ORDER BY c;
ERROR: could not find pathkey item to sort

I think the expected plan should look like:

EXPLAIN (VERBOSE, COSTS OFF)
SELECT i + 0 AS c FROM (SELECT i FROM t UNION ALL SELECT i + 1 FROM t)
ORDER BY c;
QUERY PLAN
------------------------------------------------------------
Result
Output: ((t.i + 0))
-> Merge Append
Sort Key: ((t.i + 0))
-> Index Scan using t_expr_idx on public.t
Output: t.i, (t.i + 0)
-> Sort
Output: ((t_1.i + 1)), (((t_1.i + 1) + 0))
Sort Key: (((t_1.i + 1) + 0))
-> Seq Scan on public.t t_1
Output: (t_1.i + 1), ((t_1.i + 1) + 0)
(11 rows)

For the indexscan path, find_computable_ec_member() is able to find
(t.i + 0) which can be computed from its tlist item 't.i'.

For the seqscan path, though, find_computable_ec_member() is not able
to find ((t_1.i + 1) + 0) from its tlist item '(t_1.i + 1)'.

I think this is because find_computable_ec_member() only tries to
match Vars. Maybe we should teach it to also match OpExprs?

Thanks
Richard

Richard Guo <guofenglinux@gmail.com> writes:

On Thu, Oct 10, 2024 at 5:43 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

It looks like we are generating a Path tree in which one of the
inputs to a MergeAppend is a plain unsorted seqscan, which'd
be all right except it doesn't expose the required sort value
in its targetlist.

Correct. In addition, find_computable_ec_member() fails to find a
computable expression from its targetlist.
...
I think this is because find_computable_ec_member() only tries to
match Vars. Maybe we should teach it to also match OpExprs?

Not sure. Having nothing much better to do this evening,
I cranked up a VM with an old OS and was able to "git bisect"
the problem with some tedious manual hackery. The end result was

11cad29c91524aac1d0b61e0ea0357398ab79bf8 is the first bad commit
commit 11cad29c91524aac1d0b61e0ea0357398ab79bf8
Author: Tom Lane <tgl@sss.pgh.pa.us>
Date: Thu Oct 14 16:56:39 2010 -0400

Support MergeAppend plans, to allow sorted output from append relations.

So it's specific to MergeAppend and it's been wrong from day zero.
That makes me think it's probably not find_computable_ec_member's
fault directly. Fixing it there might be the most expedient answer,
but I feel like first we should drill down a bit further to understand
the root problem. I'm too tired to do more tonight though.

regards, tom lane

On 10/10/24 10:52, Richard Guo wrote:

On Thu, Oct 10, 2024 at 5:43 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

It looks like we are generating a Path tree in which one of the
inputs to a MergeAppend is a plain unsorted seqscan, which'd
be all right except it doesn't expose the required sort value
in its targetlist.

Correct. In addition, find_computable_ec_member() fails to find a
computable expression from its targetlist.
For the indexscan path, find_computable_ec_member() is able to find
(t.i + 0) which can be computed from its tlist item 't.i'.

For the seqscan path, though, find_computable_ec_member() is not able
to find ((t_1.i + 1) + 0) from its tlist item '(t_1.i + 1)'.

I think this is because find_computable_ec_member() only tries to
match Vars. Maybe we should teach it to also match OpExprs?

Looking into that case, I don't understand only one thing:
generate_orderedappend_paths decided to try MergeAppend; the
create_append_path routine added the Sort cost, but the Sort node
itself wasn't added. Maybe the origin problem is the lack of feasibility
examinations?

--
regards, Andrei Lepikhov

Andrei Lepikhov <lepihov@gmail.com> 于2024年10月10日周四 14:50写道：

On 10/10/24 10:52, Richard Guo wrote:

On Thu, Oct 10, 2024 at 5:43 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

It looks like we are generating a Path tree in which one of the
inputs to a MergeAppend is a plain unsorted seqscan, which'd
be all right except it doesn't expose the required sort value
in its targetlist.

Correct. In addition, find_computable_ec_member() fails to find a
computable expression from its targetlist.
For the indexscan path, find_computable_ec_member() is able to find
(t.i + 0) which can be computed from its tlist item 't.i'.

For the seqscan path, though, find_computable_ec_member() is not able
to find ((t_1.i + 1) + 0) from its tlist item '(t_1.i + 1)'.

I think this is because find_computable_ec_member() only tries to
match Vars. Maybe we should teach it to also match OpExprs?

Looking into that case, I don't understand only one thing:
generate_orderedappend_paths decided to try MergeAppend; the
create_append_path routine added the Sort cost, but the Sort node
itself wasn't added. Maybe the origin problem is the lack of feasibility
examinations?

Yeah, I'm also curious why only cost Sort but not adding Sort node in
create_merge_append_path().
The comments say that " We'll need to insert a Sort node, so include cost
for that". Does another place
insert the Sort node?

--
Thanks,
Tender Wang

On Thu, Oct 10, 2024 at 5:02 PM Tender Wang <tndrwang@gmail.com> wrote:

Andrei Lepikhov <lepihov@gmail.com> 于2024年10月10日周四 14:50写道：

Looking into that case, I don't understand only one thing:
generate_orderedappend_paths decided to try MergeAppend; the
create_append_path routine added the Sort cost, but the Sort node
itself wasn't added. Maybe the origin problem is the lack of feasibility
examinations?

Yeah, I'm also curious why only cost Sort but not adding Sort node in create_merge_append_path().
The comments say that " We'll need to insert a Sort node, so include cost for that". Does another place
insert the Sort node?

The Sort node will be added in createplan.c. This isn't exclusive to
MergeAppend; we also do so for MergeJoin, for example.

Thanks
Richard

On 10/10/24 16:02, Tender Wang wrote:

Andrei Lepikhov <lepihov@gmail.com <mailto:lepihov@gmail.com>> 于2024年

I think this is because find_computable_ec_member() only tries to
match Vars.  Maybe we should teach it to also match OpExprs?

Looking into that case, I don't understand only one thing:
generate_orderedappend_paths decided to try MergeAppend; the
create_append_path routine added the Sort cost,  but the Sort node
itself wasn't added. Maybe the origin problem is the lack of
feasibility
examinations?

Yeah, I'm also curious why only cost Sort but not adding Sort node in
create_merge_append_path().
The comments say that " We'll need to insert a Sort node, so include
cost for that".  Does another place
insert the Sort node?

Before inserting the Sort node, we must identify the column
corresponding to each path key. And here is the problem: IndexScan has
two elements in the target list, but SeqScan has only one. It already
looks strange to me. How do we UNION two sources with different numbers
of resulting columns? It seems to me we have a bug under the Append node.

--
regards, Andrei Lepikhov

On 10.10.2024 13:23, Andrei Lepikhov wrote:

On 10/10/24 16:02, Tender Wang wrote:

Andrei Lepikhov <lepihov@gmail.com <mailto:lepihov@gmail.com>> 于2024年
     > I think this is because find_computable_ec_member() only tries to
     > match Vars.  Maybe we should teach it to also match OpExprs?
    Looking into that case, I don't understand only one thing:
    generate_orderedappend_paths decided to try MergeAppend; the
    create_append_path routine added the Sort cost,  but the Sort node
    itself wasn't added. Maybe the origin problem is the lack of
    feasibility
    examinations?

Yeah, I'm also curious why only cost Sort but not adding Sort node in
create_merge_append_path().
The comments say that " We'll need to insert a Sort node, so include
cost for that".  Does another place
insert the Sort node?

Before inserting the Sort node, we must identify the column
corresponding to each path key. And here is the problem: IndexScan has
two elements in the target list, but SeqScan has only one. It already
looks strange to me. How do we UNION two sources with different
numbers of resulting columns? It seems to me we have a bug under the
Append node.

Maybe a mistake exists at the stage of creating a sequential scan?
Because the subpath of the MergeAppend path does not have any elements
in pathkeys, although the pasthtarget has one element and this
expression wasn't involved anywhere?

I honestly don’t understand at what stage this expression i+1 appears:

SELECT i + 0 AS c FROM (SELECT i FROM t UNION ALL SELECT i + 1 FROM t)

--
Regards,
Alena Rybakina
Postgres Professional

On Thu, Oct 10, 2024 at 12:34 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

So it's specific to MergeAppend and it's been wrong from day zero.
That makes me think it's probably not find_computable_ec_member's
fault directly. Fixing it there might be the most expedient answer,
but I feel like first we should drill down a bit further to understand
the root problem. I'm too tired to do more tonight though.

Usually a relation's targetlist should include only Vars and PHVs
during this phase. I think this may be the rationale behind
find_computable_ec_member matching only Vars and quasi-Vars. However,
for a child rel, when we copy the parent's targetlist with appropriate
substitution, we may generate arbitrary expressions, such as an OpExpr
for 'i + 1' in this case.

We have a note in the comments in set_append_rel_size saying that

* Code that might be looking at an appendrel child must cope with
* such.

It seems to me that find_computable_ec_member does not get this memo.

Alternatively, can we wrap non-var expressions in a childrel's
targetlist into PHVs, so that we do not need special handling for an
appendrel child? I have not tried this though.

Thanks
Richard

On 10/10/24 17:23, Andrei Lepikhov wrote:

On 10/10/24 16:02, Tender Wang wrote:

Andrei Lepikhov <lepihov@gmail.com <mailto:lepihov@gmail.com>> 于2024
年      > I think this is because find_computable_ec_member() only
tries to
     > match Vars.  Maybe we should teach it to also match OpExprs?
    Looking into that case, I don't understand only one thing:
    generate_orderedappend_paths decided to try MergeAppend; the
    create_append_path routine added the Sort cost,  but the Sort node
    itself wasn't added. Maybe the origin problem is the lack of
    feasibility
    examinations?

Yeah, I'm also curious why only cost Sort but not adding Sort node in
create_merge_append_path().
The comments say that " We'll need to insert a Sort node, so include
cost for that".  Does another place
insert the Sort node?

Before inserting the Sort node, we must identify the column
corresponding to each path key. And here is the problem: IndexScan has
two elements in the target list, but SeqScan has only one. It already
looks strange to me. How do we UNION two sources with different numbers
of resulting columns? It seems to me we have a bug under the Append node.Sorry for the mess: my sentence is totally wrong: it is the MergeAppend

node with two elements in the target list (the second one is resjunk). I
think I should research the logic of how append arranges its pathkeys
beforehand.

--
regards, Andrei Lepikhov

On 10/10/24 10:52, Richard Guo wrote:

On Thu, Oct 10, 2024 at 5:43 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

It looks like we are generating a Path tree in which one of the
inputs to a MergeAppend is a plain unsorted seqscan, which'd
be all right except it doesn't expose the required sort value
in its targetlist.

I think this is because find_computable_ec_member() only tries to
match Vars. Maybe we should teach it to also match OpExprs?

Why not look if some entry of the TargetList contains the var? Something
like attached?
If I understand correctly, MergeAppend will still add a resjunk column
and Sort according to the column.

--
regards, Andrei Lepikhov

On 10.10.2024 14:57, Richard Guo wrote:

On Thu, Oct 10, 2024 at 12:34 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

So it's specific to MergeAppend and it's been wrong from day zero.
That makes me think it's probably not find_computable_ec_member's
fault directly. Fixing it there might be the most expedient answer,
but I feel like first we should drill down a bit further to understand
the root problem. I'm too tired to do more tonight though.

Usually a relation's targetlist should include only Vars and PHVs
during this phase. I think this may be the rationale behind
find_computable_ec_member matching only Vars and quasi-Vars. However,
for a child rel, when we copy the parent's targetlist with appropriate
substitution, we may generate arbitrary expressions, such as an OpExpr
for 'i + 1' in this case.

We have a note in the comments in set_append_rel_size saying that

* Code that might be looking at an appendrel child must cope with
* such.

It seems to me that find_computable_ec_member does not get this memo.

Alternatively, can we wrap non-var expressions in a childrel's
targetlist into PHVs, so that we do not need special handling for an
appendrel child? I have not tried this though.

To be honest, looking at the MergeAppend processing plan, it’s not
entirely clear to me what the functional difference is between
set_rel_pathlist and

find_computable_ec_member. Both prepare pathkeys , but what the first
function doesn't do is what the other one needs to do?Could you explain
it to me?

--
Regards,
Alena Rybakina
Postgres Professional

On 11.10.2024 11:02, Alena Rybakina wrote:

On 10.10.2024 14:57, Richard Guo wrote:

On Thu, Oct 10, 2024 at 12:34 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

So it's specific to MergeAppend and it's been wrong from day zero.
That makes me think it's probably not find_computable_ec_member's
fault directly.  Fixing it there might be the most expedient answer,
but I feel like first we should drill down a bit further to understand
the root problem.  I'm too tired to do more tonight though.

Usually a relation's targetlist should include only Vars and PHVs
during this phase.  I think this may be the rationale behind
find_computable_ec_member matching only Vars and quasi-Vars. However,
for a child rel, when we copy the parent's targetlist with appropriate
substitution, we may generate arbitrary expressions, such as an OpExpr
for 'i + 1' in this case.

We have a note in the comments in set_append_rel_size saying that

* Code that might be looking at an appendrel child must cope with
* such.

It seems to me that find_computable_ec_member does not get this memo.

Alternatively, can we wrap non-var expressions in a childrel's
targetlist into PHVs, so that we do not need special handling for an
appendrel child?  I have not tried this though.

To be honest, looking at the MergeAppend processing plan, it’s not
entirely clear to me what the functional difference is between
set_rel_pathlist and

find_computable_ec_member. Both prepare pathkeys , but what the first
function doesn't do is what the other one needs to do?Could you
explain it to me?

Sorry, I meant add_child_rel_equivalences function I've just understood
it. Sorry for noise

--
Regards,
Alena Rybakina
Postgres Professional

Andrei Lepikhov <lepihov@gmail.com> writes:

Why not look if some entry of the TargetList contains the var? Something
like attached?

I finally got my head wrapped around what is happening here.
Using a variant of Richard's example case,

SELECT b + 0 AS c FROM
(SELECT i AS b FROM t t1 UNION ALL SELECT i + 1 FROM t t2) ss
ORDER BY c;

We initially have an EquivalenceClass containing "ss.b + 0"
to represent the required ordering pathkey. When we flatten
the UNION ALL subselect into an appendrel, we add child EC
members containing transformed versions of that, namely
"t1.i + 0" and "(t2.i + 1) + 0". Similarly, the relation
targetlist for ss is "ss.b" so we derive the targetlists for
the appendrel members t1 and t2 as "t1.i" and "t2.i + 1".

Then the problem is that find_computable_ec_member is trying
to verify that "(t2.i + 1) + 0" can be computed from a
subquery that currently emits only "t2.i + 1". Its method
of pulling out just t2.i and looking for that in the subquery
tlist obviously fails.

Now, the way that the commentary for find_computable_ec_member
is written would lead you to think that what we need is to identify
that the subexpression (t2.i + 1) is available from the tlist, with
the expectation that a higher-level plan node would then compute
"subexpression + 0" from that output of a lower plan node. That's
possible but it would require expensive search to identify things.
But that's not what actually happens in the sole use of this code by
prepare_sort_from_pathkeys. What will actually happen is that we
will add the child EC member expression as a new member of the
same tlist, so that the plan node's tlist will look like

t2.i + 1, (t2.i + 1) + 0

This means that it will work so long as all of the Vars needed by the
EC member expression are available from the plan node's input, which
they surely are if they are referenced in the existing tlist. That
is, even if we wanted to compute "t2.i + 2" it'd be fine.

(This would fall down perhaps if there are volatile functions in
the sort expression, but I believe we already reject using volatile
expressions for merge append, so it's not a problem.)

So I conclude that Andrei's patch will fix it, although I don't like
the way that that requires (potentially) multiple re-executions of
pull_var_clause. I think we should refactor the code to avoid that,
which actually ends up being less code, as in the attached draft.

I wonder whether we're doing more work here than we really need to.
If the underlying table t1 has columns i and j, and we have an EC
member that references t1.j while the tlist only mentions t1.i,
wouldn't it still work to add t1.j to the tlist? So maybe groveling
through the tlist members is unnecessary and we only need to be
performing some kind of relation-level check on whether all the
required relations are included in the input. But I'm hesitant
to make that kind of leap of faith in a patch that needs to be
back-patched, especially if the problem only arises in such narrow
edge cases that we've failed to detect it for 14 years.

regards, tom lane

On Sat, Oct 12, 2024 at 4:59 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

This means that it will work so long as all of the Vars needed by the
EC member expression are available from the plan node's input, which
they surely are if they are referenced in the existing tlist. That
is, even if we wanted to compute "t2.i + 2" it'd be fine.

(This would fall down perhaps if there are volatile functions in
the sort expression, but I believe we already reject using volatile
expressions for merge append, so it's not a problem.)

So I conclude that Andrei's patch will fix it, although I don't like
the way that that requires (potentially) multiple re-executions of
pull_var_clause. I think we should refactor the code to avoid that,
which actually ends up being less code, as in the attached draft.

+1. I think it's conceptually correct that if 'Var_A + 2' is
computable in a plan node's targetlist, then 'Var_A + 1' must be also
computable in the same targetlist.

Thanks
Richard

On 12/10/2024 03:59, Tom Lane wrote:

Andrei Lepikhov <lepihov@gmail.com> writes:
But that's not what actually happens in the sole use of this code by
prepare_sort_from_pathkeys. What will actually happen is that we
will add the child EC member expression as a new member of the
same tlist, so that the plan node's tlist will look like

t2.i + 1, (t2.i + 1) + 0

I ended up with the same chain of events. During this scrutiny, I found
only a few sources of knowledge about why the code was written exactly
this way and what logic is under the hood. So, the current explanation
and discussion are profitable by themselves.

I wonder whether we're doing more work here than we really need to.
If the underlying table t1 has columns i and j, and we have an EC
member that references t1.j while the tlist only mentions t1.i,
wouldn't it still work to add t1.j to the tlist? So maybe groveling
through the tlist members is unnecessary and we only need to be
performing some kind of relation-level check on whether all the
required relations are included in the input.

I'm not sure I understand this point. Do you mean something like
attached? I thought about that, but what if we have all the relations
under, but some columns (especially ones with no source relation) needed
are absent in the target list and used far below in the plan, or not
used at all?
The patch looks good.

--
regards, Andrei Lepikhov

Andrei Lepikhov <lepihov@gmail.com> writes:

On 12/10/2024 03:59, Tom Lane wrote:

I wonder whether we're doing more work here than we really need to.
If the underlying table t1 has columns i and j, and we have an EC
member that references t1.j while the tlist only mentions t1.i,
wouldn't it still work to add t1.j to the tlist? So maybe groveling
through the tlist members is unnecessary and we only need to be
performing some kind of relation-level check on whether all the
required relations are included in the input.

I'm not sure I understand this point. Do you mean something like
attached?

More or less, yeah, although passing the tlist rather than some
more-direct representation of the current relation's relids looks
weird once you think of it this way. After thinking about this
for awhile though, I suspect it is only sure to work for appendrel
children (where an EC match should be guaranteed to exist, by
construction). Maybe we could use this simplified approach if we
know we're considering an appendrel child, but I doubt it's worth
having two code paths.

regards, tom lane