First phase of implementing hash-based grouping/aggregation. An AGG plan

node now does its own grouping of the input rows, and has no need for a
preceding GROUP node in the plan pipeline.  This allows elimination of
the misnamed tuplePerGroup option for GROUP, and actually saves more code
in nodeGroup.c than it costs in nodeAgg.c, as well as being presumably
faster.  Restructure the API of query_planner so that we do not commit to
using a sorted or unsorted plan in query_planner; instead grouping_planner
makes the decision.  (Right now it isn't any smarter than query_planner
was, but that will change as soon as it has the option to select a hash-
based aggregation step.)  Despite all the hackery, no initdb needed since
only in-memory node types changed.

8 files changed, 71 insertions, 33 deletions

diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index facef908947..533d296186a 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: execnodes.h,v 1.75 2002/09/04 20:31:42 momjian Exp $
+ * $Id: execnodes.h,v 1.76 2002/11/06 00:00:44 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -673,6 +673,8 @@ typedef struct AggState
 	CommonScanState csstate;	/* its first field is NodeTag */
 	List	   *aggs;			/* all Aggref nodes in targetlist & quals */
 	int			numaggs;		/* length of list (could be zero!) */
+	FmgrInfo   *eqfunctions;	/* per-grouping-field equality fns */
+	HeapTuple	grp_firstTuple;	/* copy of first tuple of current group */
 	AggStatePerAgg peragg;		/* per-Aggref working state */
 	MemoryContext tup_cxt;		/* context for per-output-tuple
 								 * expressions */
@@ -691,7 +693,7 @@ typedef struct GroupState
 	FmgrInfo   *eqfunctions;	/* per-field lookup data for equality fns */
 	bool		grp_useFirstTuple;		/* first tuple not processed yet */
 	bool		grp_done;
-	HeapTuple	grp_firstTuple;
+	HeapTuple	grp_firstTuple;	/* copy of first tuple of current group */
 } GroupState;
 
 /* ----------------
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index 5320c1b10d2..aad54a9c26c 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: nodes.h,v 1.120 2002/10/11 04:16:44 momjian Exp $
+ * $Id: nodes.h,v 1.121 2002/11/06 00:00:44 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -82,6 +82,7 @@ typedef enum NodeTag
 	T_HashPath,
 	T_TidPath,
 	T_AppendPath,
+	T_ResultPath,
 	T_PathKeyItem,
 	T_RestrictInfo,
 	T_JoinInfo,
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index ee0d2210134..8303fe9d09f 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: parsenodes.h,v 1.209 2002/10/14 22:14:35 tgl Exp $
+ * $Id: parsenodes.h,v 1.210 2002/11/06 00:00:44 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -101,7 +101,7 @@ typedef struct Query
 	List	   *join_rel_list;	/* list of join-relation RelOptInfos */
 	List	   *equi_key_list;	/* list of lists of equijoined
 								 * PathKeyItems */
-	List	   *query_pathkeys; /* pathkeys for query_planner()'s result */
+	List	   *query_pathkeys; /* desired pathkeys for query_planner() */
 } Query;
 
 
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 8d26fea6f09..63c8f20d807 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: plannodes.h,v 1.58 2002/09/04 20:31:44 momjian Exp $
+ * $Id: plannodes.h,v 1.59 2002/11/06 00:00:44 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -140,17 +140,23 @@ typedef struct Plan
  * ===============
  */
 
-/* all plan nodes "derive" from the Plan structure by having the
-   Plan structure as the first field.  This ensures that everything works
-   when nodes are cast to Plan's.  (node pointers are frequently cast to Plan*
-   when passed around generically in the executor */
+/*
+ * all plan nodes "derive" from the Plan structure by having the
+ * Plan structure as the first field.  This ensures that everything works
+ * when nodes are cast to Plan's.  (node pointers are frequently cast to Plan*
+ * when passed around generically in the executor)
+ */
 
 
 /* ----------------
  *	 Result node -
  *		If no outer plan, evaluate a variable-free targetlist.
- *		If outer plan, return tuples from outer plan that satisfy
- *		given quals (we can also do a level of projection)
+ *		If outer plan, return tuples from outer plan (after a level of
+ *		projection as shown by targetlist).
+ *
+ * If resconstantqual isn't NULL, it represents a one-time qualification
+ * test (i.e., one that doesn't depend on any variables from the outer plan,
+ * so needs to be evaluated only once).
  * ----------------
  */
 typedef struct Result
@@ -318,30 +324,45 @@ typedef struct HashJoin
 
 /* ---------------
  *		aggregate node
+ *
+ * An Agg node implements plain or grouped aggregation.  For grouped
+ * aggregation, we can work with presorted input or unsorted input;
+ * the latter strategy uses an internal hashtable.
+ *
+ * Notice the lack of any direct info about the aggregate functions to be
+ * computed.  They are found by scanning the node's tlist and quals during
+ * executor startup.  (It is possible that there are no aggregate functions;
+ * this could happen if they get optimized away by constant-folding, or if
+ * we are using the Agg node to implement hash-based grouping.)
  * ---------------
  */
