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.

8 files changed, 218 insertions, 89 deletions

diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index be151ac9f30..d3e84bdf69a 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.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/nodes/nodes.h,v 1.191 2007/01/05 22:19:55 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/nodes.h,v 1.192 2007/01/20 20:45:40 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -190,7 +190,9 @@ typedef enum NodeTag
 	T_ResultPath,
 	T_MaterialPath,
 	T_UniquePath,
-	T_PathKeyItem,
+	T_EquivalenceClass,
+	T_EquivalenceMember,
+	T_PathKey,
 	T_RestrictInfo,
 	T_InnerIndexscanInfo,
 	T_OuterJoinInfo,
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index f7900377398..a83a20d21b5 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.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/nodes/relation.h,v 1.132 2007/01/10 18:06:04 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.133 2007/01/20 20:45:40 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -69,7 +69,7 @@ typedef struct PlannerInfo
 	 * does not correspond to a base relation, such as a join RTE or an
 	 * unreferenced view RTE; or if the RelOptInfo hasn't been made yet.
 	 */
-	struct RelOptInfo **simple_rel_array;		/* All 1-relation RelOptInfos */
+	struct RelOptInfo **simple_rel_array;		/* All 1-rel RelOptInfos */
 	int			simple_rel_array_size;	/* allocated size of array */
 
 	/*
@@ -84,18 +84,20 @@ typedef struct PlannerInfo
 	List	   *join_rel_list;	/* list of join-relation RelOptInfos */
 	struct HTAB *join_rel_hash; /* optional hashtable for join relations */
 
-	List	   *equi_key_list;	/* list of lists of equijoined PathKeyItems */
+	List	   *eq_classes;				/* list of active EquivalenceClasses */
 
-	List	   *left_join_clauses;		/* list of RestrictInfos for outer
-										 * join clauses w/nonnullable var on
-										 * left */
+	List	   *canon_pathkeys;			/* list of "canonical" PathKeys */
 
-	List	   *right_join_clauses;		/* list of RestrictInfos for outer
-										 * join clauses w/nonnullable var on
-										 * right */
+	List	   *left_join_clauses;		/* list of RestrictInfos for
+										 * mergejoinable outer join clauses
+										 * w/nonnullable var on left */
 
-	List	   *full_join_clauses;		/* list of RestrictInfos for full
-										 * outer join clauses */
+	List	   *right_join_clauses;		/* list of RestrictInfos for
+										 * mergejoinable outer join clauses
+										 * w/nonnullable var on right */
+
+	List	   *full_join_clauses;		/* list of RestrictInfos for
+										 * mergejoinable full join clauses */
 
 	List	   *oj_info_list;	/* list of OuterJoinInfos */
 
@@ -109,6 +111,8 @@ typedef struct PlannerInfo
 	List	   *group_pathkeys; /* groupClause pathkeys, if any */
 	List	   *sort_pathkeys;	/* sortClause pathkeys, if any */
 
+	MemoryContext planner_cxt;	/* context holding PlannerInfo */
+
 	double		total_table_pages;		/* # of pages in all tables of query */
 
 	double		tuple_fraction; /* tuple_fraction passed to query_planner */
@@ -209,7 +213,10 @@ typedef struct PlannerInfo
  *		baserestrictcost - Estimated cost of evaluating the baserestrictinfo
  *					clauses at a single tuple (only used for base rels)
  *		joininfo  - List of RestrictInfo nodes, containing info about each
- *					join clause in which this relation participates
+ *					join clause in which this relation participates (but
+ *					note this excludes clauses that might be derivable from
+ *					EquivalenceClasses)
+ *		has_eclass_joins - flag that EquivalenceClass joins are possible
  *		index_outer_relids - only used for base rels; set of outer relids
  *					that participate in indexable joinclauses for this rel
  *		index_inner_paths - only used for base rels; list of InnerIndexscanInfo
@@ -278,6 +285,7 @@ typedef struct RelOptInfo
 	QualCost	baserestrictcost;		/* cost of evaluating the above */
 	List	   *joininfo;		/* RestrictInfo structures for join clauses
 								 * involving this rel */
