Simplify the planner's join clause management by storing join clauses

of a relation in a flat 'joininfo' list.  The former arrangement grouped
the join clauses according to the set of unjoined relids used in each;
however, profiling on test cases involving lots of joins proves that
that data structure is a net loss.  It takes more time to group the
join clauses together than is saved by avoiding duplicate tests later.
It doesn't help any that there are usually not more than one or two
clauses per group ...

5 files changed, 124 insertions, 198 deletions

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index f17d1af5a63..4b09f03e6e7 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.132 2005/06/06 04:13:35 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.133 2005/06/09 04:18:59 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -1048,14 +1048,10 @@ debug_print_rel(PlannerInfo *root, RelOptInfo *rel)
 		printf("\n");
 	}
 
-	foreach(l, rel->joininfo)
+	if (rel->joininfo)
 	{
-		JoinInfo   *j = (JoinInfo *) lfirst(l);
-
-		printf("\tjoininfo (");
-		print_relids(j->unjoined_relids);
-		printf("): ");
-		print_restrictclauses(root, j->jinfo_restrictinfo);
+		printf("\tjoininfo: ");
+		print_restrictclauses(root, rel->joininfo);
 		printf("\n");
 	}
 
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 0d5a4e99b36..1b488d191e8 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -9,7 +9,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.181 2005/06/05 22:32:55 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.182 2005/06/09 04:18:59 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -71,8 +71,6 @@ static Oid indexable_operator(Expr *clause, Oid opclass,
 static bool pred_test_recurse(Node *clause, Node *predicate);
 static bool pred_test_simple_clause(Expr *predicate, Node *clause);
 static Relids indexable_outerrelids(RelOptInfo *rel);
-static bool list_matches_any_index(List *clauses, RelOptInfo *rel,
-								   Relids outer_relids);
 static bool matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel,
 							  Relids outer_relids);
 static List *find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
@@ -908,7 +906,7 @@ pred_test(List *predicate_list, List *restrictinfo_list)
 	 * classes over equi-joined attributes (i.e., if it recognized that a
 	 * qualification such as "where a.b=c.d and a.b=5" could make use of
 	 * an index on c.d), then we could use that equivalence class info
-	 * here with joininfo_list to do more complete tests for the usability
+	 * here with joininfo lists to do more complete tests for the usability
 	 * of a partial index.	For now, the test only uses restriction
 	 * clauses (those in restrictinfo_list). --Nels, Dec '92
 	 *
@@ -1550,90 +1548,72 @@ indexable_outerrelids(RelOptInfo *rel)
 	Relids		outer_relids = NULL;
 	ListCell   *l;
 
+	/*
+	 * Examine each joinclause in the joininfo list to see if it matches any
+	 * key of any index.  If so, add the clause's other rels to the result.
+	 * (Note: we consider only actual participants, not extraneous rels
+	 * possibly mentioned in required_relids.)
+	 */
 	foreach(l, rel->joininfo)
 	{
-		JoinInfo   *joininfo = (JoinInfo *) lfirst(l);
+		RestrictInfo *joininfo = (RestrictInfo *) lfirst(l);
+		Relids	other_rels;
 
-		/*
-		 * Examine each joinclause in the JoinInfo node's list to see if
-		 * it matches any key of any index.  If so, add the JoinInfo's
-		 * otherrels to the result.  We can skip examining other
-		 * joinclauses in the same list as soon as we find a match, since
-		 * by definition they all have the same otherrels.
-		 */
-		if (list_matches_any_index(joininfo->jinfo_restrictinfo,
-								   rel,
-								   joininfo->unjoined_relids))
-			outer_relids = bms_add_members(outer_relids,
-										   joininfo->unjoined_relids);
+		other_rels = bms_difference(joininfo->clause_relids, rel->relids);
+		if (matches_any_index(joininfo, rel, other_rels))
+			outer_relids = bms_join(outer_relids, other_rels);
+		else
+			bms_free(other_rels);
 	}
 
 	return outer_relids;
 }
 
 /*
- * list_matches_any_index
- *	  Workhorse for indexable_outerrelids: given a list of RestrictInfos,
- *	  see if any of them match any index of the given rel.
- *
- * We define it like this so that we can recurse into OR subclauses.
+ * matches_any_index
+ *	  Workhorse for indexable_outerrelids: see if a joinclause can be
+ *	  matched to any index of the given rel.
  */
 static bool
