An inefficient query caused by unnecessary PlaceHolderVar

From bbf92981fae6bc83e622d87ff18bbc4021a2f6f2 Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Thu, 11 May 2023 17:54:26 +0800
Subject: [PATCH v2] Avoid unnecessary PlaceHolderVars for simple Vars

When we pull up a lateral subquery, if a simple Var in subquery's
targetlist is lateral reference to something outside the subquery being
pulled up, usually we need to wrap it in a PlaceHolderVar.  But if the
referenced rel is under the same lowest nulling outer join, we can omit
the PlaceHolderVar.

This patch checks that and avoids unnecessary PHVs.  This could be
beneficial because such PHVs imply lateral dependencies which makes us
have to use nestloop.
---
 src/backend/optimizer/prep/prepjointree.c | 53 +++++++++++++++++----
 src/test/regress/expected/join.out        | 58 +++++++++++++++++++++++
 src/test/regress/sql/join.sql             | 14 ++++++
 3 files changed, 115 insertions(+), 10 deletions(-)

diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 73ff40721c..b0fda8bd98 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -49,6 +49,9 @@ typedef struct pullup_replace_vars_context
 	RangeTblEntry *target_rte;	/* RTE of subquery */
 	Relids		relids;			/* relids within subquery, as numbered after
 								 * pullup (set only if target_rte->lateral) */
+	Relids		lowest_nullable_relids;	/* relids of the nullable side of the
+										 * lowest outer join subquery is within
+										 * (set only if target_rte->lateral) */
 	bool	   *outer_hasSubLinks;	/* -> outer query's hasSubLinks */
 	int			varno;			/* varno of subquery */
 	bool		wrap_non_vars;	/* do we need all non-Var outputs to be PHVs? */
@@ -81,10 +84,12 @@ static Node *pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
 										   Node **jtlink2, Relids available_rels2);
 static Node *pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 										JoinExpr *lowest_outer_join,
+										Node *lowest_nullable_side,
 										AppendRelInfo *containing_appendrel);
 static Node *pull_up_simple_subquery(PlannerInfo *root, Node *jtnode,
 									 RangeTblEntry *rte,
 									 JoinExpr *lowest_outer_join,
+									 Node *lowest_nullable_side,
 									 AppendRelInfo *containing_appendrel);
 static Node *pull_up_simple_union_all(PlannerInfo *root, Node *jtnode,
 									  RangeTblEntry *rte);
@@ -772,7 +777,7 @@ pull_up_subqueries(PlannerInfo *root)
 	/* Recursion starts with no containing join nor appendrel */
 	root->parse->jointree = (FromExpr *)
 		pull_up_subqueries_recurse(root, (Node *) root->parse->jointree,
-								   NULL, NULL);
+								   NULL, NULL, NULL);
 	/* We should still have a FromExpr */
 	Assert(IsA(root->parse->jointree, FromExpr));
 }
@@ -787,6 +792,13 @@ pull_up_subqueries(PlannerInfo *root)
  * lowest_outer_join references the lowest such JoinExpr node; otherwise
  * it is NULL.  We use this to constrain the effects of LATERAL subqueries.
  *
+ * If this jointree node is within the nullable side of an outer join, then
+ * lowest_nullable_side references the nullable side of the lowest such
+ * JoinExpr node; otherwise it is NULL.  We use this to avoid use of the
+ * PlaceHolderVar mechanism for simple Vars that are lateral references to
+ * something outside the subquery being pulled up but the referenced rel is
+ * under the same lowest nulling outer join.
+ *
  * If we are looking at a member subquery of an append relation,
  * containing_appendrel describes that relation; else it is NULL.
  * This forces use of the PlaceHolderVar mechanism for all non-Var targetlist
@@ -803,14 +815,15 @@ pull_up_subqueries(PlannerInfo *root)
  * Notice also that we can't turn pullup_replace_vars loose on the whole
  * jointree, because it'd return a mutated copy of the tree; we have to
  * invoke it just on the quals, instead.  This behavior is what makes it
- * reasonable to pass lowest_outer_join as a pointer rather than some
- * more-indirect way of identifying the lowest OJ.  Likewise, we don't
- * replace append_rel_list members but only their substructure, so the
- * containing_appendrel reference is safe to use.
+ * reasonable to pass lowest_outer_join and lowest_nullable_side as a
+ * pointer rather than some more-indirect way of identifying the lowest OJ.
+ * Likewise, we don't replace append_rel_list members but only their
+ * substructure, so the containing_appendrel reference is safe to use.
  */
 static Node *
 pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 						   JoinExpr *lowest_outer_join,
+						   Node *lowest_nullable_side,
 						   AppendRelInfo *containing_appendrel)
 {
 	/* Since this function recurses, it could be driven to stack overflow. */
@@ -837,6 +850,7 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 			 is_safe_append_member(rte->subquery)))
 			return pull_up_simple_subquery(root, jtnode, rte,
 										   lowest_outer_join,
+										   lowest_nullable_side,
 										   containing_appendrel);
 
 		/*
@@ -884,6 +898,7 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 		{
 			lfirst(l) = pull_up_subqueries_recurse(root, lfirst(l),
 												   lowest_outer_join,
+												   lowest_nullable_side,
 												   NULL);
 		}
 	}
@@ -898,9 +913,11 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 			case JOIN_INNER:
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 lowest_outer_join,
+													 lowest_nullable_side,
 													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 lowest_outer_join,
+													 lowest_nullable_side,
 													 NULL);
 				break;
 			case JOIN_LEFT:
@@ -908,25 +925,31 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 			case JOIN_ANTI:
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 j,
+													 lowest_nullable_side,
 													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 j,
+													 j->rarg,
 													 NULL);
 				break;
 			case JOIN_FULL:
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 j,
+													 j->larg,
 													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 j,
+													 j->rarg,
 													 NULL);
 				break;
 			case JOIN_RIGHT:
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 j,
+													 j->larg,
 													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 j,
+													 lowest_nullable_side,
 													 NULL);
 				break;
 			default:
@@ -956,6 +979,7 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 static Node *
 pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 						JoinExpr *lowest_outer_join,
+						Node *lowest_nullable_side,
 						AppendRelInfo *containing_appendrel)
 {
 	Query	   *parse = root->parse;
@@ -1115,10 +1139,20 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 	rvcontext.targetlist = subquery->targetList;
 	rvcontext.target_rte = rte;
 	if (rte->lateral)
+	{
 		rvcontext.relids = get_relids_in_jointree((Node *) subquery->jointree,
 												  true, true);
+		rvcontext.lowest_nullable_relids =
+			lowest_nullable_side ?
+			get_relids_in_jointree(lowest_nullable_side,
+								   true,
+								   true) : NULL;
+	}
 	else						/* won't need relids */
+	{
 		rvcontext.relids = NULL;
+		rvcontext.lowest_nullable_relids = NULL;
+	}
 	rvcontext.outer_hasSubLinks = &parse->hasSubLinks;
 	rvcontext.varno = varno;
 	/* this flag will be set below, if needed */
@@ -1418,7 +1452,7 @@ pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root, int parentRTindex,
 		rtr = makeNode(RangeTblRef);
 		rtr->rtindex = childRTindex;
 		(void) pull_up_subqueries_recurse(root, (Node *) rtr,
-										  NULL, appinfo);
+										  NULL, NULL, appinfo);
 	}
 	else if (IsA(setOp, SetOperationStmt))
 	{
@@ -2422,12 +2456,11 @@ pullup_replace_vars_callback(Var *var,
 				/*
 				 * Simple Vars always escape being wrapped, unless they are
 				 * lateral references to something outside the subquery being
-				 * pulled up.  (Even then, we could omit the PlaceHolderVar if
-				 * the referenced rel is under the same lowest outer join, but
-				 * it doesn't seem worth the trouble to check that.)
+				 * pulled up and is not under the same lowest outer join.
 				 */
 				if (rcon->target_rte->lateral &&
-					!bms_is_member(((Var *) newnode)->varno, rcon->relids))
+					!bms_is_member(((Var *) newnode)->varno, rcon->relids) &&
+					!bms_is_member(((Var *) newnode)->varno, rcon->lowest_nullable_relids))
 					wrap = true;
 				else
 					wrap = false;
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 9b8638f286..1db755baa6 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -6766,6 +6766,64 @@ select * from
  4567890123456789 | -4567890123456789 |                  |                   |                 
 (10 rows)
 
+-- lateral reference to simple Var can escape PlaceHolderVar if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)
+select * from
+  int8_tbl a left join
+  (int8_tbl b inner join
+   lateral (select *, b.q2 as x from int8_tbl c) ss on b.q2 = ss.q1)
+  on a.q1 = b.q1;
+                     QUERY PLAN                     
+----------------------------------------------------
+ Hash Right Join
+   Output: a.q1, a.q2, b.q1, b.q2, c.q1, c.q2, b.q2
+   Hash Cond: (b.q1 = a.q1)
+   ->  Hash Join
+         Output: b.q1, b.q2, c.q1, c.q2
+         Hash Cond: (b.q2 = c.q1)
+         ->  Seq Scan on public.int8_tbl b
+               Output: b.q1, b.q2
+         ->  Hash
+               Output: c.q1, c.q2
+               ->  Seq Scan on public.int8_tbl c
+                     Output: c.q1, c.q2
+   ->  Hash
+         Output: a.q1, a.q2
+         ->  Seq Scan on public.int8_tbl a
+               Output: a.q1, a.q2
+(16 rows)
+
+select * from
+  int8_tbl a left join
+  (int8_tbl b inner join
+   lateral (select *, b.q2 as x from int8_tbl c) ss on b.q2 = ss.q1)
+  on a.q1 = b.q1;
+        q1        |        q2         |        q1        |        q2        |        q1        |        q2         |        x         
+------------------+-------------------+------------------+------------------+------------------+-------------------+------------------
+              123 |  4567890123456789 |              123 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+              123 |               456 |              123 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+              123 |  4567890123456789 |              123 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+              123 |               456 |              123 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+              123 |  4567890123456789 |              123 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+              123 |               456 |              123 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+ 4567890123456789 | -4567890123456789 | 4567890123456789 |              123 |              123 |  4567890123456789 |              123
+ 4567890123456789 |  4567890123456789 | 4567890123456789 |              123 |              123 |  4567890123456789 |              123
+ 4567890123456789 |               123 | 4567890123456789 |              123 |              123 |  4567890123456789 |              123
+ 4567890123456789 | -4567890123456789 | 4567890123456789 |              123 |              123 |               456 |              123
+ 4567890123456789 |  4567890123456789 | 4567890123456789 |              123 |              123 |               456 |              123
+ 4567890123456789 |               123 | 4567890123456789 |              123 |              123 |               456 |              123
+ 4567890123456789 | -4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+ 4567890123456789 |  4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+ 4567890123456789 |               123 | 4567890123456789 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+ 4567890123456789 | -4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+ 4567890123456789 |  4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+ 4567890123456789 |               123 | 4567890123456789 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+ 4567890123456789 | -4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+ 4567890123456789 |  4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+ 4567890123456789 |               123 | 4567890123456789 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+(21 rows)
+
 -- lateral can result in join conditions appearing below their
 -- real semantic level
 explain (verbose, costs off)
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 3e5032b04d..48dd805586 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -2464,6 +2464,20 @@ select * from
   int8_tbl a left join
   lateral (select *, coalesce(a.q2, 42) as x from int8_tbl b) ss on a.q2 = ss.q1;
 
