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