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

7 files changed, 861 insertions, 24 deletions

diff --git a/src/backend/executor/Makefile b/src/backend/executor/Makefile
index 38364a9cd13..b4a0492751c 100644
--- a/src/backend/executor/Makefile
+++ b/src/backend/executor/Makefile
@@ -4,7 +4,7 @@
 #    Makefile for executor
 #
 # IDENTIFICATION
-#    $PostgreSQL: pgsql/src/backend/executor/Makefile,v 1.27 2008/02/19 10:30:07 petere Exp $
+#    $PostgreSQL: pgsql/src/backend/executor/Makefile,v 1.28 2008/10/04 21:56:52 tgl Exp $
 #
 #-------------------------------------------------------------------------
 
@@ -18,9 +18,10 @@ OBJS = execAmi.o execCurrent.o execGrouping.o execJunk.o execMain.o \
        nodeBitmapAnd.o nodeBitmapOr.o \
        nodeBitmapHeapscan.o nodeBitmapIndexscan.o nodeHash.o \
        nodeHashjoin.o nodeIndexscan.o nodeMaterial.o nodeMergejoin.o \
-       nodeNestloop.o nodeFunctionscan.o nodeResult.o nodeSeqscan.o \
-       nodeSetOp.o nodeSort.o nodeUnique.o \
-       nodeValuesscan.o nodeLimit.o nodeGroup.o \
-       nodeSubplan.o nodeSubqueryscan.o nodeTidscan.o tstoreReceiver.o spi.o
+       nodeNestloop.o nodeFunctionscan.o nodeRecursiveunion.o nodeResult.o \
+       nodeSeqscan.o nodeSetOp.o nodeSort.o nodeUnique.o \
+       nodeValuesscan.o nodeCtescan.o nodeWorktablescan.o \
+       nodeLimit.o nodeGroup.o nodeSubplan.o nodeSubqueryscan.o nodeTidscan.o \
+       tstoreReceiver.o spi.o
 
 include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/executor/execAmi.c b/src/backend/executor/execAmi.c
index afddf4d3920..1de3f5a778e 100644
--- a/src/backend/executor/execAmi.c
+++ b/src/backend/executor/execAmi.c
@@ -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/backend/executor/execAmi.c,v 1.98 2008/10/01 19:51:49 tgl Exp $
+ *	$PostgreSQL: pgsql/src/backend/executor/execAmi.c,v 1.99 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -30,6 +30,7 @@
 #include "executor/nodeMaterial.h"
 #include "executor/nodeMergejoin.h"
 #include "executor/nodeNestloop.h"
+#include "executor/nodeRecursiveunion.h"
 #include "executor/nodeResult.h"
 #include "executor/nodeSeqscan.h"
 #include "executor/nodeSetOp.h"
@@ -39,6 +40,8 @@
 #include "executor/nodeTidscan.h"
 #include "executor/nodeUnique.h"
 #include "executor/nodeValuesscan.h"
+#include "executor/nodeCtescan.h"
+#include "executor/nodeWorktablescan.h"
 
 
 /*
@@ -121,6 +124,10 @@ ExecReScan(PlanState *node, ExprContext *exprCtxt)
 			ExecReScanAppend((AppendState *) node, exprCtxt);
 			break;
 
+		case T_RecursiveUnionState:
+			ExecRecursiveUnionReScan((RecursiveUnionState *) node, exprCtxt);
+			break;
+
 		case T_BitmapAndState:
 			ExecReScanBitmapAnd((BitmapAndState *) node, exprCtxt);
 			break;
@@ -161,6 +168,14 @@ ExecReScan(PlanState *node, ExprContext *exprCtxt)
 			ExecValuesReScan((ValuesScanState *) node, exprCtxt);
 			break;
 
+		case T_CteScanState:
+			ExecCteScanReScan((CteScanState *) node, exprCtxt);
+			break;
+
+		case T_WorkTableScanState:
+			ExecWorkTableScanReScan((WorkTableScanState *) node, exprCtxt);
+			break;
+
 		case T_NestLoopState:
 			ExecReScanNestLoop((NestLoopState *) node, exprCtxt);
 			break;
@@ -396,6 +411,8 @@ ExecSupportsBackwardScan(Plan *node)
 		case T_TidScan:
 		case T_FunctionScan:
 		case T_ValuesScan:
+		case T_CteScan:
+		case T_WorkTableScan:
 			return true;
 
 		case T_SubqueryScan:
diff --git a/src/backend/executor/execProcnode.c b/src/backend/executor/execProcnode.c
index 385c415974b..e689ec00f8c 100644
--- a/src/backend/executor/execProcnode.c
+++ b/src/backend/executor/execProcnode.c
@@ -12,7 +12,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/executor/execProcnode.c,v 1.62 2008/01/01 19:45:49 momjian Exp $
+ *	  $PostgreSQL: pgsql/src/backend/executor/execProcnode.c,v 1.63 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -94,6 +94,7 @@
 #include "executor/nodeMaterial.h"
 #include "executor/nodeMergejoin.h"
 #include "executor/nodeNestloop.h"
+#include "executor/nodeRecursiveunion.h"
 #include "executor/nodeResult.h"
 #include "executor/nodeSeqscan.h"
 #include "executor/nodeSetOp.h"
@@ -103,8 +104,11 @@
 #include "executor/nodeTidscan.h"
 #include "executor/nodeUnique.h"
 #include "executor/nodeValuesscan.h"
+#include "executor/nodeCtescan.h"
+#include "executor/nodeWorktablescan.h"
 #include "miscadmin.h"
 
+
 /* ------------------------------------------------------------------------
  *		ExecInitNode
  *
@@ -147,6 +151,11 @@ ExecInitNode(Plan *node, EState *estate, int eflags)
 												  estate, eflags);
 			break;
 
+		case T_RecursiveUnion:
+			result = (PlanState *) ExecInitRecursiveUnion((RecursiveUnion *) node,
+														  estate, eflags);
+			break;
+
 		case T_BitmapAnd:
 			result = (PlanState *) ExecInitBitmapAnd((BitmapAnd *) node,
 													 estate, eflags);
@@ -200,6 +209,16 @@ ExecInitNode(Plan *node, EState *estate, int eflags)
 													  estate, eflags);
 			break;
 
+		case T_CteScan:
+			result = (PlanState *) ExecInitCteScan((CteScan *) node,
+												   estate, eflags);
+			break;
+
+		case T_WorkTableScan:
+			result = (PlanState *) ExecInitWorkTableScan((WorkTableScan *) node,
+														 estate, eflags);
+			break;
+
 			/*
 			 * join nodes
 			 */
