6 files changed, 336 insertions, 38 deletions

diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 5abb114ba8e..6917ee55aa6 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -298,6 +298,7 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids)
 	List	   *joininfos;
 	Index		rti;
 	ListCell   *l;
+	ListCell   *nextl;
 
 	/*
 	 * Mark the rel as "dead" to show it is no longer part of the join tree.
@@ -351,6 +352,26 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids)
 	}
 
 	/*
+	 * Likewise remove references from LateralJoinInfo data structures.
+	 *
+	 * If we are deleting a LATERAL subquery, we can forget its
+	 * LateralJoinInfo altogether.  Otherwise, make sure the target is not
+	 * included in any lateral_lhs set.  (It probably can't be, since that
+	 * should have precluded deciding to remove it; but let's cope anyway.)
+	 */
+	for (l = list_head(root->lateral_info_list); l != NULL; l = nextl)
+	{
+		LateralJoinInfo *ljinfo = (LateralJoinInfo *) lfirst(l);
+
+		nextl = lnext(l);
+		if (ljinfo->lateral_rhs == relid)
+			root->lateral_info_list = list_delete_ptr(root->lateral_info_list,
+													  ljinfo);
+		else
+			ljinfo->lateral_lhs = bms_del_member(ljinfo->lateral_lhs, relid);
+	}
+
+	/*
 	 * Likewise remove references from PlaceHolderVar data structures.
 	 *
 	 * Here we have a special case: if a PHV's eval_at set is just the target
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index d45ebfc4616..5d3b293b88a 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -298,8 +298,19 @@ create_scan_plan(PlannerInfo *root, Path *best_path)
 		}
 	}
 	else
+	{
 		tlist = build_relation_tlist(rel);
 
+		/*
+		 * If it's a parameterized otherrel, there might be lateral references
+		 * in the tlist, which need to be replaced with Params.  This cannot
+		 * happen for regular baserels, though.  Note use_physical_tlist()
+		 * always fails for otherrels, so we don't need to check this above.
+		 */
+		if (rel->reloptkind != RELOPT_BASEREL && best_path->param_info)
+			tlist = (List *) replace_nestloop_params(root, (Node *) tlist);
+	}
+
 	/*
 	 * Extract the relevant restriction clauses from the parent relation. The
 	 * executor must apply all these restrictions during the scan, except for
@@ -1583,6 +1594,7 @@ create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
 {
 	TidScan    *scan_plan;
 	Index		scan_relid = best_path->path.parent->relid;
+	List	   *tidquals = best_path->tidquals;
 	List	   *ortidquals;
 
 	/* it should be a base rel... */
@@ -1595,11 +1607,20 @@ create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
 	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
 	scan_clauses = extract_actual_clauses(scan_clauses, false);
 
+	/* Replace any outer-relation variables with nestloop params */
+	if (best_path->path.param_info)
+	{
+		tidquals = (List *)
+			replace_nestloop_params(root, (Node *) tidquals);
+		scan_clauses = (List *)
+			replace_nestloop_params(root, (Node *) scan_clauses);
+	}
+
 	/*
 	 * Remove any clauses that are TID quals.  This is a bit tricky since the
 	 * tidquals list has implicit OR semantics.
 	 */
-	ortidquals = best_path->tidquals;
+	ortidquals = tidquals;
 	if (list_length(ortidquals) > 1)
 		ortidquals = list_make1(make_orclause(ortidquals));
 	scan_clauses = list_difference(scan_clauses, ortidquals);
@@ -1607,7 +1628,7 @@ create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
 	scan_plan = make_tidscan(tlist,
 							 scan_clauses,
 							 scan_relid,
-							 best_path->tidquals);
+							 tidquals);
 
 	copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
 