+typedef enum AggStrategy
+{
+	AGG_PLAIN,					/* simple agg across all input rows */
+	AGG_SORTED,					/* grouped agg, input must be sorted */
+	AGG_HASHED					/* grouped agg, use internal hashtable */
+} AggStrategy;
+
 typedef struct Agg
 {
 	Plan		plan;
+	AggStrategy	aggstrategy;
+	int			numCols;		/* number of grouping columns */
+	AttrNumber *grpColIdx;		/* their indexes in the target list */
 	AggState   *aggstate;
 } Agg;
 
 /* ---------------
  *	 group node -
- *		use for queries with GROUP BY specified.
- *
- *		If tuplePerGroup is true, one tuple (with group columns only) is
- *		returned for each group and NULL is returned when there are no more
- *		groups. Otherwise, all the tuples of a group are returned with a
- *		NULL returned at the end of each group. (see nodeGroup.c for details)
+ *		Used for queries with GROUP BY (but no aggregates) specified.
+ *		The input must be presorted according to the grouping columns.
  * ---------------
  */
 typedef struct Group
 {
 	Plan		plan;
-	bool		tuplePerGroup;	/* what tuples to return (see above) */
-	int			numCols;		/* number of group columns */
-	AttrNumber *grpColIdx;		/* indexes into the target list */
+	int			numCols;		/* number of grouping columns */
+	AttrNumber *grpColIdx;		/* their indexes in the target list */
 	GroupState *grpstate;
 } Group;
 
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 071addbc1bb..480fd9630be 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -1,13 +1,13 @@
 /*-------------------------------------------------------------------------
  *
  * relation.h
- *	  Definitions for internal planner nodes.
+ *	  Definitions for planner's internal data structures.
  *
  *
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: relation.h,v 1.67 2002/09/04 20:31:44 momjian Exp $
+ * $Id: relation.h,v 1.68 2002/11/06 00:00:44 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -403,6 +403,19 @@ typedef struct AppendPath
 } AppendPath;
 
 /*
+ * ResultPath represents use of a Result plan node, either to compute a
+ * variable-free targetlist or to gate execution of a subplan with a
+ * one-time (variable-free) qual condition.  Note that in the former case
+ * path.parent will be NULL; in the latter case it is copied from the subpath.
+ */
+typedef struct ResultPath
+{
+	Path		path;
+	Path	   *subpath;
+	List	   *constantqual;
+} ResultPath;
+
+/*
  * All join-type paths share these fields.
  */
 
diff --git a/src/include/optimizer/geqo_misc.h b/src/include/optimizer/geqo_misc.h
index 6599bf7697f..5c276c0fb21 100644
--- a/src/include/optimizer/geqo_misc.h
+++ b/src/include/optimizer/geqo_misc.h
@@ -6,7 +6,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: geqo_misc.h,v 1.21 2002/09/04 20:31:45 momjian Exp $
+ * $Id: geqo_misc.h,v 1.22 2002/11/06 00:00:45 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -32,9 +32,6 @@ extern void print_pool(FILE *fp, Pool *pool, int start, int stop);
 extern void print_gen(FILE *fp, Pool *pool, int generation);
 extern void print_edge_table(FILE *fp, Edge *edge_table, int num_gene);
 
-extern void geqo_print_rel(Query *root, RelOptInfo *rel);
-extern void geqo_print_path(Query *root, Path *path, int indent);
-extern void geqo_print_joinclauses(Query *root, List *clauses);
 #endif   /* GEQO_DEBUG */
 
 #endif   /* GEQO_MISC_H */
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 0c9ce6c95e3..61c433e12dd 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: pathnode.h,v 1.44 2002/06/20 20:29:51 momjian Exp $
+ * $Id: pathnode.h,v 1.45 2002/11/06 00:00:45 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -35,6 +35,8 @@ extern IndexPath *create_index_path(Query *root, RelOptInfo *rel,
 extern TidPath *create_tidscan_path(Query *root, RelOptInfo *rel,
 					List *tideval);
 extern AppendPath *create_append_path(RelOptInfo *rel, List *subpaths);
+extern ResultPath *create_result_path(RelOptInfo *rel, Path *subpath,
+									  List *constantqual);
 extern Path *create_subqueryscan_path(RelOptInfo *rel);
 extern Path *create_functionscan_path(Query *root, RelOptInfo *rel);
 
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index d31cee5ddc7..c927d540740 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: planmain.h,v 1.60 2002/09/04 20:31:45 momjian Exp $
+ * $Id: planmain.h,v 1.61 2002/11/06 00:00:45 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -20,7 +20,8 @@
 /*
  * prototypes for plan/planmain.c
  */
-extern Plan *query_planner(Query *root, List *tlist, double tuple_fraction);
+extern void query_planner(Query *root, List *tlist, double tuple_fraction,
+						  Path **cheapest_path, Path **sorted_path);
 
 /*
  * prototypes for plan/createplan.c
@@ -33,9 +34,10 @@ extern Sort *make_sort(Query *root, List *tlist,
 		  Plan *lefttree, int keycount);
 extern Sort *make_sort_from_pathkeys(Query *root, List *tlist,
 						Plan *lefttree, List *pathkeys);
-extern Agg *make_agg(List *tlist, List *qual, Plan *lefttree);
-extern Group *make_group(List *tlist, bool tuplePerGroup, int ngrp,
-		   AttrNumber *grpColIdx, Plan *lefttree);
+extern Agg *make_agg(List *tlist, List *qual, AggStrategy aggstrategy,
+					 int ngrp, AttrNumber *grpColIdx, Plan *lefttree);
+extern Group *make_group(List *tlist, int ngrp, AttrNumber *grpColIdx,
+						 Plan *lefttree);
 extern Material *make_material(List *tlist, Plan *lefttree);
 extern Unique *make_unique(List *tlist, Plan *lefttree, List *distinctList);
 extern Limit *make_limit(List *tlist, Plan *lefttree,