LCOV - code coverage report
Current view: top level - src/backend/optimizer/util - predtest.c (source / functions) Hit Total Coverage
Test: PostgreSQL 16beta1 Lines: 622 660 94.2 %
Date: 2023-05-30 23:12:14 Functions: 26 26 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.14