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

Generated by: LCOV version 1.13