Fix planner problems with LATERAL references in PlaceHolderVars.

The planner largely failed to consider the possibility that a
PlaceHolderVar's expression might contain a lateral reference to a Var
coming from somewhere outside the PHV's syntactic scope.  We had a previous
report of a problem in this area, which I tried to fix in a quick-hack way
in commit 4da6439bd8553059766011e2a42c6e39df08717f, but Antonin Houska
pointed out that there were still some problems, and investigation turned
up other issues.  This patch largely reverts that commit in favor of a more
thoroughly thought-through solution.  The new theory is that a PHV's
ph_eval_at level cannot be higher than its original syntactic level.  If it
contains lateral references, those don't change the ph_eval_at level, but
rather they create a lateral-reference requirement for the ph_eval_at join
relation.  The code in joinpath.c needs to handle that.

Another issue is that createplan.c wasn't handling nested PlaceHolderVars
properly.

In passing, push knowledge of lateral-reference checks for join clauses
into join_clause_is_movable_to.  This is mainly so that FDWs don't need
to deal with it.

This patch doesn't fix the original join-qual-placement problem reported by
Jeremy Evans (and indeed, one of the new regression test cases shows the
wrong answer because of that).  But the PlaceHolderVar problems need to be
fixed before that issue can be addressed, so committing this separately
seems reasonable.

4 files changed, 124 insertions, 38 deletions

diff --git a/src/backend/optimizer/util/placeholder.c b/src/backend/optimizer/util/placeholder.c
index da92497689b..5049ba1c5a9 100644
--- a/src/backend/optimizer/util/placeholder.c
+++ b/src/backend/optimizer/util/placeholder.c
@@ -69,6 +69,7 @@ find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv,
 					  bool create_new_ph)
 {
 	PlaceHolderInfo *phinfo;
+	Relids		rels_used;
 	ListCell   *lc;
 
 	/* if this ever isn't true, we'd need to be able to look in parent lists */
@@ -89,8 +90,24 @@ find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv,
 
 	phinfo->phid = phv->phid;
 	phinfo->ph_var = copyObject(phv);
-	/* initialize ph_eval_at as the set of contained relids */
-	phinfo->ph_eval_at = pull_varnos((Node *) phv);
+
+	/*
+	 * Any referenced rels that are outside the PHV's syntactic scope are
+	 * LATERAL references, which should be included in ph_lateral but not in
+	 * ph_eval_at.	If no referenced rels are within the syntactic scope,
+	 * force evaluation at the syntactic location.
+	 */
+	rels_used = pull_varnos((Node *) phv->phexpr);
+	phinfo->ph_lateral = bms_difference(rels_used, phv->phrels);
+	if (bms_is_empty(phinfo->ph_lateral))
+		phinfo->ph_lateral = NULL;		/* make it exactly NULL if empty */
+	phinfo->ph_eval_at = bms_int_members(rels_used, phv->phrels);
+	/* If no contained vars, force evaluation at syntactic location */
+	if (bms_is_empty(phinfo->ph_eval_at))
+	{
+		phinfo->ph_eval_at = bms_copy(phv->phrels);
+		Assert(!bms_is_empty(phinfo->ph_eval_at));
+	}
 	/* ph_eval_at may change later, see update_placeholder_eval_levels */
 	phinfo->ph_needed = NULL;	/* initially it's unused */
 	/* for the moment, estimate width using just the datatype info */
@@ -115,6 +132,12 @@ find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv,
  *
  * We don't need to look at the targetlist because build_base_rel_tlists()
  * will already have made entries for any PHVs in the tlist.
+ *
+ * This is called before we begin deconstruct_jointree.  Once we begin
+ * deconstruct_jointree, all active placeholders must be present in
+ * root->placeholder_list, because make_outerjoininfo and
+ * update_placeholder_eval_levels require this info to be available
+ * while we crawl up the join tree.
  */
 void
 find_placeholders_in_jointree(PlannerInfo *root)
@@ -219,7 +242,7 @@ find_placeholders_in_expr(PlannerInfo *root, Node *expr)
  * The initial eval_at level set by find_placeholder_info was the set of
  * rels used in the placeholder's expression (or the whole subselect below
  * the placeholder's syntactic location, if the expr is variable-free).
- * If the subselect contains any outer joins that can null any of those rels,
+ * If the query contains any outer joins that can null any of those rels,
  * we must delay evaluation to above those joins.
  *
  * We repeat this operation each time we add another outer join to
@@ -299,6 +322,9 @@ update_placeholder_eval_levels(PlannerInfo *root, SpecialJoinInfo *new_sjinfo)
 			}
 		} while (found_some);
 
+		/* Can't move the PHV's eval_at level to above its syntactic level */
+		Assert(bms_is_subset(eval_at, syn_level));
+
 		phinfo->ph_eval_at = eval_at;
 	}
 }
@@ -309,11 +335,14 @@ update_placeholder_eval_levels(PlannerInfo *root, SpecialJoinInfo *new_sjinfo)
  *
  * This is called after we've finished determining the eval_at levels for
  * all placeholders.  We need to make sure that all vars and placeholders
