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

14 files changed, 842 insertions, 81 deletions

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 3dc41c68073..a942249fd09 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.173 2008/08/25 22:42:32 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.174 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -57,6 +57,10 @@ static void set_function_pathlist(PlannerInfo *root, RelOptInfo *rel,
 					  RangeTblEntry *rte);
 static void set_values_pathlist(PlannerInfo *root, RelOptInfo *rel,
 					RangeTblEntry *rte);
+static void set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel,
+							 RangeTblEntry *rte);
+static void set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel,
+								   RangeTblEntry *rte);
 static RelOptInfo *make_rel_from_joinlist(PlannerInfo *root, List *joinlist);
 static bool subquery_is_pushdown_safe(Query *subquery, Query *topquery,
 						  bool *differentTypes);
@@ -173,14 +177,22 @@ set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 	}
 	else if (rel->rtekind == RTE_FUNCTION)
 	{
-		/* RangeFunction --- generate a separate plan for it */
+		/* RangeFunction --- generate a suitable path for it */
 		set_function_pathlist(root, rel, rte);
 	}
 	else if (rel->rtekind == RTE_VALUES)
 	{
-		/* Values list --- generate a separate plan for it */
+		/* Values list --- generate a suitable path for it */
 		set_values_pathlist(root, rel, rte);
 	}
