Fix pull_varnos' miscomputation of relids set for a PlaceHolderVar.

Previously, pull_varnos() took the relids of a PlaceHolderVar as being
equal to the relids in its contents, but that fails to account for the
possibility that we have to postpone evaluation of the PHV due to outer
joins.  This could result in a malformed plan.  The known cases end up
triggering the "failed to assign all NestLoopParams to plan nodes"
sanity check in createplan.c, but other symptoms may be possible.

The right value to use is the join level we actually intend to evaluate
the PHV at.  We can get that from the ph_eval_at field of the associated
PlaceHolderInfo.  However, there are some places that call pull_varnos()
before the PlaceHolderInfos have been created; in that case, fall back
to the conservative assumption that the PHV will be evaluated at its
syntactic level.  (In principle this might result in missing some legal
optimization, but I'm not aware of any cases where it's an issue in
practice.)  Things are also a bit ticklish for calls occurring during
deconstruct_jointree(), but AFAICS the ph_eval_at fields should have
reached their final values by the time we need them.

The main problem in making this work is that pull_varnos() has no
way to get at the PlaceHolderInfos.  We can fix that easily, if a
bit tediously, in HEAD by passing it the planner "root" pointer.
In the back branches that'd cause an unacceptable API/ABI break for
extensions, so leave the existing entry points alone and add new ones
with the additional parameter.  (If an old entry point is called and
encounters a PHV, it'll fall back to using the syntactic level,
again possibly missing some valid optimization.)

Back-patch to v12.  The computation is surely also wrong before that,
but it appears that we cannot reach a bad plan thanks to join order
restrictions imposed on the subquery that the PlaceHolderVar came from.
The error only became reachable when commit 4be058fe9 allowed trivial
subqueries to be collapsed out completely, eliminating their join order
restrictions.

Per report from Stephan Springl.

Discussion: https://postgr.es/m/171041.1610849523@sss.pgh.pa.us

6 files changed, 131 insertions, 37 deletions

diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index a3ae2a02f77..e549ad150ae 100644
--- a/src/backend/optimizer/util/clauses.c
+++ b/src/backend/optimizer/util/clauses.c
@@ -54,6 +54,9 @@
 #include "utils/typcache.h"
 
 
