1 /*-------------------------------------------------------------------------
4 * Planning routines for subselects and parameters.
6 * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
10 * $PostgreSQL: pgsql/src/backend/optimizer/plan/subselect.c,v 1.88 2004/02/03 17:34:03 tgl Exp $
12 *-------------------------------------------------------------------------
16 #include "catalog/pg_operator.h"
17 #include "catalog/pg_type.h"
18 #include "miscadmin.h"
19 #include "nodes/makefuncs.h"
20 #include "nodes/params.h"
21 #include "optimizer/clauses.h"
22 #include "optimizer/cost.h"
23 #include "optimizer/planmain.h"
24 #include "optimizer/planner.h"
25 #include "optimizer/subselect.h"
26 #include "optimizer/var.h"
27 #include "parser/parsetree.h"
28 #include "parser/parse_expr.h"
29 #include "parser/parse_oper.h"
30 #include "parser/parse_relation.h"
31 #include "rewrite/rewriteManip.h"
32 #include "utils/builtins.h"
33 #include "utils/lsyscache.h"
34 #include "utils/syscache.h"
37 Index PlannerQueryLevel; /* level of current query */
38 List *PlannerInitPlan; /* init subplans for current query */
39 List *PlannerParamList; /* to keep track of cross-level Params */
41 int PlannerPlanId = 0; /* to assign unique ID to subquery plans */
44 * PlannerParamList keeps track of the PARAM_EXEC slots that we have decided
45 * we need for the query. At runtime these slots are used to pass values
46 * either down into subqueries (for outer references in subqueries) or up out
47 * of subqueries (for the results of a subplan). The n'th entry in the list
48 * (n counts from 0) corresponds to Param->paramid = n.
50 * Each ParamList item shows the absolute query level it is associated with,
51 * where the outermost query is level 1 and nested subqueries have higher
52 * numbers. The item the parameter slot represents can be one of three kinds:
54 * A Var: the slot represents a variable of that level that must be passed
55 * down because subqueries have outer references to it. The varlevelsup
56 * value in the Var will always be zero.
58 * An Aggref (with an expression tree representing its argument): the slot
59 * represents an aggregate expression that is an outer reference for some
60 * subquery. The Aggref itself has agglevelsup = 0, and its argument tree
61 * is adjusted to match in level.
63 * A Param: the slot holds the result of a subplan (it is a setParam item
64 * for that subplan). The absolute level shown for such items corresponds
65 * to the parent query of the subplan.
67 * Note: we detect duplicate Var parameters and coalesce them into one slot,
68 * but we do not do this for Aggref or Param slots.
70 typedef struct PlannerParamItem
72 Node *item; /* the Var, Aggref, or Param */
73 Index abslevel; /* its absolute query level */
77 typedef struct finalize_primnode_context
79 Bitmapset *paramids; /* Set of PARAM_EXEC paramids found */
80 Bitmapset *outer_params; /* Set of accessible outer paramids */
81 } finalize_primnode_context;
84 static List *convert_sublink_opers(List *lefthand, List *operOids,
85 List *targetlist, int rtindex,
87 static bool subplan_is_hashable(SubLink *slink, SubPlan *node);
88 static Node *replace_correlation_vars_mutator(Node *node, void *context);
89 static Node *process_sublinks_mutator(Node *node, bool *isTopQual);
90 static Bitmapset *finalize_plan(Plan *plan, List *rtable,
91 Bitmapset *outer_params,
92 Bitmapset *valid_params);
93 static bool finalize_primnode(Node *node, finalize_primnode_context *context);
97 * Generate a Param node to replace the given Var,
98 * which is expected to have varlevelsup > 0 (ie, it is not local).
101 replace_outer_var(Var *var)
105 PlannerParamItem *pitem;
109 Assert(var->varlevelsup > 0 && var->varlevelsup < PlannerQueryLevel);
110 abslevel = PlannerQueryLevel - var->varlevelsup;
113 * If there's already a PlannerParamList entry for this same Var, just
114 * use it. NOTE: in sufficiently complex querytrees, it is possible
115 * for the same varno/abslevel to refer to different RTEs in different
116 * parts of the parsetree, so that different fields might end up
117 * sharing the same Param number. As long as we check the vartype as
118 * well, I believe that this sort of aliasing will cause no trouble.
119 * The correct field should get stored into the Param slot at
120 * execution in each part of the tree.
122 * We also need to demand a match on vartypmod. This does not matter
123 * for the Param itself, since those are not typmod-dependent, but it
124 * does matter when make_subplan() instantiates a modified copy of the
125 * Var for a subplan's args list.
128 foreach(ppl, PlannerParamList)
130 pitem = (PlannerParamItem *) lfirst(ppl);
131 if (pitem->abslevel == abslevel && IsA(pitem->item, Var))
133 Var *pvar = (Var *) pitem->item;
135 if (pvar->varno == var->varno &&
136 pvar->varattno == var->varattno &&
137 pvar->vartype == var->vartype &&
138 pvar->vartypmod == var->vartypmod)
146 /* Nope, so make a new one */
147 var = (Var *) copyObject(var);
148 var->varlevelsup = 0;
150 pitem = (PlannerParamItem *) palloc(sizeof(PlannerParamItem));
151 pitem->item = (Node *) var;
152 pitem->abslevel = abslevel;
154 PlannerParamList = lappend(PlannerParamList, pitem);
155 /* i is already the correct index for the new item */
158 retval = makeNode(Param);
159 retval->paramkind = PARAM_EXEC;
160 retval->paramid = (AttrNumber) i;
161 retval->paramtype = var->vartype;
167 * Generate a Param node to replace the given Aggref
168 * which is expected to have agglevelsup > 0 (ie, it is not local).
171 replace_outer_agg(Aggref *agg)
174 PlannerParamItem *pitem;
178 Assert(agg->agglevelsup > 0 && agg->agglevelsup < PlannerQueryLevel);
179 abslevel = PlannerQueryLevel - agg->agglevelsup;
182 * It does not seem worthwhile to try to match duplicate outer aggs.
183 * Just make a new slot every time.
185 agg = (Aggref *) copyObject(agg);
186 IncrementVarSublevelsUp((Node *) agg, -((int) agg->agglevelsup), 0);
187 Assert(agg->agglevelsup == 0);
189 pitem = (PlannerParamItem *) palloc(sizeof(PlannerParamItem));
190 pitem->item = (Node *) agg;
191 pitem->abslevel = abslevel;
193 PlannerParamList = lappend(PlannerParamList, pitem);
194 i = length(PlannerParamList) - 1;
196 retval = makeNode(Param);
197 retval->paramkind = PARAM_EXEC;
198 retval->paramid = (AttrNumber) i;
199 retval->paramtype = agg->aggtype;
205 * Generate a new Param node that will not conflict with any other.
207 * This is used to allocate PARAM_EXEC slots for subplan outputs.
209 * paramtypmod is currently unused but might be wanted someday.
212 generate_new_param(Oid paramtype, int32 paramtypmod)
215 PlannerParamItem *pitem;
217 retval = makeNode(Param);
218 retval->paramkind = PARAM_EXEC;
219 retval->paramid = (AttrNumber) length(PlannerParamList);
220 retval->paramtype = paramtype;
222 pitem = (PlannerParamItem *) palloc(sizeof(PlannerParamItem));
223 pitem->item = (Node *) retval;
224 pitem->abslevel = PlannerQueryLevel;
226 PlannerParamList = lappend(PlannerParamList, pitem);
232 * Convert a bare SubLink (as created by the parser) into a SubPlan.
234 * We are given the raw SubLink and the already-processed lefthand argument
235 * list (use this instead of the SubLink's own field). We are also told if
236 * this expression appears at top level of a WHERE/HAVING qual.
238 * The result is whatever we need to substitute in place of the SubLink
239 * node in the executable expression. This will be either the SubPlan
240 * node (if we have to do the subplan as a subplan), or a Param node
241 * representing the result of an InitPlan, or possibly an AND or OR tree
242 * containing InitPlan Param nodes.
245 make_subplan(SubLink *slink, List *lefthand, bool isTopQual)
247 SubPlan *node = makeNode(SubPlan);
248 Query *subquery = (Query *) (slink->subselect);
249 double tuple_fraction;
257 * Copy the source Query node. This is a quick and dirty kluge to
258 * resolve the fact that the parser can generate trees with multiple
259 * links to the same sub-Query node, but the planner wants to scribble
260 * on the Query. Try to clean this up when we do querytree redesign...
262 subquery = (Query *) copyObject(subquery);
265 * For an EXISTS subplan, tell lower-level planner to expect that only
266 * the first tuple will be retrieved. For ALL and ANY subplans, we
267 * will be able to stop evaluating if the test condition fails, so
268 * very often not all the tuples will be retrieved; for lack of a
269 * better idea, specify 50% retrieval. For EXPR and MULTIEXPR
270 * subplans, use default behavior (we're only expecting one row out,
273 * NOTE: if you change these numbers, also change cost_qual_eval_walker()
274 * in path/costsize.c.
276 * XXX If an ALL/ANY subplan is uncorrelated, we may decide to hash or
277 * materialize its result below. In that case it would've been better
278 * to specify full retrieval. At present, however, we can only detect
279 * correlation or lack of it after we've made the subplan :-(. Perhaps
280 * detection of correlation should be done as a separate step.
281 * Meanwhile, we don't want to be too optimistic about the percentage
282 * of tuples retrieved, for fear of selecting a plan that's bad for
283 * the materialization case.
285 if (slink->subLinkType == EXISTS_SUBLINK)
286 tuple_fraction = 1.0; /* just like a LIMIT 1 */
287 else if (slink->subLinkType == ALL_SUBLINK ||
288 slink->subLinkType == ANY_SUBLINK)
289 tuple_fraction = 0.5; /* 50% */
291 tuple_fraction = 0.0; /* default behavior */
294 * Generate the plan for the subquery.
296 node->plan = plan = subquery_planner(subquery, tuple_fraction);
298 node->plan_id = PlannerPlanId++; /* Assign unique ID to this
301 node->rtable = subquery->rtable;
304 * Initialize other fields of the SubPlan node.
306 node->subLinkType = slink->subLinkType;
307 node->useOr = slink->useOr;
309 node->paramIds = NIL;
310 node->useHashTable = false;
311 /* At top level of a qual, can treat UNKNOWN the same as FALSE */
312 node->unknownEqFalse = isTopQual;
313 node->setParam = NIL;
314 node->parParam = NIL;
318 * Make parParam list of params that current query level will pass to
321 tmpset = bms_copy(plan->extParam);
322 while ((paramid = bms_first_member(tmpset)) >= 0)
324 PlannerParamItem *pitem = nth(paramid, PlannerParamList);
326 if (pitem->abslevel == PlannerQueryLevel)
327 node->parParam = lappendi(node->parParam, paramid);
332 * Un-correlated or undirect correlated plans of EXISTS, EXPR, ARRAY,
333 * or MULTIEXPR types can be used as initPlans. For EXISTS, EXPR, or
334 * ARRAY, we just produce a Param referring to the result of
335 * evaluating the initPlan. For MULTIEXPR, we must build an AND or
336 * OR-clause of the individual comparison operators, using the
337 * appropriate lefthand side expressions and Params for the initPlan's
340 if (node->parParam == NIL && slink->subLinkType == EXISTS_SUBLINK)
344 prm = generate_new_param(BOOLOID, -1);
345 node->setParam = makeListi1(prm->paramid);
346 PlannerInitPlan = lappend(PlannerInitPlan, node);
347 result = (Node *) prm;
349 else if (node->parParam == NIL && slink->subLinkType == EXPR_SUBLINK)
351 TargetEntry *te = lfirst(plan->targetlist);
354 Assert(!te->resdom->resjunk);
355 prm = generate_new_param(te->resdom->restype, te->resdom->restypmod);
356 node->setParam = makeListi1(prm->paramid);
357 PlannerInitPlan = lappend(PlannerInitPlan, node);
358 result = (Node *) prm;
360 else if (node->parParam == NIL && slink->subLinkType == ARRAY_SUBLINK)
362 TargetEntry *te = lfirst(plan->targetlist);
366 Assert(!te->resdom->resjunk);
367 arraytype = get_array_type(te->resdom->restype);
368 if (!OidIsValid(arraytype))
369 elog(ERROR, "could not find array type for datatype %s",
370 format_type_be(te->resdom->restype));
371 prm = generate_new_param(arraytype, -1);
372 node->setParam = makeListi1(prm->paramid);
373 PlannerInitPlan = lappend(PlannerInitPlan, node);
374 result = (Node *) prm;
376 else if (node->parParam == NIL && slink->subLinkType == MULTIEXPR_SUBLINK)
380 /* Convert the lefthand exprs and oper OIDs into executable exprs */
381 exprs = convert_sublink_opers(lefthand,
386 node->setParam = listCopy(node->paramIds);
387 PlannerInitPlan = lappend(PlannerInitPlan, node);
390 * The executable expressions are returned to become part of the
391 * outer plan's expression tree; they are not kept in the initplan
394 if (length(exprs) > 1)
395 result = (Node *) (node->useOr ? make_orclause(exprs) :
396 make_andclause(exprs));
398 result = (Node *) lfirst(exprs);
405 * We can't convert subplans of ALL_SUBLINK or ANY_SUBLINK types
406 * to initPlans, even when they are uncorrelated or undirect
407 * correlated, because we need to scan the output of the subplan
408 * for each outer tuple. But if it's an IN (= ANY) test, we might
409 * be able to use a hashtable to avoid comparing all the tuples.
411 if (subplan_is_hashable(slink, node))
412 node->useHashTable = true;
415 * Otherwise, we have the option to tack a MATERIAL node onto the
416 * top of the subplan, to reduce the cost of reading it
417 * repeatedly. This is pointless for a direct-correlated subplan,
418 * since we'd have to recompute its results each time anyway. For
419 * uncorrelated/undirect correlated subplans, we add MATERIAL if
420 * the subplan's top plan node is anything more complicated than a
421 * plain sequential scan, and we do it even for seqscan if the
422 * qual appears selective enough to eliminate many tuples.
424 else if (node->parParam == NIL)
428 switch (nodeTag(plan))
437 qualsel = clauselist_selectivity(subquery,
440 /* Is 10% selectivity a good threshold?? */
441 use_material = qualsel < 0.10;
449 * Don't add another Material node if there's one
450 * already, nor if the top node is any other type that
451 * materializes its output anyway.
453 use_material = false;
460 node->plan = plan = materialize_finished_plan(plan);
463 /* Convert the lefthand exprs and oper OIDs into executable exprs */
464 node->exprs = convert_sublink_opers(lefthand,
471 * Make node->args from parParam.
474 foreach(lst, node->parParam)
476 PlannerParamItem *pitem = nth(lfirsti(lst), PlannerParamList);
479 * The Var or Aggref has already been adjusted to have the
480 * correct varlevelsup or agglevelsup. We probably don't even
481 * need to copy it again, but be safe.
483 args = lappend(args, copyObject(pitem->item));
487 result = (Node *) node;
494 * convert_sublink_opers: given a lefthand-expressions list and a list of
495 * operator OIDs, build a list of actually executable expressions. The
496 * righthand sides of the expressions are Params or Vars representing the
497 * results of the sub-select.
499 * If rtindex is 0, we build Params to represent the sub-select outputs.
500 * The paramids of the Params created are returned in the *righthandIds list.
502 * If rtindex is not 0, we build Vars using that rtindex as varno. Copies
503 * of the Var nodes are returned in *righthandIds (this is a bit of a type
504 * cheat, but we can get away with it).
507 convert_sublink_opers(List *lefthand, List *operOids,
508 List *targetlist, int rtindex,
516 foreach(lst, operOids)
518 Oid opid = lfirsto(lst);
519 Node *leftop = lfirst(lefthand);
520 TargetEntry *te = lfirst(targetlist);
524 Assert(!te->resdom->resjunk);
528 /* Make the Var node representing the subplan's result */
529 rightop = (Node *) makeVar(rtindex,
532 te->resdom->restypmod,
535 * Copy it for caller. NB: we need a copy to avoid having
536 * doubly-linked substructure in the modified parse tree.
538 *righthandIds = lappend(*righthandIds, copyObject(rightop));
542 /* Make the Param node representing the subplan's result */
545 prm = generate_new_param(te->resdom->restype,
546 te->resdom->restypmod);
548 *righthandIds = lappendi(*righthandIds, prm->paramid);
549 rightop = (Node *) prm;
552 /* Look up the operator to pass to make_op_expr */
553 tup = SearchSysCache(OPEROID,
554 ObjectIdGetDatum(opid),
556 if (!HeapTupleIsValid(tup))
557 elog(ERROR, "cache lookup failed for operator %u", opid);
560 * Make the expression node.
562 * Note: we use make_op_expr in case runtime type conversion function
563 * calls must be inserted for this operator! (But we are not
564 * expecting to have to resolve unknown Params, so it's okay to
565 * pass a null pstate.)
567 result = lappend(result,
573 te->resdom->restype));
575 ReleaseSysCache(tup);
577 lefthand = lnext(lefthand);
578 targetlist = lnext(targetlist);
585 * subplan_is_hashable: decide whether we can implement a subplan by hashing
587 * Caution: the SubPlan node is not completely filled in yet. We can rely
588 * on its plan and parParam fields, however.
591 subplan_is_hashable(SubLink *slink, SubPlan *node)
593 double subquery_size;
597 * The sublink type must be "= ANY" --- that is, an IN operator. (We
598 * require the operator name to be unqualified, which may be overly
599 * paranoid, or may not be.) XXX since we also check that the
600 * operators are hashable, the test on operator name may be redundant?
602 if (slink->subLinkType != ANY_SUBLINK)
604 if (length(slink->operName) != 1 ||
605 strcmp(strVal(lfirst(slink->operName)), "=") != 0)
609 * The subplan must not have any direct correlation vars --- else we'd
610 * have to recompute its output each time, so that the hashtable
611 * wouldn't gain anything.
613 if (node->parParam != NIL)
617 * The estimated size of the subquery result must fit in work_mem. (XXX
618 * what about hashtable overhead?)
620 subquery_size = node->plan->plan_rows *
621 (MAXALIGN(node->plan->plan_width) + MAXALIGN(sizeof(HeapTupleData)));
622 if (subquery_size > work_mem * 1024L)
626 * The combining operators must be hashable, strict, and
627 * self-commutative. The need for hashability is obvious, since we
628 * want to use hashing. Without strictness, behavior in the presence
629 * of nulls is too unpredictable. (We actually must assume even more
630 * than plain strictness, see nodeSubplan.c for details.) And
631 * commutativity ensures that the left and right datatypes are the
632 * same; this allows us to assume that the combining operators are
633 * equality for the righthand datatype, so that they can be used to
634 * compare righthand tuples as well as comparing lefthand to righthand
635 * tuples. (This last restriction could be relaxed by using two
636 * different sets of operators with the hash table, but there is no
637 * obvious usefulness to that at present.)
639 foreach(opids, slink->operOids)
641 Oid opid = lfirsto(opids);
643 Form_pg_operator optup;
645 tup = SearchSysCache(OPEROID,
646 ObjectIdGetDatum(opid),
648 if (!HeapTupleIsValid(tup))
649 elog(ERROR, "cache lookup failed for operator %u", opid);
650 optup = (Form_pg_operator) GETSTRUCT(tup);
651 if (!optup->oprcanhash || optup->oprcom != opid ||
652 !func_strict(optup->oprcode))
654 ReleaseSysCache(tup);
657 ReleaseSysCache(tup);
663 * convert_IN_to_join: can we convert an IN SubLink to join style?
665 * The caller has found a SubLink at the top level of WHERE, but has not
666 * checked the properties of the SubLink at all. Decide whether it is
667 * appropriate to process this SubLink in join style. If not, return NULL.
668 * If so, build the qual clause(s) to replace the SubLink, and return them.
670 * Side effects of a successful conversion include adding the SubLink's
671 * subselect to the query's rangetable and adding an InClauseInfo node to
675 convert_IN_to_join(Query *parse, SubLink *sublink)
677 Query *subselect = (Query *) sublink->subselect;
682 InClauseInfo *ininfo;
686 * The sublink type must be "= ANY" --- that is, an IN operator. (We
687 * require the operator name to be unqualified, which may be overly
688 * paranoid, or may not be.)
690 if (sublink->subLinkType != ANY_SUBLINK)
692 if (length(sublink->operName) != 1 ||
693 strcmp(strVal(lfirst(sublink->operName)), "=") != 0)
697 * The sub-select must not refer to any Vars of the parent query.
698 * (Vars of higher levels should be okay, though.)
700 if (contain_vars_of_level((Node *) subselect, 1))
704 * The left-hand expressions must contain some Vars of the current
705 * query, else it's not gonna be a join.
707 left_varnos = pull_varnos((Node *) sublink->lefthand);
708 if (bms_is_empty(left_varnos))
712 * The left-hand expressions mustn't be volatile. (Perhaps we should
713 * test the combining operators, too? We'd only need to point the
714 * function directly at the sublink ...)
716 if (contain_volatile_functions((Node *) sublink->lefthand))
720 * Okay, pull up the sub-select into top range table and jointree.
722 * We rely here on the assumption that the outer query has no references
723 * to the inner (necessarily true, other than the Vars that we build
724 * below). Therefore this is a lot easier than what
725 * pull_up_subqueries has to go through.
727 rte = addRangeTableEntryForSubquery(NULL,
729 makeAlias("IN_subquery", NIL),
731 parse->rtable = lappend(parse->rtable, rte);
732 rtindex = length(parse->rtable);
733 rtr = makeNode(RangeTblRef);
734 rtr->rtindex = rtindex;
735 parse->jointree->fromlist = lappend(parse->jointree->fromlist, rtr);
738 * Now build the InClauseInfo node.
740 ininfo = makeNode(InClauseInfo);
741 ininfo->lefthand = left_varnos;
742 ininfo->righthand = bms_make_singleton(rtindex);
743 parse->in_info_list = lcons(ininfo, parse->in_info_list);
746 * Build the result qual expressions. As a side effect,
747 * ininfo->sub_targetlist is filled with a list of Vars
748 * representing the subselect outputs.
750 exprs = convert_sublink_opers(sublink->lefthand,
752 subselect->targetList,
754 &ininfo->sub_targetlist);
755 return (Node *) make_ands_explicit(exprs);
759 * Replace correlation vars (uplevel vars) with Params.
761 * Uplevel aggregates are replaced, too.
763 * Note: it is critical that this runs immediately after SS_process_sublinks.
764 * Since we do not recurse into the arguments of uplevel aggregates, they will
765 * get copied to the appropriate subplan args list in the parent query with
766 * uplevel vars not replaced by Params, but only adjusted in level (see
767 * replace_outer_agg). That's exactly what we want for the vars of the parent
768 * level --- but if an aggregate's argument contains any further-up variables,
769 * they have to be replaced with Params in their turn. That will happen when
770 * the parent level runs SS_replace_correlation_vars. Therefore it must do
771 * so after expanding its sublinks to subplans. And we don't want any steps
772 * in between, else those steps would never get applied to the aggregate
773 * argument expressions, either in the parent or the child level.
776 SS_replace_correlation_vars(Node *expr)
778 /* No setup needed for tree walk, so away we go */
779 return replace_correlation_vars_mutator(expr, NULL);
783 replace_correlation_vars_mutator(Node *node, void *context)
789 if (((Var *) node)->varlevelsup > 0)
790 return (Node *) replace_outer_var((Var *) node);
792 if (IsA(node, Aggref))
794 if (((Aggref *) node)->agglevelsup > 0)
795 return (Node *) replace_outer_agg((Aggref *) node);
797 return expression_tree_mutator(node,
798 replace_correlation_vars_mutator,
803 * Expand SubLinks to SubPlans in the given expression.
805 * The isQual argument tells whether or not this expression is a WHERE/HAVING
806 * qualifier expression. If it is, any sublinks appearing at top level need
807 * not distinguish FALSE from UNKNOWN return values.
810 SS_process_sublinks(Node *expr, bool isQual)
812 /* The only context needed is the initial are-we-in-a-qual flag */
813 return process_sublinks_mutator(expr, &isQual);
817 process_sublinks_mutator(Node *node, bool *isTopQual)
823 if (IsA(node, SubLink))
825 SubLink *sublink = (SubLink *) node;
829 * First, recursively process the lefthand-side expressions, if
834 process_sublinks_mutator((Node *) sublink->lefthand, &locTopQual);
837 * Now build the SubPlan node and make the expr to return.
839 return make_subplan(sublink, lefthand, *isTopQual);
843 * We should never see a SubPlan expression in the input (since this
844 * is the very routine that creates 'em to begin with). We shouldn't
845 * find ourselves invoked directly on a Query, either.
847 Assert(!is_subplan(node));
848 Assert(!IsA(node, Query));
851 * Because make_subplan() could return an AND or OR clause, we have to
852 * take steps to preserve AND/OR flatness of a qual. We assume the input
853 * has been AND/OR flattened and so we need no recursion here.
855 * If we recurse down through anything other than an AND node,
856 * we are definitely not at top qual level anymore. (Due to the coding
857 * here, we will not get called on the List subnodes of an AND, so no
858 * check is needed for List.)
860 if (and_clause(node))
865 /* Still at qual top-level */
866 locTopQual = *isTopQual;
868 foreach(l, ((BoolExpr *) node)->args)
872 newarg = process_sublinks_mutator(lfirst(l),
873 (void *) &locTopQual);
874 if (and_clause(newarg))
875 newargs = nconc(newargs, ((BoolExpr *) newarg)->args);
877 newargs = lappend(newargs, newarg);
879 return (Node *) make_andclause(newargs);
882 /* otherwise not at qual top-level */
890 foreach(l, ((BoolExpr *) node)->args)
894 newarg = process_sublinks_mutator(lfirst(l),
895 (void *) &locTopQual);
896 if (or_clause(newarg))
897 newargs = nconc(newargs, ((BoolExpr *) newarg)->args);
899 newargs = lappend(newargs, newarg);
901 return (Node *) make_orclause(newargs);
904 return expression_tree_mutator(node,
905 process_sublinks_mutator,
906 (void *) &locTopQual);
910 * SS_finalize_plan - do final sublink processing for a completed Plan.
912 * This recursively computes the extParam and allParam sets
913 * for every Plan node in the given plan tree.
916 SS_finalize_plan(Plan *plan, List *rtable)
918 Bitmapset *outer_params = NULL;
919 Bitmapset *valid_params = NULL;
924 * First, scan the param list to discover the sets of params that are
925 * available from outer query levels and my own query level. We do
926 * this once to save time in the per-plan recursion steps.
929 foreach(lst, PlannerParamList)
931 PlannerParamItem *pitem = (PlannerParamItem *) lfirst(lst);
933 if (pitem->abslevel < PlannerQueryLevel)
935 /* valid outer-level parameter */
936 outer_params = bms_add_member(outer_params, paramid);
937 valid_params = bms_add_member(valid_params, paramid);
939 else if (pitem->abslevel == PlannerQueryLevel &&
940 IsA(pitem->item, Param))
942 /* valid local parameter (i.e., a setParam of my child) */
943 valid_params = bms_add_member(valid_params, paramid);
950 * Now recurse through plan tree.
952 (void) finalize_plan(plan, rtable, outer_params, valid_params);
954 bms_free(outer_params);
955 bms_free(valid_params);
959 * Recursive processing of all nodes in the plan tree
961 * The return value is the computed allParam set for the given Plan node.
962 * This is just an internal notational convenience.
965 finalize_plan(Plan *plan, List *rtable,
966 Bitmapset *outer_params, Bitmapset *valid_params)
968 finalize_primnode_context context;
974 context.paramids = NULL; /* initialize set to empty */
975 context.outer_params = outer_params;
978 * When we call finalize_primnode, context.paramids sets are
979 * automatically merged together. But when recursing to self, we have
980 * to do it the hard way. We want the paramids set to include params
981 * in subplans as well as at this level.
984 /* Find params in targetlist and qual */
985 finalize_primnode((Node *) plan->targetlist, &context);
986 finalize_primnode((Node *) plan->qual, &context);
988 /* Check additional node-type-specific fields */
989 switch (nodeTag(plan))
992 finalize_primnode(((Result *) plan)->resconstantqual,
997 finalize_primnode((Node *) ((IndexScan *) plan)->indxqual,
1001 * we need not look at indxqualorig, since it will have the
1002 * same param references as indxqual.
1007 finalize_primnode((Node *) ((TidScan *) plan)->tideval,
1011 case T_SubqueryScan:
1014 * In a SubqueryScan, SS_finalize_plan has already been run on
1015 * the subplan by the inner invocation of subquery_planner, so
1016 * there's no need to do it again. Instead, just pull out the
1017 * subplan's extParams list, which represents the params it
1018 * needs from my level and higher levels.
1020 context.paramids = bms_add_members(context.paramids,
1021 ((SubqueryScan *) plan)->subplan->extParam);
1024 case T_FunctionScan:
1028 rte = rt_fetch(((FunctionScan *) plan)->scan.scanrelid,
1030 Assert(rte->rtekind == RTE_FUNCTION);
1031 finalize_primnode(rte->funcexpr, &context);
1036 foreach(lst, ((Append *) plan)->appendplans)
1039 bms_add_members(context.paramids,
1040 finalize_plan((Plan *) lfirst(lst),
1048 finalize_primnode((Node *) ((Join *) plan)->joinqual,
1053 finalize_primnode((Node *) ((Join *) plan)->joinqual,
1055 finalize_primnode((Node *) ((MergeJoin *) plan)->mergeclauses,
1060 finalize_primnode((Node *) ((Join *) plan)->joinqual,
1062 finalize_primnode((Node *) ((HashJoin *) plan)->hashclauses,
1078 elog(ERROR, "unrecognized node type: %d",
1079 (int) nodeTag(plan));
1082 /* Process left and right child plans, if any */
1083 context.paramids = bms_add_members(context.paramids,
1084 finalize_plan(plan->lefttree,
1089 context.paramids = bms_add_members(context.paramids,
1090 finalize_plan(plan->righttree,
1095 /* Now we have all the paramids */
1097 if (!bms_is_subset(context.paramids, valid_params))
1098 elog(ERROR, "plan should not reference subplan's variable");
1100 plan->extParam = bms_intersect(context.paramids, outer_params);
1101 plan->allParam = context.paramids;
1104 * For speed at execution time, make sure extParam/allParam are
1105 * actually NULL if they are empty sets.
1107 if (bms_is_empty(plan->extParam))
1109 bms_free(plan->extParam);
1110 plan->extParam = NULL;
1112 if (bms_is_empty(plan->allParam))
1114 bms_free(plan->allParam);
1115 plan->allParam = NULL;
1118 return plan->allParam;
1122 * finalize_primnode: add IDs of all PARAM_EXEC params appearing in the given
1123 * expression tree to the result set.
1126 finalize_primnode(Node *node, finalize_primnode_context *context)
1130 if (IsA(node, Param))
1132 if (((Param *) node)->paramkind == PARAM_EXEC)
1134 int paramid = (int) ((Param *) node)->paramid;
1136 context->paramids = bms_add_member(context->paramids, paramid);
1138 return false; /* no more to do here */
1140 if (is_subplan(node))
1142 SubPlan *subplan = (SubPlan *) node;
1144 /* Add outer-level params needed by the subplan to paramids */
1145 context->paramids = bms_join(context->paramids,
1146 bms_intersect(subplan->plan->extParam,
1147 context->outer_params));
1148 /* fall through to recurse into subplan args */
1150 return expression_tree_walker(node, finalize_primnode,