+	else if (rel->rtekind == RTE_CTE)
+	{
+		/* CTE reference --- generate a suitable path for it */
+		if (rte->self_reference)
+			set_worktable_pathlist(root, rel, rte);
+		else
+			set_cte_pathlist(root, rel, rte);
+	}
 	else
 	{
 		/* Plain relation */
@@ -585,8 +597,8 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
 
 	/* Generate the plan for the subquery */
 	rel->subplan = subquery_planner(root->glob, subquery,
-									root->query_level + 1,
-									tuple_fraction,
+									root,
+									false, tuple_fraction,
 									&subroot);
 	rel->subrtable = subroot->parse->rtable;
 
@@ -641,6 +653,104 @@ set_values_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 }
 
 /*
+ * set_cte_pathlist
+ *		Build the (single) access path for a non-self-reference CTE RTE
+ */
+static void
+set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
+{
+	Plan	   *cteplan;
+	PlannerInfo *cteroot;
+	Index		levelsup;
+	int			ndx;
+	ListCell   *lc;
+	int			plan_id;
+
+	/*
+	 * Find the referenced CTE, and locate the plan previously made for it.
+	 */
+	levelsup = rte->ctelevelsup;
+	cteroot = root;
+	while (levelsup-- > 0)
+	{
+		cteroot = cteroot->parent_root;
+		if (!cteroot)			/* shouldn't happen */
+			elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
+	}
+	/*
+	 * Note: cte_plan_ids can be shorter than cteList, if we are still working
+	 * on planning the CTEs (ie, this is a side-reference from another CTE).
+	 * So we mustn't use forboth here.
+	 */
+	ndx = 0;
+	foreach(lc, cteroot->parse->cteList)
+	{
+		CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
+
+		if (strcmp(cte->ctename, rte->ctename) == 0)
+			break;
+		ndx++;
+	}
+	if (lc == NULL)				/* shouldn't happen */
+		elog(ERROR, "could not find CTE \"%s\"", rte->ctename);
+	if (ndx >= list_length(cteroot->cte_plan_ids))
+		elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
+	plan_id = list_nth_int(cteroot->cte_plan_ids, ndx);
+	Assert(plan_id > 0);
+	cteplan = (Plan *) list_nth(root->glob->subplans, plan_id - 1);
+
+	/* Mark rel with estimated output rows, width, etc */
+	set_cte_size_estimates(root, rel, cteplan);
+
+	/* Generate appropriate path */
+	add_path(rel, create_ctescan_path(root, rel));
+
+	/* Select cheapest path (pretty easy in this case...) */
+	set_cheapest(rel);
+}
+
+/*
+ * set_worktable_pathlist
+ *		Build the (single) access path for a self-reference CTE RTE
+ */
+static void
+set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
+{
+	Plan	   *cteplan;
+	PlannerInfo *cteroot;
+	Index		levelsup;
+
+	/*
+	 * We need to find the non-recursive term's plan, which is in the plan
+	 * level that's processing the recursive UNION, which is one level
+	 * *below* where the CTE comes from.
+	 */
+	levelsup = rte->ctelevelsup;
+	if (levelsup == 0)			/* shouldn't happen */
+		elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
+	levelsup--;
+	cteroot = root;
+	while (levelsup-- > 0)
+	{
+		cteroot = cteroot->parent_root;
+		if (!cteroot)			/* shouldn't happen */
+			elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
+	}
+	cteplan = cteroot->non_recursive_plan;
+	if (!cteplan)				/* shouldn't happen */
+		elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
+
+	/* Mark rel with estimated output rows, width, etc */
+	set_cte_size_estimates(root, rel, cteplan);
+
+	/* Generate appropriate path */
+	add_path(rel, create_worktablescan_path(root, rel));
+
+	/* Select cheapest path (pretty easy in this case...) */
+	set_cheapest(rel);
+}
+
+/*
  * make_rel_from_joinlist
  *	  Build access paths using a "joinlist" to guide the join path search.
  *
diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c
index 9ffdc32e775..e3e4e9f02c0 100644
--- a/src/backend/optimizer/path/clausesel.c
+++ b/src/backend/optimizer/path/clausesel.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/path/clausesel.c,v 1.93 2008/08/22 00:16:03 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/path/clausesel.c,v 1.94 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -550,29 +550,17 @@ clause_selectivity(PlannerInfo *root,
 		if (var->varlevelsup == 0 &&
 			(varRelid == 0 || varRelid == (int) var->varno))
 		{
-			RangeTblEntry *rte = planner_rt_fetch(var->varno, root);
-
-			if (rte->rtekind == RTE_SUBQUERY)
-			{
-				/*
-				 * XXX not smart about subquery references... any way to do
-				 * better than default?
-				 */
-			}
-			else
-			{
-				/*
-				 * A Var at the top of a clause must be a bool Var. This is
-				 * equivalent to the clause reln.attribute = 't', so we
-				 * compute the selectivity as if that is what we have.
-				 */
-				s1 = restriction_selectivity(root,
-											 BooleanEqualOperator,
-											 list_make2(var,
-														makeBoolConst(true,
-																	  false)),
-											 varRelid);
-			}
+			/*
+			 * A Var at the top of a clause must be a bool Var. This is
+			 * equivalent to the clause reln.attribute = 't', so we
+			 * compute the selectivity as if that is what we have.
+			 */
+			s1 = restriction_selectivity(root,
+										 BooleanEqualOperator,
+										 list_make2(var,
+													makeBoolConst(true,
+																  false)),
+										 varRelid);
 		}
 	}
 	else if (IsA(clause, Const))
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index bbc77db4e25..7bfc66cac3a 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -54,7 +54,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.197 2008/09/05 21:07:29 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.198 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -934,6 +934,84 @@ cost_valuesscan(Path *path, PlannerInfo *root, RelOptInfo *baserel)
 }
 
 /*
+ * cost_ctescan
+ *	  Determines and returns the cost of scanning a CTE RTE.
+ *
+ * Note: this is used for both self-reference and regular CTEs; the
+ * possible cost differences are below the threshold of what we could
+ * estimate accurately anyway.  Note that the costs of evaluating the
+ * referenced CTE query are added into the final plan as initplan costs,
+ * and should NOT be counted here.
+ */
+void
+cost_ctescan(Path *path, PlannerInfo *root, RelOptInfo *baserel)
+{
+	Cost		startup_cost = 0;
+	Cost		run_cost = 0;
+	Cost		cpu_per_tuple;
+
+	/* Should only be applied to base relations that are CTEs */
+	Assert(baserel->relid > 0);
+	Assert(baserel->rtekind == RTE_CTE);
+
+	/* Charge one CPU tuple cost per row for tuplestore manipulation */
+	cpu_per_tuple = cpu_tuple_cost;
+
+	/* Add scanning CPU costs */
+	startup_cost += baserel->baserestrictcost.startup;
+	cpu_per_tuple += cpu_tuple_cost + baserel->baserestrictcost.per_tuple;
+	run_cost += cpu_per_tuple * baserel->tuples;
+
+	path->startup_cost = startup_cost;
+	path->total_cost = startup_cost + run_cost;
+}
+
+/*
+ * cost_recursive_union
+ *	  Determines and returns the cost of performing a recursive union,
+ *	  and also the estimated output size.
+ *
+ * We are given Plans for the nonrecursive and recursive terms.
+ *
+ * Note that the arguments and output are Plans, not Paths as in most of
+ * the rest of this module.  That's because we don't bother setting up a
+ * Path representation for recursive union --- we have only one way to do it.
+ */
+void
+cost_recursive_union(Plan *runion, Plan *nrterm, Plan *rterm)
+{
+	Cost		startup_cost;
+	Cost		total_cost;
+	double		total_rows;
+
+	/* We probably have decent estimates for the non-recursive term */
+	startup_cost = nrterm->startup_cost;
+	total_cost = nrterm->total_cost;
+	total_rows = nrterm->plan_rows;
+
+	/*
+	 * We arbitrarily assume that about 10 recursive iterations will be
+	 * needed, and that we've managed to get a good fix on the cost and
+	 * output size of each one of them.  These are mighty shaky assumptions
+	 * but it's hard to see how to do better.
+	 */
+	total_cost += 10 * rterm->total_cost;
+	total_rows += 10 * rterm->plan_rows;
+
+	/*
+	 * Also charge cpu_tuple_cost per row to account for the costs of
+	 * manipulating the tuplestores.  (We don't worry about possible
+	 * spill-to-disk costs.)
+	 */
+	total_cost += cpu_tuple_cost * total_rows;
+
+	runion->startup_cost = startup_cost;
+	runion->total_cost = total_cost;
+	runion->plan_rows = total_rows;
+	runion->plan_width = Max(nrterm->plan_width, rterm->plan_width);
+}
+
+/*
  * cost_sort
  *	  Determines and returns the cost of sorting a relation, including
  *	  the cost of reading the input data.
@@ -2475,6 +2553,44 @@ set_values_size_estimates(PlannerInfo *root, RelOptInfo *rel)
 	set_baserel_size_estimates(root, rel);
 }
 
+/*
+ * set_cte_size_estimates
+ *		Set the size estimates for a base relation that is a CTE reference.
+ *
+ * The rel's targetlist and restrictinfo list must have been constructed
+ * already, and we need the completed plan for the CTE (if a regular CTE)
+ * or the non-recursive term (if a self-reference).
+ *
+ * We set the same fields as set_baserel_size_estimates.
+ */
+void
+set_cte_size_estimates(PlannerInfo *root, RelOptInfo *rel, Plan *cteplan)
+{
+	RangeTblEntry *rte;
+
+	/* Should only be applied to base relations that are CTE references */
+	Assert(rel->relid > 0);
+	rte = planner_rt_fetch(rel->relid, root);
+	Assert(rte->rtekind == RTE_CTE);
+
+	if (rte->self_reference)
+	{
+		/*
+		 * In a self-reference, arbitrarily assume the average worktable
+		 * size is about 10 times the nonrecursive term's size.
+		 */
+		rel->tuples = 10 * cteplan->plan_rows;
+	}
+	else
+	{
+		/* Otherwise just believe the CTE plan's output estimate */
+		rel->tuples = cteplan->plan_rows;
+	}
+
+	/* Now estimate number of output rows, etc */
+	set_baserel_size_estimates(root, rel);
+}
+
 
 /*
  * set_rel_width
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 845f429a4b4..eaf0ffa4276 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/path/joinpath.c,v 1.117 2008/08/14 18:47:59 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/path/joinpath.c,v 1.118 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -408,10 +408,15 @@ match_unsorted_outer(PlannerInfo *root,
 		 * If the cheapest inner path is a join or seqscan, we should consider
 		 * materializing it.  (This is a heuristic: we could consider it
 		 * always, but for inner indexscans it's probably a waste of time.)
+		 * Also skip it if the inner path materializes its output anyway.
 		 */