+/* source-code-compatibility hacks for pull_varnos() API change */
+#define pull_varnos(a,b) pull_varnos_new(a,b)
+
 typedef struct
 {
 	PlannerInfo *root;
@@ -2182,7 +2185,13 @@ is_pseudo_constant_clause_relids(Node *clause, Relids relids)
 int
 NumRelids(Node *clause)
 {
-	Relids		varnos = pull_varnos(clause);
+	return NumRelids_new(NULL, clause);
+}
+
+int
+NumRelids_new(PlannerInfo *root, Node *clause)
+{
+	Relids		varnos = pull_varnos(root, clause);
 	int			result = bms_num_members(varnos);
 
 	bms_free(varnos);
diff --git a/src/backend/optimizer/util/inherit.c b/src/backend/optimizer/util/inherit.c
index 38bc61e6878..f0953475b1f 100644
--- a/src/backend/optimizer/util/inherit.c
+++ b/src/backend/optimizer/util/inherit.c
@@ -35,6 +35,9 @@
 #include "utils/rel.h"
 
 
+/* source-code-compatibility hacks for pull_varnos() API change */
+#define make_restrictinfo(a,b,c,d,e,f,g,h,i) make_restrictinfo_new(a,b,c,d,e,f,g,h,i)
+
 static void expand_partitioned_rtentry(PlannerInfo *root, RelOptInfo *relinfo,
 									   RangeTblEntry *parentrte,
 									   Index parentRTindex, Relation parentrel,
@@ -682,7 +685,8 @@ apply_child_basequals(PlannerInfo *root, RelOptInfo *parentrel,
 			}
 			/* reconstitute RestrictInfo with appropriate properties */
 			childquals = lappend(childquals,
-								 make_restrictinfo((Expr *) onecq,
+								 make_restrictinfo(root,
+												   (Expr *) onecq,
 												   rinfo->is_pushed_down,
 												   rinfo->outerjoin_delayed,
 												   pseudoconstant,
@@ -719,7 +723,7 @@ apply_child_basequals(PlannerInfo *root, RelOptInfo *parentrel,
 
 				/* not likely that we'd see constants here, so no check */
 				childquals = lappend(childquals,
-									 make_restrictinfo(qual,
+									 make_restrictinfo(root, qual,
 													   true, false, false,
 													   security_level,
 													   NULL, NULL, NULL));
diff --git a/src/backend/optimizer/util/orclauses.c b/src/backend/optimizer/util/orclauses.c
index 18ebc51bcac..d5b058c227e 100644
--- a/src/backend/optimizer/util/orclauses.c
+++ b/src/backend/optimizer/util/orclauses.c
@@ -24,6 +24,9 @@
 #include "optimizer/restrictinfo.h"
 
 
+/* source-code-compatibility hacks for pull_varnos() API change */
+#define make_restrictinfo(a,b,c,d,e,f,g,h,i) make_restrictinfo_new(a,b,c,d,e,f,g,h,i)
+
 static bool is_safe_restriction_clause_for(RestrictInfo *rinfo, RelOptInfo *rel);
 static Expr *extract_or_clause(RestrictInfo *or_rinfo, RelOptInfo *rel);
 static void consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel,
@@ -268,7 +271,8 @@ consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel,
 	 * Build a RestrictInfo from the new OR clause.  We can assume it's valid
 	 * as a base restriction clause.
 	 */
-	or_rinfo = make_restrictinfo(orclause,
+	or_rinfo = make_restrictinfo(root,
+								 orclause,
 								 true,
 								 false,
 								 false,
diff --git a/src/backend/optimizer/util/placeholder.c b/src/backend/optimizer/util/placeholder.c
index bbe6486287c..4cda433831a 100644
--- a/src/backend/optimizer/util/placeholder.c
+++ b/src/backend/optimizer/util/placeholder.c
@@ -23,6 +23,9 @@
 #include "optimizer/planmain.h"
 #include "utils/lsyscache.h"
 
+/* source-code-compatibility hacks for pull_varnos() API change */
+#define pull_varnos(a,b) pull_varnos_new(a,b)
+
 /* Local functions */
 static void find_placeholders_recurse(PlannerInfo *root, Node *jtnode);
 static void find_placeholders_in_expr(PlannerInfo *root, Node *expr);
@@ -98,7 +101,7 @@ find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv,
 	 * 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);
+	rels_used = pull_varnos(root, (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 */
diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c
index 3b50fd29ad6..2c3a6f2cf7c 100644
--- a/src/backend/optimizer/util/restrictinfo.c
+++ b/src/backend/optimizer/util/restrictinfo.c
@@ -21,7 +21,11 @@
 #include "optimizer/restrictinfo.h"
 
 
-static RestrictInfo *make_restrictinfo_internal(Expr *clause,
+/* source-code-compatibility hacks for pull_varnos() API change */
+#define pull_varnos(a,b) pull_varnos_new(a,b)
+
+static RestrictInfo *make_restrictinfo_internal(PlannerInfo *root,
+												Expr *clause,
 												Expr *orclause,
 												bool is_pushed_down,
 												bool outerjoin_delayed,
@@ -30,7 +34,8 @@ static RestrictInfo *make_restrictinfo_internal(Expr *clause,
 												Relids required_relids,
 												Relids outer_relids,
 												Relids nullable_relids);
-static Expr *make_sub_restrictinfos(Expr *clause,
+static Expr *make_sub_restrictinfos(PlannerInfo *root,
+									Expr *clause,
 									bool is_pushed_down,
 									bool outerjoin_delayed,
 									bool pseudoconstant,
@@ -65,12 +70,35 @@ make_restrictinfo(Expr *clause,
 				  Relids outer_relids,
 				  Relids nullable_relids)
 {
+	return make_restrictinfo_new(NULL,
+								 clause,
+								 is_pushed_down,
+								 outerjoin_delayed,
+								 pseudoconstant,
+								 security_level,
+								 required_relids,
+								 outer_relids,
+								 nullable_relids);
+}
+
+RestrictInfo *
+make_restrictinfo_new(PlannerInfo *root,
+					  Expr *clause,
+					  bool is_pushed_down,
+					  bool outerjoin_delayed,
+					  bool pseudoconstant,
+					  Index security_level,
+					  Relids required_relids,
+					  Relids outer_relids,
+					  Relids nullable_relids)
+{
 	/*
 	 * If it's an OR clause, build a modified copy with RestrictInfos inserted
 	 * above each subclause of the top-level AND/OR structure.
 	 */
 	if (is_orclause(clause))
-		return (RestrictInfo *) make_sub_restrictinfos(clause,
+		return (RestrictInfo *) make_sub_restrictinfos(root,
+													   clause,
 													   is_pushed_down,
 													   outerjoin_delayed,
 													   pseudoconstant,
@@ -82,7 +110,8 @@ make_restrictinfo(Expr *clause,
 	/* Shouldn't be an AND clause, else AND/OR flattening messed up */
 	Assert(!is_andclause(clause));
 
-	return make_restrictinfo_internal(clause,
+	return make_restrictinfo_internal(root,
+									  clause,
 									  NULL,
 									  is_pushed_down,
 									  outerjoin_delayed,
@@ -99,7 +128,8 @@ make_restrictinfo(Expr *clause,
  * Common code for the main entry points and the recursive cases.
  */
 static RestrictInfo *
-make_restrictinfo_internal(Expr *clause,
+make_restrictinfo_internal(PlannerInfo *root,
+						   Expr *clause,
 						   Expr *orclause,
 						   bool is_pushed_down,
 						   bool outerjoin_delayed,
@@ -137,8 +167,8 @@ make_restrictinfo_internal(Expr *clause,
 	 */
 	if (is_opclause(clause) && list_length(((OpExpr *) clause)->args) == 2)
 	{
-		restrictinfo->left_relids = pull_varnos(get_leftop(clause));
-		restrictinfo->right_relids = pull_varnos(get_rightop(clause));
+		restrictinfo->left_relids = pull_varnos(root, get_leftop(clause));
+		restrictinfo->right_relids = pull_varnos(root, get_rightop(clause));
 
 		restrictinfo->clause_relids = bms_union(restrictinfo->left_relids,
 												restrictinfo->right_relids);
@@ -165,7 +195,7 @@ make_restrictinfo_internal(Expr *clause,
 		restrictinfo->left_relids = NULL;
 		restrictinfo->right_relids = NULL;
 		/* and get the total relid set the hard way */
-		restrictinfo->clause_relids = pull_varnos((Node *) clause);
+		restrictinfo->clause_relids = pull_varnos(root, (Node *) clause);
 	}
 
 	/* required_relids defaults to clause_relids */
@@ -225,7 +255,8 @@ make_restrictinfo_internal(Expr *clause,
  * contained rels.
  */
 static Expr *
-make_sub_restrictinfos(Expr *clause,
+make_sub_restrictinfos(PlannerInfo *root,
+					   Expr *clause,
 					   bool is_pushed_down,
 					   bool outerjoin_delayed,
 					   bool pseudoconstant,
@@ -241,7 +272,8 @@ make_sub_restrictinfos(Expr *clause,
 
 		foreach(temp, ((BoolExpr *) clause)->args)
 			orlist = lappend(orlist,
-							 make_sub_restrictinfos(lfirst(temp),
+							 make_sub_restrictinfos(root,
+													lfirst(temp),
 													is_pushed_down,
 													outerjoin_delayed,
 													pseudoconstant,
@@ -249,7 +281,8 @@ make_sub_restrictinfos(Expr *clause,
 													NULL,
 													outer_relids,
 													nullable_relids));
-		return (Expr *) make_restrictinfo_internal(clause,
+		return (Expr *) make_restrictinfo_internal(root,
+												   clause,
 												   make_orclause(orlist),
 												   is_pushed_down,
 												   outerjoin_delayed,
@@ -266,7 +299,8 @@ make_sub_restrictinfos(Expr *clause,
 
 		foreach(temp, ((BoolExpr *) clause)->args)
 			andlist = lappend(andlist,
-							  make_sub_restrictinfos(lfirst(temp),
+							  make_sub_restrictinfos(root,
+													 lfirst(temp),
 													 is_pushed_down,
 													 outerjoin_delayed,
 													 pseudoconstant,
@@ -277,7 +311,8 @@ make_sub_restrictinfos(Expr *clause,
 		return make_andclause(andlist);
 	}
 	else
-		return (Expr *) make_restrictinfo_internal(clause,
+		return (Expr *) make_restrictinfo_internal(root,
+												   clause,
 												   NULL,
 												   is_pushed_down,
 												   outerjoin_delayed,
diff --git a/src/backend/optimizer/util/var.c b/src/backend/optimizer/util/var.c
index 15cc518a82e..58d093c1c11 100644
--- a/src/backend/optimizer/util/var.c
+++ b/src/backend/optimizer/util/var.c
@@ -23,6 +23,7 @@
 #include "access/sysattr.h"
 #include "nodes/nodeFuncs.h"
 #include "optimizer/optimizer.h"
+#include "optimizer/placeholder.h"
 #include "optimizer/prep.h"
 #include "parser/parsetree.h"
 #include "rewrite/rewriteManip.h"
@@ -31,6 +32,7 @@
 typedef struct
 {
 	Relids		varnos;
+	PlannerInfo *root;
 	int			sublevels_up;
 } pull_varnos_context;
 
@@ -94,9 +96,16 @@ static Relids alias_relid_set(Query *query, Relids relids);
 Relids
 pull_varnos(Node *node)
 {
+	return pull_varnos_new(NULL, node);
+}
+
+Relids
+pull_varnos_new(PlannerInfo *root, Node *node)
+{
 	pull_varnos_context context;
 
 	context.varnos = NULL;
+	context.root = root;
 	context.sublevels_up = 0;
 
 	/*
@@ -119,9 +128,16 @@ pull_varnos(Node *node)
 Relids
 pull_varnos_of_level(Node *node, int levelsup)
 {
+	return pull_varnos_of_level_new(NULL, node, levelsup);
+}
+
+Relids
+pull_varnos_of_level_new(PlannerInfo *root, Node *node, int levelsup)
+{
 	pull_varnos_context context;
 
 	context.varnos = NULL;
+	context.root = root;
 	context.sublevels_up = levelsup;
 
 	/*
@@ -159,33 +175,56 @@ pull_varnos_walker(Node *node, pull_varnos_context *context)
 	}
 	if (IsA(node, PlaceHolderVar))
 	{
-		/*
-		 * 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;
 
-		subcontext.varnos = NULL;
-		subcontext.sublevels_up = context->sublevels_up;
-		(void) pull_varnos_walker((Node *) phv->phexpr, &subcontext);
+		/*
+		 * If a PlaceHolderVar is not of the target query level, ignore it,
+		 * instead recursing into its expression to see if it contains any
+		 * vars that are of the target level.
+		 */
 		if (phv->phlevelsup == context->sublevels_up)
 		{
-			subcontext.varnos = bms_int_members(subcontext.varnos,
-												phv->phrels);
-			if (bms_is_empty(subcontext.varnos))
+			/*
+			 * Ideally, the PHV's contribution to context->varnos is its
+			 * ph_eval_at set.  However, this code can be invoked before
+			 * that's been computed.  If we cannot find a PlaceHolderInfo,
+			 * fall back to the conservative assumption that the PHV will be
+			 * evaluated at its syntactic level (phv->phrels).
+			 *
+			 * There is a second hazard: this code is also used to examine
+			 * qual clauses during deconstruct_jointree, when we may have a
+			 * PlaceHolderInfo but its ph_eval_at value is not yet final, so
+			 * that theoretically we could obtain a relid set that's smaller
+			 * than we'd see later on.  That should never happen though,
+			 * because we deconstruct the jointree working upwards.  Any outer
+			 * join that forces delay of evaluation of a given qual clause
+			 * will be processed before we examine that clause here, so the
+			 * ph_eval_at value should have been updated to include it.
+			 */
+			PlaceHolderInfo *phinfo = NULL;
+
+			if (phv->phlevelsup == 0 && context->root)
+			{
+				ListCell   *lc;
+
+				foreach(lc, context->root->placeholder_list)
+				{
+					phinfo = (PlaceHolderInfo *) lfirst(lc);
+					if (phinfo->phid == phv->phid)
+						break;
+					phinfo = NULL;
+				}
+			}
+			if (phinfo != NULL)
+				context->varnos = bms_add_members(context->varnos,
+												  phinfo->ph_eval_at);
+			else
 				context->varnos = bms_add_members(context->varnos,
 												  phv->phrels);
+			return false;		/* don't recurse into expression */
 		}
-		context->varnos = bms_join(context->varnos, subcontext.varnos);
-		return false;
 	}
-	if (IsA(node, Query))
+	else if (IsA(node, Query))
 	{
 		/* Recurse into RTE subquery or not-yet-planned sublink subquery */
 		bool		result;