Try a presorted outer path when referenced by an ORDER BY prefix
Hackorum builds and tests every patch posted to the lists, not only commitfest submissions. This is Hackorum's own CI rather than the PostgreSQL project's, and it is still under testing - please report anything that looks wrong.
You can run a PostgreSQL built from this patch straight from Docker, with no checkout and no build:
docker run --rm -p 5432:5432 ghcr.io/hackorum-dev/postgres-patch:t139208psql -h localhost -U postgresBuilt from patchset v5 (message #5), October 26, 2026 at 12:16 AM.
Every patchset is also pushed to a branch of our PostgreSQL fork, so you can check out the same tree CI built. Without a PostgreSQL checkout:
git clone --branch t139208_5 https://github.com/hackorum-dev/postgres.gitIn a checkout you already have, add the fork once:
git remote add hackorum https://github.com/hackorum-dev/postgres.gitthen, for this patchset and every later one:
git fetch hackorum t139208_5 && git checkout t139208_5Patchset v5 (message #5) is on t139208_5
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 /messages/by-id/E9FA92C2921F31408041863B74EE4C2001AEF33492@CCPMAILDAG03.cantab.local
/messages/by-id/E9FA92C2921F31408041863B74EE4C2001AEF33492@CCPMAILDAG03.cantab.local
[2]: "Wasteful nested loop join when there is `limit` in the query", 2025 /messages/by-id/CAAdwFAwm6HwXM_cuPWZBxrxX4E7pBdVg=KcVDSP6q9ume3hYpQ@mail.gmail.com
/messages/by-id/CAAdwFAwm6HwXM_cuPWZBxrxX4E7pBdVg=KcVDSP6q9ume3hYpQ@mail.gmail.com
--
regards, Andrei Lepikhov,
pgEdge
Attachments:
t139208_1v0-0001-Extend-the-ExecSetTupleBound-to-LEFT-JOIN-outer-s.patchtext/plain; charset=UTF-8; name=v0-0001-Extend-the-ExecSetTupleBound-to-LEFT-JOIN-outer-s.patchDownload+23-1
v0-0002-Try-pre-sorted-outer-path-for-a-JOIN.patchtext/plain; charset=UTF-8; name=v0-0002-Try-pre-sorted-outer-path-for-a-JOIN.patchDownload+110-1
v0-0003-Adjust-query-plans-changed.patchtext/plain; charset=UTF-8; name=v0-0003-Adjust-query-plans-changed.patchDownload+228-245
example_schema.sqltext/plain; charset=UTF-8; name=example_schema.sqlDownload
On 03/04/2026 13:35, Andrei Lepikhov wrote:
Feedback and review welcome.
It seems this approach should be reconsidered a little.
By watching how it works in real life, I see cases of planning regression in
massive queries. Just to demonstrate what it looks like, you may check a
concrete example in the attachment. For this specific query, I see the following
difference:
Presorted path enabled:
Planning:
Buffers: shared hit=1682
Memory: used=136930kB allocated=139488kB
Planning Time: 3194.900 ms
Execution Time: 17.681 ms
Presorted path disabled:
Planning:
Buffers: shared hit=1775
Memory: used=136225kB allocated=139488kB
Planning Time: 1328.901 ms
Execution Time: 11.785 ms
In other cases, it also causes memory consumption growth.
The relation_can_be_sorted_early is not cheap. It walks rel->reltarget->exprs,
calls find_ec_member_matching_expr per expression (which walks the EC's
ec_members list), then falls through to find_computable_ec_member, which
traverses the EC again with parser machinery to detect computability. For CASE
expressions across multiple tables — the user's actual sort keys - the EC has
multiple members, none of which match an existing reltarget exactly, so the slow
path runs to completion before returning false.
IMO, the main issue lies in multiple calls of relation_can_be_sorted_early. It
happens multiple times, but may be done once during RelOptInfo creation. We just
need to introduce a useful_query_pathkeys cache.
--
regards, Andrei Lepikhov,
pgEdge
Attachments:
query3.sqltext/plain; charset=UTF-8; name=query3.sqlDownload
Hello!
+ NestLoopState *nlstate = (NestLoopState *) child_node;
+ JoinType jointype = nlstate->js.jointype;
+
+ if (jointype == JOIN_LEFT)Isn't a `nlstate->js.ps.qual == NULL` missing from here?
CREATE TABLE outer_t (id int, k int, payload text);
CREATE TABLE inner_t (id int, fk int, val int);
INSERT INTO outer_t
SELECT g, g, 'row_' || g FROM generate_series(1, 200) g;
INSERT INTO inner_t
SELECT g, g, g FROM generate_series(1, 200) g;
SET enable_hashjoin = off;
SET enable_mergejoin = off;
SET enable_material = off;
SELECT o.id, i.val
FROM outer_t o
LEFT JOIN inner_t i ON o.k = i.fk
WHERE (i.val IS NULL OR i.val > 50)
ORDER BY o.id
LIMIT 10;
+ else if (jointype == JOIN_RIGHT)
+ ExecSetTupleBound(tuples_needed, innerPlanState(child_node));Is this branch reachable? If I follow the code correctly, it can't
happen with create_nestloop_path.
pg_plan_advice also has test failures with the patch applied.
On 13/05/2026 16:03, Zsolt Parragi wrote:
+ else if (jointype == JOIN_RIGHT) + ExecSetTupleBound(tuples_needed, innerPlanState(child_node));Is this branch reachable? If I follow the code correctly, it can't
happen with create_nestloop_path.
RIGHT NL seems like nonsense to me. This code stays here just to remind me to
add a check in the next version, if the community is interested.
pg_plan_advice also has test failures with the patch applied.
We already talked about this in the main thread for pg_plan_advice. Now, it is
unavoidable because pg_plan_advice limits optimisations that expand the planning
scope. Before, it was enough to use standard tools like create_seqscan_path and
add_path and provide a semantically correct plan. Now, every optimisation has to
meet pg_plan_advice's internal rules, which are much more restrictive.
I did not fix this test failure to highlight the unpleasant situation for
extension developers, but you can find the fix in the list [1]/messages/by-id/CAP53Pkw2Lw0bavkCR-ygmaGACBjwmY3Voq0Yhwo9rVOBWxQuyw@mail.gmail.com.
[1]: /messages/by-id/CAP53Pkw2Lw0bavkCR-ygmaGACBjwmY3Voq0Yhwo9rVOBWxQuyw@mail.gmail.com
/messages/by-id/CAP53Pkw2Lw0bavkCR-ygmaGACBjwmY3Voq0Yhwo9rVOBWxQuyw@mail.gmail.com
--
regards, Andrei Lepikhov,
pgEdge
Here is a rebased version of the patch set.
Since the last version, production use has exposed that the 'optimistic'
strategy doesn't work safely: we can't suppose during planning that the outer of
the LEFT JOIN returns no more than 'limit_tuples' rows. Some pushed-down clause
that lands as a join filter in the LEFT JOIN chain might cause the scan node to
return (and sort) far more tuples than planned.
This patch set employs an opportunistic approach: the plan estimation part
assumes full sort of the rows returned by the Scan, and the executor's
ExecSetTupleBound applies boundaries on the Sort node if no one LEFT JOIN node
in the chain contains filters.
The most beneficial strategy should employ something like a Top-Down 'smoothing'
pass after the planning stage, as mentioned [1]/messages/by-id/494586a2-fd9b-44ad-9bb5-4b6cc18bdf53@gmail.com in earlier threads. An
alternative approach is a kind of subtree replanning, as the commit [2]/messages/by-id/E1x020n-00000002XCr-0lpe@gemulon.postgresql.org has
demonstrated recently.
[1]: /messages/by-id/494586a2-fd9b-44ad-9bb5-4b6cc18bdf53@gmail.com
/messages/by-id/494586a2-fd9b-44ad-9bb5-4b6cc18bdf53@gmail.com
[2]: /messages/by-id/E1x020n-00000002XCr-0lpe@gemulon.postgresql.org
/messages/by-id/E1x020n-00000002XCr-0lpe@gemulon.postgresql.org
--
regards, Andrei Lepikhov,
pgEdge