Fix EquivalenceClass code to handle volatile sort expressions in a more

predictable manner; in particular that if you say ORDER BY output-column-ref,
it will in fact sort by that specific column even if there are multiple
syntactic matches.  An example is
	SELECT random() AS a, random() AS b FROM ... ORDER BY b, a;
While the use-case for this might be a bit debatable, it worked as expected
in earlier releases, so we should preserve the behavior for 8.3.  Per my
recent proposal.

While at it, fix convert_subquery_pathkeys() to handle RelabelType stripping
in both directions; it needs this for the same reasons make_sort_from_pathkeys
does.

8 files changed, 300 insertions, 183 deletions

diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 005879b8c91..fc4f7d2daca 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.315 2007/10/11 18:05:27 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.316 2007/11/08 21:49:47 tgl Exp $
  *
  * NOTES
  *	  Every node type that can appear in stored rules' parsetrees *must*
@@ -1405,6 +1405,7 @@ _outEquivalenceClass(StringInfo str, EquivalenceClass *node)
 	WRITE_BOOL_FIELD(ec_has_volatile);
 	WRITE_BOOL_FIELD(ec_below_outer_join);
 	WRITE_BOOL_FIELD(ec_broken);
+	WRITE_UINT_FIELD(ec_sortref);
 }
 
 static void
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index fc862438ffb..18c6ff93686 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -10,7 +10,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/path/equivclass.c,v 1.3 2007/07/07 20:46:45 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/path/equivclass.c,v 1.4 2007/11/08 21:49:47 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -294,6 +294,7 @@ process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo,
 		ec->ec_has_volatile = false;
 		ec->ec_below_outer_join = below_outer_join;
 		ec->ec_broken = false;
+		ec->ec_sortref = 0;
 		ec->ec_merged = NULL;
 		em1 = add_eq_member(ec, item1, item1_relids, false, item1_type);
 		em2 = add_eq_member(ec, item2, item2_relids, false, item2_type);
@@ -354,6 +355,9 @@ add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
  *	  class it is a member of; if none, build a new single-member
  *	  EquivalenceClass for it.
  *
+ * sortref is the SortGroupRef of the originating SortClause, if any,
+ * or zero if not.
+ *
  * This can be used safely both before and after EquivalenceClass merging;
  * since it never causes merging it does not invalidate any existing ECs
  * or PathKeys.
