Fix up planner infrastructure to support LATERAL properly.

This patch takes care of a number of problems having to do with failure
to choose valid join orders and incorrect handling of lateral references
pulled up from subqueries.  Notable changes:

* Add a LateralJoinInfo data structure similar to SpecialJoinInfo, to
represent join ordering constraints created by lateral references.
(I first considered extending the SpecialJoinInfo structure, but the
semantics are different enough that a separate data structure seems
better.)  Extend join_is_legal() and related functions to prevent trying
to form unworkable joins, and to ensure that we will consider joins that
satisfy lateral references even if the joins would be clauseless.

* Fill in the infrastructure needed for the last few types of relation scan
paths to support parameterization.  We'd have wanted this eventually
anyway, but it is necessary now because a relation that gets pulled up out
of a UNION ALL subquery may acquire a reltargetlist containing lateral
references, meaning that its paths *have* to be parameterized whether or
not we have any code that can push join quals down into the scan.

* Compute data about lateral references early in query_planner(), and save
in RelOptInfo nodes, to avoid repetitive calculations later.

* Assorted corner-case bug fixes.

There's probably still some bugs left, but this is a lot closer to being
real than it was before.

30 files changed, 817 insertions, 182 deletions

diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
index 71d53234bc3..f34f7049e43 100644
--- a/src/backend/nodes/copyfuncs.c
+++ b/src/backend/nodes/copyfuncs.c
@@ -1907,6 +1907,20 @@ _copySpecialJoinInfo(const SpecialJoinInfo *from)
 }
 
 /*
+ * _copyLateralJoinInfo
+ */
+static LateralJoinInfo *
+_copyLateralJoinInfo(const LateralJoinInfo *from)
+{
+	LateralJoinInfo *newnode = makeNode(LateralJoinInfo);
+
+	COPY_SCALAR_FIELD(lateral_rhs);
+	COPY_BITMAPSET_FIELD(lateral_lhs);
+
+	return newnode;
+}
+
+/*
  * _copyAppendRelInfo
  */
 static AppendRelInfo *
@@ -4082,6 +4096,9 @@ copyObject(const void *from)
 		case T_SpecialJoinInfo:
 			retval = _copySpecialJoinInfo(from);
 			break;
+		case T_LateralJoinInfo:
+			retval = _copyLateralJoinInfo(from);
+			break;
 		case T_AppendRelInfo:
 			retval = _copyAppendRelInfo(from);
 			break;
diff --git a/src/backend/nodes/equalfuncs.c b/src/backend/nodes/equalfuncs.c
index d690ca77a5a..b4b1c223363 100644
--- a/src/backend/nodes/equalfuncs.c
+++ b/src/backend/nodes/equalfuncs.c
@@ -863,6 +863,15 @@ _equalSpecialJoinInfo(const SpecialJoinInfo *a, const SpecialJoinInfo *b)
 }
 
 static bool
+_equalLateralJoinInfo(const LateralJoinInfo *a, const LateralJoinInfo *b)
+{
+	COMPARE_SCALAR_FIELD(lateral_rhs);
+	COMPARE_BITMAPSET_FIELD(lateral_lhs);
+
+	return true;
+}
+
+static bool
 _equalAppendRelInfo(const AppendRelInfo *a, const AppendRelInfo *b)
 {
 	COMPARE_SCALAR_FIELD(parent_relid);
@@ -2646,6 +2655,9 @@ equal(const void *a, const void *b)
 		case T_SpecialJoinInfo:
 			retval = _equalSpecialJoinInfo(a, b);
 			break;
+		case T_LateralJoinInfo:
+			retval = _equalLateralJoinInfo(a, b);
+			break;
 		case T_AppendRelInfo:
 			retval = _equalAppendRelInfo(a, b);
 			break;
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 9dee0414f36..01f381e9bad 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -1699,6 +1699,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node)
 	WRITE_NODE_FIELD(right_join_clauses);
 	WRITE_NODE_FIELD(full_join_clauses);
 	WRITE_NODE_FIELD(join_info_list);
+	WRITE_NODE_FIELD(lateral_info_list);
 	WRITE_NODE_FIELD(append_rel_list);
 	WRITE_NODE_FIELD(rowMarks);
 	WRITE_NODE_FIELD(placeholder_list);
@@ -1713,6 +1714,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node)
 	WRITE_FLOAT_FIELD(limit_tuples, "%.0f");
 	WRITE_BOOL_FIELD(hasInheritedTarget);
 	WRITE_BOOL_FIELD(hasJoinRTEs);
+	WRITE_BOOL_FIELD(hasLateralRTEs);
 	WRITE_BOOL_FIELD(hasHavingQual);
 	WRITE_BOOL_FIELD(hasPseudoConstantQuals);
 	WRITE_BOOL_FIELD(hasRecursion);
@@ -1743,6 +1745,8 @@ _outRelOptInfo(StringInfo str, const RelOptInfo *node)
 	WRITE_ENUM_FIELD(rtekind, RTEKind);
 	WRITE_INT_FIELD(min_attr);
 	WRITE_INT_FIELD(max_attr);
+	WRITE_NODE_FIELD(lateral_vars);
+	WRITE_BITMAPSET_FIELD(lateral_relids);
 	WRITE_NODE_FIELD(indexlist);
 	WRITE_UINT_FIELD(pages);
 	WRITE_FLOAT_FIELD(tuples, "%.0f");
@@ -1891,6 +1895,15 @@ _outSpecialJoinInfo(StringInfo str, const SpecialJoinInfo *node)
 }
 
 static void
