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.

3 files changed, 49 insertions, 20 deletions

diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index e1fe6c0ddb..d11f9ae6ea 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.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/parsenodes.h,v 1.337 2007/01/05 22:19:55 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/parsenodes.h,v 1.338 2007/01/09 02:14:15 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -36,6 +36,22 @@ typedef enum OnCommitAction
 	ONCOMMIT_DROP				/* ON COMMIT DROP */
 } OnCommitAction;
 
+/* Sort ordering options for ORDER BY and CREATE INDEX */
+typedef enum SortByDir
+{
+	SORTBY_DEFAULT,
+	SORTBY_ASC,
+	SORTBY_DESC,
+	SORTBY_USING				/* not allowed in CREATE INDEX ... */
+} SortByDir;
+
+typedef enum SortByNulls
+{
+	SORTBY_NULLS_DEFAULT,
+	SORTBY_NULLS_FIRST,
+	SORTBY_NULLS_LAST
+} SortByNulls;
+
 
 /*
  * Grantable rights are encoded so that we can OR them together in a bitmask.
@@ -348,14 +364,11 @@ typedef struct ResTarget
 /*
  * SortBy - for ORDER BY clause
  */
-#define SORTBY_ASC		1
-#define SORTBY_DESC		2
-#define SORTBY_USING	3
-
 typedef struct SortBy
 {
 	NodeTag		type;
-	int			sortby_kind;	/* see codes above */
+	SortByDir	sortby_dir;		/* ASC/DESC/USING */
+	SortByNulls	sortby_nulls;	/* NULLS FIRST/LAST */
 	List	   *useOp;			/* name of op to use, if SORTBY_USING */
 	Node	   *node;			/* expression to sort on */
 } SortBy;
@@ -443,6 +456,8 @@ typedef struct IndexElem
 	char	   *name;			/* name of attribute to index, or NULL */
 	Node	   *expr;			/* expression to index, or NULL */
 	List	   *opclass;		/* name of desired opclass; NIL = default */
+	SortByDir	ordering;		/* ASC/DESC/default */
+	SortByNulls	nulls_ordering;	/* FIRST/LAST/default */
 } IndexElem;
 
 /*
@@ -614,7 +629,8 @@ typedef struct RangeTblEntry
  *
  * tleSortGroupRef must match ressortgroupref of exactly one entry of the
  * associated targetlist; that is the expression to be sorted (or grouped) by.
- * sortop is the OID of the ordering operator.
+ * sortop is the OID of the ordering operator (a "<" or ">" operator).
+ * nulls_first does about what you'd expect.
  *
  * SortClauses are also used to identify targets that we will do a "Unique"
  * filter step on (for SELECT DISTINCT and SELECT DISTINCT ON).  The
@@ -627,16 +643,21 @@ typedef struct SortClause
 {
 	NodeTag		type;
 	Index		tleSortGroupRef;	/* reference into targetlist */
-	Oid			sortop;			/* the sort operator to use */
+	Oid			sortop;				/* the ordering operator ('<' op) */
+	bool		nulls_first;		/* do NULLs come before normal values? */
 } SortClause;
 
 /*
  * GroupClause -
  *	   representation of GROUP BY clauses
  *
- * GroupClause is exactly like SortClause except for the nodetag value
- * (it's probably not even really necessary to have two different
- * nodetags...).  We have routines that operate interchangeably on both.
+ * GroupClause is exactly like SortClause except for the nodetag value.
+ * We have routines that operate interchangeably on both.
+ *
+ * XXX SortClause overspecifies the semantics so far as GROUP BY is concerned
+ * (ditto for DISTINCT).  It'd be better to specify an equality operator not
+ * an ordering operator.  However, the two implementations are tightly entwined
+ * at the moment ... breaking them apart is work for another day.
  */
 typedef SortClause GroupClause;
 
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index acb73a39ed..44002a9d45 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.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/plannodes.h,v 1.87 2007/01/05 22:19:55 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/plannodes.h,v 1.88 2007/01/09 02:14:15 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -385,6 +385,7 @@ typedef struct Sort
 	int			numCols;		/* number of sort-key columns */
 	AttrNumber *sortColIdx;		/* their indexes in the target list */
 	Oid		   *sortOperators;	/* OIDs of operators to sort them by */
+	bool	   *nullsFirst;		/* NULLS FIRST/LAST directions */
 } Sort;
 
 /* ---------------
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 75fb572de0..4e285a765a 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.130 2007/01/05 22:19:56 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.131 2007/01/09 02:14:15 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -300,19 +300,23 @@ typedef struct RelOptInfo
  *		and indexes, but that created confusion without actually doing anything
  *		useful.  So now we have a separate IndexOptInfo struct for indexes.
  *
- *		opfamily[], indexkeys[], and ordering[] have ncolumns entries.
+ *		opfamily[], indexkeys[], fwdsortop[], revsortop[], and nulls_first[]
+ *		each have ncolumns entries.  Note: for historical reasons, the
+ *		opfamily array has an extra entry that is always zero.  Some code
+ *		scans until it sees a zero entry, rather than looking at ncolumns.
+ *
  *		Zeroes in the indexkeys[] array indicate index columns that are
  *		expressions; there is one element in indexprs for each such column.
  *
- *		Note: for historical reasons, the opfamily and ordering arrays have
- *		an extra entry that is always zero.  Some code scans until it sees a
- *		zero entry, rather than looking at ncolumns.
+ *		For an unordered index, the sortop arrays contains zeroes.  Note that
+ *		fwdsortop[] and nulls_first[] describe the sort ordering of a forward
+ *		indexscan; we can also consider a backward indexscan, which will
+ *		generate sort order described by revsortop/!nulls_first.
  *
  *		The indexprs and indpred expressions have been run through
  *		prepqual.c and eval_const_expressions() for ease of matching to
- *		WHERE clauses.	indpred is in implicit-AND form.
+ *		WHERE clauses. indpred is in implicit-AND form.
  */
-
 typedef struct IndexOptInfo
 {
 	NodeTag		type;
@@ -328,7 +332,9 @@ typedef struct IndexOptInfo
 	int			ncolumns;		/* number of columns in index */
 	Oid		   *opfamily;		/* OIDs of operator families for columns */
 	int		   *indexkeys;		/* column numbers of index's keys, or 0 */
-	Oid		   *ordering;		/* OIDs of sort operators for each column */
+	Oid		   *fwdsortop;		/* OIDs of sort operators for each column */
+	Oid		   *revsortop;		/* OIDs of sort operators for backward scan */
+	bool	   *nulls_first;	/* do NULLs come first in the sort order? */
 	Oid			relam;			/* OID of the access method (in pg_am) */
 
 	RegProcedure amcostestimate;	/* OID of the access method's cost fcn */
@@ -360,6 +366,7 @@ typedef struct PathKeyItem
 
 	Node	   *key;			/* the item that is ordered */
 	Oid			sortop;			/* the ordering operator ('<' op) */
+	bool		nulls_first;	/* do NULLs come before normal values? */
 
 	/*
 	 * key typically points to a Var node, ie a relation attribute, but it can