Make Vars be outer-join-aware.

Traditionally we used the same Var struct to represent the value
of a table column everywhere in parse and plan trees.  This choice
predates our support for SQL outer joins, and it's really a pretty
bad idea with outer joins, because the Var's value can depend on
where it is in the tree: it might go to NULL above an outer join.
So expression nodes that are equal() per equalfuncs.c might not
represent the same value, which is a huge correctness hazard for
the planner.

To improve this, decorate Var nodes with a bitmapset showing
which outer joins (identified by RTE indexes) may have nulled
them at the point in the parse tree where the Var appears.
This allows us to trust that equal() Vars represent the same value.
A certain amount of klugery is still needed to cope with cases
where we re-order two outer joins, but it's possible to make it
work without sacrificing that core principle.  PlaceHolderVars
receive similar decoration for the same reason.

In the planner, we include these outer join bitmapsets into the relids
that an expression is considered to depend on, and in consequence also
add outer-join relids to the relids of join RelOptInfos.  This allows
us to correctly perceive whether an expression can be calculated above
or below a particular outer join.

This change affects FDWs that want to plan foreign joins.  They *must*
follow suit when labeling foreign joins in order to match with the
core planner, but for many purposes (if postgres_fdw is any guide)
they'd prefer to consider only base relations within the join.
To support both requirements, redefine ForeignScan.fs_relids as
base+OJ relids, and add a new field fs_base_relids that's set up by
the core planner.

Large though it is, this commit just does the minimum necessary to
install the new mechanisms and get check-world passing again.
Follow-up patches will perform some cleanup.  (The README additions
and comments mention some stuff that will appear in the follow-up.)

Patch by me; thanks to Richard Guo for review.

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

1 files changed, 119 insertions, 4 deletions

diff --git a/src/backend/optimizer/util/placeholder.c b/src/backend/optimizer/util/placeholder.c
index 72b9977022b..af10dbd124f 100644
--- a/src/backend/optimizer/util/placeholder.c
+++ b/src/backend/optimizer/util/placeholder.c
@@ -23,17 +23,32 @@
 #include "optimizer/planmain.h"
 #include "utils/lsyscache.h"
 
+
+typedef struct contain_placeholder_references_context
+{
+	int			relid;
+	int			sublevels_up;
+} contain_placeholder_references_context;
+
 /* Local functions */
 static void find_placeholders_recurse(PlannerInfo *root, Node *jtnode);
 static void find_placeholders_in_expr(PlannerInfo *root, Node *expr);
+static bool contain_placeholder_references_walker(Node *node,
+												  contain_placeholder_references_context *context);
 
 
 /*
  * make_placeholder_expr
  *		Make a PlaceHolderVar for the given expression.
  *
- * phrels is the syntactic location (as a set of baserels) to attribute
+ * phrels is the syntactic location (as a set of relids) to attribute
  * to the expression.
+ *
+ * The caller is responsible for adjusting phlevelsup and phnullingrels
+ * as needed.  Because we do not know here which query level the PHV
+ * will be associated with, it's important that this function touches
+ * only root->glob; messing with other parts of PlannerInfo would be
+ * likely to do the wrong thing.
  */
 PlaceHolderVar *
 make_placeholder_expr(PlannerInfo *root, Expr *expr, Relids phrels)
@@ -42,8 +57,9 @@ make_placeholder_expr(PlannerInfo *root, Expr *expr, Relids phrels)
 
 	phv->phexpr = expr;
 	phv->phrels = phrels;
+	phv->phnullingrels = NULL;	/* caller may change this later */
 	phv->phid = ++(root->glob->lastPHId);
-	phv->phlevelsup = 0;
+	phv->phlevelsup = 0;		/* caller may change this later */
 
 	return phv;
 }
@@ -93,6 +109,15 @@ find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv)
 	phinfo->ph_var = copyObject(phv);
 
 	/*
+	 * By convention, phinfo->ph_var->phnullingrels is always empty, since the
+	 * PlaceHolderInfo represents the initially-calculated state of the
+	 * PlaceHolderVar.  PlaceHolderVars appearing in the query tree might have
+	 * varying values of phnullingrels, reflecting outer joins applied above
+	 * the calculation level.
+	 */
+	phinfo->ph_var->phnullingrels = NULL;
+
+	/*
 	 * 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,
@@ -339,6 +364,8 @@ update_placeholder_eval_levels(PlannerInfo *root, SpecialJoinInfo *new_sjinfo)
 												  sjinfo->min_lefthand);
 						eval_at = bms_add_members(eval_at,
 												  sjinfo->min_righthand);
+						if (sjinfo->ojrelid)
+							eval_at = bms_add_member(eval_at, sjinfo->ojrelid);
 						/* we'll need another iteration */
 						found_some = true;
 					}
