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

3 files changed, 204 insertions, 14 deletions

diff --git a/src/backend/utils/adt/ruleutils.c b/src/backend/utils/adt/ruleutils.c
index 71fea45ddd0..fd21152b495 100644
--- a/src/backend/utils/adt/ruleutils.c
+++ b/src/backend/utils/adt/ruleutils.c
@@ -9,7 +9,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/utils/adt/ruleutils.c,v 1.284 2008/09/06 20:18:08 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/utils/adt/ruleutils.c,v 1.285 2008/10/04 21:56:54 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -145,6 +145,7 @@ static void make_viewdef(StringInfo buf, HeapTuple ruletup, TupleDesc rulettc,
 static void get_query_def(Query *query, StringInfo buf, List *parentnamespace,
 			  TupleDesc resultDesc, int prettyFlags, int startIndent);
 static void get_values_def(List *values_lists, deparse_context *context);
+static void get_with_clause(Query *query, deparse_context *context);
 static void get_select_query_def(Query *query, deparse_context *context,
 					 TupleDesc resultDesc);
 static void get_insert_query_def(Query *query, deparse_context *context);
@@ -2205,6 +2206,73 @@ get_values_def(List *values_lists, deparse_context *context)
 }
 
 /* ----------
+ * get_with_clause			- Parse back a WITH clause
+ * ----------
+ */
+static void
+get_with_clause(Query *query, deparse_context *context)
+{
+	StringInfo	buf = context->buf;
+	const char	*sep;
+	ListCell	*l;
+
+	if (query->cteList == NIL)
+		return;
+
+	if (PRETTY_INDENT(context))
+	{
+		context->indentLevel += PRETTYINDENT_STD;
+		appendStringInfoChar(buf, ' ');
+	}
+
+	if (query->hasRecursive)
+		sep = "WITH RECURSIVE ";
+	else
+		sep = "WITH ";
+	foreach(l, query->cteList)
+	{
+		CommonTableExpr *cte = (CommonTableExpr *) lfirst(l);
+
+		appendStringInfoString(buf, sep);
+		appendStringInfoString(buf, quote_identifier(cte->ctename));
+		if (cte->aliascolnames)
+		{
+			bool		first = true;
+			ListCell   *col;
+
+			appendStringInfoChar(buf, '(');
+			foreach(col, cte->aliascolnames)
+			{
+				if (first)
+					first = false;
+				else
+					appendStringInfoString(buf, ", ");
+				appendStringInfoString(buf,
+									   quote_identifier(strVal(lfirst(col))));
+			}
+			appendStringInfoChar(buf, ')');
+		}
+		appendStringInfoString(buf, " AS (");
+		if (PRETTY_INDENT(context))
+			appendContextKeyword(context, "", 0, 0, 0);
+		get_query_def((Query *) cte->ctequery, buf, context->namespaces, NULL,
+					  context->prettyFlags, context->indentLevel);
+		if (PRETTY_INDENT(context))
+			appendContextKeyword(context, "", 0, 0, 0);
+		appendStringInfoChar(buf, ')');
+		sep = ", ";
+	}
+
+	if (PRETTY_INDENT(context))
+	{
+		context->indentLevel -= PRETTYINDENT_STD;
+		appendContextKeyword(context, "", 0, 0, 0);
+	}
+	else
+		appendStringInfoChar(buf, ' ');
+}
+
+/* ----------
  * get_select_query_def			- Parse back a SELECT parsetree
  * ----------
  */
