Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * placeholder.c
4 : * PlaceHolderVar and PlaceHolderInfo manipulation routines
5 : *
6 : *
7 : * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
8 : * Portions Copyright (c) 1994, Regents of the University of California
9 : *
10 : *
11 : * IDENTIFICATION
12 : * src/backend/optimizer/util/placeholder.c
13 : *
14 : *-------------------------------------------------------------------------
15 : */
16 : #include "postgres.h"
17 :
18 : #include "nodes/nodeFuncs.h"
19 : #include "optimizer/cost.h"
20 : #include "optimizer/pathnode.h"
21 : #include "optimizer/placeholder.h"
22 : #include "optimizer/planmain.h"
23 : #include "optimizer/var.h"
24 : #include "utils/lsyscache.h"
25 :
26 : /* Local functions */
27 : static void find_placeholders_recurse(PlannerInfo *root, Node *jtnode);
28 : static void find_placeholders_in_expr(PlannerInfo *root, Node *expr);
29 :
30 :
31 : /*
32 : * make_placeholder_expr
33 : * Make a PlaceHolderVar for the given expression.
34 : *
35 : * phrels is the syntactic location (as a set of baserels) to attribute
36 : * to the expression.
37 : */
38 : PlaceHolderVar *
39 92 : make_placeholder_expr(PlannerInfo *root, Expr *expr, Relids phrels)
40 : {
41 92 : PlaceHolderVar *phv = makeNode(PlaceHolderVar);
42 :
43 92 : phv->phexpr = expr;
44 92 : phv->phrels = phrels;
45 92 : phv->phid = ++(root->glob->lastPHId);
46 92 : phv->phlevelsup = 0;
47 :
48 92 : return phv;
49 : }
50 :
51 : /*
52 : * find_placeholder_info
53 : * Fetch the PlaceHolderInfo for the given PHV
54 : *
55 : * If the PlaceHolderInfo doesn't exist yet, create it if create_new_ph is
56 : * true, else throw an error.
57 : *
58 : * This is separate from make_placeholder_expr because subquery pullup has
59 : * to make PlaceHolderVars for expressions that might not be used at all in
60 : * the upper query, or might not remain after const-expression simplification.
61 : * We build PlaceHolderInfos only for PHVs that are still present in the
62 : * simplified query passed to query_planner().
63 : *
64 : * Note: this should only be called after query_planner() has started. Also,
65 : * create_new_ph must not be TRUE after deconstruct_jointree begins, because
66 : * make_outerjoininfo assumes that we already know about all placeholders.
67 : */
68 : PlaceHolderInfo *
69 193 : find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv,
70 : bool create_new_ph)
71 : {
72 : PlaceHolderInfo *phinfo;
73 : Relids rels_used;
74 : ListCell *lc;
75 :
76 : /* if this ever isn't true, we'd need to be able to look in parent lists */
77 193 : Assert(phv->phlevelsup == 0);
78 :
79 238 : foreach(lc, root->placeholder_list)
80 : {
81 174 : phinfo = (PlaceHolderInfo *) lfirst(lc);
82 174 : if (phinfo->phid == phv->phid)
83 129 : return phinfo;
84 : }
85 :
86 : /* Not found, so create it */
87 64 : if (!create_new_ph)
88 0 : elog(ERROR, "too late to create a new PlaceHolderInfo");
89 :
90 64 : phinfo = makeNode(PlaceHolderInfo);
91 :
92 64 : phinfo->phid = phv->phid;
93 64 : phinfo->ph_var = copyObject(phv);
94 :
95 : /*
96 : * Any referenced rels that are outside the PHV's syntactic scope are
97 : * LATERAL references, which should be included in ph_lateral but not in
98 : * ph_eval_at. If no referenced rels are within the syntactic scope,
99 : * force evaluation at the syntactic location.
100 : */
101 64 : rels_used = pull_varnos((Node *) phv->phexpr);
102 64 : phinfo->ph_lateral = bms_difference(rels_used, phv->phrels);
103 64 : if (bms_is_empty(phinfo->ph_lateral))
104 54 : phinfo->ph_lateral = NULL; /* make it exactly NULL if empty */
105 64 : phinfo->ph_eval_at = bms_int_members(rels_used, phv->phrels);
106 : /* If no contained vars, force evaluation at syntactic location */
107 64 : if (bms_is_empty(phinfo->ph_eval_at))
108 : {
109 33 : phinfo->ph_eval_at = bms_copy(phv->phrels);
110 33 : Assert(!bms_is_empty(phinfo->ph_eval_at));
111 : }
112 : /* ph_eval_at may change later, see update_placeholder_eval_levels */
113 64 : phinfo->ph_needed = NULL; /* initially it's unused */
114 : /* for the moment, estimate width using just the datatype info */
115 64 : phinfo->ph_width = get_typavgwidth(exprType((Node *) phv->phexpr),
116 64 : exprTypmod((Node *) phv->phexpr));
117 :
118 64 : root->placeholder_list = lappend(root->placeholder_list, phinfo);
119 :
120 : /*
121 : * The PHV's contained expression may contain other, lower-level PHVs. We
122 : * now know we need to get those into the PlaceHolderInfo list, too, so we
123 : * may as well do that immediately.
124 : */
125 64 : find_placeholders_in_expr(root, (Node *) phinfo->ph_var->phexpr);
126 :
127 64 : return phinfo;
128 : }
129 :
130 : /*
131 : * find_placeholders_in_jointree
132 : * Search the jointree for PlaceHolderVars, and build PlaceHolderInfos
133 : *
134 : * We don't need to look at the targetlist because build_base_rel_tlists()
135 : * will already have made entries for any PHVs in the tlist.
136 : *
137 : * This is called before we begin deconstruct_jointree. Once we begin
138 : * deconstruct_jointree, all active placeholders must be present in
139 : * root->placeholder_list, because make_outerjoininfo and
140 : * update_placeholder_eval_levels require this info to be available
141 : * while we crawl up the join tree.
142 : */
143 : void
144 13777 : find_placeholders_in_jointree(PlannerInfo *root)
145 : {
146 : /* We need do nothing if the query contains no PlaceHolderVars */
147 13777 : if (root->glob->lastPHId != 0)
148 : {
149 : /* Start recursion at top of jointree */
150 77 : Assert(root->parse->jointree != NULL &&
151 : IsA(root->parse->jointree, FromExpr));
152 77 : find_placeholders_recurse(root, (Node *) root->parse->jointree);
153 : }
154 13777 : }
155 :
156 : /*
157 : * find_placeholders_recurse
158 : * One recursion level of find_placeholders_in_jointree.
159 : *
160 : * jtnode is the current jointree node to examine.
161 : */
162 : static void
163 640 : find_placeholders_recurse(PlannerInfo *root, Node *jtnode)
164 : {
165 640 : if (jtnode == NULL)
166 640 : return;
167 640 : if (IsA(jtnode, RangeTblRef))
168 : {
169 : /* No quals to deal with here */
170 : }
171 369 : else if (IsA(jtnode, FromExpr))
172 : {
173 190 : FromExpr *f = (FromExpr *) jtnode;
174 : ListCell *l;
175 :
176 : /*
177 : * First, recurse to handle child joins.
178 : */
179 395 : foreach(l, f->fromlist)
180 : {
181 205 : find_placeholders_recurse(root, lfirst(l));
182 : }
183 :
184 : /*
185 : * Now process the top-level quals.
186 : */
187 190 : find_placeholders_in_expr(root, f->quals);
188 : }
189 179 : else if (IsA(jtnode, JoinExpr))
190 : {
191 179 : JoinExpr *j = (JoinExpr *) jtnode;
192 :
193 : /*
194 : * First, recurse to handle child joins.
195 : */
196 179 : find_placeholders_recurse(root, j->larg);
197 179 : find_placeholders_recurse(root, j->rarg);
198 :
199 : /* Process the qual clauses */
200 179 : find_placeholders_in_expr(root, j->quals);
201 : }
202 : else
203 0 : elog(ERROR, "unrecognized node type: %d",
204 : (int) nodeTag(jtnode));
205 : }
206 :
207 : /*
208 : * find_placeholders_in_expr
209 : * Find all PlaceHolderVars in the given expression, and create
210 : * PlaceHolderInfo entries for them.
211 : */
212 : static void
213 433 : find_placeholders_in_expr(PlannerInfo *root, Node *expr)
214 : {
215 : List *vars;
216 : ListCell *vl;
217 :
218 : /*
219 : * pull_var_clause does more than we need here, but it'll do and it's
220 : * convenient to use.
221 : */
222 433 : vars = pull_var_clause(expr,
223 : PVC_RECURSE_AGGREGATES |
224 : PVC_RECURSE_WINDOWFUNCS |
225 : PVC_INCLUDE_PLACEHOLDERS);
226 889 : foreach(vl, vars)
227 : {
228 456 : PlaceHolderVar *phv = (PlaceHolderVar *) lfirst(vl);
229 :
230 : /* Ignore any plain Vars */
231 456 : if (!IsA(phv, PlaceHolderVar))
232 429 : continue;
233 :
234 : /* Create a PlaceHolderInfo entry if there's not one already */
235 27 : (void) find_placeholder_info(root, phv, true);
236 : }
237 433 : list_free(vars);
238 433 : }
239 :
240 : /*
241 : * update_placeholder_eval_levels
242 : * Adjust the target evaluation levels for placeholders
243 : *
244 : * The initial eval_at level set by find_placeholder_info was the set of
245 : * rels used in the placeholder's expression (or the whole subselect below
246 : * the placeholder's syntactic location, if the expr is variable-free).
247 : * If the query contains any outer joins that can null any of those rels,
248 : * we must delay evaluation to above those joins.
249 : *
250 : * We repeat this operation each time we add another outer join to
251 : * root->join_info_list. It's somewhat annoying to have to do that, but
252 : * since we don't have very much information on the placeholders' locations,
253 : * it's hard to avoid. Each placeholder's eval_at level must be correct
254 : * by the time it starts to figure in outer-join delay decisions for higher
255 : * outer joins.
256 : *
257 : * In future we might want to put additional policy/heuristics here to
258 : * try to determine an optimal evaluation level. The current rules will
259 : * result in evaluation at the lowest possible level. However, pushing a
260 : * placeholder eval up the tree is likely to further constrain evaluation
261 : * order for outer joins, so it could easily be counterproductive; and we
262 : * don't have enough information at this point to make an intelligent choice.
263 : */
264 : void
265 1521 : update_placeholder_eval_levels(PlannerInfo *root, SpecialJoinInfo *new_sjinfo)
266 : {
267 : ListCell *lc1;
268 :
269 1622 : foreach(lc1, root->placeholder_list)
270 : {
271 101 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc1);
272 101 : Relids syn_level = phinfo->ph_var->phrels;
273 : Relids eval_at;
274 : bool found_some;
275 : ListCell *lc2;
276 :
277 : /*
278 : * We don't need to do any work on this placeholder unless the
279 : * newly-added outer join is syntactically beneath its location.
280 : */
281 121 : if (!bms_is_subset(new_sjinfo->syn_lefthand, syn_level) ||
282 20 : !bms_is_subset(new_sjinfo->syn_righthand, syn_level))
283 86 : continue;
284 :
285 : /*
286 : * Check for delays due to lower outer joins. This is the same logic
287 : * as in check_outerjoin_delay in initsplan.c, except that we don't
288 : * have anything to do with the delay_upper_joins flags; delay of
289 : * upper outer joins will be handled later, based on the eval_at
290 : * values we compute now.
291 : */
292 15 : eval_at = phinfo->ph_eval_at;
293 :
294 : do
295 : {
296 22 : found_some = false;
297 48 : foreach(lc2, root->join_info_list)
298 : {
299 26 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc2);
300 :
301 : /* disregard joins not within the PHV's sub-select */
302 52 : if (!bms_is_subset(sjinfo->syn_lefthand, syn_level) ||
303 26 : !bms_is_subset(sjinfo->syn_righthand, syn_level))
304 0 : continue;
305 :
306 : /* do we reference any nullable rels of this OJ? */
307 28 : if (bms_overlap(eval_at, sjinfo->min_righthand) ||
308 2 : (sjinfo->jointype == JOIN_FULL &&
309 0 : bms_overlap(eval_at, sjinfo->min_lefthand)))
310 : {
311 : /* yes; have we included all its rels in eval_at? */
312 41 : if (!bms_is_subset(sjinfo->min_lefthand, eval_at) ||
313 17 : !bms_is_subset(sjinfo->min_righthand, eval_at))
314 : {
315 : /* no, so add them in */
316 7 : eval_at = bms_add_members(eval_at,
317 7 : sjinfo->min_lefthand);
318 7 : eval_at = bms_add_members(eval_at,
319 7 : sjinfo->min_righthand);
320 : /* we'll need another iteration */
321 7 : found_some = true;
322 : }
323 : }
324 : }
325 22 : } while (found_some);
326 :
327 : /* Can't move the PHV's eval_at level to above its syntactic level */
328 15 : Assert(bms_is_subset(eval_at, syn_level));
329 :
330 15 : phinfo->ph_eval_at = eval_at;
331 : }
332 1521 : }
333 :
334 : /*
335 : * fix_placeholder_input_needed_levels
336 : * Adjust the "needed at" levels for placeholder inputs
337 : *
338 : * This is called after we've finished determining the eval_at levels for
339 : * all placeholders. We need to make sure that all vars and placeholders
340 : * needed to evaluate each placeholder will be available at the scan or join
341 : * level where the evaluation will be done. (It might seem that scan-level
342 : * evaluations aren't interesting, but that's not so: a LATERAL reference
343 : * within a placeholder's expression needs to cause the referenced var or
344 : * placeholder to be marked as needed in the scan where it's evaluated.)
345 : * Note that this loop can have side-effects on the ph_needed sets of other
346 : * PlaceHolderInfos; that's okay because we don't examine ph_needed here, so
347 : * there are no ordering issues to worry about.
348 : */
349 : void
350 13777 : fix_placeholder_input_needed_levels(PlannerInfo *root)
351 : {
352 : ListCell *lc;
353 :
354 13841 : foreach(lc, root->placeholder_list)
355 : {
356 64 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
357 64 : List *vars = pull_var_clause((Node *) phinfo->ph_var->phexpr,
358 : PVC_RECURSE_AGGREGATES |
359 : PVC_RECURSE_WINDOWFUNCS |
360 : PVC_INCLUDE_PLACEHOLDERS);
361 :
362 64 : add_vars_to_targetlist(root, vars, phinfo->ph_eval_at, false);
363 64 : list_free(vars);
364 : }
365 13777 : }
366 :
367 : /*
368 : * add_placeholders_to_base_rels
369 : * Add any required PlaceHolderVars to base rels' targetlists.
370 : *
371 : * If any placeholder can be computed at a base rel and is needed above it,
372 : * add it to that rel's targetlist. This might look like it could be merged
373 : * with fix_placeholder_input_needed_levels, but it must be separate because
374 : * join removal happens in between, and can change the ph_eval_at sets. There
375 : * is essentially the same logic in add_placeholders_to_joinrel, but we can't
376 : * do that part until joinrels are formed.
377 : */
378 : void
379 13777 : add_placeholders_to_base_rels(PlannerInfo *root)
380 : {
381 : ListCell *lc;
382 :
383 13840 : foreach(lc, root->placeholder_list)
384 : {
385 63 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
386 63 : Relids eval_at = phinfo->ph_eval_at;
387 : int varno;
388 :
389 101 : if (bms_get_singleton_member(eval_at, &varno) &&
390 38 : bms_nonempty_difference(phinfo->ph_needed, eval_at))
391 : {
392 36 : RelOptInfo *rel = find_base_rel(root, varno);
393 :
394 72 : rel->reltarget->exprs = lappend(rel->reltarget->exprs,
395 36 : copyObject(phinfo->ph_var));
396 : /* reltarget's cost and width fields will be updated later */
397 : }
398 : }
399 13777 : }
400 :
401 : /*
402 : * add_placeholders_to_joinrel
403 : * Add any required PlaceHolderVars to a join rel's targetlist;
404 : * and if they contain lateral references, add those references to the
405 : * joinrel's direct_lateral_relids.
406 : *
407 : * A join rel should emit a PlaceHolderVar if (a) the PHV is needed above
408 : * this join level and (b) the PHV can be computed at or below this level.
409 : */
410 : void
411 5351 : add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
412 : RelOptInfo *outer_rel, RelOptInfo *inner_rel)
413 : {
414 5351 : Relids relids = joinrel->relids;
415 : ListCell *lc;
416 :
417 5608 : foreach(lc, root->placeholder_list)
418 : {
419 257 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
420 :
421 : /* Is it still needed above this joinrel? */
422 257 : if (bms_nonempty_difference(phinfo->ph_needed, relids))
423 : {
424 : /* Is it computable here? */
425 187 : if (bms_is_subset(phinfo->ph_eval_at, relids))
426 : {
427 : /* Yup, add it to the output */
428 238 : joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs,
429 119 : phinfo->ph_var);
430 119 : joinrel->reltarget->width += phinfo->ph_width;
431 :
432 : /*
433 : * Charge the cost of evaluating the contained expression if
434 : * the PHV can be computed here but not in either input. This
435 : * is a bit bogus because we make the decision based on the
436 : * first pair of possible input relations considered for the
437 : * joinrel. With other pairs, it might be possible to compute
438 : * the PHV in one input or the other, and then we'd be double
439 : * charging the PHV's cost for some join paths. For now, live
440 : * with that; but we might want to improve it later by
441 : * refiguring the reltarget costs for each pair of inputs.
442 : */
443 211 : if (!bms_is_subset(phinfo->ph_eval_at, outer_rel->relids) &&
444 92 : !bms_is_subset(phinfo->ph_eval_at, inner_rel->relids))
445 : {
446 : QualCost cost;
447 :
448 38 : cost_qual_eval_node(&cost, (Node *) phinfo->ph_var->phexpr,
449 : root);
450 38 : joinrel->reltarget->cost.startup += cost.startup;
451 38 : joinrel->reltarget->cost.per_tuple += cost.per_tuple;
452 : }
453 :
454 : /* Adjust joinrel's direct_lateral_relids as needed */
455 119 : joinrel->direct_lateral_relids =
456 119 : bms_add_members(joinrel->direct_lateral_relids,
457 119 : phinfo->ph_lateral);
458 : }
459 : }
460 : }
461 5351 : }
|
