On 5/9/2022 12:22, Richard Guo wrote:
To resolve both issues, lower outer join passes through pull_sublinks_* into flattening routine (see attachment).On Fri, Sep 2, 2022 at 7:09 PM Andrey Lepikhov <a.lepik...@postgrespro.ru <mailto:a.lepik...@postgrespro.ru>> wrote:> Hmm, I'm not sure this patch works correctly in all cases. It seems to > me this patch pulls up the subquery without checking the constraints > imposed by lateral references. If its quals contain any lateral > references to rels outside a higher outer join, we would need to > postpone quals from below an outer join to above it, which is probably > incorrect. Yeah, it's not easy-to-solve problem. If I correctly understand the code, to fix this problem we must implement the same logic, aspull_up_subqueries (lowest_outer_join/safe_upper_varnos).Yeah, I think we'd have to consider the restrictions from lateral references to guarantee correctness when we pull up subqueries. We need to avoid the situation where quals need to be postponed past outer join. However, even if we have taken care of that, there may be other issues with flattening direct-correlated ANY SubLink. The constraints imposed by LATERAL references may make it impossible for us to find any legal join orders, as discussed in [1].
I've added these cases into subselect.sql -- regards, Andrey Lepikhov Postgres Professional
From 883f9586acb5482bb88d5ca5123195c0efdd9cc7 Mon Sep 17 00:00:00 2001
From: Andrey Lepikhov <a.lepik...@postgrespro.ru>
Date: Mon, 5 Sep 2022 16:40:48 +0500
Subject: [PATCH] Pass a lower outer join through the pullup_sublink recursive
procedure to find out some situations when qual references outer side of an
outer join.
---
src/backend/optimizer/plan/subselect.c | 19 ++++--
src/backend/optimizer/prep/prepjointree.c | 71 ++++++++++++++---------
src/include/optimizer/subselect.h | 3 +-
src/test/regress/expected/subselect.out | 52 +++++++++++++++++
src/test/regress/sql/subselect.sql | 18 ++++++
5 files changed, 131 insertions(+), 32 deletions(-)
diff --git a/src/backend/optimizer/plan/subselect.c
b/src/backend/optimizer/plan/subselect.c
index 0e7ddc4a4e..29da43bb4d 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -1442,7 +1442,8 @@ pull_subquery_clauses_mutator(Node *node, correlated_t
*ctx)
}
static List *
-pull_correlated_clauses(PlannerInfo *root, SubLink *sublink)
+pull_correlated_clauses(PlannerInfo *root, SubLink *sublink,
+ JoinExpr *lowest_outer_join)
{
Query *parse = root->parse;
Query *subselect = (Query *) sublink->subselect;
@@ -1451,6 +1452,7 @@ pull_correlated_clauses(PlannerInfo *root, SubLink
*sublink)
.newvarno =
list_length(parse->rtable) + 1, /* Looks like a hack */
.pulling_quals = NIL,
.varlevel_up = false};
+ Relids safe_upper_varnos = NULL;
Assert(IsA(subselect, Query));
@@ -1489,7 +1491,16 @@ pull_correlated_clauses(PlannerInfo *root, SubLink
*sublink)
f = subselect->jointree;
if (!f || !f->quals || !quals_is_pullable(f->quals))
- /* Degenerate case */
+ return NULL;
+
+ if (lowest_outer_join)
+ safe_upper_varnos = get_relids_in_jointree(
+ (lowest_outer_join->jointype == JOIN_RIGHT) ?
+ lowest_outer_join->larg :
lowest_outer_join->rarg, true);
+
+ if (safe_upper_varnos &&
+ !bms_is_subset(pull_varnos_of_level(root, f->quals, 1),
+ safe_upper_varnos))
return NULL;
/*
@@ -1540,7 +1551,7 @@ pull_correlated_clauses(PlannerInfo *root, SubLink
*sublink)
*/
JoinExpr *
convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
- Relids available_rels)
+ Relids available_rels,
JoinExpr *lowest_outer_join)
{
JoinExpr *result;
Query *parse = root->parse;
@@ -1586,7 +1597,7 @@ convert_ANY_sublink_to_join(PlannerInfo *root, SubLink
*sublink,
* pulled_clauses list, their places in the quals replaces by "true"
value.
*/
if (contain_vars_of_level((Node *) subselect, 1) &&
- (pclauses = pull_correlated_clauses(root, sublink)) == NIL)
+ (pclauses = pull_correlated_clauses(root, sublink,
lowest_outer_join)) == NIL)
return NULL;
/* Create a dummy ParseState for addRangeTableEntryForSubquery */
diff --git a/src/backend/optimizer/prep/prepjointree.c
b/src/backend/optimizer/prep/prepjointree.c
index 41c7066d90..5458230c81 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -62,10 +62,12 @@ typedef struct reduce_outer_joins_state
} reduce_outer_joins_state;
static Node *pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node *jtnode,
-
Relids *relids);
+
Relids *relids,
+
JoinExpr *lowest_outer_join);
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,
+
JoinExpr *lowest_outer_join);
static Node *pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
JoinExpr *lowest_outer_join,
JoinExpr *lowest_nulling_outer_join,
@@ -293,7 +295,7 @@ pull_up_sublinks(PlannerInfo *root)
/* Begin recursion through the jointree */
jtnode = pull_up_sublinks_jointree_recurse(root,
(Node *) root->parse->jointree,
-
&relids);
+
&relids, NULL);
/*
* root->parse->jointree must always be a FromExpr, so insert a dummy
one
@@ -313,7 +315,7 @@ pull_up_sublinks(PlannerInfo *root)
*/
static Node *
pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node *jtnode,
- Relids
*relids)
+ Relids
*relids, JoinExpr *lowest_outer_join)
{
if (jtnode == NULL)
{
@@ -343,7 +345,8 @@ pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node
*jtnode,
newchild = pull_up_sublinks_jointree_recurse(root,
lfirst(l),
-
&childrelids);
+
&childrelids,
+
lowest_outer_join);
newfromlist = lappend(newfromlist, newchild);
frelids = bms_join(frelids, childrelids);
}
@@ -354,7 +357,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,
+
lowest_outer_join);
/*
* Note that the result will be either newf, or a stack of
JoinExprs
@@ -385,9 +389,11 @@ pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node
*jtnode,
/* Recurse to process children and collect their relids */
j->larg = pull_up_sublinks_jointree_recurse(root, j->larg,
-
&leftrelids);
+
&leftrelids,
+
lowest_outer_join);
j->rarg = pull_up_sublinks_jointree_recurse(root, j->rarg,
-
&rightrelids);
+
&rightrelids,
+
lowest_outer_join);
/*
* Now process qual, showing appropriate child relids as
available,
@@ -408,13 +414,14 @@ pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node
*jtnode,
&jtlink,
bms_union(leftrelids,
rightrelids),
-
NULL, NULL);
+
NULL, NULL,
+
lowest_outer_join);
break;
case JOIN_LEFT:
j->quals = pull_up_sublinks_qual_recurse(root,
j->quals,
&j->rarg,
rightrelids,
-
NULL, NULL);
+
NULL, NULL, j);
break;
case JOIN_FULL:
/* can't do anything with full-join quals */
@@ -423,7 +430,7 @@ 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, j);
break;
default:
elog(ERROR, "unrecognized join type: %d",
@@ -468,7 +475,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,
+ JoinExpr
*lowest_outer_join)
{
if (node == NULL)
return NULL;
@@ -482,7 +490,8 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
if (sublink->subLinkType == ANY_SUBLINK)
{
if ((j = convert_ANY_sublink_to_join(root, sublink,
-
available_rels1)) != NULL)
+
available_rels1,
+
lowest_outer_join)) != NULL)
{
/* Yes; insert the new join node into the join
tree */
j->larg = *jtlink1;
@@ -490,7 +499,7 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
/* Recursively process pulled-up jointree nodes
*/
j->rarg =
pull_up_sublinks_jointree_recurse(root,
j->rarg,
-
&child_rels);
+
&child_rels, j);
/*
* Now recursively process the pulled-up quals.
Any inserted
@@ -502,13 +511,15 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node
*node,
&j->larg,
available_rels1,
&j->rarg,
-
child_rels);
+
child_rels,
+
j);
/* Return NULL representing constant TRUE */
return NULL;
}
if (available_rels2 != NULL &&
(j = convert_ANY_sublink_to_join(root, sublink,
-
available_rels2)) != NULL)
+
available_rels2,
+
lowest_outer_join)) != NULL)
{
/* Yes; insert the new join node into the join
tree */
j->larg = *jtlink2;
@@ -516,7 +527,7 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
/* Recursively process pulled-up jointree nodes
*/
j->rarg =
pull_up_sublinks_jointree_recurse(root,
j->rarg,
-
&child_rels);
+
&child_rels, j);
/*
* Now recursively process the pulled-up quals.
Any inserted
@@ -528,7 +539,8 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
&j->larg,
available_rels2,
&j->rarg,
-
child_rels);
+
child_rels,
+
j);
/* Return NULL representing constant TRUE */
return NULL;
}
@@ -544,7 +556,7 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
/* Recursively process pulled-up jointree nodes
*/
j->rarg =
pull_up_sublinks_jointree_recurse(root,
j->rarg,
-
&child_rels);
+
&child_rels, j);
/*
* Now recursively process the pulled-up quals.
Any inserted
@@ -556,7 +568,8 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
&j->larg,
available_rels1,
&j->rarg,
-
child_rels);
+
child_rels,
+
j);
/* Return NULL representing constant TRUE */
return NULL;
}
@@ -570,7 +583,7 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
/* Recursively process pulled-up jointree nodes
*/
j->rarg =
pull_up_sublinks_jointree_recurse(root,
j->rarg,
-
&child_rels);
+
&child_rels, j);
/*
* Now recursively process the pulled-up quals.
Any inserted
@@ -582,7 +595,8 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
&j->larg,
available_rels2,
&j->rarg,
-
child_rels);
+
child_rels,
+
j);
/* Return NULL representing constant TRUE */
return NULL;
}
@@ -610,7 +624,7 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
/* Recursively process pulled-up
jointree nodes */
j->rarg =
pull_up_sublinks_jointree_recurse(root,
j->rarg,
-
&child_rels);
+
&child_rels, j);
/*
* Now recursively process the
pulled-up quals. Because
@@ -622,7 +636,8 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
j->quals,
&j->rarg,
child_rels,
-
NULL, NULL);
+
NULL, NULL,
+
lowest_outer_join);
/* Return NULL representing constant
TRUE */
return NULL;
}
@@ -636,7 +651,7 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
/* Recursively process pulled-up
jointree nodes */
j->rarg =
pull_up_sublinks_jointree_recurse(root,
j->rarg,
-
&child_rels);
+
&child_rels, j);
/*
* Now recursively process the
pulled-up quals. Because
@@ -648,7 +663,8 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
j->quals,
&j->rarg,
child_rels,
-
NULL, NULL);
+
NULL, NULL,
+
lowest_outer_join);
/* Return NULL representing constant
TRUE */
return NULL;
}
@@ -673,7 +689,8 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
jtlink1,
available_rels1,
jtlink2,
-
available_rels2);
+
available_rels2,
+
lowest_outer_join);
if (newclause)
newclauses = lappend(newclauses, newclause);
}
diff --git a/src/include/optimizer/subselect.h
b/src/include/optimizer/subselect.h
index 456d3076e0..4e126e45ee 100644
--- a/src/include/optimizer/subselect.h
+++ b/src/include/optimizer/subselect.h
@@ -19,7 +19,8 @@
extern void SS_process_ctes(PlannerInfo *root);
extern JoinExpr *convert_ANY_sublink_to_join(PlannerInfo *root,
SubLink *sublink,
-
Relids available_rels);
+
Relids available_rels,
+
JoinExpr *lowest_outer_join);
extern JoinExpr *convert_EXISTS_sublink_to_join(PlannerInfo *root,
SubLink *sublink,
bool under_not,
diff --git a/src/test/regress/expected/subselect.out
b/src/test/regress/expected/subselect.out
index 7caef83412..a4a224d16b 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -206,6 +206,58 @@ SELECT f1 AS "Correlated Field", f3 AS "Second Field"
3 | 3
(5 rows)
+-- Constraints, imposed by LATERAL references, prohibit flattening of
underlying
+-- Sublink.
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM SUBSELECT_TBL a
+ WHERE EXISTS (SELECT f2 FROM SUBSELECT_TBL b WHERE f3 IN (
+ SELECT f3 FROM SUBSELECT_TBL c WHERE c.f1 = a.f2));
+ QUERY PLAN
+-----------------------------------------------
+ Aggregate
+ -> Nested Loop Semi Join
+ Join Filter: (SubPlan 1)
+ -> Seq Scan on subselect_tbl a
+ -> Materialize
+ -> Seq Scan on subselect_tbl b
+ SubPlan 1
+ -> Seq Scan on subselect_tbl c
+ Filter: (f1 = a.f2)
+(9 rows)
+
+SELECT count(*) FROM SUBSELECT_TBL a
+ WHERE EXISTS (SELECT f2 FROM SUBSELECT_TBL b WHERE f3 IN (
+ SELECT f3 FROM SUBSELECT_TBL c WHERE c.f1 = a.f2));
+ count
+-------
+ 5
+(1 row)
+
+-- Prohibit to unnest subquery - quals contain lateral references to rels
+-- outside a higher outer join.
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM SUBSELECT_TBL a LEFT JOIN SUBSELECT_TBL b ON b.f1 IN (
+ SELECT c.f2 FROM SUBSELECT_TBL c WHERE c.f3 = a.f2);
+ QUERY PLAN
+---------------------------------------------------------
+ Aggregate
+ -> Nested Loop Left Join
+ Join Filter: (SubPlan 1)
+ -> Seq Scan on subselect_tbl a
+ -> Materialize
+ -> Seq Scan on subselect_tbl b
+ SubPlan 1
+ -> Seq Scan on subselect_tbl c
+ Filter: (f3 = (a.f2)::double precision)
+(9 rows)
+
+SELECT count(*) FROM SUBSELECT_TBL a LEFT JOIN SUBSELECT_TBL b ON b.f1 IN (
+ SELECT c.f2 FROM SUBSELECT_TBL c WHERE c.f3 = a.f2);
+ count
+-------
+ 18
+(1 row)
+
EXPLAIN (COSTS OFF)
SELECT * FROM subselect_tbl a
WHERE a.f1 IN
diff --git a/src/test/regress/sql/subselect.sql
b/src/test/regress/sql/subselect.sql
index b29036e236..de68306a9e 100644
--- a/src/test/regress/sql/subselect.sql
+++ b/src/test/regress/sql/subselect.sql
@@ -82,6 +82,24 @@ SELECT f1 AS "Correlated Field", f3 AS "Second Field"
WHERE f1 IN
(SELECT f2 FROM SUBSELECT_TBL WHERE CAST(upper.f2 AS float) = f3);
+-- Constraints, imposed by LATERAL references, prohibit flattening of
underlying
+-- Sublink.
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM SUBSELECT_TBL a
+ WHERE EXISTS (SELECT f2 FROM SUBSELECT_TBL b WHERE f3 IN (
+ SELECT f3 FROM SUBSELECT_TBL c WHERE c.f1 = a.f2));
+SELECT count(*) FROM SUBSELECT_TBL a
+ WHERE EXISTS (SELECT f2 FROM SUBSELECT_TBL b WHERE f3 IN (
+ SELECT f3 FROM SUBSELECT_TBL c WHERE c.f1 = a.f2));
+
+-- Prohibit to unnest subquery - quals contain lateral references to rels
+-- outside a higher outer join.
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM SUBSELECT_TBL a LEFT JOIN SUBSELECT_TBL b ON b.f1 IN (
+ SELECT c.f2 FROM SUBSELECT_TBL c WHERE c.f3 = a.f2);
+SELECT count(*) FROM SUBSELECT_TBL a LEFT JOIN SUBSELECT_TBL b ON b.f1 IN (
+ SELECT c.f2 FROM SUBSELECT_TBL c WHERE c.f3 = a.f2);
+
EXPLAIN (COSTS OFF)
SELECT * FROM subselect_tbl a
WHERE a.f1 IN
--
2.37.2
