Fix filtering of "cloned" outer-join quals some more.

We've had multiple issues with the clause_is_computable_at logic that
I introduced in 2489d76c4: it's been known to accept more than one
clone of the same qual at the same plan node, and also to accept no
clones at all.  It's looking impractical to get it 100% right on the
basis of the currently-stored information, so fix it by introducing a
new RestrictInfo field "incompatible_relids" that explicitly shows
which outer joins a given clone mustn't be pushed above.

In principle we could populate this field in every RestrictInfo, but
that would cost space and there doesn't presently seem to be a need
for it in general.  Also, while deconstruct_distribute_oj_quals can
easily fill the field with the remaining members of the commutative
join set that it's considering, computing it in the general case
seems again pretty complicated.  So for now, just fill it for
clone quals.

Along the way, fix a bug that may or may not be only latent:
equivclass.c was generating replacement clauses with is_pushed_down
and has_clone/is_clone markings that didn't match their
required_relids.  This led me to conclude that leaving the clone flags
out of make_restrictinfo's purview wasn't such a great idea after all,
so add them.

Per report from Richard Guo.

Discussion: https://postgr.es/m/CAMbWs48EYi_9-pSd0ORes1kTmTeAjT4Q3gu49hJtYCbSn2JyeA@mail.gmail.com

4 files changed, 60 insertions, 94 deletions

diff --git a/src/backend/optimizer/util/inherit.c b/src/backend/optimizer/util/inherit.c
index bae9688e461..94de855a227 100644
--- a/src/backend/optimizer/util/inherit.c
+++ b/src/backend/optimizer/util/inherit.c
@@ -894,9 +894,11 @@ apply_child_basequals(PlannerInfo *root, RelOptInfo *parentrel,
 								 make_restrictinfo(root,
 												   (Expr *) onecq,
 												   rinfo->is_pushed_down,
+												   rinfo->has_clone,
+												   rinfo->is_clone,
 												   pseudoconstant,
 												   rinfo->security_level,
-												   NULL, NULL));
+												   NULL, NULL, NULL));
 			/* track minimum security level among child quals */
 			cq_min_security = Min(cq_min_security, rinfo->security_level);
 		}
@@ -929,9 +931,11 @@ apply_child_basequals(PlannerInfo *root, RelOptInfo *parentrel,
 				/* not likely that we'd see constants here, so no check */
 				childquals = lappend(childquals,
 									 make_restrictinfo(root, qual,
-													   true, false,
+													   true,
+													   false, false,
+													   false,
 													   security_level,
-													   NULL, NULL));
+													   NULL, NULL, NULL));
 				cq_min_security = Min(cq_min_security, security_level);
 			}
 			security_level++;
diff --git a/src/backend/optimizer/util/orclauses.c b/src/backend/optimizer/util/orclauses.c
index ca8b5ff92fc..6ef9d14b902 100644
--- a/src/backend/optimizer/util/orclauses.c
+++ b/src/backend/optimizer/util/orclauses.c
@@ -267,8 +267,11 @@ consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel,
 								 orclause,
 								 true,
 								 false,
+								 false,
+								 false,
 								 join_or_rinfo->security_level,
 								 NULL,
+								 NULL,
 								 NULL);
 
 	/*
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 32a407f54b5..15e3910b79a 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -1346,27 +1346,21 @@ subbuild_joinrel_restrictlist(PlannerInfo *root,
 				Assert(!RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids));
 				if (!bms_is_subset(rinfo->required_relids, both_input_relids))
 					continue;
-				if (!clause_is_computable_at(root, rinfo, both_input_relids))
+				if (bms_overlap(rinfo->incompatible_relids, both_input_relids))
 					continue;
 			}
 			else
 			{
 				/*
 				 * For non-clone clauses, we just Assert it's OK.  These might
-				 * be either join or filter clauses.
+				 * be either join or filter clauses; if it's a join clause
+				 * then it should not refer to the current join's output.
+				 * (There is little point in checking incompatible_relids,
+				 * because it'll be NULL.)
 				 */
