Hi,
While working on this patch, I continued to receive user complaints and had to
fix several corner cases: keeping parameterised paths away from the Sort, and
reconciling the PG19 changes to semi-join unique-ification with earlier
versions. Planning overhead has been an ongoing problem too. Each of these
problems came from building the sorted outer inside join planning, duplicating
what the pathlist machinery already does. That looked like a red flag that join
planning is the wrong place for it, so I went back to the literature and our
code.
After reviewing the literature and the current code, I concluded that we can
simplify the approach.
Simmen et al. [1] call this technique "sort-ahead": a sort required by ORDER BY
(or GROUP BY/DISTINCT) is pushed down into the join tree, and the optimiser
keeps it only where it is cheaper. The main price the planner pays is in the
join search: subtrees with different orders cannot be pruned against each other,
so each extra sort-ahead order multiplies the work. In our case there is only
one order, the one defined by query_pathkeys, so the overhead is a constant
factor.
The new version therefore adds the sorted path once per base relation. It then
competes in add_path() as an index path with the same ordering would: it
survives only if no cheaper path provides that order, and it may displace a more
expensive index path.
In the previous version, only the outer side of a NestLoop could use the
presorted path. Now merge joins, Merge Append and ordered Append over
partitions, unique-ification of a semi-join input, and sort-based grouping can
use it too. The regression tests whose plans changed illustrate multiple use
cases.
A few extra benefits:
1. When a join multiplies rows, the Sort operator on the base relation handles
fewer and narrower tuples than it would after the join, so it is cheaper and
less likely to spill.
2. The sort is costed on a base relation, whose cardinality we estimate much
more reliably than that of a join result. So the cost of the sort itself,
including the risk of spilling to disk, is less exposed to join misestimation
than a Sort placed above the joins.
3. A Sort on a prefix below the join, completed by an Incremental Sort above it,
can be cheaper than a single full Sort at the top.
Note:
The sort key is now evaluated below a join more often, including on rows the
join later removes. This is existing behaviour of Gather Merge and Merge Append
(see [2]); the create_am test had to stop casting relname to regclass for that
reason.
The patch is attached. An addition to pg_plan_advice as well.
Thoughts?
[1] Simmen, Shekita, Malkemus. Fundamental Techniques for Order Optimization.
SIGMOD 1996.
https://cs.uwaterloo.ca/~gweddell/cs798/p57-simmen.pdf
[2] issues with eager aggregation
https://www.postgresql.org/message-id/6e3bb6d2-e981-49a4-9e7d-f18ee06e94a1%40gmail.com
-- AL
From ee97293ba0c5d85fa1c97d7541a3a922283c89e8 Mon Sep 17 00:00:00 2001
From: Andrei Lepikhov <[email protected]>
Date: Tue, 3 Nov 2026 09:18:55 +0100
Subject: [PATCH v0 1/2] pg_plan_advice: Look through a Sort on the outer side
of a NestLoop.
pgpa_decompose_join() already disregards a Sort or IncrementalSort node
beneath a MergeJoin, but assumed that nothing similar can appear
directly under a NestLoop. If the planner pre-sorts the outer input of
a nested loop to deliver the order required by an upper node, the Sort
was taken as the real outer subplan, and pgpa_build_scan() then failed
with "plan node has no RTIs".
Such a Sort is not part of the join strategy, so descend through it in
the same way as we do for MergeJoin, unless an elided node sits on top
of the outer subplan.
---
contrib/pg_plan_advice/pgpa_join.c | 17 +++++++++++++----
1 file changed, 13 insertions(+), 4 deletions(-)
diff --git a/contrib/pg_plan_advice/pgpa_join.c
b/contrib/pg_plan_advice/pgpa_join.c
index acb6073ef52..ee9475dce19 100644
--- a/contrib/pg_plan_advice/pgpa_join.c
+++ b/contrib/pg_plan_advice/pgpa_join.c
@@ -134,7 +134,7 @@ pgpa_unroll_join(pgpa_plan_walker_context *walker, Plan
*plan,
* join tree where the planner decided to initiate parallelism,
*
* (3) Sort and IncrementalSort nodes, which can occur beneath MergeJoin
- * or GatherMerge,
+ * or GatherMerge, or on the outer side of a NestLoop,
*
* (4) Agg and Unique nodes, which can occur when we decide to make the
* nullable side of a semijoin unique and then join the result, and
@@ -309,9 +309,9 @@ pgpa_destroy_join_unroller(pgpa_join_unroller
*join_unroller)
* for all intents and purposes the real inner input is the Hash node's child,
* not the Hash node itself.
*
- * Likewise, a Merge Join may have Sort node on the inner or outer side; if
- * it does, the real input to the join is the Sort node's child, not the
- * Sort node itself.
+ * Likewise, a Merge Join may have Sort node on the inner or outer side, and
+ * a Nested Loop may have one on the outer side; if it does, the real input
+ * to the join is the Sort node's child, not the Sort node itself.
*
* In addition, with a Merge Join or a Nested Loop, the join planning code
* may add additional nodes such as Materialize or Memoize. We regard these
@@ -407,6 +407,15 @@ pgpa_decompose_join(pgpa_plan_walker_context *walker, Plan
*plan,
}
else
strategy = JSTRAT_NESTED_LOOP_PLAIN;
+
+ /*
+ * The planner may also have sorted the outer subplan,
so that the
+ * NestLoop delivers its output in the order required
above it.
+ * Such a Sort is not part of the join strategy, so
look through
+ * it to find the real outer subplan.
+ */
+ if (elidedouter == NULL && is_sorting_plan(outerplan))
+ elidedouter = pgpa_descend_node(pstmt,
&outerplan);
break;
case T_HashJoin:
--
2.56.0
From 14873adac1d42d43c708f2a4d40ef44bafeada76 Mon Sep 17 00:00:00 2001
From: Andrei Lepikhov <[email protected]>
Date: Tue, 3 Nov 2026 14:39:18 +0100
Subject: [PATCH v0 2/2] Add sort-ahead paths for base relations.
If a base relation can be sorted early on a prefix of query_pathkeys,
add an explicit Sort over its cheapest unparameterized path to its
pathlist in set_rel_pathlist(). This gives a relation without a
suitable index what such an index would provide: an ordering that
order-preserving joins, Merge Append, sort-based unique-ification and
grouping can use, so the final ordering may be delivered without a Sort
above the joins. The path competes with others in add_path(), is costed
as a full sort, and is not generated for a single-relation query.
---
contrib/pg_plan_advice/expected/gather.out | 52 +--
.../pg_plan_advice/expected/join_strategy.out | 49 +++
contrib/pg_plan_advice/sql/join_strategy.sql | 13 +
.../postgres_fdw/expected/postgres_fdw.out | 137 ++++----
src/backend/optimizer/path/allpaths.c | 53 +++
.../regress/expected/collate.icu.utf8.out | 22 +-
src/test/regress/expected/create_am.out | 8 +-
src/test/regress/expected/eager_aggregate.out | 24 +-
.../regress/expected/incremental_sort.out | 45 +--
src/test/regress/expected/inherit.out | 12 +-
src/test/regress/expected/join.out | 295 +++++++++++------
src/test/regress/expected/partition_join.out | 311 ++++++++++--------
src/test/regress/expected/subselect.out | 7 +-
src/test/regress/expected/tablesample.out | 8 +-
src/test/regress/expected/tuplesort.out | 42 +--
src/test/regress/sql/create_am.sql | 8 +-
src/test/regress/sql/incremental_sort.sql | 7 +-
src/test/regress/sql/join.sql | 38 +++
18 files changed, 723 insertions(+), 408 deletions(-)
diff --git a/contrib/pg_plan_advice/expected/gather.out
b/contrib/pg_plan_advice/expected/gather.out
index 60f2b32e24f..3577ed5b2fe 100644
--- a/contrib/pg_plan_advice/expected/gather.out
+++ b/contrib/pg_plan_advice/expected/gather.out
@@ -161,17 +161,18 @@ EXPLAIN (COSTS OFF, PLAN_ADVICE)
-> Sort
Sort Key: f.dim_id
-> Parallel Seq Scan on gt_fact f
- -> Index Scan using gt_dim_pkey on gt_dim d
+ -> Sort
+ Sort Key: d.id
+ -> Seq Scan on gt_dim d
Supplied Plan Advice:
GATHER((d d/d.d)) /* partially matched */
Generated Plan Advice:
JOIN_ORDER(f d)
MERGE_JOIN_PLAIN(d)
- SEQ_SCAN(f)
- INDEX_SCAN(d public.gt_dim_pkey)
+ SEQ_SCAN(f d)
GATHER_MERGE(f)
NO_GATHER(d)
-(17 rows)
+(18 rows)
COMMIT;
-- Force a Gather or Gather Merge on one relation but no parallelism on other.
@@ -188,18 +189,19 @@ EXPLAIN (COSTS OFF, PLAN_ADVICE)
-> Sort
Sort Key: f.dim_id
-> Parallel Seq Scan on gt_fact f
- -> Index Scan using gt_dim_pkey on gt_dim d
+ -> Sort
+ Sort Key: d.id
+ -> Seq Scan on gt_dim d
Supplied Plan Advice:
GATHER_MERGE(f) /* matched */
NO_GATHER(d) /* matched */
Generated Plan Advice:
JOIN_ORDER(f d)
MERGE_JOIN_PLAIN(d)
- SEQ_SCAN(f)
- INDEX_SCAN(d public.gt_dim_pkey)
+ SEQ_SCAN(f d)
GATHER_MERGE(f)
NO_GATHER(d)
-(18 rows)
+(19 rows)
SET LOCAL pg_plan_advice.advice = 'gather_merge(d) no_gather(f)';
EXPLAIN (COSTS OFF, PLAN_ADVICE)
@@ -233,24 +235,25 @@ EXPLAIN (COSTS OFF, PLAN_ADVICE)
QUERY PLAN
--------------------------------------------------
Merge Join
- Merge Cond: (d.id = f.dim_id)
- -> Index Scan using gt_dim_pkey on gt_dim d
+ Merge Cond: (f.dim_id = d.id)
-> Sort
Sort Key: f.dim_id
-> Gather
Workers Planned: 1
-> Parallel Seq Scan on gt_fact f
+ -> Sort
+ Sort Key: d.id
+ -> Seq Scan on gt_dim d
Supplied Plan Advice:
GATHER(f) /* matched */
NO_GATHER(d) /* matched */
Generated Plan Advice:
- JOIN_ORDER(d f)
- MERGE_JOIN_PLAIN(f)
- SEQ_SCAN(f)
- INDEX_SCAN(d public.gt_dim_pkey)
+ JOIN_ORDER(f d)
+ MERGE_JOIN_PLAIN(d)
+ SEQ_SCAN(f d)
GATHER(f)
NO_GATHER(d)
-(18 rows)
+(19 rows)
SET LOCAL pg_plan_advice.advice = 'gather(d) no_gather(f)';
EXPLAIN (COSTS OFF, PLAN_ADVICE)
@@ -284,24 +287,25 @@ BEGIN;
SET LOCAL pg_plan_advice.advice = 'no_gather(f d)';
EXPLAIN (COSTS OFF, PLAN_ADVICE)
SELECT * FROM gt_fact f JOIN gt_dim d ON f.dim_id = d.id ORDER BY d.id;
- QUERY PLAN
-------------------------------------------------
+ QUERY PLAN
+-----------------------------------
Merge Join
- Merge Cond: (d.id = f.dim_id)
- -> Index Scan using gt_dim_pkey on gt_dim d
+ Merge Cond: (f.dim_id = d.id)
-> Sort
Sort Key: f.dim_id
-> Seq Scan on gt_fact f
+ -> Sort
+ Sort Key: d.id
+ -> Seq Scan on gt_dim d
Supplied Plan Advice:
NO_GATHER(f) /* matched */
NO_GATHER(d) /* matched */
Generated Plan Advice:
- JOIN_ORDER(d f)
- MERGE_JOIN_PLAIN(f)
- SEQ_SCAN(f)
- INDEX_SCAN(d public.gt_dim_pkey)
+ JOIN_ORDER(f d)
+ MERGE_JOIN_PLAIN(d)
+ SEQ_SCAN(f d)
NO_GATHER(f d)
-(15 rows)
+(16 rows)
COMMIT;
-- Can't force Gather Merge without the ORDER BY clause, but just Gather is OK.
diff --git a/contrib/pg_plan_advice/expected/join_strategy.out
b/contrib/pg_plan_advice/expected/join_strategy.out
index 0f9db692190..be9913bd1a4 100644
--- a/contrib/pg_plan_advice/expected/join_strategy.out
+++ b/contrib/pg_plan_advice/expected/join_strategy.out
@@ -337,3 +337,52 @@ EXPLAIN (COSTS OFF, PLAN_ADVICE)
(14 rows)
COMMIT;
+-- The planner may sort the outer side of a nested loop to deliver the
+-- ORDER BY. That Sort is not part of the join strategy: advice must still
+-- be generated for such a plan, and must be applicable back to it.
+EXPLAIN (COSTS OFF, PLAN_ADVICE)
+ SELECT * FROM join_dim d JOIN join_fact f ON f.dim_id = d.id
+ ORDER BY d.dim LIMIT 10;
+ QUERY PLAN
+--------------------------------------------------------------
+ Limit
+ -> Nested Loop
+ -> Sort
+ Sort Key: d.dim
+ -> Seq Scan on join_dim d
+ -> Index Scan using join_fact_dim_id on join_fact f
+ Index Cond: (dim_id = d.id)
+ Generated Plan Advice:
+ JOIN_ORDER(d f)
+ NESTED_LOOP_PLAIN(f)
+ SEQ_SCAN(d)
+ INDEX_SCAN(f public.join_fact_dim_id)
+ NO_GATHER(d f)
+(13 rows)
+
+BEGIN;
+SET LOCAL pg_plan_advice.advice = 'JOIN_ORDER(d f) NESTED_LOOP_PLAIN(f)';
+EXPLAIN (COSTS OFF, PLAN_ADVICE)
+ SELECT * FROM join_dim d JOIN join_fact f ON f.dim_id = d.id
+ ORDER BY d.dim LIMIT 10;
+ QUERY PLAN
+--------------------------------------------------------------
+ Limit
+ -> Nested Loop
+ -> Sort
+ Sort Key: d.dim
+ -> Seq Scan on join_dim d
+ -> Index Scan using join_fact_dim_id on join_fact f
+ Index Cond: (dim_id = d.id)
+ Supplied Plan Advice:
+ JOIN_ORDER(d f) /* matched */
+ NESTED_LOOP_PLAIN(f) /* matched */
+ Generated Plan Advice:
+ JOIN_ORDER(d f)
+ NESTED_LOOP_PLAIN(f)
+ SEQ_SCAN(d)
+ INDEX_SCAN(f public.join_fact_dim_id)
+ NO_GATHER(d f)
+(16 rows)
+
+COMMIT;
diff --git a/contrib/pg_plan_advice/sql/join_strategy.sql
b/contrib/pg_plan_advice/sql/join_strategy.sql
index edd5c4c0e14..57f54e79f7d 100644
--- a/contrib/pg_plan_advice/sql/join_strategy.sql
+++ b/contrib/pg_plan_advice/sql/join_strategy.sql
@@ -82,3 +82,16 @@ SET LOCAL pg_plan_advice.advice = 'NESTED_LOOP_PLAIN(f d)';
EXPLAIN (COSTS OFF, PLAN_ADVICE)
SELECT * FROM join_fact f JOIN join_dim d ON f.dim_id = d.id;
COMMIT;
+
+-- The planner may sort the outer side of a nested loop to deliver the
+-- ORDER BY. That Sort is not part of the join strategy: advice must still
+-- be generated for such a plan, and must be applicable back to it.
+EXPLAIN (COSTS OFF, PLAN_ADVICE)
+ SELECT * FROM join_dim d JOIN join_fact f ON f.dim_id = d.id
+ ORDER BY d.dim LIMIT 10;
+BEGIN;
+SET LOCAL pg_plan_advice.advice = 'JOIN_ORDER(d f) NESTED_LOOP_PLAIN(f)';
+EXPLAIN (COSTS OFF, PLAN_ADVICE)
+ SELECT * FROM join_dim d JOIN join_fact f ON f.dim_id = d.id
+ ORDER BY d.dim LIMIT 10;
+COMMIT;
diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out
b/contrib/postgres_fdw/expected/postgres_fdw.out
index 115ebc7925f..d37133fe5e9 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -2295,21 +2295,21 @@ SELECT t1.c1, t2.c1 FROM ft1 t1 LEFT JOIN ft2 t2 ON
(t1.c8 = t2.c8) ORDER BY t1.
-------------------------------------------------------------------------
Limit
Output: t1.c1, t2.c1
- -> Sort
+ -> Incremental Sort
Output: t1.c1, t2.c1
Sort Key: t1.c1, t2.c1
- -> Merge Left Join
+ Presorted Key: t1.c1
+ -> Nested Loop Left Join
Output: t1.c1, t2.c1
- Merge Cond: (t1.c8 = t2.c8)
+ Join Filter: (t1.c8 = t2.c8)
-> Sort
Output: t1.c1, t1.c8
- Sort Key: t1.c8
+ Sort Key: t1.c1
-> Foreign Scan on public.ft1 t1
Output: t1.c1, t1.c8
Remote SQL: SELECT "C 1", c8 FROM "S 1"."T 1"
- -> Sort
+ -> Materialize
Output: t2.c1, t2.c8
- Sort Key: t2.c8
-> Foreign Scan on public.ft2 t2
Output: t2.c1, t2.c8
Remote SQL: SELECT "C 1", c8 FROM "S 1"."T 1"
@@ -4514,24 +4514,24 @@ select sum(c2) * (random() <= 1)::int as sum from ft1
order by 1;
set enable_hashagg to false;
explain (verbose, costs off)
select c2, sum from "S 1"."T 1" t1, lateral (select sum(t2.c1 + t1."C 1") sum
from ft2 t2 group by t2.c1) qry where t1.c2 * 2 = qry.sum and t1.c2 < 3 and
t1."C 1" < 100 order by 1;
- QUERY PLAN
-------------------------------------------------------------------------------------------------------
- Sort
+ QUERY PLAN
+------------------------------------------------------------------------------------------------
+ Nested Loop
Output: t1.c2, qry.sum
- Sort Key: t1.c2
- -> Nested Loop
- Output: t1.c2, qry.sum
+ -> Sort
+ Output: t1.c2, t1."C 1"
+ Sort Key: t1.c2
-> Index Scan using t1_pkey on "S 1"."T 1" t1
- Output: t1."C 1", t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7,
t1.c8
+ Output: t1.c2, t1."C 1"
Index Cond: (t1."C 1" < 100)
Filter: (t1.c2 < 3)
- -> Subquery Scan on qry
- Output: qry.sum, t2.c1
- Filter: ((t1.c2 * 2) = qry.sum)
- -> Foreign Scan
- Output: (sum((t2.c1 + t1."C 1"))), t2.c1
- Relations: Aggregate on (public.ft2 t2)
- Remote SQL: SELECT sum(("C 1" + $1::integer)), "C 1" FROM
"S 1"."T 1" GROUP BY 2
+ -> Subquery Scan on qry
+ Output: qry.sum, t2.c1
+ Filter: ((t1.c2 * 2) = qry.sum)
+ -> Foreign Scan
+ Output: (sum((t2.c1 + t1."C 1"))), t2.c1
+ Relations: Aggregate on (public.ft2 t2)
+ Remote SQL: SELECT sum(("C 1" + $1::integer)), "C 1" FROM "S
1"."T 1" GROUP BY 2
(16 rows)
select c2, sum from "S 1"."T 1" t1, lateral (select sum(t2.c1 + t1."C 1") sum
from ft2 t2 group by t2.c1) qry where t1.c2 * 2 = qry.sum and t1.c2 < 3 and
t1."C 1" < 100 order by 1;
@@ -7095,26 +7095,23 @@ BEGIN;
-> Nested Loop
Output: ft2.ctid, ft2.*, ft4.*, ft5.*, ft4.c1, ft4.c2, ft4.c3
Join Filter: (ft4.c1 = ft5.c1)
- -> Sort
+ -> Hash Join
Output: ft2.ctid, ft2.*, ft2.c2, ft4.*, ft4.c1, ft4.c2,
ft4.c3
- Sort Key: ft2.c2
- -> Hash Join
- Output: ft2.ctid, ft2.*, ft2.c2, ft4.*, ft4.c1,
ft4.c2, ft4.c3
- Hash Cond: (ft2.c2 = ft4.c1)
- -> Foreign Scan on public.ft2
- Output: ft2.ctid, ft2.*, ft2.c2
- Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6,
c7, c8, ctid FROM "S 1"."T 1" WHERE (("C 1" > 1200)) FOR UPDATE
- -> Hash
+ Hash Cond: (ft2.c2 = ft4.c1)
+ -> Foreign Scan on public.ft2
+ Output: ft2.ctid, ft2.*, ft2.c2
+ Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7,
c8, ctid FROM "S 1"."T 1" WHERE (("C 1" > 1200)) FOR UPDATE
+ -> Hash
+ Output: ft4.*, ft4.c1, ft4.c2, ft4.c3
+ -> Foreign Scan on public.ft4
Output: ft4.*, ft4.c1, ft4.c2, ft4.c3
- -> Foreign Scan on public.ft4
- Output: ft4.*, ft4.c1, ft4.c2, ft4.c3
- Remote SQL: SELECT c1, c2, c3 FROM "S
1"."T 3"
+ Remote SQL: SELECT c1, c2, c3 FROM "S 1"."T 3"
-> Materialize
Output: ft5.*, ft5.c1
-> Foreign Scan on public.ft5
Output: ft5.*, ft5.c1
Remote SQL: SELECT c1, c2, c3 FROM "S 1"."T 4"
-(29 rows)
+(26 rows)
UPDATE ft2 SET c3 = 'bar'
FROM ft4 INNER JOIN ft5 ON (ft4.c1 = ft5.c1)
@@ -11291,13 +11288,15 @@ SELECT t1.a, t2.b FROM fprt1 t1 INNER JOIN fprt2 t2
ON (t1.a = t2.b) WHERE t1.a
-> Nested Loop
Join Filter: (t1.a = t2.b)
-> Append
- -> Foreign Scan on ftprt1_p1 t1_1
+ -> Sort
+ Sort Key: t1_1.a
+ -> Foreign Scan on ftprt1_p1 t1_1
-> Foreign Scan on ftprt1_p2 t1_2
-> Materialize
-> Append
-> Foreign Scan on ftprt2_p1 t2_1
-> Foreign Scan on ftprt2_p2 t2_2
-(10 rows)
+(12 rows)
SELECT t1.a, t2.b FROM fprt1 t1 INNER JOIN fprt2 t2 ON (t1.a = t2.b) WHERE
t1.a % 25 = 0 ORDER BY 1,2 FOR UPDATE OF t1;
a | b
@@ -12412,27 +12411,27 @@ DELETE FROM result_tbl;
-- (case where subplans are re-scanned with parameter changes)
EXPLAIN (VERBOSE, COSTS OFF)
SELECT o.x FROM (VALUES (2505), (3505)) o(x), LATERAL (SELECT a FROM async_pt
WHERE a = o.x OR a = 1505 LIMIT 1) s ORDER BY o.x;
- QUERY PLAN
--------------------------------------------------------------------------------------------------------------------
- Sort
+ QUERY PLAN
+-------------------------------------------------------------------------------------------------------------
+ Nested Loop
Output: "*VALUES*".column1
- Sort Key: "*VALUES*".column1
- -> Nested Loop
+ -> Sort
Output: "*VALUES*".column1
+ Sort Key: "*VALUES*".column1
-> Values Scan on "*VALUES*"
Output: "*VALUES*".column1
- -> Limit
- Output: NULL::integer
- -> Append
- -> Async Foreign Scan on public.async_p1 async_pt_1
- Output: NULL::integer
- Remote SQL: SELECT NULL FROM public.base_tbl1 WHERE
(((a = $1::integer) OR (a = 1505)))
- -> Async Foreign Scan on public.async_p2 async_pt_2
- Output: NULL::integer
- Remote SQL: SELECT NULL FROM public.base_tbl2 WHERE
(((a = $1::integer) OR (a = 1505)))
- -> Async Foreign Scan on public.async_p3 async_pt_3
- Output: NULL::integer
- Remote SQL: SELECT NULL FROM public.base_tbl3 WHERE
(((a = $1::integer) OR (a = 1505)))
+ -> Limit
+ Output: NULL::integer
+ -> Append
+ -> Async Foreign Scan on public.async_p1 async_pt_1
+ Output: NULL::integer
+ Remote SQL: SELECT NULL FROM public.base_tbl1 WHERE (((a
= $1::integer) OR (a = 1505)))
+ -> Async Foreign Scan on public.async_p2 async_pt_2
+ Output: NULL::integer
+ Remote SQL: SELECT NULL FROM public.base_tbl2 WHERE (((a
= $1::integer) OR (a = 1505)))
+ -> Async Foreign Scan on public.async_p3 async_pt_3
+ Output: NULL::integer
+ Remote SQL: SELECT NULL FROM public.base_tbl3 WHERE (((a
= $1::integer) OR (a = 1505)))
(19 rows)
SELECT o.x FROM (VALUES (2505), (3505)) o(x), LATERAL (SELECT a FROM async_pt
WHERE a = o.x OR a = 1505 LIMIT 1) s ORDER BY o.x;
@@ -12444,27 +12443,27 @@ SELECT o.x FROM (VALUES (2505), (3505)) o(x), LATERAL
(SELECT a FROM async_pt WH
EXPLAIN (VERBOSE, COSTS OFF)
SELECT o.x FROM (VALUES (2505), (3505)) o(x), LATERAL (SELECT a FROM async_pt
WHERE a = o.x OR (a = 1505 AND o.x = 2505) LIMIT 1) s ORDER BY o.x;
- QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------
- Sort
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------------------------------------
+ Nested Loop
Output: "*VALUES*".column1
- Sort Key: "*VALUES*".column1
- -> Nested Loop
+ -> Sort
Output: "*VALUES*".column1
+ Sort Key: "*VALUES*".column1
-> Values Scan on "*VALUES*"
Output: "*VALUES*".column1
- -> Limit
- Output: NULL::integer
- -> Append
- -> Async Foreign Scan on public.async_p1 async_pt_1
- Output: NULL::integer
- Remote SQL: SELECT NULL FROM public.base_tbl1 WHERE
(((a = $1::integer) OR ((a = 1505) AND ($1::integer = 2505))))
- -> Async Foreign Scan on public.async_p2 async_pt_2
- Output: NULL::integer
- Remote SQL: SELECT NULL FROM public.base_tbl2 WHERE
(((a = $1::integer) OR ((a = 1505) AND ($1::integer = 2505))))
- -> Async Foreign Scan on public.async_p3 async_pt_3
- Output: NULL::integer
- Remote SQL: SELECT NULL FROM public.base_tbl3 WHERE
(((a = $1::integer) OR ((a = 1505) AND ($1::integer = 2505))))
+ -> Limit
+ Output: NULL::integer
+ -> Append
+ -> Async Foreign Scan on public.async_p1 async_pt_1
+ Output: NULL::integer
+ Remote SQL: SELECT NULL FROM public.base_tbl1 WHERE (((a
= $1::integer) OR ((a = 1505) AND ($1::integer = 2505))))
+ -> Async Foreign Scan on public.async_p2 async_pt_2
+ Output: NULL::integer
+ Remote SQL: SELECT NULL FROM public.base_tbl2 WHERE (((a
= $1::integer) OR ((a = 1505) AND ($1::integer = 2505))))
+ -> Async Foreign Scan on public.async_p3 async_pt_3
+ Output: NULL::integer
+ Remote SQL: SELECT NULL FROM public.base_tbl3 WHERE (((a
= $1::integer) OR ((a = 1505) AND ($1::integer = 2505))))
(19 rows)
SELECT o.x FROM (VALUES (2505), (3505)) o(x), LATERAL (SELECT a FROM async_pt
WHERE a = o.x OR (a = 1505 AND o.x = 2505) LIMIT 1) s ORDER BY o.x;
diff --git a/src/backend/optimizer/path/allpaths.c
b/src/backend/optimizer/path/allpaths.c
index 72ad61e8c24..798bee97429 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -103,6 +103,10 @@ static void set_rel_pathlist(PlannerInfo *root, RelOptInfo
*rel,
static void set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel,
RangeTblEntry *rte);
static void create_plain_partial_paths(PlannerInfo *root, RelOptInfo *rel);
+static List *get_useful_pathkeys_for_relation(PlannerInfo *root,
+
RelOptInfo *rel,
+
bool require_parallel_safe);
+static void generate_presorted_paths(PlannerInfo *root, RelOptInfo *rel);
static void set_rel_consider_parallel(PlannerInfo *root, RelOptInfo *rel,
RangeTblEntry *rte);
static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
@@ -607,6 +611,13 @@ set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
!bms_equal(rel->relids, root->all_query_rels))
generate_useful_gather_paths(root, rel, false);
+ /*
+ * Offer an explicitly sorted path on a prefix of query_pathkeys. With
a
+ * single base relation there is no join to push the sort below.
+ */
+ if (bms_membership(root->all_baserels) == BMS_MULTIPLE)
+ generate_presorted_paths(root, rel);
+
/* Now find the cheapest of the paths for this rel */
set_cheapest(rel);
@@ -3382,6 +3393,48 @@ get_useful_pathkeys_for_relation(PlannerInfo *root,
RelOptInfo *rel,
return useful_pathkeys_list;
}
+/*
+ * generate_presorted_paths
+ * Add an explicitly sorted path on a useful prefix of
query_pathkeys.
+ *
+ * query_pathkeys stands for whatever ordering the upper planner wants first:
+ * GROUP BY, window, DISTINCT or ORDER BY. A relation sorted on a prefix of
+ * it pays off wherever a consumer above can exploit an existing order.
+ *
+ * Index paths with such an ordering already survive in the pathlist. This
+ * provides the same for relations with no suitable index, or that are not
plain
+ * tables at all.
+ */
+static void
+generate_presorted_paths(PlannerInfo *root, RelOptInfo *rel)
+{
+ List *useful_pathkeys_list;
+ Path *cheapest;
+
+ /* Nothing to order, or the rel is proven empty */
+ if (root->query_pathkeys == NIL || IS_DUMMY_REL(rel))
+ return;
+
+ useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel,
false);
+ if (useful_pathkeys_list == NIL)
+ return;
+
+ /* rel->cheapest_total_path is not set yet; set_cheapest() comes later
*/
+ cheapest = get_cheapest_path_for_pathkeys(rel->pathlist, NIL, NULL,
+
TOTAL_COST, false);
+ if (cheapest == NULL)
+ return;
+
+ foreach_ptr(List, useful_pathkeys, useful_pathkeys_list)
+ {
+ if (pathkeys_contained_in(useful_pathkeys, cheapest->pathkeys))
+ continue;
+
+ add_path(rel, (Path *) create_sort_path(root, rel, cheapest,
+
useful_pathkeys, -1.0));
+ }
+}
+
/*
* generate_useful_gather_paths
* Generate parallel access paths for a relation by pushing a
Gather or
diff --git a/src/test/regress/expected/collate.icu.utf8.out
b/src/test/regress/expected/collate.icu.utf8.out
index 69b2f5109ad..b467d9aba60 100644
--- a/src/test/regress/expected/collate.icu.utf8.out
+++ b/src/test/regress/expected/collate.icu.utf8.out
@@ -3694,26 +3694,30 @@ INSERT INTO pagg_tab6 (b, c) SELECT substr('cdCD', (i %
4) + 1 , 1), substr('cdC
ANALYZE pagg_tab6;
EXPLAIN (COSTS OFF)
SELECT t1.c, count(t2.c) FROM pagg_tab5 t1 JOIN pagg_tab6 t2 ON t1.c = t2.c
AND t1.c = t2.b GROUP BY 1 ORDER BY t1.c COLLATE "C";
- QUERY PLAN
--------------------------------------------------------
+ QUERY PLAN
+---------------------------------------------------------------------
Sort
Sort Key: t1.c COLLATE "C"
-> Append
- -> HashAggregate
+ -> GroupAggregate
Group Key: t1.c
-> Nested Loop
Join Filter: (t1.c = t2.c)
- -> Seq Scan on pagg_tab6_p1 t2
- Filter: (c = b)
+ -> Sort
+ Sort Key: t2.c COLLATE case_insensitive
+ -> Seq Scan on pagg_tab6_p1 t2
+ Filter: (c = b)
-> Seq Scan on pagg_tab5_p1 t1
- -> HashAggregate
+ -> GroupAggregate
Group Key: t1_1.c
-> Nested Loop
Join Filter: (t1_1.c = t2_1.c)
- -> Seq Scan on pagg_tab6_p2 t2_1
- Filter: (c = b)
+ -> Sort
+ Sort Key: t2_1.c COLLATE case_insensitive
+ -> Seq Scan on pagg_tab6_p2 t2_1
+ Filter: (c = b)
-> Seq Scan on pagg_tab5_p2 t1_1
-(17 rows)
+(21 rows)
SELECT t1.c, count(t2.c) FROM pagg_tab5 t1 JOIN pagg_tab6 t2 ON t1.c = t2.c
AND t1.c = t2.b GROUP BY 1 ORDER BY t1.c COLLATE "C";
c | count
diff --git a/src/test/regress/expected/create_am.out
b/src/test/regress/expected/create_am.out
index c1a95157251..f99b6ded9f9 100644
--- a/src/test/regress/expected/create_am.out
+++ b/src/test/regress/expected/create_am.out
@@ -201,9 +201,9 @@ SELECT
pc.relkind,
pa.amname,
CASE WHEN relkind = 't' THEN
- (SELECT 'toast for ' || relname::regclass FROM pg_class pcm WHERE
pcm.reltoastrelid = pc.oid)
+ (SELECT 'toast for ' || pcm.oid::regclass FROM pg_class pcm WHERE
pcm.reltoastrelid = pc.oid)
ELSE
- relname::regclass::text
+ pc.oid::regclass::text
END COLLATE "C" AS relname
FROM pg_class AS pc,
pg_am AS pa
@@ -525,9 +525,9 @@ SELECT
pc.relkind,
pa.amname,
CASE WHEN relkind = 't' THEN
- (SELECT 'toast for ' || relname::regclass FROM pg_class pcm WHERE
pcm.reltoastrelid = pc.oid)
+ (SELECT 'toast for ' || pcm.oid::regclass FROM pg_class pcm WHERE
pcm.reltoastrelid = pc.oid)
ELSE
- relname::regclass::text
+ pc.oid::regclass::text
END COLLATE "C" AS relname
FROM pg_class AS pc
LEFT JOIN pg_am AS pa ON (pa.oid = pc.relam)
diff --git a/src/test/regress/expected/eager_aggregate.out
b/src/test/regress/expected/eager_aggregate.out
index bdda7da68f0..5d64e48a6f9 100644
--- a/src/test/regress/expected/eager_aggregate.out
+++ b/src/test/regress/expected/eager_aggregate.out
@@ -589,24 +589,24 @@ SELECT s1.a, sum(s2.c)
FROM eager_agg_s1 s1
JOIN eager_agg_s2 s2 ON s1.a = s2.b
GROUP BY s1.a;
- QUERY PLAN
-------------------------------------------------------------
+ QUERY PLAN
+------------------------------------------------------
Finalize GroupAggregate
Output: s1.a, sum(s2.c)
Group Key: s1.a
- -> Sort
+ -> Nested Loop
Output: s1.a, (PARTIAL sum(s2.c))
- Sort Key: s1.a
- -> Nested Loop
- Output: s1.a, (PARTIAL sum(s2.c))
- Join Filter: (s1.a = s2.b)
+ Join Filter: (s1.a = s2.b)
+ -> Sort
+ Output: s1.a
+ Sort Key: s1.a
-> Seq Scan on public.eager_agg_s1 s1
Output: s1.a
- -> Partial HashAggregate
- Output: s2.b, PARTIAL sum(s2.c)
- Group Key: s2.b
- -> Seq Scan on public.eager_agg_s2 s2
- Output: s2.b, s2.c
+ -> Partial HashAggregate
+ Output: s2.b, PARTIAL sum(s2.c)
+ Group Key: s2.b
+ -> Seq Scan on public.eager_agg_s2 s2
+ Output: s2.b, s2.c
(16 rows)
SELECT s1.a, sum(s2.c)
diff --git a/src/test/regress/expected/incremental_sort.out
b/src/test/regress/expected/incremental_sort.out
index 1e6e020fea8..5b9ab4494c5 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1610,16 +1610,16 @@ from tenk1 t, generate_series(1, 1000);
QUERY PLAN
---------------------------------------------------------------------------------
Unique
- -> Sort
- Sort Key: t.unique1, ((SubPlan expr_1))
- -> Gather
- Workers Planned: 2
- -> Nested Loop
+ -> Nested Loop
+ -> Sort
+ Sort Key: t.unique1, ((SubPlan expr_1))
+ -> Gather
+ Workers Planned: 2
-> Parallel Index Only Scan using tenk1_unique1 on tenk1
t
- -> Function Scan on generate_series
- SubPlan expr_1
- -> Index Only Scan using tenk1_unique1 on tenk1
- Index Cond: (unique1 = t.unique1)
+ SubPlan expr_1
+ -> Index Only Scan using tenk1_unique1 on tenk1
+ Index Cond: (unique1 = t.unique1)
+ -> Function Scan on generate_series
(11 rows)
explain (costs off) select
@@ -1629,16 +1629,16 @@ from tenk1 t, generate_series(1, 1000)
order by 1, 2;
QUERY PLAN
---------------------------------------------------------------------------
- Sort
- Sort Key: t.unique1, ((SubPlan expr_1))
- -> Gather
- Workers Planned: 2
- -> Nested Loop
+ Nested Loop
+ -> Sort
+ Sort Key: t.unique1, ((SubPlan expr_1))
+ -> Gather
+ Workers Planned: 2
-> Parallel Index Only Scan using tenk1_unique1 on tenk1 t
- -> Function Scan on generate_series
- SubPlan expr_1
- -> Index Only Scan using tenk1_unique1 on tenk1
- Index Cond: (unique1 = t.unique1)
+ SubPlan expr_1
+ -> Index Only Scan using tenk1_unique1 on tenk1
+ Index Cond: (unique1 = t.unique1)
+ -> Function Scan on generate_series
(10 rows)
-- Parallel sort but with expression not available until the upper rel.
@@ -1703,15 +1703,17 @@ explain (costs off) select a, b, a <-> point(5, 5) dist
from point_table order b
Order By: (a <-> '(5,5)'::point)
(6 rows)
--- Ensure we get an incremental sort on the outer side of the mergejoin
+-- Ensure we get an incremental sort on the outer side of the mergejoin.
+-- Use a left join so that the ORDER BY can only be satisfied by t1.
+set enable_nestloop = off;
explain (costs off)
select * from
- (select * from tenk1 order by four) t1 join tenk1 t2 on t1.four = t2.four
and t1.two = t2.two
+ (select * from tenk1 order by four) t1 left join tenk1 t2 on t1.four =
t2.four and t1.two = t2.two
order by t1.four, t1.two limit 1;
QUERY PLAN
-----------------------------------------------------------------------
Limit
- -> Merge Join
+ -> Merge Left Join
Merge Cond: ((tenk1.four = t2.four) AND (tenk1.two = t2.two))
-> Incremental Sort
Sort Key: tenk1.four, tenk1.two
@@ -1724,6 +1726,7 @@ order by t1.four, t1.two limit 1;
-> Seq Scan on tenk1 t2
(12 rows)
+reset enable_nestloop;
--
-- Test incremental sort for Append/MergeAppend
--
diff --git a/src/test/regress/expected/inherit.out
b/src/test/regress/expected/inherit.out
index 036fd39174f..4ae13414617 100644
--- a/src/test/regress/expected/inherit.out
+++ b/src/test/regress/expected/inherit.out
@@ -2050,16 +2050,20 @@ order by t1.b limit 10;
Merge Cond: (t1.b = t2.b)
-> Merge Append
Sort Key: t1.b
- -> Index Scan using matest0i on matest0 t1_1
+ -> Sort
+ Sort Key: t1_1.b
+ -> Seq Scan on matest0 t1_1
-> Index Scan using matest1i on matest1 t1_2
-> Materialize
-> Merge Append
Sort Key: t2.b
- -> Index Scan using matest0i on matest0 t2_1
- Filter: (c = d)
+ -> Sort
+ Sort Key: t2_1.b
+ -> Seq Scan on matest0 t2_1
+ Filter: (c = d)
-> Index Scan using matest1i on matest1 t2_2
Filter: (c = d)
-(14 rows)
+(18 rows)
reset enable_nestloop;
drop table matest0 cascade;
diff --git a/src/test/regress/expected/join.out
b/src/test/regress/expected/join.out
index 4ec9291833b..9d59c337d3d 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -2844,18 +2844,16 @@ order by x.thousand desc, x.twothousand;
----------------------------------------------------------------------------------------
Finalize GroupAggregate
Group Key: x.thousand, x.twothousand
- -> Incremental Sort
- Sort Key: x.thousand DESC, x.twothousand
- Presorted Key: x.thousand
- -> Merge Join
- Merge Cond: (y.thousand = x.thousand)
+ -> Merge Join
+ Merge Cond: (x.thousand = y.thousand)
+ -> Sort
+ Sort Key: x.thousand DESC, x.twothousand
+ -> Seq Scan on tenk1 x
+ -> Materialize
-> Partial GroupAggregate
Group Key: y.thousand
-> Index Only Scan Backward using tenk1_thous_tenthous
on tenk1 y
- -> Sort
- Sort Key: x.thousand DESC
- -> Seq Scan on tenk1 x
-(13 rows)
+(11 rows)
reset enable_hashagg;
reset enable_nestloop;
@@ -4524,29 +4522,29 @@ from int8_tbl t1 left join
cross join (select from int4_tbl where f1 = 0) t3) t23
on (t1.q1 = 123)
order by 1, 2;
- QUERY PLAN
-----------------------------------------------------------------
- Sort
- Output: t1.q1, t1.q2, ((SubPlan expr_1))
- Sort Key: t1.q1, t1.q2
- -> Nested Loop Left Join
- Output: t1.q1, t1.q2, (SubPlan expr_1)
- Join Filter: (t1.q1 = 123)
+ QUERY PLAN
+----------------------------------------------------------
+ Nested Loop Left Join
+ Output: t1.q1, t1.q2, (SubPlan expr_1)
+ Join Filter: (t1.q1 = 123)
+ -> Sort
+ Output: t1.q1, t1.q2
+ Sort Key: t1.q1, t1.q2
-> Seq Scan on public.int8_tbl t1
Output: t1.q1, t1.q2
- -> Materialize
- Output: ('()'::record)
- -> Nested Loop
- Output: '()'::record
- -> Seq Scan on public.int4_tbl
- Output: int4_tbl.f1
- Filter: (int4_tbl.f1 = 0)
- -> Seq Scan on public.int4_tbl int4_tbl_1
- Output: int4_tbl_1.f1
- Filter: (int4_tbl_1.f1 = 0)
- SubPlan expr_1
- -> Result
- Output: (('()'::record))::text
+ -> Materialize
+ Output: ('()'::record)
+ -> Nested Loop
+ Output: '()'::record
+ -> Seq Scan on public.int4_tbl
+ Output: int4_tbl.f1
+ Filter: (int4_tbl.f1 = 0)
+ -> Seq Scan on public.int4_tbl int4_tbl_1
+ Output: int4_tbl_1.f1
+ Filter: (int4_tbl_1.f1 = 0)
+ SubPlan expr_1
+ -> Result
+ Output: (('()'::record))::text
(21 rows)
select t1.q1, t1.q2, (select t23::text)
@@ -4573,31 +4571,31 @@ from int8_tbl t1 left join
on (t1.q1 = 123),
length(t23::text) f
order by 1, 2;
- QUERY PLAN
-----------------------------------------------------------------------
- Sort
+ QUERY PLAN
+----------------------------------------------------------------
+ Nested Loop
Output: t1.q1, t1.q2, f.f
- Sort Key: t1.q1, t1.q2
- -> Nested Loop
- Output: t1.q1, t1.q2, f.f
- -> Nested Loop Left Join
- Output: t1.q1, t1.q2, ('()'::record)
- Join Filter: (t1.q1 = 123)
+ -> Nested Loop Left Join
+ Output: t1.q1, t1.q2, ('()'::record)
+ Join Filter: (t1.q1 = 123)
+ -> Sort
+ Output: t1.q1, t1.q2
+ Sort Key: t1.q1, t1.q2
-> Seq Scan on public.int8_tbl t1
Output: t1.q1, t1.q2
- -> Materialize
- Output: ('()'::record)
- -> Nested Loop Left Join
- Output: '()'::record
- -> Seq Scan on public.int4_tbl
- Output: int4_tbl.f1
- Filter: (int4_tbl.f1 = 0)
- -> Seq Scan on public.int4_tbl int4_tbl_1
- Output: int4_tbl_1.f1
- Filter: (int4_tbl_1.f1 = 0)
- -> Function Scan on pg_catalog.length f
- Output: f.f
- Function Call: length((('()'::record))::text)
+ -> Materialize
+ Output: ('()'::record)
+ -> Nested Loop Left Join
+ Output: '()'::record
+ -> Seq Scan on public.int4_tbl
+ Output: int4_tbl.f1
+ Filter: (int4_tbl.f1 = 0)
+ -> Seq Scan on public.int4_tbl int4_tbl_1
+ Output: int4_tbl_1.f1
+ Filter: (int4_tbl_1.f1 = 0)
+ -> Function Scan on pg_catalog.length f
+ Output: f.f
+ Function Call: length((('()'::record))::text)
(23 rows)
select t1.q1, t1.q2, f
@@ -4741,21 +4739,21 @@ from int4_tbl i4
left join (lateral (select i4.f1) ss(x) cross join (select 1) s2(y)) j
on (i4.f1 = 0)
order by 1;
- QUERY PLAN
--------------------------------------------------
- Sort
- Output: i4.f1, ((SubPlan expr_1))
- Sort Key: i4.f1
- -> Nested Loop Left Join
- Output: i4.f1, (SubPlan expr_1)
- Join Filter: (i4.f1 = 0)
+ QUERY PLAN
+--------------------------------------------
+ Nested Loop Left Join
+ Output: i4.f1, (SubPlan expr_1)
+ Join Filter: (i4.f1 = 0)
+ -> Sort
+ Output: i4.f1
+ Sort Key: i4.f1
-> Seq Scan on public.int4_tbl i4
Output: i4.f1
- -> Result
- Output: ROW(i4.f1, 1)
- SubPlan expr_1
- -> Result
- Output: ((ROW(i4.f1, 1)))::text
+ -> Result
+ Output: ROW(i4.f1, 1)
+ SubPlan expr_1
+ -> Result
+ Output: ((ROW(i4.f1, 1)))::text
(13 rows)
select i4.f1, (select j::text)
@@ -8526,19 +8524,18 @@ select d.* from d left join
(select distinct on (id) id, generate_series(1, 2) as g from b order by id) s
on d.a = s.id
order by 1, 2;
- QUERY PLAN
------------------------------------------------------------------------
- Sort
- Sort Key: d.a, d.b
- -> Hash Left Join
- Hash Cond: (d.a = s.id)
+ QUERY PLAN
+-----------------------------------------------------------
+ Merge Left Join
+ Merge Cond: (d.a = b.id)
+ -> Sort
+ Sort Key: d.a, d.b
-> Seq Scan on d
- -> Hash
- -> Subquery Scan on s
- -> ProjectSet
- -> Unique
- -> Index Only Scan using b_pkey on b
-(10 rows)
+ -> Materialize
+ -> ProjectSet
+ -> Unique
+ -> Index Only Scan using b_pkey on b
+(9 rows)
select d.* from d left join
(select distinct on (id) id, generate_series(1, 2) as g from b order by id) s
@@ -11704,6 +11701,55 @@ select * from
0 | 9998 | 0
(1 row)
+-- Relation with only parameterized paths, gets no presorted path.
+explain (costs off)
+select x.u
+from int8_tbl a, int8_tbl b, lateral unnest(array[a.q1, a.q2]) as x(u)
+where x.u = b.q1
+order by x.u;
+ QUERY PLAN
+---------------------------------------------
+ Merge Join
+ Merge Cond: (b.q1 = x.u)
+ -> Sort
+ Sort Key: b.q1
+ -> Seq Scan on int8_tbl b
+ -> Sort
+ Sort Key: x.u
+ -> Nested Loop
+ -> Seq Scan on int8_tbl a
+ -> Function Scan on unnest x
+(10 rows)
+
+select x.u
+from int8_tbl a, int8_tbl b, lateral unnest(array[a.q1, a.q2]) as x(u)
+where x.u = b.q1
+order by x.u;
+ u
+------------------
+ 123
+ 123
+ 123
+ 123
+ 123
+ 123
+ 4567890123456789
+ 4567890123456789
+ 4567890123456789
+ 4567890123456789
+ 4567890123456789
+ 4567890123456789
+ 4567890123456789
+ 4567890123456789
+ 4567890123456789
+ 4567890123456789
+ 4567890123456789
+ 4567890123456789
+ 4567890123456789
+ 4567890123456789
+ 4567890123456789
+(21 rows)
+
-- check proper extParam/allParam handling (this isn't exactly a LATERAL issue,
-- but we can make the test case much more compact with LATERAL)
explain (verbose, costs off)
@@ -12049,29 +12095,29 @@ select t1.b, ss.phv from join_ut1 t1 left join lateral
(select t2.a as t2a, t3.a t3a, least(t1.a, t2.a, t3.a) phv
from join_pt1 t2 join join_ut1 t3 on
t2.a = t3.b) ss
on t1.a = ss.t2a order by t1.a;
- QUERY PLAN
---------------------------------------------------------------------
- Sort
+ QUERY PLAN
+--------------------------------------------------------------
+ Nested Loop Left Join
Output: t1.b, (LEAST(t1.a, t2.a, t3.a)), t1.a
- Sort Key: t1.a
- -> Nested Loop Left Join
- Output: t1.b, (LEAST(t1.a, t2.a, t3.a)), t1.a
+ -> Sort
+ Output: t1.b, t1.a
+ Sort Key: t1.a
-> Seq Scan on public.join_ut1 t1
- Output: t1.a, t1.b, t1.c
- -> Hash Join
- Output: t2.a, LEAST(t1.a, t2.a, t3.a)
- Hash Cond: (t3.b = t2.a)
- -> Seq Scan on public.join_ut1 t3
- Output: t3.a, t3.b, t3.c
- -> Hash
- Output: t2.a
- -> Append
- -> Seq Scan on public.join_pt1p1p1 t2_1
- Output: t2_1.a
- Filter: (t1.a = t2_1.a)
- -> Seq Scan on public.join_pt1p2 t2_2
- Output: t2_2.a
- Filter: (t1.a = t2_2.a)
+ Output: t1.b, t1.a
+ -> Hash Join
+ Output: t2.a, LEAST(t1.a, t2.a, t3.a)
+ Hash Cond: (t3.b = t2.a)
+ -> Seq Scan on public.join_ut1 t3
+ Output: t3.a, t3.b, t3.c
+ -> Hash
+ Output: t2.a
+ -> Append
+ -> Seq Scan on public.join_pt1p1p1 t2_1
+ Output: t2_1.a
+ Filter: (t1.a = t2_1.a)
+ -> Seq Scan on public.join_pt1p2 t2_2
+ Output: t2_2.a
+ Filter: (t1.a = t2_2.a)
(21 rows)
select t1.b, ss.phv from join_ut1 t1 left join lateral
@@ -12816,3 +12862,56 @@ WHERE s.x = s.c;
(1 row)
ROLLBACK;
+--
+-- Test sort-ahead: a relation without an index on the ORDER BY key is
+-- sorted below the join, instead of sorting the join result
+--
+BEGIN;
+CREATE TEMP TABLE sa_outer AS
+ SELECT g AS id, (g * 7919) % 1000 AS v FROM generate_series(1, 1000) g;
+CREATE TEMP TABLE sa_inner AS
+ SELECT g % 1000 + 1 AS oid, g AS x FROM generate_series(1, 20000) g;
+CREATE INDEX ON sa_inner (oid);
+ANALYZE sa_outer, sa_inner;
+-- The outer side is sorted on the ORDER BY prefix that it can provide, and
+-- an Incremental Sort above the join completes the order
+EXPLAIN (COSTS OFF)
+SELECT o.v, i.x FROM sa_outer o JOIN sa_inner i ON i.oid = o.id
+ORDER BY o.v, i.x LIMIT 5;
+ QUERY PLAN
+-------------------------------------------------------------------
+ Limit
+ -> Incremental Sort
+ Sort Key: o.v, i.x
+ Presorted Key: o.v
+ -> Nested Loop
+ -> Sort
+ Sort Key: o.v
+ -> Seq Scan on sa_outer o
+ -> Index Scan using sa_inner_oid_idx on sa_inner i
+ Index Cond: (oid = o.id)
+(10 rows)
+
+SELECT o.v, i.x FROM sa_outer o JOIN sa_inner i ON i.oid = o.id
+ORDER BY o.v, i.x LIMIT 5;
+ v | x
+---+------
+ 0 | 999
+ 0 | 1999
+ 0 | 2999
+ 0 | 3999
+ 0 | 4999
+(5 rows)
+
+-- With a single relation there is no join to sort below
+EXPLAIN (COSTS OFF)
+SELECT * FROM sa_outer ORDER BY v LIMIT 5;
+ QUERY PLAN
+----------------------------------
+ Limit
+ -> Sort
+ Sort Key: v
+ -> Seq Scan on sa_outer
+(4 rows)
+
+ROLLBACK;
diff --git a/src/test/regress/expected/partition_join.out
b/src/test/regress/expected/partition_join.out
index e53c0c1a4d8..68cdd46b12f 100644
--- a/src/test/regress/expected/partition_join.out
+++ b/src/test/regress/expected/partition_join.out
@@ -445,36 +445,41 @@ EXPLAIN (COSTS OFF)
SELECT * FROM prt1 t1 LEFT JOIN LATERAL
(SELECT t2.a AS t2a, t3.a AS t3a,
least(t1.a,t2.a,t3.b) FROM prt1 t2 JOIN prt2 t3 ON (t2.a = t3.b)) ss
ON t1.a = ss.t2a WHERE t1.b = 0 ORDER BY t1.a;
- QUERY PLAN
---------------------------------------------------------------------------
- Sort
+ QUERY PLAN
+--------------------------------------------------------------------
+ Merge Append
Sort Key: t1.a
- -> Append
- -> Nested Loop Left Join
+ -> Nested Loop Left Join
+ -> Sort
+ Sort Key: t1_1.a
-> Seq Scan on prt1_p1 t1_1
Filter: (b = 0)
- -> Nested Loop
- -> Index Only Scan using iprt1_p1_a on prt1_p1 t2_1
- Index Cond: (a = t1_1.a)
- -> Index Scan using iprt2_p1_b on prt2_p1 t3_1
- Index Cond: (b = t2_1.a)
- -> Nested Loop Left Join
+ -> Nested Loop
+ -> Index Only Scan using iprt1_p1_a on prt1_p1 t2_1
+ Index Cond: (a = t1_1.a)
+ -> Index Scan using iprt2_p1_b on prt2_p1 t3_1
+ Index Cond: (b = t2_1.a)
+ -> Nested Loop Left Join
+ -> Sort
+ Sort Key: t1_2.a
-> Seq Scan on prt1_p2 t1_2
Filter: (b = 0)
- -> Nested Loop
- -> Index Only Scan using iprt1_p2_a on prt1_p2 t2_2
- Index Cond: (a = t1_2.a)
- -> Index Scan using iprt2_p2_b on prt2_p2 t3_2
- Index Cond: (b = t2_2.a)
- -> Nested Loop Left Join
+ -> Nested Loop
+ -> Index Only Scan using iprt1_p2_a on prt1_p2 t2_2
+ Index Cond: (a = t1_2.a)
+ -> Index Scan using iprt2_p2_b on prt2_p2 t3_2
+ Index Cond: (b = t2_2.a)
+ -> Nested Loop Left Join
+ -> Sort
+ Sort Key: t1_3.a
-> Seq Scan on prt1_p3 t1_3
Filter: (b = 0)
- -> Nested Loop
- -> Index Only Scan using iprt1_p3_a on prt1_p3 t2_3
- Index Cond: (a = t1_3.a)
- -> Index Scan using iprt2_p3_b on prt2_p3 t3_3
- Index Cond: (b = t2_3.a)
-(27 rows)
+ -> Nested Loop
+ -> Index Only Scan using iprt1_p3_a on prt1_p3 t2_3
+ Index Cond: (a = t1_3.a)
+ -> Index Scan using iprt2_p3_b on prt2_p3 t3_3
+ Index Cond: (b = t2_3.a)
+(32 rows)
SELECT * FROM prt1 t1 LEFT JOIN LATERAL
(SELECT t2.a AS t2a, t3.a AS t3a,
least(t1.a,t2.a,t3.b) FROM prt1 t2 JOIN prt2 t3 ON (t2.a = t3.b)) ss
@@ -724,30 +729,35 @@ EXPLAIN (COSTS OFF)
SELECT t1.a, t1.c, t2.b, t2.c FROM prt1 t1 LEFT JOIN
(SELECT b, COALESCE(c, 'x') AS c FROM prt2 WHERE a = 0) t2 ON t1.a = t2.b
WHERE t1.c = t2.c ORDER BY t1.a, t2.b;
- QUERY PLAN
-------------------------------------------------------------------------------------------------
- Sort
+ QUERY PLAN
+------------------------------------------------------------------------------------------
+ Merge Append
Sort Key: t1.a
- -> Append
- -> Nested Loop
+ -> Nested Loop
+ -> Sort
+ Sort Key: prt2_1.b
-> Seq Scan on prt2_p1 prt2_1
Filter: (a = 0)
- -> Index Scan using iprt1_p1_a on prt1_p1 t1_1
- Index Cond: (a = prt2_1.b)
- Filter: (((COALESCE(prt2_1.c, 'x'::character
varying)))::text = (c)::text)
- -> Nested Loop
+ -> Index Scan using iprt1_p1_a on prt1_p1 t1_1
+ Index Cond: (a = prt2_1.b)
+ Filter: (((COALESCE(prt2_1.c, 'x'::character varying)))::text =
(c)::text)
+ -> Nested Loop
+ -> Sort
+ Sort Key: prt2_2.b
-> Seq Scan on prt2_p2 prt2_2
Filter: (a = 0)
- -> Index Scan using iprt1_p2_a on prt1_p2 t1_2
- Index Cond: (a = prt2_2.b)
- Filter: (((COALESCE(prt2_2.c, 'x'::character
varying)))::text = (c)::text)
- -> Nested Loop
+ -> Index Scan using iprt1_p2_a on prt1_p2 t1_2
+ Index Cond: (a = prt2_2.b)
+ Filter: (((COALESCE(prt2_2.c, 'x'::character varying)))::text =
(c)::text)
+ -> Nested Loop
+ -> Sort
+ Sort Key: prt2_3.b
-> Seq Scan on prt2_p3 prt2_3
Filter: (a = 0)
- -> Index Scan using iprt1_p3_a on prt1_p3 t1_3
- Index Cond: (a = prt2_3.b)
- Filter: (((COALESCE(prt2_3.c, 'x'::character
varying)))::text = (c)::text)
-(21 rows)
+ -> Index Scan using iprt1_p3_a on prt1_p3 t1_3
+ Index Cond: (a = prt2_3.b)
+ Filter: (((COALESCE(prt2_3.c, 'x'::character varying)))::text =
(c)::text)
+(26 rows)
SELECT t1.a, t1.c, t2.b, t2.c FROM prt1 t1 LEFT JOIN
(SELECT b, COALESCE(c, 'x') AS c FROM prt2 WHERE a = 0) t2 ON t1.a = t2.b
@@ -783,34 +793,42 @@ SELECT t1.a, t1.c, t2.a, t2.c FROM prt4 t1 LEFT JOIN
WHERE t1.c = t2.c AND t2.a IS NOT NULL ORDER BY t1.a, t1.c;
QUERY PLAN
---------------------------------------------------------------------------------------------------
- Sort
+ Incremental Sort
Sort Key: t1.a, t1.c
- -> Append
+ Presorted Key: t1.a
+ -> Merge Append
+ Sort Key: t1.a
-> Nested Loop
-> Nested Loop
- -> Seq Scan on prt1_p1 t4_1
- Filter: (b = 0)
+ -> Sort
+ Sort Key: t4_1.a
+ -> Seq Scan on prt1_p1 t4_1
+ Filter: (b = 0)
-> Index Scan using prt3_p1_a_idx on prt3_p1 t3_1
Index Cond: ((a = t4_1.a) AND (a IS NOT NULL))
-> Index Only Scan using prt4_p1_c_a_idx on prt4_p1 t1_1
Index Cond: ((c = ((COALESCE(t3_1.c, t4_1.c)))::text) AND
(a = t3_1.a))
-> Nested Loop
-> Nested Loop
- -> Seq Scan on prt1_p2 t4_2
- Filter: (b = 0)
+ -> Sort
+ Sort Key: t4_2.a
+ -> Seq Scan on prt1_p2 t4_2
+ Filter: (b = 0)
-> Index Scan using prt3_p2_a_idx on prt3_p2 t3_2
Index Cond: ((a = t4_2.a) AND (a IS NOT NULL))
-> Index Only Scan using prt4_p2_c_a_idx on prt4_p2 t1_2
Index Cond: ((c = ((COALESCE(t3_2.c, t4_2.c)))::text) AND
(a = t3_2.a))
-> Nested Loop
- -> Seq Scan on prt1_p3 t4_3
- Filter: (b = 0)
+ -> Sort
+ Sort Key: t4_3.a
+ -> Seq Scan on prt1_p3 t4_3
+ Filter: (b = 0)
-> Nested Loop
-> Index Scan using prt3_p3_a_idx on prt3_p3 t3_3
Index Cond: ((a = t4_3.a) AND (a IS NOT NULL))
-> Index Only Scan using prt4_p3_c_a_idx on prt4_p3 t1_3
Index Cond: ((c = ((COALESCE(t3_3.c,
t4_3.c)))::text) AND (a = t3_3.a))
-(27 rows)
+(35 rows)
SELECT t1.a, t1.c, t2.a, t2.c FROM prt4 t1 LEFT JOIN
(SELECT t3.a, COALESCE(t3.c, t4.c) AS c FROM prt3 t3 JOIN prt1 t4 ON t3.a =
t4.a
@@ -1410,8 +1428,8 @@ SELECT t1.a, t1.phv, t2.b, t2.phv, t3.a + t3.b, t3.phv
FROM ((SELECT 50 phv, * F
-- Semi-join
EXPLAIN (COSTS OFF)
SELECT t1.* FROM prt1 t1 WHERE t1.a IN (SELECT t1.b FROM prt2 t1, prt1_e t2
WHERE t1.a = 0 AND t1.b = (t2.a + t2.b)/2) AND t1.b = 0 ORDER BY t1.a;
- QUERY PLAN
----------------------------------------------------------------------------------
+ QUERY PLAN
+---------------------------------------------------------------------------
Merge Append
Sort Key: t1.a
-> Nested Loop
@@ -1445,13 +1463,13 @@ SELECT t1.* FROM prt1 t1 WHERE t1.a IN (SELECT t1.b
FROM prt2 t1, prt1_e t2 WHER
-> Nested Loop
Join Filter: (t1_4.a = t1_7.b)
-> Unique
- -> Sort
- Sort Key: t1_7.b
- -> Nested Loop
+ -> Nested Loop
+ -> Sort
+ Sort Key: t1_7.b
-> Seq Scan on prt2_p3 t1_7
Filter: (a = 0)
- -> Index Scan using iprt1_e_p3_ab2 on prt1_e_p3
t2_3
- Index Cond: (((a + b) / 2) = t1_7.b)
+ -> Index Scan using iprt1_e_p3_ab2 on prt1_e_p3 t2_3
+ Index Cond: (((a + b) / 2) = t1_7.b)
-> Index Scan using iprt1_p3_a on prt1_p3 t1_4
Index Cond: (a = ((t2_3.a + t2_3.b) / 2))
Filter: (b = 0)
@@ -1670,11 +1688,13 @@ SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a <
450) t1 LEFT JOIN (SELECT *
Presorted Key: prt1.a
-> Merge Left Join
Merge Cond: (prt1.a = prt2.b)
- -> Sort
- Sort Key: prt1.a
- -> Append
+ -> Append
+ -> Sort
+ Sort Key: prt1_1.a
-> Seq Scan on prt1_p1 prt1_1
Filter: ((a < 450) AND (b = 0))
+ -> Sort
+ Sort Key: prt1_2.a
-> Seq Scan on prt1_p2 prt1_2
Filter: ((a < 450) AND (b = 0))
-> Sort
@@ -1684,7 +1704,7 @@ SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450)
t1 LEFT JOIN (SELECT *
Filter: (b > 250)
-> Seq Scan on prt2_p3 prt2_2
Filter: (b > 250)
-(19 rows)
+(21 rows)
SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450) t1 LEFT JOIN (SELECT
* FROM prt2 WHERE b > 250) t2 ON t1.a = t2.b WHERE t1.b = 0 ORDER BY t1.a, t2.b;
a | b
@@ -1704,25 +1724,33 @@ SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a <
450) t1 LEFT JOIN (SELECT *
-- partitionwise join does not apply
EXPLAIN (COSTS OFF)
SELECT t1.a, t2.b FROM prt1 t1, prt2 t2 WHERE t1::text = t2::text AND t1.a =
t2.b ORDER BY t1.a;
- QUERY PLAN
------------------------------------------------------------------------------------------
+ QUERY PLAN
+------------------------------------------------------------------
Merge Join
- Merge Cond: ((t1.a = t2.b) AND (((((t1.*)::prt1))::text) =
((((t2.*)::prt2))::text)))
- -> Sort
- Sort Key: t1.a, ((((t1.*)::prt1))::text)
- -> Result
- -> Append
- -> Seq Scan on prt1_p1 t1_1
- -> Seq Scan on prt1_p2 t1_2
- -> Seq Scan on prt1_p3 t1_3
- -> Sort
- Sort Key: t2.b, ((((t2.*)::prt2))::text)
- -> Result
- -> Append
+ Merge Cond: (t1.a = t2.b)
+ Join Filter: ((((t2.*)::prt2))::text = (((t1.*)::prt1))::text)
+ -> Append
+ -> Sort
+ Sort Key: t1_1.a
+ -> Seq Scan on prt1_p1 t1_1
+ -> Sort
+ Sort Key: t1_2.a
+ -> Seq Scan on prt1_p2 t1_2
+ -> Sort
+ Sort Key: t1_3.a
+ -> Seq Scan on prt1_p3 t1_3
+ -> Materialize
+ -> Append
+ -> Sort
+ Sort Key: t2_1.b
-> Seq Scan on prt2_p1 t2_1
+ -> Sort
+ Sort Key: t2_2.b
-> Seq Scan on prt2_p2 t2_2
+ -> Sort
+ Sort Key: t2_3.b
-> Seq Scan on prt2_p3 t2_3
-(16 rows)
+(24 rows)
SELECT t1.a, t2.b FROM prt1 t1, prt2 t2 WHERE t1::text = t2::text AND t1.a =
t2.b ORDER BY t1.a;
a | b
@@ -2376,53 +2404,60 @@ EXPLAIN (COSTS OFF)
SELECT * FROM prt1_l t1 LEFT JOIN LATERAL
(SELECT t2.a AS t2a, t2.c AS t2c, t2.b AS t2b, t3.b
AS t3b, least(t1.a,t2.a,t3.b) FROM prt1_l t2 JOIN prt2_l t3 ON (t2.a = t3.b AND
t2.c = t3.c)) ss
ON t1.a = ss.t2a AND t1.c = ss.t2c WHERE t1.b = 0
ORDER BY t1.a;
- QUERY PLAN
------------------------------------------------------------------------------------------------
- Sort
+ QUERY PLAN
+-----------------------------------------------------------------------------------------
+ Merge Append
Sort Key: t1.a
- -> Append
- -> Nested Loop Left Join
+ -> Nested Loop Left Join
+ -> Sort
+ Sort Key: t1_1.a
-> Seq Scan on prt1_l_p1 t1_1
Filter: (b = 0)
- -> Hash Join
- Hash Cond: ((t3_1.b = t2_1.a) AND ((t3_1.c)::text =
(t2_1.c)::text))
- -> Seq Scan on prt2_l_p1 t3_1
- -> Hash
- -> Seq Scan on prt1_l_p1 t2_1
- Filter: ((t1_1.a = a) AND ((t1_1.c)::text =
(c)::text))
- -> Nested Loop Left Join
+ -> Hash Join
+ Hash Cond: ((t3_1.b = t2_1.a) AND ((t3_1.c)::text =
(t2_1.c)::text))
+ -> Seq Scan on prt2_l_p1 t3_1
+ -> Hash
+ -> Seq Scan on prt1_l_p1 t2_1
+ Filter: ((t1_1.a = a) AND ((t1_1.c)::text =
(c)::text))
+ -> Nested Loop Left Join
+ -> Sort
+ Sort Key: t1_2.a
-> Seq Scan on prt1_l_p2_p1 t1_2
Filter: (b = 0)
- -> Hash Join
- Hash Cond: ((t3_2.b = t2_2.a) AND ((t3_2.c)::text =
(t2_2.c)::text))
- -> Seq Scan on prt2_l_p2_p1 t3_2
- -> Hash
- -> Seq Scan on prt1_l_p2_p1 t2_2
- Filter: ((t1_2.a = a) AND ((t1_2.c)::text =
(c)::text))
- -> Nested Loop Left Join
+ -> Hash Join
+ Hash Cond: ((t3_2.b = t2_2.a) AND ((t3_2.c)::text =
(t2_2.c)::text))
+ -> Seq Scan on prt2_l_p2_p1 t3_2
+ -> Hash
+ -> Seq Scan on prt1_l_p2_p1 t2_2
+ Filter: ((t1_2.a = a) AND ((t1_2.c)::text =
(c)::text))
+ -> Nested Loop Left Join
+ -> Sort
+ Sort Key: t1_3.a
-> Seq Scan on prt1_l_p2_p2 t1_3
Filter: (b = 0)
- -> Hash Join
- Hash Cond: ((t3_3.b = t2_3.a) AND ((t3_3.c)::text =
(t2_3.c)::text))
- -> Seq Scan on prt2_l_p2_p2 t3_3
- -> Hash
- -> Seq Scan on prt1_l_p2_p2 t2_3
- Filter: ((t1_3.a = a) AND ((t1_3.c)::text =
(c)::text))
- -> Nested Loop Left Join
+ -> Hash Join
+ Hash Cond: ((t3_3.b = t2_3.a) AND ((t3_3.c)::text =
(t2_3.c)::text))
+ -> Seq Scan on prt2_l_p2_p2 t3_3
+ -> Hash
+ -> Seq Scan on prt1_l_p2_p2 t2_3
+ Filter: ((t1_3.a = a) AND ((t1_3.c)::text =
(c)::text))
+ -> Nested Loop Left Join
+ -> Sort
+ Sort Key: t1_4.a
-> Seq Scan on prt1_l_p3_p1 t1_4
Filter: (b = 0)
- -> Hash Join
- Hash Cond: ((t3_5.b = t2_5.a) AND ((t3_5.c)::text =
(t2_5.c)::text))
+ -> Hash Join
+ Hash Cond: ((t3_5.b = t2_5.a) AND ((t3_5.c)::text =
(t2_5.c)::text))
+ -> Append
+ -> Seq Scan on prt2_l_p3_p1 t3_5
+ -> Seq Scan on prt2_l_p3_p2 t3_6
+ -> Hash
-> Append
- -> Seq Scan on prt2_l_p3_p1 t3_5
- -> Seq Scan on prt2_l_p3_p2 t3_6
- -> Hash
- -> Append
- -> Seq Scan on prt1_l_p3_p1 t2_5
- Filter: ((t1_4.a = a) AND
((t1_4.c)::text = (c)::text))
- -> Seq Scan on prt1_l_p3_p2 t2_6
- Filter: ((t1_4.a = a) AND
((t1_4.c)::text = (c)::text))
-(44 rows)
+ -> Seq Scan on prt1_l_p3_p1 t2_5
+ Filter: ((t1_4.a = a) AND ((t1_4.c)::text =
(c)::text))
+ -> Seq Scan on prt1_l_p3_p2 t2_6
+ Filter: ((t1_4.a = a) AND ((t1_4.c)::text =
(c)::text))
+(51 rows)
SELECT * FROM prt1_l t1 LEFT JOIN LATERAL
(SELECT t2.a AS t2a, t2.c AS t2c, t2.b AS t2b, t3.b
AS t3b, least(t1.a,t2.a,t3.b) FROM prt1_l t2 JOIN prt2_l t3 ON (t2.a = t3.b AND
t2.c = t3.c)) ss
@@ -5417,36 +5452,48 @@ EXPLAIN (COSTS OFF)
SELECT t1.*, t2.* FROM alpha t1 INNER JOIN beta t2 ON (t1.a = t2.a AND t1.b =
t2.b AND t1.c = t2.c) WHERE ((t1.b >= 100 AND t1.b < 110) OR (t1.b >= 200 AND
t1.b < 210)) AND ((t2.b >= 100 AND t2.b < 110) OR (t2.b >= 200 AND t2.b < 210))
AND t1.c IN ('0004', '0009') ORDER BY t1.a, t1.b;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
- Sort
+ Merge Append
Sort Key: t1.a, t1.b
- -> Append
- -> Hash Join
- Hash Cond: ((t1_1.a = t2_1.a) AND (t1_1.b = t2_1.b) AND (t1_1.c
= t2_1.c))
+ -> Merge Join
+ Merge Cond: ((t1_1.a = t2_1.a) AND (t1_1.b = t2_1.b))
+ Join Filter: (t1_1.c = t2_1.c)
+ -> Sort
+ Sort Key: t1_1.a, t1_1.b
-> Seq Scan on alpha_neg_p1 t1_1
Filter: ((c = ANY ('{0004,0009}'::text[])) AND (((b >=
100) AND (b < 110)) OR ((b >= 200) AND (b < 210))))
- -> Hash
- -> Seq Scan on beta_neg_p1 t2_1
- Filter: (((b >= 100) AND (b < 110)) OR ((b >= 200)
AND (b < 210)))
- -> Hash Join
- Hash Cond: ((t1_2.a = t2_2.a) AND (t1_2.b = t2_2.b) AND (t1_2.c
= t2_2.c))
+ -> Sort
+ Sort Key: t2_1.a, t2_1.b
+ -> Seq Scan on beta_neg_p1 t2_1
+ Filter: (((b >= 100) AND (b < 110)) OR ((b >= 200) AND (b
< 210)))
+ -> Merge Join
+ Merge Cond: ((t1_2.a = t2_2.a) AND (t1_2.b = t2_2.b))
+ Join Filter: (t1_2.c = t2_2.c)
+ -> Sort
+ Sort Key: t1_2.a, t1_2.b
-> Seq Scan on alpha_neg_p2 t1_2
Filter: ((c = ANY ('{0004,0009}'::text[])) AND (((b >=
100) AND (b < 110)) OR ((b >= 200) AND (b < 210))))
- -> Hash
- -> Seq Scan on beta_neg_p2 t2_2
- Filter: (((b >= 100) AND (b < 110)) OR ((b >= 200)
AND (b < 210)))
- -> Nested Loop
- Join Filter: ((t1_3.a = t2_3.a) AND (t1_3.b = t2_3.b) AND
(t1_3.c = t2_3.c))
- -> Seq Scan on alpha_pos_p2 t1_3
- Filter: ((c = ANY ('{0004,0009}'::text[])) AND (((b >=
100) AND (b < 110)) OR ((b >= 200) AND (b < 210))))
+ -> Sort
+ Sort Key: t2_2.a, t2_2.b
+ -> Seq Scan on beta_neg_p2 t2_2
+ Filter: (((b >= 100) AND (b < 110)) OR ((b >= 200) AND (b
< 210)))
+ -> Nested Loop
+ Join Filter: ((t1_3.a = t2_3.a) AND (t1_3.b = t2_3.b) AND (t1_3.c =
t2_3.c))
+ -> Sort
+ Sort Key: t2_3.a, t2_3.b
-> Seq Scan on beta_pos_p2 t2_3
Filter: (((b >= 100) AND (b < 110)) OR ((b >= 200) AND (b
< 210)))
- -> Nested Loop
- Join Filter: ((t1_4.a = t2_4.a) AND (t1_4.b = t2_4.b) AND
(t1_4.c = t2_4.c))
- -> Seq Scan on alpha_pos_p3 t1_4
+ -> Materialize
+ -> Seq Scan on alpha_pos_p2 t1_3
Filter: ((c = ANY ('{0004,0009}'::text[])) AND (((b >=
100) AND (b < 110)) OR ((b >= 200) AND (b < 210))))
+ -> Nested Loop
+ Join Filter: ((t1_4.a = t2_4.a) AND (t1_4.b = t2_4.b) AND (t1_4.c =
t2_4.c))
+ -> Sort
+ Sort Key: t2_4.a, t2_4.b
-> Seq Scan on beta_pos_p3 t2_4
Filter: (((b >= 100) AND (b < 110)) OR ((b >= 200) AND (b
< 210)))
-(29 rows)
+ -> Seq Scan on alpha_pos_p3 t1_4
+ Filter: ((c = ANY ('{0004,0009}'::text[])) AND (((b >= 100) AND
(b < 110)) OR ((b >= 200) AND (b < 210))))
+(41 rows)
SELECT t1.*, t2.* FROM alpha t1 INNER JOIN beta t2 ON (t1.a = t2.a AND t1.b =
t2.b AND t1.c = t2.c) WHERE ((t1.b >= 100 AND t1.b < 110) OR (t1.b >= 200 AND
t1.b < 210)) AND ((t2.b >= 100 AND t2.b < 110) OR (t2.b >= 200 AND t2.b < 210))
AND t1.c IN ('0004', '0009') ORDER BY t1.a, t1.b;
a | b | c | a | b | c
diff --git a/src/test/regress/expected/subselect.out
b/src/test/regress/expected/subselect.out
index 4fbfd5ca1ac..d603a633b69 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -911,9 +911,12 @@ order by t1.a, t2.a;
Output: t2_1.a, t2_1.b
-> Index Scan using unique_tbl_p2_a_idx on
public.unique_tbl_p2 t2_2
Output: t2_2.a, t2_2.b
- -> Index Scan using unique_tbl_p3_a_idx on
public.unique_tbl_p3 t2_3
+ -> Sort
Output: t2_3.a, t2_3.b
-(44 rows)
+ Sort Key: t2_3.a
+ -> Seq Scan on public.unique_tbl_p3 t2_3
+ Output: t2_3.a, t2_3.b
+(47 rows)
reset enable_partitionwise_join;
drop table unique_tbl_p;
diff --git a/src/test/regress/expected/tablesample.out
b/src/test/regress/expected/tablesample.out
index 589d5c3054c..5a643119d51 100644
--- a/src/test/regress/expected/tablesample.out
+++ b/src/test/regress/expected/tablesample.out
@@ -253,13 +253,15 @@ select pct, count(unique1) from
group by pct;
QUERY PLAN
--------------------------------------------------------
- HashAggregate
+ GroupAggregate
Group Key: "*VALUES*".column1
-> Nested Loop
- -> Values Scan on "*VALUES*"
+ -> Sort
+ Sort Key: "*VALUES*".column1
+ -> Values Scan on "*VALUES*"
-> Sample Scan on tenk1
Sampling: bernoulli ("*VALUES*".column1)
-(6 rows)
+(8 rows)
select pct, count(unique1) from
(values (0),(100)) v(pct),
diff --git a/src/test/regress/expected/tuplesort.out
b/src/test/regress/expected/tuplesort.out
index fc1321bf443..66bc1ea6200 100644
--- a/src/test/regress/expected/tuplesort.out
+++ b/src/test/regress/expected/tuplesort.out
@@ -635,18 +635,15 @@ EXPLAIN (COSTS OFF) :qry;
-> GroupAggregate
Group Key: a.col12
Filter: (count(*) > 1)
- -> Incremental Sort
- Sort Key: a.col12 DESC, a.col1
- Presorted Key: a.col12
- -> Merge Join
- Merge Cond: (a.col12 = b.col12)
- -> Sort
- Sort Key: a.col12 DESC
- -> Seq Scan on test_mark_restore a
- -> Sort
- Sort Key: b.col12 DESC
- -> Seq Scan on test_mark_restore b
-(17 rows)
+ -> Merge Join
+ Merge Cond: (a.col12 = b.col12)
+ -> Sort
+ Sort Key: a.col12 DESC, a.col1
+ -> Seq Scan on test_mark_restore a
+ -> Sort
+ Sort Key: b.col12 DESC
+ -> Seq Scan on test_mark_restore b
+(14 rows)
:qry;
col12 | count | count | count | count | count
@@ -674,18 +671,15 @@ EXPLAIN (COSTS OFF) :qry;
-> GroupAggregate
Group Key: a.col12
Filter: (count(*) > 1)
- -> Incremental Sort
- Sort Key: a.col12 DESC, a.col1
- Presorted Key: a.col12
- -> Merge Join
- Merge Cond: (a.col12 = b.col12)
- -> Sort
- Sort Key: a.col12 DESC
- -> Seq Scan on test_mark_restore a
- -> Sort
- Sort Key: b.col12 DESC
- -> Seq Scan on test_mark_restore b
-(17 rows)
+ -> Merge Join
+ Merge Cond: (a.col12 = b.col12)
+ -> Sort
+ Sort Key: a.col12 DESC, a.col1
+ -> Seq Scan on test_mark_restore a
+ -> Sort
+ Sort Key: b.col12 DESC
+ -> Seq Scan on test_mark_restore b
+(14 rows)
:qry;
col12 | count | count | count | count | count
diff --git a/src/test/regress/sql/create_am.sql
b/src/test/regress/sql/create_am.sql
index 754fe0c694b..b5c970fcec2 100644
--- a/src/test/regress/sql/create_am.sql
+++ b/src/test/regress/sql/create_am.sql
@@ -146,9 +146,9 @@ SELECT
pc.relkind,
pa.amname,
CASE WHEN relkind = 't' THEN
- (SELECT 'toast for ' || relname::regclass FROM pg_class pcm WHERE
pcm.reltoastrelid = pc.oid)
+ (SELECT 'toast for ' || pcm.oid::regclass FROM pg_class pcm WHERE
pcm.reltoastrelid = pc.oid)
ELSE
- relname::regclass::text
+ pc.oid::regclass::text
END COLLATE "C" AS relname
FROM pg_class AS pc,
pg_am AS pa
@@ -339,9 +339,9 @@ SELECT
pc.relkind,
pa.amname,
CASE WHEN relkind = 't' THEN
- (SELECT 'toast for ' || relname::regclass FROM pg_class pcm WHERE
pcm.reltoastrelid = pc.oid)
+ (SELECT 'toast for ' || pcm.oid::regclass FROM pg_class pcm WHERE
pcm.reltoastrelid = pc.oid)
ELSE
- relname::regclass::text
+ pc.oid::regclass::text
END COLLATE "C" AS relname
FROM pg_class AS pc
LEFT JOIN pg_am AS pa ON (pa.oid = pc.relam)
diff --git a/src/test/regress/sql/incremental_sort.sql
b/src/test/regress/sql/incremental_sort.sql
index bbe658a7588..3694e0f73f0 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -293,11 +293,14 @@ create index point_table_a_idx on point_table using
gist(a);
explain (costs off) select a, b, a <-> point(5, 5) dist from point_table order
by dist, b limit 1;
explain (costs off) select a, b, a <-> point(5, 5) dist from point_table order
by dist, b desc limit 1;
--- Ensure we get an incremental sort on the outer side of the mergejoin
+-- Ensure we get an incremental sort on the outer side of the mergejoin.
+-- Use a left join so that the ORDER BY can only be satisfied by t1.
+set enable_nestloop = off;
explain (costs off)
select * from
- (select * from tenk1 order by four) t1 join tenk1 t2 on t1.four = t2.four
and t1.two = t2.two
+ (select * from tenk1 order by four) t1 left join tenk1 t2 on t1.four =
t2.four and t1.two = t2.two
order by t1.four, t1.two limit 1;
+reset enable_nestloop;
--
-- Test incremental sort for Append/MergeAppend
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 381c57a5a88..341bec76c0f 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -4418,6 +4418,17 @@ select * from
where f1 = any (select unique1 from tenk1
where unique2 = v.x offset 0)) ss;
+-- Relation with only parameterized paths, gets no presorted path.
+explain (costs off)
+select x.u
+from int8_tbl a, int8_tbl b, lateral unnest(array[a.q1, a.q2]) as x(u)
+where x.u = b.q1
+order by x.u;
+select x.u
+from int8_tbl a, int8_tbl b, lateral unnest(array[a.q1, a.q2]) as x(u)
+where x.u = b.q1
+order by x.u;
+
-- check proper extParam/allParam handling (this isn't exactly a LATERAL issue,
-- but we can make the test case much more compact with LATERAL)
explain (verbose, costs off)
@@ -4919,3 +4930,30 @@ FROM (VALUES (1)) AS v(z) LEFT JOIN
WHERE s.x = s.c;
ROLLBACK;
+
+--
+-- Test sort-ahead: a relation without an index on the ORDER BY key is
+-- sorted below the join, instead of sorting the join result
+--
+BEGIN;
+
+CREATE TEMP TABLE sa_outer AS
+ SELECT g AS id, (g * 7919) % 1000 AS v FROM generate_series(1, 1000) g;
+CREATE TEMP TABLE sa_inner AS
+ SELECT g % 1000 + 1 AS oid, g AS x FROM generate_series(1, 20000) g;
+CREATE INDEX ON sa_inner (oid);
+ANALYZE sa_outer, sa_inner;
+
+-- The outer side is sorted on the ORDER BY prefix that it can provide, and
+-- an Incremental Sort above the join completes the order
+EXPLAIN (COSTS OFF)
+SELECT o.v, i.x FROM sa_outer o JOIN sa_inner i ON i.oid = o.id
+ORDER BY o.v, i.x LIMIT 5;
+SELECT o.v, i.x FROM sa_outer o JOIN sa_inner i ON i.oid = o.id
+ORDER BY o.v, i.x LIMIT 5;
+
+-- With a single relation there is no join to sort below
+EXPLAIN (COSTS OFF)
+SELECT * FROM sa_outer ORDER BY v LIMIT 5;
+
+ROLLBACK;
--
2.56.0
