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

4 files changed, 87 insertions, 51 deletions

diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 99254740e78..529aa5cea7a 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: relation.h,v 1.42 2000/01/26 05:58:17 momjian Exp $
+ * $Id: relation.h,v 1.43 2000/02/07 04:41:02 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -54,13 +54,26 @@ typedef List *Relids;
  *	 * The presence of the remaining fields depends on the restrictions
  *		and joins that the relation participates in:
  *
- *		restrictinfo - List of RestrictInfo nodes, containing info about each
- *					 qualification clause in which this relation participates
+ *		baserestrictinfo - List of RestrictInfo nodes, containing info about
+ *					each qualification clause in which this relation
+ *					participates (only used for base rels)
  *		joininfo  - List of JoinInfo nodes, containing info about each join
  *					clause in which this relation participates
  *		innerjoin - List of Path nodes that represent indices that may be used
  *					as inner paths of nestloop joins. This field is non-null
  *					only for base rels, since join rels have no indices.
+ *
+ * Note: Keeping a restrictinfo list in the RelOptInfo is useful only for
+ * base rels, because for a join rel the set of clauses that are treated as
+ * restrict clauses varies depending on which sub-relations we choose to join.
+ * (For example, in a 3-base-rel join, a clause relating rels 1 and 2 must be
+ * treated as a restrictclause if we join {1} and {2 3} to make {1 2 3}; but
+ * if we join {1 2} and {3} then that clause will be a restrictclause in {1 2}
+ * and should not be processed again at the level of {1 2 3}.)  Therefore,
+ * the restrictinfo list in the join case appears in individual JoinPaths
+ * (field joinrestrictinfo), not in the parent relation.  But it's OK for
+ * the RelOptInfo to store the joininfo lists, because those are the same
+ * for a given rel no matter how we form it.
  */
 
 typedef struct RelOptInfo
@@ -86,7 +99,7 @@ typedef struct RelOptInfo
 	double		tuples;
 
 	/* used by various scans and joins: */
-	List	   *restrictinfo;	/* RestrictInfo structures */
+	List	   *baserestrictinfo; /* RestrictInfo structures (if base rel) */
 	List	   *joininfo;		/* JoinInfo structures */
 	List	   *innerjoin;		/* potential indexscans for nestloop joins */
 	/* innerjoin indexscans are not in the main pathlist because they are
@@ -235,6 +248,10 @@ typedef struct JoinPath
 
 	Path	   *outerjoinpath;	/* path for the outer side of the join */
 	Path	   *innerjoinpath;	/* path for the inner side of the join */
