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

6 files changed, 674 insertions, 22 deletions

diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
index 9cfa1700f43..57ef558c404 100644
--- a/src/backend/nodes/copyfuncs.c
+++ b/src/backend/nodes/copyfuncs.c
@@ -15,7 +15,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/nodes/copyfuncs.c,v 1.405 2008/09/09 18:58:08 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/nodes/copyfuncs.c,v 1.406 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -177,6 +177,27 @@ _copyAppend(Append *from)
 }
 
 /*
+ * _copyRecursiveUnion
+ */
+static RecursiveUnion *
+_copyRecursiveUnion(RecursiveUnion *from)
+{
+	RecursiveUnion	   *newnode = makeNode(RecursiveUnion);
+
+	/*
+	 * copy node superclass fields
+	 */
+	CopyPlanFields((Plan *) from, (Plan *) newnode);
+
+	/*
+	 * copy remainder of node
+	 */
+	COPY_SCALAR_FIELD(wtParam);
+
+	return newnode;
+}
+
+/*
  * _copyBitmapAnd
  */
 static BitmapAnd *
@@ -422,6 +443,49 @@ _copyValuesScan(ValuesScan *from)
 }
 
 /*
+ * _copyCteScan
+ */
+static CteScan *
+_copyCteScan(CteScan *from)
+{
+	CteScan *newnode = makeNode(CteScan);
+
+	/*
+	 * copy node superclass fields
+	 */
+	CopyScanFields((Scan *) from, (Scan *) newnode);
+
+	/*
+	 * copy remainder of node
+	 */
+	COPY_SCALAR_FIELD(ctePlanId);
+	COPY_SCALAR_FIELD(cteParam);
+
+	return newnode;
+}
+
+/*
+ * _copyWorkTableScan
+ */
+static WorkTableScan *
+_copyWorkTableScan(WorkTableScan *from)
+{
+	WorkTableScan *newnode = makeNode(WorkTableScan);
+
+	/*
+	 * copy node superclass fields
+	 */
+	CopyScanFields((Scan *) from, (Scan *) newnode);
+
+	/*
+	 * copy remainder of node
+	 */
+	COPY_SCALAR_FIELD(wtParam);
+
+	return newnode;
+}
+
+/*
  * CopyJoinFields
  *
  *		This function copies the fields of the Join node.  It is used by
@@ -1572,12 +1636,17 @@ _copyRangeTblEntry(RangeTblEntry *from)
 	COPY_SCALAR_FIELD(rtekind);
 	COPY_SCALAR_FIELD(relid);
 	COPY_NODE_FIELD(subquery);
+	COPY_SCALAR_FIELD(jointype);
+	COPY_NODE_FIELD(joinaliasvars);
 	COPY_NODE_FIELD(funcexpr);
 	COPY_NODE_FIELD(funccoltypes);
 	COPY_NODE_FIELD(funccoltypmods);
 	COPY_NODE_FIELD(values_lists);
-	COPY_SCALAR_FIELD(jointype);
-	COPY_NODE_FIELD(joinaliasvars);
+	COPY_STRING_FIELD(ctename);
+	COPY_SCALAR_FIELD(ctelevelsup);
+	COPY_SCALAR_FIELD(self_reference);
+	COPY_NODE_FIELD(ctecoltypes);
+	COPY_NODE_FIELD(ctecoltypmods);
 	COPY_NODE_FIELD(alias);
 	COPY_NODE_FIELD(eref);
 	COPY_SCALAR_FIELD(inh);
@@ -1632,6 +1701,36 @@ _copyRowMarkClause(RowMarkClause *from)
 	return newnode;
 }
 
+static WithClause *
+_copyWithClause(WithClause *from)
+{
+	WithClause *newnode = makeNode(WithClause);
+
+	COPY_NODE_FIELD(ctes);
+	COPY_SCALAR_FIELD(recursive);
+	COPY_LOCATION_FIELD(location);
+
+	return newnode;
+}
+
+static CommonTableExpr *
+_copyCommonTableExpr(CommonTableExpr *from)
+{
+	CommonTableExpr *newnode = makeNode(CommonTableExpr);
+
+	COPY_STRING_FIELD(ctename);
+	COPY_NODE_FIELD(aliascolnames);
+	COPY_NODE_FIELD(ctequery);
+	COPY_LOCATION_FIELD(location);
+	COPY_SCALAR_FIELD(cterecursive);
+	COPY_SCALAR_FIELD(cterefcount);
+	COPY_NODE_FIELD(ctecolnames);
+	COPY_NODE_FIELD(ctecoltypes);
+	COPY_NODE_FIELD(ctecoltypmods);
+
+	return newnode;
+}
+
 static A_Expr *
 _copyAExpr(A_Expr *from)
 {
@@ -1931,6 +2030,8 @@ _copyQuery(Query *from)
 	COPY_SCALAR_FIELD(hasAggs);
 	COPY_SCALAR_FIELD(hasSubLinks);
 	COPY_SCALAR_FIELD(hasDistinctOn);
+	COPY_SCALAR_FIELD(hasRecursive);
+	COPY_NODE_FIELD(cteList);
 	COPY_NODE_FIELD(rtable);
 	COPY_NODE_FIELD(jointree);
 	COPY_NODE_FIELD(targetList);
@@ -1999,6 +2100,7 @@ _copySelectStmt(SelectStmt *from)
 	COPY_NODE_FIELD(whereClause);
 	COPY_NODE_FIELD(groupClause);
 	COPY_NODE_FIELD(havingClause);
+	COPY_NODE_FIELD(withClause);
 	COPY_NODE_FIELD(valuesLists);
 	COPY_NODE_FIELD(sortClause);
 	COPY_NODE_FIELD(limitOffset);
@@ -3104,6 +3206,9 @@ copyObject(void *from)
 		case T_Append:
 			retval = _copyAppend(from);
 			break;
+		case T_RecursiveUnion:
+			retval = _copyRecursiveUnion(from);
+			break;
 		case T_BitmapAnd:
 			retval = _copyBitmapAnd(from);
 			break;
@@ -3137,6 +3242,12 @@ copyObject(void *from)
 		case T_ValuesScan:
 			retval = _copyValuesScan(from);
 			break;
+		case T_CteScan:
+			retval = _copyCteScan(from);
+			break;
+		case T_WorkTableScan:
+			retval = _copyWorkTableScan(from);
+			break;
 		case T_Join:
 			retval = _copyJoin(from);
 			break;
@@ -3672,6 +3783,12 @@ copyObject(void *from)
 		case T_RowMarkClause:
 			retval = _copyRowMarkClause(from);
 			break;
+		case T_WithClause:
+			retval = _copyWithClause(from);
+			break;
+		case T_CommonTableExpr:
+			retval = _copyCommonTableExpr(from);
+			break;
 		case T_FkConstraint:
 			retval = _copyFkConstraint(from);
 			break;
diff --git a/src/backend/nodes/equalfuncs.c b/src/backend/nodes/equalfuncs.c
index f0939b4777d..f01ebe33e87 100644
--- a/src/backend/nodes/equalfuncs.c
+++ b/src/backend/nodes/equalfuncs.c
@@ -22,7 +22,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/nodes/equalfuncs.c,v 1.331 2008/09/01 20:42:44 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/nodes/equalfuncs.c,v 1.332 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -808,6 +808,8 @@ _equalQuery(Query *a, Query *b)
 	COMPARE_SCALAR_FIELD(hasAggs);
 	COMPARE_SCALAR_FIELD(hasSubLinks);
 	COMPARE_SCALAR_FIELD(hasDistinctOn);
+	COMPARE_SCALAR_FIELD(hasRecursive);
+	COMPARE_NODE_FIELD(cteList);
 	COMPARE_NODE_FIELD(rtable);
 	COMPARE_NODE_FIELD(jointree);
 	COMPARE_NODE_FIELD(targetList);
@@ -868,6 +870,7 @@ _equalSelectStmt(SelectStmt *a, SelectStmt *b)
 	COMPARE_NODE_FIELD(whereClause);
 	COMPARE_NODE_FIELD(groupClause);
 	COMPARE_NODE_FIELD(havingClause);
+	COMPARE_NODE_FIELD(withClause);
 	COMPARE_NODE_FIELD(valuesLists);
 	COMPARE_NODE_FIELD(sortClause);
 	COMPARE_NODE_FIELD(limitOffset);
@@ -1932,12 +1935,17 @@ _equalRangeTblEntry(RangeTblEntry *a, RangeTblEntry *b)
 	COMPARE_SCALAR_FIELD(rtekind);
 	COMPARE_SCALAR_FIELD(relid);
 	COMPARE_NODE_FIELD(subquery);
+	COMPARE_SCALAR_FIELD(jointype);
+	COMPARE_NODE_FIELD(joinaliasvars);
 	COMPARE_NODE_FIELD(funcexpr);
 	COMPARE_NODE_FIELD(funccoltypes);
 	COMPARE_NODE_FIELD(funccoltypmods);
 	COMPARE_NODE_FIELD(values_lists);
-	COMPARE_SCALAR_FIELD(jointype);
-	COMPARE_NODE_FIELD(joinaliasvars);
+	COMPARE_STRING_FIELD(ctename);
+	COMPARE_SCALAR_FIELD(ctelevelsup);
+	COMPARE_SCALAR_FIELD(self_reference);
+	COMPARE_NODE_FIELD(ctecoltypes);
+	COMPARE_NODE_FIELD(ctecoltypmods);
 	COMPARE_NODE_FIELD(alias);
 	COMPARE_NODE_FIELD(eref);
 	COMPARE_SCALAR_FIELD(inh);
@@ -1970,6 +1978,32 @@ _equalRowMarkClause(RowMarkClause *a, RowMarkClause *b)
 }
 
 static bool
+_equalWithClause(WithClause *a, WithClause *b)
+{
+	COMPARE_NODE_FIELD(ctes);
+	COMPARE_SCALAR_FIELD(recursive);
+	COMPARE_LOCATION_FIELD(location);
+
+	return true;
+}
+
+static bool
+_equalCommonTableExpr(CommonTableExpr *a, CommonTableExpr *b)
+{
+	COMPARE_STRING_FIELD(ctename);
+	COMPARE_NODE_FIELD(aliascolnames);
+	COMPARE_NODE_FIELD(ctequery);
+	COMPARE_LOCATION_FIELD(location);
+	COMPARE_SCALAR_FIELD(cterecursive);
+	COMPARE_SCALAR_FIELD(cterefcount);
+	COMPARE_NODE_FIELD(ctecolnames);
+	COMPARE_NODE_FIELD(ctecoltypes);
+	COMPARE_NODE_FIELD(ctecoltypmods);
+
+	return true;
+}
+
+static bool
 _equalFkConstraint(FkConstraint *a, FkConstraint *b)
 {
 	COMPARE_STRING_FIELD(constr_name);
@@ -2593,6 +2627,12 @@ equal(void *a, void *b)
 		case T_RowMarkClause:
 			retval = _equalRowMarkClause(a, b);
 			break;
+		case T_WithClause:
+			retval = _equalWithClause(a, b);
+			break;
+		case T_CommonTableExpr:
+			retval = _equalCommonTableExpr(a, b);
+			break;
 		case T_FkConstraint:
 			retval = _equalFkConstraint(a, b);
 			break;
diff --git a/src/backend/nodes/nodeFuncs.c b/src/backend/nodes/nodeFuncs.c
index a0616415666..0127c6e14b2 100644
--- a/src/backend/nodes/nodeFuncs.c
+++ b/src/backend/nodes/nodeFuncs.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/nodes/nodeFuncs.c,v 1.32 2008/09/01 20:42:44 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/nodes/nodeFuncs.c,v 1.33 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -870,6 +870,12 @@ exprLocation(Node *expr)
 			/* XMLSERIALIZE keyword should always be the first thing */
 			loc = ((XmlSerialize *) expr)->location;
 			break;