@@ -367,7 +371,8 @@ EquivalenceClass *
 get_eclass_for_sort_expr(PlannerInfo *root,
 						 Expr *expr,
 						 Oid expr_datatype,
-						 List *opfamilies)
+						 List *opfamilies,
+						 Index sortref)
 {
 	EquivalenceClass *newec;
 	EquivalenceMember *newem;
@@ -382,7 +387,9 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 		EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
 		ListCell   *lc2;
 
-		/* we allow matching to a volatile EC here */
+		/* Never match to a volatile EC */
+		if (cur_ec->ec_has_volatile)
+			continue;
 
 		if (!equal(opfamilies, cur_ec->ec_opfamilies))
 			continue;
@@ -423,6 +430,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
 	newec->ec_has_volatile = contain_volatile_functions((Node *) expr);
 	newec->ec_below_outer_join = false;
 	newec->ec_broken = false;
+	newec->ec_sortref = sortref;
 	newec->ec_merged = NULL;
 	newem = add_eq_member(newec, expr, pull_varnos((Node *) expr),
 						  false, expr_datatype);
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index f96d7bb5554..846fe78ee6c 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
- *	  $PostgreSQL: pgsql/src/backend/optimizer/path/pathkeys.c,v 1.88 2007/11/08 19:25:37 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/path/pathkeys.c,v 1.89 2007/11/08 21:49:47 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -46,6 +46,7 @@ static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
 static PathKey *make_pathkey_from_sortinfo(PlannerInfo *root,
 						   Expr *expr, Oid ordering_op,
 						   bool nulls_first,
+						   Index sortref,
 						   bool canonicalize);
 static Var *find_indexkey_var(PlannerInfo *root, RelOptInfo *rel,
 				  AttrNumber varattno);
@@ -233,6 +234,9 @@ canonicalize_pathkeys(PlannerInfo *root, List *pathkeys)
  *	  a PathKey.  If canonicalize = true, the result is a "canonical"
  *	  PathKey, otherwise not.  (But note it might be redundant anyway.)
  *
+ * If the PathKey is being generated from a SortClause, sortref should be
+ * the SortClause's SortGroupRef; otherwise zero.
+ *
  * canonicalize should always be TRUE after EquivalenceClass merging has
  * been performed, but FALSE if we haven't done EquivalenceClass merging yet.
  */
@@ -240,6 +244,7 @@ static PathKey *
 make_pathkey_from_sortinfo(PlannerInfo *root,
 						   Expr *expr, Oid ordering_op,
 						   bool nulls_first,
+						   Index sortref,
 						   bool canonicalize)
 {
 	Oid			opfamily,
@@ -303,7 +308,8 @@ make_pathkey_from_sortinfo(PlannerInfo *root,
 	}
 
 	/* Now find or create a matching EquivalenceClass */
-	eclass = get_eclass_for_sort_expr(root, expr, opcintype, opfamilies);
+	eclass = get_eclass_for_sort_expr(root, expr, opcintype, opfamilies,
+									  sortref);
 
 	/* And finally we can find or create a PathKey node */
 	if (canonicalize)
@@ -525,6 +531,7 @@ build_index_pathkeys(PlannerInfo *root,
 											  indexkey,
 											  sortop,
 											  nulls_first,
+											  0,
 											  true);
 
 		/* Add to list unless redundant */
@@ -597,102 +604,161 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
 		PathKey	   *sub_pathkey = (PathKey *) lfirst(i);
 		EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
 		PathKey	   *best_pathkey = NULL;
-		int			best_score = -1;
-		ListCell   *j;
 
-		/*
-		 * The sub_pathkey's EquivalenceClass could contain multiple elements
-		 * (representing knowledge that multiple items are effectively equal).
-		 * Each element might match none, one, or more of the output columns
-		 * that are visible to the outer query. This means we may have
-		 * multiple possible representations of the sub_pathkey in the context
-		 * of the outer query.  Ideally we would generate them all and put
-		 * them all into an EC of the outer query, thereby propagating
-		 * equality knowledge up to the outer query.  Right now we cannot do
-		 * so, because the outer query's EquivalenceClasses are already frozen
-		 * when this is called. Instead we prefer the one that has the highest
-		 * "score" (number of EC peers, plus one if it matches the outer
-		 * query_pathkeys). This is the most likely to be useful in the outer
-		 * query.
-		 */
-		foreach(j, sub_eclass->ec_members)
+		if (sub_eclass->ec_has_volatile)
 		{
-			EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
-			Expr	   *sub_expr = sub_member->em_expr;
-			Expr	   *rtarg;
-			ListCell   *k;
-
 			/*
-			 * We handle two cases: the sub_pathkey key can be either an exact
-			 * match for a targetlist entry, or a RelabelType of a targetlist
-			 * entry.  (The latter case is worth extra code because it arises
-			 * frequently in connection with varchar fields.)
+			 * If the sub_pathkey's EquivalenceClass is volatile, then it must
+			 * have come from an ORDER BY clause, and we have to match it to
+			 * that same targetlist entry.
 			 */
-			if (IsA(sub_expr, RelabelType))
-				rtarg = ((RelabelType *) sub_expr)->arg;
-			else
-				rtarg = NULL;
-
-			foreach(k, sub_tlist)
+			TargetEntry *tle;
+
+			if (sub_eclass->ec_sortref == 0)		/* can't happen */
+				elog(ERROR, "volatile EquivalenceClass has no sortref");
+			tle = get_sortgroupref_tle(sub_eclass->ec_sortref, sub_tlist);
+			Assert(tle);
+			/* resjunk items aren't visible to outer query */
+			if (!tle->resjunk)
 			{
-				TargetEntry *tle = (TargetEntry *) lfirst(k);
+				/* We can represent this sub_pathkey */
+				EquivalenceMember *sub_member;
 				Expr	   *outer_expr;
 				EquivalenceClass *outer_ec;
-				PathKey	   *outer_pk;
-				int			score;
 
-				/* resjunk items aren't visible to outer query */
-				if (tle->resjunk)
-					continue;
+				Assert(list_length(sub_eclass->ec_members) == 1);
+				sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
+				outer_expr = (Expr *)
+					makeVar(rel->relid,
+							tle->resno,
+							exprType((Node *) tle->expr),
+							exprTypmod((Node *) tle->expr),
+							0);
+				outer_ec =
+					get_eclass_for_sort_expr(root,
+											 outer_expr,
+											 sub_member->em_datatype,
+											 sub_eclass->ec_opfamilies,
+											 0);
+				best_pathkey =
+					make_canonical_pathkey(root,
+										   outer_ec,
+										   sub_pathkey->pk_opfamily,
+										   sub_pathkey->pk_strategy,
+										   sub_pathkey->pk_nulls_first);
+			}
+		}
+		else
+		{
+			/*
+			 * Otherwise, the sub_pathkey's EquivalenceClass could contain
+			 * multiple elements (representing knowledge that multiple items
+			 * are effectively equal).  Each element might match none, one, or
+			 * more of the output columns that are visible to the outer
+			 * query. This means we may have multiple possible representations
+			 * of the sub_pathkey in the context of the outer query.  Ideally
+			 * we would generate them all and put them all into an EC of the
+			 * outer query, thereby propagating equality knowledge up to the
+			 * outer query.  Right now we cannot do so, because the outer
+			 * query's EquivalenceClasses are already frozen when this is
+			 * called. Instead we prefer the one that has the highest "score"
+			 * (number of EC peers, plus one if it matches the outer
+			 * query_pathkeys). This is the most likely to be useful in the
+			 * outer query.
+			 */
+			int			best_score = -1;
+			ListCell   *j;
 
-				if (equal(tle->expr, sub_expr))
-				{
-					/* Exact match */
-					outer_expr = (Expr *)
-						makeVar(rel->relid,
-								tle->resno,
-								exprType((Node *) tle->expr),
-								exprTypmod((Node *) tle->expr),
-								0);
-				}
-				else if (rtarg && equal(tle->expr, rtarg))
+			foreach(j, sub_eclass->ec_members)
+			{
+				EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
+				Expr	   *sub_expr = sub_member->em_expr;
+				Expr	   *sub_stripped;
+				ListCell   *k;
+
+				/*
+				 * We handle two cases: the sub_pathkey key can be either an
+				 * exact match for a targetlist entry, or it could match after
+				 * stripping RelabelType nodes.  (We need that case since
+				 * make_pathkey_from_sortinfo could add or remove RelabelType.)
+				 */
+				sub_stripped = sub_expr;
+				while (sub_stripped && IsA(sub_stripped, RelabelType))
+					sub_stripped = ((RelabelType *) sub_stripped)->arg;
+
+				foreach(k, sub_tlist)
 				{
-					/* Match after discarding RelabelType */
-					outer_expr = (Expr *)
-						makeVar(rel->relid,
-								tle->resno,
-								exprType((Node *) tle->expr),
-								exprTypmod((Node *) tle->expr),
-								0);
-					outer_expr = (Expr *)
-						makeRelabelType((Expr *) outer_expr,
-										((RelabelType *) sub_expr)->resulttype,
-									 ((RelabelType *) sub_expr)->resulttypmod,
-								   ((RelabelType *) sub_expr)->relabelformat);
-				}
-				else
-					continue;
+					TargetEntry *tle = (TargetEntry *) lfirst(k);
+					Expr	   *outer_expr;
+					EquivalenceClass *outer_ec;
+					PathKey	   *outer_pk;
+					int			score;
 
-				/* Found a representation for this sub_pathkey */
-				outer_ec = get_eclass_for_sort_expr(root,
-													outer_expr,
-													sub_member->em_datatype,
-													sub_eclass->ec_opfamilies);
-				outer_pk = make_canonical_pathkey(root,
-												  outer_ec,
-												  sub_pathkey->pk_opfamily,
-												  sub_pathkey->pk_strategy,
-												  sub_pathkey->pk_nulls_first);
-				/* score = # of equivalence peers */
-				score = list_length(outer_ec->ec_members) - 1;
-				/* +1 if it matches the proper query_pathkeys item */
-				if (retvallen < outer_query_keys &&
-					list_nth(root->query_pathkeys, retvallen) == outer_pk)
-					score++;
-				if (score > best_score)
-				{
-					best_pathkey = outer_pk;
-					best_score = score;
+					/* resjunk items aren't visible to outer query */
+					if (tle->resjunk)
+						continue;
+
+					if (equal(tle->expr, sub_expr))
+					{
+						/* Exact match */
+						outer_expr = (Expr *)
+							makeVar(rel->relid,
+									tle->resno,
+									exprType((Node *) tle->expr),
+									exprTypmod((Node *) tle->expr),
+									0);
+					}
+					else
+					{
+						Expr	   *tle_stripped;
+
+						tle_stripped = tle->expr;
+						while (tle_stripped && IsA(tle_stripped, RelabelType))
+							tle_stripped = ((RelabelType *) tle_stripped)->arg;
+
+						if (equal(tle_stripped, sub_stripped))
+						{
+							/* Match after discarding RelabelType */
+							outer_expr = (Expr *)
+								makeVar(rel->relid,
+										tle->resno,
+										exprType((Node *) tle->expr),
+										exprTypmod((Node *) tle->expr),
+										0);
+							if (exprType((Node *) outer_expr) !=
+								exprType((Node *) sub_expr))
+								outer_expr = (Expr *)
+									makeRelabelType(outer_expr,
+													exprType((Node *) sub_expr),
+													-1,
+													COERCE_DONTCARE);
+						}
+						else
+							continue;
+					}
+
+					/* Found a representation for this sub_pathkey */
+					outer_ec = get_eclass_for_sort_expr(root,
+														outer_expr,
+														sub_member->em_datatype,
+														sub_eclass->ec_opfamilies,
+														0);
+					outer_pk = make_canonical_pathkey(root,
+													  outer_ec,
+													  sub_pathkey->pk_opfamily,
+													  sub_pathkey->pk_strategy,
+													  sub_pathkey->pk_nulls_first);
+					/* score = # of equivalence peers */
+					score = list_length(outer_ec->ec_members) - 1;
+					/* +1 if it matches the proper query_pathkeys item */
+					if (retvallen < outer_query_keys &&
+						list_nth(root->query_pathkeys, retvallen) == outer_pk)
+						score++;
+					if (score > best_score)
+					{
+						best_pathkey = outer_pk;
+						best_score = score;
+					}
 				}
 			}
 		}
@@ -795,6 +861,7 @@ make_pathkeys_for_sortclauses(PlannerInfo *root,
 											 sortkey,
 											 sortcl->sortop,
 											 sortcl->nulls_first,
+											 sortcl->tleSortGroupRef,
 											 canonicalize);
 
 		/* Canonical form eliminates redundant ordering keys */
@@ -843,12 +910,14 @@ cache_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
 			get_eclass_for_sort_expr(root,
 									 (Expr *) get_leftop(clause),
 									 lefttype,
-									 restrictinfo->mergeopfamilies);
+									 restrictinfo->mergeopfamilies,
+									 0);
 		restrictinfo->right_ec =
 			get_eclass_for_sort_expr(root,
 									 (Expr *) get_rightop(clause),
 									 righttype,
-									 restrictinfo->mergeopfamilies);
+									 restrictinfo->mergeopfamilies,
+									 0);
 	}
 	else
 		Assert(restrictinfo->right_ec != NULL);
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index becb8255e87..e2b46f970ce 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -10,7 +10,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.233 2007/11/08 19:25:37 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.234 2007/11/08 21:49:47 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -2730,103 +2730,124 @@ make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
 	foreach(i, pathkeys)
 	{
 		PathKey	   *pathkey = (PathKey *) lfirst(i);
+		EquivalenceClass *ec = pathkey->pk_eclass;
 		TargetEntry *tle = NULL;
 		Oid			pk_datatype = InvalidOid;
 		Oid			sortop;
 		ListCell   *j;
 
-		/*
-		 * We can sort by any non-constant expression listed in the pathkey's
-		 * EquivalenceClass.  For now, we take the first one that corresponds
-		 * to an available item in the tlist. If there isn't any, use the first
-		 * one that is an expression in the input's vars.  (The non-const
-		 * restriction only matters if the EC is below_outer_join; but if it
-		 * isn't, it won't contain consts anyway, else we'd have discarded
-		 * the pathkey as redundant.)
-		 *
-		 * XXX if we have a choice, is there any way of figuring out which
-		 * might be cheapest to execute?  (For example, int4lt is likely much
-		 * cheaper to execute than numericlt, but both might appear in the
-		 * same equivalence class...)  Not clear that we ever will have an
-		 * interesting choice in practice, so it may not matter.
-		 */
-		foreach(j, pathkey->pk_eclass->ec_members)
+		if (ec->ec_has_volatile)
 		{
-			EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
-
-			if (em->em_is_const || em->em_is_child)
-				continue;
-
-			tle = tlist_member((Node *) em->em_expr, tlist);
-			if (tle)
-			{
-				pk_datatype = em->em_datatype;
-				break;			/* found expr already in tlist */
-			}
-
 			/*
-			 * We can also use it if the pathkey expression is a relabel
-			 * of the tlist entry, or vice versa.  This is needed for
-			 * binary-compatible cases (cf. make_pathkey_from_sortinfo).
-			 * We prefer an exact match, though, so we do the basic
-			 * search first.
+			 * If the pathkey's EquivalenceClass is volatile, then it must
+			 * have come from an ORDER BY clause, and we have to match it to
+			 * that same targetlist entry.
 			 */
-			tle = tlist_member_ignore_relabel((Node *) em->em_expr, tlist);
-			if (tle)
-			{
-				pk_datatype = em->em_datatype;
-				break;			/* found expr already in tlist */
-			}
+			if (ec->ec_sortref == 0)		/* can't happen */
+				elog(ERROR, "volatile EquivalenceClass has no sortref");
+			tle = get_sortgroupref_tle(ec->ec_sortref, tlist);
+			Assert(tle);
+			Assert(list_length(ec->ec_members) == 1);
+			pk_datatype = ((EquivalenceMember *) linitial(ec->ec_members))->em_datatype;
 		}
-		if (!tle)
+		else
 		{
-			/* No matching tlist item; look for a computable expression */
-			Expr   *sortexpr = NULL;
-
-			foreach(j, pathkey->pk_eclass->ec_members)
+			/*
+			 * Otherwise, we can sort by any non-constant expression listed in
+			 * the pathkey's EquivalenceClass.  For now, we take the first one
+			 * that corresponds to an available item in the tlist.  If there
+			 * isn't any, use the first one that is an expression in the
+			 * input's vars.  (The non-const restriction only matters if the
+			 * EC is below_outer_join; but if it isn't, it won't contain
+			 * consts anyway, else we'd have discarded the pathkey as
+			 * redundant.)
+			 *
+			 * XXX if we have a choice, is there any way of figuring out which
+			 * might be cheapest to execute?  (For example, int4lt is likely
+			 * much cheaper to execute than numericlt, but both might appear
+			 * in the same equivalence class...)  Not clear that we ever will
+			 * have an interesting choice in practice, so it may not matter.
+			 */
+			foreach(j, ec->ec_members)
 			{
 				EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
-				List	   *exprvars;
-				ListCell   *k;
 
 				if (em->em_is_const || em->em_is_child)
 					continue;
-				sortexpr = em->em_expr;
-				exprvars = pull_var_clause((Node *) sortexpr, false);
-				foreach(k, exprvars)
+
+				tle = tlist_member((Node *) em->em_expr, tlist);
+				if (tle)
 				{
-					if (!tlist_member_ignore_relabel(lfirst(k), tlist))
-						break;
+					pk_datatype = em->em_datatype;
+					break;			/* found expr already in tlist */
 				}
-				list_free(exprvars);
-				if (!k)
+
+				/*
+				 * We can also use it if the pathkey expression is a relabel
+				 * of the tlist entry, or vice versa.  This is needed for
+				 * binary-compatible cases (cf. make_pathkey_from_sortinfo).
+				 * We prefer an exact match, though, so we do the basic
+				 * search first.
+				 */
+				tle = tlist_member_ignore_relabel((Node *) em->em_expr, tlist);
+				if (tle)
 				{
 					pk_datatype = em->em_datatype;
-					break;		/* found usable expression */
+					break;			/* found expr already in tlist */
 				}
 			}
-			if (!j)
-				elog(ERROR, "could not find pathkey item to sort");
 
-			/*
-			 * Do we need to insert a Result node?
-			 */
-			if (!is_projection_capable_plan(lefttree))
+			if (!tle)
 			{
-				/* copy needed so we don't modify input's tlist below */
-				tlist = copyObject(tlist);
-				lefttree = (Plan *) make_result(root, tlist, NULL, lefttree);
-			}
+				/* No matching tlist item; look for a computable expression */
+				Expr   *sortexpr = NULL;
 
-			/*
-			 * Add resjunk entry to input's tlist
-			 */
-			tle = makeTargetEntry(sortexpr,
-								  list_length(tlist) + 1,
-								  NULL,
-								  true);
-			tlist = lappend(tlist, tle);
-			lefttree->targetlist = tlist;		/* just in case NIL before */
+				foreach(j, ec->ec_members)
+				{
+					EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
+					List	   *exprvars;
+					ListCell   *k;
+
+					if (em->em_is_const || em->em_is_child)
+						continue;
+					sortexpr = em->em_expr;
+					exprvars = pull_var_clause((Node *) sortexpr, false);
+					foreach(k, exprvars)
+					{
+						if (!tlist_member_ignore_relabel(lfirst(k), tlist))
+							break;
+					}
+					list_free(exprvars);
+					if (!k)
+					{
+						pk_datatype = em->em_datatype;
+						break;		/* found usable expression */
+					}
+				}
+				if (!j)
+					elog(ERROR, "could not find pathkey item to sort");
+
+				/*
+				 * Do we need to insert a Result node?
+				 */
+				if (!is_projection_capable_plan(lefttree))
+				{
+					/* copy needed so we don't modify input's tlist below */
+					tlist = copyObject(tlist);
+					lefttree = (Plan *) make_result(root, tlist, NULL,
+													lefttree);
+				}
+
+				/*
+				 * Add resjunk entry to input's tlist
+				 */
+				tle = makeTargetEntry(sortexpr,
+									  list_length(tlist) + 1,
+									  NULL,
+									  true);
+				tlist = lappend(tlist, tle);
+				lefttree->targetlist = tlist;	/* just in case NIL before */
+			}
 		}
 
 		/*
diff --git a/src/backend/optimizer/util/tlist.c b/src/backend/optimizer/util/tlist.c
index e58fe7dc7f1..d2ac14cfa1b 100644
--- a/src/backend/optimizer/util/tlist.c
+++ b/src/backend/optimizer/util/tlist.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/util/tlist.c,v 1.75 2007/11/08 19:25:37 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/util/tlist.c,v 1.76 2007/11/08 21:49:47 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -131,26 +131,22 @@ add_to_flat_tlist(List *tlist, List *vars)
 	return tlist;
 }
 
+
 /*
- * get_sortgroupclause_tle
- *		Find the targetlist entry matching the given SortClause
- *		(or GroupClause) by ressortgroupref, and return it.
- *
- * Because GroupClause is typedef'd as SortClause, either kind of
- * node can be passed without casting.
+ * get_sortgroupref_tle
+ *		Find the targetlist entry matching the given SortGroupRef index,
+ *		and return it.
  */
 TargetEntry *