+	List	   *joinrestrictinfo; /* RestrictInfos to apply to join */
+	/* See the notes for RelOptInfo to understand why joinrestrictinfo is
+	 * needed in JoinPath, and can't be merged into the parent RelOptInfo.
+	 */
 } JoinPath;
 
 /*
@@ -289,18 +306,29 @@ typedef struct HashPath
  * without having to evaluate the rest.  The RestrictInfo node itself stores
  * data used by the optimizer while choosing the best query plan.
  *
- * A restriction clause will appear in the restrictinfo list of a RelOptInfo
- * that describes exactly the set of base relations referenced by the
- * restriction clause.  It is not possible to apply the clause at any lower
- * nesting level, and there is little point in delaying its evaluation to
- * higher nesting levels.  (The "predicate migration" code was once intended
- * to push restriction clauses up and down the plan tree, but it's dead code
- * and is unlikely to be resurrected in the foreseeable future.)
+ * If a restriction clause references a single base relation, it will appear
+ * in the baserestrictinfo list of the RelOptInfo for that base rel.
  *
- * If a restriction clause references more than one base rel, it will also
- * appear in the JoinInfo list of every RelOptInfo that describes a strict
+ * If a restriction clause references more than one base rel, it will
+ * appear in the JoinInfo lists of every RelOptInfo that describes a strict
  * subset of the base rels mentioned in the clause.  The JoinInfo lists are
  * used to drive join tree building by selecting plausible join candidates.
+ * The clause cannot actually be applied until we have built a join rel
+ * containing all the base rels it references, however.
+ *
+ * When we construct a join rel that describes exactly the set of base rels
+ * referenced in a multi-relation restriction clause, we place that clause
+ * into the joinrestrictinfo lists of paths for the join rel.  It will be
+ * applied at that join level, and will not propagate any further up the
+ * join tree.  (Note: the "predicate migration" code was once intended to
+ * push restriction clauses up and down the plan tree based on evaluation
+ * costs, but it's dead code and is unlikely to be resurrected in the
+ * foreseeable future.)
+ *
+ * Note that in the presence of more than two rels, a multi-rel restriction
+ * might reach different heights in the join tree depending on the join
+ * sequence we use.  So, these clauses cannot be associated directly with
+ * the join RelOptInfo, but must be kept track of on a per-join-path basis.
  *
  * In general, the referenced clause might be arbitrarily complex.  The
  * kinds of clauses we can handle as indexscan quals, mergejoin clauses,
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 0a6e78d676c..79153c01d83 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: cost.h,v 1.28 2000/01/26 05:58:20 momjian Exp $
+ * $Id: cost.h,v 1.29 2000/02/07 04:41:04 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -55,9 +55,11 @@ extern Cost cost_mergejoin(Path *outer_path, Path *inner_path,
 						   List *outersortkeys, List *innersortkeys);
 extern Cost cost_hashjoin(Path *outer_path, Path *inner_path,
 						  Selectivity innerdisbursion);
-extern void set_rel_rows_width(Query *root, RelOptInfo *rel);
-extern void set_joinrel_rows_width(Query *root, RelOptInfo *rel,
-								   JoinPath *joinpath);
+extern void set_baserel_size_estimates(Query *root, RelOptInfo *rel);
+extern void set_joinrel_size_estimates(Query *root, RelOptInfo *rel,
+									   RelOptInfo *outer_rel,
+									   RelOptInfo *inner_rel,
+									   List *restrictlist);
 
 /*
  * prototypes for clausesel.c
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index a83e743781b..eefb2553b3d 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: pathnode.h,v 1.24 2000/01/26 05:58:20 momjian Exp $
+ * $Id: pathnode.h,v 1.25 2000/02/07 04:41:04 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -21,8 +21,8 @@
  */
 extern bool path_is_cheaper(Path *path1, Path *path2);
 extern Path *set_cheapest(RelOptInfo *parent_rel, List *pathlist);