+-- lateral reference to simple Var can escape PlaceHolderVar if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)
+select * from
+  int8_tbl a left join
+  (int8_tbl b inner join
+   lateral (select *, b.q2 as x from int8_tbl c) ss on b.q2 = ss.q1)
+  on a.q1 = b.q1;
+select * from
+  int8_tbl a left join
+  (int8_tbl b inner join
+   lateral (select *, b.q2 as x from int8_tbl c) ss on b.q2 = ss.q1)
+  on a.q1 = b.q1;
+
 -- lateral can result in join conditions appearing below their
 -- real semantic level
 explain (verbose, costs off)
-- 
2.31.0

From 2a464803a523660cfec6715f46ced9548bac0105 Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Thu, 11 May 2023 17:54:26 +0800
Subject: [PATCH v3] Avoid unnecessary PlaceHolderVars for Vars/PHVs

When we pull up a lateral subquery, if a Var/PHV in subquery's
targetlist is lateral reference to something outside the subquery being
pulled up, usually we need to wrap it in a PlaceHolderVar.  But if the
referenced rel is under the same lowest nulling outer join, we can omit
the PlaceHolderVar.

This patch checks that and avoids unnecessary PHVs.  This could be
beneficial because such PHVs imply lateral dependencies which makes us
have to use nestloop.
---
 src/backend/optimizer/prep/prepjointree.c |  58 ++++++++--
 src/test/regress/expected/join.out        | 128 ++++++++++++++++++++++
 src/test/regress/sql/join.sql             |  30 +++++
 3 files changed, 205 insertions(+), 11 deletions(-)

diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index aa83dd3636..83d762510a 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -49,6 +49,9 @@ typedef struct pullup_replace_vars_context
 	RangeTblEntry *target_rte;	/* RTE of subquery */
 	Relids		relids;			/* relids within subquery, as numbered after
 								 * pullup (set only if target_rte->lateral) */
+	Relids		lowest_nullable_relids;	/* relids of the nullable side of the
+										 * lowest outer join subquery is within
+										 * (set only if target_rte->lateral) */
 	bool	   *outer_hasSubLinks;	/* -> outer query's hasSubLinks */
 	int			varno;			/* varno of subquery */
 	bool		wrap_non_vars;	/* do we need all non-Var outputs to be PHVs? */
@@ -81,10 +84,12 @@ static Node *pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
 										   Node **jtlink2, Relids available_rels2);
 static Node *pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 										JoinExpr *lowest_outer_join,
+										Node *lowest_nullable_side,
 										AppendRelInfo *containing_appendrel);
 static Node *pull_up_simple_subquery(PlannerInfo *root, Node *jtnode,
 									 RangeTblEntry *rte,
 									 JoinExpr *lowest_outer_join,
+									 Node *lowest_nullable_side,
 									 AppendRelInfo *containing_appendrel);
 static Node *pull_up_simple_union_all(PlannerInfo *root, Node *jtnode,
 									  RangeTblEntry *rte);
@@ -772,7 +777,7 @@ pull_up_subqueries(PlannerInfo *root)
 	/* Recursion starts with no containing join nor appendrel */
 	root->parse->jointree = (FromExpr *)
 		pull_up_subqueries_recurse(root, (Node *) root->parse->jointree,
-								   NULL, NULL);
+								   NULL, NULL, NULL);
 	/* We should still have a FromExpr */
 	Assert(IsA(root->parse->jointree, FromExpr));
 }
@@ -787,6 +792,13 @@ pull_up_subqueries(PlannerInfo *root)
  * lowest_outer_join references the lowest such JoinExpr node; otherwise
  * it is NULL.  We use this to constrain the effects of LATERAL subqueries.
  *
+ * If this jointree node is within the nullable side of an outer join, then
+ * lowest_nullable_side references the nullable side of the lowest such
+ * JoinExpr node; otherwise it is NULL.  We use this to avoid use of the
+ * PlaceHolderVar mechanism for Vars/PHVs that are lateral references to
+ * something outside the subquery being pulled up but the referenced rel is
+ * under the same lowest nulling outer join.
+ *
  * If we are looking at a member subquery of an append relation,
  * containing_appendrel describes that relation; else it is NULL.
  * This forces use of the PlaceHolderVar mechanism for all non-Var targetlist
@@ -803,14 +815,15 @@ pull_up_subqueries(PlannerInfo *root)
  * Notice also that we can't turn pullup_replace_vars loose on the whole
  * jointree, because it'd return a mutated copy of the tree; we have to
  * invoke it just on the quals, instead.  This behavior is what makes it
- * reasonable to pass lowest_outer_join as a pointer rather than some
- * more-indirect way of identifying the lowest OJ.  Likewise, we don't
- * replace append_rel_list members but only their substructure, so the
- * containing_appendrel reference is safe to use.
+ * reasonable to pass lowest_outer_join and lowest_nullable_side as a
+ * pointer rather than some more-indirect way of identifying the lowest OJ.
+ * Likewise, we don't replace append_rel_list members but only their
+ * substructure, so the containing_appendrel reference is safe to use.
  */
 static Node *
 pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 						   JoinExpr *lowest_outer_join,
+						   Node *lowest_nullable_side,
 						   AppendRelInfo *containing_appendrel)
 {
 	/* Since this function recurses, it could be driven to stack overflow. */
@@ -837,6 +850,7 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 			 is_safe_append_member(rte->subquery)))
 			return pull_up_simple_subquery(root, jtnode, rte,
 										   lowest_outer_join,
+										   lowest_nullable_side,
 										   containing_appendrel);
 
 		/*
@@ -884,6 +898,7 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 		{
 			lfirst(l) = pull_up_subqueries_recurse(root, lfirst(l),
 												   lowest_outer_join,
+												   lowest_nullable_side,
 												   NULL);
 		}
 	}
@@ -898,9 +913,11 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 			case JOIN_INNER:
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 lowest_outer_join,
+													 lowest_nullable_side,
 													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 lowest_outer_join,
+													 lowest_nullable_side,
 													 NULL);
 				break;
 			case JOIN_LEFT:
@@ -908,25 +925,31 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 			case JOIN_ANTI:
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 j,
+													 lowest_nullable_side,
 													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 j,
+													 j->rarg,
 													 NULL);
 				break;
 			case JOIN_FULL:
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 j,
+													 j->larg,
 													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 j,
+													 j->rarg,
 													 NULL);
 				break;
 			case JOIN_RIGHT:
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 j,
+													 j->larg,
 													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 j,
+													 lowest_nullable_side,
 													 NULL);
 				break;
 			default:
@@ -956,6 +979,7 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 static Node *
 pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 						JoinExpr *lowest_outer_join,
+						Node *lowest_nullable_side,
 						AppendRelInfo *containing_appendrel)
 {
 	Query	   *parse = root->parse;
@@ -1115,10 +1139,20 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 	rvcontext.targetlist = subquery->targetList;
 	rvcontext.target_rte = rte;
 	if (rte->lateral)
+	{
 		rvcontext.relids = get_relids_in_jointree((Node *) subquery->jointree,
 												  true, true);
+		rvcontext.lowest_nullable_relids =
+			lowest_nullable_side ?
+			get_relids_in_jointree(lowest_nullable_side,
+								   true,
+								   true) : NULL;
+	}
 	else						/* won't need relids */
+	{
 		rvcontext.relids = NULL;
+		rvcontext.lowest_nullable_relids = NULL;
+	}
 	rvcontext.outer_hasSubLinks = &parse->hasSubLinks;
 	rvcontext.varno = varno;
 	/* this flag will be set below, if needed */
