Further sort-order twiddling in optimizer: be smart about

case where ORDER BY and GROUP BY request the same sort order.

4 files changed, 97 insertions, 57 deletions

diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index ae1e2d3266b..b9742d6fef5 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -9,7 +9,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.75 1999/08/22 20:14:47 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.76 1999/08/22 23:56:44 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -51,7 +51,6 @@ static List *fix_indxqual_sublist(List *indexqual, IndexPath *index_path,
 								  Form_pg_index index);
 static Node *fix_indxqual_operand(Node *node, IndexPath *index_path,
 								  Form_pg_index index);
-static Noname *make_noname(List *tlist, List *pathkeys, Plan *plan_node);
 static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
 			   List *indxid, List *indxqual, List *indxqualorig);
 static NestLoop *make_nestloop(List *qptlist, List *qpqual, Plan *lefttree,
@@ -926,12 +925,12 @@ copy_costsize(Plan *dest, Plan *src)
  *	  'tlist' is the target list of the scan to be sorted or materialized
  *	  'pathkeys' is the list of pathkeys by which the result is to be sorted
  *			(NIL implies no sort needed, just materialize it)
- *	  'plan_node' is the node which yields input tuples
+ *	  'subplan' is the node which yields input tuples
  */
-static Noname *
+Noname *
 make_noname(List *tlist,
 			List *pathkeys,
-			Plan *plan_node)
+			Plan *subplan)
 {
 	List	   *noname_tlist;
 	int			numsortkeys;
@@ -946,7 +945,7 @@ make_noname(List *tlist,
 		/* need to sort */
 		retval = (Plan *) make_sort(noname_tlist,
 									_NONAME_RELATION_ID_,
-									plan_node,
+									subplan,
 									numsortkeys);
 	}
 	else
@@ -954,7 +953,7 @@ make_noname(List *tlist,
 		/* no sort */
 		retval = (Plan *) make_material(noname_tlist,
 										_NONAME_RELATION_ID_,
-										plan_node,
+										subplan,
 										0);
 	}
 
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index 802e5970416..995d2865b03 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.42 1999/08/22 20:14:48 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.43 1999/08/22 23:56:45 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -44,11 +44,14 @@ static Plan *subplanner(Query *root, List *flat_tlist, List *qual);
  *	  qual is the qualification of the query
  *
  *	  Note: the Query node now also includes a query_pathkeys field, which
+ *	  is both an input and an output of query_planner().  The input value
  *	  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.)
