Try a presorted outer path when referenced by an ORDER BY prefix

Hi,

The attached patch set adds an optimisation that intensifies the usage
of the sorted NestLoop trick to avoid sorts higher in the query tree.

This employs the idea that it is not so rare a case when an ORDER BY
query (or GROUP BY or DISTINCT operator) can benefit from a pre-sorted
path even if the outer subtree doesn't have an index on the sort
expression. It is especially beneficial when a LIMIT clause and an OUTER
JOIN are present - combined with tuple-bound propagation through the
outer side of such a join, LIMIT can reach the Sort below the join and
turn it into a bounded top-N heapsort.

Let me explain the problem with a typical schema of a sales database. It
has a 'products' table and description tables for each category (see the
SQL script in the attachment).
A front page provides the top-N products based on popularity or other
criteria. The query looks like multiple OUTER JOINs of the main
'products' table with tables for each category. At the top, non-null
fields are combined into a JSON descriptor -- something like the following:

SELECT p.id, p.name, p.category, p.popularity,
json_strip_nulls(json_build_object(
'warranty', e.warranty_months,
'voltage', e.voltage,
'size', c.size,
'color', c.color,
'expiry', f.expiry_days,
'organic', f.organic
)) AS properties
FROM products p
LEFT JOIN electronics_props e ON e.product_id = p.id
LEFT JOIN clothing_props c ON c.product_id = p.id
LEFT JOIN food_props f ON f.product_id = p.id
ORDER BY p.popularity DESC
LIMIT 10;

AFAICS, this pattern is common in sales systems, CRM and ERP workloads -
anywhere you query "top-N items with details" over a normalised schema
with LEFT JOINs to optional property tables.

There is usually no need to join all the tables and sort afterwards;
pre-sorting the outer relation might be more beneficial. This subject
has already been discussed [1,2], but here we try to solve the case in
general. There was an argument that the user might just add an index.
But sometimes it 1) might not be reasonable (like in the example) and 2)
is impossible if the data source is not a plain table but a
FunctionScan, SubqueryScan, etc. The most important source I consider
here is an Append over foreign tables.

There is a sketchy patch set in the attachment that outlines the
solution. It consists of the following parts:

1. Executor part, the ExecSetTupleBound extension: allows recursion into
the outer side of a join to bound the underlying subtree. It is crucial
because we lack a proper hook in this subsystem, which makes the
extensible implementation of such a feature very complex.
2. Planner part, modification of the joinpath.c::match_unsorted_outer.
In the case of NestLoop, where its outer side is mentioned in the
query_pathkeys prefix, and no sort on this prefix yet exists, Postgres
tries to build such a sorted path and proposes a JOIN with sorted output.
3. Adjustment of regression tests.

Open issues
1. Scope: the optimisation targets a specific pattern (ORDER BY + LIMIT
over joins, and NestLoop). One may argue that it is too narrow to
justify core code. That's true, but I see that such a 'Sort pushdown'
might enable the optimiser to create more effective MergeJoins,
aggregates, etc. You may check the regression tests diff for insights.
2. Cost estimation: the Sort node is costed with an estimated tuple
bound from LIMIT in case of OUTER JOIN, which can, in some cases, make
the pre-sorted path look cheaper than it actually is. I don't see an
actual problem here, since it's about in-memory sorting, which shouldn't
be too expensive anyway.

Feedback and review welcome.

References
[1] "Possible optimisation: push down SORT and LIMIT nodes", 2018
https://www.postgresql.org/message-id/E9FA92C2921F31408041863B74EE4C2001AEF33492@CCPMAILDAG03.cantab.local

[2] "Wasteful nested loop join when there is `limit` in the query", 2025
https://www.postgresql.org/message-id/CAAdwFAwm6HwXM_cuPWZBxrxX4E7pBdVg=KcVDSP6q9ume3hYpQ@mail.gmail.com

--
regards, Andrei Lepikhov,
pgEdge