Implement SQL-standard WITH clauses, including WITH RECURSIVE.

There are some unimplemented aspects: recursive queries must use UNION ALL
(should allow UNION too), and we don't have SEARCH or CYCLE clauses.
These might or might not get done for 8.4, but even without them it's a
pretty useful feature.

There are also a couple of small loose ends and definitional quibbles,
which I'll send a memo about to pgsql-hackers shortly.  But let's land
the patch now so we can get on with other development.

Yoshiyuki Asaba, with lots of help from Tatsuo Ishii and Tom Lane

21 files changed, 331 insertions, 37 deletions

diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h
index e333b6d6d68..260d4621cd5 100644
--- a/src/include/catalog/catversion.h
+++ b/src/include/catalog/catversion.h
@@ -37,7 +37,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/catalog/catversion.h,v 1.491 2008/10/03 07:33:09 heikki Exp $
+ * $PostgreSQL: pgsql/src/include/catalog/catversion.h,v 1.492 2008/10/04 21:56:54 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -53,6 +53,6 @@
  */
 
 /*							yyyymmddN */
-#define CATALOG_VERSION_NO	200810031
+#define CATALOG_VERSION_NO	200810041
 
 #endif
diff --git a/src/include/executor/nodeCtescan.h b/src/include/executor/nodeCtescan.h
new file mode 100644
index 00000000000..e4530691648
--- /dev/null
+++ b/src/include/executor/nodeCtescan.h
@@ -0,0 +1,25 @@
+/*-------------------------------------------------------------------------
+ *
+ * nodeCtescan.h
+ *
+ *
+ *
+ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * $PostgreSQL: pgsql/src/include/executor/nodeCtescan.h,v 1.1 2008/10/04 21:56:55 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef NODECTESCAN_H
+#define NODECTESCAN_H
+
+#include "nodes/execnodes.h"
+
+extern int	ExecCountSlotsCteScan(CteScan *node);
+extern CteScanState *ExecInitCteScan(CteScan *node, EState *estate, int eflags);
+extern TupleTableSlot *ExecCteScan(CteScanState *node);
+extern void ExecEndCteScan(CteScanState *node);
+extern void ExecCteScanReScan(CteScanState *node, ExprContext *exprCtxt);
+
+#endif   /* NODECTESCAN_H */
diff --git a/src/include/executor/nodeRecursiveunion.h b/src/include/executor/nodeRecursiveunion.h
new file mode 100644
index 00000000000..561f82a69b3
--- /dev/null
+++ b/src/include/executor/nodeRecursiveunion.h
@@ -0,0 +1,25 @@
+/*-------------------------------------------------------------------------
+ *
+ * nodeRecursiveunion.h
+ *
+ *
+ *
+ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * $PostgreSQL: pgsql/src/include/executor/nodeRecursiveunion.h,v 1.1 2008/10/04 21:56:55 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef NODERECURSIVEUNION_H
+#define NODERECURSIVEUNION_H
+
+#include "nodes/execnodes.h"
+
+extern int	ExecCountSlotsRecursiveUnion(RecursiveUnion *node);
+extern RecursiveUnionState *ExecInitRecursiveUnion(RecursiveUnion *node, EState *estate, int eflags);
+extern TupleTableSlot *ExecRecursiveUnion(RecursiveUnionState *node);
+extern void ExecEndRecursiveUnion(RecursiveUnionState *node);
+extern void ExecRecursiveUnionReScan(RecursiveUnionState *node, ExprContext *exprCtxt);
+
+#endif   /* NODERECURSIVEUNION_H */
diff --git a/src/include/executor/nodeWorktablescan.h b/src/include/executor/nodeWorktablescan.h
new file mode 100644
index 00000000000..fb4e309a91c
--- /dev/null
+++ b/src/include/executor/nodeWorktablescan.h
@@ -0,0 +1,25 @@
+/*-------------------------------------------------------------------------
+ *
+ * nodeWorktablescan.h
+ *
+ *
+ *
+ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * $PostgreSQL: pgsql/src/include/executor/nodeWorktablescan.h,v 1.1 2008/10/04 21:56:55 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef NODEWORKTABLESCAN_H
+#define NODEWORKTABLESCAN_H
+
+#include "nodes/execnodes.h"
+
+extern int	ExecCountSlotsWorkTableScan(WorkTableScan *node);
+extern WorkTableScanState *ExecInitWorkTableScan(WorkTableScan *node, EState *estate, int eflags);
+extern TupleTableSlot *ExecWorkTableScan(WorkTableScanState *node);
+extern void ExecEndWorkTableScan(WorkTableScanState *node);
+extern void ExecWorkTableScanReScan(WorkTableScanState *node, ExprContext *exprCtxt);
+
+#endif   /* NODEWORKTABLESCAN_H */
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index eb187ce4597..02c9c8f0566 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/nodes/execnodes.h,v 1.188 2008/10/01 19:51:49 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/execnodes.h,v 1.189 2008/10/04 21:56:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -947,6 +947,26 @@ typedef struct AppendState
 } AppendState;
 
 /* ----------------
+ *	 RecursiveUnionState information
+ *
+ *		RecursiveUnionState is used for performing a recursive union.
+ *
+ *		recursing			T when we're done scanning the non-recursive term
+ *		intermediate_empty	T if intermediate_table is currently empty
+ *		working_table		working table (to be scanned by recursive term)
+ *		intermediate_table	current recursive output (next generation of WT)
+ * ----------------
+ */
+typedef struct RecursiveUnionState
+{
+	PlanState	ps;				/* its first field is NodeTag */
+	bool		recursing;
+	bool		intermediate_empty;
+	Tuplestorestate *working_table;
+	Tuplestorestate *intermediate_table;
+} RecursiveUnionState;
+
+/* ----------------
  *	 BitmapAndState information
  * ----------------
  */
