Refactor planner's pathkeys data structure to create a separate, explicit

representation of equivalence classes of variables.  This is an extensive
rewrite, but it brings a number of benefits:
* planner no longer fails in the presence of "incomplete" operator families
that don't offer operators for every possible combination of datatypes.
* avoid generating and then discarding redundant equality clauses.
* remove bogus assumption that derived equalities always use operators
named "=".
* mergejoins can work with a variety of sort orders (e.g., descending) now,
instead of tying each mergejoinable operator to exactly one sort order.
* better recognition of redundant sort columns.
* can make use of equalities appearing underneath an outer join.

5 files changed, 69 insertions, 30 deletions

diff --git a/src/include/optimizer/joininfo.h b/src/include/optimizer/joininfo.h
index d491a368eb6..f7c4bc07d39 100644
--- a/src/include/optimizer/joininfo.h
+++ b/src/include/optimizer/joininfo.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/joininfo.h,v 1.33 2007/01/05 22:19:56 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/joininfo.h,v 1.34 2007/01/20 20:45:40 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -23,8 +23,5 @@ extern bool have_relevant_joinclause(PlannerInfo *root,
 extern void add_join_clause_to_rels(PlannerInfo *root,
 						RestrictInfo *restrictinfo,
 						Relids join_relids);
-extern void remove_join_clause_from_rels(PlannerInfo *root,
-							 RestrictInfo *restrictinfo,
-							 Relids join_relids);
 
 #endif   /* JOININFO_H */
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index fd5c78372ec..98a73ebc4ee 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/pathnode.h,v 1.75 2007/01/10 18:06:04 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/pathnode.h,v 1.76 2007/01/20 20:45:40 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -71,9 +71,6 @@ extern MergePath *create_mergejoin_path(PlannerInfo *root,
 					  List *restrict_clauses,
 					  List *pathkeys,
 					  List *mergeclauses,
-					  Oid *mergefamilies,
-					  int *mergestrategies,
-					  bool *mergenullsfirst,
 					  List *outersortkeys,
 					  List *innersortkeys);
 
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 14baf430a06..7e7eb15469e 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/paths.h,v 1.94 2007/01/05 22:19:56 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/paths.h,v 1.95 2007/01/20 20:45:40 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -52,6 +52,9 @@ extern List *group_clauses_by_indexkey(IndexOptInfo *index,
 						  Relids outer_relids,
 						  SaOpControl saop_control,
 						  bool *found_clause);
+extern bool eclass_matches_any_index(EquivalenceClass *ec,
+									 EquivalenceMember *em,
+									 RelOptInfo *rel);
 extern bool match_index_to_operand(Node *operand, int indexcol,
 					   IndexOptInfo *index);
 extern List *expand_indexqual_conditions(IndexOptInfo *index,
@@ -90,6 +93,37 @@ extern RelOptInfo *make_join_rel(PlannerInfo *root,
 			  RelOptInfo *rel1, RelOptInfo *rel2);
 
 /*
+ * equivclass.c
+ *	  routines for managing EquivalenceClasses
+ */
+extern bool process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo,
+								bool below_outer_join);
+extern void reconsider_outer_join_clauses(PlannerInfo *root);
+extern EquivalenceClass *get_eclass_for_sort_expr(PlannerInfo *root,
+						 Expr *expr,
+						 Oid expr_datatype,
+						 List *opfamilies);
+extern void generate_base_implied_equalities(PlannerInfo *root);
+extern List *generate_join_implied_equalities(PlannerInfo *root,
+											  RelOptInfo *joinrel,
+											  RelOptInfo *outer_rel,
+											  RelOptInfo *inner_rel);
+extern bool exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2);
+extern void add_child_rel_equivalences(PlannerInfo *root,
+									   AppendRelInfo *appinfo,
+									   RelOptInfo *parent_rel,
+									   RelOptInfo *child_rel);
+extern List *find_eclass_clauses_for_index_join(PlannerInfo *root,
+												RelOptInfo *rel,
+												Relids outer_relids);
+extern bool have_relevant_eclass_joinclause(PlannerInfo *root,
+								RelOptInfo *rel1, RelOptInfo *rel2);
+extern bool has_relevant_eclass_joinclause(PlannerInfo *root,
+										   RelOptInfo *rel1);
+extern bool eclass_useful_for_merging(EquivalenceClass *eclass,
+									  RelOptInfo *rel);
+
+/*
  * pathkeys.c
  *	  utilities for matching and building path keys
  */
@@ -101,9 +135,6 @@ typedef enum
 	PATHKEYS_DIFFERENT			/* neither pathkey includes the other */
 } PathKeysComparison;
 
-extern void add_equijoined_keys(PlannerInfo *root, RestrictInfo *restrictinfo);
-extern bool exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2);
-extern void generate_implied_equalities(PlannerInfo *root);
 extern List *canonicalize_pathkeys(PlannerInfo *root, List *pathkeys);
 extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);
 extern bool pathkeys_contained_in(List *keys1, List *keys2);