+ *	  final output plan.  The output value is the actual pathkeys of the
+ *	  selected path.  This might not be the same as what the caller requested;
+ *	  the caller must do pathkeys_contained_in() to decide whether an
+ *	  explicit sort is still needed.  (The main 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.
  */
@@ -255,7 +258,11 @@ subplanner(Query *root,
 	if (root->query_pathkeys == NIL ||
 		pathkeys_contained_in(root->query_pathkeys,
 							  final_rel->cheapestpath->pathkeys))
+	{
+		root->query_pathkeys = final_rel->cheapestpath->pathkeys;
 		return create_plan(final_rel->cheapestpath);
+	}
+
 	/*
 	 * Otherwise, look to see if we have an already-ordered path that is
 	 * cheaper than doing an explicit sort on cheapestpath.
@@ -271,6 +278,7 @@ subplanner(Query *root,
 		if (sortedpath->path_cost <= cheapest_cost)
 		{
 			/* Found a better presorted path, use it */
+			root->query_pathkeys = sortedpath->pathkeys;
 			return create_plan(sortedpath);
 		}
 		/* otherwise, doing it the hard way is still cheaper */
@@ -300,21 +308,31 @@ subplanner(Query *root,
 				 * then poke the result.
 				 */
 				Plan	   *sortedplan = create_plan(sortedpath);
+				List	   *sortedpathkeys;
 
 				Assert(IsA(sortedplan, IndexScan));
 				((IndexScan *) sortedplan)->indxorderdir = BackwardScanDirection;
+				/*
+				 * Need to generate commuted keys representing the actual
+				 * sort order.  This should succeed, probably, but just in
+				 * case it does not, use the original root->query_pathkeys
+				 * as a conservative approximation.
+				 */
+				sortedpathkeys = copyObject(sortedpath->pathkeys);
+				if (commute_pathkeys(sortedpathkeys))
+					root->query_pathkeys = sortedpathkeys;
+
 				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 sort node on top.  union_planner has to be
-	 * able to add a sort node anyway, so no need for extra code here.
+	/* Nothing for it but to sort the cheapestpath --- but we let the
+	 * caller do that.  union_planner has to be able to add a sort node
+	 * anyway, so no need for extra code here.  (Furthermore, the given
+	 * pathkeys might involve something we can't compute yet, such as
+	 * an aggregate function...)
 	 */
-	root->query_pathkeys = NIL; /* sorry, it ain't sorted */
-
+	root->query_pathkeys = final_rel->cheapestpath->pathkeys;
 	return create_plan(final_rel->cheapestpath);
 }
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 0003262a454..3c7a665563c 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.64 1999/08/22 20:14:48 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.65 1999/08/22 23:56:45 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -39,7 +39,7 @@ static List *make_subplanTargetList(Query *parse, List *tlist,
 									AttrNumber **groupColIdx);
 static Plan *make_groupplan(List *group_tlist, bool tuplePerGroup,
 							List *groupClause, AttrNumber *grpColIdx,
-							bool is_sorted, Plan *subplan);
+							bool is_presorted, Plan *subplan);
 static Plan *make_sortplan(List *tlist, List *sortcls, Plan *plannode);
 
 /*****************************************************************************
@@ -91,7 +91,7 @@ union_planner(Query *parse)
 	List	   *rangetable = parse->rtable;
 	Plan	   *result_plan = (Plan *) NULL;
 	AttrNumber *groupColIdx = NULL;
-	bool		is_sorted = false;
+	List	   *current_pathkeys = NIL;
 	Index		rt_index;
 
 	if (parse->unionClause)
@@ -102,6 +102,11 @@ union_planner(Query *parse)
 									  parse->commandType,
 									  parse->resultRelation,
 									  parse->rtable);
+		/*
+		 * We leave current_pathkeys NIL indicating we do not know sort order.
+		 * Actually, for a normal UNION we have done an explicit sort; ought
+		 * to change interface to plan_union_queries to pass that info back!
+		 */
 	}
 	else if ((rt_index = first_inherit_rt_entry(rangetable)) != -1)
 	{
@@ -135,6 +140,10 @@ union_planner(Query *parse)
 
 		if (parse->rowMark != NULL)
 			elog(ERROR, "SELECT FOR UPDATE is not supported for inherit queries");
+		/*
+		 * We leave current_pathkeys NIL indicating we do not know sort order
+		 * of the Append-ed results.
+		 */
 	}
 	else
 	{
@@ -183,24 +192,24 @@ union_planner(Query *parse)
 		}
 
 		/*
+		 * Generate appropriate target list for subplan; may be different
+		 * from tlist if grouping or aggregation is needed.
+		 */
+		sub_tlist = make_subplanTargetList(parse, tlist, &groupColIdx);
+
+		/*
 		 * Figure out whether we need a sorted result from query_planner.
 		 *
 		 * If we have a GROUP BY clause, then we want a result sorted
-		 * properly for grouping.  Otherwise, if there is an ORDER BY clause
-		 * and no need for an aggregate node, we want to sort by the ORDER BY
-		 * clause.  (XXX In some cases, we could presort even when there is
-		 * an aggregate, but I'll leave that refinement for another day.)
-		 *
-		 * NOTE: the reason we put the target pathkeys into the Query node
-		 * rather than passing them as an argument to query_planner is that
-		 * the low-level routines in indxpath.c want to be able to see them.
+		 * properly for grouping.  Otherwise, if there is an ORDER BY clause,
+		 * we want to sort by the ORDER BY clause.
 		 */
 		if (parse->groupClause)
 		{
 			parse->query_pathkeys =
 				make_pathkeys_for_sortclauses(parse->groupClause, tlist);
 		}
-		else if (parse->sortClause && ! parse->hasAggs)
+		else if (parse->sortClause)
 		{
 			parse->query_pathkeys =
 				make_pathkeys_for_sortclauses(parse->sortClause, tlist);
@@ -210,23 +219,16 @@ union_planner(Query *parse)
 			parse->query_pathkeys = NIL;
 		}
 
-		/*
-		 * Generate appropriate target list for subplan; may be different
-		 * from tlist if grouping or aggregation is needed.
-		 */
-		sub_tlist = make_subplanTargetList(parse, tlist, &groupColIdx);
-
 		/* Generate the (sub) plan */
 		result_plan = query_planner(parse,
 									parse->commandType,
 									sub_tlist,
 									(List *) parse->qual);
 