@@ -2214,13 +2282,16 @@ get_select_query_def(Query *query, deparse_context *context,
 {
 	StringInfo	buf = context->buf;
 	bool		force_colno;
-	char	   *sep;
+	const char *sep;
 	ListCell   *l;
 
+	/* Insert the WITH clause if given */
+	get_with_clause(query, context);
+
 	/*
 	 * If the Query node has a setOperations tree, then it's the top level of
-	 * a UNION/INTERSECT/EXCEPT query; only the ORDER BY and LIMIT fields are
-	 * interesting in the top query itself.
+	 * a UNION/INTERSECT/EXCEPT query; only the WITH, ORDER BY and LIMIT
+	 * fields are interesting in the top query itself.
 	 */
 	if (query->setOperations)
 	{
@@ -2507,8 +2578,9 @@ get_setop_query(Node *setOp, Query *query, deparse_context *context,
 
 		Assert(subquery != NULL);
 		Assert(subquery->setOperations == NULL);
-		/* Need parens if ORDER BY, FOR UPDATE, or LIMIT; see gram.y */
-		need_paren = (subquery->sortClause ||
+		/* Need parens if WITH, ORDER BY, FOR UPDATE, or LIMIT; see gram.y */
+		need_paren = (subquery->cteList ||
+					  subquery->sortClause ||
 					  subquery->rowMarks ||
 					  subquery->limitOffset ||
 					  subquery->limitCount);
@@ -2523,6 +2595,12 @@ get_setop_query(Node *setOp, Query *query, deparse_context *context,
 	{
 		SetOperationStmt *op = (SetOperationStmt *) setOp;
 
+		if (PRETTY_INDENT(context))
+		{
+			context->indentLevel += PRETTYINDENT_STD;
+			appendStringInfoSpaces(buf, PRETTYINDENT_STD);
+		}
+
 		/*
 		 * We force parens whenever nesting two SetOperationStmts. There are
 		 * some cases in which parens are needed around a leaf query too, but
@@ -2570,6 +2648,9 @@ get_setop_query(Node *setOp, Query *query, deparse_context *context,
 		get_setop_query(op->rarg, query, context, resultDesc);
 		if (need_paren)
 			appendStringInfoChar(buf, ')');
+
+		if (PRETTY_INDENT(context))
+			context->indentLevel -= PRETTYINDENT_STD;
 	}
 	else
 	{
@@ -2730,11 +2811,15 @@ get_insert_query_def(Query *query, deparse_context *context)
 	}
 	else if (values_rte)
 	{
+		/* A WITH clause is possible here */
+		get_with_clause(query, context);
 		/* Add the multi-VALUES expression lists */
 		get_values_def(values_rte->values_lists, context);
 	}
 	else
 	{
+		/* A WITH clause is possible here */
+		get_with_clause(query, context);
 		/* Add the single-VALUES expression list */
 		appendContextKeyword(context, "VALUES (",
 							 -PRETTYINDENT_STD, PRETTYINDENT_STD, 2);
@@ -3360,6 +3445,13 @@ get_name_for_var_field(Var *var, int fieldno,
 			 * its result columns as RECORD, which is not allowed.
 			 */
 			break;
+		case RTE_CTE:
+			/*
+			 * XXX not implemented yet, we need more infrastructure in
+			 * deparse_namespace and explain.c.
+			 */
+			elog(ERROR, "deparsing field references to whole-row vars from WITH queries not implemented yet");
+			break;
 	}
 
 	/*
@@ -5029,6 +5121,7 @@ get_sublink_expr(SubLink *sublink, deparse_context *context)
 			need_paren = false;
 			break;
 
+		case CTE_SUBLINK:		/* shouldn't occur in a SubLink */
 		default:
 			elog(ERROR, "unrecognized sublink type: %d",
 				 (int) sublink->subLinkType);
@@ -5130,6 +5223,9 @@ get_from_clause_item(Node *jtnode, Query *query, deparse_context *context)
 				/* Values list RTE */
 				get_values_def(rte->values_lists, context);
 				break;
+			case RTE_CTE:
+				appendStringInfoString(buf, quote_identifier(rte->ctename));
+				break;
 			default:
 				elog(ERROR, "unrecognized RTE kind: %d", (int) rte->rtekind);
 				break;
diff --git a/src/backend/utils/cache/plancache.c b/src/backend/utils/cache/plancache.c
index 48addf3f539..fd535c0090d 100644
--- a/src/backend/utils/cache/plancache.c
+++ b/src/backend/utils/cache/plancache.c
@@ -35,7 +35,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/utils/cache/plancache.c,v 1.22 2008/09/15 23:37:39 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/utils/cache/plancache.c,v 1.23 2008/10/04 21:56:54 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -728,15 +728,23 @@ ScanQueryForLocks(Query *parsetree, bool acquire)
 		}
 	}
 
+	/* Recurse into subquery-in-WITH */
+	foreach(lc, parsetree->cteList)
+	{
+		CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
+
+		ScanQueryForLocks((Query *) cte->ctequery, acquire);
+	}
+
 	/*
 	 * Recurse into sublink subqueries, too.  But we already did the ones in
-	 * the rtable.
+	 * the rtable and cteList.
 	 */
 	if (parsetree->hasSubLinks)
 	{
 		query_tree_walker(parsetree, ScanQueryWalker,
 						  (void *) &acquire,
-						  QTW_IGNORE_RT_SUBQUERIES);
+						  QTW_IGNORE_RC_SUBQUERIES);
 	}
 }
 
diff --git a/src/backend/utils/sort/tuplestore.c b/src/backend/utils/sort/tuplestore.c
index 3b53ad28a5e..e127de34e52 100644
--- a/src/backend/utils/sort/tuplestore.c
+++ b/src/backend/utils/sort/tuplestore.c
@@ -46,7 +46,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/utils/sort/tuplestore.c,v 1.40 2008/10/01 19:51:49 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/utils/sort/tuplestore.c,v 1.41 2008/10/04 21:56:54 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -86,7 +86,7 @@ typedef enum
 typedef struct
 {
 	int			eflags;			/* capability flags */
-	bool		eof_reached;	/* read reached EOF */
+	bool		eof_reached;	/* read has reached EOF */
 	int			current;		/* next array index to read */
 	int			file;			/* temp file# */
 	off_t		offset;			/* byte offset in file */
@@ -374,6 +374,39 @@ tuplestore_alloc_read_pointer(Tuplestorestate *state, int eflags)
 }
 
 /*
+ * tuplestore_clear
+ *
+ *	Delete all the contents of a tuplestore, and reset its read pointers
+ *	to the start.
+ */
+void
+tuplestore_clear(Tuplestorestate *state)
+{
+	int			i;
+	TSReadPointer *readptr;
+
+	if (state->myfile)
+		BufFileClose(state->myfile);
+	state->myfile = NULL;
+	if (state->memtuples)
+	{
+		for (i = 0; i < state->memtupcount; i++)
+		{
+			FREEMEM(state, GetMemoryChunkSpace(state->memtuples[i]));
+			pfree(state->memtuples[i]);
+		}
+	}
+	state->status = TSS_INMEM;
+	state->memtupcount = 0;
+	readptr = state->readptrs;
+	for (i = 0; i < state->readptrcount; readptr++, i++)
+	{
+		readptr->eof_reached = false;
+		readptr->current = 0;
+	}
+}
+
+/*
  * tuplestore_end
  *
  *	Release resources and clean up.
@@ -463,9 +496,13 @@ tuplestore_ateof(Tuplestorestate *state)
  *
  * Note that the input tuple is always copied; the caller need not save it.
  *
- * Any read pointer that is currently "AT EOF" remains so (the read pointer
- * implicitly advances along with the write pointer); otherwise the read
- * pointer is unchanged.  This is for the convenience of nodeMaterial.c.
+ * If the active read pointer is currently "at EOF", it remains so (the read
+ * pointer implicitly advances along with the write pointer); otherwise the
+ * read pointer is unchanged.  Non-active read pointers do not move, which
+ * means they are certain to not be "at EOF" immediately after puttuple.
+ * This curious-seeming behavior is for the convenience of nodeMaterial.c and
+ * nodeCtescan.c, which would otherwise need to do extra pointer repositioning
+ * steps.
  *
  * tuplestore_puttupleslot() is a convenience routine to collect data from
  * a TupleTableSlot without an extra copy operation.
@@ -519,11 +556,27 @@ tuplestore_putvalues(Tuplestorestate *state, TupleDesc tdesc,
 static void
 tuplestore_puttuple_common(Tuplestorestate *state, void *tuple)
 {
+	TSReadPointer *readptr;
+	int			i;
+
 	switch (state->status)
 	{
 		case TSS_INMEM:
 
 			/*
+			 * Update read pointers as needed; see API spec above.
+			 */
+			readptr = state->readptrs;
+			for (i = 0; i < state->readptrcount; readptr++, i++)
+			{
+				if (readptr->eof_reached && i != state->activeptr)
+				{
+					readptr->eof_reached = false;
+					readptr->current = state->memtupcount;
+				}
+			}
+
+			/*
 			 * Grow the array as needed.  Note that we try to grow the array
 			 * when there is still one free slot remaining --- if we fail,
 			 * there'll still be room to store the incoming tuple, and then
@@ -572,6 +625,24 @@ tuplestore_puttuple_common(Tuplestorestate *state, void *tuple)
 			dumptuples(state);
 			break;
 		case TSS_WRITEFILE:
+
+			/*
+			 * Update read pointers as needed; see API spec above.
+			 * Note: BufFileTell is quite cheap, so not worth trying
+			 * to avoid multiple calls.
+			 */
+			readptr = state->readptrs;
+			for (i = 0; i < state->readptrcount; readptr++, i++)
+			{
+				if (readptr->eof_reached && i != state->activeptr)
+				{
+					readptr->eof_reached = false;
+					BufFileTell(state->myfile,
+								&readptr->file,
+								&readptr->offset);
+				}
+			}
+
 			WRITETUP(state, tuple);
 			break;
 		case TSS_READFILE:
@@ -588,6 +659,21 @@ tuplestore_puttuple_common(Tuplestorestate *state, void *tuple)
 							SEEK_SET) != 0)
 				elog(ERROR, "tuplestore seek to EOF failed");
 			state->status = TSS_WRITEFILE;
+
+			/*
+			 * Update read pointers as needed; see API spec above.
+			 */
+			readptr = state->readptrs;
+			for (i = 0; i < state->readptrcount; readptr++, i++)
+			{
+				if (readptr->eof_reached && i != state->activeptr)
+				{
+					readptr->eof_reached = false;
+					readptr->file = state->writepos_file;
+					readptr->offset = state->writepos_offset;
+				}
+			}
+
 			WRITETUP(state, tuple);
 			break;
 		default: