Update pathkeys comparison function.

3 files changed, 57 insertions, 49 deletions

diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index e19eeec01ff..f1ea6cbae68 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.3 1999/02/20 16:32:35 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.4 1999/02/20 18:01:01 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -54,7 +54,7 @@ static List *new_matching_subkeys(Var *subkey, List *considered_subkeys,
  *	{ {tab1.col1, tab2.col1} }.  This allows future joins to use either Var
  *	as a pre-sorted key to prevent Mergejoins from having to re-sort the Path.
  *	They are equal, so they are both primary sort keys.  This is why pathkeys
- *	is a List of Lists.
+ *	is a List of Lists.  -- bjm
  */
  
 /****************************************************************************
diff --git a/src/backend/optimizer/util/keys.c b/src/backend/optimizer/util/keys.c
index 123b6dc4cb4..c921c24c0d1 100644
--- a/src/backend/optimizer/util/keys.c
+++ b/src/backend/optimizer/util/keys.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/keys.c,v 1.18 1999/02/19 02:05:16 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/Attic/keys.c,v 1.19 1999/02/20 18:01:02 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -110,62 +110,70 @@ extract_join_key(JoinKey *jk, int outer_or_inner)
  *	  Returns t iff two sets of path keys are equivalent.  They are
  *	  equivalent if the first Var nodes match the second Var nodes.
  *
- *	  XXX		It isn't necessary to check that each sublist exactly contain
- *				the same elements because if the routine that built these
- *				sublists together is correct, having one element in common
- *				implies having all elements in common.
- *		Huh? bjm
+ *	See the top of optimizer/path/pathkeys.c for a description of pathkeys.
+ *	Each pathkey is ordered by its join order, so they not pre-ordered to
+ *	match.  We must search them ourselves.
  *
+ *	This gets called a lot, so it is optimized.
  */
 bool
 pathkeys_match(List *keys1, List *keys2, int *better_key)
 {
 	List	   *key1,
-			   *key2,
-			   *key1a,
-			   *key2a;
+			   *key2;
+	bool		key1_subsetof_key2 = true,
+				key2_subsetof_key1 = true;
 
 	for (key1 = keys1, key2 = keys2;
 		 key1 != NIL && key2 != NIL;
 		 key1 = lnext(key1), key2 = lnext(key2))
 	{
-		for (key1a = lfirst(key1), key2a = lfirst(key2);
-			 key1a != NIL && key2a != NIL;
-			 key1a = lnext(key1a), key2a = lnext(key2a))
-			if (!equal(lfirst(key1a), lfirst(key2a)))
+		List *i;
+
+		if (key1_subsetof_key2)
+			foreach(i, lfirst(key1))
 			{
-				*better_key = 0;
-				return false;
+				Var	*subkey = lfirst(i);
+				if (!member(subkey, lfirst(key2)))
+				{
+					key1_subsetof_key2 = false;
+					break;
+				}
 			}
-		if (key1a != NIL && key2a == NIL)
-		{
-			*better_key = 1;
-			return true;
-		}
-		if (key1a == NIL && key2a != NIL)
-		{
-			*better_key = 2;
-			return true;
-		}
+
+		if (key2_subsetof_key1)
+			foreach(i, lfirst(key2))
+			{
+				Var	*subkey = lfirst(i);
+				if (!member(subkey, lfirst(key1)))
+				{
+					key2_subsetof_key1 = false;
+					break;
+				}
+			}
+		if (!key1_subsetof_key2 && !key2_subsetof_key1)
+			break;	/* no need to continue comparisons. */
 	}
 
-	/* Now the result should be true if list keys2 has at least as many
-	 * entries as keys1, ie, we did not fall off the end of keys2 first.
-	 * If key1 is now NIL then we hit the end of keys1 before or at the
-	 * same time as the end of keys2.
-	 */
-	if (key1 != NIL && key2 == NIL)
+	if (!key1_subsetof_key2 && !key2_subsetof_key1)
 	{
-		*better_key = 1;
-		return true;
+		*better_key = 0;
+		return false;
 	}
-	if (key1 == NIL && key2 != NIL)
+	if (key1_subsetof_key2 && !key2_subsetof_key1)
 	{
 		*better_key = 2;
 		return true;
 	}
+	if (!key1_subsetof_key2 && key2_subsetof_key1)
+	{
+		*better_key = 1;
+		return true;
+	}
+
 	*better_key = 0;
 	return true;
+
 }
 
 /*
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 9041a9fe9b7..d94e124193e 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.37 1999/02/18 00:49:38 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.38 1999/02/20 18:01:02 momjian Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -172,15 +172,15 @@ better_path(Path *new_path, List *unique_paths, bool *is_new)
 	{
 		path = (Path *) lfirst(temp);
 
-#if 0
-/*def OPTDUP_DEBUG*/
+#ifdef OPTDUP_DEBUG
 		if (!pathkeys_match(new_path->pathkeys, path->pathkeys, &better_key) ||
 		    better_key != 0)
 		{
-			printf("oldpath\n");
-			pprint(path->pathkeys);
+			printf("betterkey = %d\n", better_key);
 			printf("newpath\n");
 			pprint(new_path->pathkeys);
+			printf("oldpath\n");
+			pprint(path->pathkeys);
 			if (path->pathkeys && new_path->pathkeys &&
 				length(lfirst(path->pathkeys)) >= 2/* &&
 				length(lfirst(path->pathkeys)) <
@@ -191,10 +191,10 @@ better_path(Path *new_path, List *unique_paths, bool *is_new)
 			&better_sort) ||
 			better_sort != 0)
 		{
-			printf("oldord\n");
-			pprint(path->pathorder);
 			printf("neword\n");
 			pprint(new_path->pathorder);
+			printf("oldord\n");
+			pprint(path->pathorder);
 		}
 #endif
 
@@ -204,8 +204,8 @@ better_path(Path *new_path, List *unique_paths, bool *is_new)
 			&better_sort))
 		{
 			/*
-			 * Replace pathkeys that match exactly, (1,2), (1,2).
-			 * Replace pathkeys (1,2) with (1,2,3) if the latter is not
+			 * Replace pathkeys that match exactly, {{1,2}}, {{1,2}}
+			 * Replace pathkeys {{1,2}}with {{1,2,3}}} if the latter is not
 			 * more expensive and replace unordered path with ordered
 			 * path if it is not more expensive.  Favor sorted keys
 			 * over unsorted keys in the same way.
@@ -221,10 +221,10 @@ better_path(Path *new_path, List *unique_paths, bool *is_new)
 			{
 #ifdef OPTDUP_DEBUG
 				printf("replace with new %p old %p better key %d better sort %d\n", &new_path, &path, better_key, better_sort);
-				printf("old\n");
-				pprint(path);
 				printf("new\n");
 				pprint(new_path);
+				printf("old\n");
+				pprint(path);
 #endif
 				*is_new = false;
 				return path;
@@ -241,10 +241,10 @@ better_path(Path *new_path, List *unique_paths, bool *is_new)
 			{
 #ifdef OPTDUP_DEBUG
 				printf("skip new %p old %p better key %d better sort %d\n", &new_path, &path, better_key, better_sort);
-				printf("old\n");
-				pprint(path);
 				printf("new\n");
 				pprint(new_path);
+				printf("old\n");
+				pprint(path);
 #endif
 				*is_new = false;
 				return NULL;