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'.

7 files changed, 525 insertions, 696 deletions

diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefile
index 3808f8242ff..fcca74f315b 100644
--- a/src/backend/optimizer/path/Makefile
+++ b/src/backend/optimizer/path/Makefile
@@ -4,7 +4,7 @@
 #    Makefile for optimizer/path
 #
 # IDENTIFICATION
-#    $Header: /cvsroot/pgsql/src/backend/optimizer/path/Makefile,v 1.12 1999/12/13 22:32:52 momjian Exp $
+#    $Header: /cvsroot/pgsql/src/backend/optimizer/path/Makefile,v 1.13 2000/02/07 04:40:59 tgl Exp $
 #
 #-------------------------------------------------------------------------
 
@@ -14,8 +14,7 @@ include ../../../Makefile.global
 CFLAGS += -I../..
 
 OBJS = allpaths.o clausesel.o costsize.o indxpath.o \
-       joinpath.o joinrels.o orindxpath.o pathkeys.o prune.o \
-	tidpath.o
+       joinpath.o joinrels.o orindxpath.o pathkeys.o tidpath.o
 
 all: SUBSYS.o
 
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index c4d36a064b5..52c30f7d01d 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.57 2000/01/26 05:56:34 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.58 2000/02/07 04:40:59 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -21,6 +21,7 @@
 #include "optimizer/pathnode.h"
 #include "optimizer/paths.h"
 
+
 #ifdef GEQO
 bool		enable_geqo = true;
 #else
@@ -30,31 +31,28 @@ bool		enable_geqo = false;
 int			geqo_rels = GEQO_RELS;
 
 
-static void set_base_rel_pathlist(Query *root, List *rels);
-static RelOptInfo *make_one_rel_by_joins(Query *root, List *rels,
-					  int levels_needed);
+static void set_base_rel_pathlist(Query *root);
+static RelOptInfo *make_one_rel_by_joins(Query *root, int levels_needed);
 
 #ifdef OPTIMIZER_DEBUG
 static void debug_print_rel(Query *root, RelOptInfo *rel);
-
 #endif
 
+
 /*
  * make_one_rel
  *	  Finds all possible access paths for executing a query, returning a
- *	  single rel.
- *
- * 'rels' is the list of single relation entries appearing in the query
+ *	  single rel that represents the join of all base rels in the query.
  */
 RelOptInfo *
-make_one_rel(Query *root, List *rels)
+make_one_rel(Query *root)
 {
 	int			levels_needed;
 
 	/*
 	 * Set the number of join (not nesting) levels yet to be processed.
 	 */
-	levels_needed = length(rels);
+	levels_needed = length(root->base_rel_list);
 
 	if (levels_needed <= 0)
 		return NULL;
@@ -62,159 +60,162 @@ make_one_rel(Query *root, List *rels)
 	/*
 	 * Generate access paths for the base rels.
 	 */
-	set_base_rel_pathlist(root, rels);
+	set_base_rel_pathlist(root);
 
-	if (levels_needed <= 1)
+	if (levels_needed == 1)
 	{
 		/*
 		 * Single relation, no more processing is required.
 		 */
-		return lfirst(rels);
+		return (RelOptInfo *) lfirst(root->base_rel_list);
 	}
 	else
 	{
 		/*
 		 * Generate join tree.
 		 */
-		return make_one_rel_by_joins(root, rels, levels_needed);
+		return make_one_rel_by_joins(root, levels_needed);
 	}
 }
 
 /*
  * set_base_rel_pathlist
- *	  Finds all paths available for scanning each relation entry in
- *	  'rels'.  Sequential scan and any available indices are considered
- *	  if possible (indices are not considered for lower nesting levels).
- *	  All useful paths are attached to the relation's 'pathlist' field.
- *
- *	  MODIFIES: rels
+ *	  Finds all paths available for scanning each base-relation entry.
+ *	  Sequential scan and any available indices are considered.
+ *	  Each useful path is attached to its relation's 'pathlist' field.
  */
 static void