@@ -1823,6 +1844,13 @@ create_ctescan_plan(PlannerInfo *root, Path *best_path,
 	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
 	scan_clauses = extract_actual_clauses(scan_clauses, false);
 
+	/* Replace any outer-relation variables with nestloop params */
+	if (best_path->param_info)
+	{
+		scan_clauses = (List *)
+			replace_nestloop_params(root, (Node *) scan_clauses);
+	}
+
 	scan_plan = make_ctescan(tlist, scan_clauses, scan_relid,
 							 plan_id, cte_param_id);
 
@@ -1876,6 +1904,13 @@ create_worktablescan_plan(PlannerInfo *root, Path *best_path,
 	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
 	scan_clauses = extract_actual_clauses(scan_clauses, false);
 
+	/* Replace any outer-relation variables with nestloop params */
+	if (best_path->param_info)
+	{
+		scan_clauses = (List *)
+			replace_nestloop_params(root, (Node *) scan_clauses);
+	}
+
 	scan_plan = make_worktablescan(tlist, scan_clauses, scan_relid,
 								   cteroot->wt_param_id);
 
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index 81f7cf2e9d8..824c6a7e473 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -22,9 +22,11 @@
 #include "optimizer/paths.h"
 #include "optimizer/placeholder.h"
 #include "optimizer/planmain.h"
+#include "optimizer/planner.h"
 #include "optimizer/prep.h"
 #include "optimizer/restrictinfo.h"
 #include "optimizer/var.h"
+#include "rewrite/rewriteManip.h"
 #include "utils/lsyscache.h"
 
 
@@ -33,6 +35,9 @@ int			from_collapse_limit;
 int			join_collapse_limit;
 
 
+static void extract_lateral_references(PlannerInfo *root, RelOptInfo *brel,
+						   Index rtindex);
+static void add_lateral_info(PlannerInfo *root, Index rhs, Relids lhs);
 static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode,
 					bool below_outer_join,
 					Relids *qualscope, Relids *inner_join_rels);
@@ -204,18 +209,75 @@ add_vars_to_targetlist(PlannerInfo *root, List *vars,
 	}
 }
 
+
+/*****************************************************************************
+ *
+ *	  LATERAL REFERENCES
+ *
+ *****************************************************************************/
+
 /*
- * extract_lateral_references
- *	  If the specified RTE is a LATERAL subquery, extract all its references
- *	  to Vars of the current query level, and make sure those Vars will be
- *	  available for evaluation of the RTE.
+ * find_lateral_references
+ *	  For each LATERAL subquery, extract all its references to Vars and
+ *	  PlaceHolderVars of the current query level, and make sure those values
+ *	  will be available for evaluation of the subquery.
  *
- * XXX this is rather duplicative of processing that has to happen elsewhere.
- * Maybe it'd be a good idea to do this type of extraction further upstream
- * and save the results?
+ * While later planning steps ensure that the Var/PHV source rels are on the
+ * outside of nestloops relative to the LATERAL subquery, we also need to
+ * ensure that the Vars/PHVs propagate up to the nestloop join level; this
+ * means setting suitable where_needed values for them.
+ *
+ * This has to run before deconstruct_jointree, since it might result in
+ * creation of PlaceHolderInfos or extension of their ph_may_need sets.
  */
+void
+find_lateral_references(PlannerInfo *root)
+{
+	Index		rti;
+
+	/* We need do nothing if the query contains no LATERAL RTEs */
+	if (!root->hasLateralRTEs)
+		return;
+
+	/*
+	 * Examine all baserels (the rel array has been set up by now).
+	 */
+	for (rti = 1; rti < root->simple_rel_array_size; rti++)
+	{
+		RelOptInfo *brel = root->simple_rel_array[rti];
+
+		/* there may be empty slots corresponding to non-baserel RTEs */
+		if (brel == NULL)
+			continue;
+
+		Assert(brel->relid == rti);		/* sanity check on array */
+
+		/*
+		 * This bit is less obvious than it might look.  We ignore appendrel
+		 * otherrels and consider only their parent baserels.  In a case where
+		 * a LATERAL-containing UNION ALL subquery was pulled up, it is the
+		 * otherrels that are actually going to be in the plan.  However, we
+		 * want to mark all their lateral references as needed by the parent,
+		 * because it is the parent's relid that will be used for join
+		 * planning purposes.  And the parent's RTE will contain all the
+		 * lateral references we need to know, since the pulled-up members are
+		 * nothing but copies of parts of the original RTE's subquery.  We
+		 * could visit the children instead and transform their references
+		 * back to the parent's relid, but it would be much more complicated
+		 * for no real gain.  (Important here is that the child members have
+		 * not yet received any processing beyond being pulled up.)
+		 */
+
+		/* ignore RTEs that are "other rels" */
+		if (brel->reloptkind != RELOPT_BASEREL)
+			continue;
+
+		extract_lateral_references(root, brel, rti);
+	}
+}
+
 static void