@@ -1418,7 +1452,7 @@ pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root, int parentRTindex,
 		rtr = makeNode(RangeTblRef);
 		rtr->rtindex = childRTindex;
 		(void) pull_up_subqueries_recurse(root, (Node *) rtr,
-										  NULL, appinfo);
+										  NULL, NULL, appinfo);
 	}
 	else if (IsA(setOp, SetOperationStmt))
 	{
@@ -2422,12 +2456,12 @@ pullup_replace_vars_callback(Var *var,
 				/*
 				 * Simple Vars always escape being wrapped, unless they are
 				 * lateral references to something outside the subquery being
-				 * pulled up.  (Even then, we could omit the PlaceHolderVar if
-				 * the referenced rel is under the same lowest outer join, but
-				 * it doesn't seem worth the trouble to check that.)
+				 * pulled up and is not under the same lowest outer join.
 				 */
 				if (rcon->target_rte->lateral &&
-					!bms_is_member(((Var *) newnode)->varno, rcon->relids))
+					!bms_is_member(((Var *) newnode)->varno, rcon->relids) &&
+					!bms_is_member(((Var *) newnode)->varno,
+								   rcon->lowest_nullable_relids))
 					wrap = true;
 				else
 					wrap = false;
@@ -2438,7 +2472,9 @@ pullup_replace_vars_callback(Var *var,
 				/* The same rules apply for a PlaceHolderVar */
 				if (rcon->target_rte->lateral &&
 					!bms_is_subset(((PlaceHolderVar *) newnode)->phrels,
-								   rcon->relids))
+								   rcon->relids) &&
+					!bms_is_subset(((PlaceHolderVar *) newnode)->phrels,
+								   rcon->lowest_nullable_relids))
 					wrap = true;
 				else
 					wrap = false;
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index e0418a3ae7..8719b167f3 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -7759,6 +7759,134 @@ select * from
  4567890123456789 | -4567890123456789 |                  |                   |                 
 (10 rows)
 
+-- lateral reference to simple Var can escape PlaceHolderVar if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)
+select * from
+  int8_tbl a left join
+  (int8_tbl b inner join
+   lateral (select *, b.q2 as x from int8_tbl c) ss on b.q2 = ss.q1)
+  on a.q1 = b.q1;
+                     QUERY PLAN                     
+----------------------------------------------------
+ Hash Right Join
+   Output: a.q1, a.q2, b.q1, b.q2, c.q1, c.q2, b.q2
+   Hash Cond: (b.q1 = a.q1)
+   ->  Hash Join
+         Output: b.q1, b.q2, c.q1, c.q2
+         Hash Cond: (b.q2 = c.q1)
+         ->  Seq Scan on public.int8_tbl b
+               Output: b.q1, b.q2
+         ->  Hash
+               Output: c.q1, c.q2
+               ->  Seq Scan on public.int8_tbl c
+                     Output: c.q1, c.q2
+   ->  Hash
+         Output: a.q1, a.q2
+         ->  Seq Scan on public.int8_tbl a
+               Output: a.q1, a.q2
+(16 rows)
+
+select * from
+  int8_tbl a left join
+  (int8_tbl b inner join
+   lateral (select *, b.q2 as x from int8_tbl c) ss on b.q2 = ss.q1)
+  on a.q1 = b.q1;
+        q1        |        q2         |        q1        |        q2        |        q1        |        q2         |        x         
+------------------+-------------------+------------------+------------------+------------------+-------------------+------------------
+              123 |  4567890123456789 |              123 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+              123 |               456 |              123 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+              123 |  4567890123456789 |              123 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+              123 |               456 |              123 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+              123 |  4567890123456789 |              123 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+              123 |               456 |              123 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+ 4567890123456789 | -4567890123456789 | 4567890123456789 |              123 |              123 |  4567890123456789 |              123
+ 4567890123456789 |  4567890123456789 | 4567890123456789 |              123 |              123 |  4567890123456789 |              123
+ 4567890123456789 |               123 | 4567890123456789 |              123 |              123 |  4567890123456789 |              123
+ 4567890123456789 | -4567890123456789 | 4567890123456789 |              123 |              123 |               456 |              123
+ 4567890123456789 |  4567890123456789 | 4567890123456789 |              123 |              123 |               456 |              123
+ 4567890123456789 |               123 | 4567890123456789 |              123 |              123 |               456 |              123
+ 4567890123456789 | -4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+ 4567890123456789 |  4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+ 4567890123456789 |               123 | 4567890123456789 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+ 4567890123456789 | -4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+ 4567890123456789 |  4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+ 4567890123456789 |               123 | 4567890123456789 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+ 4567890123456789 | -4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+ 4567890123456789 |  4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+ 4567890123456789 |               123 | 4567890123456789 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+(21 rows)
+
+-- lateral reference to PHV can also escape PlaceHolderVar if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)
+select ss2.* from
+  int8_tbl a left join
+  (int8_tbl b left join
+   (select coalesce(q1) as x, * from int8_tbl c) ss1 on b.q1 = ss1.q2 inner join
+   lateral (select ss1.x as y, * from int8_tbl d) ss2 on b.q2 = ss2.q1)
+  on a.q2 = ss2.q1;
+                       QUERY PLAN                       
+--------------------------------------------------------
+ Hash Right Join
+   Output: (COALESCE(c.q1)), d.q1, d.q2
+   Hash Cond: (d.q1 = a.q2)
+   ->  Hash Join
+         Output: (COALESCE(c.q1)), d.q1, d.q2
+         Hash Cond: (b.q2 = d.q1)
+         ->  Hash Left Join
+               Output: b.q2, (COALESCE(c.q1))
+               Hash Cond: (b.q1 = c.q2)
+               ->  Seq Scan on public.int8_tbl b
+                     Output: b.q1, b.q2
+               ->  Hash
+                     Output: c.q2, (COALESCE(c.q1))
+                     ->  Seq Scan on public.int8_tbl c
+                           Output: c.q2, COALESCE(c.q1)
+         ->  Hash
+               Output: d.q1, d.q2
+               ->  Seq Scan on public.int8_tbl d
+                     Output: d.q1, d.q2
+   ->  Hash
+         Output: a.q2
+         ->  Seq Scan on public.int8_tbl a
+               Output: a.q2
+(23 rows)
+
+select ss2.* from
+  int8_tbl a left join
+  (int8_tbl b left join
+   (select coalesce(q1) as x, * from int8_tbl c) ss1 on b.q1 = ss1.q2 inner join
+   lateral (select ss1.x as y, * from int8_tbl d) ss2 on b.q2 = ss2.q1)
+  on a.q2 = ss2.q1;
+        y         |        q1        |        q2         
+------------------+------------------+-------------------
+ 4567890123456789 | 4567890123456789 | -4567890123456789
+ 4567890123456789 | 4567890123456789 | -4567890123456789
+ 4567890123456789 | 4567890123456789 |  4567890123456789
+ 4567890123456789 | 4567890123456789 |  4567890123456789
+ 4567890123456789 | 4567890123456789 |               123
+ 4567890123456789 | 4567890123456789 |               123
+ 4567890123456789 |              123 |  4567890123456789
+ 4567890123456789 |              123 |               456
+              123 |              123 |  4567890123456789
+              123 |              123 |               456
+ 4567890123456789 | 4567890123456789 | -4567890123456789
+ 4567890123456789 | 4567890123456789 | -4567890123456789
+ 4567890123456789 | 4567890123456789 |  4567890123456789
+ 4567890123456789 | 4567890123456789 |  4567890123456789
+ 4567890123456789 | 4567890123456789 |               123
+ 4567890123456789 | 4567890123456789 |               123
+              123 | 4567890123456789 | -4567890123456789
+              123 | 4567890123456789 | -4567890123456789
+              123 | 4567890123456789 |  4567890123456789
+              123 | 4567890123456789 |  4567890123456789
+              123 | 4567890123456789 |               123
+              123 | 4567890123456789 |               123
+                  |                  |                  
+                  |                  |                  
+(24 rows)
+
 -- lateral can result in join conditions appearing below their
 -- real semantic level
 explain (verbose, costs off)
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index e272ff5c14..0edd62e76b 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -2904,6 +2904,36 @@ select * from
   int8_tbl a left join
   lateral (select *, coalesce(a.q2, 42) as x from int8_tbl b) ss on a.q2 = ss.q1;
 
+-- lateral reference to simple Var can escape PlaceHolderVar if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)
+select * from
+  int8_tbl a left join
+  (int8_tbl b inner join
+   lateral (select *, b.q2 as x from int8_tbl c) ss on b.q2 = ss.q1)
+  on a.q1 = b.q1;
+select * from
+  int8_tbl a left join
+  (int8_tbl b inner join
+   lateral (select *, b.q2 as x from int8_tbl c) ss on b.q2 = ss.q1)
+  on a.q1 = b.q1;
+
+-- lateral reference to PHV can also escape PlaceHolderVar if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)
+select ss2.* from
+  int8_tbl a left join
+  (int8_tbl b left join
+   (select coalesce(q1) as x, * from int8_tbl c) ss1 on b.q1 = ss1.q2 inner join
+   lateral (select ss1.x as y, * from int8_tbl d) ss2 on b.q2 = ss2.q1)
+  on a.q2 = ss2.q1;
+select ss2.* from
+  int8_tbl a left join
+  (int8_tbl b left join
+   (select coalesce(q1) as x, * from int8_tbl c) ss1 on b.q1 = ss1.q2 inner join
+   lateral (select ss1.x as y, * from int8_tbl d) ss2 on b.q2 = ss2.q1)
+  on a.q2 = ss2.q1;
+
 -- lateral can result in join conditions appearing below their
 -- real semantic level
 explain (verbose, costs off)
-- 
2.31.0

