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.

13 files changed, 133 insertions, 89 deletions

diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index 991fc14588c..435826cf457 100644
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.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/access/nbtree.h,v 1.107 2007/01/05 22:19:51 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/access/nbtree.h,v 1.108 2007/01/09 02:14:15 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -327,7 +327,11 @@ typedef struct xl_btree_newroot
 /*
  *	Operator strategy numbers for B-tree have been moved to access/skey.h,
  *	because many places need to use them in ScanKeyInit() calls.
+ *
+ *	The strategy numbers are chosen so that we can commute them by
+ *	subtraction, thus:
  */
+#define BTCommuteStrategyNumber(strat)  (BTMaxStrategyNumber + 1 - (strat))
 
 /*
  *	When a new operator class is declared, we require that the user
@@ -458,11 +462,15 @@ typedef struct BTScanOpaqueData
 typedef BTScanOpaqueData *BTScanOpaque;
 
 /*
- * We use these private sk_flags bits in preprocessed scan keys
+ * We use some private sk_flags bits in preprocessed scan keys.  We're allowed
+ * to use bits 16-31 (see skey.h).  The uppermost bits are copied from the
+ * index's indoption[] array entry for the index attribute.
  */
 #define SK_BT_REQFWD	0x00010000		/* required to continue forward scan */
 #define SK_BT_REQBKWD	0x00020000		/* required to continue backward scan */
-
+#define SK_BT_INDOPTION_SHIFT  24		/* must clear the above bits */
+#define SK_BT_DESC			(INDOPTION_DESC << SK_BT_INDOPTION_SHIFT)
+#define SK_BT_NULLS_FIRST	(INDOPTION_NULLS_FIRST << SK_BT_INDOPTION_SHIFT)
 
 /*
  * prototypes for functions in nbtree.c (external entry points for btree)
diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h
index fd67dfd27af..98a625cfbf1 100644
--- a/src/include/catalog/catversion.h
+++ b/src/include/catalog/catversion.h
@@ -37,7 +37,7 @@
  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/catalog/catversion.h,v 1.370 2007/01/05 22:19:52 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/catalog/catversion.h,v 1.371 2007/01/09 02:14:15 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -53,6 +53,6 @@
  */
 
 /*							yyyymmddN */
-#define CATALOG_VERSION_NO	200701021
+#define CATALOG_VERSION_NO	200701081
 
 #endif
