Make Vars be outer-join-aware.

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

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

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

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

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

Patch by me; thanks to Richard Guo for review.

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

13 files changed, 216 insertions, 59 deletions

diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h
index 823c70c47cc..c1ce0b76e14 100644
--- a/src/include/catalog/catversion.h
+++ b/src/include/catalog/catversion.h
@@ -57,6 +57,6 @@
  */
 
 /*							yyyymmddN */
-#define CATALOG_VERSION_NO	202301232
+#define CATALOG_VERSION_NO	202301301
 
 #endif
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index 89335d95e7b..fbbbe647a43 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -1090,6 +1090,14 @@ typedef struct RangeTblEntry
 	 * alias Vars are generated only for merged columns).  We keep these
 	 * entries only because they're needed in expandRTE() and similar code.
 	 *
+	 * Vars appearing within joinaliasvars are marked with varnullingrels sets
+	 * that describe the nulling effects of this join and lower ones.  This is
+	 * essential for FULL JOIN cases, because the COALESCE expression only
+	 * describes the semantics correctly if its inputs have been nulled by the
+	 * join.  For other cases, it allows expandRTE() to generate a valid
+	 * representation of the join's output without consulting additional
+	 * parser state.
+	 *
 	 * Within a Query loaded from a stored rule, it is possible for non-merged
 	 * joinaliasvars items to be null pointers, which are placeholders for
 	 * (necessarily unreferenced) columns dropped since the rule was made.
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 2d1d8f4bcdf..630a0440895 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -249,14 +249,26 @@ struct PlannerInfo
 	struct AppendRelInfo **append_rel_array pg_node_attr(read_write_ignore);
 
 	/*
-	 * all_baserels is a Relids set of all base relids (but not "other"
-	 * relids) in the query; that is, the Relids identifier of the final join
-	 * we need to form.  This is computed in make_one_rel, just before we
-	 * start making Paths.
+	 * all_baserels is a Relids set of all base relids (but not joins or
+	 * "other" rels) in the query.  This is computed in deconstruct_jointree.
 	 */
 	Relids		all_baserels;
 
 	/*
+	 * outer_join_rels is a Relids set of all outer-join relids in the query.
+	 * This is computed in deconstruct_jointree.
+	 */
+	Relids		outer_join_rels;
+
+	/*
+	 * all_query_rels is a Relids set of all base relids and outer join relids
+	 * (but not "other" relids) in the query.  This is the Relids identifier
+	 * of the final join we need to form.  This is computed in
+	 * deconstruct_jointree.
+	 */
+	Relids		all_query_rels;
+
+	/*
 	 * nullable_baserels is a Relids set of base relids that are nullable by
 	 * some outer join in the jointree; these are rels that are potentially
 	 * nullable below the WHERE clause, SELECT targetlist, etc.  This is
@@ -313,25 +325,28 @@ struct PlannerInfo
 	List	   *canon_pathkeys;
 
 	/*
-	 * list of RestrictInfos for mergejoinable outer join clauses
+	 * list of OuterJoinClauseInfos for mergejoinable outer join clauses
 	 * w/nonnullable var on left
 	 */
 	List	   *left_join_clauses;
 
 	/*
-	 * list of RestrictInfos for mergejoinable outer join clauses
+	 * list of OuterJoinClauseInfos for mergejoinable outer join clauses
 	 * w/nonnullable var on right
 	 */
 	List	   *right_join_clauses;
 
 	/*
-	 * list of RestrictInfos for mergejoinable full join clauses
+	 * list of OuterJoinClauseInfos for mergejoinable full join clauses
 	 */
 	List	   *full_join_clauses;
 
 	/* list of SpecialJoinInfos */
 	List	   *join_info_list;
 