@@ -1179,6 +1199,43 @@ typedef struct ValuesScanState
 	int			marked_idx;
 } ValuesScanState;
 
+/* ----------------
+ *	 CteScanState information
+ *
+ *		CteScan nodes are used to scan a CommonTableExpr query.
+ *
+ * Multiple CteScan nodes can read out from the same CTE query.  We use
+ * a tuplestore to hold rows that have been read from the CTE query but
+ * not yet consumed by all readers.
+ * ----------------
+ */
+typedef struct CteScanState
+{
+	ScanState	ss;				/* its first field is NodeTag */
+	int			eflags;			/* capability flags to pass to tuplestore */
+	int			readptr;		/* index of my tuplestore read pointer */
+	PlanState  *cteplanstate;	/* PlanState for the CTE query itself */
+	/* Link to the "leader" CteScanState (possibly this same node) */
+	struct CteScanState *leader;
+	/* The remaining fields are only valid in the "leader" CteScanState */
+	Tuplestorestate *cte_table;	/* rows already read from the CTE query */
+	bool		eof_cte;		/* reached end of CTE query? */
+} CteScanState;
+
+/* ----------------
+ *	 WorkTableScanState information
+ *
+ *		WorkTableScan nodes are used to scan the work table created by
+ *		a RecursiveUnion node.  We locate the RecursiveUnion node
+ *		during executor startup.
+ * ----------------
+ */
+typedef struct WorkTableScanState
+{
+	ScanState	ss;				/* its first field is NodeTag */
+	RecursiveUnionState *rustate;
+} WorkTableScanState;
+
 /* ----------------------------------------------------------------
  *				 Join State Information
  * ----------------------------------------------------------------
diff --git a/src/include/nodes/nodeFuncs.h b/src/include/nodes/nodeFuncs.h
index 5ea2efe81ef..bf24297eaa8 100644
--- a/src/include/nodes/nodeFuncs.h
+++ b/src/include/nodes/nodeFuncs.h
@@ -6,7 +6,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/nodes/nodeFuncs.h,v 1.28 2008/08/28 23:09:48 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/nodeFuncs.h,v 1.29 2008/10/04 21:56:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -18,8 +18,11 @@
 
 /* flags bits for query_tree_walker and query_tree_mutator */
 #define QTW_IGNORE_RT_SUBQUERIES	0x01		/* subqueries in rtable */
