Age Owner Branch data TLA 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-2024, 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_operator.h"
19 : : #include "catalog/pg_proc.h"
20 : : #include "catalog/pg_type.h"
21 : : #include "executor/executor.h"
22 : : #include "miscadmin.h"
23 : : #include "nodes/makefuncs.h"
24 : : #include "nodes/nodeFuncs.h"
25 : : #include "nodes/pathnodes.h"
26 : : #include "optimizer/optimizer.h"
27 : : #include "utils/array.h"
28 : : #include "utils/inval.h"
29 : : #include "utils/lsyscache.h"
30 : : #include "utils/syscache.h"
31 : :
32 : :
33 : : /*
34 : : * Proof attempts involving large arrays in ScalarArrayOpExpr nodes are
35 : : * likely to require O(N^2) time, and more often than not fail anyway.
36 : : * So we set an arbitrary limit on the number of array elements that
37 : : * we will allow to be treated as an AND or OR clause.
38 : : * XXX is it worth exposing this as a GUC knob?
39 : : */
40 : : #define MAX_SAOP_ARRAY_SIZE 100
41 : :
42 : : /*
43 : : * To avoid redundant coding in predicate_implied_by_recurse and
44 : : * predicate_refuted_by_recurse, we need to abstract out the notion of
45 : : * iterating over the components of an expression that is logically an AND
46 : : * or OR structure. There are multiple sorts of expression nodes that can
47 : : * be treated as ANDs or ORs, and we don't want to code each one separately.
48 : : * Hence, these types and support routines.
49 : : */
50 : : typedef enum
51 : : {
52 : : CLASS_ATOM, /* expression that's not AND or OR */
53 : : CLASS_AND, /* expression with AND semantics */
54 : : CLASS_OR, /* expression with OR semantics */
55 : : } PredClass;
56 : :
57 : : typedef struct PredIterInfoData *PredIterInfo;
58 : :
59 : : typedef struct PredIterInfoData
60 : : {
61 : : /* node-type-specific iteration state */
62 : : void *state;
63 : : List *state_list;
64 : : /* initialize to do the iteration */
65 : : void (*startup_fn) (Node *clause, PredIterInfo info);
66 : : /* next-component iteration function */
67 : : Node *(*next_fn) (PredIterInfo info);
68 : : /* release resources when done with iteration */
69 : : void (*cleanup_fn) (PredIterInfo info);
70 : : } PredIterInfoData;
71 : :
72 : : #define iterate_begin(item, clause, info) \
73 : : do { \
74 : : Node *item; \
75 : : (info).startup_fn((clause), &(info)); \
76 : : while ((item = (info).next_fn(&(info))) != NULL)
77 : :
78 : : #define iterate_end(info) \
79 : : (info).cleanup_fn(&(info)); \
80 : : } while (0)
81 : :
82 : :
83 : : static bool predicate_implied_by_recurse(Node *clause, Node *predicate,
84 : : bool weak);
85 : : static bool predicate_refuted_by_recurse(Node *clause, Node *predicate,
86 : : bool weak);
87 : : static PredClass predicate_classify(Node *clause, PredIterInfo info);
88 : : static void list_startup_fn(Node *clause, PredIterInfo info);
89 : : static Node *list_next_fn(PredIterInfo info);
90 : : static void list_cleanup_fn(PredIterInfo info);
91 : : static void boolexpr_startup_fn(Node *clause, PredIterInfo info);
92 : : static void arrayconst_startup_fn(Node *clause, PredIterInfo info);
93 : : static Node *arrayconst_next_fn(PredIterInfo info);
94 : : static void arrayconst_cleanup_fn(PredIterInfo info);
95 : : static void arrayexpr_startup_fn(Node *clause, PredIterInfo info);
96 : : static Node *arrayexpr_next_fn(PredIterInfo info);
97 : : static void arrayexpr_cleanup_fn(PredIterInfo info);
98 : : static bool predicate_implied_by_simple_clause(Expr *predicate, Node *clause,
99 : : bool weak);
100 : : static bool predicate_refuted_by_simple_clause(Expr *predicate, Node *clause,
101 : : bool weak);
102 : : static Node *extract_not_arg(Node *clause);
103 : : static Node *extract_strong_not_arg(Node *clause);
104 : : static bool clause_is_strict_for(Node *clause, Node *subexpr, bool allow_false);
105 : : static bool operator_predicate_proof(Expr *predicate, Node *clause,
106 : : bool refute_it, bool weak);
107 : : static bool operator_same_subexprs_proof(Oid pred_op, Oid clause_op,
108 : : bool refute_it);
109 : : static bool operator_same_subexprs_lookup(Oid pred_op, Oid clause_op,
110 : : bool refute_it);
111 : : static Oid get_btree_test_op(Oid pred_op, Oid clause_op, bool refute_it);
112 : : static void InvalidateOprProofCacheCallBack(Datum arg, int cacheid, uint32 hashvalue);
113 : :
114 : :
115 : : /*
116 : : * predicate_implied_by
117 : : * Recursively checks whether the clauses in clause_list imply that the
118 : : * given predicate is true.
119 : : *
120 : : * We support two definitions of implication:
121 : : *
122 : : * "Strong" implication: A implies B means that truth of A implies truth of B.
123 : : * We use this to prove that a row satisfying one WHERE clause or index
124 : : * predicate must satisfy another one.
125 : : *
126 : : * "Weak" implication: A implies B means that non-falsity of A implies
127 : : * non-falsity of B ("non-false" means "either true or NULL"). We use this to
128 : : * prove that a row satisfying one CHECK constraint must satisfy another one.
129 : : *
130 : : * Strong implication can also be used to prove that a WHERE clause implies a
131 : : * CHECK constraint, although it will fail to prove a few cases where we could
132 : : * safely conclude that the implication holds. There's no support for proving
133 : : * the converse case, since only a few kinds of CHECK constraint would allow
134 : : * deducing anything.
135 : : *
136 : : * The top-level List structure of each list corresponds to an AND list.
137 : : * We assume that eval_const_expressions() has been applied and so there
138 : : * are no un-flattened ANDs or ORs (e.g., no AND immediately within an AND,
139 : : * including AND just below the top-level List structure).
140 : : * If this is not true we might fail to prove an implication that is
141 : : * valid, but no worse consequences will ensue.
142 : : *
143 : : * We assume the predicate has already been checked to contain only
144 : : * immutable functions and operators. (In many current uses this is known
145 : : * true because the predicate is part of an index predicate that has passed
146 : : * CheckPredicate(); otherwise, the caller must check it.) We dare not make
147 : : * deductions based on non-immutable functions, because they might change
148 : : * answers between the time we make the plan and the time we execute the plan.
149 : : * Immutability of functions in the clause_list is checked here, if necessary.
150 : : */
151 : : bool
2496 rhaas@postgresql.org 152 :CBC 41868 : predicate_implied_by(List *predicate_list, List *clause_list,
153 : : bool weak)
154 : : {
155 : : Node *p,
156 : : *c;
157 : :
6883 tgl@sss.pgh.pa.us 158 [ + + ]: 41868 : if (predicate_list == NIL)
159 : 549 : return true; /* no predicate: implication is vacuous */
2496 rhaas@postgresql.org 160 [ + + ]: 41319 : if (clause_list == NIL)
6883 tgl@sss.pgh.pa.us 161 : 2416 : return false; /* no restriction: implication must fail */
162 : :
163 : : /*
164 : : * If either input is a single-element list, replace it with its lone
165 : : * member; this avoids one useless level of AND-recursion. We only need
166 : : * to worry about this at top level, since eval_const_expressions should
167 : : * have gotten rid of any trivial ANDs or ORs below that.
168 : : */
5453 169 [ + + ]: 38903 : if (list_length(predicate_list) == 1)
170 : 38758 : p = (Node *) linitial(predicate_list);
171 : : else
172 : 145 : p = (Node *) predicate_list;
2496 rhaas@postgresql.org 173 [ + + ]: 38903 : if (list_length(clause_list) == 1)
2228 tgl@sss.pgh.pa.us 174 : 34249 : c = (Node *) linitial(clause_list);
175 : : else
176 : 4654 : c = (Node *) clause_list;
177 : :
178 : : /* And away we go ... */
179 : 38903 : return predicate_implied_by_recurse(c, p, weak);
180 : : }
181 : :
182 : : /*
183 : : * predicate_refuted_by
184 : : * Recursively checks whether the clauses in clause_list refute the given
185 : : * predicate (that is, prove it false).
186 : : *
187 : : * This is NOT the same as !(predicate_implied_by), though it is similar
188 : : * in the technique and structure of the code.
189 : : *
190 : : * We support two definitions of refutation:
191 : : *
192 : : * "Strong" refutation: A refutes B means truth of A implies falsity of B.
193 : : * We use this to disprove a CHECK constraint given a WHERE clause, i.e.,
194 : : * prove that any row satisfying the WHERE clause would violate the CHECK
195 : : * constraint. (Observe we must prove B yields false, not just not-true.)
196 : : *
197 : : * "Weak" refutation: A refutes B means truth of A implies non-truth of B
198 : : * (i.e., B must yield false or NULL). We use this to detect mutually
199 : : * contradictory WHERE clauses.
200 : : *
201 : : * Weak refutation can be proven in some cases where strong refutation doesn't
202 : : * hold, so it's useful to use it when possible. We don't currently have
203 : : * support for disproving one CHECK constraint based on another one, nor for
204 : : * disproving WHERE based on CHECK. (As with implication, the last case
205 : : * doesn't seem very practical. CHECK-vs-CHECK might be useful, but isn't
206 : : * currently needed anywhere.)
207 : : *
208 : : * The top-level List structure of each list corresponds to an AND list.
209 : : * We assume that eval_const_expressions() has been applied and so there
210 : : * are no un-flattened ANDs or ORs (e.g., no AND immediately within an AND,
211 : : * including AND just below the top-level List structure).
212 : : * If this is not true we might fail to prove an implication that is
213 : : * valid, but no worse consequences will ensue.
214 : : *
215 : : * We assume the predicate has already been checked to contain only
216 : : * immutable functions and operators. We dare not make deductions based on
217 : : * non-immutable functions, because they might change answers between the
218 : : * time we make the plan and the time we execute the plan.
219 : : * Immutability of functions in the clause_list is checked here, if necessary.
220 : : */
221 : : bool
2496 rhaas@postgresql.org 222 : 23813 : predicate_refuted_by(List *predicate_list, List *clause_list,
223 : : bool weak)
224 : : {
225 : : Node *p,
226 : : *c;
227 : :
6840 tgl@sss.pgh.pa.us 228 [ + + ]: 23813 : if (predicate_list == NIL)
229 : 8773 : return false; /* no predicate: no refutation is possible */
2496 rhaas@postgresql.org 230 [ - + ]: 15040 : if (clause_list == NIL)
6840 tgl@sss.pgh.pa.us 231 :UBC 0 : return false; /* no restriction: refutation must fail */
232 : :
233 : : /*
234 : : * If either input is a single-element list, replace it with its lone
235 : : * member; this avoids one useless level of AND-recursion. We only need
236 : : * to worry about this at top level, since eval_const_expressions should
237 : : * have gotten rid of any trivial ANDs or ORs below that.
238 : : */
5453 tgl@sss.pgh.pa.us 239 [ + + ]:CBC 15040 : if (list_length(predicate_list) == 1)
240 : 11630 : p = (Node *) linitial(predicate_list);
241 : : else
242 : 3410 : p = (Node *) predicate_list;
2496 rhaas@postgresql.org 243 [ + + ]: 15040 : if (list_length(clause_list) == 1)
2228 tgl@sss.pgh.pa.us 244 : 11417 : c = (Node *) linitial(clause_list);
245 : : else
246 : 3623 : c = (Node *) clause_list;
247 : :
248 : : /* And away we go ... */
249 : 15040 : return predicate_refuted_by_recurse(c, p, weak);
250 : : }
251 : :
252 : : /*----------
253 : : * predicate_implied_by_recurse
254 : : * Does the predicate implication test for non-NULL restriction and
255 : : * predicate clauses.
256 : : *
257 : : * The logic followed here is ("=>" means "implies"):
258 : : * atom A => atom B iff: predicate_implied_by_simple_clause says so
259 : : * atom A => AND-expr B iff: A => each of B's components
260 : : * atom A => OR-expr B iff: A => any of B's components
261 : : * AND-expr A => atom B iff: any of A's components => B
262 : : * AND-expr A => AND-expr B iff: A => each of B's components
263 : : * AND-expr A => OR-expr B iff: A => any of B's components,
264 : : * *or* any of A's components => B
265 : : * OR-expr A => atom B iff: each of A's components => B
266 : : * OR-expr A => AND-expr B iff: A => each of B's components
267 : : * OR-expr A => OR-expr B iff: each of A's components => any of B's
268 : : *
269 : : * An "atom" is anything other than an AND or OR node. Notice that we don't
270 : : * have any special logic to handle NOT nodes; these should have been pushed
271 : : * down or eliminated where feasible during eval_const_expressions().
272 : : *
273 : : * All of these rules apply equally to strong or weak implication.
274 : : *
275 : : * We can't recursively expand either side first, but have to interleave
276 : : * the expansions per the above rules, to be sure we handle all of these
277 : : * examples:
278 : : * (x OR y) => (x OR y OR z)
279 : : * (x AND y AND z) => (x AND y)
280 : : * (x AND y) => ((x AND y) OR z)
281 : : * ((x OR y) AND z) => (x OR y)
282 : : * This is still not an exhaustive test, but it handles most normal cases
283 : : * under the assumption that both inputs have been AND/OR flattened.
284 : : *
285 : : * We have to be prepared to handle RestrictInfo nodes in the restrictinfo
286 : : * tree, though not in the predicate tree.
287 : : *----------
288 : : */
289 : : static bool
2496 rhaas@postgresql.org 290 : 64075 : predicate_implied_by_recurse(Node *clause, Node *predicate,
291 : : bool weak)
292 : : {
293 : : PredIterInfoData clause_info;
294 : : PredIterInfoData pred_info;
295 : : PredClass pclass;
296 : : bool result;
297 : :
298 : : /* skip through RestrictInfo */
6713 tgl@sss.pgh.pa.us 299 [ - + ]: 64075 : Assert(clause != NULL);
6883 300 [ + + ]: 64075 : if (IsA(clause, RestrictInfo))
301 : 1613 : clause = (Node *) ((RestrictInfo *) clause)->clause;
302 : :
6713 303 : 64075 : pclass = predicate_classify(predicate, &pred_info);
304 : :
305 [ + + + - ]: 64075 : switch (predicate_classify(clause, &clause_info))
306 : : {
307 [ + + + - ]: 6401 : case CLASS_AND:
308 : : switch (pclass)
309 : : {
310 : 229 : case CLASS_AND:
311 : :
312 : : /*
313 : : * AND-clause => AND-clause if A implies each of B's items
314 : : */
315 : 229 : result = true;
316 [ + + ]: 451 : iterate_begin(pitem, predicate, pred_info)
317 : : {
2496 rhaas@postgresql.org 318 [ + + ]: 410 : if (!predicate_implied_by_recurse(clause, pitem,
319 : : weak))
320 : : {
6713 tgl@sss.pgh.pa.us 321 : 188 : result = false;
322 : 188 : break;
323 : : }
324 : : }
325 : 229 : iterate_end(pred_info);
326 : 229 : return result;
327 : :
328 : 379 : case CLASS_OR:
329 : :
330 : : /*
331 : : * AND-clause => OR-clause if A implies any of B's items
332 : : *
333 : : * Needed to handle (x AND y) => ((x AND y) OR z)
334 : : */
335 : 379 : result = false;
336 [ + + ]: 1307 : iterate_begin(pitem, predicate, pred_info)
337 : : {
2496 rhaas@postgresql.org 338 [ + + ]: 954 : if (predicate_implied_by_recurse(clause, pitem,
339 : : weak))
340 : : {
6713 tgl@sss.pgh.pa.us 341 : 26 : result = true;
342 : 26 : break;
343 : : }
344 : : }
345 : 379 : iterate_end(pred_info);
346 [ + + ]: 379 : if (result)
347 : 26 : return result;
348 : :
349 : : /*
350 : : * Also check if any of A's items implies B
351 : : *
352 : : * Needed to handle ((x OR y) AND z) => (x OR y)
353 : : */
354 [ + + ]: 1069 : iterate_begin(citem, clause, clause_info)
355 : : {
2496 rhaas@postgresql.org 356 [ + + ]: 722 : if (predicate_implied_by_recurse(citem, predicate,
357 : : weak))
358 : : {
6713 tgl@sss.pgh.pa.us 359 : 6 : result = true;
360 : 6 : break;
361 : : }
362 : : }
363 : 353 : iterate_end(clause_info);
364 : 353 : return result;
365 : :
366 : 5793 : case CLASS_ATOM:
367 : :
368 : : /*
369 : : * AND-clause => atom if any of A's items implies B
370 : : */
371 : 5793 : result = false;
372 [ + + ]: 16914 : iterate_begin(citem, clause, clause_info)
373 : : {
2496 rhaas@postgresql.org 374 [ + + ]: 11692 : if (predicate_implied_by_recurse(citem, predicate,
375 : : weak))
376 : : {
6713 tgl@sss.pgh.pa.us 377 : 571 : result = true;
378 : 571 : break;
379 : : }
380 : : }
381 : 5793 : iterate_end(clause_info);
382 : 5793 : return result;
383 : : }
6713 tgl@sss.pgh.pa.us 384 :UBC 0 : break;
385 : :
6713 tgl@sss.pgh.pa.us 386 [ + + - ]:CBC 687 : case CLASS_OR:
387 : : switch (pclass)
388 : : {
389 : 204 : case CLASS_OR:
390 : :
391 : : /*
392 : : * OR-clause => OR-clause if each of A's items implies any
393 : : * of B's items. Messy but can't do it any more simply.
394 : : */
395 : 204 : result = true;
396 [ + + ]: 333 : iterate_begin(citem, clause, clause_info)
397 : : {
6402 bruce@momjian.us 398 : 278 : bool presult = false;
399 : :
6713 tgl@sss.pgh.pa.us 400 [ + + ]: 674 : iterate_begin(pitem, predicate, pred_info)
401 : : {
2496 rhaas@postgresql.org 402 [ + + ]: 525 : if (predicate_implied_by_recurse(citem, pitem,
403 : : weak))
404 : : {
6713 tgl@sss.pgh.pa.us 405 : 129 : presult = true;
406 : 129 : break;
407 : : }
408 : : }
409 : 278 : iterate_end(pred_info);
410 [ + + ]: 278 : if (!presult)
411 : : {
2489 412 : 149 : result = false; /* doesn't imply any of B's */
6713 413 : 149 : break;
414 : : }
415 : : }
416 : 204 : iterate_end(clause_info);
417 : 204 : return result;
418 : :
419 : 483 : case CLASS_AND:
420 : : case CLASS_ATOM:
421 : :
422 : : /*
423 : : * OR-clause => AND-clause if each of A's items implies B
424 : : *
425 : : * OR-clause => atom if each of A's items implies B
426 : : */
427 : 483 : result = true;
428 [ + + ]: 603 : iterate_begin(citem, clause, clause_info)
429 : : {
2496 rhaas@postgresql.org 430 [ + + ]: 577 : if (!predicate_implied_by_recurse(citem, predicate,
431 : : weak))
432 : : {
6713 tgl@sss.pgh.pa.us 433 : 457 : result = false;
434 : 457 : break;
435 : : }
436 : : }
437 : 483 : iterate_end(clause_info);
438 : 483 : return result;
439 : : }
6713 tgl@sss.pgh.pa.us 440 :UBC 0 : break;
441 : :
6713 tgl@sss.pgh.pa.us 442 [ + + + - ]:CBC 56987 : case CLASS_ATOM:
443 : : switch (pclass)
444 : : {
445 : 751 : case CLASS_AND:
446 : :
447 : : /*
448 : : * atom => AND-clause if A implies each of B's items
449 : : */
450 : 751 : result = true;
451 [ + + ]: 999 : iterate_begin(pitem, predicate, pred_info)
452 : : {
2496 rhaas@postgresql.org 453 [ + + ]: 986 : if (!predicate_implied_by_recurse(clause, pitem,
454 : : weak))
455 : : {
6713 tgl@sss.pgh.pa.us 456 : 738 : result = false;
457 : 738 : break;
458 : : }
459 : : }
460 : 751 : iterate_end(pred_info);
461 : 751 : return result;
462 : :
463 : 3227 : case CLASS_OR:
464 : :
465 : : /*
466 : : * atom => OR-clause if A implies any of B's items
467 : : */
468 : 3227 : result = false;
469 [ + + ]: 11567 : iterate_begin(pitem, predicate, pred_info)
470 : : {
2496 rhaas@postgresql.org 471 [ + + ]: 8459 : if (predicate_implied_by_recurse(clause, pitem,
472 : : weak))
473 : : {
6713 tgl@sss.pgh.pa.us 474 : 119 : result = true;
475 : 119 : break;
476 : : }
477 : : }
478 : 3227 : iterate_end(pred_info);
479 : 3227 : return result;
480 : :
481 : 53009 : case CLASS_ATOM:
482 : :
483 : : /*
484 : : * atom => atom is the base case
485 : : */
486 : : return
487 : 53009 : predicate_implied_by_simple_clause((Expr *) predicate,
488 : : clause,
489 : : weak);
490 : : }
6713 tgl@sss.pgh.pa.us 491 :UBC 0 : break;
492 : : }
493 : :
494 : : /* can't get here */
495 [ # # ]: 0 : elog(ERROR, "predicate_classify returned a bogus value");
496 : : return false;
497 : : }
498 : :
499 : : /*----------
500 : : * predicate_refuted_by_recurse
501 : : * Does the predicate refutation test for non-NULL restriction and
502 : : * predicate clauses.
503 : : *
504 : : * The logic followed here is ("R=>" means "refutes"):
505 : : * atom A R=> atom B iff: predicate_refuted_by_simple_clause says so
506 : : * atom A R=> AND-expr B iff: A R=> any of B's components
507 : : * atom A R=> OR-expr B iff: A R=> each of B's components
508 : : * AND-expr A R=> atom B iff: any of A's components R=> B
509 : : * AND-expr A R=> AND-expr B iff: A R=> any of B's components,
510 : : * *or* any of A's components R=> B
511 : : * AND-expr A R=> OR-expr B iff: A R=> each of B's components
512 : : * OR-expr A R=> atom B iff: each of A's components R=> B
513 : : * OR-expr A R=> AND-expr B iff: each of A's components R=> any of B's
514 : : * OR-expr A R=> OR-expr B iff: A R=> each of B's components
515 : : *
516 : : * All of the above rules apply equally to strong or weak refutation.
517 : : *
518 : : * In addition, if the predicate is a NOT-clause then we can use
519 : : * A R=> NOT B if: A => B
520 : : * This works for several different SQL constructs that assert the non-truth
521 : : * of their argument, ie NOT, IS FALSE, IS NOT TRUE, IS UNKNOWN, although some
522 : : * of them require that we prove strong implication. Likewise, we can use
523 : : * NOT A R=> B if: B => A
524 : : * but here we must be careful about strong vs. weak refutation and make
525 : : * the appropriate type of implication proof (weak or strong respectively).
526 : : *
527 : : * Other comments are as for predicate_implied_by_recurse().
528 : : *----------
529 : : */
530 : : static bool
2496 rhaas@postgresql.org 531 :CBC 107884 : predicate_refuted_by_recurse(Node *clause, Node *predicate,
532 : : bool weak)
533 : : {
534 : : PredIterInfoData clause_info;
535 : : PredIterInfoData pred_info;
536 : : PredClass pclass;
537 : : Node *not_arg;
538 : : bool result;
539 : :
540 : : /* skip through RestrictInfo */
6713 tgl@sss.pgh.pa.us 541 [ - + ]: 107884 : Assert(clause != NULL);
6840 542 [ + + ]: 107884 : if (IsA(clause, RestrictInfo))
543 : 8335 : clause = (Node *) ((RestrictInfo *) clause)->clause;
544 : :
6713 545 : 107884 : pclass = predicate_classify(predicate, &pred_info);
546 : :
547 [ + + + - ]: 107884 : switch (predicate_classify(clause, &clause_info))
548 : : {
549 [ + + + - ]: 15931 : case CLASS_AND:
550 : : switch (pclass)
551 : : {
552 : 3563 : case CLASS_AND:
553 : :
554 : : /*
555 : : * AND-clause R=> AND-clause if A refutes any of B's items
556 : : *
557 : : * Needed to handle (x AND y) R=> ((!x OR !y) AND z)
558 : : */
559 : 3563 : result = false;
560 [ + + ]: 12492 : iterate_begin(pitem, predicate, pred_info)
561 : : {
2496 rhaas@postgresql.org 562 [ + + ]: 8985 : if (predicate_refuted_by_recurse(clause, pitem,
563 : : weak))
564 : : {
6713 tgl@sss.pgh.pa.us 565 : 56 : result = true;
566 : 56 : break;
567 : : }
568 : : }
569 : 3563 : iterate_end(pred_info);
570 [ + + ]: 3563 : if (result)
571 : 56 : return result;
572 : :
573 : : /*
574 : : * Also check if any of A's items refutes B
575 : : *
576 : : * Needed to handle ((x OR y) AND z) R=> (!x AND !y)
577 : : */
578 [ + + ]: 12722 : iterate_begin(citem, clause, clause_info)
579 : : {
2496 rhaas@postgresql.org 580 [ + + ]: 9217 : if (predicate_refuted_by_recurse(citem, predicate,
581 : : weak))
582 : : {
6713 tgl@sss.pgh.pa.us 583 : 2 : result = true;
584 : 2 : break;
585 : : }
586 : : }
587 : 3507 : iterate_end(clause_info);
588 : 3507 : return result;
589 : :
590 : 1562 : case CLASS_OR:
591 : :
592 : : /*
593 : : * AND-clause R=> OR-clause if A refutes each of B's items
594 : : */
595 : 1562 : result = true;
596 [ + + ]: 2100 : iterate_begin(pitem, predicate, pred_info)
597 : : {
2496 rhaas@postgresql.org 598 [ + + ]: 2098 : if (!predicate_refuted_by_recurse(clause, pitem,
599 : : weak))
600 : : {
6713 tgl@sss.pgh.pa.us 601 : 1560 : result = false;
602 : 1560 : break;
603 : : }
604 : : }
605 : 1562 : iterate_end(pred_info);
606 : 1562 : return result;
607 : :
608 : 10806 : case CLASS_ATOM:
609 : :
610 : : /*
611 : : * If B is a NOT-type clause, A R=> B if A => B's arg
612 : : *
613 : : * Since, for either type of refutation, we are starting
614 : : * with the premise that A is true, we can use a strong
615 : : * implication test in all cases. That proves B's arg is
616 : : * true, which is more than we need for weak refutation if
617 : : * B is a simple NOT, but it allows not worrying about
618 : : * exactly which kind of negation clause we have.
619 : : */
6462 620 : 10806 : not_arg = extract_not_arg(predicate);
621 [ + + + + ]: 10905 : if (not_arg &&
2496 rhaas@postgresql.org 622 : 99 : predicate_implied_by_recurse(clause, not_arg,
623 : : false))
6462 tgl@sss.pgh.pa.us 624 : 11 : return true;
625 : :
626 : : /*
627 : : * AND-clause R=> atom if any of A's items refutes B
628 : : */
6713 629 : 10795 : result = false;
630 [ + + ]: 39419 : iterate_begin(citem, clause, clause_info)
631 : : {
2496 rhaas@postgresql.org 632 [ + + ]: 29283 : if (predicate_refuted_by_recurse(citem, predicate,
633 : : weak))
634 : : {
6713 tgl@sss.pgh.pa.us 635 : 659 : result = true;
636 : 659 : break;
637 : : }
638 : : }
639 : 10795 : iterate_end(clause_info);
640 : 10795 : return result;
641 : : }
6713 tgl@sss.pgh.pa.us 642 :UBC 0 : break;
643 : :
6713 tgl@sss.pgh.pa.us 644 [ + + + - ]:CBC 6878 : case CLASS_OR:
645 : : switch (pclass)
646 : : {
647 : 655 : case CLASS_OR:
648 : :
649 : : /*
650 : : * OR-clause R=> OR-clause if A refutes each of B's items
651 : : */
652 : 655 : result = true;
653 [ + - ]: 674 : iterate_begin(pitem, predicate, pred_info)
654 : : {
2496 rhaas@postgresql.org 655 [ + + ]: 674 : if (!predicate_refuted_by_recurse(clause, pitem,
656 : : weak))
657 : : {
6713 tgl@sss.pgh.pa.us 658 : 655 : result = false;
659 : 655 : break;
660 : : }
661 : : }
662 : 655 : iterate_end(pred_info);
663 : 655 : return result;
664 : :
665 : 1446 : case CLASS_AND:
666 : :
667 : : /*
668 : : * OR-clause R=> AND-clause if each of A's items refutes
669 : : * any of B's items.
670 : : */
671 : 1446 : result = true;
672 [ + + ]: 1720 : iterate_begin(citem, clause, clause_info)
673 : : {
6402 bruce@momjian.us 674 : 1700 : bool presult = false;
675 : :
6713 tgl@sss.pgh.pa.us 676 [ + + ]: 6603 : iterate_begin(pitem, predicate, pred_info)
677 : : {
2496 rhaas@postgresql.org 678 [ + + ]: 5177 : if (predicate_refuted_by_recurse(citem, pitem,
679 : : weak))
680 : : {
6713 tgl@sss.pgh.pa.us 681 : 274 : presult = true;
682 : 274 : break;
683 : : }
684 : : }
685 : 1700 : iterate_end(pred_info);
686 [ + + ]: 1700 : if (!presult)
687 : : {
2489 688 : 1426 : result = false; /* citem refutes nothing */
6713 689 : 1426 : break;
690 : : }
691 : : }
692 : 1446 : iterate_end(clause_info);
693 : 1446 : return result;
694 : :
695 : 4777 : case CLASS_ATOM:
696 : :
697 : : /*
698 : : * If B is a NOT-type clause, A R=> B if A => B's arg
699 : : *
700 : : * Same logic as for the AND-clause case above.
701 : : */
6462 702 : 4777 : not_arg = extract_not_arg(predicate);
703 [ + + - + ]: 4781 : if (not_arg &&
2496 rhaas@postgresql.org 704 : 4 : predicate_implied_by_recurse(clause, not_arg,
705 : : false))
6462 tgl@sss.pgh.pa.us 706 :UBC 0 : return true;
707 : :
708 : : /*
709 : : * OR-clause R=> atom if each of A's items refutes B
710 : : */
6713 tgl@sss.pgh.pa.us 711 :CBC 4777 : result = true;
712 [ + + ]: 5198 : iterate_begin(citem, clause, clause_info)
713 : : {
2496 rhaas@postgresql.org 714 [ + + ]: 5197 : if (!predicate_refuted_by_recurse(citem, predicate,
715 : : weak))
716 : : {
6713 tgl@sss.pgh.pa.us 717 : 4776 : result = false;
718 : 4776 : break;
719 : : }
720 : : }
721 : 4777 : iterate_end(clause_info);
722 : 4777 : return result;
723 : : }
6713 tgl@sss.pgh.pa.us 724 :UBC 0 : break;
725 : :
6713 tgl@sss.pgh.pa.us 726 :CBC 85075 : case CLASS_ATOM:
727 : :
728 : : /*
729 : : * If A is a strong NOT-clause, A R=> B if B => A's arg
730 : : *
731 : : * Since A is strong, we may assume A's arg is false (not just
732 : : * not-true). If B weakly implies A's arg, then B can be neither
733 : : * true nor null, so that strong refutation is proven. If B
734 : : * strongly implies A's arg, then B cannot be true, so that weak
735 : : * refutation is proven.
736 : : */
5162 737 : 85075 : not_arg = extract_strong_not_arg(clause);
2228 738 [ + + + + ]: 85281 : if (not_arg &&
739 : 206 : predicate_implied_by_recurse(predicate, not_arg,
740 : 206 : !weak))
6462 741 : 11 : return true;
742 : :
743 : : switch (pclass)
744 : : {
6713 745 : 8893 : case CLASS_AND:
746 : :
747 : : /*
748 : : * atom R=> AND-clause if A refutes any of B's items
749 : : */
750 : 8893 : result = false;
751 [ + + ]: 33446 : iterate_begin(pitem, predicate, pred_info)
752 : : {
2496 rhaas@postgresql.org 753 [ + + ]: 24698 : if (predicate_refuted_by_recurse(clause, pitem,
754 : : weak))
755 : : {
6713 tgl@sss.pgh.pa.us 756 : 145 : result = true;
757 : 145 : break;
758 : : }
759 : : }
760 : 8893 : iterate_end(pred_info);
761 : 8893 : return result;
762 : :
763 : 5871 : case CLASS_OR:
764 : :
765 : : /*
766 : : * atom R=> OR-clause if A refutes each of B's items
767 : : */
768 : 5871 : result = true;
769 [ + + ]: 7617 : iterate_begin(pitem, predicate, pred_info)
770 : : {
2496 rhaas@postgresql.org 771 [ + + ]: 7515 : if (!predicate_refuted_by_recurse(clause, pitem,
772 : : weak))
773 : : {
6713 tgl@sss.pgh.pa.us 774 : 5769 : result = false;
775 : 5769 : break;
776 : : }
777 : : }
778 : 5871 : iterate_end(pred_info);
779 : 5871 : return result;
780 : :
781 : 70300 : case CLASS_ATOM:
782 : :
783 : : /*
784 : : * If B is a NOT-type clause, A R=> B if A => B's arg
785 : : *
786 : : * Same logic as for the AND-clause case above.
787 : : */
6462 788 : 70300 : not_arg = extract_not_arg(predicate);
789 [ + + + + ]: 70838 : if (not_arg &&
2496 rhaas@postgresql.org 790 : 538 : predicate_implied_by_recurse(clause, not_arg,
791 : : false))
6462 tgl@sss.pgh.pa.us 792 : 16 : return true;
793 : :
794 : : /*
795 : : * atom R=> atom is the base case
796 : : */
797 : : return
6713 798 : 70284 : predicate_refuted_by_simple_clause((Expr *) predicate,
799 : : clause,
800 : : weak);
801 : : }
6713 tgl@sss.pgh.pa.us 802 :UBC 0 : break;
803 : : }
804 : :
805 : : /* can't get here */
806 [ # # ]: 0 : elog(ERROR, "predicate_classify returned a bogus value");
807 : : return false;
808 : : }
809 : :
810 : :
811 : : /*
812 : : * predicate_classify
813 : : * Classify an expression node as AND-type, OR-type, or neither (an atom).
814 : : *
815 : : * If the expression is classified as AND- or OR-type, then *info is filled
816 : : * in with the functions needed to iterate over its components.
817 : : *
818 : : * This function also implements enforcement of MAX_SAOP_ARRAY_SIZE: if a
819 : : * ScalarArrayOpExpr's array has too many elements, we just classify it as an
820 : : * atom. (This will result in its being passed as-is to the simple_clause
821 : : * functions, many of which will fail to prove anything about it.) Note that we
822 : : * cannot just stop after considering MAX_SAOP_ARRAY_SIZE elements; in general
823 : : * that would result in wrong proofs, rather than failing to prove anything.
824 : : */
825 : : static PredClass
6713 tgl@sss.pgh.pa.us 826 :CBC 343918 : predicate_classify(Node *clause, PredIterInfo info)
827 : : {
828 : : /* Caller should not pass us NULL, nor a RestrictInfo clause */
829 [ - + ]: 343918 : Assert(clause != NULL);
830 [ - + ]: 343918 : Assert(!IsA(clause, RestrictInfo));
831 : :
832 : : /*
833 : : * If we see a List, assume it's an implicit-AND list; this is the correct
834 : : * semantics for lists of RestrictInfo nodes.
835 : : */
5452 836 [ + + ]: 343918 : if (IsA(clause, List))
837 : : {
6713 838 : 30732 : info->startup_fn = list_startup_fn;
839 : 30732 : info->next_fn = list_next_fn;
840 : 30732 : info->cleanup_fn = list_cleanup_fn;
841 : 30732 : return CLASS_AND;
842 : : }
843 : :
844 : : /* Handle normal AND and OR boolean clauses */
1902 845 [ + + ]: 313186 : if (is_andclause(clause))
846 : : {
6713 847 : 5867 : info->startup_fn = boolexpr_startup_fn;
848 : 5867 : info->next_fn = list_next_fn;
849 : 5867 : info->cleanup_fn = list_cleanup_fn;
850 : 5867 : return CLASS_AND;
851 : : }
1902 852 [ + + ]: 307319 : if (is_orclause(clause))
853 : : {
6713 854 : 14364 : info->startup_fn = boolexpr_startup_fn;
855 : 14364 : info->next_fn = list_next_fn;
856 : 14364 : info->cleanup_fn = list_cleanup_fn;
857 : 14364 : return CLASS_OR;
858 : : }
859 : :
860 : : /* Handle ScalarArrayOpExpr */
861 [ + + ]: 292955 : if (IsA(clause, ScalarArrayOpExpr))
862 : : {
863 : 5822 : ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
6402 bruce@momjian.us 864 : 5822 : Node *arraynode = (Node *) lsecond(saop->args);
865 : :
866 : : /*
867 : : * We can break this down into an AND or OR structure, but only if we
868 : : * know how to iterate through expressions for the array's elements.
869 : : * We can do that if the array operand is a non-null constant or a
870 : : * simple ArrayExpr.
871 : : */
6713 tgl@sss.pgh.pa.us 872 [ + - + + ]: 5822 : if (arraynode && IsA(arraynode, Const) &&
873 [ + - ]: 5239 : !((Const *) arraynode)->constisnull)
6840 874 : 8 : {
875 : : ArrayType *arrayval;
876 : : int nelems;
877 : :
5632 878 : 5239 : arrayval = DatumGetArrayTypeP(((Const *) arraynode)->constvalue);
879 : 5239 : nelems = ArrayGetNItems(ARR_NDIM(arrayval), ARR_DIMS(arrayval));
5452 880 [ + + ]: 5239 : if (nelems <= MAX_SAOP_ARRAY_SIZE)
881 : : {
5632 882 : 5231 : info->startup_fn = arrayconst_startup_fn;
883 : 5231 : info->next_fn = arrayconst_next_fn;
884 : 5231 : info->cleanup_fn = arrayconst_cleanup_fn;
885 [ + + ]: 5231 : return saop->useOr ? CLASS_OR : CLASS_AND;
886 : : }
887 : : }
888 [ + - + + ]: 583 : else if (arraynode && IsA(arraynode, ArrayExpr) &&
889 [ + - + + ]: 1036 : !((ArrayExpr *) arraynode)->multidims &&
5452 890 : 518 : list_length(((ArrayExpr *) arraynode)->elements) <= MAX_SAOP_ARRAY_SIZE)
891 : : {
6713 892 : 514 : info->startup_fn = arrayexpr_startup_fn;
893 : 514 : info->next_fn = arrayexpr_next_fn;
894 : 514 : info->cleanup_fn = arrayexpr_cleanup_fn;
895 [ + - ]: 514 : return saop->useOr ? CLASS_OR : CLASS_AND;
896 : : }
897 : : }
898 : :
899 : : /* None of the above, so it's an atom */
900 : 287210 : return CLASS_ATOM;
901 : : }
902 : :
903 : : /*
904 : : * PredIterInfo routines for iterating over regular Lists. The iteration
905 : : * state variable is the next ListCell to visit.
906 : : */
907 : : static void
908 : 29402 : list_startup_fn(Node *clause, PredIterInfo info)
909 : : {
1735 910 : 29402 : info->state_list = (List *) clause;
911 : 29402 : info->state = (void *) list_head(info->state_list);
6713 912 : 29402 : }
913 : :
914 : : static Node *
915 : 142211 : list_next_fn(PredIterInfo info)
916 : : {
917 : 142211 : ListCell *l = (ListCell *) info->state;
918 : : Node *n;
919 : :
920 [ + + ]: 142211 : if (l == NULL)
921 : 33954 : return NULL;
922 : 108257 : n = lfirst(l);
1735 923 : 108257 : info->state = (void *) lnext(info->state_list, l);
6713 924 : 108257 : return n;
925 : : }
926 : :
927 : : static void
928 : 48918 : list_cleanup_fn(PredIterInfo info)
929 : : {
930 : : /* Nothing to clean up */
931 : 48918 : }
932 : :
933 : : /*
934 : : * BoolExpr needs its own startup function, but can use list_next_fn and
935 : : * list_cleanup_fn.
936 : : */
937 : : static void
938 : 19516 : boolexpr_startup_fn(Node *clause, PredIterInfo info)
939 : : {
1735 940 : 19516 : info->state_list = ((BoolExpr *) clause)->args;
941 : 19516 : info->state = (void *) list_head(info->state_list);
6713 942 : 19516 : }
943 : :
944 : : /*
945 : : * PredIterInfo routines for iterating over a ScalarArrayOpExpr with a
946 : : * constant array operand.
947 : : */
948 : : typedef struct
949 : : {
950 : : OpExpr opexpr;
951 : : Const constexpr;
952 : : int next_elem;
953 : : int num_elems;
954 : : Datum *elem_values;
955 : : bool *elem_nulls;
956 : : } ArrayConstIterState;
957 : :
958 : : static void
959 : 5061 : arrayconst_startup_fn(Node *clause, PredIterInfo info)
960 : : {
961 : 5061 : ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
962 : : ArrayConstIterState *state;
963 : : Const *arrayconst;
964 : : ArrayType *arrayval;
965 : : int16 elmlen;
966 : : bool elmbyval;
967 : : char elmalign;
968 : :
969 : : /* Create working state struct */
970 : 5061 : state = (ArrayConstIterState *) palloc(sizeof(ArrayConstIterState));
971 : 5061 : info->state = (void *) state;
972 : :
973 : : /* Deconstruct the array literal */
974 : 5061 : arrayconst = (Const *) lsecond(saop->args);
975 : 5061 : arrayval = DatumGetArrayTypeP(arrayconst->constvalue);
976 : 5061 : get_typlenbyvalalign(ARR_ELEMTYPE(arrayval),
977 : : &elmlen, &elmbyval, &elmalign);
978 : 5061 : deconstruct_array(arrayval,
979 : : ARR_ELEMTYPE(arrayval),
980 : : elmlen, elmbyval, elmalign,
981 : : &state->elem_values, &state->elem_nulls,
982 : : &state->num_elems);
983 : :
984 : : /* Set up a dummy OpExpr to return as the per-item node */
985 : 5061 : state->opexpr.xpr.type = T_OpExpr;
986 : 5061 : state->opexpr.opno = saop->opno;
987 : 5061 : state->opexpr.opfuncid = saop->opfuncid;
988 : 5061 : state->opexpr.opresulttype = BOOLOID;
989 : 5061 : state->opexpr.opretset = false;
4768 990 : 5061 : state->opexpr.opcollid = InvalidOid;
991 : 5061 : state->opexpr.inputcollid = saop->inputcollid;
6713 992 : 5061 : state->opexpr.args = list_copy(saop->args);
993 : :
994 : : /* Set up a dummy Const node to hold the per-element values */
995 : 5061 : state->constexpr.xpr.type = T_Const;
996 : 5061 : state->constexpr.consttype = ARR_ELEMTYPE(arrayval);
6238 997 : 5061 : state->constexpr.consttypmod = -1;
4814 peter_e@gmx.net 998 : 5061 : state->constexpr.constcollid = arrayconst->constcollid;
6713 tgl@sss.pgh.pa.us 999 : 5061 : state->constexpr.constlen = elmlen;
1000 : 5061 : state->constexpr.constbyval = elmbyval;
1001 : 5061 : lsecond(state->opexpr.args) = &state->constexpr;
1002 : :
1003 : : /* Initialize iteration state */
1004 : 5061 : state->next_elem = 0;
1005 : 5061 : }
1006 : :
1007 : : static Node *
1008 : 13210 : arrayconst_next_fn(PredIterInfo info)
1009 : : {
1010 : 13210 : ArrayConstIterState *state = (ArrayConstIterState *) info->state;
1011 : :
1012 [ + + ]: 13210 : if (state->next_elem >= state->num_elems)
1013 : 2807 : return NULL;
1014 : 10403 : state->constexpr.constvalue = state->elem_values[state->next_elem];
1015 : 10403 : state->constexpr.constisnull = state->elem_nulls[state->next_elem];
1016 : 10403 : state->next_elem++;
1017 : 10403 : return (Node *) &(state->opexpr);
1018 : : }
1019 : :
1020 : : static void
1021 : 5061 : arrayconst_cleanup_fn(PredIterInfo info)
1022 : : {
1023 : 5061 : ArrayConstIterState *state = (ArrayConstIterState *) info->state;
1024 : :
1025 : 5061 : pfree(state->elem_values);
1026 : 5061 : pfree(state->elem_nulls);
1027 : 5061 : list_free(state->opexpr.args);
1028 : 5061 : pfree(state);
1029 : 5061 : }
1030 : :
1031 : : /*
1032 : : * PredIterInfo routines for iterating over a ScalarArrayOpExpr with a
1033 : : * one-dimensional ArrayExpr array operand.
1034 : : */
1035 : : typedef struct
1036 : : {
1037 : : OpExpr opexpr;
1038 : : ListCell *next;
1039 : : } ArrayExprIterState;
1040 : :
1041 : : static void
1042 : 487 : arrayexpr_startup_fn(Node *clause, PredIterInfo info)
1043 : : {
1044 : 487 : ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
1045 : : ArrayExprIterState *state;
1046 : : ArrayExpr *arrayexpr;
1047 : :
1048 : : /* Create working state struct */
1049 : 487 : state = (ArrayExprIterState *) palloc(sizeof(ArrayExprIterState));
1050 : 487 : info->state = (void *) state;
1051 : :
1052 : : /* Set up a dummy OpExpr to return as the per-item node */
1053 : 487 : state->opexpr.xpr.type = T_OpExpr;
1054 : 487 : state->opexpr.opno = saop->opno;
1055 : 487 : state->opexpr.opfuncid = saop->opfuncid;
1056 : 487 : state->opexpr.opresulttype = BOOLOID;
1057 : 487 : state->opexpr.opretset = false;
4768 1058 : 487 : state->opexpr.opcollid = InvalidOid;
1059 : 487 : state->opexpr.inputcollid = saop->inputcollid;
6713 1060 : 487 : state->opexpr.args = list_copy(saop->args);
1061 : :
1062 : : /* Initialize iteration variable to first member of ArrayExpr */
1063 : 487 : arrayexpr = (ArrayExpr *) lsecond(saop->args);
1735 1064 : 487 : info->state_list = arrayexpr->elements;
6713 1065 : 487 : state->next = list_head(arrayexpr->elements);
1066 : 487 : }
1067 : :
1068 : : static Node *
1069 : 487 : arrayexpr_next_fn(PredIterInfo info)
1070 : : {
1071 : 487 : ArrayExprIterState *state = (ArrayExprIterState *) info->state;
1072 : :
1073 [ - + ]: 487 : if (state->next == NULL)
6713 tgl@sss.pgh.pa.us 1074 :UBC 0 : return NULL;
6713 tgl@sss.pgh.pa.us 1075 :CBC 487 : lsecond(state->opexpr.args) = lfirst(state->next);
1735 1076 : 487 : state->next = lnext(info->state_list, state->next);
6713 1077 : 487 : return (Node *) &(state->opexpr);
1078 : : }
1079 : :
1080 : : static void
1081 : 487 : arrayexpr_cleanup_fn(PredIterInfo info)
1082 : : {
1083 : 487 : ArrayExprIterState *state = (ArrayExprIterState *) info->state;
1084 : :
1085 : 487 : list_free(state->opexpr.args);
1086 : 487 : pfree(state);
6840 1087 : 487 : }
1088 : :
1089 : :
1090 : : /*
1091 : : * predicate_implied_by_simple_clause
1092 : : * Does the predicate implication test for a "simple clause" predicate
1093 : : * and a "simple clause" restriction.
1094 : : *
1095 : : * We return true if able to prove the implication, false if not.
1096 : : */
1097 : : static bool
2496 rhaas@postgresql.org 1098 : 53009 : predicate_implied_by_simple_clause(Expr *predicate, Node *clause,
1099 : : bool weak)
1100 : : {
1101 : : /* Allow interrupting long proof attempts */
5632 tgl@sss.pgh.pa.us 1102 [ - + ]: 53009 : CHECK_FOR_INTERRUPTS();
1103 : :
1104 : : /*
1105 : : * A simple and general rule is that a clause implies itself, hence we
1106 : : * check if they are equal(); this works for any kind of expression, and
1107 : : * for either implication definition. (Actually, there is an implied
1108 : : * assumption that the functions in the expression are immutable --- but
1109 : : * this was checked for the predicate by the caller.)
1110 : : */
6840 1111 [ + + ]: 53009 : if (equal((Node *) predicate, clause))
1112 : 1121 : return true;
1113 : :
1114 : : /* Next we have some clause-type-specific strategies */
20 tgl@sss.pgh.pa.us 1115 [ + + ]:GNC 51888 : switch (nodeTag(clause))
1116 : : {
1117 : 50142 : case T_OpExpr:
1118 : : {
1119 : 50142 : OpExpr *op = (OpExpr *) clause;
1120 : :
1121 : : /*----------
1122 : : * For boolean x, "x = TRUE" is equivalent to "x", likewise
1123 : : * "x = FALSE" is equivalent to "NOT x". These can be worth
1124 : : * checking because, while we preferentially simplify boolean
1125 : : * comparisons down to "x" and "NOT x", the other form has to
1126 : : * be dealt with anyway in the context of index conditions.
1127 : : *
1128 : : * We could likewise check whether the predicate is boolean
1129 : : * equality to a constant; but there are no known use-cases
1130 : : * for that at the moment, assuming that the predicate has
1131 : : * been through constant-folding.
1132 : : *----------
1133 : : */
1134 [ + + ]: 50142 : if (op->opno == BooleanEqualOperator)
1135 : : {
1136 : : Node *rightop;
1137 : :
1138 [ - + ]: 4 : Assert(list_length(op->args) == 2);
1139 : 4 : rightop = lsecond(op->args);
1140 : : /* We might never see null Consts here, but better check */
1141 [ + - + - ]: 4 : if (rightop && IsA(rightop, Const) &&
1142 [ + - ]: 4 : !((Const *) rightop)->constisnull)
1143 : : {
1144 : 4 : Node *leftop = linitial(op->args);
1145 : :
1146 [ + + ]: 4 : if (DatumGetBool(((Const *) rightop)->constvalue))
1147 : : {
1148 : : /* X = true implies X */
1149 [ + - ]: 2 : if (equal(predicate, leftop))
1150 : 2 : return true;
1151 : : }
1152 : : else
1153 : : {
1154 : : /* X = false implies NOT X */
1155 [ + - + - ]: 4 : if (is_notclause(predicate) &&
1156 : 2 : equal(get_notclausearg(predicate), leftop))
1157 : 2 : return true;
1158 : : }
1159 : : }
1160 : : }
1161 : : }
1162 : 50138 : break;
1163 : 1746 : default:
1164 : 1746 : break;
1165 : : }
1166 : :
1167 : : /* ... and some predicate-type-specific ones */
1168 [ + + ]: 51884 : switch (nodeTag(predicate))
1169 : : {
1170 : 607 : case T_NullTest:
1171 : : {
1172 : 607 : NullTest *predntest = (NullTest *) predicate;
1173 : :
1174 [ + + - ]: 607 : switch (predntest->nulltesttype)
1175 : : {
1176 : 312 : case IS_NOT_NULL:
1177 : :
1178 : : /*
1179 : : * If the predicate is of the form "foo IS NOT NULL",
1180 : : * and we are considering strong implication, we can
1181 : : * conclude that the predicate is implied if the
1182 : : * clause is strict for "foo", i.e., it must yield
1183 : : * false or NULL when "foo" is NULL. In that case
1184 : : * truth of the clause ensures that "foo" isn't NULL.
1185 : : * (Again, this is a safe conclusion because "foo"
1186 : : * must be immutable.) This doesn't work for weak
1187 : : * implication, though. Also, "row IS NOT NULL" does
1188 : : * not act in the simple way we have in mind.
1189 : : */
1190 [ + + ]: 312 : if (!weak &&
1191 [ + - + + ]: 162 : !predntest->argisrow &&
1192 : 81 : clause_is_strict_for(clause,
1193 : 81 : (Node *) predntest->arg,
1194 : : true))
1195 : 17 : return true;
1196 : 295 : break;
1197 : 295 : case IS_NULL:
1198 : 295 : break;
1199 : : }
1200 : : }
1201 : 590 : break;
1202 : 51277 : default:
1203 : 51277 : break;
1204 : : }
1205 : :
1206 : : /*
1207 : : * Finally, if both clauses are binary operator expressions, we may be
1208 : : * able to prove something using the system's knowledge about operators;
1209 : : * those proof rules are encapsulated in operator_predicate_proof().
1210 : : */
2216 tgl@sss.pgh.pa.us 1211 :CBC 51867 : return operator_predicate_proof(predicate, clause, false, weak);
1212 : : }
1213 : :
1214 : : /*
1215 : : * predicate_refuted_by_simple_clause
1216 : : * Does the predicate refutation test for a "simple clause" predicate
1217 : : * and a "simple clause" restriction.
1218 : : *
1219 : : * We return true if able to prove the refutation, false if not.
1220 : : *
1221 : : * The main motivation for covering IS [NOT] NULL cases is to support using
1222 : : * IS NULL/IS NOT NULL as partition-defining constraints.
1223 : : */
1224 : : static bool
2496 rhaas@postgresql.org 1225 : 70284 : predicate_refuted_by_simple_clause(Expr *predicate, Node *clause,
1226 : : bool weak)
1227 : : {
1228 : : /* Allow interrupting long proof attempts */
5632 tgl@sss.pgh.pa.us 1229 [ - + ]: 70284 : CHECK_FOR_INTERRUPTS();
1230 : :
1231 : : /*
1232 : : * A simple clause can't refute itself, so unlike the implication case,
1233 : : * checking for equal() clauses isn't helpful.
1234 : : *
1235 : : * But relation_excluded_by_constraints() checks for self-contradictions
1236 : : * in a list of clauses, so that we may get here with predicate and clause
1237 : : * being actually pointer-equal, and that is worth eliminating quickly.
1238 : : */
6462 1239 [ + + ]: 70284 : if ((Node *) predicate == clause)
1240 : 22292 : return false;
1241 : :
1242 : : /* Next we have some clause-type-specific strategies */
20 tgl@sss.pgh.pa.us 1243 [ + + ]:GNC 47992 : switch (nodeTag(clause))
1244 : : {
1245 : 3578 : case T_NullTest:
1246 : : {
1247 : 3578 : NullTest *clausentest = (NullTest *) clause;
1248 : :
1249 : : /* row IS NULL does not act in the simple way we have in mind */
1250 [ - + ]: 3578 : if (clausentest->argisrow)
20 tgl@sss.pgh.pa.us 1251 :UNC 0 : return false;
1252 : :
20 tgl@sss.pgh.pa.us 1253 [ + + - ]:GNC 3578 : switch (clausentest->nulltesttype)
1254 : : {
1255 : 2115 : case IS_NULL:
1256 : : {
1257 [ + + ]: 2115 : switch (nodeTag(predicate))
1258 : : {
1259 : 629 : case T_NullTest:
1260 : : {
1261 : 629 : NullTest *predntest = (NullTest *) predicate;
1262 : :
1263 : : /*
1264 : : * row IS NULL does not act in the
1265 : : * simple way we have in mind
1266 : : */
1267 [ - + ]: 629 : if (predntest->argisrow)
20 tgl@sss.pgh.pa.us 1268 :UNC 0 : return false;
1269 : :
1270 : : /*
1271 : : * foo IS NULL refutes foo IS NOT
1272 : : * NULL, at least in the non-row case,
1273 : : * for both strong and weak refutation
1274 : : */
20 tgl@sss.pgh.pa.us 1275 [ + + + + ]:GNC 646 : if (predntest->nulltesttype == IS_NOT_NULL &&
1276 : 17 : equal(predntest->arg, clausentest->arg))
1277 : 2 : return true;
1278 : : }
1279 : 627 : break;
1280 : 1486 : default:
1281 : 1486 : break;
1282 : : }
1283 : :
1284 : : /*
1285 : : * foo IS NULL weakly refutes any predicate that
1286 : : * is strict for foo, since then the predicate
1287 : : * must yield false or NULL (and since foo appears
1288 : : * in the predicate, it's known immutable).
1289 : : */
1290 [ + + + + ]: 3390 : if (weak &&
1291 : 1277 : clause_is_strict_for((Node *) predicate,
1292 : 1277 : (Node *) clausentest->arg,
1293 : : true))
1294 : 16 : return true;
1295 : :
1296 : 2097 : return false; /* we can't succeed below... */
1297 : : }
1298 : : break;
1299 : 1463 : case IS_NOT_NULL:
1300 : 1463 : break;
1301 : : }
1302 : : }
1303 : 1463 : break;
1304 : 44414 : default:
1305 : 44414 : break;
1306 : : }
1307 : :
1308 : : /* ... and some predicate-type-specific ones */
1309 [ + + ]: 45877 : switch (nodeTag(predicate))
1310 : : {
1311 : 12222 : case T_NullTest:
1312 : : {
1313 : 12222 : NullTest *predntest = (NullTest *) predicate;
1314 : :
1315 : : /* row IS NULL does not act in the simple way we have in mind */
1316 [ - + ]: 12222 : if (predntest->argisrow)
20 tgl@sss.pgh.pa.us 1317 :UNC 0 : return false;
1318 : :
20 tgl@sss.pgh.pa.us 1319 [ + + - ]:GNC 12222 : switch (predntest->nulltesttype)
1320 : : {
1321 : 1508 : case IS_NULL:
1322 : : {
1323 [ + + ]: 1508 : switch (nodeTag(clause))
1324 : : {
1325 : 8 : case T_NullTest:
1326 : : {
1327 : 8 : NullTest *clausentest = (NullTest *) clause;
1328 : :
1329 : : /*
1330 : : * row IS NULL does not act in the
1331 : : * simple way we have in mind
1332 : : */
1333 [ - + ]: 8 : if (clausentest->argisrow)
20 tgl@sss.pgh.pa.us 1334 :UNC 0 : return false;
1335 : :
1336 : : /*
1337 : : * foo IS NOT NULL refutes foo IS NULL
1338 : : * for both strong and weak refutation
1339 : : */
20 tgl@sss.pgh.pa.us 1340 [ + - + - ]:GNC 16 : if (clausentest->nulltesttype == IS_NOT_NULL &&
1341 : 8 : equal(clausentest->arg, predntest->arg))
1342 : 8 : return true;
1343 : : }
20 tgl@sss.pgh.pa.us 1344 :UNC 0 : break;
20 tgl@sss.pgh.pa.us 1345 :GNC 1500 : default:
1346 : 1500 : break;
1347 : : }
1348 : :
1349 : : /*
1350 : : * When the predicate is of the form "foo IS
1351 : : * NULL", we can conclude that the predicate is
1352 : : * refuted if the clause is strict for "foo" (see
1353 : : * notes for implication case). That works for
1354 : : * either strong or weak refutation.
1355 : : */
1356 [ + + ]: 1500 : if (clause_is_strict_for(clause,
1357 : 1500 : (Node *) predntest->arg,
1358 : : true))
1359 : 822 : return true;
1360 : : }
1361 : 678 : break;
1362 : 10714 : case IS_NOT_NULL:
1363 : 10714 : break;
1364 : : }
1365 : :
1366 : 11392 : return false; /* we can't succeed below... */
1367 : : }
1368 : : break;
1369 : 33655 : default:
1370 : 33655 : break;
1371 : : }
1372 : :
1373 : : /*
1374 : : * Finally, if both clauses are binary operator expressions, we may be
1375 : : * able to prove something using the system's knowledge about operators.
1376 : : */
2216 tgl@sss.pgh.pa.us 1377 :CBC 33655 : return operator_predicate_proof(predicate, clause, true, weak);
1378 : : }
1379 : :
1380 : :
1381 : : /*
1382 : : * If clause asserts the non-truth of a subclause, return that subclause;
1383 : : * otherwise return NULL.
1384 : : */
1385 : : static Node *
6462 1386 : 85883 : extract_not_arg(Node *clause)
1387 : : {
1388 [ - + ]: 85883 : if (clause == NULL)
6462 tgl@sss.pgh.pa.us 1389 :UBC 0 : return NULL;
6462 tgl@sss.pgh.pa.us 1390 [ + + ]:CBC 85883 : if (IsA(clause, BoolExpr))
1391 : : {
1392 : 228 : BoolExpr *bexpr = (BoolExpr *) clause;
1393 : :
1394 [ + - ]: 228 : if (bexpr->boolop == NOT_EXPR)
1395 : 228 : return (Node *) linitial(bexpr->args);
1396 : : }
1397 [ + + ]: 85655 : else if (IsA(clause, BooleanTest))
1398 : : {
1399 : 815 : BooleanTest *btest = (BooleanTest *) clause;
1400 : :
1401 [ + + ]: 815 : if (btest->booltesttype == IS_NOT_TRUE ||
1402 [ + + ]: 430 : btest->booltesttype == IS_FALSE ||
1403 [ + + ]: 428 : btest->booltesttype == IS_UNKNOWN)
1404 : 413 : return (Node *) btest->arg;
1405 : : }
1406 : 85242 : return NULL;
1407 : : }
1408 : :
1409 : : /*
1410 : : * If clause asserts the falsity of a subclause, return that subclause;
1411 : : * otherwise return NULL.
1412 : : */
1413 : : static Node *
5162 1414 : 85075 : extract_strong_not_arg(Node *clause)
1415 : : {
1416 [ - + ]: 85075 : if (clause == NULL)
5162 tgl@sss.pgh.pa.us 1417 :UBC 0 : return NULL;
5162 tgl@sss.pgh.pa.us 1418 [ + + ]:CBC 85075 : if (IsA(clause, BoolExpr))
1419 : : {
1420 : 200 : BoolExpr *bexpr = (BoolExpr *) clause;
1421 : :
1422 [ + - ]: 200 : if (bexpr->boolop == NOT_EXPR)
1423 : 200 : return (Node *) linitial(bexpr->args);
1424 : : }
1425 [ + + ]: 84875 : else if (IsA(clause, BooleanTest))
1426 : : {
1427 : 778 : BooleanTest *btest = (BooleanTest *) clause;
1428 : :
1429 [ + + ]: 778 : if (btest->booltesttype == IS_FALSE)
1430 : 6 : return (Node *) btest->arg;
1431 : : }
1432 : 84869 : return NULL;
1433 : : }
1434 : :
1435 : :
1436 : : /*
1437 : : * Can we prove that "clause" returns NULL (or FALSE) if "subexpr" is
1438 : : * assumed to yield NULL?
1439 : : *
1440 : : * In most places in the planner, "strictness" refers to a guarantee that
1441 : : * an expression yields NULL output for a NULL input, and that's mostly what
1442 : : * we're looking for here. However, at top level where the clause is known
1443 : : * to yield boolean, it may be sufficient to prove that it cannot return TRUE
1444 : : * when "subexpr" is NULL. The caller should pass allow_false = true when
1445 : : * this weaker property is acceptable. (When this function recurses
1446 : : * internally, we pass down allow_false = false since we need to prove actual
1447 : : * nullness of the subexpression.)
1448 : : *
1449 : : * We assume that the caller checked that least one of the input expressions
1450 : : * is immutable. All of the proof rules here involve matching "subexpr" to
1451 : : * some portion of "clause", so that this allows assuming that "subexpr" is
1452 : : * immutable without a separate check.
1453 : : *
1454 : : * The base case is that clause and subexpr are equal().
1455 : : *
1456 : : * We can also report success if the subexpr appears as a subexpression
1457 : : * of "clause" in a place where it'd force nullness of the overall result.
1458 : : */
1459 : : static bool
1871 1460 : 6538 : clause_is_strict_for(Node *clause, Node *subexpr, bool allow_false)
1461 : : {
1462 : : ListCell *lc;
1463 : :
1464 : : /* safety checks */
2228 1465 [ + - - + ]: 6538 : if (clause == NULL || subexpr == NULL)
2228 tgl@sss.pgh.pa.us 1466 :UBC 0 : return false;
1467 : :
1468 : : /*
1469 : : * Look through any RelabelType nodes, so that we can match, say,
1470 : : * varcharcol with lower(varcharcol::text). (In general we could recurse
1471 : : * through any nullness-preserving, immutable operation.) We should not
1472 : : * see stacked RelabelTypes here.
1473 : : */
2228 tgl@sss.pgh.pa.us 1474 [ + + ]:CBC 6538 : if (IsA(clause, RelabelType))
1475 : 13 : clause = (Node *) ((RelabelType *) clause)->arg;
1476 [ - + ]: 6538 : if (IsA(subexpr, RelabelType))
2228 tgl@sss.pgh.pa.us 1477 :UBC 0 : subexpr = (Node *) ((RelabelType *) subexpr)->arg;
1478 : :
1479 : : /* Base case */
2228 tgl@sss.pgh.pa.us 1480 [ + + ]:CBC 6538 : if (equal(clause, subexpr))
1481 : 865 : return true;
1482 : :
1483 : : /*
1484 : : * If we have a strict operator or function, a NULL result is guaranteed
1485 : : * if any input is forced NULL by subexpr. This is OK even if the op or
1486 : : * func isn't immutable, since it won't even be called on NULL input.
1487 : : */
1488 [ + + + - ]: 7897 : if (is_opclause(clause) &&
1489 : 2224 : op_strict(((OpExpr *) clause)->opno))
1490 : : {
1491 [ + - + + : 5011 : foreach(lc, ((OpExpr *) clause)->args)
+ + ]
1492 : : {
1871 1493 [ + + ]: 3619 : if (clause_is_strict_for((Node *) lfirst(lc), subexpr, false))
2228 1494 : 832 : return true;
1495 : : }
1496 : 1392 : return false;
1497 : : }
1498 [ + + + - ]: 3474 : if (is_funcclause(clause) &&
1499 : 25 : func_strict(((FuncExpr *) clause)->funcid))
1500 : : {
1501 [ + - + + : 41 : foreach(lc, ((FuncExpr *) clause)->args)
+ + ]
1502 : : {
1871 1503 [ + + ]: 28 : if (clause_is_strict_for((Node *) lfirst(lc), subexpr, false))
2228 1504 : 12 : return true;
1505 : : }
1506 : 13 : return false;
1507 : : }
1508 : :
1509 : : /*
1510 : : * CoerceViaIO is strict (whether or not the I/O functions it calls are).
1511 : : * Likewise, ArrayCoerceExpr is strict for its array argument (regardless
1512 : : * of what the per-element expression is), ConvertRowtypeExpr is strict at
1513 : : * the row level, and CoerceToDomain is strict too. These are worth
1514 : : * checking mainly because it saves us having to explain to users why some
1515 : : * type coercions are known strict and others aren't.
1516 : : */
1880 1517 [ - + ]: 3424 : if (IsA(clause, CoerceViaIO))
1880 tgl@sss.pgh.pa.us 1518 :UBC 0 : return clause_is_strict_for((Node *) ((CoerceViaIO *) clause)->arg,
1519 : : subexpr, false);
1880 tgl@sss.pgh.pa.us 1520 [ - + ]:CBC 3424 : if (IsA(clause, ArrayCoerceExpr))
1880 tgl@sss.pgh.pa.us 1521 :UBC 0 : return clause_is_strict_for((Node *) ((ArrayCoerceExpr *) clause)->arg,
1522 : : subexpr, false);
1880 tgl@sss.pgh.pa.us 1523 [ - + ]:CBC 3424 : if (IsA(clause, ConvertRowtypeExpr))
1880 tgl@sss.pgh.pa.us 1524 :UBC 0 : return clause_is_strict_for((Node *) ((ConvertRowtypeExpr *) clause)->arg,
1525 : : subexpr, false);
1880 tgl@sss.pgh.pa.us 1526 [ - + ]:CBC 3424 : if (IsA(clause, CoerceToDomain))
1880 tgl@sss.pgh.pa.us 1527 :UBC 0 : return clause_is_strict_for((Node *) ((CoerceToDomain *) clause)->arg,
1528 : : subexpr, false);
1529 : :
1530 : : /*
1531 : : * ScalarArrayOpExpr is a special case. Note that we'd only reach here
1532 : : * with a ScalarArrayOpExpr clause if we failed to deconstruct it into an
1533 : : * AND or OR tree, as for example if it has too many array elements.
1534 : : */
1871 tgl@sss.pgh.pa.us 1535 [ + + ]:CBC 3424 : if (IsA(clause, ScalarArrayOpExpr))
1536 : : {
1537 : 22 : ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
1538 : 22 : Node *scalarnode = (Node *) linitial(saop->args);
1539 : 22 : Node *arraynode = (Node *) lsecond(saop->args);
1540 : :
1541 : : /*
1542 : : * If we can prove the scalar input to be null, and the operator is
1543 : : * strict, then the SAOP result has to be null --- unless the array is
1544 : : * empty. For an empty array, we'd get either false (for ANY) or true
1545 : : * (for ALL). So if allow_false = true then the proof succeeds anyway
1546 : : * for the ANY case; otherwise we can only make the proof if we can
1547 : : * prove the array non-empty.
1548 : : */
1549 [ + + + - ]: 43 : if (clause_is_strict_for(scalarnode, subexpr, false) &&
1550 : 21 : op_strict(saop->opno))
1551 : : {
1552 : 21 : int nelems = 0;
1553 : :
1554 [ + + + + ]: 21 : if (allow_false && saop->useOr)
1555 : 7 : return true; /* can succeed even if array is empty */
1556 : :
1557 [ + - + + ]: 14 : if (arraynode && IsA(arraynode, Const))
1558 : 3 : {
1559 : 3 : Const *arrayconst = (Const *) arraynode;
1560 : : ArrayType *arrval;
1561 : :
1562 : : /*
1563 : : * If array is constant NULL then we can succeed, as in the
1564 : : * case below.
1565 : : */
1566 [ - + ]: 3 : if (arrayconst->constisnull)
1871 tgl@sss.pgh.pa.us 1567 :UBC 0 : return true;
1568 : :
1569 : : /* Otherwise, we can compute the number of elements. */
1871 tgl@sss.pgh.pa.us 1570 :CBC 3 : arrval = DatumGetArrayTypeP(arrayconst->constvalue);
1571 : 3 : nelems = ArrayGetNItems(ARR_NDIM(arrval), ARR_DIMS(arrval));
1572 : : }
1573 [ + - + + ]: 11 : else if (arraynode && IsA(arraynode, ArrayExpr) &&
1574 [ + - ]: 1 : !((ArrayExpr *) arraynode)->multidims)
1575 : : {
1576 : : /*
1577 : : * We can also reliably count the number of array elements if
1578 : : * the input is a non-multidim ARRAY[] expression.
1579 : : */
1580 : 1 : nelems = list_length(((ArrayExpr *) arraynode)->elements);
1581 : : }
1582 : :
1583 : : /* Proof succeeds if array is definitely non-empty */
1584 [ + + ]: 14 : if (nelems > 0)
1585 : 4 : return true;
1586 : : }
1587 : :
1588 : : /*
1589 : : * If we can prove the array input to be null, the proof succeeds in
1590 : : * all cases, since ScalarArrayOpExpr will always return NULL for a
1591 : : * NULL array. Otherwise, we're done here.
1592 : : */
1593 : 11 : return clause_is_strict_for(arraynode, subexpr, false);
1594 : : }
1595 : :
1596 : : /*
1597 : : * When recursing into an expression, we might find a NULL constant.
1598 : : * That's certainly NULL, whether it matches subexpr or not.
1599 : : */
1600 [ + + ]: 3402 : if (IsA(clause, Const))
1601 : 1324 : return ((Const *) clause)->constisnull;
1602 : :
6109 1603 : 2078 : return false;
1604 : : }
1605 : :
1606 : :
1607 : : /*
1608 : : * Define "operator implication tables" for btree operators ("strategies"),
1609 : : * and similar tables for refutation.
1610 : : *
1611 : : * The strategy numbers defined by btree indexes (see access/stratnum.h) are:
1612 : : * 1 < 2 <= 3 = 4 >= 5 >
1613 : : * and in addition we use 6 to represent <>. <> is not a btree-indexable
1614 : : * operator, but we assume here that if an equality operator of a btree
1615 : : * opfamily has a negator operator, the negator behaves as <> for the opfamily.
1616 : : * (This convention is also known to get_op_btree_interpretation().)
1617 : : *
1618 : : * BT_implies_table[] and BT_refutes_table[] are used for cases where we have
1619 : : * two identical subexpressions and we want to know whether one operator
1620 : : * expression implies or refutes the other. That is, if the "clause" is
1621 : : * EXPR1 clause_op EXPR2 and the "predicate" is EXPR1 pred_op EXPR2 for the
1622 : : * same two (immutable) subexpressions:
1623 : : * BT_implies_table[clause_op-1][pred_op-1]
1624 : : * is true if the clause implies the predicate
1625 : : * BT_refutes_table[clause_op-1][pred_op-1]
1626 : : * is true if the clause refutes the predicate
1627 : : * where clause_op and pred_op are strategy numbers (from 1 to 6) in the
1628 : : * same btree opfamily. For example, "x < y" implies "x <= y" and refutes
1629 : : * "x > y".
1630 : : *
1631 : : * BT_implic_table[] and BT_refute_table[] are used where we have two
1632 : : * constants that we need to compare. The interpretation of:
1633 : : *
1634 : : * test_op = BT_implic_table[clause_op-1][pred_op-1]
1635 : : *
1636 : : * where test_op, clause_op and pred_op are strategy numbers (from 1 to 6)
1637 : : * of btree operators, is as follows:
1638 : : *
1639 : : * If you know, for some EXPR, that "EXPR clause_op CONST1" is true, and you
1640 : : * want to determine whether "EXPR pred_op CONST2" must also be true, then
1641 : : * you can use "CONST2 test_op CONST1" as a test. If this test returns true,
1642 : : * then the predicate expression must be true; if the test returns false,
1643 : : * then the predicate expression may be false.
1644 : : *
1645 : : * For example, if clause is "Quantity > 10" and pred is "Quantity > 5"
1646 : : * then we test "5 <= 10" which evals to true, so clause implies pred.
1647 : : *
1648 : : * Similarly, the interpretation of a BT_refute_table entry is:
1649 : : *
1650 : : * If you know, for some EXPR, that "EXPR clause_op CONST1" is true, and you
1651 : : * want to determine whether "EXPR pred_op CONST2" must be false, then
1652 : : * you can use "CONST2 test_op CONST1" as a test. If this test returns true,
1653 : : * then the predicate expression must be false; if the test returns false,
1654 : : * then the predicate expression may be true.
1655 : : *
1656 : : * For example, if clause is "Quantity > 10" and pred is "Quantity < 5"
1657 : : * then we test "5 <= 10" which evals to true, so clause refutes pred.
1658 : : *
1659 : : * An entry where test_op == 0 means the implication cannot be determined.
1660 : : */
1661 : :
1662 : : #define BTLT BTLessStrategyNumber
1663 : : #define BTLE BTLessEqualStrategyNumber
1664 : : #define BTEQ BTEqualStrategyNumber
1665 : : #define BTGE BTGreaterEqualStrategyNumber
1666 : : #define BTGT BTGreaterStrategyNumber
1667 : : #define BTNE ROWCOMPARE_NE
1668 : :
1669 : : /* We use "none" for 0/false to make the tables align nicely */
1670 : : #define none 0
1671 : :
1672 : : static const bool BT_implies_table[6][6] = {
1673 : : /*
1674 : : * The predicate operator:
1675 : : * LT LE EQ GE GT NE
1676 : : */
1677 : : {true, true, none, none, none, true}, /* LT */
1678 : : {none, true, none, none, none, none}, /* LE */
1679 : : {none, true, true, true, none, none}, /* EQ */
1680 : : {none, none, none, true, none, none}, /* GE */
1681 : : {none, none, none, true, true, true}, /* GT */
1682 : : {none, none, none, none, none, true} /* NE */
1683 : : };
1684 : :
1685 : : static const bool BT_refutes_table[6][6] = {
1686 : : /*
1687 : : * The predicate operator:
1688 : : * LT LE EQ GE GT NE
1689 : : */
1690 : : {none, none, true, true, true, none}, /* LT */
1691 : : {none, none, none, none, true, none}, /* LE */
1692 : : {true, none, none, none, true, true}, /* EQ */
1693 : : {true, none, none, none, none, none}, /* GE */
1694 : : {true, true, true, none, none, none}, /* GT */
1695 : : {none, none, true, none, none, none} /* NE */
1696 : : };
1697 : :
1698 : : static const StrategyNumber BT_implic_table[6][6] = {
1699 : : /*
1700 : : * The predicate operator:
1701 : : * LT LE EQ GE GT NE
1702 : : */
1703 : : {BTGE, BTGE, none, none, none, BTGE}, /* LT */
1704 : : {BTGT, BTGE, none, none, none, BTGT}, /* LE */
1705 : : {BTGT, BTGE, BTEQ, BTLE, BTLT, BTNE}, /* EQ */
1706 : : {none, none, none, BTLE, BTLT, BTLT}, /* GE */
1707 : : {none, none, none, BTLE, BTLE, BTLE}, /* GT */
1708 : : {none, none, none, none, none, BTEQ} /* NE */
1709 : : };
1710 : :
1711 : : static const StrategyNumber BT_refute_table[6][6] = {
1712 : : /*
1713 : : * The predicate operator:
1714 : : * LT LE EQ GE GT NE
1715 : : */
1716 : : {none, none, BTGE, BTGE, BTGE, none}, /* LT */
1717 : : {none, none, BTGT, BTGT, BTGE, none}, /* LE */
1718 : : {BTLE, BTLT, BTNE, BTGT, BTGE, BTEQ}, /* EQ */
1719 : : {BTLE, BTLT, BTLT, none, none, none}, /* GE */
1720 : : {BTLE, BTLE, BTLE, none, none, none}, /* GT */
1721 : : {none, none, BTEQ, none, none, none} /* NE */
1722 : : };
1723 : :
1724 : :
1725 : : /*
1726 : : * operator_predicate_proof
1727 : : * Does the predicate implication or refutation test for a "simple clause"
1728 : : * predicate and a "simple clause" restriction, when both are operator
1729 : : * clauses using related operators and identical input expressions.
1730 : : *
1731 : : * When refute_it == false, we want to prove the predicate true;
1732 : : * when refute_it == true, we want to prove the predicate false.
1733 : : * (There is enough common code to justify handling these two cases
1734 : : * in one routine.) We return true if able to make the proof, false
1735 : : * if not able to prove it.
1736 : : *
1737 : : * We mostly need not distinguish strong vs. weak implication/refutation here.
1738 : : * This depends on the assumption that a pair of related operators (i.e.,
1739 : : * commutators, negators, or btree opfamily siblings) will not return one NULL
1740 : : * and one non-NULL result for the same inputs. Then, for the proof types
1741 : : * where we start with an assumption of truth of the clause, the predicate
1742 : : * operator could not return NULL either, so it doesn't matter whether we are
1743 : : * trying to make a strong or weak proof. For weak implication, it could be
1744 : : * that the clause operator returned NULL, but then the predicate operator
1745 : : * would as well, so that the weak implication still holds. This argument
1746 : : * doesn't apply in the case where we are considering two different constant
1747 : : * values, since then the operators aren't being given identical inputs. But
1748 : : * we only support that for btree operators, for which we can assume that all
1749 : : * non-null inputs result in non-null outputs, so that it doesn't matter which
1750 : : * two non-null constants we consider. If either constant is NULL, we have
1751 : : * to think harder, but sometimes the proof still works, as explained below.
1752 : : *
1753 : : * We can make proofs involving several expression forms (here "foo" and "bar"
1754 : : * represent subexpressions that are identical according to equal()):
1755 : : * "foo op1 bar" refutes "foo op2 bar" if op1 is op2's negator
1756 : : * "foo op1 bar" implies "bar op2 foo" if op1 is op2's commutator
1757 : : * "foo op1 bar" refutes "bar op2 foo" if op1 is negator of op2's commutator
1758 : : * "foo op1 bar" can imply/refute "foo op2 bar" based on btree semantics
1759 : : * "foo op1 bar" can imply/refute "bar op2 foo" based on btree semantics
1760 : : * "foo op1 const1" can imply/refute "foo op2 const2" based on btree semantics
1761 : : *
1762 : : * For the last three cases, op1 and op2 have to be members of the same btree
1763 : : * operator family. When both subexpressions are identical, the idea is that,
1764 : : * for instance, x < y implies x <= y, independently of exactly what x and y
1765 : : * are. If we have two different constants compared to the same expression
1766 : : * foo, we have to execute a comparison between the two constant values
1767 : : * in order to determine the result; for instance, foo < c1 implies foo < c2
1768 : : * if c1 <= c2. We assume it's safe to compare the constants at plan time
1769 : : * if the comparison operator is immutable.
1770 : : *
1771 : : * Note: all the operators and subexpressions have to be immutable for the
1772 : : * proof to be safe. We assume the predicate expression is entirely immutable,
1773 : : * so no explicit check on the subexpressions is needed here, but in some
1774 : : * cases we need an extra check of operator immutability. In particular,
1775 : : * btree opfamilies can contain cross-type operators that are merely stable,
1776 : : * and we dare not make deductions with those.
1777 : : */
1778 : : static bool
2216 1779 : 85522 : operator_predicate_proof(Expr *predicate, Node *clause,
1780 : : bool refute_it, bool weak)
1781 : : {
1782 : : OpExpr *pred_opexpr,
1783 : : *clause_opexpr;
1784 : : Oid pred_collation,
1785 : : clause_collation;
1786 : : Oid pred_op,
1787 : : clause_op,
1788 : : test_op;
1789 : : Node *pred_leftop,
1790 : : *pred_rightop,
1791 : : *clause_leftop,
1792 : : *clause_rightop;
1793 : : Const *pred_const,
1794 : : *clause_const;
1795 : : Expr *test_expr;
1796 : : ExprState *test_exprstate;
1797 : : Datum test_result;
1798 : : bool isNull;
1799 : : EState *estate;
1800 : : MemoryContext oldcontext;
1801 : :
1802 : : /*
1803 : : * Both expressions must be binary opclauses, else we can't do anything.
1804 : : *
1805 : : * Note: in future we might extend this logic to other operator-based
1806 : : * constructs such as DistinctExpr. But the planner isn't very smart
1807 : : * about DistinctExpr in general, and this probably isn't the first place
1808 : : * to fix if you want to improve that.
1809 : : */
6883 1810 [ + + ]: 85522 : if (!is_opclause(predicate))
1811 : 17412 : return false;
3593 1812 : 68110 : pred_opexpr = (OpExpr *) predicate;
1813 [ - + ]: 68110 : if (list_length(pred_opexpr->args) != 2)
6883 tgl@sss.pgh.pa.us 1814 :UBC 0 : return false;
6883 tgl@sss.pgh.pa.us 1815 [ + + ]:CBC 68110 : if (!is_opclause(clause))
1816 : 2918 : return false;
3593 1817 : 65192 : clause_opexpr = (OpExpr *) clause;
1818 [ - + ]: 65192 : if (list_length(clause_opexpr->args) != 2)
6883 tgl@sss.pgh.pa.us 1819 :UBC 0 : return false;
1820 : :
1821 : : /*
1822 : : * If they're marked with different collations then we can't do anything.
1823 : : * This is a cheap test so let's get it out of the way early.
1824 : : */
3593 tgl@sss.pgh.pa.us 1825 :CBC 65192 : pred_collation = pred_opexpr->inputcollid;
1826 : 65192 : clause_collation = clause_opexpr->inputcollid;
4775 1827 [ + + ]: 65192 : if (pred_collation != clause_collation)
1828 : 10040 : return false;
1829 : :
1830 : : /* Grab the operator OIDs now too. We may commute these below. */
3593 1831 : 55152 : pred_op = pred_opexpr->opno;
1832 : 55152 : clause_op = clause_opexpr->opno;
1833 : :
1834 : : /*
1835 : : * We have to match up at least one pair of input expressions.
1836 : : */
1837 : 55152 : pred_leftop = (Node *) linitial(pred_opexpr->args);
1838 : 55152 : pred_rightop = (Node *) lsecond(pred_opexpr->args);
1839 : 55152 : clause_leftop = (Node *) linitial(clause_opexpr->args);
1840 : 55152 : clause_rightop = (Node *) lsecond(clause_opexpr->args);
1841 : :
1842 [ + + ]: 55152 : if (equal(pred_leftop, clause_leftop))
1843 : : {
1844 [ + + ]: 20616 : if (equal(pred_rightop, clause_rightop))
1845 : : {
1846 : : /* We have x op1 y and x op2 y */
1847 : 2312 : return operator_same_subexprs_proof(pred_op, clause_op, refute_it);
1848 : : }
1849 : : else
1850 : : {
1851 : : /* Fail unless rightops are both Consts */
1852 [ + - + + ]: 18304 : if (pred_rightop == NULL || !IsA(pred_rightop, Const))
1853 : 816 : return false;
1854 : 17488 : pred_const = (Const *) pred_rightop;
1855 [ + - + + ]: 17488 : if (clause_rightop == NULL || !IsA(clause_rightop, Const))
1856 : 31 : return false;
1857 : 17457 : clause_const = (Const *) clause_rightop;
1858 : : }
1859 : : }
1860 [ + + ]: 34536 : else if (equal(pred_rightop, clause_rightop))
1861 : : {
1862 : : /* Fail unless leftops are both Consts */
1863 [ + - + + ]: 1575 : if (pred_leftop == NULL || !IsA(pred_leftop, Const))
1864 : 1571 : return false;
1865 : 4 : pred_const = (Const *) pred_leftop;
1866 [ + - - + ]: 4 : if (clause_leftop == NULL || !IsA(clause_leftop, Const))
3593 tgl@sss.pgh.pa.us 1867 :UBC 0 : return false;
3593 tgl@sss.pgh.pa.us 1868 :CBC 4 : clause_const = (Const *) clause_leftop;
1869 : : /* Commute both operators so we can assume Consts are on the right */
6883 1870 : 4 : pred_op = get_commutator(pred_op);
1871 [ - + ]: 4 : if (!OidIsValid(pred_op))
6883 tgl@sss.pgh.pa.us 1872 :UBC 0 : return false;
6883 tgl@sss.pgh.pa.us 1873 :CBC 4 : clause_op = get_commutator(clause_op);
1874 [ - + ]: 4 : if (!OidIsValid(clause_op))
6883 tgl@sss.pgh.pa.us 1875 :UBC 0 : return false;
1876 : : }
3593 tgl@sss.pgh.pa.us 1877 [ + + ]:CBC 32961 : else if (equal(pred_leftop, clause_rightop))
1878 : : {
1879 [ + + ]: 362 : if (equal(pred_rightop, clause_leftop))
1880 : : {
1881 : : /* We have x op1 y and y op2 x */
1882 : : /* Commute pred_op that we can treat this like a straight match */
1883 : 310 : pred_op = get_commutator(pred_op);
1884 [ - + ]: 310 : if (!OidIsValid(pred_op))
3593 tgl@sss.pgh.pa.us 1885 :UBC 0 : return false;
3593 tgl@sss.pgh.pa.us 1886 :CBC 310 : return operator_same_subexprs_proof(pred_op, clause_op, refute_it);
1887 : : }
1888 : : else
1889 : : {
1890 : : /* Fail unless pred_rightop/clause_leftop are both Consts */
1891 [ + - + + ]: 52 : if (pred_rightop == NULL || !IsA(pred_rightop, Const))
1892 : 48 : return false;
1893 : 4 : pred_const = (Const *) pred_rightop;
1894 [ + - - + ]: 4 : if (clause_leftop == NULL || !IsA(clause_leftop, Const))
3593 tgl@sss.pgh.pa.us 1895 :UBC 0 : return false;
3593 tgl@sss.pgh.pa.us 1896 :CBC 4 : clause_const = (Const *) clause_leftop;
1897 : : /* Commute clause_op so we can assume Consts are on the right */
1898 : 4 : clause_op = get_commutator(clause_op);
1899 [ - + ]: 4 : if (!OidIsValid(clause_op))
3593 tgl@sss.pgh.pa.us 1900 :UBC 0 : return false;
1901 : : }
1902 : : }
3593 tgl@sss.pgh.pa.us 1903 [ + + ]:CBC 32599 : else if (equal(pred_rightop, clause_leftop))
1904 : : {
1905 : : /* Fail unless pred_leftop/clause_rightop are both Consts */
1906 [ + - + + ]: 73 : if (pred_leftop == NULL || !IsA(pred_leftop, Const))
1907 : 53 : return false;
1908 : 20 : pred_const = (Const *) pred_leftop;
1909 [ + - - + ]: 20 : if (clause_rightop == NULL || !IsA(clause_rightop, Const))
3593 tgl@sss.pgh.pa.us 1910 :UBC 0 : return false;
3593 tgl@sss.pgh.pa.us 1911 :CBC 20 : clause_const = (Const *) clause_rightop;
1912 : : /* Commute pred_op so we can assume Consts are on the right */
1913 : 20 : pred_op = get_commutator(pred_op);
1914 [ - + ]: 20 : if (!OidIsValid(pred_op))
3593 tgl@sss.pgh.pa.us 1915 :UBC 0 : return false;
1916 : : }
1917 : : else
1918 : : {
1919 : : /* Failed to match up any of the subexpressions, so we lose */
3593 tgl@sss.pgh.pa.us 1920 :CBC 32526 : return false;
1921 : : }
1922 : :
1923 : : /*
1924 : : * We have two identical subexpressions, and two other subexpressions that
1925 : : * are not identical but are both Consts; and we have commuted the
1926 : : * operators if necessary so that the Consts are on the right. We'll need
1927 : : * to compare the Consts' values. If either is NULL, we can't do that, so
1928 : : * usually the proof fails ... but in some cases we can claim success.
1929 : : */
1930 [ + + ]: 17485 : if (clause_const->constisnull)
1931 : : {
1932 : : /* If clause_op isn't strict, we can't prove anything */
2216 1933 [ - + ]: 2 : if (!op_strict(clause_op))
2216 tgl@sss.pgh.pa.us 1934 :UBC 0 : return false;
1935 : :
1936 : : /*
1937 : : * At this point we know that the clause returns NULL. For proof
1938 : : * types that assume truth of the clause, this means the proof is
1939 : : * vacuously true (a/k/a "false implies anything"). That's all proof
1940 : : * types except weak implication.
1941 : : */
2216 tgl@sss.pgh.pa.us 1942 [ + + - + ]:CBC 2 : if (!(weak && !refute_it))
1943 : 1 : return true;
1944 : :
1945 : : /*
1946 : : * For weak implication, it's still possible for the proof to succeed,
1947 : : * if the predicate can also be proven NULL. In that case we've got
1948 : : * NULL => NULL which is valid for this proof type.
1949 : : */
1950 [ - + - - ]: 1 : if (pred_const->constisnull && op_strict(pred_op))
2216 tgl@sss.pgh.pa.us 1951 :UBC 0 : return true;
1952 : : /* Else the proof fails */
2216 tgl@sss.pgh.pa.us 1953 :CBC 1 : return false;
1954 : : }
1955 [ + + ]: 17483 : if (pred_const->constisnull)
1956 : : {
1957 : : /*
1958 : : * If the pred_op is strict, we know the predicate yields NULL, which
1959 : : * means the proof succeeds for either weak implication or weak
1960 : : * refutation.
1961 : : */
1962 [ + + + - ]: 10 : if (weak && op_strict(pred_op))
1963 : 6 : return true;
1964 : : /* Else the proof fails */
3593 1965 : 4 : return false;
1966 : : }
1967 : :
1968 : : /*
1969 : : * Lookup the constant-comparison operator using the system catalogs and
1970 : : * the operator implication tables.
1971 : : */
5631 1972 : 17473 : test_op = get_btree_test_op(pred_op, clause_op, refute_it);
1973 : :
1974 [ + + ]: 17473 : if (!OidIsValid(test_op))
1975 : : {
1976 : : /* couldn't find a suitable comparison operator */
1977 : 8000 : return false;
1978 : : }
1979 : :
1980 : : /*
1981 : : * Evaluate the test. For this we need an EState.
1982 : : */
1983 : 9473 : estate = CreateExecutorState();
1984 : :
1985 : : /* We can use the estate's working context to avoid memory leaks. */
1986 : 9473 : oldcontext = MemoryContextSwitchTo(estate->es_query_cxt);
1987 : :
1988 : : /* Build expression tree */
1989 : 9473 : test_expr = make_opclause(test_op,
1990 : : BOOLOID,
1991 : : false,
1992 : : (Expr *) pred_const,
1993 : : (Expr *) clause_const,
1994 : : InvalidOid,
1995 : : pred_collation);
1996 : :
1997 : : /* Fill in opfuncids */
5574 1998 : 9473 : fix_opfuncids((Node *) test_expr);
1999 : :
2000 : : /* Prepare it for execution */
2001 : 9473 : test_exprstate = ExecInitExpr(test_expr, NULL);
2002 : :
2003 : : /* And execute it. */
5631 tgl@sss.pgh.pa.us 2004 :UBC 0 : test_result = ExecEvalExprSwitchContext(test_exprstate,
5631 tgl@sss.pgh.pa.us 2005 [ - + ]:CBC 9473 : GetPerTupleExprContext(estate),
2006 : : &isNull);
2007 : :
2008 : : /* Get back to outer memory context */
2009 : 9473 : MemoryContextSwitchTo(oldcontext);
2010 : :
2011 : : /* Release all the junk we just created */
2012 : 9473 : FreeExecutorState(estate);
2013 : :
2014 [ - + ]: 9473 : if (isNull)
2015 : : {
2016 : : /* Treat a null result as non-proof ... but it's a tad fishy ... */
5631 tgl@sss.pgh.pa.us 2017 [ # # ]:UBC 0 : elog(DEBUG2, "null predicate test result");
2018 : 0 : return false;
2019 : : }
5631 tgl@sss.pgh.pa.us 2020 :CBC 9473 : return DatumGetBool(test_result);
2021 : : }
2022 : :
2023 : :
2024 : : /*
2025 : : * operator_same_subexprs_proof
2026 : : * Assuming that EXPR1 clause_op EXPR2 is true, try to prove or refute
2027 : : * EXPR1 pred_op EXPR2.
2028 : : *
2029 : : * Return true if able to make the proof, false if not able to prove it.
2030 : : */
2031 : : static bool
3593 2032 : 2622 : operator_same_subexprs_proof(Oid pred_op, Oid clause_op, bool refute_it)
2033 : : {
2034 : : /*
2035 : : * A simple and general rule is that the predicate is proven if clause_op
2036 : : * and pred_op are the same, or refuted if they are each other's negators.
2037 : : * We need not check immutability since the pred_op is already known
2038 : : * immutable. (Actually, by this point we may have the commutator of a
2039 : : * known-immutable pred_op, but that should certainly be immutable too.
2040 : : * Likewise we don't worry whether the pred_op's negator is immutable.)
2041 : : *
2042 : : * Note: the "same" case won't get here if we actually had EXPR1 clause_op
2043 : : * EXPR2 and EXPR1 pred_op EXPR2, because the overall-expression-equality
2044 : : * test in predicate_implied_by_simple_clause would have caught it. But
2045 : : * we can see the same operator after having commuted the pred_op.
2046 : : */
2047 [ + + ]: 2622 : if (refute_it)
2048 : : {
2049 [ + + ]: 2239 : if (get_negator(pred_op) == clause_op)
2050 : 923 : return true;
2051 : : }
2052 : : else
2053 : : {
2054 [ + + ]: 383 : if (pred_op == clause_op)
2055 : 292 : return true;
2056 : : }
2057 : :
2058 : : /*
2059 : : * Otherwise, see if we can determine the implication by finding the
2060 : : * operators' relationship via some btree opfamily.
2061 : : */
2062 : 1407 : return operator_same_subexprs_lookup(pred_op, clause_op, refute_it);
2063 : : }
2064 : :
2065 : :
2066 : : /*
2067 : : * We use a lookaside table to cache the result of btree proof operator
2068 : : * lookups, since the actual lookup is pretty expensive and doesn't change
2069 : : * for any given pair of operators (at least as long as pg_amop doesn't
2070 : : * change). A single hash entry stores both implication and refutation
2071 : : * results for a given pair of operators; but note we may have determined
2072 : : * only one of those sets of results as yet.
2073 : : */
2074 : : typedef struct OprProofCacheKey
2075 : : {
2076 : : Oid pred_op; /* predicate operator */
2077 : : Oid clause_op; /* clause operator */
2078 : : } OprProofCacheKey;
2079 : :
2080 : : typedef struct OprProofCacheEntry
2081 : : {
2082 : : /* the hash lookup key MUST BE FIRST */
2083 : : OprProofCacheKey key;
2084 : :
2085 : : bool have_implic; /* do we know the implication result? */
2086 : : bool have_refute; /* do we know the refutation result? */
2087 : : bool same_subexprs_implies; /* X clause_op Y implies X pred_op Y? */
2088 : : bool same_subexprs_refutes; /* X clause_op Y refutes X pred_op Y? */
2089 : : Oid implic_test_op; /* OID of the test operator, or 0 if none */
2090 : : Oid refute_test_op; /* OID of the test operator, or 0 if none */
2091 : : } OprProofCacheEntry;
2092 : :
2093 : : static HTAB *OprProofCacheHash = NULL;
2094 : :
2095 : :
2096 : : /*
2097 : : * lookup_proof_cache
2098 : : * Get, and fill in if necessary, the appropriate cache entry.
2099 : : */
2100 : : static OprProofCacheEntry *
2101 : 18880 : lookup_proof_cache(Oid pred_op, Oid clause_op, bool refute_it)
2102 : : {
2103 : : OprProofCacheKey key;
2104 : : OprProofCacheEntry *cache_entry;
2105 : : bool cfound;
2106 : 18880 : bool same_subexprs = false;
4666 2107 : 18880 : Oid test_op = InvalidOid;
5631 2108 : 18880 : bool found = false;
2109 : : List *pred_op_infos,
2110 : : *clause_op_infos;
2111 : : ListCell *lcp,
2112 : : *lcc;
2113 : :
2114 : : /*
2115 : : * Find or make a cache entry for this pair of operators.
2116 : : */
2117 [ + + ]: 18880 : if (OprProofCacheHash == NULL)
2118 : : {
2119 : : /* First time through: initialize the hash table */
2120 : : HASHCTL ctl;
2121 : :
2122 : 167 : ctl.keysize = sizeof(OprProofCacheKey);
2123 : 167 : ctl.entrysize = sizeof(OprProofCacheEntry);
2124 : 167 : OprProofCacheHash = hash_create("Btree proof lookup cache", 256,
2125 : : &ctl, HASH_ELEM | HASH_BLOBS);
2126 : :
2127 : : /* Arrange to flush cache on pg_amop changes */
2128 : 167 : CacheRegisterSyscacheCallback(AMOPOPID,
2129 : : InvalidateOprProofCacheCallBack,
2130 : : (Datum) 0);
2131 : : }
2132 : :
2133 : 18880 : key.pred_op = pred_op;
2134 : 18880 : key.clause_op = clause_op;
2135 : 18880 : cache_entry = (OprProofCacheEntry *) hash_search(OprProofCacheHash,
2136 : : &key,
2137 : : HASH_ENTER, &cfound);
2138 [ + + ]: 18880 : if (!cfound)
2139 : : {
2140 : : /* new cache entry, set it invalid */
2141 : 594 : cache_entry->have_implic = false;
2142 : 594 : cache_entry->have_refute = false;
2143 : : }
2144 : : else
2145 : : {
2146 : : /* pre-existing cache entry, see if we know the answer yet */
3593 2147 [ + + + + ]: 18286 : if (refute_it ? cache_entry->have_refute : cache_entry->have_implic)
2148 : 18247 : return cache_entry;
2149 : : }
2150 : :
2151 : : /*
2152 : : * Try to find a btree opfamily containing the given operators.
2153 : : *
2154 : : * We must find a btree opfamily that contains both operators, else the
2155 : : * implication can't be determined. Also, the opfamily must contain a
2156 : : * suitable test operator taking the operators' righthand datatypes.
2157 : : *
2158 : : * If there are multiple matching opfamilies, assume we can use any one to
2159 : : * determine the logical relationship of the two operators and the correct
2160 : : * corresponding test operator. This should work for any logically
2161 : : * consistent opfamilies.
2162 : : *
2163 : : * Note that we can determine the operators' relationship for
2164 : : * same-subexprs cases even from an opfamily that lacks a usable test
2165 : : * operator. This can happen in cases with incomplete sets of cross-type
2166 : : * comparison operators.
2167 : : */
4666 2168 : 633 : clause_op_infos = get_op_btree_interpretation(clause_op);
2169 [ + + ]: 633 : if (clause_op_infos)
2170 : 627 : pred_op_infos = get_op_btree_interpretation(pred_op);
2171 : : else /* no point in looking */
2172 : 6 : pred_op_infos = NIL;
2173 : :
2174 [ + + + + : 742 : foreach(lcp, pred_op_infos)
+ + ]
2175 : : {
2176 : 421 : OpBtreeInterpretation *pred_op_info = lfirst(lcp);
2177 : 421 : Oid opfamily_id = pred_op_info->opfamily_id;
2178 : :
2179 [ + - + + : 542 : foreach(lcc, clause_op_infos)
+ + ]
2180 : : {
2181 : 433 : OpBtreeInterpretation *clause_op_info = lfirst(lcc);
2182 : : StrategyNumber pred_strategy,
2183 : : clause_strategy,
2184 : : test_strategy;
2185 : :
2186 : : /* Must find them in same opfamily */
2187 [ + + ]: 433 : if (opfamily_id != clause_op_info->opfamily_id)
2188 : 12 : continue;
2189 : : /* Lefttypes should match */
2190 [ - + ]: 421 : Assert(clause_op_info->oplefttype == pred_op_info->oplefttype);
2191 : :
2192 : 421 : pred_strategy = pred_op_info->strategy;
2193 : 421 : clause_strategy = clause_op_info->strategy;
2194 : :
2195 : : /*
2196 : : * Check to see if we can make a proof for same-subexpressions
2197 : : * cases based on the operators' relationship in this opfamily.
2198 : : */
3593 2199 [ + + ]: 421 : if (refute_it)
2200 : 254 : same_subexprs |= BT_refutes_table[clause_strategy - 1][pred_strategy - 1];
2201 : : else
2202 : 167 : same_subexprs |= BT_implies_table[clause_strategy - 1][pred_strategy - 1];
2203 : :
2204 : : /*
2205 : : * Look up the "test" strategy number in the implication table
2206 : : */
4666 2207 [ + + ]: 421 : if (refute_it)
2208 : 254 : test_strategy = BT_refute_table[clause_strategy - 1][pred_strategy - 1];
2209 : : else
2210 : 167 : test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1];
2211 : :
2212 [ + + ]: 421 : if (test_strategy == 0)
2213 : : {
2214 : : /* Can't determine implication using this interpretation */
6883 2215 : 109 : continue;
2216 : : }
2217 : :
2218 : : /*
2219 : : * See if opfamily has an operator for the test strategy and the
2220 : : * datatypes.
2221 : : */
4666 2222 [ + + ]: 312 : if (test_strategy == BTNE)
2223 : : {
2224 : 54 : test_op = get_opfamily_member(opfamily_id,
2225 : : pred_op_info->oprighttype,
2226 : : clause_op_info->oprighttype,
2227 : : BTEqualStrategyNumber);
2228 [ + - ]: 54 : if (OidIsValid(test_op))
2229 : 54 : test_op = get_negator(test_op);
2230 : : }
2231 : : else
2232 : : {
2233 : 258 : test_op = get_opfamily_member(opfamily_id,
2234 : : pred_op_info->oprighttype,
2235 : : clause_op_info->oprighttype,
2236 : : test_strategy);
2237 : : }
2238 : :
2239 [ - + ]: 312 : if (!OidIsValid(test_op))
4666 tgl@sss.pgh.pa.us 2240 :UBC 0 : continue;
2241 : :
2242 : : /*
2243 : : * Last check: test_op must be immutable.
2244 : : *
2245 : : * Note that we require only the test_op to be immutable, not the
2246 : : * original clause_op. (pred_op is assumed to have been checked
2247 : : * immutable by the caller.) Essentially we are assuming that the
2248 : : * opfamily is consistent even if it contains operators that are
2249 : : * merely stable.
2250 : : */
6883 tgl@sss.pgh.pa.us 2251 [ + - ]:CBC 312 : if (op_volatile(test_op) == PROVOLATILE_IMMUTABLE)
2252 : : {
2253 : 312 : found = true;
2254 : 312 : break;
2255 : : }
2256 : : }
2257 : :
4666 2258 [ + + ]: 421 : if (found)
2259 : 312 : break;
2260 : : }
2261 : :
2262 : 633 : list_free_deep(pred_op_infos);
2263 : 633 : list_free_deep(clause_op_infos);
2264 : :
6883 2265 [ + + ]: 633 : if (!found)
2266 : : {
2267 : : /* couldn't find a suitable comparison operator */
5631 2268 : 321 : test_op = InvalidOid;
2269 : : }
2270 : :
2271 : : /*
2272 : : * If we think we were able to prove something about same-subexpressions
2273 : : * cases, check to make sure the clause_op is immutable before believing
2274 : : * it completely. (Usually, the clause_op would be immutable if the
2275 : : * pred_op is, but it's not entirely clear that this must be true in all
2276 : : * cases, so let's check.)
2277 : : */
3593 2278 [ + + - + ]: 808 : if (same_subexprs &&
2279 : 175 : op_volatile(clause_op) != PROVOLATILE_IMMUTABLE)
3593 tgl@sss.pgh.pa.us 2280 :UBC 0 : same_subexprs = false;
2281 : :
2282 : : /* Cache the results, whether positive or negative */
5631 tgl@sss.pgh.pa.us 2283 [ + + ]:CBC 633 : if (refute_it)
2284 : : {
2285 : 254 : cache_entry->refute_test_op = test_op;
3593 2286 : 254 : cache_entry->same_subexprs_refutes = same_subexprs;
5631 2287 : 254 : cache_entry->have_refute = true;
2288 : : }
2289 : : else
2290 : : {
2291 : 379 : cache_entry->implic_test_op = test_op;
3593 2292 : 379 : cache_entry->same_subexprs_implies = same_subexprs;
5631 2293 : 379 : cache_entry->have_implic = true;
2294 : : }
2295 : :
3593 2296 : 633 : return cache_entry;
2297 : : }
2298 : :
2299 : : /*
2300 : : * operator_same_subexprs_lookup
2301 : : * Convenience subroutine to look up the cached answer for
2302 : : * same-subexpressions cases.
2303 : : */
2304 : : static bool
2305 : 1407 : operator_same_subexprs_lookup(Oid pred_op, Oid clause_op, bool refute_it)
2306 : : {
2307 : : OprProofCacheEntry *cache_entry;
2308 : :
2309 : 1407 : cache_entry = lookup_proof_cache(pred_op, clause_op, refute_it);
2310 [ + + ]: 1407 : if (refute_it)
2311 : 1316 : return cache_entry->same_subexprs_refutes;
2312 : : else
2313 : 91 : return cache_entry->same_subexprs_implies;
2314 : : }
2315 : :
2316 : : /*
2317 : : * get_btree_test_op
2318 : : * Identify the comparison operator needed for a btree-operator
2319 : : * proof or refutation involving comparison of constants.
2320 : : *
2321 : : * Given the truth of a clause "var clause_op const1", we are attempting to
2322 : : * prove or refute a predicate "var pred_op const2". The identities of the
2323 : : * two operators are sufficient to determine the operator (if any) to compare
2324 : : * const2 to const1 with.
2325 : : *
2326 : : * Returns the OID of the operator to use, or InvalidOid if no proof is
2327 : : * possible.
2328 : : */
2329 : : static Oid
2330 : 17473 : get_btree_test_op(Oid pred_op, Oid clause_op, bool refute_it)
2331 : : {
2332 : : OprProofCacheEntry *cache_entry;
2333 : :
2334 : 17473 : cache_entry = lookup_proof_cache(pred_op, clause_op, refute_it);
2335 [ + + ]: 17473 : if (refute_it)
2336 : 15871 : return cache_entry->refute_test_op;
2337 : : else
2338 : 1602 : return cache_entry->implic_test_op;
2339 : : }
2340 : :
2341 : :
2342 : : /*
2343 : : * Callback for pg_amop inval events
2344 : : */
2345 : : static void
4625 2346 : 270 : InvalidateOprProofCacheCallBack(Datum arg, int cacheid, uint32 hashvalue)
2347 : : {
2348 : : HASH_SEQ_STATUS status;
2349 : : OprProofCacheEntry *hentry;
2350 : :
5631 2351 [ - + ]: 270 : Assert(OprProofCacheHash != NULL);
2352 : :
2353 : : /* Currently we just reset all entries; hard to be smarter ... */
2354 : 270 : hash_seq_init(&status, OprProofCacheHash);
2355 : :
2356 [ + + ]: 2227 : while ((hentry = (OprProofCacheEntry *) hash_seq_search(&status)) != NULL)
2357 : : {
2358 : 1957 : hentry->have_implic = false;
2359 : 1957 : hentry->have_refute = false;
2360 : : }
6883 2361 : 270 : }
|
