Age Owner TLA Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * placeholder.c
4 : * PlaceHolderVar and PlaceHolderInfo manipulation routines
5 : *
6 : *
7 : * Portions Copyright (c) 1996-2023, 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 :
27 : typedef struct contain_placeholder_references_context
28 : {
29 : int relid;
30 : int sublevels_up;
31 : } contain_placeholder_references_context;
32 :
33 : /* Local functions */
34 : static void find_placeholders_recurse(PlannerInfo *root, Node *jtnode);
35 : static void find_placeholders_in_expr(PlannerInfo *root, Node *expr);
36 : static bool contain_placeholder_references_walker(Node *node,
37 : contain_placeholder_references_context *context);
38 :
39 :
40 : /*
41 : * make_placeholder_expr
42 : * Make a PlaceHolderVar for the given expression.
43 : *
44 : * phrels is the syntactic location (as a set of relids) to attribute
45 : * to the expression.
46 : *
47 : * The caller is responsible for adjusting phlevelsup and phnullingrels
48 : * as needed. Because we do not know here which query level the PHV
49 : * will be associated with, it's important that this function touches
50 : * only root->glob; messing with other parts of PlannerInfo would be
51 : * likely to do the wrong thing.
52 : */
53 : PlaceHolderVar *
5283 tgl 54 GIC 676 : make_placeholder_expr(PlannerInfo *root, Expr *expr, Relids phrels)
55 : {
56 676 : PlaceHolderVar *phv = makeNode(PlaceHolderVar);
57 :
58 676 : phv->phexpr = expr;
59 676 : phv->phrels = phrels;
69 tgl 60 GNC 676 : phv->phnullingrels = NULL; /* caller may change this later */
5283 tgl 61 GIC 676 : phv->phid = ++(root->glob->lastPHId);
69 tgl 62 GNC 676 : phv->phlevelsup = 0; /* caller may change this later */
63 :
5283 tgl 64 GIC 676 : return phv;
65 : }
66 :
67 : /*
68 : * find_placeholder_info
69 : * Fetch the PlaceHolderInfo for the given PHV
4261 tgl 70 ECB : *
71 : * If the PlaceHolderInfo doesn't exist yet, create it if we haven't yet
72 : * frozen the set of PlaceHolderInfos for the query; else throw an error.
73 : *
4576 74 : * This is separate from make_placeholder_expr because subquery pullup has
75 : * to make PlaceHolderVars for expressions that might not be used at all in
76 : * the upper query, or might not remain after const-expression simplification.
77 : * We build PlaceHolderInfos only for PHVs that are still present in the
78 : * simplified query passed to query_planner().
79 : *
80 : * Note: this should only be called after query_planner() has started.
81 : */
82 : PlaceHolderInfo *
235 tgl 83 GNC 2557 : find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv)
84 : {
85 : PlaceHolderInfo *phinfo;
86 : Relids rels_used;
87 :
88 : /* if this ever isn't true, we'd need to be able to look in parent lists */
5283 tgl 89 GIC 2557 : Assert(phv->phlevelsup == 0);
90 :
91 : /* Use placeholder_array to look up existing PlaceHolderInfo quickly */
235 tgl 92 GNC 2557 : if (phv->phid < root->placeholder_array_size)
93 2208 : phinfo = root->placeholder_array[phv->phid];
94 : else
95 349 : phinfo = NULL;
96 2557 : if (phinfo != NULL)
97 : {
98 2088 : Assert(phinfo->phid == phv->phid);
99 2088 : return phinfo;
100 : }
101 :
102 : /* Not found, so create it */
103 469 : if (root->placeholdersFrozen)
4261 tgl 104 UIC 0 : elog(ERROR, "too late to create a new PlaceHolderInfo");
4261 tgl 105 ECB :
5282 tgl 106 GIC 469 : phinfo = makeNode(PlaceHolderInfo);
107 :
5282 tgl 108 CBC 469 : phinfo->phid = phv->phid;
109 469 : phinfo->ph_var = copyObject(phv);
110 :
111 : /*
112 : * By convention, phinfo->ph_var->phnullingrels is always empty, since the
113 : * PlaceHolderInfo represents the initially-calculated state of the
114 : * PlaceHolderVar. PlaceHolderVars appearing in the query tree might have
115 : * varying values of phnullingrels, reflecting outer joins applied above
116 : * the calculation level.
117 : */
69 tgl 118 GNC 469 : phinfo->ph_var->phnullingrels = NULL;
119 :
3522 tgl 120 ECB : /*
121 : * Any referenced rels that are outside the PHV's syntactic scope are
122 : * LATERAL references, which should be included in ph_lateral but not in
3260 bruce 123 : * ph_eval_at. If no referenced rels are within the syntactic scope,
3522 tgl 124 : * force evaluation at the syntactic location.
125 : */
808 tgl 126 GIC 469 : rels_used = pull_varnos(root, (Node *) phv->phexpr);
3522 127 469 : phinfo->ph_lateral = bms_difference(rels_used, phv->phrels);
128 469 : phinfo->ph_eval_at = bms_int_members(rels_used, phv->phrels);
3522 tgl 129 ECB : /* If no contained vars, force evaluation at syntactic location */
3522 tgl 130 GIC 469 : if (bms_is_empty(phinfo->ph_eval_at))
3522 tgl 131 ECB : {
3522 tgl 132 CBC 328 : phinfo->ph_eval_at = bms_copy(phv->phrels);
3522 tgl 133 GIC 328 : Assert(!bms_is_empty(phinfo->ph_eval_at));
134 : }
5050 bruce 135 469 : phinfo->ph_needed = NULL; /* initially it's unused */
136 : /* for the moment, estimate width using just the datatype info */
5282 tgl 137 469 : phinfo->ph_width = get_typavgwidth(exprType((Node *) phv->phexpr),
138 469 : exprTypmod((Node *) phv->phexpr));
139 :
140 : /*
141 : * Add to both placeholder_list and placeholder_array. Note: because we
142 : * store pointers to the PlaceHolderInfos in two data structures, it'd be
143 : * unsafe to pass the whole placeholder_list structure through
144 : * expression_tree_mutator or the like --- or at least, you'd have to
145 : * rebuild the placeholder_array afterwards.
146 : */
5282 tgl 147 CBC 469 : root->placeholder_list = lappend(root->placeholder_list, phinfo);
148 :
235 tgl 149 GNC 469 : if (phinfo->phid >= root->placeholder_array_size)
150 : {
151 : /* Must allocate or enlarge placeholder_array */
152 : int new_size;
153 :
154 349 : new_size = root->placeholder_array_size ? root->placeholder_array_size * 2 : 8;
155 349 : while (phinfo->phid >= new_size)
235 tgl 156 UNC 0 : new_size *= 2;
235 tgl 157 GNC 349 : if (root->placeholder_array)
148 peter 158 UNC 0 : root->placeholder_array =
159 0 : repalloc0_array(root->placeholder_array, PlaceHolderInfo *, root->placeholder_array_size, new_size);
160 : else
148 peter 161 GNC 349 : root->placeholder_array =
162 349 : palloc0_array(PlaceHolderInfo *, new_size);
235 tgl 163 349 : root->placeholder_array_size = new_size;
164 : }
165 469 : root->placeholder_array[phinfo->phid] = phinfo;
166 :
167 : /*
168 : * The PHV's contained expression may contain other, lower-level PHVs. We
169 : * now know we need to get those into the PlaceHolderInfo list, too, so we
170 : * may as well do that immediately.
171 : */
3525 tgl 172 GIC 469 : find_placeholders_in_expr(root, (Node *) phinfo->ph_var->phexpr);
3525 tgl 173 ECB :
5282 tgl 174 CBC 469 : return phinfo;
5283 tgl 175 ECB : }
176 :
177 : /*
178 : * find_placeholders_in_jointree
4041 179 : * Search the jointree for PlaceHolderVars, and build PlaceHolderInfos
4576 180 : *
181 : * We don't need to look at the targetlist because build_base_rel_tlists()
4041 182 : * will already have made entries for any PHVs in the tlist.
183 : */
184 : void
4041 tgl 185 GIC 128145 : find_placeholders_in_jointree(PlannerInfo *root)
186 : {
187 : /* This must be done before freezing the set of PHIs */
235 tgl 188 GNC 128145 : Assert(!root->placeholdersFrozen);
189 :
190 : /* We need do nothing if the query contains no PlaceHolderVars */
4576 tgl 191 CBC 128145 : if (root->glob->lastPHId != 0)
192 : {
4041 tgl 193 ECB : /* Start recursion at top of jointree */
4576 tgl 194 GIC 500 : Assert(root->parse->jointree != NULL &&
195 : IsA(root->parse->jointree, FromExpr));
3525 196 500 : find_placeholders_recurse(root, (Node *) root->parse->jointree);
197 : }
4576 tgl 198 CBC 128145 : }
4576 tgl 199 ECB :
4576 tgl 200 EUB : /*
4576 tgl 201 ECB : * find_placeholders_recurse
4041 tgl 202 EUB : * One recursion level of find_placeholders_in_jointree.
4576 203 : *
204 : * jtnode is the current jointree node to examine.
4576 tgl 205 ECB : */
3525 206 : static void
4576 tgl 207 CBC 2721 : find_placeholders_recurse(PlannerInfo *root, Node *jtnode)
208 : {
209 2721 : if (jtnode == NULL)
3525 tgl 210 UIC 0 : return;
4576 tgl 211 GIC 2721 : if (IsA(jtnode, RangeTblRef))
212 : {
213 : /* No quals to deal with here */
214 : }
215 1373 : else if (IsA(jtnode, FromExpr))
4576 tgl 216 ECB : {
4576 tgl 217 GIC 614 : FromExpr *f = (FromExpr *) jtnode;
4576 tgl 218 ECB : ListCell *l;
219 :
220 : /*
221 : * First, recurse to handle child joins.
222 : */
4576 tgl 223 GIC 1317 : foreach(l, f->fromlist)
224 : {
3525 225 703 : find_placeholders_recurse(root, lfirst(l));
226 : }
227 :
228 : /*
4576 tgl 229 ECB : * Now process the top-level quals.
230 : */
3525 tgl 231 GIC 614 : find_placeholders_in_expr(root, f->quals);
4576 tgl 232 ECB : }
4576 tgl 233 GIC 759 : else if (IsA(jtnode, JoinExpr))
234 : {
4576 tgl 235 CBC 759 : JoinExpr *j = (JoinExpr *) jtnode;
236 :
237 : /*
3525 tgl 238 ECB : * First, recurse to handle child joins.
239 : */
3525 tgl 240 CBC 759 : find_placeholders_recurse(root, j->larg);
3525 tgl 241 GIC 759 : find_placeholders_recurse(root, j->rarg);
4576 tgl 242 ECB :
243 : /* Process the qual clauses */
3525 tgl 244 GIC 759 : find_placeholders_in_expr(root, j->quals);
245 : }
246 : else
4576 tgl 247 UIC 0 : elog(ERROR, "unrecognized node type: %d",
248 : (int) nodeTag(jtnode));
249 : }
250 :
4576 tgl 251 ECB : /*
252 : * find_placeholders_in_expr
3525 253 : * Find all PlaceHolderVars in the given expression, and create
3525 tgl 254 EUB : * PlaceHolderInfo entries for them.
4576 tgl 255 ECB : */
256 : static void
3525 tgl 257 GIC 1842 : find_placeholders_in_expr(PlannerInfo *root, Node *expr)
258 : {
4576 tgl 259 ECB : List *vars;
260 : ListCell *vl;
261 :
262 : /*
263 : * pull_var_clause does more than we need here, but it'll do and it's
264 : * convenient to use.
265 : */
4261 tgl 266 GIC 1842 : vars = pull_var_clause(expr,
2586 tgl 267 ECB : PVC_RECURSE_AGGREGATES |
268 : PVC_RECURSE_WINDOWFUNCS |
4289 269 : PVC_INCLUDE_PLACEHOLDERS);
4576 tgl 270 GIC 3913 : foreach(vl, vars)
271 : {
272 2071 : PlaceHolderVar *phv = (PlaceHolderVar *) lfirst(vl);
273 :
274 : /* Ignore any plain Vars */
4576 tgl 275 CBC 2071 : if (!IsA(phv, PlaceHolderVar))
4576 tgl 276 GIC 1819 : continue;
4576 tgl 277 ECB :
278 : /* Create a PlaceHolderInfo entry if there's not one already */
235 tgl 279 GNC 252 : (void) find_placeholder_info(root, phv);
280 : }
4576 tgl 281 GIC 1842 : list_free(vars);
282 1842 : }
283 :
284 : /*
4576 tgl 285 ECB : * fix_placeholder_input_needed_levels
286 : * Adjust the "needed at" levels for placeholder inputs
287 : *
288 : * This is called after we've finished determining the eval_at levels for
289 : * all placeholders. We need to make sure that all vars and placeholders
3522 290 : * needed to evaluate each placeholder will be available at the scan or join
291 : * level where the evaluation will be done. (It might seem that scan-level
292 : * evaluations aren't interesting, but that's not so: a LATERAL reference
293 : * within a placeholder's expression needs to cause the referenced var or
294 : * placeholder to be marked as needed in the scan where it's evaluated.)
295 : * Note that this loop can have side-effects on the ph_needed sets of other
296 : * PlaceHolderInfos; that's okay because we don't examine ph_needed here, so
297 : * there are no ordering issues to worry about.
298 : */
4576 299 : void
4576 tgl 300 GIC 128145 : fix_placeholder_input_needed_levels(PlannerInfo *root)
301 : {
4576 tgl 302 ECB : ListCell *lc;
303 :
4576 tgl 304 GIC 128614 : foreach(lc, root->placeholder_list)
305 : {
306 469 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
3522 tgl 307 CBC 469 : List *vars = pull_var_clause((Node *) phinfo->ph_var->phexpr,
308 : PVC_RECURSE_AGGREGATES |
309 : PVC_RECURSE_WINDOWFUNCS |
310 : PVC_INCLUDE_PLACEHOLDERS);
311 :
235 tgl 312 GNC 469 : add_vars_to_targetlist(root, vars, phinfo->ph_eval_at);
3522 tgl 313 GIC 469 : list_free(vars);
314 : }
4760 315 128145 : }
316 :
317 : /*
318 : * add_placeholders_to_base_rels
319 : * Add any required PlaceHolderVars to base rels' targetlists.
320 : *
321 : * If any placeholder can be computed at a base rel and is needed above it,
322 : * add it to that rel's targetlist. This might look like it could be merged
4576 tgl 323 ECB : * with fix_placeholder_input_needed_levels, but it must be separate because
324 : * join removal happens in between, and can change the ph_eval_at sets. There
325 : * is essentially the same logic in add_placeholders_to_joinrel, but we can't
326 : * do that part until joinrels are formed.
4760 327 : */
328 : void
4760 tgl 329 GIC 128145 : add_placeholders_to_base_rels(PlannerInfo *root)
4760 tgl 330 ECB : {
331 : ListCell *lc;
332 :
4760 tgl 333 GIC 128611 : foreach(lc, root->placeholder_list)
334 : {
4760 tgl 335 CBC 466 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
5282 tgl 336 GIC 466 : Relids eval_at = phinfo->ph_eval_at;
337 : int varno;
5282 tgl 338 ECB :
2676 tgl 339 GIC 797 : if (bms_get_singleton_member(eval_at, &varno) &&
340 331 : bms_nonempty_difference(phinfo->ph_needed, eval_at))
341 : {
5283 342 325 : RelOptInfo *rel = find_base_rel(root, varno);
343 :
344 : /*
345 : * As in add_vars_to_targetlist(), a value computed at scan level
346 : * has not yet been nulled by any outer join, so its phnullingrels
347 : * should be empty.
348 : */
69 tgl 349 GNC 325 : Assert(phinfo->ph_var->phnullingrels == NULL);
350 :
351 : /* Copying the PHV might be unnecessary here, but be safe */
2582 tgl 352 GIC 325 : rel->reltarget->exprs = lappend(rel->reltarget->exprs,
353 325 : copyObject(phinfo->ph_var));
354 : /* reltarget's cost and width fields will be updated later */
355 : }
356 : }
5283 357 128145 : }
358 :
359 : /*
360 : * add_placeholders_to_joinrel
361 : * Add any newly-computable PlaceHolderVars to a join rel's targetlist;
362 : * and if computable PHVs contain lateral references, add those
363 : * references to the joinrel's direct_lateral_relids.
364 : *
860 tgl 365 ECB : * A join rel should emit a PlaceHolderVar if (a) the PHV can be computed
366 : * at or below this join level and (b) the PHV is needed above this level.
367 : * Our caller build_join_rel() has already added any PHVs that were computed
368 : * in either join input rel, so we need add only newly-computable ones to
369 : * the targetlist. However, direct_lateral_relids must be updated for every
370 : * PHV computable at or below this join, as explained below.
371 : */
372 : void
2607 tgl 373 GIC 74563 : add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel,
374 : RelOptInfo *outer_rel, RelOptInfo *inner_rel,
375 : SpecialJoinInfo *sjinfo)
5283 tgl 376 ECB : {
5283 tgl 377 GIC 74563 : Relids relids = joinrel->relids;
5283 tgl 378 ECB : ListCell *lc;
379 :
5283 tgl 380 CBC 76287 : foreach(lc, root->placeholder_list)
5283 tgl 381 ECB : {
5283 tgl 382 CBC 1724 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
5283 tgl 383 ECB :
384 : /* Is it computable here? */
860 tgl 385 GIC 1724 : if (bms_is_subset(phinfo->ph_eval_at, relids))
386 : {
387 : /* Is it still needed above this joinrel? */
388 1154 : if (bms_nonempty_difference(phinfo->ph_needed, relids))
389 : {
390 : /*
391 : * Yes, but only add to tlist if it wasn't computed in either
392 : * input; otherwise it should be there already. Also, we
393 : * charge the cost of evaluating the contained expression if
394 : * the PHV can be computed here but not in either input. This
395 : * is a bit bogus because we make the decision based on the
396 : * first pair of possible input relations considered for the
397 : * joinrel. With other pairs, it might be possible to compute
398 : * the PHV in one input or the other, and then we'd be double
2607 tgl 399 ECB : * charging the PHV's cost for some join paths. For now, live
400 : * with that; but we might want to improve it later by
401 : * refiguring the reltarget costs for each pair of inputs.
402 : */
2607 tgl 403 GIC 761 : if (!bms_is_subset(phinfo->ph_eval_at, outer_rel->relids) &&
2607 tgl 404 CBC 535 : !bms_is_subset(phinfo->ph_eval_at, inner_rel->relids))
405 : {
406 : /* Copying might be unnecessary here, but be safe */
69 tgl 407 GNC 168 : PlaceHolderVar *phv = copyObject(phinfo->ph_var);
408 : QualCost cost;
409 :
410 : /*
411 : * It'll start out not nulled by anything. Joins above
412 : * this one might add to its phnullingrels later, in much
413 : * the same way as for Vars.
414 : */
415 168 : Assert(phv->phnullingrels == NULL);
416 :
235 417 168 : joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs,
418 : phv);
419 168 : cost_qual_eval_node(&cost, (Node *) phv->phexpr, root);
2582 tgl 420 GIC 168 : joinrel->reltarget->cost.startup += cost.startup;
421 168 : joinrel->reltarget->cost.per_tuple += cost.per_tuple;
235 tgl 422 GNC 168 : joinrel->reltarget->width += phinfo->ph_width;
423 : }
424 : }
425 :
426 : /*
427 : * Also adjust joinrel's direct_lateral_relids to include the
428 : * PHV's source rel(s). We must do this even if we're not
429 : * actually going to emit the PHV, otherwise join_is_legal() will
860 tgl 430 ECB : * reject valid join orderings. (In principle maybe we could
431 : * instead remove the joinrel's lateral_relids dependency; but
432 : * that's complicated to get right, and cases where we're not
433 : * going to emit the PHV are too rare to justify the work.)
434 : *
435 : * In principle we should only do this if the join doesn't yet
436 : * include the PHV's source rel(s). But our caller
437 : * build_join_rel() will clean things up by removing the join's
438 : * own relids from its direct_lateral_relids, so we needn't
439 : * account for that here.
440 : */
860 tgl 441 CBC 1154 : joinrel->direct_lateral_relids =
860 tgl 442 GIC 1154 : bms_add_members(joinrel->direct_lateral_relids,
443 1154 : phinfo->ph_lateral);
444 : }
5283 tgl 445 ECB : }
5283 tgl 446 GIC 74563 : }
447 :
448 : /*
449 : * contain_placeholder_references_to
450 : * Detect whether any PlaceHolderVars in the given clause contain
451 : * references to the given relid (typically an OJ relid).
452 : *
453 : * "Contain" means that there's a use of the relid inside the PHV's
454 : * contained expression, so that changing the nullability status of
455 : * the rel might change what the PHV computes.
456 : *
457 : * The code here to cope with upper-level PHVs is likely dead, but keep it
458 : * anyway just in case.
459 : */
460 : bool
69 tgl 461 GNC 7672 : contain_placeholder_references_to(PlannerInfo *root, Node *clause,
462 : int relid)
463 : {
464 : contain_placeholder_references_context context;
465 :
466 : /* We can answer quickly in the common case that there's no PHVs at all */
467 7672 : if (root->glob->lastPHId == 0)
468 7428 : return false;
469 : /* Else run the recursive search */
470 244 : context.relid = relid;
471 244 : context.sublevels_up = 0;
472 244 : return contain_placeholder_references_walker(clause, &context);
473 : }
474 :
475 : static bool
476 862 : contain_placeholder_references_walker(Node *node,
477 : contain_placeholder_references_context *context)
478 : {
479 862 : if (node == NULL)
480 30 : return false;
481 832 : if (IsA(node, PlaceHolderVar))
482 : {
483 21 : PlaceHolderVar *phv = (PlaceHolderVar *) node;
484 :
485 : /* We should just look through PHVs of other query levels */
486 21 : if (phv->phlevelsup == context->sublevels_up)
487 : {
488 : /* If phrels matches, we found what we came for */
489 21 : if (bms_is_member(context->relid, phv->phrels))
490 6 : return true;
491 :
492 : /*
493 : * We should not examine phnullingrels: what we are looking for is
494 : * references in the contained expression, not OJs that might null
495 : * the result afterwards. Also, we don't need to recurse into the
496 : * contained expression, because phrels should adequately
497 : * summarize what's in there. So we're done here.
498 : */
499 15 : return false;
500 : }
501 : }
502 811 : else if (IsA(node, Query))
503 : {
504 : /* Recurse into RTE subquery or not-yet-planned sublink subquery */
505 : bool result;
506 :
69 tgl 507 UNC 0 : context->sublevels_up++;
508 0 : result = query_tree_walker((Query *) node,
509 : contain_placeholder_references_walker,
510 : context,
511 : 0);
512 0 : context->sublevels_up--;
513 0 : return result;
514 : }
69 tgl 515 GNC 811 : return expression_tree_walker(node, contain_placeholder_references_walker,
516 : context);
517 : }
|