+	bool		has_eclass_joins;		/* T means joininfo is incomplete */
 
 	/* cached info about inner indexscan paths for relation: */
 	Relids		index_outer_relids;		/* other relids in indexable join
@@ -349,31 +357,106 @@ typedef struct IndexOptInfo
 
 
 /*
+ * EquivalenceClasses
+ *
+ * Whenever we can determine that a mergejoinable equality clause A = B is
+ * not delayed by any outer join, we create an EquivalenceClass containing
+ * the expressions A and B to record this knowledge.  If we later find another
+ * equivalence B = C, we add C to the existing EquivalenceClass; this may
+ * require merging two existing EquivalenceClasses.  At the end of the qual
+ * distribution process, we have sets of values that are known all transitively
+ * equal to each other, where "equal" is according to the rules of the btree
+ * operator family(s) shown in ec_opfamilies.  (We restrict an EC to contain
+ * only equalities whose operators belong to the same set of opfamilies.  This
+ * could probably be relaxed, but for now it's not worth the trouble, since
+ * nearly all equality operators belong to only one btree opclass anyway.)
+ *
+ * We also use EquivalenceClasses as the base structure for PathKeys, letting
+ * us represent knowledge about different sort orderings being equivalent.
+ * Since every PathKey must reference an EquivalenceClass, we will end up
+ * with single-member EquivalenceClasses whenever a sort key expression has
+ * not been equivalenced to anything else.  It is also possible that such an
+ * EquivalenceClass will contain a volatile expression ("ORDER BY random()"),
+ * which is a case that can't arise otherwise since clauses containing
+ * volatile functions are never considered mergejoinable.  We mark such
+ * EquivalenceClasses specially to prevent them from being merged with
+ * ordinary EquivalenceClasses.
+ *
+ * We allow equality clauses appearing below the nullable side of an outer join
+ * to form EquivalenceClasses, but these have a slightly different meaning:
+ * the included values might be all NULL rather than all the same non-null
+ * values.  See src/backend/optimizer/README for more on that point.
+ *
+ * NB: if ec_merged isn't NULL, this class has been merged into another, and
+ * should be ignored in favor of using the pointed-to class.
+ */
+typedef struct EquivalenceClass
+{
+	NodeTag		type;
+
+	List	   *ec_opfamilies;		/* btree operator family OIDs */
+	List	   *ec_members;			/* list of EquivalenceMembers */
+	List	   *ec_sources;			/* list of generating RestrictInfos */
+	Relids		ec_relids;			/* all relids appearing in ec_members */
+	bool		ec_has_const;		/* any pseudoconstants in ec_members? */
+	bool		ec_has_volatile;	/* the (sole) member is a volatile expr */
+	bool		ec_below_outer_join;	/* equivalence applies below an OJ */
+	bool		ec_broken;			/* failed to generate needed clauses? */
+	struct EquivalenceClass *ec_merged;		/* set if merged into another EC */
+} EquivalenceClass;
+
+/*
+ * EquivalenceMember - one member expression of an EquivalenceClass
+ *
+ * em_is_child signifies that this element was built by transposing a member
+ * for an inheritance parent relation to represent the corresponding expression
+ * on an inheritance child.  The element should be ignored for all purposes
+ * except constructing inner-indexscan paths for the child relation.  (Other
+ * types of join are driven from transposed joininfo-list entries.)  Note
+ * that the EC's ec_relids field does NOT include the child relation.
+ *
+ * em_datatype is usually the same as exprType(em_expr), but can be
+ * different when dealing with a binary-compatible opfamily; in particular
+ * anyarray_ops would never work without this.  Use em_datatype when
+ * looking up a specific btree operator to work with this expression.
+ */
+typedef struct EquivalenceMember
+{
+	NodeTag		type;
+
+	Expr	   *em_expr;		/* the expression represented */
+	Relids		em_relids;		/* all relids appearing in em_expr */
+	bool		em_is_const;	/* expression is pseudoconstant? */
+	bool		em_is_child;	/* derived version for a child relation? */
+	Oid			em_datatype;	/* the "nominal type" used by the opfamily */
+} EquivalenceMember;
+
+/*
  * PathKeys
  *
- *	The sort ordering of a path is represented by a list of sublists of
- *	PathKeyItem nodes.	An empty list implies no known ordering.  Otherwise
- *	the first sublist represents the primary sort key, the second the
- *	first secondary sort key, etc.	Each sublist contains one or more
- *	PathKeyItem nodes, each of which can be taken as the attribute that
- *	appears at that sort position.	(See optimizer/README for more
- *	information.)
+ * The sort ordering of a path is represented by a list of PathKey nodes.
+ * An empty list implies no known ordering.  Otherwise the first item
+ * represents the primary sort key, the second the first secondary sort key,
+ * etc.  The value being sorted is represented by linking to an
+ * EquivalenceClass containing that value and including pk_opfamily among its
+ * ec_opfamilies.  This is a convenient method because it makes it trivial
+ * to detect equivalent and closely-related orderings.  (See optimizer/README
+ * for more information.)
+ *
+ * Note: pk_strategy is either BTLessStrategyNumber (for ASC) or
+ * BTGreaterStrategyNumber (for DESC).  We assume that all ordering-capable
+ * index types will use btree-compatible strategy numbers.
  */
 
