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.127 2007/11/15 22:25:15 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/cost.h"
22 #include "optimizer/planmain.h"
23 #include "optimizer/planner.h"
24 #include "optimizer/subselect.h"
25 #include "optimizer/var.h"
26 #include "parser/parse_expr.h"
27 #include "parser/parse_relation.h"
28 #include "parser/parsetree.h"
29 #include "rewrite/rewriteManip.h"
30 #include "utils/builtins.h"
31 #include "utils/lsyscache.h"
32 #include "utils/syscache.h"
35 typedef struct convert_testexpr_context
38 int rtindex; /* RT index for Vars, or 0 for Params */
39 List *righthandIds; /* accumulated list of Vars or Param IDs */
40 } convert_testexpr_context;
42 typedef struct process_sublinks_context
46 } process_sublinks_context;
48 typedef struct finalize_primnode_context
51 Bitmapset *paramids; /* Set of PARAM_EXEC paramids found */
52 Bitmapset *outer_params; /* Set of accessible outer paramids */
53 } finalize_primnode_context;
56 static Node *convert_testexpr(PlannerInfo *root,
60 static Node *convert_testexpr_mutator(Node *node,
61 convert_testexpr_context *context);
62 static bool subplan_is_hashable(SubLink *slink, SubPlan *node, Plan *plan);
63 static bool hash_ok_operator(OpExpr *expr);
64 static Node *replace_correlation_vars_mutator(Node *node, PlannerInfo *root);
65 static Node *process_sublinks_mutator(Node *node,
66 process_sublinks_context *context);
67 static Bitmapset *finalize_plan(PlannerInfo *root,
69 Bitmapset *outer_params,
70 Bitmapset *valid_params);
71 static bool finalize_primnode(Node *node, finalize_primnode_context *context);
75 * Generate a Param node to replace the given Var,
76 * which is expected to have varlevelsup > 0 (ie, it is not local).
79 replace_outer_var(PlannerInfo *root, Var *var)
83 PlannerParamItem *pitem;
87 Assert(var->varlevelsup > 0 && var->varlevelsup < root->query_level);
88 abslevel = root->query_level - var->varlevelsup;
91 * If there's already a paramlist entry for this same Var, just use it.
92 * NOTE: in sufficiently complex querytrees, it is possible for the same
93 * varno/abslevel to refer to different RTEs in different parts of the
94 * parsetree, so that different fields might end up sharing the same Param
95 * number. As long as we check the vartype as well, I believe that this
96 * sort of aliasing will cause no trouble. The correct field should get
97 * stored into the Param slot at execution in each part of the tree.
99 * We also need to demand a match on vartypmod. This does not matter for
100 * the Param itself, since those are not typmod-dependent, but it does
101 * matter when make_subplan() instantiates a modified copy of the Var for
102 * a subplan's args list.
105 foreach(ppl, root->glob->paramlist)
107 pitem = (PlannerParamItem *) lfirst(ppl);
108 if (pitem->abslevel == abslevel && IsA(pitem->item, Var))
110 Var *pvar = (Var *) pitem->item;
112 if (pvar->varno == var->varno &&
113 pvar->varattno == var->varattno &&
114 pvar->vartype == var->vartype &&
115 pvar->vartypmod == var->vartypmod)
123 /* Nope, so make a new one */
124 var = (Var *) copyObject(var);
125 var->varlevelsup = 0;
127 pitem = makeNode(PlannerParamItem);
128 pitem->item = (Node *) var;
129 pitem->abslevel = abslevel;
131 root->glob->paramlist = lappend(root->glob->paramlist, pitem);
132 /* i is already the correct index for the new item */
135 retval = makeNode(Param);
136 retval->paramkind = PARAM_EXEC;
138 retval->paramtype = var->vartype;
139 retval->paramtypmod = var->vartypmod;
145 * Generate a Param node to replace the given Aggref
146 * which is expected to have agglevelsup > 0 (ie, it is not local).
149 replace_outer_agg(PlannerInfo *root, Aggref *agg)
152 PlannerParamItem *pitem;
156 Assert(agg->agglevelsup > 0 && agg->agglevelsup < root->query_level);
157 abslevel = root->query_level - agg->agglevelsup;
160 * It does not seem worthwhile to try to match duplicate outer aggs. Just
161 * make a new slot every time.
163 agg = (Aggref *) copyObject(agg);
164 IncrementVarSublevelsUp((Node *) agg, -((int) agg->agglevelsup), 0);
165 Assert(agg->agglevelsup == 0);
167 pitem = makeNode(PlannerParamItem);
168 pitem->item = (Node *) agg;
169 pitem->abslevel = abslevel;
171 root->glob->paramlist = lappend(root->glob->paramlist, pitem);
172 i = list_length(root->glob->paramlist) - 1;
174 retval = makeNode(Param);
175 retval->paramkind = PARAM_EXEC;
177 retval->paramtype = agg->aggtype;
178 retval->paramtypmod = -1;
184 * Generate a new Param node that will not conflict with any other.
186 * This is used to allocate PARAM_EXEC slots for subplan outputs.
189 generate_new_param(PlannerInfo *root, Oid paramtype, int32 paramtypmod)
192 PlannerParamItem *pitem;
194 retval = makeNode(Param);
195 retval->paramkind = PARAM_EXEC;
196 retval->paramid = list_length(root->glob->paramlist);
197 retval->paramtype = paramtype;
198 retval->paramtypmod = paramtypmod;
200 pitem = makeNode(PlannerParamItem);
201 pitem->item = (Node *) retval;
202 pitem->abslevel = root->query_level;
204 root->glob->paramlist = lappend(root->glob->paramlist, pitem);
210 * Get the datatype of the first column of the plan's output.
212 * This is stored for ARRAY_SUBLINK and for exprType(), which doesn't have any
213 * way to get at the plan associated with a SubPlan node. We really only need
214 * the value for EXPR_SUBLINK and ARRAY_SUBLINK subplans, but for consistency
218 get_first_col_type(Plan *plan)
220 TargetEntry *tent = (TargetEntry *) linitial(plan->targetlist);
222 Assert(IsA(tent, TargetEntry));
223 Assert(!tent->resjunk);
224 return exprType((Node *) tent->expr);
228 * Convert a SubLink (as created by the parser) into a SubPlan.
230 * We are given the original SubLink and the already-processed testexpr
231 * (use this instead of the SubLink's own field). We are also told if
232 * this expression appears at top level of a WHERE/HAVING qual.
234 * The result is whatever we need to substitute in place of the SubLink
235 * node in the executable expression. This will be either the SubPlan
236 * node (if we have to do the subplan as a subplan), or a Param node
237 * representing the result of an InitPlan, or a row comparison expression
238 * tree containing InitPlan Param nodes.
241 make_subplan(PlannerInfo *root, SubLink *slink, Node *testexpr, bool isTopQual)
243 Query *subquery = (Query *) (slink->subselect);
244 double tuple_fraction;
247 PlannerInfo *subroot;
254 * Copy the source Query node. This is a quick and dirty kluge to resolve
255 * the fact that the parser can generate trees with multiple links to the
256 * same sub-Query node, but the planner wants to scribble on the Query.
257 * Try to clean this up when we do querytree redesign...
259 subquery = (Query *) copyObject(subquery);
262 * For an EXISTS subplan, tell lower-level planner to expect that only the
263 * first tuple will be retrieved. For ALL and ANY subplans, we will be
264 * able to stop evaluating if the test condition fails, so very often not
265 * all the tuples will be retrieved; for lack of a better idea, specify
266 * 50% retrieval. For EXPR and ROWCOMPARE subplans, use default behavior
267 * (we're only expecting one row out, anyway).
269 * NOTE: if you change these numbers, also change cost_qual_eval_walker()
270 * and get_initplan_cost() in path/costsize.c.
272 * XXX If an ALL/ANY subplan is uncorrelated, we may decide to hash or
273 * materialize its result below. In that case it would've been better to
274 * specify full retrieval. At present, however, we can only detect
275 * correlation or lack of it after we've made the subplan :-(. Perhaps
276 * detection of correlation should be done as a separate step. Meanwhile,
277 * we don't want to be too optimistic about the percentage of tuples
278 * retrieved, for fear of selecting a plan that's bad for the
279 * materialization case.
281 if (slink->subLinkType == EXISTS_SUBLINK)
282 tuple_fraction = 1.0; /* just like a LIMIT 1 */
283 else if (slink->subLinkType == ALL_SUBLINK ||
284 slink->subLinkType == ANY_SUBLINK)
285 tuple_fraction = 0.5; /* 50% */
287 tuple_fraction = 0.0; /* default behavior */
290 * Generate the plan for the subquery.
292 plan = subquery_planner(root->glob, subquery,
293 root->query_level + 1,
298 * Initialize the SubPlan node. Note plan_id isn't set yet.
300 splan = makeNode(SubPlan);
301 splan->subLinkType = slink->subLinkType;
302 splan->testexpr = NULL;
303 splan->paramIds = NIL;
304 splan->firstColType = get_first_col_type(plan);
305 splan->useHashTable = false;
306 /* At top level of a qual, can treat UNKNOWN the same as FALSE */
307 splan->unknownEqFalse = isTopQual;
308 splan->setParam = NIL;
309 splan->parParam = NIL;
313 * Make parParam list of params that current query level will pass to this
316 tmpset = bms_copy(plan->extParam);
317 while ((paramid = bms_first_member(tmpset)) >= 0)
319 PlannerParamItem *pitem = list_nth(root->glob->paramlist, paramid);
321 if (pitem->abslevel == root->query_level)
322 splan->parParam = lappend_int(splan->parParam, paramid);
327 * Un-correlated or undirect correlated plans of EXISTS, EXPR, ARRAY, or
328 * ROWCOMPARE types can be used as initPlans. For EXISTS, EXPR, or ARRAY,
329 * we just produce a Param referring to the result of evaluating the
330 * initPlan. For ROWCOMPARE, we must modify the testexpr tree to contain
331 * PARAM_EXEC Params instead of the PARAM_SUBLINK Params emitted by the
334 if (splan->parParam == NIL && slink->subLinkType == EXISTS_SUBLINK)
338 prm = generate_new_param(root, BOOLOID, -1);
339 splan->setParam = list_make1_int(prm->paramid);
341 result = (Node *) prm;
343 else if (splan->parParam == NIL && slink->subLinkType == EXPR_SUBLINK)
345 TargetEntry *te = linitial(plan->targetlist);
348 Assert(!te->resjunk);
349 prm = generate_new_param(root,
350 exprType((Node *) te->expr),
351 exprTypmod((Node *) te->expr));
352 splan->setParam = list_make1_int(prm->paramid);
354 result = (Node *) prm;
356 else if (splan->parParam == NIL && slink->subLinkType == ARRAY_SUBLINK)
358 TargetEntry *te = linitial(plan->targetlist);
362 Assert(!te->resjunk);
363 arraytype = get_array_type(exprType((Node *) te->expr));
364 if (!OidIsValid(arraytype))
365 elog(ERROR, "could not find array type for datatype %s",
366 format_type_be(exprType((Node *) te->expr)));
367 prm = generate_new_param(root,
369 exprTypmod((Node *) te->expr));
370 splan->setParam = list_make1_int(prm->paramid);
372 result = (Node *) prm;
374 else if (splan->parParam == NIL && slink->subLinkType == ROWCOMPARE_SUBLINK)
376 /* Adjust the Params */
377 result = convert_testexpr(root,
381 splan->setParam = list_copy(splan->paramIds);
385 * The executable expression is returned to become part of the outer
386 * plan's expression tree; it is not kept in the initplan node.
394 /* Adjust the Params */
395 splan->testexpr = convert_testexpr(root,
401 * We can't convert subplans of ALL_SUBLINK or ANY_SUBLINK types to
402 * initPlans, even when they are uncorrelated or undirect correlated,
403 * because we need to scan the output of the subplan for each outer
404 * tuple. But if it's an IN (= ANY) test, we might be able to use a
405 * hashtable to avoid comparing all the tuples.
407 if (subplan_is_hashable(slink, splan, plan))
408 splan->useHashTable = true;
411 * Otherwise, we have the option to tack a MATERIAL node onto the top
412 * of the subplan, to reduce the cost of reading it repeatedly. This
413 * is pointless for a direct-correlated subplan, since we'd have to
414 * recompute its results each time anyway. For uncorrelated/undirect
415 * correlated subplans, we add MATERIAL unless the subplan's top plan
416 * node would materialize its output anyway.
418 else if (splan->parParam == NIL)
422 switch (nodeTag(plan))
427 use_material = false;
434 plan = materialize_finished_plan(plan);
438 * Make splan->args from parParam.
441 foreach(l, splan->parParam)
443 PlannerParamItem *pitem = list_nth(root->glob->paramlist,
447 * The Var or Aggref has already been adjusted to have the correct
448 * varlevelsup or agglevelsup. We probably don't even need to
449 * copy it again, but be safe.
451 args = lappend(args, copyObject(pitem->item));
455 result = (Node *) splan;
460 * Add the subplan and its rtable to the global lists.
462 root->glob->subplans = lappend(root->glob->subplans,
464 root->glob->subrtables = lappend(root->glob->subrtables,
465 subroot->parse->rtable);
466 splan->plan_id = list_length(root->glob->subplans);
469 root->init_plans = lappend(root->init_plans, splan);
472 * A parameterless subplan (not initplan) should be prepared to handle
473 * REWIND efficiently. If it has direct parameters then there's no point
474 * since it'll be reset on each scan anyway; and if it's an initplan then
475 * there's no point since it won't get re-run without parameter changes
476 * anyway. The input of a hashed subplan doesn't need REWIND either.
478 if (splan->parParam == NIL && !isInitPlan && !splan->useHashTable)
479 root->glob->rewindPlanIDs = bms_add_member(root->glob->rewindPlanIDs,
486 * convert_testexpr: convert the testexpr given by the parser into
487 * actually executable form. This entails replacing PARAM_SUBLINK Params
488 * with Params or Vars representing the results of the sub-select:
490 * If rtindex is 0, we build Params to represent the sub-select outputs.
491 * The paramids of the Params created are returned in the *righthandIds list.
493 * If rtindex is not 0, we build Vars using that rtindex as varno. Copies
494 * of the Var nodes are returned in *righthandIds (this is a bit of a type
495 * cheat, but we can get away with it).
497 * The given testexpr has already been recursively processed by
498 * process_sublinks_mutator. Hence it can no longer contain any
499 * PARAM_SUBLINK Params for lower SubLink nodes; we can safely assume that
500 * any we find are for our own level of SubLink.
503 convert_testexpr(PlannerInfo *root,
509 convert_testexpr_context context;
512 context.rtindex = rtindex;
513 context.righthandIds = NIL;
514 result = convert_testexpr_mutator(testexpr, &context);
515 *righthandIds = context.righthandIds;
520 convert_testexpr_mutator(Node *node,
521 convert_testexpr_context *context)
525 if (IsA(node, Param))
527 Param *param = (Param *) node;
529 if (param->paramkind == PARAM_SUBLINK)
532 * We expect to encounter the Params in column-number sequence. We
533 * could handle non-sequential order if necessary, but for now
534 * there's no need. (This is also a useful cross-check that we
535 * aren't finding any unexpected Params.)
537 if (param->paramid != list_length(context->righthandIds) + 1)
538 elog(ERROR, "unexpected PARAM_SUBLINK ID: %d", param->paramid);
540 if (context->rtindex)
542 /* Make the Var node representing the subplan's result */
545 newvar = makeVar(context->rtindex,
552 * Copy it for caller. NB: we need a copy to avoid having
553 * doubly-linked substructure in the modified parse tree.
555 context->righthandIds = lappend(context->righthandIds,
557 return (Node *) newvar;
561 /* Make the Param node representing the subplan's result */
564 newparam = generate_new_param(context->root,
568 context->righthandIds = lappend_int(context->righthandIds,
570 return (Node *) newparam;
574 return expression_tree_mutator(node,
575 convert_testexpr_mutator,
580 * subplan_is_hashable: decide whether we can implement a subplan by hashing
582 * Caution: the SubPlan node is not completely filled in yet. We can rely
583 * on its plan and parParam fields, however.
586 subplan_is_hashable(SubLink *slink, SubPlan *node, Plan *plan)
588 double subquery_size;
592 * The sublink type must be "= ANY" --- that is, an IN operator. We
593 * expect that the test expression will be either a single OpExpr, or an
594 * AND-clause containing OpExprs. (If it's anything else then the parser
595 * must have determined that the operators have non-equality-like
596 * semantics. In the OpExpr case we can't be sure what the operator's
597 * semantics are like, but the test below for hashability will reject
598 * anything that's not equality.)
600 if (slink->subLinkType != ANY_SUBLINK)
602 if (slink->testexpr == NULL ||
603 (!IsA(slink->testexpr, OpExpr) &&
604 !and_clause(slink->testexpr)))
608 * The subplan must not have any direct correlation vars --- else we'd
609 * have to recompute its output each time, so that the hashtable wouldn't
612 if (node->parParam != NIL)
616 * The estimated size of the subquery result must fit in work_mem. (Note:
617 * we use sizeof(HeapTupleHeaderData) here even though the tuples will
618 * actually be stored as MinimalTuples; this provides some fudge factor
619 * for hashtable overhead.)
621 subquery_size = plan->plan_rows *
622 (MAXALIGN(plan->plan_width) + MAXALIGN(sizeof(HeapTupleHeaderData)));
623 if (subquery_size > work_mem * 1024L)
627 * The combining operators must be hashable and strict. The need for
628 * hashability is obvious, since we want to use hashing. Without
629 * strictness, behavior in the presence of nulls is too unpredictable. We
630 * actually must assume even more than plain strictness: they can't yield
631 * NULL for non-null inputs, either (see nodeSubplan.c). However, hash
632 * indexes and hash joins assume that too.
634 if (IsA(slink->testexpr, OpExpr))
636 if (!hash_ok_operator((OpExpr *) slink->testexpr))
641 foreach(l, ((BoolExpr *) slink->testexpr)->args)
643 Node *andarg = (Node *) lfirst(l);
645 if (!IsA(andarg, OpExpr))
646 return false; /* probably can't happen */
647 if (!hash_ok_operator((OpExpr *) andarg))
656 hash_ok_operator(OpExpr *expr)
658 Oid opid = expr->opno;
660 Form_pg_operator optup;
662 tup = SearchSysCache(OPEROID,
663 ObjectIdGetDatum(opid),
665 if (!HeapTupleIsValid(tup))
666 elog(ERROR, "cache lookup failed for operator %u", opid);
667 optup = (Form_pg_operator) GETSTRUCT(tup);
668 if (!optup->oprcanhash || !func_strict(optup->oprcode))
670 ReleaseSysCache(tup);
673 ReleaseSysCache(tup);
678 * convert_IN_to_join: can we convert an IN SubLink to join style?
680 * The caller has found a SubLink at the top level of WHERE, but has not
681 * checked the properties of the SubLink at all. Decide whether it is
682 * appropriate to process this SubLink in join style. If not, return NULL.
683 * If so, build the qual clause(s) to replace the SubLink, and return them.
685 * Side effects of a successful conversion include adding the SubLink's
686 * subselect to the query's rangetable and adding an InClauseInfo node to
690 convert_IN_to_join(PlannerInfo *root, SubLink *sublink)
692 Query *parse = root->parse;
693 Query *subselect = (Query *) sublink->subselect;
699 InClauseInfo *ininfo;
703 * The sublink type must be "= ANY" --- that is, an IN operator. We
704 * expect that the test expression will be either a single OpExpr, or an
705 * AND-clause containing OpExprs. (If it's anything else then the parser
706 * must have determined that the operators have non-equality-like
707 * semantics. In the OpExpr case we can't be sure what the operator's
708 * semantics are like, and must check for ourselves.)
710 if (sublink->subLinkType != ANY_SUBLINK)
712 if (sublink->testexpr && IsA(sublink->testexpr, OpExpr))
714 Oid opno = ((OpExpr *) sublink->testexpr)->opno;
718 get_op_btree_interpretation(opno, &opfamilies, &opstrats);
719 if (!list_member_int(opstrats, ROWCOMPARE_EQ))
721 in_operators = list_make1_oid(opno);
723 else if (and_clause(sublink->testexpr))
727 /* OK, but we need to extract the per-column operator OIDs */
729 foreach(lc, ((BoolExpr *) sublink->testexpr)->args)
731 OpExpr *op = (OpExpr *) lfirst(lc);
733 if (!IsA(op, OpExpr)) /* probably shouldn't happen */
735 in_operators = lappend_oid(in_operators, op->opno);
742 * The sub-select must not refer to any Vars of the parent query. (Vars of
743 * higher levels should be okay, though.)
745 if (contain_vars_of_level((Node *) subselect, 1))
749 * The left-hand expressions must contain some Vars of the current query,
750 * else it's not gonna be a join.
752 left_varnos = pull_varnos(sublink->testexpr);
753 if (bms_is_empty(left_varnos))
757 * The combining operators and left-hand expressions mustn't be volatile.
759 if (contain_volatile_functions(sublink->testexpr))
763 * Okay, pull up the sub-select into top range table and jointree.
765 * We rely here on the assumption that the outer query has no references
766 * to the inner (necessarily true, other than the Vars that we build
767 * below). Therefore this is a lot easier than what pull_up_subqueries has
770 rte = addRangeTableEntryForSubquery(NULL,
772 makeAlias("IN_subquery", NIL),
774 parse->rtable = lappend(parse->rtable, rte);
775 rtindex = list_length(parse->rtable);
776 rtr = makeNode(RangeTblRef);
777 rtr->rtindex = rtindex;
778 parse->jointree->fromlist = lappend(parse->jointree->fromlist, rtr);
781 * Now build the InClauseInfo node.
783 ininfo = makeNode(InClauseInfo);
784 ininfo->lefthand = left_varnos;
785 ininfo->righthand = bms_make_singleton(rtindex);
786 ininfo->in_operators = in_operators;
789 * Build the result qual expression. As a side effect,
790 * ininfo->sub_targetlist is filled with a list of Vars representing the
793 result = convert_testexpr(root,
796 &ininfo->sub_targetlist);
798 Assert(list_length(in_operators) == list_length(ininfo->sub_targetlist));
800 /* Add the completed node to the query's list */
801 root->in_info_list = lappend(root->in_info_list, ininfo);
807 * Replace correlation vars (uplevel vars) with Params.
809 * Uplevel aggregates are replaced, too.
811 * Note: it is critical that this runs immediately after SS_process_sublinks.
812 * Since we do not recurse into the arguments of uplevel aggregates, they will
813 * get copied to the appropriate subplan args list in the parent query with
814 * uplevel vars not replaced by Params, but only adjusted in level (see
815 * replace_outer_agg). That's exactly what we want for the vars of the parent
816 * level --- but if an aggregate's argument contains any further-up variables,
817 * they have to be replaced with Params in their turn. That will happen when
818 * the parent level runs SS_replace_correlation_vars. Therefore it must do
819 * so after expanding its sublinks to subplans. And we don't want any steps
820 * in between, else those steps would never get applied to the aggregate
821 * argument expressions, either in the parent or the child level.
824 SS_replace_correlation_vars(PlannerInfo *root, Node *expr)
826 /* No setup needed for tree walk, so away we go */
827 return replace_correlation_vars_mutator(expr, root);
831 replace_correlation_vars_mutator(Node *node, PlannerInfo *root)
837 if (((Var *) node)->varlevelsup > 0)
838 return (Node *) replace_outer_var(root, (Var *) node);
840 if (IsA(node, Aggref))
842 if (((Aggref *) node)->agglevelsup > 0)
843 return (Node *) replace_outer_agg(root, (Aggref *) node);
845 return expression_tree_mutator(node,
846 replace_correlation_vars_mutator,
851 * Expand SubLinks to SubPlans in the given expression.
853 * The isQual argument tells whether or not this expression is a WHERE/HAVING
854 * qualifier expression. If it is, any sublinks appearing at top level need
855 * not distinguish FALSE from UNKNOWN return values.
858 SS_process_sublinks(PlannerInfo *root, Node *expr, bool isQual)
860 process_sublinks_context context;
863 context.isTopQual = isQual;
864 return process_sublinks_mutator(expr, &context);
868 process_sublinks_mutator(Node *node, process_sublinks_context *context)
870 process_sublinks_context locContext;
872 locContext.root = context->root;
876 if (IsA(node, SubLink))
878 SubLink *sublink = (SubLink *) node;
882 * First, recursively process the lefthand-side expressions, if any.
883 * They're not top-level anymore.
885 locContext.isTopQual = false;
886 testexpr = process_sublinks_mutator(sublink->testexpr, &locContext);
889 * Now build the SubPlan node and make the expr to return.
891 return make_subplan(context->root,
898 * We should never see a SubPlan expression in the input (since this is
899 * the very routine that creates 'em to begin with). We shouldn't find
900 * ourselves invoked directly on a Query, either.
902 Assert(!is_subplan(node));
903 Assert(!IsA(node, Query));
906 * Because make_subplan() could return an AND or OR clause, we have to
907 * take steps to preserve AND/OR flatness of a qual. We assume the input
908 * has been AND/OR flattened and so we need no recursion here.
910 * If we recurse down through anything other than an AND node, we are
911 * definitely not at top qual level anymore. (Due to the coding here, we
912 * will not get called on the List subnodes of an AND, so no check is
915 if (and_clause(node))
920 /* Still at qual top-level */
921 locContext.isTopQual = context->isTopQual;
923 foreach(l, ((BoolExpr *) node)->args)
927 newarg = process_sublinks_mutator(lfirst(l), &locContext);
928 if (and_clause(newarg))
929 newargs = list_concat(newargs, ((BoolExpr *) newarg)->args);
931 newargs = lappend(newargs, newarg);
933 return (Node *) make_andclause(newargs);
936 /* otherwise not at qual top-level */
937 locContext.isTopQual = false;
944 foreach(l, ((BoolExpr *) node)->args)
948 newarg = process_sublinks_mutator(lfirst(l), &locContext);
949 if (or_clause(newarg))
950 newargs = list_concat(newargs, ((BoolExpr *) newarg)->args);
952 newargs = lappend(newargs, newarg);
954 return (Node *) make_orclause(newargs);
957 return expression_tree_mutator(node,
958 process_sublinks_mutator,
959 (void *) &locContext);
963 * SS_finalize_plan - do final sublink processing for a completed Plan.
965 * This recursively computes the extParam and allParam sets for every Plan
966 * node in the given plan tree. It also attaches any generated InitPlans
967 * to the top plan node.
970 SS_finalize_plan(PlannerInfo *root, Plan *plan)
972 Bitmapset *outer_params,
981 * First, scan the param list to discover the sets of params that are
982 * available from outer query levels and my own query level. We do this
983 * once to save time in the per-plan recursion steps.
985 outer_params = valid_params = NULL;
987 foreach(l, root->glob->paramlist)
989 PlannerParamItem *pitem = (PlannerParamItem *) lfirst(l);
991 if (pitem->abslevel < root->query_level)
993 /* valid outer-level parameter */
994 outer_params = bms_add_member(outer_params, paramid);
995 valid_params = bms_add_member(valid_params, paramid);
997 else if (pitem->abslevel == root->query_level &&
998 IsA(pitem->item, Param))
1000 /* valid local parameter (i.e., a setParam of my child) */
1001 valid_params = bms_add_member(valid_params, paramid);
1008 * Now recurse through plan tree.
1010 (void) finalize_plan(root, plan, outer_params, valid_params);
1012 bms_free(outer_params);
1013 bms_free(valid_params);
1016 * Finally, attach any initPlans to the topmost plan node, and add their
1017 * extParams to the topmost node's, too. However, any setParams of the
1018 * initPlans should not be present in the topmost node's extParams, only
1019 * in its allParams. (As of PG 8.1, it's possible that some initPlans
1020 * have extParams that are setParams of other initPlans, so we have to
1021 * take care of this situation explicitly.)
1023 * We also add the eval cost of each initPlan to the startup cost of the
1024 * top node. This is a conservative overestimate, since in fact each
1025 * initPlan might be executed later than plan startup, or even not at all.
1027 plan->initPlan = root->init_plans;
1028 root->init_plans = NIL; /* make sure they're not attached twice */
1030 initExtParam = initSetParam = NULL;
1032 foreach(l, plan->initPlan)
1034 SubPlan *initsubplan = (SubPlan *) lfirst(l);
1035 Plan *initplan = planner_subplan_get_plan(root, initsubplan);
1038 initExtParam = bms_add_members(initExtParam, initplan->extParam);
1039 foreach(l2, initsubplan->setParam)
1041 initSetParam = bms_add_member(initSetParam, lfirst_int(l2));
1043 initplan_cost += get_initplan_cost(root, initsubplan);
1045 /* allParam must include all these params */
1046 plan->allParam = bms_add_members(plan->allParam, initExtParam);
1047 plan->allParam = bms_add_members(plan->allParam, initSetParam);
1048 /* but extParam shouldn't include any setParams */
1049 initExtParam = bms_del_members(initExtParam, initSetParam);
1050 /* empty test ensures extParam is exactly NULL if it's empty */
1051 if (!bms_is_empty(initExtParam))
1052 plan->extParam = bms_join(plan->extParam, initExtParam);
1054 plan->startup_cost += initplan_cost;
1055 plan->total_cost += initplan_cost;
1059 * Recursive processing of all nodes in the plan tree
1061 * The return value is the computed allParam set for the given Plan node.
1062 * This is just an internal notational convenience.
1065 finalize_plan(PlannerInfo *root, Plan *plan,
1066 Bitmapset *outer_params, Bitmapset *valid_params)
1068 finalize_primnode_context context;
1073 context.root = root;
1074 context.paramids = NULL; /* initialize set to empty */
1075 context.outer_params = outer_params;
1078 * When we call finalize_primnode, context.paramids sets are automatically
1079 * merged together. But when recursing to self, we have to do it the hard
1080 * way. We want the paramids set to include params in subplans as well as
1084 /* Find params in targetlist and qual */
1085 finalize_primnode((Node *) plan->targetlist, &context);
1086 finalize_primnode((Node *) plan->qual, &context);
1088 /* Check additional node-type-specific fields */
1089 switch (nodeTag(plan))
1092 finalize_primnode(((Result *) plan)->resconstantqual,
1097 finalize_primnode((Node *) ((IndexScan *) plan)->indexqual,
1101 * we need not look at indexqualorig, since it will have the same
1102 * param references as indexqual.
1106 case T_BitmapIndexScan:
1107 finalize_primnode((Node *) ((BitmapIndexScan *) plan)->indexqual,
1111 * we need not look at indexqualorig, since it will have the same
1112 * param references as indexqual.
1116 case T_BitmapHeapScan:
1117 finalize_primnode((Node *) ((BitmapHeapScan *) plan)->bitmapqualorig,
1122 finalize_primnode((Node *) ((TidScan *) plan)->tidquals,
1126 case T_SubqueryScan:
1129 * In a SubqueryScan, SS_finalize_plan has already been run on the
1130 * subplan by the inner invocation of subquery_planner, so there's
1131 * no need to do it again. Instead, just pull out the subplan's
1132 * extParams list, which represents the params it needs from my
1133 * level and higher levels.
1135 context.paramids = bms_add_members(context.paramids,
1136 ((SubqueryScan *) plan)->subplan->extParam);
1139 case T_FunctionScan:
1140 finalize_primnode(((FunctionScan *) plan)->funcexpr,
1145 finalize_primnode((Node *) ((ValuesScan *) plan)->values_lists,
1153 foreach(l, ((Append *) plan)->appendplans)
1156 bms_add_members(context.paramids,
1169 foreach(l, ((BitmapAnd *) plan)->bitmapplans)
1172 bms_add_members(context.paramids,
1185 foreach(l, ((BitmapOr *) plan)->bitmapplans)
1188 bms_add_members(context.paramids,
1198 finalize_primnode((Node *) ((Join *) plan)->joinqual,
1203 finalize_primnode((Node *) ((Join *) plan)->joinqual,
1205 finalize_primnode((Node *) ((MergeJoin *) plan)->mergeclauses,
1210 finalize_primnode((Node *) ((Join *) plan)->joinqual,
1212 finalize_primnode((Node *) ((HashJoin *) plan)->hashclauses,
1217 finalize_primnode(((Limit *) plan)->limitOffset,
1219 finalize_primnode(((Limit *) plan)->limitCount,
1234 elog(ERROR, "unrecognized node type: %d",
1235 (int) nodeTag(plan));
1238 /* Process left and right child plans, if any */
1239 context.paramids = bms_add_members(context.paramids,
1245 context.paramids = bms_add_members(context.paramids,
1251 /* Now we have all the paramids */
1253 if (!bms_is_subset(context.paramids, valid_params))
1254 elog(ERROR, "plan should not reference subplan's variable");
1256 plan->extParam = bms_intersect(context.paramids, outer_params);
1257 plan->allParam = context.paramids;
1260 * For speed at execution time, make sure extParam/allParam are actually
1261 * NULL if they are empty sets.
1263 if (bms_is_empty(plan->extParam))
1265 bms_free(plan->extParam);
1266 plan->extParam = NULL;
1268 if (bms_is_empty(plan->allParam))
1270 bms_free(plan->allParam);
1271 plan->allParam = NULL;
1274 return plan->allParam;
1278 * finalize_primnode: add IDs of all PARAM_EXEC params appearing in the given
1279 * expression tree to the result set.
1282 finalize_primnode(Node *node, finalize_primnode_context *context)
1286 if (IsA(node, Param))
1288 if (((Param *) node)->paramkind == PARAM_EXEC)
1290 int paramid = ((Param *) node)->paramid;
1292 context->paramids = bms_add_member(context->paramids, paramid);
1294 return false; /* no more to do here */
1296 if (is_subplan(node))
1298 SubPlan *subplan = (SubPlan *) node;
1299 Plan *plan = planner_subplan_get_plan(context->root, subplan);
1301 /* Add outer-level params needed by the subplan to paramids */
1302 context->paramids = bms_join(context->paramids,
1303 bms_intersect(plan->extParam,
1304 context->outer_params));
1305 /* fall through to recurse into subplan args */
1307 return expression_tree_walker(node, finalize_primnode,
1312 * SS_make_initplan_from_plan - given a plan tree, make it an InitPlan
1314 * The plan is expected to return a scalar value of the indicated type.
1315 * We build an EXPR_SUBLINK SubPlan node and put it into the initplan
1316 * list for the current query level. A Param that represents the initplan's
1317 * output is returned.
1319 * We assume the plan hasn't been put through SS_finalize_plan.
1322 SS_make_initplan_from_plan(PlannerInfo *root, Plan *plan,
1323 Oid resulttype, int32 resulttypmod)
1325 List *saved_init_plans;
1330 * We must run SS_finalize_plan(), since that's normally done before a
1331 * subplan gets put into the initplan list. However it will try to attach
1332 * any pre-existing initplans to this one, which we don't want (they are
1333 * siblings not children of this initplan). So, a quick kluge to hide
1334 * them. (This is something else that could perhaps be cleaner if we did
1335 * extParam/allParam processing in setrefs.c instead of here? See notes
1336 * for materialize_finished_plan.)
1338 saved_init_plans = root->init_plans;
1339 root->init_plans = NIL;
1342 * Build extParam/allParam sets for plan nodes.
1344 SS_finalize_plan(root, plan);
1346 /* Restore outer initplan list */
1347 root->init_plans = saved_init_plans;
1350 * Add the subplan and its rtable to the global lists.
1352 root->glob->subplans = lappend(root->glob->subplans,
1354 root->glob->subrtables = lappend(root->glob->subrtables,
1355 root->parse->rtable);
1358 * Create a SubPlan node and add it to the outer list of InitPlans.
1360 node = makeNode(SubPlan);
1361 node->subLinkType = EXPR_SUBLINK;
1362 node->firstColType = get_first_col_type(plan);
1363 node->plan_id = list_length(root->glob->subplans);
1365 root->init_plans = lappend(root->init_plans, node);
1368 * The node can't have any inputs (since it's an initplan), so the
1369 * parParam and args lists remain empty.
1373 * Make a Param that will be the subplan's output.
1375 prm = generate_new_param(root, resulttype, resulttypmod);
1376 node->setParam = list_make1_int(prm->paramid);