diff --git a/src/include/catalog/index.h b/src/include/catalog/index.h
index 8848ba12d65..32c704b71e6 100644
--- a/src/include/catalog/index.h
+++ b/src/include/catalog/index.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/catalog/index.h,v 1.72 2007/01/05 22:19:52 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/catalog/index.h,v 1.73 2007/01/09 02:14:15 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -35,6 +35,7 @@ extern Oid index_create(Oid heapRelationId,
 			 Oid accessMethodObjectId,
 			 Oid tableSpaceId,
 			 Oid *classObjectId,
+			 int16 *coloptions,
 			 Datum reloptions,
 			 bool isprimary,
 			 bool isconstraint,
diff --git a/src/include/catalog/pg_am.h b/src/include/catalog/pg_am.h
index a0dbc20f407..80aad731302 100644
--- a/src/include/catalog/pg_am.h
+++ b/src/include/catalog/pg_am.h
@@ -8,7 +8,7 @@
  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/catalog/pg_am.h,v 1.48 2007/01/05 22:19:52 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/catalog/pg_am.h,v 1.49 2007/01/09 02:14:15 tgl Exp $
  *
  * NOTES
  *		the genbki.sh script reads this file and generates .bki
@@ -39,15 +39,18 @@
 CATALOG(pg_am,2601)
 {
 	NameData	amname;			/* access method name */
-	int2		amstrategies;	/* total NUMBER of strategies (operators) by
+	int2		amstrategies;	/* total number of strategies (operators) by
 								 * which we can traverse/search this AM.
 								 * Zero if AM does not have a fixed set of
 								 * strategy assignments. */
-	int2		amsupport;		/* total NUMBER of support functions that this
+	int2		amsupport;		/* total number of support functions that this
 								 * AM uses */
 	int2		amorderstrategy;/* if this AM has a sort order, the strategy
-								 * number of the sort operator. Zero if AM is
-								 * not ordered. */
+								 * number of the default (ASC) sort operator.
+								 * Zero if AM is not ordered. */
+	int2		amdescorder;	/* if this AM has a sort order, the strategy
+								 * number of the DESC sort operator.
+								 * Zero if AM is not ordered. */
 	bool		amcanunique;	/* does AM support UNIQUE indexes? */
 	bool		amcanmulticol;	/* does AM support multi-column indexes? */
 	bool		amoptionalkey;	/* can query omit key for the first column? */
@@ -80,46 +83,47 @@ typedef FormData_pg_am *Form_pg_am;
  *		compiler constants for pg_am
  * ----------------
  */
-#define Natts_pg_am						23
+#define Natts_pg_am						24
 #define Anum_pg_am_amname				1
 #define Anum_pg_am_amstrategies			2
 #define Anum_pg_am_amsupport			3
 #define Anum_pg_am_amorderstrategy		4
-#define Anum_pg_am_amcanunique			5
-#define Anum_pg_am_amcanmulticol		6
-#define Anum_pg_am_amoptionalkey		7
-#define Anum_pg_am_amindexnulls			8
-#define Anum_pg_am_amstorage			9
-#define Anum_pg_am_amclusterable		10
-#define Anum_pg_am_aminsert				11
-#define Anum_pg_am_ambeginscan			12
-#define Anum_pg_am_amgettuple			13
-#define Anum_pg_am_amgetmulti			14
-#define Anum_pg_am_amrescan				15
-#define Anum_pg_am_amendscan			16
-#define Anum_pg_am_ammarkpos			17
-#define Anum_pg_am_amrestrpos			18
-#define Anum_pg_am_ambuild				19
-#define Anum_pg_am_ambulkdelete			20
-#define Anum_pg_am_amvacuumcleanup		21
-#define Anum_pg_am_amcostestimate		22
-#define Anum_pg_am_amoptions			23
+#define Anum_pg_am_amdescorder			5
+#define Anum_pg_am_amcanunique			6
+#define Anum_pg_am_amcanmulticol		7
+#define Anum_pg_am_amoptionalkey		8
+#define Anum_pg_am_amindexnulls			9
+#define Anum_pg_am_amstorage			10
+#define Anum_pg_am_amclusterable		11
+#define Anum_pg_am_aminsert				12
+#define Anum_pg_am_ambeginscan			13
+#define Anum_pg_am_amgettuple			14
+#define Anum_pg_am_amgetmulti			15
+#define Anum_pg_am_amrescan				16
+#define Anum_pg_am_amendscan			17
+#define Anum_pg_am_ammarkpos			18
+#define Anum_pg_am_amrestrpos			19
+#define Anum_pg_am_ambuild				20
+#define Anum_pg_am_ambulkdelete			21
+#define Anum_pg_am_amvacuumcleanup		22
+#define Anum_pg_am_amcostestimate		23
+#define Anum_pg_am_amoptions			24
 
 /* ----------------
  *		initial contents of pg_am
  * ----------------
  */
 
-DATA(insert OID = 403 (  btree	5 1 1 t t t t f t btinsert btbeginscan btgettuple btgetmulti btrescan btendscan btmarkpos btrestrpos btbuild btbulkdelete btvacuumcleanup btcostestimate btoptions ));
+DATA(insert OID = 403 (  btree	5 1 1 5 t t t t f t btinsert btbeginscan btgettuple btgetmulti btrescan btendscan btmarkpos btrestrpos btbuild btbulkdelete btvacuumcleanup btcostestimate btoptions ));
 DESCR("b-tree index access method");
 #define BTREE_AM_OID 403
-DATA(insert OID = 405 (  hash	1 1 0 f f f f f f hashinsert hashbeginscan hashgettuple hashgetmulti hashrescan hashendscan hashmarkpos hashrestrpos hashbuild hashbulkdelete hashvacuumcleanup hashcostestimate hashoptions ));
+DATA(insert OID = 405 (  hash	1 1 0 0 f f f f f f hashinsert hashbeginscan hashgettuple hashgetmulti hashrescan hashendscan hashmarkpos hashrestrpos hashbuild hashbulkdelete hashvacuumcleanup hashcostestimate hashoptions ));
 DESCR("hash index access method");
 #define HASH_AM_OID 405
-DATA(insert OID = 783 (  gist	0 7 0 f t t t t t gistinsert gistbeginscan gistgettuple gistgetmulti gistrescan gistendscan gistmarkpos gistrestrpos gistbuild gistbulkdelete gistvacuumcleanup gistcostestimate gistoptions ));
+DATA(insert OID = 783 (  gist	0 7 0 0 f t t t t t gistinsert gistbeginscan gistgettuple gistgetmulti gistrescan gistendscan gistmarkpos gistrestrpos gistbuild gistbulkdelete gistvacuumcleanup gistcostestimate gistoptions ));
 DESCR("GiST index access method");
 #define GIST_AM_OID 783
-DATA(insert OID = 2742 (  gin	0 4 0 f f f f t f gininsert ginbeginscan gingettuple gingetmulti ginrescan ginendscan ginmarkpos ginrestrpos ginbuild ginbulkdelete ginvacuumcleanup gincostestimate ginoptions ));
+DATA(insert OID = 2742 (  gin	0 4 0 0 f f f f t f gininsert ginbeginscan gingettuple gingetmulti ginrescan ginendscan ginmarkpos ginrestrpos ginbuild ginbulkdelete ginvacuumcleanup gincostestimate ginoptions ));
 DESCR("GIN index access method");
 #define GIN_AM_OID 2742
 
diff --git a/src/include/catalog/pg_attribute.h b/src/include/catalog/pg_attribute.h
index 413ec569b51..463e10a5da1 100644
--- a/src/include/catalog/pg_attribute.h
+++ b/src/include/catalog/pg_attribute.h
@@ -8,7 +8,7 @@
  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/catalog/pg_attribute.h,v 1.128 2007/01/05 22:19:52 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/catalog/pg_attribute.h,v 1.129 2007/01/09 02:14:15 tgl Exp $
  *
  * NOTES
  *	  the genbki.sh script reads this file and generates .bki
@@ -465,7 +465,8 @@ DATA(insert ( 1259 tableoid			26 0  4  -7 0 -1 -1 t p i t f f t 0));
 { 0, {"indisvalid"},		16, -1, 1, 7, 0, -1, -1, true, 'p', 'c', true, false, false, true, 0 }, \
 { 0, {"indkey"},			22, -1, -1, 8, 1, -1, -1, false, 'p', 'i', true, false, false, true, 0 }, \
 { 0, {"indclass"},			30, -1, -1, 9, 1, -1, -1, false, 'p', 'i', true, false, false, true, 0 }, \
-{ 0, {"indexprs"},			25, -1, -1, 10, 0, -1, -1, false, 'x', 'i', false, false, false, true, 0 }, \
-{ 0, {"indpred"},			25, -1, -1, 11, 0, -1, -1, false, 'x', 'i', false, false, false, true, 0 }
+{ 0, {"indoption"},			22, -1, -1, 10, 1, -1, -1, false, 'p', 'i', true, false, false, true, 0 }, \
+{ 0, {"indexprs"},			25, -1, -1, 11, 0, -1, -1, false, 'x', 'i', false, false, false, true, 0 }, \
+{ 0, {"indpred"},			25, -1, -1, 12, 0, -1, -1, false, 'x', 'i', false, false, false, true, 0 }
 
 #endif   /* PG_ATTRIBUTE_H */
diff --git a/src/include/catalog/pg_index.h b/src/include/catalog/pg_index.h
index d88b9c58e71..31c6e25fb0d 100644
--- a/src/include/catalog/pg_index.h
+++ b/src/include/catalog/pg_index.h
@@ -8,7 +8,7 @@
  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/catalog/pg_index.h,v 1.42 2007/01/05 22:19:52 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/catalog/pg_index.h,v 1.43 2007/01/09 02:14:15 tgl Exp $
  *
  * NOTES
  *	  the genbki.sh script reads this file and generates .bki
@@ -46,6 +46,7 @@ CATALOG(pg_index,2610) BKI_WITHOUT_OIDS
 	/* VARIABLE LENGTH FIELDS: */
 	int2vector	indkey;			/* column numbers of indexed cols, or 0 */
 	oidvector	indclass;		/* opclass identifiers */
+	int2vector	indoption;		/* per-column flags (AM-specific meanings) */
 	text		indexprs;		/* expression trees for index attributes that
 								 * are not simple column references; one for
 								 * each zero entry in indkey[] */
@@ -64,7 +65,7 @@ typedef FormData_pg_index *Form_pg_index;
  *		compiler constants for pg_index
  * ----------------
  */
-#define Natts_pg_index					11
+#define Natts_pg_index					12
 #define Anum_pg_index_indexrelid		1
 #define Anum_pg_index_indrelid			2
 #define Anum_pg_index_indnatts			3
@@ -74,7 +75,16 @@ typedef FormData_pg_index *Form_pg_index;
 #define Anum_pg_index_indisvalid		7
 #define Anum_pg_index_indkey			8
 #define Anum_pg_index_indclass			9
-#define Anum_pg_index_indexprs			10
-#define Anum_pg_index_indpred			11
+#define Anum_pg_index_indoption			10
+#define Anum_pg_index_indexprs			11
+#define Anum_pg_index_indpred			12
+
+/*
+ * Index AMs that support ordered scans must support these two indoption
+ * bits.  Otherwise, the content of the per-column indoption fields is
+ * open for future definition.
+ */
+#define INDOPTION_DESC			0x0001	/* values are in reverse order */
+#define INDOPTION_NULLS_FIRST	0x0002	/* NULLs are first instead of last */
 
 #endif   /* PG_INDEX_H */
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index e1fe6c0ddba..d11f9ae6ead 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 acb73a39ed6..44002a9d45d 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 75fb572de0f..4e285a765ad 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
diff --git a/src/include/parser/parse_clause.h b/src/include/parser/parse_clause.h
index f59f031db3c..06309613682 100644
--- a/src/include/parser/parse_clause.h
+++ b/src/include/parser/parse_clause.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/parser/parse_clause.h,v 1.47 2007/01/05 22:19:57 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/parser/parse_clause.h,v 1.48 2007/01/09 02:14:15 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -38,9 +38,9 @@ extern List *addAllTargetsToSortList(ParseState *pstate,
 						bool resolveUnknown);
 extern 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);
 extern Index assignSortGroupRef(TargetEntry *tle, List *tlist);
-extern bool targetIsInSortList(TargetEntry *tle, List *sortList);
+extern bool targetIsInSortList(TargetEntry *tle, Oid sortop, List *sortList);
 
 #endif   /* PARSE_CLAUSE_H */
diff --git a/src/include/utils/lsyscache.h b/src/include/utils/lsyscache.h
index 41e0c5162fb..15d2b8a06d9 100644
--- a/src/include/utils/lsyscache.h
+++ b/src/include/utils/lsyscache.h
@@ -6,7 +6,7 @@
  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/utils/lsyscache.h,v 1.110 2007/01/05 22:19:59 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/utils/lsyscache.h,v 1.111 2007/01/09 02:14:16 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -37,6 +37,7 @@ extern Oid	get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype,
 								int16 strategy);
 extern bool get_op_mergejoin_info(Oid eq_op, Oid *left_sortop,
 					  Oid *right_sortop, Oid *opfamily);
