1 /*-------------------------------------------------------------------------
4 * Planning routines for subselects and parameters.
6 * Portions Copyright (c) 1996-2008, 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.132 2008/07/10 02:14: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 "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 List *subst_nodes; /* Nodes to substitute for Params */
39 } convert_testexpr_context;
41 typedef struct process_sublinks_context
45 } process_sublinks_context;
47 typedef struct finalize_primnode_context
50 Bitmapset *paramids; /* Non-local PARAM_EXEC paramids found */
51 } finalize_primnode_context;
54 static List *generate_subquery_params(PlannerInfo *root, List *tlist,
56 static List *generate_subquery_vars(PlannerInfo *root, List *tlist,
58 static Node *convert_testexpr(PlannerInfo *root,
61 static Node *convert_testexpr_mutator(Node *node,
62 convert_testexpr_context *context);
63 static bool subplan_is_hashable(SubLink *slink, SubPlan *node, Plan *plan);
64 static bool hash_ok_operator(OpExpr *expr);
65 static Node *replace_correlation_vars_mutator(Node *node, PlannerInfo *root);
66 static Node *process_sublinks_mutator(Node *node,
67 process_sublinks_context *context);
68 static Bitmapset *finalize_plan(PlannerInfo *root,
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 */
379 params = generate_subquery_params(root,
382 result = convert_testexpr(root,
385 splan->setParam = list_copy(splan->paramIds);
389 * The executable expression is returned to become part of the outer
390 * plan's expression tree; it is not kept in the initplan node.
402 /* Adjust the Params in the testexpr */
403 params = generate_subquery_params(root,
406 splan->testexpr = convert_testexpr(root,
412 * We can't convert subplans of ALL_SUBLINK or ANY_SUBLINK types to
413 * initPlans, even when they are uncorrelated or undirect correlated,
414 * because we need to scan the output of the subplan for each outer
415 * tuple. But if it's an IN (= ANY) test, we might be able to use a
416 * hashtable to avoid comparing all the tuples.
418 if (subplan_is_hashable(slink, splan, plan))
419 splan->useHashTable = true;
422 * Otherwise, we have the option to tack a MATERIAL node onto the top
423 * of the subplan, to reduce the cost of reading it repeatedly. This
424 * is pointless for a direct-correlated subplan, since we'd have to
425 * recompute its results each time anyway. For uncorrelated/undirect
426 * correlated subplans, we add MATERIAL unless the subplan's top plan
427 * node would materialize its output anyway.
429 else if (splan->parParam == NIL)
433 switch (nodeTag(plan))
438 use_material = false;
445 plan = materialize_finished_plan(plan);
449 * Make splan->args from parParam.
452 foreach(l, splan->parParam)
454 PlannerParamItem *pitem = list_nth(root->glob->paramlist,
458 * The Var or Aggref has already been adjusted to have the correct
459 * varlevelsup or agglevelsup. We probably don't even need to
460 * copy it again, but be safe.
462 args = lappend(args, copyObject(pitem->item));
466 result = (Node *) splan;
471 * Add the subplan and its rtable to the global lists.
473 root->glob->subplans = lappend(root->glob->subplans,
475 root->glob->subrtables = lappend(root->glob->subrtables,
476 subroot->parse->rtable);
477 splan->plan_id = list_length(root->glob->subplans);
480 root->init_plans = lappend(root->init_plans, splan);
483 * A parameterless subplan (not initplan) should be prepared to handle
484 * REWIND efficiently. If it has direct parameters then there's no point
485 * since it'll be reset on each scan anyway; and if it's an initplan then
486 * there's no point since it won't get re-run without parameter changes
487 * anyway. The input of a hashed subplan doesn't need REWIND either.
489 if (splan->parParam == NIL && !isInitPlan && !splan->useHashTable)
490 root->glob->rewindPlanIDs = bms_add_member(root->glob->rewindPlanIDs,
497 * generate_subquery_params: build a list of Params representing the output
498 * columns of a sublink's sub-select, given the sub-select's targetlist.
500 * We also return an integer list of the paramids of the Params.
503 generate_subquery_params(PlannerInfo *root, List *tlist, List **paramIds)
512 TargetEntry *tent = (TargetEntry *) lfirst(lc);
518 param = generate_new_param(root,
519 exprType((Node *) tent->expr),
520 exprTypmod((Node *) tent->expr));
521 result = lappend(result, param);
522 ids = lappend_int(ids, param->paramid);
530 * generate_subquery_vars: build a list of Vars representing the output
531 * columns of a sublink's sub-select, given the sub-select's targetlist.
532 * The Vars have the specified varno (RTE index).
535 generate_subquery_vars(PlannerInfo *root, List *tlist, Index varno)
543 TargetEntry *tent = (TargetEntry *) lfirst(lc);
551 exprType((Node *) tent->expr),
552 exprTypmod((Node *) tent->expr),
554 result = lappend(result, var);
561 * convert_testexpr: convert the testexpr given by the parser into
562 * actually executable form. This entails replacing PARAM_SUBLINK Params
563 * with Params or Vars representing the results of the sub-select. The
564 * nodes to be substituted are passed in as the List result from
565 * generate_subquery_params or generate_subquery_vars.
567 * The given testexpr has already been recursively processed by
568 * process_sublinks_mutator. Hence it can no longer contain any
569 * PARAM_SUBLINK Params for lower SubLink nodes; we can safely assume that
570 * any we find are for our own level of SubLink.
573 convert_testexpr(PlannerInfo *root,
577 convert_testexpr_context context;
580 context.subst_nodes = subst_nodes;
581 return convert_testexpr_mutator(testexpr, &context);
585 convert_testexpr_mutator(Node *node,
586 convert_testexpr_context *context)
590 if (IsA(node, Param))
592 Param *param = (Param *) node;
594 if (param->paramkind == PARAM_SUBLINK)
596 if (param->paramid <= 0 ||
597 param->paramid > list_length(context->subst_nodes))
598 elog(ERROR, "unexpected PARAM_SUBLINK ID: %d", param->paramid);
601 * We copy the list item to avoid having doubly-linked
602 * substructure in the modified parse tree. This is probably
603 * unnecessary when it's a Param, but be safe.
605 return (Node *) copyObject(list_nth(context->subst_nodes,
606 param->paramid - 1));
609 return expression_tree_mutator(node,
610 convert_testexpr_mutator,
615 * subplan_is_hashable: decide whether we can implement a subplan by hashing
617 * Caution: the SubPlan node is not completely filled in yet. We can rely
618 * on its plan and parParam fields, however.
621 subplan_is_hashable(SubLink *slink, SubPlan *node, Plan *plan)
623 double subquery_size;
627 * The sublink type must be "= ANY" --- that is, an IN operator. We
628 * expect that the test expression will be either a single OpExpr, or an
629 * AND-clause containing OpExprs. (If it's anything else then the parser
630 * must have determined that the operators have non-equality-like
631 * semantics. In the OpExpr case we can't be sure what the operator's
632 * semantics are like, but the test below for hashability will reject
633 * anything that's not equality.)
635 if (slink->subLinkType != ANY_SUBLINK)
637 if (slink->testexpr == NULL ||
638 (!IsA(slink->testexpr, OpExpr) &&
639 !and_clause(slink->testexpr)))
643 * The subplan must not have any direct correlation vars --- else we'd
644 * have to recompute its output each time, so that the hashtable wouldn't
647 if (node->parParam != NIL)
651 * The estimated size of the subquery result must fit in work_mem. (Note:
652 * we use sizeof(HeapTupleHeaderData) here even though the tuples will
653 * actually be stored as MinimalTuples; this provides some fudge factor
654 * for hashtable overhead.)
656 subquery_size = plan->plan_rows *
657 (MAXALIGN(plan->plan_width) + MAXALIGN(sizeof(HeapTupleHeaderData)));
658 if (subquery_size > work_mem * 1024L)
662 * The combining operators must be hashable and strict. The need for
663 * hashability is obvious, since we want to use hashing. Without
664 * strictness, behavior in the presence of nulls is too unpredictable. We
665 * actually must assume even more than plain strictness: they can't yield
666 * NULL for non-null inputs, either (see nodeSubplan.c). However, hash
667 * indexes and hash joins assume that too.
669 if (IsA(slink->testexpr, OpExpr))
671 if (!hash_ok_operator((OpExpr *) slink->testexpr))
676 foreach(l, ((BoolExpr *) slink->testexpr)->args)
678 Node *andarg = (Node *) lfirst(l);
680 if (!IsA(andarg, OpExpr))
681 return false; /* probably can't happen */
682 if (!hash_ok_operator((OpExpr *) andarg))
691 hash_ok_operator(OpExpr *expr)
693 Oid opid = expr->opno;
695 Form_pg_operator optup;
697 tup = SearchSysCache(OPEROID,
698 ObjectIdGetDatum(opid),
700 if (!HeapTupleIsValid(tup))
701 elog(ERROR, "cache lookup failed for operator %u", opid);
702 optup = (Form_pg_operator) GETSTRUCT(tup);
703 if (!optup->oprcanhash || !func_strict(optup->oprcode))
705 ReleaseSysCache(tup);
708 ReleaseSysCache(tup);
713 * convert_IN_to_join: can we convert an IN SubLink to join style?
715 * The caller has found a SubLink at the top level of WHERE, but has not
716 * checked the properties of the SubLink at all. Decide whether it is
717 * appropriate to process this SubLink in join style. If not, return NULL.
718 * If so, build the qual clause(s) to replace the SubLink, and return them.
720 * Side effects of a successful conversion include adding the SubLink's
721 * subselect to the query's rangetable and adding an InClauseInfo node to
725 convert_IN_to_join(PlannerInfo *root, SubLink *sublink)
727 Query *parse = root->parse;
728 Query *subselect = (Query *) sublink->subselect;
737 InClauseInfo *ininfo;
741 * The sublink type must be "= ANY" --- that is, an IN operator. We
742 * expect that the test expression will be either a single OpExpr, or an
743 * AND-clause containing OpExprs. (If it's anything else then the parser
744 * must have determined that the operators have non-equality-like
745 * semantics. In the OpExpr case we can't be sure what the operator's
746 * semantics are like, and must check for ourselves.)
748 if (sublink->subLinkType != ANY_SUBLINK)
750 if (sublink->testexpr && IsA(sublink->testexpr, OpExpr))
752 OpExpr *op = (OpExpr *) sublink->testexpr;
757 if (list_length(op->args) != 2)
758 return NULL; /* not binary operator? */
759 get_op_btree_interpretation(opno, &opfamilies, &opstrats);
760 if (!list_member_int(opstrats, ROWCOMPARE_EQ))
762 in_operators = list_make1_oid(opno);
763 left_exprs = list_make1(linitial(op->args));
764 right_exprs = list_make1(lsecond(op->args));
766 else if (and_clause(sublink->testexpr))
770 /* OK, but we need to extract the per-column info */
771 in_operators = left_exprs = right_exprs = NIL;
772 foreach(lc, ((BoolExpr *) sublink->testexpr)->args)
774 OpExpr *op = (OpExpr *) lfirst(lc);
776 if (!IsA(op, OpExpr)) /* probably shouldn't happen */
778 if (list_length(op->args) != 2)
779 return NULL; /* not binary operator? */
780 in_operators = lappend_oid(in_operators, op->opno);
781 left_exprs = lappend(left_exprs, linitial(op->args));
782 right_exprs = lappend(right_exprs, lsecond(op->args));
789 * The sub-select must not refer to any Vars of the parent query. (Vars of
790 * higher levels should be okay, though.)
792 if (contain_vars_of_level((Node *) subselect, 1))
796 * The left-hand expressions must contain some Vars of the current query,
797 * else it's not gonna be a join.
799 left_varnos = pull_varnos((Node *) left_exprs);
800 if (bms_is_empty(left_varnos))
803 /* ... and the right-hand expressions better not contain Vars at all */
804 Assert(!contain_var_clause((Node *) right_exprs));
807 * The combining operators and left-hand expressions mustn't be volatile.
809 if (contain_volatile_functions(sublink->testexpr))
813 * Okay, pull up the sub-select into top range table and jointree.
815 * We rely here on the assumption that the outer query has no references
816 * to the inner (necessarily true, other than the Vars that we build
817 * below). Therefore this is a lot easier than what pull_up_subqueries has
820 rte = addRangeTableEntryForSubquery(NULL,
822 makeAlias("IN_subquery", NIL),
824 parse->rtable = lappend(parse->rtable, rte);
825 rtindex = list_length(parse->rtable);
826 rtr = makeNode(RangeTblRef);
827 rtr->rtindex = rtindex;
828 parse->jointree->fromlist = lappend(parse->jointree->fromlist, rtr);
831 * Build a list of Vars representing the subselect outputs.
833 subquery_vars = generate_subquery_vars(root,
834 subselect->targetList,
838 * Build the result qual expression, replacing Params with these Vars.
840 result = convert_testexpr(root,
845 * Now build the InClauseInfo node.
847 ininfo = makeNode(InClauseInfo);
848 ininfo->lefthand = left_varnos;
849 ininfo->righthand = bms_make_singleton(rtindex);
850 ininfo->in_operators = in_operators;
853 * ininfo->sub_targetlist must be filled with a list of expressions that
854 * would need to be unique-ified if we try to implement the IN using a
855 * regular join to unique-ified subquery output. This is most easily done
856 * by applying convert_testexpr to just the RHS inputs of the testexpr
857 * operators. That handles cases like type coercions of the subquery
858 * outputs, clauses dropped due to const-simplification, etc.
860 ininfo->sub_targetlist = (List *) convert_testexpr(root,
861 (Node *) right_exprs,
864 /* Add the completed node to the query's list */
865 root->in_info_list = lappend(root->in_info_list, ininfo);
871 * Replace correlation vars (uplevel vars) with Params.
873 * Uplevel aggregates are replaced, too.
875 * Note: it is critical that this runs immediately after SS_process_sublinks.
876 * Since we do not recurse into the arguments of uplevel aggregates, they will
877 * get copied to the appropriate subplan args list in the parent query with
878 * uplevel vars not replaced by Params, but only adjusted in level (see
879 * replace_outer_agg). That's exactly what we want for the vars of the parent
880 * level --- but if an aggregate's argument contains any further-up variables,
881 * they have to be replaced with Params in their turn. That will happen when
882 * the parent level runs SS_replace_correlation_vars. Therefore it must do
883 * so after expanding its sublinks to subplans. And we don't want any steps
884 * in between, else those steps would never get applied to the aggregate
885 * argument expressions, either in the parent or the child level.
888 SS_replace_correlation_vars(PlannerInfo *root, Node *expr)
890 /* No setup needed for tree walk, so away we go */
891 return replace_correlation_vars_mutator(expr, root);
895 replace_correlation_vars_mutator(Node *node, PlannerInfo *root)
901 if (((Var *) node)->varlevelsup > 0)
902 return (Node *) replace_outer_var(root, (Var *) node);
904 if (IsA(node, Aggref))
906 if (((Aggref *) node)->agglevelsup > 0)
907 return (Node *) replace_outer_agg(root, (Aggref *) node);
909 return expression_tree_mutator(node,
910 replace_correlation_vars_mutator,
915 * Expand SubLinks to SubPlans in the given expression.
917 * The isQual argument tells whether or not this expression is a WHERE/HAVING
918 * qualifier expression. If it is, any sublinks appearing at top level need
919 * not distinguish FALSE from UNKNOWN return values.
922 SS_process_sublinks(PlannerInfo *root, Node *expr, bool isQual)
924 process_sublinks_context context;
927 context.isTopQual = isQual;
928 return process_sublinks_mutator(expr, &context);
932 process_sublinks_mutator(Node *node, process_sublinks_context *context)
934 process_sublinks_context locContext;
936 locContext.root = context->root;
940 if (IsA(node, SubLink))
942 SubLink *sublink = (SubLink *) node;
946 * First, recursively process the lefthand-side expressions, if any.
947 * They're not top-level anymore.
949 locContext.isTopQual = false;
950 testexpr = process_sublinks_mutator(sublink->testexpr, &locContext);
953 * Now build the SubPlan node and make the expr to return.
955 return make_subplan(context->root,
962 * We should never see a SubPlan expression in the input (since this is
963 * the very routine that creates 'em to begin with). We shouldn't find
964 * ourselves invoked directly on a Query, either.
966 Assert(!is_subplan(node));
967 Assert(!IsA(node, Query));
970 * Because make_subplan() could return an AND or OR clause, we have to
971 * take steps to preserve AND/OR flatness of a qual. We assume the input
972 * has been AND/OR flattened and so we need no recursion here.
974 * If we recurse down through anything other than an AND node, we are
975 * definitely not at top qual level anymore. (Due to the coding here, we
976 * will not get called on the List subnodes of an AND, so no check is
979 if (and_clause(node))
984 /* Still at qual top-level */
985 locContext.isTopQual = context->isTopQual;
987 foreach(l, ((BoolExpr *) node)->args)
991 newarg = process_sublinks_mutator(lfirst(l), &locContext);
992 if (and_clause(newarg))
993 newargs = list_concat(newargs, ((BoolExpr *) newarg)->args);
995 newargs = lappend(newargs, newarg);
997 return (Node *) make_andclause(newargs);
1000 /* otherwise not at qual top-level */
1001 locContext.isTopQual = false;
1003 if (or_clause(node))
1005 List *newargs = NIL;
1008 foreach(l, ((BoolExpr *) node)->args)
1012 newarg = process_sublinks_mutator(lfirst(l), &locContext);
1013 if (or_clause(newarg))
1014 newargs = list_concat(newargs, ((BoolExpr *) newarg)->args);
1016 newargs = lappend(newargs, newarg);
1018 return (Node *) make_orclause(newargs);
1021 return expression_tree_mutator(node,
1022 process_sublinks_mutator,
1023 (void *) &locContext);
1027 * SS_finalize_plan - do final sublink processing for a completed Plan.
1029 * This recursively computes the extParam and allParam sets for every Plan
1030 * node in the given plan tree. It also optionally attaches any previously
1031 * generated InitPlans to the top plan node. (Any InitPlans should already
1032 * have been put through SS_finalize_plan.)
1035 SS_finalize_plan(PlannerInfo *root, Plan *plan, bool attach_initplans)
1037 Bitmapset *valid_params,
1045 * Examine any initPlans to determine the set of external params they
1046 * reference, the set of output params they supply, and their total cost.
1047 * We'll use at least some of this info below. (Note we are assuming that
1048 * finalize_plan doesn't touch the initPlans.)
1050 * In the case where attach_initplans is false, we are assuming that the
1051 * existing initPlans are siblings that might supply params needed by the
1054 initExtParam = initSetParam = NULL;
1056 foreach(l, root->init_plans)
1058 SubPlan *initsubplan = (SubPlan *) lfirst(l);
1059 Plan *initplan = planner_subplan_get_plan(root, initsubplan);
1062 initExtParam = bms_add_members(initExtParam, initplan->extParam);
1063 foreach(l2, initsubplan->setParam)
1065 initSetParam = bms_add_member(initSetParam, lfirst_int(l2));
1067 initplan_cost += get_initplan_cost(root, initsubplan);
1071 * Now determine the set of params that are validly referenceable in this
1072 * query level; to wit, those available from outer query levels plus the
1073 * output parameters of any initPlans. (We do not include output
1074 * parameters of regular subplans. Those should only appear within the
1075 * testexpr of SubPlan nodes, and are taken care of locally within
1076 * finalize_primnode.)
1078 * Note: this is a bit overly generous since some parameters of upper
1079 * query levels might belong to query subtrees that don't include this
1080 * query. However, valid_params is only a debugging crosscheck, so it
1081 * doesn't seem worth expending lots of cycles to try to be exact.
1083 valid_params = bms_copy(initSetParam);
1085 foreach(l, root->glob->paramlist)
1087 PlannerParamItem *pitem = (PlannerParamItem *) lfirst(l);
1089 if (pitem->abslevel < root->query_level)
1091 /* valid outer-level parameter */
1092 valid_params = bms_add_member(valid_params, paramid);
1099 * Now recurse through plan tree.
1101 (void) finalize_plan(root, plan, valid_params);
1103 bms_free(valid_params);
1106 * Finally, attach any initPlans to the topmost plan node, and add their
1107 * extParams to the topmost node's, too. However, any setParams of the
1108 * initPlans should not be present in the topmost node's extParams, only
1109 * in its allParams. (As of PG 8.1, it's possible that some initPlans
1110 * have extParams that are setParams of other initPlans, so we have to
1111 * take care of this situation explicitly.)
1113 * We also add the eval cost of each initPlan to the startup cost of the
1114 * top node. This is a conservative overestimate, since in fact each
1115 * initPlan might be executed later than plan startup, or even not at all.
1117 if (attach_initplans)
1119 plan->initPlan = root->init_plans;
1120 root->init_plans = NIL; /* make sure they're not attached twice */
1122 /* allParam must include all these params */
1123 plan->allParam = bms_add_members(plan->allParam, initExtParam);
1124 plan->allParam = bms_add_members(plan->allParam, initSetParam);
1125 /* extParam must include any child extParam */
1126 plan->extParam = bms_add_members(plan->extParam, initExtParam);
1127 /* but extParam shouldn't include any setParams */
1128 plan->extParam = bms_del_members(plan->extParam, initSetParam);
1129 /* ensure extParam is exactly NULL if it's empty */
1130 if (bms_is_empty(plan->extParam))
1131 plan->extParam = NULL;
1133 plan->startup_cost += initplan_cost;
1134 plan->total_cost += initplan_cost;
1139 * Recursive processing of all nodes in the plan tree
1141 * The return value is the computed allParam set for the given Plan node.
1142 * This is just an internal notational convenience.
1145 finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params)
1147 finalize_primnode_context context;
1152 context.root = root;
1153 context.paramids = NULL; /* initialize set to empty */
1156 * When we call finalize_primnode, context.paramids sets are automatically
1157 * merged together. But when recursing to self, we have to do it the hard
1158 * way. We want the paramids set to include params in subplans as well as
1162 /* Find params in targetlist and qual */
1163 finalize_primnode((Node *) plan->targetlist, &context);
1164 finalize_primnode((Node *) plan->qual, &context);
1166 /* Check additional node-type-specific fields */
1167 switch (nodeTag(plan))
1170 finalize_primnode(((Result *) plan)->resconstantqual,
1175 finalize_primnode((Node *) ((IndexScan *) plan)->indexqual,
1179 * we need not look at indexqualorig, since it will have the same
1180 * param references as indexqual.
1184 case T_BitmapIndexScan:
1185 finalize_primnode((Node *) ((BitmapIndexScan *) plan)->indexqual,
1189 * we need not look at indexqualorig, since it will have the same
1190 * param references as indexqual.
1194 case T_BitmapHeapScan:
1195 finalize_primnode((Node *) ((BitmapHeapScan *) plan)->bitmapqualorig,
1200 finalize_primnode((Node *) ((TidScan *) plan)->tidquals,
1204 case T_SubqueryScan:
1207 * In a SubqueryScan, SS_finalize_plan has already been run on the
1208 * subplan by the inner invocation of subquery_planner, so there's
1209 * no need to do it again. Instead, just pull out the subplan's
1210 * extParams list, which represents the params it needs from my
1211 * level and higher levels.
1213 context.paramids = bms_add_members(context.paramids,
1214 ((SubqueryScan *) plan)->subplan->extParam);
1217 case T_FunctionScan:
1218 finalize_primnode(((FunctionScan *) plan)->funcexpr,
1223 finalize_primnode((Node *) ((ValuesScan *) plan)->values_lists,
1231 foreach(l, ((Append *) plan)->appendplans)
1234 bms_add_members(context.paramids,
1246 foreach(l, ((BitmapAnd *) plan)->bitmapplans)
1249 bms_add_members(context.paramids,
1261 foreach(l, ((BitmapOr *) plan)->bitmapplans)
1264 bms_add_members(context.paramids,
1273 finalize_primnode((Node *) ((Join *) plan)->joinqual,
1278 finalize_primnode((Node *) ((Join *) plan)->joinqual,
1280 finalize_primnode((Node *) ((MergeJoin *) plan)->mergeclauses,
1285 finalize_primnode((Node *) ((Join *) plan)->joinqual,
1287 finalize_primnode((Node *) ((HashJoin *) plan)->hashclauses,
1292 finalize_primnode(((Limit *) plan)->limitOffset,
1294 finalize_primnode(((Limit *) plan)->limitCount,
1309 elog(ERROR, "unrecognized node type: %d",
1310 (int) nodeTag(plan));
1313 /* Process left and right child plans, if any */
1314 context.paramids = bms_add_members(context.paramids,
1319 context.paramids = bms_add_members(context.paramids,
1324 /* Now we have all the paramids */
1326 if (!bms_is_subset(context.paramids, valid_params))
1327 elog(ERROR, "plan should not reference subplan's variable");
1330 * Note: by definition, extParam and allParam should have the same value
1331 * in any plan node that doesn't have child initPlans. We set them
1332 * equal here, and later SS_finalize_plan will update them properly
1333 * in node(s) that it attaches initPlans to.
1335 * For speed at execution time, make sure extParam/allParam are actually
1336 * NULL if they are empty sets.
1338 if (bms_is_empty(context.paramids))
1340 plan->extParam = NULL;
1341 plan->allParam = NULL;
1345 plan->extParam = context.paramids;
1346 plan->allParam = bms_copy(context.paramids);
1349 return plan->allParam;
1353 * finalize_primnode: add IDs of all PARAM_EXEC params appearing in the given
1354 * expression tree to the result set.
1357 finalize_primnode(Node *node, finalize_primnode_context *context)
1361 if (IsA(node, Param))
1363 if (((Param *) node)->paramkind == PARAM_EXEC)
1365 int paramid = ((Param *) node)->paramid;
1367 context->paramids = bms_add_member(context->paramids, paramid);
1369 return false; /* no more to do here */
1371 if (is_subplan(node))
1373 SubPlan *subplan = (SubPlan *) node;
1374 Plan *plan = planner_subplan_get_plan(context->root, subplan);
1376 Bitmapset *subparamids;
1378 /* Recurse into the testexpr, but not into the Plan */
1379 finalize_primnode(subplan->testexpr, context);
1382 * Remove any param IDs of output parameters of the subplan that were
1383 * referenced in the testexpr. These are not interesting for
1384 * parameter change signaling since we always re-evaluate the subplan.
1385 * Note that this wouldn't work too well if there might be uses of the
1386 * same param IDs elsewhere in the plan, but that can't happen because
1387 * generate_new_param never tries to merge params.
1389 foreach(lc, subplan->paramIds)
1391 context->paramids = bms_del_member(context->paramids,
1395 /* Also examine args list */
1396 finalize_primnode((Node *) subplan->args, context);
1399 * Add params needed by the subplan to paramids, but excluding those
1400 * we will pass down to it.
1402 subparamids = bms_copy(plan->extParam);
1403 foreach(lc, subplan->parParam)
1405 subparamids = bms_del_member(subparamids, lfirst_int(lc));
1407 context->paramids = bms_join(context->paramids, subparamids);
1409 return false; /* no more to do here */
1411 return expression_tree_walker(node, finalize_primnode,
1416 * SS_make_initplan_from_plan - given a plan tree, make it an InitPlan
1418 * The plan is expected to return a scalar value of the indicated type.
1419 * We build an EXPR_SUBLINK SubPlan node and put it into the initplan
1420 * list for the current query level. A Param that represents the initplan's
1421 * output is returned.
1423 * We assume the plan hasn't been put through SS_finalize_plan.
1426 SS_make_initplan_from_plan(PlannerInfo *root, Plan *plan,
1427 Oid resulttype, int32 resulttypmod)
1433 * We must run SS_finalize_plan(), since that's normally done before a
1434 * subplan gets put into the initplan list. Tell it not to attach any
1435 * pre-existing initplans to this one, since they are siblings not
1436 * children of this initplan. (This is something else that could perhaps
1437 * be cleaner if we did extParam/allParam processing in setrefs.c instead
1438 * of here? See notes for materialize_finished_plan.)
1442 * Build extParam/allParam sets for plan nodes.
1444 SS_finalize_plan(root, plan, false);
1447 * Add the subplan and its rtable to the global lists.
1449 root->glob->subplans = lappend(root->glob->subplans,
1451 root->glob->subrtables = lappend(root->glob->subrtables,
1452 root->parse->rtable);
1455 * Create a SubPlan node and add it to the outer list of InitPlans.
1456 * Note it has to appear after any other InitPlans it might depend on
1457 * (see comments in ExecReScan).
1459 node = makeNode(SubPlan);
1460 node->subLinkType = EXPR_SUBLINK;
1461 node->firstColType = get_first_col_type(plan);
1462 node->plan_id = list_length(root->glob->subplans);
1464 root->init_plans = lappend(root->init_plans, node);
1467 * The node can't have any inputs (since it's an initplan), so the
1468 * parParam and args lists remain empty.
1472 * Make a Param that will be the subplan's output.
1474 prm = generate_new_param(root, resulttype, resulttypmod);
1475 node->setParam = list_make1_int(prm->paramid);