1 /*-------------------------------------------------------------------------
4 * Planning routines for subselects and parameters.
6 * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
7 * Portions Copyright (c) 1994, Regents of the University of California
10 * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/subselect.c,v 1.29 2000/03/02 04:08:16 tgl Exp $
12 *-------------------------------------------------------------------------
16 #include "catalog/pg_operator.h"
17 #include "catalog/pg_type.h"
18 #include "nodes/makefuncs.h"
19 #include "nodes/nodeFuncs.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 "parser/parse_expr.h"
26 #include "parser/parse_node.h"
27 #include "parser/parse_oper.h"
28 #include "utils/lsyscache.h"
31 int PlannerQueryLevel; /* level of current query */
32 List *PlannerInitPlan; /* init subplans for current query */
33 List *PlannerParamVar; /* to get Var from Param->paramid */
34 int PlannerPlanId; /* to assign unique ID to subquery plans */
36 /*--------------------
37 * PlannerParamVar is a list of Var nodes, wherein the n'th entry
38 * (n counts from 0) corresponds to Param->paramid = n. The Var nodes
39 * are ordinary except for one thing: their varlevelsup field does NOT
40 * have the usual interpretation of "subplan levels out from current".
41 * Instead, it contains the absolute plan level, with the outermost
42 * plan being level 1 and nested plans having higher level numbers.
43 * This nonstandardness is useful because we don't have to run around
44 * and update the list elements when we enter or exit a subplan
45 * recursion level. But we must pay attention not to confuse this
46 * meaning with the normal meaning of varlevelsup.
52 * Create a new entry in the PlannerParamVar list, and return its index.
54 * var contains the data to be copied, except for varlevelsup which
55 * is set from the absolute level value given by varlevel.
58 new_param(Var *var, int varlevel)
60 Var *paramVar = (Var *) copyObject(var);
62 paramVar->varlevelsup = varlevel;
64 PlannerParamVar = lappend(PlannerParamVar, paramVar);
66 return length(PlannerParamVar) - 1;
70 * Generate a Param node to replace the given Var,
71 * which is expected to have varlevelsup > 0 (ie, it is not local).
81 Assert(var->varlevelsup > 0 && var->varlevelsup < PlannerQueryLevel);
82 varlevel = PlannerQueryLevel - var->varlevelsup;
85 * If there's already a PlannerParamVar entry for this same Var,
86 * just use it. NOTE: in situations involving UNION or inheritance,
87 * it is possible for the same varno/varlevel to refer to different RTEs
88 * in different parts of the parsetree, so that different fields might
89 * end up sharing the same Param number. As long as we check the vartype
90 * as well, I believe that this sort of aliasing will cause no trouble.
91 * The correct field should get stored into the Param slot at execution
92 * in each part of the tree.
95 foreach(ppv, PlannerParamVar)
97 Var *pvar = lfirst(ppv);
99 if (pvar->varno == var->varno &&
100 pvar->varattno == var->varattno &&
101 pvar->varlevelsup == varlevel &&
102 pvar->vartype == var->vartype)
109 /* Nope, so make a new one */
110 i = new_param(var, varlevel);
113 retval = makeNode(Param);
114 retval->paramkind = PARAM_EXEC;
115 retval->paramid = (AttrNumber) i;
116 retval->paramtype = var->vartype;
122 * Convert a bare SubLink (as created by the parser) into a SubPlan.
125 make_subplan(SubLink *slink)
127 SubPlan *node = makeNode(SubPlan);
128 Query *subquery = (Query *) (slink->subselect);
129 double tuple_fraction;
133 List *saved_ip = PlannerInitPlan;
135 PlannerInitPlan = NULL;
137 PlannerQueryLevel++; /* we becomes child */
140 * For an EXISTS subplan, tell lower-level planner to expect that
141 * only the first tuple will be retrieved. For ALL, ANY, and MULTIEXPR
142 * subplans, we will be able to stop evaluating if the test condition
143 * fails, so very often not all the tuples will be retrieved; for lack
144 * of a better idea, specify 50% retrieval. For EXPR_SUBLINK use default
147 * NOTE: if you change these numbers, also change cost_qual_eval_walker
150 if (slink->subLinkType == EXISTS_SUBLINK)
151 tuple_fraction = 1.0; /* just like a LIMIT 1 */
152 else if (slink->subLinkType == EXPR_SUBLINK)
153 tuple_fraction = -1.0; /* default behavior */
155 tuple_fraction = 0.5; /* 50% */
157 node->plan = plan = union_planner(subquery, tuple_fraction);
160 * Assign subPlan, extParam and locParam to plan nodes. At the moment,
161 * SS_finalize_plan doesn't handle initPlan-s and so we assign them
162 * to the topmost plan node and take care about its extParam too.
164 (void) SS_finalize_plan(plan);
165 plan->initPlan = PlannerInitPlan;
167 /* Create extParam list as union of InitPlan-s' lists */
168 foreach(lst, PlannerInitPlan)
172 foreach(lp, ((SubPlan *) lfirst(lst))->plan->extParam)
174 if (!intMember(lfirsti(lp), plan->extParam))
175 plan->extParam = lappendi(plan->extParam, lfirsti(lp));
179 /* and now we are parent again */
180 PlannerInitPlan = saved_ip;
183 node->plan_id = PlannerPlanId++;
184 node->rtable = subquery->rtable;
185 node->sublink = slink;
186 slink->subselect = NULL; /* cool ?! */
188 /* make parParam list of params coming from current query level */
189 foreach(lst, plan->extParam)
191 Var *var = nth(lfirsti(lst), PlannerParamVar);
193 /* note varlevelsup is absolute level number */
194 if (var->varlevelsup == PlannerQueryLevel)
195 node->parParam = lappendi(node->parParam, lfirsti(lst));
199 * Un-correlated or undirect correlated plans of EXISTS, EXPR, or
200 * MULTIEXPR types can be used as initPlans. For EXISTS or EXPR,
201 * we just produce a Param referring to the result of evaluating the
202 * initPlan. For MULTIEXPR, we must build an AND or OR-clause of the
203 * individual comparison operators, using the appropriate lefthand
204 * side expressions and Params for the initPlan's target items.
206 if (node->parParam == NIL && slink->subLinkType == EXISTS_SUBLINK)
208 Var *var = makeVar(0, 0, BOOLOID, -1, 0);
209 Param *prm = makeNode(Param);
211 prm->paramkind = PARAM_EXEC;
212 prm->paramid = (AttrNumber) new_param(var, PlannerQueryLevel);
213 prm->paramtype = var->vartype;
214 pfree(var); /* var is only needed for new_param */
215 node->setParam = lappendi(node->setParam, prm->paramid);
216 PlannerInitPlan = lappend(PlannerInitPlan, node);
217 result = (Node *) prm;
219 else if (node->parParam == NIL && slink->subLinkType == EXPR_SUBLINK)
221 TargetEntry *te = lfirst(plan->targetlist);
222 /* need a var node just to pass to new_param()... */
223 Var *var = makeVar(0, 0, te->resdom->restype,
224 te->resdom->restypmod, 0);
225 Param *prm = makeNode(Param);
227 prm->paramkind = PARAM_EXEC;
228 prm->paramid = (AttrNumber) new_param(var, PlannerQueryLevel);
229 prm->paramtype = var->vartype;
230 pfree(var); /* var is only needed for new_param */
231 node->setParam = lappendi(node->setParam, prm->paramid);
232 PlannerInitPlan = lappend(PlannerInitPlan, node);
233 result = (Node *) prm;
235 else if (node->parParam == NIL && slink->subLinkType == MULTIEXPR_SUBLINK)
241 * Convert oper list of Opers into a list of Exprs, using
242 * lefthand arguments and Params representing inside results.
244 foreach(lst, slink->oper)
246 Oper *oper = (Oper *) lfirst(lst);
247 Node *lefthand = nth(i, slink->lefthand);
248 TargetEntry *te = nth(i, plan->targetlist);
249 /* need a var node just to pass to new_param()... */
250 Var *var = makeVar(0, 0, te->resdom->restype,
251 te->resdom->restypmod, 0);
252 Param *prm = makeNode(Param);
254 Form_pg_operator opform;
258 prm->paramkind = PARAM_EXEC;
259 prm->paramid = (AttrNumber) new_param(var, PlannerQueryLevel);
260 prm->paramtype = var->vartype;
261 pfree(var); /* var is only needed for new_param */
263 Assert(IsA(oper, Oper));
264 tup = get_operator_tuple(oper->opno);
265 Assert(HeapTupleIsValid(tup));
266 opform = (Form_pg_operator) GETSTRUCT(tup);
267 /* Note: we use make_operand in case runtime type conversion
268 * function calls must be inserted for this operator!
270 left = make_operand("", lefthand,
271 exprType(lefthand), opform->oprleft);
272 right = make_operand("", (Node *) prm,
273 prm->paramtype, opform->oprright);
274 newoper = lappend(newoper,
278 node->setParam = lappendi(node->setParam, prm->paramid);
281 slink->oper = newoper;
282 slink->lefthand = NIL;
283 PlannerInitPlan = lappend(PlannerInitPlan, node);
285 result = (Node *) ((slink->useor) ? make_orclause(newoper) :
286 make_andclause(newoper));
288 result = (Node *) lfirst(newoper);
292 Expr *expr = makeNode(Expr);
298 * We can't convert subplans of ALL_SUBLINK or ANY_SUBLINK types to
299 * initPlans, even when they are uncorrelated or undirect correlated,
300 * because we need to scan the output of the subplan for each outer
301 * tuple. However, we have the option to tack a MATERIAL node onto
302 * the top of an uncorrelated/undirect correlated subplan, which lets
303 * us do the work of evaluating the subplan only once. We do this
304 * if the subplan's top plan node is anything more complicated than
305 * a sequential or index scan, and we do it even for those plan types
306 * if the qual appears selective enough to eliminate many tuples.
308 if (node->parParam == NIL)
312 switch (nodeTag(plan))
318 qualsel = clauselist_selectivity(subquery, plan->qual, 0);
319 /* Is 10% selectivity a good threshold?? */
320 use_material = qualsel < 0.10;
325 List *indxqual = ((IndexScan *) plan)->indxqualorig;
328 qualsel = clauselist_selectivity(subquery, plan->qual, 0);
329 qualsel *= clauselist_selectivity(subquery, indxqual, 0);
330 /* Note: if index is lossy, we just double-counted the
331 * index selectivity. Worth fixing?
333 /* Is 10% selectivity a good threshold?? */
334 use_material = qualsel < 0.10;
339 /* Don't add another Material node if there's one already,
340 * nor if the top node is a Sort, since Sort materializes
341 * its output anyway. (I doubt either case can happen in
342 * practice for a subplan, but...)
344 use_material = false;
352 plan = (Plan *) make_noname(plan->targetlist,
360 * Make expression of SUBPLAN type
362 expr->typeOid = BOOLOID; /* bogus, but we don't really care */
363 expr->opType = SUBPLAN_EXPR;
364 expr->oper = (Node *) node;
367 * Make expr->args from parParam.
369 foreach(lst, node->parParam)
371 Var *var = nth(lfirsti(lst), PlannerParamVar);
373 var = (Var *) copyObject(var);
374 /* Must fix absolute-level varlevelsup from the
375 * PlannerParamVar entry. But since var is at current
376 * subplan level, this is easy:
378 var->varlevelsup = 0;
379 args = lappend(args, var);
383 * Convert oper list of Opers into a list of Exprs, using
384 * lefthand arguments and Consts representing inside results.
386 foreach(lst, slink->oper)
388 Oper *oper = (Oper *) lfirst(lst);
389 Node *lefthand = nth(i, slink->lefthand);
390 TargetEntry *te = nth(i, plan->targetlist);
393 Form_pg_operator opform;
398 * XXX really ought to fill in constlen and constbyval correctly,
399 * but right now ExecEvalExpr won't look at them...
401 con = makeConst(te->resdom->restype, 0, 0, true, 0, 0, 0);
403 Assert(IsA(oper, Oper));
404 tup = get_operator_tuple(oper->opno);
405 Assert(HeapTupleIsValid(tup));
406 opform = (Form_pg_operator) GETSTRUCT(tup);
407 /* Note: we use make_operand in case runtime type conversion
408 * function calls must be inserted for this operator!
410 left = make_operand("", lefthand,
411 exprType(lefthand), opform->oprleft);
412 right = make_operand("", (Node *) con,
413 con->consttype, opform->oprright);
414 newoper = lappend(newoper,
420 slink->oper = newoper;
421 slink->lefthand = NIL;
422 result = (Node *) expr;
428 /* this oughta be merged with LispUnioni */
431 set_unioni(List *l1, List *l2)
438 return nconc(l1, set_differencei(l2, l1));
442 * finalize_primnode: build lists of subplans and params appearing
443 * in the given expression tree. NOTE: items are added to lists passed in,
444 * so caller must initialize lists to NIL before first call!
447 typedef struct finalize_primnode_results {
448 List *subplans; /* List of subplans found in expr */
449 List *paramids; /* List of PARAM_EXEC paramids found */
450 } finalize_primnode_results;
453 finalize_primnode(Node *node, finalize_primnode_results *results)
457 if (IsA(node, Param))
459 if (((Param *) node)->paramkind == PARAM_EXEC)
461 int paramid = (int) ((Param *) node)->paramid;
463 if (! intMember(paramid, results->paramids))
464 results->paramids = lconsi(paramid, results->paramids);
466 return false; /* no more to do here */
468 if (is_subplan(node))
470 SubPlan *subplan = (SubPlan *) ((Expr *) node)->oper;
473 /* Add subplan to subplans list */
474 results->subplans = lappend(results->subplans, subplan);
475 /* Check extParam list for params to add to paramids */
476 foreach(lst, subplan->plan->extParam)
478 int paramid = lfirsti(lst);
479 Var *var = nth(paramid, PlannerParamVar);
481 /* note varlevelsup is absolute level number */
482 if (var->varlevelsup < PlannerQueryLevel &&
483 ! intMember(paramid, results->paramids))
484 results->paramids = lconsi(paramid, results->paramids);
486 /* fall through to recurse into subplan args */
488 return expression_tree_walker(node, finalize_primnode,
493 * Replace correlation vars (uplevel vars) with Params.
496 static Node *replace_correlation_vars_mutator(Node *node, void *context);
499 SS_replace_correlation_vars(Node *expr)
501 /* No setup needed for tree walk, so away we go */
502 return replace_correlation_vars_mutator(expr, NULL);
506 replace_correlation_vars_mutator(Node *node, void *context)
512 if (((Var *) node)->varlevelsup > 0)
513 return (Node *) replace_var((Var *) node);
515 return expression_tree_mutator(node,
516 replace_correlation_vars_mutator,
521 * Expand SubLinks to SubPlans in the given expression.
524 static Node *process_sublinks_mutator(Node *node, void *context);
527 SS_process_sublinks(Node *expr)
529 /* No setup needed for tree walk, so away we go */
530 return process_sublinks_mutator(expr, NULL);
534 process_sublinks_mutator(Node *node, void *context)
538 if (IsA(node, SubLink))
540 SubLink *sublink = (SubLink *) node;
542 /* First, scan the lefthand-side expressions, if any.
543 * This is a tad klugy since we modify the input SubLink node,
544 * but that should be OK (make_subplan does it too!)
546 sublink->lefthand = (List *)
547 process_sublinks_mutator((Node *) sublink->lefthand, context);
548 /* Now build the SubPlan node and make the expr to return */
549 return make_subplan(sublink);
552 * Note that we will never see a SubPlan expression in the input
553 * (since this is the very routine that creates 'em to begin with).
554 * So the code in expression_tree_mutator() that might do
555 * inappropriate things with SubPlans or SubLinks will not be
558 Assert(! is_subplan(node));
560 return expression_tree_mutator(node,
561 process_sublinks_mutator,
566 SS_finalize_plan(Plan *plan)
568 List *extParam = NIL;
569 List *locParam = NIL;
570 finalize_primnode_results results;
576 results.subplans = NIL; /* initialize lists to NIL */
577 results.paramids = NIL;
579 * When we call finalize_primnode, results.paramids lists are
580 * automatically merged together. But when recursing to self,
581 * we have to do it the hard way. We want the paramids list
582 * to include params in subplans as well as at this level.
583 * (We don't care about finding subplans of subplans, though.)
586 /* Find params and subplans in targetlist and qual */
587 finalize_primnode((Node *) plan->targetlist, &results);
588 finalize_primnode((Node *) plan->qual, &results);
590 /* Check additional node-type-specific fields */
591 switch (nodeTag(plan))
594 finalize_primnode(((Result *) plan)->resconstantqual,
599 foreach(lst, ((Append *) plan)->appendplans)
600 results.paramids = set_unioni(results.paramids,
601 SS_finalize_plan((Plan *) lfirst(lst)));
605 finalize_primnode((Node *) ((IndexScan *) plan)->indxqual,
610 finalize_primnode((Node *) ((MergeJoin *) plan)->mergeclauses,
615 finalize_primnode((Node *) ((HashJoin *) plan)->hashclauses,
620 finalize_primnode((Node *) ((Hash *) plan)->hashkey,
625 finalize_primnode((Node *) ((TidScan *) plan)->tideval,
639 elog(ERROR, "SS_finalize_plan: node %d unsupported",
643 /* Process left and right subplans, if any */
644 results.paramids = set_unioni(results.paramids,
645 SS_finalize_plan(plan->lefttree));
646 results.paramids = set_unioni(results.paramids,
647 SS_finalize_plan(plan->righttree));
649 /* Now we have all the paramids and subplans */
651 foreach(lst, results.paramids)
653 Var *var = nth(lfirsti(lst), PlannerParamVar);
655 /* note varlevelsup is absolute level number */
656 if (var->varlevelsup < PlannerQueryLevel)
657 extParam = lappendi(extParam, lfirsti(lst));
658 else if (var->varlevelsup > PlannerQueryLevel)
659 elog(ERROR, "SS_finalize_plan: plan shouldn't reference subplan's variable");
662 Assert(var->varno == 0 && var->varattno == 0);
663 locParam = lappendi(locParam, lfirsti(lst));
667 plan->extParam = extParam;
668 plan->locParam = locParam;
669 plan->subPlan = results.subplans;
671 return results.paramids;
675 * Construct a list of all subplans found within the given node tree.
678 static bool SS_pull_subplan_walker(Node *node, List **listptr);
681 SS_pull_subplan(Node *expr)
685 SS_pull_subplan_walker(expr, &result);
690 SS_pull_subplan_walker(Node *node, List **listptr)
694 if (is_subplan(node))
696 *listptr = lappend(*listptr, ((Expr *) node)->oper);
697 /* fall through to check args to subplan */
699 return expression_tree_walker(node, SS_pull_subplan_walker,