@@ -323,6 +342,10 @@ ExecProcNode(PlanState *node)
 			result = ExecAppend((AppendState *) node);
 			break;
 
+		case T_RecursiveUnionState:
+			result = ExecRecursiveUnion((RecursiveUnionState *) node);
+			break;
+
 			/* BitmapAndState does not yield tuples */
 
 			/* BitmapOrState does not yield tuples */
@@ -360,6 +383,14 @@ ExecProcNode(PlanState *node)
 			result = ExecValuesScan((ValuesScanState *) node);
 			break;
 
+		case T_CteScanState:
+			result = ExecCteScan((CteScanState *) node);
+			break;
+
+		case T_WorkTableScanState:
+			result = ExecWorkTableScan((WorkTableScanState *) node);
+			break;
+
 			/*
 			 * join nodes
 			 */
@@ -501,6 +532,9 @@ ExecCountSlotsNode(Plan *node)
 		case T_Append:
 			return ExecCountSlotsAppend((Append *) node);
 
+		case T_RecursiveUnion:
+			return ExecCountSlotsRecursiveUnion((RecursiveUnion *) node);
+
 		case T_BitmapAnd:
 			return ExecCountSlotsBitmapAnd((BitmapAnd *) node);
 
@@ -534,6 +568,12 @@ ExecCountSlotsNode(Plan *node)
 		case T_ValuesScan:
 			return ExecCountSlotsValuesScan((ValuesScan *) node);
 
+		case T_CteScan:
+			return ExecCountSlotsCteScan((CteScan *) node);
+
+		case T_WorkTableScan:
+			return ExecCountSlotsWorkTableScan((WorkTableScan *) node);
+
 			/*
 			 * join nodes
 			 */
@@ -620,6 +660,10 @@ ExecEndNode(PlanState *node)
 			ExecEndAppend((AppendState *) node);
 			break;
 
+		case T_RecursiveUnionState:
+			ExecEndRecursiveUnion((RecursiveUnionState *) node);
+			break;
+
 		case T_BitmapAndState:
 			ExecEndBitmapAnd((BitmapAndState *) node);
 			break;
@@ -663,6 +707,14 @@ ExecEndNode(PlanState *node)
 			ExecEndValuesScan((ValuesScanState *) node);
 			break;
 
+		case T_CteScanState:
+			ExecEndCteScan((CteScanState *) node);
+			break;
+
+		case T_WorkTableScanState:
+			ExecEndWorkTableScan((WorkTableScanState *) node);
+			break;
+
 			/*
 			 * join nodes
 			 */
