Propagate pathkeys from CTEs up to the outer query

On 29/1/2024 10:18, Richard Guo wrote:

In [1] we've reached a conclusion that for a MATERIALIZED CTE it's okay
to 'allow our statistics or guesses for the sub-query to subsequently
influence what the upper planner does'.  Commit f7816aec23 exposes
column statistics to the upper planner.  In the light of that, here is a
patch that exposes info about the ordering of the CTE result to the
upper planner.

This patch was initially posted in that same thread and has received
some comments from Tom in [2].  Due to the presence of multiple patches
in that thread, it has led to confusion.  So fork a new thread here
specifically dedicated to discussing the patch about exposing pathkeys
from CTEs to the upper planner.

I like this approach. It looks good initially, but such features need
more opinions/views/time to analyse corner cases.
It goes alongside my current backburner - pull parameterisation through
the GROUP-BY and the query block fence up to the JOIN searching code of
the parent query.

--
regards,
Andrei Lepikhov
Postgres Professional

Richard Guo <guofenglinux@gmail.com> writes:

This patch was initially posted in that same thread and has received
some comments from Tom in [2]. Due to the presence of multiple patches
in that thread, it has led to confusion. So fork a new thread here
specifically dedicated to discussing the patch about exposing pathkeys
from CTEs to the upper planner.

I got around to looking at this finally. I was a bit surprised by
your choice of data structure. You made a per-CTE-item cte_paths
list paralleling cte_plan_ids, but what I had had in mind was a
per-subplan list of paths paralleling glob->subplans and subroots.
This would mean that the code for ordinary SubqueryScans would
also need to fill in that list, but surely that's a trivial cost
compared to everything else we do to prepare a subplan. I don't
think that we have any immediate need to remember that info for
an ordinary SubqueryScan, but it seems plausible that we will
in future. Also, I'm not sure that a Path is fully interpretable
without the associated PlannerInfo (subroot), so keeping it
beside the list of subroots seems more future-proof than dissociating
it from that. This approach would also be more amenable to postponing
creation of the subplans, as we speculated about earlier. (I have
no near-term desire to actually do that, but maybe someday it will
happen.)

regards, tom lane

On Tue, Mar 26, 2024 at 1:39 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

I got around to looking at this finally. I was a bit surprised by
your choice of data structure. You made a per-CTE-item cte_paths
list paralleling cte_plan_ids, but what I had had in mind was a
per-subplan list of paths paralleling glob->subplans and subroots.
This would mean that the code for ordinary SubqueryScans would
also need to fill in that list, but surely that's a trivial cost
compared to everything else we do to prepare a subplan. I don't
think that we have any immediate need to remember that info for
an ordinary SubqueryScan, but it seems plausible that we will
in future. Also, I'm not sure that a Path is fully interpretable
without the associated PlannerInfo (subroot), so keeping it
beside the list of subroots seems more future-proof than dissociating
it from that. This approach would also be more amenable to postponing
creation of the subplans, as we speculated about earlier. (I have
no near-term desire to actually do that, but maybe someday it will
happen.)

I agree with your points. Previously I was thinking that CTEs were the
only scenario where we needed to remember the best path and only
required the best path's pathkeys. However, considering potential
future use cases as you mentioned, I concur that having a per-subplan
list of paths would be more future-proof. Please see attached v4 patch.

Thanks
Richard

Richard Guo <guofenglinux@gmail.com> writes:

I agree with your points. Previously I was thinking that CTEs were the
only scenario where we needed to remember the best path and only
required the best path's pathkeys. However, considering potential
future use cases as you mentioned, I concur that having a per-subplan
list of paths would be more future-proof. Please see attached v4 patch.

Hm, well, you didn't actually fill in the paths for the other
subqueries. I agree that it's not worth doing so in
SS_make_initplan_from_plan, but a comment explaining that decision
seems in order. Also, there's nothing stopping us from saving the
path for subplans made in build_subplan, except adding a parameter
to pass them down. So I did that, and made a couple other cosmetic
changes, and pushed it.

One thing I noticed while testing is that while your regression-test
query successfully propagates the pathkeys:

regression=# explain with x as materialized (select unique1 from tenk1 b order by unique1)
select count(*) from tenk1 a
where unique1 in (select * from x);
QUERY PLAN
----------------------------------------------------------------------------------------------------
Aggregate (cost=915.55..915.56 rows=1 width=8)
CTE x
-> Index Only Scan using tenk1_unique1 on tenk1 b (cost=0.29..270.29 rows=10000 width=4)
-> Merge Semi Join (cost=0.31..620.26 rows=10000 width=0)
Merge Cond: (a.unique1 = x.unique1)
-> Index Only Scan using tenk1_unique1 on tenk1 a (cost=0.29..270.29 rows=10000 width=4)
-> CTE Scan on x (cost=0.00..200.00 rows=10000 width=4)
(7 rows)

this variant doesn't:

regression=# explain with x as materialized (select unique1 from tenk1 b)
select count(*) from tenk1 a
where unique1 in (select * from x);
QUERY PLAN
----------------------------------------------------------------------------------------------------
Aggregate (cost=1028.07..1028.08 rows=1 width=8)
CTE x
-> Index Only Scan using tenk1_unique1 on tenk1 b (cost=0.29..270.29 rows=10000 width=4)
-> Hash Semi Join (cost=325.28..732.78 rows=10000 width=0)
Hash Cond: (a.unique1 = x.unique1)
-> Index Only Scan using tenk1_unique1 on tenk1 a (cost=0.29..270.29 rows=10000 width=4)
-> Hash (cost=200.00..200.00 rows=10000 width=4)
-> CTE Scan on x (cost=0.00..200.00 rows=10000 width=4)
(8 rows)

That's not the fault of anything we did here; the IndexOnlyScan path
in the subquery is in fact not marked with any pathkeys, even though
clearly its result is sorted. I believe that's an intentional
decision from way way back, that pathkeys only correspond to orderings
that are of interest in the current query level. "select unique1 from
tenk1 b order by unique1" has an interest in ordering by unique1,
but "select unique1 from tenk1 b" does not, so it's choosing that
path strictly according to cost. Not generating pathkeys in such a
query saves a few cycles and ensures that we won't improperly prefer
a path on the basis of pathkeys if it hasn't got a cost advantage.
So I'm quite hesitant to muck with that old decision, especially in
the waning days of a development cycle, but the results do feel a
little strange here.

regards, tom lane

On Wed, Mar 27, 2024 at 1:20 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:

Richard Guo <guofenglinux@gmail.com> writes:

I agree with your points. Previously I was thinking that CTEs were the
only scenario where we needed to remember the best path and only
required the best path's pathkeys. However, considering potential
future use cases as you mentioned, I concur that having a per-subplan
list of paths would be more future-proof. Please see attached v4 patch.

Hm, well, you didn't actually fill in the paths for the other
subqueries. I agree that it's not worth doing so in
SS_make_initplan_from_plan, but a comment explaining that decision
seems in order. Also, there's nothing stopping us from saving the
path for subplans made in build_subplan, except adding a parameter
to pass them down. So I did that, and made a couple other cosmetic
changes, and pushed it.

Thanks for the adjustments and pushing!

That's not the fault of anything we did here; the IndexOnlyScan path
in the subquery is in fact not marked with any pathkeys, even though
clearly its result is sorted. I believe that's an intentional
decision from way way back, that pathkeys only correspond to orderings
that are of interest in the current query level. "select unique1 from
tenk1 b order by unique1" has an interest in ordering by unique1,
but "select unique1 from tenk1 b" does not, so it's choosing that
path strictly according to cost. Not generating pathkeys in such a
query saves a few cycles and ensures that we won't improperly prefer
a path on the basis of pathkeys if it hasn't got a cost advantage.
So I'm quite hesitant to muck with that old decision, especially in
the waning days of a development cycle, but the results do feel a
little strange here.

Yeah, I also noticed this while writing the test case. That's why I
added 'order by unique1' explicitly in the CTE subquery. This also
happens to subquery RTEs, such as

explain (costs off)
select * from (select unique1 from tenk1 offset 0) order by unique1;
QUERY PLAN
----------------------------------------------------
Sort
Sort Key: tenk1.unique1
-> Index Only Scan using tenk1_unique1 on tenk1
(3 rows)

I agree that mucking with the old decision might not be a good idea. In
addition, for a MATERIALIZED CTE, generating pathkeys according to the
outer query's ordering requirements breaks the idea of optimization
fence: the outer query should not affect the plan chosen for the CTE
query.

Thanks
Richard

On Wed, 27 Mar 2024 at 06:20, Tom Lane <tgl@sss.pgh.pa.us> wrote:

That's not the fault of anything we did here; the IndexOnlyScan path
in the subquery is in fact not marked with any pathkeys, even though
clearly its result is sorted. I believe that's an intentional
decision from way way back, that pathkeys only correspond to orderings
that are of interest in the current query level. "select unique1 from
tenk1 b order by unique1" has an interest in ordering by unique1,
but "select unique1 from tenk1 b" does not, so it's choosing that
path strictly according to cost. Not generating pathkeys in such a
query saves a few cycles and ensures that we won't improperly prefer
a path on the basis of pathkeys if it hasn't got a cost advantage.
So I'm quite hesitant to muck with that old decision, especially in
the waning days of a development cycle, but the results do feel a
little strange here.

I agree that add_path() might start making questionable choices if we
were to include unrelated pathkeys in a path. However, I don't think
it would be a bad idea to give a subquery a bit more context about
where it's running and which orders might be useful for the outer
query.

What's been reported in [1]/messages/by-id/242fc7c6-a8aa-2daf-ac4c-0a231e2619c1@gmail.com I think could be solved by giving the
planner some way to tell subqueries what pathkeys are useful to the
outer query.

David

[1]: /messages/by-id/242fc7c6-a8aa-2daf-ac4c-0a231e2619c1@gmail.com