+	/* counter for assigning RestrictInfo serial numbers */
+	int			last_rinfo_serial;
+
 	/*
 	 * all_result_relids is empty for SELECT, otherwise it contains at least
 	 * parse->resultRelation.  For UPDATE/DELETE/MERGE across an inheritance
@@ -592,9 +607,10 @@ typedef struct PartitionSchemeData *PartitionScheme;
  * or the output of a sub-SELECT or function that appears in the range table.
  * In either case it is uniquely identified by an RT index.  A "joinrel"
  * is the joining of two or more base rels.  A joinrel is identified by
- * the set of RT indexes for its component baserels.  We create RelOptInfo
- * nodes for each baserel and joinrel, and store them in the PlannerInfo's
- * simple_rel_array and join_rel_list respectively.
+ * the set of RT indexes for its component baserels, along with RT indexes
+ * for any outer joins it has computed.  We create RelOptInfo nodes for each
+ * baserel and joinrel, and store them in the PlannerInfo's simple_rel_array
+ * and join_rel_list respectively.
  *
  * Note that there is only one joinrel for any given set of component
  * baserels, no matter what order we assemble them in; so an unordered
@@ -633,8 +649,10 @@ typedef struct PartitionSchemeData *PartitionScheme;
  * Parts of this data structure are specific to various scan and join
  * mechanisms.  It didn't seem worth creating new node types for them.
  *
- *		relids - Set of base-relation identifiers; it is a base relation
- *				if there is just one, a join relation if more than one
+ *		relids - Set of relation identifiers (RT indexes).  This is a base
+ *				 relation if there is just one, a join relation if more;
+ *				 in the join case, RT indexes of any outer joins formed
+ *				 at or below this join are included along with baserels
  *		rows - estimated number of tuples in the relation after restriction
  *			   clauses have been applied (ie, output rows of a plan for it)
  *		consider_startup - true if there is any value in keeping plain paths for
@@ -846,7 +864,7 @@ typedef struct RelOptInfo
 	RelOptKind	reloptkind;
 
 	/*
-	 * all relations included in this RelOptInfo; set of base relids
+	 * all relations included in this RelOptInfo; set of base + OJ relids
 	 * (rangetable indexes)
 	 */
 	Relids		relids;
@@ -911,7 +929,7 @@ typedef struct RelOptInfo
 	int32	   *attr_widths pg_node_attr(read_write_ignore);
 	/* LATERAL Vars and PHVs referenced by rel */
 	List	   *lateral_vars;
-	/* rels that reference me laterally */
+	/* rels that reference this baserel laterally */
 	Relids		lateral_referencers;
 	/* list of IndexOptInfo */
 	List	   *indexlist;
@@ -921,10 +939,7 @@ typedef struct RelOptInfo
 	BlockNumber pages;
 	Cardinality tuples;
 	double		allvisfrac;
-
-	/*
-	 * Indexes in PlannerInfo's eq_classes list of ECs that mention this rel
-	 */
+	/* indexes in PlannerInfo's eq_classes list of ECs that mention this rel */
 	Bitmapset  *eclass_indexes;
 	PlannerInfo *subroot;		/* if subquery */
 	List	   *subplan_params; /* if subquery */
@@ -1378,6 +1393,8 @@ typedef struct EquivalenceMember
 	bool		em_is_const;	/* expression is pseudoconstant? */
 	bool		em_is_child;	/* derived version for a child relation? */
 	Oid			em_datatype;	/* the "nominal type" used by the opfamily */
+	/* if em_is_child is true, this links to corresponding EM for top parent */
+	struct EquivalenceMember *em_parent pg_node_attr(read_write_ignore);
 } EquivalenceMember;
 
 /*
@@ -1484,7 +1501,13 @@ typedef struct PathTarget
  * Note: ppi_clauses is only used in ParamPathInfos for base relation paths;
  * in join cases it's NIL because the set of relevant clauses varies depending
  * on how the join is formed.  The relevant clauses will appear in each
- * parameterized join path's joinrestrictinfo list, instead.
+ * parameterized join path's joinrestrictinfo list, instead.  ParamPathInfos
+ * for append relations don't bother with this, either.
+ *
+ * ppi_serials is the set of rinfo_serial numbers for quals that are enforced
+ * by this path.  As with ppi_clauses, it's only maintained for baserels.
+ * (We could construct it on-the-fly from ppi_clauses, but it seems better
+ * to materialize a copy.)
  */
 typedef struct ParamPathInfo
 {
@@ -1495,6 +1518,7 @@ typedef struct ParamPathInfo
 	Relids		ppi_req_outer;	/* rels supplying parameters used by path */
 	Cardinality ppi_rows;		/* estimated number of result tuples */
 	List	   *ppi_clauses;	/* join clauses available from outer rels */
+	Bitmapset  *ppi_serials;	/* set of rinfo_serial for enforced quals */
 } ParamPathInfo;
 
 