-list_matches_any_index(List *clauses, RelOptInfo *rel, Relids outer_relids)
+matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel, Relids outer_relids)
 {
 	ListCell   *l;
 
-	foreach(l, clauses)
-	{
-		RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
-		ListCell *j;
-
-		Assert(IsA(rinfo, RestrictInfo));
+	Assert(IsA(rinfo, RestrictInfo));
 
-		/* RestrictInfos that aren't ORs are easy */
-		if (!restriction_is_or_clause(rinfo))
-		{
-			if (matches_any_index(rinfo, rel, outer_relids))
-				return true;
-			continue;
-		}
-
-		foreach(j, ((BoolExpr *) rinfo->orclause)->args)
+	if (restriction_is_or_clause(rinfo))
+	{
+		foreach(l, ((BoolExpr *) rinfo->orclause)->args)
 		{
-			Node   *orarg = (Node *) lfirst(j);
+			Node   *orarg = (Node *) lfirst(l);
 
 			/* OR arguments should be ANDs or sub-RestrictInfos */
 			if (and_clause(orarg))
 			{
-				List   *andargs = ((BoolExpr *) orarg)->args;
+				ListCell   *j;
 
 				/* Recurse to examine AND items and sub-ORs */
-				if (list_matches_any_index(andargs, rel, outer_relids))
-					return true;
+				foreach(j, ((BoolExpr *) orarg)->args)
+				{
+					RestrictInfo *arinfo = (RestrictInfo *) lfirst(j);
+
+					if (matches_any_index(arinfo, rel, outer_relids))
+						return true;
+				}
 			}
 			else
 			{
+				/* Recurse to examine simple clause */
 				Assert(IsA(orarg, RestrictInfo));
 				Assert(!restriction_is_or_clause((RestrictInfo *) orarg));
 				if (matches_any_index((RestrictInfo *) orarg, rel,
-									   outer_relids))
+									  outer_relids))
 					return true;
 			}
 		}
-	}
-
-	return false;
-}
 
-/*
- * matches_any_index
- *	  Workhorse for indexable_outerrelids: see if a simple joinclause can be
- *	  matched to any index of the given rel.
- */
-static bool
-matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel, Relids outer_relids)
-{
-	ListCell   *l;
+		return false;
+	}
 
 	/* Normal case for a simple restriction clause */
 	foreach(l, rel->indexlist)
@@ -1833,7 +1813,7 @@ find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
 {
 	List	   *clause_list = NIL;
 	bool		jfound = false;
-	int			numsources;
+	Relids		join_relids;
 	ListCell   *l;
 
 	/*
@@ -1854,46 +1834,33 @@ find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
 		clause_list = lappend(clause_list, rinfo);
 	}
 
-	/* found anything in base restrict list? */
-	numsources = (clause_list != NIL) ? 1 : 0;
-
 	/* Look for joinclauses that are usable with given outer_relids */
+	join_relids = bms_union(rel->relids, outer_relids);
+
 	foreach(l, rel->joininfo)
 	{
-		JoinInfo   *joininfo = (JoinInfo *) lfirst(l);
-		bool		jfoundhere = false;
-		ListCell   *j;
+		RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 
-		if (!bms_is_subset(joininfo->unjoined_relids, outer_relids))
+		/* Can't use pushed-down clauses in outer join */
+		if (isouterjoin && rinfo->is_pushed_down)
+			continue;
+		if (!bms_is_subset(rinfo->required_relids, join_relids))
 			continue;
 
-		foreach(j, joininfo->jinfo_restrictinfo)
-		{
-			RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
-
-			/* Can't use pushed-down clauses in outer join */
-			if (isouterjoin && rinfo->is_pushed_down)
-				continue;
-
-			clause_list = lappend(clause_list, rinfo);
-			if (!jfoundhere)
-			{
-				jfoundhere = true;
-				jfound = true;
-				numsources++;
-			}
-		}
+		clause_list = lappend(clause_list, rinfo);
+		jfound = true;
 	}
 
+	bms_free(join_relids);
+
 	/* if no join clause was matched then forget it, per comments above */
 	if (!jfound)
 		return NIL;
 
 	/*
-	 * If we found clauses in more than one list, we may now have
-	 * clauses that are known redundant.  Get rid of 'em.
+	 * We may now have clauses that are known redundant.  Get rid of 'em.
 	 */
-	if (numsources > 1)
+	if (list_length(clause_list) > 1)
 	{
 		clause_list = remove_redundant_join_clauses(root,
 													clause_list,
@@ -2304,7 +2271,8 @@ expand_indexqual_conditions(IndexOptInfo *index, List *clausegroups)
 				{
 					resultquals = lappend(resultquals,
 										  make_restrictinfo(boolqual,
-															true, true));
+															true, true,
+															NULL));
 					continue;
 				}
 			}
