Repair planning bugs caused by my misguided removal of restrictinfo link

fields in JoinPaths --- turns out that we do need that after all :-(.
Also, rearrange planner so that only one RelOptInfo is created for a
particular set of joined base relations, no matter how many different
subsets of relations it can be created from.  This saves memory and
processing time compared to the old method of making a bunch of RelOptInfos
and then removing the duplicates.  Clean up the jointree iteration logic;
not sure if it's better, but I sure find it more readable and plausible
now, particularly for the case of 'bushy plans'.

1 files changed, 187 insertions, 147 deletions

diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 371dd2b7b56..f8912a1a547 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.50 2000/02/06 03:27:32 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.51 2000/02/07 04:40:59 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -31,126 +31,108 @@ static Path *best_innerjoin(List *join_paths, List *outer_relid);
 static List *sort_inner_and_outer(RelOptInfo *joinrel,
 								  RelOptInfo *outerrel,
 								  RelOptInfo *innerrel,
+								  List *restrictlist,
 								  List *mergeclause_list);
 static List *match_unsorted_outer(RelOptInfo *joinrel, RelOptInfo *outerrel,
-								  RelOptInfo *innerrel, List *outerpath_list,
-								  Path *cheapest_inner, Path *best_innerjoin,
+								  RelOptInfo *innerrel, List *restrictlist,
+								  List *outerpath_list, Path *cheapest_inner,
+								  Path *best_innerjoin,
 								  List *mergeclause_list);
 static List *match_unsorted_inner(RelOptInfo *joinrel, RelOptInfo *outerrel,
-								  RelOptInfo *innerrel, List *innerpath_list,
+								  RelOptInfo *innerrel, List *restrictlist,
+								  List *innerpath_list,
 								  List *mergeclause_list);
 static List *hash_inner_and_outer(Query *root, RelOptInfo *joinrel,
-								  RelOptInfo *outerrel, RelOptInfo *innerrel);
+								  RelOptInfo *outerrel, RelOptInfo *innerrel,
+								  List *restrictlist);
 static Selectivity estimate_disbursion(Query *root, Var *var);
-static List *select_mergejoin_clauses(List *restrictinfo_list);
+static List *select_mergejoin_clauses(RelOptInfo *joinrel,
+									  RelOptInfo *outerrel,
+									  RelOptInfo *innerrel,
+									  List *restrictlist);
+
 
 /*
- * update_rels_pathlist_for_joins
- *	  Creates all possible ways to process joins for each of the join
- *	  relations in the list 'joinrels.'  Each unique path will be included
- *	  in the join relation's 'pathlist' field.
- *
- * 'joinrels' is the list of relation entries to be joined
+ * add_paths_to_joinrel
+ *	  Given a join relation and two component rels from which it can be made,
+ *	  consider all possible paths that use the two component rels as outer
+ *	  and inner rel respectively.  Add these paths to the join rel's pathlist
+ *	  if they survive comparison with other paths (and remove any existing
+ *	  paths that are dominated by these paths).
  *
- * Modifies the pathlist field of each joinrel node to contain
- * the unique join paths.
+ * Modifies the pathlist field of the joinrel node to contain the best
+ * paths found so far.
  */
 void