+_outLateralJoinInfo(StringInfo str, const LateralJoinInfo *node)
+{
+	WRITE_NODE_TYPE("LATERALJOININFO");
+
+	WRITE_UINT_FIELD(lateral_rhs);
+	WRITE_BITMAPSET_FIELD(lateral_lhs);
+}
+
+static void
 _outAppendRelInfo(StringInfo str, const AppendRelInfo *node)
 {
 	WRITE_NODE_TYPE("APPENDRELINFO");
@@ -3036,6 +3049,9 @@ _outNode(StringInfo str, const void *obj)
 			case T_SpecialJoinInfo:
 				_outSpecialJoinInfo(str, obj);
 				break;
+			case T_LateralJoinInfo:
+				_outLateralJoinInfo(str, obj);
+				break;
 			case T_AppendRelInfo:
 				_outAppendRelInfo(str, obj);
 				break;
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 23a8afb3d0c..6369da9ef46 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -268,8 +268,9 @@ set_rel_size(PlannerInfo *root, RelOptInfo *rel,
 			case RTE_CTE:
 
 				/*
-				 * CTEs don't support parameterized paths, so just go ahead
-				 * and build their paths immediately.
+				 * CTEs don't support making a choice between parameterized
+				 * and unparameterized paths, so just go ahead and build their
+				 * paths immediately.
 				 */
 				if (rte->self_reference)
 					set_worktable_pathlist(root, rel, rte);
@@ -376,8 +377,18 @@ set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 static void
 set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 {
+	Relids		required_outer;
+
+	/*
+	 * We don't support pushing join clauses into the quals of a seqscan, but
+	 * it could still have required parameterization due to LATERAL refs in
+	 * its tlist.  (That can only happen if the seqscan is on a relation
+	 * pulled up out of a UNION ALL appendrel.)
+	 */
+	required_outer = rel->lateral_relids;
+
 	/* Consider sequential scan */
-	add_path(rel, create_seqscan_path(root, rel, NULL));
+	add_path(rel, create_seqscan_path(root, rel, required_outer));
 
 	/* Consider index scans */
 	create_index_paths(root, rel);
@@ -536,10 +547,10 @@ set_append_rel_size(PlannerInfo *root, RelOptInfo *rel,
 		 * CE failed, so finish copying/modifying targetlist and join quals.
 		 *
 		 * Note: the resulting childrel->reltargetlist may contain arbitrary
-		 * expressions, which normally would not occur in a reltargetlist.
-		 * That is okay because nothing outside of this routine will look at
-		 * the child rel's reltargetlist.  We do have to cope with the case
-		 * while constructing attr_widths estimates below, though.
+		 * expressions, which otherwise would not occur in a reltargetlist.
+		 * Code that might be looking at an appendrel child must cope with
+		 * such.  Note in particular that "arbitrary expression" can include
+		 * "Var belonging to another relation", due to LATERAL references.
 		 */
 		childrel->joininfo = (List *)
 			adjust_appendrel_attrs(root,
@@ -610,7 +621,8 @@ set_append_rel_size(PlannerInfo *root, RelOptInfo *rel,
 					int			pndx = parentvar->varattno - rel->min_attr;
 					int32		child_width = 0;
 
-					if (IsA(childvar, Var))
+					if (IsA(childvar, Var) &&
+						((Var *) childvar)->varno == childrel->relid)
 					{
 						int			cndx = ((Var *) childvar)->varattno - childrel->min_attr;
 
@@ -1054,17 +1066,10 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
 
 	/*
 	 * If it's a LATERAL subquery, it might contain some Vars of the current
-	 * query level, requiring it to be treated as parameterized.
+	 * query level, requiring it to be treated as parameterized, even though
+	 * we don't support pushing down join quals into subqueries.
 	 */
-	if (rte->lateral)
-	{
-		required_outer = pull_varnos_of_level((Node *) subquery, 1);
-		/* Enforce convention that empty required_outer is exactly NULL */
-		if (bms_is_empty(required_outer))
-			required_outer = NULL;
-	}
-	else
-		required_outer = NULL;
+	required_outer = rel->lateral_relids;
 
 	/* We need a workspace for keeping track of set-op type coercions */
 	differentTypes = (bool *)
@@ -1175,10 +1180,6 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
 /*
  * set_function_pathlist
  *		Build the (single) access path for a function RTE
- *
- * As with subqueries, a function RTE's path might be parameterized due to
- * LATERAL references, but that's inherent in the function expression and
- * not a result of pushing down join quals.
  */
 static void
 set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
@@ -1186,18 +1187,11 @@ set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 	Relids		required_outer;
 
 	/*
-	 * If it's a LATERAL function, it might contain some Vars of the current
-	 * query level, requiring it to be treated as parameterized.
+	 * We don't support pushing join clauses into the quals of a function
+	 * scan, but it could still have required parameterization due to LATERAL
+	 * refs in the function expression.
 	 */
-	if (rte->lateral)
-	{
-		required_outer = pull_varnos_of_level(rte->funcexpr, 0);
-		/* Enforce convention that empty required_outer is exactly NULL */
-		if (bms_is_empty(required_outer))
-			required_outer = NULL;
-	}
-	else
-		required_outer = NULL;
+	required_outer = rel->lateral_relids;
 
 	/* Generate appropriate path */
 	add_path(rel, create_functionscan_path(root, rel, required_outer));
@@ -1209,10 +1203,6 @@ set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 /*
  * set_values_pathlist
  *		Build the (single) access path for a VALUES RTE
- *
- * As with subqueries, a VALUES RTE's path might be parameterized due to
- * LATERAL references, but that's inherent in the values expressions and
- * not a result of pushing down join quals.
  */
 static void
 set_values_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
@@ -1220,18 +1210,11 @@ set_values_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 	Relids		required_outer;
 
 	/*
-	 * If it's a LATERAL RTE, it might contain some Vars of the current query
-	 * level, requiring it to be treated as parameterized.
+	 * We don't support pushing join clauses into the quals of a values scan,
+	 * but it could still have required parameterization due to LATERAL refs
+	 * in the values expressions.
 	 */
-	if (rte->lateral)
-	{
-		required_outer = pull_varnos_of_level((Node *) rte->values_lists, 0);
-		/* Enforce convention that empty required_outer is exactly NULL */
-		if (bms_is_empty(required_outer))
-			required_outer = NULL;
-	}
-	else
-		required_outer = NULL;
+	required_outer = rel->lateral_relids;
 
 	/* Generate appropriate path */
 	add_path(rel, create_valuesscan_path(root, rel, required_outer));
@@ -1245,7 +1228,7 @@ set_values_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
  *		Build the (single) access path for a non-self-reference CTE RTE
  *
  * There's no need for a separate set_cte_size phase, since we don't
- * support parameterized paths for CTEs.
+ * support join-qual-parameterized paths for CTEs.
  */
 static void
 set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
@@ -1256,6 +1239,7 @@ set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 	int			ndx;
 	ListCell   *lc;
 	int			plan_id;
+	Relids		required_outer;
 
 	/*
 	 * Find the referenced CTE, and locate the plan previously made for it.
@@ -1294,8 +1278,16 @@ set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 	/* Mark rel with estimated output rows, width, etc */
 	set_cte_size_estimates(root, rel, cteplan);
 
+	/*
+	 * We don't support pushing join clauses into the quals of a CTE scan, but
+	 * it could still have required parameterization due to LATERAL refs in
+	 * its tlist.  (That can only happen if the CTE scan is on a relation
+	 * pulled up out of a UNION ALL appendrel.)
+	 */
+	required_outer = rel->lateral_relids;
+
 	/* Generate appropriate path */
-	add_path(rel, create_ctescan_path(root, rel));
+	add_path(rel, create_ctescan_path(root, rel, required_outer));
 
 	/* Select cheapest path (pretty easy in this case...) */
 	set_cheapest(rel);
@@ -1306,7 +1298,7 @@ set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
  *		Build the (single) access path for a self-reference CTE RTE
  *
  * There's no need for a separate set_worktable_size phase, since we don't
- * support parameterized paths for CTEs.
+ * support join-qual-parameterized paths for CTEs.
  */
 static void
 set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
@@ -1314,6 +1306,7 @@ set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 	Plan	   *cteplan;
 	PlannerInfo *cteroot;
 	Index		levelsup;
+	Relids		required_outer;
 
 	/*
 	 * We need to find the non-recursive term's plan, which is in the plan
@@ -1338,8 +1331,18 @@ set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 	/* Mark rel with estimated output rows, width, etc */
 	set_cte_size_estimates(root, rel, cteplan);
 
+	/*
+	 * We don't support pushing join clauses into the quals of a worktable
+	 * scan, but it could still have required parameterization due to LATERAL
+	 * refs in its tlist.  (That can only happen if the worktable scan is on a
+	 * relation pulled up out of a UNION ALL appendrel.  I'm not sure this is
+	 * actually possible given the restrictions on recursive references, but
+	 * it's easy enough to support.)
+	 */
+	required_outer = rel->lateral_relids;
+
 	/* Generate appropriate path */
-	add_path(rel, create_worktablescan_path(root, rel));
+	add_path(rel, create_worktablescan_path(root, rel, required_outer));
 
 	/* Select cheapest path (pretty easy in this case...) */
 	set_cheapest(rel);
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index c7d21d00310..223a0616fa0 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -855,14 +855,19 @@ cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root)
 /*
  * cost_tidscan
  *	  Determines and returns the cost of scanning a relation using TIDs.
+ *
+ * 'baserel' is the relation to be scanned
+ * 'tidquals' is the list of TID-checkable quals
+ * 'param_info' is the ParamPathInfo if this is a parameterized path, else NULL
  */
 void
 cost_tidscan(Path *path, PlannerInfo *root,
-			 RelOptInfo *baserel, List *tidquals)
+			 RelOptInfo *baserel, List *tidquals, ParamPathInfo *param_info)
 {
 	Cost		startup_cost = 0;
 	Cost		run_cost = 0;
 	bool		isCurrentOf = false;
+	QualCost	qpqual_cost;
 	Cost		cpu_per_tuple;
 	QualCost	tid_qual_cost;
 	int			ntuples;
@@ -873,8 +878,11 @@ cost_tidscan(Path *path, PlannerInfo *root,
 	Assert(baserel->relid > 0);
 	Assert(baserel->rtekind == RTE_RELATION);
 
-	/* For now, tidscans are never parameterized */
-	path->rows = baserel->rows;
+	/* Mark the path with the correct row estimate */
+	if (param_info)
+		path->rows = param_info->ppi_rows;
+	else
+		path->rows = baserel->rows;
 
 	/* Count how many tuples we expect to retrieve */
 	ntuples = 0;
@@ -931,10 +939,12 @@ cost_tidscan(Path *path, PlannerInfo *root,
 	/* disk costs --- assume each tuple on a different page */
 	run_cost += spc_random_page_cost * ntuples;
 
-	/* CPU costs */
-	startup_cost += baserel->baserestrictcost.startup +
-		tid_qual_cost.per_tuple;
-	cpu_per_tuple = cpu_tuple_cost + baserel->baserestrictcost.per_tuple -
+	/* Add scanning CPU costs */
+	get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
+
+	/* XXX currently we assume TID quals are a subset of qpquals */
+	startup_cost += qpqual_cost.startup + tid_qual_cost.per_tuple;
+	cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple -
 		tid_qual_cost.per_tuple;
 	run_cost += cpu_per_tuple * ntuples;
 
@@ -1097,25 +1107,32 @@ cost_valuesscan(Path *path, PlannerInfo *root,
  * and should NOT be counted here.
  */
 void
-cost_ctescan(Path *path, PlannerInfo *root, RelOptInfo *baserel)
+cost_ctescan(Path *path, PlannerInfo *root,
+			 RelOptInfo *baserel, ParamPathInfo *param_info)
 {
 	Cost		startup_cost = 0;
 	Cost		run_cost = 0;
+	QualCost	qpqual_cost;
 	Cost		cpu_per_tuple;
 
 	/* Should only be applied to base relations that are CTEs */
 	Assert(baserel->relid > 0);
 	Assert(baserel->rtekind == RTE_CTE);
 
-	/* ctescans are never parameterized */
-	path->rows = baserel->rows;
+	/* Mark the path with the correct row estimate */
+	if (param_info)
+		path->rows = param_info->ppi_rows;
+	else
+		path->rows = baserel->rows;
 
 	/* Charge one CPU tuple cost per row for tuplestore manipulation */
 	cpu_per_tuple = cpu_tuple_cost;
 
 	/* Add scanning CPU costs */
-	startup_cost += baserel->baserestrictcost.startup;
-	cpu_per_tuple += cpu_tuple_cost + baserel->baserestrictcost.per_tuple;
+	get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
+
+	startup_cost += qpqual_cost.startup;
+	cpu_per_tuple += cpu_tuple_cost + qpqual_cost.per_tuple;
 	run_cost += cpu_per_tuple * baserel->tuples;
 
 	path->startup_cost = startup_cost;
@@ -3904,13 +3921,20 @@ set_rel_width(PlannerInfo *root, RelOptInfo *rel)
 	{
 		Node	   *node = (Node *) lfirst(lc);
 
-		if (IsA(node, Var))
+		/*
+		 * Ordinarily, a Var in a rel's reltargetlist must belong to that rel;
+		 * but there are corner cases involving LATERAL references in
+		 * appendrel members where that isn't so (see set_append_rel_size()).
+		 * If the Var has the wrong varno, fall through to the generic case
+		 * (it doesn't seem worth the trouble to be any smarter).
+		 */
+		if (IsA(node, Var) &&
+			((Var *) node)->varno == rel->relid)
 		{
 			Var		   *var = (Var *) node;
 			int			ndx;
 			int32		item_width;
 
-			Assert(var->varno == rel->relid);
 			Assert(var->varattno >= rel->min_attr);
 			Assert(var->varattno <= rel->max_attr);
 
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index b6efb0fb4cd..69fcf90e361 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -194,6 +194,15 @@ static Const *string_to_const(const char *str, Oid datatype);
  * 'rel' is the relation for which we want to generate index paths
  *
  * Note: check_partial_indexes() must have been run previously for this rel.
+ *
+ * Note: in corner cases involving LATERAL appendrel children, it's possible
+ * that rel->lateral_relids is nonempty.  Currently, we include lateral_relids
+ * into the parameterization reported for each path, but don't take it into
+ * account otherwise.  The fact that any such rels *must* be available as
+ * parameter sources perhaps should influence our choices of index quals ...
+ * but for now, it doesn't seem worth troubling over.  In particular, comments
+ * below about "unparameterized" paths should be read as meaning
+ * "unparameterized so far as the indexquals are concerned".
  */
 void
 create_index_paths(PlannerInfo *root, RelOptInfo *rel)
@@ -304,7 +313,8 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel)
 		BitmapHeapPath *bpath;
 
 		bitmapqual = choose_bitmap_and(root, rel, bitindexpaths);
-		bpath = create_bitmap_heap_path(root, rel, bitmapqual, NULL, 1.0);
+		bpath = create_bitmap_heap_path(root, rel, bitmapqual,
+										rel->lateral_relids, 1.0);
 		add_path(rel, (Path *) bpath);
 	}
 
@@ -735,12 +745,13 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
 	 * clause.
 	 *
 	 * We also build a Relids set showing which outer rels are required by the
-	 * selected clauses.
+	 * selected clauses.  Any lateral_relids are included in that, but not
+	 * otherwise accounted for.
 	 */
 	index_clauses = NIL;
 	clause_columns = NIL;
 	found_clause = false;
-	outer_relids = NULL;
+	outer_relids = bms_copy(rel->lateral_relids);
 	for (indexcol = 0; indexcol < index->ncolumns; indexcol++)
 	{
 		ListCell   *lc;
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index f54c3931ce4..d87ba464014 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -149,28 +149,20 @@ add_paths_to_joinrel(PlannerInfo *root,
 
 	/*
 	 * However, when a LATERAL subquery is involved, we have to be a bit
-	 * laxer, because there may simply not be any paths for the joinrel that
-	 * aren't parameterized by whatever the subquery is parameterized by.
-	 * Hence, add to param_source_rels anything that is in the minimum
-	 * parameterization of either input (and not in the other input).
-	 *
-	 * XXX need a more principled way of determining minimum parameterization.
+	 * laxer, because there will simply not be any paths for the joinrel that
+	 * aren't parameterized by whatever the subquery is parameterized by,
+	 * unless its parameterization is resolved within the joinrel.  Hence, add
+	 * to param_source_rels anything that is laterally referenced in either
+	 * input and is not in the join already.
 	 */
-	if (outerrel->cheapest_total_path == NULL)
+	foreach(lc, root->lateral_info_list)
 	{
-		Path	   *cheapest = (Path *) linitial(outerrel->cheapest_parameterized_paths);
+		LateralJoinInfo *ljinfo = (LateralJoinInfo *) lfirst(lc);
 
-		param_source_rels = bms_join(param_source_rels,
-									 bms_difference(PATH_REQ_OUTER(cheapest),
-													innerrel->relids));
-	}
-	if (innerrel->cheapest_total_path == NULL)
-	{
-		Path	   *cheapest = (Path *) linitial(innerrel->cheapest_parameterized_paths);
-
-		param_source_rels = bms_join(param_source_rels,
-									 bms_difference(PATH_REQ_OUTER(cheapest),
-													outerrel->relids));
+		if (bms_is_member(ljinfo->lateral_rhs, joinrel->relids))
+			param_source_rels = bms_join(param_source_rels,
+										 bms_difference(ljinfo->lateral_lhs,
+														joinrel->relids));
 	}
 
 	/*
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 1a01ae9b70e..4c705048147 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -224,11 +224,14 @@ join_search_one_level(PlannerInfo *root, int level)
 		 * to accept failure at level 4 and go on to discover a workable
 		 * bushy plan at level 5.
 		 *
-		 * However, if there are no special joins then join_is_legal() should
-		 * never fail, and so the following sanity check is useful.
+		 * However, if there are no special joins and no lateral references
+		 * then join_is_legal() should never fail, and so the following sanity
+		 * check is useful.
 		 *----------
 		 */
-		if (joinrels[level] == NIL && root->join_info_list == NIL)
+		if (joinrels[level] == NIL &&
+			root->join_info_list == NIL &&
+			root->lateral_info_list == NIL)
 			elog(ERROR, "failed to build any %d-way joins", level);
 	}
 }
@@ -329,6 +332,8 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
 	bool		reversed;
 	bool		unique_ified;
 	bool		is_valid_inner;
+	bool		lateral_fwd;
+	bool		lateral_rev;
 	ListCell   *l;
 
 	/*
@@ -508,6 +513,47 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
 		(match_sjinfo == NULL || unique_ified))
 		return false;			/* invalid join path */
 
+	/*
+	 * We also have to check for constraints imposed by LATERAL references.
+	 * The proposed rels could each contain lateral references to the other,
+	 * in which case the join is impossible.  If there are lateral references
+	 * in just one direction, then the join has to be done with a nestloop
+	 * with the lateral referencer on the inside.  If the join matches an SJ
+	 * that cannot be implemented by such a nestloop, the join is impossible.
+	 */
+	lateral_fwd = lateral_rev = false;
+	foreach(l, root->lateral_info_list)
+	{
+		LateralJoinInfo *ljinfo = (LateralJoinInfo *) lfirst(l);
+
+		if (bms_is_member(ljinfo->lateral_rhs, rel2->relids) &&
+			bms_overlap(ljinfo->lateral_lhs, rel1->relids))
+		{
+			/* has to be implemented as nestloop with rel1 on left */
+			if (lateral_rev)
+				return false;	/* have lateral refs in both directions */
+			lateral_fwd = true;
+			if (!bms_is_subset(ljinfo->lateral_lhs, rel1->relids))
+				return false;	/* rel1 can't compute the required parameter */
+			if (match_sjinfo &&
+				(reversed || match_sjinfo->jointype == JOIN_FULL))
+				return false;	/* not implementable as nestloop */
+		}
+		if (bms_is_member(ljinfo->lateral_rhs, rel1->relids) &&
+			bms_overlap(ljinfo->lateral_lhs, rel2->relids))
+		{
+			/* has to be implemented as nestloop with rel2 on left */
+			if (lateral_fwd)
+				return false;	/* have lateral refs in both directions */
+			lateral_rev = true;
+			if (!bms_is_subset(ljinfo->lateral_lhs, rel2->relids))
+				return false;	/* rel2 can't compute the required parameter */
+			if (match_sjinfo &&
+				(!reversed || match_sjinfo->jointype == JOIN_FULL))
+				return false;	/* not implementable as nestloop */
+		}
+	}
+
 	/* Otherwise, it's a valid join */
 	*sjinfo_p = match_sjinfo;
 	*reversed_p = reversed;
@@ -752,12 +798,14 @@ make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
 /*
  * have_join_order_restriction
  *		Detect whether the two relations should be joined to satisfy
- *		a join-order restriction arising from special joins.
+ *		a join-order restriction arising from special or lateral joins.
  *
  * In practice this is always used with have_relevant_joinclause(), and so
  * could be merged with that function, but it seems clearer to separate the
  * two concerns.  We need this test because there are degenerate cases where
  * a clauseless join must be performed to satisfy join-order restrictions.
+ * Also, if one rel has a lateral reference to the other, we should consider
+ * joining them even if the join would be clauseless.
  *
  * Note: this is only a problem if one side of a degenerate outer join
  * contains multiple rels, or a clauseless join is required within an
@@ -774,6 +822,22 @@ have_join_order_restriction(PlannerInfo *root,
 	ListCell   *l;
 
 	/*
+	 * If either side has a lateral reference to the other, attempt the join
+	 * regardless of outer-join considerations.
+	 */
+	foreach(l, root->lateral_info_list)
+	{
+		LateralJoinInfo *ljinfo = (LateralJoinInfo *) lfirst(l);
+
+		if (bms_is_member(ljinfo->lateral_rhs, rel2->relids) &&
+			bms_overlap(ljinfo->lateral_lhs, rel1->relids))
+			return true;
+		if (bms_is_member(ljinfo->lateral_rhs, rel1->relids) &&
+			bms_overlap(ljinfo->lateral_lhs, rel2->relids))
+			return true;
+	}
+
+	/*
 	 * It's possible that the rels correspond to the left and right sides of a
 	 * degenerate outer join, that is, one with no joinclause mentioning the
 	 * non-nullable side; in which case we should force the join to occur.
@@ -846,8 +910,9 @@ have_join_order_restriction(PlannerInfo *root,
 
 /*
  * has_join_restriction
- *		Detect whether the specified relation has join-order restrictions
- *		due to being inside an outer join or an IN (sub-SELECT).
+ *		Detect whether the specified relation has join-order restrictions,
+ *		due to being inside an outer join or an IN (sub-SELECT),
+ *		or participating in any LATERAL references.
  *
  * Essentially, this tests whether have_join_order_restriction() could
  * succeed with this rel and some other one.  It's OK if we sometimes
@@ -859,6 +924,15 @@ has_join_restriction(PlannerInfo *root, RelOptInfo *rel)
 {
 	ListCell   *l;
 
+	foreach(l, root->lateral_info_list)
+	{
+		LateralJoinInfo *ljinfo = (LateralJoinInfo *) lfirst(l);
+
+		if (bms_is_member(ljinfo->lateral_rhs, rel->relids) ||
+			bms_overlap(ljinfo->lateral_lhs, rel->relids))
+			return true;
+	}
+
 	foreach(l, root->join_info_list)
 	{
 		SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
diff --git a/src/backend/optimizer/path/tidpath.c b/src/backend/optimizer/path/tidpath.c
index 35702c27050..36390d50a2e 100644
--- a/src/backend/optimizer/path/tidpath.c
+++ b/src/backend/optimizer/path/tidpath.c
@@ -249,10 +249,20 @@ TidQualFromRestrictinfo(List *restrictinfo, int varno)
 void
 create_tidscan_paths(PlannerInfo *root, RelOptInfo *rel)
 {
+	Relids		required_outer;
 	List	   *tidquals;
 
+	/*
+	 * We don't support pushing join clauses into the quals of a tidscan, but
+	 * it could still have required parameterization due to LATERAL refs in
+	 * its tlist.  (That can only happen if the tidscan is on a relation
+	 * pulled up out of a UNION ALL appendrel.)
+	 */
+	required_outer = rel->lateral_relids;
+
 	tidquals = TidQualFromRestrictinfo(rel->baserestrictinfo, rel->relid);
 
 	if (tidquals)
-		add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals));
+		add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
+												   required_outer));
 }
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 5abb114ba8e..6917ee55aa6 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -298,6 +298,7 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids)
 	List	   *joininfos;
 	Index		rti;
 	ListCell   *l;
+	ListCell   *nextl;
 
 	/*
 	 * Mark the rel as "dead" to show it is no longer part of the join tree.
@@ -351,6 +352,26 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids)
 	}
 
 	/*
+	 * Likewise remove references from LateralJoinInfo data structures.
+	 *
+	 * If we are deleting a LATERAL subquery, we can forget its
+	 * LateralJoinInfo altogether.  Otherwise, make sure the target is not
+	 * included in any lateral_lhs set.  (It probably can't be, since that
+	 * should have precluded deciding to remove it; but let's cope anyway.)
+	 */
+	for (l = list_head(root->lateral_info_list); l != NULL; l = nextl)
+	{
+		LateralJoinInfo *ljinfo = (LateralJoinInfo *) lfirst(l);
+
+		nextl = lnext(l);
+		if (ljinfo->lateral_rhs == relid)
+			root->lateral_info_list = list_delete_ptr(root->lateral_info_list,
+													  ljinfo);
+		else
+			ljinfo->lateral_lhs = bms_del_member(ljinfo->lateral_lhs, relid);
+	}
+
+	/*
 	 * Likewise remove references from PlaceHolderVar data structures.
 	 *
 	 * Here we have a special case: if a PHV's eval_at set is just the target
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index d45ebfc4616..5d3b293b88a 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -298,8 +298,19 @@ create_scan_plan(PlannerInfo *root, Path *best_path)
 		}
 	}
 	else
+	{
 		tlist = build_relation_tlist(rel);
 
+		/*
+		 * If it's a parameterized otherrel, there might be lateral references
+		 * in the tlist, which need to be replaced with Params.  This cannot
+		 * happen for regular baserels, though.  Note use_physical_tlist()
+		 * always fails for otherrels, so we don't need to check this above.
+		 */
+		if (rel->reloptkind != RELOPT_BASEREL && best_path->param_info)
+			tlist = (List *) replace_nestloop_params(root, (Node *) tlist);
+	}
+
 	/*
 	 * Extract the relevant restriction clauses from the parent relation. The
 	 * executor must apply all these restrictions during the scan, except for
@@ -1583,6 +1594,7 @@ create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
 {
 	TidScan    *scan_plan;
 	Index		scan_relid = best_path->path.parent->relid;
+	List	   *tidquals = best_path->tidquals;
 	List	   *ortidquals;
 
 	/* it should be a base rel... */
@@ -1595,11 +1607,20 @@ create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
 	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
 	scan_clauses = extract_actual_clauses(scan_clauses, false);
 
+	/* Replace any outer-relation variables with nestloop params */
+	if (best_path->path.param_info)
+	{
+		tidquals = (List *)
+			replace_nestloop_params(root, (Node *) tidquals);
+		scan_clauses = (List *)
+			replace_nestloop_params(root, (Node *) scan_clauses);
+	}
+
 	/*
 	 * Remove any clauses that are TID quals.  This is a bit tricky since the
 	 * tidquals list has implicit OR semantics.
 	 */
-	ortidquals = best_path->tidquals;
+	ortidquals = tidquals;
 	if (list_length(ortidquals) > 1)
 		ortidquals = list_make1(make_orclause(ortidquals));
 	scan_clauses = list_difference(scan_clauses, ortidquals);
@@ -1607,7 +1628,7 @@ create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
 	scan_plan = make_tidscan(tlist,
 							 scan_clauses,
 							 scan_relid,
-							 best_path->tidquals);
+							 tidquals);
 
 	copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
 
@@ -1823,6 +1844,13 @@ create_ctescan_plan(PlannerInfo *root, Path *best_path,
 	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
 	scan_clauses = extract_actual_clauses(scan_clauses, false);
 
+	/* Replace any outer-relation variables with nestloop params */
+	if (best_path->param_info)
+	{
+		scan_clauses = (List *)
+			replace_nestloop_params(root, (Node *) scan_clauses);
+	}
+
 	scan_plan = make_ctescan(tlist, scan_clauses, scan_relid,
 							 plan_id, cte_param_id);
 
@@ -1876,6 +1904,13 @@ create_worktablescan_plan(PlannerInfo *root, Path *best_path,
 	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
 	scan_clauses = extract_actual_clauses(scan_clauses, false);
 
+	/* Replace any outer-relation variables with nestloop params */
+	if (best_path->param_info)
+	{
+		scan_clauses = (List *)
+			replace_nestloop_params(root, (Node *) scan_clauses);
+	}
+
 	scan_plan = make_worktablescan(tlist, scan_clauses, scan_relid,
 								   cteroot->wt_param_id);
 
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index 81f7cf2e9d8..824c6a7e473 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -22,9 +22,11 @@
 #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 "optimizer/var.h"
+#include "rewrite/rewriteManip.h"
 #include "utils/lsyscache.h"
 
 
@@ -33,6 +35,9 @@ int			from_collapse_limit;
 int			join_collapse_limit;
 
 
+static void extract_lateral_references(PlannerInfo *root, RelOptInfo *brel,
+						   Index rtindex);
+static void add_lateral_info(PlannerInfo *root, Index rhs, Relids lhs);
 static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode,
 					bool below_outer_join,
 					Relids *qualscope, Relids *inner_join_rels);
@@ -204,18 +209,75 @@ add_vars_to_targetlist(PlannerInfo *root, List *vars,
 	}
 }
 
+
+/*****************************************************************************
+ *
+ *	  LATERAL REFERENCES
+ *
+ *****************************************************************************/
+
 /*
- * extract_lateral_references
- *	  If the specified RTE is a LATERAL subquery, extract all its references
- *	  to Vars of the current query level, and make sure those Vars will be
- *	  available for evaluation of the RTE.
+ * 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.
  *
- * XXX this is rather duplicative of processing that has to happen elsewhere.
- * Maybe it'd be a good idea to do this type of extraction further upstream
- * and save the results?
+ * 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.
+ *
+ * This has to run before deconstruct_jointree, since it might result in
+ * creation of PlaceHolderInfos or extension of their ph_may_need sets.
  */
+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
+		 * otherrels that are actually going to be in the plan.  However, we
+		 * want to mark all their 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 members are
+		 * nothing but copies of parts of the original RTE's subquery.  We
+		 * could visit the 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.)
+		 */
+
+		/* 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, int rtindex)
+extract_lateral_references(PlannerInfo *root, RelOptInfo *brel, Index rtindex)
 {
 	RangeTblEntry *rte = root->simple_rte_array[rtindex];
 	List	   *vars;
@@ -235,35 +297,52 @@ extract_lateral_references(PlannerInfo *root, int rtindex)
 	else if (rte->rtekind == RTE_VALUES)
 		vars = pull_vars_of_level((Node *) rte->values_lists, 0);
 	else
-		return;
+	{
+		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   *var = (Node *) lfirst(lc);
+		Node   *node = (Node *) lfirst(lc);
 
-		var = copyObject(var);
-		if (IsA(var, Var))
+		node = copyObject(node);
+		if (IsA(node, Var))
 		{
-			((Var *) var)->varlevelsup = 0;
+			Var	   *var = (Var *) node;
+
+			/* Adjustment is easy since it's just one node */
+			var->varlevelsup = 0;
 		}