-get_sortgroupclause_tle(SortClause *sortClause,
-						List *targetList)
+get_sortgroupref_tle(Index sortref, List *targetList)
 {
-	Index		refnumber = sortClause->tleSortGroupRef;
 	ListCell   *l;
 
 	foreach(l, targetList)
 	{
 		TargetEntry *tle = (TargetEntry *) lfirst(l);
 
-		if (tle->ressortgroupref == refnumber)
+		if (tle->ressortgroupref == sortref)
 			return tle;
 	}
 
@@ -159,6 +155,21 @@ get_sortgroupclause_tle(SortClause *sortClause,
 }
 
 /*
+ * get_sortgroupclause_tle
+ *		Find the targetlist entry matching the given SortClause
+ *		(or GroupClause) by ressortgroupref, and return it.
+ *
+ * Because GroupClause is typedef'd as SortClause, either kind of
+ * node can be passed without casting.
+ */
+TargetEntry *
+get_sortgroupclause_tle(SortClause *sortClause,
+						List *targetList)
+{
+	return get_sortgroupref_tle(sortClause->tleSortGroupRef, targetList);
+}
+
+/*
  * get_sortgroupclause_expr
  *		Find the targetlist entry matching the given SortClause
  *		(or GroupClause) by ressortgroupref, and return its expression.
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 38903520222..db6eef20964 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.147 2007/10/11 18:05:27 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.148 2007/11/08 21:49:48 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -449,7 +449,10 @@ typedef struct IndexOptInfo
  * which is a case that can't arise otherwise since clauses containing
  * volatile functions are never considered mergejoinable.  We mark such
  * EquivalenceClasses specially to prevent them from being merged with
- * ordinary EquivalenceClasses.
+ * ordinary EquivalenceClasses.  Also, for volatile expressions we have
+ * to be careful to match the EquivalenceClass to the correct targetlist
+ * entry: consider SELECT random() AS a, random() AS b ... ORDER BY b,a.
+ * So we record the SortGroupRef of the originating sort clause.
  *
  * We allow equality clauses appearing below the nullable side of an outer join
  * to form EquivalenceClasses, but these have a slightly different meaning:
@@ -472,6 +475,7 @@ typedef struct EquivalenceClass
 	bool		ec_has_volatile;	/* the (sole) member is a volatile expr */
 	bool		ec_below_outer_join;	/* equivalence applies below an OJ */
 	bool		ec_broken;			/* failed to generate needed clauses? */
+	Index		ec_sortref;			/* originating sortclause label, or 0 */
 	struct EquivalenceClass *ec_merged;		/* set if merged into another EC */
 } EquivalenceClass;
 
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index cbde0c7b9a5..cf589b48af7 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/paths.h,v 1.99 2007/09/26 18:51:51 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/paths.h,v 1.100 2007/11/08 21:49:48 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -115,7 +115,8 @@ extern void reconsider_outer_join_clauses(PlannerInfo *root);
 extern EquivalenceClass *get_eclass_for_sort_expr(PlannerInfo *root,
 						 Expr *expr,
 						 Oid expr_datatype,
-						 List *opfamilies);
+						 List *opfamilies,
+						 Index sortref);
 extern void generate_base_implied_equalities(PlannerInfo *root);
 extern List *generate_join_implied_equalities(PlannerInfo *root,
 											  RelOptInfo *joinrel,
diff --git a/src/include/optimizer/tlist.h b/src/include/optimizer/tlist.h
index bb127cbce2b..515339363ab 100644
--- a/src/include/optimizer/tlist.h
+++ b/src/include/optimizer/tlist.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/tlist.h,v 1.46 2007/11/08 19:25:37 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/tlist.h,v 1.47 2007/11/08 21:49:48 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -23,6 +23,8 @@ extern TargetEntry *tlist_member_ignore_relabel(Node *node, List *targetlist);
 extern List *flatten_tlist(List *tlist);
 extern List *add_to_flat_tlist(List *tlist, List *vars);
 
+extern TargetEntry *get_sortgroupref_tle(Index sortref,
+						List *targetList);
 extern TargetEntry *get_sortgroupclause_tle(SortClause *sortClause,
 						List *targetList);
 extern Node *get_sortgroupclause_expr(SortClause *sortClause,