Hi all,
Inspired by the Cloudberry (a Greenplum-based database) bug discussion
[0], I added support for pulling up an EXISTS subquery from an outer
join’s ON clause when it references both join inputs. This is
implemented in the second patch.
The implementation shares subquery preparation with the existing
semijoin/antijoin conversion. When those transformations are blocked by
references to the preserved input, it tries a LEFT JOIN against distinct
correlation keys, attached to the nullable input. A CASE expression in
the original ON clause checks the match marker and evaluates the
remaining correlations. For NOT EXISTS, this fallback is allowed only
when all correlation keys are fixed by the nullable input; otherwise,
the SubPlan is retained.
[0]
https://github.com/apache/cloudberry/pull/1933/changes/4e9f8c7db45186b520632803e2eb22a350f5d8b9
I also tested the patches with SQLsmith. The only internal error
encountered was the one already reported in [1], which is unrelated to
these changes.
[1]
https://www.postgresql.org/message-id/flat/CACJufxF7iSeRF2%2BbprERSwBe5zShVch1EJK-KcxQCcLT-UHBbg%40mail.gmail.com#bb062383fbe183d923596ede64d1d62f
--
Regards,
Alena Rybakina
Yandex
From c0df6fb512dd3a95825c138aa4542194c582afd8 Mon Sep 17 00:00:00 2001
From: Alena Rybakina <[email protected]>
Date: Thu, 24 Sep 2026 18:41:51 +0300
Subject: [PATCH v11 1/3] Allow pulling up EXISTS sublinks with correlated
JOIN/ON clauses
convert_EXISTS_sublink_to_join() gave up if anything but the WHERE
clause of the EXISTS sub-select referred to the parent query, so a query
like
SELECT * FROM ta
WHERE EXISTS (SELECT 1 FROM tb JOIN tc ON tc.id = tb.id
AND tb.aval = ta.id);
was executed with a correlated SubPlan instead of a semijoin.
Now the JOIN/ON clauses that refer to the parent query are moved to the
WHERE clause of the sub-select, which becomes the semijoin or antijoin
qual. This is only done for the quals of inner joins that are not below
the nullable side of an outer join, since moving any other qual above
its join could change the result. If the ON clause of an outer join, or
a qual below the nullable side of an outer join, refers to the parent
query, or a qual to be moved is volatile, the sublink is not pulled up.
Join quals that don't refer to the parent query stay where they are.
Author: Alena Rybakina <[email protected]>
Reviewed-by: Ranier Vilela <[email protected]>
Reviewed-by: Ilia Evdokimov <[email protected]>
Reviewed-by: Peter Petrov <[email protected]>
Tested-by: Solaimurugan Vellaipandiyan <[email protected]>
Discussion: https://postgr.es/m/[email protected]
---
src/backend/optimizer/plan/subselect.c | 157 +++++-
src/test/regress/expected/subselect.out | 610 ++++++++++++++++++++++++
src/test/regress/sql/subselect.sql | 291 +++++++++++
3 files changed, 1038 insertions(+), 20 deletions(-)
diff --git a/src/backend/optimizer/plan/subselect.c
b/src/backend/optimizer/plan/subselect.c
index 5760b616813..c72eaf2cbd7 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -93,6 +93,8 @@ static void inline_cte(PlannerInfo *root, CommonTableExpr
*cte);
static bool inline_cte_walker(Node *node, inline_cte_walker_context *context);
static bool sublink_testexpr_is_not_nullable(PlannerInfo *root, SubLink
*sublink);
static bool simplify_EXISTS_query(PlannerInfo *root, Query *query);
+static bool collect_correlated_join_quals(Node *jtnode, bool nullable_side,
+
List **hoist_nodes);
static Query *convert_EXISTS_to_ANY(PlannerInfo *root, Query *subselect,
Node
**testexpr, List **paramIds);
static Node *replace_correlation_vars_mutator(Node *node, PlannerInfo *root);
@@ -1593,6 +1595,10 @@ sublink_testexpr_is_not_nullable(PlannerInfo *root,
SubLink *sublink)
* convert_EXISTS_sublink_to_join: try to convert an EXISTS SubLink to a join
*
* The API of this function is identical to convert_ANY_sublink_to_join's.
+ *
+ * References to the parent query are allowed in the WHERE clause of the
+ * sub-select and in the JOIN/ON clauses that can be moved to the WHERE
+ * clause without changing the result; see collect_correlated_join_quals().
*/
JoinExpr *
convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink *sublink,
@@ -1602,6 +1608,9 @@ convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink
*sublink,
Query *parse = root->parse;
Query *subselect = (Query *) sublink->subselect;
Node *whereClause;
+ FromExpr *jointree;
+ List *hoist_nodes = NIL;
+ ListCell *lc;
PlannerInfo subroot;
int rtoffset;
int varno;
@@ -1637,31 +1646,29 @@ convert_EXISTS_sublink_to_join(PlannerInfo *root,
SubLink *sublink,
return NULL;
/*
- * Separate out the WHERE clause. (We could theoretically also remove
- * top-level plain JOIN/ON clauses, but it's probably not worth the
- * trouble.)
- */
- whereClause = subselect->jointree->quals;
- subselect->jointree->quals = NULL;
-
- /*
- * The rest of the sub-select must not refer to any Vars of the parent
- * query. (Vars of higher levels should be okay, though.)
+ * Only the jointree (the WHERE clause and the JOIN/ON clauses) may
refer
+ * to Vars of the parent query; which of them can be moved to the join
+ * qual is checked below. The rest of the sub-select must not refer to
+ * any Vars of the parent query. (Vars of higher levels should be okay,
+ * though.)
*/
+ jointree = subselect->jointree;
+ subselect->jointree = NULL;
if (contain_vars_of_level((Node *) subselect, 1))
return NULL;
+ subselect->jointree = jointree;
/*
- * On the other hand, the WHERE clause must contain some Vars of the
- * parent query, else it's not gonna be a join.
+ * On the other hand, the jointree must contain some Vars of the parent
+ * query, else it's not gonna be a join.
*/
- if (!contain_vars_of_level(whereClause, 1))
+ if (!contain_vars_of_level((Node *) jointree, 1))
return NULL;
/*
* We don't risk optimizing if the WHERE clause is volatile, either.
*/
- if (contain_volatile_functions(whereClause))
+ if (contain_volatile_functions(jointree->quals))
return NULL;
/*
@@ -1675,24 +1682,46 @@ convert_EXISTS_sublink_to_join(PlannerInfo *root,
SubLink *sublink,
* Note: we construct up an entirely dummy PlannerInfo for use here.
This
* is fine because only the "glob" and "parse" links will be used in
this
* case.
- *
- * Note: we temporarily assign back the WHERE clause so that any virtual
- * generated column references within it can be expanded. It should be
- * separated out again afterward.
*/
MemSet(&subroot, 0, sizeof(subroot));
subroot.type = T_PlannerInfo;
subroot.glob = root->glob;
subroot.parse = subselect;
- subselect->jointree->quals = whereClause;
subselect = preprocess_relation_rtes(&subroot);
/*
- * Now separate out the WHERE clause again.
+ * Now separate out the WHERE clause.
*/
whereClause = subselect->jointree->quals;
subselect->jointree->quals = NULL;
+ /*
+ * Find the JOIN/ON clauses that refer to the parent query, and move
them
+ * to the WHERE clause. Fail if some of them can't be moved.
+ */
+ if (!collect_correlated_join_quals((Node *) subselect->jointree, false,
+
&hoist_nodes))
+ return NULL;
+
+ foreach(lc, hoist_nodes)
+ {
+ Node *node = (Node *) lfirst(lc);
+
+ if (IsA(node, JoinExpr))
+ {
+ whereClause = make_and_qual(whereClause, ((JoinExpr *)
node)->quals);
+ ((JoinExpr *) node)->quals = NULL;
+ }
+ else
+ {
+ whereClause = make_and_qual(whereClause, ((FromExpr *)
node)->quals);
+ ((FromExpr *) node)->quals = NULL;
+ }
+ }
+
+ /* Now the rest of the sub-select must not refer to the parent query */
+ Assert(!contain_vars_of_level((Node *) subselect, 1));
+
/*
* The subquery must have a nonempty jointree, but we can make it so.
*/
@@ -1777,6 +1806,94 @@ convert_EXISTS_sublink_to_join(PlannerInfo *root,
SubLink *sublink,
return result;
}
+/*
+ * collect_correlated_join_quals: find the quals of an EXISTS sub-select's
+ * jointree that refer to the parent query
+ *
+ * convert_EXISTS_sublink_to_join() moves such quals to the WHERE clause of
+ * the sub-select, which then becomes the semijoin or antijoin qual. That is
+ * only safe for the quals of inner joins (and of FROM lists) that are not
+ * below the nullable side of an outer join. The ON clause of an outer join
+ * doesn't filter out rows of its non-nullable side, and a qual below the
+ * nullable side of an outer join only decides which rows are null-extended,
+ * so evaluating either of them above the join could change the result.
+ *
+ * nullable_side is true if jtnode is below the nullable side of some outer
+ * join. JoinExpr and FromExpr nodes whose quals are to be moved are appended
+ * to *hoist_nodes. Returns false if some quals referring to the parent query
+ * can't be moved, or are volatile.
+ */
+static bool
+collect_correlated_join_quals(Node *jtnode, bool nullable_side,
+ List **hoist_nodes)
+{
+ if (jtnode == NULL || IsA(jtnode, RangeTblRef))
+ return true;
+
+ if (IsA(jtnode, FromExpr))
+ {
+ FromExpr *f = (FromExpr *) jtnode;
+ ListCell *lc;
+
+ if (contain_vars_of_level(f->quals, 1))
+ {
+ if (nullable_side ||
contain_volatile_functions(f->quals))
+ return false;
+ *hoist_nodes = lappend(*hoist_nodes, f);
+ }
+
+ foreach(lc, f->fromlist)
+ {
+ if (!collect_correlated_join_quals(lfirst(lc),
nullable_side,
+
hoist_nodes))
+ return false;
+ }
+ }
+ else if (IsA(jtnode, JoinExpr))
+ {
+ JoinExpr *j = (JoinExpr *) jtnode;
+ bool larg_nullable = nullable_side;
+ bool rarg_nullable = nullable_side;
+
+ switch (j->jointype)
+ {
+ case JOIN_INNER:
+ break;
+ case JOIN_LEFT:
+ rarg_nullable = true;
+ break;
+ case JOIN_RIGHT:
+ larg_nullable = true;
+ break;
+ case JOIN_FULL:
+ larg_nullable = true;
+ rarg_nullable = true;
+ break;
+ default:
+ /* semijoins and antijoins aren't expected here
*/
+ return false;
+ }
+
+ if (contain_vars_of_level(j->quals, 1))
+ {
+ if (j->jointype != JOIN_INNER || nullable_side ||
+ contain_volatile_functions(j->quals))
+ return false;
+ *hoist_nodes = lappend(*hoist_nodes, j);
+ }
+
+ if (!collect_correlated_join_quals(j->larg, larg_nullable,
+
hoist_nodes) ||
+ !collect_correlated_join_quals(j->rarg, rarg_nullable,
+
hoist_nodes))
+ return false;
+ }
+ else
+ elog(ERROR, "unrecognized node type: %d", (int)
nodeTag(jtnode));
+
+ return true;
+}
+
/*
* simplify_EXISTS_query: remove any useless stuff in an EXISTS's subquery
*
diff --git a/src/test/regress/expected/subselect.out
b/src/test/regress/expected/subselect.out
index cf295d56507..612634aeb49 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -1042,6 +1042,616 @@ where exists (
where road.name = ss.f1 );
rollback;
--
+-- Tests for pulling up EXISTS sublinks whose JOIN/ON clauses refer to the
+-- parent query
+--
+CREATE TEMP TABLE td (id int);
+INSERT INTO td SELECT g FROM generate_series(1, 100) g;
+ANALYZE td;
+-- Pull-up: correlated ON clause of an inner join
+EXPLAIN (COSTS OFF)
+SELECT 1
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ JOIN tc ON ta.id = tc.id
+ AND ta.id = tb.id
+);
+ QUERY PLAN
+------------------------------------
+ Hash Right Semi Join
+ Hash Cond: (tc.id = ta.id)
+ -> Hash Join
+ Hash Cond: (tb.id = tc.id)
+ -> Seq Scan on tb
+ -> Hash
+ -> Seq Scan on tc
+ -> Hash
+ -> Seq Scan on ta
+(9 rows)
+
+SELECT 1
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ JOIN tc ON ta.id = tc.id
+ AND ta.id = tb.id
+)
+ORDER BY 1;
+ ?column?
+----------
+ 1
+ 1
+(2 rows)
+
+-- Pull-up: the correlated ON clause refers only to the parent query
+EXPLAIN (COSTS OFF)
+SELECT 1
+FROM ta
+JOIN tb ON true
+WHERE EXISTS (
+ SELECT 1
+ FROM tb tb1
+ JOIN tc ON ta.id = tb.id
+);
+ QUERY PLAN
+------------------------------------
+ Nested Loop Semi Join
+ -> Hash Join
+ Hash Cond: (ta.id = tb.id)
+ -> Seq Scan on ta
+ -> Hash
+ -> Seq Scan on tb
+ -> Nested Loop
+ -> Seq Scan on tb tb1
+ -> Materialize
+ -> Seq Scan on tc
+(10 rows)
+
+SELECT 1
+FROM ta
+JOIN tb ON true
+WHERE EXISTS (
+ SELECT 1
+ FROM tb tb1
+ JOIN tc ON ta.id = tb.id
+)
+ORDER BY 1;
+ ?column?
+----------
+ 1
+ 1
+(2 rows)
+
+-- Pull-up: correlated ON clause of a join nested in another join
+EXPLAIN (COSTS OFF)
+SELECT ta.*
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ JOIN tc ON tc.id = tb.id
+ AND tb.id = ta.id
+ JOIN td ON td.id = tc.id
+);
+ QUERY PLAN
+-------------------------------------------------------
+ Nested Loop
+ Join Filter: (ta.id = td.id)
+ -> HashAggregate
+ Group Key: tb.id
+ -> Nested Loop
+ Join Filter: (tc.id = td.id)
+ -> Hash Join
+ Hash Cond: (tb.id = td.id)
+ -> Seq Scan on tb
+ -> Hash
+ -> Seq Scan on td
+ -> Index Only Scan using tc_pkey on tc
+ Index Cond: (id = tb.id)
+ -> Index Scan using ta_pkey on ta
+ Index Cond: (id = tc.id)
+(15 rows)
+
+SELECT ta.*
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ JOIN tc ON tc.id = tb.id
+ AND tb.id = ta.id
+ JOIN td ON td.id = tc.id
+)
+ORDER BY 1;
+ id | val
+----+-----
+ 1 | 1
+ 2 | 2
+(2 rows)
+
+-- Pull-up: correlated ON clause together with an EXISTS in the WHERE clause
+EXPLAIN (COSTS OFF)
+SELECT 1
+FROM ta ta1
+WHERE EXISTS (
+ SELECT 1
+ FROM ta
+ JOIN tb ON ta.id = ta1.id
+ AND ta1.val = 1
+ WHERE EXISTS (
+ SELECT 1
+ FROM ta ta2
+ WHERE ta2.id = ta1.id
+ )
+);
+ QUERY PLAN
+-------------------------------------------------
+ Nested Loop Semi Join
+ -> Seq Scan on ta ta2
+ Filter: (val = 1)
+ -> Nested Loop
+ -> Index Only Scan using ta_pkey on ta
+ Index Cond: (id = ta2.id)
+ -> Seq Scan on tb
+(7 rows)
+
+SELECT 1
+FROM ta ta1
+WHERE EXISTS (
+ SELECT 1
+ FROM ta
+ JOIN tb ON ta.id = ta1.id
+ AND ta1.val = 1
+ WHERE EXISTS (
+ SELECT 1
+ FROM ta ta2
+ WHERE ta2.id = ta1.id
+ )
+)
+ORDER BY 1;
+ ?column?
+----------
+ 1
+(1 row)
+
+-- Pull-up: the moved ON clause contains an EXISTS sublink referring to
+-- the parent query, but not to the surrounding subquery
+EXPLAIN (COSTS OFF)
+SELECT ta.id
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ JOIN tc ON tc.id = ta.id
+ AND EXISTS (
+ SELECT 1
+ FROM td
+ WHERE td.id = ta.id
+ )
+);
+ QUERY PLAN
+-------------------------------------------------
+ Nested Loop Semi Join
+ -> Hash Semi Join
+ Hash Cond: (ta.id = td.id)
+ -> Seq Scan on ta
+ -> Hash
+ -> Seq Scan on td
+ -> Nested Loop
+ -> Index Only Scan using tc_pkey on tc
+ Index Cond: (id = td.id)
+ -> Seq Scan on tb
+(10 rows)
+
+SELECT ta.id
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ JOIN tc ON tc.id = ta.id
+ AND EXISTS (
+ SELECT 1
+ FROM td
+ WHERE td.id = ta.id
+ )
+)
+ORDER BY 1;
+ id
+----
+ 1
+ 2
+(2 rows)
+
+-- Pull-up: the nested EXISTS refers to both the parent query and the
+-- surrounding subquery; both reference levels must be adjusted correctly
+EXPLAIN (COSTS OFF)
+SELECT ta.id
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ JOIN tc ON tc.id = ta.id
+ AND EXISTS (
+ SELECT 1
+ FROM td
+ WHERE tb.id = ta.id
+ )
+);
+ QUERY PLAN
+--------------------------------------------
+ Hash Right Semi Join
+ Hash Cond: (tc.id = ta.id)
+ Join Filter: EXISTS(SubPlan exists_1)
+ -> Nested Loop
+ -> Seq Scan on tb
+ -> Materialize
+ -> Seq Scan on tc
+ -> Hash
+ -> Seq Scan on ta
+ SubPlan exists_1
+ -> Result
+ One-Time Filter: (tb.id = ta.id)
+ -> Seq Scan on td
+(13 rows)
+
+SELECT ta.id
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ JOIN tc ON tc.id = ta.id
+ AND EXISTS (
+ SELECT 1
+ FROM td
+ WHERE tb.id = ta.id
+ )
+)
+ORDER BY 1;
+ id
+----
+ 1
+ 2
+(2 rows)
+
+-- No pull-up: the ON clause of an outer join refers to the parent query
+EXPLAIN (COSTS OFF)
+SELECT 1
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ RIGHT JOIN tc ON ta.id = tc.id
+);
+ QUERY PLAN
+----------------------------------------
+ Seq Scan on ta
+ Filter: EXISTS(SubPlan exists_1)
+ SubPlan exists_1
+ -> Nested Loop Left Join
+ Join Filter: (ta.id = tc.id)
+ -> Seq Scan on tc
+ -> Materialize
+ -> Seq Scan on tb
+(8 rows)
+
+SELECT 1
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ RIGHT JOIN tc ON ta.id = tc.id
+)
+ORDER BY 1;
+ ?column?
+----------
+ 1
+ 1
+(2 rows)
+
+DROP TABLE td;
+-- Check which JOIN/ON clauses can be moved across outer joins. The data
+-- includes unmatched rows so that incorrectly moving a qual changes results.
+CREATE TEMP TABLE ex_o (x int, y int);
+CREATE TEMP TABLE ex_a (x int, y int);
+CREATE TEMP TABLE ex_b (x int, y int);
+CREATE TEMP TABLE ex_c (x int, y int);
+INSERT INTO ex_o VALUES (1, 1), (2, 2), (3, 3), (NULL, NULL);
+INSERT INTO ex_a VALUES (1, 10), (5, 50);
+INSERT INTO ex_b VALUES (7, 70);
+INSERT INTO ex_c VALUES (100, 1);
+ANALYZE ex_o, ex_a, ex_b, ex_c;
+-- No pull-up: the ON clause of a LEFT JOIN refers to the parent query
+EXPLAIN (COSTS OFF)
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM ex_a a LEFT JOIN ex_b b ON a.x = o.x);
+ QUERY PLAN
+----------------------------------------
+ Seq Scan on ex_o o
+ Filter: EXISTS(SubPlan exists_1)
+ SubPlan exists_1
+ -> Nested Loop Left Join
+ Join Filter: (a.x = o.x)
+ -> Seq Scan on ex_a a
+ -> Materialize
+ -> Seq Scan on ex_b b
+(8 rows)
+
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM ex_a a LEFT JOIN ex_b b ON a.x = o.x)
+ORDER BY 1;
+ x | y
+---+---
+ 1 | 1
+ 2 | 2
+ 3 | 3
+ |
+(4 rows)
+
+-- No pull-up: correlated inner join below the nullable side of a LEFT JOIN
+EXPLAIN (COSTS OFF)
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM ex_a a
+ LEFT JOIN (ex_b b JOIN ex_c c ON b.x = c.x AND c.y = o.y)
+ ON a.x = b.x);
+ QUERY PLAN
+------------------------------------------------
+ Seq Scan on ex_o o
+ Filter: EXISTS(SubPlan exists_1)
+ SubPlan exists_1
+ -> Nested Loop Left Join
+ Join Filter: (a.x = b.x)
+ -> Seq Scan on ex_a a
+ -> Materialize
+ -> Nested Loop
+ Join Filter: (b.x = c.x)
+ -> Seq Scan on ex_b b
+ -> Seq Scan on ex_c c
+ Filter: (y = o.y)
+(12 rows)
+
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM ex_a a
+ LEFT JOIN (ex_b b JOIN ex_c c ON b.x = c.x AND c.y = o.y)
+ ON a.x = b.x)
+ORDER BY 1;
+ x | y
+---+---
+ 1 | 1
+ 2 | 2
+ 3 | 3
+ |
+(4 rows)
+
+-- No pull-up: correlated inner join below a FULL JOIN
+EXPLAIN (COSTS OFF)
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM (ex_a a JOIN ex_c c ON a.x = o.x)
+ FULL JOIN ex_b b ON a.x = b.x);
+ QUERY PLAN
+-----------------------------------------
+ Seq Scan on ex_o o
+ Filter: EXISTS(SubPlan exists_1)
+ SubPlan exists_1
+ -> Hash Full Join
+ Hash Cond: (a.x = b.x)
+ -> Nested Loop
+ -> Seq Scan on ex_a a
+ Filter: (x = o.x)
+ -> Seq Scan on ex_c c
+ -> Hash
+ -> Seq Scan on ex_b b
+(11 rows)
+
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM (ex_a a JOIN ex_c c ON a.x = o.x)
+ FULL JOIN ex_b b ON a.x = b.x)
+ORDER BY 1;
+ x | y
+---+---
+ 1 | 1
+ 2 | 2
+ 3 | 3
+ |
+(4 rows)
+
+-- Pull-up: correlated inner join above a LEFT JOIN; the uncorrelated ON
+-- clause of the LEFT JOIN must be kept
+EXPLAIN (COSTS OFF)
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM ex_a a LEFT JOIN ex_b b ON a.x = b.x
+ JOIN ex_c c ON b.y = c.y AND c.y = o.y);
+ QUERY PLAN
+----------------------------------------------
+ Nested Loop Semi Join
+ Join Filter: (o.y = b.y)
+ -> Seq Scan on ex_o o
+ -> Materialize
+ -> Nested Loop
+ Join Filter: (b.y = c.y)
+ -> Nested Loop
+ Join Filter: (a.x = b.x)
+ -> Seq Scan on ex_b b
+ -> Seq Scan on ex_a a
+ -> Seq Scan on ex_c c
+(11 rows)
+
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM ex_a a LEFT JOIN ex_b b ON a.x = b.x
+ JOIN ex_c c ON b.y = c.y AND c.y = o.y)
+ORDER BY 1;
+ x | y
+---+---
+(0 rows)
+
+-- Pull-up: correlated inner join on the non-nullable side of a LEFT JOIN
+EXPLAIN (COSTS OFF)
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM (ex_a a JOIN ex_c c ON a.x = o.x)
+ LEFT JOIN ex_b b ON a.x = b.x);
+ QUERY PLAN
+--------------------------------------------
+ Hash Right Semi Join
+ Hash Cond: (a.x = o.x)
+ -> Nested Loop
+ -> Seq Scan on ex_c c
+ -> Nested Loop Left Join
+ Join Filter: (a.x = b.x)
+ -> Seq Scan on ex_a a
+ -> Materialize
+ -> Seq Scan on ex_b b
+ -> Hash
+ -> Seq Scan on ex_o o
+(11 rows)
+
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM (ex_a a JOIN ex_c c ON a.x = o.x)
+ LEFT JOIN ex_b b ON a.x = b.x)
+ORDER BY 1;
+ x | y
+---+---
+ 1 | 1
+(1 row)
+
+-- No pull-up: volatile correlated ON clause. Only check the plan, since
+-- executing this query would give nondeterministic results.
+EXPLAIN (COSTS OFF)
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM ex_a a JOIN ex_b b ON a.x = o.x AND random() >
0.5);
+ QUERY PLAN
+-------------------------------------------------------------
+ Seq Scan on ex_o o
+ Filter: EXISTS(SubPlan exists_1)
+ SubPlan exists_1
+ -> Nested Loop
+ Join Filter: (random() > '0.5'::double precision)
+ -> Seq Scan on ex_a a
+ Filter: (x = o.x)
+ -> Seq Scan on ex_b b
+(8 rows)
+
+-- Pull-up as an antijoin: combine the correlated ON and WHERE clauses.
+-- Unmatched rows, including NULLs, must survive.
+EXPLAIN (COSTS OFF)
+SELECT * FROM ex_o o
+WHERE NOT EXISTS (SELECT 1 FROM ex_a a JOIN ex_c c ON a.x = o.x
+ WHERE c.y = o.y);
+ QUERY PLAN
+--------------------------------------------
+ Hash Right Anti Join
+ Hash Cond: ((c.y = o.y) AND (a.x = o.x))
+ -> Nested Loop
+ -> Seq Scan on ex_c c
+ -> Seq Scan on ex_a a
+ -> Hash
+ -> Seq Scan on ex_o o
+(7 rows)
+
+SELECT * FROM ex_o o
+WHERE NOT EXISTS (SELECT 1 FROM ex_a a JOIN ex_c c ON a.x = o.x
+ WHERE c.y = o.y)
+ORDER BY 1;
+ x | y
+---+---
+ 2 | 2
+ 3 | 3
+ |
+(3 rows)
+
+-- No pull-up for NOT EXISTS either: the LEFT JOIN preserves rows even
+-- when the correlated ON clause is false, so no outer rows should survive
+EXPLAIN (COSTS OFF)
+SELECT * FROM ex_o o
+WHERE NOT EXISTS (SELECT 1 FROM ex_a a LEFT JOIN ex_b b ON a.x = o.x);
+ QUERY PLAN
+------------------------------------------
+ Seq Scan on ex_o o
+ Filter: (NOT EXISTS(SubPlan exists_1))
+ SubPlan exists_1
+ -> Nested Loop Left Join
+ Join Filter: (a.x = o.x)
+ -> Seq Scan on ex_a a
+ -> Materialize
+ -> Seq Scan on ex_b b
+(8 rows)
+
+SELECT * FROM ex_o o
+WHERE NOT EXISTS (SELECT 1 FROM ex_a a LEFT JOIN ex_b b ON a.x = o.x)
+ORDER BY 1;
+ x | y
+---+---
+(0 rows)
+
+-- Pull-up in a parent LEFT JOIN's ON clause: the moved qual references
+-- only its nullable side, which is included in available_rels
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x);
+ QUERY PLAN
+--------------------------------------------------
+ Nested Loop Left Join
+ Join Filter: (o.x = a.x)
+ -> Seq Scan on ex_o o
+ -> Materialize
+ -> Nested Loop Semi Join
+ Join Filter: (a.x = c.y)
+ -> Seq Scan on ex_a a
+ -> Materialize
+ -> Nested Loop
+ -> Seq Scan on ex_b b
+ -> Seq Scan on ex_c c
+(11 rows)
+
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x)
+ORDER BY 1, 2;
+ x | ax
+---+----
+ 1 | 1
+ 2 |
+ 3 |
+ |
+(4 rows)
+
+-- No pull-up: the moved qual also references the preserved side of the
+-- parent LEFT JOIN, which is not included in available_rels
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x);
+ QUERY PLAN
+-----------------------------------------
+ Hash Left Join
+ Hash Cond: (o.x = a.x)
+ Join Filter: EXISTS(SubPlan exists_1)
+ -> Seq Scan on ex_o o
+ -> Hash
+ -> Seq Scan on ex_a a
+ SubPlan exists_1
+ -> Result
+ One-Time Filter: (a.x = o.x)
+ -> Nested Loop
+ -> Seq Scan on ex_b b
+ -> Seq Scan on ex_c c
+ Filter: (y = o.x)
+(13 rows)
+
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x)
+ORDER BY 1, 2;
+ x | ax
+---+----
+ 1 | 1
+ 2 |
+ 3 |
+ |
+(4 rows)
+
+DROP TABLE ex_o, ex_a, ex_b, ex_c;
-- Test case for sublinks pushed down into subselects via join alias expansion
--
select
diff --git a/src/test/regress/sql/subselect.sql
b/src/test/regress/sql/subselect.sql
index 07438694f6e..16e92f51f5e 100644
--- a/src/test/regress/sql/subselect.sql
+++ b/src/test/regress/sql/subselect.sql
@@ -529,6 +529,297 @@ where exists (
rollback;
--
+-- Tests for pulling up EXISTS sublinks whose JOIN/ON clauses refer to the
+-- parent query
+--
+
+CREATE TEMP TABLE td (id int);
+INSERT INTO td SELECT g FROM generate_series(1, 100) g;
+ANALYZE td;
+
+-- Pull-up: correlated ON clause of an inner join
+EXPLAIN (COSTS OFF)
+SELECT 1
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ JOIN tc ON ta.id = tc.id
+ AND ta.id = tb.id
+);
+SELECT 1
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ JOIN tc ON ta.id = tc.id
+ AND ta.id = tb.id
+)
+ORDER BY 1;
+
+-- Pull-up: the correlated ON clause refers only to the parent query
+EXPLAIN (COSTS OFF)
+SELECT 1
+FROM ta
+JOIN tb ON true
+WHERE EXISTS (
+ SELECT 1
+ FROM tb tb1
+ JOIN tc ON ta.id = tb.id
+);
+SELECT 1
+FROM ta
+JOIN tb ON true
+WHERE EXISTS (
+ SELECT 1
+ FROM tb tb1
+ JOIN tc ON ta.id = tb.id
+)
+ORDER BY 1;
+
+-- Pull-up: correlated ON clause of a join nested in another join
+EXPLAIN (COSTS OFF)
+SELECT ta.*
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ JOIN tc ON tc.id = tb.id
+ AND tb.id = ta.id
+ JOIN td ON td.id = tc.id
+);
+SELECT ta.*
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ JOIN tc ON tc.id = tb.id
+ AND tb.id = ta.id
+ JOIN td ON td.id = tc.id
+)
+ORDER BY 1;
+
+-- Pull-up: correlated ON clause together with an EXISTS in the WHERE clause
+EXPLAIN (COSTS OFF)
+SELECT 1
+FROM ta ta1
+WHERE EXISTS (
+ SELECT 1
+ FROM ta
+ JOIN tb ON ta.id = ta1.id
+ AND ta1.val = 1
+ WHERE EXISTS (
+ SELECT 1
+ FROM ta ta2
+ WHERE ta2.id = ta1.id
+ )
+);
+SELECT 1
+FROM ta ta1
+WHERE EXISTS (
+ SELECT 1
+ FROM ta
+ JOIN tb ON ta.id = ta1.id
+ AND ta1.val = 1
+ WHERE EXISTS (
+ SELECT 1
+ FROM ta ta2
+ WHERE ta2.id = ta1.id
+ )
+)
+ORDER BY 1;
+
+-- Pull-up: the moved ON clause contains an EXISTS sublink referring to
+-- the parent query, but not to the surrounding subquery
+EXPLAIN (COSTS OFF)
+SELECT ta.id
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ JOIN tc ON tc.id = ta.id
+ AND EXISTS (
+ SELECT 1
+ FROM td
+ WHERE td.id = ta.id
+ )
+);
+SELECT ta.id
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ JOIN tc ON tc.id = ta.id
+ AND EXISTS (
+ SELECT 1
+ FROM td
+ WHERE td.id = ta.id
+ )
+)
+ORDER BY 1;
+
+-- Pull-up: the nested EXISTS refers to both the parent query and the
+-- surrounding subquery; both reference levels must be adjusted correctly
+EXPLAIN (COSTS OFF)
+SELECT ta.id
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ JOIN tc ON tc.id = ta.id
+ AND EXISTS (
+ SELECT 1
+ FROM td
+ WHERE tb.id = ta.id
+ )
+);
+SELECT ta.id
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ JOIN tc ON tc.id = ta.id
+ AND EXISTS (
+ SELECT 1
+ FROM td
+ WHERE tb.id = ta.id
+ )
+)
+ORDER BY 1;
+
+-- No pull-up: the ON clause of an outer join refers to the parent query
+EXPLAIN (COSTS OFF)
+SELECT 1
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ RIGHT JOIN tc ON ta.id = tc.id
+);
+SELECT 1
+FROM ta
+WHERE EXISTS (
+ SELECT 1
+ FROM tb
+ RIGHT JOIN tc ON ta.id = tc.id
+)
+ORDER BY 1;
+
+DROP TABLE td;
+
+-- Check which JOIN/ON clauses can be moved across outer joins. The data
+-- includes unmatched rows so that incorrectly moving a qual changes results.
+CREATE TEMP TABLE ex_o (x int, y int);
+CREATE TEMP TABLE ex_a (x int, y int);
+CREATE TEMP TABLE ex_b (x int, y int);
+CREATE TEMP TABLE ex_c (x int, y int);
+INSERT INTO ex_o VALUES (1, 1), (2, 2), (3, 3), (NULL, NULL);
+INSERT INTO ex_a VALUES (1, 10), (5, 50);
+INSERT INTO ex_b VALUES (7, 70);
+INSERT INTO ex_c VALUES (100, 1);
+ANALYZE ex_o, ex_a, ex_b, ex_c;
+
+-- No pull-up: the ON clause of a LEFT JOIN refers to the parent query
+EXPLAIN (COSTS OFF)
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM ex_a a LEFT JOIN ex_b b ON a.x = o.x);
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM ex_a a LEFT JOIN ex_b b ON a.x = o.x)
+ORDER BY 1;
+
+-- No pull-up: correlated inner join below the nullable side of a LEFT JOIN
+EXPLAIN (COSTS OFF)
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM ex_a a
+ LEFT JOIN (ex_b b JOIN ex_c c ON b.x = c.x AND c.y = o.y)
+ ON a.x = b.x);
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM ex_a a
+ LEFT JOIN (ex_b b JOIN ex_c c ON b.x = c.x AND c.y = o.y)
+ ON a.x = b.x)
+ORDER BY 1;
+
+-- No pull-up: correlated inner join below a FULL JOIN
+EXPLAIN (COSTS OFF)
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM (ex_a a JOIN ex_c c ON a.x = o.x)
+ FULL JOIN ex_b b ON a.x = b.x);
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM (ex_a a JOIN ex_c c ON a.x = o.x)
+ FULL JOIN ex_b b ON a.x = b.x)
+ORDER BY 1;
+
+-- Pull-up: correlated inner join above a LEFT JOIN; the uncorrelated ON
+-- clause of the LEFT JOIN must be kept
+EXPLAIN (COSTS OFF)
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM ex_a a LEFT JOIN ex_b b ON a.x = b.x
+ JOIN ex_c c ON b.y = c.y AND c.y = o.y);
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM ex_a a LEFT JOIN ex_b b ON a.x = b.x
+ JOIN ex_c c ON b.y = c.y AND c.y = o.y)
+ORDER BY 1;
+
+-- Pull-up: correlated inner join on the non-nullable side of a LEFT JOIN
+EXPLAIN (COSTS OFF)
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM (ex_a a JOIN ex_c c ON a.x = o.x)
+ LEFT JOIN ex_b b ON a.x = b.x);
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM (ex_a a JOIN ex_c c ON a.x = o.x)
+ LEFT JOIN ex_b b ON a.x = b.x)
+ORDER BY 1;
+
+-- No pull-up: volatile correlated ON clause. Only check the plan, since
+-- executing this query would give nondeterministic results.
+EXPLAIN (COSTS OFF)
+SELECT * FROM ex_o o
+WHERE EXISTS (SELECT 1 FROM ex_a a JOIN ex_b b ON a.x = o.x AND random() >
0.5);
+
+-- Pull-up as an antijoin: combine the correlated ON and WHERE clauses.
+-- Unmatched rows, including NULLs, must survive.
+EXPLAIN (COSTS OFF)
+SELECT * FROM ex_o o
+WHERE NOT EXISTS (SELECT 1 FROM ex_a a JOIN ex_c c ON a.x = o.x
+ WHERE c.y = o.y);
+SELECT * FROM ex_o o
+WHERE NOT EXISTS (SELECT 1 FROM ex_a a JOIN ex_c c ON a.x = o.x
+ WHERE c.y = o.y)
+ORDER BY 1;
+
+-- No pull-up for NOT EXISTS either: the LEFT JOIN preserves rows even
+-- when the correlated ON clause is false, so no outer rows should survive
+EXPLAIN (COSTS OFF)
+SELECT * FROM ex_o o
+WHERE NOT EXISTS (SELECT 1 FROM ex_a a LEFT JOIN ex_b b ON a.x = o.x);
+SELECT * FROM ex_o o
+WHERE NOT EXISTS (SELECT 1 FROM ex_a a LEFT JOIN ex_b b ON a.x = o.x)
+ORDER BY 1;
+
+-- Pull-up in a parent LEFT JOIN's ON clause: the moved qual references
+-- only its nullable side, which is included in available_rels
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x);
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x)
+ORDER BY 1, 2;
+
+-- No pull-up: the moved qual also references the preserved side of the
+-- parent LEFT JOIN, which is not included in available_rels
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x);
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x)
+ORDER BY 1, 2;
+
+DROP TABLE ex_o, ex_a, ex_b, ex_c;
+
-- Test case for sublinks pushed down into subselects via join alias expansion
--
--
2.50.1 (Apple Git-155)
From cc7bf4864d8ee296306bf0295773810061c37d93 Mon Sep 17 00:00:00 2001
From: Alena Rybakina <[email protected]>
Date: Mon, 12 Oct 2026 21:02:30 +0300
Subject: [PATCH v11 2/3] Pull up EXISTS from outer-join ON clauses referencing
both sides
An EXISTS in an outer join's ON clause cannot become a semijoin on the
nullable input when it also references the preserved input. For strict
equality correlations, group the subquery's keys and LEFT JOIN them to
the nullable input. Replace EXISTS with a match-guarded CASE testing the
preserved-side correlations in the original ON clause.
Prepare the EXISTS query once for both strategies. Choose the LEFT JOIN
fallback when the correlations exceed available_rels but fit the parent
join's two inputs, before renumbering Vars. Keep failures to move quals
across an outer join inside the subquery as failures for both strategies.
Pass preserved-side context through the existing ON traversal, without
a separate expression pass. Require every key to be fixed by the nullable
input for NOT EXISTS, and retain SubPlans for unsupported correlations,
volatile parent quals, and EXISTS under OR.
Cover LEFT and RIGHT joins, duplicates, NULLs, empty inputs, independent
keys, mixed semijoin/fallback conjuncts, and comparisons with SubPlans.
Validation: make -s -j8 check-world and pgindent --check passed.
---
src/backend/optimizer/plan/subselect.c | 312 ++++++++++--
src/backend/optimizer/prep/prepjointree.c | 79 ++-
src/include/optimizer/subselect.h | 4 +-
src/test/regress/expected/subselect.out | 564 +++++++++++++++++++++-
src/test/regress/sql/subselect.sql | 226 ++++++++-
5 files changed, 1108 insertions(+), 77 deletions(-)
diff --git a/src/backend/optimizer/plan/subselect.c
b/src/backend/optimizer/plan/subselect.c
index c72eaf2cbd7..7689feed5f0 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -33,7 +33,9 @@
#include "optimizer/planner.h"
#include "optimizer/prep.h"
#include "optimizer/subselect.h"
+#include "optimizer/tlist.h"
#include "parser/parse_relation.h"
+#include "parser/parse_oper.h"
#include "rewrite/rewriteManip.h"
#include "utils/builtins.h"
#include "utils/lsyscache.h"
@@ -95,6 +97,10 @@ static bool sublink_testexpr_is_not_nullable(PlannerInfo
*root, SubLink *sublink
static bool simplify_EXISTS_query(PlannerInfo *root, Query *query);
static bool collect_correlated_join_quals(Node *jtnode, bool nullable_side,
List **hoist_nodes);
+static JoinExpr *convert_EXISTS_query_to_left_join(PlannerInfo *root,
+
Query *subquery, Node *quals,
+
Relids preserved_rels, Relids nullable_rels,
+
bool under_not, Node **replacement);
static Query *convert_EXISTS_to_ANY(PlannerInfo *root, Query *subselect,
Node
**testexpr, List **paramIds);
static Node *replace_correlation_vars_mutator(Node *node, PlannerInfo *root);
@@ -1592,32 +1598,20 @@ sublink_testexpr_is_not_nullable(PlannerInfo *root,
SubLink *sublink)
}
/*
- * convert_EXISTS_sublink_to_join: try to convert an EXISTS SubLink to a join
- *
- * The API of this function is identical to convert_ANY_sublink_to_join's.
- *
- * References to the parent query are allowed in the WHERE clause of the
- * sub-select and in the JOIN/ON clauses that can be moved to the WHERE
- * clause without changing the result; see collect_correlated_join_quals().
+ * Prepare a private EXISTS query for either semijoin pull-up or the outer-join
+ * fallback. Keep the original Var numbering until the caller has chosen a
+ * strategy. Failure to move a qual across an outer join inside the subquery
+ * is a hard failure for both strategies.
*/
-JoinExpr *
-convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink *sublink,
- bool under_not,
Relids available_rels)
+static Query *
+prepare_EXISTS_query(PlannerInfo *root, SubLink *sublink, Node **where_clause)
{
- JoinExpr *result;
- Query *parse = root->parse;
- Query *subselect = (Query *) sublink->subselect;
+ Query *subselect = castNode(Query, sublink->subselect);
Node *whereClause;
FromExpr *jointree;
List *hoist_nodes = NIL;
ListCell *lc;
PlannerInfo subroot;
- int rtoffset;
- int varno;
- Relids clause_varnos;
- Relids upper_varnos;
-
- Assert(sublink->subLinkType == EXISTS_SUBLINK);
/*
* Can't flatten if it contains WITH. (We could arrange to pull up the
@@ -1722,6 +1716,51 @@ convert_EXISTS_sublink_to_join(PlannerInfo *root,
SubLink *sublink,
/* Now the rest of the sub-select must not refer to the parent query */
Assert(!contain_vars_of_level((Node *) subselect, 1));
+ *where_clause = whereClause;
+ return subselect;
+}
+
+/*
+ * convert_EXISTS_sublink_to_join: try to convert an EXISTS SubLink to a join
+ *
+ * Normally build a semijoin or antijoin using available_rels. When processing
+ * an outer join's ON clause, the caller may also supply preserved_rels to
+ * permit a LEFT JOIN fallback on the nullable input (available_rels).
+ * *replacement is NULL for a semijoin/antijoin, or the boolean expression
+ * replacing EXISTS for the fallback. For NOT EXISTS the caller negates it.
+ */
+JoinExpr *
+convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink *sublink,
+ bool under_not,
Relids available_rels,
+ Relids
preserved_rels, Node **replacement)
+{
+ JoinExpr *result;
+ Query *parse = root->parse;
+ Query *subselect;
+ Node *whereClause;
+ int rtoffset;
+ Relids upper_varnos;
+
+ Assert(sublink->subLinkType == EXISTS_SUBLINK);
+ *replacement = NULL;
+ subselect = prepare_EXISTS_query(root, sublink, &whereClause);
+ if (subselect == NULL)
+ return NULL;
+
+ /* Decide before renumbering or attaching anything to the parent query.
*/
+ upper_varnos = pull_varnos_of_level(root, whereClause, 1);
+ Assert(!bms_is_empty(upper_varnos));
+ if (!bms_is_subset(upper_varnos, available_rels))
+ {
+ if (preserved_rels == NULL ||
+ !bms_is_subset(upper_varnos,
+ bms_union(available_rels,
preserved_rels)))
+ return NULL;
+ return convert_EXISTS_query_to_left_join(root, subselect,
whereClause,
+
preserved_rels, available_rels,
+
under_not, replacement);
+ }
+
/*
* The subquery must have a nonempty jointree, but we can make it so.
*/
@@ -1754,30 +1793,6 @@ convert_EXISTS_sublink_to_join(PlannerInfo *root,
SubLink *sublink,
IncrementVarSublevelsUp((Node *) subselect, -1, 1);
IncrementVarSublevelsUp(whereClause, -1, 1);
- /*
- * Now that the WHERE clause is adjusted to match the parent query
- * environment, we can easily identify all the level-zero rels it uses.
- * The ones <= rtoffset belong to the upper query; the ones > rtoffset
do
- * not.
- */
- clause_varnos = pull_varnos(root, whereClause);
- upper_varnos = NULL;
- varno = -1;
- while ((varno = bms_next_member(clause_varnos, varno)) >= 0)
- {
- if (varno <= rtoffset)
- upper_varnos = bms_add_member(upper_varnos, varno);
- }
- bms_free(clause_varnos);
- Assert(!bms_is_empty(upper_varnos));
-
- /*
- * Now that we've got the set of upper-level varnos, we can make the
last
- * check: only available_rels can be referenced.
- */
- if (!bms_is_subset(upper_varnos, available_rels))
- return NULL;
-
/*
* Now we can attach the modified subquery rtable to the parent. This
also
* adds subquery's RTEPermissionInfos into the upper query.
@@ -1806,12 +1821,219 @@ convert_EXISTS_sublink_to_join(PlannerInfo *root,
SubLink *sublink,
return result;
}
+/*
+ * convert_EXISTS_query_to_left_join
+ *
+ * Handle an EXISTS in an outer join's ON clause which refers to both sides.
+ * Join distinct correlation keys to the nullable input and test the remaining
+ * correlations in the original ON clause, guarded by a match marker.
+ * For example, o LEFT JOIN a ON o.x = a.x AND EXISTS
+ * (SELECT 1 FROM b JOIN c ON c.y = a.x AND c.x = o.x) becomes
+ *
+ * o LEFT JOIN
+ * (a LEFT JOIN (SELECT DISTINCT c.y, c.x, true AS matched
+ * FROM b CROSS JOIN c) s ON s.y = a.x)
+ * ON o.x = a.x AND
+ * CASE WHEN s.matched THEN (s.x = o.x) IS TRUE ELSE false END.
+ *
+ * All projected keys are fixed by correlations to the two parent inputs.
+ * Thus at most one key group can pass ON for each original pair of rows.
+ * For NOT EXISTS, every key must be fixed by the nullable input alone:
+ * otherwise another, nonmatching key group could incorrectly pass NOT.
+ *
+ * subquery and quals are private working trees from prepare_EXISTS_query().
+ * The caller supplies larg and attaches the returned join to the nullable
+ * input. On failure the parent query and original SubLink are unchanged.
+ */
+static JoinExpr *
+convert_EXISTS_query_to_left_join(PlannerInfo *root, Query *subquery, Node
*quals,
+ Relids
preserved_rels, Relids nullable_rels,
+ bool
under_not, Node **replacement)
+{
+ List *innerquals = NIL;
+ List *outerquals = NIL;
+ List *nullablequals = NIL;
+ List *correlated = NIL;
+ List *clauses;
+ Bitmapset *fixed_keys = NULL;
+ int i;
+ ListCell *lc;
+ ParseState *pstate;
+ ParseNamespaceItem *nsitem;
+ RangeTblEntry *joinrte;
+ RangeTblRef *rtr;
+ JoinExpr *join;
+ CaseExpr *expr;
+ CaseWhen *when;
+ BooleanTest *test;
+ Var *flag;
+ Index rti;
+ Index joinrti;
+
+ /* Key grouping must not change evaluations of volatile expressions. */
+ if (contain_volatile_functions((Node *) subquery) ||
+ contain_volatile_functions(quals))
+ return NULL;
+
+ /* Collect the keys and record which are fixed by the nullable input. */
+ clauses = list_copy(make_ands_implicit((Expr *) quals));
+ for (i = 0; i < list_length(clauses); i++)
+ {
+ Node *qual = list_nth(clauses, i);
+ OpExpr *op;
+ Var *inner;
+ Var *outer;
+ Oid sortop;
+ Oid eqop;
+ bool hashable;
+ TargetEntry *tle;
+
+ /* Preparation can have introduced nested ANDs. */
+ if (is_andclause(qual))
+ {
+ clauses = list_concat(clauses, ((BoolExpr *)
qual)->args);
+ continue;
+ }
+ if (!contain_vars_of_level(qual, 1))
+ {
+ innerquals = lappend(innerquals, qual);
+ continue;
+ }
+ if (!IsA(qual, OpExpr))
+ return NULL;
+ op = (OpExpr *) qual;
+ if (list_length(op->args) != 2 ||
+ !IsA(linitial(op->args), Var) ||
!IsA(lsecond(op->args), Var))
+ return NULL;
+ inner = linitial_node(Var, op->args);
+ outer = lsecond_node(Var, op->args);
+ if (inner->varlevelsup == 1)
+ {
+ inner = lsecond_node(Var, op->args);
+ outer = linitial_node(Var, op->args);
+ }
+ if (inner->varlevelsup != 0 || outer->varlevelsup != 1 ||
+ inner->varattno <= 0 || inner->vartype !=
outer->vartype ||
+ op->inputcollid != inner->varcollid ||
+ (!bms_is_member(outer->varno, preserved_rels) &&
+ !bms_is_member(outer->varno, nullable_rels)))
+ return NULL;
+ get_sort_group_operators(inner->vartype, false, false, false,
+ &sortop,
&eqop, NULL, &hashable);
+ if (!OidIsValid(eqop) || op->opno != eqop ||
+ get_commutator(eqop) != eqop || !op_strict(eqop) ||
+ (!OidIsValid(sortop) && !hashable))
+ return NULL;
+
+ /* Normalize the equality to inner = outer. */
+ op->args = list_make2(inner, outer);
+ correlated = lappend(correlated, op);
+ tle = tlist_member((Expr *) inner, subquery->targetList);
+ if (tle == NULL)
+ {
+ SortGroupClause *group = makeNode(SortGroupClause);
+
+ tle = makeTargetEntry((Expr *) copyObject(inner),
+
list_length(subquery->targetList) + 1,
+
pstrdup("key"), false);
+ tle->ressortgroupref = tle->resno;
+ subquery->targetList = lappend(subquery->targetList,
tle);
+ group->tleSortGroupRef = tle->ressortgroupref;
+ group->eqop = eqop;
+ group->sortop = sortop;
+ group->hashable = hashable;
+ subquery->groupClause = lappend(subquery->groupClause,
group);
+ }
+ if (bms_is_member(outer->varno, nullable_rels))
+ fixed_keys = bms_add_member(fixed_keys, tle->resno);
+ }
+ if (subquery->targetList == NIL)
+ return NULL;
+
+ /* Negation is safe only when the new join is many-to-one. */
+ if (under_not &&
+ bms_num_members(fixed_keys) !=
list_length(subquery->targetList))
+ return NULL;
+
+ rti = list_length(root->parse->rtable) + 1;
+ joinrti = rti + 1;
+ foreach(lc, correlated)
+ {
+ OpExpr *op = lfirst_node(OpExpr, lc);
+ Var *inner = linitial_node(Var, op->args);
+ Var *outer = lsecond_node(Var, op->args);
+ TargetEntry *tle = tlist_member((Expr *) inner,
subquery->targetList);
+ Var *key;
+
+ Assert(tle != NULL);
+ key = makeVar(rti, tle->resno, inner->vartype, inner->vartypmod,
+ inner->varcollid, 0);
+ outer->varlevelsup = 0;
+ op->args = list_make2(key, outer);
+ if (bms_is_member(outer->varno, nullable_rels))
+ nullablequals = lappend(nullablequals, op);
+ else
+ {
+ key->varnullingrels = bms_make_singleton(joinrti);
+ outerquals = lappend(outerquals, op);
+ }
+ }
+ if (nullablequals == NIL || outerquals == NIL)
+ return NULL;
+ subquery->jointree->quals = (Node *) make_ands_explicit(innerquals);
+ if (contain_vars_of_level((Node *) subquery, 1))
+ return NULL;
+
+ /* A separate marker distinguishes no match from a nullable key value.
*/
+ subquery->targetList = lappend(subquery->targetList,
+
makeTargetEntry((Expr *) makeBoolConst(true, false),
+
list_length(subquery->targetList) + 1,
+
pstrdup("matched"), false));
+ pstate = make_parsestate(NULL);
+ nsitem = addRangeTableEntryForSubquery(pstate, subquery,
+
makeAlias("exists_keys", NIL), false, false);
+ root->parse->rtable = lappend(root->parse->rtable, nsitem->p_rte);
+ free_parsestate(pstate);
+
+ joinrte = makeNode(RangeTblEntry);
+ joinrte->rtekind = RTE_JOIN;
+ joinrte->jointype = JOIN_LEFT;
+ joinrte->eref = makeAlias("unnamed_join", NIL);
+ root->parse->rtable = lappend(root->parse->rtable, joinrte);
+ rtr = makeNode(RangeTblRef);
+ rtr->rtindex = rti;
+ join = makeNode(JoinExpr);
+ join->jointype = JOIN_LEFT;
+ join->rarg = (Node *) rtr;
+ join->quals = (Node *) make_ands_explicit(nullablequals);
+ join->rtindex = joinrti;
+
+ flag = makeVar(rti, list_length(subquery->targetList), BOOLOID,
+ -1, InvalidOid, 0);
+ flag->varnullingrels = bms_make_singleton(joinrti);
+ test = makeNode(BooleanTest);
+ test->arg = make_ands_explicit(outerquals);
+ test->booltesttype = IS_TRUE;
+ test->location = -1;
+ when = makeNode(CaseWhen);
+ when->expr = (Expr *) flag;
+ when->result = (Expr *) test;
+ when->location = -1;
+ expr = makeNode(CaseExpr);
+ expr->casetype = BOOLOID;
+ expr->args = list_make1(when);
+ expr->defresult = (Expr *) makeBoolConst(false, false);
+ expr->location = -1;
+ *replacement = (Node *) expr;
+ return join;
+}
+
/*
* collect_correlated_join_quals: find the quals of an EXISTS sub-select's
* jointree that refer to the parent query
*
- * convert_EXISTS_sublink_to_join() moves such quals to the WHERE clause of
- * the sub-select, which then becomes the semijoin or antijoin qual. That is
+ * prepare_EXISTS_query() moves such quals to the WHERE clause of the
+ * sub-select for use by either join conversion strategy. That is
* only safe for the quals of inner joins (and of FROM lists) that are not
* below the nullable side of an outer join. The ON clause of an outer join
* doesn't filter out rows of its non-nullable side, and a qual below the
diff --git a/src/backend/optimizer/prep/prepjointree.c
b/src/backend/optimizer/prep/prepjointree.c
index dfe320beccd..a122e3249a9 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -114,7 +114,8 @@ static Node *pull_up_sublinks_jointree_recurse(PlannerInfo
*root, Node *jtnode,
Relids *relids);
static Node *pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
Node **jtlink1, Relids available_rels1,
-
Node **jtlink2, Relids available_rels2);
+
Node **jtlink2, Relids available_rels2,
+
Relids preserved_rels);
static Node *pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
JoinExpr *lowest_outer_join,
AppendRelInfo *containing_appendrel);
@@ -664,7 +665,9 @@ replace_empty_jointree(Query *parse)
* side of the join). In that case it is legal to push the semijoin
* down into the nullable side of the join. If the sublink references any
* nonnullable-side variables then it would have to be evaluated as part
- * of the outer join, which makes things way too complicated.
+ * of the outer join, so we cannot use a semijoin. For some such EXISTS
+ * clauses, we can instead add a LEFT JOIN to the nullable side and keep a
+ * boolean CASE in the original ON clause.
*
* Under similar conditions, EXISTS and NOT EXISTS clauses can be handled
* by pulling up the sub-SELECT and creating a semijoin or anti-semijoin.
@@ -750,7 +753,8 @@ pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node
*jtnode,
/* Now process qual --- all children are available for use */
newf->quals = pull_up_sublinks_qual_recurse(root, f->quals,
&jtlink, frelids,
-
NULL, NULL);
+
NULL, NULL,
+
NULL);
/*
* Note that the result will be either newf, or a stack of
JoinExprs
@@ -790,7 +794,7 @@ pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node
*jtnode,
* and attach any pulled-up jointree items at the right place.
In the
* inner-join case we put new JoinExprs above the existing one
(much
* as for a FromExpr-style join). In outer-join cases the new
- * JoinExprs must go into the nullable side of the outer join.
The
+ * semijoins must go into the nullable side of the outer join.
The
* point of the available_rels machinations is to ensure that
we only
* pull up quals for which that's okay.
*
@@ -804,13 +808,16 @@ pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node
*jtnode,
&jtlink,
bms_union(leftrelids,
rightrelids),
-
NULL, NULL);
+
NULL, NULL,
+
NULL);
break;
case JOIN_LEFT:
+ /* The fallback must not multiply volatile ON
evaluations. */
j->quals = pull_up_sublinks_qual_recurse(root,
j->quals,
&j->rarg,
rightrelids,
-
NULL, NULL);
+
NULL, NULL,
+
contain_volatile_functions(j->quals) ? NULL :
leftrelids);
break;
case JOIN_FULL:
/* can't do anything with full-join quals */
@@ -819,7 +826,8 @@ pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node
*jtnode,
j->quals = pull_up_sublinks_qual_recurse(root,
j->quals,
&j->larg,
leftrelids,
-
NULL, NULL);
+
NULL, NULL,
+
contain_volatile_functions(j->quals) ? NULL :
rightrelids);
break;
default:
elog(ERROR, "unrecognized join type: %d",
@@ -854,7 +862,12 @@ pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node
*jtnode,
* denotes the relations present underneath jtlink1). Optionally, jtlink2 can
* point to a second link where new JoinExprs should be inserted if they
* reference available_rels2 (pass NULL for both those arguments if not used).
- * Note that SubLinks referencing both sets of variables cannot be optimized.
+ * SubLinks referencing both sets cannot use a semijoin. For an outer join's
+ * ON clause, preserved_rels identifies the preserved input, while jtlink1
+ * and available_rels1 identify the nullable input. This permits the EXISTS
+ * converter to choose a LEFT JOIN with a replacement qual. Pass this context
+ * only through the original ON's AND conjuncts, not into newly pulled-up
quals.
+ *
* If we find multiple pull-up-able SubLinks, they'll get stacked onto jtlink1
* and/or jtlink2 in the order we encounter them. We rely on subsequent
* optimization to rearrange the stack if appropriate.
@@ -864,7 +877,8 @@ pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node
*jtnode,
static Node *
pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
Node **jtlink1,
Relids available_rels1,
- Node **jtlink2,
Relids available_rels2)
+ Node **jtlink2,
Relids available_rels2,
+ Relids preserved_rels)
{
if (node == NULL)
return NULL;
@@ -911,7 +925,8 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
&j->larg,
available_rels1,
&j->rarg,
-
child_rels);
+
child_rels,
+
NULL);
/* Return NULL representing constant TRUE */
return NULL;
}
@@ -937,19 +952,25 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node
*node,
&j->larg,
available_rels2,
&j->rarg,
-
child_rels);
+
child_rels,
+
NULL);
/* Return NULL representing constant TRUE */
return NULL;
}
}
else if (sublink->subLinkType == EXISTS_SUBLINK)
{
+ Node *replacement;
+
if ((j = convert_EXISTS_sublink_to_join(root, sublink,
false,
-
available_rels1)) != NULL)
+
available_rels1,
+
preserved_rels, &replacement)) != NULL)
{
/* Yes; insert the new join node into the join
tree */
j->larg = *jtlink1;
*jtlink1 = (Node *) j;
+ if (replacement != NULL)
+ return replacement;
/* Recursively process pulled-up jointree nodes
*/
j->rarg =
pull_up_sublinks_jointree_recurse(root,
j->rarg,
@@ -965,13 +986,15 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node
*node,
&j->larg,
available_rels1,
&j->rarg,
-
child_rels);
+
child_rels,
+
NULL);
/* Return NULL representing constant TRUE */
return NULL;
}
if (available_rels2 != NULL &&
(j = convert_EXISTS_sublink_to_join(root,
sublink, false,
-
available_rels2)) != NULL)
+
available_rels2,
+
NULL, &replacement)) != NULL)
{
/* Yes; insert the new join node into the join
tree */
j->larg = *jtlink2;
@@ -991,7 +1014,8 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node
*node,
&j->larg,
available_rels2,
&j->rarg,
-
child_rels);
+
child_rels,
+
NULL);
/* Return NULL representing constant TRUE */
return NULL;
}
@@ -1031,7 +1055,8 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node
*node,
j->quals,
&j->rarg,
child_rels,
-
NULL, NULL);
+
NULL, NULL,
+
NULL);
/* Return NULL representing constant
TRUE */
return NULL;
}
@@ -1057,19 +1082,25 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node
*node,
j->quals,
&j->rarg,
child_rels,
-
NULL, NULL);
+
NULL, NULL,
+
NULL);
/* Return NULL representing constant
TRUE */
return NULL;
}
}
else if (sublink->subLinkType == EXISTS_SUBLINK)
{
+ Node *replacement;
+
if ((j = convert_EXISTS_sublink_to_join(root,
sublink, true,
-
available_rels1)) != NULL)
+
available_rels1,
+
preserved_rels, &replacement)) != NULL)
{
/* Yes; insert the new join node into
the join tree */
j->larg = *jtlink1;
*jtlink1 = (Node *) j;
+ if (replacement != NULL)
+ return (Node *)
make_notclause((Expr *) replacement);
/* Recursively process pulled-up
jointree nodes */
j->rarg =
pull_up_sublinks_jointree_recurse(root,
j->rarg,
@@ -1085,13 +1116,15 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node
*node,
j->quals,
&j->rarg,
child_rels,
-
NULL, NULL);
+
NULL, NULL,
+
NULL);
/* Return NULL representing constant
TRUE */
return NULL;
}
if (available_rels2 != NULL &&
(j =
convert_EXISTS_sublink_to_join(root, sublink, true,
-
available_rels2)) != NULL)
+
available_rels2,
+
NULL, &replacement)) != NULL)
{
/* Yes; insert the new join node into
the join tree */
j->larg = *jtlink2;
@@ -1111,7 +1144,8 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node
*node,
j->quals,
&j->rarg,
child_rels,
-
NULL, NULL);
+
NULL, NULL,
+
NULL);
/* Return NULL representing constant
TRUE */
return NULL;
}
@@ -1136,7 +1170,8 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node
*node,
jtlink1,
available_rels1,
jtlink2,
-
available_rels2);
+
available_rels2,
+
preserved_rels);
if (newclause)
newclauses = lappend(newclauses, newclause);
}
diff --git a/src/include/optimizer/subselect.h
b/src/include/optimizer/subselect.h
index 4ecccf46bd3..56f5f3ffcda 100644
--- a/src/include/optimizer/subselect.h
+++ b/src/include/optimizer/subselect.h
@@ -27,7 +27,9 @@ extern JoinExpr *convert_ANY_sublink_to_join(PlannerInfo
*root,
extern JoinExpr *convert_EXISTS_sublink_to_join(PlannerInfo *root,
SubLink *sublink,
bool under_not,
-
Relids available_rels);
+
Relids available_rels,
+
Relids preserved_rels,
+
Node **replacement);
extern Node *SS_replace_correlation_vars(PlannerInfo *root, Node *expr);
extern Node *SS_process_sublinks(PlannerInfo *root, Node *expr, bool isQual);
extern void SS_identify_outer_params(PlannerInfo *root);
diff --git a/src/test/regress/expected/subselect.out
b/src/test/regress/expected/subselect.out
index 612634aeb49..ed3aba87554 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -1616,14 +1616,427 @@ ORDER BY 1, 2;
|
(4 rows)
--- No pull-up: the moved qual also references the preserved side of the
--- parent LEFT JOIN, which is not included in available_rels
+-- Pull-up using a LEFT JOIN and CASE: both sides of the parent join are
+-- referenced; the new join is attached to the nullable input
EXPLAIN (COSTS OFF)
SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
ON o.x = a.x AND EXISTS
(SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x);
- QUERY PLAN
------------------------------------------
+ QUERY PLAN
+---------------------------------------------------------------------------
+ Hash Left Join
+ Hash Cond: (o.x = a.x)
+ Join Filter: CASE WHEN (true) THEN ((c.y = o.x) IS TRUE) ELSE false END
+ -> Seq Scan on ex_o o
+ -> Hash
+ -> Hash Left Join
+ Hash Cond: (a.x = c.y)
+ -> Seq Scan on ex_a a
+ -> Hash
+ -> Group
+ Group Key: c.y
+ -> Sort
+ Sort Key: c.y
+ -> Nested Loop
+ -> Seq Scan on ex_b b
+ -> Seq Scan on ex_c c
+(16 rows)
+
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x)
+ORDER BY 1, 2;
+ x | ax
+---+----
+ 1 | 1
+ 2 |
+ 3 |
+ |
+(4 rows)
+
+-- Duplicate subquery rows must not multiply either side of the parent join.
+-- Include an a row which satisfies the original ON qual but fails EXISTS.
+INSERT INTO ex_b VALUES (7, 70);
+INSERT INTO ex_c VALUES (100, 1), (200, 2), (300, NULL);
+INSERT INTO ex_a VALUES (1, 11), (2, 20), (3, 30), (NULL, 99);
+SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON a.x <= o.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x
+ WHERE b.x > 0)
+ORDER BY 1, 2, 3;
+ x | ax | y
+---+----+----
+ 1 | 1 | 10
+ 1 | 1 | 11
+ 2 | 2 | 20
+ 3 | |
+ | |
+(5 rows)
+
+-- Compare bags of rows against a SubPlan reference, including duplicates.
+WITH pulled AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON a.x <= o.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x
+ WHERE b.x > 0)
+), reference AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON a.x <= o.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x
+ WHERE b.x > 0 OFFSET 0)
+)
+(SELECT * FROM pulled EXCEPT ALL SELECT * FROM reference)
+UNION ALL
+(SELECT * FROM reference EXCEPT ALL SELECT * FROM pulled);
+ x | ax | y
+---+----+---
+(0 rows)
+
+-- NOT EXISTS must return TRUE, not NULL, when a correlation key is NULL.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON (o.x = a.x OR (o.x IS NULL AND a.x IS NULL)) AND NOT EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x);
+
QUERY PLAN
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Nested Loop Left Join
+ Join Filter: (((o.x = a.x) OR ((o.x IS NULL) AND (a.x IS NULL))) AND (NOT
CASE WHEN exists_keys.matched THEN ((exists_keys.key = o.x) IS TRUE) ELSE false
END))
+ -> Seq Scan on ex_o o
+ -> Materialize
+ -> Nested Loop Left Join
+ Join Filter: (exists_keys.key = a.x)
+ -> Seq Scan on ex_a a
+ -> Materialize
+ -> Subquery Scan on exists_keys
+ -> Group
+ Group Key: c.y
+ -> Sort
+ Sort Key: c.y
+ -> Nested Loop
+ -> Seq Scan on ex_b b
+ -> Seq Scan on ex_c c
+(16 rows)
+
+SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON (o.x = a.x OR (o.x IS NULL AND a.x IS NULL)) AND NOT EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x)
+ORDER BY 1, 2, 3;
+ x | ax | y
+---+----+----
+ 1 | |
+ 2 | |
+ 3 | 3 | 30
+ | | 99
+(4 rows)
+
+-- Check NOT EXISTS with both matching and null nullable-side keys.
+-- NOT EXISTS must still accept such an a row.
+SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = 1 AND NOT EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x)
+ORDER BY 1, 2, 3;
+ x | ax | y
+---+----+----
+ 1 | 2 | 20
+ 1 | 3 | 30
+ 1 | 5 | 50
+ 1 | | 99
+ 2 | |
+ 3 | |
+ | |
+(7 rows)
+
+-- The same transformation applies to a RIGHT JOIN.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax FROM ex_a a RIGHT JOIN ex_o o
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON o.x = c.y AND a.x = c.y);
+ QUERY PLAN
+---------------------------------------------------------------------------
+ Hash Left Join
+ Hash Cond: (o.x = a.x)
+ Join Filter: CASE WHEN (true) THEN ((c.y = o.x) IS TRUE) ELSE false END
+ -> Seq Scan on ex_o o
+ -> Hash
+ -> Hash Left Join
+ Hash Cond: (a.x = c.y)
+ -> Seq Scan on ex_a a
+ -> Hash
+ -> Group
+ Group Key: c.y
+ -> Sort
+ Sort Key: c.y
+ -> Nested Loop
+ -> Seq Scan on ex_b b
+ -> Seq Scan on ex_c c
+(16 rows)
+
+SELECT o.x, a.x AS ax FROM ex_a a RIGHT JOIN ex_o o
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON o.x = c.y AND a.x = c.y)
+ORDER BY 1, 2;
+ x | ax
+---+----
+ 1 | 1
+ 1 | 1
+ 2 | 2
+ 3 |
+ |
+(5 rows)
+
+-- A key in the preserved input can itself have been null-extended earlier.
+SELECT o.x, d.x AS dx, a.x AS ax FROM
+ (ex_o o LEFT JOIN ex_a d ON o.x = d.x AND d.x <> 2)
+ LEFT JOIN ex_a a ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = d.x)
+ORDER BY 1, 2, 3;
+ x | dx | ax
+---+----+----
+ 1 | 1 | 1
+ 1 | 1 | 1
+ 1 | 1 | 1
+ 1 | 1 | 1
+ 2 | |
+ 3 | 3 |
+ | |
+(7 rows)
+
+-- Multiple conjuncts can each add a LEFT JOIN to the nullable input.
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x)
+ AND NOT EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x
+ WHERE c.y = 2)
+ORDER BY 1, 2;
+ x | ax
+---+----
+ 1 | 1
+ 1 | 1
+ 2 |
+ 3 |
+ |
+(5 rows)
+
+-- Independent correlation keys are grouped together.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x);
+ QUERY PLAN
+------------------------------------------------------------------------------------------------------
+ Hash Left Join
+ Hash Cond: (o.x = a.x)
+ Join Filter: CASE WHEN exists_keys.matched THEN ((exists_keys.key_1 = o.x)
IS TRUE) ELSE false END
+ -> Seq Scan on ex_o o
+ -> Hash
+ -> Nested Loop Left Join
+ Join Filter: (exists_keys.key = a.x)
+ -> Seq Scan on ex_a a
+ -> Materialize
+ -> Subquery Scan on exists_keys
+ -> Group
+ Group Key: c.y, c.x
+ -> Sort
+ Sort Key: c.y, c.x
+ -> Nested Loop
+ -> Seq Scan on ex_b b
+ -> Seq Scan on ex_c c
+(17 rows)
+
+-- Off-diagonal keys and duplicates must not create extra parent rows.
+INSERT INTO ex_c VALUES (1, 1), (1, 1), (1, 2), (2, 2), (3, 9);
+SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x)
+ORDER BY 1, 2, 3;
+ x | ax | y
+---+----+----
+ 1 | 1 | 10
+ 1 | 1 | 11
+ 2 | 2 | 20
+ 3 | |
+ | |
+(5 rows)
+
+SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON a.x = o.x AND NOT EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x)
+ORDER BY 1, 2, 3;
+ x | ax | y
+---+----+----
+ 1 | |
+ 2 | |
+ 3 | 3 | 30
+ | |
+(4 rows)
+
+WITH pulled AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x)
+), reference AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x OFFSET 0)
+)
+(SELECT * FROM pulled EXCEPT ALL SELECT * FROM reference)
+UNION ALL
+(SELECT * FROM reference EXCEPT ALL SELECT * FROM pulled);
+ x | ax | y
+---+----+---
+(0 rows)
+
+WITH pulled AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON a.x = o.x AND NOT EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x)
+), reference AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON a.x = o.x AND NOT EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x OFFSET 0)
+)
+(SELECT * FROM pulled EXCEPT ALL SELECT * FROM reference)
+UNION ALL
+(SELECT * FROM reference EXCEPT ALL SELECT * FROM pulled);
+ x | ax | y
+---+----+---
+(0 rows)
+
+-- Several key groups per a are safe for EXISTS, even without o.x = a.x.
+WITH pulled AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON o.x >= a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x)
+), reference AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON o.x >= a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x OFFSET 0)
+)
+(SELECT * FROM pulled EXCEPT ALL SELECT * FROM reference)
+UNION ALL
+(SELECT * FROM reference EXCEPT ALL SELECT * FROM pulled);
+ x | ax | y
+---+----+---
+(0 rows)
+
+-- NOT EXISTS must retain its SubPlan when a can match several key groups.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND NOT EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x);
+ QUERY PLAN
+---------------------------------------------------
+ Hash Left Join
+ Hash Cond: (o.x = a.x)
+ Join Filter: (NOT EXISTS(SubPlan exists_1))
+ -> Seq Scan on ex_o o
+ -> Hash
+ -> Seq Scan on ex_a a
+ SubPlan exists_1
+ -> Nested Loop
+ -> Seq Scan on ex_b b
+ -> Seq Scan on ex_c c
+ Filter: ((y = a.x) AND (x = o.x))
+(11 rows)
+
+-- An EXISTS under OR cannot use the remaining correlations to filter groups.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x OR EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x);
+ QUERY PLAN
+----------------------------------------------------------
+ Nested Loop Left Join
+ Join Filter: ((o.x = a.x) OR EXISTS(SubPlan exists_1))
+ -> Seq Scan on ex_o o
+ -> Materialize
+ -> Seq Scan on ex_a a
+ SubPlan exists_1
+ -> Nested Loop
+ -> Seq Scan on ex_b b
+ -> Seq Scan on ex_c c
+ Filter: ((y = a.x) AND (x = o.x))
+(10 rows)
+
+-- Do not multiply evaluations of volatile parent quals.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x FROM ex_o o LEFT JOIN ex_a a
+ ON random() > 0.5 AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x);
+ QUERY PLAN
+------------------------------------------------------------------------------------
+ Nested Loop Left Join
+ Join Filter: ((random() > '0.5'::double precision) AND EXISTS(SubPlan
exists_1))
+ -> Seq Scan on ex_o o
+ -> Materialize
+ -> Seq Scan on ex_a a
+ SubPlan exists_1
+ -> Nested Loop
+ -> Seq Scan on ex_b b
+ -> Seq Scan on ex_c c
+ Filter: ((y = a.x) AND (x = o.x))
+(10 rows)
+
+DELETE FROM ex_c WHERE x < 100;
+-- Pull-up does not require an equality in the parent ON.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x >= a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x);
+ QUERY PLAN
+-------------------------------------------------------------------------------------------------------------------------
+ Nested Loop Left Join
+ Join Filter: ((o.x >= a.x) AND CASE WHEN exists_keys.matched THEN
((exists_keys.key_1 = o.x) IS TRUE) ELSE false END)
+ -> Seq Scan on ex_o o
+ -> Materialize
+ -> Nested Loop Left Join
+ Join Filter: (exists_keys.key = a.x)
+ -> Seq Scan on ex_a a
+ -> Materialize
+ -> Subquery Scan on exists_keys
+ -> Group
+ Group Key: c.y, c.x
+ -> Sort
+ Sort Key: c.y, c.x
+ -> Nested Loop
+ -> Seq Scan on ex_b b
+ -> Seq Scan on ex_c c
+(16 rows)
+
+-- Other parent conjuncts can contain OR.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON (o.x = a.x OR o.y = 1) AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x);
+ QUERY PLAN
+---------------------------------------------------------------------------------------------------------------------------------------
+ Nested Loop Left Join
+ Join Filter: (CASE WHEN exists_keys.matched THEN ((exists_keys.key_1 = o.x)
IS TRUE) ELSE false END AND ((o.x = a.x) OR (o.y = 1)))
+ -> Seq Scan on ex_o o
+ -> Materialize
+ -> Nested Loop Left Join
+ Join Filter: (exists_keys.key = a.x)
+ -> Seq Scan on ex_a a
+ -> Materialize
+ -> Subquery Scan on exists_keys
+ -> Group
+ Group Key: c.y, c.x
+ -> Sort
+ Sort Key: c.y, c.x
+ -> Nested Loop
+ -> Seq Scan on ex_b b
+ -> Seq Scan on ex_c c
+(16 rows)
+
+-- No pull-up for a volatile correlated qual.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c
+ ON c.y = a.x AND c.y = o.x AND random() > 0.5);
+ QUERY PLAN
+-------------------------------------------------------------------
Hash Left Join
Hash Cond: (o.x = a.x)
Join Filter: EXISTS(SubPlan exists_1)
@@ -1634,22 +2047,159 @@ SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
-> Result
One-Time Filter: (a.x = o.x)
-> Nested Loop
+ Join Filter: (random() > '0.5'::double precision)
-> Seq Scan on ex_b b
-> Seq Scan on ex_c c
Filter: (y = o.x)
-(13 rows)
+(14 rows)
+
+-- Multiple preserved-side keys, with correlations in WHERE rather than ON.
+INSERT INTO ex_o VALUES (1, 10);
+INSERT INTO ex_c VALUES (1, 10), (1, 10), (1, 11);
+SELECT o.x, o.y, a.x AS ax, a.y AS ay FROM ex_o o LEFT JOIN ex_a a
+ ON EXISTS (SELECT 1 FROM ex_b b, ex_c c
+ WHERE c.x = o.x AND c.y = o.y AND c.x = a.x AND c.y = a.y)
+ORDER BY 1, 2, 3, 4;
+ x | y | ax | ay
+---+----+----+----
+ 1 | 1 | |
+ 1 | 10 | 1 | 10
+ 2 | 2 | |
+ 3 | 3 | |
+ | | |
+(5 rows)
+
+-- Check NOT EXISTS against a SubPlan for keys fixed by the nullable side.
+WITH pulled AS (
+ SELECT o.x, o.y, a.x AS ax, a.y AS ay FROM ex_o o LEFT JOIN ex_a a
+ ON NOT EXISTS (SELECT 1 FROM ex_b b, ex_c c
+ WHERE c.x = o.x AND c.y = o.y AND c.x = a.x AND c.y = a.y)
+), reference AS (
+ SELECT o.x, o.y, a.x AS ax, a.y AS ay FROM ex_o o LEFT JOIN ex_a a
+ ON NOT EXISTS (SELECT 1 FROM ex_b b, ex_c c
+ WHERE c.x = o.x AND c.y = o.y AND c.x = a.x AND c.y = a.y
+ OFFSET 0)
+)
+(SELECT * FROM pulled EXCEPT ALL SELECT * FROM reference)
+UNION ALL
+(SELECT * FROM reference EXCEPT ALL SELECT * FROM pulled);
+ x | y | ax | ay
+---+---+----+----
+(0 rows)
+-- Ordinary semijoin pull-up and LEFT JOIN fallback share the ON traversal.
+-- Put the fallback first so the later semijoin is attached above it.
+EXPLAIN (COSTS OFF)
SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
ON o.x = a.x AND EXISTS
- (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x)
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x)
+ AND EXISTS (SELECT 1 FROM ex_c c WHERE c.y = a.x);
+ QUERY PLAN
+-----------------------------------------------------------------------------------------------
+ Nested Loop Left Join
+ Join Filter: (CASE WHEN (true) THEN ((c_1.x = o.x) IS TRUE) ELSE false END
AND (o.x = a.x))
+ -> Seq Scan on ex_o o
+ -> Materialize
+ -> Nested Loop Left Join
+ Join Filter: (c_1.y = a.x)
+ -> Nested Loop Semi Join
+ Join Filter: (a.x = c.y)
+ -> Seq Scan on ex_a a
+ -> Materialize
+ -> Seq Scan on ex_c c
+ -> Group
+ Group Key: c_1.y, c_1.x
+ -> Sort
+ Sort Key: c_1.y, c_1.x
+ -> Nested Loop
+ -> Seq Scan on ex_b b
+ -> Seq Scan on ex_c c_1
+(18 rows)
+
+WITH pulled AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x)
+ AND EXISTS (SELECT 1 FROM ex_c c WHERE c.y = a.x)
+), reference AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x OFFSET 0)
+ AND EXISTS (SELECT 1 FROM ex_c c WHERE c.y = a.x OFFSET 0)
+)
+(SELECT * FROM pulled EXCEPT ALL SELECT * FROM reference)
+UNION ALL
+(SELECT * FROM reference EXCEPT ALL SELECT * FROM pulled);
+ x | ax | y
+---+----+---
+(0 rows)
+
+-- A correlation in an inner outer-join ON is a hard failure, even when
+-- the parent ON provides both preserved and nullable inputs for a fallback.
+-- Since b is nonempty, the subquery has rows regardless of its ON result.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b LEFT JOIN ex_c c ON c.y = a.x AND c.x = o.x);
+ QUERY PLAN
+---------------------------------------------------
+ Hash Left Join
+ Hash Cond: (o.x = a.x)
+ Join Filter: EXISTS(SubPlan exists_1)
+ -> Seq Scan on ex_o o
+ -> Hash
+ -> Seq Scan on ex_a a
+ SubPlan exists_1
+ -> Nested Loop Left Join
+ -> Seq Scan on ex_b b
+ -> Seq Scan on ex_c c
+ Filter: ((y = a.x) AND (x = o.x))
+(11 rows)
+
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b LEFT JOIN ex_c c ON c.y = a.x AND c.x = o.x)
ORDER BY 1, 2;
x | ax
---+----
1 | 1
+ 1 | 1
+ 1 | 1
+ 1 | 1
+ 2 | 2
+ 3 | 3
+ |
+(7 rows)
+
+-- Empty inner input must preserve every o row, with a null-extended a.
+DELETE FROM ex_b;
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x)
+ORDER BY 1, 2;
+ x | ax
+---+----
+ 1 |
+ 1 |
2 |
3 |
|
-(4 rows)
+(5 rows)
+
+SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON (o.x = a.x OR (o.x IS NULL AND a.x IS NULL)) AND NOT EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x)
+ORDER BY 1, 2, 3;
+ x | ax | y
+---+----+----
+ 1 | 1 | 10
+ 1 | 1 | 10
+ 1 | 1 | 11
+ 1 | 1 | 11
+ 2 | 2 | 20
+ 3 | 3 | 30
+ | | 99
+(7 rows)
DROP TABLE ex_o, ex_a, ex_b, ex_c;
-- Test case for sublinks pushed down into subselects via join alias expansion
diff --git a/src/test/regress/sql/subselect.sql
b/src/test/regress/sql/subselect.sql
index 16e92f51f5e..8f6fbf7d095 100644
--- a/src/test/regress/sql/subselect.sql
+++ b/src/test/regress/sql/subselect.sql
@@ -807,8 +807,8 @@ SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
(SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x)
ORDER BY 1, 2;
--- No pull-up: the moved qual also references the preserved side of the
--- parent LEFT JOIN, which is not included in available_rels
+-- Pull-up using a LEFT JOIN and CASE: both sides of the parent join are
+-- referenced; the new join is attached to the nullable input
EXPLAIN (COSTS OFF)
SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
ON o.x = a.x AND EXISTS
@@ -818,6 +818,228 @@ SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
(SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x)
ORDER BY 1, 2;
+-- Duplicate subquery rows must not multiply either side of the parent join.
+-- Include an a row which satisfies the original ON qual but fails EXISTS.
+INSERT INTO ex_b VALUES (7, 70);
+INSERT INTO ex_c VALUES (100, 1), (200, 2), (300, NULL);
+INSERT INTO ex_a VALUES (1, 11), (2, 20), (3, 30), (NULL, 99);
+SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON a.x <= o.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x
+ WHERE b.x > 0)
+ORDER BY 1, 2, 3;
+
+-- Compare bags of rows against a SubPlan reference, including duplicates.
+WITH pulled AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON a.x <= o.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x
+ WHERE b.x > 0)
+), reference AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON a.x <= o.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x
+ WHERE b.x > 0 OFFSET 0)
+)
+(SELECT * FROM pulled EXCEPT ALL SELECT * FROM reference)
+UNION ALL
+(SELECT * FROM reference EXCEPT ALL SELECT * FROM pulled);
+
+-- NOT EXISTS must return TRUE, not NULL, when a correlation key is NULL.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON (o.x = a.x OR (o.x IS NULL AND a.x IS NULL)) AND NOT EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x);
+SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON (o.x = a.x OR (o.x IS NULL AND a.x IS NULL)) AND NOT EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x)
+ORDER BY 1, 2, 3;
+
+-- Check NOT EXISTS with both matching and null nullable-side keys.
+-- NOT EXISTS must still accept such an a row.
+SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = 1 AND NOT EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x)
+ORDER BY 1, 2, 3;
+
+-- The same transformation applies to a RIGHT JOIN.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax FROM ex_a a RIGHT JOIN ex_o o
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON o.x = c.y AND a.x = c.y);
+SELECT o.x, a.x AS ax FROM ex_a a RIGHT JOIN ex_o o
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON o.x = c.y AND a.x = c.y)
+ORDER BY 1, 2;
+
+-- A key in the preserved input can itself have been null-extended earlier.
+SELECT o.x, d.x AS dx, a.x AS ax FROM
+ (ex_o o LEFT JOIN ex_a d ON o.x = d.x AND d.x <> 2)
+ LEFT JOIN ex_a a ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = d.x)
+ORDER BY 1, 2, 3;
+
+-- Multiple conjuncts can each add a LEFT JOIN to the nullable input.
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x)
+ AND NOT EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x
+ WHERE c.y = 2)
+ORDER BY 1, 2;
+
+-- Independent correlation keys are grouped together.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x);
+-- Off-diagonal keys and duplicates must not create extra parent rows.
+INSERT INTO ex_c VALUES (1, 1), (1, 1), (1, 2), (2, 2), (3, 9);
+SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x)
+ORDER BY 1, 2, 3;
+SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON a.x = o.x AND NOT EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x)
+ORDER BY 1, 2, 3;
+WITH pulled AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x)
+), reference AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x OFFSET 0)
+)
+(SELECT * FROM pulled EXCEPT ALL SELECT * FROM reference)
+UNION ALL
+(SELECT * FROM reference EXCEPT ALL SELECT * FROM pulled);
+WITH pulled AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON a.x = o.x AND NOT EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x)
+), reference AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON a.x = o.x AND NOT EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x OFFSET 0)
+)
+(SELECT * FROM pulled EXCEPT ALL SELECT * FROM reference)
+UNION ALL
+(SELECT * FROM reference EXCEPT ALL SELECT * FROM pulled);
+-- Several key groups per a are safe for EXISTS, even without o.x = a.x.
+WITH pulled AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON o.x >= a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x)
+), reference AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON o.x >= a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x OFFSET 0)
+)
+(SELECT * FROM pulled EXCEPT ALL SELECT * FROM reference)
+UNION ALL
+(SELECT * FROM reference EXCEPT ALL SELECT * FROM pulled);
+-- NOT EXISTS must retain its SubPlan when a can match several key groups.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND NOT EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x);
+-- An EXISTS under OR cannot use the remaining correlations to filter groups.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x OR EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x);
+-- Do not multiply evaluations of volatile parent quals.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x FROM ex_o o LEFT JOIN ex_a a
+ ON random() > 0.5 AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x);
+DELETE FROM ex_c WHERE x < 100;
+-- Pull-up does not require an equality in the parent ON.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x >= a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x);
+-- Other parent conjuncts can contain OR.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON (o.x = a.x OR o.y = 1) AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x);
+-- No pull-up for a volatile correlated qual.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c
+ ON c.y = a.x AND c.y = o.x AND random() > 0.5);
+
+-- Multiple preserved-side keys, with correlations in WHERE rather than ON.
+INSERT INTO ex_o VALUES (1, 10);
+INSERT INTO ex_c VALUES (1, 10), (1, 10), (1, 11);
+SELECT o.x, o.y, a.x AS ax, a.y AS ay FROM ex_o o LEFT JOIN ex_a a
+ ON EXISTS (SELECT 1 FROM ex_b b, ex_c c
+ WHERE c.x = o.x AND c.y = o.y AND c.x = a.x AND c.y = a.y)
+ORDER BY 1, 2, 3, 4;
+-- Check NOT EXISTS against a SubPlan for keys fixed by the nullable side.
+WITH pulled AS (
+ SELECT o.x, o.y, a.x AS ax, a.y AS ay FROM ex_o o LEFT JOIN ex_a a
+ ON NOT EXISTS (SELECT 1 FROM ex_b b, ex_c c
+ WHERE c.x = o.x AND c.y = o.y AND c.x = a.x AND c.y = a.y)
+), reference AS (
+ SELECT o.x, o.y, a.x AS ax, a.y AS ay FROM ex_o o LEFT JOIN ex_a a
+ ON NOT EXISTS (SELECT 1 FROM ex_b b, ex_c c
+ WHERE c.x = o.x AND c.y = o.y AND c.x = a.x AND c.y = a.y
+ OFFSET 0)
+)
+(SELECT * FROM pulled EXCEPT ALL SELECT * FROM reference)
+UNION ALL
+(SELECT * FROM reference EXCEPT ALL SELECT * FROM pulled);
+
+-- Ordinary semijoin pull-up and LEFT JOIN fallback share the ON traversal.
+-- Put the fallback first so the later semijoin is attached above it.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x)
+ AND EXISTS (SELECT 1 FROM ex_c c WHERE c.y = a.x);
+WITH pulled AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x)
+ AND EXISTS (SELECT 1 FROM ex_c c WHERE c.y = a.x)
+), reference AS (
+ SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.x = o.x OFFSET 0)
+ AND EXISTS (SELECT 1 FROM ex_c c WHERE c.y = a.x OFFSET 0)
+)
+(SELECT * FROM pulled EXCEPT ALL SELECT * FROM reference)
+UNION ALL
+(SELECT * FROM reference EXCEPT ALL SELECT * FROM pulled);
+
+-- A correlation in an inner outer-join ON is a hard failure, even when
+-- the parent ON provides both preserved and nullable inputs for a fallback.
+-- Since b is nonempty, the subquery has rows regardless of its ON result.
+EXPLAIN (COSTS OFF)
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b LEFT JOIN ex_c c ON c.y = a.x AND c.x = o.x);
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b LEFT JOIN ex_c c ON c.y = a.x AND c.x = o.x)
+ORDER BY 1, 2;
+
+-- Empty inner input must preserve every o row, with a null-extended a.
+DELETE FROM ex_b;
+SELECT o.x, a.x AS ax FROM ex_o o LEFT JOIN ex_a a
+ ON o.x = a.x AND EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x)
+ORDER BY 1, 2;
+SELECT o.x, a.x AS ax, a.y FROM ex_o o LEFT JOIN ex_a a
+ ON (o.x = a.x OR (o.x IS NULL AND a.x IS NULL)) AND NOT EXISTS
+ (SELECT 1 FROM ex_b b JOIN ex_c c ON c.y = a.x AND c.y = o.x)
+ORDER BY 1, 2, 3;
+
DROP TABLE ex_o, ex_a, ex_b, ex_c;
-- Test case for sublinks pushed down into subselects via join alias expansion
--
2.50.1 (Apple Git-155)