-		else if (IsA(var, PlaceHolderVar))
+		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);
+
 			/*
-			 * It's sufficient to set phlevelsup = 0, because we call
-			 * add_vars_to_targetlist with create_new_ph = false (as we must,
-			 * because deconstruct_jointree has already started); therefore
-			 * nobody is going to look at the contained expression to notice
-			 * whether its Vars have the right level.
+			 * 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.
 			 */
-			((PlaceHolderVar *) var)->phlevelsup = 0;
+			if (levelsup > 0)
+				phv->phexpr = preprocess_phv_expression(root, phv->phexpr);
 		}
 		else
 			Assert(false);
-		newvars = lappend(newvars, var);
+		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
@@ -274,10 +353,146 @@ extract_lateral_references(PlannerInfo *root, int rtindex)
 	where_needed = bms_make_singleton(rtindex);
 
 	/* Push the Vars into their source relations' targetlists */
-	add_vars_to_targetlist(root, newvars, where_needed, false);
+	add_vars_to_targetlist(root, newvars, where_needed, true);
 
-	list_free(newvars);
-	list_free(vars);
+	/* Remember the lateral references for create_lateral_join_info */
+	brel->lateral_vars = newvars;
+}
+
+/*
+ * create_lateral_join_info
+ *	  For each LATERAL subquery, create LateralJoinInfo(s) and add them to
+ *	  root->lateral_info_list, and fill in the per-rel lateral_relids sets.
+ *
+ * This has to run after deconstruct_jointree, because we need to know the
+ * final ph_eval_at values for referenced PlaceHolderVars.
+ */
+void
+create_lateral_join_info(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];
+		Relids		lateral_relids;
+		ListCell *lc;
+
+		/* 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;
+
+				add_lateral_info(root, rti, bms_make_singleton(var->varno));
+				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);
+
+				add_lateral_info(root, rti, bms_copy(phinfo->ph_eval_at));
+				lateral_relids = bms_add_members(lateral_relids,
+												 phinfo->ph_eval_at);
+			}
+			else
+				Assert(false);
+		}
+
+		/* We now know all the relids needed for lateral refs in this rel */
+		if (bms_is_empty(lateral_relids))
+			continue;			/* ensure lateral_relids is NULL if empty */
+		brel->lateral_relids = lateral_relids;
+
+		/*
+		 * If it's an appendrel parent, copy its lateral_relids to each child
+		 * rel.  We intentionally give each child rel the same minimum
+		 * parameterization, even though it's quite possible that some don't
+		 * reference all the lateral rels.  This is because any append path
+		 * for the parent will have to have the same parameterization for
+		 * every child anyway, and there's no value in forcing extra
+		 * reparameterize_path() calls.
+		 */
+		if (root->simple_rte_array[rti]->inh)
+		{
+			foreach(lc, root->append_rel_list)
+			{
+				AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
+				RelOptInfo *childrel;
+
+				if (appinfo->parent_relid != rti)
+					continue;
+				childrel = root->simple_rel_array[appinfo->child_relid];
+				Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL);
+				Assert(childrel->lateral_relids == NULL);
+				childrel->lateral_relids = lateral_relids;
+			}
+		}
+	}
+}
+
+/*
+ * add_lateral_info
+ *		Add a LateralJoinInfo to root->lateral_info_list, if needed
+ *
+ * We suppress redundant list entries.  The passed lhs set must be freshly
+ * made; we free it if not used in a new list entry.
+ */
+static void
+add_lateral_info(PlannerInfo *root, Index rhs, Relids lhs)
+{
+	LateralJoinInfo *ljinfo;
+	ListCell   *l;
+
+	Assert(!bms_is_member(rhs, lhs));
+
+	/*
+	 * If an existing list member has the same RHS and an LHS that is a subset
+	 * of the new one, it's redundant, but we don't trouble to get rid of it.
+	 * The only case that is really worth worrying about is identical entries,
+	 * and we handle that well enough with this simple logic.
+	 */
+	foreach(l, root->lateral_info_list)
+	{
+		ljinfo = (LateralJoinInfo *) lfirst(l);
+		if (rhs == ljinfo->lateral_rhs &&
+			bms_is_subset(lhs, ljinfo->lateral_lhs))
+		{
+			bms_free(lhs);
+			return;
+		}
+	}
+
+	/* Not there, so make a new entry */
+	ljinfo = makeNode(LateralJoinInfo);
+	ljinfo->lateral_rhs = rhs;
+	ljinfo->lateral_lhs = lhs;
+	root->lateral_info_list = lappend(root->lateral_info_list, ljinfo);
 }
 
 
