Postpone extParam/allParam calculations until the very end of planning.

Until now we computed these Param ID sets at the end of subquery_planner,
but that approach depends on subquery_planner returning a concrete Plan
tree.  We would like to switch over to returning one or more Paths for a
subquery, and in that representation the necessary details aren't fully
fleshed out (not to mention that we don't really want to do this work for
Paths that end up getting discarded).  Hence, refactor so that we can
compute the param ID sets at the end of planning, just before
set_plan_references is run.

The main change necessary to make this work is that we need to capture
the set of outer-level Param IDs available to the current query level
before exiting subquery_planner, since the outer levels' plan_params lists
are transient.  (That's not going to pose a problem for returning Paths,
since all the work involved in producing that data is part of expression
preprocessing, which will continue to happen before Paths are produced.)
On the plus side, this change gets rid of several existing kluges.

Eventually I'd like to get rid of SS_finalize_plan altogether in favor of
doing this work during set_plan_references, but that will require some
complex rejiggering because SS_finalize_plan needs to visit subplans and
initplans before the main plan.  So leave that idea for another day.

1 files changed, 140 insertions, 126 deletions

diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index f3038cdffda..d0bc412c833 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -22,6 +22,7 @@
 #include "nodes/nodeFuncs.h"
 #include "optimizer/clauses.h"
 #include "optimizer/cost.h"
+#include "optimizer/pathnode.h"
 #include "optimizer/planmain.h"
 #include "optimizer/planner.h"
 #include "optimizer/prep.h"
@@ -2048,60 +2049,38 @@ process_sublinks_mutator(Node *node, process_sublinks_context *context)
 }
 
 /*
- * SS_finalize_plan - do final sublink and parameter processing for a
- * completed Plan.
+ * SS_identify_outer_params - identify the Params available from outer levels
  *
- * This recursively computes the extParam and allParam sets for every Plan
- * node in the given plan tree.  It also optionally attaches any previously
- * generated InitPlans to the top plan node.  (Any InitPlans should already
- * have been put through SS_finalize_plan.)
+ * This must be run after SS_replace_correlation_vars and SS_process_sublinks
+ * processing is complete in a given query level as well as all of its
+ * descendant levels (which means it's most practical to do it at the end of
+ * processing the query level).  We compute the set of paramIds that outer
+ * levels will make available to this level+descendants, and record it in
+ * root->outer_params for use while computing extParam/allParam sets in final
+ * plan cleanup.  (We can't just compute it then, because the upper levels'
+ * plan_params lists are transient and will be gone by then.)
  */
 void
-SS_finalize_plan(PlannerInfo *root, Plan *plan, bool attach_initplans)
+SS_identify_outer_params(PlannerInfo *root)
 {
-	Bitmapset  *valid_params,
-			   *initExtParam,
-			   *initSetParam;
-	Cost		initplan_cost;
+	Bitmapset  *outer_params;
 	PlannerInfo *proot;
 	ListCell   *l;
 
 	/*
-	 * Examine any initPlans to determine the set of external params they
-	 * reference, the set of output params they supply, and their total cost.
-	 * We'll use at least some of this info below.  (Note we are assuming that
-	 * finalize_plan doesn't touch the initPlans.)
-	 *
-	 * In the case where attach_initplans is false, we are assuming that the
-	 * existing initPlans are siblings that might supply params needed by the
-	 * current plan.
+	 * If no parameters have been assigned anywhere in the tree, we certainly
+	 * don't need to do anything here.
 	 */
-	initExtParam = initSetParam = NULL;
-	initplan_cost = 0;
-	foreach(l, root->init_plans)
-	{
-		SubPlan    *initsubplan = (SubPlan *) lfirst(l);
-		Plan	   *initplan = planner_subplan_get_plan(root, initsubplan);
-		ListCell   *l2;
-
-		initExtParam = bms_add_members(initExtParam, initplan->extParam);
-		foreach(l2, initsubplan->setParam)
-		{
-			initSetParam = bms_add_member(initSetParam, lfirst_int(l2));
-		}
-		initplan_cost += initsubplan->startup_cost + initsubplan->per_call_cost;
-	}
+	if (root->glob->nParamExec == 0)
+		return;
 
 	/*
-	 * Now determine the set of params that are validly referenceable in this
-	 * query level; to wit, those available from outer query levels plus the
-	 * output parameters of any local initPlans.  (We do not include output
-	 * parameters of regular subplans.  Those should only appear within the
-	 * testexpr of SubPlan nodes, and are taken care of locally within
-	 * finalize_primnode.  Likewise, special parameters that are generated by
-	 * nodes such as ModifyTable are handled within finalize_plan.)
+	 * Scan all query levels above this one to see which parameters are due to
+	 * be available from them, either because lower query levels have
+	 * requested them (via plan_params) or because they will be available from
+	 * initPlans of those levels.
 	 */
-	valid_params = bms_copy(initSetParam);
+	outer_params = NULL;
 	for (proot = root->parent_root; proot != NULL; proot = proot->parent_root)
 	{
 		/* Include ordinary Var/PHV/Aggref params */
@@ -2109,7 +2088,7 @@ SS_finalize_plan(PlannerInfo *root, Plan *plan, bool attach_initplans)
 		{
 			PlannerParamItem *pitem = (PlannerParamItem *) lfirst(l);
 
-			valid_params = bms_add_member(valid_params, pitem->paramId);
+			outer_params = bms_add_member(outer_params, pitem->paramId);
 		}
 		/* Include any outputs of outer-level initPlans */
 		foreach(l, proot->init_plans)
@@ -2119,48 +2098,42 @@ SS_finalize_plan(PlannerInfo *root, Plan *plan, bool attach_initplans)
 
 			foreach(l2, initsubplan->setParam)
 			{
-				valid_params = bms_add_member(valid_params, lfirst_int(l2));
+				outer_params = bms_add_member(outer_params, lfirst_int(l2));
 			}
 		}
 		/* Include worktable ID, if a recursive query is being planned */
 		if (proot->wt_param_id >= 0)
-			valid_params = bms_add_member(valid_params, proot->wt_param_id);
+			outer_params = bms_add_member(outer_params, proot->wt_param_id);
 	}