diff --git a/src/backend/executor/nodeCtescan.c b/src/backend/executor/nodeCtescan.c
new file mode 100644
index 00000000000..b4ae27df385
--- /dev/null
+++ b/src/backend/executor/nodeCtescan.c
@@ -0,0 +1,335 @@
+/*-------------------------------------------------------------------------
+ *
+ * nodeCtescan.c
+ *	  routines to handle CteScan nodes.
+ *
+ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *	  $PostgreSQL: pgsql/src/backend/executor/nodeCtescan.c,v 1.1 2008/10/04 21:56:53 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include "executor/execdebug.h"
+#include "executor/nodeCtescan.h"
+#include "miscadmin.h"
+
+static TupleTableSlot *CteScanNext(CteScanState *node);
+
+/* ----------------------------------------------------------------
+ *		CteScanNext
+ *
+ *		This is a workhorse for ExecCteScan
+ * ----------------------------------------------------------------
+ */
+static TupleTableSlot *
+CteScanNext(CteScanState *node)
+{
+	EState	   *estate;
+	ScanDirection dir;
+	bool		forward;
+	Tuplestorestate *tuplestorestate;
+	bool		eof_tuplestore;
+	TupleTableSlot *slot;
+
+	/*
+	 * get state info from node
+	 */
+	estate = node->ss.ps.state;
+	dir = estate->es_direction;
+	forward = ScanDirectionIsForward(dir);
+	tuplestorestate = node->leader->cte_table;
+	tuplestore_select_read_pointer(tuplestorestate, node->readptr);
+	slot = node->ss.ss_ScanTupleSlot;
+
+	/*
+	 * If we are not at the end of the tuplestore, or are going backwards, try
+	 * to fetch a tuple from tuplestore.
+	 */
+	eof_tuplestore = tuplestore_ateof(tuplestorestate);
+
+	if (!forward && eof_tuplestore)
+	{
+		if (!node->leader->eof_cte)
+		{
+			/*
+			 * When reversing direction at tuplestore EOF, the first
+			 * gettupleslot call will fetch the last-added tuple; but we want
+			 * to return the one before that, if possible. So do an extra
+			 * fetch.
+			 */
+			if (!tuplestore_advance(tuplestorestate, forward))
+				return NULL;	/* the tuplestore must be empty */
+		}
+		eof_tuplestore = false;
+	}
+
+	/*
+	 * If we can fetch another tuple from the tuplestore, return it.
+	 */
+	if (!eof_tuplestore)
+	{
+		if (tuplestore_gettupleslot(tuplestorestate, forward, slot))
+			return slot;
+		if (forward)
+			eof_tuplestore = true;
+	}
+
+	/*
+	 * If necessary, try to fetch another row from the CTE query.
+	 *
+	 * Note: the eof_cte state variable exists to short-circuit further calls
+	 * of the CTE plan.  It's not optional, unfortunately, because some plan
+	 * node types are not robust about being called again when they've already
+	 * returned NULL.
+	 */
+	if (eof_tuplestore && !node->leader->eof_cte)
+	{
+		TupleTableSlot *cteslot;
+
+		/*
+		 * We can only get here with forward==true, so no need to worry about
+		 * which direction the subplan will go.
+		 */
+		cteslot = ExecProcNode(node->cteplanstate);
+		if (TupIsNull(cteslot))
+		{
+			node->leader->eof_cte = true;
+			return NULL;
+		}
+
+		/*
+		 * Append a copy of the returned tuple to tuplestore.  NOTE: because
+		 * our read pointer is certainly in EOF state, its read position will
+		 * move forward over the added tuple.  This is what we want.  Also,
+		 * any other readers will *not* move past the new tuple, which is
+		 * what they want.
+		 */
+		tuplestore_puttupleslot(tuplestorestate, cteslot);
+
+		/*
+		 * We MUST copy the CTE query's output tuple into our own slot.
+		 * This is because other CteScan nodes might advance the CTE query
+		 * before we are called again, and our output tuple must stay
+		 * stable over that.
+		 */
+		return ExecCopySlot(slot, cteslot);
+	}
+
+	/*
+	 * Nothing left ...
+	 */
+	return ExecClearTuple(slot);
+}
+
+/* ----------------------------------------------------------------
+ *		ExecCteScan(node)
+ *
+ *		Scans the CTE sequentially and returns the next qualifying tuple.
+ *		It calls the ExecScan() routine and passes it the access method
+ *		which retrieves tuples sequentially.
+ * ----------------------------------------------------------------
+ */
+TupleTableSlot *
+ExecCteScan(CteScanState *node)
+{
+	/*
+	 * use CteScanNext as access method
+	 */
+	return ExecScan(&node->ss, (ExecScanAccessMtd) CteScanNext);
+}
+
+
+/* ----------------------------------------------------------------
+ *		ExecInitCteScan
+ * ----------------------------------------------------------------
+ */
+CteScanState *
+ExecInitCteScan(CteScan *node, EState *estate, int eflags)
+{
+	CteScanState *scanstate;
+	ParamExecData *prmdata;
+
+	/* check for unsupported flags */
+	Assert(!(eflags & EXEC_FLAG_MARK));
+
+	/*
+	 * For the moment we have to force the tuplestore to allow REWIND, because
+	 * we might be asked to rescan the CTE even though upper levels didn't
+	 * tell us to be prepared to do it efficiently.  Annoying, since this
+	 * prevents truncation of the tuplestore.  XXX FIXME
+	 */
+	eflags |= EXEC_FLAG_REWIND;
+
+	/*
+	 * CteScan should not have any children.
+	 */
+	Assert(outerPlan(node) == NULL);
+	Assert(innerPlan(node) == NULL);
+
+	/*
+	 * create new CteScanState for node
+	 */
+	scanstate = makeNode(CteScanState);
+	scanstate->ss.ps.plan = (Plan *) node;
+	scanstate->ss.ps.state = estate;
+	scanstate->eflags = eflags;
+	scanstate->cte_table = NULL;
+	scanstate->eof_cte = false;
+
+	/*
+	 * Find the already-initialized plan for the CTE query.
+	 */
+	scanstate->cteplanstate = (PlanState *) list_nth(estate->es_subplanstates,
+													 node->ctePlanId - 1);
+
+	/*
+	 * The Param slot associated with the CTE query is used to hold a
+	 * pointer to the CteState of the first CteScan node that initializes
+	 * for this CTE.  This node will be the one that holds the shared
+	 * state for all the CTEs.
+	 */
+	prmdata = &(estate->es_param_exec_vals[node->cteParam]);
+	Assert(prmdata->execPlan == NULL);
+	Assert(!prmdata->isnull);
+	scanstate->leader = (CteScanState *) DatumGetPointer(prmdata->value);
+	if (scanstate->leader == NULL)
+	{
+		/* I am the leader */
+		prmdata->value = PointerGetDatum(scanstate);
+		scanstate->leader = scanstate;
+		scanstate->cte_table = tuplestore_begin_heap(true, false, work_mem);
+		tuplestore_set_eflags(scanstate->cte_table, scanstate->eflags);
+		scanstate->readptr = 0;
+	}
+	else
+	{
+		/* Not the leader */
+		Assert(IsA(scanstate->leader, CteScanState));
+		scanstate->readptr =
+			tuplestore_alloc_read_pointer(scanstate->leader->cte_table,
+										  scanstate->eflags);
+	}
+
+	/*
+	 * Miscellaneous initialization
+	 *
+	 * create expression context for node
+	 */
+	ExecAssignExprContext(estate, &scanstate->ss.ps);
+
+	/*
+	 * initialize child expressions
+	 */
+	scanstate->ss.ps.targetlist = (List *)
+		ExecInitExpr((Expr *) node->scan.plan.targetlist,
+					 (PlanState *) scanstate);
+	scanstate->ss.ps.qual = (List *)
+		ExecInitExpr((Expr *) node->scan.plan.qual,
+					 (PlanState *) scanstate);
+
+#define CTESCAN_NSLOTS 2
+
+	/*
+	 * tuple table initialization
+	 */
+	ExecInitResultTupleSlot(estate, &scanstate->ss.ps);
+	ExecInitScanTupleSlot(estate, &scanstate->ss);
+
+	/*
+	 * The scan tuple type (ie, the rowtype we expect to find in the work
+	 * table) is the same as the result rowtype of the CTE query.
+	 */
+	ExecAssignScanType(&scanstate->ss,
+					   ExecGetResultType(scanstate->cteplanstate));
+
+	/*
+	 * Initialize result tuple type and projection info.
+	 */
+	ExecAssignResultTypeFromTL(&scanstate->ss.ps);
+	ExecAssignScanProjectionInfo(&scanstate->ss);
+
+	scanstate->ss.ps.ps_TupFromTlist = false;
+
+	return scanstate;
+}
+
+int
+ExecCountSlotsCteScan(CteScan *node)
+{
+	return ExecCountSlotsNode(outerPlan(node)) +
+		ExecCountSlotsNode(innerPlan(node)) +
+		CTESCAN_NSLOTS;
+}
+
+/* ----------------------------------------------------------------
+ *		ExecEndCteScan
+ *
+ *		frees any storage allocated through C routines.
+ * ----------------------------------------------------------------
+ */
+void
+ExecEndCteScan(CteScanState *node)
+{
+	/*
+	 * Free exprcontext
+	 */
+	ExecFreeExprContext(&node->ss.ps);
+
+	/*
+	 * clean out the tuple table
+	 */
+	ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
+	ExecClearTuple(node->ss.ss_ScanTupleSlot);
+
+	/*
+	 * If I am the leader, free the tuplestore.
+	 */
+	if (node->leader == node)
+		tuplestore_end(node->cte_table);
+}
+
+/* ----------------------------------------------------------------
+ *		ExecCteScanReScan
+ *
+ *		Rescans the relation.
+ * ----------------------------------------------------------------
+ */
+void
+ExecCteScanReScan(CteScanState *node, ExprContext *exprCtxt)
+{
+	Tuplestorestate *tuplestorestate;
+
+	tuplestorestate = node->leader->cte_table;
+
+	ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
+
+	if (node->leader == node)
+	{
+		/*
+		 * The leader is responsible for clearing the tuplestore if a new
+		 * scan of the underlying CTE is required.
+		 */
+		if (node->cteplanstate->chgParam != NULL)
+		{
+			tuplestore_clear(tuplestorestate);
+			node->eof_cte = false;
+		}
+		else
+		{
+			tuplestore_select_read_pointer(tuplestorestate, node->readptr);
+			tuplestore_rescan(tuplestorestate);
+		}
+	}
+	else
+	{
+		/* Not leader, so just rewind my own pointer */
+		tuplestore_select_read_pointer(tuplestorestate, node->readptr);
+		tuplestore_rescan(tuplestorestate);
+	}
+}
diff --git a/src/backend/executor/nodeRecursiveunion.c b/src/backend/executor/nodeRecursiveunion.c
new file mode 100644
index 00000000000..7136a623015
--- /dev/null
+++ b/src/backend/executor/nodeRecursiveunion.c
@@ -0,0 +1,225 @@
+/*-------------------------------------------------------------------------
+ *
+ * nodeRecursiveunion.c
+ *	  routines to handle RecursiveUnion nodes.
+ *
+ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *	  $PostgreSQL: pgsql/src/backend/executor/nodeRecursiveunion.c,v 1.1 2008/10/04 21:56:53 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "executor/execdebug.h"
+#include "executor/nodeRecursiveunion.h"
+#include "miscadmin.h"
+
+
+/* ----------------------------------------------------------------
+ *		ExecRecursiveUnion(node)
+ *
+ *		Scans the recursive query sequentially and returns the next
+ *      qualifying tuple.
+ *
+ * 1. evaluate non recursive term and assign the result to RT
+ *
+ * 2. execute recursive terms
+ *
+ * 2.1 WT := RT
+ * 2.2 while WT is not empty repeat 2.3 to 2.6. if WT is empty returns RT
+ * 2.3 replace the name of recursive term with WT
+ * 2.4 evaluate the recursive term and store into WT
+ * 2.5 append WT to RT
+ * 2.6 go back to 2.2
+ * ----------------------------------------------------------------
+ */
+TupleTableSlot *
+ExecRecursiveUnion(RecursiveUnionState *node)
+{
+	PlanState  *outerPlan = outerPlanState(node);
+	PlanState  *innerPlan = innerPlanState(node);
+	RecursiveUnion *plan = (RecursiveUnion *) node->ps.plan;
+	TupleTableSlot *slot;
+
+	/* 1. Evaluate non-recursive term */
+	if (!node->recursing)
+	{
+		slot = ExecProcNode(outerPlan);
+		if (!TupIsNull(slot))
+		{
+			tuplestore_puttupleslot(node->working_table, slot);
+			return slot;
+		}
+		node->recursing = true;
+	}
+
+retry:
+	/* 2. Execute recursive term */
+	slot = ExecProcNode(innerPlan);
+	if (TupIsNull(slot))
+	{
+		if (node->intermediate_empty)
+			return NULL;
+
+		/* done with old working table ... */
+		tuplestore_end(node->working_table);
+
+		/* intermediate table becomes working table */
+		node->working_table = node->intermediate_table;
+
+		/* create new empty intermediate table */
+		node->intermediate_table = tuplestore_begin_heap(false, false, work_mem);
+		node->intermediate_empty = true;
+
+		/* and reset the inner plan */
+		innerPlan->chgParam = bms_add_member(innerPlan->chgParam,
+											 plan->wtParam);
+		goto retry;
+	}
+ 	else
+ 	{
+ 		node->intermediate_empty = false;
+ 		tuplestore_puttupleslot(node->intermediate_table, slot);
+ 	}
+
+	return slot;
+}
+
+/* ----------------------------------------------------------------
+ *		ExecInitRecursiveUnionScan
+ * ----------------------------------------------------------------
+ */
+RecursiveUnionState *
+ExecInitRecursiveUnion(RecursiveUnion *node, EState *estate, int eflags)
+{
+	RecursiveUnionState *rustate;
+	ParamExecData *prmdata;
+
+	/* check for unsupported flags */
+	Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
+
+	/*
+	 * create state structure
+	 */
+	rustate = makeNode(RecursiveUnionState);
+	rustate->ps.plan = (Plan *) node;
+	rustate->ps.state = estate;
+
+	/* initialize processing state */
+	rustate->recursing = false;
+	rustate->intermediate_empty = true;
+	rustate->working_table = tuplestore_begin_heap(false, false, work_mem);
+	rustate->intermediate_table = tuplestore_begin_heap(false, false, work_mem);
+
+	/*
+	 * Make the state structure available to descendant WorkTableScan nodes
+	 * via the Param slot reserved for it.
+	 */
+	prmdata = &(estate->es_param_exec_vals[node->wtParam]);
+	Assert(prmdata->execPlan == NULL);
+	prmdata->value = PointerGetDatum(rustate);
+	prmdata->isnull = false;
+
+	/*
+	 * Miscellaneous initialization
+	 *
+	 * RecursiveUnion plans don't have expression contexts because they never
+	 * call ExecQual or ExecProject.
+	 */
+	Assert(node->plan.qual == NIL);
+
+#define RECURSIVEUNION_NSLOTS 1
+
+	/*
+	 * RecursiveUnion nodes still have Result slots, which hold pointers to
+	 * tuples, so we have to initialize them.
+	 */
+	ExecInitResultTupleSlot(estate, &rustate->ps);
+
+	/*
+	 * Initialize result tuple type and projection info.  (Note: we have
+	 * to set up the result type before initializing child nodes, because
+	 * nodeWorktablescan.c expects it to be valid.)
+	 */
+	ExecAssignResultTypeFromTL(&rustate->ps);
+	rustate->ps.ps_ProjInfo = NULL;
+
+	/*
+	 * initialize child nodes
+	 */
+	outerPlanState(rustate) = ExecInitNode(outerPlan(node), estate, eflags);
+	innerPlanState(rustate) = ExecInitNode(innerPlan(node), estate, eflags);
+
+	return rustate;
+}
+
+int
+ExecCountSlotsRecursiveUnion(RecursiveUnion *node)
+{
+	return ExecCountSlotsNode(outerPlan(node)) +
+		ExecCountSlotsNode(innerPlan(node)) +
+		RECURSIVEUNION_NSLOTS;
+}
+
+/* ----------------------------------------------------------------
+ *		ExecEndRecursiveUnionScan
+ *
+ *		frees any storage allocated through C routines.
+ * ----------------------------------------------------------------
+ */
+void
+ExecEndRecursiveUnion(RecursiveUnionState *node)
+{
+	/* Release tuplestores */
+	tuplestore_end(node->working_table);
+	tuplestore_end(node->intermediate_table);
+
+	/*
+	 * clean out the upper tuple table
+	 */
+	ExecClearTuple(node->ps.ps_ResultTupleSlot);
+
+	/*
+	 * close down subplans
+	 */
+	ExecEndNode(outerPlanState(node));
+	ExecEndNode(innerPlanState(node));
+}
+
+/* ----------------------------------------------------------------
+ *		ExecRecursiveUnionReScan
+ *
+ *		Rescans the relation.
+ * ----------------------------------------------------------------
+ */
+void
+ExecRecursiveUnionReScan(RecursiveUnionState *node, ExprContext *exprCtxt)
+{
+	PlanState  *outerPlan = outerPlanState(node);
+	PlanState  *innerPlan = innerPlanState(node);
+	RecursiveUnion *plan = (RecursiveUnion *) node->ps.plan;
+
+	/*
+	 * Set recursive term's chgParam to tell it that we'll modify the
+	 * working table and therefore it has to rescan.
+	 */
+	innerPlan->chgParam = bms_add_member(innerPlan->chgParam, plan->wtParam);
+
+	/*
+	 * if chgParam of subnode is not null then plan will be re-scanned by
+	 * first ExecProcNode.  Because of above, we only have to do this to
+	 * the non-recursive term.
+	 */
+	if (outerPlan->chgParam == NULL)
+		ExecReScan(outerPlan, exprCtxt);
+
+	/* reset processing state */
+	node->recursing = false;
+	node->intermediate_empty = true;
+	tuplestore_clear(node->working_table);
+	tuplestore_clear(node->intermediate_table);
+}
diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c
index 3ebb045f922..338d94e7608 100644
--- a/src/backend/executor/nodeSubplan.c
+++ b/src/backend/executor/nodeSubplan.c
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/executor/nodeSubplan.c,v 1.94 2008/08/22 00:16:03 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/executor/nodeSubplan.c,v 1.95 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -66,9 +66,13 @@ ExecSubPlan(SubPlanState *node,
 	if (isDone)
 		*isDone = ExprSingleResult;
 
+	/* Sanity checks */
+	if (subplan->subLinkType == CTE_SUBLINK)
+		elog(ERROR, "CTE subplans should not be executed via ExecSubPlan");
 	if (subplan->setParam != NIL)
 		elog(ERROR, "cannot set parent params from subquery");
 
+	/* Select appropriate evaluation strategy */
 	if (subplan->useHashTable)
 		return ExecHashSubPlan(node, econtext, isNull);
 	else
@@ -688,11 +692,14 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
 	 * If this plan is un-correlated or undirect correlated one and want to
 	 * set params for parent plan then mark parameters as needing evaluation.
 	 *
+	 * A CTE subplan's output parameter is never to be evaluated in the normal
+	 * way, so skip this in that case.
+	 *
 	 * Note that in the case of un-correlated subqueries we don't care about
 	 * setting parent->chgParam here: indices take care about it, for others -
 	 * it doesn't matter...
 	 */
-	if (subplan->setParam != NIL)
+	if (subplan->setParam != NIL && subplan->subLinkType != CTE_SUBLINK)
 	{
 		ListCell   *lst;
 
@@ -907,22 +914,21 @@ ExecSetParamPlan(SubPlanState *node, ExprContext *econtext)
 	bool		found = false;
 	ArrayBuildState *astate = NULL;
 
-	/*
-	 * Must switch to per-query memory context.
-	 */
-	oldcontext = MemoryContextSwitchTo(econtext->ecxt_per_query_memory);
-
 	if (subLinkType == ANY_SUBLINK ||
 		subLinkType == ALL_SUBLINK)
 		elog(ERROR, "ANY/ALL subselect unsupported as initplan");
+	if (subLinkType == CTE_SUBLINK)
+		elog(ERROR, "CTE subplans should not be executed via ExecSetParamPlan");
 
 	/*
-	 * By definition, an initplan has no parameters from our query level, but
-	 * it could have some from an outer level.	Rescan it if needed.
+	 * Must switch to per-query memory context.
 	 */
-	if (planstate->chgParam != NULL)
-		ExecReScan(planstate, NULL);
+	oldcontext = MemoryContextSwitchTo(econtext->ecxt_per_query_memory);
 
+	/*
+	 * Run the plan.  (If it needs to be rescanned, the first ExecProcNode
+	 * call will take care of that.)
+	 */
 	for (slot = ExecProcNode(planstate);
 		 !TupIsNull(slot);
 		 slot = ExecProcNode(planstate))
@@ -932,7 +938,7 @@ ExecSetParamPlan(SubPlanState *node, ExprContext *econtext)
 
 		if (subLinkType == EXISTS_SUBLINK)
 		{
-			/* There can be only one param... */
+			/* There can be only one setParam... */
 			int			paramid = linitial_int(subplan->setParam);
 			ParamExecData *prm = &(econtext->ecxt_param_exec_vals[paramid]);
 
@@ -994,7 +1000,7 @@ ExecSetParamPlan(SubPlanState *node, ExprContext *econtext)
 
 	if (subLinkType == ARRAY_SUBLINK)
 	{
-		/* There can be only one param... */
+		/* There can be only one setParam... */
 		int			paramid = linitial_int(subplan->setParam);
 		ParamExecData *prm = &(econtext->ecxt_param_exec_vals[paramid]);
 
@@ -1014,7 +1020,7 @@ ExecSetParamPlan(SubPlanState *node, ExprContext *econtext)
 	{
 		if (subLinkType == EXISTS_SUBLINK)
 		{
-			/* There can be only one param... */
+			/* There can be only one setParam... */
 			int			paramid = linitial_int(subplan->setParam);
 			ParamExecData *prm = &(econtext->ecxt_param_exec_vals[paramid]);
 
@@ -1059,18 +1065,25 @@ ExecReScanSetParamPlan(SubPlanState *node, PlanState *parent)
 		elog(ERROR, "extParam set of initplan is empty");
 
 	/*
-	 * Don't actually re-scan: ExecSetParamPlan does it if needed.
+	 * Don't actually re-scan: it'll happen inside ExecSetParamPlan if needed.
 	 */
 
 	/*
-	 * Mark this subplan's output parameters as needing recalculation
+	 * Mark this subplan's output parameters as needing recalculation.
+	 *
+	 * CTE subplans are never executed via parameter recalculation; instead
+	 * they get run when called by nodeCtescan.c.  So don't mark the output
+	 * parameter of a CTE subplan as dirty, but do set the chgParam bit
+	 * for it so that dependent plan nodes will get told to rescan.
 	 */
 	foreach(l, subplan->setParam)
 	{
 		int			paramid = lfirst_int(l);
 		ParamExecData *prm = &(estate->es_param_exec_vals[paramid]);
 
-		prm->execPlan = node;
+		if (subplan->subLinkType != CTE_SUBLINK)
+			prm->execPlan = node;
+
 		parent->chgParam = bms_add_member(parent->chgParam, paramid);
 	}
 }
diff --git a/src/backend/executor/nodeWorktablescan.c b/src/backend/executor/nodeWorktablescan.c
new file mode 100644
index 00000000000..2f09c5e22dd
--- /dev/null
+++ b/src/backend/executor/nodeWorktablescan.c
@@ -0,0 +1,194 @@
+/*-------------------------------------------------------------------------
+ *
+ * nodeWorktablescan.c
+ *	  routines to handle WorkTableScan nodes.
+ *
+ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *	  $PostgreSQL: pgsql/src/backend/executor/nodeWorktablescan.c,v 1.1 2008/10/04 21:56:53 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include "executor/execdebug.h"
+#include "executor/nodeWorktablescan.h"
+
+static TupleTableSlot *WorkTableScanNext(WorkTableScanState *node);
+
+/* ----------------------------------------------------------------
+ *		WorkTableScanNext
+ *
+ *		This is a workhorse for ExecWorkTableScan
+ * ----------------------------------------------------------------
+ */
+static TupleTableSlot *
+WorkTableScanNext(WorkTableScanState *node)
+{
+	TupleTableSlot *slot;
+	EState	   *estate;
+	ScanDirection direction;
+	Tuplestorestate *tuplestorestate;
+
+	/*
+	 * get information from the estate and scan state
+	 */
+	estate = node->ss.ps.state;
+	direction = estate->es_direction;
+
+	tuplestorestate = node->rustate->working_table;
+
+	/*
+	 * Get the next tuple from tuplestore. Return NULL if no more tuples.
+	 */
+	slot = node->ss.ss_ScanTupleSlot;
+	(void) tuplestore_gettupleslot(tuplestorestate,
+								   ScanDirectionIsForward(direction),
+								   slot);
+	return slot;
+}
+
+/* ----------------------------------------------------------------
+ *		ExecWorkTableScan(node)
+ *
+ *		Scans the worktable sequentially and returns the next qualifying tuple.
+ *		It calls the ExecScan() routine and passes it the access method
+ *		which retrieves tuples sequentially.
+ * ----------------------------------------------------------------
+ */
+TupleTableSlot *
+ExecWorkTableScan(WorkTableScanState *node)
+{
+	/*
+	 * use WorkTableScanNext as access method
+	 */
+	return ExecScan(&node->ss, (ExecScanAccessMtd) WorkTableScanNext);
+}
+
+
+/* ----------------------------------------------------------------
+ *		ExecInitWorkTableScan
+ * ----------------------------------------------------------------
+ */
+WorkTableScanState *
+ExecInitWorkTableScan(WorkTableScan *node, EState *estate, int eflags)
+{
+	WorkTableScanState *scanstate;
+	ParamExecData *prmdata;
+
+	/* check for unsupported flags */
+	Assert(!(eflags & EXEC_FLAG_MARK));
+
+	/*
+	 * WorkTableScan should not have any children.
+	 */
+	Assert(outerPlan(node) == NULL);
+	Assert(innerPlan(node) == NULL);
+
+	/*
+	 * create new WorkTableScanState for node
+	 */
+	scanstate = makeNode(WorkTableScanState);
+	scanstate->ss.ps.plan = (Plan *) node;
+	scanstate->ss.ps.state = estate;
+
+	/*
+	 * Find the ancestor RecursiveUnion's state
+	 * via the Param slot reserved for it.
+	 */
+	prmdata = &(estate->es_param_exec_vals[node->wtParam]);
+	Assert(prmdata->execPlan == NULL);
+	Assert(!prmdata->isnull);
+	scanstate->rustate = (RecursiveUnionState *) DatumGetPointer(prmdata->value);
+	Assert(scanstate->rustate && IsA(scanstate->rustate, RecursiveUnionState));
+
+	/*
+	 * Miscellaneous initialization
+	 *
+	 * create expression context for node
+	 */
+	ExecAssignExprContext(estate, &scanstate->ss.ps);
+
+	/*
+	 * initialize child expressions
+	 */
+	scanstate->ss.ps.targetlist = (List *)
+		ExecInitExpr((Expr *) node->scan.plan.targetlist,
+					 (PlanState *) scanstate);
+	scanstate->ss.ps.qual = (List *)
+		ExecInitExpr((Expr *) node->scan.plan.qual,
+					 (PlanState *) scanstate);
+
+#define WORKTABLESCAN_NSLOTS 2
+
+	/*
+	 * tuple table initialization
+	 */
+	ExecInitResultTupleSlot(estate, &scanstate->ss.ps);
+	ExecInitScanTupleSlot(estate, &scanstate->ss);
+
+	/*
+	 * The scan tuple type (ie, the rowtype we expect to find in the work
+	 * table) is the same as the result rowtype of the ancestor RecursiveUnion
+	 * node.  Note this depends on the assumption that RecursiveUnion doesn't
+	 * allow projection.
+	 */
+	ExecAssignScanType(&scanstate->ss,
+					   ExecGetResultType(&scanstate->rustate->ps));
+
+	/*
+	 * Initialize result tuple type and projection info.
+	 */
+	ExecAssignResultTypeFromTL(&scanstate->ss.ps);
+	ExecAssignScanProjectionInfo(&scanstate->ss);
+
+	scanstate->ss.ps.ps_TupFromTlist = false;
+
+	return scanstate;
+}
+
+int
+ExecCountSlotsWorkTableScan(WorkTableScan *node)
+{
+	return ExecCountSlotsNode(outerPlan(node)) +
+		ExecCountSlotsNode(innerPlan(node)) +
+		WORKTABLESCAN_NSLOTS;
+}
+
+/* ----------------------------------------------------------------
+ *		ExecEndWorkTableScan
+ *
+ *		frees any storage allocated through C routines.
+ * ----------------------------------------------------------------
+ */
+void
+ExecEndWorkTableScan(WorkTableScanState *node)
+{
+	/*
+	 * Free exprcontext
+	 */
+	ExecFreeExprContext(&node->ss.ps);
+
+	/*
+	 * clean out the tuple table
+	 */
+	ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
+	ExecClearTuple(node->ss.ss_ScanTupleSlot);
+}
+
+/* ----------------------------------------------------------------
+ *		ExecWorkTableScanReScan
+ *
+ *		Rescans the relation.
+ * ----------------------------------------------------------------
+ */
+void
+ExecWorkTableScanReScan(WorkTableScanState *node, ExprContext *exprCtxt)
+{
+	ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
+	tuplestore_rescan(node->rustate->working_table);
+}