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.

6 files changed, 209 insertions, 95 deletions

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));
 }