-extern List *add_pathlist(RelOptInfo *parent_rel, List *old_paths,
-						  List *new_paths);
+extern void add_path(RelOptInfo *parent_rel, Path *new_path);
+extern void add_pathlist(RelOptInfo *parent_rel, List *new_paths);
 
 extern Path *create_seqscan_path(RelOptInfo *rel);
 extern IndexPath *create_index_path(Query *root, RelOptInfo *rel,
@@ -31,25 +31,34 @@ extern IndexPath *create_index_path(Query *root, RelOptInfo *rel,
 extern TidPath *create_tidscan_path(RelOptInfo *rel, List *tideval);
 
 extern NestPath *create_nestloop_path(RelOptInfo *joinrel,
-									  Path *outer_path, Path *inner_path,
+									  Path *outer_path,
+									  Path *inner_path,
+									  List *restrict_clauses,
 									  List *pathkeys);
 
-extern MergePath *create_mergejoin_path(RelOptInfo *joinrel, Path *outer_path,
-										Path *inner_path, List *pathkeys,
+extern MergePath *create_mergejoin_path(RelOptInfo *joinrel,
+										Path *outer_path,
+										Path *inner_path,
+										List *restrict_clauses,
+										List *pathkeys,
 										List *mergeclauses,
 										List *outersortkeys,
 										List *innersortkeys);
 
-extern HashPath *create_hashjoin_path(RelOptInfo *joinrel, Path *outer_path,
-									  Path *inner_path, List *hashclauses,
+extern HashPath *create_hashjoin_path(RelOptInfo *joinrel,
+									  Path *outer_path,
+									  Path *inner_path,
+									  List *restrict_clauses,
+									  List *hashclauses,
 									  Selectivity innerdisbursion);
 
 /*
- * prototypes for rel.c
+ * prototypes for relnode.c
  */
-extern RelOptInfo *rel_member(Relids relid, List *rels);
 extern RelOptInfo *get_base_rel(Query *root, int relid);
-extern RelOptInfo *get_join_rel(Query *root, Relids relid);
+extern RelOptInfo *get_join_rel(Query *root, RelOptInfo *outer_rel,
+								RelOptInfo *inner_rel,
+								List **restrictlist_ptr);
 
 /*
  * prototypes for indexnode.h
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index bcecd4c923c..256aac90d75 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -8,7 +8,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: paths.h,v 1.41 2000/02/06 03:27:35 tgl Exp $
+ * $Id: paths.h,v 1.42 2000/02/07 04:41:04 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -27,15 +27,15 @@
 extern bool enable_geqo;
 extern int	geqo_rels;
 
-extern RelOptInfo *make_one_rel(Query *root, List *rels);
+extern RelOptInfo *make_one_rel(Query *root);
 
 /*
  * indxpath.c
  *	  routines to generate index paths
  */
 extern List *create_index_paths(Query *root, RelOptInfo *rel, List *indices,
-				   List *restrictinfo_list,
-				   List *joininfo_list);
+								List *restrictinfo_list,
+								List *joininfo_list);
 extern Oid indexable_operator(Expr *clause, Oid opclass, Oid relam,
 							  bool indexkey_on_left);
 extern List *extract_or_indexqual_conditions(RelOptInfo *rel,
@@ -60,7 +60,22 @@ extern List *create_tidscan_paths(Query *root, RelOptInfo *rel);
  * joinpath.c
  *	   routines to create join paths
  */
-extern void update_rels_pathlist_for_joins(Query *root, List *joinrels);
+extern void add_paths_to_joinrel(Query *root, RelOptInfo *joinrel,
+								 RelOptInfo *outerrel,
+								 RelOptInfo *innerrel,
+								 List *restrictlist);
+
+/*
+ * joinrels.c
+ *	  routines to determine which relations to join
+ */
+extern void make_rels_by_joins(Query *root, int level);
+extern RelOptInfo *make_rels_by_clause_joins(Query *root,
+											 RelOptInfo *old_rel,
+											 List *other_rels);
+extern RelOptInfo *make_rels_by_clauseless_joins(Query *root,
+												 RelOptInfo *old_rel,
+												 List *other_rels);
 
 /*
  * pathkeys.c
@@ -90,22 +105,4 @@ extern List *find_mergeclauses_for_pathkeys(List *pathkeys,
 extern List *make_pathkeys_for_mergeclauses(List *mergeclauses,
 											List *tlist);
 
-/*
- * joinrels.c
- *	  routines to determine which relations to join
- */
-extern List *make_rels_by_joins(Query *root, List *old_rels);
-extern List *make_rels_by_clause_joins(Query *root, RelOptInfo *old_rel,
-						  List *joininfo_list, Relids only_relids);
-extern List *make_rels_by_clauseless_joins(RelOptInfo *old_rel,
-							  List *inner_rels);
-extern RelOptInfo *get_cheapest_complete_rel(List *join_rel_list);
-
-/*
- * prune.c
- */
-extern void merge_rels_with_same_relids(List *rel_list);
-extern void rels_set_cheapest(Query *root, List *rel_list);
-extern List *del_rels_all_bushy_inactive(List *old_rels);
-
 #endif	 /* PATHS_H */