-#define QTW_IGNORE_JOINALIASES		0x02		/* JOIN alias var lists */
-#define QTW_DONT_COPY_QUERY			0x04		/* do not copy top Query */
+#define QTW_IGNORE_CTE_SUBQUERIES	0x02		/* subqueries in cteList */
+#define QTW_IGNORE_RC_SUBQUERIES	0x03		/* both of above */
+#define QTW_IGNORE_JOINALIASES		0x04		/* JOIN alias var lists */
+#define QTW_EXAMINE_RTES			0x08		/* examine RTEs */
+#define QTW_DONT_COPY_QUERY			0x10		/* do not copy top Query */
 
 
 extern Oid	exprType(Node *expr);
@@ -49,4 +52,7 @@ extern bool query_or_expression_tree_walker(Node *node, bool (*walker) (),
 extern Node *query_or_expression_tree_mutator(Node *node, Node *(*mutator) (),
 												   void *context, int flags);
 
+extern bool raw_expression_tree_walker(Node *node, bool (*walker) (),
+									   void *context);
+
 #endif   /* NODEFUNCS_H */
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index c02b4c17904..4aa5ce43458 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/nodes/nodes.h,v 1.212 2008/09/09 18:58:08 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/nodes.h,v 1.213 2008/10/04 21:56:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -44,6 +44,7 @@ typedef enum NodeTag
 	T_Plan = 100,
 	T_Result,
 	T_Append,
+	T_RecursiveUnion,
 	T_BitmapAnd,
 	T_BitmapOr,
 	T_Scan,
@@ -55,6 +56,8 @@ typedef enum NodeTag
 	T_SubqueryScan,
 	T_FunctionScan,
 	T_ValuesScan,
+	T_CteScan,
+	T_WorkTableScan,
 	T_Join,
 	T_NestLoop,
 	T_MergeJoin,
@@ -78,6 +81,7 @@ typedef enum NodeTag
 	T_PlanState = 200,
 	T_ResultState,
 	T_AppendState,
+	T_RecursiveUnionState,
 	T_BitmapAndState,
 	T_BitmapOrState,
 	T_ScanState,
@@ -89,6 +93,8 @@ typedef enum NodeTag
 	T_SubqueryScanState,
 	T_FunctionScanState,
 	T_ValuesScanState,
+	T_CteScanState,
+	T_WorkTableScanState,
 	T_JoinState,
 	T_NestLoopState,
 	T_MergeJoinState,
@@ -352,6 +358,8 @@ typedef enum NodeTag
 	T_LockingClause,
 	T_RowMarkClause,
 	T_XmlSerialize,
+	T_WithClause,
+	T_CommonTableExpr,
 
 	/*
 	 * TAGS FOR RANDOM OTHER STUFF
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index 8b8757659b7..2660d7adb80 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -13,7 +13,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/nodes/parsenodes.h,v 1.375 2008/09/08 00:47:41 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/parsenodes.h,v 1.376 2008/10/04 21:56:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -115,6 +115,9 @@ typedef struct Query
 	bool		hasAggs;		/* has aggregates in tlist or havingQual */
 	bool		hasSubLinks;	/* has subquery SubLink */
 	bool		hasDistinctOn;	/* distinctClause is from DISTINCT ON */
+	bool		hasRecursive;	/* WITH RECURSIVE was specified */
+
+	List	   *cteList;		/* WITH list (of CommonTableExpr's) */
 
 	List	   *rtable;			/* list of range table entries */
 	FromExpr   *jointree;		/* table join tree (FROM and WHERE clauses) */
@@ -563,7 +566,8 @@ typedef enum RTEKind
 	RTE_JOIN,					/* join */
 	RTE_SPECIAL,				/* special rule relation (NEW or OLD) */
 	RTE_FUNCTION,				/* function in FROM */
-	RTE_VALUES					/* VALUES (<exprlist>), (<exprlist>), ... */
+	RTE_VALUES,					/* VALUES (<exprlist>), (<exprlist>), ... */
+	RTE_CTE						/* common table expr (WITH list element) */
 } RTEKind;
 
 typedef struct RangeTblEntry
