Support ORDER BY ... NULLS FIRST/LAST, and add ASC/DESC/NULLS FIRST/NULLS LAST

per-column options for btree indexes.  The planner's support for this is still
pretty rudimentary; it does not yet know how to plan mergejoins with
nondefault ordering options.  The documentation is pretty rudimentary, too.
I'll work on improving that stuff later.

Note incompatible change from prior behavior: ORDER BY ... USING will now be
rejected if the operator is not a less-than or greater-than member of some
btree opclass.  This prevents less-than-sane behavior if an operator that
doesn't actually define a proper sort ordering is selected.

1 files changed, 107 insertions, 41 deletions

diff --git a/src/backend/parser/parse_clause.c b/src/backend/parser/parse_clause.c
index 663273df48b..6db3fce8377 100644
--- a/src/backend/parser/parse_clause.c
+++ b/src/backend/parser/parse_clause.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/parser/parse_clause.c,v 1.161 2007/01/05 22:19:33 momjian Exp $
+ *	  $PostgreSQL: pgsql/src/backend/parser/parse_clause.c,v 1.162 2007/01/09 02:14:14 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -33,6 +33,7 @@
 #include "parser/parse_target.h"
 #include "rewrite/rewriteManip.h"
 #include "utils/guc.h"
+#include "utils/lsyscache.h"
 
 
 #define ORDER_CLAUSE 0
@@ -1305,13 +1306,15 @@ findTargetlistEntry(ParseState *pstate, Node *node, List **tlist, int clause)
 }
 
 static GroupClause *
-make_group_clause(TargetEntry *tle, List *targetlist, Oid sortop)
+make_group_clause(TargetEntry *tle, List *targetlist,
+				  Oid sortop, bool nulls_first)
 {
 	GroupClause *result;
 
 	result = makeNode(GroupClause);
 	result->tleSortGroupRef = assignSortGroupRef(tle, targetlist);
 	result->sortop = sortop;
+	result->nulls_first = nulls_first;
 	return result;
 }
 
