1/*-------------------------------------------------------------------------
2 *
3 * placeholder.c
4 * PlaceHolderVar and PlaceHolderInfo manipulation routines
5 *
6 *
7 * Portions Copyright (c) 1996-2019, 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/optimizer.h"
21#include "optimizer/pathnode.h"
22#include "optimizer/placeholder.h"
23#include "optimizer/planmain.h"
24#include "utils/lsyscache.h"
25
26/* Local functions */
27static void find_placeholders_recurse(PlannerInfo *root, Node *jtnode);
28static 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 */
38PlaceHolderVar *
39make_placeholder_expr(PlannerInfo *root, Expr *expr, Relids phrels)
40{
41 PlaceHolderVar *phv = makeNode(PlaceHolderVar);
42
43 phv->phexpr = expr;
44 phv->phrels = phrels;
45 phv->phid = ++(root->glob->lastPHId);
46 phv->phlevelsup = 0;
47
48 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 */
68PlaceHolderInfo *
69find_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 Assert(phv->phlevelsup == 0);
78
79 foreach(lc, root->placeholder_list)
80 {
81 phinfo = (PlaceHolderInfo *) lfirst(lc);
82 if (phinfo->phid == phv->phid)
83 return phinfo;
84 }
85
86 /* Not found, so create it */
87 if (!create_new_ph)
88 elog(ERROR, "too late to create a new PlaceHolderInfo");
89
90 phinfo = makeNode(PlaceHolderInfo);
91
92 phinfo->phid = phv->phid;
93 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 rels_used = pull_varnos((Node *) phv->phexpr);
102 phinfo->ph_lateral = bms_difference(rels_used, phv->phrels);
103 if (bms_is_empty(phinfo->ph_lateral))
104 phinfo->ph_lateral = NULL; /* make it exactly NULL if empty */
105 phinfo->ph_eval_at = bms_int_members(rels_used, phv->phrels);
106 /* If no contained vars, force evaluation at syntactic location */
107 if (bms_is_empty(phinfo->ph_eval_at))
108 {
109 phinfo->ph_eval_at = bms_copy(phv->phrels);
110 Assert(!bms_is_empty(phinfo->ph_eval_at));
111 }
112 /* ph_eval_at may change later, see update_placeholder_eval_levels */
113 phinfo->ph_needed = NULL; /* initially it's unused */
114 /* for the moment, estimate width using just the datatype info */
115 phinfo->ph_width = get_typavgwidth(exprType((Node *) phv->phexpr),
116 exprTypmod((Node *) phv->phexpr));
117
118 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 find_placeholders_in_expr(root, (Node *) phinfo->ph_var->phexpr);
126
127 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 */
143void
144find_placeholders_in_jointree(PlannerInfo *root)
145{
146 /* We need do nothing if the query contains no PlaceHolderVars */
147 if (root->glob->lastPHId != 0)
148 {
149 /* Start recursion at top of jointree */
150 Assert(root->parse->jointree != NULL &&
151 IsA(root->parse->jointree, FromExpr));
152 find_placeholders_recurse(root, (Node *) root->parse->jointree);
153 }
154}
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 */
162static void
163find_placeholders_recurse(PlannerInfo *root, Node *jtnode)
164{
165 if (jtnode == NULL)
166 return;
167 if (IsA(jtnode, RangeTblRef))
168 {
169 /* No quals to deal with here */
170 }
171 else if (IsA(jtnode, FromExpr))
172 {
173 FromExpr *f = (FromExpr *) jtnode;
174 ListCell *l;
175
176 /*
177 * First, recurse to handle child joins.
178 */
179 foreach(l, f->fromlist)
180 {
181 find_placeholders_recurse(root, lfirst(l));
182 }
183
184 /*
185 * Now process the top-level quals.
186 */
187 find_placeholders_in_expr(root, f->quals);
188 }
189 else if (IsA(jtnode, JoinExpr))
190 {
191 JoinExpr *j = (JoinExpr *) jtnode;
192
193 /*
194 * First, recurse to handle child joins.
195 */
196 find_placeholders_recurse(root, j->larg);
197 find_placeholders_recurse(root, j->rarg);
198
199 /* Process the qual clauses */
200 find_placeholders_in_expr(root, j->quals);
201 }
202 else
203 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 */
212static void
213find_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 vars = pull_var_clause(expr,
223 PVC_RECURSE_AGGREGATES |
224 PVC_RECURSE_WINDOWFUNCS |
225 PVC_INCLUDE_PLACEHOLDERS);
226 foreach(vl, vars)
227 {
228 PlaceHolderVar *phv = (PlaceHolderVar *) lfirst(vl);
229
230 /* Ignore any plain Vars */
231 if (!IsA(phv, PlaceHolderVar))
232 continue;
233
234 /* Create a PlaceHolderInfo entry if there's not one already */
235 (void) find_placeholder_info(root, phv, true);
236 }
237 list_free(vars);
238}
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 */
264void
265update_placeholder_eval_levels(PlannerInfo *root, SpecialJoinInfo *new_sjinfo)
266{
267 ListCell *lc1;
268
269 foreach(lc1, root->placeholder_list)
270 {
271 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc1);
272 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 if (!bms_is_subset(new_sjinfo->syn_lefthand, syn_level) ||
282 !bms_is_subset(new_sjinfo->syn_righthand, syn_level))
283 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 eval_at = phinfo->ph_eval_at;
293
294 do
295 {
296 found_some = false;
297 foreach(lc2, root->join_info_list)
298 {
299 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc2);
300
301 /* disregard joins not within the PHV's sub-select */
302 if (!bms_is_subset(sjinfo->syn_lefthand, syn_level) ||
303 !bms_is_subset(sjinfo->syn_righthand, syn_level))
304 continue;
305
306 /* do we reference any nullable rels of this OJ? */
307 if (bms_overlap(eval_at, sjinfo->min_righthand) ||
308 (sjinfo->jointype == JOIN_FULL &&
309 bms_overlap(eval_at, sjinfo->min_lefthand)))
310 {
311 /* yes; have we included all its rels in eval_at? */
312 if (!bms_is_subset(sjinfo->min_lefthand, eval_at) ||
313 !bms_is_subset(sjinfo->min_righthand, eval_at))
314 {
315 /* no, so add them in */
316 eval_at = bms_add_members(eval_at,
317 sjinfo->min_lefthand);
318 eval_at = bms_add_members(eval_at,
319 sjinfo->min_righthand);
320 /* we'll need another iteration */
321 found_some = true;
322 }
323 }
324 }
325 } while (found_some);
326
327 /* Can't move the PHV's eval_at level to above its syntactic level */
328 Assert(bms_is_subset(eval_at, syn_level));
329
330 phinfo->ph_eval_at = eval_at;
331 }
332}
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 */
349void
350fix_placeholder_input_needed_levels(PlannerInfo *root)
351{
352 ListCell *lc;
353
354 foreach(lc, root->placeholder_list)
355 {
356 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
357 List *vars = pull_var_clause((Node *) phinfo->ph_var->phexpr,
358 PVC_RECURSE_AGGREGATES |
359 PVC_RECURSE_WINDOWFUNCS |
360 PVC_INCLUDE_PLACEHOLDERS);
361
362 add_vars_to_targetlist(root, vars, phinfo->ph_eval_at, false);
363 list_free(vars);
364 }
365}
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 */
378void
379add_placeholders_to_base_rels(PlannerInfo *root)
380{
381 ListCell *lc;
382
383 foreach(lc, root->placeholder_list)
384 {
385 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
386 Relids eval_at = phinfo->ph_eval_at;
387 int varno;
388
389 if (bms_get_singleton_member(eval_at, &varno) &&
390 bms_nonempty_difference(phinfo->ph_needed, eval_at))
391 {
392 RelOptInfo *rel = find_base_rel(root, varno);
393
394 rel->reltarget->exprs = lappend(rel->reltarget->exprs,
395 copyObject(phinfo->ph_var));
396 /* reltarget's cost and width fields will be updated later */
397 }
398 }
399}
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 */
410void
411add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
412 RelOptInfo *outer_rel, RelOptInfo *inner_rel)
413{
414 Relids relids = joinrel->relids;
415 ListCell *lc;
416
417 foreach(lc, root->placeholder_list)
418 {
419 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
420
421 /* Is it still needed above this joinrel? */
422 if (bms_nonempty_difference(phinfo->ph_needed, relids))
423 {
424 /* Is it computable here? */
425 if (bms_is_subset(phinfo->ph_eval_at, relids))
426 {
427 /* Yup, add it to the output */
428 joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs,
429 phinfo->ph_var);
430 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 if (!bms_is_subset(phinfo->ph_eval_at, outer_rel->relids) &&
444 !bms_is_subset(phinfo->ph_eval_at, inner_rel->relids))
445 {
446 QualCost cost;
447
448 cost_qual_eval_node(&cost, (Node *) phinfo->ph_var->phexpr,
449 root);
450 joinrel->reltarget->cost.startup += cost.startup;
451 joinrel->reltarget->cost.per_tuple += cost.per_tuple;
452 }
453
454 /* Adjust joinrel's direct_lateral_relids as needed */
455 joinrel->direct_lateral_relids =
456 bms_add_members(joinrel->direct_lateral_relids,
457 phinfo->ph_lateral);
458 }
459 }
460 }
461}
462