@@ -589,6 +593,20 @@ typedef struct RangeTblEntry
 	Query	   *subquery;		/* the sub-query */
 
 	/*
+	 * Fields valid for a join RTE (else NULL/zero):
+	 *
+	 * joinaliasvars is a list of Vars or COALESCE expressions corresponding
+	 * to the columns of the join result.  An alias Var referencing column K
+	 * of the join result can be replaced by the K'th element of joinaliasvars
+	 * --- but to simplify the task of reverse-listing aliases correctly, we
+	 * do not do that until planning time.	In a Query loaded from a stored
+	 * rule, it is also possible for joinaliasvars items to be NULL Consts,
+	 * denoting columns dropped since the rule was made.
+	 */
+	JoinType	jointype;		/* type of join */
+	List	   *joinaliasvars;	/* list of alias-var expansions */
+
+	/*
 	 * Fields valid for a function RTE (else NULL):
 	 *
 	 * If the function returns RECORD, funccoltypes lists the column types
@@ -605,18 +623,13 @@ typedef struct RangeTblEntry
 	List	   *values_lists;	/* list of expression lists */
 
 	/*
-	 * Fields valid for a join RTE (else NULL/zero):
-	 *
-	 * joinaliasvars is a list of Vars or COALESCE expressions corresponding
-	 * to the columns of the join result.  An alias Var referencing column K
-	 * of the join result can be replaced by the K'th element of joinaliasvars
-	 * --- but to simplify the task of reverse-listing aliases correctly, we
-	 * do not do that until planning time.	In a Query loaded from a stored
-	 * rule, it is also possible for joinaliasvars items to be NULL Consts,
-	 * denoting columns dropped since the rule was made.
+	 * Fields valid for a CTE RTE (else NULL/zero):
 	 */
-	JoinType	jointype;		/* type of join */
-	List	   *joinaliasvars;	/* list of alias-var expansions */
+	char	   *ctename;		/* name of the WITH list item */
+	Index		ctelevelsup;	/* number of query levels up */
+	bool		self_reference;	/* is this a recursive self-reference? */
+	List	   *ctecoltypes;	/* OID list of column type OIDs */
+	List	   *ctecoltypmods;	/* integer list of column typmods */
 
 	/*
 	 * Fields valid in all RTEs:
@@ -697,6 +710,43 @@ typedef struct RowMarkClause
 	bool		noWait;			/* NOWAIT option */
 } RowMarkClause;
 
+/*
+ * WithClause -
+ *     representation of WITH clause
+ *
+ * Note: WithClause does not propagate into the Query representation;
+ * but CommonTableExpr does.
+ */
+typedef struct WithClause
+{
+	NodeTag		type;
+	List	   *ctes;			/* list of CommonTableExprs */
+	bool		recursive;		/* true = WITH RECURSIVE */
+	int			location;		/* token location, or -1 if unknown */
+} WithClause;
+
+/*
+ * CommonTableExpr -
+ *     representation of WITH list element
+ *
+ * We don't currently support the SEARCH or CYCLE clause.
+ */
+typedef struct CommonTableExpr
+{
+	NodeTag		type;
+	char	   *ctename;		/* query name (never qualified) */
+	List	   *aliascolnames;	/* optional list of column names */
+	Node	   *ctequery;		/* subquery (SelectStmt or Query) */
+	int			location;		/* token location, or -1 if unknown */
+	/* These fields are set during parse analysis: */
+	bool		cterecursive;	/* is this CTE actually recursive? */
+	int			cterefcount;	/* number of RTEs referencing this CTE
+								 * (excluding internal self-references) */
+	List	   *ctecolnames;	/* list of output column names */
+	List	   *ctecoltypes;	/* OID list of output column type OIDs */
+	List	   *ctecoltypmods;	/* integer list of output column typmods */
+} CommonTableExpr;
+
 /*****************************************************************************
  *		Optimizable Statements
  *****************************************************************************/
@@ -781,6 +831,7 @@ typedef struct SelectStmt
 	Node	   *whereClause;	/* WHERE qualification */
 	List	   *groupClause;	/* GROUP BY clauses */
 	Node	   *havingClause;	/* HAVING conditional-expression */