@@ -113,23 +144,29 @@ extern Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
 										  List *pathkeys,
 										  double fraction);
 extern List *build_index_pathkeys(PlannerInfo *root, IndexOptInfo *index,
-					 ScanDirection scandir, bool canonical);
+					 ScanDirection scandir);
 extern List *convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
 						  List *subquery_pathkeys);
 extern List *build_join_pathkeys(PlannerInfo *root,
 					RelOptInfo *joinrel,
 					JoinType jointype,
 					List *outer_pathkeys);
-extern List *make_pathkeys_for_sortclauses(List *sortclauses,
-							  List *tlist);
-extern void cache_mergeclause_pathkeys(PlannerInfo *root,
+extern List *make_pathkeys_for_sortclauses(PlannerInfo *root,
+							  List *sortclauses,
+							  List *tlist,
+							  bool canonicalize);
+extern void cache_mergeclause_eclasses(PlannerInfo *root,
 						   RestrictInfo *restrictinfo);
 extern List *find_mergeclauses_for_pathkeys(PlannerInfo *root,
 							   List *pathkeys,
+							   bool outer_keys,
 							   List *restrictinfos);
-extern List *make_pathkeys_for_mergeclauses(PlannerInfo *root,
-							   List *mergeclauses,
-							   RelOptInfo *rel);
+extern List *select_outer_pathkeys_for_merge(PlannerInfo *root,
+											 List *mergeclauses,
+											 RelOptInfo *joinrel);
+extern List *make_inner_pathkeys_for_merge(PlannerInfo *root,
+										   List *mergeclauses,
+										   List *outer_pathkeys);
 extern int pathkeys_useful_for_merging(PlannerInfo *root,
 							RelOptInfo *rel,
 							List *pathkeys);
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 0f6799338bb..5118061182a 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/planmain.h,v 1.97 2007/01/10 18:06:04 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/planmain.h,v 1.98 2007/01/20 20:45:40 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -38,6 +38,8 @@ extern Plan *create_plan(PlannerInfo *root, Path *best_path);
 extern SubqueryScan *make_subqueryscan(List *qptlist, List *qpqual,
 				  Index scanrelid, Plan *subplan);
 extern Append *make_append(List *appendplans, bool isTarget, List *tlist);
+extern Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree,
+						List *pathkeys);
 extern Sort *make_sort_from_sortclauses(PlannerInfo *root, List *sortcls,
 						   Plan *lefttree);
 extern Sort *make_sort_from_groupcols(PlannerInfo *root, List *groupcls,
@@ -69,12 +71,22 @@ extern int	join_collapse_limit;
 
 extern void add_base_rels_to_query(PlannerInfo *root, Node *jtnode);
 extern void build_base_rel_tlists(PlannerInfo *root, List *final_tlist);
+extern void add_vars_to_targetlist(PlannerInfo *root, List *vars,
+								   Relids where_needed);
 extern List *deconstruct_jointree(PlannerInfo *root);
+extern void distribute_restrictinfo_to_rels(PlannerInfo *root,
+											RestrictInfo *restrictinfo);
 extern void process_implied_equality(PlannerInfo *root,
-						 Node *item1, Node *item2,
-						 Oid sortop1, Oid sortop2,
-						 Relids item1_relids, Relids item2_relids,
-						 bool delete_it);
+									 Oid opno,
+									 Expr *item1,
+									 Expr *item2,
+									 Relids qualscope,
+									 bool below_outer_join,
+									 bool both_const);
+extern RestrictInfo *build_implied_join_equality(Oid opno,
+							Expr *item1,
+							Expr *item2,
+							Relids qualscope);
 
 /*
  * prototypes for plan/setrefs.c
diff --git a/src/include/optimizer/restrictinfo.h b/src/include/optimizer/restrictinfo.h
index 619e7cef398..272c5a67037 100644
--- a/src/include/optimizer/restrictinfo.h
+++ b/src/include/optimizer/restrictinfo.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/restrictinfo.h,v 1.39 2007/01/05 22:19:56 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/restrictinfo.h,v 1.40 2007/01/20 20:45:40 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -32,12 +32,8 @@ extern List *extract_actual_clauses(List *restrictinfo_list,
 extern void extract_actual_join_clauses(List *restrictinfo_list,
 							List **joinquals,
 							List **otherquals);
-extern List *remove_redundant_join_clauses(PlannerInfo *root,
-							  List *restrictinfo_list,
-							  bool isouterjoin);
 extern List *select_nonredundant_join_clauses(PlannerInfo *root,
 								 List *restrictinfo_list,
-								 List *reference_list,
-								 bool isouterjoin);
+								 List *reference_list);
 
 #endif   /* RESTRICTINFO_H */