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

4 files changed, 455 insertions, 16 deletions

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))