@@ -2319,17 +2343,17 @@ typedef struct LimitPath
  * If a restriction clause references a single base relation, it will appear
  * in the baserestrictinfo list of the RelOptInfo for that base rel.
  *
- * If a restriction clause references more than one base rel, it will
+ * If a restriction clause references more than one base+OJ relation, it will
  * appear in the joininfo list of every RelOptInfo that describes a strict
- * subset of the base rels mentioned in the clause.  The joininfo lists are
+ * subset of the relations mentioned in the clause.  The joininfo lists are
  * used to drive join tree building by selecting plausible join candidates.
  * The clause cannot actually be applied until we have built a join rel
- * containing all the base rels it references, however.
+ * containing all the relations it references, however.
  *
- * When we construct a join rel that includes all the base rels referenced
+ * When we construct a join rel that includes all the relations referenced
  * in a multi-relation restriction clause, we place that clause into the
  * joinrestrictinfo lists of paths for the join rel, if neither left nor
- * right sub-path includes all base rels referenced in the clause.  The clause
+ * right sub-path includes all relations referenced in the clause.  The clause
  * will be applied at that join level, and will not propagate any further up
  * the join tree.  (Note: the "predicate migration" code was once intended to
  * push restriction clauses up and down the plan tree based on evaluation
@@ -2350,12 +2374,14 @@ typedef struct LimitPath
  * or join to enforce that all members of each EquivalenceClass are in fact
  * equal in all rows emitted by the scan or join.
  *
- * When dealing with outer joins we have to be very careful about pushing qual
- * clauses up and down the tree.  An outer join's own JOIN/ON conditions must
- * be evaluated exactly at that join node, unless they are "degenerate"
- * conditions that reference only Vars from the nullable side of the join.
- * Quals appearing in WHERE or in a JOIN above the outer join cannot be pushed
- * down below the outer join, if they reference any nullable Vars.
+ * The clause_relids field lists the base plus outer-join RT indexes that
+ * actually appear in the clause.  required_relids lists the minimum set of
+ * relids needed to evaluate the clause; while this is often equal to
+ * clause_relids, it can be more.  We will add relids to required_relids when
+ * we need to force an outer join ON clause to be evaluated exactly at the
+ * level of the outer join, which is true except when it is a "degenerate"
+ * condition that references only Vars from the nullable side of the join.
+ *
  * RestrictInfo nodes contain a flag to indicate whether a qual has been
  * pushed down to a lower level than its original syntactic placement in the
  * join tree would suggest.  If an outer join prevents us from pushing a qual
@@ -2440,6 +2466,12 @@ typedef struct LimitPath
  * or merge or hash join clause, so it's of no interest to large parts of
  * the planner.
  *
+ * When we generate multiple versions of a clause so as to have versions
+ * that will work after commuting some left joins per outer join identity 3,
+ * we mark the one with the fewest nullingrels bits with has_clone = true,
+ * and the rest with is_clone = true.  This allows proper filtering of
+ * these redundant clauses, so that we apply only one version of them.
+ *
  * When join clauses are generated from EquivalenceClasses, there may be
  * several equally valid ways to enforce join equivalence, of which we need
  * apply only one.  We mark clauses of this kind by setting parent_ec to
@@ -2474,16 +2506,23 @@ typedef struct RestrictInfo
 	/* see comment above */
 	bool		pseudoconstant pg_node_attr(equal_ignore);
 
+	/* see comment above */
+	bool		has_clone;
+	bool		is_clone;
+
 	/* true if known to contain no leaked Vars */
 	bool		leakproof pg_node_attr(equal_ignore);
 
-	/* to indicate if clause contains any volatile functions. */
+	/* indicates if clause contains any volatile functions */
 	VolatileFunctionStatus has_volatile pg_node_attr(equal_ignore);
 
 	/* see comment above */
 	Index		security_level;
 
-	/* The set of relids (varnos) actually referenced in the clause: */
+	/* number of base rels in clause_relids */
+	int			num_base_rels pg_node_attr(equal_ignore);
+
+	/* The relids (varnos+varnullingrels) actually referenced in the clause: */
 	Relids		clause_relids pg_node_attr(equal_ignore);
 
 	/* The set of relids required to evaluate the clause: */
@@ -2508,6 +2547,25 @@ typedef struct RestrictInfo
 	 */
 	Expr	   *orclause pg_node_attr(equal_ignore);
 
+	/*----------
+	 * Serial number of this RestrictInfo.  This is unique within the current
+	 * PlannerInfo context, with a few critical exceptions:
+	 * 1. When we generate multiple clones of the same qual condition to
+	 * cope with outer join identity 3, all the clones get the same serial
+	 * number.  This reflects that we only want to apply one of them in any
+	 * given plan.
+	 * 2. If we manufacture a commuted version of a qual to use as an index
+	 * condition, it copies the original's rinfo_serial, since it is in
+	 * practice the same condition.
+	 * 3. RestrictInfos made for a child relation copy their parent's
+	 * rinfo_serial.  Likewise, when an EquivalenceClass makes a derived
+	 * equality clause for a child relation, it copies the rinfo_serial of
+	 * the matching equality clause for the parent.  This allows detection
+	 * of redundant pushed-down equality clauses.
+	 *----------
+	 */
+	int			rinfo_serial;
+
 	/*
 	 * Generating EquivalenceClass.  This field is NULL unless clause is
 	 * potentially redundant.
@@ -2624,10 +2682,15 @@ typedef struct MergeScanSelCache
  * of a plan tree.  This is used during planning to represent the contained
  * expression.  At the end of the planning process it is replaced by either
  * the contained expression or a Var referring to a lower-level evaluation of
- * the contained expression.  Typically the evaluation occurs below an outer
+ * the contained expression.  Generally the evaluation occurs below an outer
  * join, and Var references above the outer join might thereby yield NULL
  * instead of the expression value.
  *
+ * phrels and phlevelsup correspond to the varno/varlevelsup fields of a
+ * plain Var, except that phrels has to be a relid set since the evaluation
+ * level of a PlaceHolderVar might be a join rather than a base relation.
+ * Likewise, phnullingrels corresponds to varnullingrels.
+ *
  * Although the planner treats this as an expression node type, it is not
  * recognized by the parser or executor, so we declare it here rather than
  * in primnodes.h.
@@ -2640,8 +2703,10 @@ typedef struct MergeScanSelCache
  * PHV.  Another way in which it can happen is that initplan sublinks
  * could get replaced by differently-numbered Params when sublink folding
  * is done.  (The end result of such a situation would be some
- * unreferenced initplans, which is annoying but not really a problem.) On
- * the same reasoning, there is no need to examine phrels.
+ * unreferenced initplans, which is annoying but not really a problem.)
+ * On the same reasoning, there is no need to examine phrels.  But we do
+ * need to compare phnullingrels, as that represents effects that are
+ * external to the original value of the PHV.
  */
 
 typedef struct PlaceHolderVar
@@ -2651,9 +2716,12 @@ typedef struct PlaceHolderVar
 	/* the represented expression */
 	Expr	   *phexpr pg_node_attr(equal_ignore);
 
-	/* base relids syntactically within expr src */
+	/* base+OJ relids syntactically within expr src */
 	Relids		phrels pg_node_attr(equal_ignore);
 
+	/* RT indexes of outer joins that can null PHV's value */
+	Relids		phnullingrels;
+
 	/* ID for PHV (unique within planner run) */
 	Index		phid;
 
@@ -2677,20 +2745,49 @@ typedef struct PlaceHolderVar
  * We make SpecialJoinInfos for FULL JOINs even though there is no flexibility
  * of planning for them, because this simplifies make_join_rel()'s API.
  *
- * min_lefthand and min_righthand are the sets of base relids that must be
- * available on each side when performing the special join.  lhs_strict is
- * true if the special join's condition cannot succeed when the LHS variables
- * are all NULL (this means that an outer join can commute with upper-level
- * outer joins even if it appears in their RHS).  We don't bother to set
- * lhs_strict for FULL JOINs, however.
- *
+ * min_lefthand and min_righthand are the sets of base+OJ relids that must be
+ * available on each side when performing the special join.
  * It is not valid for either min_lefthand or min_righthand to be empty sets;
  * if they were, this would break the logic that enforces join order.
  *
- * syn_lefthand and syn_righthand are the sets of base relids that are
+ * syn_lefthand and syn_righthand are the sets of base+OJ relids that are
  * syntactically below this special join.  (These are needed to help compute
  * min_lefthand and min_righthand for higher joins.)
  *
+ * jointype is never JOIN_RIGHT; a RIGHT JOIN is handled by switching
+ * the inputs to make it a LEFT JOIN.  So the allowed values of jointype
+ * in a join_info_list member are only LEFT, FULL, SEMI, or ANTI.
+ *
+ * ojrelid is the RT index of the join RTE representing this outer join,
+ * if there is one.  It is zero when jointype is INNER or SEMI, and can be
+ * zero for jointype ANTI (if the join was transformed from a SEMI join).
+ * One use for this field is that when constructing the output targetlist of a
+ * join relation that implements this OJ, we add ojrelid to the varnullingrels
+ * and phnullingrels fields of nullable (RHS) output columns, so that the
+ * output Vars and PlaceHolderVars correctly reflect the nulling that has
+ * potentially happened to them.
+ *
+ * commute_above_l is filled with the relids of syntactically-higher outer
+ * joins that have been found to commute with this one per outer join identity
+ * 3 (see optimizer/README), when this join is in the LHS of the upper join
+ * (so, this is the lower join in the first form of the identity).
+ *
+ * commute_above_r is filled with the relids of syntactically-higher outer
+ * joins that have been found to commute with this one per outer join identity
+ * 3, when this join is in the RHS of the upper join (so, this is the lower
+ * join in the second form of the identity).
+ *
+ * commute_below is filled with the relids of syntactically-lower outer joins
+ * that have been found to commute with this one per outer join identity 3.
+ * (We need not record which side they are on, since that can be determined
+ * by seeing whether the lower join's relid appears in syn_lefthand or
+ * syn_righthand.)
+ *
+ * lhs_strict is true if the special join's condition cannot succeed when the
+ * LHS variables are all NULL (this means that an outer join can commute with
+ * upper-level outer joins even if it appears in their RHS).  We don't bother
+ * to set lhs_strict for FULL JOINs, however.
+ *
  * delay_upper_joins is set true if we detect a pushed-down clause that has
  * to be evaluated after this join is formed (because it references the RHS).
  * Any outer joins that have such a clause and this join in their RHS cannot
@@ -2705,10 +2802,6 @@ typedef struct PlaceHolderVar
  * join planning; but it's helpful to have it available during planning of
  * parameterized table scans, so we store it in the SpecialJoinInfo structs.)
  *