+	root->outer_params = outer_params;
+}
 
-	/*
-	 * Now recurse through plan tree.
-	 */
-	(void) finalize_plan(root, plan, valid_params, NULL);
-
-	bms_free(valid_params);
+/*
+ * SS_attach_initplans - attach initplans to topmost plan node
+ *
+ * Attach any initplans created in the current query level to the topmost plan
+ * node for the query level, and increment that node's cost to account for
+ * them.  (The initPlans could actually go in any node at or above where
+ * they're referenced, but there seems no reason to put them any lower than
+ * the topmost node for the query level.)
+ */
+void
+SS_attach_initplans(PlannerInfo *root, Plan *plan)
+{
+	ListCell   *lc;
 
-	/*
-	 * Finally, attach any initPlans to the topmost plan node, and add their
-	 * extParams to the topmost node's, too.  However, any setParams of the
-	 * initPlans should not be present in the topmost node's extParams, only
-	 * in its allParams.  (As of PG 8.1, it's possible that some initPlans
-	 * have extParams that are setParams of other initPlans, so we have to
-	 * take care of this situation explicitly.)
-	 *
-	 * We also add the eval cost of each initPlan to the startup cost of the
-	 * top node.  This is a conservative overestimate, since in fact each
-	 * initPlan might be executed later than plan startup, or even not at all.
-	 */
-	if (attach_initplans)
+	plan->initPlan = root->init_plans;
+	foreach(lc, plan->initPlan)
 	{
-		plan->initPlan = root->init_plans;
-		root->init_plans = NIL; /* make sure they're not attached twice */
-
-		/* allParam must include all these params */
-		plan->allParam = bms_add_members(plan->allParam, initExtParam);
-		plan->allParam = bms_add_members(plan->allParam, initSetParam);
-		/* extParam must include any child extParam */
-		plan->extParam = bms_add_members(plan->extParam, initExtParam);
-		/* but extParam shouldn't include any setParams */
-		plan->extParam = bms_del_members(plan->extParam, initSetParam);
-		/* ensure extParam is exactly NULL if it's empty */
-		if (bms_is_empty(plan->extParam))
-			plan->extParam = NULL;
+		SubPlan    *initsubplan = (SubPlan *) lfirst(lc);
+		Cost		initplan_cost;
+
+		/*
+		 * Assume each initPlan gets run once during top plan startup.  This
+		 * is a conservative overestimate, since in fact an initPlan might be
+		 * executed later than plan startup, or even not at all.
+		 */
+		initplan_cost = initsubplan->startup_cost + initsubplan->per_call_cost;
 
 		plan->startup_cost += initplan_cost;
 		plan->total_cost += initplan_cost;
@@ -2168,16 +2141,35 @@ SS_finalize_plan(PlannerInfo *root, Plan *plan, bool attach_initplans)
 }
 
 /*
+ * SS_finalize_plan - do final parameter processing for a completed Plan.
+ *
+ * This recursively computes the extParam and allParam sets for every Plan
+ * node in the given plan tree.  (Oh, and RangeTblFunction.funcparams too.)
+ *
+ * We assume that SS_finalize_plan has already been run on any initplans or
+ * subplans the plan tree could reference.
+ */
+void
+SS_finalize_plan(PlannerInfo *root, Plan *plan)
+{
+	/* No setup needed, just recurse through plan tree. */
+	(void) finalize_plan(root, plan, root->outer_params, NULL);
+}
+
+/*
  * Recursive processing of all nodes in the plan tree
  *
- * valid_params is the set of param IDs considered valid to reference in
- * this plan node or its children.
+ * valid_params is the set of param IDs supplied by outer plan levels
+ * that are valid to reference in this plan node or its children.
+ *
  * scan_params is a set of param IDs to force scan plan nodes to reference.
  * This is for EvalPlanQual support, and is always NULL at the top of the
  * recursion.
  *
  * The return value is the computed allParam set for the given Plan node.
  * This is just an internal notational convenience.
+ *
+ * Do not scribble on caller's values of valid_params or scan_params!
  */
 static Bitmapset *
 finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params,
@@ -2186,7 +2178,10 @@ finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params,
 	finalize_primnode_context context;
 	int			locally_added_param;
 	Bitmapset  *nestloop_params;
+	Bitmapset  *initExtParam;
+	Bitmapset  *initSetParam;
 	Bitmapset  *child_params;
+	ListCell   *l;
 
 	if (plan == NULL)
 		return NULL;
@@ -2197,6 +2192,29 @@ finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params,
 	nestloop_params = NULL;		/* there aren't any */
 
 	/*
+	 * Examine any initPlans to determine the set of external params they
+	 * reference and the set of output params they supply.  (We assume
+	 * SS_finalize_plan was run on them already.)
+	 */
+	initExtParam = initSetParam = NULL;
+	foreach(l, plan->initPlan)
+	{
+		SubPlan    *initsubplan = (SubPlan *) lfirst(l);
+		Plan	   *initplan = planner_subplan_get_plan(root, initsubplan);
+		ListCell   *l2;
+
+		initExtParam = bms_add_members(initExtParam, initplan->extParam);
+		foreach(l2, initsubplan->setParam)
+		{
+			initSetParam = bms_add_member(initSetParam, lfirst_int(l2));
+		}
+	}
+
+	/* Any setParams are validly referenceable in this node and children */
+	if (initSetParam)
+		valid_params = bms_union(valid_params, initSetParam);
+
+	/*
 	 * When we call finalize_primnode, context.paramids sets are automatically
 	 * merged together.  But when recursing to self, we have to do it the hard
 	 * way.  We want the paramids set to include params in subplans as well as
@@ -2274,18 +2292,22 @@ finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params,
 			break;
 
 		case T_SubqueryScan:
+			{
+				SubqueryScan *sscan = (SubqueryScan *) plan;
+				RelOptInfo *rel;
 
-			/*
-			 * In a SubqueryScan, SS_finalize_plan has already been run on the
-			 * subplan by the inner invocation of subquery_planner, so there's
-			 * no need to do it again.  Instead, just pull out the subplan's
-			 * extParams list, which represents the params it needs from my
-			 * level and higher levels.
-			 */
-			context.paramids = bms_add_members(context.paramids,
-								 ((SubqueryScan *) plan)->subplan->extParam);
-			/* We need scan_params too, though */
-			context.paramids = bms_add_members(context.paramids, scan_params);
+				/* We must run SS_finalize_plan on the subquery */
+				rel = find_base_rel(root, sscan->scan.scanrelid);
+				Assert(rel->subplan == sscan->subplan);
+				SS_finalize_plan(rel->subroot, sscan->subplan);
+
+				/* Now we can add its extParams to the parent's params */
+				context.paramids = bms_add_members(context.paramids,
+												   sscan->subplan->extParam);
+				/* We need scan_params too, though */
+				context.paramids = bms_add_members(context.paramids,
+												   scan_params);
+			}
 			break;
 
 		case T_FunctionScan:
@@ -2338,7 +2360,8 @@ finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params,
 				 * have to do instead is to find the referenced CTE plan and
 				 * incorporate its external paramids, so that the correct
 				 * things will happen if the CTE references outer-level
-				 * variables.  See test cases for bug #4902.
+				 * variables.  See test cases for bug #4902.  (We assume
+				 * SS_finalize_plan was run on the CTE plan already.)
 				 */
 				int			plan_id = ((CteScan *) plan)->ctePlanId;
 				Plan	   *cteplan;
@@ -2610,30 +2633,35 @@ finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params,
 										  locally_added_param);
 	}
 
-	/* Now we have all the paramids */
+	/* Now we have all the paramids referenced in this node and children */
 
 	if (!bms_is_subset(context.paramids, valid_params))
 		elog(ERROR, "plan should not reference subplan's variable");
 
 	/*
-	 * Note: by definition, extParam and allParam should have the same value
-	 * in any plan node that doesn't have child initPlans.  We set them equal
-	 * here, and later SS_finalize_plan will update them properly in node(s)
-	 * that it attaches initPlans to.
-	 *
+	 * The plan node's allParam and extParam fields should include all its
+	 * referenced paramids, plus contributions from any child initPlans.
+	 * However, any setParams of the initPlans should not be present in the
+	 * parent node's extParams, only in its allParams.  (It's possible that
+	 * some initPlans have extParams that are setParams of other initPlans.)
+	 */
+
+	/* allParam must include initplans' extParams and setParams */
+	plan->allParam = bms_union(context.paramids, initExtParam);
+	plan->allParam = bms_add_members(plan->allParam, initSetParam);
+	/* extParam must include any initplan extParams */
+	plan->extParam = bms_union(context.paramids, initExtParam);
+	/* but not any initplan setParams */
+	plan->extParam = bms_del_members(plan->extParam, initSetParam);
+
+	/*
 	 * For speed at execution time, make sure extParam/allParam are actually
 	 * NULL if they are empty sets.
 	 */
-	if (bms_is_empty(context.paramids))
-	{
+	if (bms_is_empty(plan->extParam))
 		plan->extParam = NULL;
+	if (bms_is_empty(plan->allParam))
 		plan->allParam = NULL;
-	}
-	else
-	{
-		plan->extParam = context.paramids;
-		plan->allParam = bms_copy(context.paramids);
-	}
 
 	return plan->allParam;
 }
@@ -2686,7 +2714,8 @@ finalize_primnode(Node *node, finalize_primnode_context *context)
 
 		/*
 		 * Add params needed by the subplan to paramids, but excluding those
-		 * we will pass down to it.
+		 * we will pass down to it.  (We assume SS_finalize_plan was run on
+		 * the subplan already.)
 		 */
 		subparamids = bms_copy(plan->extParam);
 		foreach(lc, subplan->parParam)
@@ -2706,13 +2735,12 @@ finalize_primnode(Node *node, finalize_primnode_context *context)
  *
  * The plan is expected to return a scalar value of the given type/collation.
  * We build an EXPR_SUBLINK SubPlan node and put it into the initplan
- * list for the current query level.  A Param that represents the initplan's
+ * list for the outer query level.  A Param that represents the initplan's
  * output is returned.
- *
- * We assume the plan hasn't been put through SS_finalize_plan.
  */
 Param *
-SS_make_initplan_from_plan(PlannerInfo *root, Plan *plan,
+SS_make_initplan_from_plan(PlannerInfo *root,
+						   PlannerInfo *subroot, Plan *plan,
 						   Oid resulttype, int32 resulttypmod,
 						   Oid resultcollation)
 {
@@ -2720,24 +2748,10 @@ SS_make_initplan_from_plan(PlannerInfo *root, Plan *plan,
 	Param	   *prm;
 
 	/*
-	 * We must run SS_finalize_plan(), since that's normally done before a
-	 * subplan gets put into the initplan list.  Tell it not to attach any
-	 * pre-existing initplans to this one, since they are siblings not
-	 * children of this initplan.  (This is something else that could perhaps
-	 * be cleaner if we did extParam/allParam processing in setrefs.c instead
-	 * of here?  See notes for materialize_finished_plan.)
-	 */
-
-	/*
-	 * Build extParam/allParam sets for plan nodes.
-	 */
-	SS_finalize_plan(root, plan, false);
-
-	/*
 	 * Add the subplan and its PlannerInfo to the global lists.
 	 */
 	root->glob->subplans = lappend(root->glob->subplans, plan);
-	root->glob->subroots = lappend(root->glob->subroots, root);
+	root->glob->subroots = lappend(root->glob->subroots, subroot);
 
 	/*
 	 * Create a SubPlan node and add it to the outer list of InitPlans. Note
@@ -2757,7 +2771,7 @@ SS_make_initplan_from_plan(PlannerInfo *root, Plan *plan,
 	 * parParam and args lists remain empty.
 	 */
 
-	cost_subplan(root, node, plan);
+	cost_subplan(subroot, node, plan);
 
 	/*
 	 * Make a Param that will be the subplan's output.