New cost model for planning, incorporating a penalty for random page

accesses versus sequential accesses, a (very crude) estimate of the
effects of caching on random page accesses, and cost to evaluate WHERE-
clause expressions.  Export critical parameters for this model as SET
variables.  Also, create SET variables for the planner's enable flags
(enable_seqscan, enable_indexscan, etc) so that these can be controlled
more conveniently than via PGOPTIONS.

Planner now estimates both startup cost (cost before retrieving
first tuple) and total cost of each path, so it can optimize queries
with LIMIT on a reasonable basis by interpolating between these costs.
Same facility is a win for EXISTS(...) subqueries and some other cases.

Redesign pathkey representation to achieve a major speedup in planning
(I saw as much as 5X on a 10-way join); also minor changes in planner
to reduce memory consumption by recycling discarded Path nodes and
not constructing unnecessary lists.

Minor cleanups to display more-plausible costs in some cases in
EXPLAIN output.

Initdb forced by change in interface to index cost estimation
functions.

12 files changed, 133 insertions, 70 deletions

diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h
index d6d8ff6ffba..bf93830ca21 100644
--- a/src/include/catalog/catversion.h
+++ b/src/include/catalog/catversion.h
@@ -37,7 +37,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: catversion.h,v 1.13 2000/01/27 18:11:40 tgl Exp $
+ * $Id: catversion.h,v 1.14 2000/02/15 20:49:23 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -53,6 +53,6 @@
  */
 
 /*                          yyyymmddN */
-#define CATALOG_VERSION_NO  200001271
+#define CATALOG_VERSION_NO  200002151
 
 #endif
diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.h
index 064232d62cc..87107b1df36 100644
--- a/src/include/catalog/pg_proc.h
+++ b/src/include/catalog/pg_proc.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: pg_proc.h,v 1.120 2000/02/10 19:51:46 momjian Exp $
+ * $Id: pg_proc.h,v 1.121 2000/02/15 20:49:23 tgl Exp $
  *
  * NOTES
  *	  The script catalog/genbki.sh reads this file and generates .bki
@@ -212,9 +212,9 @@ DESCR("not equal");
 DATA(insert OID =  89 (  version		   PGUID 11 f t f 0 f 25 "" 100 0 0 100 version - ));
 DESCR("PostgreSQL version string");
 
-DATA(insert OID = 1265 (  rtcostestimate   PGUID 11 f t f 6 f 0 "0 0 0 0 0 0" 100 0 0 100  rtcostestimate - ));
+DATA(insert OID = 1265 (  rtcostestimate   PGUID 11 f t f 7 f 0 "0 0 0 0 0 0 0" 100 0 0 100  rtcostestimate - ));
 DESCR("r-tree cost estimator");
-DATA(insert OID = 1268 (  btcostestimate   PGUID 11 f t f 6 f 0 "0 0 0 0 0 0" 100 0 0 100  btcostestimate - ));
+DATA(insert OID = 1268 (  btcostestimate   PGUID 11 f t f 7 f 0 "0 0 0 0 0 0 0" 100 0 0 100  btcostestimate - ));
 DESCR("btree cost estimator");
 
 /* OIDS 100 - 199 */
@@ -796,7 +796,7 @@ DESCR("convert name to char()");
 DATA(insert OID =  409 (  bpchar_name	   PGUID 11 f t t 1 f	19 "1042" 100 0 0 100	bpchar_name - ));
 DESCR("convert char() to name");
 
-DATA(insert OID =  438 (  hashcostestimate PGUID 11 f t f 6 f 0 "0 0 0 0 0 0" 100 0 0 100  hashcostestimate - ));
+DATA(insert OID =  438 (  hashcostestimate PGUID 11 f t f 7 f 0 "0 0 0 0 0 0 0" 100 0 0 100  hashcostestimate - ));
 DESCR("hash index cost estimator");
 
 DATA(insert OID = 440 (  hashgettuple	   PGUID 11 f t f 2 f 23 "0" 100 0 0 100  hashgettuple - ));
