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