-update_rels_pathlist_for_joins(Query *root, List *joinrels)
+add_paths_to_joinrel(Query *root,
+					 RelOptInfo *joinrel,
+					 RelOptInfo *outerrel,
+					 RelOptInfo *innerrel,
+					 List *restrictlist)
 {
-	List	   *j;
-
-	foreach(j, joinrels)
-	{
-		RelOptInfo *joinrel = (RelOptInfo *) lfirst(j);
-		Relids		innerrelids;
-		Relids		outerrelids;
-		RelOptInfo *innerrel;
-		RelOptInfo *outerrel;
-		Path	   *bestinnerjoin;
-		List	   *pathlist;
-		List	   *mergeclause_list = NIL;
-
-		/*
-		 * On entry, joinrel->relids is a list of two sublists of relids,
-		 * namely the outer and inner member relids.  Extract these sublists
-		 * and change joinrel->relids to a flattened single list.
-		 * (Use listCopy so as not to damage the member lists...)
-		 */
-		outerrelids = lfirst(joinrel->relids);
-		innerrelids = lsecond(joinrel->relids);
-
-		joinrel->relids = nconc(listCopy(outerrelids),
-								listCopy(innerrelids));
-
-		/*
-		 * Get the corresponding RelOptInfos for the outer and inner sides.
-		 * Base relation id is an integer and join relation relid is a
-		 * list of integers.
-		 */
-		innerrel = (length(innerrelids) == 1) ?
-			get_base_rel(root, lfirsti(innerrelids)) :
-			get_join_rel(root, innerrelids);
-		outerrel = (length(outerrelids) == 1) ?
-			get_base_rel(root, lfirsti(outerrelids)) :
-			get_join_rel(root, outerrelids);
+	Path	   *bestinnerjoin;
+	List	   *mergeclause_list = NIL;
 
-		/*
-		 * Get the best inner join for match_unsorted_outer().
-		 */
-		bestinnerjoin = best_innerjoin(innerrel->innerjoin, outerrel->relids);
+	/*
+	 * Get the best inner join for match_unsorted_outer().
+	 */
+	bestinnerjoin = best_innerjoin(innerrel->innerjoin, outerrel->relids);
 
-		/*
-		 * Find potential mergejoin clauses.
-		 */
-		if (enable_mergejoin)
-			mergeclause_list = select_mergejoin_clauses(joinrel->restrictinfo);
+	/*
+	 * Find potential mergejoin clauses.
+	 */
+	if (enable_mergejoin)
+		mergeclause_list = select_mergejoin_clauses(joinrel,
+													outerrel,
+													innerrel,
+													restrictlist);
 
-		/*
-		 * 1. Consider mergejoin paths where both relations must be
-		 * explicitly sorted.
-		 */
-		pathlist = sort_inner_and_outer(joinrel, outerrel,
-										innerrel, mergeclause_list);
+	/*
+	 * 1. Consider mergejoin paths where both relations must be
+	 * explicitly sorted.
+	 */
+	add_pathlist(joinrel, sort_inner_and_outer(joinrel,
+											   outerrel,
+											   innerrel,
+											   restrictlist,
+											   mergeclause_list));
 
-		/*
-		 * 2. Consider paths where the outer relation need not be
-		 * explicitly sorted. This includes both nestloops and
-		 * mergejoins where the outer path is already ordered.
-		 */
-		pathlist = add_pathlist(joinrel, pathlist,
-								match_unsorted_outer(joinrel,
-													 outerrel,
-													 innerrel,
-													 outerrel->pathlist,
-													 innerrel->cheapestpath,
-													 bestinnerjoin,
-													 mergeclause_list));
+	/*
+	 * 2. Consider paths where the outer relation need not be
+	 * explicitly sorted. This includes both nestloops and
+	 * mergejoins where the outer path is already ordered.
+	 */
+	add_pathlist(joinrel, match_unsorted_outer(joinrel,
+											   outerrel,
+											   innerrel,
+											   restrictlist,
+											   outerrel->pathlist,
+											   innerrel->cheapestpath,
+											   bestinnerjoin,
+											   mergeclause_list));
 
-		/*
-		 * 3. Consider paths where the inner relation need not be
-		 * explicitly sorted.  This includes mergejoins only
-		 * (nestloops were already built in match_unsorted_outer).
-		 */
-		pathlist = add_pathlist(joinrel, pathlist,
-								match_unsorted_inner(joinrel, outerrel,
-													 innerrel,
-													 innerrel->pathlist,
-													 mergeclause_list));
+	/*
+	 * 3. Consider paths where the inner relation need not be
+	 * explicitly sorted.  This includes mergejoins only
+	 * (nestloops were already built in match_unsorted_outer).
+	 */
+	add_pathlist(joinrel, match_unsorted_inner(joinrel,
+											   outerrel,
+											   innerrel,
+											   restrictlist,
+											   innerrel->pathlist,
+											   mergeclause_list));
 
-		/*
-		 * 4. Consider paths where both outer and inner relations must be
-		 * hashed before being joined.
-		 */
-		if (enable_hashjoin)
-			pathlist = add_pathlist(joinrel, pathlist,
-									hash_inner_and_outer(root, joinrel,
-														 outerrel,
-														 innerrel));
-
-		/* Save the completed pathlist in the join rel */
-		joinrel->pathlist = pathlist;
-	}
+	/*
+	 * 4. Consider paths where both outer and inner relations must be
+	 * hashed before being joined.
+	 */
+	if (enable_hashjoin)
+		add_pathlist(joinrel, hash_inner_and_outer(root,
+												   joinrel,
+												   outerrel,
+												   innerrel,
+												   restrictlist));
 }
 
 /*
@@ -197,8 +179,10 @@ best_innerjoin(List *join_paths, Relids outer_relids)
  * 'joinrel' is the join relation
  * 'outerrel' is the outer join relation
  * 'innerrel' is the inner join relation
+ * 'restrictlist' contains all of the RestrictInfo nodes for restriction
+ *		clauses that apply to this join
  * 'mergeclause_list' is a list of RestrictInfo nodes for available
- *				mergejoin clauses between these two relations
+ *		mergejoin clauses in this join
  *
  * Returns a list of mergejoin paths.
  */