@@ -1031,7 +1031,7 @@ DESCR("larger of two");
 DATA(insert OID = 771 (  int2smaller	   PGUID 11 f t t 2 f 21 "21 21" 100 0 0 100  int2smaller - ));
 DESCR("smaller of two");
 
-DATA(insert OID = 772 (  gistcostestimate  PGUID 11 f t f 6 f 0 "0 0 0 0 0 0" 100 0 0 100  gistcostestimate - ));
+DATA(insert OID = 772 (  gistcostestimate  PGUID 11 f t f 7 f 0 "0 0 0 0 0 0 0" 100 0 0 100  gistcostestimate - ));
 DESCR("gist cost estimator");
 DATA(insert OID = 774 (  gistgettuple	   PGUID 11 f t f 2 f 23 "0" 100 0 0 100  gistgettuple - ));
 DESCR("gist(internal)");
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index c1d6c4c1ca5..161b53c25af 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: nodes.h,v 1.63 2000/01/26 05:58:16 momjian Exp $
+ * $Id: nodes.h,v 1.64 2000/02/15 20:49:24 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -257,6 +257,9 @@ typedef struct Node
 	(IsA(t, Noname) || IsA(t, Material) || IsA(t, Sort) || \
 	 IsA(t, Unique))
 
+#define IsA_Value(t) \
+	(IsA(t, Integer) || IsA(t, Float) || IsA(t, String))
+
 /* ----------------------------------------------------------------
  *					  extern declarations follow
  * ----------------------------------------------------------------
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index 6eb47618c5e..df7bec10f00 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: parsenodes.h,v 1.98 2000/02/15 03:38:14 thomas Exp $
+ * $Id: parsenodes.h,v 1.99 2000/02/15 20:49:24 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -72,6 +72,7 @@ typedef struct Query
 	/* internal to planner */
 	List	   *base_rel_list;	/* list of base-relation RelOptInfos */
 	List	   *join_rel_list;	/* list of join-relation RelOptInfos */
+	List	   *equi_key_list;	/* list of lists of equijoined PathKeyItems */
 	List	   *query_pathkeys; /* pathkeys for query_planner()'s result */
 } Query;
 
