Major revision of sort-node handling: push knowledge of query

sort order down into planner, instead of handling it only at the very top
level of the planner.  This fixes many things.  An explicit sort is now
avoided if there is a cheaper alternative (typically an indexscan) not
only for ORDER BY, but also for the internal sort of GROUP BY.  It works
even when there is no other reason (such as a WHERE condition) to consider
the indexscan.  It works for indexes on functions.  It works for indexes
on functions, backwards.  It's just so cool...

CAUTION: I have changed the representation of SortClause nodes, therefore
THIS UPDATE BREAKS STORED RULES.  You will need to initdb.

1 files changed, 91 insertions, 11 deletions

diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index 76e010c9d22..f6f62abfe08 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.40 1999/07/16 04:59:19 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.41 1999/08/21 03:49:03 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -17,11 +17,13 @@
 
 
 #include "optimizer/clauses.h"
+#include "optimizer/cost.h"
 #include "optimizer/paths.h"
 #include "optimizer/planmain.h"
 #include "optimizer/prep.h"
 #include "optimizer/subselect.h"
 #include "optimizer/tlist.h"
+#include "utils/lsyscache.h"
 
 
 static Plan *subplanner(Query *root, List *flat_tlist, List *qual);
@@ -42,6 +44,13 @@ static Result *make_result(List *tlist, Node *resconstantqual, Plan *subplan);
  *	  tlist is the target list of the query
  *	  qual is the qualification of the query
  *
+ *	  Note: the Query node now also includes a query_pathkeys field, which
+ *	  signals query_planner that the indicated sort order is wanted in the
+ *	  final output plan.  If, for some reason, query_planner is unable to
+ *	  comply, it sets query_pathkeys to NIL before returning.  (The reason
+ *	  query_pathkeys is a Query field and not a passed parameter is that
+ *	  the low-level routines in indxpath.c need to see it.)
+ *
  *	  Returns a query plan.
  */
 Plan *
@@ -100,6 +109,8 @@ query_planner(Query *root,
 	 */
 	if (var_only_tlist == NULL && qual == NULL)
 	{
+		root->query_pathkeys = NIL; /* these plans make unordered results */
+
 		switch (command_type)
 		{
 			case CMD_SELECT:
@@ -152,6 +163,8 @@ query_planner(Query *root,
 		 */
 		set_tlist_references(subplan);
 
+		root->query_pathkeys = NIL; /* result is unordered, no? */
+
 		return subplan;
 	}
 
@@ -163,15 +176,15 @@ query_planner(Query *root,
 	 * responsibility to optimally push these expressions down the plan
 	 * tree.  -- Wei
 	 *
-	 * Note: formerly there was a test here to skip the flatten call if we
-	 * expected union_planner to insert a Group or Agg node above our
+	 * Note: formerly there was a test here to skip the unflatten call if
+	 * we expected union_planner to insert a Group or Agg node above our
 	 * result. However, now union_planner tells us exactly what it wants
 	 * returned, and we just do it.  Much cleaner.
 	 */
 	else
 	{
-		subplan->targetlist = flatten_tlist_vars(tlist,
-												 subplan->targetlist);
+		subplan->targetlist = unflatten_tlist(tlist,
+											  subplan->targetlist);
 		return subplan;
 	}
 
@@ -204,6 +217,8 @@ subplanner(Query *root,
 		   List *qual)
 {
 	RelOptInfo *final_rel;
+	Cost		cheapest_cost;
+	Path	   *sortedpath;
 
 	/*
 	 * Initialize the targetlist and qualification, adding entries to
@@ -244,18 +259,83 @@ subplanner(Query *root,
 	}
 #endif
 
+	if (! final_rel)
+	{
+		elog(NOTICE, "final relation is null");
+		root->query_pathkeys = NIL; /* result is unordered, no? */
+		return create_plan((Path *) NULL);
+	}
+
+	/*
+	 * Determine the cheapest path and create a subplan to execute it.
+	 *
+	 * If no special sort order is wanted, or if the cheapest path is
+	 * already appropriately ordered, just use the cheapest path.
+	 */
+	if (root->query_pathkeys == NIL ||
+		pathkeys_contained_in(root->query_pathkeys,
+							  final_rel->cheapestpath->pathkeys))
+		return create_plan(final_rel->cheapestpath);
 	/*
-	 * Determine the cheapest path and create a subplan corresponding to
-	 * it.
+	 * Otherwise, look to see if we have an already-ordered path that is
+	 * cheaper than doing an explicit sort on cheapestpath.
 	 */
-	if (final_rel)
-		return create_plan((Path *) final_rel->cheapestpath);
+	cheapest_cost = final_rel->cheapestpath->path_cost +
+		cost_sort(root->query_pathkeys, final_rel->size, final_rel->width);
+
+	sortedpath = get_cheapest_path_for_pathkeys(final_rel->pathlist,
+												root->query_pathkeys,
+												false);
+	if (sortedpath)
+	{
+		if (sortedpath->path_cost <= cheapest_cost)
+		{
+			/* Found a better presorted path, use it */
+			return create_plan(sortedpath);
+		}
+		/* otherwise, doing it the hard way is still cheaper */
+	}
 	else
 	{
-		elog(NOTICE, "final relation is null");
-		return create_plan((Path *) NULL);
+		/*
+		 * If we found no usable presorted path at all, it is possible
+		 * that the user asked for descending sort order.  Check to see
+		 * if we can satisfy the pathkeys by using a backwards indexscan.
+		 * To do this, we commute all the operators in the pathkeys and
+		 * then look for a matching path that is an IndexPath.
+		 */
+		List	   *commuted_pathkeys = copyObject(root->query_pathkeys);
+
+		if (commute_pathkeys(commuted_pathkeys))
+		{
+			/* pass 'true' to force only IndexPaths to be considered */
+			sortedpath = get_cheapest_path_for_pathkeys(final_rel->pathlist,
+														commuted_pathkeys,
+														true);
+			if (sortedpath && sortedpath->path_cost <= cheapest_cost)
+			{
+				/*
+				 * Kluge here: since IndexPath has no representation for
+				 * backwards scan, we have to convert to Plan format and
+				 * then poke the result.
+				 */
+				Plan	   *sortedplan = create_plan(sortedpath);
+
+				Assert(IsA(sortedplan, IndexScan));
+				((IndexScan *) sortedplan)->indxorderdir = BackwardScanDirection;
+				return sortedplan;
+			}
+		}
 	}
 
+	/* Nothing for it but to sort the cheapestpath...
+	 *
+	 * we indicate we failed to sort the plan, and let the caller
+	 * stick the appropriate sortplan on top.
+	 */
+	root->query_pathkeys = NIL; /* sorry, it ain't sorted */
+
+	return create_plan(final_rel->cheapestpath);
 }
 
 /*****************************************************************************