- * jointype is never JOIN_RIGHT; a RIGHT JOIN is handled by switching
- * the inputs to make it a LEFT JOIN.  So the allowed values of jointype
- * in a join_info_list member are only LEFT, FULL, SEMI, or ANTI.
- *
  * For purposes of join selectivity estimation, we create transient
  * SpecialJoinInfo structures for regular inner joins; so it is possible
  * to have jointype == JOIN_INNER in such a structure, even though this is
@@ -2728,11 +2821,15 @@ struct SpecialJoinInfo
 	pg_node_attr(no_read)
 
 	NodeTag		type;
-	Relids		min_lefthand;	/* base relids in minimum LHS for join */
-	Relids		min_righthand;	/* base relids in minimum RHS for join */
-	Relids		syn_lefthand;	/* base relids syntactically within LHS */
-	Relids		syn_righthand;	/* base relids syntactically within RHS */
+	Relids		min_lefthand;	/* base+OJ relids in minimum LHS for join */
+	Relids		min_righthand;	/* base+OJ relids in minimum RHS for join */
+	Relids		syn_lefthand;	/* base+OJ relids syntactically within LHS */
+	Relids		syn_righthand;	/* base+OJ relids syntactically within RHS */
 	JoinType	jointype;		/* always INNER, LEFT, FULL, SEMI, or ANTI */