-extract_lateral_references(PlannerInfo *root, int rtindex)
+extract_lateral_references(PlannerInfo *root, RelOptInfo *brel, Index rtindex)
 {
 	RangeTblEntry *rte = root->simple_rte_array[rtindex];
 	List	   *vars;
@@ -235,35 +297,52 @@ extract_lateral_references(PlannerInfo *root, int rtindex)
 	else if (rte->rtekind == RTE_VALUES)
 		vars = pull_vars_of_level((Node *) rte->values_lists, 0);
 	else
-		return;
+	{
+		Assert(false);
+		return;					/* keep compiler quiet */
+	}
+
+	if (vars == NIL)
+		return;					/* nothing to do */
 
 	/* Copy each Var (or PlaceHolderVar) and adjust it to match our level */
 	newvars = NIL;
 	foreach(lc, vars)
 	{
-		Node   *var = (Node *) lfirst(lc);
+		Node   *node = (Node *) lfirst(lc);
 
-		var = copyObject(var);
-		if (IsA(var, Var))
+		node = copyObject(node);
+		if (IsA(node, Var))
 		{
-			((Var *) var)->varlevelsup = 0;
+			Var	   *var = (Var *) node;
+
+			/* Adjustment is easy since it's just one node */
+			var->varlevelsup = 0;
 		}
-		else if (IsA(var, PlaceHolderVar))
+		else if (IsA(node, PlaceHolderVar))
 		{
+			PlaceHolderVar *phv = (PlaceHolderVar *) node;
+			int		levelsup = phv->phlevelsup;
+
+			/* Have to work harder to adjust the contained expression too */
+			if (levelsup != 0)
+				IncrementVarSublevelsUp(node, -levelsup, 0);
+
 			/*
-			 * It's sufficient to set phlevelsup = 0, because we call
-			 * add_vars_to_targetlist with create_new_ph = false (as we must,
-			 * because deconstruct_jointree has already started); therefore
-			 * nobody is going to look at the contained expression to notice
-			 * whether its Vars have the right level.
+			 * If we pulled the PHV out of a subquery RTE, its expression
+			 * needs to be preprocessed.  subquery_planner() already did this
+			 * for level-zero PHVs in function and values RTEs, though.
 			 */
-			((PlaceHolderVar *) var)->phlevelsup = 0;
+			if (levelsup > 0)
+				phv->phexpr = preprocess_phv_expression(root, phv->phexpr);
 		}
 		else
 			Assert(false);
-		newvars = lappend(newvars, var);
+		newvars = lappend(newvars, node);
 	}
 
+	list_free(vars);
+
 	/*
 	 * We mark the Vars as being "needed" at the LATERAL RTE.  This is a bit
 	 * of a cheat: a more formal approach would be to mark each one as needed
@@ -274,10 +353,146 @@ extract_lateral_references(PlannerInfo *root, int rtindex)
 	where_needed = bms_make_singleton(rtindex);
 
 	/* Push the Vars into their source relations' targetlists */
-	add_vars_to_targetlist(root, newvars, where_needed, false);
+	add_vars_to_targetlist(root, newvars, where_needed, true);
 
-	list_free(newvars);
-	list_free(vars);
+	/* Remember the lateral references for create_lateral_join_info */
+	brel->lateral_vars = newvars;
+}
+
+/*
+ * create_lateral_join_info
+ *	  For each LATERAL subquery, create LateralJoinInfo(s) and add them to
+ *	  root->lateral_info_list, and fill in the per-rel lateral_relids sets.
+ *
+ * This has to run after deconstruct_jointree, because we need to know the
+ * final ph_eval_at values for referenced PlaceHolderVars.
+ */
+void
+create_lateral_join_info(PlannerInfo *root)
+{
+	Index		rti;
+
+	/* We need do nothing if the query contains no LATERAL RTEs */
+	if (!root->hasLateralRTEs)
+		return;
+
+	/*
+	 * Examine all baserels (the rel array has been set up by now).
+	 */
+	for (rti = 1; rti < root->simple_rel_array_size; rti++)
+	{
+		RelOptInfo *brel = root->simple_rel_array[rti];
+		Relids		lateral_relids;
+		ListCell *lc;
+
+		/* there may be empty slots corresponding to non-baserel RTEs */
+		if (brel == NULL)
+			continue;
+
+		Assert(brel->relid == rti);		/* sanity check on array */
+
+		/* ignore RTEs that are "other rels" */
+		if (brel->reloptkind != RELOPT_BASEREL)
+			continue;
+
+		lateral_relids = NULL;
+
+		/* consider each laterally-referenced Var or PHV */
+		foreach(lc, brel->lateral_vars)
+		{
+			Node   *node = (Node *) lfirst(lc);
+
+			if (IsA(node, Var))
+			{
+				Var	   *var = (Var *) node;
+
+				add_lateral_info(root, rti, bms_make_singleton(var->varno));
+				lateral_relids = bms_add_member(lateral_relids,
+												var->varno);
+			}
+			else if (IsA(node, PlaceHolderVar))
+			{
+				PlaceHolderVar *phv = (PlaceHolderVar *) node;
+				PlaceHolderInfo *phinfo = find_placeholder_info(root, phv,
+																false);
+
+				add_lateral_info(root, rti, bms_copy(phinfo->ph_eval_at));
+				lateral_relids = bms_add_members(lateral_relids,
+												 phinfo->ph_eval_at);
+			}
+			else
+				Assert(false);
+		}
+
+		/* We now know all the relids needed for lateral refs in this rel */
+		if (bms_is_empty(lateral_relids))
+			continue;			/* ensure lateral_relids is NULL if empty */
+		brel->lateral_relids = lateral_relids;
+
+		/*
+		 * If it's an appendrel parent, copy its lateral_relids to each child
+		 * rel.  We intentionally give each child rel the same minimum
+		 * parameterization, even though it's quite possible that some don't
+		 * reference all the lateral rels.  This is because any append path
+		 * for the parent will have to have the same parameterization for
+		 * every child anyway, and there's no value in forcing extra
+		 * reparameterize_path() calls.
+		 */
+		if (root->simple_rte_array[rti]->inh)
+		{
+			foreach(lc, root->append_rel_list)
+			{
+				AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
+				RelOptInfo *childrel;
+
+				if (appinfo->parent_relid != rti)
+					continue;
+				childrel = root->simple_rel_array[appinfo->child_relid];
+				Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL);
+				Assert(childrel->lateral_relids == NULL);
+				childrel->lateral_relids = lateral_relids;
+			}
+		}
+	}
+}
+
+/*
+ * add_lateral_info
+ *		Add a LateralJoinInfo to root->lateral_info_list, if needed
+ *
+ * We suppress redundant list entries.  The passed lhs set must be freshly
+ * made; we free it if not used in a new list entry.
+ */
+static void
+add_lateral_info(PlannerInfo *root, Index rhs, Relids lhs)
+{
+	LateralJoinInfo *ljinfo;
+	ListCell   *l;
+
+	Assert(!bms_is_member(rhs, lhs));
+
+	/*
+	 * If an existing list member has the same RHS and an LHS that is a subset
+	 * of the new one, it's redundant, but we don't trouble to get rid of it.
+	 * The only case that is really worth worrying about is identical entries,
+	 * and we handle that well enough with this simple logic.
+	 */
+	foreach(l, root->lateral_info_list)
+	{
+		ljinfo = (LateralJoinInfo *) lfirst(l);
+		if (rhs == ljinfo->lateral_rhs &&
+			bms_is_subset(lhs, ljinfo->lateral_lhs))
+		{
+			bms_free(lhs);
+			return;
+		}
+	}
+
+	/* Not there, so make a new entry */
+	ljinfo = makeNode(LateralJoinInfo);
+	ljinfo->lateral_rhs = rhs;
+	ljinfo->lateral_lhs = lhs;
+	root->lateral_info_list = lappend(root->lateral_info_list, ljinfo);
 }
 
 
