Line data Source code
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 :
22 : static RestrictInfo *make_restrictinfo_internal(Expr *clause,
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 : */
56 : RestrictInfo *
57 24109 : make_restrictinfo(Expr *clause,
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 24109 : if (or_clause((Node *) clause))
71 334 : 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 23775 : Assert(!and_clause((Node *) clause));
82 :
83 23775 : 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 *
100 25107 : make_restrictinfo_internal(Expr *clause,
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 25107 : RestrictInfo *restrictinfo = makeNode(RestrictInfo);
111 :
112 25107 : restrictinfo->clause = clause;
113 25107 : restrictinfo->orclause = orclause;
114 25107 : restrictinfo->is_pushed_down = is_pushed_down;
115 25107 : restrictinfo->outerjoin_delayed = outerjoin_delayed;
116 25107 : restrictinfo->pseudoconstant = pseudoconstant;
117 25107 : restrictinfo->can_join = false; /* may get set below */
118 25107 : restrictinfo->security_level = security_level;
119 25107 : restrictinfo->outer_relids = outer_relids;
120 25107 : 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 25107 : if (security_level > 0)
128 594 : restrictinfo->leakproof = !contain_leaked_vars((Node *) clause);
129 : else
130 24513 : 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 25107 : if (is_opclause(clause) && list_length(((OpExpr *) clause)->args) == 2)
137 : {
138 21086 : restrictinfo->left_relids = pull_varnos(get_leftop(clause));
139 21086 : restrictinfo->right_relids = pull_varnos(get_rightop(clause));
140 :
141 21086 : restrictinfo->clause_relids = bms_union(restrictinfo->left_relids,
142 21086 : 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 62591 : if (!bms_is_empty(restrictinfo->left_relids) &&
151 28135 : !bms_is_empty(restrictinfo->right_relids) &&
152 7716 : !bms_overlap(restrictinfo->left_relids,
153 7716 : restrictinfo->right_relids))
154 : {
155 7587 : restrictinfo->can_join = true;
156 : /* pseudoconstant should certainly not be true */
157 7587 : Assert(!restrictinfo->pseudoconstant);
158 : }
159 : }
160 : else
161 : {
162 : /* Not a binary opclause, so mark left/right relid sets as empty */
163 4021 : restrictinfo->left_relids = NULL;
164 4021 : restrictinfo->right_relids = NULL;
165 : /* and get the total relid set the hard way */
166 4021 : restrictinfo->clause_relids = pull_varnos((Node *) clause);
167 : }
168 :
169 : /* required_relids defaults to clause_relids */
170 25107 : if (required_relids != NULL)
171 22490 : restrictinfo->required_relids = required_relids;
172 : else
173 2617 : 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 25107 : restrictinfo->parent_ec = NULL;
183 :
184 25107 : restrictinfo->eval_cost.startup = -1;
185 25107 : restrictinfo->norm_selec = -1;
186 25107 : restrictinfo->outer_selec = -1;
187 :
188 25107 : restrictinfo->mergeopfamilies = NIL;
189 :
190 25107 : restrictinfo->left_ec = NULL;
191 25107 : restrictinfo->right_ec = NULL;
192 25107 : restrictinfo->left_em = NULL;
193 25107 : restrictinfo->right_em = NULL;
194 25107 : restrictinfo->scansel_cache = NIL;
195 :
196 25107 : restrictinfo->outer_is_left = false;
197 :
198 25107 : restrictinfo->hashjoinoperator = InvalidOid;
199 :
200 25107 : restrictinfo->left_bucketsize = -1;
201 25107 : restrictinfo->right_bucketsize = -1;
202 25107 : restrictinfo->left_mcvfreq = -1;
203 25107 : restrictinfo->right_mcvfreq = -1;
204 :
205 25107 : return restrictinfo;
206 : }
207 :
208 : /*
209 : * Recursively insert sub-RestrictInfo nodes into a boolean expression.
210 : *
211 : * We put RestrictInfos above simple (non-AND/OR) clauses and above
212 : * sub-OR clauses, but not above sub-AND clauses, because there's no need.
213 : * This may seem odd but it is closely related to the fact that we use
214 : * implicit-AND lists at top level of RestrictInfo lists. Only ORs and
215 : * simple clauses are valid RestrictInfos.
216 : *
217 : * The same is_pushed_down, outerjoin_delayed, and pseudoconstant flag
218 : * values can be applied to all RestrictInfo nodes in the result. Likewise
219 : * for security_level, outer_relids, and nullable_relids.
220 : *
221 : * The given required_relids are attached to our top-level output,
222 : * but any OR-clause constituents are allowed to default to just the
223 : * contained rels.
224 : */
225 : static Expr *
226 1400 : make_sub_restrictinfos(Expr *clause,
227 : bool is_pushed_down,
228 : bool outerjoin_delayed,
229 : bool pseudoconstant,
230 : Index security_level,
231 : Relids required_relids,
232 : Relids outer_relids,
233 : Relids nullable_relids)
234 : {
235 1400 : if (or_clause((Node *) clause))
236 : {
237 343 : List *orlist = NIL;
238 : ListCell *temp;
239 :
240 1271 : foreach(temp, ((BoolExpr *) clause)->args)
241 928 : orlist = lappend(orlist,
242 928 : make_sub_restrictinfos(lfirst(temp),
243 : is_pushed_down,
244 : outerjoin_delayed,
245 : pseudoconstant,
246 : security_level,
247 : NULL,
248 : outer_relids,
249 : nullable_relids));
250 343 : return (Expr *) make_restrictinfo_internal(clause,
251 : make_orclause(orlist),
252 : is_pushed_down,
253 : outerjoin_delayed,
254 : pseudoconstant,
255 : security_level,
256 : required_relids,
257 : outer_relids,
258 : nullable_relids);
259 : }
260 1057 : else if (and_clause((Node *) clause))
261 : {
262 68 : List *andlist = NIL;
263 : ListCell *temp;
264 :
265 206 : foreach(temp, ((BoolExpr *) clause)->args)
266 138 : andlist = lappend(andlist,
267 138 : make_sub_restrictinfos(lfirst(temp),
268 : is_pushed_down,
269 : outerjoin_delayed,
270 : pseudoconstant,
271 : security_level,
272 : required_relids,
273 : outer_relids,
274 : nullable_relids));
275 68 : return make_andclause(andlist);
276 : }
277 : else
278 989 : return (Expr *) make_restrictinfo_internal(clause,
279 : NULL,
280 : is_pushed_down,
281 : outerjoin_delayed,
282 : pseudoconstant,
283 : security_level,
284 : required_relids,
285 : outer_relids,
286 : nullable_relids);
287 : }
288 :
289 : /*
290 : * restriction_is_or_clause
291 : *
292 : * Returns t iff the restrictinfo node contains an 'or' clause.
293 : */
294 : bool
295 19125 : restriction_is_or_clause(RestrictInfo *restrictinfo)
296 : {
297 19125 : if (restrictinfo->orclause != NULL)
298 1141 : return true;
299 : else
300 17984 : return false;
301 : }
302 :
303 : /*
304 : * restriction_is_securely_promotable
305 : *
306 : * Returns true if it's okay to evaluate this clause "early", that is before
307 : * other restriction clauses attached to the specified relation.
308 : */
309 : bool
310 43983 : restriction_is_securely_promotable(RestrictInfo *restrictinfo,
311 : RelOptInfo *rel)
312 : {
313 : /*
314 : * It's okay if there are no baserestrictinfo clauses for the rel that
315 : * would need to go before this one, *or* if this one is leakproof.
316 : */
317 44530 : if (restrictinfo->security_level <= rel->baserestrict_min_security ||
318 547 : restrictinfo->leakproof)
319 43710 : return true;
320 : else
321 273 : return false;
322 : }
323 :
324 : /*
325 : * get_actual_clauses
326 : *
327 : * Returns a list containing the bare clauses from 'restrictinfo_list'.
328 : *
329 : * This is only to be used in cases where none of the RestrictInfos can
330 : * be pseudoconstant clauses (for instance, it's OK on indexqual lists).
331 : */
332 : List *
333 14868 : get_actual_clauses(List *restrictinfo_list)
334 : {
335 14868 : List *result = NIL;
336 : ListCell *l;
337 :
338 31686 : foreach(l, restrictinfo_list)
339 : {
340 16818 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
341 :
342 16818 : Assert(!rinfo->pseudoconstant);
343 :
344 16818 : result = lappend(result, rinfo->clause);
345 : }
346 14868 : return result;
347 : }
348 :
349 : /*
350 : * extract_actual_clauses
351 : *
352 : * Extract bare clauses from 'restrictinfo_list', returning either the
353 : * regular ones or the pseudoconstant ones per 'pseudoconstant'.
354 : */
355 : List *
356 23376 : extract_actual_clauses(List *restrictinfo_list,
357 : bool pseudoconstant)
358 : {
359 23376 : List *result = NIL;
360 : ListCell *l;
361 :
362 34386 : foreach(l, restrictinfo_list)
363 : {
364 11010 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
365 :
366 11010 : if (rinfo->pseudoconstant == pseudoconstant)
367 9914 : result = lappend(result, rinfo->clause);
368 : }
369 23376 : return result;
370 : }
371 :
372 : /*
373 : * extract_actual_join_clauses
374 : *
375 : * Extract bare clauses from 'restrictinfo_list', separating those that
376 : * syntactically match the join level from those that were pushed down.
377 : * Pseudoconstant clauses are excluded from the results.
378 : *
379 : * This is only used at outer joins, since for plain joins we don't care
380 : * about pushed-down-ness.
381 : */
382 : void
383 1034 : extract_actual_join_clauses(List *restrictinfo_list,
384 : List **joinquals,
385 : List **otherquals)
386 : {
387 : ListCell *l;
388 :
389 1034 : *joinquals = NIL;
390 1034 : *otherquals = NIL;
391 :
392 1908 : foreach(l, restrictinfo_list)
393 : {
394 874 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
395 :
396 874 : if (rinfo->is_pushed_down)
397 : {
398 35 : if (!rinfo->pseudoconstant)
399 35 : *otherquals = lappend(*otherquals, rinfo->clause);
400 : }
401 : else
402 : {
403 : /* joinquals shouldn't have been marked pseudoconstant */
404 839 : Assert(!rinfo->pseudoconstant);
405 839 : *joinquals = lappend(*joinquals, rinfo->clause);
406 : }
407 : }
408 1034 : }
409 :
410 :
411 : /*
412 : * join_clause_is_movable_to
413 : * Test whether a join clause is a safe candidate for parameterization
414 : * of a scan on the specified base relation.
415 : *
416 : * A movable join clause is one that can safely be evaluated at a rel below
417 : * its normal semantic level (ie, its required_relids), if the values of
418 : * variables that it would need from other rels are provided.
419 : *
420 : * We insist that the clause actually reference the target relation; this
421 : * prevents undesirable movement of degenerate join clauses, and ensures
422 : * that there is a unique place that a clause can be moved down to.
423 : *
424 : * We cannot move an outer-join clause into the non-nullable side of its
425 : * outer join, as that would change the results (rows would be suppressed
426 : * rather than being null-extended).
427 : *
428 : * Also there must not be an outer join below the clause that would null the
429 : * Vars coming from the target relation. Otherwise the clause might give
430 : * results different from what it would give at its normal semantic level.
431 : *
432 : * Also, the join clause must not use any relations that have LATERAL
433 : * references to the target relation, since we could not put such rels on
434 : * the outer side of a nestloop with the target relation.
435 : */
436 : bool
437 5916 : join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
438 : {
439 : /* Clause must physically reference target rel */
440 5916 : if (!bms_is_member(baserel->relid, rinfo->clause_relids))
441 527 : return false;
442 :
443 : /* Cannot move an outer-join clause into the join's outer side */
444 5389 : if (bms_is_member(baserel->relid, rinfo->outer_relids))
445 2308 : return false;
446 :
447 : /* Target rel must not be nullable below the clause */
448 3081 : if (bms_is_member(baserel->relid, rinfo->nullable_relids))
449 88 : return false;
450 :
451 : /* Clause must not use any rels with LATERAL references to this rel */
452 2993 : if (bms_overlap(baserel->lateral_referencers, rinfo->clause_relids))
453 3 : return false;
454 :
455 2990 : return true;
456 : }
457 :
458 : /*
459 : * join_clause_is_movable_into
460 : * Test whether a join clause is movable and can be evaluated within
461 : * the current join context.
462 : *
463 : * currentrelids: the relids of the proposed evaluation location
464 : * current_and_outer: the union of currentrelids and the required_outer
465 : * relids (parameterization's outer relations)
466 : *
467 : * The API would be a bit clearer if we passed the current relids and the
468 : * outer relids separately and did bms_union internally; but since most
469 : * callers need to apply this function to multiple clauses, we make the
470 : * caller perform the union.
471 : *
472 : * Obviously, the clause must only refer to Vars available from the current
473 : * relation plus the outer rels. We also check that it does reference at
474 : * least one current Var, ensuring that the clause will be pushed down to
475 : * a unique place in a parameterized join tree. And we check that we're
476 : * not pushing the clause into its outer-join outer side, nor down into
477 : * a lower outer join's inner side.
478 : *
479 : * The check about pushing a clause down into a lower outer join's inner side
480 : * is only approximate; it sometimes returns "false" when actually it would
481 : * be safe to use the clause here because we're still above the outer join
482 : * in question. This is okay as long as the answers at different join levels
483 : * are consistent: it just means we might sometimes fail to push a clause as
484 : * far down as it could safely be pushed. It's unclear whether it would be
485 : * worthwhile to do this more precisely. (But if it's ever fixed to be
486 : * exactly accurate, there's an Assert in get_joinrel_parampathinfo() that
487 : * should be re-enabled.)
488 : *
489 : * There's no check here equivalent to join_clause_is_movable_to's test on
490 : * lateral_referencers. We assume the caller wouldn't be inquiring unless
491 : * it'd verified that the proposed outer rels don't have lateral references
492 : * to the current rel(s). (If we are considering join paths with the outer
493 : * rels on the outside and the current rels on the inside, then this should
494 : * have been checked at the outset of such consideration; see join_is_legal
495 : * and the path parameterization checks in joinpath.c.) On the other hand,
496 : * in join_clause_is_movable_to we are asking whether the clause could be
497 : * moved for some valid set of outer rels, so we don't have the benefit of
498 : * relying on prior checks for lateral-reference validity.
499 : *
500 : * Note: if this returns true, it means that the clause could be moved to
501 : * this join relation, but that doesn't mean that this is the lowest join
502 : * it could be moved to. Caller may need to make additional calls to verify
503 : * that this doesn't succeed on either of the inputs of a proposed join.
504 : *
505 : * Note: get_joinrel_parampathinfo depends on the fact that if
506 : * current_and_outer is NULL, this function will always return false
507 : * (since one or the other of the first two tests must fail).
508 : */
509 : bool
510 13034 : join_clause_is_movable_into(RestrictInfo *rinfo,
511 : Relids currentrelids,
512 : Relids current_and_outer)
513 : {
514 : /* Clause must be evaluable given available context */
515 13034 : if (!bms_is_subset(rinfo->clause_relids, current_and_outer))
516 1357 : return false;
517 :
518 : /* Clause must physically reference at least one target rel */
519 11677 : if (!bms_overlap(currentrelids, rinfo->clause_relids))
520 499 : return false;
521 :
522 : /* Cannot move an outer-join clause into the join's outer side */
523 11178 : if (bms_overlap(currentrelids, rinfo->outer_relids))
524 90 : return false;
525 :
526 : /*
527 : * Target rel(s) must not be nullable below the clause. This is
528 : * approximate, in the safe direction, because the current join might be
529 : * above the join where the nulling would happen, in which case the clause
530 : * would work correctly here. But we don't have enough info to be sure.
531 : */
532 11088 : if (bms_overlap(currentrelids, rinfo->nullable_relids))
533 43 : return false;
534 :
535 11045 : return true;
536 : }
|