-		/* query_planner sets query_pathkeys to NIL if it didn't make
-		 * a properly sorted plan
+		/* query_planner returns actual sort order (which is not
+		 * necessarily what we requested) in query_pathkeys.
 		 */
-		if (parse->query_pathkeys)
-			is_sorted = true;
+		current_pathkeys = parse->query_pathkeys;
 	}
 
 	/* query_planner returns NULL if it thinks plan is bogus */
@@ -241,6 +243,8 @@ union_planner(Query *parse)
 	{
 		bool		tuplePerGroup;
 		List	   *group_tlist;
+		List	   *group_pathkeys;
+		bool		is_sorted;
 
 		/*
 		 * Decide whether how many tuples per group the Group node needs
@@ -261,18 +265,33 @@ union_planner(Query *parse)
 		else
 			group_tlist = tlist;
 
+		/*
+		 * Figure out whether the path result is already ordered the way we
+		 * need it --- if so, no need for an explicit sort step.
+		 */
+		group_pathkeys = make_pathkeys_for_sortclauses(parse->groupClause,
+													   tlist);
+		if (pathkeys_contained_in(group_pathkeys, current_pathkeys))
+		{
+			is_sorted = true;	/* no sort needed now */
+			/* current_pathkeys remains unchanged */
+		}
+		else
+		{
+			/* We will need to do an explicit sort by the GROUP BY clause.
+			 * make_groupplan will do the work, but set current_pathkeys
+			 * to indicate the resulting order.
+			 */
+			is_sorted = false;
+			current_pathkeys = group_pathkeys;
+		}
+
 		result_plan = make_groupplan(group_tlist,
 									 tuplePerGroup,
 									 parse->groupClause,
 									 groupColIdx,
 									 is_sorted,
 									 result_plan);
-
-		/*
-		 * Assume the result of the group step is not ordered suitably
-		 * for any ORDER BY that may exist.  XXX it might be; improve this!
-		 */
-		is_sorted = false;
 	}
 
 	/*
@@ -325,20 +344,23 @@ union_planner(Query *parse)
 		/* HAVING clause, if any, becomes qual of the Agg node */
 		result_plan->qual = (List *) parse->havingQual;
 
-		/*
-		 * Assume result is not ordered suitably for ORDER BY.
-		 * XXX it might be; improve this!
-		 */
-		is_sorted = false;
+		/* Note: Agg does not affect any existing sort order of the tuples */
 	}
 
 	/*
 	 * If we were not able to make the plan come out in the right order,
 	 * add an explicit sort step.
 	 */
-	if (parse->sortClause && ! is_sorted)
+	if (parse->sortClause)
 	{
-		result_plan = make_sortplan(tlist, parse->sortClause, result_plan);
+		List	   *sort_pathkeys;
+
+		sort_pathkeys = make_pathkeys_for_sortclauses(parse->sortClause,
+													  tlist);
+		if (! pathkeys_contained_in(sort_pathkeys, current_pathkeys))
+		{
+			result_plan = make_sortplan(tlist, parse->sortClause, result_plan);
+		}
 	}
 
 	/*
@@ -474,12 +496,12 @@ make_groupplan(List *group_tlist,
 			   bool tuplePerGroup,
 			   List *groupClause,
 			   AttrNumber *grpColIdx,
-			   bool is_sorted,
+			   bool is_presorted,
 			   Plan *subplan)
 {
 	int			numCols = length(groupClause);
 
-	if (! is_sorted)
+	if (! is_presorted)
 	{
 		/*
 		 * The Sort node always just takes a copy of the subplan's tlist
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 3abda02d932..09c39ceea77 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -6,7 +6,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- * $Id: planmain.h,v 1.32 1999/08/22 20:14:56 tgl Exp $
+ * $Id: planmain.h,v 1.33 1999/08/22 23:56:43 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -33,6 +33,7 @@ extern Sort *make_sort(List *tlist, Oid nonameid, Plan *lefttree,
 extern Agg *make_agg(List *tlist, Plan *lefttree);
 extern Group *make_group(List *tlist, bool tuplePerGroup, int ngrp,
 		   AttrNumber *grpColIdx, Plan *lefttree);
+extern Noname *make_noname(List *tlist, List *pathkeys, Plan *subplan);
 extern Unique *make_unique(List *tlist, Plan *lefttree, char *uniqueAttr);
 extern Result *make_result(List *tlist, Node *resconstantqual, Plan *subplan);