+extern bool get_op_compare_function(Oid opno, Oid *cmpfunc, bool *reverse);
 extern Oid	get_op_hash_function(Oid opno);
 extern void get_op_btree_interpretation(Oid opno,
 							List **opfamilies, List **opstrats);
diff --git a/src/include/utils/rel.h b/src/include/utils/rel.h
index ae81b7483e1..c8b78b95422 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.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/utils/rel.h,v 1.94 2007/01/05 22:19:59 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/utils/rel.h,v 1.95 2007/01/09 02:14:16 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -189,6 +189,7 @@ typedef struct RelationData
 	Oid		   *rd_operator;	/* OIDs of index operators */
 	RegProcedure *rd_support;	/* OIDs of support procedures */
 	FmgrInfo   *rd_supportinfo; /* lookup info for support procedures */
+	int16	   *rd_indoption;	/* per-column AM-specific flags */
 	List	   *rd_indexprs;	/* index expression trees, if any */
 	List	   *rd_indpred;		/* index predicate tree, if any */
 	void	   *rd_amcache;		/* available for use by index AM */
diff --git a/src/include/utils/tuplesort.h b/src/include/utils/tuplesort.h
index 2ee315d8557..cea50b4836b 100644
--- a/src/include/utils/tuplesort.h
+++ b/src/include/utils/tuplesort.h
@@ -13,7 +13,7 @@
  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/utils/tuplesort.h,v 1.24 2007/01/05 22:20:00 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/utils/tuplesort.h,v 1.25 2007/01/09 02:14:16 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -45,14 +45,14 @@ typedef struct Tuplesortstate Tuplesortstate;
  */
 
 extern Tuplesortstate *tuplesort_begin_heap(TupleDesc tupDesc,
-					 int nkeys,
-					 Oid *sortOperators, AttrNumber *attNums,
+					 int nkeys, AttrNumber *attNums,
+					 Oid *sortOperators, bool *nullsFirstFlags,
 					 int workMem, bool randomAccess);
 extern Tuplesortstate *tuplesort_begin_index(Relation indexRel,
 					  bool enforceUnique,
 					  int workMem, bool randomAccess);
 extern Tuplesortstate *tuplesort_begin_datum(Oid datumType,
-					  Oid sortOperator,
+					  Oid sortOperator, bool nullsFirstFlag,
 					  int workMem, bool randomAccess);
 
 extern void tuplesort_puttupleslot(Tuplesortstate *state,
@@ -84,28 +84,17 @@ extern void tuplesort_rescan(Tuplesortstate *state);
 extern void tuplesort_markpos(Tuplesortstate *state);
 extern void tuplesort_restorepos(Tuplesortstate *state);
 
-/*
- * This routine selects an appropriate sorting function to implement
- * a sort operator as efficiently as possible.
- */
-typedef enum
-{
-	SORTFUNC_LT,				/* raw "<" operator */
-	SORTFUNC_REVLT,				/* raw "<" operator, but reverse NULLs */
-	SORTFUNC_CMP,				/* -1 / 0 / 1 three-way comparator */
-	SORTFUNC_REVCMP				/* 1 / 0 / -1 (reversed) 3-way comparator */
-} SortFunctionKind;
-
-extern void SelectSortFunction(Oid sortOperator,
-				   RegProcedure *sortFunction,
-				   SortFunctionKind *kind);
+/* Setup for ApplySortFunction */
+extern void SelectSortFunction(Oid sortOperator, bool nulls_first,
+				   Oid *sortFunction,
+				   int *sortFlags);
 
 /*
  * Apply a sort function (by now converted to fmgr lookup form)
  * and return a 3-way comparison result.  This takes care of handling
- * NULLs and sort ordering direction properly.
+ * reverse-sort and NULLs-ordering properly.
  */
-extern int32 ApplySortFunction(FmgrInfo *sortFunction, SortFunctionKind kind,
+extern int32 ApplySortFunction(FmgrInfo *sortFunction, int sortFlags,
 				  Datum datum1, bool isNull1,
 				  Datum datum2, bool isNull2);