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.

9 files changed, 87 insertions, 49 deletions

diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 3b9cf8a8c9a..132f0526676 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -6,7 +6,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- * $Id: execnodes.h,v 1.33 1999/07/16 17:07:33 momjian Exp $
+ * $Id: execnodes.h,v 1.34 1999/08/21 03:49:08 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -572,6 +572,7 @@ typedef struct MaterialState
 typedef struct AggState
 {
 	CommonScanState csstate;	/* its first field is NodeTag */
+	List	   *aggs;			/* all Aggref nodes in targetlist & quals */
 	bool		agg_done;
 } AggState;
 
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index ab22b737e48..5a1d07ec391 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -6,7 +6,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- * $Id: parsenodes.h,v 1.77 1999/07/18 03:45:01 tgl Exp $
+ * $Id: parsenodes.h,v 1.78 1999/08/21 03:49:09 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -48,28 +48,29 @@ typedef struct Query
 	bool		hasAggs;		/* has aggregates in target list */
 	bool		hasSubLinks;	/* has subquery SubLink */
 
-	char	   *uniqueFlag;		/* NULL, '*', or Unique attribute name */
-	List	   *sortClause;		/* a list of SortClause's */
-
 	List	   *rtable;			/* list of range table entries */
 	List	   *targetList;		/* target list (of TargetEntry) */
-	Node	   *qual;			/* qualifications */
+	Node	   *qual;			/* qualifications applied to tuples */
 	List	   *rowMark;		/* list of RowMark entries */
 
-	List	   *groupClause;	/* list of columns to specified in GROUP
-								 * BY */
-	Node	   *havingQual;		/* qualification of each group */
+	char	   *uniqueFlag;		/* NULL, '*', or Unique attribute name */
+	List	   *sortClause;		/* a list of SortClause's */
 
-	List	   *intersectClause;
+	List	   *groupClause;	/* a list of GroupClause's */
+
+	Node	   *havingQual;		/* qualifications applied to groups */
 
+	List	   *intersectClause;
 	List	   *unionClause;	/* unions are linked under the previous
 								 * query */
+
 	Node	   *limitOffset;	/* # of result tuples to skip */
 	Node	   *limitCount;		/* # of result tuples to return */
 
 	/* internal to planner */
-	List	   *base_rel_list;	/* base relation list */
-	List	   *join_rel_list;	/* list of relation involved in joins */
+	List	   *base_rel_list;	/* list of base-relation RelOptInfos */
+	List	   *join_rel_list;	/* list of join-relation RelOptInfos */
+	List	   *query_pathkeys;	/* pathkeys for query_planner()'s result */
 } Query;
 
 
@@ -608,7 +609,7 @@ typedef struct InsertStmt
 	List	   *targetList;		/* the target list (of ResTarget) */
 	List	   *fromClause;		/* the from clause */
 	Node	   *whereClause;	/* qualifications */
-	List	   *groupClause;	/* group by clause */
+	List	   *groupClause;	/* GROUP BY clauses */
 	Node	   *havingClause;	/* having conditional-expression */
 	List	   *unionClause;	/* union subselect parameters */
 	bool		unionall;		/* union without unique sort */
@@ -652,7 +653,7 @@ typedef struct SelectStmt
 	List	   *targetList;		/* the target list (of ResTarget) */
 	List	   *fromClause;		/* the from clause */
 	Node	   *whereClause;	/* qualifications */
-	List	   *groupClause;	/* group by clause */
+	List	   *groupClause;	/* GROUP BY clauses */
 	Node	   *havingClause;	/* having conditional-expression */
 	List	   *intersectClause;
 	List	   *exceptClause;
@@ -950,25 +951,28 @@ typedef struct RangeTblEntry
 
 /*
  * SortClause -
- *	   used in the sort clause for retrieves and cursors
+ *	   representation of ORDER BY clauses
+ *
+ * tleSortGroupRef must match ressortgroupref of exactly one Resdom of the
+ * associated targetlist; that is the expression to be sorted (or grouped) by.
+ * sortop is the OID of the ordering operator.
  */
 typedef struct SortClause
 {
 	NodeTag		type;
-	Resdom	   *resdom;			/* attributes in tlist to be sorted */
-	Oid			opoid;			/* sort operators */
+	Index		tleSortGroupRef; /* reference into targetlist */
+	Oid			sortop;			/* the sort operator to use */
 } SortClause;
 
 /*
  * GroupClause -
- *	   used in the GROUP BY clause
+ *	   representation of GROUP BY clauses
+ *
+ * GroupClause is exactly like SortClause except for the nodetag value
+ * (and it's probably not even really necessary to have two different
+ * nodetags...).  We have routines that operate interchangeably on both.
  */
