?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Disallow empty passwords in LDAP authentication, the same way
[PostgreSQL.git] / src / backend / optimizer / util / restrictinfo.c
blob15faad9b94cb609752b6c988db1d90cd08abfcda
1 /*-------------------------------------------------------------------------
2 *
3 * restrictinfo.c
4 * RestrictInfo node manipulation routines.
5 *
6 * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
8 *
9 *
10 * IDENTIFICATION
11 * $PostgreSQL$
12 *
13 *-------------------------------------------------------------------------
14 */
15 #include "postgres.h"
16
17 #include "optimizer/clauses.h"
18 #include "optimizer/cost.h"
19 #include "optimizer/paths.h"
20 #include "optimizer/predtest.h"
21 #include "optimizer/restrictinfo.h"
22 #include "optimizer/var.h"
23
24
25 static RestrictInfo *make_restrictinfo_internal(Expr *clause,
26 Expr *orclause,
27 bool is_pushed_down,
28 bool outerjoin_delayed,
29 bool pseudoconstant,
30 Relids required_relids,
31 Relids nullable_relids);
32 static Expr *make_sub_restrictinfos(Expr *clause,
33 bool is_pushed_down,
34 bool outerjoin_delayed,
35 bool pseudoconstant,
36 Relids required_relids,
37 Relids nullable_relids);
38 static List *select_nonredundant_join_list(List *restrictinfo_list,
39 List *reference_list);
40 static bool join_clause_is_redundant(RestrictInfo *rinfo,
41 List *reference_list);
42
43
44 /*
45 * make_restrictinfo
46 *
47 * Build a RestrictInfo node containing the given subexpression.
48 *
49 * The is_pushed_down, outerjoin_delayed, and pseudoconstant flags for the
50 * RestrictInfo must be supplied by the caller, as well as the correct value
51 * for nullable_relids. required_relids can be NULL, in which case it
52 * defaults to the actual clause contents (i.e., clause_relids).
53 *
54 * We initialize fields that depend only on the given subexpression, leaving
55 * others that depend on context (or may never be needed at all) to be filled
56 * later.
57 */
58 RestrictInfo *
59 make_restrictinfo(Expr *clause,
60 bool is_pushed_down,
61 bool outerjoin_delayed,
62 bool pseudoconstant,
63 Relids required_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 required_relids,
76 nullable_relids);
77
78 /* Shouldn't be an AND clause, else AND/OR flattening messed up */
79 Assert(!and_clause((Node *) clause));
80
81 return make_restrictinfo_internal(clause,
82 NULL,
83 is_pushed_down,
84 outerjoin_delayed,
85 pseudoconstant,
86 required_relids,
87 nullable_relids);
88 }
89
90 /*
91 * make_restrictinfo_from_bitmapqual
92 *
93 * Given the bitmapqual Path structure for a bitmap indexscan, generate
94 * RestrictInfo node(s) equivalent to the condition represented by the
95 * indexclauses of the Path structure.
96 *
97 * The result is a List (effectively, implicit-AND representation) of
98 * RestrictInfos.
99 *
100 * The caller must pass is_pushed_down, but we assume outerjoin_delayed
101 * and pseudoconstant are false and nullable_relids is NULL (no other
102 * kind of qual should ever get into a bitmapqual).
103 *
104 * If include_predicates is true, we add any partial index predicates to
105 * the explicit index quals. When this is not true, we return a condition
106 * that might be weaker than the actual scan represents.
107 *
108 * To do this through the normal make_restrictinfo() API, callers would have
109 * to strip off the RestrictInfo nodes present in the indexclauses lists, and
110 * then make_restrictinfo() would have to build new ones. It's better to have
111 * a specialized routine to allow sharing of RestrictInfos.
112 *
113 * The qual manipulations here are much the same as in create_bitmap_subplan;
114 * keep the two routines in sync!
115 */
116 List *
117 make_restrictinfo_from_bitmapqual(Path *bitmapqual,
118 bool is_pushed_down,
119 bool include_predicates)
120 {
121 List *result;
122 ListCell *l;
123
124 if (IsA(bitmapqual, BitmapAndPath))
125 {
126 BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
127
128 /*
129 * There may well be redundant quals among the subplans, since a
130 * top-level WHERE qual might have gotten used to form several
131 * different index quals. We don't try exceedingly hard to eliminate
132 * redundancies, but we do eliminate obvious duplicates by using
133 * list_concat_unique.
134 */
135 result = NIL;
136 foreach(l, apath->bitmapquals)
137 {
138 List *sublist;
139
140 sublist = make_restrictinfo_from_bitmapqual((Path *) lfirst(l),
141 is_pushed_down,
142 include_predicates);
143 result = list_concat_unique(result, sublist);
144 }
145 }
146 else if (IsA(bitmapqual, BitmapOrPath))
147 {
148 BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
149 List *withris = NIL;
150 List *withoutris = NIL;
151
152 /*
153 * Here, we only detect qual-free subplans. A qual-free subplan would
154 * cause us to generate "... OR true ..." which we may as well reduce
155 * to just "true". We do not try to eliminate redundant subclauses
156 * because (a) it's not as likely as in the AND case, and (b) we might
157 * well be working with hundreds or even thousands of OR conditions,
158 * perhaps from a long IN list. The performance of list_append_unique
159 * would be unacceptable.
160 */
161 foreach(l, opath->bitmapquals)
162 {
163 List *sublist;
164
165 sublist = make_restrictinfo_from_bitmapqual((Path *) lfirst(l),
166 is_pushed_down,
167 include_predicates);
168 if (sublist == NIL)
169 {
170 /*
171 * If we find a qual-less subscan, it represents a constant
172 * TRUE, and hence the OR result is also constant TRUE, so we
173 * can stop here.
174 */
175 return NIL;
176 }
177
178 /*
179 * If the sublist contains multiple RestrictInfos, we create an
180 * AND subclause. If there's just one, we have to check if it's
181 * an OR clause, and if so flatten it to preserve AND/OR flatness
182 * of our output.
183 *
184 * We construct lists with and without sub-RestrictInfos, so as
185 * not to have to regenerate duplicate RestrictInfos below.
186 */
187 if (list_length(sublist) > 1)
188 {
189 withris = lappend(withris, make_andclause(sublist));
190 sublist = get_actual_clauses(sublist);
191 withoutris = lappend(withoutris, make_andclause(sublist));
192 }
193 else
194 {
195 RestrictInfo *subri = (RestrictInfo *) linitial(sublist);
196
197 Assert(IsA(subri, RestrictInfo));
198 if (restriction_is_or_clause(subri))
199 {
200 BoolExpr *subor = (BoolExpr *) subri->orclause;
201
202 Assert(or_clause((Node *) subor));
203 withris = list_concat(withris,
204 list_copy(subor->args));
205 subor = (BoolExpr *) subri->clause;
206 Assert(or_clause((Node *) subor));
207 withoutris = list_concat(withoutris,
208 list_copy(subor->args));
209 }
210 else
211 {
212 withris = lappend(withris, subri);
213 withoutris = lappend(withoutris, subri->clause);
214 }
215 }
216 }
217
218 /*
219 * Avoid generating one-element ORs, which could happen due to
220 * redundancy elimination or ScalarArrayOpExpr quals.
221 */
222 if (list_length(withris) <= 1)
223 result = withris;
224 else
225 {
226 /* Here's the magic part not available to outside callers */
227 result =
228 list_make1(make_restrictinfo_internal(make_orclause(withoutris),
229 make_orclause(withris),
230 is_pushed_down,
231 false,
232 false,
233 NULL,
234 NULL));
235 }
236 }
237 else if (IsA(bitmapqual, IndexPath))
238 {
239 IndexPath *ipath = (IndexPath *) bitmapqual;
240
241 result = list_copy(ipath->indexclauses);
242 if (include_predicates && ipath->indexinfo->indpred != NIL)
243 {
244 foreach(l, ipath->indexinfo->indpred)
245 {
246 Expr *pred = (Expr *) lfirst(l);
247
248 /*
249 * We know that the index predicate must have been implied by
250 * the query condition as a whole, but it may or may not be
251 * implied by the conditions that got pushed into the
252 * bitmapqual. Avoid generating redundant conditions.
253 */
254 if (!predicate_implied_by(list_make1(pred), result))
255 result = lappend(result,
256 make_restrictinfo(pred,
257 is_pushed_down,
258 false,
259 false,
260 NULL,
261 NULL));
262 }
263 }
264 }
265 else
266 {
267 elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
268 result = NIL; /* keep compiler quiet */
269 }
270
271 return result;
272 }
273
274 /*
275 * make_restrictinfo_internal
276 *
277 * Common code for the main entry points and the recursive cases.
278 */
279 static RestrictInfo *
280 make_restrictinfo_internal(Expr *clause,
281 Expr *orclause,
282 bool is_pushed_down,
283 bool outerjoin_delayed,
284 bool pseudoconstant,
285 Relids required_relids,
286 Relids nullable_relids)
287 {
288 RestrictInfo *restrictinfo = makeNode(RestrictInfo);
289
290 restrictinfo->clause = clause;
291 restrictinfo->orclause = orclause;
292 restrictinfo->is_pushed_down = is_pushed_down;
293 restrictinfo->outerjoin_delayed = outerjoin_delayed;
294 restrictinfo->pseudoconstant = pseudoconstant;
295 restrictinfo->can_join = false; /* may get set below */
296 restrictinfo->nullable_relids = nullable_relids;
297
298 /*
299 * If it's a binary opclause, set up left/right relids info. In any case
300 * set up the total clause relids info.
301 */
302 if (is_opclause(clause) && list_length(((OpExpr *) clause)->args) == 2)
303 {
304 restrictinfo->left_relids = pull_varnos(get_leftop(clause));
305 restrictinfo->right_relids = pull_varnos(get_rightop(clause));
306
307 restrictinfo->clause_relids = bms_union(restrictinfo->left_relids,
308 restrictinfo->right_relids);
309
310 /*
311 * Does it look like a normal join clause, i.e., a binary operator
312 * relating expressions that come from distinct relations? If so we
313 * might be able to use it in a join algorithm. Note that this is a
314 * purely syntactic test that is made regardless of context.
315 */
316 if (!bms_is_empty(restrictinfo->left_relids) &&
317 !bms_is_empty(restrictinfo->right_relids) &&
318 !bms_overlap(restrictinfo->left_relids,
319 restrictinfo->right_relids))
320 {
321 restrictinfo->can_join = true;
322 /* pseudoconstant should certainly not be true */
323 Assert(!restrictinfo->pseudoconstant);
324 }
325 }
326 else
327 {
328 /* Not a binary opclause, so mark left/right relid sets as empty */
329 restrictinfo->left_relids = NULL;
330 restrictinfo->right_relids = NULL;
331 /* and get the total relid set the hard way */
332 restrictinfo->clause_relids = pull_varnos((Node *) clause);
333 }
334
335 /* required_relids defaults to clause_relids */
336 if (required_relids != NULL)
337 restrictinfo->required_relids = required_relids;
338 else
339 restrictinfo->required_relids = restrictinfo->clause_relids;
340
341 /*
342 * Fill in all the cacheable fields with "not yet set" markers. None of
343 * these will be computed until/unless needed. Note in particular that we
344 * don't mark a binary opclause as mergejoinable or hashjoinable here;
345 * that happens only if it appears in the right context (top level of a
346 * joinclause list).
347 */
348 restrictinfo->parent_ec = NULL;
349
350 restrictinfo->eval_cost.startup = -1;
351 restrictinfo->norm_selec = -1;
352 restrictinfo->outer_selec = -1;
353
354 restrictinfo->mergeopfamilies = NIL;
355
356 restrictinfo->left_ec = NULL;
357 restrictinfo->right_ec = NULL;
358 restrictinfo->left_em = NULL;
359 restrictinfo->right_em = NULL;
360 restrictinfo->scansel_cache = NIL;
361
362 restrictinfo->outer_is_left = false;
363
364 restrictinfo->hashjoinoperator = InvalidOid;
365
366 restrictinfo->left_bucketsize = -1;
367 restrictinfo->right_bucketsize = -1;
368
369 return restrictinfo;
370 }
371
372 /*
373 * Recursively insert sub-RestrictInfo nodes into a boolean expression.
374 *
375 * We put RestrictInfos above simple (non-AND/OR) clauses and above
376 * sub-OR clauses, but not above sub-AND clauses, because there's no need.
377 * This may seem odd but it is closely related to the fact that we use
378 * implicit-AND lists at top level of RestrictInfo lists. Only ORs and
379 * simple clauses are valid RestrictInfos.
380 *
381 * The same is_pushed_down, outerjoin_delayed, and pseudoconstant flag
382 * values can be applied to all RestrictInfo nodes in the result. Likewise
383 * for nullable_relids.
384 *
385 * The given required_relids are attached to our top-level output,
386 * but any OR-clause constituents are allowed to default to just the
387 * contained rels.
388 */
389 static Expr *
390 make_sub_restrictinfos(Expr *clause,
391 bool is_pushed_down,
392 bool outerjoin_delayed,
393 bool pseudoconstant,
394 Relids required_relids,
395 Relids nullable_relids)
396 {
397 if (or_clause((Node *) clause))
398 {
399 List *orlist = NIL;
400 ListCell *temp;
401
402 foreach(temp, ((BoolExpr *) clause)->args)
403 orlist = lappend(orlist,
404 make_sub_restrictinfos(lfirst(temp),
405 is_pushed_down,
406 outerjoin_delayed,
407 pseudoconstant,
408 NULL,
409 nullable_relids));
410 return (Expr *) make_restrictinfo_internal(clause,
411 make_orclause(orlist),
412 is_pushed_down,
413 outerjoin_delayed,
414 pseudoconstant,
415 required_relids,
416 nullable_relids);
417 }
418 else if (and_clause((Node *) clause))
419 {
420 List *andlist = NIL;
421 ListCell *temp;
422
423 foreach(temp, ((BoolExpr *) clause)->args)
424 andlist = lappend(andlist,
425 make_sub_restrictinfos(lfirst(temp),
426 is_pushed_down,
427 outerjoin_delayed,
428 pseudoconstant,
429 required_relids,
430 nullable_relids));
431 return make_andclause(andlist);
432 }
433 else
434 return (Expr *) make_restrictinfo_internal(clause,
435 NULL,
436 is_pushed_down,
437 outerjoin_delayed,
438 pseudoconstant,
439 required_relids,
440 nullable_relids);
441 }
442
443 /*
444 * restriction_is_or_clause
445 *
446 * Returns t iff the restrictinfo node contains an 'or' clause.
447 */
448 bool
449 restriction_is_or_clause(RestrictInfo *restrictinfo)
450 {
451 if (restrictinfo->orclause != NULL)
452 return true;
453 else
454 return false;
455 }
456
457 /*
458 * get_actual_clauses
459 *
460 * Returns a list containing the bare clauses from 'restrictinfo_list'.
461 *
462 * This is only to be used in cases where none of the RestrictInfos can
463 * be pseudoconstant clauses (for instance, it's OK on indexqual lists).
464 */
465 List *
466 get_actual_clauses(List *restrictinfo_list)
467 {
468 List *result = NIL;
469 ListCell *l;
470
471 foreach(l, restrictinfo_list)
472 {
473 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
474
475 Assert(IsA(rinfo, RestrictInfo));
476
477 Assert(!rinfo->pseudoconstant);
478
479 result = lappend(result, rinfo->clause);
480 }
481 return result;
482 }
483
484 /*
485 * extract_actual_clauses
486 *
487 * Extract bare clauses from 'restrictinfo_list', returning either the
488 * regular ones or the pseudoconstant ones per 'pseudoconstant'.
489 */
490 List *
491 extract_actual_clauses(List *restrictinfo_list,
492 bool pseudoconstant)
493 {
494 List *result = NIL;
495 ListCell *l;
496
497 foreach(l, restrictinfo_list)
498 {
499 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
500
501 Assert(IsA(rinfo, RestrictInfo));
502
503 if (rinfo->pseudoconstant == pseudoconstant)
504 result = lappend(result, rinfo->clause);
505 }
506 return result;
507 }
508
509 /*
510 * extract_actual_join_clauses
511 *
512 * Extract bare clauses from 'restrictinfo_list', separating those that
513 * syntactically match the join level from those that were pushed down.
514 * Pseudoconstant clauses are excluded from the results.
515 *
516 * This is only used at outer joins, since for plain joins we don't care
517 * about pushed-down-ness.
518 */
519 void
520 extract_actual_join_clauses(List *restrictinfo_list,
521 List **joinquals,
522 List **otherquals)
523 {
524 ListCell *l;
525
526 *joinquals = NIL;
527 *otherquals = NIL;
528
529 foreach(l, restrictinfo_list)
530 {
531 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
532
533 Assert(IsA(rinfo, RestrictInfo));
534
535 if (rinfo->is_pushed_down)
536 {
537 if (!rinfo->pseudoconstant)
538 *otherquals = lappend(*otherquals, rinfo->clause);
539 }
540 else
541 {
542 /* joinquals shouldn't have been marked pseudoconstant */
543 Assert(!rinfo->pseudoconstant);
544 *joinquals = lappend(*joinquals, rinfo->clause);
545 }
546 }
547 }
548
549
550 /*
551 * select_nonredundant_join_clauses
552 *
553 * Given a list of RestrictInfo clauses that are to be applied in a join,
554 * select the ones that are not redundant with any clause that's enforced
555 * by the inner_path. This is used for nestloop joins, wherein any clause
556 * being used in an inner indexscan need not be checked again at the join.
557 *
558 * "Redundant" means either equal() or derived from the same EquivalenceClass.
559 * We have to check the latter because indxqual.c may select different derived
560 * clauses than were selected by generate_join_implied_equalities().
561 *
562 * Note that we are *not* checking for local redundancies within the given
563 * restrictinfo_list; that should have been handled elsewhere.
564 */
565 List *
566 select_nonredundant_join_clauses(PlannerInfo *root,
567 List *restrictinfo_list,
568 Path *inner_path)
569 {
570 if (IsA(inner_path, IndexPath))
571 {
572 /*
573 * Check the index quals to see if any of them are join clauses.
574 *
575 * We can skip this if the index path is an ordinary indexpath and not
576 * a special innerjoin path, since it then wouldn't be using any join
577 * clauses.
578 */
579 IndexPath *innerpath = (IndexPath *) inner_path;
580
581 if (innerpath->isjoininner)
582 restrictinfo_list =
583 select_nonredundant_join_list(restrictinfo_list,
584 innerpath->indexclauses);
585 }
586 else if (IsA(inner_path, BitmapHeapPath))
587 {
588 /*
589 * Same deal for bitmapped index scans.
590 *
591 * Note: both here and above, we ignore any implicit index
592 * restrictions associated with the use of partial indexes. This is
593 * OK because we're only trying to prove we can dispense with some
594 * join quals; failing to prove that doesn't result in an incorrect
595 * plan. It's quite unlikely that a join qual could be proven
596 * redundant by an index predicate anyway. (Also, if we did manage to
597 * prove it, we'd have to have a special case for update targets; see
598 * notes about EvalPlanQual testing in create_indexscan_plan().)
599 */
600 BitmapHeapPath *innerpath = (BitmapHeapPath *) inner_path;
601
602 if (innerpath->isjoininner)
603 {
604 List *bitmapclauses;
605
606 bitmapclauses =
607 make_restrictinfo_from_bitmapqual(innerpath->bitmapqual,
608 true,
609 false);
610 restrictinfo_list =
611 select_nonredundant_join_list(restrictinfo_list,
612 bitmapclauses);
613 }
614 }
615
616 /*
617 * XXX the inner path of a nestloop could also be an append relation whose
618 * elements use join quals. However, they might each use different quals;
619 * we could only remove join quals that are enforced by all the appendrel
620 * members. For the moment we don't bother to try.
621 */
622
623 return restrictinfo_list;
624 }
625
626 /*
627 * select_nonredundant_join_list
628 * Select the members of restrictinfo_list that are not redundant with
629 * any member of reference_list. See above for more info.
630 */
631 static List *
632 select_nonredundant_join_list(List *restrictinfo_list,
633 List *reference_list)
634 {
635 List *result = NIL;
636 ListCell *item;
637
638 foreach(item, restrictinfo_list)
639 {
640 RestrictInfo *rinfo = (RestrictInfo *) lfirst(item);
641
642 /* drop it if redundant with any reference clause */
643 if (join_clause_is_redundant(rinfo, reference_list))
644 continue;
645
646 /* otherwise, add it to result list */
647 result = lappend(result, rinfo);
648 }
649
650 return result;
651 }
652
653 /*
654 * join_clause_is_redundant
655 * Test whether rinfo is redundant with any clause in reference_list.
656 */
657 static bool
658 join_clause_is_redundant(RestrictInfo *rinfo,
659 List *reference_list)
660 {
661 ListCell *refitem;
662
663 foreach(refitem, reference_list)
664 {
665 RestrictInfo *refrinfo = (RestrictInfo *) lfirst(refitem);
666
667 /* always consider exact duplicates redundant */
668 if (equal(rinfo, refrinfo))
669 return true;
670
671 /* check if derived from same EquivalenceClass */
672 if (rinfo->parent_ec != NULL &&
673 rinfo->parent_ec == refrinfo->parent_ec)
674 return true;
675 }
676
677 return false;
678 }
PostgreSQL from CVS