@@ -2553,7 +2521,7 @@ prefix_quals(Node *leftop, Oid opclass,
 			elog(ERROR, "no = operator for opclass %u", opclass);
 		expr = make_opclause(oproid, BOOLOID, false,
 							 (Expr *) leftop, (Expr *) prefix_const);
-		result = list_make1(make_restrictinfo(expr, true, true));
+		result = list_make1(make_restrictinfo(expr, true, true, NULL));
 		return result;
 	}
 
@@ -2568,7 +2536,7 @@ prefix_quals(Node *leftop, Oid opclass,
 		elog(ERROR, "no >= operator for opclass %u", opclass);
 	expr = make_opclause(oproid, BOOLOID, false,
 						 (Expr *) leftop, (Expr *) prefix_const);
-	result = list_make1(make_restrictinfo(expr, true, true));
+	result = list_make1(make_restrictinfo(expr, true, true, NULL));
 
 	/*-------
 	 * If we can create a string larger than the prefix, we can say
@@ -2584,7 +2552,7 @@ prefix_quals(Node *leftop, Oid opclass,
 			elog(ERROR, "no < operator for opclass %u", opclass);
 		expr = make_opclause(oproid, BOOLOID, false,
 							 (Expr *) leftop, (Expr *) greaterstr);
-		result = lappend(result, make_restrictinfo(expr, true, true));
+		result = lappend(result, make_restrictinfo(expr, true, true, NULL));
 	}
 
 	return result;
@@ -2655,7 +2623,7 @@ network_prefix_quals(Node *leftop, Oid expr_op, Oid opclass, Datum rightop)
 						 (Expr *) leftop,
 						 (Expr *) makeConst(datatype, -1, opr1right,
 											false, false));
-	result = list_make1(make_restrictinfo(expr, true, true));
+	result = list_make1(make_restrictinfo(expr, true, true, NULL));
 
 	/* create clause "key <= network_scan_last( rightop )" */
 
@@ -2670,7 +2638,7 @@ network_prefix_quals(Node *leftop, Oid expr_op, Oid opclass, Datum rightop)
 						 (Expr *) leftop,
 						 (Expr *) makeConst(datatype, -1, opr2right,
 											false, false));
-	result = lappend(result, make_restrictinfo(expr, true, true));
+	result = lappend(result, make_restrictinfo(expr, true, true, NULL));
 
 	return result;
 }
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index a1681ae994f..f51e492eca1 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -8,12 +8,13 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/path/joinrels.c,v 1.73 2005/06/05 22:32:55 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/path/joinrels.c,v 1.74 2005/06/09 04:18:59 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
 #include "postgres.h"
 
+#include "optimizer/joininfo.h"
 #include "optimizer/pathnode.h"
 #include "optimizer/paths.h"
 