@@ -1124,7 +1125,6 @@ typedef struct RangeTblEntry
 {
 	NodeTag		type;
 	char	   *relname;		/* real name of the relation */
-//	char	   *refname;		/* reference name (given in FROM clause) */
 #ifndef DISABLE_JOIN_SYNTAX
 	Attr	   *ref;			/* reference names (given in FROM clause) */
 #endif
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index ff83431e580..2731c57948c 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: plannodes.h,v 1.37 2000/01/27 18:11:44 tgl Exp $
+ * $Id: plannodes.h,v 1.38 2000/02/15 20:49:25 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -65,10 +65,15 @@ typedef struct Plan
 {
 	NodeTag		type;
 
-	/* planner's estimates of cost and result size */
-	Cost		cost;
-	double		plan_rows;
-	int			plan_width;
+	/* estimated execution costs for plan (see costsize.c for more info) */
+	Cost		startup_cost;	/* cost expended before fetching any tuples */
+	Cost		total_cost;		/* total cost (assuming all tuples fetched) */
+
+	/* planner's estimate of result size (note: LIMIT, if any, is not
+	 * considered in setting plan_rows)
+	 */
+	double		plan_rows;		/* number of rows plan is expected to emit */
+	int			plan_width;		/* average row width in bytes */
 
 	EState	   *state;			/* at execution time, state's of
 								 * individual nodes point to one EState
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 529aa5cea7a..3efdaa5b325 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -7,13 +7,14 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: relation.h,v 1.43 2000/02/07 04:41:02 tgl Exp $
+ * $Id: relation.h,v 1.44 2000/02/15 20:49:25 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
 #ifndef RELATION_H
 #define RELATION_H
 
+#include "access/sdir.h"
 #include "nodes/parsenodes.h"
 
 /*
@@ -26,6 +27,12 @@
 typedef List *Relids;
 
 /*
+ * When looking for a "cheapest path", this enum specifies whether we want
+ * cheapest startup cost or cheapest total cost.
+ */
+typedef enum CostSelector { STARTUP_COST, TOTAL_COST } CostSelector;
+
+/*
  * RelOptInfo
  *		Per-relation information for planning/optimization
  *
@@ -38,10 +45,14 @@ typedef List *Relids;
  *			   clauses have been applied (ie, output rows of a plan for it)
  *		width - avg. number of bytes per tuple in the relation after the
  *				appropriate projections have been done (ie, output width)
- *		targetlist - List of TargetList nodes
+ *		targetlist - List of TargetEntry nodes for the attributes we need
+ *					 to output from this relation
  *		pathlist - List of Path nodes, one for each potentially useful
  *				   method of generating the relation
- *		cheapestpath -	least expensive Path (regardless of ordering)
+ *		cheapest_startup_path - the pathlist member with lowest startup cost
+ *								(regardless of its ordering)
+ *		cheapest_total_path - the pathlist member with lowest total cost
+ *							  (regardless of its ordering)
  *		pruneable - flag to let the planner know whether it can prune the
  *					pathlist of this RelOptInfo or not.
  *
@@ -57,6 +68,8 @@ typedef List *Relids;
  *		baserestrictinfo - List of RestrictInfo nodes, containing info about
  *					each qualification clause in which this relation
  *					participates (only used for base rels)
+ *		baserestrictcost - Estimated cost of evaluating the baserestrictinfo
+ *					clauses at a single tuple (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
@@ -74,6 +87,10 @@ typedef List *Relids;
  * (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.
+ *
+ * We store baserestrictcost in the RelOptInfo (for base relations) because
+ * we know we will need it at least once (to price the sequential scan)
+ * and may need it multiple times to price index scans.
  */
 
 typedef struct RelOptInfo
@@ -90,7 +107,8 @@ typedef struct RelOptInfo
 	/* materialization information */
 	List	   *targetlist;
 	List	   *pathlist;		/* Path structures */
-	struct Path *cheapestpath;
+	struct Path *cheapest_startup_path;
+	struct Path *cheapest_total_path;
 	bool		pruneable;
 
 	/* statistics from pg_class (only valid if it's a base rel!) */
@@ -100,6 +118,7 @@ typedef struct RelOptInfo
 
 	/* used by various scans and joins: */
 	List	   *baserestrictinfo; /* RestrictInfo structures (if base rel) */
+	Cost		baserestrictcost; /* cost of evaluating the above */
 	List	   *joininfo;		/* JoinInfo structures */
 	List	   *innerjoin;		/* potential indexscans for nestloop joins */
 	/* innerjoin indexscans are not in the main pathlist because they are
@@ -126,6 +145,7 @@ typedef struct RelOptInfo
  *		amcostestimate - OID of the relam's cost estimator
  *		indproc	  - OID of the function if a functional index, else 0
  *		indpred	  - index predicate if a partial index, else NULL
+ *		lossy	  - true if index is lossy (may return non-matching tuples)
  *
  *		NB. the last element of the arrays classlist, indexkeys and ordering
  *			is always 0.
@@ -151,6 +171,7 @@ typedef struct IndexOptInfo
 
 	Oid			indproc;		/* if a functional index */
 	List	   *indpred;		/* if a partial index */
+	bool		lossy;			/* if a lossy index */
 } IndexOptInfo;
 
 /*
@@ -190,7 +211,9 @@ typedef struct Path
 
 	RelOptInfo *parent;			/* the relation this path can build */
 
-	Cost		path_cost;		/* estimated execution cost of path */
+	/* estimated execution costs for path (see costsize.c for more info) */
+	Cost		startup_cost;	/* cost expended before fetching any tuples */
+	Cost		total_cost;		/* total cost (assuming all tuples fetched) */
 
 	NodeTag		pathtype;		/* tag identifying scan/join method */
 	/* XXX why is pathtype separate from the NodeTag? */
@@ -207,27 +230,34 @@ typedef struct Path
  * the same tuple more than once, even if it is matched in multiple scans.)
  *
  * 'indexid' is a list of index relation OIDs, one per scan to be performed.