- * needed to evaluate each placeholder will be available at the join level
- * where the evaluation will be done.  Note that this loop can have
- * side-effects on the ph_needed sets of other PlaceHolderInfos; that's okay
- * because we don't examine ph_needed here, so there are no ordering issues
- * to worry about.
+ * needed to evaluate each placeholder will be available at the scan or join
+ * level where the evaluation will be done.  (It might seem that scan-level
+ * evaluations aren't interesting, but that's not so: a LATERAL reference
+ * within a placeholder's expression needs to cause the referenced var or
+ * placeholder to be marked as needed in the scan where it's evaluated.)
+ * Note that this loop can have side-effects on the ph_needed sets of other
+ * PlaceHolderInfos; that's okay because we don't examine ph_needed here, so
+ * there are no ordering issues to worry about.
  */
 void
 fix_placeholder_input_needed_levels(PlannerInfo *root)
@@ -323,27 +352,23 @@ fix_placeholder_input_needed_levels(PlannerInfo *root)
 	foreach(lc, root->placeholder_list)
 	{
 		PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
-		Relids		eval_at = phinfo->ph_eval_at;
-
-		/* No work unless it'll be evaluated above baserel level */
-		if (bms_membership(eval_at) == BMS_MULTIPLE)
-		{
-			List	   *vars = pull_var_clause((Node *) phinfo->ph_var->phexpr,
-											   PVC_RECURSE_AGGREGATES,
-											   PVC_INCLUDE_PLACEHOLDERS);
+		List	   *vars = pull_var_clause((Node *) phinfo->ph_var->phexpr,
+										   PVC_RECURSE_AGGREGATES,
+										   PVC_INCLUDE_PLACEHOLDERS);
 
-			add_vars_to_targetlist(root, vars, eval_at, false);
-			list_free(vars);
-		}
+		add_vars_to_targetlist(root, vars, phinfo->ph_eval_at, false);
+		list_free(vars);
 	}
 }
 
 /*
  * add_placeholders_to_base_rels
- *		Add any required PlaceHolderVars to base rels' targetlists.
+ *		Add any required PlaceHolderVars to base rels' targetlists, and
+ *		update lateral_vars lists for lateral references contained in them.
  *
  * If any placeholder can be computed at a base rel and is needed above it,
- * add it to that rel's targetlist.  This might look like it could be merged
+ * add it to that rel's targetlist, and add any lateral references it requires
+ * to the rel's lateral_vars list.  This might look like it could be merged
  * with fix_placeholder_input_needed_levels, but it must be separate because
  * join removal happens in between, and can change the ph_eval_at sets.  There
  * is essentially the same logic in add_placeholders_to_joinrel, but we can't
@@ -359,14 +384,52 @@ add_placeholders_to_base_rels(PlannerInfo *root)
 		PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
 		Relids		eval_at = phinfo->ph_eval_at;
 
-		if (bms_membership(eval_at) == BMS_SINGLETON &&
-			bms_nonempty_difference(phinfo->ph_needed, eval_at))
+		if (bms_membership(eval_at) == BMS_SINGLETON)
 		{
 			int			varno = bms_singleton_member(eval_at);
 			RelOptInfo *rel = find_base_rel(root, varno);
 
-			rel->reltargetlist = lappend(rel->reltargetlist,
-										 copyObject(phinfo->ph_var));
+			/* add it to reltargetlist if needed above the rel scan level */
+			if (bms_nonempty_difference(phinfo->ph_needed, eval_at))
+				rel->reltargetlist = lappend(rel->reltargetlist,
+											 copyObject(phinfo->ph_var));
+			/* if there are lateral refs in it, add them to lateral_vars */
+			if (phinfo->ph_lateral != NULL)
+			{
+				List	   *vars = pull_var_clause((Node *) phinfo->ph_var->phexpr,
+												   PVC_RECURSE_AGGREGATES,
+												   PVC_INCLUDE_PLACEHOLDERS);
+				ListCell   *lc2;
+
+				foreach(lc2, vars)
+				{
+					Node	   *node = (Node *) lfirst(lc2);
+
+					if (IsA(node, Var))
+					{
+						Var		   *var = (Var *) node;
+
+						if (var->varno != varno)
+							rel->lateral_vars = lappend(rel->lateral_vars,
+														var);
+					}
+					else if (IsA(node, PlaceHolderVar))
+					{
+						PlaceHolderVar *other_phv = (PlaceHolderVar *) node;
+						PlaceHolderInfo *other_phi;
+
+						other_phi = find_placeholder_info(root, other_phv,
+														  false);
+						if (!bms_is_subset(other_phi->ph_eval_at, eval_at))
+							rel->lateral_vars = lappend(rel->lateral_vars,
+														other_phv);
+					}
+					else
+						Assert(false);
+				}
+
+				list_free(vars);
+			}
 		}
 	}
 }
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 8ee5671a551..b6265b31675 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -113,6 +113,7 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptKind reloptkind)
 	/* min_attr, max_attr, attr_needed, attr_widths are set below */
 	rel->lateral_vars = NIL;
 	rel->lateral_relids = NULL;
