PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
restrictinfo.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * restrictinfo.c
4  * RestrictInfo node manipulation routines.
5  *
6  * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
7  * Portions Copyright (c) 1994, Regents of the University of California
8  *
9  *
10  * IDENTIFICATION
11  * src/backend/optimizer/util/restrictinfo.c
12  *
13  *-------------------------------------------------------------------------
14  */
15 #include "postgres.h"
16 
17 #include "optimizer/clauses.h"
18 #include "optimizer/restrictinfo.h"
19 #include "optimizer/var.h"
20 
21 
23  Expr *orclause,
24  bool is_pushed_down,
25  bool outerjoin_delayed,
26  bool pseudoconstant,
27  Index security_level,
28  Relids required_relids,
29  Relids outer_relids,
30  Relids nullable_relids);
31 static Expr *make_sub_restrictinfos(Expr *clause,
32  bool is_pushed_down,
33  bool outerjoin_delayed,
34  bool pseudoconstant,
35  Index security_level,
36  Relids required_relids,
37  Relids outer_relids,
38  Relids nullable_relids);
39 
40 
41 /*
42  * make_restrictinfo
43  *
44  * Build a RestrictInfo node containing the given subexpression.
45  *
46  * The is_pushed_down, outerjoin_delayed, and pseudoconstant flags for the
47  * RestrictInfo must be supplied by the caller, as well as the correct values
48  * for security_level, outer_relids, and nullable_relids.
49  * required_relids can be NULL, in which case it defaults to the actual clause
50  * contents (i.e., clause_relids).
51  *
52  * We initialize fields that depend only on the given subexpression, leaving
53  * others that depend on context (or may never be needed at all) to be filled
54  * later.
55  */
58  bool is_pushed_down,
59  bool outerjoin_delayed,
60  bool pseudoconstant,
61  Index security_level,
62  Relids required_relids,
63  Relids outer_relids,
64  Relids nullable_relids)
65 {
66  /*
67  * If it's an OR clause, build a modified copy with RestrictInfos inserted
68  * above each subclause of the top-level AND/OR structure.
69  */
70  if (or_clause((Node *) clause))
71  return (RestrictInfo *) make_sub_restrictinfos(clause,
72  is_pushed_down,
73  outerjoin_delayed,
74  pseudoconstant,
75  security_level,
76  required_relids,
77  outer_relids,
78  nullable_relids);
79 
80  /* Shouldn't be an AND clause, else AND/OR flattening messed up */
81  Assert(!and_clause((Node *) clause));
82 
83  return make_restrictinfo_internal(clause,
84  NULL,
85  is_pushed_down,
86  outerjoin_delayed,
87  pseudoconstant,
88  security_level,
89  required_relids,
90  outer_relids,
91  nullable_relids);
92 }
93 
94 /*
95  * make_restrictinfo_internal
96  *
97  * Common code for the main entry points and the recursive cases.
98  */
99 static RestrictInfo *
101  Expr *orclause,
102  bool is_pushed_down,
103  bool outerjoin_delayed,
104  bool pseudoconstant,
105  Index security_level,
106  Relids required_relids,
107  Relids outer_relids,
108  Relids nullable_relids)
109 {
110  RestrictInfo *restrictinfo = makeNode(RestrictInfo);
111 
112  restrictinfo->clause = clause;
113  restrictinfo->orclause = orclause;
114  restrictinfo->is_pushed_down = is_pushed_down;
115  restrictinfo->outerjoin_delayed = outerjoin_delayed;
116  restrictinfo->pseudoconstant = pseudoconstant;
117  restrictinfo->can_join = false; /* may get set below */
118  restrictinfo->security_level = security_level;
119  restrictinfo->outer_relids = outer_relids;
120  restrictinfo->nullable_relids = nullable_relids;
121 
122  /*
123  * If it's potentially delayable by lower-level security quals, figure out
124  * whether it's leakproof. We can skip testing this for level-zero quals,
125  * since they would never get delayed on security grounds anyway.
126  */
127  if (security_level > 0)
128  restrictinfo->leakproof = !contain_leaked_vars((Node *) clause);
129  else
130  restrictinfo->leakproof = false; /* really, "don't know" */
131 
132  /*
133  * If it's a binary opclause, set up left/right relids info. In any case
134  * set up the total clause relids info.
135  */
136  if (is_opclause(clause) && list_length(((OpExpr *) clause)->args) == 2)
137  {
138  restrictinfo->left_relids = pull_varnos(get_leftop(clause));
139  restrictinfo->right_relids = pull_varnos(get_rightop(clause));
140 
141  restrictinfo->clause_relids = bms_union(restrictinfo->left_relids,
142  restrictinfo->right_relids);
143 
144  /*
145  * Does it look like a normal join clause, i.e., a binary operator
146  * relating expressions that come from distinct relations? If so we
147  * might be able to use it in a join algorithm. Note that this is a
148  * purely syntactic test that is made regardless of context.
149  */
150  if (!bms_is_empty(restrictinfo->left_relids) &&
151  !bms_is_empty(restrictinfo->right_relids) &&
152  !bms_overlap(restrictinfo->left_relids,
153  restrictinfo->right_relids))
154  {
155  restrictinfo->can_join = true;
156  /* pseudoconstant should certainly not be true */
157  Assert(!restrictinfo->pseudoconstant);
158  }
159  }
160  else
161  {
162  /* Not a binary opclause, so mark left/right relid sets as empty */
163  restrictinfo->left_relids = NULL;
164  restrictinfo->right_relids = NULL;
165  /* and get the total relid set the hard way */
166  restrictinfo->clause_relids = pull_varnos((Node *) clause);
167  }
168 
169  /* required_relids defaults to clause_relids */
170  if (required_relids != NULL)
171  restrictinfo->required_relids = required_relids;
172  else
173  restrictinfo->required_relids = restrictinfo->clause_relids;
174 
175  /*
176  * Fill in all the cacheable fields with "not yet set" markers. None of
177  * these will be computed until/unless needed. Note in particular that we
178  * don't mark a binary opclause as mergejoinable or hashjoinable here;
179  * that happens only if it appears in the right context (top level of a
180  * joinclause list).
181  */
182  restrictinfo->parent_ec = NULL;
183 
184  restrictinfo->eval_cost.startup = -1;
185  restrictinfo->norm_selec = -1;
186  restrictinfo->outer_selec = -1;
187 
188  restrictinfo->mergeopfamilies = NIL;
189 
190  restrictinfo->left_ec = NULL;
191  restrictinfo->right_ec = NULL;
192  restrictinfo->left_em = NULL;
193  restrictinfo->right_em = NULL;
194  restrictinfo->scansel_cache = NIL;
195 
196  restrictinfo->outer_is_left = false;
197 
198  restrictinfo->hashjoinoperator = InvalidOid;
199 
200  restrictinfo->left_bucketsize = -1;
201  restrictinfo->right_bucketsize = -1;
202 
203  return restrictinfo;
204 }
205 
206 /*
207  * Recursively insert sub-RestrictInfo nodes into a boolean expression.
208  *
209  * We put RestrictInfos above simple (non-AND/OR) clauses and above
210  * sub-OR clauses, but not above sub-AND clauses, because there's no need.
211  * This may seem odd but it is closely related to the fact that we use
212  * implicit-AND lists at top level of RestrictInfo lists. Only ORs and
213  * simple clauses are valid RestrictInfos.
214  *
215  * The same is_pushed_down, outerjoin_delayed, and pseudoconstant flag
216  * values can be applied to all RestrictInfo nodes in the result. Likewise
217  * for security_level, outer_relids, and nullable_relids.
218  *
219  * The given required_relids are attached to our top-level output,
220  * but any OR-clause constituents are allowed to default to just the
221  * contained rels.
222  */
223 static Expr *
225  bool is_pushed_down,
226  bool outerjoin_delayed,
227  bool pseudoconstant,
228  Index security_level,
229  Relids required_relids,
230  Relids outer_relids,
231  Relids nullable_relids)
232 {
233  if (or_clause((Node *) clause))
234  {
235  List *orlist = NIL;
236  ListCell *temp;
237 
238  foreach(temp, ((BoolExpr *) clause)->args)
239  orlist = lappend(orlist,
241  is_pushed_down,
242  outerjoin_delayed,
243  pseudoconstant,
244  security_level,
245  NULL,
246  outer_relids,
247  nullable_relids));
248  return (Expr *) make_restrictinfo_internal(clause,
249  make_orclause(orlist),
250  is_pushed_down,
251  outerjoin_delayed,
252  pseudoconstant,
253  security_level,
254  required_relids,
255  outer_relids,
256  nullable_relids);
257  }
258  else if (and_clause((Node *) clause))
259  {
260  List *andlist = NIL;
261  ListCell *temp;
262 
263  foreach(temp, ((BoolExpr *) clause)->args)
264  andlist = lappend(andlist,
266  is_pushed_down,
267  outerjoin_delayed,
268  pseudoconstant,
269  security_level,
270  required_relids,
271  outer_relids,
272  nullable_relids));
273  return make_andclause(andlist);
274  }
275  else
276  return (Expr *) make_restrictinfo_internal(clause,
277  NULL,
278  is_pushed_down,
279  outerjoin_delayed,
280  pseudoconstant,
281  security_level,
282  required_relids,
283  outer_relids,
284  nullable_relids);
285 }
286 
287 /*
288  * restriction_is_or_clause
289  *
290  * Returns t iff the restrictinfo node contains an 'or' clause.
291  */
292 bool
294 {
295  if (restrictinfo->orclause != NULL)
296  return true;
297  else
298  return false;
299 }
300 
301 /*
302  * restriction_is_securely_promotable
303  *
304  * Returns true if it's okay to evaluate this clause "early", that is before
305  * other restriction clauses attached to the specified relation.
306  */
307 bool
309  RelOptInfo *rel)
310 {
311  /*
312  * It's okay if there are no baserestrictinfo clauses for the rel that
313  * would need to go before this one, *or* if this one is leakproof.
314  */
315  if (restrictinfo->security_level <= rel->baserestrict_min_security ||
316  restrictinfo->leakproof)
317  return true;
318  else
319  return false;
320 }
321 
322 /*
323  * get_actual_clauses
324  *
325  * Returns a list containing the bare clauses from 'restrictinfo_list'.
326  *
327  * This is only to be used in cases where none of the RestrictInfos can
328  * be pseudoconstant clauses (for instance, it's OK on indexqual lists).
329  */
330 List *
331 get_actual_clauses(List *restrictinfo_list)
332 {
333  List *result = NIL;
334  ListCell *l;
335 
336  foreach(l, restrictinfo_list)
337  {
339 
340  Assert(!rinfo->pseudoconstant);
341 
342  result = lappend(result, rinfo->clause);
343  }
344  return result;
345 }
346 
347 /*
348  * extract_actual_clauses
349  *
350  * Extract bare clauses from 'restrictinfo_list', returning either the
351  * regular ones or the pseudoconstant ones per 'pseudoconstant'.
352  */
353 List *
354 extract_actual_clauses(List *restrictinfo_list,
355  bool pseudoconstant)
356 {
357  List *result = NIL;
358  ListCell *l;
359 
360  foreach(l, restrictinfo_list)
361  {
363 
364  if (rinfo->pseudoconstant == pseudoconstant)
365  result = lappend(result, rinfo->clause);
366  }
367  return result;
368 }
369 
370 /*
371  * extract_actual_join_clauses
372  *
373  * Extract bare clauses from 'restrictinfo_list', separating those that
374  * syntactically match the join level from those that were pushed down.
375  * Pseudoconstant clauses are excluded from the results.
376  *
377  * This is only used at outer joins, since for plain joins we don't care
378  * about pushed-down-ness.
379  */
380 void
382  List **joinquals,
383  List **otherquals)
384 {
385  ListCell *l;
386 
387  *joinquals = NIL;
388  *otherquals = NIL;
389 
390  foreach(l, restrictinfo_list)
391  {
393 
394  if (rinfo->is_pushed_down)
395  {
396  if (!rinfo->pseudoconstant)
397  *otherquals = lappend(*otherquals, rinfo->clause);
398  }
399  else
400  {
401  /* joinquals shouldn't have been marked pseudoconstant */
402  Assert(!rinfo->pseudoconstant);
403  *joinquals = lappend(*joinquals, rinfo->clause);
404  }
405  }
406 }
407 
408 
409 /*
410  * join_clause_is_movable_to
411  * Test whether a join clause is a safe candidate for parameterization
412  * of a scan on the specified base relation.
413  *
414  * A movable join clause is one that can safely be evaluated at a rel below
415  * its normal semantic level (ie, its required_relids), if the values of
416  * variables that it would need from other rels are provided.
417  *
418  * We insist that the clause actually reference the target relation; this
419  * prevents undesirable movement of degenerate join clauses, and ensures
420  * that there is a unique place that a clause can be moved down to.
421  *
422  * We cannot move an outer-join clause into the non-nullable side of its
423  * outer join, as that would change the results (rows would be suppressed
424  * rather than being null-extended).
425  *
426  * Also there must not be an outer join below the clause that would null the
427  * Vars coming from the target relation. Otherwise the clause might give
428  * results different from what it would give at its normal semantic level.
429  *
430  * Also, the join clause must not use any relations that have LATERAL
431  * references to the target relation, since we could not put such rels on
432  * the outer side of a nestloop with the target relation.
433  */
434 bool
436 {
437  /* Clause must physically reference target rel */
438  if (!bms_is_member(baserel->relid, rinfo->clause_relids))
439  return false;
440 
441  /* Cannot move an outer-join clause into the join's outer side */
442  if (bms_is_member(baserel->relid, rinfo->outer_relids))
443  return false;
444 
445  /* Target rel must not be nullable below the clause */
446  if (bms_is_member(baserel->relid, rinfo->nullable_relids))
447  return false;
448 
449  /* Clause must not use any rels with LATERAL references to this rel */
450  if (bms_overlap(baserel->lateral_referencers, rinfo->clause_relids))
451  return false;
452 
453  return true;
454 }
455 
456 /*
457  * join_clause_is_movable_into
458  * Test whether a join clause is movable and can be evaluated within
459  * the current join context.
460  *
461  * currentrelids: the relids of the proposed evaluation location
462  * current_and_outer: the union of currentrelids and the required_outer
463  * relids (parameterization's outer relations)
464  *
465  * The API would be a bit clearer if we passed the current relids and the
466  * outer relids separately and did bms_union internally; but since most
467  * callers need to apply this function to multiple clauses, we make the
468  * caller perform the union.
469  *
470  * Obviously, the clause must only refer to Vars available from the current
471  * relation plus the outer rels. We also check that it does reference at
472  * least one current Var, ensuring that the clause will be pushed down to
473  * a unique place in a parameterized join tree. And we check that we're
474  * not pushing the clause into its outer-join outer side, nor down into
475  * a lower outer join's inner side.
476  *
477  * The check about pushing a clause down into a lower outer join's inner side
478  * is only approximate; it sometimes returns "false" when actually it would
479  * be safe to use the clause here because we're still above the outer join
480  * in question. This is okay as long as the answers at different join levels
481  * are consistent: it just means we might sometimes fail to push a clause as
482  * far down as it could safely be pushed. It's unclear whether it would be
483  * worthwhile to do this more precisely. (But if it's ever fixed to be
484  * exactly accurate, there's an Assert in get_joinrel_parampathinfo() that
485  * should be re-enabled.)
486  *
487  * There's no check here equivalent to join_clause_is_movable_to's test on
488  * lateral_referencers. We assume the caller wouldn't be inquiring unless
489  * it'd verified that the proposed outer rels don't have lateral references
490  * to the current rel(s). (If we are considering join paths with the outer
491  * rels on the outside and the current rels on the inside, then this should
492  * have been checked at the outset of such consideration; see join_is_legal
493  * and the path parameterization checks in joinpath.c.) On the other hand,
494  * in join_clause_is_movable_to we are asking whether the clause could be
495  * moved for some valid set of outer rels, so we don't have the benefit of
496  * relying on prior checks for lateral-reference validity.
497  *
498  * Note: if this returns true, it means that the clause could be moved to
499  * this join relation, but that doesn't mean that this is the lowest join
500  * it could be moved to. Caller may need to make additional calls to verify
501  * that this doesn't succeed on either of the inputs of a proposed join.
502  *
503  * Note: get_joinrel_parampathinfo depends on the fact that if
504  * current_and_outer is NULL, this function will always return false
505  * (since one or the other of the first two tests must fail).
506  */
507 bool
509  Relids currentrelids,
510  Relids current_and_outer)
511 {
512  /* Clause must be evaluable given available context */
513  if (!bms_is_subset(rinfo->clause_relids, current_and_outer))
514  return false;
515 
516  /* Clause must physically reference at least one target rel */
517  if (!bms_overlap(currentrelids, rinfo->clause_relids))
518  return false;
519 
520  /* Cannot move an outer-join clause into the join's outer side */
521  if (bms_overlap(currentrelids, rinfo->outer_relids))
522  return false;
523 
524  /*
525  * Target rel(s) must not be nullable below the clause. This is
526  * approximate, in the safe direction, because the current join might be
527  * above the join where the nulling would happen, in which case the clause
528  * would work correctly here. But we don't have enough info to be sure.
529  */
530  if (bms_overlap(currentrelids, rinfo->nullable_relids))
531  return false;
532 
533  return true;
534 }
QualCost eval_cost
Definition: relation.h:1674
#define NIL
Definition: pg_list.h:69
bool contain_leaked_vars(Node *clause)
Definition: clauses.c:1427
Index security_level
Definition: relation.h:1649
RestrictInfo * make_restrictinfo(Expr *clause, bool is_pushed_down, bool outerjoin_delayed, bool pseudoconstant, Index security_level, Relids required_relids, Relids outer_relids, Relids nullable_relids)
Definition: restrictinfo.c:57
Relids required_relids
Definition: relation.h:1655
void extract_actual_join_clauses(List *restrictinfo_list, List **joinquals, List **otherquals)
Definition: restrictinfo.c:381
bool leakproof
Definition: relation.h:1647
#define castNode(_type_, nodeptr)
Definition: nodes.h:577
Expr * orclause
Definition: relation.h:1668
static RestrictInfo * make_restrictinfo_internal(Expr *clause, Expr *orclause, bool is_pushed_down, bool outerjoin_delayed, bool pseudoconstant, Index security_level, Relids required_relids, Relids outer_relids, Relids nullable_relids)
Definition: restrictinfo.c:100
Relids clause_relids
Definition: relation.h:1652
bool pseudoconstant
Definition: relation.h:1645
Definition: nodes.h:508
List * get_actual_clauses(List *restrictinfo_list)
Definition: restrictinfo.c:331
Relids left_relids
Definition: relation.h:1664
EquivalenceClass * right_ec
Definition: relation.h:1686
Index baserestrict_min_security
Definition: relation.h:547
List * mergeopfamilies
Definition: relation.h:1682
bool restriction_is_or_clause(RestrictInfo *restrictinfo)
Definition: restrictinfo.c:293
Cost startup
Definition: relation.h:45
Relids outer_relids
Definition: relation.h:1658
Selectivity norm_selec
Definition: relation.h:1675
#define is_opclause(clause)
Definition: clauses.h:20
EquivalenceMember * left_em
Definition: relation.h:1687
Node * get_leftop(const Expr *clause)
Definition: clauses.c:198
EquivalenceClass * parent_ec
Definition: relation.h:1671
bool can_join
Definition: relation.h:1643
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:307
bool outerjoin_delayed
Definition: relation.h:1641
bool and_clause(Node *clause)
Definition: clauses.c:313
bool outer_is_left
Definition: relation.h:1692
Selectivity outer_selec
Definition: relation.h:1678
bool join_clause_is_movable_into(RestrictInfo *rinfo, Relids currentrelids, Relids current_and_outer)
Definition: restrictinfo.c:508
Relids pull_varnos(Node *node)
Definition: var.c:95
Index relid
Definition: relation.h:518
List * lappend(List *list, void *datum)
Definition: list.c:128
Relids lateral_referencers
Definition: relation.h:526
EquivalenceMember * right_em
Definition: relation.h:1688
Expr * clause
Definition: relation.h:1637
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:633
Relids nullable_relids
Definition: relation.h:1661
bool or_clause(Node *clause)
Definition: clauses.c:279
unsigned int Index
Definition: c.h:361
static Expr * make_sub_restrictinfos(Expr *clause, bool is_pushed_down, bool outerjoin_delayed, bool pseudoconstant, Index security_level, Relids required_relids, Relids outer_relids, Relids nullable_relids)
Definition: restrictinfo.c:224
#define InvalidOid
Definition: postgres_ext.h:36
bool is_pushed_down
Definition: relation.h:1639
Selectivity left_bucketsize
Definition: relation.h:1698
#define makeNode(_type_)
Definition: nodes.h:556
Relids right_relids
Definition: relation.h:1665
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:670
#define lfirst(lc)
Definition: pg_list.h:106
bool restriction_is_securely_promotable(RestrictInfo *restrictinfo, RelOptInfo *rel)
Definition: restrictinfo.c:308
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:217
Oid hashjoinoperator
Definition: relation.h:1695
static int list_length(const List *l)
Definition: pg_list.h:89
List * extract_actual_clauses(List *restrictinfo_list, bool pseudoconstant)
Definition: restrictinfo.c:354
Node * get_rightop(const Expr *clause)
Definition: clauses.c:215
bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
Definition: restrictinfo.c:435
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:442
Selectivity right_bucketsize
Definition: relation.h:1699
EquivalenceClass * left_ec
Definition: relation.h:1685
Expr * make_andclause(List *andclauses)
Definition: clauses.c:326
Definition: pg_list.h:45
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:419
Expr * make_orclause(List *orclauses)
Definition: clauses.c:292
List * scansel_cache
Definition: relation.h:1689