1 /*-------------------------------------------------------------------------
4 * Planning routines for subselects and parameters.
6 * Portions Copyright (c) 1996-2007, 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.116 2007/01/05 22:19:32 momjian 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 "optimizer/clauses.h"
21 #include "optimizer/planmain.h"
22 #include "optimizer/planner.h"
23 #include "optimizer/subselect.h"
24 #include "optimizer/var.h"
25 #include "parser/parse_expr.h"
26 #include "parser/parse_relation.h"
27 #include "parser/parsetree.h"
28 #include "rewrite/rewriteManip.h"
29 #include "utils/builtins.h"
30 #include "utils/lsyscache.h"
31 #include "utils/syscache.h"
34 Index PlannerQueryLevel; /* level of current query */
35 List *PlannerInitPlan; /* init subplans for current query */
36 List *PlannerParamList; /* to keep track of cross-level Params */
38 int PlannerPlanId = 0; /* to assign unique ID to subquery plans */
41 * PlannerParamList keeps track of the PARAM_EXEC slots that we have decided
42 * we need for the query. At runtime these slots are used to pass values
43 * either down into subqueries (for outer references in subqueries) or up out
44 * of subqueries (for the results of a subplan). The n'th entry in the list
45 * (n counts from 0) corresponds to Param->paramid = n.
47 * Each ParamList item shows the absolute query level it is associated with,
48 * where the outermost query is level 1 and nested subqueries have higher
49 * numbers. The item the parameter slot represents can be one of three kinds:
51 * A Var: the slot represents a variable of that level that must be passed
52 * down because subqueries have outer references to it. The varlevelsup
53 * value in the Var will always be zero.
55 * An Aggref (with an expression tree representing its argument): the slot
56 * represents an aggregate expression that is an outer reference for some
57 * subquery. The Aggref itself has agglevelsup = 0, and its argument tree
58 * is adjusted to match in level.
60 * A Param: the slot holds the result of a subplan (it is a setParam item
61 * for that subplan). The absolute level shown for such items corresponds
62 * to the parent query of the subplan.
64 * Note: we detect duplicate Var parameters and coalesce them into one slot,
65 * but we do not do this for Aggref or Param slots.
67 typedef struct PlannerParamItem
69 Node *item; /* the Var, Aggref, or Param */
70 Index abslevel; /* its absolute query level */
74 typedef struct convert_testexpr_context
76 int rtindex; /* RT index for Vars, or 0 for Params */
77 List *righthandIds; /* accumulated list of Vars or Param IDs */
78 } convert_testexpr_context;
80 typedef struct finalize_primnode_context
82 Bitmapset *paramids; /* Set of PARAM_EXEC paramids found */
83 Bitmapset *outer_params; /* Set of accessible outer paramids */
84 } finalize_primnode_context;
87 static Node *convert_testexpr(Node *testexpr,
90 static Node *convert_testexpr_mutator(Node *node,
91 convert_testexpr_context *context);
92 static bool subplan_is_hashable(SubLink *slink, SubPlan *node);
93 static bool hash_ok_operator(OpExpr *expr);
94 static Node *replace_correlation_vars_mutator(Node *node, void *context);
95 static Node *process_sublinks_mutator(Node *node, bool *isTopQual);
96 static Bitmapset *finalize_plan(Plan *plan, List *rtable,
97 Bitmapset *outer_params,
98 Bitmapset *valid_params);
99 static bool finalize_primnode(Node *node, finalize_primnode_context *context);
103 * Generate a Param node to replace the given Var,
104 * which is expected to have varlevelsup > 0 (ie, it is not local).
107 replace_outer_var(Var *var)
111 PlannerParamItem *pitem;
115 Assert(var->varlevelsup > 0 && var->varlevelsup < PlannerQueryLevel);
116 abslevel = PlannerQueryLevel - var->varlevelsup;
119 * If there's already a PlannerParamList entry for this same Var, just use
120 * it. NOTE: in sufficiently complex querytrees, it is possible for the
121 * same varno/abslevel to refer to different RTEs in different parts of
122 * the parsetree, so that different fields might end up sharing the same
123 * Param number. As long as we check the vartype as well, I believe that
124 * this sort of aliasing will cause no trouble. The correct field should
125 * get stored into the Param slot at execution in each part of the tree.
127 * We also need to demand a match on vartypmod. This does not matter for
128 * the Param itself, since those are not typmod-dependent, but it does
129 * matter when make_subplan() instantiates a modified copy of the Var for
130 * a subplan's args list.
133 foreach(ppl, PlannerParamList)
135 pitem = (PlannerParamItem *) lfirst(ppl);
136 if (pitem->abslevel == abslevel && IsA(pitem->item, Var))
138 Var *pvar = (Var *) pitem->item;
140 if (pvar->varno == var->varno &&
141 pvar->varattno == var->varattno &&
142 pvar->vartype == var->vartype &&
143 pvar->vartypmod == var->vartypmod)
151 /* Nope, so make a new one */
152 var = (Var *) copyObject(var);
153 var->varlevelsup = 0;
155 pitem = (PlannerParamItem *) palloc(sizeof(PlannerParamItem));
156 pitem->item = (Node *) var;
157 pitem->abslevel = abslevel;
159 PlannerParamList = lappend(PlannerParamList, pitem);
160 /* i is already the correct index for the new item */
163 retval = makeNode(Param);
164 retval->paramkind = PARAM_EXEC;
166 retval->paramtype = var->vartype;
167 retval->paramtypmod = var->vartypmod;
173 * Generate a Param node to replace the given Aggref
174 * which is expected to have agglevelsup > 0 (ie, it is not local).
177 replace_outer_agg(Aggref *agg)
180 PlannerParamItem *pitem;
184 Assert(agg->agglevelsup > 0 && agg->agglevelsup < PlannerQueryLevel);
185 abslevel = PlannerQueryLevel - agg->agglevelsup;
188 * It does not seem worthwhile to try to match duplicate outer aggs. Just
189 * make a new slot every time.
191 agg = (Aggref *) copyObject(agg);
192 IncrementVarSublevelsUp((Node *) agg, -((int) agg->agglevelsup), 0);
193 Assert(agg->agglevelsup == 0);
195 pitem = (PlannerParamItem *) palloc(sizeof(PlannerParamItem));
196 pitem->item = (Node *) agg;
197 pitem->abslevel = abslevel;
199 PlannerParamList = lappend(PlannerParamList, pitem);
200 i = list_length(PlannerParamList) - 1;
202 retval = makeNode(Param);
203 retval->paramkind = PARAM_EXEC;
205 retval->paramtype = agg->aggtype;
206 retval->paramtypmod = -1;
212 * Generate a new Param node that will not conflict with any other.
214 * This is used to allocate PARAM_EXEC slots for subplan outputs.
217 generate_new_param(Oid paramtype, int32 paramtypmod)
220 PlannerParamItem *pitem;
222 retval = makeNode(Param);
223 retval->paramkind = PARAM_EXEC;
224 retval->paramid = list_length(PlannerParamList);
225 retval->paramtype = paramtype;
226 retval->paramtypmod = paramtypmod;
228 pitem = (PlannerParamItem *) palloc(sizeof(PlannerParamItem));
229 pitem->item = (Node *) retval;
230 pitem->abslevel = PlannerQueryLevel;
232 PlannerParamList = lappend(PlannerParamList, pitem);
238 * Convert a SubLink (as created by the parser) into a SubPlan.
240 * We are given the original SubLink and the already-processed testexpr
241 * (use this instead of the SubLink's own field). We are also told if
242 * this expression appears at top level of a WHERE/HAVING qual.
244 * The result is whatever we need to substitute in place of the SubLink
245 * node in the executable expression. This will be either the SubPlan
246 * node (if we have to do the subplan as a subplan), or a Param node
247 * representing the result of an InitPlan, or a row comparison expression
248 * tree containing InitPlan Param nodes.
251 make_subplan(SubLink *slink, Node *testexpr, bool isTopQual)
253 SubPlan *node = makeNode(SubPlan);
254 Query *subquery = (Query *) (slink->subselect);
255 double tuple_fraction;
262 * Copy the source Query node. This is a quick and dirty kluge to resolve
263 * the fact that the parser can generate trees with multiple links to the
264 * same sub-Query node, but the planner wants to scribble on the Query.
265 * Try to clean this up when we do querytree redesign...
267 subquery = (Query *) copyObject(subquery);
270 * For an EXISTS subplan, tell lower-level planner to expect that only the
271 * first tuple will be retrieved. For ALL and ANY subplans, we will be
272 * able to stop evaluating if the test condition fails, so very often not
273 * all the tuples will be retrieved; for lack of a better idea, specify
274 * 50% retrieval. For EXPR and ROWCOMPARE subplans, use default behavior
275 * (we're only expecting one row out, anyway).
277 * NOTE: if you change these numbers, also change cost_qual_eval_walker()
278 * in path/costsize.c.
280 * XXX If an ALL/ANY subplan is uncorrelated, we may decide to hash or
281 * materialize its result below. In that case it would've been better to
282 * specify full retrieval. At present, however, we can only detect
283 * correlation or lack of it after we've made the subplan :-(. Perhaps
284 * detection of correlation should be done as a separate step. Meanwhile,
285 * we don't want to be too optimistic about the percentage of tuples
286 * retrieved, for fear of selecting a plan that's bad for the
287 * materialization case.
289 if (slink->subLinkType == EXISTS_SUBLINK)
290 tuple_fraction = 1.0; /* just like a LIMIT 1 */
291 else if (slink->subLinkType == ALL_SUBLINK ||
292 slink->subLinkType == ANY_SUBLINK)
293 tuple_fraction = 0.5; /* 50% */
295 tuple_fraction = 0.0; /* default behavior */
298 * Generate the plan for the subquery.
300 node->plan = plan = subquery_planner(subquery, tuple_fraction, NULL);
302 node->plan_id = PlannerPlanId++; /* Assign unique ID to this SubPlan */
304 node->rtable = subquery->rtable;
307 * Initialize other fields of the SubPlan node.
309 node->subLinkType = slink->subLinkType;
310 node->testexpr = NULL;
311 node->paramIds = NIL;
312 node->useHashTable = false;
313 /* At top level of a qual, can treat UNKNOWN the same as FALSE */
314 node->unknownEqFalse = isTopQual;
315 node->setParam = NIL;
316 node->parParam = NIL;
320 * Make parParam list of params that current query level will pass to this
323 tmpset = bms_copy(plan->extParam);
324 while ((paramid = bms_first_member(tmpset)) >= 0)
326 PlannerParamItem *pitem = list_nth(PlannerParamList, paramid);
328 if (pitem->abslevel == PlannerQueryLevel)
329 node->parParam = lappend_int(node->parParam, paramid);
334 * Un-correlated or undirect correlated plans of EXISTS, EXPR, ARRAY, or
335 * ROWCOMPARE types can be used as initPlans. For EXISTS, EXPR, or ARRAY,
336 * we just produce a Param referring to the result of evaluating the
337 * initPlan. For ROWCOMPARE, we must modify the testexpr tree to contain
338 * PARAM_EXEC Params instead of the PARAM_SUBLINK Params emitted by the
341 if (node->parParam == NIL && slink->subLinkType == EXISTS_SUBLINK)
345 prm = generate_new_param(BOOLOID, -1);
346 node->setParam = list_make1_int(prm->paramid);
347 PlannerInitPlan = lappend(PlannerInitPlan, node);
348 result = (Node *) prm;
350 else if (node->parParam == NIL && slink->subLinkType == EXPR_SUBLINK)
352 TargetEntry *te = linitial(plan->targetlist);
355 Assert(!te->resjunk);
356 prm = generate_new_param(exprType((Node *) te->expr),
357 exprTypmod((Node *) te->expr));
358 node->setParam = list_make1_int(prm->paramid);
359 PlannerInitPlan = lappend(PlannerInitPlan, node);
360 result = (Node *) prm;
362 else if (node->parParam == NIL && slink->subLinkType == ARRAY_SUBLINK)
364 TargetEntry *te = linitial(plan->targetlist);
368 Assert(!te->resjunk);
369 arraytype = get_array_type(exprType((Node *) te->expr));
370 if (!OidIsValid(arraytype))
371 elog(ERROR, "could not find array type for datatype %s",
372 format_type_be(exprType((Node *) te->expr)));
373 prm = generate_new_param(arraytype, exprTypmod((Node *) te->expr));
374 node->setParam = list_make1_int(prm->paramid);
375 PlannerInitPlan = lappend(PlannerInitPlan, node);
376 result = (Node *) prm;
378 else if (node->parParam == NIL && slink->subLinkType == ROWCOMPARE_SUBLINK)
380 /* Adjust the Params */
381 result = convert_testexpr(testexpr,
384 node->setParam = list_copy(node->paramIds);
385 PlannerInitPlan = lappend(PlannerInitPlan, node);
388 * The executable expression is returned to become part of the outer
389 * plan's expression tree; it is not kept in the initplan node.
397 /* Adjust the Params */
398 node->testexpr = convert_testexpr(testexpr,
403 * We can't convert subplans of ALL_SUBLINK or ANY_SUBLINK types to
404 * initPlans, even when they are uncorrelated or undirect correlated,
405 * because we need to scan the output of the subplan for each outer
406 * tuple. But if it's an IN (= ANY) test, we might be able to use a
407 * hashtable to avoid comparing all the tuples.
409 if (subplan_is_hashable(slink, node))
410 node->useHashTable = true;
413 * Otherwise, we have the option to tack a MATERIAL node onto the top
414 * of the subplan, to reduce the cost of reading it repeatedly. This
415 * is pointless for a direct-correlated subplan, since we'd have to
416 * recompute its results each time anyway. For uncorrelated/undirect
417 * correlated subplans, we add MATERIAL unless the subplan's top plan
418 * node would materialize its output anyway.
420 else if (node->parParam == NIL)
424 switch (nodeTag(plan))
429 use_material = false;
436 node->plan = plan = materialize_finished_plan(plan);
440 * Make node->args from parParam.
443 foreach(l, node->parParam)
445 PlannerParamItem *pitem = list_nth(PlannerParamList, lfirst_int(l));
448 * The Var or Aggref has already been adjusted to have the correct
449 * varlevelsup or agglevelsup. We probably don't even need to
450 * copy it again, but be safe.
452 args = lappend(args, copyObject(pitem->item));
456 result = (Node *) node;
463 * convert_testexpr: convert the testexpr given by the parser into
464 * actually executable form. This entails replacing PARAM_SUBLINK Params
465 * with Params or Vars representing the results of the sub-select:
467 * If rtindex is 0, we build Params to represent the sub-select outputs.
468 * The paramids of the Params created are returned in the *righthandIds list.
470 * If rtindex is not 0, we build Vars using that rtindex as varno. Copies
471 * of the Var nodes are returned in *righthandIds (this is a bit of a type
472 * cheat, but we can get away with it).
474 * The given testexpr has already been recursively processed by
475 * process_sublinks_mutator. Hence it can no longer contain any
476 * PARAM_SUBLINK Params for lower SubLink nodes; we can safely assume that
477 * any we find are for our own level of SubLink.
480 convert_testexpr(Node *testexpr,
485 convert_testexpr_context context;
487 context.rtindex = rtindex;
488 context.righthandIds = NIL;
489 result = convert_testexpr_mutator(testexpr, &context);
490 *righthandIds = context.righthandIds;
495 convert_testexpr_mutator(Node *node,
496 convert_testexpr_context *context)
500 if (IsA(node, Param))
502 Param *param = (Param *) node;
504 if (param->paramkind == PARAM_SUBLINK)
507 * We expect to encounter the Params in column-number sequence. We
508 * could handle non-sequential order if necessary, but for now
509 * there's no need. (This is also a useful cross-check that we
510 * aren't finding any unexpected Params.)
512 if (param->paramid != list_length(context->righthandIds) + 1)
513 elog(ERROR, "unexpected PARAM_SUBLINK ID: %d", param->paramid);
515 if (context->rtindex)
517 /* Make the Var node representing the subplan's result */
520 newvar = makeVar(context->rtindex,
527 * Copy it for caller. NB: we need a copy to avoid having
528 * doubly-linked substructure in the modified parse tree.
530 context->righthandIds = lappend(context->righthandIds,
532 return (Node *) newvar;
536 /* Make the Param node representing the subplan's result */
539 newparam = generate_new_param(param->paramtype,
542 context->righthandIds = lappend_int(context->righthandIds,
544 return (Node *) newparam;
548 return expression_tree_mutator(node,
549 convert_testexpr_mutator,
554 * subplan_is_hashable: decide whether we can implement a subplan by hashing
556 * Caution: the SubPlan node is not completely filled in yet. We can rely
557 * on its plan and parParam fields, however.
560 subplan_is_hashable(SubLink *slink, SubPlan *node)
562 double subquery_size;
566 * The sublink type must be "= ANY" --- that is, an IN operator. We
567 * expect that the test expression will be either a single OpExpr, or an
568 * AND-clause containing OpExprs. (If it's anything else then the parser
569 * must have determined that the operators have non-equality-like
570 * semantics. In the OpExpr case we can't be sure what the operator's
571 * semantics are like, but the test below for hashability will reject
572 * anything that's not equality.)
574 if (slink->subLinkType != ANY_SUBLINK)
576 if (slink->testexpr == NULL ||
577 (!IsA(slink->testexpr, OpExpr) &&
578 !and_clause(slink->testexpr)))
582 * The subplan must not have any direct correlation vars --- else we'd
583 * have to recompute its output each time, so that the hashtable wouldn't
586 if (node->parParam != NIL)
590 * The estimated size of the subquery result must fit in work_mem. (Note:
591 * we use sizeof(HeapTupleHeaderData) here even though the tuples will
592 * actually be stored as MinimalTuples; this provides some fudge factor
593 * for hashtable overhead.)
595 subquery_size = node->plan->plan_rows *
596 (MAXALIGN(node->plan->plan_width) + MAXALIGN(sizeof(HeapTupleHeaderData)));
597 if (subquery_size > work_mem * 1024L)
601 * The combining operators must be hashable, strict, and self-commutative.
602 * The need for hashability is obvious, since we want to use hashing.
603 * Without strictness, behavior in the presence of nulls is too
604 * unpredictable. (We actually must assume even more than plain
605 * strictness, see nodeSubplan.c for details.) And commutativity ensures
606 * that the left and right datatypes are the same; this allows us to
607 * assume that the combining operators are equality for the righthand
608 * datatype, so that they can be used to compare righthand tuples as well
609 * as comparing lefthand to righthand tuples. (This last restriction
610 * could be relaxed by using two different sets of operators with the hash
611 * table, but there is no obvious usefulness to that at present.)
613 if (IsA(slink->testexpr, OpExpr))
615 if (!hash_ok_operator((OpExpr *) slink->testexpr))
620 foreach(l, ((BoolExpr *) slink->testexpr)->args)
622 Node *andarg = (Node *) lfirst(l);
624 if (!IsA(andarg, OpExpr))
625 return false; /* probably can't happen */
626 if (!hash_ok_operator((OpExpr *) andarg))
635 hash_ok_operator(OpExpr *expr)
637 Oid opid = expr->opno;
639 Form_pg_operator optup;
641 tup = SearchSysCache(OPEROID,
642 ObjectIdGetDatum(opid),
644 if (!HeapTupleIsValid(tup))
645 elog(ERROR, "cache lookup failed for operator %u", opid);
646 optup = (Form_pg_operator) GETSTRUCT(tup);
647 if (!optup->oprcanhash || optup->oprcom != opid ||
648 !func_strict(optup->oprcode))
650 ReleaseSysCache(tup);
653 ReleaseSysCache(tup);
658 * convert_IN_to_join: can we convert an IN SubLink to join style?
660 * The caller has found a SubLink at the top level of WHERE, but has not
661 * checked the properties of the SubLink at all. Decide whether it is
662 * appropriate to process this SubLink in join style. If not, return NULL.
663 * If so, build the qual clause(s) to replace the SubLink, and return them.
665 * Side effects of a successful conversion include adding the SubLink's
666 * subselect to the query's rangetable and adding an InClauseInfo node to
670 convert_IN_to_join(PlannerInfo *root, SubLink *sublink)
672 Query *parse = root->parse;
673 Query *subselect = (Query *) sublink->subselect;
678 InClauseInfo *ininfo;
681 * The sublink type must be "= ANY" --- that is, an IN operator. We
682 * expect that the test expression will be either a single OpExpr, or an
683 * AND-clause containing OpExprs. (If it's anything else then the parser
684 * must have determined that the operators have non-equality-like
685 * semantics. In the OpExpr case we can't be sure what the operator's
686 * semantics are like, and must check for ourselves.)
688 if (sublink->subLinkType != ANY_SUBLINK)
690 if (sublink->testexpr && IsA(sublink->testexpr, OpExpr))
695 get_op_btree_interpretation(((OpExpr *) sublink->testexpr)->opno,
696 &opfamilies, &opstrats);
697 if (!list_member_int(opstrats, ROWCOMPARE_EQ))
700 else if (!and_clause(sublink->testexpr))
704 * The sub-select must not refer to any Vars of the parent query. (Vars of
705 * higher levels should be okay, though.)
707 if (contain_vars_of_level((Node *) subselect, 1))
711 * The left-hand expressions must contain some Vars of the current query,
712 * else it's not gonna be a join.
714 left_varnos = pull_varnos(sublink->testexpr);
715 if (bms_is_empty(left_varnos))
719 * The combining operators and left-hand expressions mustn't be volatile.
721 if (contain_volatile_functions(sublink->testexpr))
725 * Okay, pull up the sub-select into top range table and jointree.
727 * We rely here on the assumption that the outer query has no references
728 * to the inner (necessarily true, other than the Vars that we build
729 * below). Therefore this is a lot easier than what pull_up_subqueries has
732 rte = addRangeTableEntryForSubquery(NULL,
734 makeAlias("IN_subquery", NIL),
736 parse->rtable = lappend(parse->rtable, rte);
737 rtindex = list_length(parse->rtable);
738 rtr = makeNode(RangeTblRef);
739 rtr->rtindex = rtindex;
740 parse->jointree->fromlist = lappend(parse->jointree->fromlist, rtr);
743 * Now build the InClauseInfo node.
745 ininfo = makeNode(InClauseInfo);
746 ininfo->lefthand = left_varnos;
747 ininfo->righthand = bms_make_singleton(rtindex);
748 root->in_info_list = lappend(root->in_info_list, ininfo);
751 * Build the result qual expression. As a side effect,
752 * ininfo->sub_targetlist is filled with a list of Vars representing the
755 return convert_testexpr(sublink->testexpr,
757 &ininfo->sub_targetlist);
761 * Replace correlation vars (uplevel vars) with Params.
763 * Uplevel aggregates are replaced, too.
765 * Note: it is critical that this runs immediately after SS_process_sublinks.
766 * Since we do not recurse into the arguments of uplevel aggregates, they will
767 * get copied to the appropriate subplan args list in the parent query with
768 * uplevel vars not replaced by Params, but only adjusted in level (see
769 * replace_outer_agg). That's exactly what we want for the vars of the parent
770 * level --- but if an aggregate's argument contains any further-up variables,
771 * they have to be replaced with Params in their turn. That will happen when
772 * the parent level runs SS_replace_correlation_vars. Therefore it must do
773 * so after expanding its sublinks to subplans. And we don't want any steps
774 * in between, else those steps would never get applied to the aggregate
775 * argument expressions, either in the parent or the child level.
778 SS_replace_correlation_vars(Node *expr)
780 /* No setup needed for tree walk, so away we go */
781 return replace_correlation_vars_mutator(expr, NULL);
785 replace_correlation_vars_mutator(Node *node, void *context)
791 if (((Var *) node)->varlevelsup > 0)
792 return (Node *) replace_outer_var((Var *) node);
794 if (IsA(node, Aggref))
796 if (((Aggref *) node)->agglevelsup > 0)
797 return (Node *) replace_outer_agg((Aggref *) node);
799 return expression_tree_mutator(node,
800 replace_correlation_vars_mutator,
805 * Expand SubLinks to SubPlans in the given expression.
807 * The isQual argument tells whether or not this expression is a WHERE/HAVING
808 * qualifier expression. If it is, any sublinks appearing at top level need
809 * not distinguish FALSE from UNKNOWN return values.
812 SS_process_sublinks(Node *expr, bool isQual)
814 /* The only context needed is the initial are-we-in-a-qual flag */
815 return process_sublinks_mutator(expr, &isQual);
819 process_sublinks_mutator(Node *node, bool *isTopQual)
825 if (IsA(node, SubLink))
827 SubLink *sublink = (SubLink *) node;
831 * First, recursively process the lefthand-side expressions, if any.
834 testexpr = process_sublinks_mutator(sublink->testexpr, &locTopQual);
837 * Now build the SubPlan node and make the expr to return.
839 return make_subplan(sublink, testexpr, *isTopQual);
843 * We should never see a SubPlan expression in the input (since this is
844 * the very routine that creates 'em to begin with). We shouldn't find
845 * 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, we are
856 * definitely not at top qual level anymore. (Due to the coding here, we
857 * will not get called on the List subnodes of an AND, so no check is
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 = list_concat(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 = list_concat(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 for every Plan
913 * node in the given plan tree. It also attaches any generated InitPlans
914 * to the top plan node.
917 SS_finalize_plan(Plan *plan, List *rtable)
919 Bitmapset *outer_params,
928 * First, scan the param list to discover the sets of params that are
929 * available from outer query levels and my own query level. We do this
930 * once to save time in the per-plan recursion steps.
932 outer_params = valid_params = NULL;
934 foreach(l, PlannerParamList)
936 PlannerParamItem *pitem = (PlannerParamItem *) lfirst(l);
938 if (pitem->abslevel < PlannerQueryLevel)
940 /* valid outer-level parameter */
941 outer_params = bms_add_member(outer_params, paramid);
942 valid_params = bms_add_member(valid_params, paramid);
944 else if (pitem->abslevel == PlannerQueryLevel &&
945 IsA(pitem->item, Param))
947 /* valid local parameter (i.e., a setParam of my child) */
948 valid_params = bms_add_member(valid_params, paramid);
955 * Now recurse through plan tree.
957 (void) finalize_plan(plan, rtable, outer_params, valid_params);
959 bms_free(outer_params);
960 bms_free(valid_params);
963 * Finally, attach any initPlans to the topmost plan node, and add their
964 * extParams to the topmost node's, too. However, any setParams of the
965 * initPlans should not be present in the topmost node's extParams, only
966 * in its allParams. (As of PG 8.1, it's possible that some initPlans
967 * have extParams that are setParams of other initPlans, so we have to
968 * take care of this situation explicitly.)
970 * We also add the total_cost of each initPlan to the startup cost of the
971 * top node. This is a conservative overestimate, since in fact each
972 * initPlan might be executed later than plan startup, or even not at all.
974 plan->initPlan = PlannerInitPlan;
975 PlannerInitPlan = NIL; /* make sure they're not attached twice */
977 initExtParam = initSetParam = NULL;
979 foreach(l, plan->initPlan)
981 SubPlan *initplan = (SubPlan *) lfirst(l);
984 initExtParam = bms_add_members(initExtParam,
985 initplan->plan->extParam);
986 foreach(l2, initplan->setParam)
988 initSetParam = bms_add_member(initSetParam, lfirst_int(l2));
990 initplan_cost += initplan->plan->total_cost;
992 /* allParam must include all these params */
993 plan->allParam = bms_add_members(plan->allParam, initExtParam);
994 plan->allParam = bms_add_members(plan->allParam, initSetParam);
995 /* but extParam shouldn't include any setParams */
996 initExtParam = bms_del_members(initExtParam, initSetParam);
997 /* empty test ensures extParam is exactly NULL if it's empty */
998 if (!bms_is_empty(initExtParam))
999 plan->extParam = bms_join(plan->extParam, initExtParam);
1001 plan->startup_cost += initplan_cost;
1002 plan->total_cost += initplan_cost;
1006 * Recursive processing of all nodes in the plan tree
1008 * The return value is the computed allParam set for the given Plan node.
1009 * This is just an internal notational convenience.
1012 finalize_plan(Plan *plan, List *rtable,
1013 Bitmapset *outer_params, Bitmapset *valid_params)
1015 finalize_primnode_context context;
1020 context.paramids = NULL; /* initialize set to empty */
1021 context.outer_params = outer_params;
1024 * When we call finalize_primnode, context.paramids sets are automatically
1025 * merged together. But when recursing to self, we have to do it the hard
1026 * way. We want the paramids set to include params in subplans as well as
1030 /* Find params in targetlist and qual */
1031 finalize_primnode((Node *) plan->targetlist, &context);
1032 finalize_primnode((Node *) plan->qual, &context);
1034 /* Check additional node-type-specific fields */
1035 switch (nodeTag(plan))
1038 finalize_primnode(((Result *) plan)->resconstantqual,
1043 finalize_primnode((Node *) ((IndexScan *) plan)->indexqual,
1047 * we need not look at indexqualorig, since it will have the same
1048 * param references as indexqual.
1052 case T_BitmapIndexScan:
1053 finalize_primnode((Node *) ((BitmapIndexScan *) plan)->indexqual,
1057 * we need not look at indexqualorig, since it will have the same
1058 * param references as indexqual.
1062 case T_BitmapHeapScan:
1063 finalize_primnode((Node *) ((BitmapHeapScan *) plan)->bitmapqualorig,
1068 finalize_primnode((Node *) ((TidScan *) plan)->tidquals,
1072 case T_SubqueryScan:
1075 * In a SubqueryScan, SS_finalize_plan has already been run on the
1076 * subplan by the inner invocation of subquery_planner, so there's
1077 * no need to do it again. Instead, just pull out the subplan's
1078 * extParams list, which represents the params it needs from my
1079 * level and higher levels.
1081 context.paramids = bms_add_members(context.paramids,
1082 ((SubqueryScan *) plan)->subplan->extParam);
1085 case T_FunctionScan:
1089 rte = rt_fetch(((FunctionScan *) plan)->scan.scanrelid,
1091 Assert(rte->rtekind == RTE_FUNCTION);
1092 finalize_primnode(rte->funcexpr, &context);
1100 rte = rt_fetch(((ValuesScan *) plan)->scan.scanrelid,
1102 Assert(rte->rtekind == RTE_VALUES);
1103 finalize_primnode((Node *) rte->values_lists, &context);
1111 foreach(l, ((Append *) plan)->appendplans)
1114 bms_add_members(context.paramids,
1115 finalize_plan((Plan *) lfirst(l),
1127 foreach(l, ((BitmapAnd *) plan)->bitmapplans)
1130 bms_add_members(context.paramids,
1131 finalize_plan((Plan *) lfirst(l),
1143 foreach(l, ((BitmapOr *) plan)->bitmapplans)
1146 bms_add_members(context.paramids,
1147 finalize_plan((Plan *) lfirst(l),
1156 finalize_primnode((Node *) ((Join *) plan)->joinqual,
1161 finalize_primnode((Node *) ((Join *) plan)->joinqual,
1163 finalize_primnode((Node *) ((MergeJoin *) plan)->mergeclauses,
1168 finalize_primnode((Node *) ((Join *) plan)->joinqual,
1170 finalize_primnode((Node *) ((HashJoin *) plan)->hashclauses,
1175 finalize_primnode(((Limit *) plan)->limitOffset,
1177 finalize_primnode(((Limit *) plan)->limitCount,
1192 elog(ERROR, "unrecognized node type: %d",
1193 (int) nodeTag(plan));
1196 /* Process left and right child plans, if any */
1197 context.paramids = bms_add_members(context.paramids,
1198 finalize_plan(plan->lefttree,
1203 context.paramids = bms_add_members(context.paramids,
1204 finalize_plan(plan->righttree,
1209 /* Now we have all the paramids */
1211 if (!bms_is_subset(context.paramids, valid_params))
1212 elog(ERROR, "plan should not reference subplan's variable");
1214 plan->extParam = bms_intersect(context.paramids, outer_params);
1215 plan->allParam = context.paramids;
1218 * For speed at execution time, make sure extParam/allParam are actually
1219 * NULL if they are empty sets.
1221 if (bms_is_empty(plan->extParam))
1223 bms_free(plan->extParam);
1224 plan->extParam = NULL;
1226 if (bms_is_empty(plan->allParam))
1228 bms_free(plan->allParam);
1229 plan->allParam = NULL;
1232 return plan->allParam;
1236 * finalize_primnode: add IDs of all PARAM_EXEC params appearing in the given
1237 * expression tree to the result set.
1240 finalize_primnode(Node *node, finalize_primnode_context *context)
1244 if (IsA(node, Param))
1246 if (((Param *) node)->paramkind == PARAM_EXEC)
1248 int paramid = ((Param *) node)->paramid;
1250 context->paramids = bms_add_member(context->paramids, paramid);
1252 return false; /* no more to do here */
1254 if (is_subplan(node))
1256 SubPlan *subplan = (SubPlan *) node;
1258 /* Add outer-level params needed by the subplan to paramids */
1259 context->paramids = bms_join(context->paramids,
1260 bms_intersect(subplan->plan->extParam,
1261 context->outer_params));
1262 /* fall through to recurse into subplan args */
1264 return expression_tree_walker(node, finalize_primnode,
1269 * SS_make_initplan_from_plan - given a plan tree, make it an InitPlan
1271 * The plan is expected to return a scalar value of the indicated type.
1272 * We build an EXPR_SUBLINK SubPlan node and put it into the initplan
1273 * list for the current query level. A Param that represents the initplan's
1274 * output is returned.
1276 * We assume the plan hasn't been put through SS_finalize_plan.
1279 SS_make_initplan_from_plan(PlannerInfo *root, Plan *plan,
1280 Oid resulttype, int32 resulttypmod)
1282 List *saved_initplan = PlannerInitPlan;
1287 * Set up for a new level of subquery. This is just to keep
1288 * SS_finalize_plan from becoming confused.
1290 PlannerQueryLevel++;
1291 PlannerInitPlan = NIL;
1294 * Build extParam/allParam sets for plan nodes.
1296 SS_finalize_plan(plan, root->parse->rtable);
1298 /* Return to outer subquery context */
1299 PlannerQueryLevel--;
1300 PlannerInitPlan = saved_initplan;
1303 * Create a SubPlan node and add it to the outer list of InitPlans.
1305 node = makeNode(SubPlan);
1306 node->subLinkType = EXPR_SUBLINK;
1308 node->plan_id = PlannerPlanId++; /* Assign unique ID to this SubPlan */
1310 node->rtable = root->parse->rtable;
1312 PlannerInitPlan = lappend(PlannerInitPlan, node);
1315 * The node can't have any inputs (since it's an initplan), so the
1316 * parParam and args lists remain empty.
1320 * Make a Param that will be the subplan's output.
1322 prm = generate_new_param(resulttype, resulttypmod);
1323 node->setParam = list_make1_int(prm->paramid);