-typedef struct PathKeyItem
+typedef struct PathKey
 {
 	NodeTag		type;
 
-	Node	   *key;			/* the item that is ordered */
-	Oid			sortop;			/* the ordering operator ('<' op) */
-	bool		nulls_first;	/* do NULLs come before normal values? */
-
-	/*
-	 * key typically points to a Var node, ie a relation attribute, but it can
-	 * also point to an arbitrary expression representing the value indexed by
-	 * an index expression.
-	 */
-} PathKeyItem;
+	EquivalenceClass *pk_eclass;	/* the value that is ordered */
+	Oid			pk_opfamily;		/* btree opfamily defining the ordering */
+	int			pk_strategy;		/* sort direction (ASC or DESC) */
+	bool		pk_nulls_first;		/* do NULLs come before normal values? */
+} PathKey;
 
 /*
  * Type "Path" is used as-is for sequential-scan paths.  For other
@@ -398,7 +481,7 @@ typedef struct Path
 	Cost		total_cost;		/* total cost (assuming all tuples fetched) */
 
 	List	   *pathkeys;		/* sort ordering of path's output */
-	/* pathkeys is a List of Lists of PathKeyItem nodes; see above */
+	/* pathkeys is a List of PathKey nodes; see above */
 } Path;
 
 /*----------
@@ -618,11 +701,7 @@ typedef JoinPath NestPath;
  * A mergejoin path has these fields.
  *
  * path_mergeclauses lists the clauses (in the form of RestrictInfos)
- * that will be used in the merge.  The parallel arrays path_mergeFamilies,
- * path_mergeStrategies, and path_mergeNullsFirst specify the merge semantics
- * for each clause (i.e., define the relevant sort ordering for each clause).
- * (XXX is this the most reasonable path-time representation?  It's at least
- * partially redundant with the pathkeys of the input paths.)
+ * that will be used in the merge.
  *
  * Note that the mergeclauses are a subset of the parent relation's
  * restriction-clause list.  Any join clauses that are not mergejoinable
@@ -639,10 +718,6 @@ typedef struct MergePath
 {
 	JoinPath	jpath;
 	List	   *path_mergeclauses;		/* join clauses to be used for merge */
-	/* these are arrays, but have the same length as the mergeclauses list: */
-	Oid		   *path_mergeFamilies;		/* per-clause OIDs of opfamilies */
-	int		   *path_mergeStrategies;	/* per-clause ordering (ASC or DESC) */
-	bool	   *path_mergeNullsFirst;	/* per-clause nulls ordering */
 	List	   *outersortkeys;	/* keys for explicit sort, if any */
 	List	   *innersortkeys;	/* keys for explicit sort, if any */
 } MergePath;
@@ -696,6 +771,15 @@ typedef struct HashPath
  * 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.
  *
+ * RestrictInfos that represent equivalence conditions (i.e., mergejoinable
+ * equalities that are not outerjoin-delayed) are handled a bit differently.
+ * Initially we attach them to the EquivalenceClasses that are derived from
+ * them.  When we construct a scan or join path, we look through all the
+ * EquivalenceClasses and generate derived RestrictInfos representing the
+ * minimal set of conditions that need to be checked for this particular scan
+ * or join to enforce that all members of each EquivalenceClass are in fact
+ * equal in all rows emitted by the scan or join.
+ *
  * When dealing with outer joins we have to be very careful about pushing qual
  * clauses up and down the tree.  An outer join's own JOIN/ON conditions must
  * be evaluated exactly at that join node, and any quals appearing in WHERE or
@@ -728,9 +812,9 @@ typedef struct HashPath
  *
  * In general, the referenced clause might be arbitrarily complex.	The
  * kinds of clauses we can handle as indexscan quals, mergejoin clauses,