@@ -413,6 +440,14 @@ add_placeholders_to_base_rels(PlannerInfo *root)
 		{
 			RelOptInfo *rel = find_base_rel(root, varno);
 
+			/*
+			 * As in add_vars_to_targetlist(), a value computed at scan level
+			 * has not yet been nulled by any outer join, so its phnullingrels
+			 * should be empty.
+			 */
+			Assert(phinfo->ph_var->phnullingrels == NULL);
+
+			/* Copying the PHV might be unnecessary here, but be safe */
 			rel->reltarget->exprs = lappend(rel->reltarget->exprs,
 											copyObject(phinfo->ph_var));
 			/* reltarget's cost and width fields will be updated later */
@@ -435,7 +470,8 @@ add_placeholders_to_base_rels(PlannerInfo *root)
  */
 void
 add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
-							RelOptInfo *outer_rel, RelOptInfo *inner_rel)
+							RelOptInfo *outer_rel, RelOptInfo *inner_rel,
+							SpecialJoinInfo *sjinfo)
 {
 	Relids		relids = joinrel->relids;
 	ListCell   *lc;
@@ -466,9 +502,17 @@ add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
 				if (!bms_is_subset(phinfo->ph_eval_at, outer_rel->relids) &&
 					!bms_is_subset(phinfo->ph_eval_at, inner_rel->relids))
 				{
-					PlaceHolderVar *phv = phinfo->ph_var;
+					/* Copying might be unnecessary here, but be safe */
+					PlaceHolderVar *phv = copyObject(phinfo->ph_var);
 					QualCost	cost;
 
+					/*
+					 * It'll start out not nulled by anything.  Joins above
+					 * this one might add to its phnullingrels later, in much
+					 * the same way as for Vars.
+					 */
+					Assert(phv->phnullingrels == NULL);
+
 					joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs,
 														phv);
 					cost_qual_eval_node(&cost, (Node *) phv->phexpr, root);
@@ -499,3 +543,74 @@ add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
 		}
 	}
 }
+
+/*
+ * contain_placeholder_references_to
+ *		Detect whether any PlaceHolderVars in the given clause contain
+ *		references to the given relid (typically an OJ relid).
+ *
+ * "Contain" means that there's a use of the relid inside the PHV's
+ * contained expression, so that changing the nullability status of
+ * the rel might change what the PHV computes.
+ *
+ * The code here to cope with upper-level PHVs is likely dead, but keep it
+ * anyway just in case.
+ */
+bool
+contain_placeholder_references_to(PlannerInfo *root, Node *clause,
+								  int relid)
+{
+	contain_placeholder_references_context context;
+
+	/* We can answer quickly in the common case that there's no PHVs at all */
+	if (root->glob->lastPHId == 0)
+		return false;
+	/* Else run the recursive search */
+	context.relid = relid;
+	context.sublevels_up = 0;
+	return contain_placeholder_references_walker(clause, &context);
+}
+
+static bool
+contain_placeholder_references_walker(Node *node,
+									  contain_placeholder_references_context *context)
+{
+	if (node == NULL)
+		return false;
+	if (IsA(node, PlaceHolderVar))
+	{
+		PlaceHolderVar *phv = (PlaceHolderVar *) node;
+
+		/* We should just look through PHVs of other query levels */
+		if (phv->phlevelsup == context->sublevels_up)
+		{
+			/* If phrels matches, we found what we came for */
+			if (bms_is_member(context->relid, phv->phrels))
+				return true;
+
+			/*
+			 * We should not examine phnullingrels: what we are looking for is
+			 * references in the contained expression, not OJs that might null
+			 * the result afterwards.  Also, we don't need to recurse into the
+			 * contained expression, because phrels should adequately
+			 * summarize what's in there.  So we're done here.
+			 */
+			return false;
+		}
+	}
+	else if (IsA(node, Query))
+	{
+		/* Recurse into RTE subquery or not-yet-planned sublink subquery */
+		bool		result;
+
+		context->sublevels_up++;
+		result = query_tree_walker((Query *) node,
+								   contain_placeholder_references_walker,
+								   context,
+								   0);
+		context->sublevels_up--;
+		return result;
+	}
+	return expression_tree_walker(node, contain_placeholder_references_walker,
+								  context);
+}