+	Index		ojrelid;		/* outer join's RT index; 0 if none */
+	Relids		commute_above_l;	/* commuting OJs above this one, if LHS */
+	Relids		commute_above_r;	/* commuting OJs above this one, if RHS */
+	Relids		commute_below;	/* commuting OJs below this one */
 	bool		lhs_strict;		/* joinclause is strict for some LHS rel */
 	bool		delay_upper_joins;	/* can't commute with upper RHS */
 	/* Remaining fields are set only for JOIN_SEMI jointype: */
@@ -2743,6 +2840,21 @@ struct SpecialJoinInfo
 };
 
 /*
+ * Transient outer-join clause info.
+ *
+ * We set aside every outer join ON clause that looks mergejoinable,
+ * and process it specially at the end of qual distribution.
+ */
+typedef struct OuterJoinClauseInfo
+{
+	pg_node_attr(no_copy_equal, no_read)
+
+	NodeTag		type;
+	RestrictInfo *rinfo;		/* a mergejoinable outer-join clause */
+	SpecialJoinInfo *sjinfo;	/* the outer join's SpecialJoinInfo */
+} OuterJoinClauseInfo;
+
+/*
  * Append-relation info.
  *
  * When we expand an inheritable table or a UNION-ALL subselect into an
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index c1234fcf36d..4781a9c6325 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -695,6 +695,7 @@ typedef struct WorkTableScan
  * When the plan node represents a foreign join, scan.scanrelid is zero and
  * fs_relids must be consulted to identify the join relation.  (fs_relids
  * is valid for simple scans as well, but will always match scan.scanrelid.)
+ * fs_relids includes outer joins; fs_base_relids does not.
  *
  * If the FDW's PlanDirectModify() callback decides to repurpose a ForeignScan
  * node to perform the UPDATE or DELETE operation directly in the remote
@@ -716,7 +717,8 @@ typedef struct ForeignScan
 	List	   *fdw_private;	/* private data for FDW */
 	List	   *fdw_scan_tlist; /* optional tlist describing scan tuple */
 	List	   *fdw_recheck_quals;	/* original quals not in scan.plan.qual */
