Modify planner's implied-equality-deduction code so that when a set

of known-equal expressions includes any constant expressions (including
Params from outer queries), we actively suppress any 'var = var'
clauses that are or could be deduced from the set, generating only the
deducible 'var = const' clauses instead.  The idea here is to push down
the restrictions implied by the equality set to base relations whenever
possible.  Once we have applied the 'var = const' clauses, the 'var = var'
clauses are redundant, and should be suppressed both to save work at
execution and to avoid double-counting restrictivity.

12 files changed, 395 insertions, 168 deletions

diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index e896b479018..bf9e5c10d6f 100644
--- a/src/backend/nodes/list.c
+++ b/src/backend/nodes/list.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/nodes/list.c,v 1.44 2003/01/20 18:54:47 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/nodes/list.c,v 1.45 2003/01/24 03:58:34 tgl Exp $
  *
  * NOTES
  *	  XXX a few of the following functions are duplicated to handle
@@ -357,6 +357,7 @@ set_union(List *l1, List *l2)
 	return retval;
 }
 
+/* set_union for integer lists */
 List *
 set_unioni(List *l1, List *l2)
 {
@@ -371,6 +372,21 @@ set_unioni(List *l1, List *l2)
 	return retval;
 }
 
+/* set_union when pointer-equality comparison is sufficient */
+List *
+set_ptrUnion(List *l1, List *l2)
+{
+	List	   *retval = listCopy(l1);
+	List	   *i;
+
+	foreach(i, l2)
+	{
+		if (!ptrMember(lfirst(i), retval))
+			retval = lappend(retval, lfirst(i));
+	}
+	return retval;
+}
+
 /*
  * Generate the intersection of two lists,
  * ie, all members of both l1 and l2.
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 02a92fd9960..443d54c6473 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -9,7 +9,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.132 2003/01/20 18:54:49 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.133 2003/01/24 03:58:34 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -1596,12 +1596,14 @@ make_innerjoin_index_path(Query *root,
 	 * nconc the two lists; then we might have some restriction
 	 * clauses appearing twice, which'd mislead
 	 * restrictlist_selectivity into double-counting their
-	 * selectivity.)
+	 * selectivity.  However, since RestrictInfo nodes aren't copied when
+	 * linking them into different lists, it should be sufficient to use
+	 * pointer comparison to remove duplicates.)
 	 */
 	pathnode->rows = rel->tuples *
 		restrictlist_selectivity(root,
-								 set_union(rel->baserestrictinfo,
-										   clausegroup),
+								 set_ptrUnion(rel->baserestrictinfo,
+											  clausegroup),
 								 lfirsti(rel->relids));
 	/* Like costsize.c, force estimate to be at least one row */
 	if (pathnode->rows < 1.0)
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 194bdddc2f0..b99a44a4404 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -11,7 +11,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.44 2003/01/15 19:35:40 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.45 2003/01/24 03:58:35 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -23,6 +23,7 @@
 #include "optimizer/paths.h"
 #include "optimizer/planmain.h"
 #include "optimizer/tlist.h"
+#include "optimizer/var.h"
 #include "parser/parsetree.h"
 #include "parser/parse_func.h"
 #include "utils/lsyscache.h"
@@ -147,14 +148,30 @@ add_equijoined_keys(Query *root, RestrictInfo *restrictinfo)
  * generate_implied_equalities
  *	  Scan the completed equi_key_list for the query, and generate explicit
  *	  qualifications (WHERE clauses) for all the pairwise equalities not
- *	  already mentioned in the quals.  This is useful because the additional
- *	  clauses help the selectivity-estimation code, and in fact it's
- *	  *necessary* to ensure that sort keys we think are equivalent really
- *	  are (see src/backend/optimizer/README for more info).
+ *	  already mentioned in the quals; or remove qualifications found to be
+ *	  redundant.
+ *
+ * Adding deduced equalities is useful because the additional clauses help
+ * the selectivity-estimation code and may allow better joins to be chosen;
+ * and in fact it's *necessary* to ensure that sort keys we think are
+ * equivalent really are (see src/backend/optimizer/README for more info).
+ *
+ * If an equi_key_list set includes any constants then we adopt a different
+ * strategy: we record all the "var = const" deductions we can make, and
+ * actively remove all the "var = var" clauses that are implied by the set
+ * (including the clauses that originally gave rise to the set!).  The reason
+ * is that given input like "a = b AND b = 42", once we have deduced "a = 42"
+ * there is no longer any need to apply the clause "a = b"; not only is
+ * it a waste of time to check it, but we will misestimate selectivity if the
+ * clause is left in.  So we must remove it.  For this purpose, any pathkey
+ * item that mentions no Vars of the current level can be taken as a constant.
+ * (The only case where this would be risky is if the item contains volatile
+ * functions; but we will never consider such an expression to be a pathkey
+ * at all, because check_mergejoinable() will reject it.)
  *
  * This routine just walks the equi_key_list to find all pairwise equalities.
- * We call process_implied_equality (in plan/initsplan.c) to determine whether
- * each is already known and add it to the proper restrictinfo list if not.
+ * We call process_implied_equality (in plan/initsplan.c) to adjust the
+ * restrictinfo datastructures for each pair.
  */
 void
 generate_implied_equalities(Query *root)
@@ -164,35 +181,119 @@ generate_implied_equalities(Query *root)
 	foreach(cursetlink, root->equi_key_list)
 	{
 		List	   *curset = lfirst(cursetlink);
+		int			nitems = length(curset);
+		Relids	   *relids;
+		bool		have_consts;
 		List	   *ptr1;
+		int			i1;
 
 		/*
 		 * A set containing only two items cannot imply any equalities
 		 * beyond the one that created the set, so we can skip it.
 		 */
-		if (length(curset) < 3)
+		if (nitems < 3)
 			continue;
 
 		/*
+		 * Collect info about relids mentioned in each item.  For this
+		 * routine we only really care whether there are any at all in
+		 * each item, but process_implied_equality() needs the exact
+		 * lists, so we may as well pull them here.
+		 */
+		relids = (Relids *) palloc(nitems * sizeof(Relids));
+		have_consts = false;
+		i1 = 0;
+		foreach(ptr1, curset)
+		{
+			PathKeyItem *item1 = (PathKeyItem *) lfirst(ptr1);
+
+			relids[i1] = pull_varnos(item1->key);
+			if (relids[i1] == NIL)
+				have_consts = true;
+			i1++;
+		}
+
+		/*
 		 * Match each item in the set with all that appear after it (it's
 		 * sufficient to generate A=B, need not process B=A too).
 		 */
+		i1 = 0;
 		foreach(ptr1, curset)
 		{
 			PathKeyItem *item1 = (PathKeyItem *) lfirst(ptr1);
 			List	   *ptr2;
+			int			i2 = i1 + 1;
 
 			foreach(ptr2, lnext(ptr1))
 			{
 				PathKeyItem *item2 = (PathKeyItem *) lfirst(ptr2);
 
-				process_implied_equality(root, item1->key, item2->key,
-										 item1->sortop, item2->sortop);
+				/*
+				 * If it's "const = const" then just ignore it altogether.
+				 * There is no place in the restrictinfo structure to store
+				 * it.  (If the two consts are in fact unequal, then
+				 * propagating the comparison to Vars will cause us to
+				 * produce zero rows out, as expected.)
+				 */
+				if (relids[i1] != NIL || relids[i2] != NIL)
+				{
+					/*
+					 * Tell process_implied_equality to delete the clause,
+					 * not add it, if it's "var = var" and we have constants
+					 * present in the list.
+					 */
+					bool	delete_it = (have_consts &&
+										 relids[i1] != NIL &&
+										 relids[i2] != NIL);
+					process_implied_equality(root,
+											 item1->key, item2->key,
+											 item1->sortop, item2->sortop,
+											 relids[i1], relids[i2],
+											 delete_it);
+				}
+				i2++;
 			}
+			i1++;
+		}
+	}
+}
+
+/*
+ * exprs_known_equal
+ *	  Detect whether two expressions are known equal due to equijoin clauses.
+ *
+ * Note: does not bother to check for "equal(item1, item2)"; caller must
+ * check that case if it's possible to pass identical items.
+ */
+bool
+exprs_known_equal(Query *root, Node *item1, Node *item2)
+{
+	List	   *cursetlink;
+
+	foreach(cursetlink, root->equi_key_list)
+	{
+		List	   *curset = lfirst(cursetlink);
+		bool		item1member = false;
+		bool		item2member = false;
+		List	   *ptr;
+
+		foreach(ptr, curset)
+		{
+			PathKeyItem *pitem = (PathKeyItem *) lfirst(ptr);
+
+			if (equal(item1, pitem->key))
+				item1member = true;
+			else if (equal(item2, pitem->key))
+				item2member = true;
+			/* Exit as soon as equality is proven */
+			if (item1member && item2member)
+				return true;
 		}
 	}
+	return false;
 }
 
