1 files changed, 112 insertions, 50 deletions

diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 04ad96f802e..c1026a25768 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/path/joinrels.c,v 1.76.2.1 2005/11/22 18:23:10 momjian Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/path/joinrels.c,v 1.76.2.2 2007/02/16 00:14:16 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -25,7 +25,7 @@ static List *make_rels_by_clause_joins(PlannerInfo *root,
 static List *make_rels_by_clauseless_joins(PlannerInfo *root,
 							  RelOptInfo *old_rel,
 							  ListCell *other_rels);
-static bool is_inside_IN(PlannerInfo *root, RelOptInfo *rel);
+static bool has_join_restriction(PlannerInfo *root, RelOptInfo *rel);
 
 
 /*
@@ -72,7 +72,7 @@ make_rels_by_joins(PlannerInfo *root, int level, List **joinrels)
 			other_rels = list_head(joinrels[1]);		/* consider all initial
 														 * rels */
 
-		if (old_rel->joininfo != NIL)
+		if (old_rel->joininfo != NIL || has_join_restriction(root, old_rel))
 		{
 			/*
 			 * Note that if all available join clauses for this rel require
@@ -80,30 +80,19 @@ make_rels_by_joins(PlannerInfo *root, int level, List **joinrels)
 			 * it here.  In most cases that's OK; it'll be considered by
 			 * "bushy plan" join code in a higher-level pass where we have
 			 * those other rels collected into a join rel.
+			 *
+			 * See also the last-ditch case below.
 			 */
 			new_rels = make_rels_by_clause_joins(root,
 												 old_rel,
 												 other_rels);
-
-			/*
-			 * An exception occurs when there is a clauseless join inside an
-			 * IN (sub-SELECT) construct.  Here, the members of the subselect
-			 * all have join clauses (against the stuff outside the IN), but
-			 * they *must* be joined to each other before we can make use of
-			 * those join clauses.	So do the clauseless join bit.
-			 *
-			 * See also the last-ditch case below.
-			 */
-			if (new_rels == NIL && is_inside_IN(root, old_rel))
-				new_rels = make_rels_by_clauseless_joins(root,
-														 old_rel,
-														 other_rels);
 		}
 		else
 		{
 			/*
 			 * Oops, we have a relation that is not joined to any other
-			 * relation.  Cartesian product time.
+			 * relation, either directly or by join-order restrictions.
+			 * Cartesian product time.
 			 */
 			new_rels = make_rels_by_clauseless_joins(root,
 													 old_rel,
@@ -126,8 +115,8 @@ make_rels_by_joins(PlannerInfo *root, int level, List **joinrels)
 	 * joined to relations of level-k initial rels, for 2 <= k <= level-2.
 	 *
 	 * We only consider bushy-plan joins for pairs of rels where there is a
-	 * suitable join clause, in order to avoid unreasonable growth of planning
-	 * time.
+	 * suitable join clause (or join order restriction), in order to avoid
+	 * unreasonable growth of planning time.
 	 */
 	for (k = 2;; k++)
 	{
@@ -146,8 +135,14 @@ make_rels_by_joins(PlannerInfo *root, int level, List **joinrels)
 			ListCell   *other_rels;
 			ListCell   *r2;
 
-			if (old_rel->joininfo == NIL)
-				continue;		/* we ignore clauseless joins here */
+			/*
+			 * We can ignore clauseless joins here, *except* when they
+			 * participate in join-order restrictions --- then we might have
+			 * to force a bushy join plan.
+			 */
+			if (old_rel->joininfo == NIL &&
+				!has_join_restriction(root, old_rel))
+				continue;
 
 			if (k == other_level)
 				other_rels = lnext(r);	/* only consider remaining rels */
@@ -163,9 +158,10 @@ make_rels_by_joins(PlannerInfo *root, int level, List **joinrels)
 					/*
 					 * OK, we can build a rel of the right level from this
 					 * pair of rels.  Do so if there is at least one usable
-					 * join clause.
+					 * join clause or a relevant join restriction.
 					 */
-					if (have_relevant_joinclause(old_rel, new_rel))
+					if (have_relevant_joinclause(old_rel, new_rel) ||
+						have_join_order_restriction(root, old_rel, new_rel))
 					{
 						RelOptInfo *jrel;
 
@@ -245,8 +241,8 @@ make_rels_by_joins(PlannerInfo *root, int level, List **joinrels)
 /*
  * make_rels_by_clause_joins
  *	  Build joins between the given relation 'old_rel' and other relations
- *	  that are mentioned within old_rel's joininfo list (i.e., relations
- *	  that participate in join clauses that 'old_rel' also participates in).
+ *	  that participate in join clauses that 'old_rel' also participates in
+ *	  (or participate in join-order restrictions with it).
  *	  The join rel nodes are returned in a list.
  *
  * 'old_rel' is the relation entry for the relation to be joined
@@ -269,7 +265,8 @@ make_rels_by_clause_joins(PlannerInfo *root,
 		RelOptInfo *other_rel = (RelOptInfo *) lfirst(l);
 
 		if (!bms_overlap(old_rel->relids, other_rel->relids) &&
-			have_relevant_joinclause(old_rel, other_rel))
+			(have_relevant_joinclause(old_rel, other_rel) ||
+			 have_join_order_restriction(root, old_rel, other_rel)))
 		{
 			RelOptInfo *jrel;
 
@@ -328,29 +325,6 @@ make_rels_by_clauseless_joins(PlannerInfo *root,
 
 
 /*
- * is_inside_IN
- *		Detect whether the specified relation is inside an IN (sub-SELECT).
- *
- * Note that we are actually only interested in rels that have been pulled up
- * out of an IN, so the routine name is a slight misnomer.
- */
-static bool
-is_inside_IN(PlannerInfo *root, RelOptInfo *rel)
-{
-	ListCell   *l;
-
-	foreach(l, root->in_info_list)
-	{
-		InClauseInfo *ininfo = (InClauseInfo *) lfirst(l);
-
-		if (bms_is_subset(rel->relids, ininfo->righthand))
-			return true;
-	}
-	return false;
-}
-
-
-/*
  * make_jointree_rel
  *		Find or build a RelOptInfo join rel representing a specific
  *		jointree item.	For JoinExprs, we only consider the construction
@@ -603,3 +577,91 @@ make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
 
 	return joinrel;
 }
+
+
+/*
+ * have_join_order_restriction
+ *		Detect whether the two relations should be joined to satisfy
+ *		a join-order restriction arising from IN clauses.
+ *
+ * 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 these tests because there are degenerate cases where
+ * a clauseless join must be performed to satisfy join-order restrictions.
+ */
+bool
+have_join_order_restriction(PlannerInfo *root,
+							RelOptInfo *rel1, RelOptInfo *rel2)
+{
+	ListCell   *l;
+
+	/*
+	 * It's possible that the rels correspond to the left and right sides
+	 * of a degenerate IN-clause; in which case we should force the join
+	 * to occur.
+	 *
+	 * Also, the two rels could represent a clauseless join that has to be
+	 * completed to build up the LHS or RHS of an IN-clause.
+	 */
+	foreach(l, root->in_info_list)
+	{
+		InClauseInfo *ininfo = (InClauseInfo *) lfirst(l);
+
+		/* Can we perform the IN with these rels? */
+		if (bms_is_subset(ininfo->lefthand, rel1->relids) &&
+			bms_is_subset(ininfo->righthand, rel2->relids))
+			return true;
+		if (bms_is_subset(ininfo->lefthand, rel2->relids) &&
+			bms_is_subset(ininfo->righthand, rel1->relids))
+			return true;
+
+		/*
+		 * Might we need to join these rels to complete the RHS?  It's
+		 * probably overkill to test "overlap", since we never join part of an
+		 * IN's RHS to anything else, but may as well keep the coding similar
+		 * to the OJ case.
+		 */
+		if (bms_overlap(ininfo->righthand, rel1->relids) &&
+			bms_overlap(ininfo->righthand, rel2->relids))
+			return true;
+
+		/* Likewise for the LHS. */
+		if (bms_overlap(ininfo->lefthand, rel1->relids) &&
+			bms_overlap(ininfo->lefthand, rel2->relids))
+			return true;
+	}
+
+	return false;
+}
+
+
+/*
+ * has_join_restriction
+ *		Detect whether the specified relation has join-order restrictions
+ *		due to being inside an IN (sub-SELECT).
+ *
+ * Essentially, this tests whether have_join_order_restriction() could
+ * succeed with this rel and some other one.
+ */
+static bool
+has_join_restriction(PlannerInfo *root, RelOptInfo *rel)
+{
+	ListCell   *l;
+
+	foreach(l, root->in_info_list)
+	{
+		InClauseInfo *ininfo = (InClauseInfo *) lfirst(l);
+
+		/* ignore if IN is already contained in rel */
+		if (bms_is_subset(ininfo->lefthand, rel->relids) &&
+			bms_is_subset(ininfo->righthand, rel->relids))
+			continue;
+
+		/* restricted if it overlaps LHS or RHS, but doesn't contain IN */
+		if (bms_overlap(ininfo->lefthand, rel->relids) ||
+			bms_overlap(ininfo->righthand, rel->relids))
+			return true;
+	}
+
+	return false;
+}