-		if (!(IsA(inner_cheapest_total, IndexPath) ||
-			  IsA(inner_cheapest_total, BitmapHeapPath) ||
-			  IsA(inner_cheapest_total, TidPath)))
+		if (!(inner_cheapest_total->pathtype == T_IndexScan ||
+			  inner_cheapest_total->pathtype == T_BitmapHeapScan ||
+			  inner_cheapest_total->pathtype == T_TidScan ||
+			  inner_cheapest_total->pathtype == T_Material ||
+			  inner_cheapest_total->pathtype == T_FunctionScan ||
+			  inner_cheapest_total->pathtype == T_CteScan ||
+			  inner_cheapest_total->pathtype == T_WorkTableScan))
 			matpath = (Path *)
 				create_material_path(innerrel, inner_cheapest_total);
 
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 1195024b5fc..aabbf64a755 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -10,7 +10,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.248 2008/09/05 21:07:29 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.249 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -62,6 +62,10 @@ static FunctionScan *create_functionscan_plan(PlannerInfo *root, Path *best_path
 						 List *tlist, List *scan_clauses);
 static ValuesScan *create_valuesscan_plan(PlannerInfo *root, Path *best_path,
 					   List *tlist, List *scan_clauses);
+static CteScan *create_ctescan_plan(PlannerInfo *root, Path *best_path,
+									List *tlist, List *scan_clauses);
+static WorkTableScan *create_worktablescan_plan(PlannerInfo *root, Path *best_path,
+												List *tlist, List *scan_clauses);
 static NestLoop *create_nestloop_plan(PlannerInfo *root, NestPath *best_path,
 					 Plan *outer_plan, Plan *inner_plan);
 static MergeJoin *create_mergejoin_plan(PlannerInfo *root, MergePath *best_path,
@@ -93,6 +97,10 @@ static FunctionScan *make_functionscan(List *qptlist, List *qpqual,
 				  List *funccoltypes, List *funccoltypmods);
 static ValuesScan *make_valuesscan(List *qptlist, List *qpqual,
 				Index scanrelid, List *values_lists);
+static CteScan *make_ctescan(List *qptlist, List *qpqual,
+							 Index scanrelid, int ctePlanId, int cteParam);
+static WorkTableScan *make_worktablescan(List *qptlist, List *qpqual,
+										 Index scanrelid, int wtParam);
 static BitmapAnd *make_bitmap_and(List *bitmapplans);
 static BitmapOr *make_bitmap_or(List *bitmapplans);
 static NestLoop *make_nestloop(List *tlist,
@@ -148,6 +156,8 @@ create_plan(PlannerInfo *root, Path *best_path)
 		case T_SubqueryScan:
 		case T_FunctionScan:
 		case T_ValuesScan:
+		case T_CteScan:
+		case T_WorkTableScan:
 			plan = create_scan_plan(root, best_path);
 			break;
 		case T_HashJoin:
@@ -270,6 +280,20 @@ create_scan_plan(PlannerInfo *root, Path *best_path)
 												   scan_clauses);
 			break;
 
+		case T_CteScan:
+			plan = (Plan *) create_ctescan_plan(root,
+												best_path,
+												tlist,
+												scan_clauses);
+			break;
+
+		case T_WorkTableScan:
+			plan = (Plan *) create_worktablescan_plan(root,
+													  best_path,
+													  tlist,
+													  scan_clauses);
+			break;
+
 		default:
 			elog(ERROR, "unrecognized node type: %d",
 				 (int) best_path->pathtype);
@@ -324,12 +348,13 @@ use_physical_tlist(RelOptInfo *rel)
 
 	/*
 	 * We can do this for real relation scans, subquery scans, function scans,
-	 * and values scans (but not for, eg, joins).
+	 * values scans, and CTE scans (but not for, eg, joins).
 	 */
 	if (rel->rtekind != RTE_RELATION &&
 		rel->rtekind != RTE_SUBQUERY &&
 		rel->rtekind != RTE_FUNCTION &&
-		rel->rtekind != RTE_VALUES)
+		rel->rtekind != RTE_VALUES &&
+		rel->rtekind != RTE_CTE)
 		return false;
 
 	/*
@@ -375,6 +400,8 @@ disuse_physical_tlist(Plan *plan, Path *path)
 		case T_SubqueryScan:
 		case T_FunctionScan:
 		case T_ValuesScan:
+		case T_CteScan:
+		case T_WorkTableScan:
 			plan->targetlist = build_relation_tlist(path->parent);
 			break;
 		default:
@@ -1335,6 +1362,145 @@ create_valuesscan_plan(PlannerInfo *root, Path *best_path,
 	return scan_plan;
 }
 
+/*
+ * create_ctescan_plan
+ *	 Returns a ctescan plan for the base relation scanned by 'best_path'
+ *	 with restriction clauses 'scan_clauses' and targetlist 'tlist'.
+ */
+static CteScan *
+create_ctescan_plan(PlannerInfo *root, Path *best_path,
+					List *tlist, List *scan_clauses)
+{
+	CteScan	   *scan_plan;
+	Index		scan_relid = best_path->parent->relid;
+	RangeTblEntry *rte;
+	SubPlan	   *ctesplan = NULL;
+	int			plan_id;
+	int			cte_param_id;
+	PlannerInfo *cteroot;
+	Index		levelsup;
+	int			ndx;
+	ListCell   *lc;
+
+	Assert(scan_relid > 0);
+	rte = planner_rt_fetch(scan_relid, root);
+	Assert(rte->rtekind == RTE_CTE);
+	Assert(!rte->self_reference);
+
+	/*
+	 * Find the referenced CTE, and locate the SubPlan previously made for it.
+	 */
+	levelsup = rte->ctelevelsup;
+	cteroot = root;
+	while (levelsup-- > 0)
+	{
+		cteroot = cteroot->parent_root;
+		if (!cteroot)			/* shouldn't happen */
+			elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
+	}
+	/*
+	 * Note: cte_plan_ids can be shorter than cteList, if we are still working
+	 * on planning the CTEs (ie, this is a side-reference from another CTE).
+	 * So we mustn't use forboth here.
+	 */
+	ndx = 0;
+	foreach(lc, cteroot->parse->cteList)
+	{
+		CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
+
+		if (strcmp(cte->ctename, rte->ctename) == 0)
+			break;
+		ndx++;
+	}
+	if (lc == NULL)				/* shouldn't happen */
+		elog(ERROR, "could not find CTE \"%s\"", rte->ctename);
+	if (ndx >= list_length(cteroot->cte_plan_ids))
+		elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
+	plan_id = list_nth_int(cteroot->cte_plan_ids, ndx);
+	Assert(plan_id > 0);
+	foreach(lc, cteroot->init_plans)
+	{
+		ctesplan = (SubPlan *) lfirst(lc);
+		if (ctesplan->plan_id == plan_id)
+			break;
+	}
+	if (lc == NULL)				/* shouldn't happen */
+		elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
+
+	/*
+	 * We need the CTE param ID, which is the sole member of the
+	 * SubPlan's setParam list.
+	 */
+	cte_param_id = linitial_int(ctesplan->setParam);
+
+	/* Sort clauses into best execution order */
+	scan_clauses = order_qual_clauses(root, scan_clauses);
+
+	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
+	scan_clauses = extract_actual_clauses(scan_clauses, false);
+
+	scan_plan = make_ctescan(tlist, scan_clauses, scan_relid,
+							 plan_id, cte_param_id);
+
+	copy_path_costsize(&scan_plan->scan.plan, best_path);
+
+	return scan_plan;
+}
+
+/*
+ * create_worktablescan_plan
+ *	 Returns a worktablescan plan for the base relation scanned by 'best_path'
+ *	 with restriction clauses 'scan_clauses' and targetlist 'tlist'.
+ */
+static WorkTableScan *
+create_worktablescan_plan(PlannerInfo *root, Path *best_path,
+						  List *tlist, List *scan_clauses)
+{
+	WorkTableScan *scan_plan;
+	Index		scan_relid = best_path->parent->relid;
+	RangeTblEntry *rte;
+	Index		levelsup;
+	PlannerInfo *cteroot;
+
+	Assert(scan_relid > 0);
+	rte = planner_rt_fetch(scan_relid, root);
+	Assert(rte->rtekind == RTE_CTE);
+	Assert(rte->self_reference);
+
+	/*
+	 * We need to find the worktable param ID, which is in the plan level
+	 * that's processing the recursive UNION, which is one level *below*
+	 * where the CTE comes from.
+	 */
+	levelsup = rte->ctelevelsup;
+	if (levelsup == 0)			/* shouldn't happen */
+			elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
+	levelsup--;
+	cteroot = root;
+	while (levelsup-- > 0)
+	{
+		cteroot = cteroot->parent_root;
+		if (!cteroot)			/* shouldn't happen */
+			elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
+	}
+	if (cteroot->wt_param_id < 0)	/* shouldn't happen */
+		elog(ERROR, "could not find param ID for CTE \"%s\"", rte->ctename);
+
+	/* Sort clauses into best execution order */
+	scan_clauses = order_qual_clauses(root, scan_clauses);
+
+	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
+	scan_clauses = extract_actual_clauses(scan_clauses, false);
+
+	scan_plan = make_worktablescan(tlist, scan_clauses, scan_relid,
+								   cteroot->wt_param_id);
+
+	copy_path_costsize(&scan_plan->scan.plan, best_path);
+
+	return scan_plan;
+}
+
+
 /*****************************************************************************
  *
  *	JOIN METHODS
@@ -2291,6 +2457,48 @@ make_valuesscan(List *qptlist,
 	return node;
 }
 
+static CteScan *
+make_ctescan(List *qptlist,
+			 List *qpqual,
+			 Index scanrelid,
+			 int ctePlanId,
+			 int cteParam)
+{
+	CteScan *node = makeNode(CteScan);
+	Plan	   *plan = &node->scan.plan;
+
+	/* cost should be inserted by caller */
+	plan->targetlist = qptlist;
+	plan->qual = qpqual;
+	plan->lefttree = NULL;
+	plan->righttree = NULL;
+	node->scan.scanrelid = scanrelid;
+	node->ctePlanId = ctePlanId;
+	node->cteParam = cteParam;
+
+	return node;
+}
+
+static WorkTableScan *
+make_worktablescan(List *qptlist,
+				   List *qpqual,
+				   Index scanrelid,
+				   int wtParam)
+{
+	WorkTableScan *node = makeNode(WorkTableScan);
+	Plan	   *plan = &node->scan.plan;
+
+	/* cost should be inserted by caller */
+	plan->targetlist = qptlist;
+	plan->qual = qpqual;
+	plan->lefttree = NULL;
+	plan->righttree = NULL;
+	node->scan.scanrelid = scanrelid;
+	node->wtParam = wtParam;
+
+	return node;
+}
+
 Append *
 make_append(List *appendplans, bool isTarget, List *tlist)
 {
@@ -2333,6 +2541,26 @@ make_append(List *appendplans, bool isTarget, List *tlist)
 	return node;
 }
 
