Planner speedup hacking. Avoid saving useless pathkeys, so that path

comparison does not consider paths different when they differ only in
uninteresting aspects of sort order.  (We had a special case of this
consideration for indexscans already, but generalize it to apply to
ordered join paths too.)  Be stricter about what is a canonical pathkey
to allow faster pathkey comparison.  Cache canonical pathkeys and
dispersion stats for left and right sides of a RestrictInfo's clause,
to avoid repeated computation.  Total speedup will depend on number of
tables in a query, but I see about 4x speedup of planning phase for
a sample seven-table query.

2 files changed, 20 insertions, 10 deletions

diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 993003eaa2f..11a6b184ebc 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.31 2000/11/12 00:37:01 tgl Exp $
+ * $Id: pathnode.h,v 1.32 2000/12/14 22:30:45 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -30,6 +30,7 @@ extern Path *create_seqscan_path(RelOptInfo *rel);
 extern IndexPath *create_index_path(Query *root, RelOptInfo *rel,
 				  IndexOptInfo *index,
 				  List *restriction_clauses,
+				  List *pathkeys,
 				  ScanDirection indexscandir);
 extern TidPath *create_tidscan_path(RelOptInfo *rel, List *tideval);
 extern AppendPath *create_append_path(RelOptInfo *rel, List *subpaths);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 327e63dd694..167bea427ef 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.48 2000/09/29 18:21:40 tgl Exp $
+ * $Id: paths.h,v 1.49 2000/12/14 22:30:45 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -34,9 +34,7 @@ extern RelOptInfo *make_fromexpr_rel(Query *root, FromExpr *from);
  * indxpath.c
  *	  routines to generate index paths
  */
-extern void 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);
 extern Oid indexable_operator(Expr *clause, Oid opclass, Oid relam,
 				   bool indexkey_on_left);
 extern List *extract_or_indexqual_conditions(RelOptInfo *rel,
@@ -97,6 +95,9 @@ extern void generate_implied_equalities(Query *root);
 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 PathKeysComparison compare_noncanonical_pathkeys(List *keys1,
+														List *keys2);
+extern bool noncanonical_pathkeys_contained_in(List *keys1, List *keys2);
 extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
 							   CostSelector cost_criterion);
 extern Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
@@ -105,15 +106,23 @@ extern Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
 extern List *build_index_pathkeys(Query *root, RelOptInfo *rel,
 					 IndexOptInfo *index,
 					 ScanDirection scandir);
-extern List *build_join_pathkeys(List *outer_pathkeys,
-					List *join_rel_tlist,
-					List *equi_key_list);
+extern List *build_join_pathkeys(Query *root,
+								 RelOptInfo *joinrel,
+								 List *outer_pathkeys);
 extern List *make_pathkeys_for_sortclauses(List *sortclauses,
 							  List *tlist);
-extern List *find_mergeclauses_for_pathkeys(List *pathkeys,
-							   List *restrictinfos);
+extern List *find_mergeclauses_for_pathkeys(Query *root,
+											List *pathkeys,
+											List *restrictinfos);
 extern List *make_pathkeys_for_mergeclauses(Query *root,
 											List *mergeclauses,
 											RelOptInfo *rel);
+extern int	pathkeys_useful_for_merging(Query *root,
+										RelOptInfo *rel,
+										List *pathkeys);
+extern int	pathkeys_useful_for_ordering(Query *root, List *pathkeys);
+extern List *truncate_useless_pathkeys(Query *root,
+									   RelOptInfo *rel,
+									   List *pathkeys);
 
 #endif	 /* PATHS_H */