-typedef struct GroupClause
-{
-	NodeTag		type;
-	Oid			grpOpoid;		/* the sort operator to use */
-	Index		tleGroupref;	/* reference into targetlist */
-} GroupClause;
+typedef SortClause GroupClause;
 
 #define ROW_MARK_FOR_UPDATE		(1 << 0)
 #define ROW_ACL_FOR_UPDATE		(1 << 1)
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 532be5196bf..095ee074d38 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -6,7 +6,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- * $Id: plannodes.h,v 1.29 1999/08/09 06:20:27 momjian Exp $
+ * $Id: plannodes.h,v 1.30 1999/08/21 03:49:09 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -232,7 +232,6 @@ typedef struct HashJoin
 typedef struct Agg
 {
 	Plan		plan;
-	List	   *aggs;
 	AggState   *aggstate;
 } Agg;
 
diff --git a/src/include/nodes/primnodes.h b/src/include/nodes/primnodes.h
index 2c4d0ffaa72..4eea81446b2 100644
--- a/src/include/nodes/primnodes.h
+++ b/src/include/nodes/primnodes.h
@@ -6,7 +6,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- * $Id: primnodes.h,v 1.33 1999/08/16 02:17:39 tgl Exp $
+ * $Id: primnodes.h,v 1.34 1999/08/21 03:49:09 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -25,15 +25,33 @@
 /* ----------------
  * Resdom (Result Domain)
  *		resno			- attribute number
- *		restype			- type of the resdom
- *		restypmod		- type-specific modifier of the result
+ *		restype			- type of the value
+ *		restypmod		- type-specific modifier of the value
  *		resname			- name of the resdom (could be NULL)
+ *		ressortgroupref	- nonzero if referenced by a sort/group clause
  *		reskey			- order of key in a sort (for those > 0)
- *		reskeyop		- sort operator Oid
- *		resgroupref		- set to nonzero if referenced from a group by clause
+ *		reskeyop		- sort operator's regproc Oid
  *		resjunk			- set to true to eliminate the attribute
  *						  from final target list
  *
+ * Notes:
+ * ressortgroupref is the parse/plan-time representation of ORDER BY and
+ * GROUP BY items.  Targetlist entries with ressortgroupref=0 are not
+ * sort/group items.  If ressortgroupref>0, then this item is an ORDER BY or
+ * GROUP BY value.  No two entries in a targetlist may have the same nonzero
+ * ressortgroupref --- but there is no particular meaning to the nonzero
+ * values, except as tags.  (For example, one must not assume that lower
+ * ressortgroupref means a more significant sort key.)  The order of the
+ * associated SortClause or GroupClause lists determine the semantics.
+ *
+ * reskey and reskeyop are the execution-time representation of sorting.
+ * reskey must be zero in any non-sort-key item.  The reskey of sort key
+ * targetlist items for a sort plan node is 1,2,...,n for the n sort keys.
+ * The reskeyop of each such targetlist item is the sort operator's
+ * regproc OID.  reskeyop will be zero in non-sort-key items.
+ *
+ * Both reskey and reskeyop are typically zero during parse/plan stages.
+ * The executor does not pay any attention to ressortgroupref.
  * ----------------
  */
 typedef struct Resdom
@@ -43,9 +61,9 @@ typedef struct Resdom
 	Oid			restype;
 	int32		restypmod;
 	char	   *resname;
+	Index		ressortgroupref;
 	Index		reskey;
 	Oid			reskeyop;
-	Index		resgroupref;
 	bool		resjunk;
 } Resdom;
 
@@ -275,7 +293,8 @@ typedef struct Iter
  *		basetype		- base type Oid of the aggregate
  *		aggtype			- type Oid of final result of the aggregate
  *		target			- attribute or expression we are aggregating on
- *		aggno			- index to ecxt_values
+ *		usenulls		- TRUE to accept null values as inputs
+ *		aggno			- workspace for nodeAgg.c executor
  * ----------------
  */
 typedef struct Aggref
@@ -285,8 +304,8 @@ typedef struct Aggref
 	Oid			basetype;
 	Oid			aggtype;
 	Node	   *target;
-	int			aggno;
 	bool		usenulls;