+	rel->lateral_referencers = NULL;
 	rel->indexlist = NIL;
 	rel->pages = 0;
 	rel->tuples = 0;
@@ -374,6 +375,7 @@ build_join_rel(PlannerInfo *root,
 	joinrel->attr_widths = NULL;
 	joinrel->lateral_vars = NIL;
 	joinrel->lateral_relids = NULL;
+	joinrel->lateral_referencers = NULL;
 	joinrel->indexlist = NIL;
 	joinrel->pages = 0;
 	joinrel->tuples = 0;
diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c
index cd7109b687b..33b029b0e4e 100644
--- a/src/backend/optimizer/util/restrictinfo.c
+++ b/src/backend/optimizer/util/restrictinfo.c
@@ -651,24 +651,32 @@ extract_actual_join_clauses(List *restrictinfo_list,
  * outer join, as that would change the results (rows would be suppressed
  * rather than being null-extended).
  *
- * And the target relation must not be in the clause's nullable_relids, i.e.,
+ * Also the target relation must not be in the clause's nullable_relids, i.e.,
  * there must not be an outer join below the clause that would null the Vars
  * coming from the target relation.  Otherwise the clause might give results
  * different from what it would give at its normal semantic level.
+ *
+ * Also, the join clause must not use any relations that have LATERAL
+ * references to the target relation, since we could not put such rels on
+ * the outer side of a nestloop with the target relation.
  */
 bool
-join_clause_is_movable_to(RestrictInfo *rinfo, Index baserelid)
+join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
 {
 	/* Clause must physically reference target rel */
-	if (!bms_is_member(baserelid, rinfo->clause_relids))
+	if (!bms_is_member(baserel->relid, rinfo->clause_relids))
 		return false;
 
 	/* Cannot move an outer-join clause into the join's outer side */
-	if (bms_is_member(baserelid, rinfo->outer_relids))
+	if (bms_is_member(baserel->relid, rinfo->outer_relids))
 		return false;
 
 	/* Target rel must not be nullable below the clause */
-	if (bms_is_member(baserelid, rinfo->nullable_relids))
+	if (bms_is_member(baserel->relid, rinfo->nullable_relids))
+		return false;
+
+	/* Clause must not use any rels with LATERAL references to this rel */
+	if (bms_overlap(baserel->lateral_referencers, rinfo->clause_relids))
 		return false;
 
 	return true;
@@ -695,6 +703,11 @@ join_clause_is_movable_to(RestrictInfo *rinfo, Index baserelid)
  * not pushing the clause into its outer-join outer side, nor down into
  * a lower outer join's inner side.
  *
+ * There's no check here equivalent to join_clause_is_movable_to's test on
+ * lateral_relids.	We assume the caller wouldn't be inquiring unless it'd
+ * verified that the proposed outer rels don't have lateral references to
+ * the current rel(s).
+ *
  * Note: get_joinrel_parampathinfo depends on the fact that if
  * current_and_outer is NULL, this function will always return false
  * (since one or the other of the first two tests must fail).
diff --git a/src/backend/optimizer/util/var.c b/src/backend/optimizer/util/var.c
index 5f736ad6c40..4a3d5c8408e 100644
--- a/src/backend/optimizer/util/var.c
+++ b/src/backend/optimizer/util/var.c
@@ -161,8 +161,13 @@ pull_varnos_walker(Node *node, pull_varnos_context *context)
 	if (IsA(node, PlaceHolderVar))
 	{
 		/*
-		 * Normally, we can just take the varnos in the contained expression.
-		 * But if it is variable-free, use the PHV's syntactic relids.
+		 * A PlaceHolderVar acts as a variable of its syntactic scope, or
+		 * lower than that if it references only a subset of the rels in its
+		 * syntactic scope.  It might also contain lateral references, but we
+		 * should ignore such references when computing the set of varnos in
+		 * an expression tree.	Also, if the PHV contains no variables within
+		 * its syntactic scope, it will be forced to be evaluated exactly at
+		 * the syntactic scope, so take that as the relid set.
 		 */
 		PlaceHolderVar *phv = (PlaceHolderVar *) node;
 		pull_varnos_context subcontext;
@@ -170,12 +175,15 @@ pull_varnos_walker(Node *node, pull_varnos_context *context)
 		subcontext.varnos = NULL;
 		subcontext.sublevels_up = context->sublevels_up;
 		(void) pull_varnos_walker((Node *) phv->phexpr, &subcontext);
-
-		if (bms_is_empty(subcontext.varnos) &&
-			phv->phlevelsup == context->sublevels_up)
-			context->varnos = bms_add_members(context->varnos, phv->phrels);
-		else
-			context->varnos = bms_join(context->varnos, subcontext.varnos);
+		if (phv->phlevelsup == context->sublevels_up)
+		{
+			subcontext.varnos = bms_int_members(subcontext.varnos,
+												phv->phrels);
+			if (bms_is_empty(subcontext.varnos))
+				context->varnos = bms_add_members(context->varnos,
+												  phv->phrels);
+		}
+		context->varnos = bms_join(context->varnos, subcontext.varnos);
 		return false;
 	}
 	if (IsA(node, Query))