- * or hashjoin clauses are fairly limited --- the code for each kind of
- * path is responsible for identifying the restrict clauses it can use
- * and ignoring the rest.  Clauses not implemented by an indexscan,
+ * or hashjoin clauses are limited (e.g., no volatile functions).  The code
+ * for each kind of path is responsible for identifying the restrict clauses
+ * it can use and ignoring the rest.  Clauses not implemented by an indexscan,
  * mergejoin, or hashjoin will be placed in the plan qual or joinqual field
  * of the finished Plan node, where they will be enforced by general-purpose
  * qual-expression-evaluation code.  (But we are still entitled to count
@@ -758,6 +842,12 @@ typedef struct HashPath
  * estimates.  Note that a pseudoconstant clause can never be an indexqual
  * or merge or hash join clause, so it's of no interest to large parts of
  * the planner.
+ *
+ * When join clauses are generated from EquivalenceClasses, there may be
+ * several equally valid ways to enforce join equivalence, of which we need
+ * apply only one.  We mark clauses of this kind by setting parent_ec to
+ * point to the generating EquivalenceClass.  Multiple clauses with the same
+ * parent_ec in the same join are redundant.
  */
 
 typedef struct RestrictInfo
@@ -787,23 +877,22 @@ typedef struct RestrictInfo
 	/* This field is NULL unless clause is an OR clause: */
 	Expr	   *orclause;		/* modified clause with RestrictInfos */
 
+	/* This field is NULL unless clause is potentially redundant: */
+	EquivalenceClass *parent_ec;	/* generating EquivalenceClass */
+
 	/* cache space for cost and selectivity */
 	QualCost	eval_cost;		/* eval cost of clause; -1 if not yet set */
 	Selectivity this_selec;		/* selectivity; -1 if not yet set */
 
-	/* valid if clause is mergejoinable, else InvalidOid: */
-	Oid			mergejoinoperator;		/* copy of clause operator */
-	Oid			left_sortop;	/* leftside sortop needed for mergejoin */
-	Oid			right_sortop;	/* rightside sortop needed for mergejoin */
-	Oid			mergeopfamily;	/* btree opfamily relating these ops */
+	/* valid if clause is mergejoinable, else NIL */
+	List	   *mergeopfamilies;	/* opfamilies containing clause operator */
 
-	/* cache space for mergeclause processing; NIL if not yet set */
-	List	   *left_pathkey;	/* canonical pathkey for left side */
-	List	   *right_pathkey;	/* canonical pathkey for right side */
+	/* cache space for mergeclause processing; NULL if not yet set */
+	EquivalenceClass *left_ec;	/* EquivalenceClass containing lefthand */
+	EquivalenceClass *right_ec;	/* EquivalenceClass containing righthand */
 
-	/* cache space for mergeclause processing; -1 if not yet set */
-	Selectivity left_mergescansel;		/* fraction of left side to scan */
-	Selectivity right_mergescansel;		/* fraction of right side to scan */
+	/* transient workspace for use while considering a specific join path */
+	bool		outer_is_left;	/* T = outer var on left, F = on right */
 
 	/* valid if clause is hashjoinable, else InvalidOid: */
 	Oid			hashjoinoperator;		/* copy of clause operator */
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 */
diff --git a/src/include/utils/lsyscache.h b/src/include/utils/lsyscache.h
index 8d4c0d8e3ef..f0e3f2c20d4 100644
--- a/src/include/utils/lsyscache.h
+++ b/src/include/utils/lsyscache.h
@@ -6,7 +6,7 @@
  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/utils/lsyscache.h,v 1.112 2007/01/10 18:06:05 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/utils/lsyscache.h,v 1.113 2007/01/20 20:45:41 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -35,12 +35,11 @@ extern void get_op_opfamily_properties(Oid opno, Oid opfamily,
 						  bool *recheck);
 extern Oid	get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype,
 								int16 strategy);
-extern bool get_op_mergejoin_info(Oid eq_op, Oid *left_sortop,
-					  Oid *right_sortop, Oid *opfamily);
 extern bool get_compare_function_for_ordering_op(Oid opno,
 												 Oid *cmpfunc, bool *reverse);
 extern Oid	get_equality_op_for_ordering_op(Oid opno);
 extern Oid	get_ordering_op_for_equality_op(Oid opno, bool use_lhs_type);
+extern List *get_mergejoin_opfamilies(Oid opno);
 extern Oid	get_compatible_hash_operator(Oid opno, bool use_lhs_type);
 extern Oid	get_op_hash_function(Oid opno);
 extern void get_op_btree_interpretation(Oid opno,