+
 /*
  * make_canonical_pathkey
  *	  Given a PathKeyItem, find the equi_key_list subset it is a member of,
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index 037ed3314cf..3a824d55d72 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v 1.82 2003/01/20 18:54:52 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v 1.83 2003/01/24 03:58:43 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -40,8 +40,6 @@ static void distribute_qual_to_rels(Query *root, Node *clause,
 						bool isouterjoin,
 						bool isdeduced,
 						Relids qualscope);
-static void add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo,
-					  Relids join_relids);
 static void add_vars_to_targetlist(Query *root, List *vars);
 static bool qual_is_redundant(Query *root, RestrictInfo *restrictinfo,
 				  List *restrictlist);
@@ -539,7 +537,7 @@ distribute_qual_to_rels(Query *root, Node *clause,
 		/*
 		 * Add clause to the join lists of all the relevant relations.
 		 */
-		add_join_info_to_rels(root, restrictinfo, relids);
+		add_join_clause_to_rels(root, restrictinfo, relids);
 
 		/*
 		 * Add vars used in the join clause to targetlists of their
@@ -573,78 +571,95 @@ distribute_qual_to_rels(Query *root, Node *clause,
 }
 
 /*
- * add_join_info_to_rels
- *	  For every relation participating in a join clause, add 'restrictinfo' to
- *	  the appropriate joininfo list (creating a new list and adding it to the
- *	  appropriate rel node if necessary).
- *
- * Note that the same copy of the restrictinfo node is linked to by all the
- * lists it is in.  This allows us to exploit caching of information about
- * the restriction clause (but we must be careful that the information does
- * not depend on context).
- *
- * 'restrictinfo' describes the join clause
- * 'join_relids' is the list of relations participating in the join clause
- */
-static void
-add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo,
-					  Relids join_relids)
-{
-	List	   *join_relid;
-
-	/* For every relid, find the joininfo, and add the proper join entries */
-	foreach(join_relid, join_relids)
-	{
-		int			cur_relid = lfirsti(join_relid);
-		Relids		unjoined_relids = NIL;
-		JoinInfo   *joininfo;
-		List	   *otherrel;
-
-		/* Get the relids not equal to the current relid */
-		foreach(otherrel, join_relids)
-		{
-			if (lfirsti(otherrel) != cur_relid)
-				unjoined_relids = lappendi(unjoined_relids, lfirsti(otherrel));
-		}
-		Assert(unjoined_relids != NIL);
-
-		/*
-		 * Find or make the joininfo node for this combination of rels,
-		 * and add the restrictinfo node to it.
-		 */
-		joininfo = make_joininfo_node(find_base_rel(root, cur_relid),
-									  unjoined_relids);
-		joininfo->jinfo_restrictinfo = lappend(joininfo->jinfo_restrictinfo,
-											   restrictinfo);
-	}
-}
-
-/*
  * process_implied_equality
  *	  Check to see whether we already have a restrictinfo item that says
- *	  item1 = item2, and create one if not.  This is a consequence of
- *	  transitivity of mergejoin equality: if we have mergejoinable
- *	  clauses A = B and B = C, we can deduce A = C (where = is an
- *	  appropriate mergejoinable operator).
+ *	  item1 = item2, and create one if not; or if delete_it is true,
+ *	  remove any such restrictinfo item.
+ *
+ * This processing is a consequence of transitivity of mergejoin equality:
+ * if we have mergejoinable clauses A = B and B = C, we can deduce A = C
+ * (where = is an appropriate mergejoinable operator).  See path/pathkeys.c
+ * for more details.
  */
 void
