Back-patch code to deduce implied equalities from transitivity of

mergejoin clauses, and add these equalities to the given WHERE clauses.
This is necessary to ensure that sort keys we think are equivalent
really are equivalent as soon as their rels have been joined.  Without
this, 7.0 may create an incorrect mergejoin plan.

1 files changed, 78 insertions, 5 deletions

diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 580675a85b7..6c507cfd452 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.21 2000/04/12 17:15:20 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.21.2.1 2000/09/23 23:50:47 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -19,6 +19,7 @@
 #include "optimizer/joininfo.h"
 #include "optimizer/pathnode.h"
 #include "optimizer/paths.h"
+#include "optimizer/planmain.h"
 #include "optimizer/tlist.h"
 #include "optimizer/var.h"
 #include "parser/parsetree.h"
@@ -227,36 +228,108 @@ add_equijoined_keys(Query *root, RestrictInfo *restrictinfo)
 	 * into our new set. When done, we add the new set to the front of
 	 * equi_key_list.
 	 *
+	 * It may well be that the two items we're given are already known to
+	 * be equijoin-equivalent, in which case we don't need to change our
+	 * data structure.  If we find both of them in the same equivalence
+	 * set to start with, we can quit immediately.
+	 *
 	 * This is a standard UNION-FIND problem, for which there exist better
 	 * data structures than simple lists.  If this code ever proves to be
 	 * a bottleneck then it could be sped up --- but for now, simple is
 	 * beautiful.
 	 */
-	newset = lcons(item1, lcons(item2, NIL));
+	newset = NIL;
 
 	foreach(cursetlink, root->equi_key_list)
 	{
 		List	   *curset = lfirst(cursetlink);
+		bool		item1here = member(item1, curset);
+		bool		item2here = member(item2, curset);
 
-		if (member(item1, curset) || member(item2, curset))
+		if (item1here || item2here)
 		{
+			/* If find both in same equivalence set, no need to do any more */
+			if (item1here && item2here)
+			{
+				/* Better not have seen only one in an earlier set... */
+				Assert(newset == NIL);
+				return;
+			}
+
+			/* Build the new set only when we know we must */
+			if (newset == NIL)
+				newset = lcons(item1, lcons(item2, NIL));
+
 			/* Found a set to merge into our new set */
 			newset = LispUnion(newset, curset);
 
 			/*
 			 * Remove old set from equi_key_list.  NOTE this does not
-			 * change lnext(cursetlink), so the outer foreach doesn't
-			 * break.
+			 * change lnext(cursetlink), so the foreach loop doesn't break.
 			 */
 			root->equi_key_list = lremove(curset, root->equi_key_list);
 			freeList(curset);	/* might as well recycle old cons cells */
 		}
 	}
 
+	/* Build the new set only when we know we must */
+	if (newset == NIL)
+		newset = lcons(item1, lcons(item2, NIL));
+
 	root->equi_key_list = lcons(newset, root->equi_key_list);
 }
 
 /*
+ * 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).
+ *
+ * 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.
+ */
+void
+generate_implied_equalities(Query *root)
+{
+	List	   *cursetlink;
+
+	foreach(cursetlink, root->equi_key_list)
+	{
+		List	   *curset = lfirst(cursetlink);
+		List	   *ptr1;
+
+		/*
+		 * 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)
+			continue;
+
+		/*
+		 * 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).
+		 */
+		foreach(ptr1, curset)
+		{
+			PathKeyItem *item1 = (PathKeyItem *) lfirst(ptr1);
+			List	   *ptr2;
+
+			foreach(ptr2, lnext(ptr1))
+			{
+				PathKeyItem *item2 = (PathKeyItem *) lfirst(ptr2);
+
+				process_implied_equality(root, item1->key, item2->key,
+										 item1->sortop, item2->sortop);
+			}
+		}
+	}
+}
+
+/*
  * make_canonical_pathkey
  *	  Given a PathKeyItem, find the equi_key_list subset it is a member of,
  *	  if any.  If so, return a pointer to that sublist, which is the