-	Bitmapset  *fs_relids;		/* RTIs generated by this scan */
+	Bitmapset  *fs_relids;		/* base+OJ RTIs generated by this scan */
+	Bitmapset  *fs_base_relids; /* base RTIs generated by this scan */
 	bool		fsSystemCol;	/* true if any "system column" is needed */
 } ForeignScan;
 
diff --git a/src/include/nodes/primnodes.h b/src/include/nodes/primnodes.h
index dec7d5c775f..6c96fa2f516 100644
--- a/src/include/nodes/primnodes.h
+++ b/src/include/nodes/primnodes.h
@@ -190,6 +190,14 @@ typedef struct Expr
  * row identity information during UPDATE/DELETE/MERGE.  This value should
  * never be seen outside the planner.
  *
+ * varnullingrels is the set of RT indexes of outer joins that can force
+ * the Var's value to null (at the point where it appears in the query).
+ * See optimizer/README for discussion of that.
+ *
+ * varlevelsup is greater than zero in Vars that represent outer references.
+ * Note that it affects the meaning of all of varno, varnullingrels, and
+ * varnosyn, all of which refer to the range table of that query level.
+ *
  * In the parser, varnosyn and varattnosyn are either identical to
  * varno/varattno, or they specify the column's position in an aliased JOIN
  * RTE that hides the semantic referent RTE's refname.  This is a syntactic
@@ -232,6 +240,8 @@ typedef struct Var
 	int32		vartypmod;
 	/* OID of collation, or InvalidOid if none */
 	Oid			varcollid;