+		case T_WithClause:
+			loc = ((WithClause *) expr)->location;
+			break;
+		case T_CommonTableExpr:
+			loc = ((CommonTableExpr *) expr)->location;
+			break;
 		default:
 			/* for any other node type it's just unknown... */
 			loc = -1;
@@ -1205,6 +1211,17 @@ expression_tree_walker(Node *node,
 		case T_Query:
 			/* Do nothing with a sub-Query, per discussion above */
 			break;
+		case T_CommonTableExpr:
+			{
+				CommonTableExpr *cte = (CommonTableExpr *) node;
+
+				/*
+				 * Invoke the walker on the CTE's Query node, so it
+				 * can recurse into the sub-query if it wants to.
+				 */
+				return walker(cte->ctequery, context);
+			}
+			break;
 		case T_List:
 			foreach(temp, (List *) node)
 			{
@@ -1313,6 +1330,11 @@ query_tree_walker(Query *query,
 		return true;
 	if (walker(query->limitCount, context))
 		return true;
+	if (!(flags & QTW_IGNORE_CTE_SUBQUERIES))
+	{
+		if (walker((Node *) query->cteList, context))
+			return true;
+	}
 	if (range_table_walker(query->rtable, walker, context, flags))
 		return true;
 	return false;
@@ -1335,10 +1357,16 @@ range_table_walker(List *rtable,
 	{
 		RangeTblEntry *rte = (RangeTblEntry *) lfirst(rt);
 
+		/* For historical reasons, visiting RTEs is not the default */
+		if (flags & QTW_EXAMINE_RTES)
+			if (walker(rte, context))
+				return true;
+
 		switch (rte->rtekind)
 		{
 			case RTE_RELATION:
 			case RTE_SPECIAL:
+ 			case RTE_CTE:
 				/* nothing to do */
 				break;
 			case RTE_SUBQUERY:
@@ -1806,6 +1834,21 @@ expression_tree_mutator(Node *node,
 		case T_Query:
 			/* Do nothing with a sub-Query, per discussion above */
 			return node;
+		case T_CommonTableExpr:
+			{
+				CommonTableExpr *cte = (CommonTableExpr *) node;
+				CommonTableExpr *newnode;
+
+				FLATCOPY(newnode, cte, CommonTableExpr);
+
+				/*
+				 * Also invoke the mutator on the CTE's Query node, so it
+				 * can recurse into the sub-query if it wants to.
+				 */
+				MUTATE(newnode->ctequery, cte->ctequery, Node *);
+				return (Node *) newnode;
+			}
+			break;
 		case T_List:
 			{
 				/*
@@ -1935,6 +1978,10 @@ query_tree_mutator(Query *query,
 	MUTATE(query->havingQual, query->havingQual, Node *);
 	MUTATE(query->limitOffset, query->limitOffset, Node *);
 	MUTATE(query->limitCount, query->limitCount, Node *);
+	if (!(flags & QTW_IGNORE_CTE_SUBQUERIES))
+		MUTATE(query->cteList, query->cteList, List *);
+	else						/* else copy CTE list as-is */
+		query->cteList = copyObject(query->cteList);
 	query->rtable = range_table_mutator(query->rtable,
 										mutator, context, flags);
 	return query;
@@ -1964,6 +2011,7 @@ range_table_mutator(List *rtable,
 		{
 			case RTE_RELATION:
 			case RTE_SPECIAL:
+			case RTE_CTE:
 				/* we don't bother to copy eref, aliases, etc; OK? */
 				break;
 			case RTE_SUBQUERY:
@@ -2044,3 +2092,304 @@ query_or_expression_tree_mutator(Node *node,
 	else
 		return mutator(node, context);
 }
+
+
+/*
+ * raw_expression_tree_walker --- walk raw parse trees
+ *
+ * This has exactly the same API as expression_tree_walker, but instead of
+ * walking post-analysis parse trees, it knows how to walk the node types
+ * found in raw grammar output.  (There is not currently any need for a
+ * combined walker, so we keep them separate in the name of efficiency.)
+ * Unlike expression_tree_walker, there is no special rule about query
+ * boundaries: we descend to everything that's possibly interesting.
+ *
+ * Currently, the node type coverage extends to SelectStmt and everything
+ * that could appear under it, but not other statement types.
+ */
+bool
+raw_expression_tree_walker(Node *node, bool (*walker) (), void *context)
+{
+	ListCell   *temp;
+
+	/*
+	 * The walker has already visited the current node, and so we need only
+	 * recurse into any sub-nodes it has.
+	 */
+	if (node == NULL)
+		return false;
+
+	/* Guard against stack overflow due to overly complex expressions */
+	check_stack_depth();
+
+	switch (nodeTag(node))
+	{
+		case T_SetToDefault:
+		case T_CurrentOfExpr:
+		case T_Integer:
+		case T_Float:
+		case T_String:
+		case T_BitString:
+		case T_Null:
+		case T_ParamRef:
+		case T_A_Const:
+		case T_A_Star:
+			/* primitive node types with no subnodes */
+			break;
+		case T_Alias:
+			/* we assume the colnames list isn't interesting */
+			break;
+		case T_RangeVar:
+			return walker(((RangeVar *) node)->alias, context);
+		case T_SubLink:
+			{
+				SubLink    *sublink = (SubLink *) node;
+
+				if (walker(sublink->testexpr, context))
+					return true;
+				/* we assume the operName is not interesting */
+				if (walker(sublink->subselect, context))
+					return true;
+			}
+			break;
+		case T_CaseExpr:
+			{
+				CaseExpr   *caseexpr = (CaseExpr *) node;
+
+				if (walker(caseexpr->arg, context))
+					return true;
+				/* we assume walker doesn't care about CaseWhens, either */
+				foreach(temp, caseexpr->args)
+				{
+					CaseWhen   *when = (CaseWhen *) lfirst(temp);
+
+					Assert(IsA(when, CaseWhen));
+					if (walker(when->expr, context))
+						return true;
+					if (walker(when->result, context))
+						return true;
+				}
+				if (walker(caseexpr->defresult, context))
+					return true;
+			}
+			break;
+		case T_RowExpr:
+			return walker(((RowExpr *) node)->args, context);
+		case T_CoalesceExpr:
+			return walker(((CoalesceExpr *) node)->args, context);
+		case T_MinMaxExpr:
+			return walker(((MinMaxExpr *) node)->args, context);
+		case T_XmlExpr:
+			{
+				XmlExpr    *xexpr = (XmlExpr *) node;
+
+				if (walker(xexpr->named_args, context))
+					return true;
+				/* we assume walker doesn't care about arg_names */
+				if (walker(xexpr->args, context))
+					return true;
+			}
+			break;
+		case T_NullTest:
+			return walker(((NullTest *) node)->arg, context);
+		case T_BooleanTest:
+			return walker(((BooleanTest *) node)->arg, context);
+		case T_JoinExpr:
+			{
+				JoinExpr   *join = (JoinExpr *) node;
+
+				if (walker(join->larg, context))
+					return true;
+				if (walker(join->rarg, context))
+					return true;
+				if (walker(join->quals, context))
+					return true;
+				if (walker(join->alias, context))
+					return true;
+				/* using list is deemed uninteresting */
+			}
+			break;
+		case T_IntoClause:
+			{
+				IntoClause *into = (IntoClause *) node;
+
+				if (walker(into->rel, context))
+					return true;
+				/* colNames, options are deemed uninteresting */
+			}
+			break;
+		case T_List:
+			foreach(temp, (List *) node)
+			{
+				if (walker((Node *) lfirst(temp), context))
+					return true;
+			}
+			break;
+		case T_SelectStmt:
+			{
+				SelectStmt *stmt = (SelectStmt *) node;
+
+				if (walker(stmt->distinctClause, context))
+					return true;
+				if (walker(stmt->intoClause, context))
+					return true;
+				if (walker(stmt->targetList, context))
+					return true;
+				if (walker(stmt->fromClause, context))
+					return true;
+				if (walker(stmt->whereClause, context))
+					return true;
+				if (walker(stmt->groupClause, context))
+					return true;
+				if (walker(stmt->havingClause, context))
+					return true;
+				if (walker(stmt->withClause, context))
+					return true;
+				if (walker(stmt->valuesLists, context))
+					return true;
+				if (walker(stmt->sortClause, context))
+					return true;
+				if (walker(stmt->limitOffset, context))
+					return true;
+				if (walker(stmt->limitCount, context))
+					return true;
+				if (walker(stmt->lockingClause, context))
+					return true;
+				if (walker(stmt->larg, context))
+					return true;
+				if (walker(stmt->rarg, context))
+					return true;
+			}
+			break;
+		case T_A_Expr:
+			{
+				A_Expr *expr = (A_Expr *) node;
+
+				if (walker(expr->lexpr, context))
+					return true;
+				if (walker(expr->rexpr, context))
+					return true;
+				/* operator name is deemed uninteresting */
+			}
+			break;
+		case T_ColumnRef:
+			/* we assume the fields contain nothing interesting */
+			break;
+		case T_FuncCall:
+			{
+				FuncCall *fcall = (FuncCall *) node;
+
+				if (walker(fcall->args, context))
+					return true;
+				/* function name is deemed uninteresting */
+			}
+			break;
+		case T_A_Indices:
+			{
+				A_Indices *indices = (A_Indices *) node;
+
+				if (walker(indices->lidx, context))
+					return true;
+				if (walker(indices->uidx, context))
+					return true;
+			}
+			break;
+		case T_A_Indirection:
+			{
+				A_Indirection *indir = (A_Indirection *) node;
+
+				if (walker(indir->arg, context))
+					return true;
+				if (walker(indir->indirection, context))
+					return true;
+			}
+			break;
+		case T_A_ArrayExpr:
+			return walker(((A_ArrayExpr *) node)->elements, context);
+		case T_ResTarget:
+			{
+				ResTarget *rt = (ResTarget *) node;
+
+				if (walker(rt->indirection, context))
+					return true;
+				if (walker(rt->val, context))
+					return true;
+			}
+			break;
+		case T_TypeCast:
+			{
+				TypeCast *tc = (TypeCast *) node;
+
+				if (walker(tc->arg, context))
+					return true;
+				if (walker(tc->typename, context))
+					return true;
+			}
+			break;
+		case T_SortBy:
+			return walker(((SortBy *) node)->node, context);
+		case T_RangeSubselect:
+			{
+				RangeSubselect *rs = (RangeSubselect *) node;
+
+				if (walker(rs->subquery, context))
+					return true;
+				if (walker(rs->alias, context))
+					return true;
+			}
+			break;
+		case T_RangeFunction:
+			{
+				RangeFunction *rf = (RangeFunction *) node;
+
+				if (walker(rf->funccallnode, context))
+					return true;
+				if (walker(rf->alias, context))
+					return true;
+			}
+			break;
+		case T_TypeName:
+			{
+				TypeName *tn = (TypeName *) node;
+
+				if (walker(tn->typmods, context))
+					return true;
+				if (walker(tn->arrayBounds, context))
+					return true;
+				/* type name itself is deemed uninteresting */
+			}
+			break;
+		case T_ColumnDef:
+			{
+				ColumnDef *coldef = (ColumnDef *) node;
+
+				if (walker(coldef->typename, context))
+					return true;
+				if (walker(coldef->raw_default, context))
+					return true;
+				/* for now, constraints are ignored */
+			}
+			break;
+		case T_LockingClause:
+			return walker(((LockingClause *) node)->lockedRels, context);
+		case T_XmlSerialize:
+			{
+				XmlSerialize *xs = (XmlSerialize *) node;
+
+				if (walker(xs->expr, context))
+					return true;
+				if (walker(xs->typename, context))
+					return true;
+			}
+			break;
+		case T_WithClause:
+			return walker(((WithClause *) node)->ctes, context);
+		case T_CommonTableExpr:
+			return walker(((CommonTableExpr *) node)->ctequery, context);
+		default:
+			elog(ERROR, "unrecognized node type: %d",
+				 (int) nodeTag(node));
+			break;
+	}
+	return false;
+}
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 0b74b3a063d..6d39a51a983 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.339 2008/09/09 18:58:08 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.340 2008/10/04 21:56:53 tgl Exp $
  *
  * NOTES
  *	  Every node type that can appear in stored rules' parsetrees *must*
@@ -332,6 +332,16 @@ _outAppend(StringInfo str, Append *node)
 }
 
 static void
+_outRecursiveUnion(StringInfo str, RecursiveUnion *node)
+{
+	WRITE_NODE_TYPE("RECURSIVEUNION");
+
+	_outPlanInfo(str, (Plan *) node);
+
+	WRITE_INT_FIELD(wtParam);
+}
+
+static void
 _outBitmapAnd(StringInfo str, BitmapAnd *node)
 {
 	WRITE_NODE_TYPE("BITMAPAND");
@@ -447,6 +457,27 @@ _outValuesScan(StringInfo str, ValuesScan *node)
 }
 
 static void
+_outCteScan(StringInfo str, CteScan *node)
+{
+	WRITE_NODE_TYPE("CTESCAN");
+
+	_outScanInfo(str, (Scan *) node);
+
+	WRITE_INT_FIELD(ctePlanId);
+	WRITE_INT_FIELD(cteParam);
+}
+
+static void
+_outWorkTableScan(StringInfo str, WorkTableScan *node)
+{
+	WRITE_NODE_TYPE("WORKTABLESCAN");
+
+	_outScanInfo(str, (Scan *) node);
+
+	WRITE_INT_FIELD(wtParam);
+}
+
+static void
 _outJoin(StringInfo str, Join *node)
 {
 	WRITE_NODE_TYPE("JOIN");
@@ -1382,6 +1413,7 @@ _outPlannerInfo(StringInfo str, PlannerInfo *node)
 	WRITE_NODE_FIELD(resultRelations);
 	WRITE_NODE_FIELD(returningLists);
 	WRITE_NODE_FIELD(init_plans);
+	WRITE_NODE_FIELD(cte_plan_ids);
 	WRITE_NODE_FIELD(eq_classes);
 	WRITE_NODE_FIELD(canon_pathkeys);
 	WRITE_NODE_FIELD(left_join_clauses);
@@ -1398,6 +1430,8 @@ _outPlannerInfo(StringInfo str, PlannerInfo *node)
 	WRITE_BOOL_FIELD(hasJoinRTEs);
 	WRITE_BOOL_FIELD(hasHavingQual);
 	WRITE_BOOL_FIELD(hasPseudoConstantQuals);
+	WRITE_BOOL_FIELD(hasRecursion);
+	WRITE_INT_FIELD(wt_param_id);
 }
 
 static void
@@ -1648,6 +1682,7 @@ _outSelectStmt(StringInfo str, SelectStmt *node)
 	WRITE_NODE_FIELD(whereClause);
 	WRITE_NODE_FIELD(groupClause);
 	WRITE_NODE_FIELD(havingClause);
+	WRITE_NODE_FIELD(withClause);
 	WRITE_NODE_FIELD(valuesLists);
 	WRITE_NODE_FIELD(sortClause);
 	WRITE_NODE_FIELD(limitOffset);
@@ -1793,6 +1828,8 @@ _outQuery(StringInfo str, Query *node)
 	WRITE_BOOL_FIELD(hasAggs);
 	WRITE_BOOL_FIELD(hasSubLinks);
 	WRITE_BOOL_FIELD(hasDistinctOn);
+	WRITE_BOOL_FIELD(hasRecursive);
+	WRITE_NODE_FIELD(cteList);
 	WRITE_NODE_FIELD(rtable);
 	WRITE_NODE_FIELD(jointree);
 	WRITE_NODE_FIELD(targetList);
@@ -1829,6 +1866,32 @@ _outRowMarkClause(StringInfo str, RowMarkClause *node)
 }
 
 static void
+_outWithClause(StringInfo str, WithClause *node)
+{
+	WRITE_NODE_TYPE("WITHCLAUSE");
+
+	WRITE_NODE_FIELD(ctes);
+	WRITE_BOOL_FIELD(recursive);
+	WRITE_LOCATION_FIELD(location);
+}
+
+static void
+_outCommonTableExpr(StringInfo str, CommonTableExpr *node)
+{
+	WRITE_NODE_TYPE("COMMONTABLEEXPR");
+
+	WRITE_STRING_FIELD(ctename);
+	WRITE_NODE_FIELD(aliascolnames);
+	WRITE_NODE_FIELD(ctequery);
+	WRITE_LOCATION_FIELD(location);
+	WRITE_BOOL_FIELD(cterecursive);
+	WRITE_INT_FIELD(cterefcount);
+	WRITE_NODE_FIELD(ctecolnames);
+	WRITE_NODE_FIELD(ctecoltypes);
+	WRITE_NODE_FIELD(ctecoltypmods);
+}
+
+static void
 _outSetOperationStmt(StringInfo str, SetOperationStmt *node)
 {
 	WRITE_NODE_TYPE("SETOPERATIONSTMT");
@@ -1861,6 +1924,10 @@ _outRangeTblEntry(StringInfo str, RangeTblEntry *node)
 		case RTE_SUBQUERY:
 			WRITE_NODE_FIELD(subquery);
 			break;
+		case RTE_JOIN:
+			WRITE_ENUM_FIELD(jointype, JoinType);
+			WRITE_NODE_FIELD(joinaliasvars);
+			break;
 		case RTE_FUNCTION:
 			WRITE_NODE_FIELD(funcexpr);
 			WRITE_NODE_FIELD(funccoltypes);
@@ -1869,9 +1936,12 @@ _outRangeTblEntry(StringInfo str, RangeTblEntry *node)
 		case RTE_VALUES:
 			WRITE_NODE_FIELD(values_lists);
 			break;
-		case RTE_JOIN:
-			WRITE_ENUM_FIELD(jointype, JoinType);
-			WRITE_NODE_FIELD(joinaliasvars);
+		case RTE_CTE:
+			WRITE_STRING_FIELD(ctename);
+			WRITE_UINT_FIELD(ctelevelsup);
+			WRITE_BOOL_FIELD(self_reference);
+			WRITE_NODE_FIELD(ctecoltypes);
+			WRITE_NODE_FIELD(ctecoltypmods);
 			break;
 		default:
 			elog(ERROR, "unrecognized RTE kind: %d", (int) node->rtekind);
@@ -2060,6 +2130,25 @@ _outSortBy(StringInfo str, SortBy *node)
 }
 
 static void
+_outRangeSubselect(StringInfo str, RangeSubselect *node)
+{
+	WRITE_NODE_TYPE("RANGESUBSELECT");
+
+	WRITE_NODE_FIELD(subquery);
+	WRITE_NODE_FIELD(alias);
+}
+
+static void
+_outRangeFunction(StringInfo str, RangeFunction *node)
+{
+	WRITE_NODE_TYPE("RANGEFUNCTION");
+
+	WRITE_NODE_FIELD(funccallnode);
+	WRITE_NODE_FIELD(alias);
+	WRITE_NODE_FIELD(coldeflist);
+}
+
+static void
 _outConstraint(StringInfo str, Constraint *node)
 {
 	WRITE_NODE_TYPE("CONSTRAINT");
@@ -2159,6 +2248,9 @@ _outNode(StringInfo str, void *obj)
 			case T_Append:
 				_outAppend(str, obj);
 				break;
+			case T_RecursiveUnion:
+				_outRecursiveUnion(str, obj);
+				break;
 			case T_BitmapAnd:
 				_outBitmapAnd(str, obj);
 				break;
@@ -2192,6 +2284,12 @@ _outNode(StringInfo str, void *obj)
 			case T_ValuesScan:
 				_outValuesScan(str, obj);
 				break;
+			case T_CteScan:
+				_outCteScan(str, obj);
+				break;
+			case T_WorkTableScan:
+				_outWorkTableScan(str, obj);
+				break;
 			case T_Join:
 				_outJoin(str, obj);
 				break;
@@ -2473,6 +2571,12 @@ _outNode(StringInfo str, void *obj)
 			case T_RowMarkClause:
 				_outRowMarkClause(str, obj);
 				break;
+			case T_WithClause:
+				_outWithClause(str, obj);
+				break;
+			case T_CommonTableExpr:
+				_outCommonTableExpr(str, obj);
+				break;
 			case T_SetOperationStmt:
 				_outSetOperationStmt(str, obj);
 				break;
@@ -2509,6 +2613,12 @@ _outNode(StringInfo str, void *obj)
 			case T_SortBy:
 				_outSortBy(str, obj);
 				break;
+			case T_RangeSubselect:
+				_outRangeSubselect(str, obj);
+				break;
+			case T_RangeFunction:
+				_outRangeFunction(str, obj);
+				break;
 			case T_Constraint:
 				_outConstraint(str, obj);
 				break;
diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c
index 58a7495d37e..3338e1b8302 100644
--- a/src/backend/nodes/print.c
+++ b/src/backend/nodes/print.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/nodes/print.c,v 1.89 2008/06/19 00:46:04 alvherre Exp $
+ *	  $PostgreSQL: pgsql/src/backend/nodes/print.c,v 1.90 2008/10/04 21:56:53 tgl Exp $
  *
  * HISTORY
  *	  AUTHOR			DATE			MAJOR EVENT
@@ -272,6 +272,14 @@ print_rt(List *rtable)
 				printf("%d\t%s\t[subquery]",
 					   i, rte->eref->aliasname);
 				break;
+			case RTE_JOIN:
+				printf("%d\t%s\t[join]",
+					   i, rte->eref->aliasname);
+				break;
+			case RTE_SPECIAL:
+				printf("%d\t%s\t[special]",
+					   i, rte->eref->aliasname);
+				break;
 			case RTE_FUNCTION:
 				printf("%d\t%s\t[rangefunction]",
 					   i, rte->eref->aliasname);
@@ -280,12 +288,8 @@ print_rt(List *rtable)
 				printf("%d\t%s\t[values list]",
 					   i, rte->eref->aliasname);
 				break;
-			case RTE_JOIN:
-				printf("%d\t%s\t[join]",
-					   i, rte->eref->aliasname);
-				break;
-			case RTE_SPECIAL:
-				printf("%d\t%s\t[special]",
+			case RTE_CTE:
+				printf("%d\t%s\t[cte]",
 					   i, rte->eref->aliasname);
 				break;
 			default:
diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c
index 1eca85d0b60..3f7ce455df2 100644
--- a/src/backend/nodes/readfuncs.c
+++ b/src/backend/nodes/readfuncs.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/nodes/readfuncs.c,v 1.214 2008/09/01 20:42:44 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/nodes/readfuncs.c,v 1.215 2008/10/04 21:56:53 tgl Exp $
  *
  * NOTES
  *	  Path and Plan nodes do not have any readfuncs support, because we
@@ -155,6 +155,8 @@ _readQuery(void)
 	READ_BOOL_FIELD(hasAggs);
 	READ_BOOL_FIELD(hasSubLinks);
 	READ_BOOL_FIELD(hasDistinctOn);
+	READ_BOOL_FIELD(hasRecursive);
+	READ_NODE_FIELD(cteList);
 	READ_NODE_FIELD(rtable);
 	READ_NODE_FIELD(jointree);
 	READ_NODE_FIELD(targetList);
@@ -231,6 +233,27 @@ _readRowMarkClause(void)
 }
 
 /*
+ * _readCommonTableExpr
+ */
+static CommonTableExpr *
+_readCommonTableExpr(void)
+{
+	READ_LOCALS(CommonTableExpr);
+
+	READ_STRING_FIELD(ctename);
+	READ_NODE_FIELD(aliascolnames);
+	READ_NODE_FIELD(ctequery);
+	READ_LOCATION_FIELD(location);
+	READ_BOOL_FIELD(cterecursive);
+	READ_INT_FIELD(cterefcount);
+	READ_NODE_FIELD(ctecolnames);
+	READ_NODE_FIELD(ctecoltypes);
+	READ_NODE_FIELD(ctecoltypmods);
+
+	READ_DONE();
+}
+
+/*
  * _readSetOperationStmt
  */
 static SetOperationStmt *
@@ -1007,6 +1030,10 @@ _readRangeTblEntry(void)
 		case RTE_SUBQUERY:
 			READ_NODE_FIELD(subquery);
 			break;
+		case RTE_JOIN:
+			READ_ENUM_FIELD(jointype, JoinType);
+			READ_NODE_FIELD(joinaliasvars);
+			break;
 		case RTE_FUNCTION:
 			READ_NODE_FIELD(funcexpr);
 			READ_NODE_FIELD(funccoltypes);
@@ -1015,9 +1042,12 @@ _readRangeTblEntry(void)
 		case RTE_VALUES:
 			READ_NODE_FIELD(values_lists);
 			break;
-		case RTE_JOIN:
-			READ_ENUM_FIELD(jointype, JoinType);
-			READ_NODE_FIELD(joinaliasvars);
+		case RTE_CTE:
+			READ_STRING_FIELD(ctename);
+			READ_UINT_FIELD(ctelevelsup);
+			READ_BOOL_FIELD(self_reference);
+			READ_NODE_FIELD(ctecoltypes);
+			READ_NODE_FIELD(ctecoltypmods);
 			break;
 		default:
 			elog(ERROR, "unrecognized RTE kind: %d",
@@ -1060,6 +1090,8 @@ parseNodeString(void)
 		return_value = _readSortGroupClause();
 	else if (MATCH("ROWMARKCLAUSE", 13))
 		return_value = _readRowMarkClause();
+	else if (MATCH("COMMONTABLEEXPR", 15))
+		return_value = _readCommonTableExpr();
 	else if (MATCH("SETOPERATIONSTMT", 16))
 		return_value = _readSetOperationStmt();
 	else if (MATCH("ALIAS", 5))