-#ifdef USE_ASSERT_CHECKING
-				if (RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids))
-					Assert(clause_is_computable_at(root, rinfo,
-												   joinrel->relids));
-				else
-				{
-					Assert(bms_is_subset(rinfo->required_relids,
-										 both_input_relids));
-					Assert(clause_is_computable_at(root, rinfo,
-												   both_input_relids));
-				}
-#endif
+				Assert(RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids) ||
+					   bms_is_subset(rinfo->required_relids,
+									 both_input_relids));
 			}
 
 			/*
diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c
index 760d24bebf3..d6d26a2b515 100644
--- a/src/backend/optimizer/util/restrictinfo.c
+++ b/src/backend/optimizer/util/restrictinfo.c
@@ -25,16 +25,22 @@ static RestrictInfo *make_restrictinfo_internal(PlannerInfo *root,
 												Expr *clause,
 												Expr *orclause,
 												bool is_pushed_down,
+												bool has_clone,
+												bool is_clone,
 												bool pseudoconstant,
 												Index security_level,
 												Relids required_relids,
+												Relids incompatible_relids,
 												Relids outer_relids);
 static Expr *make_sub_restrictinfos(PlannerInfo *root,
 									Expr *clause,
 									bool is_pushed_down,
+									bool has_clone,
+									bool is_clone,
 									bool pseudoconstant,
 									Index security_level,
 									Relids required_relids,
+									Relids incompatible_relids,
 									Relids outer_relids);
 
 
@@ -43,16 +49,12 @@ static Expr *make_sub_restrictinfos(PlannerInfo *root,
  *
  * Build a RestrictInfo node containing the given subexpression.
  *
- * The is_pushed_down and pseudoconstant flags for the
+ * The is_pushed_down, has_clone, is_clone, and pseudoconstant flags for the
  * RestrictInfo must be supplied by the caller, as well as the correct values
- * for security_level and outer_relids.
+ * for security_level, incompatible_relids, and outer_relids.
  * required_relids can be NULL, in which case it defaults to the actual clause
  * contents (i.e., clause_relids).
  *
- * Note that there aren't options to set the has_clone and is_clone flags:
- * we always initialize those to false.  There's just one place that wants
- * something different, so making all callers pass them seems inconvenient.
- *
  * We initialize fields that depend only on the given subexpression, leaving
  * others that depend on context (or may never be needed at all) to be filled
  * later.
@@ -61,9 +63,12 @@ RestrictInfo *
 make_restrictinfo(PlannerInfo *root,
 				  Expr *clause,
 				  bool is_pushed_down,
+				  bool has_clone,
+				  bool is_clone,
 				  bool pseudoconstant,
 				  Index security_level,
 				  Relids required_relids,
+				  Relids incompatible_relids,
 				  Relids outer_relids)
 {
 	/*
@@ -74,9 +79,12 @@ make_restrictinfo(PlannerInfo *root,
 		return (RestrictInfo *) make_sub_restrictinfos(root,
 													   clause,
 													   is_pushed_down,
+													   has_clone,
+													   is_clone,
 													   pseudoconstant,
 													   security_level,
 													   required_relids,
+													   incompatible_relids,
 													   outer_relids);
 
 	/* Shouldn't be an AND clause, else AND/OR flattening messed up */
@@ -86,9 +94,12 @@ make_restrictinfo(PlannerInfo *root,
 									  clause,
 									  NULL,
 									  is_pushed_down,
+									  has_clone,
+									  is_clone,
 									  pseudoconstant,
 									  security_level,
 									  required_relids,
+									  incompatible_relids,
 									  outer_relids);
 }
 