+ *
  * 'indexqual' is a list of index qualifications, also one per scan.
  * Each entry in 'indexqual' is a sublist of qualification expressions with
  * implicit AND semantics across the sublist items.  Only expressions that
  * are usable as indexquals (as determined by indxpath.c) may appear here.
- *
  * NOTE that the semantics of the top-level list in 'indexqual' is OR
  * combination, while the sublists are implicitly AND combinations!
+ *
+ * 'indexscandir' is one of:
+ *		ForwardScanDirection: forward scan of an ordered index
+ *		BackwardScanDirection: backward scan of an ordered index
+ *		NoMovementScanDirection: scan of an unordered index, or don't care
+ * (The executor doesn't care whether it gets ForwardScanDirection or
+ * NoMovementScanDirection for an indexscan, but the planner wants to
+ * distinguish ordered from unordered indexes for building pathkeys.)
+ *
+ * 'joinrelids' is only used in IndexPaths that are constructed for use
+ * as the inner path of a nestloop join.  These paths have indexquals
+ * that refer to values of other rels, so those other rels must be
+ * included in the outer joinrel in order to make a usable join.
  *----------
  */
-
 typedef struct IndexPath
 {
 	Path		path;
 	List	   *indexid;
 	List	   *indexqual;
-	/*
-	 * joinrelids is only used in IndexPaths that are constructed for use
-	 * as the inner path of a nestloop join.  These paths have indexquals
-	 * that refer to values of other rels, so those other rels must be
-	 * included in the outer joinrel in order to make a usable join.
-	 */
+	ScanDirection indexscandir;
 	Relids		joinrelids;			/* other rels mentioned in indexqual */
 } IndexPath;
 
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 79153c01d83..960a2ea9e9a 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.29 2000/02/07 04:41:04 tgl Exp $
+ * $Id: cost.h,v 1.30 2000/02/15 20:49:25 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -17,9 +17,12 @@
 #include "nodes/relation.h"
 
 /* defaults for costsize.c's Cost parameters */
-/* NB: cost-estimation code should use the variables, not the constants! */
-#define CPU_PAGE_WEIGHT  0.033
-#define CPU_INDEX_PAGE_WEIGHT  0.017
+/* NB: cost-estimation code should use the variables, not these constants! */
+#define DEFAULT_EFFECTIVE_CACHE_SIZE  1000.0	/* measured in pages */
+#define DEFAULT_RANDOM_PAGE_COST  4.0
+#define DEFAULT_CPU_TUPLE_COST  0.01
+#define DEFAULT_CPU_INDEX_TUPLE_COST 0.001
+#define DEFAULT_CPU_OPERATOR_COST  0.0025
 
 /* defaults for function attributes used for expensive function calculations */
 #define BYTE_PCT 100
@@ -33,8 +36,12 @@
  *	  routines to compute costs and sizes
  */
 
-extern Cost cpu_page_weight;
-extern Cost cpu_index_page_weight;
+/* parameter variables and flags */
+extern double effective_cache_size;
+extern Cost random_page_cost;
+extern Cost cpu_tuple_cost;
+extern Cost cpu_index_tuple_cost;
+extern Cost cpu_operator_cost;
 extern Cost disable_cost;
 extern bool enable_seqscan;
 extern bool enable_indexscan;
@@ -44,17 +51,20 @@ extern bool enable_nestloop;
 extern bool enable_mergejoin;
 extern bool enable_hashjoin;
 
