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