+	/* RT indexes of outer joins that can replace the Var's value with null */
+	Bitmapset  *varnullingrels;
 
 	/*
 	 * for subquery variables referencing outer relations; 0 in a normal var,
diff --git a/src/include/optimizer/optimizer.h b/src/include/optimizer/optimizer.h
index 69ce6ee4d37..b6df013c213 100644
--- a/src/include/optimizer/optimizer.h
+++ b/src/include/optimizer/optimizer.h
@@ -197,6 +197,6 @@ extern bool contain_var_clause(Node *node);
 extern bool contain_vars_of_level(Node *node, int levelsup);
 extern int	locate_var_of_level(Node *node, int levelsup);
 extern List *pull_var_clause(Node *node, int flags);
-extern Node *flatten_join_alias_vars(Query *query, Node *node);
+extern Node *flatten_join_alias_vars(PlannerInfo *root, Query *query, Node *node);
 
 #endif							/* OPTIMIZER_H */
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 02305ef902f..69be701b167 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -304,6 +304,7 @@ extern void expand_planner_arrays(PlannerInfo *root, int add_size);
 extern RelOptInfo *build_simple_rel(PlannerInfo *root, int relid,
 									RelOptInfo *parent);
 extern RelOptInfo *find_base_rel(PlannerInfo *root, int relid);
+extern RelOptInfo *find_base_rel_ignore_join(PlannerInfo *root, int relid);
 extern RelOptInfo *find_join_rel(PlannerInfo *root, Relids relids);
 extern RelOptInfo *build_join_rel(PlannerInfo *root,
 								  Relids joinrelids,
@@ -332,9 +333,10 @@ extern ParamPathInfo *get_appendrel_parampathinfo(RelOptInfo *appendrel,
 												  Relids required_outer);
 extern ParamPathInfo *find_param_path_info(RelOptInfo *rel,
 										   Relids required_outer);
+extern Bitmapset *get_param_path_clause_serials(Path *path);
 extern RelOptInfo *build_child_join_rel(PlannerInfo *root,
 										RelOptInfo *outer_rel, RelOptInfo *inner_rel,
 										RelOptInfo *parent_joinrel, List *restrictlist,
-										SpecialJoinInfo *sjinfo, JoinType jointype);
+										SpecialJoinInfo *sjinfo);
 
 #endif							/* PATHNODE_H */
diff --git a/src/include/optimizer/placeholder.h b/src/include/optimizer/placeholder.h
index 7367dca1e8a..31e1578e822 100644
--- a/src/include/optimizer/placeholder.h
+++ b/src/include/optimizer/placeholder.h
@@ -27,6 +27,9 @@ extern void update_placeholder_eval_levels(PlannerInfo *root,
 extern void fix_placeholder_input_needed_levels(PlannerInfo *root);
 extern void add_placeholders_to_base_rels(PlannerInfo *root);
 extern void add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
-										RelOptInfo *outer_rel, RelOptInfo *inner_rel);
+										RelOptInfo *outer_rel, RelOptInfo *inner_rel,
+										SpecialJoinInfo *sjinfo);
+extern bool contain_placeholder_references_to(PlannerInfo *root, Node *clause,
+											  int relid);
 
 #endif							/* PLACEHOLDER_H */
diff --git a/src/include/optimizer/prep.h b/src/include/optimizer/prep.h
index 452b92ad55e..54fd61c9c3e 100644
--- a/src/include/optimizer/prep.h
+++ b/src/include/optimizer/prep.h
@@ -29,7 +29,8 @@ extern void pull_up_subqueries(PlannerInfo *root);
 extern void flatten_simple_union_all(PlannerInfo *root);
 extern void reduce_outer_joins(PlannerInfo *root);
 extern void remove_useless_result_rtes(PlannerInfo *root);