+RecursiveUnion *
+make_recursive_union(List *tlist,
+					 Plan *lefttree,
+					 Plan *righttree,
+					 int wtParam)
+{
+	RecursiveUnion *node = makeNode(RecursiveUnion);
+	Plan	   *plan = &node->plan;
+
+	cost_recursive_union(plan, lefttree, righttree);
+
+	plan->targetlist = tlist;
+	plan->qual = NIL;
+	plan->lefttree = lefttree;
+	plan->righttree = righttree;
+	node->wtParam = wtParam;
+
+	return node;
+}
+
 static BitmapAnd *
 make_bitmap_and(List *bitmapplans)
 {
@@ -3284,6 +3512,7 @@ is_projection_capable_plan(Plan *plan)
 		case T_SetOp:
 		case T_Limit:
 		case T_Append:
+		case T_RecursiveUnion:
 			return false;
 		default:
 			break;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index ec2b0f794a0..0a704dc6545 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/planner.c,v 1.243 2008/09/09 18:58:08 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/planner.c,v 1.244 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -173,7 +173,8 @@ standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams)
 	}
 
 	/* primary planning entry point (may recurse for subqueries) */
-	top_plan = subquery_planner(glob, parse, 1, tuple_fraction, &root);
+	top_plan = subquery_planner(glob, parse, NULL,
+								false, tuple_fraction, &root);
 
 	/*
 	 * If creating a plan for a scrollable cursor, make sure it can run
@@ -228,7 +229,8 @@ standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams)
  *
  * glob is the global state for the current planner run.
  * parse is the querytree produced by the parser & rewriter.
- * level is the current recursion depth (1 at the top-level Query).
+ * parent_root is the immediate parent Query's info (NULL at the top level).
+ * hasRecursion is true if this is a recursive WITH query.
  * tuple_fraction is the fraction of tuples we expect will be retrieved.
  * tuple_fraction is interpreted as explained for grouping_planner, below.
  *
@@ -249,7 +251,8 @@ standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams)
  */
 Plan *
 subquery_planner(PlannerGlobal *glob, Query *parse,
-				 Index level, double tuple_fraction,
+				 PlannerInfo *parent_root,
+				 bool hasRecursion, double tuple_fraction,
 				 PlannerInfo **subroot)
 {
 	int			num_old_subplans = list_length(glob->subplans);
@@ -263,12 +266,28 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
 	root = makeNode(PlannerInfo);
 	root->parse = parse;
 	root->glob = glob;
-	root->query_level = level;
+	root->query_level = parent_root ? parent_root->query_level + 1 : 1;
+	root->parent_root = parent_root;
 	root->planner_cxt = CurrentMemoryContext;
 	root->init_plans = NIL;
+	root->cte_plan_ids = NIL;
 	root->eq_classes = NIL;
 	root->append_rel_list = NIL;
 
+	root->hasRecursion = hasRecursion;
+	if (hasRecursion)
+		root->wt_param_id = SS_assign_worktable_param(root);
+	else
+		root->wt_param_id = -1;
+	root->non_recursive_plan = NULL;
+
+	/*
+	 * If there is a WITH list, process each WITH query and build an
+	 * initplan SubPlan structure for it.
+	 */
+	if (parse->cteList)
+		SS_process_ctes(root);
+
 	/*
 	 * Look for ANY and EXISTS SubLinks in WHERE and JOIN/ON clauses, and try
 	 * to transform them into joins.  Note that this step does not descend
@@ -776,7 +795,9 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 
 		/*
 		 * Construct the plan for set operations.  The result will not need
-		 * any work except perhaps a top-level sort and/or LIMIT.
+		 * any work except perhaps a top-level sort and/or LIMIT.  Note that
+		 * any special work for recursive unions is the responsibility of
+		 * plan_set_operations.
 		 */
 		result_plan = plan_set_operations(root, tuple_fraction,
 										  &set_sortclauses);
@@ -838,6 +859,9 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 
 		MemSet(&agg_counts, 0, sizeof(AggClauseCounts));
 
+		/* A recursive query should always have setOperations */
+		Assert(!root->hasRecursion);
+
 		/* Preprocess GROUP BY clause, if any */
 		if (parse->groupClause)
 			preprocess_groupclause(root);
diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c
index 18362628727..6d7ec283b34 100644
--- a/src/backend/optimizer/plan/setrefs.c
+++ b/src/backend/optimizer/plan/setrefs.c
@@ -9,7 +9,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/setrefs.c,v 1.144 2008/09/09 18:58:08 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/setrefs.c,v 1.145 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -201,11 +201,13 @@ set_plan_references(PlannerGlobal *glob, Plan *plan, List *rtable)
 
 		/* zap unneeded sub-structure */
 		newrte->subquery = NULL;
+		newrte->joinaliasvars = NIL;
 		newrte->funcexpr = NULL;
 		newrte->funccoltypes = NIL;
 		newrte->funccoltypmods = NIL;
 		newrte->values_lists = NIL;
-		newrte->joinaliasvars = NIL;
+		newrte->ctecoltypes = NIL;
+		newrte->ctecoltypmods = NIL;
 
 		glob->finalrtable = lappend(glob->finalrtable, newrte);
 
@@ -343,7 +345,28 @@ set_plan_refs(PlannerGlobal *glob, Plan *plan, int rtoffset)
 					fix_scan_list(glob, splan->values_lists, rtoffset);
 			}
 			break;