-extern Cost cost_seqscan(RelOptInfo *baserel);
-extern Cost cost_index(Query *root, RelOptInfo *baserel, IndexOptInfo *index,
+extern void cost_seqscan(Path *path, RelOptInfo *baserel);
+extern void cost_index(Path *path, Query *root,
+					   RelOptInfo *baserel, IndexOptInfo *index,
 					   List *indexQuals, bool is_injoin);
-extern Cost cost_tidscan(RelOptInfo *baserel, List *tideval);
-extern Cost cost_sort(List *pathkeys, double tuples, int width);
-extern Cost cost_nestloop(Path *outer_path, Path *inner_path,
-						  bool is_indexjoin);
-extern Cost cost_mergejoin(Path *outer_path, Path *inner_path,
+extern void cost_tidscan(Path *path, RelOptInfo *baserel, List *tideval);
+extern void cost_sort(Path *path, List *pathkeys, double tuples, int width);
+extern void cost_nestloop(Path *path, Path *outer_path, Path *inner_path,
+						  List *restrictlist, bool is_indexjoin);
+extern void cost_mergejoin(Path *path, Path *outer_path, Path *inner_path,
+						   List *restrictlist,
 						   List *outersortkeys, List *innersortkeys);
-extern Cost cost_hashjoin(Path *outer_path, Path *inner_path,
-						  Selectivity innerdisbursion);
+extern void cost_hashjoin(Path *path, Path *outer_path, Path *inner_path,
+						  List *restrictlist, Selectivity innerdisbursion);
+extern Cost cost_qual_eval(List *quals);
 extern void set_baserel_size_estimates(Query *root, RelOptInfo *rel);
 extern void set_joinrel_size_estimates(Query *root, RelOptInfo *rel,
 									   RelOptInfo *outer_rel,
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index eefb2553b3d..e59848278f4 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.25 2000/02/07 04:41:04 tgl Exp $
+ * $Id: pathnode.h,v 1.26 2000/02/15 20:49:26 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -19,15 +19,18 @@
 /*
  * prototypes for pathnode.c
  */
-extern bool path_is_cheaper(Path *path1, Path *path2);
-extern Path *set_cheapest(RelOptInfo *parent_rel, List *pathlist);
+extern int compare_path_costs(Path *path1, Path *path2,
+							  CostSelector criterion);
+extern int compare_fractional_path_costs(Path *path1, Path *path2,
+										 double fraction);
+extern void set_cheapest(RelOptInfo *parent_rel);
 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,
 									IndexOptInfo *index,
-									List *restriction_clauses);
+									List *restriction_clauses,
+									ScanDirection indexscandir);
 extern TidPath *create_tidscan_path(RelOptInfo *rel, List *tideval);
 
 extern NestPath *create_nestloop_path(RelOptInfo *joinrel,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 256aac90d75..d7a0cc2d546 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.42 2000/02/07 04:41:04 tgl Exp $
+ * $Id: paths.h,v 1.43 2000/02/15 20:49:26 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -33,9 +33,9 @@ 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);
+extern void create_index_paths(Query *root, RelOptInfo *rel, List *indices,
+							   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,
@@ -47,14 +47,14 @@ extern List *expand_indexqual_conditions(List *indexquals);
  * orindxpath.c
  *	  additional routines for indexable OR clauses
  */
-extern List *create_or_index_paths(Query *root, RelOptInfo *rel,
-								   List *clauses);
+extern void create_or_index_paths(Query *root, RelOptInfo *rel,
+								  List *clauses);
 
 /*
  * tidpath.h
  *	  routines to generate tid paths
  */
-extern List *create_tidscan_paths(Query *root, RelOptInfo *rel);
+extern void create_tidscan_paths(Query *root, RelOptInfo *rel);
 
 /*
  * joinpath.c
@@ -89,20 +89,27 @@ typedef enum
 	PATHKEYS_DIFFERENT			/* neither pathkey includes the other */
 } PathKeysComparison;
 
+extern void add_equijoined_keys(Query *root, RestrictInfo *restrictinfo);
+extern List *canonicalize_pathkeys(Query *root, List *pathkeys);
 extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);
 extern bool pathkeys_contained_in(List *keys1, List *keys2);
 extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
-											bool indexpaths_only);
+											CostSelector cost_criterion);
+extern Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
+													   List *pathkeys,
+													   double fraction);
 extern List *build_index_pathkeys(Query *root, RelOptInfo *rel,
-								  IndexOptInfo *index);
+								  IndexOptInfo *index,
+								  ScanDirection scandir);
 extern List *build_join_pathkeys(List *outer_pathkeys,
-								 List *join_rel_tlist, List *joinclauses);
-extern bool commute_pathkeys(List *pathkeys);
+								 List *join_rel_tlist,
+								 List *equi_key_list);
 extern List *make_pathkeys_for_sortclauses(List *sortclauses,
 										   List *tlist);
 extern List *find_mergeclauses_for_pathkeys(List *pathkeys,
 											List *restrictinfos);