-set_base_rel_pathlist(Query *root, List *rels)
+set_base_rel_pathlist(Query *root)
 {
-	List	   *temp;
+	List	   *rellist;
 
-	foreach(temp, rels)
+	foreach(rellist, root->base_rel_list)
 	{
-		RelOptInfo *rel = (RelOptInfo *) lfirst(temp);
+		RelOptInfo *rel = (RelOptInfo *) lfirst(rellist);
 		List	   *indices = find_relation_indices(root, rel);
-		List	   *sequential_scan_list;
-		List	   *rel_index_scan_list;
-		List	   *or_index_scan_list;
-		List	   *tidscan_pathlist;
-
-		sequential_scan_list = lcons(create_seqscan_path(rel), NIL);
-		/* Tid Scan Pathlist add */
-		tidscan_pathlist = create_tidscan_paths(root, rel);
-		if (tidscan_pathlist)
-			sequential_scan_list = nconc(sequential_scan_list,
-										 tidscan_pathlist);
-		rel_index_scan_list = create_index_paths(root,
-												 rel,
-												 indices,
-												 rel->restrictinfo,
-												 rel->joininfo);
+
+		/* Mark rel with estimated output rows, width, etc */
+		set_baserel_size_estimates(root, rel);
+
+		/*
+		 * Generate paths and add them to the rel's pathlist.
+		 *
+		 * add_path/add_pathlist will discard any paths that are dominated
+		 * by another available path, keeping only those paths that are
+		 * superior along at least one dimension of cost or sortedness.
+		 */
+
+		/* Consider sequential scan */
+		add_path(rel, create_seqscan_path(rel));
+
+		/* Consider TID scans */
+		add_pathlist(rel, create_tidscan_paths(root, rel));
+
+		/* Consider index paths for both simple and OR index clauses */
+		add_pathlist(rel, create_index_paths(root,
+											 rel,
+											 indices,
+											 rel->baserestrictinfo,
+											 rel->joininfo));
 
 		/* Note: create_or_index_paths depends on create_index_paths
 		 * to have marked OR restriction clauses with relevant indices;
 		 * this is why it doesn't need to be given the full list of indices.
 		 */
-		or_index_scan_list = create_or_index_paths(root, rel,
-												   rel->restrictinfo);
-
-		/* add_pathlist will discard any paths that are dominated by
-		 * another available path, keeping only those paths that are
-		 * superior along at least one dimension of cost or sortedness.
-		 */
-		rel->pathlist = add_pathlist(rel,
-									 sequential_scan_list,
-									 nconc(rel_index_scan_list,
-										   or_index_scan_list));
+		add_pathlist(rel, create_or_index_paths(root, rel,
+												rel->baserestrictinfo));
 
-		/* Now find the cheapest of the paths */
+		/* Now find the cheapest of the paths for this rel */
 		set_cheapest(rel, rel->pathlist);
-		/* Mark rel with estimated output rows and width */
-		set_rel_rows_width(root, rel);
 	}
 }
 
 /*
  * make_one_rel_by_joins
  *	  Find all possible joinpaths for a query by successively finding ways
- *	  to join single relations into join relations.
- *
- *	  Find all possible joinpaths(bushy trees) for a query by systematically
- *	  finding ways to join relations(both original and derived) together.
+ *	  to join component relations into join relations.
  *
- * 'rels' is the current list of relations for which join paths
- *				are to be found, i.e., the current list of relations that
- *				have already been derived.
- * 'levels_needed' is the number of iterations needed
+ * 'levels_needed' is the number of iterations needed, ie, the number of
+ *		base relations present in the query
  *
  * Returns the final level of join relations, i.e., the relation that is
  * the result of joining all the original relations together.
  */
 static RelOptInfo *