From e5d2f55b263e92c71af3388a44bd8f8472e820e7 Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Thu, 20 Jun 2024 16:48:01 +0900
Subject: [PATCH v4] Avoid unnecessary wrapping for Vars and PHVs

When pulling up a lateral subquery that is underneath an outer join, the
current code always wraps a Var or PHV in the subquery's targetlist into
a new PlaceHolderVar if it is a lateral reference to something outside
the subquery.  This is necessary when the Var/PHV references the
non-nullable side of the outer join from the nullable side: we need to
ensure that it is evaluated at the right place and hence is forced to
null when the outer join should do so.  However, if the referenced rel
is under the same lowest nulling outer join, we can actually omit the
wrapping.  It could be beneficial to get rid of such PHVs because they
imply lateral dependencies, which force us to resort to nestloop joins.

This patch implements this optimization by remembering the relids of the
nullable side of the lowest outer join the subquery is within, and
subsequently checking whether the referenced rel is under the same
lowest nulling outer join.
---
 src/backend/optimizer/prep/prepjointree.c |  59 ++++++++--
 src/test/regress/expected/join.out        | 128 ++++++++++++++++++++++
 src/test/regress/sql/join.sql             |  30 +++++
 3 files changed, 206 insertions(+), 11 deletions(-)

diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 5482ab85a7..b37566e0b0 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -49,6 +49,9 @@ typedef struct pullup_replace_vars_context
 	RangeTblEntry *target_rte;	/* RTE of subquery */
 	Relids		relids;			/* relids within subquery, as numbered after
 								 * pullup (set only if target_rte->lateral) */
+	Relids		lowest_nullable_relids;	/* relids of the nullable side of the
+										 * lowest outer join subquery is within
+										 * (set only if target_rte->lateral) */
 	bool	   *outer_hasSubLinks;	/* -> outer query's hasSubLinks */
 	int			varno;			/* varno of subquery */
 	bool		wrap_non_vars;	/* do we need all non-Var outputs to be PHVs? */
@@ -81,10 +84,12 @@ static Node *pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
 										   Node **jtlink2, Relids available_rels2);
 static Node *pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 										JoinExpr *lowest_outer_join,
+										Node *lowest_nullable_side,
 										AppendRelInfo *containing_appendrel);
 static Node *pull_up_simple_subquery(PlannerInfo *root, Node *jtnode,
 									 RangeTblEntry *rte,
 									 JoinExpr *lowest_outer_join,
+									 Node *lowest_nullable_side,
 									 AppendRelInfo *containing_appendrel);
 static Node *pull_up_simple_union_all(PlannerInfo *root, Node *jtnode,
 									  RangeTblEntry *rte);
@@ -821,7 +826,7 @@ pull_up_subqueries(PlannerInfo *root)
 	/* Recursion starts with no containing join nor appendrel */
 	root->parse->jointree = (FromExpr *)
 		pull_up_subqueries_recurse(root, (Node *) root->parse->jointree,
-								   NULL, NULL);
+								   NULL, NULL, NULL);
 	/* We should still have a FromExpr */
 	Assert(IsA(root->parse->jointree, FromExpr));
 }
@@ -836,6 +841,13 @@ pull_up_subqueries(PlannerInfo *root)
  * lowest_outer_join references the lowest such JoinExpr node; otherwise
  * it is NULL.  We use this to constrain the effects of LATERAL subqueries.
  *
+ * If this jointree node is within the nullable side of an outer join, then
+ * lowest_nullable_side references the nullable side of the lowest such
+ * JoinExpr node; otherwise it is NULL.  We use this to avoid use of the
+ * PlaceHolderVar mechanism for Vars/PHVs that are lateral references to
+ * something outside the subquery being pulled up but the referenced rel is
+ * under the same lowest nulling outer join.
+ *
  * If we are looking at a member subquery of an append relation,
  * containing_appendrel describes that relation; else it is NULL.
  * This forces use of the PlaceHolderVar mechanism for all non-Var targetlist
@@ -852,14 +864,15 @@ pull_up_subqueries(PlannerInfo *root)
  * Notice also that we can't turn pullup_replace_vars loose on the whole
  * jointree, because it'd return a mutated copy of the tree; we have to
  * invoke it just on the quals, instead.  This behavior is what makes it
- * reasonable to pass lowest_outer_join as a pointer rather than some
- * more-indirect way of identifying the lowest OJ.  Likewise, we don't
- * replace append_rel_list members but only their substructure, so the
- * containing_appendrel reference is safe to use.
+ * reasonable to pass lowest_outer_join and lowest_nullable_side as a
+ * pointer rather than some more-indirect way of identifying the lowest OJ.
+ * Likewise, we don't replace append_rel_list members but only their
+ * substructure, so the containing_appendrel reference is safe to use.
  */
 static Node *
 pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 						   JoinExpr *lowest_outer_join,
+						   Node *lowest_nullable_side,
 						   AppendRelInfo *containing_appendrel)
 {
 	/* Since this function recurses, it could be driven to stack overflow. */
@@ -886,6 +899,7 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 			 is_safe_append_member(rte->subquery)))
 			return pull_up_simple_subquery(root, jtnode, rte,
 										   lowest_outer_join,
+										   lowest_nullable_side,
 										   containing_appendrel);
 
 		/*
@@ -933,6 +947,7 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 		{
 			lfirst(l) = pull_up_subqueries_recurse(root, lfirst(l),
 												   lowest_outer_join,
+												   lowest_nullable_side,
 												   NULL);
 		}
 	}
@@ -947,9 +962,11 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 			case JOIN_INNER:
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 lowest_outer_join,
+													 lowest_nullable_side,
 													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 lowest_outer_join,
+													 lowest_nullable_side,
 													 NULL);
 				break;
 			case JOIN_LEFT:
@@ -957,25 +974,31 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 			case JOIN_ANTI:
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 j,
+													 lowest_nullable_side,
 													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 j,
+													 j->rarg,
 													 NULL);
 				break;
 			case JOIN_FULL:
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 j,
+													 j->larg,
 													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 j,
+													 j->rarg,
 													 NULL);
 				break;
 			case JOIN_RIGHT:
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 j,
+													 j->larg,
 													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 j,
+													 lowest_nullable_side,
 													 NULL);
 				break;
 			default:
@@ -1005,6 +1028,7 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 static Node *
 pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 						JoinExpr *lowest_outer_join,
+						Node *lowest_nullable_side,
 						AppendRelInfo *containing_appendrel)
 {
 	Query	   *parse = root->parse;
@@ -1164,10 +1188,20 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 	rvcontext.targetlist = subquery->targetList;
 	rvcontext.target_rte = rte;
 	if (rte->lateral)
+	{
 		rvcontext.relids = get_relids_in_jointree((Node *) subquery->jointree,
 												  true, true);
+		rvcontext.lowest_nullable_relids =
+			lowest_nullable_side ?
+			get_relids_in_jointree(lowest_nullable_side,
+								   true,
+								   true) : NULL;
+	}
 	else						/* won't need relids */
+	{
 		rvcontext.relids = NULL;
+		rvcontext.lowest_nullable_relids = NULL;
+	}
 	rvcontext.outer_hasSubLinks = &parse->hasSubLinks;
 	rvcontext.varno = varno;
 	/* this flag will be set below, if needed */
@@ -1467,7 +1501,7 @@ pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root, int parentRTindex,
 		rtr = makeNode(RangeTblRef);
 		rtr->rtindex = childRTindex;
 		(void) pull_up_subqueries_recurse(root, (Node *) rtr,
-										  NULL, appinfo);
+										  NULL, NULL, appinfo);
 	}
 	else if (IsA(setOp, SetOperationStmt))
 	{
@@ -2469,12 +2503,13 @@ pullup_replace_vars_callback(Var *var,
 				/*
 				 * Simple Vars always escape being wrapped, unless they are
 				 * lateral references to something outside the subquery being
-				 * pulled up.  (Even then, we could omit the PlaceHolderVar if
-				 * the referenced rel is under the same lowest outer join, but
-				 * it doesn't seem worth the trouble to check that.)
+				 * pulled up and the referenced rel is not under the same
+				 * lowest outer join.
 				 */
 				if (rcon->target_rte->lateral &&
-					!bms_is_member(((Var *) newnode)->varno, rcon->relids))
+					!bms_is_member(((Var *) newnode)->varno, rcon->relids) &&
+					!bms_is_member(((Var *) newnode)->varno,
+								   rcon->lowest_nullable_relids))
 					wrap = true;
 				else
 					wrap = false;
@@ -2485,7 +2520,9 @@ pullup_replace_vars_callback(Var *var,
 				/* The same rules apply for a PlaceHolderVar */
 				if (rcon->target_rte->lateral &&
 					!bms_is_subset(((PlaceHolderVar *) newnode)->phrels,
-								   rcon->relids))
+								   rcon->relids) &&
+					!bms_is_subset(((PlaceHolderVar *) newnode)->phrels,
+								   rcon->lowest_nullable_relids))
 					wrap = true;
 				else
 					wrap = false;
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 6b16c3a676..650e84de47 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -6790,6 +6790,134 @@ select * from
  4567890123456789 | -4567890123456789 |                  |                   |                 
 (10 rows)
 
+-- lateral references for simple Vars can escape being wrapped if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)
+select * from
+  int8_tbl a left join
+  (int8_tbl b inner join
+   lateral (select *, b.q2 as x from int8_tbl c) ss on b.q2 = ss.q1)
+  on a.q1 = b.q1;
+                     QUERY PLAN                     
+----------------------------------------------------
+ Hash Right Join
+   Output: a.q1, a.q2, b.q1, b.q2, c.q1, c.q2, b.q2
+   Hash Cond: (b.q1 = a.q1)
+   ->  Hash Join
+         Output: b.q1, b.q2, c.q1, c.q2
+         Hash Cond: (b.q2 = c.q1)
+         ->  Seq Scan on public.int8_tbl b
+               Output: b.q1, b.q2
+         ->  Hash
+               Output: c.q1, c.q2
+               ->  Seq Scan on public.int8_tbl c
+                     Output: c.q1, c.q2
+   ->  Hash
+         Output: a.q1, a.q2
+         ->  Seq Scan on public.int8_tbl a
+               Output: a.q1, a.q2
+(16 rows)
+
+select * from
+  int8_tbl a left join
+  (int8_tbl b inner join
+   lateral (select *, b.q2 as x from int8_tbl c) ss on b.q2 = ss.q1)
+  on a.q1 = b.q1;
+        q1        |        q2         |        q1        |        q2        |        q1        |        q2         |        x         
+------------------+-------------------+------------------+------------------+------------------+-------------------+------------------
+              123 |  4567890123456789 |              123 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+              123 |               456 |              123 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+              123 |  4567890123456789 |              123 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+              123 |               456 |              123 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+              123 |  4567890123456789 |              123 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+              123 |               456 |              123 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+ 4567890123456789 | -4567890123456789 | 4567890123456789 |              123 |              123 |  4567890123456789 |              123
+ 4567890123456789 |  4567890123456789 | 4567890123456789 |              123 |              123 |  4567890123456789 |              123
+ 4567890123456789 |               123 | 4567890123456789 |              123 |              123 |  4567890123456789 |              123
+ 4567890123456789 | -4567890123456789 | 4567890123456789 |              123 |              123 |               456 |              123
+ 4567890123456789 |  4567890123456789 | 4567890123456789 |              123 |              123 |               456 |              123
+ 4567890123456789 |               123 | 4567890123456789 |              123 |              123 |               456 |              123
+ 4567890123456789 | -4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+ 4567890123456789 |  4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+ 4567890123456789 |               123 | 4567890123456789 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+ 4567890123456789 | -4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+ 4567890123456789 |  4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+ 4567890123456789 |               123 | 4567890123456789 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+ 4567890123456789 | -4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+ 4567890123456789 |  4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+ 4567890123456789 |               123 | 4567890123456789 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+(21 rows)
+
+-- lateral references for PHVs can also escape being wrapped if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)
+select ss2.* from
+  int8_tbl a left join
+  (int8_tbl b left join
+   (select coalesce(q1) as x, * from int8_tbl c) ss1 on b.q1 = ss1.q2 inner join
+   lateral (select ss1.x as y, * from int8_tbl d) ss2 on b.q2 = ss2.q1)
+  on a.q2 = ss2.q1;
+                       QUERY PLAN                       
+--------------------------------------------------------
+ Hash Right Join
+   Output: (COALESCE(c.q1)), d.q1, d.q2
+   Hash Cond: (d.q1 = a.q2)
+   ->  Hash Join
+         Output: (COALESCE(c.q1)), d.q1, d.q2
+         Hash Cond: (b.q2 = d.q1)
+         ->  Hash Left Join
+               Output: b.q2, (COALESCE(c.q1))
+               Hash Cond: (b.q1 = c.q2)
+               ->  Seq Scan on public.int8_tbl b
+                     Output: b.q1, b.q2
+               ->  Hash
+                     Output: c.q2, (COALESCE(c.q1))
+                     ->  Seq Scan on public.int8_tbl c
+                           Output: c.q2, COALESCE(c.q1)
+         ->  Hash
+               Output: d.q1, d.q2
+               ->  Seq Scan on public.int8_tbl d
+                     Output: d.q1, d.q2
+   ->  Hash
+         Output: a.q2
+         ->  Seq Scan on public.int8_tbl a
+               Output: a.q2
+(23 rows)
+
+select ss2.* from
+  int8_tbl a left join
+  (int8_tbl b left join
+   (select coalesce(q1) as x, * from int8_tbl c) ss1 on b.q1 = ss1.q2 inner join
+   lateral (select ss1.x as y, * from int8_tbl d) ss2 on b.q2 = ss2.q1)
+  on a.q2 = ss2.q1;
+        y         |        q1        |        q2         
+------------------+------------------+-------------------
+ 4567890123456789 | 4567890123456789 | -4567890123456789
+ 4567890123456789 | 4567890123456789 | -4567890123456789
+ 4567890123456789 | 4567890123456789 |  4567890123456789
+ 4567890123456789 | 4567890123456789 |  4567890123456789
+ 4567890123456789 | 4567890123456789 |               123
+ 4567890123456789 | 4567890123456789 |               123
+ 4567890123456789 |              123 |  4567890123456789
+ 4567890123456789 |              123 |               456
+              123 |              123 |  4567890123456789
+              123 |              123 |               456
+ 4567890123456789 | 4567890123456789 | -4567890123456789
+ 4567890123456789 | 4567890123456789 | -4567890123456789
+ 4567890123456789 | 4567890123456789 |  4567890123456789
+ 4567890123456789 | 4567890123456789 |  4567890123456789
+ 4567890123456789 | 4567890123456789 |               123
+ 4567890123456789 | 4567890123456789 |               123
+              123 | 4567890123456789 | -4567890123456789
+              123 | 4567890123456789 | -4567890123456789
+              123 | 4567890123456789 |  4567890123456789
+              123 | 4567890123456789 |  4567890123456789
+              123 | 4567890123456789 |               123
+              123 | 4567890123456789 |               123
+                  |                  |                  
+                  |                  |                  
+(24 rows)
+
 -- lateral can result in join conditions appearing below their
 -- real semantic level
 explain (verbose, costs off)
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 8bfe3b7ba6..d512216ad9 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -2476,6 +2476,36 @@ select * from
   int8_tbl a left join
   lateral (select *, coalesce(a.q2, 42) as x from int8_tbl b) ss on a.q2 = ss.q1;
 
+-- lateral references for simple Vars can escape being wrapped if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)
+select * from
+  int8_tbl a left join
+  (int8_tbl b inner join
+   lateral (select *, b.q2 as x from int8_tbl c) ss on b.q2 = ss.q1)
+  on a.q1 = b.q1;
+select * from
+  int8_tbl a left join
+  (int8_tbl b inner join
+   lateral (select *, b.q2 as x from int8_tbl c) ss on b.q2 = ss.q1)
+  on a.q1 = b.q1;
+
+-- lateral references for PHVs can also escape being wrapped if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)
+select ss2.* from
+  int8_tbl a left join
+  (int8_tbl b left join
+   (select coalesce(q1) as x, * from int8_tbl c) ss1 on b.q1 = ss1.q2 inner join
+   lateral (select ss1.x as y, * from int8_tbl d) ss2 on b.q2 = ss2.q1)
+  on a.q2 = ss2.q1;
+select ss2.* from
+  int8_tbl a left join
+  (int8_tbl b left join
+   (select coalesce(q1) as x, * from int8_tbl c) ss1 on b.q1 = ss1.q2 inner join
+   lateral (select ss1.x as y, * from int8_tbl d) ss2 on b.q2 = ss2.q1)
+  on a.q2 = ss2.q1;
+
 -- lateral can result in join conditions appearing below their
 -- real semantic level
 explain (verbose, costs off)
-- 
2.43.0

From 421163892151833189d17620dcc3a76a2695d338 Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Thu, 20 Jun 2024 16:48:01 +0900
Subject: [PATCH v5] Avoid unnecessary wrapping for Vars and PHVs

When pulling up a lateral subquery that is underneath an outer join,
the current code always wraps a Var or PHV in the subquery's
targetlist into a new PlaceHolderVar if it is a lateral reference to
something outside the subquery.  This is necessary when the Var/PHV
references the non-nullable side of the outer join from the nullable
side: we need to ensure that it is evaluated at the right place and
hence is forced to null when the outer join should do so.  However, if
the referenced rel is under the same lowest nulling outer join, we can
actually omit the wrapping.  It could be beneficial to get rid of such
PHVs because they imply lateral dependencies, which force us to resort
to nestloop joins.

This patch implements this optimization by remembering the relids of
the nullable side of the lowest outer join the subquery is within, and
subsequently checking whether the referenced rel is under the same
lowest nulling outer join.

No backpatch as this could result in plan changes.

Author: Richard Guo
Reviewed-by: James Coleman, Dmitry Dolgov
Discussion: https://postgr.es/m/CAMbWs48uk6C7Z9m_FNT8_21CMCk68hrgAsz=z6zpP1PNZMkeoQ@mail.gmail.com
---
 src/backend/optimizer/prep/prepjointree.c |  64 +++++++++--
 src/test/regress/expected/join.out        | 128 ++++++++++++++++++++++
 src/test/regress/sql/join.sql             |  30 +++++
 3 files changed, 210 insertions(+), 12 deletions(-)

diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 33b10d72cb..ca1ba569f7 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -49,6 +49,10 @@ typedef struct pullup_replace_vars_context
 	RangeTblEntry *target_rte;	/* RTE of subquery */
 	Relids		relids;			/* relids within subquery, as numbered after
 								 * pullup (set only if target_rte->lateral) */
+	Relids		lowest_nullable_relids; /* relids of the nullable side of the
+										 * lowest outer join subquery is
+										 * within (set only if
+										 * target_rte->lateral) */
 	bool	   *outer_hasSubLinks;	/* -> outer query's hasSubLinks */
 	int			varno;			/* varno of subquery */
 	bool		wrap_non_vars;	/* do we need all non-Var outputs to be PHVs? */
