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, 42 insertions, 17 deletions

diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 7328f41a399..8f1d8e81cc4 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.219 2007/01/05 22:19:31 momjian Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.220 2007/01/09 02:14:12 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -117,7 +117,7 @@ static MergeJoin *make_mergejoin(List *tlist,
 			   Plan *lefttree, Plan *righttree,
 			   JoinType jointype);
 static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
-		  AttrNumber *sortColIdx, Oid *sortOperators);
+		  AttrNumber *sortColIdx, Oid *sortOperators, bool *nullsFirst);
 static Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree,
 						List *pathkeys);
 
@@ -734,7 +734,9 @@ create_unique_plan(PlannerInfo *root, UniquePath *best_path)
 			Assert(tle != NULL);
 			sortList = addTargetToSortList(NULL, tle,
 										   sortList, subplan->targetlist,
-										   SORTBY_ASC, NIL, false);
+										   SORTBY_DEFAULT,
+										   SORTBY_NULLS_DEFAULT,
+										   NIL, false);
 		}
 		plan = (Plan *) make_sort_from_sortclauses(root, sortList, subplan);
 		plan = (Plan *) make_unique(plan, sortList);
@@ -2359,11 +2361,12 @@ make_mergejoin(List *tlist,
 /*
  * make_sort --- basic routine to build a Sort plan node
  *
- * Caller must have built the sortColIdx and sortOperators arrays already.
+ * Caller must have built the sortColIdx, sortOperators, and nullsFirst
+ * arrays already.
  */
 static Sort *
 make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
-		  AttrNumber *sortColIdx, Oid *sortOperators)
+		  AttrNumber *sortColIdx, Oid *sortOperators, bool *nullsFirst)
 {
 	Sort	   *node = makeNode(Sort);
 	Plan	   *plan = &node->plan;
@@ -2383,6 +2386,7 @@ make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
 	node->numCols = numCols;
 	node->sortColIdx = sortColIdx;
 	node->sortOperators = sortOperators;
+	node->nullsFirst = nullsFirst;
 
 	return node;
 }
@@ -2397,14 +2401,23 @@ make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
  * max possible number of columns.	Return value is the new column count.
  */
 static int
-add_sort_column(AttrNumber colIdx, Oid sortOp,
-				int numCols, AttrNumber *sortColIdx, Oid *sortOperators)
+add_sort_column(AttrNumber colIdx, Oid sortOp, bool nulls_first,
+				int numCols, AttrNumber *sortColIdx,
+				Oid *sortOperators, bool *nullsFirst)
 {
 	int			i;
 
 	for (i = 0; i < numCols; i++)
 	{
-		if (sortColIdx[i] == colIdx)
+		/*
+		 * Note: we check sortOp 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.
+		 */
+		if (sortColIdx[i] == colIdx &&
+			sortOperators[numCols] == sortOp)
 		{
 			/* Already sorting by this col, so extra sort key is useless */
 			return numCols;
@@ -2414,6 +2427,7 @@ add_sort_column(AttrNumber colIdx, Oid sortOp,
 	/* Add the column */
 	sortColIdx[numCols] = colIdx;
 	sortOperators[numCols] = sortOp;
+	nullsFirst[numCols] = nulls_first;
 	return numCols + 1;
 }
 
@@ -2441,6 +2455,7 @@ make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys)
 	int			numsortkeys;
 	AttrNumber *sortColIdx;
 	Oid		   *sortOperators;
+	bool	   *nullsFirst;
 
 	/*
 	 * We will need at most list_length(pathkeys) sort columns; possibly less
@@ -2448,6 +2463,7 @@ make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys)
 	numsortkeys = list_length(pathkeys);
 	sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
 	sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
+	nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
 
 	numsortkeys = 0;
 
@@ -2527,13 +2543,15 @@ make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys)
 		 * So enter it only once in the sort arrays.
 		 */
 		numsortkeys = add_sort_column(tle->resno, pathkey->sortop,
-									  numsortkeys, sortColIdx, sortOperators);
+									  pathkey->nulls_first,
+									  numsortkeys,
+									  sortColIdx, sortOperators, nullsFirst);
 	}
 
 	Assert(numsortkeys > 0);
 
 	return make_sort(root, lefttree, numsortkeys,
-					 sortColIdx, sortOperators);
+					 sortColIdx, sortOperators, nullsFirst);
 }
 
 /*
@@ -2551,6 +2569,7 @@ make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree)
 	int			numsortkeys;
 	AttrNumber *sortColIdx;
 	Oid		   *sortOperators;
+	bool	   *nullsFirst;
 
 	/*
 	 * We will need at most list_length(sortcls) sort columns; possibly less
@@ -2558,6 +2577,7 @@ make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree)
 	numsortkeys = list_length(sortcls);
 	sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
 	sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
+	nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
 
 	numsortkeys = 0;
 
@@ -2572,13 +2592,15 @@ make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree)
 		 * redundantly.
 		 */
 		numsortkeys = add_sort_column(tle->resno, sortcl->sortop,
-									  numsortkeys, sortColIdx, sortOperators);
+									  sortcl->nulls_first,
+									  numsortkeys,
+									  sortColIdx, sortOperators, nullsFirst);
 	}
 
 	Assert(numsortkeys > 0);
 
 	return make_sort(root, lefttree, numsortkeys,
-					 sortColIdx, sortOperators);
+					 sortColIdx, sortOperators, nullsFirst);
 }
 
 /*
@@ -2591,8 +2613,8 @@ make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree)
  * This might look like it could be merged with make_sort_from_sortclauses,
  * but presently we *must* use the grpColIdx[] array to locate sort columns,
  * because the child plan's tlist is not marked with ressortgroupref info
- * appropriate to the grouping node.  So, only the sortop is used from the
- * GroupClause entries.
+ * appropriate to the grouping node.  So, only the sort direction info
+ * is used from the GroupClause entries.
  */
 Sort *
 make_sort_from_groupcols(PlannerInfo *root,
@@ -2606,6 +2628,7 @@ make_sort_from_groupcols(PlannerInfo *root,
 	int			numsortkeys;
 	AttrNumber *sortColIdx;
 	Oid		   *sortOperators;
+	bool	   *nullsFirst;
 
 	/*
 	 * We will need at most list_length(groupcls) sort columns; possibly less
@@ -2613,6 +2636,7 @@ make_sort_from_groupcols(PlannerInfo *root,
 	numsortkeys = list_length(groupcls);
 	sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
 	sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
+	nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
 
 	numsortkeys = 0;
 
@@ -2627,14 +2651,16 @@ make_sort_from_groupcols(PlannerInfo *root,
 		 * redundantly.
 		 */
 		numsortkeys = add_sort_column(tle->resno, grpcl->sortop,
-									  numsortkeys, sortColIdx, sortOperators);
+									  grpcl->nulls_first,
+									  numsortkeys,
+									  sortColIdx, sortOperators, nullsFirst);
 		grpno++;
 	}
 
 	Assert(numsortkeys > 0);
 
 	return make_sort(root, lefttree, numsortkeys,
-					 sortColIdx, sortOperators);
+					 sortColIdx, sortOperators, nullsFirst);
 }
 
 Material *
@@ -2871,7 +2897,6 @@ make_unique(Plan *lefttree, List *distinctList)
  * distinctList is a list of SortClauses, identifying the targetlist items
  * that should be considered by the SetOp filter.
  */
-
 SetOp *
 make_setop(SetOpCmd cmd, Plan *lefttree,
 		   List *distinctList, AttrNumber flagColIdx)