@@ -1380,8 +1383,9 @@ transformGroupClause(ParseState *pstate, List *grouplist,
 
 				tle_list = list_delete_cell(tle_list, tl, prev);
 
-				/* Use the sort clause's sorting operator */
-				gc = make_group_clause(tle, *targetlist, sc->sortop);
+				/* Use the sort clause's sorting information */
+				gc = make_group_clause(tle, *targetlist,
+									   sc->sortop, sc->nulls_first);
 				result = lappend(result, gc);
 				found = true;
 				break;
@@ -1408,12 +1412,18 @@ transformGroupClause(ParseState *pstate, List *grouplist,
 		GroupClause *gc;
 		Oid			sort_op;
 
-		/* avoid making duplicate grouplist entries */
-		if (targetIsInSortList(tle, result))
+		/*
+		 * Avoid making duplicate grouplist entries.  Note that we don't
+		 * enforce a particular sortop here.  Along with the copying of sort
+		 * information above, this means that if you write something like
+		 * "GROUP BY foo ORDER BY foo USING <<<", the GROUP BY operation
+		 * silently takes on the equality semantics implied by the ORDER BY.
+		 */
+		if (targetIsInSortList(tle, InvalidOid, result))
 			continue;
 
 		sort_op = ordering_oper_opid(exprType((Node *) tle->expr));
-		gc = make_group_clause(tle, *targetlist, sort_op);
+		gc = make_group_clause(tle, *targetlist, sort_op, false);
 		result = lappend(result, gc);
 	}
 
@@ -1447,7 +1457,8 @@ transformSortClause(ParseState *pstate,
 
 		sortlist = addTargetToSortList(pstate, tle,
 									   sortlist, *targetlist,
-									   sortby->sortby_kind,
+									   sortby->sortby_dir,
+									   sortby->sortby_nulls,
 									   sortby->useOp,
 									   resolveUnknown);
 	}
@@ -1553,7 +1564,9 @@ transformDistinctClause(ParseState *pstate, List *distinctlist,
 			{
 				*sortClause = addTargetToSortList(pstate, tle,
 												  *sortClause, *targetlist,
-												  SORTBY_ASC, NIL, true);
+												  SORTBY_DEFAULT,
+												  SORTBY_NULLS_DEFAULT,
+												  NIL, true);
 
 				/*
 				 * Probably, the tle should always have been added at the end
@@ -1601,8 +1614,9 @@ addAllTargetsToSortList(ParseState *pstate, List *sortlist,
 		if (!tle->resjunk)
 			sortlist = addTargetToSortList(pstate, tle,
 										   sortlist, targetlist,
-										   SORTBY_ASC, NIL,
-										   resolveUnknown);
+										   SORTBY_DEFAULT,
+										   SORTBY_NULLS_DEFAULT,
+										   NIL, resolveUnknown);
 	}
 	return sortlist;
 }
@@ -1610,8 +1624,7 @@ addAllTargetsToSortList(ParseState *pstate, List *sortlist,
 /*
  * addTargetToSortList
  *		If the given targetlist entry isn't already in the ORDER BY list,
- *		add it to the end of the list, using the sortop with given name
- *		or the default sort operator if opname == NIL.
+ *		add it to the end of the list, using the given sort ordering info.
  *
  * If resolveUnknown is TRUE, convert TLEs of type UNKNOWN to TEXT.  If not,
  * do nothing (which implies the search for a sort operator will fail).
@@ -1623,49 +1636,89 @@ addAllTargetsToSortList(ParseState *pstate, List *sortlist,
 List *
 addTargetToSortList(ParseState *pstate, TargetEntry *tle,
 					List *sortlist, List *targetlist,
-					int sortby_kind, List *sortby_opname,
-					bool resolveUnknown)
+					SortByDir sortby_dir, SortByNulls sortby_nulls,
+					List *sortby_opname, bool resolveUnknown)
 {
+	Oid			restype = exprType((Node *) tle->expr);
+	Oid			sortop;
+	Oid			cmpfunc;
+	bool		reverse;
+
+	/* if tlist item is an UNKNOWN literal, change it to TEXT */
+	if (restype == UNKNOWNOID && resolveUnknown)
+	{
+		tle->expr = (Expr *) coerce_type(pstate, (Node *) tle->expr,
+										 restype, TEXTOID, -1,
+										 COERCION_IMPLICIT,
+										 COERCE_IMPLICIT_CAST);
+		restype = TEXTOID;
+	}
+
+	/* determine the sortop */
+	switch (sortby_dir)
+	{
+		case SORTBY_DEFAULT:
+		case SORTBY_ASC:
+			sortop = ordering_oper_opid(restype);
+			reverse = false;
+			break;
+		case SORTBY_DESC:
+			sortop = reverse_ordering_oper_opid(restype);
+			reverse = true;
+			break;
+		case SORTBY_USING:
+			Assert(sortby_opname != NIL);
+			sortop = compatible_oper_opid(sortby_opname,
+										  restype,
+										  restype,
+										  false);
+			/*
+			 * Verify it's a valid ordering operator, and determine
+			 * whether to consider it like ASC or DESC.
+			 */
+			if (!get_op_compare_function(sortop, &cmpfunc, &reverse))
+				ereport(ERROR,
+						(errcode(ERRCODE_WRONG_OBJECT_TYPE),
+						 errmsg("operator %s is not a valid ordering operator",
+								strVal(llast(sortby_opname))),
+						 errhint("Ordering operators must be \"<\" or \">\" members of btree operator families.")));
+			break;
+		default:
+			elog(ERROR, "unrecognized sortby_dir: %d", sortby_dir);
+			sortop = InvalidOid; /* keep compiler quiet */
+			reverse = false;
+			break;
+	}
+
 	/* avoid making duplicate sortlist entries */
-	if (!targetIsInSortList(tle, sortlist))
+	if (!targetIsInSortList(tle, sortop, sortlist))
 	{
 		SortClause *sortcl = makeNode(SortClause);
-		Oid			restype = exprType((Node *) tle->expr);
-
-		/* if tlist item is an UNKNOWN literal, change it to TEXT */
-		if (restype == UNKNOWNOID && resolveUnknown)
-		{
-			tle->expr = (Expr *) coerce_type(pstate, (Node *) tle->expr,
-											 restype, TEXTOID, -1,
-											 COERCION_IMPLICIT,
-											 COERCE_IMPLICIT_CAST);
-			restype = TEXTOID;
-		}
 
 		sortcl->tleSortGroupRef = assignSortGroupRef(tle, targetlist);
 
-		switch (sortby_kind)
+		sortcl->sortop = sortop;
+
+		switch (sortby_nulls)
 		{
-			case SORTBY_ASC:
-				sortcl->sortop = ordering_oper_opid(restype);
+			case SORTBY_NULLS_DEFAULT:
+				/* NULLS FIRST is default for DESC; other way for ASC */
+				sortcl->nulls_first = reverse;
 				break;
-			case SORTBY_DESC:
-				sortcl->sortop = reverse_ordering_oper_opid(restype);
+			case SORTBY_NULLS_FIRST:
+				sortcl->nulls_first = true;
 				break;
-			case SORTBY_USING:
-				Assert(sortby_opname != NIL);
-				sortcl->sortop = compatible_oper_opid(sortby_opname,
-													  restype,
-													  restype,
-													  false);
+			case SORTBY_NULLS_LAST:
+				sortcl->nulls_first = false;
 				break;
 			default:
-				elog(ERROR, "unrecognized sortby_kind: %d", sortby_kind);
+				elog(ERROR, "unrecognized sortby_nulls: %d", sortby_nulls);
 				break;
 		}
 
 		sortlist = lappend(sortlist, sortcl);
 	}
+
 	return sortlist;
 }
 
@@ -1701,13 +1754,23 @@ assignSortGroupRef(TargetEntry *tle, List *tlist)
 /*
  * targetIsInSortList
  *		Is the given target item already in the sortlist?
+ *		If sortop is not InvalidOid, also test for a match to the sortop.
+ *
+ * It is not an oversight that this function ignores the nulls_first flag.
+ * We check sortop when determining if an ORDER BY item is redundant with
+ * earlier ORDER BY items, because it's conceivable that "ORDER BY
+ * foo USING <, foo USING <<<" is not redundant, if <<< distinguishes
+ * values that < considers equal.  We need not check nulls_first
+ * however, because a lower-order column with the same sortop but
+ * opposite nulls direction is redundant.  Also, we can consider
+ * ORDER BY foo ASC, foo DESC redundant, so check for a commutator match.
  *
  * Works for both SortClause and GroupClause lists.  Note that the main
  * reason we need this routine (and not just a quick test for nonzeroness
  * of ressortgroupref) is that a TLE might be in only one of the lists.
  */
 bool
-targetIsInSortList(TargetEntry *tle, List *sortList)
+targetIsInSortList(TargetEntry *tle, Oid sortop, List *sortList)
 {
 	Index		ref = tle->ressortgroupref;
 	ListCell   *l;
@@ -1720,7 +1783,10 @@ targetIsInSortList(TargetEntry *tle, List *sortList)
 	{
 		SortClause *scl = (SortClause *) lfirst(l);
 
-		if (scl->tleSortGroupRef == ref)
+		if (scl->tleSortGroupRef == ref &&
+			(sortop == InvalidOid ||
+			 sortop == scl->sortop ||
+			 sortop == get_commutator(scl->sortop)))
 			return true;
 	}
 	return false;