@@ -81,10 +85,12 @@ static Node *pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
 										   Node **jtlink2, Relids available_rels2);
 static Node *pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 										JoinExpr *lowest_outer_join,
+										Node *lowest_nullable_side,
 										AppendRelInfo *containing_appendrel);
 static Node *pull_up_simple_subquery(PlannerInfo *root, Node *jtnode,
 									 RangeTblEntry *rte,
 									 JoinExpr *lowest_outer_join,
+									 Node *lowest_nullable_side,
 									 AppendRelInfo *containing_appendrel);
 static Node *pull_up_simple_union_all(PlannerInfo *root, Node *jtnode,
 									  RangeTblEntry *rte);
@@ -916,7 +922,7 @@ pull_up_subqueries(PlannerInfo *root)
 	/* Recursion starts with no containing join nor appendrel */
 	root->parse->jointree = (FromExpr *)
 		pull_up_subqueries_recurse(root, (Node *) root->parse->jointree,
-								   NULL, NULL);
+								   NULL, NULL, NULL);
 	/* We should still have a FromExpr */
 	Assert(IsA(root->parse->jointree, FromExpr));
 }
@@ -931,6 +937,13 @@ pull_up_subqueries(PlannerInfo *root)
  * lowest_outer_join references the lowest such JoinExpr node; otherwise
  * it is NULL.  We use this to constrain the effects of LATERAL subqueries.
  *
+ * If this jointree node is within the nullable side of an outer join, then
+ * lowest_nullable_side references the nullable side of the lowest such
+ * JoinExpr node; otherwise it is NULL.  We use this to avoid use of the
+ * PlaceHolderVar mechanism for Vars/PHVs that are lateral references to
+ * something outside the subquery being pulled up but the referenced rel is
+ * under the same lowest nulling outer join.
+ *
  * If we are looking at a member subquery of an append relation,
  * containing_appendrel describes that relation; else it is NULL.
  * This forces use of the PlaceHolderVar mechanism for all non-Var targetlist
@@ -947,14 +960,15 @@ pull_up_subqueries(PlannerInfo *root)
  * Notice also that we can't turn pullup_replace_vars loose on the whole
  * jointree, because it'd return a mutated copy of the tree; we have to
  * invoke it just on the quals, instead.  This behavior is what makes it
- * reasonable to pass lowest_outer_join as a pointer rather than some
- * more-indirect way of identifying the lowest OJ.  Likewise, we don't
- * replace append_rel_list members but only their substructure, so the
- * containing_appendrel reference is safe to use.
+ * reasonable to pass lowest_outer_join and lowest_nullable_side as pointers
+ * rather than some more-indirect way of identifying the lowest OJ.  Likewise,
+ * we don't replace append_rel_list members but only their substructure, so
+ * the containing_appendrel reference is safe to use.
  */
 static Node *
 pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 						   JoinExpr *lowest_outer_join,
+						   Node *lowest_nullable_side,
 						   AppendRelInfo *containing_appendrel)
 {
 	/* Since this function recurses, it could be driven to stack overflow. */
@@ -981,6 +995,7 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 			 is_safe_append_member(rte->subquery)))
 			return pull_up_simple_subquery(root, jtnode, rte,
 										   lowest_outer_join,
+										   lowest_nullable_side,
 										   containing_appendrel);
 
 		/*
@@ -1028,6 +1043,7 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 		{
 			lfirst(l) = pull_up_subqueries_recurse(root, lfirst(l),
 												   lowest_outer_join,
+												   lowest_nullable_side,
 												   NULL);
 		}
 	}
@@ -1042,9 +1058,11 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 			case JOIN_INNER:
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 lowest_outer_join,
+													 lowest_nullable_side,
 													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 lowest_outer_join,
+													 lowest_nullable_side,
 													 NULL);
 				break;
 			case JOIN_LEFT:
@@ -1052,25 +1070,31 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 			case JOIN_ANTI:
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 j,
+													 lowest_nullable_side,
 													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 j,
+													 j->rarg,
 													 NULL);
 				break;
 			case JOIN_FULL:
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 j,
+													 j->larg,
 													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 j,
+													 j->rarg,
 													 NULL);
 				break;
 			case JOIN_RIGHT:
 				j->larg = pull_up_subqueries_recurse(root, j->larg,
 													 j,
+													 j->larg,
 													 NULL);
 				j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 													 j,
+													 lowest_nullable_side,
 													 NULL);
 				break;
 			default:
@@ -1100,6 +1124,7 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 static Node *
 pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 						JoinExpr *lowest_outer_join,
+						Node *lowest_nullable_side,
 						AppendRelInfo *containing_appendrel)
 {
 	Query	   *parse = root->parse;
@@ -1259,10 +1284,20 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 	rvcontext.targetlist = subquery->targetList;
 	rvcontext.target_rte = rte;
 	if (rte->lateral)
+	{
 		rvcontext.relids = get_relids_in_jointree((Node *) subquery->jointree,
 												  true, true);
+		rvcontext.lowest_nullable_relids =
+			lowest_nullable_side ?
+			get_relids_in_jointree(lowest_nullable_side,
+								   true,
+								   true) : NULL;
+	}
 	else						/* won't need relids */
+	{
 		rvcontext.relids = NULL;
+		rvcontext.lowest_nullable_relids = NULL;
+	}
 	rvcontext.outer_hasSubLinks = &parse->hasSubLinks;
 	rvcontext.varno = varno;
 	/* this flag will be set below, if needed */