@@ -362,9 +577,7 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
 	{
 		int			varno = ((RangeTblRef *) jtnode)->rtindex;
 
-		/* No quals to deal with, but do check for LATERAL subqueries */
-		extract_lateral_references(root, varno);
-		/* Result qualscope is just the one Relid */
+		/* No quals to deal with, just return correct result */
 		*qualscope = bms_make_singleton(varno);
 		/* A single baserel does not create an inner join */
 		*inner_join_rels = NULL;
diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c
index 0bbca071fb0..373f65b76fe 100644
--- a/src/backend/optimizer/plan/planagg.c
+++ b/src/backend/optimizer/plan/planagg.c
@@ -392,8 +392,9 @@ build_minmax_path(PlannerInfo *root, MinMaxAggInfo *mminfo,
 	subroot->parse = parse = (Query *) copyObject(root->parse);
 	/* make sure subroot planning won't change root->init_plans contents */
 	subroot->init_plans = list_copy(root->init_plans);
-	/* There shouldn't be any OJ info to translate, as yet */
+	/* There shouldn't be any OJ or LATERAL info to translate, as yet */
 	Assert(subroot->join_info_list == NIL);
+	Assert(subroot->lateral_info_list == NIL);
 	/* and we haven't created PlaceHolderInfos, either */
 	Assert(subroot->placeholder_list == NIL);
 
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index 9838dc45d5e..04acc006f53 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -141,6 +141,7 @@ query_planner(PlannerInfo *root, List *tlist,
 	root->right_join_clauses = NIL;
 	root->full_join_clauses = NIL;
 	root->join_info_list = NIL;
+	root->lateral_info_list = NIL;
 	root->placeholder_list = NIL;
 	root->initial_rels = NIL;
 
@@ -178,9 +179,17 @@ query_planner(PlannerInfo *root, List *tlist,
 
 	find_placeholders_in_jointree(root);
 
+	find_lateral_references(root);
+
 	joinlist = deconstruct_jointree(root);
 
 	/*
+	 * Create the LateralJoinInfo list now that we have finalized
+	 * PlaceHolderVar eval levels.
+	 */
+	create_lateral_join_info(root);
+
+	/*
 	 * Reconsider any postponed outer-join quals now that we have built up
 	 * equivalence classes.  (This could result in further additions or
 	 * mergings of classes.)
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 3485f2025ca..6170d48892e 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -54,6 +54,7 @@ planner_hook_type planner_hook = NULL;
 #define EXPRKIND_VALUES		3
 #define EXPRKIND_LIMIT		4
 #define EXPRKIND_APPINFO	5
+#define EXPRKIND_PHV		6
 
 
 static Node *preprocess_expression(PlannerInfo *root, Node *expr, int kind);
@@ -348,10 +349,12 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
 	/*
 	 * Detect whether any rangetable entries are RTE_JOIN kind; if not, we can
 	 * avoid the expense of doing flatten_join_alias_vars().  Also check for
-	 * outer joins --- if none, we can skip reduce_outer_joins(). This must be
-	 * done after we have done pull_up_subqueries, of course.
+	 * outer joins --- if none, we can skip reduce_outer_joins().  And check
+	 * for LATERAL RTEs, too.  This must be done after we have done
+	 * pull_up_subqueries(), of course.
 	 */
 	root->hasJoinRTEs = false;
+	root->hasLateralRTEs = false;
 	hasOuterJoins = false;
 	foreach(l, parse->rtable)
 	{
@@ -361,12 +364,10 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
 		{
 			root->hasJoinRTEs = true;
 			if (IS_OUTER_JOIN(rte->jointype))
-			{
 				hasOuterJoins = true;
-				/* Can quit scanning once we find an outer join */
-				break;
-			}
 		}
+		if (rte->lateral)
+			root->hasLateralRTEs = true;
 	}
 
 	/*
@@ -576,7 +577,7 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
  * preprocess_expression
  *		Do subquery_planner's preprocessing work for an expression,
  *		which can be a targetlist, a WHERE clause (including JOIN/ON
- *		conditions), or a HAVING clause.
+ *		conditions), a HAVING clause, or a few other things.
  */
 static Node *
 preprocess_expression(PlannerInfo *root, Node *expr, int kind)
@@ -693,6 +694,23 @@ preprocess_qual_conditions(PlannerInfo *root, Node *jtnode)
 }
 
 /*
+ * preprocess_phv_expression
+ *	  Do preprocessing on a PlaceHolderVar expression that's been pulled up.
+ *
+ * If a LATERAL subquery references an output of another subquery, and that
+ * output must be wrapped in a PlaceHolderVar because of an intermediate outer
+ * join, then we'll push the PlaceHolderVar expression down into the subquery
+ * and later pull it back up during find_lateral_references, which runs after
+ * subquery_planner has preprocessed all the expressions that were in the
+ * current query level to start with.  So we need to preprocess it then.
+ */
+Expr *
+preprocess_phv_expression(PlannerInfo *root, Expr *expr)
+{
+	return (Expr *) preprocess_expression(root, (Node *) expr, EXPRKIND_PHV);
+}
+
+/*
  * inheritance_planner
  *	  Generate a plan in the case where the result relation is an
  *	  inheritance set.
@@ -821,8 +839,9 @@ inheritance_planner(PlannerInfo *root)
 		}
 
 		/* We needn't modify the child's append_rel_list */
-		/* There shouldn't be any OJ info to translate, as yet */
+		/* There shouldn't be any OJ or LATERAL info to translate, as yet */
 		Assert(subroot.join_info_list == NIL);
+		Assert(subroot.lateral_info_list == NIL);
 		/* and we haven't created PlaceHolderInfos, either */
 		Assert(subroot.placeholder_list == NIL);
 		/* hack to mark target relation as an inheritance partition */
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index d391ce540d2..3d1fcdc16c9 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -1026,11 +1026,14 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 										subroot->append_rel_list);
 
 	/*
-	 * We don't have to do the equivalent bookkeeping for outer-join info,
-	 * because that hasn't been set up yet.  placeholder_list likewise.
+	 * We don't have to do the equivalent bookkeeping for outer-join or
+	 * LATERAL info, because that hasn't been set up yet.  placeholder_list
+	 * likewise.
 	 */
 	Assert(root->join_info_list == NIL);
 	Assert(subroot->join_info_list == NIL);
+	Assert(root->lateral_info_list == NIL);
+	Assert(subroot->lateral_info_list == NIL);
 	Assert(root->placeholder_list == NIL);
 	Assert(subroot->placeholder_list == NIL);
 
@@ -2319,6 +2322,7 @@ substitute_multiple_relids_walker(Node *node,
 	}
 	/* Shouldn't need to handle planner auxiliary nodes here */
 	Assert(!IsA(node, SpecialJoinInfo));
+	Assert(!IsA(node, LateralJoinInfo));
 	Assert(!IsA(node, AppendRelInfo));
 	Assert(!IsA(node, PlaceHolderInfo));
 	Assert(!IsA(node, MinMaxAggInfo));
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index 8ee6cf7f0e0..9e8d942f6f3 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -1746,6 +1746,7 @@ adjust_appendrel_attrs_mutator(Node *node,
 	}
 	/* Shouldn't need to handle planner auxiliary nodes here */
 	Assert(!IsA(node, SpecialJoinInfo));
+	Assert(!IsA(node, LateralJoinInfo));
 	Assert(!IsA(node, AppendRelInfo));
 	Assert(!IsA(node, PlaceHolderInfo));
 	Assert(!IsA(node, MinMaxAggInfo));
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index d16c3b8db1c..691afbf0ed6 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -902,18 +902,21 @@ create_bitmap_or_path(PlannerInfo *root,
  *	  Creates a path corresponding to a scan by TID, returning the pathnode.
  */
 TidPath *
-create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals)
+create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals,
+					Relids required_outer)
 {
 	TidPath    *pathnode = makeNode(TidPath);
 
 	pathnode->path.pathtype = T_TidScan;
 	pathnode->path.parent = rel;
-	pathnode->path.param_info = NULL;	/* never parameterized at present */
+	pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
+														  required_outer);
 	pathnode->path.pathkeys = NIL;		/* always unordered */
 
 	pathnode->tidquals = tidquals;
 
-	cost_tidscan(&pathnode->path, root, rel, tidquals);
+	cost_tidscan(&pathnode->path, root, rel, tidquals,
+				 pathnode->path.param_info);
 
 	return pathnode;
 }
@@ -1061,7 +1064,7 @@ create_result_path(List *quals)
 
 	pathnode->path.pathtype = T_Result;
 	pathnode->path.parent = NULL;
-	pathnode->path.param_info = NULL;
+	pathnode->path.param_info = NULL;		/* there are no other rels... */
 	pathnode->path.pathkeys = NIL;
 	pathnode->quals = quals;
 
@@ -1711,16 +1714,17 @@ create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel,
  *	  returning the pathnode.
  */
 Path *
-create_ctescan_path(PlannerInfo *root, RelOptInfo *rel)
+create_ctescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer)
 {
 	Path	   *pathnode = makeNode(Path);
 
 	pathnode->pathtype = T_CteScan;
 	pathnode->parent = rel;
-	pathnode->param_info = NULL;	/* never parameterized at present */
+	pathnode->param_info = get_baserel_parampathinfo(root, rel,
+													 required_outer);
 	pathnode->pathkeys = NIL;	/* XXX for now, result is always unordered */
 
-	cost_ctescan(pathnode, root, rel);
+	cost_ctescan(pathnode, root, rel, pathnode->param_info);
 
 	return pathnode;
 }
@@ -1731,17 +1735,19 @@ create_ctescan_path(PlannerInfo *root, RelOptInfo *rel)
  *	  returning the pathnode.
  */
 Path *