+	WithClause *withClause;		/* WITH clause */
 
 	/*
 	 * In a "leaf" node representing a VALUES list, the above fields are all
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 2f0ed9a5d79..cdf06b00207 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/nodes/plannodes.h,v 1.103 2008/09/09 18:58:08 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/plannodes.h,v 1.104 2008/10/04 21:56:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -183,6 +183,20 @@ typedef struct Append
 } Append;
 
 /* ----------------
+ *	RecursiveUnion node -
+ *		Generate a recursive union of two subplans.
+ *
+ * The "outer" subplan is always the non-recursive term, and the "inner"
+ * subplan is the recursive term.
+ * ----------------
+ */
+typedef struct RecursiveUnion
+{
+	Plan		plan;
+	int			wtParam;		/* ID of Param representing work table */
+} RecursiveUnion;
+
+/* ----------------
  *	 BitmapAnd node -
  *		Generate the intersection of the results of sub-plans.
  *
@@ -358,6 +372,28 @@ typedef struct ValuesScan
 	List	   *values_lists;	/* list of expression lists */
 } ValuesScan;
 
+/* ----------------
+ *		CteScan node
+ * ----------------
+ */
+typedef struct CteScan
+{
+	Scan		scan;
+	int			ctePlanId;		/* ID of init SubPlan for CTE */
+	int			cteParam;		/* ID of Param representing CTE output */
+} CteScan;
+
+/* ----------------
+ *		WorkTableScan node
+ * ----------------
+ */
+typedef struct WorkTableScan
+{
+	Scan		scan;
+	int			wtParam;		/* ID of Param representing work table */
+} WorkTableScan;
+
+
 /*
  * ==========
  * Join nodes
diff --git a/src/include/nodes/primnodes.h b/src/include/nodes/primnodes.h
index e144251dd1c..e8614492fe4 100644
--- a/src/include/nodes/primnodes.h
+++ b/src/include/nodes/primnodes.h
@@ -10,7 +10,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/nodes/primnodes.h,v 1.141 2008/09/01 20:42:45 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/primnodes.h,v 1.142 2008/10/04 21:56:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -386,6 +386,7 @@ typedef struct BoolExpr
  *	ROWCOMPARE_SUBLINK	(lefthand) op (SELECT ...)
  *	EXPR_SUBLINK		(SELECT with single targetlist item ...)
  *	ARRAY_SUBLINK		ARRAY(SELECT with single targetlist item ...)
+ *	CTE_SUBLINK			WITH query (never actually part of an expression)
  * For ALL, ANY, and ROWCOMPARE, the lefthand is a list of expressions of the
  * same length as the subselect's targetlist.  ROWCOMPARE will *always* have
  * a list with more than one entry; if the subselect has just one target
@@ -412,6 +413,9 @@ typedef struct BoolExpr
  *
  * In EXISTS, EXPR, and ARRAY SubLinks, testexpr and operName are unused and
  * are always null.
+ *
+ * The CTE_SUBLINK case never occurs in actual SubLink nodes, but it is used
+ * in SubPlans generated for WITH subqueries.
  */
 typedef enum SubLinkType
 {
@@ -420,7 +424,8 @@ typedef enum SubLinkType
 	ANY_SUBLINK,
 	ROWCOMPARE_SUBLINK,
 	EXPR_SUBLINK,
-	ARRAY_SUBLINK
+	ARRAY_SUBLINK,
+	CTE_SUBLINK					/* for SubPlans only */
 } SubLinkType;
 
 
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index c66bc05a749..9cb4370c854 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.159 2008/09/09 18:58:08 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.160 2008/10/04 21:56:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -104,6 +104,8 @@ typedef struct PlannerInfo
 
 	Index		query_level;	/* 1 at the outermost Query */
 
+	struct PlannerInfo *parent_root; /* NULL at outermost Query */
+
 	/*
 	 * simple_rel_array holds pointers to "base rels" and "other rels" (see
 	 * comments for RelOptInfo for more info).	It is indexed by rangetable
@@ -138,7 +140,9 @@ typedef struct PlannerInfo
 
 	List	   *returningLists; /* list of lists of TargetEntry, or NIL */
 
