5 files changed, 132 insertions, 0 deletions
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index b2cc9f07f56..9f0212fad23 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -334,6 +334,7 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
 	bool		must_be_leftjoin;
 	bool		lateral_fwd;
 	bool		lateral_rev;
+	Relids		join_lateral_rels;
 	ListCell   *l;
 
 	/*
@@ -569,6 +570,35 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
 		}
 	}
 
+	/*
+	 * LATERAL references could also cause problems later on if we accept this
+	 * join: if the join's minimum parameterization includes any rels that
+	 * would have to be on the inside of an outer join with this join rel,
+	 * then it's never going to be possible to build the complete query using
+	 * this join.  We should reject this join not only because it'll save
+	 * work, but because if we don't, the clauseless-join heuristics might
+	 * think that legality of this join means that some other join rel need
+	 * not be formed, and that could lead to failure to find any plan at all.
+	 * It seems best not to merge this check into the main loop above, because
+	 * it is concerned with SJs that are not otherwise relevant to this join.
+	 */
+	join_lateral_rels = min_join_parameterization(root, joinrelids);
+	if (join_lateral_rels)
+	{
+		foreach(l, root->join_info_list)
+		{
+			SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
+
+			if (bms_overlap(sjinfo->min_righthand, join_lateral_rels) &&
+				bms_overlap(sjinfo->min_lefthand, joinrelids))
+				return false;	/* will not be able to join to min_righthand */
+			if (sjinfo->jointype == JOIN_FULL &&
+				bms_overlap(sjinfo->min_lefthand, join_lateral_rels) &&
+				bms_overlap(sjinfo->min_righthand, joinrelids))
+				return false;	/* will not be able to join to min_lefthand */
+		}
+	}
+
 	/* Otherwise, it's a valid join */
 	*sjinfo_p = match_sjinfo;
 	*reversed_p = reversed;
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 996b7fe5136..8cc7bd771b3 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -500,6 +500,47 @@ build_join_rel(PlannerInfo *root,
 }
 
 /*
+ * min_join_parameterization
+ *
+ * Determine the minimum possible parameterization of a joinrel, that is, the
+ * set of other rels it contains LATERAL references to.  We save this value in
+ * the join's RelOptInfo.  This function is split out of build_join_rel()
+ * because join_is_legal() needs the value to check a prospective join.
+ */
+Relids
+min_join_parameterization(PlannerInfo *root, Relids joinrelids)
+{
+	Relids		result;
+	ListCell   *lc;
+
+	/* Easy if there are no lateral references */
+	if (root->lateral_info_list == NIL)
+		return NULL;
+
+	/*
+	 * Scan lateral_info_list to find all the lateral references occurring in
+	 * or below this join.
+	 */
+	result = NULL;
+	foreach(lc, root->lateral_info_list)
+	{
+		LateralJoinInfo *ljinfo = (LateralJoinInfo *) lfirst(lc);
+
+		if (bms_is_subset(ljinfo->lateral_rhs, joinrelids))
+			result = bms_add_members(result, ljinfo->lateral_lhs);
+	}
+
+	/* Remove any rels that are already included in the join */
+	result = bms_del_members(result, joinrelids);
+
+	/* Maintain invariant that result is exactly NULL if empty */
+	if (bms_is_empty(result))
+		result = NULL;
+
+	return result;
+}
+
+/*
  * build_joinrel_tlist
  *	  Builds a join relation's target list from an input relation.
  *	  (This is invoked twice to handle the two input relations.)
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index f28b4e2b063..eea75d0d1ec 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -147,6 +147,7 @@ extern RelOptInfo *build_join_rel(PlannerInfo *root,
 			   RelOptInfo *inner_rel,
 			   SpecialJoinInfo *sjinfo,
 			   List **restrictlist_ptr);
+extern Relids min_join_parameterization(PlannerInfo *root, Relids joinrelids);
 extern RelOptInfo *build_empty_join_rel(PlannerInfo *root);
 extern AppendRelInfo *find_childrel_appendrelinfo(PlannerInfo *root,
 							RelOptInfo *rel);
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index f8a9f3f264b..dba5d2dbab3 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -3580,6 +3580,47 @@ select * from
 (2 rows)
 
 --
+-- test for appropriate join order in the presence of lateral references
+--
+explain (verbose, costs off)
+select * from
+  text_tbl t1
+  left join int8_tbl i8
+  on i8.q2 = 123,
+  lateral (select i8.q1, t2.f1 from text_tbl t2 limit 1) as ss
+where t1.f1 = ss.f1;
+                    QUERY PLAN                    
+--------------------------------------------------
+ Nested Loop
+   Output: t1.f1, i8.q1, i8.q2, (i8.q1), t2.f1
+   Join Filter: (t1.f1 = t2.f1)
+   ->  Nested Loop Left Join
+         Output: t1.f1, i8.q1, i8.q2
+         ->  Seq Scan on public.text_tbl t1
+               Output: t1.f1
+         ->  Materialize
+               Output: i8.q1, i8.q2
+               ->  Seq Scan on public.int8_tbl i8
+                     Output: i8.q1, i8.q2
+                     Filter: (i8.q2 = 123)
+   ->  Limit
+         Output: (i8.q1), t2.f1
+         ->  Seq Scan on public.text_tbl t2
+               Output: i8.q1, t2.f1
+(16 rows)
+
+select * from
+  text_tbl t1
+  left join int8_tbl i8
+  on i8.q2 = 123,
+  lateral (select i8.q1, t2.f1 from text_tbl t2 limit 1) as ss
+where t1.f1 = ss.f1;
+  f1  |        q1        | q2  |        q1        |  f1  
+------+------------------+-----+------------------+------
+ doh! | 4567890123456789 | 123 | 4567890123456789 | doh!
+(1 row)
+
+--
 -- test ability to push constants through outer join clauses
 --
 explain (costs off)
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 528e1ef9708..fdd4e78cf28 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -1116,6 +1116,25 @@ select * from
   on i8.q1 = i4.f1;
 
 --
+-- test for appropriate join order in the presence of lateral references
+--
+
+explain (verbose, costs off)
+select * from
+  text_tbl t1
+  left join int8_tbl i8
+  on i8.q2 = 123,
+  lateral (select i8.q1, t2.f1 from text_tbl t2 limit 1) as ss
+where t1.f1 = ss.f1;
+
+select * from
+  text_tbl t1
+  left join int8_tbl i8
+  on i8.q2 = 123,
+  lateral (select i8.q1, t2.f1 from text_tbl t2 limit 1) as ss
+where t1.f1 = ss.f1;
+
+--
 -- test ability to push constants through outer join clauses
 --