-make_one_rel_by_joins(Query *root, List *rels, int levels_needed)
+make_one_rel_by_joins(Query *root, int levels_needed)
 {
-	List	   *x;
-	List	   *joined_rels = NIL;
+	int			lev;
 	RelOptInfo *rel;
 
 	/*******************************************
 	 * genetic query optimizer entry point	   *
 	 *	  <utesch@aut.tu-freiberg.de>		   *
+	 * rest will be skipped in case of GEQO    *
 	 *******************************************/
-	if (enable_geqo && length(root->base_rel_list) >= geqo_rels)
+	if (enable_geqo && levels_needed >= geqo_rels)
 		return geqo(root);
 
-	/*******************************************
-	 * rest will be skipped in case of GEQO    *
-	 *******************************************/
+	/*
+	 * We employ a simple "dynamic programming" algorithm: we first
+	 * find all ways to build joins of two base relations, then all ways
+	 * to build joins of three base relations (from two-base-rel joins
+	 * and other base rels), then four-base-rel joins, and so on until
+	 * we have considered all ways to join all N relations into one rel.
+	 */
 
-	while (--levels_needed)
+	for (lev = 2; lev <= levels_needed; lev++)
 	{
+		List	   *first_old_rel = root->join_rel_list;
+		List	   *x;
 
 		/*
 		 * Determine all possible pairs of relations to be joined at this
-		 * level.  Determine paths for joining these relation pairs and
-		 * modify 'joined_rels' accordingly, then eliminate redundant join
-		 * relations.
+		 * level, and build paths for making each one from every available
+		 * pair of lower-level relations.  Results are prepended to
+		 * root->join_rel_list.
 		 */
-		joined_rels = make_rels_by_joins(root, rels);
+		make_rels_by_joins(root, lev);
 
-		update_rels_pathlist_for_joins(root, joined_rels);
-
-		merge_rels_with_same_relids(joined_rels);
+		/*
+		 * The relations created at the current level will appear at the
+		 * front of root->join_rel_list.
+		 */
+		foreach(x, root->join_rel_list)
+		{
+			if (x == first_old_rel)
+				break;			/* no more rels added at this level */
 
-		root->join_rel_list = rels = joined_rels;
+			rel = (RelOptInfo *) lfirst(x);
 
 #ifdef NOT_USED
-
-		/*
-		 * * for each expensive predicate in each path in each distinct
-		 * rel, * consider doing pullup  -- JMH
-		 */
-		if (XfuncMode != XFUNC_NOPULL && XfuncMode != XFUNC_OFF)
-			foreach(x, joined_rels)
-				xfunc_trypullup((RelOptInfo *) lfirst(x));
+			/*
+			 * * for each expensive predicate in each path in each distinct
+			 * rel, * consider doing pullup  -- JMH
+			 */
+			if (XfuncMode != XFUNC_NOPULL && XfuncMode != XFUNC_OFF)
+				xfunc_trypullup(rel);
 #endif
 
-		rels_set_cheapest(root, joined_rels);
-
-		foreach(x, joined_rels)
-		{
-			rel = (RelOptInfo *) lfirst(x);
+			/* Find and save the cheapest path for this rel */
+			set_cheapest(rel, rel->pathlist);
 
 #ifdef OPTIMIZER_DEBUG
-			printf("levels left: %d\n", levels_needed);
 			debug_print_rel(root, rel);
 #endif
 		}
-
 	}
 
-	return get_cheapest_complete_rel(rels);
+	/*
+	 * Now, the front of the join_rel_list should be the single rel
+	 * representing the join of all the base rels.
+	 */
+	Assert(length(root->join_rel_list) > 0);
+	rel = (RelOptInfo *) lfirst(root->join_rel_list);
+	Assert(length(rel->relids) == levels_needed);
+	Assert(length(root->join_rel_list) == 1 ||
+		   length(((RelOptInfo *) lsecond(root->join_rel_list))->relids) < levels_needed);
+
+	return rel;
 }
 
 /*****************************************************************************
@@ -222,6 +223,7 @@ make_one_rel_by_joins(Query *root, List *rels, int levels_needed)
  *****************************************************************************/
 
 #ifdef OPTIMIZER_DEBUG
+
 static void
 print_joinclauses(Query *root, List *clauses)
 {
@@ -286,7 +288,7 @@ print_path(Query *root, Path *path, int indent)
 				for (i = 0; i < indent + 1; i++)
 					printf("\t");
 				printf("   clauses=(");
-				print_joinclauses(root, jp->path.parent->restrictinfo);
+				print_joinclauses(root, jp->joinrestrictinfo);
 				printf(")\n");
 
 				if (nodeTag(path) == T_MergePath)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 1246f87830d..7c8d4b63c07 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -19,7 +19,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v 1.50 2000/01/26 05:56:34 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v 1.51 2000/02/07 04:40:59 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -447,22 +447,26 @@ cost_hashjoin(Path *outer_path,
 }
 
 /*
- * set_rel_rows_width
- *		Set the 'rows' and 'width' estimates for the given base relation.
+ * set_baserel_size_estimates
+ *		Set the size estimates for the given base relation.
  *
- * 'rows' is the estimated number of output tuples (after applying
- * restriction clauses).
- * 'width' is the estimated average output tuple width in bytes.
+ * The rel's targetlist and restrictinfo list must have been constructed
+ * already.
+ *
+ * We set the following fields of the rel node:
+ *	rows: the estimated number of output tuples (after applying
+ *	      restriction clauses).
+ *	width: the estimated average output tuple width in bytes.
  */
 void
-set_rel_rows_width(Query *root, RelOptInfo *rel)
+set_baserel_size_estimates(Query *root, RelOptInfo *rel)
 {
 	/* Should only be applied to base relations */
 	Assert(length(rel->relids) == 1);
 
 	rel->rows = rel->tuples *
 		restrictlist_selectivity(root,
-								 rel->restrictinfo,
+								 rel->baserestrictinfo,
 								 lfirsti(rel->relids));
 	Assert(rel->rows >= 0);
 
@@ -470,28 +474,56 @@ set_rel_rows_width(Query *root, RelOptInfo *rel)
 }
 
 /*
- * set_joinrel_rows_width
- *		Set the 'rows' and 'width' estimates for the given join relation.
+ * set_joinrel_size_estimates
+ *		Set the size estimates for the given join relation.
+ *
+ * The rel's targetlist must have been constructed already, and a
+ * restriction clause list that matches the given component rels must
+ * be provided.
+ *
+ * Since there is more than one way to make a joinrel for more than two
+ * base relations, the results we get here could depend on which component
+ * rel pair is provided.  In theory we should get the same answers no matter
+ * which pair is provided; in practice, since the selectivity estimation
+ * routines don't handle all cases equally well, we might not.  But there's
+ * not much to be done about it.  (Would it make sense to repeat the
+ * calculations for each pair of input rels that's encountered, and somehow
+ * average the results?  Probably way more trouble than it's worth.)
+ *
+ * We set the same relnode fields as set_baserel_size_estimates() does.
  */
 void
-set_joinrel_rows_width(Query *root, RelOptInfo *rel,
-					   JoinPath *joinpath)
+set_joinrel_size_estimates(Query *root, RelOptInfo *rel,
+						   RelOptInfo *outer_rel,
+						   RelOptInfo *inner_rel,
+						   List *restrictlist)
 {
 	double		temp;
 
 	/* cartesian product */
-	temp = joinpath->outerjoinpath->parent->rows *
-		joinpath->innerjoinpath->parent->rows;
+	temp = outer_rel->rows * inner_rel->rows;
 
-	/* apply join restrictivity */
+	/*
+	 * Apply join restrictivity.  Note that we are only considering clauses
+	 * that become restriction clauses at this join level; we are not
+	 * double-counting them because they were not considered in estimating
+	 * the sizes of the component rels.
+	 */
 	temp *= restrictlist_selectivity(root,
-									 joinpath->path.parent->restrictinfo,
+									 restrictlist,
 									 0);
 
 	Assert(temp >= 0);
 	rel->rows = temp;
 
-	set_rel_width(root, rel);
+	/*
+	 * We could apply set_rel_width() to compute the output tuple width
+	 * from scratch, but at present it's always just the sum of the input
+	 * widths, so why work harder than necessary?  If relnode.c is ever
+	 * taught to remove unneeded columns from join targetlists, go back
+	 * to using set_rel_width here.
+	 */
+	rel->width = outer_rel->width + inner_rel->width;
 }
 
 /*
@@ -516,6 +548,7 @@ set_rel_width(Query *root, RelOptInfo *rel)
  *
  *	  If a field is variable-length, we make a default assumption.  Would be
  *	  better if VACUUM recorded some stats about the average field width...
+ *	  also, we have access to the atttypmod, but fail to use it...
  */
 static int
 compute_attribute_width(TargetEntry *tlistentry)
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);
 	}
 
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 5fc673e5dba..e872b67623a 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -8,399 +8,263 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinrels.c,v 1.42 2000/02/06 03:27:32 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinrels.c,v 1.43 2000/02/07 04:40:59 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
 #include "postgres.h"
 