-process_implied_equality(Query *root, Node *item1, Node *item2,
-						 Oid sortop1, Oid sortop2)
+process_implied_equality(Query *root,
+						 Node *item1, Node *item2,
+						 Oid sortop1, Oid sortop2,
+						 Relids item1_relids, Relids item2_relids,
+						 bool delete_it)
 {
+	Relids		relids;
+	RelOptInfo *rel1;
+	List	   *restrictlist;
+	List	   *itm;
 	Oid			ltype,
 				rtype;
 	Operator	eq_operator;
 	Form_pg_operator pgopform;
 	Expr	   *clause;
 
+	/* Get list of relids referenced in the two expressions */
+	relids = set_unioni(item1_relids, item2_relids);
+
 	/*
-	 * Forget it if this equality is already recorded.
-	 *
-	 * Note: if only a single relation is involved, we may fall through
-	 * here and end up rejecting the equality later on in qual_is_redundant.
-	 * This is a tad slow but should be okay.
+	 * generate_implied_equalities() shouldn't call me on two constants.
+	 */
+	Assert(relids != NIL);
+
+	/*
+	 * If the exprs involve a single rel, we need to look at that rel's
+	 * baserestrictinfo list.  If multiple rels, any one will have a
+	 * joininfo node for the rest, and we can scan any of 'em.
 	 */
-	if (exprs_known_equal(root, item1, item2))
+	rel1 = find_base_rel(root, lfirsti(relids));
+	if (lnext(relids) == NIL)
+		restrictlist = rel1->baserestrictinfo;
+	else
+	{
+		JoinInfo   *joininfo = find_joininfo_node(rel1, lnext(relids));
+
+		restrictlist = joininfo ? joininfo->jinfo_restrictinfo : NIL;
+	}
+
+	/*
+	 * Scan to see if equality is already known.  If so, we're done in
+	 * the add case, and done after removing it in the delete case.
+	 */
+	foreach(itm, restrictlist)
+	{
+		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(itm);
+		Node	   *left,
+				   *right;
+
+		if (restrictinfo->mergejoinoperator == InvalidOid)
+			continue;			/* ignore non-mergejoinable clauses */
+		/* We now know the restrictinfo clause is a binary opclause */
+		left = get_leftop(restrictinfo->clause);
+		right = get_rightop(restrictinfo->clause);
+		if ((equal(item1, left) && equal(item2, right)) ||
+			(equal(item2, left) && equal(item1, right)))
+		{
+			/* found a matching clause */
+			if (delete_it)
+			{
+				if (lnext(relids) == NIL)
+				{
+					/* delete it from local restrictinfo list */
+					rel1->baserestrictinfo = lremove(restrictinfo,
+													 rel1->baserestrictinfo);
+				}
+				else
+				{
+					/* let joininfo.c do it */
+					remove_join_clause_from_rels(root, restrictinfo, relids);
+				}
+			}
+			return;				/* done */
+		}
+	}
+
+	/* Didn't find it.  Done if deletion requested */
+	if (delete_it)
 		return;
 
 	/*
@@ -692,73 +707,7 @@ process_implied_equality(Query *root, Node *item1, Node *item2,
 	 */
 	distribute_qual_to_rels(root, (Node *) clause,
 							true, false, true,
-							pull_varnos((Node *) clause));
-}
-
-/*
- * exprs_known_equal
- *	  Detect whether two expressions are known equal due to equijoin clauses.
- *
- * This is not completely accurate since we avoid adding redundant restriction
- * clauses to individual base rels (see qual_is_redundant).  However, after
- * the implied-equality-deduction phase, it is complete for expressions
- * involving Vars of multiple rels; that's sufficient for planned uses.
- */
-bool
-exprs_known_equal(Query *root, Node *item1, Node *item2)
-{
-	List	   *relids;
-	RelOptInfo *rel1;
-	List	   *restrictlist;
-	List	   *itm;
-
-	/* Get list of relids referenced in the two expressions */
-	relids = set_unioni(pull_varnos(item1), pull_varnos(item2));
-
-	/*
-	 * If there are no Vars at all, say "true".  This prevents
-	 * process_implied_equality from trying to store "const = const"
-	 * deductions.
-	 */
-	if (relids == NIL)
-		return true;
-
-	/*
-	 * If the exprs involve a single rel, we need to look at that rel's
-	 * baserestrictinfo list.  If multiple rels, any one will have a
-	 * joininfo node for the rest, and we can scan any of 'em.
-	 */
-	rel1 = find_base_rel(root, lfirsti(relids));
-	relids = lnext(relids);
-	if (relids == NIL)
-		restrictlist = rel1->baserestrictinfo;
-	else
-	{
-		JoinInfo   *joininfo = find_joininfo_node(rel1, relids);
-
-		restrictlist = joininfo ? joininfo->jinfo_restrictinfo : NIL;
-	}
-
-	/*
-	 * Scan to see if equality is known.
-	 */
-	foreach(itm, restrictlist)
-	{
-		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(itm);
-		Node	   *left,
-				   *right;
-
-		if (restrictinfo->mergejoinoperator == InvalidOid)
-			continue;			/* ignore non-mergejoinable clauses */
-		/* We now know the restrictinfo clause is a binary opclause */
-		left = get_leftop(restrictinfo->clause);
-		right = get_rightop(restrictinfo->clause);
-		if ((equal(item1, left) && equal(item2, right)) ||
-			(equal(item2, left) && equal(item1, right)))
-			return true;		/* found a matching clause */
-	}
-
-	return false;
+							relids);
 }
 
 /*
@@ -770,19 +719,32 @@ exprs_known_equal(Query *root, Node *item1, Node *item2)
  *				SELECT * FROM tab WHERE f1 = f2 AND f2 = f3;
  *	  We need to suppress the redundant condition to avoid computing
  *	  too-small selectivity, not to mention wasting time at execution.
+ *
+ * Note: quals of the form "var = const" are never considered redundant,
+ * only those of the form "var = var".  This is needed because when we
+ * have constants in an implied-equality set, we use a different strategy
+ * that suppresses all "var = var" deductions.  We must therefore keep
+ * all the "var = const" quals.
  */
 static bool
 qual_is_redundant(Query *root,
 				  RestrictInfo *restrictinfo,
 				  List *restrictlist)
 {
-	List	   *oldquals;
-	List	   *olditem;
 	Node	   *newleft;
 	Node	   *newright;
+	List	   *oldquals;
+	List	   *olditem;
 	List	   *equalexprs;
 	bool		someadded;
 
+	newleft = get_leftop(restrictinfo->clause);
+	newright = get_rightop(restrictinfo->clause);
+
+	/* Never redundant unless vars appear on both sides */
+	if (!contain_var_clause(newleft) || !contain_var_clause(newright))
+		return false;
+
 	/*
 	 * Set cached pathkeys.  NB: it is okay to do this now because this
 	 * routine is only invoked while we are generating implied equalities.
@@ -822,8 +784,6 @@ qual_is_redundant(Query *root,
 	 * we find we can reach the right-side expr of the new qual, we are
 	 * done.  We give up when we can't expand the equalexprs list any more.
 	 */
-	newleft = get_leftop(restrictinfo->clause);
-	newright = get_rightop(restrictinfo->clause);
 	equalexprs = makeList1(newleft);
 	do
 	{
diff --git a/src/backend/optimizer/util/joininfo.c b/src/backend/optimizer/util/joininfo.c
index c202615b1f5..79a9f7a3bac 100644
--- a/src/backend/optimizer/util/joininfo.c
+++ b/src/backend/optimizer/util/joininfo.c
@@ -8,13 +8,14 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/joininfo.c,v 1.32 2003/01/20 18:54:56 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/joininfo.c,v 1.33 2003/01/24 03:58:43 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
 #include "postgres.h"
 
 #include "optimizer/joininfo.h"
+#include "optimizer/pathnode.h"
 
 
 /*
@@ -63,3 +64,110 @@ make_joininfo_node(RelOptInfo *this_rel, Relids join_relids)
 	}
 	return joininfo;
 }
+
+
+/*
+ * add_join_clause_to_rels
+ *	  For every relation participating in a join clause, add 'restrictinfo' to
+ *	  the appropriate joininfo list (creating a new list and adding it to the
+ *	  appropriate rel node if necessary).
+ *
+ * Note that the same copy of the restrictinfo node is linked to by all the
+ * lists it is in.  This allows us to exploit caching of information about
+ * the restriction clause (but we must be careful that the information does
+ * not depend on context).
+ *
+ * 'restrictinfo' describes the join clause
+ * 'join_relids' is the list of relations participating in the join clause
+ *				 (there must be more than one)
+ */
+void
+add_join_clause_to_rels(Query *root,
+						RestrictInfo *restrictinfo,
+						Relids join_relids)
+{
+	List	   *join_relid;
+
+	/* For every relid, find the joininfo, and add the proper join entries */
+	foreach(join_relid, join_relids)
+	{
+		int			cur_relid = lfirsti(join_relid);
+		Relids		unjoined_relids = NIL;
+		JoinInfo   *joininfo;
+		List	   *otherrel;
+
+		/* Get the relids not equal to the current relid */
+		foreach(otherrel, join_relids)
+		{
+			if (lfirsti(otherrel) != cur_relid)
+				unjoined_relids = lappendi(unjoined_relids, lfirsti(otherrel));
+		}
+		Assert(unjoined_relids != NIL);
+
+		/*
+		 * Find or make the joininfo node for this combination of rels,
+		 * and add the restrictinfo node to it.
+		 */
+		joininfo = make_joininfo_node(find_base_rel(root, cur_relid),
+									  unjoined_relids);
+		joininfo->jinfo_restrictinfo = lappend(joininfo->jinfo_restrictinfo,
+											   restrictinfo);
+		/*
+		 * Can't freeList(unjoined_relids) because new joininfo node may
+		 * link to it.  We could avoid leaking memory by doing listCopy()
+		 * in make_joininfo_node, but for now speed seems better.
+		 */
+	}
+}
+
+/*
+ * remove_join_clause_from_rels
+ *	  Delete 'restrictinfo' from all the joininfo lists it is in
+ *
+ * This reverses the effect of add_join_clause_to_rels.  It's used when we
+ * discover that a join clause is redundant.
+ *
+ * 'restrictinfo' describes the join clause
+ * 'join_relids' is the list of relations participating in the join clause
+ *				 (there must be more than one)
+ */
+void
+remove_join_clause_from_rels(Query *root,
+							 RestrictInfo *restrictinfo,
+							 Relids join_relids)
+{
+	List	   *join_relid;
+
+	/* For every relid, find the joininfo */
+	foreach(join_relid, join_relids)
+	{
+		int			cur_relid = lfirsti(join_relid);
+		Relids		unjoined_relids = NIL;
+		JoinInfo   *joininfo;
+		List	   *otherrel;
+
+		/* Get the relids not equal to the current relid */
+		foreach(otherrel, join_relids)
+		{
+			if (lfirsti(otherrel) != cur_relid)
+				unjoined_relids = lappendi(unjoined_relids, lfirsti(otherrel));
+		}
+		Assert(unjoined_relids != NIL);
+
+		/*
+		 * Find the joininfo node for this combination of rels; it should
+		 * exist already, if add_join_clause_to_rels was called.
+		 */
+		joininfo = find_joininfo_node(find_base_rel(root, cur_relid),
+									  unjoined_relids);
+		Assert(joininfo);
+		/*
+		 * Remove the restrictinfo from the list.  Pointer comparison
+		 * is sufficient.
+		 */
+		Assert(ptrMember(restrictinfo, joininfo->jinfo_restrictinfo));
+		joininfo->jinfo_restrictinfo = lremove(restrictinfo,
+											   joininfo->jinfo_restrictinfo);
+		freeList(unjoined_relids);
+	}
+}
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 144fac75501..06a73bf4e9e 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/relnode.c,v 1.44 2003/01/20 18:54:56 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/relnode.c,v 1.45 2003/01/24 03:58:43 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -549,14 +549,19 @@ subbuild_joinrel_joinlist(RelOptInfo *joinrel,
 			/*
 			 * These clauses are still join clauses at this level, so find
 			 * or make the appropriate JoinInfo item for the joinrel, and
-			 * add the clauses to it (eliminating duplicates).
+			 * add the clauses to it, eliminating duplicates.  (Since
+			 * RestrictInfo nodes are normally multiply-linked rather than
+			 * copied, pointer equality should be a sufficient test.  If
+			 * two equal() nodes should happen to sneak in, no great harm
+			 * is done --- they'll be detected by redundant-clause testing
+			 * when they reach a restriction list.)
 			 */
 			JoinInfo   *new_joininfo;
 
 			new_joininfo = make_joininfo_node(joinrel, new_unjoined_relids);
 			new_joininfo->jinfo_restrictinfo =
-				set_union(new_joininfo->jinfo_restrictinfo,
-						  joininfo->jinfo_restrictinfo);
+				set_ptrUnion(new_joininfo->jinfo_restrictinfo,
+							 joininfo->jinfo_restrictinfo);
 		}
 	}
 }
diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c
index bc1fcc36464..bdcc338d609 100644
--- a/src/backend/optimizer/util/restrictinfo.c
+++ b/src/backend/optimizer/util/restrictinfo.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/restrictinfo.c,v 1.15 2002/11/24 21:52:14 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/restrictinfo.c,v 1.16 2003/01/24 03:58:43 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -17,6 +17,7 @@
 #include "optimizer/clauses.h"
 #include "optimizer/paths.h"
 #include "optimizer/restrictinfo.h"
+#include "optimizer/var.h"
 
 
 /*
@@ -101,6 +102,13 @@ get_actual_join_clauses(List *restrictinfo_list,
  * equality between any set member on the left and any member on the right;
  * by transitivity, all the rest are then equal.
  *
+ * However, clauses that are of the form "var expr = const expr" cannot be
+ * eliminated as redundant.  This is because when there are const expressions
+ * in a pathkey set, generate_implied_equalities() suppresses "var = var"
+ * clauses in favor of "var = const" clauses.  We cannot afford to drop any
+ * of the latter, even though they might seem redundant by the pathkey
+ * membership test.
+ *
  * Weird special case: if we have two clauses that seem redundant
  * except one is pushed down into an outer join and the other isn't,
  * then they're not really redundant, because one constrains the
@@ -120,7 +128,7 @@ remove_redundant_join_clauses(Query *root, List *restrictinfo_list,
 	{
 		RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);
 
-		/* eliminate duplicates */
+		/* always eliminate duplicates */
 		if (member(rinfo, result))
 			continue;
 