@@ -102,9 +113,12 @@ make_restrictinfo_internal(PlannerInfo *root,
 						   Expr *clause,
 						   Expr *orclause,
 						   bool is_pushed_down,
+						   bool has_clone,
+						   bool is_clone,
 						   bool pseudoconstant,
 						   Index security_level,
 						   Relids required_relids,
+						   Relids incompatible_relids,
 						   Relids outer_relids)
 {
 	RestrictInfo *restrictinfo = makeNode(RestrictInfo);
@@ -114,10 +128,11 @@ make_restrictinfo_internal(PlannerInfo *root,
 	restrictinfo->orclause = orclause;
 	restrictinfo->is_pushed_down = is_pushed_down;
 	restrictinfo->pseudoconstant = pseudoconstant;
-	restrictinfo->has_clone = false;	/* may get set by caller */
-	restrictinfo->is_clone = false; /* may get set by caller */
+	restrictinfo->has_clone = has_clone;
+	restrictinfo->is_clone = is_clone;
 	restrictinfo->can_join = false; /* may get set below */
 	restrictinfo->security_level = security_level;
+	restrictinfo->incompatible_relids = incompatible_relids;
 	restrictinfo->outer_relids = outer_relids;
 
 	/*
@@ -244,9 +259,9 @@ make_restrictinfo_internal(PlannerInfo *root,
  * implicit-AND lists at top level of RestrictInfo lists.  Only ORs and
  * simple clauses are valid RestrictInfos.
  *
- * The same is_pushed_down and pseudoconstant flag
+ * The same is_pushed_down, has_clone, is_clone, and pseudoconstant flag
  * values can be applied to all RestrictInfo nodes in the result.  Likewise
- * for security_level and outer_relids.
+ * for security_level, incompatible_relids, and outer_relids.
  *
  * The given required_relids are attached to our top-level output,
  * but any OR-clause constituents are allowed to default to just the
@@ -256,9 +271,12 @@ static Expr *
 make_sub_restrictinfos(PlannerInfo *root,
 					   Expr *clause,
 					   bool is_pushed_down,
+					   bool has_clone,
+					   bool is_clone,
 					   bool pseudoconstant,
 					   Index security_level,
 					   Relids required_relids,
+					   Relids incompatible_relids,
 					   Relids outer_relids)
 {
 	if (is_orclause(clause))
@@ -271,17 +289,23 @@ make_sub_restrictinfos(PlannerInfo *root,
 							 make_sub_restrictinfos(root,
 													lfirst(temp),
 													is_pushed_down,
+													has_clone,
+													is_clone,
 													pseudoconstant,
 													security_level,
 													NULL,
+													incompatible_relids,
 													outer_relids));
 		return (Expr *) make_restrictinfo_internal(root,
 												   clause,
 												   make_orclause(orlist),
 												   is_pushed_down,
+												   has_clone,
+												   is_clone,
 												   pseudoconstant,
 												   security_level,
 												   required_relids,
+												   incompatible_relids,
 												   outer_relids);
 	}
 	else if (is_andclause(clause))
@@ -294,9 +318,12 @@ make_sub_restrictinfos(PlannerInfo *root,
 							  make_sub_restrictinfos(root,
 													 lfirst(temp),
 													 is_pushed_down,
+													 has_clone,
+													 is_clone,
 													 pseudoconstant,
 													 security_level,
 													 required_relids,
+													 incompatible_relids,
 													 outer_relids));
 		return make_andclause(andlist);
 	}
@@ -305,9 +332,12 @@ make_sub_restrictinfos(PlannerInfo *root,
 												   clause,
 												   NULL,
 												   is_pushed_down,
+												   has_clone,
+												   is_clone,
 												   pseudoconstant,
 												   security_level,
 												   required_relids,
+												   incompatible_relids,
 												   outer_relids);
 }
 
@@ -513,78 +543,13 @@ extract_actual_join_clauses(List *restrictinfo_list,
 		{
 			/* joinquals shouldn't have been marked pseudoconstant */
 			Assert(!rinfo->pseudoconstant);
-			Assert(!rinfo_is_constant_true(rinfo));
-			*joinquals = lappend(*joinquals, rinfo->clause);
+			if (!rinfo_is_constant_true(rinfo))
+				*joinquals = lappend(*joinquals, rinfo->clause);
 		}
 	}
 }
 
 /*
- * clause_is_computable_at
- *		Test whether a clause is computable at a given evaluation level.
- *
- * There are two conditions for whether an expression can actually be
- * evaluated at a given join level: the evaluation context must include
- * all the relids (both base and OJ) used by the expression, and we must
- * not have already evaluated any outer joins that null Vars/PHVs of the
- * expression and are not listed in their nullingrels.
- *
- * This function checks the second condition; we assume the caller already
- * saw to the first one.
- *
- * For speed reasons, we don't individually examine each Var/PHV of the
- * expression, but just look at the overall clause_relids (the union of the
- * varnos and varnullingrels).  This could give a misleading answer if the
- * Vars of a given varno don't all have the same varnullingrels; but that
- * really shouldn't happen within a single scalar expression or RestrictInfo
- * clause.  Despite that, this is still annoyingly expensive :-(
- */
-bool
-clause_is_computable_at(PlannerInfo *root,
-						RestrictInfo *rinfo,
-						Relids eval_relids)
-{
-	Relids		clause_relids;
-	ListCell   *lc;
-
-	/* Nothing to do if no outer joins have been performed yet. */
-	if (!bms_overlap(eval_relids, root->outer_join_rels))
-		return true;
-
-	/*
-	 * For an ordinary qual clause, we consider the actual clause_relids as
-	 * explained above.  However, it's possible for multiple members of a
-	 * group of clone quals to have the same clause_relids, so for clones use
-	 * the required_relids instead to ensure we select just one of them.
-	 */
-	if (rinfo->has_clone || rinfo->is_clone)
-		clause_relids = rinfo->required_relids;
-	else
-		clause_relids = rinfo->clause_relids;
-
-	foreach(lc, root->join_info_list)
-	{
-		SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
-
-		/* Ignore outer joins that are not yet performed. */
-		if (!bms_is_member(sjinfo->ojrelid, eval_relids))
-			continue;
-
-		/* OK if clause lists it (we assume all Vars in it agree). */
-		if (bms_is_member(sjinfo->ojrelid, clause_relids))
-			continue;
-
-		/* Else, trouble if clause mentions any nullable Vars. */
-		if (bms_overlap(clause_relids, sjinfo->min_righthand) ||
-			(sjinfo->jointype == JOIN_FULL &&
-			 bms_overlap(clause_relids, sjinfo->min_lefthand)))
-			return false;		/* doesn't work */
-	}
-
-	return true;				/* OK */
-}
-
-/*
  * join_clause_is_movable_to
  *		Test whether a join clause is a safe candidate for parameterization
  *		of a scan on the specified base relation.