PostgreSQL Source Code  git master
placeholder.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * placeholder.c
4  * PlaceHolderVar and PlaceHolderInfo manipulation routines
5  *
6  *
7  * Portions Copyright (c) 1996-2024, 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 
28 {
29  int relid;
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);
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  */
55 {
57 
58  phv->phexpr = expr;
59  phv->phrels = phrels;
60  phv->phnullingrels = NULL; /* caller may change this later */
61  phv->phid = ++(root->glob->lastPHId);
62  phv->phlevelsup = 0; /* caller may change this later */
63 
64  return phv;
65 }
66 
67 /*
68  * find_placeholder_info
69  * Fetch the PlaceHolderInfo for the given PHV
70  *
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  *
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  */
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 */
89  Assert(phv->phlevelsup == 0);
90 
91  /* Use placeholder_array to look up existing PlaceHolderInfo quickly */
92  if (phv->phid < root->placeholder_array_size)
93  phinfo = root->placeholder_array[phv->phid];
94  else
95  phinfo = NULL;
96  if (phinfo != NULL)
97  {
98  Assert(phinfo->phid == phv->phid);
99  return phinfo;
100  }
101 
102  /* Not found, so create it */
103  if (root->placeholdersFrozen)
104  elog(ERROR, "too late to create a new PlaceHolderInfo");
105 
106  phinfo = makeNode(PlaceHolderInfo);
107 
108  phinfo->phid = phv->phid;
109  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  */
118  phinfo->ph_var->phnullingrels = NULL;
119 
120  /*
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
123  * ph_eval_at. If no referenced rels are within the syntactic scope,
124  * force evaluation at the syntactic location.
125  */
126  rels_used = pull_varnos(root, (Node *) phv->phexpr);
127  phinfo->ph_lateral = bms_difference(rels_used, phv->phrels);
128  phinfo->ph_eval_at = bms_int_members(rels_used, phv->phrels);
129  /* If no contained vars, force evaluation at syntactic location */
130  if (bms_is_empty(phinfo->ph_eval_at))
131  {
132  phinfo->ph_eval_at = bms_copy(phv->phrels);
133  Assert(!bms_is_empty(phinfo->ph_eval_at));
134  }
135  phinfo->ph_needed = NULL; /* initially it's unused */
136  /* for the moment, estimate width using just the datatype info */
137  phinfo->ph_width = get_typavgwidth(exprType((Node *) phv->phexpr),
138  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  */
147  root->placeholder_list = lappend(root->placeholder_list, phinfo);
148 
149  if (phinfo->phid >= root->placeholder_array_size)
150  {
151  /* Must allocate or enlarge placeholder_array */
152  int new_size;
153 
154  new_size = root->placeholder_array_size ? root->placeholder_array_size * 2 : 8;
155  while (phinfo->phid >= new_size)
156  new_size *= 2;
157  if (root->placeholder_array)
158  root->placeholder_array =
159  repalloc0_array(root->placeholder_array, PlaceHolderInfo *, root->placeholder_array_size, new_size);
160  else
161  root->placeholder_array =
162  palloc0_array(PlaceHolderInfo *, new_size);
163  root->placeholder_array_size = new_size;
164  }
165  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  */
172  find_placeholders_in_expr(root, (Node *) phinfo->ph_var->phexpr);
173 
174  return phinfo;
175 }
176 
177 /*
178  * find_placeholders_in_jointree
179  * Search the jointree for PlaceHolderVars, and build PlaceHolderInfos
180  *
181  * We don't need to look at the targetlist because build_base_rel_tlists()
182  * will already have made entries for any PHVs in the tlist.
183  */
184 void
186 {
187  /* This must be done before freezing the set of PHIs */
188  Assert(!root->placeholdersFrozen);
189 
190  /* We need do nothing if the query contains no PlaceHolderVars */
191  if (root->glob->lastPHId != 0)
192  {
193  /* Start recursion at top of jointree */
194  Assert(root->parse->jointree != NULL &&
195  IsA(root->parse->jointree, FromExpr));
196  find_placeholders_recurse(root, (Node *) root->parse->jointree);
197  }
198 }
199 
200 /*
201  * find_placeholders_recurse
202  * One recursion level of find_placeholders_in_jointree.
203  *
204  * jtnode is the current jointree node to examine.
205  */
206 static void
208 {
209  if (jtnode == NULL)
210  return;
211  if (IsA(jtnode, RangeTblRef))
212  {
213  /* No quals to deal with here */
214  }
215  else if (IsA(jtnode, FromExpr))
216  {
217  FromExpr *f = (FromExpr *) jtnode;
218  ListCell *l;
219 
220  /*
221  * First, recurse to handle child joins.
222  */
223  foreach(l, f->fromlist)
224  {
226  }
227 
228  /*
229  * Now process the top-level quals.
230  */
232  }
233  else if (IsA(jtnode, JoinExpr))
234  {
235  JoinExpr *j = (JoinExpr *) jtnode;
236 
237  /*
238  * First, recurse to handle child joins.
239  */
242 
243  /* Process the qual clauses */
245  }
246  else
247  elog(ERROR, "unrecognized node type: %d",
248  (int) nodeTag(jtnode));
249 }
250 
251 /*
252  * find_placeholders_in_expr
253  * Find all PlaceHolderVars in the given expression, and create
254  * PlaceHolderInfo entries for them.
255  */
256 static void
258 {
259  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  */
266  vars = pull_var_clause(expr,
270  foreach(vl, vars)
271  {
272  PlaceHolderVar *phv = (PlaceHolderVar *) lfirst(vl);
273 
274  /* Ignore any plain Vars */
275  if (!IsA(phv, PlaceHolderVar))
276  continue;
277 
278  /* Create a PlaceHolderInfo entry if there's not one already */
279  (void) find_placeholder_info(root, phv);
280  }
281  list_free(vars);
282 }
283 
284 /*
285  * 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
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  */
299 void
301 {
302  ListCell *lc;
303 
304  foreach(lc, root->placeholder_list)
305  {
306  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
307  List *vars = pull_var_clause((Node *) phinfo->ph_var->phexpr,
311 
313  list_free(vars);
314  }
315 }
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
323  * 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.
327  */
328 void
330 {
331  ListCell *lc;
332 
333  foreach(lc, root->placeholder_list)
334  {
335  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
336  Relids eval_at = phinfo->ph_eval_at;
337  int varno;
338 
339  if (bms_get_singleton_member(eval_at, &varno) &&
340  bms_nonempty_difference(phinfo->ph_needed, eval_at))
341  {
342  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  */
349  Assert(phinfo->ph_var->phnullingrels == NULL);
350 
351  /* Copying the PHV might be unnecessary here, but be safe */
352  rel->reltarget->exprs = lappend(rel->reltarget->exprs,
353  copyObject(phinfo->ph_var));
354  /* reltarget's cost and width fields will be updated later */
355  }
356  }
357 }
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  *
365  * 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
374  RelOptInfo *outer_rel, RelOptInfo *inner_rel,
375  SpecialJoinInfo *sjinfo)
376 {
377  Relids relids = joinrel->relids;
378  int64 tuple_width = joinrel->reltarget->width;
379  ListCell *lc;
380 
381  foreach(lc, root->placeholder_list)
382  {
383  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
384 
385  /* Is it computable here? */
386  if (bms_is_subset(phinfo->ph_eval_at, relids))
387  {
388  /* Is it still needed above this joinrel? */
389  if (bms_nonempty_difference(phinfo->ph_needed, relids))
390  {
391  /*
392  * Yes, but only add to tlist if it wasn't computed in either
393  * input; otherwise it should be there already. Also, we
394  * charge the cost of evaluating the contained expression if
395  * the PHV can be computed here but not in either input. This
396  * is a bit bogus because we make the decision based on the
397  * first pair of possible input relations considered for the
398  * joinrel. With other pairs, it might be possible to compute
399  * the PHV in one input or the other, and then we'd be double
400  * charging the PHV's cost for some join paths. For now, live
401  * with that; but we might want to improve it later by
402  * refiguring the reltarget costs for each pair of inputs.
403  */
404  if (!bms_is_subset(phinfo->ph_eval_at, outer_rel->relids) &&
405  !bms_is_subset(phinfo->ph_eval_at, inner_rel->relids))
406  {
407  /* Copying might be unnecessary here, but be safe */
408  PlaceHolderVar *phv = copyObject(phinfo->ph_var);
409  QualCost cost;
410 
411  /*
412  * It'll start out not nulled by anything. Joins above
413  * this one might add to its phnullingrels later, in much
414  * the same way as for Vars.
415  */
416  Assert(phv->phnullingrels == NULL);
417 
418  joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs,
419  phv);
420  cost_qual_eval_node(&cost, (Node *) phv->phexpr, root);
421  joinrel->reltarget->cost.startup += cost.startup;
422  joinrel->reltarget->cost.per_tuple += cost.per_tuple;
423  tuple_width += phinfo->ph_width;
424  }
425  }
426 
427  /*
428  * Also adjust joinrel's direct_lateral_relids to include the
429  * PHV's source rel(s). We must do this even if we're not
430  * actually going to emit the PHV, otherwise join_is_legal() will
431  * reject valid join orderings. (In principle maybe we could
432  * instead remove the joinrel's lateral_relids dependency; but
433  * that's complicated to get right, and cases where we're not
434  * going to emit the PHV are too rare to justify the work.)
435  *
436  * In principle we should only do this if the join doesn't yet
437  * include the PHV's source rel(s). But our caller
438  * build_join_rel() will clean things up by removing the join's
439  * own relids from its direct_lateral_relids, so we needn't
440  * account for that here.
441  */
442  joinrel->direct_lateral_relids =
444  phinfo->ph_lateral);
445  }
446  }
447 
448  joinrel->reltarget->width = clamp_width_est(tuple_width);
449 }
450 
451 /*
452  * contain_placeholder_references_to
453  * Detect whether any PlaceHolderVars in the given clause contain
454  * references to the given relid (typically an OJ relid).
455  *
456  * "Contain" means that there's a use of the relid inside the PHV's
457  * contained expression, so that changing the nullability status of
458  * the rel might change what the PHV computes.
459  *
460  * The code here to cope with upper-level PHVs is likely dead, but keep it
461  * anyway just in case.
462  */
463 bool
465  int relid)
466 {
468 
469  /* We can answer quickly in the common case that there's no PHVs at all */
470  if (root->glob->lastPHId == 0)
471  return false;
472  /* Else run the recursive search */
473  context.relid = relid;
474  context.sublevels_up = 0;
476 }
477 
478 static bool
481 {
482  if (node == NULL)
483  return false;
484  if (IsA(node, PlaceHolderVar))
485  {
486  PlaceHolderVar *phv = (PlaceHolderVar *) node;
487 
488  /* We should just look through PHVs of other query levels */
489  if (phv->phlevelsup == context->sublevels_up)
490  {
491  /* If phrels matches, we found what we came for */
492  if (bms_is_member(context->relid, phv->phrels))
493  return true;
494 
495  /*
496  * We should not examine phnullingrels: what we are looking for is
497  * references in the contained expression, not OJs that might null
498  * the result afterwards. Also, we don't need to recurse into the
499  * contained expression, because phrels should adequately
500  * summarize what's in there. So we're done here.
501  */
502  return false;
503  }
504  }
505  else if (IsA(node, Query))
506  {
507  /* Recurse into RTE subquery or not-yet-planned sublink subquery */
508  bool result;
509 
510  context->sublevels_up++;
511  result = query_tree_walker((Query *) node,
513  context,
514  0);
515  context->sublevels_up--;
516  return result;
517  }
519  context);
520 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:412
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:510
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:346
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:917
Bitmapset * bms_int_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:1109
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:122
bool bms_get_singleton_member(const Bitmapset *a, int *member)
Definition: bitmapset.c:715
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:641
#define bms_is_empty(a)
Definition: bitmapset.h:118
#define Assert(condition)
Definition: c.h:858
void cost_qual_eval_node(QualCost *cost, Node *qual, PlannerInfo *root)
Definition: costsize.c:4666
int32 clamp_width_est(int64 tuple_width)
Definition: costsize.c:231
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:224
#define palloc0_array(type, count)
Definition: fe_memutils.h:65
void add_vars_to_targetlist(PlannerInfo *root, List *vars, Relids where_needed)
Definition: initsplan.c:279
int j
Definition: isn.c:74
List * lappend(List *list, void *datum)
Definition: list.c:339
void list_free(List *list)
Definition: list.c:1546
int32 get_typavgwidth(Oid typid, int32 typmod)
Definition: lsyscache.c:2578
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:42
int32 exprTypmod(const Node *expr)
Definition: nodeFuncs.c:298
#define query_tree_walker(q, w, c, f)
Definition: nodeFuncs.h:156
#define expression_tree_walker(n, w, c)
Definition: nodeFuncs.h:151
#define IsA(nodeptr, _type_)
Definition: nodes.h:158
#define copyObject(obj)
Definition: nodes.h:224
#define nodeTag(nodeptr)
Definition: nodes.h:133
#define makeNode(_type_)
Definition: nodes.h:155
#define PVC_RECURSE_AGGREGATES
Definition: optimizer.h:187
#define PVC_RECURSE_WINDOWFUNCS
Definition: optimizer.h:189
#define PVC_INCLUDE_PLACEHOLDERS
Definition: optimizer.h:190
#define repalloc0_array(pointer, type, oldcount, count)
Definition: palloc.h:109
#define lfirst(lc)
Definition: pg_list.h:172
bool contain_placeholder_references_to(PlannerInfo *root, Node *clause, int relid)
Definition: placeholder.c:464
PlaceHolderInfo * find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv)
Definition: placeholder.c:83
void add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo)
Definition: placeholder.c:373
void add_placeholders_to_base_rels(PlannerInfo *root)
Definition: placeholder.c:329
struct contain_placeholder_references_context contain_placeholder_references_context
static bool contain_placeholder_references_walker(Node *node, contain_placeholder_references_context *context)
Definition: placeholder.c:479
void fix_placeholder_input_needed_levels(PlannerInfo *root)
Definition: placeholder.c:300
PlaceHolderVar * make_placeholder_expr(PlannerInfo *root, Expr *expr, Relids phrels)
Definition: placeholder.c:54
static void find_placeholders_in_expr(PlannerInfo *root, Node *expr)
Definition: placeholder.c:257
static void find_placeholders_recurse(PlannerInfo *root, Node *jtnode)
Definition: placeholder.c:207
void find_placeholders_in_jointree(PlannerInfo *root)
Definition: placeholder.c:185
tree context
Definition: radixtree.h:1833
tree ctl root
Definition: radixtree.h:1884
RelOptInfo * find_base_rel(PlannerInfo *root, int relid)
Definition: relnode.c:414
Node * quals
Definition: primnodes.h:2311
List * fromlist
Definition: primnodes.h:2310
Definition: pg_list.h:54
Definition: nodes.h:129
List * exprs
Definition: pathnodes.h:1533
QualCost cost
Definition: pathnodes.h:1539
Relids ph_lateral
Definition: pathnodes.h:3091
Relids ph_needed
Definition: pathnodes.h:3094
Relids ph_eval_at
Definition: pathnodes.h:3088
PlaceHolderVar * ph_var
Definition: pathnodes.h:3085
Relids phnullingrels
Definition: pathnodes.h:2791
Index phlevelsup
Definition: pathnodes.h:2797
Cost per_tuple
Definition: pathnodes.h:48
Cost startup
Definition: pathnodes.h:47
Relids relids
Definition: pathnodes.h:865
struct PathTarget * reltarget
Definition: pathnodes.h:887
Relids direct_lateral_relids
Definition: pathnodes.h:905
Definition: regcomp.c:281
List * pull_var_clause(Node *node, int flags)
Definition: var.c:607
Relids pull_varnos(PlannerInfo *root, Node *node)
Definition: var.c:108