-extern List *make_pathkeys_for_mergeclauses(List *mergeclauses,
+extern List *make_pathkeys_for_mergeclauses(Query *root,
+											List *mergeclauses,
 											List *tlist);
 
 #endif	 /* PATHS_H */
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 340f54485cb..2d61a035bf8 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: planmain.h,v 1.37 2000/01/27 18:11:45 tgl Exp $
+ * $Id: planmain.h,v 1.38 2000/02/15 20:49:26 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -20,7 +20,8 @@
 /*
  * prototypes for plan/planmain.c
  */
-extern Plan *query_planner(Query *root, List *tlist, List *qual);
+extern Plan *query_planner(Query *root, List *tlist, List *qual,
+						   double tuple_fraction);
 
 /*
  * prototypes for plan/createplan.c
@@ -29,7 +30,7 @@ extern Plan *create_plan(Query *root, Path *best_path);
 extern SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid);
 extern Sort *make_sort(List *tlist, Oid nonameid, Plan *lefttree,
 		  int keycount);
-extern Agg *make_agg(List *tlist, Plan *lefttree);
+extern Agg *make_agg(List *tlist, List *qual, Plan *lefttree);
 extern Group *make_group(List *tlist, bool tuplePerGroup, int ngrp,
 		   AttrNumber *grpColIdx, Plan *lefttree);
 extern Noname *make_noname(List *tlist, List *pathkeys, Plan *subplan);
diff --git a/src/include/optimizer/planner.h b/src/include/optimizer/planner.h
index 00a6e55dfd0..c06f41b852e 100644
--- a/src/include/optimizer/planner.h
+++ b/src/include/optimizer/planner.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: planner.h,v 1.13 2000/01/26 05:58:21 momjian Exp $
+ * $Id: planner.h,v 1.14 2000/02/15 20:49:26 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -21,7 +21,7 @@
 #include "nodes/plannodes.h"
 
 extern Plan *planner(Query *parse);
-extern Plan *union_planner(Query *parse);
+extern Plan *union_planner(Query *parse, double tuple_fraction);
 extern void pg_checkretval(Oid rettype, List *querytree_list);
 
 #endif	 /* PLANNER_H */
diff --git a/src/include/utils/builtins.h b/src/include/utils/builtins.h
index cb7ab0e8027..7f9dcc6c469 100644
--- a/src/include/utils/builtins.h
+++ b/src/include/utils/builtins.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: builtins.h,v 1.100 2000/02/10 19:51:52 momjian Exp $
+ * $Id: builtins.h,v 1.101 2000/02/15 20:49:27 tgl Exp $
  *
  * NOTES
  *	  This should normally only be included by fmgr.h.
@@ -403,19 +403,23 @@ extern bool convert_to_scalar(Datum value, Oid typid, double *scaleval);
 
 extern void btcostestimate(Query *root, RelOptInfo *rel,
 						   IndexOptInfo *index, List *indexQuals,
-						   Cost *indexAccessCost,
+						   Cost *indexStartupCost,
+						   Cost *indexTotalCost,
 						   Selectivity *indexSelectivity);
 extern void rtcostestimate(Query *root, RelOptInfo *rel,
 						   IndexOptInfo *index, List *indexQuals,
-						   Cost *indexAccessCost,
+						   Cost *indexStartupCost,
+						   Cost *indexTotalCost,
 						   Selectivity *indexSelectivity);
 extern void hashcostestimate(Query *root, RelOptInfo *rel,
 							 IndexOptInfo *index, List *indexQuals,
-							 Cost *indexAccessCost,
+							 Cost *indexStartupCost,
+							 Cost *indexTotalCost,
 							 Selectivity *indexSelectivity);
 extern void gistcostestimate(Query *root, RelOptInfo *rel,
 							 IndexOptInfo *index, List *indexQuals,
-							 Cost *indexAccessCost,
+							 Cost *indexStartupCost,
+							 Cost *indexTotalCost,
 							 Selectivity *indexSelectivity);
 
 /* tid.c */