+	int			aggno;
 } Aggref;
 
 /* ----------------
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index b0ec64c3e32..58da94368c9 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -7,7 +7,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- * $Id: paths.h,v 1.34 1999/08/16 02:17:45 tgl Exp $
+ * $Id: paths.h,v 1.35 1999/08/21 03:49:15 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -56,11 +56,15 @@ typedef enum
 
 extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);
 extern bool pathkeys_contained_in(List *keys1, List *keys2);
-extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys);
+extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
+											bool indexpaths_only);
 extern List *build_index_pathkeys(Query *root, RelOptInfo *rel,
 								  RelOptInfo *index);
 extern List *build_join_pathkeys(List *outer_pathkeys,
 								 List *join_rel_tlist, List *joinclauses);
+extern bool commute_pathkeys(List *pathkeys);
+extern List *make_pathkeys_for_sortclauses(List *sortclauses,
+										   List *tlist);
 extern List *find_mergeclauses_for_pathkeys(List *pathkeys,
 											List *restrictinfos);
 extern List *make_pathkeys_for_mergeclauses(List *mergeclauses,
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 0ba017471d1..38ff367384b 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.30 1999/08/09 00:56:04 tgl Exp $
+ * $Id: planmain.h,v 1.31 1999/08/21 03:49:15 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -33,7 +33,7 @@ extern Sort *make_sort(List *tlist, Oid nonameid, Plan *lefttree,
 		  int keycount);
 extern Agg *make_agg(List *tlist, Plan *lefttree);
 extern Group *make_group(List *tlist, bool tuplePerGroup, int ngrp,
-		   AttrNumber *grpColIdx, Sort *lefttree);
+		   AttrNumber *grpColIdx, Plan *lefttree);
 extern Unique *make_unique(List *tlist, Plan *lefttree, char *uniqueAttr);
 
 /*
@@ -54,9 +54,14 @@ extern void replace_tlist_with_subplan_refs(List *tlist,
 								Index subvarno,
 								List *subplanTargetList);
 extern bool set_agg_tlist_references(Agg *aggNode);
+extern List *pull_agg_clause(Node *clause);
 extern void check_having_for_ungrouped_vars(Node *clause,
 								List *groupClause,
 								List *targetList);
+
+/*
+ * prep/prepkeyset.c
+ */
 extern void transformKeySetQuery(Query *origNode);
 
 #endif	 /* PLANMAIN_H */
diff --git a/src/include/optimizer/tlist.h b/src/include/optimizer/tlist.h
index fb08b708352..f0ddb9ac9dc 100644
--- a/src/include/optimizer/tlist.h
+++ b/src/include/optimizer/tlist.h
@@ -6,7 +6,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- * $Id: tlist.h,v 1.20 1999/08/16 02:17:45 tgl Exp $
+ * $Id: tlist.h,v 1.21 1999/08/21 03:49:15 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -21,16 +21,17 @@ extern void add_var_to_tlist(RelOptInfo *rel, Var *var);
 extern TargetEntry *create_tl_element(Var *var, int resdomno);
 extern List *get_actual_tlist(List *tlist);
 extern Resdom *tlist_member(Var *var, List *tlist);
-extern Resdom *tlist_resdom(List *tlist, Resdom *resnode);
 
 extern TargetEntry *match_varid(Var *test_var, List *tlist);
 extern List *new_unsorted_tlist(List *targetlist);
 extern List *copy_vars(List *target, List *source);
 extern List *flatten_tlist(List *tlist);
-extern List *flatten_tlist_vars(List *full_tlist,
-				   List *flat_tlist);
+extern List *add_to_flat_tlist(List *tlist, List *vars);
+extern List *unflatten_tlist(List *full_tlist,
+							 List *flat_tlist);
 
 extern Var *get_expr(TargetEntry *tle);
-extern Var *get_groupclause_expr(GroupClause *groupClause, List *targetList);
+extern Node *get_sortgroupclause_expr(SortClause *sortClause,
+									  List *targetList);
 
 #endif	 /* TLIST_H */
diff --git a/src/include/parser/parse_clause.h b/src/include/parser/parse_clause.h
index 3b1aafa07d9..6b30301ea0b 100644
--- a/src/include/parser/parse_clause.h
+++ b/src/include/parser/parse_clause.h
@@ -6,7 +6,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- * $Id: parse_clause.h,v 1.12 1999/07/19 00:26:16 tgl Exp $
+ * $Id: parse_clause.h,v 1.13 1999/08/21 03:49:17 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -20,8 +20,11 @@ extern void setTargetTable(ParseState *pstate, char *relname);
 extern Node *transformWhereClause(ParseState *pstate, Node *where,
 								  Node *using);
 extern List *transformGroupClause(ParseState *pstate, List *grouplist,
-					 List *targetlist);
-extern List *transformSortClause(ParseState *pstate,
-					List *orderlist, List *sortClause,
-					List *targetlist, char *uniqueFlag);
+								  List *targetlist);
+extern List *transformSortClause(ParseState *pstate, List *orderlist,
+								 List *targetlist, char *uniqueFlag);
+
+extern List *addAllTargetsToSortList(List *sortlist, List *targetlist);
+extern Index assignSortGroupRef(TargetEntry *tle, List *tlist);
+
 #endif	 /* PARSE_CLAUSE_H */
diff --git a/src/include/parser/parse_func.h b/src/include/parser/parse_func.h
index 38626290cb1..1fdb8f9890d 100644
--- a/src/include/parser/parse_func.h
+++ b/src/include/parser/parse_func.h
@@ -6,7 +6,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- * $Id: parse_func.h,v 1.18 1999/07/15 23:04:02 momjian Exp $
+ * $Id: parse_func.h,v 1.19 1999/08/21 03:49:17 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -45,6 +45,8 @@ extern Node *ParseNestedFuncOrColumn(ParseState *pstate, Attr *attr,
 extern Node *ParseFuncOrColumn(ParseState *pstate, char *funcname, List *fargs,
 				  int *curr_resno, int precedence);
 
+extern List *setup_base_tlist(Oid typeid);
+
 extern void func_error(char *caller, char *funcname,
 					   int nargs, Oid *argtypes, char *msg);