+		case T_CteScan:
+			{
+				CteScan *splan = (CteScan *) plan;
+
+				splan->scan.scanrelid += rtoffset;
+				splan->scan.plan.targetlist =
+					fix_scan_list(glob, splan->scan.plan.targetlist, rtoffset);
+				splan->scan.plan.qual =
+					fix_scan_list(glob, splan->scan.plan.qual, rtoffset);
+			}
+			break;
+		case T_WorkTableScan:
+			{
+				WorkTableScan *splan = (WorkTableScan *) plan;
 
+				splan->scan.scanrelid += rtoffset;
+				splan->scan.plan.targetlist =
+					fix_scan_list(glob, splan->scan.plan.targetlist, rtoffset);
+				splan->scan.plan.qual =
+					fix_scan_list(glob, splan->scan.plan.qual, rtoffset);
+			}
+			break;
 		case T_NestLoop:
 		case T_MergeJoin:
 		case T_HashJoin:
@@ -434,6 +457,11 @@ set_plan_refs(PlannerGlobal *glob, Plan *plan, int rtoffset)
 				}
 			}
 			break;
+		case T_RecursiveUnion:
+			/* This doesn't evaluate targetlist or check quals either */
+			set_dummy_tlist_references(plan, rtoffset);
+			Assert(plan->qual == NIL);
+			break;
 		case T_BitmapAnd:
 			{
 				BitmapAnd  *splan = (BitmapAnd *) plan;
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index fe8be5b1bbb..00d84d56823 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/subselect.c,v 1.140 2008/08/28 23:09:46 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/subselect.c,v 1.141 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -213,6 +213,20 @@ generate_new_param(PlannerInfo *root, Oid paramtype, int32 paramtypmod)
 }
 
 /*
+ * Assign a (nonnegative) PARAM_EXEC ID for a recursive query's worktable.
+ */
+int
+SS_assign_worktable_param(PlannerInfo *root)
+{
+	Param	   *param;
+
+	/* We generate a Param of datatype INTERNAL */
+	param = generate_new_param(root, INTERNALOID, -1);
+	/* ... but the caller only cares about its ID */
+	return param->paramid;
+}
+
+/*
  * Get the datatype of the first column of the plan's output.
  *
  * This is stored for ARRAY_SUBLINK and for exprType(), which doesn't have any
@@ -308,8 +322,8 @@ make_subplan(PlannerInfo *root, Query *orig_subquery, SubLinkType subLinkType,
 	 * Generate the plan for the subquery.
 	 */
 	plan = subquery_planner(root->glob, subquery,
-							root->query_level + 1,
-							tuple_fraction,
+							root,
+							false, tuple_fraction,
 							&subroot);
 
 	/* And convert to SubPlan or InitPlan format. */
@@ -342,8 +356,8 @@ make_subplan(PlannerInfo *root, Query *orig_subquery, SubLinkType subLinkType,
 		{
 			/* Generate the plan for the ANY subquery; we'll need all rows */
 			plan = subquery_planner(root->glob, subquery,
-									root->query_level + 1,
-									0.0,
+									root,
+									false, 0.0,
 									&subroot);
 
 			/* Now we can check if it'll fit in work_mem */
@@ -549,6 +563,8 @@ build_subplan(PlannerInfo *root, Plan *plan, List *rtable,
 			{
 				case T_Material:
 				case T_FunctionScan:
+				case T_CteScan:
+				case T_WorkTableScan:
 				case T_Sort:
 					use_material = false;
 					break;
@@ -798,6 +814,123 @@ hash_ok_operator(OpExpr *expr)
 	return true;
 }
 
+
+/*
+ * SS_process_ctes: process a query's WITH list
+ *
+ * We plan each interesting WITH item and convert it to an initplan.
+ * A side effect is to fill in root->cte_plan_ids with a list that
+ * parallels root->parse->cteList and provides the subplan ID for
+ * each CTE's initplan.
+ */
+void
+SS_process_ctes(PlannerInfo *root)
+{
+	ListCell   *lc;
+
+	Assert(root->cte_plan_ids == NIL);
+
+	foreach(lc, root->parse->cteList)
+	{
+		CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
+		Query	   *subquery;
+		Plan	   *plan;
+		PlannerInfo *subroot;
+		SubPlan    *splan;
+		Bitmapset  *tmpset;
+		int			paramid;
+		Param	   *prm;
+
+		/*
+		 * Ignore CTEs that are not actually referenced anywhere.
+		 */
+		if (cte->cterefcount == 0)
+		{
+			/* Make a dummy entry in cte_plan_ids */
+			root->cte_plan_ids = lappend_int(root->cte_plan_ids, -1);
+			continue;
+		}
+
+		/*
+		 * Copy the source Query node.  Probably not necessary, but let's
+		 * keep this similar to make_subplan.
+		 */
+		subquery = (Query *) copyObject(cte->ctequery);
+
+		/*
+		 * Generate the plan for the CTE query.  Always plan for full
+		 * retrieval --- we don't have enough info to predict otherwise.
+		 */
+		plan = subquery_planner(root->glob, subquery,
+								root,
+								cte->cterecursive, 0.0,
+								&subroot);
+
+		/*
+		 * Make a SubPlan node for it.  This is just enough unlike
+		 * build_subplan that we can't share code.
+		 *
+		 * Note plan_id isn't set till further down, likewise the cost fields.
+		 */
+		splan = makeNode(SubPlan);
+		splan->subLinkType = CTE_SUBLINK;
+		splan->testexpr = NULL;
+		splan->paramIds = NIL;
+		splan->firstColType = get_first_col_type(plan);
+		splan->useHashTable = false;
+		splan->unknownEqFalse = false;
+		splan->setParam = NIL;
+		splan->parParam = NIL;
+		splan->args = NIL;
+
+		/*
+		 * Make parParam and args lists of param IDs and expressions that
+		 * current query level will pass to this child plan.  Even though
+		 * this is an initplan, there could be side-references to earlier
+		 * initplan's outputs, specifically their CTE output parameters.
+		 */
+		tmpset = bms_copy(plan->extParam);
+		while ((paramid = bms_first_member(tmpset)) >= 0)
+		{
+			PlannerParamItem *pitem = list_nth(root->glob->paramlist, paramid);
+
+			if (pitem->abslevel == root->query_level)
+			{
+				prm = (Param *) pitem->item;
+				if (!IsA(prm, Param) ||
+					prm->paramtype != INTERNALOID)
+					elog(ERROR, "bogus local parameter passed to WITH query");
+
+				splan->parParam = lappend_int(splan->parParam, paramid);
+				splan->args = lappend(splan->args, copyObject(prm));
+			}
+		}
+		bms_free(tmpset);
+
+		/*
+		 * Assign a param to represent the query output.  We only really
+		 * care about reserving a parameter ID number.
+		 */
+		prm = generate_new_param(root, INTERNALOID, -1);
+		splan->setParam = list_make1_int(prm->paramid);
+
+		/*
+		 * Add the subplan and its rtable to the global lists.
+		 */
+		root->glob->subplans = lappend(root->glob->subplans, plan);
+		root->glob->subrtables = lappend(root->glob->subrtables,
+										 subroot->parse->rtable);
+		splan->plan_id = list_length(root->glob->subplans);
+
+		root->init_plans = lappend(root->init_plans, splan);
+
+		root->cte_plan_ids = lappend_int(root->cte_plan_ids, splan->plan_id);
+
+		/* Lastly, fill in the cost estimates for use later */
+		cost_subplan(root, splan, plan);
+	}
+}
+
 /*
  * convert_ANY_sublink_to_join: can we convert an ANY SubLink to a join?
  *
@@ -1589,6 +1722,9 @@ SS_finalize_plan(PlannerInfo *root, Plan *plan, bool attach_initplans)
 
 		paramid++;
 	}
+	/* Also include the recursion working table, if any */
+	if (root->wt_param_id >= 0)
+		valid_params = bms_add_member(valid_params, root->wt_param_id);
 
 	/*
 	 * Now recurse through plan tree.
@@ -1719,6 +1855,18 @@ finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params)
 							  &context);
 			break;
 
+		case T_CteScan:
+			context.paramids =
+				bms_add_member(context.paramids,
+							   ((CteScan *) plan)->cteParam);
+			break;
+
+		case T_WorkTableScan:
+			context.paramids =
+				bms_add_member(context.paramids,
+							   ((WorkTableScan *) plan)->wtParam);
+			break;
+
 		case T_Append:
 			{
 				ListCell   *l;
@@ -1790,6 +1938,7 @@ finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params)
 							  &context);
 			break;
 
+		case T_RecursiveUnion:
 		case T_Hash:
 		case T_Agg:
 		case T_SeqScan:
@@ -1816,6 +1965,15 @@ finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params)
 													 plan->righttree,
 													 valid_params));
 
+	/*
+	 * RecursiveUnion *generates* its worktable param, so don't bubble that up
+	 */
+	if (IsA(plan, RecursiveUnion))
+	{
+		context.paramids = bms_del_member(context.paramids,
+										  ((RecursiveUnion *) plan)->wtParam);
+	}
+
 	/* Now we have all the paramids */
 
 	if (!bms_is_subset(context.paramids, valid_params))
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 965856385d7..21bd8332f4a 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -16,7 +16,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/prep/prepjointree.c,v 1.54 2008/08/25 22:42:33 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/prep/prepjointree.c,v 1.55 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -567,10 +567,18 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 	subroot->parse = subquery;
 	subroot->glob = root->glob;
 	subroot->query_level = root->query_level;
+	subroot->parent_root = root->parent_root;
 	subroot->planner_cxt = CurrentMemoryContext;
 	subroot->init_plans = NIL;
+	subroot->cte_plan_ids = NIL;
 	subroot->eq_classes = NIL;
 	subroot->append_rel_list = NIL;
+	subroot->hasRecursion = false;
+	subroot->wt_param_id = -1;
+	subroot->non_recursive_plan = NULL;
+
+	/* No CTEs to worry about */
+	Assert(subquery->cteList == NIL);
 
 	/*
 	 * Pull up any SubLinks within the subquery's quals, so that we don't
@@ -916,8 +924,8 @@ is_simple_subquery(Query *subquery)
 		return false;
 
 	/*
-	 * Can't pull up a subquery involving grouping, aggregation, sorting, or
-	 * limiting.
+	 * Can't pull up a subquery involving grouping, aggregation, sorting,
+	 * limiting, or WITH.  (XXX WITH could possibly be allowed later)
 	 */
 	if (subquery->hasAggs ||
 		subquery->groupClause ||
@@ -925,7 +933,8 @@ is_simple_subquery(Query *subquery)
 		subquery->sortClause ||
 		subquery->distinctClause ||
 		subquery->limitOffset ||
-		subquery->limitCount)
+		subquery->limitCount ||
+		subquery->cteList)
 		return false;
 
 	/*
@@ -985,11 +994,12 @@ is_simple_union_all(Query *subquery)
 		return false;
 	Assert(IsA(topop, SetOperationStmt));
 
-	/* Can't handle ORDER BY, LIMIT/OFFSET, or locking */
+	/* Can't handle ORDER BY, LIMIT/OFFSET, locking, or WITH */
 	if (subquery->sortClause ||
 		subquery->limitOffset ||
 		subquery->limitCount ||
-		subquery->rowMarks)
+		subquery->rowMarks ||
+		subquery->cteList)
 		return false;
 
 	/* Recursively check the tree of set operations */
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index 7dc274797e5..0836fde517b 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -22,7 +22,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/prep/prepunion.c,v 1.155 2008/08/28 23:09:46 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/prep/prepunion.c,v 1.156 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -56,6 +56,10 @@ static Plan *recurse_set_operations(Node *setOp, PlannerInfo *root,
 					   List *colTypes, bool junkOK,
 					   int flag, List *refnames_tlist,
 					   List **sortClauses, double *pNumGroups);
+static Plan *generate_recursion_plan(SetOperationStmt *setOp,
+						PlannerInfo *root, double tuple_fraction,
+						List *refnames_tlist,
+						List **sortClauses);
 static Plan *generate_union_plan(SetOperationStmt *op, PlannerInfo *root,
 					double tuple_fraction,
 					List *refnames_tlist,
@@ -148,6 +152,14 @@ plan_set_operations(PlannerInfo *root, double tuple_fraction,
 	Assert(leftmostQuery != NULL);
 
 	/*
+	 * If the topmost node is a recursive union, it needs special processing.
+	 */
+	if (root->hasRecursion)
+		return generate_recursion_plan(topop, root, tuple_fraction,
+									   leftmostQuery->targetList,
+									   sortClauses);
+
+	/*
 	 * Recurse on setOperations tree to generate plans for set ops. The final
 	 * output plan should have just the column types shown as the output from
 	 * the top-level node, plus possibly resjunk working columns (we can rely
@@ -200,8 +212,8 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 		 * Generate plan for primitive subquery
 		 */
 		subplan = subquery_planner(root->glob, subquery,
-								   root->query_level + 1,
-								   tuple_fraction,
+								   root,
+								   false, tuple_fraction,
 								   &subroot);
 
 		/*
@@ -294,6 +306,58 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
 }
 
 /*
+ * Generate plan for a recursive UNION node
+ */
+static Plan *
+generate_recursion_plan(SetOperationStmt *setOp, PlannerInfo *root,
+						double tuple_fraction,
+						List *refnames_tlist,
+						List **sortClauses)
+{
+	Plan	   *plan;
+	Plan	   *lplan;
+	Plan	   *rplan;
+	List	   *tlist;
+
+	/* Parser should have rejected other cases */
+	if (setOp->op != SETOP_UNION || !setOp->all)
+		elog(ERROR, "only UNION ALL queries can be recursive");
+	/* Worktable ID should be assigned */
+	Assert(root->wt_param_id >= 0);
+
+	/*
+	 * Unlike a regular UNION node, process the left and right inputs
+	 * separately without any intention of combining them into one Append.
+	 */
+	lplan = recurse_set_operations(setOp->larg, root, tuple_fraction,
+								   setOp->colTypes, false, -1,
+								   refnames_tlist, sortClauses, NULL);
+	/* The right plan will want to look at the left one ... */
+	root->non_recursive_plan = lplan;
+	rplan = recurse_set_operations(setOp->rarg, root, tuple_fraction,
+								   setOp->colTypes, false, -1,
+								   refnames_tlist, sortClauses, NULL);
+	root->non_recursive_plan = NULL;
+
+	/*
+	 * Generate tlist for RecursiveUnion plan node --- same as in Append cases
+	 */
+	tlist = generate_append_tlist(setOp->colTypes, false,
+								  list_make2(lplan, rplan),
+								  refnames_tlist);
+
+	/*
+	 * And make the plan node.
+	 */
+	plan = (Plan *) make_recursive_union(tlist, lplan, rplan,
+										 root->wt_param_id);
+
+	*sortClauses = NIL;			/* result of UNION ALL is always unsorted */
+
+	return plan;
+}
+
+/*
  * Generate plan for a UNION or UNION ALL node
  */
 static Plan *
@@ -1346,7 +1410,7 @@ adjust_appendrel_attrs(Node *node, AppendRelInfo *appinfo)
 		newnode = query_tree_mutator((Query *) node,
 									 adjust_appendrel_attrs_mutator,
 									 (void *) appinfo,
-									 QTW_IGNORE_RT_SUBQUERIES);
+									 QTW_IGNORE_RC_SUBQUERIES);
 		if (newnode->resultRelation == appinfo->parent_relid)
 		{
 			newnode->resultRelation = appinfo->child_relid;
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index 097105a89a2..bd0192d829e 100644
--- a/src/backend/optimizer/util/clauses.c
+++ b/src/backend/optimizer/util/clauses.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/util/clauses.c,v 1.267 2008/09/09 18:58:08 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/util/clauses.c,v 1.268 2008/10/04 21:56:53 tgl Exp $
  *
  * HISTORY
  *	  AUTHOR			DATE			MAJOR EVENT
@@ -3361,6 +3361,7 @@ inline_function(Oid funcid, Oid result_type, List *args,
 		querytree->intoClause ||
 		querytree->hasAggs ||
 		querytree->hasSubLinks ||
+		querytree->cteList ||
 		querytree->rtable ||
 		querytree->jointree->fromlist ||
 		querytree->jointree->quals ||
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 8e32895fb27..a922abcee8a 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/util/pathnode.c,v 1.147 2008/09/05 21:07:29 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/util/pathnode.c,v 1.148 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -1220,6 +1220,45 @@ create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel)
 }
 
 /*
+ * create_ctescan_path
+ *	  Creates a path corresponding to a scan of a non-self-reference CTE,
+ *	  returning the pathnode.
+ */
+Path *
+create_ctescan_path(PlannerInfo *root, RelOptInfo *rel)
+{
+	Path	   *pathnode = makeNode(Path);
+
+	pathnode->pathtype = T_CteScan;
+	pathnode->parent = rel;
+	pathnode->pathkeys = NIL;	/* XXX for now, result is always unordered */
+
+	cost_ctescan(pathnode, root, rel);
+
+	return pathnode;
+}
+
+/*
+ * create_worktablescan_path
+ *	  Creates a path corresponding to a scan of a self-reference CTE,
+ *	  returning the pathnode.
+ */
+Path *
+create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel)
+{
+	Path	   *pathnode = makeNode(Path);
+
+	pathnode->pathtype = T_WorkTableScan;
+	pathnode->parent = rel;
+	pathnode->pathkeys = NIL;	/* result is always unordered */
+
+	/* Cost is the same as for a regular CTE scan */
+	cost_ctescan(pathnode, root, rel);
+
+	return pathnode;
+}
+
+/*
  * create_nestloop_path
  *	  Creates a pathnode corresponding to a nestloop join between two
  *	  relations.
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index e6cd2f26b95..044cb8bbe68 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -9,7 +9,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/util/plancat.c,v 1.151 2008/09/01 20:42:44 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/util/plancat.c,v 1.152 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -657,8 +657,8 @@ relation_excluded_by_constraints(PlannerInfo *root,
  * dropped cols.
  *
  * We also support building a "physical" tlist for subqueries, functions,
- * and values lists, since the same optimization can occur in SubqueryScan,
- * FunctionScan, and ValuesScan nodes.
+ * values lists, and CTEs, since the same optimization can occur in
+ * SubqueryScan, FunctionScan, ValuesScan, CteScan, and WorkTableScan nodes.
  */
 List *
 build_physical_tlist(PlannerInfo *root, RelOptInfo *rel)
@@ -733,6 +733,9 @@ build_physical_tlist(PlannerInfo *root, RelOptInfo *rel)
 			break;
 
 		case RTE_FUNCTION:
+		case RTE_VALUES:
+		case RTE_CTE:
+			/* Not all of these can have dropped cols, but share code anyway */
 			expandRTE(rte, varno, 0, -1, true /* include dropped */ ,
 					  NULL, &colvars);
 			foreach(l, colvars)
@@ -757,21 +760,6 @@ build_physical_tlist(PlannerInfo *root, RelOptInfo *rel)
 			}
 			break;
 
-		case RTE_VALUES:
-			expandRTE(rte, varno, 0, -1, false /* dropped not applicable */ ,
-					  NULL, &colvars);
-			foreach(l, colvars)
-			{
-				var = (Var *) lfirst(l);
-
-				tlist = lappend(tlist,
-								makeTargetEntry((Expr *) var,
-												var->varattno,
-												NULL,
-												false));
-			}
-			break;
-
 		default:
 			/* caller error */
 			elog(ERROR, "unsupported RTE kind %d in build_physical_tlist",
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index f5592d17bb9..2fb6cd2efe6 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/util/relnode.c,v 1.90 2008/08/14 18:47:59 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/util/relnode.c,v 1.91 2008/10/04 21:56:53 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -101,6 +101,7 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptKind reloptkind)
 		case RTE_SUBQUERY:
 		case RTE_FUNCTION:
 		case RTE_VALUES:
+		case RTE_CTE:
 
 			/*
 			 * Subquery, function, or values list --- set up attr range and