@@ -1563,7 +1598,7 @@ pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root, int parentRTindex,
 		rtr = makeNode(RangeTblRef);
 		rtr->rtindex = childRTindex;
 		(void) pull_up_subqueries_recurse(root, (Node *) rtr,
-										  NULL, appinfo);
+										  NULL, NULL, appinfo);
 	}
 	else if (IsA(setOp, SetOperationStmt))
 	{
@@ -1810,6 +1845,7 @@ pull_up_simple_values(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte)
 	rvcontext.targetlist = tlist;
 	rvcontext.target_rte = rte;
 	rvcontext.relids = NULL;
+	rvcontext.lowest_nullable_relids = NULL;
 	rvcontext.outer_hasSubLinks = &parse->hasSubLinks;
 	rvcontext.varno = varno;
 	rvcontext.wrap_non_vars = false;
@@ -1971,9 +2007,10 @@ pull_up_constant_function(PlannerInfo *root, Node *jtnode,
 	/*
 	 * Since this function was reduced to a Const, it doesn't contain any
 	 * lateral references, even if it's marked as LATERAL.  This means we
-	 * don't need to fill relids.
+	 * don't need to fill relids and lowest_nullable_relids.
 	 */
 	rvcontext.relids = NULL;
+	rvcontext.lowest_nullable_relids = NULL;
 
 	rvcontext.outer_hasSubLinks = &parse->hasSubLinks;
 	rvcontext.varno = ((RangeTblRef *) jtnode)->rtindex;
@@ -2571,12 +2608,13 @@ pullup_replace_vars_callback(Var *var,
 				/*
 				 * Simple Vars always escape being wrapped, unless they are
 				 * lateral references to something outside the subquery being
-				 * pulled up.  (Even then, we could omit the PlaceHolderVar if
-				 * the referenced rel is under the same lowest outer join, but
-				 * it doesn't seem worth the trouble to check that.)
+				 * pulled up and the referenced rel is not under the same
+				 * lowest nulling outer join.
 				 */
 				if (rcon->target_rte->lateral &&
-					!bms_is_member(((Var *) newnode)->varno, rcon->relids))
+					!bms_is_member(((Var *) newnode)->varno, rcon->relids) &&
+					!bms_is_member(((Var *) newnode)->varno,
+								   rcon->lowest_nullable_relids))
 					wrap = true;
 				else
 					wrap = false;
@@ -2587,7 +2625,9 @@ pullup_replace_vars_callback(Var *var,
 				/* The same rules apply for a PlaceHolderVar */
 				if (rcon->target_rte->lateral &&
 					!bms_is_subset(((PlaceHolderVar *) newnode)->phrels,
-								   rcon->relids))
+								   rcon->relids) &&
+					!bms_is_subset(((PlaceHolderVar *) newnode)->phrels,
+								   rcon->lowest_nullable_relids))
 					wrap = true;
 				else
 					wrap = false;
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index ebf2e3f851..6f157b20d9 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -6972,6 +6972,134 @@ select * from
  4567890123456789 | -4567890123456789 |                  |                   |                 
 (10 rows)
 
+-- lateral references for simple Vars can escape being wrapped if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)
+select * from
+  int8_tbl a left join
+  (int8_tbl b inner join
+   lateral (select *, b.q2 as x from int8_tbl c) ss on b.q2 = ss.q1)
+  on a.q1 = b.q1;
+                     QUERY PLAN                     
+----------------------------------------------------
+ Hash Right Join
+   Output: a.q1, a.q2, b.q1, b.q2, c.q1, c.q2, b.q2
+   Hash Cond: (b.q1 = a.q1)
+   ->  Hash Join
+         Output: b.q1, b.q2, c.q1, c.q2
+         Hash Cond: (b.q2 = c.q1)
+         ->  Seq Scan on public.int8_tbl b
+               Output: b.q1, b.q2
+         ->  Hash
+               Output: c.q1, c.q2
+               ->  Seq Scan on public.int8_tbl c
+                     Output: c.q1, c.q2
+   ->  Hash
+         Output: a.q1, a.q2
+         ->  Seq Scan on public.int8_tbl a
+               Output: a.q1, a.q2
+(16 rows)
+
+select * from
+  int8_tbl a left join
+  (int8_tbl b inner join
+   lateral (select *, b.q2 as x from int8_tbl c) ss on b.q2 = ss.q1)
+  on a.q1 = b.q1;
+        q1        |        q2         |        q1        |        q2        |        q1        |        q2         |        x         
+------------------+-------------------+------------------+------------------+------------------+-------------------+------------------
+              123 |  4567890123456789 |              123 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+              123 |               456 |              123 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+              123 |  4567890123456789 |              123 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+              123 |               456 |              123 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+              123 |  4567890123456789 |              123 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+              123 |               456 |              123 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+ 4567890123456789 | -4567890123456789 | 4567890123456789 |              123 |              123 |  4567890123456789 |              123
+ 4567890123456789 |  4567890123456789 | 4567890123456789 |              123 |              123 |  4567890123456789 |              123
+ 4567890123456789 |               123 | 4567890123456789 |              123 |              123 |  4567890123456789 |              123
+ 4567890123456789 | -4567890123456789 | 4567890123456789 |              123 |              123 |               456 |              123
+ 4567890123456789 |  4567890123456789 | 4567890123456789 |              123 |              123 |               456 |              123
+ 4567890123456789 |               123 | 4567890123456789 |              123 |              123 |               456 |              123
+ 4567890123456789 | -4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+ 4567890123456789 |  4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+ 4567890123456789 |               123 | 4567890123456789 | 4567890123456789 | 4567890123456789 | -4567890123456789 | 4567890123456789
+ 4567890123456789 | -4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+ 4567890123456789 |  4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+ 4567890123456789 |               123 | 4567890123456789 | 4567890123456789 | 4567890123456789 |  4567890123456789 | 4567890123456789
+ 4567890123456789 | -4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+ 4567890123456789 |  4567890123456789 | 4567890123456789 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+ 4567890123456789 |               123 | 4567890123456789 | 4567890123456789 | 4567890123456789 |               123 | 4567890123456789
+(21 rows)
+
+-- lateral references for PHVs can also escape being wrapped if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)
+select ss2.* from
+  int8_tbl a left join
+  (int8_tbl b left join
+   (select coalesce(q1) as x, * from int8_tbl c) ss1 on b.q1 = ss1.q2 inner join
+   lateral (select ss1.x as y, * from int8_tbl d) ss2 on b.q2 = ss2.q1)
+  on a.q2 = ss2.q1;
+                       QUERY PLAN                       
+--------------------------------------------------------
+ Hash Right Join
+   Output: (COALESCE(c.q1)), d.q1, d.q2
+   Hash Cond: (d.q1 = a.q2)
+   ->  Hash Join
+         Output: (COALESCE(c.q1)), d.q1, d.q2
+         Hash Cond: (b.q2 = d.q1)
+         ->  Hash Left Join
+               Output: b.q2, (COALESCE(c.q1))
+               Hash Cond: (b.q1 = c.q2)
+               ->  Seq Scan on public.int8_tbl b
+                     Output: b.q1, b.q2
+               ->  Hash
+                     Output: c.q2, (COALESCE(c.q1))
+                     ->  Seq Scan on public.int8_tbl c
+                           Output: c.q2, COALESCE(c.q1)
+         ->  Hash
+               Output: d.q1, d.q2
+               ->  Seq Scan on public.int8_tbl d
+                     Output: d.q1, d.q2
+   ->  Hash
+         Output: a.q2
+         ->  Seq Scan on public.int8_tbl a
+               Output: a.q2
+(23 rows)
+
+select ss2.* from
+  int8_tbl a left join
+  (int8_tbl b left join
+   (select coalesce(q1) as x, * from int8_tbl c) ss1 on b.q1 = ss1.q2 inner join
+   lateral (select ss1.x as y, * from int8_tbl d) ss2 on b.q2 = ss2.q1)
+  on a.q2 = ss2.q1;
+        y         |        q1        |        q2         
+------------------+------------------+-------------------
+ 4567890123456789 | 4567890123456789 | -4567890123456789
+ 4567890123456789 | 4567890123456789 | -4567890123456789
+ 4567890123456789 | 4567890123456789 |  4567890123456789
+ 4567890123456789 | 4567890123456789 |  4567890123456789
+ 4567890123456789 | 4567890123456789 |               123
+ 4567890123456789 | 4567890123456789 |               123
+ 4567890123456789 |              123 |  4567890123456789
+ 4567890123456789 |              123 |               456
+              123 |              123 |  4567890123456789
+              123 |              123 |               456
+ 4567890123456789 | 4567890123456789 | -4567890123456789
+ 4567890123456789 | 4567890123456789 | -4567890123456789
+ 4567890123456789 | 4567890123456789 |  4567890123456789
+ 4567890123456789 | 4567890123456789 |  4567890123456789
+ 4567890123456789 | 4567890123456789 |               123
+ 4567890123456789 | 4567890123456789 |               123
+              123 | 4567890123456789 | -4567890123456789
+              123 | 4567890123456789 | -4567890123456789
+              123 | 4567890123456789 |  4567890123456789
+              123 | 4567890123456789 |  4567890123456789
+              123 | 4567890123456789 |               123
+              123 | 4567890123456789 |               123
+                  |                  |                  
+                  |                  |                  
+(24 rows)
+
 -- lateral can result in join conditions appearing below their
 -- real semantic level
 explain (verbose, costs off)
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 1004fc0355..54843eafc9 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -2543,6 +2543,36 @@ select * from
   int8_tbl a left join
   lateral (select *, coalesce(a.q2, 42) as x from int8_tbl b) ss on a.q2 = ss.q1;
 
+-- lateral references for simple Vars can escape being wrapped if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)
+select * from
+  int8_tbl a left join
+  (int8_tbl b inner join
+   lateral (select *, b.q2 as x from int8_tbl c) ss on b.q2 = ss.q1)
+  on a.q1 = b.q1;
+select * from
+  int8_tbl a left join
+  (int8_tbl b inner join
+   lateral (select *, b.q2 as x from int8_tbl c) ss on b.q2 = ss.q1)
+  on a.q1 = b.q1;
+
+-- lateral references for PHVs can also escape being wrapped if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)
+select ss2.* from
+  int8_tbl a left join
+  (int8_tbl b left join
+   (select coalesce(q1) as x, * from int8_tbl c) ss1 on b.q1 = ss1.q2 inner join
+   lateral (select ss1.x as y, * from int8_tbl d) ss2 on b.q2 = ss2.q1)
+  on a.q2 = ss2.q1;
+select ss2.* from
+  int8_tbl a left join
+  (int8_tbl b left join
+   (select coalesce(q1) as x, * from int8_tbl c) ss1 on b.q1 = ss1.q2 inner join
+   lateral (select ss1.x as y, * from int8_tbl d) ss2 on b.q2 = ss2.q1)
+  on a.q2 = ss2.q1;
+
 -- lateral can result in join conditions appearing below their
 -- real semantic level
 explain (verbose, costs off)
-- 
2.43.0

From cd9f79c71e0bdcc8cbf62f319649d5359a74ea7b Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Mon, 2 Dec 2024 10:31:39 +0900
Subject: [PATCH v6] Avoid unnecessary wrapping for Vars and PHVs

When pulling up a lateral subquery that is under an outer join, the
current code always wraps a Var or PHV in the subquery's targetlist
into a new PlaceHolderVar if it is a lateral reference to something
outside the subquery.  This is necessary when the Var/PHV references
the non-nullable side of the outer join from the nullable side: we
need to ensure that it is evaluated at the right place and hence is
forced to null when the outer join should do so.  However, if the
referenced rel is under the same lowest nulling outer join, we can
actually omit the wrapping.  That's safe because if the subquery
variable is forced to NULL by the outer join, the lateral reference
variable will come out as NULL too.  It could be beneficial to get rid
of such PHVs because they imply lateral dependencies, which force us
to resort to nestloop joins.

This patch leverages the newly introduced nullingrel_info to check if
the nullingrels of the subquery RTE are a subset of those of the
laterally referenced rel, in order to determine if the referenced rel
is under the same lowest nulling outer join.

No backpatch as this could result in plan changes.

Author: Richard Guo
Reviewed-by: James Coleman, Dmitry Dolgov
Discussion: https://postgr.es/m/CAMbWs48uk6C7Z9m_FNT8_21CMCk68hrgAsz=z6zpP1PNZMkeoQ@mail.gmail.com
---
 src/backend/optimizer/prep/prepjointree.c |  39 ++++--
 src/test/regress/expected/subselect.out   | 138 ++++++++++++++++++++++
 src/test/regress/sql/subselect.sql        |  36 ++++++
 3 files changed, 204 insertions(+), 9 deletions(-)

diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 2ebd938f6b..3fa4d78c3e 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -2598,26 +2598,47 @@ pullup_replace_vars_callback(Var *var,
 				/*
 				 * Simple Vars always escape being wrapped, unless they are
 				 * lateral references to something outside the subquery being
-				 * pulled up.  (Even then, we could omit the PlaceHolderVar if
-				 * the referenced rel is under the same lowest outer join, but
-				 * it doesn't seem worth the trouble to check that.)
+				 * pulled up and the referenced rel is not under the same
+				 * lowest nulling outer join.
 				 */
+				wrap = false;
 				if (rcon->target_rte->lateral &&
 					!bms_is_member(((Var *) newnode)->varno, rcon->relids))
-					wrap = true;
-				else
-					wrap = false;
+				{
+					nullingrel_info *nullinfo = rcon->nullinfo;
+					int			lvarno = ((Var *) newnode)->varno;
+
+					Assert(lvarno > 0 && lvarno <= nullinfo->rtlength);
+					if (!bms_is_subset(nullinfo->nullingrels[rcon->varno],
+									   nullinfo->nullingrels[lvarno]))
+						wrap = true;
+				}
 			}
 			else if (newnode && IsA(newnode, PlaceHolderVar) &&
 					 ((PlaceHolderVar *) newnode)->phlevelsup == 0)
 			{
 				/* The same rules apply for a PlaceHolderVar */
+				wrap = false;
 				if (rcon->target_rte->lateral &&
 					!bms_is_subset(((PlaceHolderVar *) newnode)->phrels,
 								   rcon->relids))
-					wrap = true;
-				else
-					wrap = false;
+				{
+					nullingrel_info *nullinfo = rcon->nullinfo;
+					Relids		lvarnos = ((PlaceHolderVar *) newnode)->phrels;
+					int			lvarno;
+
+					lvarno = -1;
+					while ((lvarno = bms_next_member(lvarnos, lvarno)) >= 0)
+					{
+						Assert(lvarno > 0 && lvarno <= nullinfo->rtlength);
+						if (!bms_is_subset(nullinfo->nullingrels[rcon->varno],
+										   nullinfo->nullingrels[lvarno]))
+						{
+							wrap = true;
+							break;
+						}
+					}
+				}
 			}
 			else if (rcon->wrap_non_vars)
 			{
diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out
index 6c1fb2bfdb..566dec67fa 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -1848,6 +1848,144 @@ order by 1, 2;
  4567890123456789 | 9135780246913578
 (11 rows)
 
+-- lateral references for simple Vars can escape being wrapped if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)
+select t1.q1, x from
+  int8_tbl t1 left join
+  (int8_tbl t2 inner join
+   lateral (select t2.q2 as x, * from int8_tbl t3) ss on t2.q2 = ss.q1)
+  on t1.q1 = t2.q1
+order by 1, 2;
+                       QUERY PLAN                       
+--------------------------------------------------------
+ Sort
+   Output: t1.q1, t2.q2
+   Sort Key: t1.q1, t2.q2
+   ->  Hash Right Join
+         Output: t1.q1, t2.q2
+         Hash Cond: (t2.q1 = t1.q1)
+         ->  Hash Join
+               Output: t2.q2, t2.q1
+               Hash Cond: (t2.q2 = t3.q1)
+               ->  Seq Scan on public.int8_tbl t2
+                     Output: t2.q1, t2.q2
+               ->  Hash
+                     Output: t3.q1
+                     ->  Seq Scan on public.int8_tbl t3
+                           Output: t3.q1
+         ->  Hash
+               Output: t1.q1
+               ->  Seq Scan on public.int8_tbl t1
+                     Output: t1.q1
+(19 rows)
+
+select t1.q1, x from
+  int8_tbl t1 left join
+  (int8_tbl t2 inner join
+   lateral (select t2.q2 as x, * from int8_tbl t3) ss on t2.q2 = ss.q1)
+  on t1.q1 = t2.q1
+order by 1, 2;
+        q1        |        x         
+------------------+------------------
+              123 | 4567890123456789
+              123 | 4567890123456789
+              123 | 4567890123456789
+              123 | 4567890123456789
+              123 | 4567890123456789
+              123 | 4567890123456789
+ 4567890123456789 |              123
+ 4567890123456789 |              123
+ 4567890123456789 |              123
+ 4567890123456789 |              123
+ 4567890123456789 |              123
+ 4567890123456789 |              123
+ 4567890123456789 | 4567890123456789
+ 4567890123456789 | 4567890123456789
+ 4567890123456789 | 4567890123456789
+ 4567890123456789 | 4567890123456789
+ 4567890123456789 | 4567890123456789
+ 4567890123456789 | 4567890123456789
+ 4567890123456789 | 4567890123456789
+ 4567890123456789 | 4567890123456789
+ 4567890123456789 | 4567890123456789
+(21 rows)
+
+-- lateral references for PHVs can also escape being wrapped if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)
+select ss2.* from
+  int8_tbl t1 left join
+  (int8_tbl t2 left join
+   (select coalesce(q1) as x, * from int8_tbl t3) ss1 on t2.q1 = ss1.q2 inner join
+   lateral (select ss1.x as y, * from int8_tbl t4) ss2 on t2.q2 = ss2.q1)
+  on t1.q2 = ss2.q1
+order by 1, 2, 3;
+                           QUERY PLAN                           
+----------------------------------------------------------------
+ Sort
+   Output: (COALESCE(t3.q1)), t4.q1, t4.q2
+   Sort Key: (COALESCE(t3.q1)), t4.q1, t4.q2
+   ->  Hash Right Join
+         Output: (COALESCE(t3.q1)), t4.q1, t4.q2
+         Hash Cond: (t4.q1 = t1.q2)
+         ->  Hash Join
+               Output: (COALESCE(t3.q1)), t4.q1, t4.q2
+               Hash Cond: (t2.q2 = t4.q1)
+               ->  Hash Left Join
+                     Output: t2.q2, (COALESCE(t3.q1))
+                     Hash Cond: (t2.q1 = t3.q2)
+                     ->  Seq Scan on public.int8_tbl t2
+                           Output: t2.q1, t2.q2
+                     ->  Hash
+                           Output: t3.q2, (COALESCE(t3.q1))
+                           ->  Seq Scan on public.int8_tbl t3
+                                 Output: t3.q2, COALESCE(t3.q1)
+               ->  Hash
+                     Output: t4.q1, t4.q2
+                     ->  Seq Scan on public.int8_tbl t4
+                           Output: t4.q1, t4.q2
+         ->  Hash
+               Output: t1.q2
+               ->  Seq Scan on public.int8_tbl t1
+                     Output: t1.q2
+(26 rows)
+
+select ss2.* from
+  int8_tbl t1 left join
+  (int8_tbl t2 left join
+   (select coalesce(q1) as x, * from int8_tbl t3) ss1 on t2.q1 = ss1.q2 inner join
+   lateral (select ss1.x as y, * from int8_tbl t4) ss2 on t2.q2 = ss2.q1)
+  on t1.q2 = ss2.q1
+order by 1, 2, 3;
+        y         |        q1        |        q2         
+------------------+------------------+-------------------
+              123 |              123 |               456
+              123 |              123 |  4567890123456789
+              123 | 4567890123456789 | -4567890123456789
+              123 | 4567890123456789 | -4567890123456789
+              123 | 4567890123456789 |               123
+              123 | 4567890123456789 |               123
+              123 | 4567890123456789 |  4567890123456789
+              123 | 4567890123456789 |  4567890123456789
+ 4567890123456789 |              123 |               456
+ 4567890123456789 |              123 |  4567890123456789
+ 4567890123456789 | 4567890123456789 | -4567890123456789
+ 4567890123456789 | 4567890123456789 | -4567890123456789
+ 4567890123456789 | 4567890123456789 | -4567890123456789
+ 4567890123456789 | 4567890123456789 | -4567890123456789
+ 4567890123456789 | 4567890123456789 |               123
+ 4567890123456789 | 4567890123456789 |               123
+ 4567890123456789 | 4567890123456789 |               123
+ 4567890123456789 | 4567890123456789 |               123
+ 4567890123456789 | 4567890123456789 |  4567890123456789
+ 4567890123456789 | 4567890123456789 |  4567890123456789
+ 4567890123456789 | 4567890123456789 |  4567890123456789
+ 4567890123456789 | 4567890123456789 |  4567890123456789
+                  |                  |                  
+                  |                  |                  
+(24 rows)
+
 --
 -- Tests for CTE inlining behavior
 --
diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql
index e5a562c3f5..23c6350d94 100644
--- a/src/test/regress/sql/subselect.sql
+++ b/src/test/regress/sql/subselect.sql
@@ -939,6 +939,42 @@ select t1.q1, x from
   on t1.q2 = t2.q2
 order by 1, 2;
 
+-- lateral references for simple Vars can escape being wrapped if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)
+select t1.q1, x from
+  int8_tbl t1 left join
+  (int8_tbl t2 inner join
+   lateral (select t2.q2 as x, * from int8_tbl t3) ss on t2.q2 = ss.q1)
+  on t1.q1 = t2.q1
+order by 1, 2;
+
+select t1.q1, x from
+  int8_tbl t1 left join
+  (int8_tbl t2 inner join
+   lateral (select t2.q2 as x, * from int8_tbl t3) ss on t2.q2 = ss.q1)
+  on t1.q1 = t2.q1
+order by 1, 2;
+
+-- lateral references for PHVs can also escape being wrapped if the
+-- referenced rel is under the same lowest nulling outer join
+explain (verbose, costs off)
+select ss2.* from
+  int8_tbl t1 left join
+  (int8_tbl t2 left join
+   (select coalesce(q1) as x, * from int8_tbl t3) ss1 on t2.q1 = ss1.q2 inner join
+   lateral (select ss1.x as y, * from int8_tbl t4) ss2 on t2.q2 = ss2.q1)
+  on t1.q2 = ss2.q1
+order by 1, 2, 3;
+
+select ss2.* from
+  int8_tbl t1 left join
+  (int8_tbl t2 left join
+   (select coalesce(q1) as x, * from int8_tbl t3) ss1 on t2.q1 = ss1.q2 inner join
+   lateral (select ss1.x as y, * from int8_tbl t4) ss2 on t2.q2 = ss2.q1)
+  on t1.q2 = ss2.q1
+order by 1, 2, 3;
+
 --
 -- Tests for CTE inlining behavior
 --
-- 
2.43.0