@@ -206,6 +190,7 @@ static List *
 sort_inner_and_outer(RelOptInfo *joinrel,
 					 RelOptInfo *outerrel,
 					 RelOptInfo *innerrel,
+					 List *restrictlist,
 					 List *mergeclause_list)
 {
 	List	   *path_list = NIL;
@@ -255,12 +240,14 @@ sort_inner_and_outer(RelOptInfo *joinrel,
 		innerkeys = make_pathkeys_for_mergeclauses(curclause_list,
 												   innerrel->targetlist);
 		/* Build pathkeys representing output sort order. */
-		merge_pathkeys = build_join_pathkeys(outerkeys, joinrel->targetlist,
+		merge_pathkeys = build_join_pathkeys(outerkeys,
+											 joinrel->targetlist,
 											 curclause_list);
 		/* And now we can make the path. */
 		path_node = create_mergejoin_path(joinrel,
 										  outerrel->cheapestpath,
 										  innerrel->cheapestpath,
+										  restrictlist,
 										  merge_pathkeys,
 										  get_actual_clauses(curclause_list),
 										  outerkeys,
@@ -301,11 +288,13 @@ sort_inner_and_outer(RelOptInfo *joinrel,
  * 'joinrel' is the join relation
  * 'outerrel' is the outer join relation
  * 'innerrel' is the inner join relation
+ * 'restrictlist' contains all of the RestrictInfo nodes for restriction
+ *		clauses that apply to this join
  * 'outerpath_list' is the list of possible outer paths
  * 'cheapest_inner' is the cheapest inner path
  * 'best_innerjoin' is the best inner index path (if any)
  * 'mergeclause_list' is a list of RestrictInfo nodes for available
- *				mergejoin clauses between these two relations
+ *		mergejoin clauses in this join
  *
  * Returns a list of possible join path nodes.
  */
@@ -313,6 +302,7 @@ static List *
 match_unsorted_outer(RelOptInfo *joinrel,
 					 RelOptInfo *outerrel,
 					 RelOptInfo *innerrel,
+					 List *restrictlist,
 					 List *outerpath_list,
 					 Path *cheapest_inner,
 					 Path *best_innerjoin,
@@ -358,6 +348,7 @@ match_unsorted_outer(RelOptInfo *joinrel,
 							create_nestloop_path(joinrel,
 												 outerpath,
 												 nestinnerpath,
+												 restrictlist,
 												 merge_pathkeys));
 
 		/* Done with this outer path if no chance for a mergejoin */
@@ -425,6 +416,7 @@ match_unsorted_outer(RelOptInfo *joinrel,
 							create_mergejoin_path(joinrel,
 												  outerpath,
 												  mergeinnerpath,
+												  restrictlist,
 												  merge_pathkeys,
 												  mergeclauses,
 												  NIL,
@@ -442,9 +434,11 @@ match_unsorted_outer(RelOptInfo *joinrel,
  * 'joinrel' is the join result relation
  * 'outerrel' is the outer join relation
  * 'innerrel' is the inner join relation
+ * 'restrictlist' contains all of the RestrictInfo nodes for restriction
+ *		clauses that apply to this join
  * 'innerpath_list' is the list of possible inner join paths
  * 'mergeclause_list' is a list of RestrictInfo nodes for available
- *				mergejoin clauses between these two relations
+ *		mergejoin clauses in this join
  *
  * Returns a list of possible merge paths.
  */
@@ -452,6 +446,7 @@ static List *
 match_unsorted_inner(RelOptInfo *joinrel,
 					 RelOptInfo *outerrel,
 					 RelOptInfo *innerrel,
+					 List *restrictlist,
 					 List *innerpath_list,
 					 List *mergeclause_list)
 {
@@ -510,6 +505,7 @@ match_unsorted_inner(RelOptInfo *joinrel,
 								create_mergejoin_path(joinrel,
 													  mergeouterpath,
 													  innerpath,
+													  restrictlist,
 													  merge_pathkeys,
 													  mergeclauses,
 													  outersortkeys,
@@ -528,6 +524,8 @@ match_unsorted_inner(RelOptInfo *joinrel,
  * 'joinrel' is the join relation
  * 'outerrel' is the outer join relation
  * 'innerrel' is the inner join relation
+ * 'restrictlist' contains all of the RestrictInfo nodes for restriction
+ *		clauses that apply to this join
  *
  * Returns a list of hashjoin paths.
  */
@@ -535,39 +533,62 @@ static List *
 hash_inner_and_outer(Query *root,
 					 RelOptInfo *joinrel,
 					 RelOptInfo *outerrel,
-					 RelOptInfo *innerrel)
+					 RelOptInfo *innerrel,
+					 List *restrictlist)
 {
 	List	   *hpath_list = NIL;
+	Relids		outerrelids = outerrel->relids;
+	Relids		innerrelids = innerrel->relids;
 	List	   *i;
 
-	foreach(i, joinrel->restrictinfo)
+	/*
+	 * Scan the join's restrictinfo list to find hashjoinable clauses
+	 * that are usable with this pair of sub-relations.  Since we currently
+	 * accept only var-op-var clauses as hashjoinable, we need only check
+	 * the membership of the vars to determine whether a particular clause
+	 * can be used with this pair of sub-relations.  This code would need
+	 * to be upgraded if we wanted to allow more-complex expressions in
+	 * hash joins.
+	 */
+	foreach(i, restrictlist)
 	{
 		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i);
+		Expr	   *clause;
+		Var		   *left,
+				   *right,
+				   *inner;
+		Selectivity	innerdisbursion;
+		HashPath   *hash_path;
+
+		if (restrictinfo->hashjoinoperator == InvalidOid)
+			continue;			/* not hashjoinable */
+
+		clause = restrictinfo->clause;
+		/* these must be OK, since check_hashjoinable accepted the clause */
+		left = get_leftop(clause);
+		right = get_rightop(clause);
+
+		/* check if clause is usable with these sub-rels, find inner var */
+		if (intMember(left->varno, outerrelids) &&
+			intMember(right->varno, innerrelids))
+			inner = right;
+		else if (intMember(left->varno, innerrelids) &&
+				 intMember(right->varno, outerrelids))
+			inner = left;
+		else
+			continue;			/* no good for these input relations */
 
-		/* we consider only clauses previously marked hashjoinable */
-		if (restrictinfo->hashjoinoperator)
-		{
-			Expr	   *clause = restrictinfo->clause;
-			Var		   *leftop = get_leftop(clause);
-			Var		   *rightop = get_rightop(clause);
-			Var		   *innerop;
-			Selectivity	innerdisbursion;
-			HashPath   *hash_path;
-
-			/* find the inner var and estimate its disbursion */
-			if (intMember(leftop->varno, innerrel->relids))
-				innerop = leftop;
-			else
-				innerop = rightop;
-			innerdisbursion = estimate_disbursion(root, innerop);
-
-			hash_path = create_hashjoin_path(joinrel,
-											 outerrel->cheapestpath,
-											 innerrel->cheapestpath,
-											 lcons(clause, NIL),
-											 innerdisbursion);
-			hpath_list = lappend(hpath_list, hash_path);
-		}
+		/* estimate disbursion of inner var for costing purposes */
+		innerdisbursion = estimate_disbursion(root, inner);
+
+		hash_path = create_hashjoin_path(joinrel,
+										 outerrel->cheapestpath,
+										 innerrel->cheapestpath,
+										 restrictlist,
+										 lcons(clause, NIL),
+										 innerdisbursion);
+
+		hpath_list = lappend(hpath_list, hash_path);
 	}
 
 	return hpath_list;
@@ -600,28 +621,47 @@ estimate_disbursion(Query *root, Var *var)
  *	  Select mergejoin clauses that are usable for a particular join.
  *	  Returns a list of RestrictInfo nodes for those clauses.
  *
- * Currently, all we need is the restrictinfo list of the joinrel.
- * By definition, any mergejoinable clause in that list will work ---
- * it must involve only vars in the join, or it wouldn't have been
- * in the restrict list, and it must involve vars on both sides of
- * the join, or it wouldn't have made it up to this level of join.
- * Since we currently allow only simple Vars as the left and right
- * sides of mergejoin clauses, that means the mergejoin clauses must
- * be usable for this join.  If we ever allow more complex expressions
- * containing multiple Vars, we would need to check that each side
- * of a potential joinclause uses only vars from one side of the join.
+ * We examine each restrictinfo clause known for the join to see
+ * if it is mergejoinable and involves vars from the two sub-relations
+ * currently of interest.
+ *
+ * Since we currently allow only plain Vars as the left and right sides
+ * of mergejoin clauses, this test is relatively simple.  This routine
+ * would need to be upgraded to support more-complex expressions
+ * as sides of mergejoins.  In theory, we could allow arbitrarily complex
+ * expressions in mergejoins, so long as one side uses only vars from one
+ * sub-relation and the other side uses only vars from the other.
  */
 static List *
-select_mergejoin_clauses(List *restrictinfo_list)
+select_mergejoin_clauses(RelOptInfo *joinrel,
+						 RelOptInfo *outerrel,
+						 RelOptInfo *innerrel,
+						 List *restrictlist)
 {
 	List	   *result_list = NIL;
+	Relids		outerrelids = outerrel->relids;
+	Relids		innerrelids = innerrel->relids;
 	List	   *i;
 
-	foreach(i, restrictinfo_list)
+	foreach(i, restrictlist)
 	{
-		RestrictInfo   *restrictinfo = lfirst(i);
-
-		if (restrictinfo->mergejoinoperator != InvalidOid)
+		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i);
+		Expr	   *clause;
+		Var		   *left,
+				   *right;
+
+		if (restrictinfo->mergejoinoperator == InvalidOid)
+			continue;			/* not mergejoinable */
+
+		clause = restrictinfo->clause;
+		/* these must be OK, since check_mergejoinable accepted the clause */
+		left = get_leftop(clause);
+		right = get_rightop(clause);
+
+		if ((intMember(left->varno, outerrelids) &&
+			 intMember(right->varno, innerrelids)) ||
+			(intMember(left->varno, innerrelids) &&
+			 intMember(right->varno, outerrelids)))
 			result_list = lcons(restrictinfo, result_list);
 	}