-#ifdef HAVE_LIMITS_H
-#include <limits.h>
-#ifndef MAXINT
-#define MAXINT		  INT_MAX
-#endif
-#else
-#ifdef HAVE_VALUES_H
-#include <values.h>
-#endif
-#endif
-
 #include "optimizer/cost.h"
 #include "optimizer/joininfo.h"
 #include "optimizer/pathnode.h"
 #include "optimizer/paths.h"
 #include "optimizer/tlist.h"
 
-static RelOptInfo *make_join_rel(RelOptInfo *outer_rel, RelOptInfo *inner_rel);
-static List *new_join_tlist(List *tlist, int first_resdomno);
-static void build_joinrel_restrict_and_join(RelOptInfo *joinrel,
-											List *joininfo_list,
-											Relids join_relids);
+
+static RelOptInfo *make_join_rel(Query *root, RelOptInfo *rel1,
+								 RelOptInfo *rel2);
+
 
 /*
  * make_rels_by_joins
- *	  Find all possible joins for each of the outer join relations in
- *	  'old_rels'.  A rel node is created for each possible join relation,
- *	  and the resulting list of nodes is returned.	If at all possible, only
- *	  those relations for which join clauses exist are considered.	If none
- *	  of these exist for a given relation, all remaining possibilities are
- *	  considered.
+ *	  Consider ways to produce join relations containing exactly 'level'
+ *	  base relations.  (This is one step of the dynamic-programming method
+ *	  embodied in make_one_rel_by_joins.)  Join rel nodes for each feasible
+ *	  combination of base rels are created and added to the front of the
+ *	  query's join_rel_list.  Implementation paths are created for each
+ *	  such joinrel, too.
  *
- * Returns a list of rel nodes corresponding to the new join relations.
+ * Returns nothing, but adds entries to root->join_rel_list.
  */