-	List	   *init_plans;		/* init subplans for query */
+	List	   *init_plans;		/* init SubPlans for query */
+
+	List	   *cte_plan_ids;	/* per-CTE-item list of subplan IDs */
 
 	List	   *eq_classes;		/* list of active EquivalenceClasses */
 
@@ -178,6 +182,11 @@ typedef struct PlannerInfo
 	bool		hasHavingQual;	/* true if havingQual was non-null */
 	bool		hasPseudoConstantQuals; /* true if any RestrictInfo has
 										 * pseudoconstant = true */
+	bool		hasRecursion;	/* true if planning a recursive WITH item */
+
+	/* These fields are used only when hasRecursion is true: */
+	int			wt_param_id;			/* PARAM_EXEC ID for the work table */
+	struct Plan *non_recursive_plan;	/* plan for non-recursive term */
 } PlannerInfo;
 
 
@@ -542,8 +551,9 @@ typedef struct PathKey
 } PathKey;
 
 /*
- * Type "Path" is used as-is for sequential-scan paths.  For other
- * path types it is the first component of a larger struct.
+ * Type "Path" is used as-is for sequential-scan paths, as well as some other
+ * simple plan types that we don't need any extra information in the path for.
+ * For other path types it is the first component of a larger struct.
  *
  * Note: "pathtype" is the NodeTag of the Plan node we could build from this
  * Path.  It is partially redundant with the Path's NodeTag, but allows us
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 8ad8f7f0626..181327caa81 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/cost.h,v 1.92 2008/08/22 00:16:04 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/cost.h,v 1.93 2008/10/04 21:56:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -72,6 +72,8 @@ extern void cost_functionscan(Path *path, PlannerInfo *root,
 				  RelOptInfo *baserel);
 extern void cost_valuesscan(Path *path, PlannerInfo *root,
 				RelOptInfo *baserel);
+extern void cost_ctescan(Path *path, PlannerInfo *root, RelOptInfo *baserel);
+extern void cost_recursive_union(Plan *runion, Plan *nrterm, Plan *rterm);
 extern void cost_sort(Path *path, PlannerInfo *root,
 		  List *pathkeys, Cost input_cost, double tuples, int width,
 		  double limit_tuples);
@@ -104,6 +106,8 @@ extern void set_joinrel_size_estimates(PlannerInfo *root, RelOptInfo *rel,
 						   List *restrictlist);
 extern void set_function_size_estimates(PlannerInfo *root, RelOptInfo *rel);
 extern void set_values_size_estimates(PlannerInfo *root, RelOptInfo *rel);
+extern void set_cte_size_estimates(PlannerInfo *root, RelOptInfo *rel,
+								   Plan *cteplan);
 
 /*
  * prototypes for clausesel.c
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 1db1674e122..b8a256aa1b8 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/pathnode.h,v 1.78 2008/08/14 18:48:00 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/pathnode.h,v 1.79 2008/10/04 21:56:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -54,6 +54,8 @@ extern UniquePath *create_unique_path(PlannerInfo *root, RelOptInfo *rel,
 extern Path *create_subqueryscan_path(RelOptInfo *rel, List *pathkeys);
 extern Path *create_functionscan_path(PlannerInfo *root, RelOptInfo *rel);
 extern Path *create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel);
+extern Path *create_ctescan_path(PlannerInfo *root, RelOptInfo *rel);
+extern Path *create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel);
 
 extern NestPath *create_nestloop_path(PlannerInfo *root,
 					 RelOptInfo *joinrel,
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index a6b15187cea..1e8017fb6d4 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/planmain.h,v 1.112 2008/09/09 18:58:09 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/planmain.h,v 1.113 2008/10/04 21:56:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -42,6 +42,8 @@ extern Plan *create_plan(PlannerInfo *root, Path *best_path);
 extern SubqueryScan *make_subqueryscan(List *qptlist, List *qpqual,
 				  Index scanrelid, Plan *subplan, List *subrtable);
 extern Append *make_append(List *appendplans, bool isTarget, List *tlist);
+extern RecursiveUnion *make_recursive_union(List *tlist,
+			   Plan *lefttree, Plan *righttree, int wtParam);
 extern Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree,
 						List *pathkeys, double limit_tuples);
 extern Sort *make_sort_from_sortclauses(PlannerInfo *root, List *sortcls,
diff --git a/src/include/optimizer/planner.h b/src/include/optimizer/planner.h
index 0405868b74a..3529fd18505 100644
--- a/src/include/optimizer/planner.h
+++ b/src/include/optimizer/planner.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/planner.h,v 1.44 2008/01/01 19:45:58 momjian Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/planner.h,v 1.45 2008/10/04 21:56:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -30,7 +30,8 @@ extern PlannedStmt *planner(Query *parse, int cursorOptions,
 extern PlannedStmt *standard_planner(Query *parse, int cursorOptions,
 				 ParamListInfo boundParams);
 extern Plan *subquery_planner(PlannerGlobal *glob, Query *parse,
-				 Index level, double tuple_fraction,
+				 PlannerInfo *parent_root,
+				 bool hasRecursion, double tuple_fraction,
 				 PlannerInfo **subroot);
 
 #endif   /* PLANNER_H */
diff --git a/src/include/optimizer/subselect.h b/src/include/optimizer/subselect.h
index 97e230a2dbf..e227221e946 100644
--- a/src/include/optimizer/subselect.h
+++ b/src/include/optimizer/subselect.h
@@ -5,7 +5,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/optimizer/subselect.h,v 1.33 2008/08/17 01:20:00 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/subselect.h,v 1.34 2008/10/04 21:56:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -15,6 +15,7 @@
 #include "nodes/plannodes.h"
 #include "nodes/relation.h"
 
+extern void SS_process_ctes(PlannerInfo *root);
 extern bool convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
 										Relids available_rels,
 										Node **new_qual, List **fromlist);
@@ -28,5 +29,6 @@ extern void SS_finalize_plan(PlannerInfo *root, Plan *plan,
 							 bool attach_initplans);
 extern Param *SS_make_initplan_from_plan(PlannerInfo *root, Plan *plan,
 						   Oid resulttype, int32 resulttypmod);
+extern int	SS_assign_worktable_param(PlannerInfo *root);
 
 #endif   /* SUBSELECT_H */
diff --git a/src/include/parser/parse_cte.h b/src/include/parser/parse_cte.h
new file mode 100644
index 00000000000..142e833f3e1
--- /dev/null
+++ b/src/include/parser/parse_cte.h
@@ -0,0 +1,21 @@
+/*-------------------------------------------------------------------------
+ *
+ * parse_cte.h
+ *	  handle CTEs (common table expressions) in parser
+ *
+ *
+ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * $PostgreSQL: pgsql/src/include/parser/parse_cte.h,v 1.1 2008/10/04 21:56:55 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef PARSE_CTE_H
+#define PARSE_CTE_H
+
+#include "parser/parse_node.h"
+
+extern List *transformWithClause(ParseState *pstate, WithClause *withClause);
+
+#endif   /* PARSE_CTE_H */
diff --git a/src/include/parser/parse_node.h b/src/include/parser/parse_node.h
index 460655d3b14..05817cf51a3 100644
--- a/src/include/parser/parse_node.h
+++ b/src/include/parser/parse_node.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/parser/parse_node.h,v 1.56 2008/09/01 20:42:45 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/parser/parse_node.h,v 1.57 2008/10/04 21:56:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -50,6 +50,10 @@
  * implicit RTEs into p_relnamespace but not p_varnamespace, so that they
  * do not affect the set of columns available for unqualified references.
  *
+ * p_ctenamespace: list of CommonTableExprs (WITH items) that are visible
+ * at the moment.  This is different from p_relnamespace because you have
+ * to make an RTE before you can access a CTE.
+ *
  * p_paramtypes: an array of p_numparams type OIDs for $n parameter symbols
  * (zeroth entry in array corresponds to $1).  If p_variableparams is true, the
  * set of param types is not predetermined; in that case, a zero array entry
@@ -68,6 +72,7 @@ typedef struct ParseState
 								 * node's fromlist) */
 	List	   *p_relnamespace; /* current namespace for relations */
 	List	   *p_varnamespace; /* current namespace for columns */
+	List	   *p_ctenamespace; /* current namespace for common table exprs */
 	Oid		   *p_paramtypes;	/* OIDs of types for $n parameter symbols */
 	int			p_numparams;	/* allocated size of p_paramtypes[] */
 	int			p_next_resno;	/* next targetlist resno to assign */
diff --git a/src/include/parser/parse_relation.h b/src/include/parser/parse_relation.h
index 1c4e1b6b8ed..9c81d4b50b5 100644
--- a/src/include/parser/parse_relation.h
+++ b/src/include/parser/parse_relation.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/parser/parse_relation.h,v 1.58 2008/09/01 20:42:45 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/parser/parse_relation.h,v 1.59 2008/10/04 21:56:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -31,6 +31,7 @@ extern int RTERangeTablePosn(ParseState *pstate,
 extern RangeTblEntry *GetRTEByRangeTablePosn(ParseState *pstate,
 					   int varno,
 					   int sublevels_up);
+extern CommonTableExpr *GetCTEForRTE(ParseState *pstate, RangeTblEntry *rte);
 extern Node *scanRTEForColumn(ParseState *pstate, RangeTblEntry *rte,
 				 char *colname, int location);
 extern Node *colNameToVar(ParseState *pstate, char *colname, bool localonly,
@@ -72,6 +73,11 @@ extern RangeTblEntry *addRangeTableEntryForJoin(ParseState *pstate,
 						  List *aliasvars,
 						  Alias *alias,
 						  bool inFromCl);
+extern RangeTblEntry *addRangeTableEntryForCTE(ParseState *pstate,
+						 CommonTableExpr *cte,
+						 Index levelsup,
+						 Alias *alias,
+						 bool inFromCl);
 extern void addRTEtoQuery(ParseState *pstate, RangeTblEntry *rte,
 			  bool addToJoinList,
 			  bool addToRelNameSpace, bool addToVarNameSpace);
diff --git a/src/include/utils/errcodes.h b/src/include/utils/errcodes.h
index 9cfdd16bde2..baecd7bafcb 100644
--- a/src/include/utils/errcodes.h
+++ b/src/include/utils/errcodes.h
@@ -11,7 +11,7 @@
  *
  * Copyright (c) 2003-2008, PostgreSQL Global Development Group
  *
- * $PostgreSQL: pgsql/src/include/utils/errcodes.h,v 1.25 2008/05/15 22:39:49 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/utils/errcodes.h,v 1.26 2008/10/04 21:56:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -246,6 +246,7 @@
 #define ERRCODE_INSUFFICIENT_PRIVILEGE		MAKE_SQLSTATE('4','2', '5','0','1')
 #define ERRCODE_CANNOT_COERCE				MAKE_SQLSTATE('4','2', '8','4','6')
 #define ERRCODE_GROUPING_ERROR				MAKE_SQLSTATE('4','2', '8','0','3')
+#define ERRCODE_INVALID_RECURSION			MAKE_SQLSTATE('4','2', 'P','1','9')
 #define ERRCODE_INVALID_FOREIGN_KEY			MAKE_SQLSTATE('4','2', '8','3','0')
 #define ERRCODE_INVALID_NAME				MAKE_SQLSTATE('4','2', '6','0','2')
 #define ERRCODE_NAME_TOO_LONG				MAKE_SQLSTATE('4','2', '6','2','2')
diff --git a/src/include/utils/tuplestore.h b/src/include/utils/tuplestore.h
index 3fe32f682b1..201e8ba055b 100644
--- a/src/include/utils/tuplestore.h
+++ b/src/include/utils/tuplestore.h
@@ -24,7 +24,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $PostgreSQL: pgsql/src/include/utils/tuplestore.h,v 1.24 2008/10/01 19:51:50 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/utils/tuplestore.h,v 1.25 2008/10/04 21:56:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -74,6 +74,8 @@ extern bool tuplestore_ateof(Tuplestorestate *state);
 
 extern void tuplestore_rescan(Tuplestorestate *state);
 
+extern void tuplestore_clear(Tuplestorestate *state);
+
 extern void tuplestore_end(Tuplestorestate *state);
 
 #endif   /* TUPLESTORE_H */