-create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel)
+create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel,
+						  Relids required_outer)
 {
 	Path	   *pathnode = makeNode(Path);
 
 	pathnode->pathtype = T_WorkTableScan;
 	pathnode->parent = rel;
-	pathnode->param_info = NULL;	/* never parameterized at present */
+	pathnode->param_info = get_baserel_parampathinfo(root, rel,
+													 required_outer);
 	pathnode->pathkeys = NIL;	/* result is always unordered */
 
 	/* Cost is the same as for a regular CTE scan */
-	cost_ctescan(pathnode, root, rel);
+	cost_ctescan(pathnode, root, rel, pathnode->param_info);
 
 	return pathnode;
 }
diff --git a/src/backend/optimizer/util/placeholder.c b/src/backend/optimizer/util/placeholder.c
index e05c8ddef1b..317a01940e3 100644
--- a/src/backend/optimizer/util/placeholder.c
+++ b/src/backend/optimizer/util/placeholder.c
@@ -412,14 +412,14 @@ add_placeholders_to_base_rels(PlannerInfo *root)
 		PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
 		Relids		eval_at = phinfo->ph_eval_at;
 
-		if (bms_membership(eval_at) == BMS_SINGLETON)
+		if (bms_membership(eval_at) == BMS_SINGLETON &&
+			bms_nonempty_difference(phinfo->ph_needed, eval_at))
 		{
 			int			varno = bms_singleton_member(eval_at);
 			RelOptInfo *rel = find_base_rel(root, varno);
 
-			if (bms_nonempty_difference(phinfo->ph_needed, rel->relids))
-				rel->reltargetlist = lappend(rel->reltargetlist,
-											 copyObject(phinfo->ph_var));
+			rel->reltargetlist = lappend(rel->reltargetlist,
+										 copyObject(phinfo->ph_var));
 		}
 	}
 }
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 8d4ab03d20e..680184c0e9f 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -109,6 +109,8 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptKind reloptkind)
 	rel->relid = relid;
 	rel->rtekind = rte->rtekind;
 	/* min_attr, max_attr, attr_needed, attr_widths are set below */
+	rel->lateral_vars = NIL;
+	rel->lateral_relids = NULL;
 	rel->indexlist = NIL;
 	rel->pages = 0;
 	rel->tuples = 0;