@@ -132,6 +140,7 @@ remove_redundant_join_clauses(Query *root, List *restrictinfo_list,
 
 			cache_mergeclause_pathkeys(root, rinfo);
 
+			/* do the cheap tests first */
 			foreach(olditem, result)
 			{
 				RestrictInfo *oldrinfo = (RestrictInfo *) lfirst(olditem);
@@ -148,7 +157,20 @@ remove_redundant_join_clauses(Query *root, List *restrictinfo_list,
 			}
 
 			if (redundant)
-				continue;
+			{
+				/*
+				 * It looks redundant, now check for "var = const" case.
+				 * If left_relids/right_relids are set, then there are
+				 * definitely vars on both sides; else we must check the
+				 * hard way.
+				 */
+				if (rinfo->left_relids)
+					continue;	/* var = var, so redundant */
+				if (contain_var_clause(get_leftop(rinfo->clause)) &&
+					contain_var_clause(get_rightop(rinfo->clause)))
+					continue;	/* var = var, so redundant */
+				/* else var = const, not redundant */
+			}
 		}
 
 		/* otherwise, add it to result list */
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 20d353a0a50..62e0b8b32a9 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -15,7 +15,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/utils/adt/selfuncs.c,v 1.128 2003/01/22 20:16:42 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/utils/adt/selfuncs.c,v 1.129 2003/01/24 03:58:43 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -84,8 +84,8 @@
 #include "optimizer/clauses.h"
 #include "optimizer/cost.h"
 #include "optimizer/pathnode.h"
+#include "optimizer/paths.h"
 #include "optimizer/plancat.h"
-#include "optimizer/planmain.h"
 #include "optimizer/prep.h"
 #include "optimizer/tlist.h"
 #include "optimizer/var.h"
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index d3b01b7fed0..56a66409161 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: pg_list.h,v 1.31 2003/01/20 18:55:04 tgl Exp $
+ * $Id: pg_list.h,v 1.32 2003/01/24 03:58:43 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -141,6 +141,7 @@ extern List *set_differencei(List *list1, List *list2);
 extern List *lreverse(List *l);
 extern List *set_union(List *list1, List *list2);
 extern List *set_unioni(List *list1, List *list2);
+extern List *set_ptrUnion(List *list1, List *list2);
 extern List *set_intersecti(List *list1, List *list2);
 
 extern bool equali(List *list1, List *list2);
diff --git a/src/include/optimizer/joininfo.h b/src/include/optimizer/joininfo.h
index 37131b722d2..6fd806bbaf1 100644
--- a/src/include/optimizer/joininfo.h
+++ b/src/include/optimizer/joininfo.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: joininfo.h,v 1.22 2003/01/20 18:55:04 tgl Exp $
+ * $Id: joininfo.h,v 1.23 2003/01/24 03:58:43 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -16,7 +16,15 @@
 
 #include "nodes/relation.h"
 
-extern JoinInfo *find_joininfo_node(RelOptInfo *this_rel, List *join_relids);
-extern JoinInfo *make_joininfo_node(RelOptInfo *this_rel, List *join_relids);
+
+extern JoinInfo *find_joininfo_node(RelOptInfo *this_rel, Relids join_relids);
+extern JoinInfo *make_joininfo_node(RelOptInfo *this_rel, Relids join_relids);
+
+extern void add_join_clause_to_rels(Query *root,
+									RestrictInfo *restrictinfo,
+									Relids join_relids);
+extern void remove_join_clause_from_rels(Query *root,
+										 RestrictInfo *restrictinfo,
+										 Relids join_relids);
 
 #endif   /* JOININFO_H */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 7ed5b403a87..76285bac408 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -8,7 +8,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: paths.h,v 1.63 2002/12/16 21:30:30 tgl Exp $
+ * $Id: paths.h,v 1.64 2003/01/24 03:58:43 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -17,6 +17,7 @@
 
 #include "nodes/relation.h"
 
+
 /* default GEQO threshold (default value for geqo_rels) */
 /* If you change this, update backend/utils/misc/postgresql.sample.conf */
 #define DEFAULT_GEQO_RELS 11
@@ -92,6 +93,7 @@ typedef enum
 } PathKeysComparison;
 
 extern void add_equijoined_keys(Query *root, RestrictInfo *restrictinfo);
+extern bool exprs_known_equal(Query *root, Node *item1, Node *item2);
 extern void generate_implied_equalities(Query *root);
 extern List *canonicalize_pathkeys(Query *root, List *pathkeys);
 extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index cf9c2ddeb64..399b3bb1310 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: planmain.h,v 1.67 2003/01/20 18:55:05 tgl Exp $
+ * $Id: planmain.h,v 1.68 2003/01/24 03:58:44 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -57,9 +57,11 @@ extern Result *make_result(List *tlist, Node *resconstantqual, Plan *subplan);
 extern void add_base_rels_to_query(Query *root, Node *jtnode);
 extern void build_base_rel_tlists(Query *root, List *tlist);
 extern Relids distribute_quals_to_rels(Query *root, Node *jtnode);
-extern void process_implied_equality(Query *root, Node *item1, Node *item2,
-						 Oid sortop1, Oid sortop2);
-extern bool exprs_known_equal(Query *root, Node *item1, Node *item2);
+extern void process_implied_equality(Query *root,
+									 Node *item1, Node *item2,
+									 Oid sortop1, Oid sortop2,
+									 Relids item1_relids, Relids item2_relids,
+									 bool delete_it);
 
 /*
  * prototypes for plan/setrefs.c