@@ -169,30 +170,20 @@ make_rels_by_joins(PlannerInfo *root, int level, List **joinrels)
 
 				if (!bms_overlap(old_rel->relids, new_rel->relids))
 				{
-					ListCell   *i;
-
 					/*
 					 * 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.
 					 */
-					foreach(i, old_rel->joininfo)
+					if (have_relevant_joinclause(old_rel, new_rel))
 					{
-						JoinInfo   *joininfo = (JoinInfo *) lfirst(i);
-
-						if (bms_is_subset(joininfo->unjoined_relids,
-										  new_rel->relids))
-						{
-							RelOptInfo *jrel;
-
-							jrel = make_join_rel(root, old_rel, new_rel,
-												 JOIN_INNER);
-							/* Avoid making duplicate entries ... */
-							if (jrel && !list_member_ptr(result_rels, jrel))
-								result_rels = lcons(jrel, result_rels);
-							break;		/* need not consider more
-										 * joininfos */
-						}
+						RelOptInfo *jrel;
+
+						jrel = make_join_rel(root, old_rel, new_rel,
+											 JOIN_INNER);
+						/* Avoid making duplicate entries ... */
+						if (jrel && !list_member_ptr(result_rels, jrel))
+							result_rels = lcons(jrel, result_rels);
 					}
 				}
 			}
@@ -269,7 +260,7 @@ 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 nodes (i.e., relations
+ *	  that are mentioned within old_rel's joininfo list (i.e., relations
  *	  that participate in join clauses that 'old_rel' also participates in).
  *	  The join rel nodes are returned in a list.
  *
@@ -278,10 +269,7 @@ make_rels_by_joins(PlannerInfo *root, int level, List **joinrels)
  * rels to be considered for joining
  *
  * Currently, this is only used with initial rels in other_rels, but it