@@ -362,9 +577,7 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
 	{
 		int			varno = ((RangeTblRef *) jtnode)->rtindex;
 
-		/* No quals to deal with, but do check for LATERAL subqueries */
-		extract_lateral_references(root, varno);
-		/* Result qualscope is just the one Relid */
+		/* No quals to deal with, just return correct result */
 		*qualscope = bms_make_singleton(varno);
 		/* A single baserel does not create an inner join */
 		*inner_join_rels = NULL;
diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c
index 0bbca071fb0..373f65b76fe 100644
--- a/src/backend/optimizer/plan/planagg.c
+++ b/src/backend/optimizer/plan/planagg.c
@@ -392,8 +392,9 @@ build_minmax_path(PlannerInfo *root, MinMaxAggInfo *mminfo,
 	subroot->parse = parse = (Query *) copyObject(root->parse);
 	/* make sure subroot planning won't change root->init_plans contents */
 	subroot->init_plans = list_copy(root->init_plans);
-	/* There shouldn't be any OJ info to translate, as yet */
+	/* There shouldn't be any OJ or LATERAL info to translate, as yet */
 	Assert(subroot->join_info_list == NIL);
+	Assert(subroot->lateral_info_list == NIL);
 	/* and we haven't created PlaceHolderInfos, either */
 	Assert(subroot->placeholder_list == NIL);
 
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index 9838dc45d5e..04acc006f53 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -141,6 +141,7 @@ query_planner(PlannerInfo *root, List *tlist,
 	root->right_join_clauses = NIL;
 	root->full_join_clauses = NIL;
 	root->join_info_list = NIL;
+	root->lateral_info_list = NIL;
 	root->placeholder_list = NIL;
 	root->initial_rels = NIL;
 
@@ -178,9 +179,17 @@ query_planner(PlannerInfo *root, List *tlist,
 
 	find_placeholders_in_jointree(root);
 
+	find_lateral_references(root);
+
 	joinlist = deconstruct_jointree(root);
 
 	/*
+	 * Create the LateralJoinInfo list now that we have finalized
+	 * PlaceHolderVar eval levels.
+	 */
+	create_lateral_join_info(root);
+
+	/*
 	 * Reconsider any postponed outer-join quals now that we have built up
 	 * equivalence classes.  (This could result in further additions or
 	 * mergings of classes.)
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 3485f2025ca..6170d48892e 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -54,6 +54,7 @@ planner_hook_type planner_hook = NULL;
 #define EXPRKIND_VALUES		3
 #define EXPRKIND_LIMIT		4
 #define EXPRKIND_APPINFO	5
+#define EXPRKIND_PHV		6
 
 
 static Node *preprocess_expression(PlannerInfo *root, Node *expr, int kind);
@@ -348,10 +349,12 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
 	/*
 	 * Detect whether any rangetable entries are RTE_JOIN kind; if not, we can
 	 * avoid the expense of doing flatten_join_alias_vars().  Also check for
-	 * outer joins --- if none, we can skip reduce_outer_joins(). This must be
-	 * done after we have done pull_up_subqueries, of course.
+	 * outer joins --- if none, we can skip reduce_outer_joins().  And check
+	 * for LATERAL RTEs, too.  This must be done after we have done
+	 * pull_up_subqueries(), of course.
 	 */
 	root->hasJoinRTEs = false;
+	root->hasLateralRTEs = false;
 	hasOuterJoins = false;
 	foreach(l, parse->rtable)
 	{
@@ -361,12 +364,10 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
 		{
 			root->hasJoinRTEs = true;
 			if (IS_OUTER_JOIN(rte->jointype))
-			{
 				hasOuterJoins = true;
-				/* Can quit scanning once we find an outer join */
-				break;
-			}
 		}
+		if (rte->lateral)
+			root->hasLateralRTEs = true;
 	}
 
 	/*
@@ -576,7 +577,7 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
  * preprocess_expression
  *		Do subquery_planner's preprocessing work for an expression,
  *		which can be a targetlist, a WHERE clause (including JOIN/ON
- *		conditions), or a HAVING clause.
+ *		conditions), a HAVING clause, or a few other things.
  */
 static Node *
 preprocess_expression(PlannerInfo *root, Node *expr, int kind)
@@ -693,6 +694,23 @@ preprocess_qual_conditions(PlannerInfo *root, Node *jtnode)
 }
 
 /*
+ * preprocess_phv_expression
+ *	  Do preprocessing on a PlaceHolderVar expression that's been pulled up.
+ *
+ * If a LATERAL subquery references an output of another subquery, and that
+ * output must be wrapped in a PlaceHolderVar because of an intermediate outer
+ * join, then we'll push the PlaceHolderVar expression down into the subquery
+ * and later pull it back up during find_lateral_references, which runs after
+ * subquery_planner has preprocessed all the expressions that were in the
+ * current query level to start with.  So we need to preprocess it then.
+ */
+Expr *
+preprocess_phv_expression(PlannerInfo *root, Expr *expr)
+{
+	return (Expr *) preprocess_expression(root, (Node *) expr, EXPRKIND_PHV);
+}
+
+/*
  * inheritance_planner
  *	  Generate a plan in the case where the result relation is an
  *	  inheritance set.
@@ -821,8 +839,9 @@ inheritance_planner(PlannerInfo *root)
 		}
 
 		/* We needn't modify the child's append_rel_list */
-		/* There shouldn't be any OJ info to translate, as yet */
+		/* There shouldn't be any OJ or LATERAL info to translate, as yet */
 		Assert(subroot.join_info_list == NIL);
+		Assert(subroot.lateral_info_list == NIL);
 		/* and we haven't created PlaceHolderInfos, either */
 		Assert(subroot.placeholder_list == NIL);
 		/* hack to mark target relation as an inheritance partition */