1 files changed, 70 insertions, 75 deletions

diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index da0cc7f266c..9ae1bf31d5e 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -3791,6 +3791,8 @@ create_mergejoin_plan(PlannerInfo *root,
 	Oid		   *mergecollations;
 	int		   *mergestrategies;
 	bool	   *mergenullsfirst;
+	PathKey    *opathkey;
+	EquivalenceClass *opeclass;
 	int			i;
 	ListCell   *lc;
 	ListCell   *lop;
@@ -3909,7 +3911,8 @@ create_mergejoin_plan(PlannerInfo *root,
 	 * Compute the opfamily/collation/strategy/nullsfirst arrays needed by the
 	 * executor.  The information is in the pathkeys for the two inputs, but
 	 * we need to be careful about the possibility of mergeclauses sharing a
-	 * pathkey (compare find_mergeclauses_for_pathkeys()).
+	 * pathkey, as well as the possibility that the inner pathkeys are not in
+	 * an order matching the mergeclauses.
 	 */
 	nClauses = list_length(mergeclauses);
 	Assert(nClauses == list_length(best_path->path_mergeclauses));
@@ -3918,6 +3921,8 @@ create_mergejoin_plan(PlannerInfo *root,
 	mergestrategies = (int *) palloc(nClauses * sizeof(int));
 	mergenullsfirst = (bool *) palloc(nClauses * sizeof(bool));
 
+	opathkey = NULL;
+	opeclass = NULL;
 	lop = list_head(outerpathkeys);
 	lip = list_head(innerpathkeys);
 	i = 0;
@@ -3926,11 +3931,9 @@ create_mergejoin_plan(PlannerInfo *root,
 		RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
 		EquivalenceClass *oeclass;
 		EquivalenceClass *ieclass;
-		PathKey    *opathkey;
-		PathKey    *ipathkey;
-		EquivalenceClass *opeclass;
-		EquivalenceClass *ipeclass;
-		ListCell   *l2;
+		PathKey    *ipathkey = NULL;
+		EquivalenceClass *ipeclass = NULL;
+		bool		first_inner_match = false;
 
 		/* fetch outer/inner eclass from mergeclause */
 		if (rinfo->outer_is_left)
@@ -3947,104 +3950,96 @@ create_mergejoin_plan(PlannerInfo *root,
 		Assert(ieclass != NULL);
 
 		/*
-		 * For debugging purposes, we check that the eclasses match the paths'
-		 * pathkeys.  In typical cases the merge clauses are one-to-one with
-		 * the pathkeys, but when dealing with partially redundant query
-		 * conditions, we might have clauses that re-reference earlier path
-		 * keys.  The case that we need to reject is where a pathkey is
-		 * entirely skipped over.
+		 * We must identify the pathkey elements associated with this clause
+		 * by matching the eclasses (which should give a unique match, since
+		 * the pathkey lists should be canonical).  In typical cases the merge
+		 * clauses are one-to-one with the pathkeys, but when dealing with
+		 * partially redundant query conditions, things are more complicated.
 		 *
-		 * lop and lip reference the first as-yet-unused pathkey elements;
-		 * it's okay to match them, or any element before them.  If they're
-		 * NULL then we have found all pathkey elements to be used.
+		 * lop and lip reference the first as-yet-unmatched pathkey elements.
+		 * If they're NULL then all pathkey elements have been matched.
+		 *
+		 * The ordering of the outer pathkeys should match the mergeclauses,
+		 * by construction (see find_mergeclauses_for_outer_pathkeys()). There
+		 * could be more than one mergeclause for the same outer pathkey, but
+		 * no pathkey may be entirely skipped over.
 		 */
-		if (lop)
+		if (oeclass != opeclass)	/* multiple matches are not interesting */
 		{
+			/* doesn't match the current opathkey, so must match the next */
+			if (lop == NULL)
+				elog(ERROR, "outer pathkeys do not match mergeclauses");
 			opathkey = (PathKey *) lfirst(lop);
 			opeclass = opathkey->pk_eclass;
-			if (oeclass == opeclass)
-			{
-				/* fast path for typical case */
-				lop = lnext(lop);
-			}
-			else
-			{
-				/* redundant clauses ... must match something before lop */
-				foreach(l2, outerpathkeys)
-				{
-					if (l2 == lop)
-						break;
-					opathkey = (PathKey *) lfirst(l2);
-					opeclass = opathkey->pk_eclass;
-					if (oeclass == opeclass)
-						break;
-				}
-				if (oeclass != opeclass)
-					elog(ERROR, "outer pathkeys do not match mergeclauses");
-			}
-		}
-		else
-		{
-			/* redundant clauses ... must match some already-used pathkey */
-			opathkey = NULL;
-			opeclass = NULL;
-			foreach(l2, outerpathkeys)
-			{
-				opathkey = (PathKey *) lfirst(l2);
-				opeclass = opathkey->pk_eclass;
-				if (oeclass == opeclass)
-					break;
-			}
-			if (l2 == NULL)
+			lop = lnext(lop);
+			if (oeclass != opeclass)
 				elog(ERROR, "outer pathkeys do not match mergeclauses");
 		}
 
+		/*
+		 * The inner pathkeys likewise should not have skipped-over keys, but
+		 * it's possible for a mergeclause to reference some earlier inner
+		 * pathkey if we had redundant pathkeys.  For example we might have
+		 * mergeclauses like "o.a = i.x AND o.b = i.y AND o.c = i.x".  The
+		 * implied inner ordering is then "ORDER BY x, y, x", but the pathkey
+		 * mechanism drops the second sort by x as redundant, and this code
+		 * must cope.
+		 *
+		 * It's also possible for the implied inner-rel ordering to be like
+		 * "ORDER BY x, y, x DESC".  We still drop the second instance of x as
+		 * redundant; but this means that the sort ordering of a redundant
+		 * inner pathkey should not be considered significant.  So we must
+		 * detect whether this is the first clause matching an inner pathkey.
+		 */
 		if (lip)
 		{
 			ipathkey = (PathKey *) lfirst(lip);
 			ipeclass = ipathkey->pk_eclass;
 			if (ieclass == ipeclass)
 			{
-				/* fast path for typical case */
+				/* successful first match to this inner pathkey */
 				lip = lnext(lip);
-			}
-			else
-			{
-				/* redundant clauses ... must match something before lip */
-				foreach(l2, innerpathkeys)
-				{
-					if (l2 == lip)
-						break;
-					ipathkey = (PathKey *) lfirst(l2);
-					ipeclass = ipathkey->pk_eclass;
-					if (ieclass == ipeclass)
-						break;
-				}
-				if (ieclass != ipeclass)
-					elog(ERROR, "inner pathkeys do not match mergeclauses");
+				first_inner_match = true;
 			}
 		}
-		else
+		if (!first_inner_match)
 		{
-			/* redundant clauses ... must match some already-used pathkey */
-			ipathkey = NULL;
-			ipeclass = NULL;
+			/* redundant clause ... must match something before lip */
+			ListCell   *l2;
+
 			foreach(l2, innerpathkeys)
 			{
+				if (l2 == lip)
+					break;
 				ipathkey = (PathKey *) lfirst(l2);
 				ipeclass = ipathkey->pk_eclass;
 				if (ieclass == ipeclass)
 					break;
 			}
-			if (l2 == NULL)
+			if (ieclass != ipeclass)
 				elog(ERROR, "inner pathkeys do not match mergeclauses");
 		}
 
-		/* pathkeys should match each other too (more debugging) */
+		/*
+		 * The pathkeys should always match each other as to opfamily and
+		 * collation (which affect equality), but if we're considering a
+		 * redundant inner pathkey, its sort ordering might not match.  In
+		 * such cases we may ignore the inner pathkey's sort ordering and use
+		 * the outer's.  (In effect, we're lying to the executor about the
+		 * sort direction of this inner column, but it does not matter since
+		 * the run-time row comparisons would only reach this column when
+		 * there's equality for the earlier column containing the same eclass.
+		 * There could be only one value in this column for the range of inner
+		 * rows having a given value in the earlier column, so it does not
+		 * matter which way we imagine this column to be ordered.)  But a
+		 * non-redundant inner pathkey had better match outer's ordering too.
+		 */
 		if (opathkey->pk_opfamily != ipathkey->pk_opfamily ||
-			opathkey->pk_eclass->ec_collation != ipathkey->pk_eclass->ec_collation ||
-			opathkey->pk_strategy != ipathkey->pk_strategy ||
-			opathkey->pk_nulls_first != ipathkey->pk_nulls_first)
+			opathkey->pk_eclass->ec_collation != ipathkey->pk_eclass->ec_collation)
+			elog(ERROR, "left and right pathkeys do not match in mergejoin");
+		if (first_inner_match &&
+			(opathkey->pk_strategy != ipathkey->pk_strategy ||
+			 opathkey->pk_nulls_first != ipathkey->pk_nulls_first))
 			elog(ERROR, "left and right pathkeys do not match in mergejoin");
 
 		/* OK, save info for executor */