- * will work for joining to joinrels too, if the caller ensures there is no
- * membership overlap between old_rel and the rels in other_rels.  (We need
- * no extra test for overlap for initial rels, since the is_subset test can
- * only succeed when other_rel is not already part of old_rel.)
+ * will work for joining to joinrels too.
  */
 static List *
 make_rels_by_clause_joins(PlannerInfo *root,
@@ -289,31 +277,20 @@ make_rels_by_clause_joins(PlannerInfo *root,
 						  ListCell *other_rels)
 {
 	List	   *result = NIL;
-	ListCell   *i,
-			   *j;
+	ListCell   *l;
 
-	foreach(i, old_rel->joininfo)
+	for_each_cell(l, other_rels)
 	{
-		JoinInfo   *joininfo = (JoinInfo *) lfirst(i);
-		Relids		unjoined_relids = joininfo->unjoined_relids;
+		RelOptInfo *other_rel = (RelOptInfo *) lfirst(l);
 
-		for_each_cell(j, other_rels)
+		if (!bms_overlap(old_rel->relids, other_rel->relids) &&
+			have_relevant_joinclause(old_rel, other_rel))
 		{
-			RelOptInfo *other_rel = (RelOptInfo *) lfirst(j);
-
-			if (bms_is_subset(unjoined_relids, other_rel->relids))
-			{
-				RelOptInfo *jrel;
-
-				jrel = make_join_rel(root, old_rel, other_rel, JOIN_INNER);
+			RelOptInfo *jrel;
 
-				/*
-				 * Avoid entering same joinrel into our output list more
-				 * than once.
-				 */
-				if (jrel && !list_member_ptr(result, jrel))
-					result = lcons(jrel, result);
-			}
+			jrel = make_join_rel(root, old_rel, other_rel, JOIN_INNER);
+			if (jrel)
+				result = lcons(jrel, result);
 		}
 	}
 
diff --git a/src/backend/optimizer/path/orindxpath.c b/src/backend/optimizer/path/orindxpath.c
index 0e2eefc868c..7eadd220b94 100644
--- a/src/backend/optimizer/path/orindxpath.c
+++ b/src/backend/optimizer/path/orindxpath.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/path/orindxpath.c,v 1.71 2005/06/05 22:32:55 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/path/orindxpath.c,v 1.72 2005/06/09 04:18:59 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -96,43 +96,37 @@ create_or_index_quals(PlannerInfo *root, RelOptInfo *rel)
 	 */
 	foreach(i, rel->joininfo)
 	{
-		JoinInfo   *joininfo = (JoinInfo *) lfirst(i);
-		ListCell   *j;
+		RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
 
-		foreach(j, joininfo->jinfo_restrictinfo)
+		if (restriction_is_or_clause(rinfo) &&
+			rinfo->valid_everywhere)
 		{
-			RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
+			/*
+			 * Use the generate_bitmap_or_paths() machinery to estimate
+			 * the value of each OR clause.  We can use regular
+			 * restriction clauses along with the OR clause contents to
+			 * generate indexquals.  We pass outer_relids = NULL so that
+			 * sub-clauses that are actually joins will be ignored.
+			 */
+			List *orpaths;
+			ListCell *k;
 
-			if (restriction_is_or_clause(rinfo) &&
-				rinfo->valid_everywhere)
-			{
-				/*
-				 * Use the generate_bitmap_or_paths() machinery to estimate
-				 * the value of each OR clause.  We can use regular
-				 * restriction clauses along with the OR clause contents to
-				 * generate indexquals.  We pass outer_relids = NULL so that
-				 * sub-clauses that are actually joins will be ignored.
-				 */
-				List *orpaths;
-				ListCell *k;
+			orpaths = generate_bitmap_or_paths(root, rel,
+											   list_make1(rinfo),
+											   rel->baserestrictinfo,
+											   false, NULL);
 
-				orpaths = generate_bitmap_or_paths(root, rel,
-												   list_make1(rinfo),
-												   rel->baserestrictinfo,
-												   false, NULL);
+			/* Locate the cheapest OR path */
+			foreach(k, orpaths)
+			{
+				BitmapOrPath   *path = (BitmapOrPath *) lfirst(k);
 
-				/* Locate the cheapest OR path */
-				foreach(k, orpaths)
+				Assert(IsA(path, BitmapOrPath));
+				if (bestpath == NULL ||
+					path->path.total_cost < bestpath->path.total_cost)
 				{
-					BitmapOrPath   *path = (BitmapOrPath *) lfirst(k);
-
-					Assert(IsA(path, BitmapOrPath));
-					if (bestpath == NULL ||
-						path->path.total_cost < bestpath->path.total_cost)
-					{
-						bestpath = path;
-						bestrinfo = rinfo;
-					}
+					bestpath = path;
+					bestrinfo = rinfo;
 				}
 			}
 		}
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 2994421e5b7..52075fbf465 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -11,7 +11,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/path/pathkeys.c,v 1.67 2005/06/05 22:32:55 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/path/pathkeys.c,v 1.68 2005/06/09 04:18:59 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -1157,11 +1157,11 @@ make_pathkeys_for_mergeclauses(PlannerInfo *root,
 /*
  * pathkeys_useful_for_merging
  *		Count the number of pathkeys that may be useful for mergejoins
- *		above the given relation (by looking at its joininfo lists).
+ *		above the given relation (by looking at its joininfo list).
  *
  * We consider a pathkey potentially useful if it corresponds to the merge
  * ordering of either side of any joinclause for the rel.  This might be
- * overoptimistic, since joinclauses that appear in different join lists
+ * overoptimistic, since joinclauses that require different other relations
  * might never be usable at the same time, but trying to be exact is likely
  * to be more trouble than it's worth.
  */
@@ -1179,31 +1179,22 @@ pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
 
 		foreach(j, rel->joininfo)
 		{
-			JoinInfo   *joininfo = (JoinInfo *) lfirst(j);
-			ListCell   *k;
-
-			foreach(k, joininfo->jinfo_restrictinfo)
-			{
-				RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(k);
-
-				if (restrictinfo->mergejoinoperator == InvalidOid)
-					continue;
-				cache_mergeclause_pathkeys(root, restrictinfo);
+			RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
 
-				/*
-				 * We can compare canonical pathkey sublists by simple
-				 * pointer equality; see compare_pathkeys.
-				 */
-				if (pathkey == restrictinfo->left_pathkey ||
-					pathkey == restrictinfo->right_pathkey)
-				{
-					matched = true;
-					break;
-				}
-			}
+			if (restrictinfo->mergejoinoperator == InvalidOid)
+				continue;
+			cache_mergeclause_pathkeys(root, restrictinfo);
 
-			if (matched)
+			/*
+			 * We can compare canonical pathkey sublists by simple
+			 * pointer equality; see compare_pathkeys.
+			 */
+			if (pathkey == restrictinfo->left_pathkey ||
+				pathkey == restrictinfo->right_pathkey)
+			{
+				matched = true;
 				break;
+			}
 		}
 
 		/*