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-2022, 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 */
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  */
40 {
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 we haven't yet
56  * frozen the set of PlaceHolderInfos for the query; 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.
65  */
68 {
69  PlaceHolderInfo *phinfo;
70  Relids rels_used;
71 
72  /* if this ever isn't true, we'd need to be able to look in parent lists */
73  Assert(phv->phlevelsup == 0);
74 
75  /* Use placeholder_array to look up existing PlaceHolderInfo quickly */
76  if (phv->phid < root->placeholder_array_size)
77  phinfo = root->placeholder_array[phv->phid];
78  else
79  phinfo = NULL;
80  if (phinfo != NULL)
81  {
82  Assert(phinfo->phid == phv->phid);
83  return phinfo;
84  }
85 
86  /* Not found, so create it */
87  if (root->placeholdersFrozen)
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(root, (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  /*
119  * Add to both placeholder_list and placeholder_array. Note: because we
120  * store pointers to the PlaceHolderInfos in two data structures, it'd be
121  * unsafe to pass the whole placeholder_list structure through
122  * expression_tree_mutator or the like --- or at least, you'd have to
123  * rebuild the placeholder_array afterwards.
124  */
125  root->placeholder_list = lappend(root->placeholder_list, phinfo);
126 
127  if (phinfo->phid >= root->placeholder_array_size)
128  {
129  /* Must allocate or enlarge placeholder_array */
130  int new_size;
131 
132  new_size = root->placeholder_array_size ? root->placeholder_array_size * 2 : 8;
133  while (phinfo->phid >= new_size)
134  new_size *= 2;
135  if (root->placeholder_array)
136  root->placeholder_array =
137  repalloc0_array(root->placeholder_array, PlaceHolderInfo *, root->placeholder_array_size, new_size);
138  else
139  root->placeholder_array =
140  palloc0_array(PlaceHolderInfo *, new_size);
141  root->placeholder_array_size = new_size;
142  }
143  root->placeholder_array[phinfo->phid] = phinfo;
144 
145  /*
146  * The PHV's contained expression may contain other, lower-level PHVs. We
147  * now know we need to get those into the PlaceHolderInfo list, too, so we
148  * may as well do that immediately.
149  */
150  find_placeholders_in_expr(root, (Node *) phinfo->ph_var->phexpr);
151 
152  return phinfo;
153 }
154 
155 /*
156  * find_placeholders_in_jointree
157  * Search the jointree for PlaceHolderVars, and build PlaceHolderInfos
158  *
159  * We don't need to look at the targetlist because build_base_rel_tlists()
160  * will already have made entries for any PHVs in the tlist.
161  */
162 void
164 {
165  /* This must be done before freezing the set of PHIs */
166  Assert(!root->placeholdersFrozen);
167 
168  /* We need do nothing if the query contains no PlaceHolderVars */
169  if (root->glob->lastPHId != 0)
170  {
171  /* Start recursion at top of jointree */
172  Assert(root->parse->jointree != NULL &&
173  IsA(root->parse->jointree, FromExpr));
174  find_placeholders_recurse(root, (Node *) root->parse->jointree);
175  }
176 }
177 
178 /*
179  * find_placeholders_recurse
180  * One recursion level of find_placeholders_in_jointree.
181  *
182  * jtnode is the current jointree node to examine.
183  */
184 static void
186 {
187  if (jtnode == NULL)
188  return;
189  if (IsA(jtnode, RangeTblRef))
190  {
191  /* No quals to deal with here */
192  }
193  else if (IsA(jtnode, FromExpr))
194  {
195  FromExpr *f = (FromExpr *) jtnode;
196  ListCell *l;
197 
198  /*
199  * First, recurse to handle child joins.
200  */
201  foreach(l, f->fromlist)
202  {
204  }
205 
206  /*
207  * Now process the top-level quals.
208  */
210  }
211  else if (IsA(jtnode, JoinExpr))
212  {
213  JoinExpr *j = (JoinExpr *) jtnode;
214 
215  /*
216  * First, recurse to handle child joins.
217  */
218  find_placeholders_recurse(root, j->larg);
219  find_placeholders_recurse(root, j->rarg);
220 
221  /* Process the qual clauses */
222  find_placeholders_in_expr(root, j->quals);
223  }
224  else
225  elog(ERROR, "unrecognized node type: %d",
226  (int) nodeTag(jtnode));
227 }
228 
229 /*
230  * find_placeholders_in_expr
231  * Find all PlaceHolderVars in the given expression, and create
232  * PlaceHolderInfo entries for them.
233  */
234 static void
236 {
237  List *vars;
238  ListCell *vl;
239 
240  /*
241  * pull_var_clause does more than we need here, but it'll do and it's
242  * convenient to use.
243  */
244  vars = pull_var_clause(expr,
248  foreach(vl, vars)
249  {
250  PlaceHolderVar *phv = (PlaceHolderVar *) lfirst(vl);
251 
252  /* Ignore any plain Vars */
253  if (!IsA(phv, PlaceHolderVar))
254  continue;
255 
256  /* Create a PlaceHolderInfo entry if there's not one already */
257  (void) find_placeholder_info(root, phv);
258  }
259  list_free(vars);
260 }
261 
262 /*
263  * update_placeholder_eval_levels
264  * Adjust the target evaluation levels for placeholders
265  *
266  * The initial eval_at level set by find_placeholder_info was the set of
267  * rels used in the placeholder's expression (or the whole subselect below
268  * the placeholder's syntactic location, if the expr is variable-free).
269  * If the query contains any outer joins that can null any of those rels,
270  * we must delay evaluation to above those joins.
271  *
272  * We repeat this operation each time we add another outer join to
273  * root->join_info_list. It's somewhat annoying to have to do that, but
274  * since we don't have very much information on the placeholders' locations,
275  * it's hard to avoid. Each placeholder's eval_at level must be correct
276  * by the time it starts to figure in outer-join delay decisions for higher
277  * outer joins.
278  *
279  * In future we might want to put additional policy/heuristics here to
280  * try to determine an optimal evaluation level. The current rules will
281  * result in evaluation at the lowest possible level. However, pushing a
282  * placeholder eval up the tree is likely to further constrain evaluation
283  * order for outer joins, so it could easily be counterproductive; and we
284  * don't have enough information at this point to make an intelligent choice.
285  */
286 void
288 {
289  ListCell *lc1;
290 
291  foreach(lc1, root->placeholder_list)
292  {
293  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc1);
294  Relids syn_level = phinfo->ph_var->phrels;
295  Relids eval_at;
296  bool found_some;
297  ListCell *lc2;
298 
299  /*
300  * We don't need to do any work on this placeholder unless the
301  * newly-added outer join is syntactically beneath its location.
302  */
303  if (!bms_is_subset(new_sjinfo->syn_lefthand, syn_level) ||
304  !bms_is_subset(new_sjinfo->syn_righthand, syn_level))
305  continue;
306 
307  /*
308  * Check for delays due to lower outer joins. This is the same logic
309  * as in check_outerjoin_delay in initsplan.c, except that we don't
310  * have anything to do with the delay_upper_joins flags; delay of
311  * upper outer joins will be handled later, based on the eval_at
312  * values we compute now.
313  */
314  eval_at = phinfo->ph_eval_at;
315 
316  do
317  {
318  found_some = false;
319  foreach(lc2, root->join_info_list)
320  {
321  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc2);
322 
323  /* disregard joins not within the PHV's sub-select */
324  if (!bms_is_subset(sjinfo->syn_lefthand, syn_level) ||
325  !bms_is_subset(sjinfo->syn_righthand, syn_level))
326  continue;
327 
328  /* do we reference any nullable rels of this OJ? */
329  if (bms_overlap(eval_at, sjinfo->min_righthand) ||
330  (sjinfo->jointype == JOIN_FULL &&
331  bms_overlap(eval_at, sjinfo->min_lefthand)))
332  {
333  /* yes; have we included all its rels in eval_at? */
334  if (!bms_is_subset(sjinfo->min_lefthand, eval_at) ||
335  !bms_is_subset(sjinfo->min_righthand, eval_at))
336  {
337  /* no, so add them in */
338  eval_at = bms_add_members(eval_at,
339  sjinfo->min_lefthand);
340  eval_at = bms_add_members(eval_at,
341  sjinfo->min_righthand);
342  /* we'll need another iteration */
343  found_some = true;
344  }
345  }
346  }
347  } while (found_some);
348 
349  /* Can't move the PHV's eval_at level to above its syntactic level */
350  Assert(bms_is_subset(eval_at, syn_level));
351 
352  phinfo->ph_eval_at = eval_at;
353  }
354 }
355 
356 /*
357  * fix_placeholder_input_needed_levels
358  * Adjust the "needed at" levels for placeholder inputs
359  *
360  * This is called after we've finished determining the eval_at levels for
361  * all placeholders. We need to make sure that all vars and placeholders
362  * needed to evaluate each placeholder will be available at the scan or join
363  * level where the evaluation will be done. (It might seem that scan-level
364  * evaluations aren't interesting, but that's not so: a LATERAL reference
365  * within a placeholder's expression needs to cause the referenced var or
366  * placeholder to be marked as needed in the scan where it's evaluated.)
367  * Note that this loop can have side-effects on the ph_needed sets of other
368  * PlaceHolderInfos; that's okay because we don't examine ph_needed here, so
369  * there are no ordering issues to worry about.
370  */
371 void
373 {
374  ListCell *lc;
375 
376  foreach(lc, root->placeholder_list)
377  {
378  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
379  List *vars = pull_var_clause((Node *) phinfo->ph_var->phexpr,
383 
384  add_vars_to_targetlist(root, vars, phinfo->ph_eval_at);
385  list_free(vars);
386  }
387 }
388 
389 /*
390  * add_placeholders_to_base_rels
391  * Add any required PlaceHolderVars to base rels' targetlists.
392  *
393  * If any placeholder can be computed at a base rel and is needed above it,
394  * add it to that rel's targetlist. This might look like it could be merged
395  * with fix_placeholder_input_needed_levels, but it must be separate because
396  * join removal happens in between, and can change the ph_eval_at sets. There
397  * is essentially the same logic in add_placeholders_to_joinrel, but we can't
398  * do that part until joinrels are formed.
399  */
400 void
402 {
403  ListCell *lc;
404 
405  foreach(lc, root->placeholder_list)
406  {
407  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
408  Relids eval_at = phinfo->ph_eval_at;
409  int varno;
410 
411  if (bms_get_singleton_member(eval_at, &varno) &&
412  bms_nonempty_difference(phinfo->ph_needed, eval_at))
413  {
414  RelOptInfo *rel = find_base_rel(root, varno);
415 
416  rel->reltarget->exprs = lappend(rel->reltarget->exprs,
417  copyObject(phinfo->ph_var));
418  /* reltarget's cost and width fields will be updated later */
419  }
420  }
421 }
422 
423 /*
424  * add_placeholders_to_joinrel
425  * Add any newly-computable PlaceHolderVars to a join rel's targetlist;
426  * and if computable PHVs contain lateral references, add those
427  * references to the joinrel's direct_lateral_relids.
428  *
429  * A join rel should emit a PlaceHolderVar if (a) the PHV can be computed
430  * at or below this join level and (b) the PHV is needed above this level.
431  * Our caller build_join_rel() has already added any PHVs that were computed
432  * in either join input rel, so we need add only newly-computable ones to
433  * the targetlist. However, direct_lateral_relids must be updated for every
434  * PHV computable at or below this join, as explained below.
435  */
436 void
438  RelOptInfo *outer_rel, RelOptInfo *inner_rel)
439 {
440  Relids relids = joinrel->relids;
441  ListCell *lc;
442 
443  foreach(lc, root->placeholder_list)
444  {
445  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
446 
447  /* Is it computable here? */
448  if (bms_is_subset(phinfo->ph_eval_at, relids))
449  {
450  /* Is it still needed above this joinrel? */
451  if (bms_nonempty_difference(phinfo->ph_needed, relids))
452  {
453  /*
454  * Yes, but only add to tlist if it wasn't computed in either
455  * input; otherwise it should be there already. Also, we
456  * charge the cost of evaluating the contained expression if
457  * the PHV can be computed here but not in either input. This
458  * is a bit bogus because we make the decision based on the
459  * first pair of possible input relations considered for the
460  * joinrel. With other pairs, it might be possible to compute
461  * the PHV in one input or the other, and then we'd be double
462  * charging the PHV's cost for some join paths. For now, live
463  * with that; but we might want to improve it later by
464  * refiguring the reltarget costs for each pair of inputs.
465  */
466  if (!bms_is_subset(phinfo->ph_eval_at, outer_rel->relids) &&
467  !bms_is_subset(phinfo->ph_eval_at, inner_rel->relids))
468  {
469  PlaceHolderVar *phv = phinfo->ph_var;
470  QualCost cost;
471 
472  joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs,
473  phv);
474  cost_qual_eval_node(&cost, (Node *) phv->phexpr, root);
475  joinrel->reltarget->cost.startup += cost.startup;
476  joinrel->reltarget->cost.per_tuple += cost.per_tuple;
477  joinrel->reltarget->width += phinfo->ph_width;
478  }
479  }
480 
481  /*
482  * Also adjust joinrel's direct_lateral_relids to include the
483  * PHV's source rel(s). We must do this even if we're not
484  * actually going to emit the PHV, otherwise join_is_legal() will
485  * reject valid join orderings. (In principle maybe we could
486  * instead remove the joinrel's lateral_relids dependency; but
487  * that's complicated to get right, and cases where we're not
488  * going to emit the PHV are too rare to justify the work.)
489  *
490  * In principle we should only do this if the join doesn't yet
491  * include the PHV's source rel(s). But our caller
492  * build_join_rel() will clean things up by removing the join's
493  * own relids from its direct_lateral_relids, so we needn't
494  * account for that here.
495  */
496  joinrel->direct_lateral_relids =
498  phinfo->ph_lateral);
499  }
500  }
501 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:316
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:292
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:796
Bitmapset * bms_int_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:906
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:704
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:495
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:74
bool bms_get_singleton_member(const Bitmapset *a, int *member)
Definition: bitmapset.c:618
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:548
void cost_qual_eval_node(QualCost *cost, Node *qual, PlannerInfo *root)
Definition: costsize.c:4394
#define ERROR
Definition: elog.h:35
#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:228
int j
Definition: isn.c:74
Assert(fmt[strlen(fmt) - 1] !='\n')
List * lappend(List *list, void *datum)
Definition: list.c:338
void list_free(List *list)
Definition: list.c:1545
int32 get_typavgwidth(Oid typid, int32 typmod)
Definition: lsyscache.c:2536
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:43
int32 exprTypmod(const Node *expr)
Definition: nodeFuncs.c:266
#define IsA(nodeptr, _type_)
Definition: nodes.h:168
#define copyObject(obj)
Definition: nodes.h:233
#define nodeTag(nodeptr)
Definition: nodes.h:122
#define makeNode(_type_)
Definition: nodes.h:165
@ JOIN_FULL
Definition: nodes.h:295
#define PVC_RECURSE_AGGREGATES
Definition: optimizer.h:184
#define PVC_RECURSE_WINDOWFUNCS
Definition: optimizer.h:186
#define PVC_INCLUDE_PLACEHOLDERS
Definition: optimizer.h:187
#define repalloc0_array(pointer, type, oldcount, count)
Definition: palloc.h:107
#define lfirst(lc)
Definition: pg_list.h:170
PlaceHolderInfo * find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv)
Definition: placeholder.c:67
void add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel)
Definition: placeholder.c:437
void add_placeholders_to_base_rels(PlannerInfo *root)
Definition: placeholder.c:401
void update_placeholder_eval_levels(PlannerInfo *root, SpecialJoinInfo *new_sjinfo)
Definition: placeholder.c:287
void fix_placeholder_input_needed_levels(PlannerInfo *root)
Definition: placeholder.c:372
PlaceHolderVar * make_placeholder_expr(PlannerInfo *root, Expr *expr, Relids phrels)
Definition: placeholder.c:39
static void find_placeholders_in_expr(PlannerInfo *root, Node *expr)
Definition: placeholder.c:235
static void find_placeholders_recurse(PlannerInfo *root, Node *jtnode)
Definition: placeholder.c:185
void find_placeholders_in_jointree(PlannerInfo *root)
Definition: placeholder.c:163
RelOptInfo * find_base_rel(PlannerInfo *root, int relid)
Definition: relnode.c:360
Node * quals
Definition: primnodes.h:1665
List * fromlist
Definition: primnodes.h:1664
Definition: pg_list.h:52
Definition: nodes.h:118
List * exprs
Definition: pathnodes.h:1424
QualCost cost
Definition: pathnodes.h:1430
Relids ph_lateral
Definition: pathnodes.h:2876
Relids ph_needed
Definition: pathnodes.h:2879
Relids ph_eval_at
Definition: pathnodes.h:2873
PlaceHolderVar * ph_var
Definition: pathnodes.h:2870
Index phlevelsup
Definition: pathnodes.h:2630
Index lastPHId
Definition: pathnodes.h:138
List * placeholder_list
Definition: pathnodes.h:361
PlannerGlobal * glob
Definition: pathnodes.h:202
Query * parse
Definition: pathnodes.h:199
bool placeholdersFrozen
Definition: pathnodes.h:461
List * join_info_list
Definition: pathnodes.h:330
Cost per_tuple
Definition: pathnodes.h:48
Cost startup
Definition: pathnodes.h:47
FromExpr * jointree
Definition: parsenodes.h:156
Relids relids
Definition: pathnodes.h:821
struct PathTarget * reltarget
Definition: pathnodes.h:843
Relids direct_lateral_relids
Definition: pathnodes.h:861
Relids syn_lefthand
Definition: pathnodes.h:2702
Relids min_righthand
Definition: pathnodes.h:2701
JoinType jointype
Definition: pathnodes.h:2704
Relids min_lefthand
Definition: pathnodes.h:2700
Relids syn_righthand
Definition: pathnodes.h:2703
Definition: regcomp.c:282
List * pull_var_clause(Node *node, int flags)
Definition: var.c:597
Relids pull_varnos(PlannerInfo *root, Node *node)
Definition: var.c:100