Deduce equality constraints that are implied by transitivity of

mergejoinable qual clauses, and add them to the query quals.  For
example, WHERE a = b AND b = c will cause us to add AND a = c.
This is necessary to ensure that it's safe to use these variables
as interchangeable sort keys, which is something 7.0 knows how to do.
Should provide a useful improvement in planning ability, too.

1 files changed, 84 insertions, 148 deletions

diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index e51daddd04..e9906bfef2 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -3,12 +3,15 @@
  * pathkeys.c
  *	  Utilities for matching and building path keys
  *
+ * See src/backend/optimizer/README for a great deal of information about
+ * the nature and use of path keys.
+ *
+ *
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.22 2000/05/30 00:49:47 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.23 2000/07/24 03:10:56 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -18,156 +21,17 @@
 #include "optimizer/clauses.h"
 #include "optimizer/pathnode.h"
 #include "optimizer/paths.h"
+#include "optimizer/planmain.h"
 #include "optimizer/tlist.h"
 #include "parser/parsetree.h"
 #include "parser/parse_func.h"
 #include "utils/lsyscache.h"
 
+
 static PathKeyItem *makePathKeyItem(Node *key, Oid sortop);
 static List *make_canonical_pathkey(Query *root, PathKeyItem *item);
 static Var *find_indexkey_var(Query *root, RelOptInfo *rel,
-				  AttrNumber varattno);
-
-
-/*--------------------
- *	Explanation of Path.pathkeys
- *
- *	Path.pathkeys is a List of Lists of PathKeyItem nodes that represent
- *	the sort order of the result generated by the Path.  The n'th sublist
- *	represents the n'th sort key of the result.
- *
- *	In single/base relation RelOptInfo's, the Paths represent various ways
- *	of scanning the relation and the resulting ordering of the tuples.
- *	Sequential scan Paths have NIL pathkeys, indicating no known ordering.
- *	Index scans have Path.pathkeys that represent the chosen index's ordering,
- *	if any.  A single-key index would create a pathkey with a single sublist,
- *	e.g. ( (tab1.indexkey1/sortop1) ).	A multi-key index generates a sublist
- *	per key, e.g. ( (tab1.indexkey1/sortop1) (tab1.indexkey2/sortop2) ) which
- *	shows major sort by indexkey1 (ordering by sortop1) and minor sort by
- *	indexkey2 with sortop2.
- *
- *	Note that a multi-pass indexscan (OR clause scan) has NIL pathkeys since
- *	we can say nothing about the overall order of its result.  Also, an
- *	indexscan on an unordered type of index generates NIL pathkeys.  However,
- *	we can always create a pathkey by doing an explicit sort.  The pathkeys
- *	for a sort plan's output just represent the sort key fields and the
- *	ordering operators used.
- *
- *	Things get more interesting when we consider joins.  Suppose we do a
- *	mergejoin between A and B using the mergeclause A.X = B.Y.	The output
- *	of the mergejoin is sorted by X --- but it is also sorted by Y.  We
- *	represent this fact by listing both keys in a single pathkey sublist:
- *	( (A.X/xsortop B.Y/ysortop) ).	This pathkey asserts that the major
- *	sort order of the Path can be taken to be *either* A.X or B.Y.
- *	They are equal, so they are both primary sort keys.  By doing this,
- *	we allow future joins to use either var as a pre-sorted key, so upper
- *	Mergejoins may be able to avoid having to re-sort the Path.  This is
- *	why pathkeys is a List of Lists.
- *
- *	We keep a sortop associated with each PathKeyItem because cross-data-type
- *	mergejoins are possible; for example int4 = int8 is mergejoinable.
- *	In this case we need to remember that the left var is ordered by int4lt
- *	while the right var is ordered by int8lt.  So the different members of
- *	each sublist could have different sortops.
- *
- *	Note that while the order of the top list is meaningful (primary vs.
- *	secondary sort key), the order of each sublist is arbitrary.  Each sublist
- *	should be regarded as a set of equivalent keys, with no significance
- *	to the list order.
- *
- *	With a little further thought, it becomes apparent that pathkeys for
- *	joins need not only come from mergejoins.  For example, if we do a
- *	nestloop join between outer relation A and inner relation B, then any
- *	pathkeys relevant to A are still valid for the join result: we have
- *	not altered the order of the tuples from A.  Even more interesting,
- *	if there was a mergeclause (more formally, an "equijoin clause") A.X=B.Y,
- *	and A.X was a pathkey for the outer relation A, then we can assert that
- *	B.Y is a pathkey for the join result; X was ordered before and still is,
- *	and the joined values of Y are equal to the joined values of X, so Y
- *	must now be ordered too.  This is true even though we used no mergejoin.
- *
- *	More generally, whenever we have an equijoin clause A.X = B.Y and a
- *	pathkey A.X, we can add B.Y to that pathkey if B is part of the joined
- *	relation the pathkey is for, *no matter how we formed the join*.
- *
- *	In short, then: when producing the pathkeys for a merge or nestloop join,
- *	we can keep all of the keys of the outer path, since the ordering of the
- *	outer path will be preserved in the result.  Furthermore, we can add to
- *	each pathkey sublist any inner vars that are equijoined to any of the
- *	outer vars in the sublist; this works regardless of whether we are
- *	implementing the join using that equijoin clause as a mergeclause,
- *	or merely enforcing the clause after-the-fact as a qpqual filter.
- *
- *	Although Hashjoins also work only with equijoin operators, it is *not*
- *	safe to consider the output of a Hashjoin to be sorted in any particular
- *	order --- not even the outer path's order.  This is true because the
- *	executor might have to split the join into multiple batches.  Therefore
- *	a Hashjoin is always given NIL pathkeys.  (Also, we need to use only
- *	mergejoinable operators when deducing which inner vars are now sorted,
- *	because a mergejoin operator tells us which left- and right-datatype
- *	sortops can be considered equivalent, whereas a hashjoin operator
- *	doesn't imply anything about sort order.)
- *
- *	Pathkeys are also useful to represent an ordering that we wish to achieve,
- *	since they are easily compared to the pathkeys of a potential candidate
- *	path.  So, SortClause lists are turned into pathkeys lists for use inside
- *	the optimizer.
- *
- *	OK, now for how it *really* works:
- *
- *	We did implement pathkeys just as described above, and found that the
- *	planner spent a huge amount of time comparing pathkeys, because the
- *	representation of pathkeys as unordered lists made it expensive to decide
- *	whether two were equal or not.	So, we've modified the representation
- *	as described next.
- *
- *	If we scan the WHERE clause for equijoin clauses (mergejoinable clauses)
- *	during planner startup, we can construct lists of equivalent pathkey items
- *	for the query.	There could be more than two items per equivalence set;
- *	for example, WHERE A.X = B.Y AND B.Y = C.Z AND D.R = E.S creates the
- *	equivalence sets { A.X B.Y C.Z } and { D.R E.S } (plus associated sortops).
- *	Any pathkey item that belongs to an equivalence set implies that all the
- *	other items in its set apply to the relation too, or at least all the ones
- *	that are for fields present in the relation.  (Some of the items in the
- *	set might be for as-yet-unjoined relations.)  Furthermore, any multi-item
- *	pathkey sublist that appears at any stage of planning the query *must* be
- *	a subset of one or another of these equivalence sets; there's no way we'd
- *	have put two items in the same pathkey sublist unless they were equijoined
- *	in WHERE.
- *
- *	Now suppose that we allow a pathkey sublist to contain pathkey items for
- *	vars that are not yet part of the pathkey's relation.  This introduces
- *	no logical difficulty, because such items can easily be seen to be
- *	irrelevant; we just mandate that they be ignored.  But having allowed
- *	this, we can declare (by fiat) that any multiple-item pathkey sublist
- *	must be equal() to the appropriate equivalence set.  In effect, whenever
- *	we make a pathkey sublist that mentions any var appearing in an
- *	equivalence set, we instantly add all the other vars equivalenced to it,
- *	whether they appear yet in the pathkey's relation or not.  And we also
- *	mandate that the pathkey sublist appear in the same order as the
- *	equivalence set it comes from.	(In practice, we simply return a pointer
- *	to the relevant equivalence set without building any new sublist at all.)
- *	This makes comparing pathkeys very simple and fast, and saves a lot of
- *	work and memory space for pathkey construction as well.
- *
- *	Note that pathkey sublists having just one item still exist, and are
- *	not expected to be equal() to any equivalence set.	This occurs when
- *	we describe a sort order that involves a var that's not mentioned in
- *	any equijoin clause of the WHERE.  We could add singleton sets containing
- *	such vars to the query's list of equivalence sets, but there's little
- *	point in doing so.
- *
- *	By the way, it's OK and even useful for us to build equivalence sets
- *	that mention multiple vars from the same relation.	For example, if
- *	we have WHERE A.X = A.Y and we are scanning A using an index on X,
- *	we can legitimately conclude that the path is sorted by Y as well;
- *	and this could be handy if Y is the variable used in other join clauses
- *	or ORDER BY.  So, any WHERE clause with a mergejoinable operator can
- *	contribute to an equivalence set, even if it's not a join clause.
- *
- *	-- bjm & tgl
- *--------------------
- */
+							  AttrNumber varattno);
 
 
 /*
@@ -225,36 +89,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