Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * predtest.c
4 : * Routines to attempt to prove logical implications between predicate
5 : * expressions.
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/predtest.c
13 : *
14 : *-------------------------------------------------------------------------
15 : */
16 : #include "postgres.h"
17 :
18 : #include "catalog/pg_proc.h"
19 : #include "catalog/pg_type.h"
20 : #include "executor/executor.h"
21 : #include "miscadmin.h"
22 : #include "nodes/nodeFuncs.h"
23 : #include "optimizer/clauses.h"
24 : #include "optimizer/predtest.h"
25 : #include "utils/array.h"
26 : #include "utils/inval.h"
27 : #include "utils/lsyscache.h"
28 : #include "utils/syscache.h"
29 :
30 :
31 : /*
32 : * Proof attempts involving large arrays in ScalarArrayOpExpr nodes are
33 : * likely to require O(N^2) time, and more often than not fail anyway.
34 : * So we set an arbitrary limit on the number of array elements that
35 : * we will allow to be treated as an AND or OR clause.
36 : * XXX is it worth exposing this as a GUC knob?
37 : */
38 : #define MAX_SAOP_ARRAY_SIZE 100
39 :
40 : /*
41 : * To avoid redundant coding in predicate_implied_by_recurse and
42 : * predicate_refuted_by_recurse, we need to abstract out the notion of
43 : * iterating over the components of an expression that is logically an AND
44 : * or OR structure. There are multiple sorts of expression nodes that can
45 : * be treated as ANDs or ORs, and we don't want to code each one separately.
46 : * Hence, these types and support routines.
47 : */
48 : typedef enum
49 : {
50 : CLASS_ATOM, /* expression that's not AND or OR */
51 : CLASS_AND, /* expression with AND semantics */
52 : CLASS_OR /* expression with OR semantics */
53 : } PredClass;
54 :
55 : typedef struct PredIterInfoData *PredIterInfo;
56 :
57 : typedef struct PredIterInfoData
58 : {
59 : /* node-type-specific iteration state */
60 : void *state;
61 : /* initialize to do the iteration */
62 : void (*startup_fn) (Node *clause, PredIterInfo info);
63 : /* next-component iteration function */
64 : Node *(*next_fn) (PredIterInfo info);
65 : /* release resources when done with iteration */
66 : void (*cleanup_fn) (PredIterInfo info);
67 : } PredIterInfoData;
68 :
69 : #define iterate_begin(item, clause, info) \
70 : do { \
71 : Node *item; \
72 : (info).startup_fn((clause), &(info)); \
73 : while ((item = (info).next_fn(&(info))) != NULL)
74 :
75 : #define iterate_end(info) \
76 : (info).cleanup_fn(&(info)); \
77 : } while (0)
78 :
79 :
80 : static bool predicate_implied_by_recurse(Node *clause, Node *predicate,
81 : bool clause_is_check);
82 : static bool predicate_refuted_by_recurse(Node *clause, Node *predicate,
83 : bool clause_is_check);
84 : static PredClass predicate_classify(Node *clause, PredIterInfo info);
85 : static void list_startup_fn(Node *clause, PredIterInfo info);
86 : static Node *list_next_fn(PredIterInfo info);
87 : static void list_cleanup_fn(PredIterInfo info);
88 : static void boolexpr_startup_fn(Node *clause, PredIterInfo info);
89 : static void arrayconst_startup_fn(Node *clause, PredIterInfo info);
90 : static Node *arrayconst_next_fn(PredIterInfo info);
91 : static void arrayconst_cleanup_fn(PredIterInfo info);
92 : static void arrayexpr_startup_fn(Node *clause, PredIterInfo info);
93 : static Node *arrayexpr_next_fn(PredIterInfo info);
94 : static void arrayexpr_cleanup_fn(PredIterInfo info);
95 : static bool predicate_implied_by_simple_clause(Expr *predicate, Node *clause,
96 : bool clause_is_check);
97 : static bool predicate_refuted_by_simple_clause(Expr *predicate, Node *clause,
98 : bool clause_is_check);
99 : static Node *extract_not_arg(Node *clause);
100 : static Node *extract_strong_not_arg(Node *clause);
101 : static bool list_member_strip(List *list, Expr *datum);
102 : static bool operator_predicate_proof(Expr *predicate, Node *clause,
103 : bool refute_it);
104 : static bool operator_same_subexprs_proof(Oid pred_op, Oid clause_op,
105 : bool refute_it);
106 : static bool operator_same_subexprs_lookup(Oid pred_op, Oid clause_op,
107 : bool refute_it);
108 : static Oid get_btree_test_op(Oid pred_op, Oid clause_op, bool refute_it);
109 : static void InvalidateOprProofCacheCallBack(Datum arg, int cacheid, uint32 hashvalue);
110 :
111 :
112 : /*
113 : * predicate_implied_by
114 : * Recursively checks whether the clauses in clause_list imply that the
115 : * given predicate is true. If clause_is_check is true, assume that the
116 : * clauses in clause_list are CHECK constraints (where null is
117 : * effectively true) rather than WHERE clauses (where null is effectively
118 : * false).
119 : *
120 : * The top-level List structure of each list corresponds to an AND list.
121 : * We assume that eval_const_expressions() has been applied and so there
122 : * are no un-flattened ANDs or ORs (e.g., no AND immediately within an AND,
123 : * including AND just below the top-level List structure).
124 : * If this is not true we might fail to prove an implication that is
125 : * valid, but no worse consequences will ensue.
126 : *
127 : * We assume the predicate has already been checked to contain only
128 : * immutable functions and operators. (In most current uses this is true
129 : * because the predicate is part of an index predicate that has passed
130 : * CheckPredicate().) We dare not make deductions based on non-immutable
131 : * functions, because they might change answers between the time we make
132 : * the plan and the time we execute the plan.
133 : */
134 : bool
135 2339 : predicate_implied_by(List *predicate_list, List *clause_list,
136 : bool clause_is_check)
137 : {
138 : Node *p,
139 : *r;
140 :
141 2339 : if (predicate_list == NIL)
142 135 : return true; /* no predicate: implication is vacuous */
143 2204 : if (clause_list == NIL)
144 108 : return false; /* no restriction: implication must fail */
145 :
146 : /*
147 : * If either input is a single-element list, replace it with its lone
148 : * member; this avoids one useless level of AND-recursion. We only need
149 : * to worry about this at top level, since eval_const_expressions should
150 : * have gotten rid of any trivial ANDs or ORs below that.
151 : */
152 2096 : if (list_length(predicate_list) == 1)
153 2061 : p = (Node *) linitial(predicate_list);
154 : else
155 35 : p = (Node *) predicate_list;
156 2096 : if (list_length(clause_list) == 1)
157 1578 : r = (Node *) linitial(clause_list);
158 : else
159 518 : r = (Node *) clause_list;
160 :
161 : /* And away we go ... */
162 2096 : return predicate_implied_by_recurse(r, p, clause_is_check);
163 : }
164 :
165 : /*
166 : * predicate_refuted_by
167 : * Recursively checks whether the clauses in clause_list refute the given
168 : * predicate (that is, prove it false). If clause_is_check is true, assume
169 : * that the clauses in clause_list are CHECK constraints (where null is
170 : * effectively true) rather than WHERE clauses (where null is effectively
171 : * false).
172 : *
173 : * This is NOT the same as !(predicate_implied_by), though it is similar
174 : * in the technique and structure of the code.
175 : *
176 : * An important fine point is that truth of the clauses must imply that
177 : * the predicate returns FALSE, not that it does not return TRUE. This
178 : * is normally used to try to refute CHECK constraints, and the only
179 : * thing we can assume about a CHECK constraint is that it didn't return
180 : * FALSE --- a NULL result isn't a violation per the SQL spec. (Someday
181 : * perhaps this code should be extended to support both "strong" and
182 : * "weak" refutation, but for now we only need "strong".)
183 : *
184 : * The top-level List structure of each list corresponds to an AND list.
185 : * We assume that eval_const_expressions() has been applied and so there
186 : * are no un-flattened ANDs or ORs (e.g., no AND immediately within an AND,
187 : * including AND just below the top-level List structure).
188 : * If this is not true we might fail to prove an implication that is
189 : * valid, but no worse consequences will ensue.
190 : *
191 : * We assume the predicate has already been checked to contain only
192 : * immutable functions and operators. We dare not make deductions based on
193 : * non-immutable functions, because they might change answers between the
194 : * time we make the plan and the time we execute the plan.
195 : */
196 : bool
197 3042 : predicate_refuted_by(List *predicate_list, List *clause_list,
198 : bool clause_is_check)
199 : {
200 : Node *p,
201 : *r;
202 :
203 3042 : if (predicate_list == NIL)
204 1854 : return false; /* no predicate: no refutation is possible */
205 1188 : if (clause_list == NIL)
206 281 : return false; /* no restriction: refutation must fail */
207 :
208 : /*
209 : * If either input is a single-element list, replace it with its lone
210 : * member; this avoids one useless level of AND-recursion. We only need
211 : * to worry about this at top level, since eval_const_expressions should
212 : * have gotten rid of any trivial ANDs or ORs below that.
213 : */
214 907 : if (list_length(predicate_list) == 1)
215 527 : p = (Node *) linitial(predicate_list);
216 : else
217 380 : p = (Node *) predicate_list;
218 907 : if (list_length(clause_list) == 1)
219 609 : r = (Node *) linitial(clause_list);
220 : else
221 298 : r = (Node *) clause_list;
222 :
223 : /* And away we go ... */
224 907 : return predicate_refuted_by_recurse(r, p, clause_is_check);
225 : }
226 :
227 : /*----------
228 : * predicate_implied_by_recurse
229 : * Does the predicate implication test for non-NULL restriction and
230 : * predicate clauses.
231 : *
232 : * The logic followed here is ("=>" means "implies"):
233 : * atom A => atom B iff: predicate_implied_by_simple_clause says so
234 : * atom A => AND-expr B iff: A => each of B's components
235 : * atom A => OR-expr B iff: A => any of B's components
236 : * AND-expr A => atom B iff: any of A's components => B
237 : * AND-expr A => AND-expr B iff: A => each of B's components
238 : * AND-expr A => OR-expr B iff: A => any of B's components,
239 : * *or* any of A's components => B
240 : * OR-expr A => atom B iff: each of A's components => B
241 : * OR-expr A => AND-expr B iff: A => each of B's components
242 : * OR-expr A => OR-expr B iff: each of A's components => any of B's
243 : *
244 : * An "atom" is anything other than an AND or OR node. Notice that we don't
245 : * have any special logic to handle NOT nodes; these should have been pushed
246 : * down or eliminated where feasible by prepqual.c.
247 : *
248 : * We can't recursively expand either side first, but have to interleave
249 : * the expansions per the above rules, to be sure we handle all of these
250 : * examples:
251 : * (x OR y) => (x OR y OR z)
252 : * (x AND y AND z) => (x AND y)
253 : * (x AND y) => ((x AND y) OR z)
254 : * ((x OR y) AND z) => (x OR y)
255 : * This is still not an exhaustive test, but it handles most normal cases
256 : * under the assumption that both inputs have been AND/OR flattened.
257 : *
258 : * We have to be prepared to handle RestrictInfo nodes in the restrictinfo
259 : * tree, though not in the predicate tree.
260 : *----------
261 : */
262 : static bool
263 4212 : predicate_implied_by_recurse(Node *clause, Node *predicate,
264 : bool clause_is_check)
265 : {
266 : PredIterInfoData clause_info;
267 : PredIterInfoData pred_info;
268 : PredClass pclass;
269 : bool result;
270 :
271 : /* skip through RestrictInfo */
272 4212 : Assert(clause != NULL);
273 4212 : if (IsA(clause, RestrictInfo))
274 2485 : clause = (Node *) ((RestrictInfo *) clause)->clause;
275 :
276 4212 : pclass = predicate_classify(predicate, &pred_info);
277 :
278 4212 : switch (predicate_classify(clause, &clause_info))
279 : {
280 : case CLASS_AND:
281 766 : switch (pclass)
282 : {
283 : case CLASS_AND:
284 :
285 : /*
286 : * AND-clause => AND-clause if A implies each of B's items
287 : */
288 52 : result = true;
289 145 : iterate_begin(pitem, predicate, pred_info)
290 : {
291 84 : if (!predicate_implied_by_recurse(clause, pitem,
292 : clause_is_check))
293 : {
294 43 : result = false;
295 43 : break;
296 : }
297 : }
298 52 : iterate_end(pred_info);
299 52 : return result;
300 :
301 : case CLASS_OR:
302 :
303 : /*
304 : * AND-clause => OR-clause if A implies any of B's items
305 : *
306 : * Needed to handle (x AND y) => ((x AND y) OR z)
307 : */
308 42 : result = false;
309 147 : iterate_begin(pitem, predicate, pred_info)
310 : {
311 72 : if (predicate_implied_by_recurse(clause, pitem,
312 : clause_is_check))
313 : {
314 9 : result = true;
315 9 : break;
316 : }
317 : }
318 42 : iterate_end(pred_info);
319 42 : if (result)
320 9 : return result;
321 :
322 : /*
323 : * Also check if any of A's items implies B
324 : *
325 : * Needed to handle ((x OR y) AND z) => (x OR y)
326 : */
327 142 : iterate_begin(citem, clause, clause_info)
328 : {
329 77 : if (predicate_implied_by_recurse(citem, predicate,
330 : clause_is_check))
331 : {
332 1 : result = true;
333 1 : break;
334 : }
335 : }
336 33 : iterate_end(clause_info);
337 33 : return result;
338 :
339 : case CLASS_ATOM:
340 :
341 : /*
342 : * AND-clause => atom if any of A's items implies B
343 : */
344 672 : result = false;
345 2588 : iterate_begin(citem, clause, clause_info)
346 : {
347 1345 : if (predicate_implied_by_recurse(citem, predicate,
348 : clause_is_check))
349 : {
350 101 : result = true;
351 101 : break;
352 : }
353 : }
354 672 : iterate_end(clause_info);
355 672 : return result;
356 : }
357 0 : break;
358 :
359 : case CLASS_OR:
360 104 : switch (pclass)
361 : {
362 : case CLASS_OR:
363 :
364 : /*
365 : * OR-clause => OR-clause if each of A's items implies any
366 : * of B's items. Messy but can't do it any more simply.
367 : */
368 24 : result = true;
369 66 : iterate_begin(citem, clause, clause_info)
370 : {
371 35 : bool presult = false;
372 :
373 118 : iterate_begin(pitem, predicate, pred_info)
374 : {
375 66 : if (predicate_implied_by_recurse(citem, pitem,
376 : clause_is_check))
377 : {
378 18 : presult = true;
379 18 : break;
380 : }
381 : }
382 35 : iterate_end(pred_info);
383 35 : if (!presult)
384 : {
385 17 : result = false; /* doesn't imply any of B's */
386 17 : break;
387 : }
388 : }
389 24 : iterate_end(clause_info);
390 24 : return result;
391 :
392 : case CLASS_AND:
393 : case CLASS_ATOM:
394 :
395 : /*
396 : * OR-clause => AND-clause if each of A's items implies B
397 : *
398 : * OR-clause => atom if each of A's items implies B
399 : */
400 80 : result = true;
401 183 : iterate_begin(citem, clause, clause_info)
402 : {
403 99 : if (!predicate_implied_by_recurse(citem, predicate,
404 : clause_is_check))
405 : {
406 76 : result = false;
407 76 : break;
408 : }
409 : }
410 80 : iterate_end(clause_info);
411 80 : return result;
412 : }
413 0 : break;
414 :
415 : case CLASS_ATOM:
416 3342 : switch (pclass)
417 : {
418 : case CLASS_AND:
419 :
420 : /*
421 : * atom => AND-clause if A implies each of B's items
422 : */
423 34 : result = true;
424 73 : iterate_begin(pitem, predicate, pred_info)
425 : {
426 38 : if (!predicate_implied_by_recurse(clause, pitem,
427 : clause_is_check))
428 : {
429 33 : result = false;
430 33 : break;
431 : }
432 : }
433 34 : iterate_end(pred_info);
434 34 : return result;
435 :
436 : case CLASS_OR:
437 :
438 : /*
439 : * atom => OR-clause if A implies any of B's items
440 : */
441 161 : result = false;
442 603 : iterate_begin(pitem, predicate, pred_info)
443 : {
444 322 : if (predicate_implied_by_recurse(clause, pitem,
445 : clause_is_check))
446 : {
447 41 : result = true;
448 41 : break;
449 : }
450 : }
451 161 : iterate_end(pred_info);
452 161 : return result;
453 :
454 : case CLASS_ATOM:
455 :
456 : /*
457 : * atom => atom is the base case
458 : */
459 3147 : return
460 3147 : predicate_implied_by_simple_clause((Expr *) predicate,
461 : clause,
462 : clause_is_check);
463 : }
464 0 : break;
465 : }
466 :
467 : /* can't get here */
468 0 : elog(ERROR, "predicate_classify returned a bogus value");
469 : return false;
470 : }
471 :
472 : /*----------
473 : * predicate_refuted_by_recurse
474 : * Does the predicate refutation test for non-NULL restriction and
475 : * predicate clauses.
476 : *
477 : * The logic followed here is ("R=>" means "refutes"):
478 : * atom A R=> atom B iff: predicate_refuted_by_simple_clause says so
479 : * atom A R=> AND-expr B iff: A R=> any of B's components
480 : * atom A R=> OR-expr B iff: A R=> each of B's components
481 : * AND-expr A R=> atom B iff: any of A's components R=> B
482 : * AND-expr A R=> AND-expr B iff: A R=> any of B's components,
483 : * *or* any of A's components R=> B
484 : * AND-expr A R=> OR-expr B iff: A R=> each of B's components
485 : * OR-expr A R=> atom B iff: each of A's components R=> B
486 : * OR-expr A R=> AND-expr B iff: each of A's components R=> any of B's
487 : * OR-expr A R=> OR-expr B iff: A R=> each of B's components
488 : *
489 : * In addition, if the predicate is a NOT-clause then we can use
490 : * A R=> NOT B if: A => B
491 : * This works for several different SQL constructs that assert the non-truth
492 : * of their argument, ie NOT, IS FALSE, IS NOT TRUE, IS UNKNOWN.
493 : * Unfortunately we *cannot* use
494 : * NOT A R=> B if: B => A
495 : * because this type of reasoning fails to prove that B doesn't yield NULL.
496 : * We can however make the more limited deduction that
497 : * NOT A R=> A
498 : *
499 : * Other comments are as for predicate_implied_by_recurse().
500 : *----------
501 : */
502 : static bool
503 6984 : predicate_refuted_by_recurse(Node *clause, Node *predicate,
504 : bool clause_is_check)
505 : {
506 : PredIterInfoData clause_info;
507 : PredIterInfoData pred_info;
508 : PredClass pclass;
509 : Node *not_arg;
510 : bool result;
511 :
512 : /* skip through RestrictInfo */
513 6984 : Assert(clause != NULL);
514 6984 : if (IsA(clause, RestrictInfo))
515 1236 : clause = (Node *) ((RestrictInfo *) clause)->clause;
516 :
517 6984 : pclass = predicate_classify(predicate, &pred_info);
518 :
519 6984 : switch (predicate_classify(clause, &clause_info))
520 : {
521 : case CLASS_AND:
522 1276 : switch (pclass)
523 : {
524 : case CLASS_AND:
525 :
526 : /*
527 : * AND-clause R=> AND-clause if A refutes any of B's items
528 : *
529 : * Needed to handle (x AND y) R=> ((!x OR !y) AND z)
530 : */
531 325 : result = false;
532 1447 : iterate_begin(pitem, predicate, pred_info)
533 : {
534 873 : if (predicate_refuted_by_recurse(clause, pitem,
535 : clause_is_check))
536 : {
537 76 : result = true;
538 76 : break;
539 : }
540 : }
541 325 : iterate_end(pred_info);
542 325 : if (result)
543 76 : return result;
544 :
545 : /*
546 : * Also check if any of A's items refutes B
547 : *
548 : * Needed to handle ((x OR y) AND z) R=> (!x AND !y)
549 : */
550 1080 : iterate_begin(citem, clause, clause_info)
551 : {
552 582 : if (predicate_refuted_by_recurse(citem, predicate,
553 : clause_is_check))
554 : {
555 0 : result = true;
556 0 : break;
557 : }
558 : }
559 249 : iterate_end(clause_info);
560 249 : return result;
561 :
562 : case CLASS_OR:
563 :
564 : /*
565 : * AND-clause R=> OR-clause if A refutes each of B's items
566 : */
567 73 : result = true;
568 194 : iterate_begin(pitem, predicate, pred_info)
569 : {
570 105 : if (!predicate_refuted_by_recurse(clause, pitem,
571 : clause_is_check))
572 : {
573 57 : result = false;
574 57 : break;
575 : }
576 : }
577 73 : iterate_end(pred_info);
578 73 : return result;
579 :
580 : case CLASS_ATOM:
581 :
582 : /*
583 : * If B is a NOT-clause, A R=> B if A => B's arg
584 : */
585 878 : not_arg = extract_not_arg(predicate);
586 883 : if (not_arg &&
587 5 : predicate_implied_by_recurse(clause, not_arg,
588 : clause_is_check))
589 3 : return true;
590 :
591 : /*
592 : * AND-clause R=> atom if any of A's items refutes B
593 : */
594 875 : result = false;
595 3786 : iterate_begin(citem, clause, clause_info)
596 : {
597 2115 : if (predicate_refuted_by_recurse(citem, predicate,
598 : clause_is_check))
599 : {
600 79 : result = true;
601 79 : break;
602 : }
603 : }
604 875 : iterate_end(clause_info);
605 875 : return result;
606 : }
607 0 : break;
608 :
609 : case CLASS_OR:
610 179 : switch (pclass)
611 : {
612 : case CLASS_OR:
613 :
614 : /*
615 : * OR-clause R=> OR-clause if A refutes each of B's items
616 : */
617 29 : result = true;
618 62 : iterate_begin(pitem, predicate, pred_info)
619 : {
620 31 : if (!predicate_refuted_by_recurse(clause, pitem,
621 : clause_is_check))
622 : {
623 27 : result = false;
624 27 : break;
625 : }
626 : }
627 29 : iterate_end(pred_info);
628 29 : return result;
629 :
630 : case CLASS_AND:
631 :
632 : /*
633 : * OR-clause R=> AND-clause if each of A's items refutes
634 : * any of B's items.
635 : */
636 34 : result = true;
637 71 : iterate_begin(citem, clause, clause_info)
638 : {
639 37 : bool presult = false;
640 :
641 165 : iterate_begin(pitem, predicate, pred_info)
642 : {
643 94 : if (predicate_refuted_by_recurse(citem, pitem,
644 : clause_is_check))
645 : {
646 3 : presult = true;
647 3 : break;
648 : }
649 : }
650 37 : iterate_end(pred_info);
651 37 : if (!presult)
652 : {
653 34 : result = false; /* citem refutes nothing */
654 34 : break;
655 : }
656 : }
657 34 : iterate_end(clause_info);
658 34 : return result;
659 :
660 : case CLASS_ATOM:
661 :
662 : /*
663 : * If B is a NOT-clause, A R=> B if A => B's arg
664 : */
665 116 : not_arg = extract_not_arg(predicate);
666 116 : if (not_arg &&
667 0 : predicate_implied_by_recurse(clause, not_arg,
668 : clause_is_check))
669 0 : return true;
670 :
671 : /*
672 : * OR-clause R=> atom if each of A's items refutes B
673 : */
674 116 : result = true;
675 247 : iterate_begin(citem, clause, clause_info)
676 : {
677 127 : if (!predicate_refuted_by_recurse(citem, predicate,
678 : clause_is_check))
679 : {
680 112 : result = false;
681 112 : break;
682 : }
683 : }
684 116 : iterate_end(clause_info);
685 116 : return result;
686 : }
687 0 : break;
688 :
689 : case CLASS_ATOM:
690 :
691 : /*
692 : * If A is a strong NOT-clause, A R=> B if B equals A's arg
693 : *
694 : * We cannot make the stronger conclusion that B is refuted if B
695 : * implies A's arg; that would only prove that B is not-TRUE, not
696 : * that it's not NULL either. Hence use equal() rather than
697 : * predicate_implied_by_recurse(). We could do the latter if we
698 : * ever had a need for the weak form of refutation.
699 : */
700 5529 : not_arg = extract_strong_not_arg(clause);
701 5529 : if (not_arg && equal(predicate, not_arg))
702 0 : return true;
703 :
704 5529 : switch (pclass)
705 : {
706 : case CLASS_AND:
707 :
708 : /*
709 : * atom R=> AND-clause if A refutes any of B's items
710 : */
711 649 : result = false;
712 3186 : iterate_begin(pitem, predicate, pred_info)
713 : {
714 1945 : if (predicate_refuted_by_recurse(clause, pitem,
715 : clause_is_check))
716 : {
717 57 : result = true;
718 57 : break;
719 : }
720 : }
721 649 : iterate_end(pred_info);
722 649 : return result;
723 :
724 : case CLASS_OR:
725 :
726 : /*
727 : * atom R=> OR-clause if A refutes each of B's items
728 : */
729 185 : result = true;
730 405 : iterate_begin(pitem, predicate, pred_info)
731 : {
732 205 : if (!predicate_refuted_by_recurse(clause, pitem,
733 : clause_is_check))
734 : {
735 170 : result = false;
736 170 : break;
737 : }
738 : }
739 185 : iterate_end(pred_info);
740 185 : return result;
741 :
742 : case CLASS_ATOM:
743 :
744 : /*
745 : * If B is a NOT-clause, A R=> B if A => B's arg
746 : */
747 4695 : not_arg = extract_not_arg(predicate);
748 4703 : if (not_arg &&
749 8 : predicate_implied_by_recurse(clause, not_arg,
750 : clause_is_check))
751 0 : return true;
752 :
753 : /*
754 : * atom R=> atom is the base case
755 : */
756 4695 : return
757 4695 : predicate_refuted_by_simple_clause((Expr *) predicate,
758 : clause,
759 : clause_is_check);
760 : }
761 0 : break;
762 : }
763 :
764 : /* can't get here */
765 0 : elog(ERROR, "predicate_classify returned a bogus value");
766 : return false;
767 : }
768 :
769 :
770 : /*
771 : * predicate_classify
772 : * Classify an expression node as AND-type, OR-type, or neither (an atom).
773 : *
774 : * If the expression is classified as AND- or OR-type, then *info is filled
775 : * in with the functions needed to iterate over its components.
776 : *
777 : * This function also implements enforcement of MAX_SAOP_ARRAY_SIZE: if a
778 : * ScalarArrayOpExpr's array has too many elements, we just classify it as an
779 : * atom. (This will result in its being passed as-is to the simple_clause
780 : * functions, which will fail to prove anything about it.) Note that we
781 : * cannot just stop after considering MAX_SAOP_ARRAY_SIZE elements; in general
782 : * that would result in wrong proofs, rather than failing to prove anything.
783 : */
784 : static PredClass
785 22392 : predicate_classify(Node *clause, PredIterInfo info)
786 : {
787 : /* Caller should not pass us NULL, nor a RestrictInfo clause */
788 22392 : Assert(clause != NULL);
789 22392 : Assert(!IsA(clause, RestrictInfo));
790 :
791 : /*
792 : * If we see a List, assume it's an implicit-AND list; this is the correct
793 : * semantics for lists of RestrictInfo nodes.
794 : */
795 22392 : if (IsA(clause, List))
796 : {
797 2881 : info->startup_fn = list_startup_fn;
798 2881 : info->next_fn = list_next_fn;
799 2881 : info->cleanup_fn = list_cleanup_fn;
800 2881 : return CLASS_AND;
801 : }
802 :
803 : /* Handle normal AND and OR boolean clauses */
804 19511 : if (and_clause(clause))
805 : {
806 257 : info->startup_fn = boolexpr_startup_fn;
807 257 : info->next_fn = list_next_fn;
808 257 : info->cleanup_fn = list_cleanup_fn;
809 257 : return CLASS_AND;
810 : }
811 19254 : if (or_clause(clause))
812 : {
813 476 : info->startup_fn = boolexpr_startup_fn;
814 476 : info->next_fn = list_next_fn;
815 476 : info->cleanup_fn = list_cleanup_fn;
816 476 : return CLASS_OR;
817 : }
818 :
819 : /* Handle ScalarArrayOpExpr */
820 18778 : if (IsA(clause, ScalarArrayOpExpr))
821 : {
822 321 : ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
823 321 : Node *arraynode = (Node *) lsecond(saop->args);
824 :
825 : /*
826 : * We can break this down into an AND or OR structure, but only if we
827 : * know how to iterate through expressions for the array's elements.
828 : * We can do that if the array operand is a non-null constant or a
829 : * simple ArrayExpr.
830 : */
831 642 : if (arraynode && IsA(arraynode, Const) &&
832 321 : !((Const *) arraynode)->constisnull)
833 0 : {
834 : ArrayType *arrayval;
835 : int nelems;
836 :
837 321 : arrayval = DatumGetArrayTypeP(((Const *) arraynode)->constvalue);
838 321 : nelems = ArrayGetNItems(ARR_NDIM(arrayval), ARR_DIMS(arrayval));
839 321 : if (nelems <= MAX_SAOP_ARRAY_SIZE)
840 : {
841 321 : info->startup_fn = arrayconst_startup_fn;
842 321 : info->next_fn = arrayconst_next_fn;
843 321 : info->cleanup_fn = arrayconst_cleanup_fn;
844 321 : return saop->useOr ? CLASS_OR : CLASS_AND;
845 : }
846 : }
847 0 : else if (arraynode && IsA(arraynode, ArrayExpr) &&
848 0 : !((ArrayExpr *) arraynode)->multidims &&
849 0 : list_length(((ArrayExpr *) arraynode)->elements) <= MAX_SAOP_ARRAY_SIZE)
850 : {
851 0 : info->startup_fn = arrayexpr_startup_fn;
852 0 : info->next_fn = arrayexpr_next_fn;
853 0 : info->cleanup_fn = arrayexpr_cleanup_fn;
854 0 : return saop->useOr ? CLASS_OR : CLASS_AND;
855 : }
856 : }
857 :
858 : /* None of the above, so it's an atom */
859 18457 : return CLASS_ATOM;
860 : }
861 :
862 : /*
863 : * PredIterInfo routines for iterating over regular Lists. The iteration
864 : * state variable is the next ListCell to visit.
865 : */
866 : static void
867 2694 : list_startup_fn(Node *clause, PredIterInfo info)
868 : {
869 2694 : info->state = (void *) list_head((List *) clause);
870 2694 : }
871 :
872 : static Node *
873 10519 : list_next_fn(PredIterInfo info)
874 : {
875 10519 : ListCell *l = (ListCell *) info->state;
876 : Node *n;
877 :
878 10519 : if (l == NULL)
879 2675 : return NULL;
880 7844 : n = lfirst(l);
881 7844 : info->state = (void *) lnext(l);
882 7844 : return n;
883 : }
884 :
885 : static void
886 3398 : list_cleanup_fn(PredIterInfo info)
887 : {
888 : /* Nothing to clean up */
889 3398 : }
890 :
891 : /*
892 : * BoolExpr needs its own startup function, but can use list_next_fn and
893 : * list_cleanup_fn.
894 : */
895 : static void
896 704 : boolexpr_startup_fn(Node *clause, PredIterInfo info)
897 : {
898 704 : info->state = (void *) list_head(((BoolExpr *) clause)->args);
899 704 : }
900 :
901 : /*
902 : * PredIterInfo routines for iterating over a ScalarArrayOpExpr with a
903 : * constant array operand.
904 : */
905 : typedef struct
906 : {
907 : OpExpr opexpr;
908 : Const constexpr;
909 : int next_elem;
910 : int num_elems;
911 : Datum *elem_values;
912 : bool *elem_nulls;
913 : } ArrayConstIterState;
914 :
915 : static void
916 307 : arrayconst_startup_fn(Node *clause, PredIterInfo info)
917 : {
918 307 : ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
919 : ArrayConstIterState *state;
920 : Const *arrayconst;
921 : ArrayType *arrayval;
922 : int16 elmlen;
923 : bool elmbyval;
924 : char elmalign;
925 :
926 : /* Create working state struct */
927 307 : state = (ArrayConstIterState *) palloc(sizeof(ArrayConstIterState));
928 307 : info->state = (void *) state;
929 :
930 : /* Deconstruct the array literal */
931 307 : arrayconst = (Const *) lsecond(saop->args);
932 307 : arrayval = DatumGetArrayTypeP(arrayconst->constvalue);
933 307 : get_typlenbyvalalign(ARR_ELEMTYPE(arrayval),
934 : &elmlen, &elmbyval, &elmalign);
935 307 : deconstruct_array(arrayval,
936 : ARR_ELEMTYPE(arrayval),
937 : elmlen, elmbyval, elmalign,
938 : &state->elem_values, &state->elem_nulls,
939 : &state->num_elems);
940 :
941 : /* Set up a dummy OpExpr to return as the per-item node */
942 307 : state->opexpr.xpr.type = T_OpExpr;
943 307 : state->opexpr.opno = saop->opno;
944 307 : state->opexpr.opfuncid = saop->opfuncid;
945 307 : state->opexpr.opresulttype = BOOLOID;
946 307 : state->opexpr.opretset = false;
947 307 : state->opexpr.opcollid = InvalidOid;
948 307 : state->opexpr.inputcollid = saop->inputcollid;
949 307 : state->opexpr.args = list_copy(saop->args);
950 :
951 : /* Set up a dummy Const node to hold the per-element values */
952 307 : state->constexpr.xpr.type = T_Const;
953 307 : state->constexpr.consttype = ARR_ELEMTYPE(arrayval);
954 307 : state->constexpr.consttypmod = -1;
955 307 : state->constexpr.constcollid = arrayconst->constcollid;
956 307 : state->constexpr.constlen = elmlen;
957 307 : state->constexpr.constbyval = elmbyval;
958 307 : lsecond(state->opexpr.args) = &state->constexpr;
959 :
960 : /* Initialize iteration state */
961 307 : state->next_elem = 0;
962 307 : }
963 :
964 : static Node *
965 484 : arrayconst_next_fn(PredIterInfo info)
966 : {
967 484 : ArrayConstIterState *state = (ArrayConstIterState *) info->state;
968 :
969 484 : if (state->next_elem >= state->num_elems)
970 76 : return NULL;
971 408 : state->constexpr.constvalue = state->elem_values[state->next_elem];
972 408 : state->constexpr.constisnull = state->elem_nulls[state->next_elem];
973 408 : state->next_elem++;
974 408 : return (Node *) &(state->opexpr);
975 : }
976 :
977 : static void
978 307 : arrayconst_cleanup_fn(PredIterInfo info)
979 : {
980 307 : ArrayConstIterState *state = (ArrayConstIterState *) info->state;
981 :
982 307 : pfree(state->elem_values);
983 307 : pfree(state->elem_nulls);
984 307 : list_free(state->opexpr.args);
985 307 : pfree(state);
986 307 : }
987 :
988 : /*
989 : * PredIterInfo routines for iterating over a ScalarArrayOpExpr with a
990 : * one-dimensional ArrayExpr array operand.
991 : */
992 : typedef struct
993 : {
994 : OpExpr opexpr;
995 : ListCell *next;
996 : } ArrayExprIterState;
997 :
998 : static void
999 0 : arrayexpr_startup_fn(Node *clause, PredIterInfo info)
1000 : {
1001 0 : ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
1002 : ArrayExprIterState *state;
1003 : ArrayExpr *arrayexpr;
1004 :
1005 : /* Create working state struct */
1006 0 : state = (ArrayExprIterState *) palloc(sizeof(ArrayExprIterState));
1007 0 : info->state = (void *) state;
1008 :
1009 : /* Set up a dummy OpExpr to return as the per-item node */
1010 0 : state->opexpr.xpr.type = T_OpExpr;
1011 0 : state->opexpr.opno = saop->opno;
1012 0 : state->opexpr.opfuncid = saop->opfuncid;
1013 0 : state->opexpr.opresulttype = BOOLOID;
1014 0 : state->opexpr.opretset = false;
1015 0 : state->opexpr.opcollid = InvalidOid;
1016 0 : state->opexpr.inputcollid = saop->inputcollid;
1017 0 : state->opexpr.args = list_copy(saop->args);
1018 :
1019 : /* Initialize iteration variable to first member of ArrayExpr */
1020 0 : arrayexpr = (ArrayExpr *) lsecond(saop->args);
1021 0 : state->next = list_head(arrayexpr->elements);
1022 0 : }
1023 :
1024 : static Node *
1025 0 : arrayexpr_next_fn(PredIterInfo info)
1026 : {
1027 0 : ArrayExprIterState *state = (ArrayExprIterState *) info->state;
1028 :
1029 0 : if (state->next == NULL)
1030 0 : return NULL;
1031 0 : lsecond(state->opexpr.args) = lfirst(state->next);
1032 0 : state->next = lnext(state->next);
1033 0 : return (Node *) &(state->opexpr);
1034 : }
1035 :
1036 : static void
1037 0 : arrayexpr_cleanup_fn(PredIterInfo info)
1038 : {
1039 0 : ArrayExprIterState *state = (ArrayExprIterState *) info->state;
1040 :
1041 0 : list_free(state->opexpr.args);
1042 0 : pfree(state);
1043 0 : }
1044 :
1045 :
1046 : /*----------
1047 : * predicate_implied_by_simple_clause
1048 : * Does the predicate implication test for a "simple clause" predicate
1049 : * and a "simple clause" restriction.
1050 : *
1051 : * We return TRUE if able to prove the implication, FALSE if not.
1052 : *
1053 : * We have three strategies for determining whether one simple clause
1054 : * implies another:
1055 : *
1056 : * A simple and general way is to see if they are equal(); this works for any
1057 : * kind of expression. (Actually, there is an implied assumption that the
1058 : * functions in the expression are immutable, ie dependent only on their input
1059 : * arguments --- but this was checked for the predicate by the caller.)
1060 : *
1061 : * When clause_is_check is false, we know we are within an AND/OR
1062 : * subtree of a WHERE clause. So, if the predicate is of the form "foo IS
1063 : * NOT NULL", we can conclude that the predicate is implied if the clause is
1064 : * a strict operator or function that has "foo" as an input. In this case
1065 : * the clause must yield NULL when "foo" is NULL, which we can take as
1066 : * equivalent to FALSE given the context. (Again, "foo" is already known
1067 : * immutable, so the clause will certainly always fail.) Also, if the clause
1068 : * is just "foo" (meaning it's a boolean variable), the predicate is implied
1069 : * since the clause can't be true if "foo" is NULL.
1070 : *
1071 : * Finally, if both clauses are binary operator expressions, we may be able
1072 : * to prove something using the system's knowledge about operators; those
1073 : * proof rules are encapsulated in operator_predicate_proof().
1074 : *----------
1075 : */
1076 : static bool
1077 3147 : predicate_implied_by_simple_clause(Expr *predicate, Node *clause,
1078 : bool clause_is_check)
1079 : {
1080 : /* Allow interrupting long proof attempts */
1081 3147 : CHECK_FOR_INTERRUPTS();
1082 :
1083 : /* First try the equal() test */
1084 3147 : if (equal((Node *) predicate, clause))
1085 147 : return true;
1086 :
1087 : /* Next try the IS NOT NULL case */
1088 3028 : if (predicate && IsA(predicate, NullTest) &&
1089 28 : ((NullTest *) predicate)->nulltesttype == IS_NOT_NULL)
1090 : {
1091 21 : Expr *nonnullarg = ((NullTest *) predicate)->arg;
1092 :
1093 : /* row IS NOT NULL does not act in the simple way we have in mind */
1094 21 : if (!((NullTest *) predicate)->argisrow && !clause_is_check)
1095 : {
1096 12 : if (is_opclause(clause) &&
1097 6 : list_member_strip(((OpExpr *) clause)->args, nonnullarg) &&
1098 0 : op_strict(((OpExpr *) clause)->opno))
1099 0 : return true;
1100 6 : if (is_funcclause(clause) &&
1101 0 : list_member_strip(((FuncExpr *) clause)->args, nonnullarg) &&
1102 0 : func_strict(((FuncExpr *) clause)->funcid))
1103 0 : return true;
1104 6 : if (equal(clause, nonnullarg))
1105 0 : return true;
1106 : }
1107 21 : return false; /* we can't succeed below... */
1108 : }
1109 :
1110 : /* Else try operator-related knowledge */
1111 2979 : return operator_predicate_proof(predicate, clause, false);
1112 : }
1113 :
1114 : /*----------
1115 : * predicate_refuted_by_simple_clause
1116 : * Does the predicate refutation test for a "simple clause" predicate
1117 : * and a "simple clause" restriction.
1118 : *
1119 : * We return TRUE if able to prove the refutation, FALSE if not.
1120 : *
1121 : * Unlike the implication case, checking for equal() clauses isn't
1122 : * helpful.
1123 : *
1124 : * When the predicate is of the form "foo IS NULL", we can conclude that
1125 : * the predicate is refuted if the clause is a strict operator or function
1126 : * that has "foo" as an input (see notes for implication case), or if the
1127 : * clause is "foo IS NOT NULL". A clause "foo IS NULL" refutes a predicate
1128 : * "foo IS NOT NULL", but unfortunately does not refute strict predicates,
1129 : * because we are looking for strong refutation. (The motivation for covering
1130 : * these cases is to support using IS NULL/IS NOT NULL as partition-defining
1131 : * constraints.)
1132 : *
1133 : * Finally, if both clauses are binary operator expressions, we may be able
1134 : * to prove something using the system's knowledge about operators; those
1135 : * proof rules are encapsulated in operator_predicate_proof().
1136 : *----------
1137 : */
1138 : static bool
1139 4695 : predicate_refuted_by_simple_clause(Expr *predicate, Node *clause,
1140 : bool clause_is_check)
1141 : {
1142 : /* Allow interrupting long proof attempts */
1143 4695 : CHECK_FOR_INTERRUPTS();
1144 :
1145 : /* A simple clause can't refute itself */
1146 : /* Worth checking because of relation_excluded_by_constraints() */
1147 4695 : if ((Node *) predicate == clause)
1148 1277 : return false;
1149 :
1150 : /* Try the predicate-IS-NULL case */
1151 4398 : if (predicate && IsA(predicate, NullTest) &&
1152 980 : ((NullTest *) predicate)->nulltesttype == IS_NULL)
1153 : {
1154 20 : Expr *isnullarg = ((NullTest *) predicate)->arg;
1155 :
1156 20 : if (clause_is_check)
1157 0 : return false;
1158 :
1159 : /* row IS NULL does not act in the simple way we have in mind */
1160 20 : if (((NullTest *) predicate)->argisrow)
1161 0 : return false;
1162 :
1163 : /* Any strict op/func on foo refutes foo IS NULL */
1164 35 : if (is_opclause(clause) &&
1165 27 : list_member_strip(((OpExpr *) clause)->args, isnullarg) &&
1166 12 : op_strict(((OpExpr *) clause)->opno))
1167 12 : return true;
1168 8 : if (is_funcclause(clause) &&
1169 0 : list_member_strip(((FuncExpr *) clause)->args, isnullarg) &&
1170 0 : func_strict(((FuncExpr *) clause)->funcid))
1171 0 : return true;
1172 :
1173 : /* foo IS NOT NULL refutes foo IS NULL */
1174 13 : if (clause && IsA(clause, NullTest) &&
1175 8 : ((NullTest *) clause)->nulltesttype == IS_NOT_NULL &&
1176 6 : !((NullTest *) clause)->argisrow &&
1177 3 : equal(((NullTest *) clause)->arg, isnullarg))
1178 1 : return true;
1179 :
1180 7 : return false; /* we can't succeed below... */
1181 : }
1182 :
1183 : /* Try the clause-IS-NULL case */
1184 3596 : if (clause && IsA(clause, NullTest) &&
1185 198 : ((NullTest *) clause)->nulltesttype == IS_NULL)
1186 : {
1187 47 : Expr *isnullarg = ((NullTest *) clause)->arg;
1188 :
1189 : /* row IS NULL does not act in the simple way we have in mind */
1190 47 : if (((NullTest *) clause)->argisrow)
1191 0 : return false;
1192 :
1193 : /* foo IS NULL refutes foo IS NOT NULL */
1194 75 : if (predicate && IsA(predicate, NullTest) &&
1195 56 : ((NullTest *) predicate)->nulltesttype == IS_NOT_NULL &&
1196 56 : !((NullTest *) predicate)->argisrow &&
1197 28 : equal(((NullTest *) predicate)->arg, isnullarg))
1198 19 : return true;
1199 :
1200 28 : return false; /* we can't succeed below... */
1201 : }
1202 :
1203 : /* Else try operator-related knowledge */
1204 3351 : return operator_predicate_proof(predicate, clause, true);
1205 : }
1206 :
1207 :
1208 : /*
1209 : * If clause asserts the non-truth of a subclause, return that subclause;
1210 : * otherwise return NULL.
1211 : */
1212 : static Node *
1213 5689 : extract_not_arg(Node *clause)
1214 : {
1215 5689 : if (clause == NULL)
1216 0 : return NULL;
1217 5689 : if (IsA(clause, BoolExpr))
1218 : {
1219 0 : BoolExpr *bexpr = (BoolExpr *) clause;
1220 :
1221 0 : if (bexpr->boolop == NOT_EXPR)
1222 0 : return (Node *) linitial(bexpr->args);
1223 : }
1224 5689 : else if (IsA(clause, BooleanTest))
1225 : {
1226 13 : BooleanTest *btest = (BooleanTest *) clause;
1227 :
1228 13 : if (btest->booltesttype == IS_NOT_TRUE ||
1229 0 : btest->booltesttype == IS_FALSE ||
1230 0 : btest->booltesttype == IS_UNKNOWN)
1231 13 : return (Node *) btest->arg;
1232 : }
1233 5676 : return NULL;
1234 : }
1235 :
1236 : /*
1237 : * If clause asserts the falsity of a subclause, return that subclause;
1238 : * otherwise return NULL.
1239 : */
1240 : static Node *
1241 5529 : extract_strong_not_arg(Node *clause)
1242 : {
1243 5529 : if (clause == NULL)
1244 0 : return NULL;
1245 5529 : if (IsA(clause, BoolExpr))
1246 : {
1247 0 : BoolExpr *bexpr = (BoolExpr *) clause;
1248 :
1249 0 : if (bexpr->boolop == NOT_EXPR)
1250 0 : return (Node *) linitial(bexpr->args);
1251 : }
1252 5529 : else if (IsA(clause, BooleanTest))
1253 : {
1254 10 : BooleanTest *btest = (BooleanTest *) clause;
1255 :
1256 10 : if (btest->booltesttype == IS_FALSE)
1257 0 : return (Node *) btest->arg;
1258 : }
1259 5529 : return NULL;
1260 : }
1261 :
1262 :
1263 : /*
1264 : * Check whether an Expr is equal() to any member of a list, ignoring
1265 : * any top-level RelabelType nodes. This is legitimate for the purposes
1266 : * we use it for (matching IS [NOT] NULL arguments to arguments of strict
1267 : * functions) because RelabelType doesn't change null-ness. It's helpful
1268 : * for cases such as a varchar argument of a strict function on text.
1269 : */
1270 : static bool
1271 21 : list_member_strip(List *list, Expr *datum)
1272 : {
1273 : ListCell *cell;
1274 :
1275 21 : if (datum && IsA(datum, RelabelType))
1276 0 : datum = ((RelabelType *) datum)->arg;
1277 :
1278 39 : foreach(cell, list)
1279 : {
1280 30 : Expr *elem = (Expr *) lfirst(cell);
1281 :
1282 30 : if (elem && IsA(elem, RelabelType))
1283 7 : elem = ((RelabelType *) elem)->arg;
1284 :
1285 30 : if (equal(elem, datum))
1286 12 : return true;
1287 : }
1288 :
1289 9 : return false;
1290 : }
1291 :
1292 :
1293 : /*
1294 : * Define "operator implication tables" for btree operators ("strategies"),
1295 : * and similar tables for refutation.
1296 : *
1297 : * The strategy numbers defined by btree indexes (see access/stratnum.h) are:
1298 : * 1 < 2 <= 3 = 4 >= 5 >
1299 : * and in addition we use 6 to represent <>. <> is not a btree-indexable
1300 : * operator, but we assume here that if an equality operator of a btree
1301 : * opfamily has a negator operator, the negator behaves as <> for the opfamily.
1302 : * (This convention is also known to get_op_btree_interpretation().)
1303 : *
1304 : * BT_implies_table[] and BT_refutes_table[] are used for cases where we have
1305 : * two identical subexpressions and we want to know whether one operator
1306 : * expression implies or refutes the other. That is, if the "clause" is
1307 : * EXPR1 clause_op EXPR2 and the "predicate" is EXPR1 pred_op EXPR2 for the
1308 : * same two (immutable) subexpressions:
1309 : * BT_implies_table[clause_op-1][pred_op-1]
1310 : * is true if the clause implies the predicate
1311 : * BT_refutes_table[clause_op-1][pred_op-1]
1312 : * is true if the clause refutes the predicate
1313 : * where clause_op and pred_op are strategy numbers (from 1 to 6) in the
1314 : * same btree opfamily. For example, "x < y" implies "x <= y" and refutes
1315 : * "x > y".
1316 : *
1317 : * BT_implic_table[] and BT_refute_table[] are used where we have two
1318 : * constants that we need to compare. The interpretation of:
1319 : *
1320 : * test_op = BT_implic_table[clause_op-1][pred_op-1]
1321 : *
1322 : * where test_op, clause_op and pred_op are strategy numbers (from 1 to 6)
1323 : * of btree operators, is as follows:
1324 : *
1325 : * If you know, for some EXPR, that "EXPR clause_op CONST1" is true, and you
1326 : * want to determine whether "EXPR pred_op CONST2" must also be true, then
1327 : * you can use "CONST2 test_op CONST1" as a test. If this test returns true,
1328 : * then the predicate expression must be true; if the test returns false,
1329 : * then the predicate expression may be false.
1330 : *
1331 : * For example, if clause is "Quantity > 10" and pred is "Quantity > 5"
1332 : * then we test "5 <= 10" which evals to true, so clause implies pred.
1333 : *
1334 : * Similarly, the interpretation of a BT_refute_table entry is:
1335 : *
1336 : * If you know, for some EXPR, that "EXPR clause_op CONST1" is true, and you
1337 : * want to determine whether "EXPR pred_op CONST2" must be false, then
1338 : * you can use "CONST2 test_op CONST1" as a test. If this test returns true,
1339 : * then the predicate expression must be false; if the test returns false,
1340 : * then the predicate expression may be true.
1341 : *
1342 : * For example, if clause is "Quantity > 10" and pred is "Quantity < 5"
1343 : * then we test "5 <= 10" which evals to true, so clause refutes pred.
1344 : *
1345 : * An entry where test_op == 0 means the implication cannot be determined.
1346 : */
1347 :
1348 : #define BTLT BTLessStrategyNumber
1349 : #define BTLE BTLessEqualStrategyNumber
1350 : #define BTEQ BTEqualStrategyNumber
1351 : #define BTGE BTGreaterEqualStrategyNumber
1352 : #define BTGT BTGreaterStrategyNumber
1353 : #define BTNE ROWCOMPARE_NE
1354 :
1355 : /* We use "none" for 0/false to make the tables align nicely */
1356 : #define none 0
1357 :
1358 : static const bool BT_implies_table[6][6] = {
1359 : /*
1360 : * The predicate operator:
1361 : * LT LE EQ GE GT NE
1362 : */
1363 : {TRUE, TRUE, none, none, none, TRUE}, /* LT */
1364 : {none, TRUE, none, none, none, none}, /* LE */
1365 : {none, TRUE, TRUE, TRUE, none, none}, /* EQ */
1366 : {none, none, none, TRUE, none, none}, /* GE */
1367 : {none, none, none, TRUE, TRUE, TRUE}, /* GT */
1368 : {none, none, none, none, none, TRUE} /* NE */
1369 : };
1370 :
1371 : static const bool BT_refutes_table[6][6] = {
1372 : /*
1373 : * The predicate operator:
1374 : * LT LE EQ GE GT NE
1375 : */
1376 : {none, none, TRUE, TRUE, TRUE, none}, /* LT */
1377 : {none, none, none, none, TRUE, none}, /* LE */
1378 : {TRUE, none, none, none, TRUE, TRUE}, /* EQ */
1379 : {TRUE, none, none, none, none, none}, /* GE */
1380 : {TRUE, TRUE, TRUE, none, none, none}, /* GT */
1381 : {none, none, TRUE, none, none, none} /* NE */
1382 : };
1383 :
1384 : static const StrategyNumber BT_implic_table[6][6] = {
1385 : /*
1386 : * The predicate operator:
1387 : * LT LE EQ GE GT NE
1388 : */
1389 : {BTGE, BTGE, none, none, none, BTGE}, /* LT */
1390 : {BTGT, BTGE, none, none, none, BTGT}, /* LE */
1391 : {BTGT, BTGE, BTEQ, BTLE, BTLT, BTNE}, /* EQ */
1392 : {none, none, none, BTLE, BTLT, BTLT}, /* GE */
1393 : {none, none, none, BTLE, BTLE, BTLE}, /* GT */
1394 : {none, none, none, none, none, BTEQ} /* NE */
1395 : };
1396 :
1397 : static const StrategyNumber BT_refute_table[6][6] = {
1398 : /*
1399 : * The predicate operator:
1400 : * LT LE EQ GE GT NE
1401 : */
1402 : {none, none, BTGE, BTGE, BTGE, none}, /* LT */
1403 : {none, none, BTGT, BTGT, BTGE, none}, /* LE */
1404 : {BTLE, BTLT, BTNE, BTGT, BTGE, BTEQ}, /* EQ */
1405 : {BTLE, BTLT, BTLT, none, none, none}, /* GE */
1406 : {BTLE, BTLE, BTLE, none, none, none}, /* GT */
1407 : {none, none, BTEQ, none, none, none} /* NE */
1408 : };
1409 :
1410 :
1411 : /*
1412 : * operator_predicate_proof
1413 : * Does the predicate implication or refutation test for a "simple clause"
1414 : * predicate and a "simple clause" restriction, when both are operator
1415 : * clauses using related operators and identical input expressions.
1416 : *
1417 : * When refute_it == false, we want to prove the predicate true;
1418 : * when refute_it == true, we want to prove the predicate false.
1419 : * (There is enough common code to justify handling these two cases
1420 : * in one routine.) We return TRUE if able to make the proof, FALSE
1421 : * if not able to prove it.
1422 : *
1423 : * We can make proofs involving several expression forms (here "foo" and "bar"
1424 : * represent subexpressions that are identical according to equal()):
1425 : * "foo op1 bar" refutes "foo op2 bar" if op1 is op2's negator
1426 : * "foo op1 bar" implies "bar op2 foo" if op1 is op2's commutator
1427 : * "foo op1 bar" refutes "bar op2 foo" if op1 is negator of op2's commutator
1428 : * "foo op1 bar" can imply/refute "foo op2 bar" based on btree semantics
1429 : * "foo op1 bar" can imply/refute "bar op2 foo" based on btree semantics
1430 : * "foo op1 const1" can imply/refute "foo op2 const2" based on btree semantics
1431 : *
1432 : * For the last three cases, op1 and op2 have to be members of the same btree
1433 : * operator family. When both subexpressions are identical, the idea is that,
1434 : * for instance, x < y implies x <= y, independently of exactly what x and y
1435 : * are. If we have two different constants compared to the same expression
1436 : * foo, we have to execute a comparison between the two constant values
1437 : * in order to determine the result; for instance, foo < c1 implies foo < c2
1438 : * if c1 <= c2. We assume it's safe to compare the constants at plan time
1439 : * if the comparison operator is immutable.
1440 : *
1441 : * Note: all the operators and subexpressions have to be immutable for the
1442 : * proof to be safe. We assume the predicate expression is entirely immutable,
1443 : * so no explicit check on the subexpressions is needed here, but in some
1444 : * cases we need an extra check of operator immutability. In particular,
1445 : * btree opfamilies can contain cross-type operators that are merely stable,
1446 : * and we dare not make deductions with those.
1447 : */
1448 : static bool
1449 6330 : operator_predicate_proof(Expr *predicate, Node *clause, bool refute_it)
1450 : {
1451 : OpExpr *pred_opexpr,
1452 : *clause_opexpr;
1453 : Oid pred_collation,
1454 : clause_collation;
1455 : Oid pred_op,
1456 : clause_op,
1457 : test_op;
1458 : Node *pred_leftop,
1459 : *pred_rightop,
1460 : *clause_leftop,
1461 : *clause_rightop;
1462 : Const *pred_const,
1463 : *clause_const;
1464 : Expr *test_expr;
1465 : ExprState *test_exprstate;
1466 : Datum test_result;
1467 : bool isNull;
1468 : EState *estate;
1469 : MemoryContext oldcontext;
1470 :
1471 : /*
1472 : * Both expressions must be binary opclauses, else we can't do anything.
1473 : *
1474 : * Note: in future we might extend this logic to other operator-based
1475 : * constructs such as DistinctExpr. But the planner isn't very smart
1476 : * about DistinctExpr in general, and this probably isn't the first place
1477 : * to fix if you want to improve that.
1478 : */
1479 6330 : if (!is_opclause(predicate))
1480 2272 : return false;
1481 4058 : pred_opexpr = (OpExpr *) predicate;
1482 4058 : if (list_length(pred_opexpr->args) != 2)
1483 0 : return false;
1484 4058 : if (!is_opclause(clause))
1485 513 : return false;
1486 3545 : clause_opexpr = (OpExpr *) clause;
1487 3545 : if (list_length(clause_opexpr->args) != 2)
1488 0 : return false;
1489 :
1490 : /*
1491 : * If they're marked with different collations then we can't do anything.
1492 : * This is a cheap test so let's get it out of the way early.
1493 : */
1494 3545 : pred_collation = pred_opexpr->inputcollid;
1495 3545 : clause_collation = clause_opexpr->inputcollid;
1496 3545 : if (pred_collation != clause_collation)
1497 551 : return false;
1498 :
1499 : /* Grab the operator OIDs now too. We may commute these below. */
1500 2994 : pred_op = pred_opexpr->opno;
1501 2994 : clause_op = clause_opexpr->opno;
1502 :
1503 : /*
1504 : * We have to match up at least one pair of input expressions.
1505 : */
1506 2994 : pred_leftop = (Node *) linitial(pred_opexpr->args);
1507 2994 : pred_rightop = (Node *) lsecond(pred_opexpr->args);
1508 2994 : clause_leftop = (Node *) linitial(clause_opexpr->args);
1509 2994 : clause_rightop = (Node *) lsecond(clause_opexpr->args);
1510 :
1511 2994 : if (equal(pred_leftop, clause_leftop))
1512 : {
1513 922 : if (equal(pred_rightop, clause_rightop))
1514 : {
1515 : /* We have x op1 y and x op2 y */
1516 154 : return operator_same_subexprs_proof(pred_op, clause_op, refute_it);
1517 : }
1518 : else
1519 : {
1520 : /* Fail unless rightops are both Consts */
1521 768 : if (pred_rightop == NULL || !IsA(pred_rightop, Const))
1522 2 : return false;
1523 766 : pred_const = (Const *) pred_rightop;
1524 766 : if (clause_rightop == NULL || !IsA(clause_rightop, Const))
1525 0 : return false;
1526 766 : clause_const = (Const *) clause_rightop;
1527 : }
1528 : }
1529 2072 : else if (equal(pred_rightop, clause_rightop))
1530 : {
1531 : /* Fail unless leftops are both Consts */
1532 116 : if (pred_leftop == NULL || !IsA(pred_leftop, Const))
1533 116 : return false;
1534 0 : pred_const = (Const *) pred_leftop;
1535 0 : if (clause_leftop == NULL || !IsA(clause_leftop, Const))
1536 0 : return false;
1537 0 : clause_const = (Const *) clause_leftop;
1538 : /* Commute both operators so we can assume Consts are on the right */
1539 0 : pred_op = get_commutator(pred_op);
1540 0 : if (!OidIsValid(pred_op))
1541 0 : return false;
1542 0 : clause_op = get_commutator(clause_op);
1543 0 : if (!OidIsValid(clause_op))
1544 0 : return false;
1545 : }
1546 1956 : else if (equal(pred_leftop, clause_rightop))
1547 : {
1548 3 : if (equal(pred_rightop, clause_leftop))
1549 : {
1550 : /* We have x op1 y and y op2 x */
1551 : /* Commute pred_op that we can treat this like a straight match */
1552 3 : pred_op = get_commutator(pred_op);
1553 3 : if (!OidIsValid(pred_op))
1554 0 : return false;
1555 3 : return operator_same_subexprs_proof(pred_op, clause_op, refute_it);
1556 : }
1557 : else
1558 : {
1559 : /* Fail unless pred_rightop/clause_leftop are both Consts */
1560 0 : if (pred_rightop == NULL || !IsA(pred_rightop, Const))
1561 0 : return false;
1562 0 : pred_const = (Const *) pred_rightop;
1563 0 : if (clause_leftop == NULL || !IsA(clause_leftop, Const))
1564 0 : return false;
1565 0 : clause_const = (Const *) clause_leftop;
1566 : /* Commute clause_op so we can assume Consts are on the right */
1567 0 : clause_op = get_commutator(clause_op);
1568 0 : if (!OidIsValid(clause_op))
1569 0 : return false;
1570 : }
1571 : }
1572 1953 : else if (equal(pred_rightop, clause_leftop))
1573 : {
1574 : /* Fail unless pred_leftop/clause_rightop are both Consts */
1575 0 : if (pred_leftop == NULL || !IsA(pred_leftop, Const))
1576 0 : return false;
1577 0 : pred_const = (Const *) pred_leftop;
1578 0 : if (clause_rightop == NULL || !IsA(clause_rightop, Const))
1579 0 : return false;
1580 0 : clause_const = (Const *) clause_rightop;
1581 : /* Commute pred_op so we can assume Consts are on the right */
1582 0 : pred_op = get_commutator(pred_op);
1583 0 : if (!OidIsValid(pred_op))
1584 0 : return false;
1585 : }
1586 : else
1587 : {
1588 : /* Failed to match up any of the subexpressions, so we lose */
1589 1953 : return false;
1590 : }
1591 :
1592 : /*
1593 : * We have two identical subexpressions, and two other subexpressions that
1594 : * are not identical but are both Consts; and we have commuted the
1595 : * operators if necessary so that the Consts are on the right. We'll need
1596 : * to compare the Consts' values. If either is NULL, fail.
1597 : */
1598 766 : if (pred_const->constisnull)
1599 0 : return false;
1600 766 : if (clause_const->constisnull)
1601 2 : return false;
1602 :
1603 : /*
1604 : * Lookup the constant-comparison operator using the system catalogs and
1605 : * the operator implication tables.
1606 : */
1607 764 : test_op = get_btree_test_op(pred_op, clause_op, refute_it);
1608 :
1609 764 : if (!OidIsValid(test_op))
1610 : {
1611 : /* couldn't find a suitable comparison operator */
1612 202 : return false;
1613 : }
1614 :
1615 : /*
1616 : * Evaluate the test. For this we need an EState.
1617 : */
1618 562 : estate = CreateExecutorState();
1619 :
1620 : /* We can use the estate's working context to avoid memory leaks. */
1621 562 : oldcontext = MemoryContextSwitchTo(estate->es_query_cxt);
1622 :
1623 : /* Build expression tree */
1624 562 : test_expr = make_opclause(test_op,
1625 : BOOLOID,
1626 : false,
1627 : (Expr *) pred_const,
1628 : (Expr *) clause_const,
1629 : InvalidOid,
1630 : pred_collation);
1631 :
1632 : /* Fill in opfuncids */
1633 562 : fix_opfuncids((Node *) test_expr);
1634 :
1635 : /* Prepare it for execution */
1636 562 : test_exprstate = ExecInitExpr(test_expr, NULL);
1637 :
1638 : /* And execute it. */
1639 562 : test_result = ExecEvalExprSwitchContext(test_exprstate,
1640 562 : GetPerTupleExprContext(estate),
1641 : &isNull);
1642 :
1643 : /* Get back to outer memory context */
1644 562 : MemoryContextSwitchTo(oldcontext);
1645 :
1646 : /* Release all the junk we just created */
1647 562 : FreeExecutorState(estate);
1648 :
1649 562 : if (isNull)
1650 : {
1651 : /* Treat a null result as non-proof ... but it's a tad fishy ... */
1652 0 : elog(DEBUG2, "null predicate test result");
1653 0 : return false;
1654 : }
1655 562 : return DatumGetBool(test_result);
1656 : }
1657 :
1658 :
1659 : /*
1660 : * operator_same_subexprs_proof
1661 : * Assuming that EXPR1 clause_op EXPR2 is true, try to prove or refute
1662 : * EXPR1 pred_op EXPR2.
1663 : *
1664 : * Return TRUE if able to make the proof, false if not able to prove it.
1665 : */
1666 : static bool
1667 157 : operator_same_subexprs_proof(Oid pred_op, Oid clause_op, bool refute_it)
1668 : {
1669 : /*
1670 : * A simple and general rule is that the predicate is proven if clause_op
1671 : * and pred_op are the same, or refuted if they are each other's negators.
1672 : * We need not check immutability since the pred_op is already known
1673 : * immutable. (Actually, by this point we may have the commutator of a
1674 : * known-immutable pred_op, but that should certainly be immutable too.
1675 : * Likewise we don't worry whether the pred_op's negator is immutable.)
1676 : *
1677 : * Note: the "same" case won't get here if we actually had EXPR1 clause_op
1678 : * EXPR2 and EXPR1 pred_op EXPR2, because the overall-expression-equality
1679 : * test in predicate_implied_by_simple_clause would have caught it. But
1680 : * we can see the same operator after having commuted the pred_op.
1681 : */
1682 157 : if (refute_it)
1683 : {
1684 150 : if (get_negator(pred_op) == clause_op)
1685 8 : return true;
1686 : }
1687 : else
1688 : {
1689 7 : if (pred_op == clause_op)
1690 3 : return true;
1691 : }
1692 :
1693 : /*
1694 : * Otherwise, see if we can determine the implication by finding the
1695 : * operators' relationship via some btree opfamily.
1696 : */
1697 146 : return operator_same_subexprs_lookup(pred_op, clause_op, refute_it);
1698 : }
1699 :
1700 :
1701 : /*
1702 : * We use a lookaside table to cache the result of btree proof operator
1703 : * lookups, since the actual lookup is pretty expensive and doesn't change
1704 : * for any given pair of operators (at least as long as pg_amop doesn't
1705 : * change). A single hash entry stores both implication and refutation
1706 : * results for a given pair of operators; but note we may have determined
1707 : * only one of those sets of results as yet.
1708 : */
1709 : typedef struct OprProofCacheKey
1710 : {
1711 : Oid pred_op; /* predicate operator */
1712 : Oid clause_op; /* clause operator */
1713 : } OprProofCacheKey;
1714 :
1715 : typedef struct OprProofCacheEntry
1716 : {
1717 : /* the hash lookup key MUST BE FIRST */
1718 : OprProofCacheKey key;
1719 :
1720 : bool have_implic; /* do we know the implication result? */
1721 : bool have_refute; /* do we know the refutation result? */
1722 : bool same_subexprs_implies; /* X clause_op Y implies X pred_op Y? */
1723 : bool same_subexprs_refutes; /* X clause_op Y refutes X pred_op Y? */
1724 : Oid implic_test_op; /* OID of the test operator, or 0 if none */
1725 : Oid refute_test_op; /* OID of the test operator, or 0 if none */
1726 : } OprProofCacheEntry;
1727 :
1728 : static HTAB *OprProofCacheHash = NULL;
1729 :
1730 :
1731 : /*
1732 : * lookup_proof_cache
1733 : * Get, and fill in if necessary, the appropriate cache entry.
1734 : */
1735 : static OprProofCacheEntry *
1736 910 : lookup_proof_cache(Oid pred_op, Oid clause_op, bool refute_it)
1737 : {
1738 : OprProofCacheKey key;
1739 : OprProofCacheEntry *cache_entry;
1740 : bool cfound;
1741 910 : bool same_subexprs = false;
1742 910 : Oid test_op = InvalidOid;
1743 910 : bool found = false;
1744 : List *pred_op_infos,
1745 : *clause_op_infos;
1746 : ListCell *lcp,
1747 : *lcc;
1748 :
1749 : /*
1750 : * Find or make a cache entry for this pair of operators.
1751 : */
1752 910 : if (OprProofCacheHash == NULL)
1753 : {
1754 : /* First time through: initialize the hash table */
1755 : HASHCTL ctl;
1756 :
1757 19 : MemSet(&ctl, 0, sizeof(ctl));
1758 19 : ctl.keysize = sizeof(OprProofCacheKey);
1759 19 : ctl.entrysize = sizeof(OprProofCacheEntry);
1760 19 : OprProofCacheHash = hash_create("Btree proof lookup cache", 256,
1761 : &ctl, HASH_ELEM | HASH_BLOBS);
1762 :
1763 : /* Arrange to flush cache on pg_amop changes */
1764 19 : CacheRegisterSyscacheCallback(AMOPOPID,
1765 : InvalidateOprProofCacheCallBack,
1766 : (Datum) 0);
1767 : }
1768 :
1769 910 : key.pred_op = pred_op;
1770 910 : key.clause_op = clause_op;
1771 910 : cache_entry = (OprProofCacheEntry *) hash_search(OprProofCacheHash,
1772 : (void *) &key,
1773 : HASH_ENTER, &cfound);
1774 910 : if (!cfound)
1775 : {
1776 : /* new cache entry, set it invalid */
1777 84 : cache_entry->have_implic = false;
1778 84 : cache_entry->have_refute = false;
1779 : }
1780 : else
1781 : {
1782 : /* pre-existing cache entry, see if we know the answer yet */
1783 826 : if (refute_it ? cache_entry->have_refute : cache_entry->have_implic)
1784 822 : return cache_entry;
1785 : }
1786 :
1787 : /*
1788 : * Try to find a btree opfamily containing the given operators.
1789 : *
1790 : * We must find a btree opfamily that contains both operators, else the
1791 : * implication can't be determined. Also, the opfamily must contain a
1792 : * suitable test operator taking the operators' righthand datatypes.
1793 : *
1794 : * If there are multiple matching opfamilies, assume we can use any one to
1795 : * determine the logical relationship of the two operators and the correct
1796 : * corresponding test operator. This should work for any logically
1797 : * consistent opfamilies.
1798 : *
1799 : * Note that we can determine the operators' relationship for
1800 : * same-subexprs cases even from an opfamily that lacks a usable test
1801 : * operator. This can happen in cases with incomplete sets of cross-type
1802 : * comparison operators.
1803 : */
1804 88 : clause_op_infos = get_op_btree_interpretation(clause_op);
1805 88 : if (clause_op_infos)
1806 88 : pred_op_infos = get_op_btree_interpretation(pred_op);
1807 : else /* no point in looking */
1808 0 : pred_op_infos = NIL;
1809 :
1810 113 : foreach(lcp, pred_op_infos)
1811 : {
1812 83 : OpBtreeInterpretation *pred_op_info = lfirst(lcp);
1813 83 : Oid opfamily_id = pred_op_info->opfamily_id;
1814 :
1815 108 : foreach(lcc, clause_op_infos)
1816 : {
1817 83 : OpBtreeInterpretation *clause_op_info = lfirst(lcc);
1818 : StrategyNumber pred_strategy,
1819 : clause_strategy,
1820 : test_strategy;
1821 :
1822 : /* Must find them in same opfamily */
1823 83 : if (opfamily_id != clause_op_info->opfamily_id)
1824 0 : continue;
1825 : /* Lefttypes should match */
1826 83 : Assert(clause_op_info->oplefttype == pred_op_info->oplefttype);
1827 :
1828 83 : pred_strategy = pred_op_info->strategy;
1829 83 : clause_strategy = clause_op_info->strategy;
1830 :
1831 : /*
1832 : * Check to see if we can make a proof for same-subexpressions
1833 : * cases based on the operators' relationship in this opfamily.
1834 : */
1835 83 : if (refute_it)
1836 49 : same_subexprs |= BT_refutes_table[clause_strategy - 1][pred_strategy - 1];
1837 : else
1838 34 : same_subexprs |= BT_implies_table[clause_strategy - 1][pred_strategy - 1];
1839 :
1840 : /*
1841 : * Look up the "test" strategy number in the implication table
1842 : */
1843 83 : if (refute_it)
1844 49 : test_strategy = BT_refute_table[clause_strategy - 1][pred_strategy - 1];
1845 : else
1846 34 : test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1];
1847 :
1848 83 : if (test_strategy == 0)
1849 : {
1850 : /* Can't determine implication using this interpretation */
1851 25 : continue;
1852 : }
1853 :
1854 : /*
1855 : * See if opfamily has an operator for the test strategy and the
1856 : * datatypes.
1857 : */
1858 58 : if (test_strategy == BTNE)
1859 : {
1860 6 : test_op = get_opfamily_member(opfamily_id,
1861 : pred_op_info->oprighttype,
1862 : clause_op_info->oprighttype,
1863 : BTEqualStrategyNumber);
1864 6 : if (OidIsValid(test_op))
1865 6 : test_op = get_negator(test_op);
1866 : }
1867 : else
1868 : {
1869 52 : test_op = get_opfamily_member(opfamily_id,
1870 : pred_op_info->oprighttype,
1871 : clause_op_info->oprighttype,
1872 : test_strategy);
1873 : }
1874 :
1875 58 : if (!OidIsValid(test_op))
1876 0 : continue;
1877 :
1878 : /*
1879 : * Last check: test_op must be immutable.
1880 : *
1881 : * Note that we require only the test_op to be immutable, not the
1882 : * original clause_op. (pred_op is assumed to have been checked
1883 : * immutable by the caller.) Essentially we are assuming that the
1884 : * opfamily is consistent even if it contains operators that are
1885 : * merely stable.
1886 : */
1887 58 : if (op_volatile(test_op) == PROVOLATILE_IMMUTABLE)
1888 : {
1889 58 : found = true;
1890 58 : break;
1891 : }
1892 : }
1893 :
1894 83 : if (found)
1895 58 : break;
1896 : }
1897 :
1898 88 : list_free_deep(pred_op_infos);
1899 88 : list_free_deep(clause_op_infos);
1900 :
1901 88 : if (!found)
1902 : {
1903 : /* couldn't find a suitable comparison operator */
1904 30 : test_op = InvalidOid;
1905 : }
1906 :
1907 : /*
1908 : * If we think we were able to prove something about same-subexpressions
1909 : * cases, check to make sure the clause_op is immutable before believing
1910 : * it completely. (Usually, the clause_op would be immutable if the
1911 : * pred_op is, but it's not entirely clear that this must be true in all
1912 : * cases, so let's check.)
1913 : */
1914 122 : if (same_subexprs &&
1915 34 : op_volatile(clause_op) != PROVOLATILE_IMMUTABLE)
1916 0 : same_subexprs = false;
1917 :
1918 : /* Cache the results, whether positive or negative */
1919 88 : if (refute_it)
1920 : {
1921 49 : cache_entry->refute_test_op = test_op;
1922 49 : cache_entry->same_subexprs_refutes = same_subexprs;
1923 49 : cache_entry->have_refute = true;
1924 : }
1925 : else
1926 : {
1927 39 : cache_entry->implic_test_op = test_op;
1928 39 : cache_entry->same_subexprs_implies = same_subexprs;
1929 39 : cache_entry->have_implic = true;
1930 : }
1931 :
1932 88 : return cache_entry;
1933 : }
1934 :
1935 : /*
1936 : * operator_same_subexprs_lookup
1937 : * Convenience subroutine to look up the cached answer for
1938 : * same-subexpressions cases.
1939 : */
1940 : static bool
1941 146 : operator_same_subexprs_lookup(Oid pred_op, Oid clause_op, bool refute_it)
1942 : {
1943 : OprProofCacheEntry *cache_entry;
1944 :
1945 146 : cache_entry = lookup_proof_cache(pred_op, clause_op, refute_it);
1946 146 : if (refute_it)
1947 142 : return cache_entry->same_subexprs_refutes;
1948 : else
1949 4 : return cache_entry->same_subexprs_implies;
1950 : }
1951 :
1952 : /*
1953 : * get_btree_test_op
1954 : * Identify the comparison operator needed for a btree-operator
1955 : * proof or refutation involving comparison of constants.
1956 : *
1957 : * Given the truth of a clause "var clause_op const1", we are attempting to
1958 : * prove or refute a predicate "var pred_op const2". The identities of the
1959 : * two operators are sufficient to determine the operator (if any) to compare
1960 : * const2 to const1 with.
1961 : *
1962 : * Returns the OID of the operator to use, or InvalidOid if no proof is
1963 : * possible.
1964 : */
1965 : static Oid
1966 764 : get_btree_test_op(Oid pred_op, Oid clause_op, bool refute_it)
1967 : {
1968 : OprProofCacheEntry *cache_entry;
1969 :
1970 764 : cache_entry = lookup_proof_cache(pred_op, clause_op, refute_it);
1971 764 : if (refute_it)
1972 585 : return cache_entry->refute_test_op;
1973 : else
1974 179 : return cache_entry->implic_test_op;
1975 : }
1976 :
1977 :
1978 : /*
1979 : * Callback for pg_amop inval events
1980 : */
1981 : static void
1982 4 : InvalidateOprProofCacheCallBack(Datum arg, int cacheid, uint32 hashvalue)
1983 : {
1984 : HASH_SEQ_STATUS status;
1985 : OprProofCacheEntry *hentry;
1986 :
1987 4 : Assert(OprProofCacheHash != NULL);
1988 :
1989 : /* Currently we just reset all entries; hard to be smarter ... */
1990 4 : hash_seq_init(&status, OprProofCacheHash);
1991 :
1992 21 : while ((hentry = (OprProofCacheEntry *) hash_seq_search(&status)) != NULL)
1993 : {
1994 13 : hentry->have_implic = false;
1995 13 : hentry->have_refute = false;
1996 : }
1997 4 : }
|