-extern Relids get_relids_in_jointree(Node *jtnode, bool include_joins);
+extern Relids get_relids_in_jointree(Node *jtnode, bool include_outer_joins,
+									 bool include_inner_joins);
 extern Relids get_relids_for_join(Query *query, int joinrelid);
 
 /*
diff --git a/src/include/optimizer/restrictinfo.h b/src/include/optimizer/restrictinfo.h
index a47fccc2ed1..c79bb420e4e 100644
--- a/src/include/optimizer/restrictinfo.h
+++ b/src/include/optimizer/restrictinfo.h
@@ -41,6 +41,9 @@ extern void extract_actual_join_clauses(List *restrictinfo_list,
 										Relids joinrelids,
 										List **joinquals,
 										List **otherquals);
+extern bool clause_is_computable_at(PlannerInfo *root,
+									Relids clause_relids,
+									Relids eval_relids);
 extern bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel);
 extern bool join_clause_is_movable_into(RestrictInfo *rinfo,
 										Relids currentrelids,
diff --git a/src/include/parser/parse_node.h b/src/include/parser/parse_node.h
index 1a3792236a1..f589112d5e5 100644
--- a/src/include/parser/parse_node.h
+++ b/src/include/parser/parse_node.h
@@ -118,6 +118,13 @@ typedef Node *(*CoerceParamHook) (ParseState *pstate, Param *param,
  * This is one-for-one with p_rtable, but contains NULLs for non-join
  * RTEs, and may be shorter than p_rtable if the last RTE(s) aren't joins.
  *
+ * p_nullingrels: list of Bitmapsets associated with p_rtable entries, each
+ * containing the set of outer-join RTE indexes that can null that relation
+ * at the current point in the parse tree.  This is one-for-one with p_rtable,
+ * but may be shorter than p_rtable, in which case the missing entries are
+ * implicitly empty (NULL).  That rule allows us to save work when the query
+ * contains no outer joins.
+ *
  * p_joinlist: list of join items (RangeTblRef and JoinExpr nodes) that
  * will become the fromlist of the query's top-level FromExpr node.
  *
@@ -187,6 +194,7 @@ struct ParseState
 	List	   *p_rteperminfos; /* list of RTEPermissionInfo nodes for each
 								 * RTE_RELATION entry in rtable */
 	List	   *p_joinexprs;	/* JoinExprs for RTE_JOIN p_rtable entries */
+	List	   *p_nullingrels;	/* Bitmapsets showing nulling outer joins */
 	List	   *p_joinlist;		/* join items so far (will become FromExpr
 								 * node's fromlist) */
 	List	   *p_namespace;	/* currently-referenceable RTEs (List of
diff --git a/src/include/parser/parse_relation.h b/src/include/parser/parse_relation.h
index dfa584b6ace..67d9b1e412c 100644
--- a/src/include/parser/parse_relation.h
+++ b/src/include/parser/parse_relation.h
@@ -41,6 +41,7 @@ extern Node *scanNSItemForColumn(ParseState *pstate, ParseNamespaceItem *nsitem,
 								 int location);
 extern Node *colNameToVar(ParseState *pstate, const char *colname, bool localonly,
 						  int location);
+extern void markNullableIfNeeded(ParseState *pstate, Var *var);
 extern void markVarForSelectPriv(ParseState *pstate, Var *var);
 extern Relation parserOpenTable(ParseState *pstate, const RangeVar *relation,
 								int lockmode);
@@ -113,7 +114,7 @@ extern void errorMissingColumn(ParseState *pstate,
 extern void expandRTE(RangeTblEntry *rte, int rtindex, int sublevels_up,
 					  int location, bool include_dropped,
 					  List **colnames, List **colvars);
-extern List *expandNSItemVars(ParseNamespaceItem *nsitem,
+extern List *expandNSItemVars(ParseState *pstate, ParseNamespaceItem *nsitem,
 							  int sublevels_up, int location,
 							  List **colnames);
 extern List *expandNSItemAttrs(ParseState *pstate, ParseNamespaceItem *nsitem,
diff --git a/src/include/rewrite/rewriteManip.h b/src/include/rewrite/rewriteManip.h
index 02d130cc269..365061fff44 100644
--- a/src/include/rewrite/rewriteManip.h
+++ b/src/include/rewrite/rewriteManip.h
@@ -65,6 +65,13 @@ extern bool contain_windowfuncs(Node *node);
 extern int	locate_windowfunc(Node *node);
 extern bool checkExprHasSubLink(Node *node);
 
+extern Node *add_nulling_relids(Node *node,
+								const Bitmapset *target_relids,
+								const Bitmapset *added_relids);
+extern Node *remove_nulling_relids(Node *node,
+								   const Bitmapset *removable_relids,
+								   const Bitmapset *except_relids);
+
 extern Node *replace_rte_variables(Node *node,
 								   int target_varno, int sublevels_up,
 								   replace_rte_variables_callback callback,