@@ -365,6 +367,8 @@ build_join_rel(PlannerInfo *root,
 	joinrel->max_attr = 0;
 	joinrel->attr_needed = NULL;
 	joinrel->attr_widths = NULL;
+	joinrel->lateral_vars = NIL;
+	joinrel->lateral_relids = NULL;
 	joinrel->indexlist = NIL;
 	joinrel->pages = 0;
 	joinrel->tuples = 0;
@@ -472,8 +476,7 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
 
 	foreach(vars, input_rel->reltargetlist)
 	{
-		Node	   *origvar = (Node *) lfirst(vars);
-		Var		   *var;
+		Var		   *var = (Var *) lfirst(vars);
 		RelOptInfo *baserel;
 		int			ndx;
 
@@ -481,22 +484,17 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
 		 * Ignore PlaceHolderVars in the input tlists; we'll make our own
 		 * decisions about whether to copy them.
 		 */
-		if (IsA(origvar, PlaceHolderVar))
+		if (IsA(var, PlaceHolderVar))
 			continue;
 
 		/*
-		 * We can't run into any child RowExprs here, but we could find a
-		 * whole-row Var with a ConvertRowtypeExpr atop it.
+		 * Otherwise, anything in a baserel or joinrel targetlist ought to be
+		 * a Var.  (More general cases can only appear in appendrel child
+		 * rels, which will never be seen here.)
 		 */
-		var = (Var *) origvar;
-		while (!IsA(var, Var))
-		{
-			if (IsA(var, ConvertRowtypeExpr))
-				var = (Var *) ((ConvertRowtypeExpr *) var)->arg;
-			else
-				elog(ERROR, "unexpected node type in reltargetlist: %d",
-					 (int) nodeTag(var));
-		}
+		if (!IsA(var, Var))
+			elog(ERROR, "unexpected node type in reltargetlist: %d",
+				 (int) nodeTag(var));
 
 		/* Get the Var's original base rel */
 		baserel = find_base_rel(root, var->varno);
@@ -506,7 +504,7 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
 		if (bms_nonempty_difference(baserel->attr_needed[ndx], relids))
 		{
 			/* Yup, add it to the output */
-			joinrel->reltargetlist = lappend(joinrel->reltargetlist, origvar);
+			joinrel->reltargetlist = lappend(joinrel->reltargetlist, var);
 			joinrel->width += baserel->attr_widths[ndx];
 		}
 	}
diff --git a/src/backend/optimizer/util/var.c b/src/backend/optimizer/util/var.c
index 21b7753f05d..a0668c9615b 100644
--- a/src/backend/optimizer/util/var.c
+++ b/src/backend/optimizer/util/var.c
@@ -746,6 +746,7 @@ flatten_join_alias_vars_mutator(Node *node,
 	Assert(!IsA(node, SubPlan));
 	/* Shouldn't need to handle these planner auxiliary nodes here */
 	Assert(!IsA(node, SpecialJoinInfo));
+	Assert(!IsA(node, LateralJoinInfo));
 	Assert(!IsA(node, PlaceHolderInfo));
 	Assert(!IsA(node, MinMaxAggInfo));
 
diff --git a/src/backend/rewrite/rewriteManip.c b/src/backend/rewrite/rewriteManip.c
index 5fcf2741988..ef04c342a29 100644
--- a/src/backend/rewrite/rewriteManip.c
+++ b/src/backend/rewrite/rewriteManip.c
@@ -367,6 +367,7 @@ OffsetVarNodes_walker(Node *node, OffsetVarNodes_context *context)
 	/* Shouldn't need to handle other planner auxiliary nodes here */
 	Assert(!IsA(node, PlanRowMark));
 	Assert(!IsA(node, SpecialJoinInfo));
+	Assert(!IsA(node, LateralJoinInfo));
 	Assert(!IsA(node, PlaceHolderInfo));
 	Assert(!IsA(node, MinMaxAggInfo));
 
@@ -548,6 +549,7 @@ ChangeVarNodes_walker(Node *node, ChangeVarNodes_context *context)
 	}
 	/* Shouldn't need to handle other planner auxiliary nodes here */
 	Assert(!IsA(node, SpecialJoinInfo));
+	Assert(!IsA(node, LateralJoinInfo));
 	Assert(!IsA(node, PlaceHolderInfo));
 	Assert(!IsA(node, MinMaxAggInfo));
 
@@ -816,6 +818,7 @@ rangeTableEntry_used_walker(Node *node,
 	Assert(!IsA(node, PlaceHolderVar));
 	Assert(!IsA(node, PlanRowMark));
 	Assert(!IsA(node, SpecialJoinInfo));
+	Assert(!IsA(node, LateralJoinInfo));
 	Assert(!IsA(node, AppendRelInfo));
 	Assert(!IsA(node, PlaceHolderInfo));
 	Assert(!IsA(node, MinMaxAggInfo));
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index b96a30b60ed..438a1d98630 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -235,6 +235,7 @@ typedef enum NodeTag
 	T_RestrictInfo,
 	T_PlaceHolderVar,
 	T_SpecialJoinInfo,
+	T_LateralJoinInfo,
 	T_AppendRelInfo,
 	T_PlaceHolderInfo,
 	T_MinMaxAggInfo,
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 8238981c289..43c2956fdf5 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -193,7 +193,9 @@ typedef struct PlannerInfo
 	List	   *full_join_clauses;		/* list of RestrictInfos for
 										 * mergejoinable full join clauses */
 
-	List	   *join_info_list; /* list of SpecialJoinInfos */
+	List	   *join_info_list;		/* list of SpecialJoinInfos */
+
+	List	   *lateral_info_list;	/* list of LateralJoinInfos */
 
 	List	   *append_rel_list;	/* list of AppendRelInfos */
 
@@ -223,6 +225,7 @@ typedef struct PlannerInfo
 	bool		hasInheritedTarget;		/* true if parse->resultRelation is an
 										 * inheritance child rel */
 	bool		hasJoinRTEs;	/* true if any RTEs are RTE_JOIN kind */
+	bool		hasLateralRTEs;	/* true if any RTEs are marked LATERAL */
 	bool		hasHavingQual;	/* true if havingQual was non-null */
 	bool		hasPseudoConstantQuals; /* true if any RestrictInfo has
 										 * pseudoconstant = true */
@@ -300,8 +303,8 @@ typedef struct PlannerInfo
  *						we need to output from this relation.
  *						List is in no particular order, but all rels of an
  *						appendrel set must use corresponding orders.
- *						NOTE: in a child relation, may contain RowExpr or
- *						ConvertRowtypeExpr representing a whole-row Var.
+ *						NOTE: in an appendrel child relation, may contain
+ *						arbitrary expressions pulled up from a subquery!
  *		pathlist - List of Path nodes, one for each potentially useful
  *				   method of generating the relation
  *		ppilist - ParamPathInfo nodes for parameterized Paths, if any
@@ -330,6 +333,10 @@ typedef struct PlannerInfo
  *				the attribute is needed as part of final targetlist
  *		attr_widths - cache space for per-attribute width estimates;
  *					  zero means not computed yet
+ *		lateral_vars - lateral cross-references of rel, if any (list of
+ *					   Vars and PlaceHolderVars)
+ *		lateral_relids - required outer rels for LATERAL, as a Relids set
+ *						 (for child rels this can be more than lateral_vars)
  *		indexlist - list of IndexOptInfo nodes for relation's indexes
  *					(always NIL if it's not a table)
  *		pages - number of disk pages in relation (zero if not a table)
@@ -417,6 +424,8 @@ typedef struct RelOptInfo
 	AttrNumber	max_attr;		/* largest attrno of rel */
 	Relids	   *attr_needed;	/* array indexed [min_attr .. max_attr] */
 	int32	   *attr_widths;	/* array indexed [min_attr .. max_attr] */
+	List	   *lateral_vars;	/* LATERAL Vars and PHVs referenced by rel */
+	Relids		lateral_relids;	/* minimum parameterization of rel */
 	List	   *indexlist;		/* list of IndexOptInfo */
 	BlockNumber pages;			/* size estimates derived from pg_class */
 	double		tuples;
@@ -1324,6 +1333,35 @@ typedef struct SpecialJoinInfo
 } SpecialJoinInfo;
 
 /*
+ * "Lateral join" info.
+ *
+ * Lateral references in subqueries constrain the join order in a way that's
+ * somewhat like outer joins, though different in detail.  We construct one or
+ * more LateralJoinInfos for each RTE with lateral references, and add them to
+ * the PlannerInfo node's lateral_info_list.
+ *
+ * lateral_rhs is the relid of a baserel with lateral references, and
+ * lateral_lhs is a set of relids of baserels it references, all of which
+ * must be present on the LHS to compute a parameter needed by the RHS.
+ * Typically, lateral_lhs is a singleton, but it can include multiple rels
+ * if the RHS references a PlaceHolderVar with a multi-rel ph_eval_at level.
+ * We disallow joining to only part of the LHS in such cases, since that would
+ * result in a join tree with no convenient place to compute the PHV.
+ *
+ * When an appendrel contains lateral references (eg "LATERAL (SELECT x.col1
+ * UNION ALL SELECT y.col2)"), the LateralJoinInfos reference the parent
+ * baserel not the member otherrels, since it is the parent relid that is
+ * considered for joining purposes.
+ */
+
+typedef struct LateralJoinInfo
+{
+	NodeTag		type;
+	Index		lateral_rhs;	/* a baserel containing lateral refs */
+	Relids		lateral_lhs;	/* some base relids it references */
+} LateralJoinInfo;
+
+/*
  * Append-relation info.
  *
  * When we expand an inheritable table or a UNION-ALL subselect into an
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 7f6870e5f08..1cc9a7e5397 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -77,14 +77,15 @@ extern void cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root);
 extern void cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root);
 extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec);
 extern void cost_tidscan(Path *path, PlannerInfo *root,
-			 RelOptInfo *baserel, List *tidquals);
+			 RelOptInfo *baserel, List *tidquals, ParamPathInfo *param_info);
 extern void cost_subqueryscan(Path *path, PlannerInfo *root,
 				  RelOptInfo *baserel, ParamPathInfo *param_info);
 extern void cost_functionscan(Path *path, PlannerInfo *root,
 				  RelOptInfo *baserel, ParamPathInfo *param_info);
 extern void cost_valuesscan(Path *path, PlannerInfo *root,
 				RelOptInfo *baserel, ParamPathInfo *param_info);
-extern void cost_ctescan(Path *path, PlannerInfo *root, RelOptInfo *baserel);
+extern void cost_ctescan(Path *path, PlannerInfo *root,
+			 RelOptInfo *baserel, ParamPathInfo *param_info);
 extern void cost_recursive_union(Plan *runion, Plan *nrterm, Plan *rterm);
 extern void cost_sort(Path *path, PlannerInfo *root,
 		  List *pathkeys, Cost input_cost, double tuples, int width,
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 33f2bf13c09..de889fbfa68 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -55,7 +55,7 @@ extern BitmapOrPath *create_bitmap_or_path(PlannerInfo *root,
 					  RelOptInfo *rel,
 					  List *bitmapquals);
 extern TidPath *create_tidscan_path(PlannerInfo *root, RelOptInfo *rel,
-					List *tidquals);
+					List *tidquals, Relids required_outer);
 extern AppendPath *create_append_path(RelOptInfo *rel, List *subpaths,
 				   Relids required_outer);
 extern MergeAppendPath *create_merge_append_path(PlannerInfo *root,
@@ -73,8 +73,10 @@ extern Path *create_functionscan_path(PlannerInfo *root, RelOptInfo *rel,
 						 Relids required_outer);
 extern Path *create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel,
 					   Relids required_outer);
-extern Path *create_ctescan_path(PlannerInfo *root, RelOptInfo *rel);
-extern Path *create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel);
+extern Path *create_ctescan_path(PlannerInfo *root, RelOptInfo *rel,
+					Relids required_outer);
+extern Path *create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel,
+						  Relids required_outer);
 extern ForeignPath *create_foreignscan_path(PlannerInfo *root, RelOptInfo *rel,
 						double rows, Cost startup_cost, Cost total_cost,
 						List *pathkeys,
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 5a9e677f94f..c395d4292c8 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -94,6 +94,8 @@ extern void add_base_rels_to_query(PlannerInfo *root, Node *jtnode);
 extern void build_base_rel_tlists(PlannerInfo *root, List *final_tlist);
 extern void add_vars_to_targetlist(PlannerInfo *root, List *vars,
 					   Relids where_needed, bool create_new_ph);
+extern void find_lateral_references(PlannerInfo *root);
+extern void create_lateral_join_info(PlannerInfo *root);
 extern List *deconstruct_jointree(PlannerInfo *root);
 extern void distribute_restrictinfo_to_rels(PlannerInfo *root,
 								RestrictInfo *restrictinfo);
diff --git a/src/include/optimizer/planner.h b/src/include/optimizer/planner.h
index af0c817a43d..35f16e8fb71 100644
--- a/src/include/optimizer/planner.h
+++ b/src/include/optimizer/planner.h
@@ -42,6 +42,8 @@ extern bool is_dummy_plan(Plan *plan);
 
 extern Expr *expression_planner(Expr *expr);
 
+extern Expr *preprocess_phv_expression(PlannerInfo *root, Expr *expr);
+
 extern bool plan_cluster_use_sort(Oid tableOid, Oid indexOid);
 
 #endif   /* PLANNER_H */
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 0856b457bfc..264d8966605 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -3167,16 +3167,15 @@ explain (costs off)
   select * from int8_tbl a,
     int8_tbl x left join lateral (select a.q1 from int4_tbl y) ss(z)
       on x.q2 = ss.z;
-                QUERY PLAN                
-------------------------------------------
- Nested Loop Left Join
-   Join Filter: (x.q2 = ($0))
-   ->  Nested Loop
-         ->  Seq Scan on int8_tbl a
-         ->  Materialize
-               ->  Seq Scan on int8_tbl x
-   ->  Seq Scan on int4_tbl y
-(7 rows)
+             QUERY PLAN             
+------------------------------------
+ Nested Loop
+   ->  Seq Scan on int8_tbl a
+   ->  Nested Loop Left Join
+         Join Filter: (x.q2 = ($0))
+         ->  Seq Scan on int8_tbl x
+         ->  Seq Scan on int4_tbl y
+(6 rows)
 
 select * from int8_tbl a,
   int8_tbl x left join lateral (select a.q1 from int4_tbl y) ss(z)
@@ -3336,6 +3335,109 @@ select * from
  4567890123456789 | -4567890123456789 |                  |                   | 4567890123456789 |                  |                  
 (10 rows)
 
+select x.* from
+  int8_tbl x left join (select q1,coalesce(q2,0) q2 from int8_tbl) y on x.q2 = y.q1,
+  lateral (select x.q1,y.q1,y.q2) v(xq1,yq1,yq2);
+        q1        |        q2         
+------------------+-------------------
+              123 |               456
+              123 |  4567890123456789
+              123 |  4567890123456789
+              123 |  4567890123456789
+ 4567890123456789 |               123
+ 4567890123456789 |               123
+ 4567890123456789 |  4567890123456789
+ 4567890123456789 |  4567890123456789
+ 4567890123456789 |  4567890123456789
+ 4567890123456789 | -4567890123456789
+(10 rows)
+
+select v.* from
+  (int8_tbl x left join (select q1,coalesce(q2,0) q2 from int8_tbl) y on x.q2 = y.q1)
+  left join int4_tbl z on z.f1 = x.q2,
+  lateral (select x.q1,y.q1 union all select x.q2,y.q2) v(vx,vy);
+        vx         |        vy         
+-------------------+-------------------
+               123 |                  
+               456 |                  
+               123 |  4567890123456789
+  4567890123456789 | -4567890123456789
+               123 |  4567890123456789
+  4567890123456789 |  4567890123456789
+               123 |  4567890123456789
+  4567890123456789 |               123
+  4567890123456789 |               123
+               123 |  4567890123456789
+  4567890123456789 |               123
+               123 |               456
+  4567890123456789 |  4567890123456789
+  4567890123456789 | -4567890123456789
+  4567890123456789 |  4567890123456789
+  4567890123456789 |  4567890123456789
+  4567890123456789 |  4567890123456789
+  4567890123456789 |               123
+  4567890123456789 |                  
+ -4567890123456789 |                  
+(20 rows)
+
+select v.* from
+  (int8_tbl x left join (select q1,(select coalesce(q2,0)) q2 from int8_tbl) y on x.q2 = y.q1)
+  left join int4_tbl z on z.f1 = x.q2,
+  lateral (select x.q1,y.q1 union all select x.q2,y.q2) v(vx,vy);
+        vx         |        vy         
+-------------------+-------------------
+               123 |                  
+               456 |                  
+               123 |  4567890123456789
+  4567890123456789 | -4567890123456789
+               123 |  4567890123456789
+  4567890123456789 |  4567890123456789
+               123 |  4567890123456789
+  4567890123456789 |               123
+  4567890123456789 |               123
+               123 |  4567890123456789
+  4567890123456789 |               123
+               123 |               456
+  4567890123456789 |  4567890123456789
+  4567890123456789 | -4567890123456789
+  4567890123456789 |  4567890123456789
+  4567890123456789 |  4567890123456789
+  4567890123456789 |  4567890123456789
+  4567890123456789 |               123
+  4567890123456789 |                  
+ -4567890123456789 |                  
+(20 rows)
+
+create temp table dual();
+insert into dual default values;
+select v.* from
+  (int8_tbl x left join (select q1,(select coalesce(q2,0)) q2 from int8_tbl) y on x.q2 = y.q1)
+  left join int4_tbl z on z.f1 = x.q2,
+  lateral (select x.q1,y.q1 from dual union all select x.q2,y.q2 from dual) v(vx,vy);
+        vx         |        vy         
+-------------------+-------------------
+               123 |                  
+               456 |                  
+               123 |  4567890123456789
+  4567890123456789 |               123
+               123 |  4567890123456789
+  4567890123456789 |  4567890123456789
+               123 |  4567890123456789
+  4567890123456789 | -4567890123456789
+  4567890123456789 |               123
+               123 |               456
+  4567890123456789 |               123
+               123 |  4567890123456789
+  4567890123456789 |  4567890123456789
+  4567890123456789 |               123
+  4567890123456789 |  4567890123456789
+  4567890123456789 |  4567890123456789
+  4567890123456789 |  4567890123456789
+  4567890123456789 | -4567890123456789
+  4567890123456789 |                  
+ -4567890123456789 |                  
+(20 rows)
+
 -- test some error cases where LATERAL should have been used but wasn't
 select f1,g from int4_tbl a, generate_series(0, f1) g;
 ERROR:  column "f1" does not exist
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 3c8ed5027ef..24553045da1 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -916,6 +916,23 @@ select * from
 select * from
   int8_tbl x left join (select q1,coalesce(q2,0) q2 from int8_tbl) y on x.q2 = y.q1,
   lateral (select x.q1,y.q1,y.q2) v(xq1,yq1,yq2);
+select x.* from
+  int8_tbl x left join (select q1,coalesce(q2,0) q2 from int8_tbl) y on x.q2 = y.q1,
+  lateral (select x.q1,y.q1,y.q2) v(xq1,yq1,yq2);
+select v.* from
+  (int8_tbl x left join (select q1,coalesce(q2,0) q2 from int8_tbl) y on x.q2 = y.q1)
+  left join int4_tbl z on z.f1 = x.q2,
+  lateral (select x.q1,y.q1 union all select x.q2,y.q2) v(vx,vy);
+select v.* from
+  (int8_tbl x left join (select q1,(select coalesce(q2,0)) q2 from int8_tbl) y on x.q2 = y.q1)
+  left join int4_tbl z on z.f1 = x.q2,
+  lateral (select x.q1,y.q1 union all select x.q2,y.q2) v(vx,vy);
+create temp table dual();
+insert into dual default values;
+select v.* from
+  (int8_tbl x left join (select q1,(select coalesce(q2,0)) q2 from int8_tbl) y on x.q2 = y.q1)
+  left join int4_tbl z on z.f1 = x.q2,
+  lateral (select x.q1,y.q1 from dual union all select x.q2,y.q2 from dual) v(vx,vy);
 
 -- test some error cases where LATERAL should have been used but wasn't
 select f1,g from int4_tbl a, generate_series(0, f1) g;