-List *
-make_rels_by_joins(Query *root, List *old_rels)
+void
+make_rels_by_joins(Query *root, int level)
 {
-	List	   *join_list = NIL;
 	List	   *r;
 
-	foreach(r, old_rels)
+	/*
+	 * First, consider left-sided and right-sided plans, in which rels of
+	 * exactly level-1 member relations are joined against base relations.
+	 * We prefer to join using join clauses, but if we find a rel of level-1
+	 * members that has no join clauses, we will generate Cartesian-product
+	 * joins against all base rels not already contained in it.
+	 *
+	 * In the first pass (level == 2), we try to join each base rel to each
+	 * base rel that appears later in base_rel_list.  (The mirror-image
+	 * joins are handled automatically by make_join_rel.)  In later passes,
+	 * we try to join rels of size level-1 from join_rel_list to each
+	 * base rel in base_rel_list.
+	 *
+	 * We assume that the rels already present in join_rel_list appear in
+	 * decreasing order of level (number of members).  This should be true
+	 * since we always add new higher-level rels to the front of the list.
+	 */
+	if (level == 2)
+		r = root->base_rel_list;	/* level-1 is base rels */
+	else
+		r = root->join_rel_list;
+	for (; r != NIL; r = lnext(r))
 	{
 		RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
-		List	   *joined_rels;
+		int			old_level = length(old_rel->relids);
+		List	   *other_rels;
+
+		if (old_level != level-1)
+			break;
 
-		if (!(joined_rels = make_rels_by_clause_joins(root, old_rel,
-													  old_rel->joininfo,
-													  NIL)))
+		if (level == 2)
+			other_rels = lnext(r); /* only consider remaining base rels */
+		else
+			other_rels = root->base_rel_list; /* consider all base rels */
+
+		if (old_rel->joininfo != NIL)
+		{
+			/*
+			 * Note that if all available join clauses for this rel require
+			 * more than one other rel, we will fail to make any joins against
+			 * it here.  That's OK; it'll be considered by "bushy plan" join
+			 * code in a higher-level pass.
+			 */
+			make_rels_by_clause_joins(root,
+									  old_rel,
+									  other_rels);
+		}
+		else
 		{
 			/*
 			 * Oops, we have a relation that is not joined to any other
 			 * relation.  Cartesian product time.
 			 */
-			joined_rels = make_rels_by_clauseless_joins(old_rel,
-													root->base_rel_list);
-			joined_rels = nconc(joined_rels,
-								make_rels_by_clauseless_joins(old_rel,
-															  old_rels));
+			make_rels_by_clauseless_joins(root,
+										  old_rel,
+										  other_rels);
 		}
-
-		join_list = nconc(join_list, joined_rels);
 	}
 
-	return join_list;
-}
-
-/*
- * make_rels_by_clause_joins
- *	  Build joins between an outer relation 'old_rel' and relations
- *	  within old_rel's joininfo nodes
- *	  (i.e., relations that participate in join clauses that 'old_rel'
- *	  also participates in).
- *
- * 'old_rel' is the relation entry for the outer relation
- * 'joininfo_list' is a list of join clauses which 'old_rel'
- *		participates in
- * 'only_relids': if not NIL, only joins against base rels mentioned in
- *		only_relids are allowable.
- *
- * Returns a list of new join relations.
- */
-List *
-make_rels_by_clause_joins(Query *root, RelOptInfo *old_rel,
-						  List *joininfo_list, Relids only_relids)
-{
-	List	   *join_list = NIL;
-	List	   *i;
-
-	foreach(i, joininfo_list)
+	/*
+	 * Now, consider "bushy plans" in which relations of k base rels are
+	 * joined to relations of level-k base rels, for 2 <= k <= level-2.
+	 * The previous loop left r pointing to the first rel of level 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.
+	 */
+	for (; r != NIL; r = lnext(r))
 	{
-		JoinInfo   *joininfo = (JoinInfo *) lfirst(i);
-		Relids		unjoined_relids = joininfo->unjoined_relids;
-		RelOptInfo *joined_rel;
-
-		if (unjoined_relids == NIL)
-			continue;			/* probably can't happen */
-
-		if (length(unjoined_relids) == 1 &&
-			(only_relids == NIL ||
-			 /* geqo only wants certain relids to be joined to old_rel */
-			 intMember(lfirsti(unjoined_relids), only_relids)))
-		{
-			RelOptInfo   *base_rel = get_base_rel(root,
-												  lfirsti(unjoined_relids));
+		RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
+		int			old_level = length(old_rel->relids);
+		List	   *r2;
 
-			/* Left-sided join of outer rel against a single base rel */
-			joined_rel = make_join_rel(old_rel, base_rel);
-			join_list = lappend(join_list, joined_rel);
+		/* We can quit once past the halfway point (make_join_rel took care
+		 * of making the opposite-direction joins)
+		 */
+		if (old_level * 2 < level)
+			break;
 
-			/* Consider right-sided plan as well */
-			if (length(old_rel->relids) > 1)
-			{
-				joined_rel = make_join_rel(base_rel, old_rel);
-				join_list = lappend(join_list, joined_rel);
-			}
-		}
+		if (old_rel->joininfo == NIL)
+			continue;			/* we ignore clauseless joins here */
 
-		if (only_relids == NIL)	/* no bushy plans for geqo */
+		foreach(r2, lnext(r))
 		{
-			List	   *r;
-
-			/* Build "bushy" plans: join old_rel against all pre-existing
-			 * joins of rels it doesn't already contain, if there is a
-			 * suitable join clause.
-			 */
-			foreach(r, root->join_rel_list)
+			RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);
+			int			new_level = length(new_rel->relids);
+
+			if (old_level + new_level > level)
+				continue;		/* scan down to new_rels of right size */
+			if (old_level + new_level < level)
+				break;			/* no more new_rels of right size */
+			if (nonoverlap_setsi(old_rel->relids, new_rel->relids))
 			{
-				RelOptInfo *join_rel = lfirst(r);
+				List	   *i;
 
-				Assert(length(join_rel->relids) > 1);
-				if (is_subseti(unjoined_relids, join_rel->relids) &&
-					nonoverlap_setsi(old_rel->relids, join_rel->relids))
+				/* 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)
 				{
-					joined_rel = make_join_rel(old_rel, join_rel);
-					join_list = lappend(join_list, joined_rel);
+					JoinInfo   *joininfo = (JoinInfo *) lfirst(i);
+
+					if (is_subseti(joininfo->unjoined_relids, new_rel->relids))
+					{
+						make_join_rel(root, old_rel, new_rel);
+						break;
+					}
 				}
 			}
 		}
 	}
-
-	return join_list;
 }
 
 /*
- * make_rels_by_clauseless_joins
- *	  Given an outer relation 'old_rel' and a list of inner relations
- *	  'inner_rels', create a join relation between 'old_rel' and each
- *	  member of 'inner_rels' that isn't already included in 'old_rel'.
+ * 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 participate in join clauses that 'old_rel' also participates in).
+ *	  The join rel nodes are added to root->join_rel_list.
+ *
+ * 'old_rel' is the relation entry for the relation to be joined
+ * 'other_rels': other rels to be considered for joining
+ *
+ * Currently, this is only used with base rels in other_rels, but it would
+ * 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 base rels, since the is_subset test can
+ * only succeed when other_rel is not already part of old_rel.)
  *
- * Returns a list of new join relations.
+ * Returns NULL if no suitable joins were found, else the last suitable
+ * joinrel processed.  (The only caller who checks the return value is
+ * geqo_eval.c, and it sets things up so there can be no more than one
+ * "suitable" joinrel; so we don't bother with returning a list.)
  */
-List *
-make_rels_by_clauseless_joins(RelOptInfo *old_rel, List *inner_rels)
+RelOptInfo *
+make_rels_by_clause_joins(Query *root,
+						  RelOptInfo *old_rel,
+						  List *other_rels)
 {
-	List	   *join_list = NIL;
-	List	   *i;
+	RelOptInfo *result = NULL;
+	List	   *i,
+			   *j;
 
-	foreach(i, inner_rels)
+	foreach(i, old_rel->joininfo)
 	{
-		RelOptInfo *inner_rel = (RelOptInfo *) lfirst(i);
+		JoinInfo   *joininfo = (JoinInfo *) lfirst(i);
+		Relids		unjoined_relids = joininfo->unjoined_relids;
 
-		if (nonoverlap_setsi(inner_rel->relids, old_rel->relids))
+		foreach(j, other_rels)
 		{
-			join_list = lappend(join_list,
-								make_join_rel(old_rel, inner_rel));
+			RelOptInfo   *other_rel = (RelOptInfo *) lfirst(j);
+
+			if (is_subseti(unjoined_relids, other_rel->relids))
+				result = make_join_rel(root, old_rel, other_rel);
 		}
 	}
 
-	return join_list;
+	return result;
 }
 
 /*
- * make_join_rel
- *	  Creates and initializes a new join relation.
- *
- * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be
- *		joined
- *
- * Returns the new join relation node.
- */
-static RelOptInfo *
-make_join_rel(RelOptInfo *outer_rel, RelOptInfo *inner_rel)
-{
-	RelOptInfo *joinrel = makeNode(RelOptInfo);
-	List	   *new_outer_tlist;
-	List	   *new_inner_tlist;
-
-	/*
-	 * This function uses a trick to pass inner/outer rels as two sublists.
-	 * The list will be flattened out in update_rels_pathlist_for_joins().
-	 */
-	joinrel->relids = lcons(outer_rel->relids, lcons(inner_rel->relids, NIL));
-	joinrel->rows = 0;
-	joinrel->width = 0;
-	joinrel->targetlist = NIL;
-	joinrel->pathlist = NIL;
-	joinrel->cheapestpath = (Path *) NULL;
-	joinrel->pruneable = true;
-	joinrel->indexed = false;
-	joinrel->pages = 0;
-	joinrel->tuples = 0;
-	joinrel->restrictinfo = NIL;
-	joinrel->joininfo = NIL;
-	joinrel->innerjoin = NIL;
-
-	/*
-	 * Create a new tlist by removing irrelevant elements from both tlists
-	 * of the outer and inner join relations and then merging the results
-	 * together.
-	 */
-	new_outer_tlist = new_join_tlist(outer_rel->targetlist, 1);
-	new_inner_tlist = new_join_tlist(inner_rel->targetlist,
-									 length(new_outer_tlist) + 1);
-	joinrel->targetlist = nconc(new_outer_tlist, new_inner_tlist);
-
-	/*
-	 * Construct restrict and join clause lists for the new joinrel.
-	 *
-	 * nconc(listCopy(x), y) is an idiom for making a new list without
-	 * changing either input list.
-	 */
-	build_joinrel_restrict_and_join(joinrel,
-									nconc(listCopy(outer_rel->joininfo),
-										  inner_rel->joininfo),
-									nconc(listCopy(outer_rel->relids),
-										  inner_rel->relids));
-
-	return joinrel;
-}
-
-/*
- * new_join_tlist
- *	  Builds a join relation's target list by keeping those elements that
- *	  will be in the final target list and any other elements that are still
- *	  needed for future joins.	For a target list entry to still be needed
- *	  for future joins, its 'joinlist' field must not be empty after removal
- *	  of all relids in 'other_relids'.
+ * make_rels_by_clauseless_joins
+ *	  Given a relation 'old_rel' and a list of other relations
+ *	  'other_rels', create a join relation between 'old_rel' and each
+ *	  member of 'other_rels' that isn't already included in 'old_rel'.
  *
- *	  XXX this seems to be a dead test --- we don't keep track of joinlists
- *	  for individual targetlist entries anymore, if we ever did...
+ * 'old_rel' is the relation entry for the relation to be joined
+ * 'other_rels': other rels to be considered for joining
  *
- * 'tlist' is the target list of one of the join relations
- * 'other_relids' is a list of relids contained within the other
- *				join relation
- * 'first_resdomno' is the resdom number to use for the first created
- *				target list entry
+ * Currently, this is only used with base rels in other_rels, but it would
+ * work for joining to joinrels too.
  *
- * Returns the new target list.
+ * Returns NULL if no suitable joins were found, else the last suitable
+ * joinrel processed.  (The only caller who checks the return value is
+ * geqo_eval.c, and it sets things up so there can be no more than one
+ * "suitable" joinrel; so we don't bother with returning a list.)
  */
-static List *
-new_join_tlist(List *tlist,
-			   int first_resdomno)
+RelOptInfo *
+make_rels_by_clauseless_joins(Query *root,
+							  RelOptInfo *old_rel,
+							  List *other_rels)
 {
-	int			resdomno = first_resdomno - 1;
-	List	   *t_list = NIL;
+	RelOptInfo *result = NULL;
 	List	   *i;
-	List	   *join_list = NIL;
 
-	foreach(i, tlist)
+	foreach(i, other_rels)
 	{
-		TargetEntry *xtl = lfirst(i);
-		bool		in_final_tlist;
+		RelOptInfo *other_rel = (RelOptInfo *) lfirst(i);
 
-		/*
-		 * XXX surely this is wrong?  join_list is never changed?  tgl
-		 * 2/99
-		 */
-		in_final_tlist = (join_list == NIL);
-		if (in_final_tlist)
-		{
-			resdomno += 1;
-			t_list = lappend(t_list,
-							 create_tl_element(get_expr(xtl), resdomno));
-		}
+		if (nonoverlap_setsi(other_rel->relids, old_rel->relids))
+			result = make_join_rel(root, old_rel, other_rel);
 	}
 
-	return t_list;
+	return result;
 }
 
-/*
- * build_joinrel_restrict_and_join
- *	  Builds a join relation's restrictinfo and joininfo lists from the
- *	  joininfo lists of the relations it joins.  If a join clause from an
- *	  input relation refers to base rels still not present in the joinrel,
- *	  then it is still a join clause for the joinrel; we put it into an
- *	  appropriate JoinInfo list for the joinrel.  Otherwise, the clause is
- *	  now a restrict clause for the joined relation, and we put it into
- *	  the joinrel's restrictinfo list.  (It will not need to be considered
- *	  further up the join tree.)
- *
- * 'joininfo_list' is a list of joininfo nodes from the relations being joined
- * 'join_relids' is a list of all base relids in the new join relation
- *
- * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass
- * up to the join relation.  I believe this is no longer necessary, because
- * RestrictInfo nodes are no longer context-dependent.  Instead, just add
- * the original nodes to the lists belonging to the join relation.
- */
-static void
-build_joinrel_restrict_and_join(RelOptInfo *joinrel,
-								List *joininfo_list,
-								Relids join_relids)
-{
-	List	   *xjoininfo;
-
-	foreach(xjoininfo, joininfo_list)
-	{
-		JoinInfo   *joininfo = (JoinInfo *) lfirst(xjoininfo);
-		Relids		new_unjoined_relids;
-
-		new_unjoined_relids = set_differencei(joininfo->unjoined_relids,
-											  join_relids);
-		if (new_unjoined_relids == NIL)
-		{
-			/*
-			 * Clauses in this JoinInfo list become restriction clauses
-			 * for the joinrel, since they refer to no outside rels.
-			 *
-			 * Be careful to eliminate duplicates, since we will see the
-			 * same clauses arriving from both input relations...
-			 */
-			joinrel->restrictinfo =
-				LispUnion(joinrel->restrictinfo,
-						  joininfo->jinfo_restrictinfo);
-		}
-		else
-		{
-			/*
-			 * These clauses are still join clauses at this level,
-			 * so find or make the appropriate JoinInfo item for the joinrel,
-			 * and add the clauses to it (eliminating duplicates).
-			 */
-			JoinInfo   *new_joininfo;
-
-			new_joininfo = find_joininfo_node(joinrel, new_unjoined_relids);
-			new_joininfo->jinfo_restrictinfo =
-				LispUnion(new_joininfo->jinfo_restrictinfo,
-						  joininfo->jinfo_restrictinfo);
-		}
-	}
-}
 
 /*
- * get_cheapest_complete_rel
- *	   Find the join relation that includes all the original
- *	   relations, i.e. the final join result.
- *
- * 'join_rel_list' is a list of join relations.
- *
- * Returns the list of final join relations.
+ * make_join_rel
+ *	   Find or create a join RelOptInfo that represents the join of
+ *	   the two given rels, and add to it path information for paths
+ *	   created with the two rels as outer and inner rel.
+ *	   (The join rel may already contain paths generated from other
+ *	   pairs of rels that add up to the same set of base rels.)
+ *	   The join rel is stored in the query's join_rel_list.
  */
-RelOptInfo *
-get_cheapest_complete_rel(List *join_rel_list)
+static RelOptInfo *
+make_join_rel(Query *root, RelOptInfo *rel1, RelOptInfo *rel2)
 {
-	RelOptInfo *final_rel = NULL;
-	List	   *xrel;
+	RelOptInfo	   *joinrel;
+	List		   *restrictlist;
 
 	/*
-	 * find the relations that have no further joins, i.e., its joininfos
-	 * all have unjoined_relids nil.  (Actually, a JoinInfo shouldn't
-	 * ever have nil unjoined_relids, so I think this code is overly
-	 * complex.  In fact it seems wrong; shouldn't we be looking for
-	 * rels with complete relids lists???  Seems like a cartesian-product
-	 * case could fail because sub-relations could have nil JoinInfo lists.
-	 * Doesn't actually fail but I don't really understand why...)
+	 * Find or build the join RelOptInfo, and compute the restrictlist
+	 * that goes with this particular joining.
 	 */
-	foreach(xrel, join_rel_list)
-	{
-		RelOptInfo *rel = (RelOptInfo *) lfirst(xrel);
-		bool		final = true;
-		List	   *xjoininfo;
-
-		foreach(xjoininfo, rel->joininfo)
-		{
-			JoinInfo   *joininfo = (JoinInfo *) lfirst(xjoininfo);
+	joinrel = get_join_rel(root, rel1, rel2, &restrictlist);
 
-			if (joininfo->unjoined_relids != NIL)
-			{
-				final = false;
-				break;
-			}
-		}
-		if (final)
-			if (final_rel == NULL ||
-			 path_is_cheaper(rel->cheapestpath, final_rel->cheapestpath))
-				final_rel = rel;
-	}
+	/*
+	 * We consider paths using each rel as both outer and inner.
+	 */
+	add_paths_to_joinrel(root, joinrel, rel1, rel2, restrictlist);
+	add_paths_to_joinrel(root, joinrel, rel2, rel1, restrictlist);
 
-	return final_rel;
+	return joinrel;
 }
diff --git a/src/backend/optimizer/path/prune.c b/src/backend/optimizer/path/prune.c
deleted file mode 100644
index f2dc6d90dfc..00000000000
--- a/src/backend/optimizer/path/prune.c
+++ /dev/null
@@ -1,109 +0,0 @@
-/*-------------------------------------------------------------------------
- *
- * prune.c
- *	  Routines to prune redundant paths and relations
- *
- * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
- * Portions Copyright (c) 1994, Regents of the University of California
- *
- *
- * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/Attic/prune.c,v 1.46 2000/02/06 03:27:32 tgl Exp $
- *
- *-------------------------------------------------------------------------
- */
-#include "postgres.h"
-
-
-#include "optimizer/cost.h"
-#include "optimizer/pathnode.h"
-#include "optimizer/paths.h"
-
-static List *merge_rel_with_same_relids(RelOptInfo *rel, List *unmerged_rels);
-
-/*
- * merge_rels_with_same_relids
- *	  Removes any redundant relation entries from a list of rel nodes
- *	  'rel_list', merging their pathlists into the first non-duplicate
- *	  relation entry for each value of relids.
- *
- * Returns the resulting list.
- */
-void
-merge_rels_with_same_relids(List *rel_list)
-{
-	List	   *i;
-
-	/*
-	 * rel_list can shorten while running as duplicate relations are
-	 * deleted.  Obviously, the first relation can't be a duplicate,
-	 * so the list head pointer won't change.
-	 */
-	foreach(i, rel_list)
-	{
-		lnext(i) = merge_rel_with_same_relids((RelOptInfo *) lfirst(i),
-											  lnext(i));
-	}
-}
-
-/*
- * merge_rel_with_same_relids
- *	  Prunes those relations from 'unmerged_rels' that are redundant with
- *	  'rel'.  A relation is redundant if it is built up of the same
- *	  relations as 'rel'.  Paths for the redundant relations are merged into
- *	  the pathlist of 'rel'.
- *
- * Returns a list of non-redundant relations, and sets the pathlist field
- * of 'rel' appropriately.
- *
- */
-static List *
-merge_rel_with_same_relids(RelOptInfo *rel, List *unmerged_rels)
-{
-	List	   *result = NIL;
-	List	   *i;
-
-	foreach(i, unmerged_rels)
-	{
-		RelOptInfo *unmerged_rel = (RelOptInfo *) lfirst(i);
-
-		if (sameseti(rel->relids, unmerged_rel->relids))
-		{
-			/*
-			 * These rels are for the same set of base relations,
-			 * so get the best of their pathlists.  We assume it's
-			 * ok to reassign a path to the other RelOptInfo without
-			 * doing more than changing its parent pointer (cf. pathnode.c).
-			 */
-			rel->pathlist = add_pathlist(rel,
-										 rel->pathlist,
-										 unmerged_rel->pathlist);
-		}
-		else
-			result = lappend(result, unmerged_rel);
-	}
-	return result;
-}
-
-/*
- * rels_set_cheapest
- *	  For each relation entry in 'rel_list' (which should contain only join
- *	  relations), set pointers to the cheapest path and compute rel size.
- */
-void
-rels_set_cheapest(Query *root, List *rel_list)
-{
-	List	   *x;
-
-	foreach(x, rel_list)
-	{
-		RelOptInfo	   *rel = (RelOptInfo *) lfirst(x);
-		JoinPath	   *cheapest;
-
-		cheapest = (JoinPath *) set_cheapest(rel, rel->pathlist);
-		if (IsA_JoinPath(cheapest))
-			set_joinrel_rows_width(root, rel, cheapest);
-		else
-			elog(ERROR, "rels_set_cheapest: non JoinPath found");
-	}
-}
diff --git a/src/backend/optimizer/path/tidpath.c b/src/backend/optimizer/path/tidpath.c
index 35bcbc7e561..ab0427ef322 100644
--- a/src/backend/optimizer/path/tidpath.c
+++ b/src/backend/optimizer/path/tidpath.c
@@ -9,7 +9,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/tidpath.c,v 1.3 2000/01/26 05:56:34 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/tidpath.c,v 1.4 2000/02/07 04:40:59 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -37,7 +37,7 @@
 #include "utils/lsyscache.h"
 
 static List	*create_tidscan_joinpaths(RelOptInfo *);
-static List	*TidqualFromRestrictinfo(List *relids, List * restrictinfo);
+static List	*TidqualFromRestrictinfo(List *relids, List *restrictinfo);
 static bool	isEvaluable(int varno, Node *node);
 static Node	*TidequalClause(int varno, Expr *node);
 static List	*TidqualFromExpr(int varno, Expr *expr);
@@ -209,16 +209,17 @@ List *TidqualFromExpr(int varno, Expr *expr)
 	return rlst;
 } 
 
-static
-List *TidqualFromRestrictinfo(List *relids, List * restrictinfo)
+static List *
+TidqualFromRestrictinfo(List *relids, List *restrictinfo)
 {
 	List	*lst, *rlst = NIL;
 	int	varno;
 	Node	*node;
 	Expr	*expr;
 
-	if (length(relids)>1)	return NIL;
-	varno = (int)lfirst(relids);
+	if (length(relids) != 1)
+		return NIL;
+	varno = lfirsti(relids);
 	foreach (lst, restrictinfo)
 	{
 		node = lfirst(lst);
@@ -226,9 +227,7 @@ List *TidqualFromRestrictinfo(List *relids, List * restrictinfo)
 		expr = ((RestrictInfo *)node)->clause;
 		rlst = TidqualFromExpr(varno, expr);
 		if (rlst)
-		{
 			break;
-		}
 	}
 	return rlst;
 }
@@ -281,8 +280,9 @@ List *
 create_tidscan_paths(Query *root, RelOptInfo *rel)
 {
 	List	*rlst = NIL;
-	TidPath	*pathnode = (TidPath *)0;
-	List	*tideval = TidqualFromRestrictinfo(rel->relids, rel->restrictinfo);
+	TidPath	*pathnode = (TidPath *) NULL;
+	List	*tideval = TidqualFromRestrictinfo(rel->relids,
+											   rel->baserestrictinfo);
 	
 	if (tideval)
 		pathnode = create_tidscan_path(rel, tideval);