Adding upstream version 14.5.upstream/14.5upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 2751 insertions, 0 deletions

diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
new file mode 100644
index 0000000..276e62b
--- /dev/null
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -0,0 +1,2751 @@
+/*-------------------------------------------------------------------------
+ *
+ * initsplan.c
+ *	  Target list, qualification, joininfo initialization routines
+ *
+ * Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *	  src/backend/optimizer/plan/initsplan.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "catalog/pg_class.h"
+#include "catalog/pg_type.h"
+#include "nodes/makefuncs.h"
+#include "nodes/nodeFuncs.h"
+#include "optimizer/clauses.h"
+#include "optimizer/cost.h"
+#include "optimizer/inherit.h"
+#include "optimizer/joininfo.h"
+#include "optimizer/optimizer.h"
+#include "optimizer/pathnode.h"
+#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 "parser/analyze.h"
+#include "rewrite/rewriteManip.h"
+#include "utils/lsyscache.h"
+#include "utils/typcache.h"
+
+/* These parameters are set by GUC */
+int			from_collapse_limit;
+int			join_collapse_limit;
+
+
+/* Elements of the postponed_qual_list used during deconstruct_recurse */
+typedef struct PostponedQual
+{
+	Node	   *qual;			/* a qual clause waiting to be processed */
+	Relids		relids;			/* the set of baserels it references */
+} PostponedQual;
+
+
+static void extract_lateral_references(PlannerInfo *root, RelOptInfo *brel,
+									   Index rtindex);
+static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode,
+								 bool below_outer_join,
+								 Relids *qualscope, Relids *inner_join_rels,
+								 List **postponed_qual_list);
+static void process_security_barrier_quals(PlannerInfo *root,
+										   int rti, Relids qualscope,
+										   bool below_outer_join);
+static SpecialJoinInfo *make_outerjoininfo(PlannerInfo *root,
+										   Relids left_rels, Relids right_rels,
+										   Relids inner_join_rels,
+										   JoinType jointype, List *clause);
+static void compute_semijoin_info(PlannerInfo *root, SpecialJoinInfo *sjinfo,
+								  List *clause);
+static void distribute_qual_to_rels(PlannerInfo *root, Node *clause,
+									bool below_outer_join,
+									JoinType jointype,
+									Index security_level,
+									Relids qualscope,
+									Relids ojscope,
+									Relids outerjoin_nonnullable,
+									List **postponed_qual_list);
+static bool check_outerjoin_delay(PlannerInfo *root, Relids *relids_p,
+								  Relids *nullable_relids_p, bool is_pushed_down);
+static bool check_equivalence_delay(PlannerInfo *root,
+									RestrictInfo *restrictinfo);
+static bool check_redundant_nullability_qual(PlannerInfo *root, Node *clause);
+static void check_mergejoinable(RestrictInfo *restrictinfo);
+static void check_hashjoinable(RestrictInfo *restrictinfo);
+static void check_memoizable(RestrictInfo *restrictinfo);
+
+
+/*****************************************************************************
+ *
+ *	 JOIN TREES
+ *
+ *****************************************************************************/
+
+/*
+ * add_base_rels_to_query
+ *
+ *	  Scan the query's jointree and create baserel RelOptInfos for all
+ *	  the base relations (e.g., table, subquery, and function RTEs)
+ *	  appearing in the jointree.
+ *
+ * The initial invocation must pass root->parse->jointree as the value of
+ * jtnode.  Internally, the function recurses through the jointree.
+ *
+ * At the end of this process, there should be one baserel RelOptInfo for
+ * every non-join RTE that is used in the query.  Some of the baserels
+ * may be appendrel parents, which will require additional "otherrel"
+ * RelOptInfos for their member rels, but those are added later.
+ */
+void
+add_base_rels_to_query(PlannerInfo *root, Node *jtnode)
+{
+	if (jtnode == NULL)
+		return;
+	if (IsA(jtnode, RangeTblRef))
+	{
+		int			varno = ((RangeTblRef *) jtnode)->rtindex;
+
+		(void) build_simple_rel(root, varno, NULL);
+	}
+	else if (IsA(jtnode, FromExpr))
+	{
+		FromExpr   *f = (FromExpr *) jtnode;
+		ListCell   *l;
+
+		foreach(l, f->fromlist)
+			add_base_rels_to_query(root, lfirst(l));
+	}
+	else if (IsA(jtnode, JoinExpr))
+	{
+		JoinExpr   *j = (JoinExpr *) jtnode;
+
+		add_base_rels_to_query(root, j->larg);
+		add_base_rels_to_query(root, j->rarg);
+	}
+	else
+		elog(ERROR, "unrecognized node type: %d",
+			 (int) nodeTag(jtnode));
+}
+
+/*
+ * add_other_rels_to_query
+ *	  create "otherrel" RelOptInfos for the children of appendrel baserels
+ *
+ * At the end of this process, there should be RelOptInfos for all relations
+ * that will be scanned by the query.
+ */
+void
+add_other_rels_to_query(PlannerInfo *root)
+{
+	int			rti;
+
+	for (rti = 1; rti < root->simple_rel_array_size; rti++)
+	{
+		RelOptInfo *rel = root->simple_rel_array[rti];
+		RangeTblEntry *rte = root->simple_rte_array[rti];
+
+		/* there may be empty slots corresponding to non-baserel RTEs */
+		if (rel == NULL)
+			continue;
+
+		/* Ignore any "otherrels" that were already added. */
+		if (rel->reloptkind != RELOPT_BASEREL)
+			continue;
+
+		/* If it's marked as inheritable, look for children. */
+		if (rte->inh)
+			expand_inherited_rtentry(root, rel, rte, rti);
+	}
+}
+
+
+/*****************************************************************************
+ *
+ *	 TARGET LISTS
+ *
+ *****************************************************************************/
+
+/*
+ * build_base_rel_tlists
+ *	  Add targetlist entries for each var needed in the query's final tlist
+ *	  (and HAVING clause, if any) to the appropriate base relations.
+ *
+ * We mark such vars as needed by "relation 0" to ensure that they will
+ * propagate up through all join plan steps.
+ */
+void
+build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
+{
+	List	   *tlist_vars = pull_var_clause((Node *) final_tlist,
+											 PVC_RECURSE_AGGREGATES |
+											 PVC_RECURSE_WINDOWFUNCS |
+											 PVC_INCLUDE_PLACEHOLDERS);
+
+	if (tlist_vars != NIL)
+	{
+		add_vars_to_targetlist(root, tlist_vars, bms_make_singleton(0), true);
+		list_free(tlist_vars);
+	}
+
+	/*
+	 * If there's a HAVING clause, we'll need the Vars it uses, too.  Note
+	 * that HAVING can contain Aggrefs but not WindowFuncs.
+	 */
+	if (root->parse->havingQual)
+	{
+		List	   *having_vars = pull_var_clause(root->parse->havingQual,
+												  PVC_RECURSE_AGGREGATES |
+												  PVC_INCLUDE_PLACEHOLDERS);
+
+		if (having_vars != NIL)
+		{
+			add_vars_to_targetlist(root, having_vars,
+								   bms_make_singleton(0), true);
+			list_free(having_vars);
+		}
+	}
+}
+
+/*
+ * add_vars_to_targetlist
+ *	  For each variable appearing in the list, add it to the owning
+ *	  relation's targetlist if not already present, and mark the variable
+ *	  as being needed for the indicated join (or for final output if
+ *	  where_needed includes "relation 0").
+ *
+ *	  The list may also contain PlaceHolderVars.  These don't necessarily
+ *	  have a single owning relation; we keep their attr_needed info in
+ *	  root->placeholder_list instead.  If create_new_ph is true, it's OK
+ *	  to create new PlaceHolderInfos; otherwise, the PlaceHolderInfos must
+ *	  already exist, and we should only update their ph_needed.  (This should
+ *	  be true before deconstruct_jointree begins, and false after that.)
+ */
+void
+add_vars_to_targetlist(PlannerInfo *root, List *vars,
+					   Relids where_needed, bool create_new_ph)
+{
+	ListCell   *temp;
+
+	Assert(!bms_is_empty(where_needed));
+
+	foreach(temp, vars)
+	{
+		Node	   *node = (Node *) lfirst(temp);
+
+		if (IsA(node, Var))
+		{
+			Var		   *var = (Var *) node;
+			RelOptInfo *rel = find_base_rel(root, var->varno);
+			int			attno = var->varattno;
+
+			if (bms_is_subset(where_needed, rel->relids))
+				continue;
+			Assert(attno >= rel->min_attr && attno <= rel->max_attr);
+			attno -= rel->min_attr;
+			if (rel->attr_needed[attno] == NULL)
+			{
+				/* Variable not yet requested, so add to rel's targetlist */
+				/* XXX is copyObject necessary here? */
+				rel->reltarget->exprs = lappend(rel->reltarget->exprs,
+												copyObject(var));
+				/* reltarget cost and width will be computed later */
+			}
+			rel->attr_needed[attno] = bms_add_members(rel->attr_needed[attno],
+													  where_needed);
+		}
+		else if (IsA(node, PlaceHolderVar))
+		{
+			PlaceHolderVar *phv = (PlaceHolderVar *) node;
+			PlaceHolderInfo *phinfo = find_placeholder_info(root, phv,
+															create_new_ph);
+
+			phinfo->ph_needed = bms_add_members(phinfo->ph_needed,
+												where_needed);
+		}
+		else
+			elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node));
+	}
+}
+
+
+/*****************************************************************************
+ *
+ *	  LATERAL REFERENCES
+ *
+ *****************************************************************************/
+
+/*
+ * 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.
+ *
+ * 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.
+ *
+ * Note that this only deals with lateral references in unflattened LATERAL
+ * subqueries.  When we flatten a LATERAL subquery, its lateral references
+ * become plain Vars in the parent query, but they may have to be wrapped in
+ * PlaceHolderVars if they need to be forced NULL by outer joins that don't
+ * also null the LATERAL subquery.  That's all handled elsewhere.
+ *
+ * This has to run before deconstruct_jointree, since it might result in
+ * creation of PlaceHolderInfos.
+ */
+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
+		 * otherrel that is actually going to be in the plan.  However, we
+		 * want to mark all its 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 member is
+		 * nothing but a copy of parts of the original RTE's subquery.  We
+		 * could visit the parent's 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.)  Similarly, in appendrels created by inheritance expansion,
+		 * it's sufficient to look at the parent relation.
+		 */
+
+		/* 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, RelOptInfo *brel, Index rtindex)
+{
+	RangeTblEntry *rte = root->simple_rte_array[rtindex];
+	List	   *vars;
+	List	   *newvars;
+	Relids		where_needed;
+	ListCell   *lc;
+
+	/* No cross-references are possible if it's not LATERAL */
+	if (!rte->lateral)
+		return;
+
+	/* Fetch the appropriate variables */
+	if (rte->rtekind == RTE_RELATION)
+		vars = pull_vars_of_level((Node *) rte->tablesample, 0);
+	else if (rte->rtekind == RTE_SUBQUERY)
+		vars = pull_vars_of_level((Node *) rte->subquery, 1);
+	else if (rte->rtekind == RTE_FUNCTION)
+		vars = pull_vars_of_level((Node *) rte->functions, 0);
+	else if (rte->rtekind == RTE_TABLEFUNC)
+		vars = pull_vars_of_level((Node *) rte->tablefunc, 0);
+	else if (rte->rtekind == RTE_VALUES)
+		vars = pull_vars_of_level((Node *) rte->values_lists, 0);
+	else
+	{
+		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	   *node = (Node *) lfirst(lc);
+
+		node = copyObject(node);
+		if (IsA(node, Var))
+		{
+			Var		   *var = (Var *) node;
+
+			/* Adjustment is easy since it's just one node */
+			var->varlevelsup = 0;
+		}
+		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);
+
+			/*
+			 * 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.
+			 */
+			if (levelsup > 0)
+				phv->phexpr = preprocess_phv_expression(root, phv->phexpr);
+		}
+		else
+			Assert(false);
+		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
+	 * at the join of the LATERAL RTE with its source RTE.  But it will work,
+	 * and it's much less tedious than computing a separate where_needed for
+	 * each Var.
+	 */
+	where_needed = bms_make_singleton(rtindex);
+
+	/*
+	 * Push Vars into their source relations' targetlists, and PHVs into
+	 * root->placeholder_list.
+	 */
+	add_vars_to_targetlist(root, newvars, where_needed, true);
+
+	/* Remember the lateral references for create_lateral_join_info */
+	brel->lateral_vars = newvars;
+}
+
+/*
+ * create_lateral_join_info
+ *	  Fill in the per-base-relation direct_lateral_relids, lateral_relids
+ *	  and lateral_referencers sets.
+ *
+ * This has to run after deconstruct_jointree, because we need to know the
+ * final ph_eval_at values for PlaceHolderVars.
+ */
+void
+create_lateral_join_info(PlannerInfo *root)
+{
+	bool		found_laterals = false;
+	Index		rti;
+	ListCell   *lc;
+
+	/* 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;
+
+		/* 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;
+
+				found_laterals = true;
+				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);
+
+				found_laterals = true;
+				lateral_relids = bms_add_members(lateral_relids,
+												 phinfo->ph_eval_at);
+			}
+			else
+				Assert(false);
+		}
+
+		/* We now have all the simple lateral refs from this rel */
+		brel->direct_lateral_relids = lateral_relids;
+		brel->lateral_relids = bms_copy(lateral_relids);
+	}
+
+	/*
+	 * Now check for lateral references within PlaceHolderVars, and mark their
+	 * eval_at rels as having lateral references to the source rels.
+	 *
+	 * For a PHV that is due to be evaluated at a baserel, mark its source(s)
+	 * as direct lateral dependencies of the baserel (adding onto the ones
+	 * recorded above).  If it's due to be evaluated at a join, mark its
+	 * source(s) as indirect lateral dependencies of each baserel in the join,
+	 * ie put them into lateral_relids but not direct_lateral_relids.  This is
+	 * appropriate because we can't put any such baserel on the outside of a
+	 * join to one of the PHV's lateral dependencies, but on the other hand we
+	 * also can't yet join it directly to the dependency.
+	 */
+	foreach(lc, root->placeholder_list)
+	{
+		PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
+		Relids		eval_at = phinfo->ph_eval_at;
+		int			varno;
+
+		if (phinfo->ph_lateral == NULL)
+			continue;			/* PHV is uninteresting if no lateral refs */
+
+		found_laterals = true;
+
+		if (bms_get_singleton_member(eval_at, &varno))
+		{
+			/* Evaluation site is a baserel */
+			RelOptInfo *brel = find_base_rel(root, varno);
+
+			brel->direct_lateral_relids =
+				bms_add_members(brel->direct_lateral_relids,
+								phinfo->ph_lateral);
+			brel->lateral_relids =
+				bms_add_members(brel->lateral_relids,
+								phinfo->ph_lateral);
+		}
+		else
+		{
+			/* Evaluation site is a join */
+			varno = -1;
+			while ((varno = bms_next_member(eval_at, varno)) >= 0)
+			{
+				RelOptInfo *brel = find_base_rel(root, varno);
+
+				brel->lateral_relids = bms_add_members(brel->lateral_relids,
+													   phinfo->ph_lateral);
+			}
+		}
+	}
+
+	/*
+	 * If we found no actual lateral references, we're done; but reset the
+	 * hasLateralRTEs flag to avoid useless work later.
+	 */
+	if (!found_laterals)
+	{
+		root->hasLateralRTEs = false;
+		return;
+	}
+
+	/*
+	 * Calculate the transitive closure of the lateral_relids sets, so that
+	 * they describe both direct and indirect lateral references.  If relation
+	 * X references Y laterally, and Y references Z laterally, then we will
+	 * have to scan X on the inside of a nestloop with Z, so for all intents
+	 * and purposes X is laterally dependent on Z too.
+	 *
+	 * This code is essentially Warshall's algorithm for transitive closure.
+	 * The outer loop considers each baserel, and propagates its lateral
+	 * dependencies to those baserels that have a lateral dependency on it.
+	 */
+	for (rti = 1; rti < root->simple_rel_array_size; rti++)
+	{
+		RelOptInfo *brel = root->simple_rel_array[rti];
+		Relids		outer_lateral_relids;
+		Index		rti2;
+
+		if (brel == NULL || brel->reloptkind != RELOPT_BASEREL)
+			continue;
+
+		/* need not consider baserel further if it has no lateral refs */
+		outer_lateral_relids = brel->lateral_relids;
+		if (outer_lateral_relids == NULL)
+			continue;
+
+		/* else scan all baserels */
+		for (rti2 = 1; rti2 < root->simple_rel_array_size; rti2++)
+		{
+			RelOptInfo *brel2 = root->simple_rel_array[rti2];
+
+			if (brel2 == NULL || brel2->reloptkind != RELOPT_BASEREL)
+				continue;
+
+			/* if brel2 has lateral ref to brel, propagate brel's refs */
+			if (bms_is_member(rti, brel2->lateral_relids))
+				brel2->lateral_relids = bms_add_members(brel2->lateral_relids,
+														outer_lateral_relids);
+		}
+	}
+
+	/*
+	 * Now that we've identified all lateral references, mark each baserel
+	 * with the set of relids of rels that reference it laterally (possibly
+	 * indirectly) --- that is, the inverse mapping of lateral_relids.
+	 */
+	for (rti = 1; rti < root->simple_rel_array_size; rti++)
+	{
+		RelOptInfo *brel = root->simple_rel_array[rti];
+		Relids		lateral_relids;
+		int			rti2;
+
+		if (brel == NULL || brel->reloptkind != RELOPT_BASEREL)
+			continue;
+
+		/* Nothing to do at rels with no lateral refs */
+		lateral_relids = brel->lateral_relids;
+		if (lateral_relids == NULL)
+			continue;
+
+		/*
+		 * We should not have broken the invariant that lateral_relids is
+		 * exactly NULL if empty.
+		 */
+		Assert(!bms_is_empty(lateral_relids));
+
+		/* Also, no rel should have a lateral dependency on itself */
+		Assert(!bms_is_member(rti, lateral_relids));
+
+		/* Mark this rel's referencees */
+		rti2 = -1;
+		while ((rti2 = bms_next_member(lateral_relids, rti2)) >= 0)
+		{
+			RelOptInfo *brel2 = root->simple_rel_array[rti2];
+
+			Assert(brel2 != NULL && brel2->reloptkind == RELOPT_BASEREL);
+			brel2->lateral_referencers =
+				bms_add_member(brel2->lateral_referencers, rti);
+		}
+	}
+}
+
+
+/*****************************************************************************
+ *
+ *	  JOIN TREE PROCESSING
+ *
+ *****************************************************************************/
+
+/*
+ * deconstruct_jointree
+ *	  Recursively scan the query's join tree for WHERE and JOIN/ON qual
+ *	  clauses, and add these to the appropriate restrictinfo and joininfo
+ *	  lists belonging to base RelOptInfos.  Also, add SpecialJoinInfo nodes
+ *	  to root->join_info_list for any outer joins appearing in the query tree.
+ *	  Return a "joinlist" data structure showing the join order decisions
+ *	  that need to be made by make_one_rel().
+ *
+ * The "joinlist" result is a list of items that are either RangeTblRef
+ * jointree nodes or sub-joinlists.  All the items at the same level of
+ * joinlist must be joined in an order to be determined by make_one_rel()
+ * (note that legal orders may be constrained by SpecialJoinInfo nodes).
+ * A sub-joinlist represents a subproblem to be planned separately. Currently
+ * sub-joinlists arise only from FULL OUTER JOIN or when collapsing of
+ * subproblems is stopped by join_collapse_limit or from_collapse_limit.
+ *
+ * NOTE: when dealing with inner joins, it is appropriate to let a qual clause
+ * be evaluated at the lowest level where all the variables it mentions are
+ * available.  However, we cannot push a qual down into the nullable side(s)
+ * of an outer join since the qual might eliminate matching rows and cause a
+ * NULL row to be incorrectly emitted by the join.  Therefore, we artificially
+ * OR the minimum-relids of such an outer join into the required_relids of
+ * clauses appearing above it.  This forces those clauses to be delayed until
+ * application of the outer join (or maybe even higher in the join tree).
+ */
+List *
+deconstruct_jointree(PlannerInfo *root)
+{
+	List	   *result;
+	Relids		qualscope;
+	Relids		inner_join_rels;
+	List	   *postponed_qual_list = NIL;
+
+	/* Start recursion at top of jointree */
+	Assert(root->parse->jointree != NULL &&
+		   IsA(root->parse->jointree, FromExpr));
+
+	/* this is filled as we scan the jointree */
+	root->nullable_baserels = NULL;
+
+	result = deconstruct_recurse(root, (Node *) root->parse->jointree, false,
+								 &qualscope, &inner_join_rels,
+								 &postponed_qual_list);
+
+	/* Shouldn't be any leftover quals */
+	Assert(postponed_qual_list == NIL);
+
+	return result;
+}
+
+/*
+ * deconstruct_recurse
+ *	  One recursion level of deconstruct_jointree processing.
+ *
+ * Inputs:
+ *	jtnode is the jointree node to examine
+ *	below_outer_join is true if this node is within the nullable side of a
+ *		higher-level outer join
+ * Outputs:
+ *	*qualscope gets the set of base Relids syntactically included in this
+ *		jointree node (do not modify or free this, as it may also be pointed
+ *		to by RestrictInfo and SpecialJoinInfo nodes)
+ *	*inner_join_rels gets the set of base Relids syntactically included in
+ *		inner joins appearing at or below this jointree node (do not modify
+ *		or free this, either)
+ *	*postponed_qual_list is a list of PostponedQual structs, which we can
+ *		add quals to if they turn out to belong to a higher join level
+ *	Return value is the appropriate joinlist for this jointree node
+ *
+ * In addition, entries will be added to root->join_info_list for outer joins.
+ */
+static List *
+deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
+					Relids *qualscope, Relids *inner_join_rels,
+					List **postponed_qual_list)
+{
+	List	   *joinlist;
+
+	if (jtnode == NULL)
+	{
+		*qualscope = NULL;
+		*inner_join_rels = NULL;
+		return NIL;
+	}
+	if (IsA(jtnode, RangeTblRef))
+	{
+		int			varno = ((RangeTblRef *) jtnode)->rtindex;
+
+		/* qualscope is just the one RTE */
+		*qualscope = bms_make_singleton(varno);
+		/* Deal with any securityQuals attached to the RTE */
+		if (root->qual_security_level > 0)
+			process_security_barrier_quals(root,
+										   varno,
+										   *qualscope,
+										   below_outer_join);
+		/* A single baserel does not create an inner join */
+		*inner_join_rels = NULL;
+		joinlist = list_make1(jtnode);
+	}
+	else if (IsA(jtnode, FromExpr))
+	{
+		FromExpr   *f = (FromExpr *) jtnode;
+		List	   *child_postponed_quals = NIL;
+		int			remaining;
+		ListCell   *l;
+
+		/*
+		 * First, recurse to handle child joins.  We collapse subproblems into
+		 * a single joinlist whenever the resulting joinlist wouldn't exceed
+		 * from_collapse_limit members.  Also, always collapse one-element
+		 * subproblems, since that won't lengthen the joinlist anyway.
+		 */
+		*qualscope = NULL;
+		*inner_join_rels = NULL;
+		joinlist = NIL;
+		remaining = list_length(f->fromlist);
+		foreach(l, f->fromlist)
+		{
+			Relids		sub_qualscope;
+			List	   *sub_joinlist;
+			int			sub_members;
+
+			sub_joinlist = deconstruct_recurse(root, lfirst(l),
+											   below_outer_join,
+											   &sub_qualscope,
+											   inner_join_rels,
+											   &child_postponed_quals);
+			*qualscope = bms_add_members(*qualscope, sub_qualscope);
+			sub_members = list_length(sub_joinlist);
+			remaining--;
+			if (sub_members <= 1 ||
+				list_length(joinlist) + sub_members + remaining <= from_collapse_limit)
+				joinlist = list_concat(joinlist, sub_joinlist);
+			else
+				joinlist = lappend(joinlist, sub_joinlist);
+		}
+
+		/*
+		 * A FROM with more than one list element is an inner join subsuming
+		 * all below it, so we should report inner_join_rels = qualscope. If
+		 * there was exactly one element, we should (and already did) report
+		 * whatever its inner_join_rels were.  If there were no elements (is
+		 * that still possible?) the initialization before the loop fixed it.
+		 */
+		if (list_length(f->fromlist) > 1)
+			*inner_join_rels = *qualscope;
+
+		/*
+		 * Try to process any quals postponed by children.  If they need
+		 * further postponement, add them to my output postponed_qual_list.
+		 */
+		foreach(l, child_postponed_quals)
+		{
+			PostponedQual *pq = (PostponedQual *) lfirst(l);
+
+			if (bms_is_subset(pq->relids, *qualscope))
+				distribute_qual_to_rels(root, pq->qual,
+										below_outer_join, JOIN_INNER,
+										root->qual_security_level,
+										*qualscope, NULL, NULL,
+										NULL);
+			else
+				*postponed_qual_list = lappend(*postponed_qual_list, pq);
+		}
+
+		/*
+		 * Now process the top-level quals.
+		 */
+		foreach(l, (List *) f->quals)
+		{
+			Node	   *qual = (Node *) lfirst(l);
+
+			distribute_qual_to_rels(root, qual,
+									below_outer_join, JOIN_INNER,
+									root->qual_security_level,
+									*qualscope, NULL, NULL,
+									postponed_qual_list);
+		}
+	}
+	else if (IsA(jtnode, JoinExpr))
+	{
+		JoinExpr   *j = (JoinExpr *) jtnode;
+		List	   *child_postponed_quals = NIL;
+		Relids		leftids,
+					rightids,
+					left_inners,
+					right_inners,
+					nonnullable_rels,
+					nullable_rels,
+					ojscope;
+		List	   *leftjoinlist,
+				   *rightjoinlist;
+		List	   *my_quals;
+		SpecialJoinInfo *sjinfo;
+		ListCell   *l;
+
+		/*
+		 * Order of operations here is subtle and critical.  First we recurse
+		 * to handle sub-JOINs.  Their join quals will be placed without
+		 * regard for whether this level is an outer join, which is correct.
+		 * Then we place our own join quals, which are restricted by lower
+		 * outer joins in any case, and are forced to this level if this is an
+		 * outer join and they mention the outer side.  Finally, if this is an
+		 * outer join, we create a join_info_list entry for the join.  This
+		 * will prevent quals above us in the join tree that use those rels
+		 * from being pushed down below this level.  (It's okay for upper
+		 * quals to be pushed down to the outer side, however.)
+		 */
+		switch (j->jointype)
+		{
+			case JOIN_INNER:
+				leftjoinlist = deconstruct_recurse(root, j->larg,
+												   below_outer_join,
+												   &leftids, &left_inners,
+												   &child_postponed_quals);
+				rightjoinlist = deconstruct_recurse(root, j->rarg,
+													below_outer_join,
+													&rightids, &right_inners,
+													&child_postponed_quals);
+				*qualscope = bms_union(leftids, rightids);
+				*inner_join_rels = *qualscope;
+				/* Inner join adds no restrictions for quals */
+				nonnullable_rels = NULL;
+				/* and it doesn't force anything to null, either */
+				nullable_rels = NULL;
+				break;
+			case JOIN_LEFT:
+			case JOIN_ANTI:
+				leftjoinlist = deconstruct_recurse(root, j->larg,
+												   below_outer_join,
+												   &leftids, &left_inners,
+												   &child_postponed_quals);
+				rightjoinlist = deconstruct_recurse(root, j->rarg,
+													true,
+													&rightids, &right_inners,
+													&child_postponed_quals);
+				*qualscope = bms_union(leftids, rightids);
+				*inner_join_rels = bms_union(left_inners, right_inners);
+				nonnullable_rels = leftids;
+				nullable_rels = rightids;
+				break;
+			case JOIN_SEMI:
+				leftjoinlist = deconstruct_recurse(root, j->larg,
+												   below_outer_join,
+												   &leftids, &left_inners,
+												   &child_postponed_quals);
+				rightjoinlist = deconstruct_recurse(root, j->rarg,
+													below_outer_join,
+													&rightids, &right_inners,
+													&child_postponed_quals);
+				*qualscope = bms_union(leftids, rightids);
+				*inner_join_rels = bms_union(left_inners, right_inners);
+				/* Semi join adds no restrictions for quals */
+				nonnullable_rels = NULL;
+
+				/*
+				 * Theoretically, a semijoin would null the RHS; but since the
+				 * RHS can't be accessed above the join, this is immaterial
+				 * and we needn't account for it.
+				 */
+				nullable_rels = NULL;
+				break;
+			case JOIN_FULL:
+				leftjoinlist = deconstruct_recurse(root, j->larg,
+												   true,
+												   &leftids, &left_inners,
+												   &child_postponed_quals);
+				rightjoinlist = deconstruct_recurse(root, j->rarg,
+													true,
+													&rightids, &right_inners,
+													&child_postponed_quals);
+				*qualscope = bms_union(leftids, rightids);
+				*inner_join_rels = bms_union(left_inners, right_inners);
+				/* each side is both outer and inner */
+				nonnullable_rels = *qualscope;
+				nullable_rels = *qualscope;
+				break;
+			default:
+				/* JOIN_RIGHT was eliminated during reduce_outer_joins() */
+				elog(ERROR, "unrecognized join type: %d",
+					 (int) j->jointype);
+				nonnullable_rels = NULL;	/* keep compiler quiet */
+				nullable_rels = NULL;
+				leftjoinlist = rightjoinlist = NIL;
+				break;
+		}
+
+		/* Report all rels that will be nulled anywhere in the jointree */
+		root->nullable_baserels = bms_add_members(root->nullable_baserels,
+												  nullable_rels);
+
+		/*
+		 * Try to process any quals postponed by children.  If they need
+		 * further postponement, add them to my output postponed_qual_list.
+		 * Quals that can be processed now must be included in my_quals, so
+		 * that they'll be handled properly in make_outerjoininfo.
+		 */
+		my_quals = NIL;
+		foreach(l, child_postponed_quals)
+		{
+			PostponedQual *pq = (PostponedQual *) lfirst(l);
+
+			if (bms_is_subset(pq->relids, *qualscope))
+				my_quals = lappend(my_quals, pq->qual);
+			else
+			{
+				/*
+				 * We should not be postponing any quals past an outer join.
+				 * If this Assert fires, pull_up_subqueries() messed up.
+				 */
+				Assert(j->jointype == JOIN_INNER);
+				*postponed_qual_list = lappend(*postponed_qual_list, pq);
+			}
+		}
+		my_quals = list_concat(my_quals, (List *) j->quals);
+
+		/*
+		 * For an OJ, form the SpecialJoinInfo now, because we need the OJ's
+		 * semantic scope (ojscope) to pass to distribute_qual_to_rels.  But
+		 * we mustn't add it to join_info_list just yet, because we don't want
+		 * distribute_qual_to_rels to think it is an outer join below us.
+		 *
+		 * Semijoins are a bit of a hybrid: we build a SpecialJoinInfo, but we
+		 * want ojscope = NULL for distribute_qual_to_rels.
+		 */
+		if (j->jointype != JOIN_INNER)
+		{
+			sjinfo = make_outerjoininfo(root,
+										leftids, rightids,
+										*inner_join_rels,
+										j->jointype,
+										my_quals);
+			if (j->jointype == JOIN_SEMI)
+				ojscope = NULL;
+			else
+				ojscope = bms_union(sjinfo->min_lefthand,
+									sjinfo->min_righthand);
+		}
+		else
+		{
+			sjinfo = NULL;
+			ojscope = NULL;
+		}
+
+		/* Process the JOIN's qual clauses */
+		foreach(l, my_quals)
+		{
+			Node	   *qual = (Node *) lfirst(l);
+
+			distribute_qual_to_rels(root, qual,
+									below_outer_join, j->jointype,
+									root->qual_security_level,
+									*qualscope,
+									ojscope, nonnullable_rels,
+									postponed_qual_list);
+		}
+
+		/* Now we can add the SpecialJoinInfo to join_info_list */
+		if (sjinfo)
+		{
+			root->join_info_list = lappend(root->join_info_list, sjinfo);
+			/* Each time we do that, recheck placeholder eval levels */
+			update_placeholder_eval_levels(root, sjinfo);
+		}
+
+		/*
+		 * Finally, compute the output joinlist.  We fold subproblems together
+		 * except at a FULL JOIN or where join_collapse_limit would be
+		 * exceeded.
+		 */
+		if (j->jointype == JOIN_FULL)
+		{
+			/* force the join order exactly at this node */
+			joinlist = list_make1(list_make2(leftjoinlist, rightjoinlist));
+		}
+		else if (list_length(leftjoinlist) + list_length(rightjoinlist) <=
+				 join_collapse_limit)
+		{
+			/* OK to combine subproblems */
+			joinlist = list_concat(leftjoinlist, rightjoinlist);
+		}
+		else
+		{
+			/* can't combine, but needn't force join order above here */
+			Node	   *leftpart,
+					   *rightpart;
+
+			/* avoid creating useless 1-element sublists */
+			if (list_length(leftjoinlist) == 1)
+				leftpart = (Node *) linitial(leftjoinlist);
+			else
+				leftpart = (Node *) leftjoinlist;
+			if (list_length(rightjoinlist) == 1)
+				rightpart = (Node *) linitial(rightjoinlist);
+			else
+				rightpart = (Node *) rightjoinlist;
+			joinlist = list_make2(leftpart, rightpart);
+		}
+	}
+	else
+	{
+		elog(ERROR, "unrecognized node type: %d",
+			 (int) nodeTag(jtnode));
+		joinlist = NIL;			/* keep compiler quiet */
+	}
+	return joinlist;
+}
+
+/*
+ * process_security_barrier_quals
+ *	  Transfer security-barrier quals into relation's baserestrictinfo list.
+ *
+ * The rewriter put any relevant security-barrier conditions into the RTE's
+ * securityQuals field, but it's now time to copy them into the rel's
+ * baserestrictinfo.
+ *
+ * In inheritance cases, we only consider quals attached to the parent rel
+ * here; they will be valid for all children too, so it's okay to consider
+ * them for purposes like equivalence class creation.  Quals attached to
+ * individual child rels will be dealt with during path creation.
+ */
+static void
+process_security_barrier_quals(PlannerInfo *root,
+							   int rti, Relids qualscope,
+							   bool below_outer_join)
+{
+	RangeTblEntry *rte = root->simple_rte_array[rti];
+	Index		security_level = 0;
+	ListCell   *lc;
+
+	/*
+	 * Each element of the securityQuals list has been preprocessed into an
+	 * implicitly-ANDed list of clauses.  All the clauses in a given sublist
+	 * should get the same security level, but successive sublists get higher
+	 * levels.
+	 */
+	foreach(lc, rte->securityQuals)
+	{
+		List	   *qualset = (List *) lfirst(lc);
+		ListCell   *lc2;
+
+		foreach(lc2, qualset)
+		{
+			Node	   *qual = (Node *) lfirst(lc2);
+
+			/*
+			 * We cheat to the extent of passing ojscope = qualscope rather
+			 * than its more logical value of NULL.  The only effect this has
+			 * is to force a Var-free qual to be evaluated at the rel rather
+			 * than being pushed up to top of tree, which we don't want.
+			 */
+			distribute_qual_to_rels(root, qual,
+									below_outer_join,
+									JOIN_INNER,
+									security_level,
+									qualscope,
+									qualscope,
+									NULL,
+									NULL);
+		}
+		security_level++;
+	}
+
+	/* Assert that qual_security_level is higher than anything we just used */
+	Assert(security_level <= root->qual_security_level);
+}
+
+/*
+ * make_outerjoininfo
+ *	  Build a SpecialJoinInfo for the current outer join
+ *
+ * Inputs:
+ *	left_rels: the base Relids syntactically on outer side of join
+ *	right_rels: the base Relids syntactically on inner side of join
+ *	inner_join_rels: base Relids participating in inner joins below this one
+ *	jointype: what it says (must always be LEFT, FULL, SEMI, or ANTI)
+ *	clause: the outer join's join condition (in implicit-AND format)
+ *
+ * The node should eventually be appended to root->join_info_list, but we
+ * do not do that here.
+ *
+ * Note: we assume that this function is invoked bottom-up, so that
+ * root->join_info_list already contains entries for all outer joins that are
+ * syntactically below this one.
+ */
+static SpecialJoinInfo *
+make_outerjoininfo(PlannerInfo *root,
+				   Relids left_rels, Relids right_rels,
+				   Relids inner_join_rels,
+				   JoinType jointype, List *clause)
+{
+	SpecialJoinInfo *sjinfo = makeNode(SpecialJoinInfo);
+	Relids		clause_relids;
+	Relids		strict_relids;
+	Relids		min_lefthand;
+	Relids		min_righthand;
+	ListCell   *l;
+
+	/*
+	 * We should not see RIGHT JOIN here because left/right were switched
+	 * earlier
+	 */
+	Assert(jointype != JOIN_INNER);
+	Assert(jointype != JOIN_RIGHT);
+
+	/*
+	 * Presently the executor cannot support FOR [KEY] UPDATE/SHARE marking of
+	 * rels appearing on the nullable side of an outer join. (It's somewhat
+	 * unclear what that would mean, anyway: what should we mark when a result
+	 * row is generated from no element of the nullable relation?)	So,
+	 * complain if any nullable rel is FOR [KEY] UPDATE/SHARE.
+	 *
+	 * You might be wondering why this test isn't made far upstream in the
+	 * parser.  It's because the parser hasn't got enough info --- consider
+	 * FOR UPDATE applied to a view.  Only after rewriting and flattening do
+	 * we know whether the view contains an outer join.
+	 *
+	 * We use the original RowMarkClause list here; the PlanRowMark list would
+	 * list everything.
+	 */
+	foreach(l, root->parse->rowMarks)
+	{
+		RowMarkClause *rc = (RowMarkClause *) lfirst(l);
+
+		if (bms_is_member(rc->rti, right_rels) ||
+			(jointype == JOIN_FULL && bms_is_member(rc->rti, left_rels)))
+			ereport(ERROR,
+					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+			/*------
+			 translator: %s is a SQL row locking clause such as FOR UPDATE */
+					 errmsg("%s cannot be applied to the nullable side of an outer join",
+							LCS_asString(rc->strength))));
+	}
+
+	sjinfo->syn_lefthand = left_rels;
+	sjinfo->syn_righthand = right_rels;
+	sjinfo->jointype = jointype;
+	/* this always starts out false */
+	sjinfo->delay_upper_joins = false;
+
+	compute_semijoin_info(root, sjinfo, clause);
+
+	/* If it's a full join, no need to be very smart */
+	if (jointype == JOIN_FULL)
+	{
+		sjinfo->min_lefthand = bms_copy(left_rels);
+		sjinfo->min_righthand = bms_copy(right_rels);
+		sjinfo->lhs_strict = false; /* don't care about this */
+		return sjinfo;
+	}
+
+	/*
+	 * Retrieve all relids mentioned within the join clause.
+	 */
+	clause_relids = pull_varnos(root, (Node *) clause);
+
+	/*
+	 * For which relids is the clause strict, ie, it cannot succeed if the
+	 * rel's columns are all NULL?
+	 */
+	strict_relids = find_nonnullable_rels((Node *) clause);
+
+	/* Remember whether the clause is strict for any LHS relations */
+	sjinfo->lhs_strict = bms_overlap(strict_relids, left_rels);
+
+	/*
+	 * Required LHS always includes the LHS rels mentioned in the clause. We
+	 * may have to add more rels based on lower outer joins; see below.
+	 */
+	min_lefthand = bms_intersect(clause_relids, left_rels);
+
+	/*
+	 * Similarly for required RHS.  But here, we must also include any lower
+	 * inner joins, to ensure we don't try to commute with any of them.
+	 */
+	min_righthand = bms_int_members(bms_union(clause_relids, inner_join_rels),
+									right_rels);
+
+	/*
+	 * Now check previous outer joins for ordering restrictions.
+	 */
+	foreach(l, root->join_info_list)
+	{
+		SpecialJoinInfo *otherinfo = (SpecialJoinInfo *) lfirst(l);
+
+		/*
+		 * A full join is an optimization barrier: we can't associate into or
+		 * out of it.  Hence, if it overlaps either LHS or RHS of the current
+		 * rel, expand that side's min relset to cover the whole full join.
+		 */
+		if (otherinfo->jointype == JOIN_FULL)
+		{
+			if (bms_overlap(left_rels, otherinfo->syn_lefthand) ||
+				bms_overlap(left_rels, otherinfo->syn_righthand))
+			{
+				min_lefthand = bms_add_members(min_lefthand,
+											   otherinfo->syn_lefthand);
+				min_lefthand = bms_add_members(min_lefthand,
+											   otherinfo->syn_righthand);
+			}
+			if (bms_overlap(right_rels, otherinfo->syn_lefthand) ||
+				bms_overlap(right_rels, otherinfo->syn_righthand))
+			{
+				min_righthand = bms_add_members(min_righthand,
+												otherinfo->syn_lefthand);
+				min_righthand = bms_add_members(min_righthand,
+												otherinfo->syn_righthand);
+			}
+			/* Needn't do anything else with the full join */
+			continue;
+		}
+
+		/*
+		 * For a lower OJ in our LHS, if our join condition uses the lower
+		 * join's RHS and is not strict for that rel, we must preserve the
+		 * ordering of the two OJs, so add lower OJ's full syntactic relset to
+		 * min_lefthand.  (We must use its full syntactic relset, not just its
+		 * min_lefthand + min_righthand.  This is because there might be other
+		 * OJs below this one that this one can commute with, but we cannot
+		 * commute with them if we don't with this one.)  Also, if the current
+		 * join is a semijoin or antijoin, we must preserve ordering
+		 * regardless of strictness.
+		 *
+		 * Note: I believe we have to insist on being strict for at least one
+		 * rel in the lower OJ's min_righthand, not its whole syn_righthand.
+		 */
+		if (bms_overlap(left_rels, otherinfo->syn_righthand))
+		{
+			if (bms_overlap(clause_relids, otherinfo->syn_righthand) &&
+				(jointype == JOIN_SEMI || jointype == JOIN_ANTI ||
+				 !bms_overlap(strict_relids, otherinfo->min_righthand)))
+			{
+				min_lefthand = bms_add_members(min_lefthand,
+											   otherinfo->syn_lefthand);
+				min_lefthand = bms_add_members(min_lefthand,
+											   otherinfo->syn_righthand);
+			}
+		}
+
+		/*
+		 * For a lower OJ in our RHS, if our join condition does not use the
+		 * lower join's RHS and the lower OJ's join condition is strict, we
+		 * can interchange the ordering of the two OJs; otherwise we must add
+		 * the lower OJ's full syntactic relset to min_righthand.
+		 *
+		 * Also, if our join condition does not use the lower join's LHS
+		 * either, force the ordering to be preserved.  Otherwise we can end
+		 * up with SpecialJoinInfos with identical min_righthands, which can
+		 * confuse join_is_legal (see discussion in backend/optimizer/README).
+		 *
+		 * Also, we must preserve ordering anyway if either the current join
+		 * or the lower OJ is either a semijoin or an antijoin.
+		 *
+		 * Here, we have to consider that "our join condition" includes any
+		 * clauses that syntactically appeared above the lower OJ and below
+		 * ours; those are equivalent to degenerate clauses in our OJ and must
+		 * be treated as such.  Such clauses obviously can't reference our
+		 * LHS, and they must be non-strict for the lower OJ's RHS (else
+		 * reduce_outer_joins would have reduced the lower OJ to a plain
+		 * join).  Hence the other ways in which we handle clauses within our
+		 * join condition are not affected by them.  The net effect is
+		 * therefore sufficiently represented by the delay_upper_joins flag
+		 * saved for us by check_outerjoin_delay.
+		 */
+		if (bms_overlap(right_rels, otherinfo->syn_righthand))
+		{
+			if (bms_overlap(clause_relids, otherinfo->syn_righthand) ||
+				!bms_overlap(clause_relids, otherinfo->min_lefthand) ||
+				jointype == JOIN_SEMI ||
+				jointype == JOIN_ANTI ||
+				otherinfo->jointype == JOIN_SEMI ||
+				otherinfo->jointype == JOIN_ANTI ||
+				!otherinfo->lhs_strict || otherinfo->delay_upper_joins)
+			{
+				min_righthand = bms_add_members(min_righthand,
+												otherinfo->syn_lefthand);
+				min_righthand = bms_add_members(min_righthand,
+												otherinfo->syn_righthand);
+			}
+		}
+	}
+
+	/*
+	 * Examine PlaceHolderVars.  If a PHV is supposed to be evaluated within
+	 * this join's nullable side, then ensure that min_righthand contains the
+	 * full eval_at set of the PHV.  This ensures that the PHV actually can be
+	 * evaluated within the RHS.  Note that this works only because we should
+	 * already have determined the final eval_at level for any PHV
+	 * syntactically within this join.
+	 */
+	foreach(l, root->placeholder_list)
+	{
+		PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
+		Relids		ph_syn_level = phinfo->ph_var->phrels;
+
+		/* Ignore placeholder if it didn't syntactically come from RHS */
+		if (!bms_is_subset(ph_syn_level, right_rels))
+			continue;
+
+		/* Else, prevent join from being formed before we eval the PHV */
+		min_righthand = bms_add_members(min_righthand, phinfo->ph_eval_at);
+	}
+
+	/*
+	 * If we found nothing to put in min_lefthand, punt and make it the full
+	 * LHS, to avoid having an empty min_lefthand which will confuse later
+	 * processing. (We don't try to be smart about such cases, just correct.)
+	 * Likewise for min_righthand.
+	 */
+	if (bms_is_empty(min_lefthand))
+		min_lefthand = bms_copy(left_rels);
+	if (bms_is_empty(min_righthand))
+		min_righthand = bms_copy(right_rels);
+
+	/* Now they'd better be nonempty */
+	Assert(!bms_is_empty(min_lefthand));
+	Assert(!bms_is_empty(min_righthand));
+	/* Shouldn't overlap either */
+	Assert(!bms_overlap(min_lefthand, min_righthand));
+
+	sjinfo->min_lefthand = min_lefthand;
+	sjinfo->min_righthand = min_righthand;
+
+	return sjinfo;
+}
+
+/*
+ * compute_semijoin_info
+ *	  Fill semijoin-related fields of a new SpecialJoinInfo
+ *
+ * Note: this relies on only the jointype and syn_righthand fields of the
+ * SpecialJoinInfo; the rest may not be set yet.
+ */
+static void
+compute_semijoin_info(PlannerInfo *root, SpecialJoinInfo *sjinfo, List *clause)
+{
+	List	   *semi_operators;
+	List	   *semi_rhs_exprs;
+	bool		all_btree;
+	bool		all_hash;
+	ListCell   *lc;
+
+	/* Initialize semijoin-related fields in case we can't unique-ify */
+	sjinfo->semi_can_btree = false;
+	sjinfo->semi_can_hash = false;
+	sjinfo->semi_operators = NIL;
+	sjinfo->semi_rhs_exprs = NIL;
+
+	/* Nothing more to do if it's not a semijoin */
+	if (sjinfo->jointype != JOIN_SEMI)
+		return;
+
+	/*
+	 * Look to see whether the semijoin's join quals consist of AND'ed
+	 * equality operators, with (only) RHS variables on only one side of each
+	 * one.  If so, we can figure out how to enforce uniqueness for the RHS.
+	 *
+	 * Note that the input clause list is the list of quals that are
+	 * *syntactically* associated with the semijoin, which in practice means
+	 * the synthesized comparison list for an IN or the WHERE of an EXISTS.
+	 * Particularly in the latter case, it might contain clauses that aren't
+	 * *semantically* associated with the join, but refer to just one side or
+	 * the other.  We can ignore such clauses here, as they will just drop
+	 * down to be processed within one side or the other.  (It is okay to
+	 * consider only the syntactically-associated clauses here because for a
+	 * semijoin, no higher-level quals could refer to the RHS, and so there
+	 * can be no other quals that are semantically associated with this join.
+	 * We do things this way because it is useful to have the set of potential
+	 * unique-ification expressions before we can extract the list of quals
+	 * that are actually semantically associated with the particular join.)
+	 *
+	 * Note that the semi_operators list consists of the joinqual operators
+	 * themselves (but commuted if needed to put the RHS value on the right).
+	 * These could be cross-type operators, in which case the operator
+	 * actually needed for uniqueness is a related single-type operator. We
+	 * assume here that that operator will be available from the btree or hash
+	 * opclass when the time comes ... if not, create_unique_plan() will fail.
+	 */
+	semi_operators = NIL;
+	semi_rhs_exprs = NIL;
+	all_btree = true;
+	all_hash = enable_hashagg;	/* don't consider hash if not enabled */
+	foreach(lc, clause)
+	{
+		OpExpr	   *op = (OpExpr *) lfirst(lc);
+		Oid			opno;
+		Node	   *left_expr;
+		Node	   *right_expr;
+		Relids		left_varnos;
+		Relids		right_varnos;
+		Relids		all_varnos;
+		Oid			opinputtype;
+
+		/* Is it a binary opclause? */
+		if (!IsA(op, OpExpr) ||
+			list_length(op->args) != 2)
+		{
+			/* No, but does it reference both sides? */
+			all_varnos = pull_varnos(root, (Node *) op);
+			if (!bms_overlap(all_varnos, sjinfo->syn_righthand) ||
+				bms_is_subset(all_varnos, sjinfo->syn_righthand))
+			{
+				/*
+				 * Clause refers to only one rel, so ignore it --- unless it
+				 * contains volatile functions, in which case we'd better
+				 * punt.
+				 */
+				if (contain_volatile_functions((Node *) op))
+					return;
+				continue;
+			}
+			/* Non-operator clause referencing both sides, must punt */
+			return;
+		}
+
+		/* Extract data from binary opclause */
+		opno = op->opno;
+		left_expr = linitial(op->args);
+		right_expr = lsecond(op->args);
+		left_varnos = pull_varnos(root, left_expr);
+		right_varnos = pull_varnos(root, right_expr);
+		all_varnos = bms_union(left_varnos, right_varnos);
+		opinputtype = exprType(left_expr);
+
+		/* Does it reference both sides? */
+		if (!bms_overlap(all_varnos, sjinfo->syn_righthand) ||
+			bms_is_subset(all_varnos, sjinfo->syn_righthand))
+		{
+			/*
+			 * Clause refers to only one rel, so ignore it --- unless it
+			 * contains volatile functions, in which case we'd better punt.
+			 */
+			if (contain_volatile_functions((Node *) op))
+				return;
+			continue;
+		}
+
+		/* check rel membership of arguments */
+		if (!bms_is_empty(right_varnos) &&
+			bms_is_subset(right_varnos, sjinfo->syn_righthand) &&
+			!bms_overlap(left_varnos, sjinfo->syn_righthand))
+		{
+			/* typical case, right_expr is RHS variable */
+		}
+		else if (!bms_is_empty(left_varnos) &&
+				 bms_is_subset(left_varnos, sjinfo->syn_righthand) &&
+				 !bms_overlap(right_varnos, sjinfo->syn_righthand))
+		{
+			/* flipped case, left_expr is RHS variable */
+			opno = get_commutator(opno);
+			if (!OidIsValid(opno))
+				return;
+			right_expr = left_expr;
+		}
+		else
+		{
+			/* mixed membership of args, punt */
+			return;
+		}
+
+		/* all operators must be btree equality or hash equality */
+		if (all_btree)
+		{
+			/* oprcanmerge is considered a hint... */
+			if (!op_mergejoinable(opno, opinputtype) ||
+				get_mergejoin_opfamilies(opno) == NIL)
+				all_btree = false;
+		}
+		if (all_hash)
+		{
+			/* ... but oprcanhash had better be correct */
+			if (!op_hashjoinable(opno, opinputtype))
+				all_hash = false;
+		}
+		if (!(all_btree || all_hash))
+			return;
+
+		/* so far so good, keep building lists */
+		semi_operators = lappend_oid(semi_operators, opno);
+		semi_rhs_exprs = lappend(semi_rhs_exprs, copyObject(right_expr));
+	}
+
+	/* Punt if we didn't find at least one column to unique-ify */
+	if (semi_rhs_exprs == NIL)
+		return;
+
+	/*
+	 * The expressions we'd need to unique-ify mustn't be volatile.
+	 */
+	if (contain_volatile_functions((Node *) semi_rhs_exprs))
+		return;
+
+	/*
+	 * If we get here, we can unique-ify the semijoin's RHS using at least one
+	 * of sorting and hashing.  Save the information about how to do that.
+	 */
+	sjinfo->semi_can_btree = all_btree;
+	sjinfo->semi_can_hash = all_hash;
+	sjinfo->semi_operators = semi_operators;
+	sjinfo->semi_rhs_exprs = semi_rhs_exprs;
+}
+
+
+/*****************************************************************************
+ *
+ *	  QUALIFICATIONS
+ *
+ *****************************************************************************/
+
+/*
+ * distribute_qual_to_rels
+ *	  Add clause information to either the baserestrictinfo or joininfo list
+ *	  (depending on whether the clause is a join) of each base relation
+ *	  mentioned in the clause.  A RestrictInfo node is created and added to
+ *	  the appropriate list for each rel.  Alternatively, if the clause uses a
+ *	  mergejoinable operator and is not delayed by outer-join rules, enter
+ *	  the left- and right-side expressions into the query's list of
+ *	  EquivalenceClasses.  Alternatively, if the clause needs to be treated
+ *	  as belonging to a higher join level, just add it to postponed_qual_list.
+ *
+ * 'clause': the qual clause to be distributed
+ * 'below_outer_join': true if the qual is from a JOIN/ON that is below the
+ *		nullable side of a higher-level outer join
+ * 'jointype': type of join the qual is from (JOIN_INNER for a WHERE clause)
+ * 'security_level': security_level to assign to the qual
+ * 'qualscope': set of baserels the qual's syntactic scope covers
+ * 'ojscope': NULL if not an outer-join qual, else the minimum set of baserels
+ *		needed to form this join
+ * 'outerjoin_nonnullable': NULL if not an outer-join qual, else the set of
+ *		baserels appearing on the outer (nonnullable) side of the join
+ *		(for FULL JOIN this includes both sides of the join, and must in fact
+ *		equal qualscope)
+ * 'postponed_qual_list': list of PostponedQual structs, which we can add
+ *		this qual to if it turns out to belong to a higher join level.
+ *		Can be NULL if caller knows postponement is impossible.
+ *
+ * 'qualscope' identifies what level of JOIN the qual came from syntactically.
+ * 'ojscope' is needed if we decide to force the qual up to the outer-join
+ * level, which will be ojscope not necessarily qualscope.
+ *
+ * At the time this is called, root->join_info_list must contain entries for
+ * all and only those special joins that are syntactically below this qual.
+ */
+static void
+distribute_qual_to_rels(PlannerInfo *root, Node *clause,
+						bool below_outer_join,
+						JoinType jointype,
+						Index security_level,
+						Relids qualscope,
+						Relids ojscope,
+						Relids outerjoin_nonnullable,
+						List **postponed_qual_list)
+{
+	Relids		relids;
+	bool		is_pushed_down;
+	bool		outerjoin_delayed;
+	bool		pseudoconstant = false;
+	bool		maybe_equivalence;
+	bool		maybe_outer_join;
+	Relids		nullable_relids;
+	RestrictInfo *restrictinfo;
+
+	/*
+	 * Retrieve all relids mentioned within the clause.
+	 */
+	relids = pull_varnos(root, clause);
+
+	/*
+	 * In ordinary SQL, a WHERE or JOIN/ON clause can't reference any rels
+	 * that aren't within its syntactic scope; however, if we pulled up a
+	 * LATERAL subquery then we might find such references in quals that have
+	 * been pulled up.  We need to treat such quals as belonging to the join
+	 * level that includes every rel they reference.  Although we could make
+	 * pull_up_subqueries() place such quals correctly to begin with, it's
+	 * easier to handle it here.  When we find a clause that contains Vars
+	 * outside its syntactic scope, we add it to the postponed-quals list, and
+	 * process it once we've recursed back up to the appropriate join level.
+	 */
+	if (!bms_is_subset(relids, qualscope))
+	{
+		PostponedQual *pq = (PostponedQual *) palloc(sizeof(PostponedQual));
+
+		Assert(root->hasLateralRTEs);	/* shouldn't happen otherwise */
+		Assert(jointype == JOIN_INNER); /* mustn't postpone past outer join */
+		pq->qual = clause;
+		pq->relids = relids;
+		*postponed_qual_list = lappend(*postponed_qual_list, pq);
+		return;
+	}
+
+	/*
+	 * If it's an outer-join clause, also check that relids is a subset of
+	 * ojscope.  (This should not fail if the syntactic scope check passed.)
+	 */
+	if (ojscope && !bms_is_subset(relids, ojscope))
+		elog(ERROR, "JOIN qualification cannot refer to other relations");
+
+	/*
+	 * If the clause is variable-free, our normal heuristic for pushing it
+	 * down to just the mentioned rels doesn't work, because there are none.
+	 *
+	 * If the clause is an outer-join clause, we must force it to the OJ's
+	 * semantic level to preserve semantics.
+	 *
+	 * Otherwise, when the clause contains volatile functions, we force it to
+	 * be evaluated at its original syntactic level.  This preserves the
+	 * expected semantics.
+	 *
+	 * When the clause contains no volatile functions either, it is actually a
+	 * pseudoconstant clause that will not change value during any one
+	 * execution of the plan, and hence can be used as a one-time qual in a
+	 * gating Result plan node.  We put such a clause into the regular
+	 * RestrictInfo lists for the moment, but eventually createplan.c will
+	 * pull it out and make a gating Result node immediately above whatever
+	 * plan node the pseudoconstant clause is assigned to.  It's usually best
+	 * to put a gating node as high in the plan tree as possible. If we are
+	 * not below an outer join, we can actually push the pseudoconstant qual
+	 * all the way to the top of the tree.  If we are below an outer join, we
+	 * leave the qual at its original syntactic level (we could push it up to
+	 * just below the outer join, but that seems more complex than it's
+	 * worth).
+	 */
+	if (bms_is_empty(relids))
+	{
+		if (ojscope)
+		{
+			/* clause is attached to outer join, eval it there */
+			relids = bms_copy(ojscope);
+			/* mustn't use as gating qual, so don't mark pseudoconstant */
+		}
+		else
+		{
+			/* eval at original syntactic level */
+			relids = bms_copy(qualscope);
+			if (!contain_volatile_functions(clause))
+			{
+				/* mark as gating qual */
+				pseudoconstant = true;
+				/* tell createplan.c to check for gating quals */
+				root->hasPseudoConstantQuals = true;
+				/* if not below outer join, push it to top of tree */
+				if (!below_outer_join)
+				{
+					relids =
+						get_relids_in_jointree((Node *) root->parse->jointree,
+											   false);
+					qualscope = bms_copy(relids);
+				}
+			}
+		}
+	}
+
+	/*----------
+	 * Check to see if clause application must be delayed by outer-join
+	 * considerations.
+	 *
+	 * A word about is_pushed_down: we mark the qual as "pushed down" if
+	 * it is (potentially) applicable at a level different from its original
+	 * syntactic level.  This flag is used to distinguish OUTER JOIN ON quals
+	 * from other quals pushed down to the same joinrel.  The rules are:
+	 *		WHERE quals and INNER JOIN quals: is_pushed_down = true.
+	 *		Non-degenerate OUTER JOIN quals: is_pushed_down = false.
+	 *		Degenerate OUTER JOIN quals: is_pushed_down = true.
+	 * A "degenerate" OUTER JOIN qual is one that doesn't mention the
+	 * non-nullable side, and hence can be pushed down into the nullable side
+	 * without changing the join result.  It is correct to treat it as a
+	 * regular filter condition at the level where it is evaluated.
+	 *
+	 * Note: it is not immediately obvious that a simple boolean is enough
+	 * for this: if for some reason we were to attach a degenerate qual to
+	 * its original join level, it would need to be treated as an outer join
+	 * qual there.  However, this cannot happen, because all the rels the
+	 * clause mentions must be in the outer join's min_righthand, therefore
+	 * the join it needs must be formed before the outer join; and we always
+	 * attach quals to the lowest level where they can be evaluated.  But
+	 * if we were ever to re-introduce a mechanism for delaying evaluation
+	 * of "expensive" quals, this area would need work.
+	 *
+	 * Note: generally, use of is_pushed_down has to go through the macro
+	 * RINFO_IS_PUSHED_DOWN, because that flag alone is not always sufficient
+	 * to tell whether a clause must be treated as pushed-down in context.
+	 * This seems like another reason why it should perhaps be rethought.
+	 *----------
+	 */
+	if (bms_overlap(relids, outerjoin_nonnullable))
+	{
+		/*
+		 * The qual is attached to an outer join and mentions (some of the)
+		 * rels on the nonnullable side, so it's not degenerate.
+		 *
+		 * We can't use such a clause to deduce equivalence (the left and
+		 * right sides might be unequal above the join because one of them has
+		 * gone to NULL) ... but we might be able to use it for more limited
+		 * deductions, if it is mergejoinable.  So consider adding it to the
+		 * lists of set-aside outer-join clauses.
+		 */
+		is_pushed_down = false;
+		maybe_equivalence = false;
+		maybe_outer_join = true;
+
+		/* Check to see if must be delayed by lower outer join */
+		outerjoin_delayed = check_outerjoin_delay(root,
+												  &relids,
+												  &nullable_relids,
+												  false);
+
+		/*
+		 * Now force the qual to be evaluated exactly at the level of joining
+		 * corresponding to the outer join.  We cannot let it get pushed down
+		 * into the nonnullable side, since then we'd produce no output rows,
+		 * rather than the intended single null-extended row, for any
+		 * nonnullable-side rows failing the qual.
+		 *
+		 * (Do this step after calling check_outerjoin_delay, because that
+		 * trashes relids.)
+		 */
+		Assert(ojscope);
+		relids = ojscope;
+		Assert(!pseudoconstant);
+	}
+	else
+	{
+		/*
+		 * Normal qual clause or degenerate outer-join clause.  Either way, we
+		 * can mark it as pushed-down.
+		 */
+		is_pushed_down = true;
+
+		/* Check to see if must be delayed by lower outer join */
+		outerjoin_delayed = check_outerjoin_delay(root,
+												  &relids,
+												  &nullable_relids,
+												  true);
+
+		if (outerjoin_delayed)
+		{
+			/* Should still be a subset of current scope ... */
+			Assert(root->hasLateralRTEs || bms_is_subset(relids, qualscope));
+			Assert(ojscope == NULL || bms_is_subset(relids, ojscope));
+
+			/*
+			 * Because application of the qual will be delayed by outer join,
+			 * we mustn't assume its vars are equal everywhere.
+			 */
+			maybe_equivalence = false;
+
+			/*
+			 * It's possible that this is an IS NULL clause that's redundant
+			 * with a lower antijoin; if so we can just discard it.  We need
+			 * not test in any of the other cases, because this will only be
+			 * possible for pushed-down, delayed clauses.
+			 */
+			if (check_redundant_nullability_qual(root, clause))
+				return;
+		}
+		else
+		{
+			/*
+			 * Qual is not delayed by any lower outer-join restriction, so we
+			 * can consider feeding it to the equivalence machinery. However,
+			 * if it's itself within an outer-join clause, treat it as though
+			 * it appeared below that outer join (note that we can only get
+			 * here when the clause references only nullable-side rels).
+			 */
+			maybe_equivalence = true;
+			if (outerjoin_nonnullable != NULL)
+				below_outer_join = true;
+		}
+
+		/*
+		 * Since it doesn't mention the LHS, it's certainly not useful as a
+		 * set-aside OJ clause, even if it's in an OJ.
+		 */
+		maybe_outer_join = false;
+	}
+
+	/*
+	 * Build the RestrictInfo node itself.
+	 */
+	restrictinfo = make_restrictinfo(root,
+									 (Expr *) clause,
+									 is_pushed_down,
+									 outerjoin_delayed,
+									 pseudoconstant,
+									 security_level,
+									 relids,
+									 outerjoin_nonnullable,
+									 nullable_relids);
+
+	/*
+	 * If it's a join clause (either naturally, or because delayed by
+	 * outer-join rules), add vars used in the clause to targetlists of their
+	 * relations, so that they will be emitted by the plan nodes that scan
+	 * those relations (else they won't be available at the join node!).
+	 *
+	 * Note: if the clause gets absorbed into an EquivalenceClass then this
+	 * may be unnecessary, but for now we have to do it to cover the case
+	 * where the EC becomes ec_broken and we end up reinserting the original
+	 * clauses into the plan.
+	 */
+	if (bms_membership(relids) == BMS_MULTIPLE)
+	{
+		List	   *vars = pull_var_clause(clause,
+										   PVC_RECURSE_AGGREGATES |
+										   PVC_RECURSE_WINDOWFUNCS |
+										   PVC_INCLUDE_PLACEHOLDERS);
+
+		add_vars_to_targetlist(root, vars, relids, false);
+		list_free(vars);
+	}
+
+	/*
+	 * We check "mergejoinability" of every clause, not only join clauses,
+	 * because we want to know about equivalences between vars of the same
+	 * relation, or between vars and consts.
+	 */
+	check_mergejoinable(restrictinfo);
+
+	/*
+	 * If it is a true equivalence clause, send it to the EquivalenceClass
+	 * machinery.  We do *not* attach it directly to any restriction or join
+	 * lists.  The EC code will propagate it to the appropriate places later.
+	 *
+	 * If the clause has a mergejoinable operator and is not
+	 * outerjoin-delayed, yet isn't an equivalence because it is an outer-join
+	 * clause, the EC code may yet be able to do something with it.  We add it
+	 * to appropriate lists for further consideration later.  Specifically:
+	 *
+	 * If it is a left or right outer-join qualification that relates the two
+	 * sides of the outer join (no funny business like leftvar1 = leftvar2 +
+	 * rightvar), we add it to root->left_join_clauses or
+	 * root->right_join_clauses according to which side the nonnullable
+	 * variable appears on.
+	 *
+	 * If it is a full outer-join qualification, we add it to
+	 * root->full_join_clauses.  (Ideally we'd discard cases that aren't
+	 * leftvar = rightvar, as we do for left/right joins, but this routine
+	 * doesn't have the info needed to do that; and the current usage of the
+	 * full_join_clauses list doesn't require that, so it's not currently
+	 * worth complicating this routine's API to make it possible.)
+	 *
+	 * If none of the above hold, pass it off to
+	 * distribute_restrictinfo_to_rels().
+	 *
+	 * In all cases, it's important to initialize the left_ec and right_ec
+	 * fields of a mergejoinable clause, so that all possibly mergejoinable
+	 * expressions have representations in EquivalenceClasses.  If
+	 * process_equivalence is successful, it will take care of that;
+	 * otherwise, we have to call initialize_mergeclause_eclasses to do it.
+	 */
+	if (restrictinfo->mergeopfamilies)
+	{
+		if (maybe_equivalence)
+		{
+			if (check_equivalence_delay(root, restrictinfo) &&
+				process_equivalence(root, &restrictinfo, below_outer_join))
+				return;
+			/* EC rejected it, so set left_ec/right_ec the hard way ... */
+			if (restrictinfo->mergeopfamilies)	/* EC might have changed this */
+				initialize_mergeclause_eclasses(root, restrictinfo);
+			/* ... and fall through to distribute_restrictinfo_to_rels */
+		}
+		else if (maybe_outer_join && restrictinfo->can_join)
+		{
+			/* we need to set up left_ec/right_ec the hard way */
+			initialize_mergeclause_eclasses(root, restrictinfo);
+			/* now see if it should go to any outer-join lists */
+			if (bms_is_subset(restrictinfo->left_relids,
+							  outerjoin_nonnullable) &&
+				!bms_overlap(restrictinfo->right_relids,
+							 outerjoin_nonnullable))
+			{
+				/* we have outervar = innervar */
+				root->left_join_clauses = lappend(root->left_join_clauses,
+												  restrictinfo);
+				return;
+			}
+			if (bms_is_subset(restrictinfo->right_relids,
+							  outerjoin_nonnullable) &&
+				!bms_overlap(restrictinfo->left_relids,
+							 outerjoin_nonnullable))
+			{
+				/* we have innervar = outervar */
+				root->right_join_clauses = lappend(root->right_join_clauses,
+												   restrictinfo);
+				return;
+			}
+			if (jointype == JOIN_FULL)
+			{
+				/* FULL JOIN (above tests cannot match in this case) */
+				root->full_join_clauses = lappend(root->full_join_clauses,
+												  restrictinfo);
+				return;
+			}
+			/* nope, so fall through to distribute_restrictinfo_to_rels */
+		}
+		else
+		{
+			/* we still need to set up left_ec/right_ec */
+			initialize_mergeclause_eclasses(root, restrictinfo);
+		}
+	}
+
+	/* No EC special case applies, so push it into the clause lists */
+	distribute_restrictinfo_to_rels(root, restrictinfo);
+}
+
+/*
+ * check_outerjoin_delay
+ *		Detect whether a qual referencing the given relids must be delayed
+ *		in application due to the presence of a lower outer join, and/or
+ *		may force extra delay of higher-level outer joins.
+ *
+ * If the qual must be delayed, add relids to *relids_p to reflect the lowest
+ * safe level for evaluating the qual, and return true.  Any extra delay for
+ * higher-level joins is reflected by setting delay_upper_joins to true in
+ * SpecialJoinInfo structs.  We also compute nullable_relids, the set of
+ * referenced relids that are nullable by lower outer joins (note that this
+ * can be nonempty even for a non-delayed qual).
+ *
+ * For an is_pushed_down qual, we can evaluate the qual as soon as (1) we have
+ * all the rels it mentions, and (2) we are at or above any outer joins that
+ * can null any of these rels and are below the syntactic location of the
+ * given qual.  We must enforce (2) because pushing down such a clause below
+ * the OJ might cause the OJ to emit null-extended rows that should not have
+ * been formed, or that should have been rejected by the clause.  (This is
+ * only an issue for non-strict quals, since if we can prove a qual mentioning
+ * only nullable rels is strict, we'd have reduced the outer join to an inner
+ * join in reduce_outer_joins().)
+ *
+ * To enforce (2), scan the join_info_list and merge the required-relid sets of
+ * any such OJs into the clause's own reference list.  At the time we are
+ * called, the join_info_list contains only outer joins below this qual.  We
+ * have to repeat the scan until no new relids get added; this ensures that
+ * the qual is suitably delayed regardless of the order in which OJs get
+ * executed.  As an example, if we have one OJ with LHS=A, RHS=B, and one with
+ * LHS=B, RHS=C, it is implied that these can be done in either order; if the
+ * B/C join is done first then the join to A can null C, so a qual actually
+ * mentioning only C cannot be applied below the join to A.
+ *
+ * For a non-pushed-down qual, this isn't going to determine where we place the
+ * qual, but we need to determine outerjoin_delayed and nullable_relids anyway
+ * for use later in the planning process.
+ *
+ * Lastly, a pushed-down qual that references the nullable side of any current
+ * join_info_list member and has to be evaluated above that OJ (because its
+ * required relids overlap the LHS too) causes that OJ's delay_upper_joins
+ * flag to be set true.  This will prevent any higher-level OJs from
+ * being interchanged with that OJ, which would result in not having any
+ * correct place to evaluate the qual.  (The case we care about here is a
+ * sub-select WHERE clause within the RHS of some outer join.  The WHERE
+ * clause must effectively be treated as a degenerate clause of that outer
+ * join's condition.  Rather than trying to match such clauses with joins
+ * directly, we set delay_upper_joins here, and when the upper outer join
+ * is processed by make_outerjoininfo, it will refrain from allowing the
+ * two OJs to commute.)
+ */
+static bool
+check_outerjoin_delay(PlannerInfo *root,
+					  Relids *relids_p, /* in/out parameter */
+					  Relids *nullable_relids_p,	/* output parameter */
+					  bool is_pushed_down)
+{
+	Relids		relids;
+	Relids		nullable_relids;
+	bool		outerjoin_delayed;
+	bool		found_some;
+
+	/* fast path if no special joins */
+	if (root->join_info_list == NIL)
+	{
+		*nullable_relids_p = NULL;
+		return false;
+	}
+
+	/* must copy relids because we need the original value at the end */
+	relids = bms_copy(*relids_p);
+	nullable_relids = NULL;
+	outerjoin_delayed = false;
+	do
+	{
+		ListCell   *l;
+
+		found_some = false;
+		foreach(l, root->join_info_list)
+		{
+			SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
+
+			/* do we reference any nullable rels of this OJ? */
+			if (bms_overlap(relids, sjinfo->min_righthand) ||
+				(sjinfo->jointype == JOIN_FULL &&
+				 bms_overlap(relids, sjinfo->min_lefthand)))
+			{
+				/* yes; have we included all its rels in relids? */
+				if (!bms_is_subset(sjinfo->min_lefthand, relids) ||
+					!bms_is_subset(sjinfo->min_righthand, relids))
+				{
+					/* no, so add them in */
+					relids = bms_add_members(relids, sjinfo->min_lefthand);
+					relids = bms_add_members(relids, sjinfo->min_righthand);
+					outerjoin_delayed = true;
+					/* we'll need another iteration */
+					found_some = true;
+				}
+				/* track all the nullable rels of relevant OJs */
+				nullable_relids = bms_add_members(nullable_relids,
+												  sjinfo->min_righthand);
+				if (sjinfo->jointype == JOIN_FULL)
+					nullable_relids = bms_add_members(nullable_relids,
+													  sjinfo->min_lefthand);
+				/* set delay_upper_joins if needed */
+				if (is_pushed_down && sjinfo->jointype != JOIN_FULL &&
+					bms_overlap(relids, sjinfo->min_lefthand))
+					sjinfo->delay_upper_joins = true;
+			}
+		}
+	} while (found_some);
+
+	/* identify just the actually-referenced nullable rels */
+	nullable_relids = bms_int_members(nullable_relids, *relids_p);
+
+	/* replace *relids_p, and return nullable_relids */
+	bms_free(*relids_p);
+	*relids_p = relids;
+	*nullable_relids_p = nullable_relids;
+	return outerjoin_delayed;
+}
+
+/*
+ * check_equivalence_delay
+ *		Detect whether a potential equivalence clause is rendered unsafe
+ *		by outer-join-delay considerations.  Return true if it's safe.
+ *
+ * The initial tests in distribute_qual_to_rels will consider a mergejoinable
+ * clause to be a potential equivalence clause if it is not outerjoin_delayed.
+ * But since the point of equivalence processing is that we will recombine the
+ * two sides of the clause with others, we have to check that each side
+ * satisfies the not-outerjoin_delayed condition on its own; otherwise it might
+ * not be safe to evaluate everywhere we could place a derived equivalence
+ * condition.
+ */
+static bool
+check_equivalence_delay(PlannerInfo *root,
+						RestrictInfo *restrictinfo)
+{
+	Relids		relids;
+	Relids		nullable_relids;
+
+	/* fast path if no special joins */
+	if (root->join_info_list == NIL)
+		return true;
+
+	/* must copy restrictinfo's relids to avoid changing it */
+	relids = bms_copy(restrictinfo->left_relids);
+	/* check left side does not need delay */
+	if (check_outerjoin_delay(root, &relids, &nullable_relids, true))
+		return false;
+
+	/* and similarly for the right side */
+	relids = bms_copy(restrictinfo->right_relids);
+	if (check_outerjoin_delay(root, &relids, &nullable_relids, true))
+		return false;
+
+	return true;
+}
+
+/*
+ * check_redundant_nullability_qual
+ *	  Check to see if the qual is an IS NULL qual that is redundant with
+ *	  a lower JOIN_ANTI join.
+ *
+ * We want to suppress redundant IS NULL quals, not so much to save cycles
+ * as to avoid generating bogus selectivity estimates for them.  So if
+ * redundancy is detected here, distribute_qual_to_rels() just throws away
+ * the qual.
+ */
+static bool
+check_redundant_nullability_qual(PlannerInfo *root, Node *clause)
+{
+	Var		   *forced_null_var;
+	Index		forced_null_rel;
+	ListCell   *lc;
+
+	/* Check for IS NULL, and identify the Var forced to NULL */
+	forced_null_var = find_forced_null_var(clause);
+	if (forced_null_var == NULL)
+		return false;
+	forced_null_rel = forced_null_var->varno;
+
+	/*
+	 * If the Var comes from the nullable side of a lower antijoin, the IS
+	 * NULL condition is necessarily true.
+	 */
+	foreach(lc, root->join_info_list)
+	{
+		SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
+
+		if (sjinfo->jointype == JOIN_ANTI &&
+			bms_is_member(forced_null_rel, sjinfo->syn_righthand))
+			return true;
+	}
+
+	return false;
+}
+
+/*
+ * distribute_restrictinfo_to_rels
+ *	  Push a completed RestrictInfo into the proper restriction or join
+ *	  clause list(s).
+ *
+ * This is the last step of distribute_qual_to_rels() for ordinary qual
+ * clauses.  Clauses that are interesting for equivalence-class processing
+ * are diverted to the EC machinery, but may ultimately get fed back here.
+ */
+void
+distribute_restrictinfo_to_rels(PlannerInfo *root,
+								RestrictInfo *restrictinfo)
+{
+	Relids		relids = restrictinfo->required_relids;
+	RelOptInfo *rel;
+
+	switch (bms_membership(relids))
+	{
+		case BMS_SINGLETON:
+
+			/*
+			 * There is only one relation participating in the clause, so it
+			 * is a restriction clause for that relation.
+			 */
+			rel = find_base_rel(root, bms_singleton_member(relids));
+
+			/* Add clause to rel's restriction list */
+			rel->baserestrictinfo = lappend(rel->baserestrictinfo,
+											restrictinfo);
+			/* Update security level info */
+			rel->baserestrict_min_security = Min(rel->baserestrict_min_security,
+												 restrictinfo->security_level);
+			break;
+		case BMS_MULTIPLE:
+
+			/*
+			 * The clause is a join clause, since there is more than one rel
+			 * in its relid set.
+			 */
+
+			/*
+			 * Check for hashjoinable operators.  (We don't bother setting the
+			 * hashjoin info except in true join clauses.)
+			 */
+			check_hashjoinable(restrictinfo);
+
+			/*
+			 * Likewise, check if the clause is suitable to be used with a
+			 * Memoize node to cache inner tuples during a parameterized
+			 * nested loop.
+			 */
+			check_memoizable(restrictinfo);
+
+			/*
+			 * Add clause to the join lists of all the relevant relations.
+			 */
+			add_join_clause_to_rels(root, restrictinfo, relids);
+			break;
+		default:
+
+			/*
+			 * clause references no rels, and therefore we have no place to
+			 * attach it.  Shouldn't get here if callers are working properly.
+			 */
+			elog(ERROR, "cannot cope with variable-free clause");
+			break;
+	}
+}
+
+/*
+ * process_implied_equality
+ *	  Create a restrictinfo item that says "item1 op item2", and push it
+ *	  into the appropriate lists.  (In practice opno is always a btree
+ *	  equality operator.)
+ *
+ * "qualscope" is the nominal syntactic level to impute to the restrictinfo.
+ * This must contain at least all the rels used in the expressions, but it
+ * is used only to set the qual application level when both exprs are
+ * variable-free.  Otherwise the qual is applied at the lowest join level
+ * that provides all its variables.
+ *
+ * "nullable_relids" is the set of relids used in the expressions that are
+ * potentially nullable below the expressions.  (This has to be supplied by
+ * caller because this function is used after deconstruct_jointree, so we
+ * don't have knowledge of where the clause items came from.)
+ *
+ * "security_level" is the security level to assign to the new restrictinfo.
+ *
+ * "both_const" indicates whether both items are known pseudo-constant;
+ * in this case it is worth applying eval_const_expressions() in case we
+ * can produce constant TRUE or constant FALSE.  (Otherwise it's not,
+ * because the expressions went through eval_const_expressions already.)
+ *
+ * Returns the generated RestrictInfo, if any.  The result will be NULL
+ * if both_const is true and we successfully reduced the clause to
+ * constant TRUE.
+ *
+ * Note: this function will copy item1 and item2, but it is caller's
+ * responsibility to make sure that the Relids parameters are fresh copies
+ * not shared with other uses.
+ *
+ * Note: we do not do initialize_mergeclause_eclasses() here.  It is
+ * caller's responsibility that left_ec/right_ec be set as necessary.
+ */
+RestrictInfo *
+process_implied_equality(PlannerInfo *root,
+						 Oid opno,
+						 Oid collation,
+						 Expr *item1,
+						 Expr *item2,
+						 Relids qualscope,
+						 Relids nullable_relids,
+						 Index security_level,
+						 bool below_outer_join,
+						 bool both_const)
+{
+	RestrictInfo *restrictinfo;
+	Node	   *clause;
+	Relids		relids;
+	bool		pseudoconstant = false;
+
+	/*
+	 * Build the new clause.  Copy to ensure it shares no substructure with
+	 * original (this is necessary in case there are subselects in there...)
+	 */
+	clause = (Node *) make_opclause(opno,
+									BOOLOID,	/* opresulttype */
+									false,	/* opretset */
+									copyObject(item1),
+									copyObject(item2),
+									InvalidOid,
+									collation);
+
+	/* If both constant, try to reduce to a boolean constant. */
+	if (both_const)
+	{
+		clause = eval_const_expressions(root, clause);
+
+		/* If we produced const TRUE, just drop the clause */
+		if (clause && IsA(clause, Const))
+		{
+			Const	   *cclause = (Const *) clause;
+
+			Assert(cclause->consttype == BOOLOID);
+			if (!cclause->constisnull && DatumGetBool(cclause->constvalue))
+				return NULL;
+		}
+	}
+
+	/*
+	 * The rest of this is a very cut-down version of distribute_qual_to_rels.
+	 * We can skip most of the work therein, but there are a couple of special
+	 * cases we still have to handle.
+	 *
+	 * Retrieve all relids mentioned within the possibly-simplified clause.
+	 */
+	relids = pull_varnos(root, clause);
+	Assert(bms_is_subset(relids, qualscope));
+
+	/*
+	 * If the clause is variable-free, our normal heuristic for pushing it
+	 * down to just the mentioned rels doesn't work, because there are none.
+	 * Apply at the given qualscope, or at the top of tree if it's nonvolatile
+	 * (which it very likely is, but we'll check, just to be sure).
+	 */
+	if (bms_is_empty(relids))
+	{
+		/* eval at original syntactic level */
+		relids = bms_copy(qualscope);
+		if (!contain_volatile_functions(clause))
+		{
+			/* mark as gating qual */
+			pseudoconstant = true;
+			/* tell createplan.c to check for gating quals */
+			root->hasPseudoConstantQuals = true;
+			/* if not below outer join, push it to top of tree */
+			if (!below_outer_join)
+			{
+				relids =
+					get_relids_in_jointree((Node *) root->parse->jointree,
+										   false);
+			}
+		}
+	}
+
+	/*
+	 * Build the RestrictInfo node itself.
+	 */
+	restrictinfo = make_restrictinfo(root,
+									 (Expr *) clause,
+									 true,	/* is_pushed_down */
+									 false, /* outerjoin_delayed */
+									 pseudoconstant,
+									 security_level,
+									 relids,
+									 NULL,	/* outer_relids */
+									 nullable_relids);
+
+	/*
+	 * If it's a join clause, add vars used in the clause to targetlists of
+	 * their relations, so that they will be emitted by the plan nodes that
+	 * scan those relations (else they won't be available at the join node!).
+	 *
+	 * Typically, we'd have already done this when the component expressions
+	 * were first seen by distribute_qual_to_rels; but it is possible that
+	 * some of the Vars could have missed having that done because they only
+	 * appeared in single-relation clauses originally.  So do it here for
+	 * safety.
+	 */
+	if (bms_membership(relids) == BMS_MULTIPLE)
+	{
+		List	   *vars = pull_var_clause(clause,
+										   PVC_RECURSE_AGGREGATES |
+										   PVC_RECURSE_WINDOWFUNCS |
+										   PVC_INCLUDE_PLACEHOLDERS);
+
+		add_vars_to_targetlist(root, vars, relids, false);
+		list_free(vars);
+	}
+
+	/*
+	 * Check mergejoinability.  This will usually succeed, since the op came
+	 * from an EquivalenceClass; but we could have reduced the original clause
+	 * to a constant.
+	 */
+	check_mergejoinable(restrictinfo);
+
+	/*
+	 * Note we don't do initialize_mergeclause_eclasses(); the caller can
+	 * handle that much more cheaply than we can.  It's okay to call
+	 * distribute_restrictinfo_to_rels() before that happens.
+	 */
+
+	/*
+	 * Push the new clause into all the appropriate restrictinfo lists.
+	 */
+	distribute_restrictinfo_to_rels(root, restrictinfo);
+
+	return restrictinfo;
+}
+
+/*
+ * build_implied_join_equality --- build a RestrictInfo for a derived equality
+ *
+ * This overlaps the functionality of process_implied_equality(), but we
+ * must not push the RestrictInfo into the joininfo tree.
+ *
+ * Note: this function will copy item1 and item2, but it is caller's
+ * responsibility to make sure that the Relids parameters are fresh copies
+ * not shared with other uses.
+ *
+ * Note: we do not do initialize_mergeclause_eclasses() here.  It is
+ * caller's responsibility that left_ec/right_ec be set as necessary.
+ */
+RestrictInfo *
+build_implied_join_equality(PlannerInfo *root,
+							Oid opno,
+							Oid collation,
+							Expr *item1,
+							Expr *item2,
+							Relids qualscope,
+							Relids nullable_relids,
+							Index security_level)
+{
+	RestrictInfo *restrictinfo;
+	Expr	   *clause;
+
+	/*
+	 * Build the new clause.  Copy to ensure it shares no substructure with
+	 * original (this is necessary in case there are subselects in there...)
+	 */
+	clause = make_opclause(opno,
+						   BOOLOID, /* opresulttype */
+						   false,	/* opretset */
+						   copyObject(item1),
+						   copyObject(item2),
+						   InvalidOid,
+						   collation);
+
+	/*
+	 * Build the RestrictInfo node itself.
+	 */
+	restrictinfo = make_restrictinfo(root,
+									 clause,
+									 true,	/* is_pushed_down */
+									 false, /* outerjoin_delayed */
+									 false, /* pseudoconstant */
+									 security_level,	/* security_level */
+									 qualscope, /* required_relids */
+									 NULL,	/* outer_relids */
+									 nullable_relids);	/* nullable_relids */
+
+	/* Set mergejoinability/hashjoinability flags */
+	check_mergejoinable(restrictinfo);
+	check_hashjoinable(restrictinfo);
+	check_memoizable(restrictinfo);
+
+	return restrictinfo;
+}
+
+
+/*
+ * match_foreign_keys_to_quals
+ *		Match foreign-key constraints to equivalence classes and join quals
+ *
+ * The idea here is to see which query join conditions match equality
+ * constraints of a foreign-key relationship.  For such join conditions,
+ * we can use the FK semantics to make selectivity estimates that are more
+ * reliable than estimating from statistics, especially for multiple-column
+ * FKs, where the normal assumption of independent conditions tends to fail.
+ *
+ * In this function we annotate the ForeignKeyOptInfos in root->fkey_list
+ * with info about which eclasses and join qual clauses they match, and
+ * discard any ForeignKeyOptInfos that are irrelevant for the query.
+ */
+void
+match_foreign_keys_to_quals(PlannerInfo *root)
+{
+	List	   *newlist = NIL;
+	ListCell   *lc;
+
+	foreach(lc, root->fkey_list)
+	{
+		ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+		RelOptInfo *con_rel;
+		RelOptInfo *ref_rel;
+		int			colno;
+
+		/*
+		 * Either relid might identify a rel that is in the query's rtable but
+		 * isn't referenced by the jointree so won't have a RelOptInfo.  Hence
+		 * don't use find_base_rel() here.  We can ignore such FKs.
+		 */
+		if (fkinfo->con_relid >= root->simple_rel_array_size ||
+			fkinfo->ref_relid >= root->simple_rel_array_size)
+			continue;			/* just paranoia */
+		con_rel = root->simple_rel_array[fkinfo->con_relid];
+		if (con_rel == NULL)
+			continue;
+		ref_rel = root->simple_rel_array[fkinfo->ref_relid];
+		if (ref_rel == NULL)
+			continue;
+
+		/*
+		 * Ignore FK unless both rels are baserels.  This gets rid of FKs that
+		 * link to inheritance child rels (otherrels) and those that link to
+		 * rels removed by join removal (dead rels).
+		 */
+		if (con_rel->reloptkind != RELOPT_BASEREL ||
+			ref_rel->reloptkind != RELOPT_BASEREL)
+			continue;
+
+		/*
+		 * Scan the columns and try to match them to eclasses and quals.
+		 *
+		 * Note: for simple inner joins, any match should be in an eclass.
+		 * "Loose" quals that syntactically match an FK equality must have
+		 * been rejected for EC status because they are outer-join quals or
+		 * similar.  We can still consider them to match the FK if they are
+		 * not outerjoin_delayed.
+		 */
+		for (colno = 0; colno < fkinfo->nkeys; colno++)
+		{
+			EquivalenceClass *ec;
+			AttrNumber	con_attno,
+						ref_attno;
+			Oid			fpeqop;
+			ListCell   *lc2;
+
+			ec = match_eclasses_to_foreign_key_col(root, fkinfo, colno);
+			/* Don't bother looking for loose quals if we got an EC match */
+			if (ec != NULL)
+			{
+				fkinfo->nmatched_ec++;
+				if (ec->ec_has_const)
+					fkinfo->nconst_ec++;
+				continue;
+			}
+
+			/*
+			 * Scan joininfo list for relevant clauses.  Either rel's joininfo
+			 * list would do equally well; we use con_rel's.
+			 */
+			con_attno = fkinfo->conkey[colno];
+			ref_attno = fkinfo->confkey[colno];
+			fpeqop = InvalidOid;	/* we'll look this up only if needed */
+
+			foreach(lc2, con_rel->joininfo)
+			{
+				RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc2);
+				OpExpr	   *clause = (OpExpr *) rinfo->clause;
+				Var		   *leftvar;
+				Var		   *rightvar;
+
+				/* Ignore outerjoin-delayed clauses */
+				if (rinfo->outerjoin_delayed)
+					continue;
+
+				/* Only binary OpExprs are useful for consideration */
+				if (!IsA(clause, OpExpr) ||
+					list_length(clause->args) != 2)
+					continue;
+				leftvar = (Var *) get_leftop((Expr *) clause);
+				rightvar = (Var *) get_rightop((Expr *) clause);
+
+				/* Operands must be Vars, possibly with RelabelType */
+				while (leftvar && IsA(leftvar, RelabelType))
+					leftvar = (Var *) ((RelabelType *) leftvar)->arg;
+				if (!(leftvar && IsA(leftvar, Var)))
+					continue;
+				while (rightvar && IsA(rightvar, RelabelType))
+					rightvar = (Var *) ((RelabelType *) rightvar)->arg;
+				if (!(rightvar && IsA(rightvar, Var)))
+					continue;
+
+				/* Now try to match the vars to the current foreign key cols */
+				if (fkinfo->ref_relid == leftvar->varno &&
+					ref_attno == leftvar->varattno &&
+					fkinfo->con_relid == rightvar->varno &&
+					con_attno == rightvar->varattno)
+				{
+					/* Vars match, but is it the right operator? */
+					if (clause->opno == fkinfo->conpfeqop[colno])
+					{
+						fkinfo->rinfos[colno] = lappend(fkinfo->rinfos[colno],
+														rinfo);
+						fkinfo->nmatched_ri++;
+					}
+				}
+				else if (fkinfo->ref_relid == rightvar->varno &&
+						 ref_attno == rightvar->varattno &&
+						 fkinfo->con_relid == leftvar->varno &&
+						 con_attno == leftvar->varattno)
+				{
+					/*
+					 * Reverse match, must check commutator operator.  Look it
+					 * up if we didn't already.  (In the worst case we might
+					 * do multiple lookups here, but that would require an FK
+					 * equality operator without commutator, which is
+					 * unlikely.)
+					 */
+					if (!OidIsValid(fpeqop))
+						fpeqop = get_commutator(fkinfo->conpfeqop[colno]);
+					if (clause->opno == fpeqop)
+					{
+						fkinfo->rinfos[colno] = lappend(fkinfo->rinfos[colno],
+														rinfo);
+						fkinfo->nmatched_ri++;
+					}
+				}
+			}
+			/* If we found any matching loose quals, count col as matched */
+			if (fkinfo->rinfos[colno])
+				fkinfo->nmatched_rcols++;
+		}
+
+		/*
+		 * Currently, we drop multicolumn FKs that aren't fully matched to the
+		 * query.  Later we might figure out how to derive some sort of
+		 * estimate from them, in which case this test should be weakened to
+		 * "if ((fkinfo->nmatched_ec + fkinfo->nmatched_rcols) > 0)".
+		 */
+		if ((fkinfo->nmatched_ec + fkinfo->nmatched_rcols) == fkinfo->nkeys)
+			newlist = lappend(newlist, fkinfo);
+	}
+	/* Replace fkey_list, thereby discarding any useless entries */
+	root->fkey_list = newlist;
+}
+
+
+/*****************************************************************************
+ *
+ *	 CHECKS FOR MERGEJOINABLE AND HASHJOINABLE CLAUSES
+ *
+ *****************************************************************************/
+
+/*
+ * check_mergejoinable
+ *	  If the restrictinfo's clause is mergejoinable, set the mergejoin
+ *	  info fields in the restrictinfo.
+ *
+ *	  Currently, we support mergejoin for binary opclauses where
+ *	  the operator is a mergejoinable operator.  The arguments can be
+ *	  anything --- as long as there are no volatile functions in them.
+ */
+static void
+check_mergejoinable(RestrictInfo *restrictinfo)
+{
+	Expr	   *clause = restrictinfo->clause;
+	Oid			opno;
+	Node	   *leftarg;
+
+	if (restrictinfo->pseudoconstant)
+		return;
+	if (!is_opclause(clause))
+		return;
+	if (list_length(((OpExpr *) clause)->args) != 2)
+		return;
+
+	opno = ((OpExpr *) clause)->opno;
+	leftarg = linitial(((OpExpr *) clause)->args);
+
+	if (op_mergejoinable(opno, exprType(leftarg)) &&
+		!contain_volatile_functions((Node *) restrictinfo))
+		restrictinfo->mergeopfamilies = get_mergejoin_opfamilies(opno);
+
+	/*
+	 * Note: op_mergejoinable is just a hint; if we fail to find the operator
+	 * in any btree opfamilies, mergeopfamilies remains NIL and so the clause
+	 * is not treated as mergejoinable.
+	 */
+}
+
+/*
+ * check_hashjoinable
+ *	  If the restrictinfo's clause is hashjoinable, set the hashjoin
+ *	  info fields in the restrictinfo.
+ *
+ *	  Currently, we support hashjoin for binary opclauses where
+ *	  the operator is a hashjoinable operator.  The arguments can be
+ *	  anything --- as long as there are no volatile functions in them.
+ */
+static void
+check_hashjoinable(RestrictInfo *restrictinfo)
+{
+	Expr	   *clause = restrictinfo->clause;
+	Oid			opno;
+	Node	   *leftarg;
+
+	if (restrictinfo->pseudoconstant)
+		return;
+	if (!is_opclause(clause))
+		return;
+	if (list_length(((OpExpr *) clause)->args) != 2)
+		return;
+
+	opno = ((OpExpr *) clause)->opno;
+	leftarg = linitial(((OpExpr *) clause)->args);
+
+	if (op_hashjoinable(opno, exprType(leftarg)) &&
+		!contain_volatile_functions((Node *) restrictinfo))
+		restrictinfo->hashjoinoperator = opno;
+}
+
+/*
+ * check_memoizable
+ *	  If the restrictinfo's clause is suitable to be used for a Memoize node,
+ *	  set the hasheqoperator to the hash equality operator that will be needed
+ *	  during caching.
+ */
+static void
+check_memoizable(RestrictInfo *restrictinfo)
+{
+	TypeCacheEntry *typentry;
+	Expr	   *clause = restrictinfo->clause;
+	Oid			lefttype;
+	Oid			righttype;
+
+	if (restrictinfo->pseudoconstant)
+		return;
+	if (!is_opclause(clause))
+		return;
+	if (list_length(((OpExpr *) clause)->args) != 2)
+		return;
+
+	lefttype = exprType(linitial(((OpExpr *) clause)->args));
+	righttype = exprType(lsecond(((OpExpr *) clause)->args));
+
+	/*
+	 * Really there should be a field for both the left and right hash
+	 * equality operator, however, in v14, there's only a single field in
+	 * RestrictInfo to record the operator in, so we must insist that the left
+	 * and right types match.
+	 */
+	if (lefttype != righttype)
+		return;
+
+	typentry = lookup_type_cache(lefttype, TYPECACHE_HASH_PROC |
+										   TYPECACHE_EQ_OPR);
+
+	if (!OidIsValid(typentry->hash_proc) || !OidIsValid(typentry->eq_opr))
+		return;
+
+	restrictinfo->hasheqoperator = typentry->eq_opr;
+}