predtest.c File Reference

#include "postgres.h"
#include "catalog/pg_operator.h"
#include "catalog/pg_proc.h"
#include "catalog/pg_type.h"
#include "executor/executor.h"
#include "miscadmin.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "nodes/pathnodes.h"
#include "optimizer/optimizer.h"
#include "utils/array.h"
#include "utils/inval.h"
#include "utils/lsyscache.h"
#include "utils/syscache.h"

Include dependency graph for predtest.c:

Go to the source code of this file.

Data Structures
struct	PredIterInfoData
struct	ArrayConstIterState
struct	ArrayExprIterState
struct	OprProofCacheKey
struct	OprProofCacheEntry

Macros
#define	MAX_SAOP_ARRAY_SIZE   100
#define	iterate_begin(item, clause, info)
#define	iterate_end(info)
#define	BTLT   BTLessStrategyNumber
#define	BTLE   BTLessEqualStrategyNumber
#define	BTEQ   BTEqualStrategyNumber
#define	BTGE   BTGreaterEqualStrategyNumber
#define	BTGT   BTGreaterStrategyNumber
#define	BTNE   ROWCOMPARE_NE
#define	none   0

Typedefs
typedef struct PredIterInfoData *	PredIterInfo
typedef struct PredIterInfoData	PredIterInfoData
typedef struct OprProofCacheKey	OprProofCacheKey
typedef struct OprProofCacheEntry	OprProofCacheEntry

Enumerations
enum	PredClass { CLASS_ATOM , CLASS_AND , CLASS_OR }

Functions
static bool	predicate_implied_by_recurse (Node *clause, Node *predicate, bool weak)
static bool	predicate_refuted_by_recurse (Node *clause, Node *predicate, bool weak)
static PredClass	predicate_classify (Node *clause, PredIterInfo info)
static void	list_startup_fn (Node *clause, PredIterInfo info)
static Node *	list_next_fn (PredIterInfo info)
static void	list_cleanup_fn (PredIterInfo info)
static void	boolexpr_startup_fn (Node *clause, PredIterInfo info)
static void	arrayconst_startup_fn (Node *clause, PredIterInfo info)
static Node *	arrayconst_next_fn (PredIterInfo info)
static void	arrayconst_cleanup_fn (PredIterInfo info)
static void	arrayexpr_startup_fn (Node *clause, PredIterInfo info)
static Node *	arrayexpr_next_fn (PredIterInfo info)
static void	arrayexpr_cleanup_fn (PredIterInfo info)
static bool	predicate_implied_by_simple_clause (Expr *predicate, Node *clause, bool weak)
static bool	predicate_refuted_by_simple_clause (Expr *predicate, Node *clause, bool weak)
static Node *	extract_not_arg (Node *clause)
static Node *	extract_strong_not_arg (Node *clause)
static bool	clause_is_strict_for (Node *clause, Node *subexpr, bool allow_false)
static bool	operator_predicate_proof (Expr *predicate, Node *clause, bool refute_it, bool weak)
static bool	operator_same_subexprs_proof (Oid pred_op, Oid clause_op, bool refute_it)
static bool	operator_same_subexprs_lookup (Oid pred_op, Oid clause_op, bool refute_it)
static Oid	get_btree_test_op (Oid pred_op, Oid clause_op, bool refute_it)
static void	InvalidateOprProofCacheCallBack (Datum arg, int cacheid, uint32 hashvalue)
bool	predicate_implied_by (List *predicate_list, List *clause_list, bool weak)
bool	predicate_refuted_by (List *predicate_list, List *clause_list, bool weak)
static OprProofCacheEntry *	lookup_proof_cache (Oid pred_op, Oid clause_op, bool refute_it)

Variables
static const bool	BT_implies_table [6][6]
static const bool	BT_refutes_table [6][6]
static const StrategyNumber	BT_implic_table [6][6]
static const StrategyNumber	BT_refute_table [6][6]
static HTAB *	OprProofCacheHash = NULL

Macro Definition Documentation

BTEQ

#define BTEQ   BTEqualStrategyNumber

Definition at line 1664 of file predtest.c.

BTGE

#define BTGE   BTGreaterEqualStrategyNumber

Definition at line 1665 of file predtest.c.

BTGT

#define BTGT   BTGreaterStrategyNumber

Definition at line 1666 of file predtest.c.

BTLE

#define BTLE   BTLessEqualStrategyNumber

Definition at line 1663 of file predtest.c.

BTLT

#define BTLT   BTLessStrategyNumber

Definition at line 1662 of file predtest.c.

BTNE

#define BTNE   ROWCOMPARE_NE

Definition at line 1667 of file predtest.c.

iterate_begin

#define iterate_begin	(		item,
			clause,
			info
	)

Value:

    do { \
        Node   *item; \
        (info).startup_fn((clause), &(info)); \
        while ((item = (info).next_fn(&(info))) != NULL)

Definition at line 72 of file predtest.c.

iterate_end

#define iterate_end

(

info

)

Value:

        (info).cleanup_fn(&(info)); \
    } while (0)

Definition at line 78 of file predtest.c.

MAX_SAOP_ARRAY_SIZE

#define MAX_SAOP_ARRAY_SIZE   100

Definition at line 40 of file predtest.c.

none

#define none   0

Definition at line 1670 of file predtest.c.

Typedef Documentation

OprProofCacheEntry

typedef struct OprProofCacheEntry OprProofCacheEntry

OprProofCacheKey

typedef struct OprProofCacheKey OprProofCacheKey

PredIterInfo

typedef struct PredIterInfoData* PredIterInfo

Definition at line 57 of file predtest.c.

PredIterInfoData

typedef struct PredIterInfoData PredIterInfoData

Enumeration Type Documentation

PredClass

enum PredClass

Enumerator
CLASS_ATOM
CLASS_AND
CLASS_OR

Definition at line 50 of file predtest.c.

{
    CLASS_ATOM,                 /* expression that's not AND or OR */
    CLASS_AND,                  /* expression with AND semantics */
    CLASS_OR,                   /* expression with OR semantics */
} PredClass;

Function Documentation

arrayconst_cleanup_fn()

static void arrayconst_cleanup_fn ( PredIterInfo  info )

static

Definition at line 1021 of file predtest.c.

{
    ArrayConstIterState *state = (ArrayConstIterState *) info->state;
 
    pfree(state->elem_values);
    pfree(state->elem_nulls);
    list_free(state->opexpr.args);
    pfree(state);
}

References list_free(), pfree(), and PredIterInfoData::state.

Referenced by predicate_classify().

arrayconst_next_fn()

static Node * arrayconst_next_fn ( PredIterInfo  info )

static

Definition at line 1008 of file predtest.c.

{
    ArrayConstIterState *state = (ArrayConstIterState *) info->state;
 
    if (state->next_elem >= state->num_elems)
        return NULL;
    state->const_expr.constvalue = state->elem_values[state->next_elem];
    state->const_expr.constisnull = state->elem_nulls[state->next_elem];
    state->next_elem++;
    return (Node *) &(state->opexpr);
}

References if(), and PredIterInfoData::state.

Referenced by predicate_classify().

arrayconst_startup_fn()

static void arrayconst_startup_fn ( Node *  clause, PredIterInfo  info  )

static

Definition at line 959 of file predtest.c.

{
    ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
    ArrayConstIterState *state;
    Const      *arrayconst;
    ArrayType  *arrayval;
    int16       elmlen;
    bool        elmbyval;
    char        elmalign;
 
    /* Create working state struct */
    state = (ArrayConstIterState *) palloc(sizeof(ArrayConstIterState));
    info->state = (void *) state;
 
    /* Deconstruct the array literal */
    arrayconst = (Const *) lsecond(saop->args);
    arrayval = DatumGetArrayTypeP(arrayconst->constvalue);
    get_typlenbyvalalign(ARR_ELEMTYPE(arrayval),
                         &elmlen, &elmbyval, &elmalign);
    deconstruct_array(arrayval,
                      ARR_ELEMTYPE(arrayval),
                      elmlen, elmbyval, elmalign,
                      &state->elem_values, &state->elem_nulls,
                      &state->num_elems);
 
    /* Set up a dummy OpExpr to return as the per-item node */
    state->opexpr.xpr.type = T_OpExpr;
    state->opexpr.opno = saop->opno;
    state->opexpr.opfuncid = saop->opfuncid;
    state->opexpr.opresulttype = BOOLOID;
    state->opexpr.opretset = false;
    state->opexpr.opcollid = InvalidOid;
    state->opexpr.inputcollid = saop->inputcollid;
    state->opexpr.args = list_copy(saop->args);
 
    /* Set up a dummy Const node to hold the per-element values */
    state->const_expr.xpr.type = T_Const;
    state->const_expr.consttype = ARR_ELEMTYPE(arrayval);
    state->const_expr.consttypmod = -1;
    state->const_expr.constcollid = arrayconst->constcollid;
    state->const_expr.constlen = elmlen;
    state->const_expr.constbyval = elmbyval;
    lsecond(state->opexpr.args) = &state->const_expr;
 
    /* Initialize iteration state */
    state->next_elem = 0;
}

References ScalarArrayOpExpr::args, ARR_ELEMTYPE, DatumGetArrayTypeP, deconstruct_array(), get_typlenbyvalalign(), InvalidOid, list_copy(), lsecond, ScalarArrayOpExpr::opno, palloc(), and PredIterInfoData::state.

Referenced by predicate_classify().

arrayexpr_cleanup_fn()

static void arrayexpr_cleanup_fn ( PredIterInfo  info )

static

Definition at line 1081 of file predtest.c.

{
    ArrayExprIterState *state = (ArrayExprIterState *) info->state;
 
    list_free(state->opexpr.args);
    pfree(state);
}

References list_free(), pfree(), and PredIterInfoData::state.

Referenced by predicate_classify().

arrayexpr_next_fn()

static Node * arrayexpr_next_fn ( PredIterInfo  info )

static

Definition at line 1069 of file predtest.c.

{
    ArrayExprIterState *state = (ArrayExprIterState *) info->state;
 
    if (state->next == NULL)
        return NULL;
    lsecond(state->opexpr.args) = lfirst(state->next);
    state->next = lnext(info->state_list, state->next);
    return (Node *) &(state->opexpr);
}

References if(), lfirst, lnext(), lsecond, state::next, PredIterInfoData::state, and PredIterInfoData::state_list.

Referenced by predicate_classify().

arrayexpr_startup_fn()

static void arrayexpr_startup_fn ( Node *  clause, PredIterInfo  info  )

static

Definition at line 1042 of file predtest.c.

{
    ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
    ArrayExprIterState *state;
    ArrayExpr  *arrayexpr;
 
    /* Create working state struct */
    state = (ArrayExprIterState *) palloc(sizeof(ArrayExprIterState));
    info->state = (void *) state;
 
    /* Set up a dummy OpExpr to return as the per-item node */
    state->opexpr.xpr.type = T_OpExpr;
    state->opexpr.opno = saop->opno;
    state->opexpr.opfuncid = saop->opfuncid;
    state->opexpr.opresulttype = BOOLOID;
    state->opexpr.opretset = false;
    state->opexpr.opcollid = InvalidOid;
    state->opexpr.inputcollid = saop->inputcollid;
    state->opexpr.args = list_copy(saop->args);
 
    /* Initialize iteration variable to first member of ArrayExpr */
    arrayexpr = (ArrayExpr *) lsecond(saop->args);
    info->state_list = arrayexpr->elements;
    state->next = list_head(arrayexpr->elements);
}

References ScalarArrayOpExpr::args, ArrayExpr::elements, InvalidOid, list_copy(), list_head(), lsecond, state::next, ScalarArrayOpExpr::opno, palloc(), PredIterInfoData::state, and PredIterInfoData::state_list.

Referenced by predicate_classify().

boolexpr_startup_fn()

static void boolexpr_startup_fn ( Node *  clause, PredIterInfo  info  )

static

Definition at line 938 of file predtest.c.

{
    info->state_list = ((BoolExpr *) clause)->args;
    info->state = (void *) list_head(info->state_list);
}

References list_head(), PredIterInfoData::state, and PredIterInfoData::state_list.

Referenced by predicate_classify().

clause_is_strict_for()

static bool clause_is_strict_for ( Node *  clause, Node *  subexpr, bool  allow_false  )

static

Definition at line 1460 of file predtest.c.

{
    ListCell   *lc;
 
    /* safety checks */
    if (clause == NULL || subexpr == NULL)
        return false;
 
    /*
     * Look through any RelabelType nodes, so that we can match, say,
     * varcharcol with lower(varcharcol::text).  (In general we could recurse
     * through any nullness-preserving, immutable operation.)  We should not
     * see stacked RelabelTypes here.
     */
    if (IsA(clause, RelabelType))
        clause = (Node *) ((RelabelType *) clause)->arg;
    if (IsA(subexpr, RelabelType))
        subexpr = (Node *) ((RelabelType *) subexpr)->arg;
 
    /* Base case */
    if (equal(clause, subexpr))
        return true;
 
    /*
     * If we have a strict operator or function, a NULL result is guaranteed
     * if any input is forced NULL by subexpr.  This is OK even if the op or
     * func isn't immutable, since it won't even be called on NULL input.
     */
    if (is_opclause(clause) &&
        op_strict(((OpExpr *) clause)->opno))
    {
        foreach(lc, ((OpExpr *) clause)->args)
        {
            if (clause_is_strict_for((Node *) lfirst(lc), subexpr, false))
                return true;
        }
        return false;
    }
    if (is_funcclause(clause) &&
        func_strict(((FuncExpr *) clause)->funcid))
    {
        foreach(lc, ((FuncExpr *) clause)->args)
        {
            if (clause_is_strict_for((Node *) lfirst(lc), subexpr, false))
                return true;
        }
        return false;
    }
 
    /*
     * CoerceViaIO is strict (whether or not the I/O functions it calls are).
     * Likewise, ArrayCoerceExpr is strict for its array argument (regardless
     * of what the per-element expression is), ConvertRowtypeExpr is strict at
     * the row level, and CoerceToDomain is strict too.  These are worth
     * checking mainly because it saves us having to explain to users why some
     * type coercions are known strict and others aren't.
     */
    if (IsA(clause, CoerceViaIO))
        return clause_is_strict_for((Node *) ((CoerceViaIO *) clause)->arg,
                                    subexpr, false);
    if (IsA(clause, ArrayCoerceExpr))
        return clause_is_strict_for((Node *) ((ArrayCoerceExpr *) clause)->arg,
                                    subexpr, false);
    if (IsA(clause, ConvertRowtypeExpr))
        return clause_is_strict_for((Node *) ((ConvertRowtypeExpr *) clause)->arg,
                                    subexpr, false);
    if (IsA(clause, CoerceToDomain))
        return clause_is_strict_for((Node *) ((CoerceToDomain *) clause)->arg,
                                    subexpr, false);
 
    /*
     * ScalarArrayOpExpr is a special case.  Note that we'd only reach here
     * with a ScalarArrayOpExpr clause if we failed to deconstruct it into an
     * AND or OR tree, as for example if it has too many array elements.
     */
    if (IsA(clause, ScalarArrayOpExpr))
    {
        ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
        Node       *scalarnode = (Node *) linitial(saop->args);
        Node       *arraynode = (Node *) lsecond(saop->args);
 
        /*
         * If we can prove the scalar input to be null, and the operator is
         * strict, then the SAOP result has to be null --- unless the array is
         * empty.  For an empty array, we'd get either false (for ANY) or true
         * (for ALL).  So if allow_false = true then the proof succeeds anyway
         * for the ANY case; otherwise we can only make the proof if we can
         * prove the array non-empty.
         */
        if (clause_is_strict_for(scalarnode, subexpr, false) &&
            op_strict(saop->opno))
        {
            int         nelems = 0;
 
            if (allow_false && saop->useOr)
                return true;    /* can succeed even if array is empty */
 
            if (arraynode && IsA(arraynode, Const))
            {
                Const      *arrayconst = (Const *) arraynode;
                ArrayType  *arrval;
 
                /*
                 * If array is constant NULL then we can succeed, as in the
                 * case below.
                 */
                if (arrayconst->constisnull)
                    return true;
 
                /* Otherwise, we can compute the number of elements. */
                arrval = DatumGetArrayTypeP(arrayconst->constvalue);
                nelems = ArrayGetNItems(ARR_NDIM(arrval), ARR_DIMS(arrval));
            }
            else if (arraynode && IsA(arraynode, ArrayExpr) &&
                     !((ArrayExpr *) arraynode)->multidims)
            {
                /*
                 * We can also reliably count the number of array elements if
                 * the input is a non-multidim ARRAY[] expression.
                 */
                nelems = list_length(((ArrayExpr *) arraynode)->elements);
            }
 
            /* Proof succeeds if array is definitely non-empty */
            if (nelems > 0)
                return true;
        }
 
        /*
         * If we can prove the array input to be null, the proof succeeds in
         * all cases, since ScalarArrayOpExpr will always return NULL for a
         * NULL array.  Otherwise, we're done here.
         */
        return clause_is_strict_for(arraynode, subexpr, false);
    }
 
    /*
     * When recursing into an expression, we might find a NULL constant.
     * That's certainly NULL, whether it matches subexpr or not.
     */
    if (IsA(clause, Const))
        return ((Const *) clause)->constisnull;
 
    return false;
}

References arg, ScalarArrayOpExpr::args, ARR_DIMS, ARR_NDIM, ArrayGetNItems(), DatumGetArrayTypeP, equal(), func_strict(), is_funcclause(), is_opclause(), IsA, lfirst, linitial, list_length(), lsecond, op_strict(), ScalarArrayOpExpr::opno, and ScalarArrayOpExpr::useOr.

Referenced by predicate_implied_by_simple_clause(), and predicate_refuted_by_simple_clause().

extract_not_arg()

static Node * extract_not_arg ( Node *  clause )

static

Definition at line 1386 of file predtest.c.

{
    if (clause == NULL)
        return NULL;
    if (IsA(clause, BoolExpr))
    {
        BoolExpr   *bexpr = (BoolExpr *) clause;
 
        if (bexpr->boolop == NOT_EXPR)
            return (Node *) linitial(bexpr->args);
    }
    else if (IsA(clause, BooleanTest))
    {
        BooleanTest *btest = (BooleanTest *) clause;
 
        if (btest->booltesttype == IS_NOT_TRUE ||
            btest->booltesttype == IS_FALSE ||
            btest->booltesttype == IS_UNKNOWN)
            return (Node *) btest->arg;
    }
    return NULL;
}

References BooleanTest::arg, BoolExpr::args, BoolExpr::boolop, BooleanTest::booltesttype, IS_FALSE, IS_NOT_TRUE, IS_UNKNOWN, IsA, linitial, and NOT_EXPR.

Referenced by predicate_refuted_by_recurse().

extract_strong_not_arg()

static Node * extract_strong_not_arg ( Node *  clause )

static

Definition at line 1414 of file predtest.c.

{
    if (clause == NULL)
        return NULL;
    if (IsA(clause, BoolExpr))
    {
        BoolExpr   *bexpr = (BoolExpr *) clause;
 
        if (bexpr->boolop == NOT_EXPR)
            return (Node *) linitial(bexpr->args);
    }
    else if (IsA(clause, BooleanTest))
    {
        BooleanTest *btest = (BooleanTest *) clause;
 
        if (btest->booltesttype == IS_FALSE)
            return (Node *) btest->arg;
    }
    return NULL;
}

References BooleanTest::arg, BoolExpr::args, BoolExpr::boolop, BooleanTest::booltesttype, IS_FALSE, IsA, linitial, and NOT_EXPR.

Referenced by predicate_refuted_by_recurse().

get_btree_test_op()

static Oid get_btree_test_op ( Oid  pred_op, Oid  clause_op, bool  refute_it  )

static

Definition at line 2330 of file predtest.c.

{
    OprProofCacheEntry *cache_entry;
 
    cache_entry = lookup_proof_cache(pred_op, clause_op, refute_it);
    if (refute_it)
        return cache_entry->refute_test_op;
    else
        return cache_entry->implic_test_op;
}

References OprProofCacheEntry::implic_test_op, lookup_proof_cache(), and OprProofCacheEntry::refute_test_op.

Referenced by operator_predicate_proof().

InvalidateOprProofCacheCallBack()

static void InvalidateOprProofCacheCallBack ( Datum  arg, int  cacheid, uint32  hashvalue  )

static

Definition at line 2346 of file predtest.c.

{
    HASH_SEQ_STATUS status;
    OprProofCacheEntry *hentry;
 
    Assert(OprProofCacheHash != NULL);
 
    /* Currently we just reset all entries; hard to be smarter ... */
    hash_seq_init(&status, OprProofCacheHash);
 
    while ((hentry = (OprProofCacheEntry *) hash_seq_search(&status)) != NULL)
    {
        hentry->have_implic = false;
        hentry->have_refute = false;
    }
}

References Assert, hash_seq_init(), hash_seq_search(), OprProofCacheEntry::have_implic, OprProofCacheEntry::have_refute, and OprProofCacheHash.

Referenced by lookup_proof_cache().

list_cleanup_fn()

static void list_cleanup_fn ( PredIterInfo  info )

static

Definition at line 928 of file predtest.c.

{
    /* Nothing to clean up */
}

Referenced by predicate_classify().

list_next_fn()

static Node * list_next_fn ( PredIterInfo  info )

static

Definition at line 915 of file predtest.c.

{
    ListCell   *l = (ListCell *) info->state;
    Node       *n;
 
    if (l == NULL)
        return NULL;
    n = lfirst(l);
    info->state = (void *) lnext(info->state_list, l);
    return n;
}

References if(), lfirst, lnext(), PredIterInfoData::state, and PredIterInfoData::state_list.

Referenced by predicate_classify().

list_startup_fn()

static void list_startup_fn ( Node *  clause, PredIterInfo  info  )

static

Definition at line 908 of file predtest.c.

{
    info->state_list = (List *) clause;
    info->state = (void *) list_head(info->state_list);
}

References list_head(), PredIterInfoData::state, and PredIterInfoData::state_list.

Referenced by predicate_classify().

lookup_proof_cache()

static OprProofCacheEntry* lookup_proof_cache ( Oid  pred_op, Oid  clause_op, bool  refute_it  )

static

Definition at line 2101 of file predtest.c.

{
    OprProofCacheKey key;
    OprProofCacheEntry *cache_entry;
    bool        cfound;
    bool        same_subexprs = false;
    Oid         test_op = InvalidOid;
    bool        found = false;
    List       *pred_op_infos,
               *clause_op_infos;
    ListCell   *lcp,
               *lcc;
 
    /*
     * Find or make a cache entry for this pair of operators.
     */
    if (OprProofCacheHash == NULL)
    {
        /* First time through: initialize the hash table */
        HASHCTL     ctl;
 
        ctl.keysize = sizeof(OprProofCacheKey);
        ctl.entrysize = sizeof(OprProofCacheEntry);
        OprProofCacheHash = hash_create("Btree proof lookup cache", 256,
                                        &ctl, HASH_ELEM | HASH_BLOBS);
 
        /* Arrange to flush cache on pg_amop changes */
        CacheRegisterSyscacheCallback(AMOPOPID,
                                      InvalidateOprProofCacheCallBack,
                                      (Datum) 0);
    }
 
    key.pred_op = pred_op;
    key.clause_op = clause_op;
    cache_entry = (OprProofCacheEntry *) hash_search(OprProofCacheHash,
                                                     &key,
                                                     HASH_ENTER, &cfound);
    if (!cfound)
    {
        /* new cache entry, set it invalid */
        cache_entry->have_implic = false;
        cache_entry->have_refute = false;
    }
    else
    {
        /* pre-existing cache entry, see if we know the answer yet */
        if (refute_it ? cache_entry->have_refute : cache_entry->have_implic)
            return cache_entry;
    }
 
    /*
     * Try to find a btree opfamily containing the given operators.
     *
     * We must find a btree opfamily that contains both operators, else the
     * implication can't be determined.  Also, the opfamily must contain a
     * suitable test operator taking the operators' righthand datatypes.
     *
     * If there are multiple matching opfamilies, assume we can use any one to
     * determine the logical relationship of the two operators and the correct
     * corresponding test operator.  This should work for any logically
     * consistent opfamilies.
     *
     * Note that we can determine the operators' relationship for
     * same-subexprs cases even from an opfamily that lacks a usable test
     * operator.  This can happen in cases with incomplete sets of cross-type
     * comparison operators.
     */
    clause_op_infos = get_op_btree_interpretation(clause_op);
    if (clause_op_infos)
        pred_op_infos = get_op_btree_interpretation(pred_op);
    else                        /* no point in looking */
        pred_op_infos = NIL;
 
    foreach(lcp, pred_op_infos)
    {
        OpBtreeInterpretation *pred_op_info = lfirst(lcp);
        Oid         opfamily_id = pred_op_info->opfamily_id;
 
        foreach(lcc, clause_op_infos)
        {
            OpBtreeInterpretation *clause_op_info = lfirst(lcc);
            StrategyNumber pred_strategy,
                        clause_strategy,
                        test_strategy;
 
            /* Must find them in same opfamily */
            if (opfamily_id != clause_op_info->opfamily_id)
                continue;
            /* Lefttypes should match */
            Assert(clause_op_info->oplefttype == pred_op_info->oplefttype);
 
            pred_strategy = pred_op_info->strategy;
            clause_strategy = clause_op_info->strategy;
 
            /*
             * Check to see if we can make a proof for same-subexpressions
             * cases based on the operators' relationship in this opfamily.
             */
            if (refute_it)
                same_subexprs |= BT_refutes_table[clause_strategy - 1][pred_strategy - 1];
            else
                same_subexprs |= BT_implies_table[clause_strategy - 1][pred_strategy - 1];
 
            /*
             * Look up the "test" strategy number in the implication table
             */
            if (refute_it)
                test_strategy = BT_refute_table[clause_strategy - 1][pred_strategy - 1];
            else
                test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1];
 
            if (test_strategy == 0)
            {
                /* Can't determine implication using this interpretation */
                continue;
            }
 
            /*
             * See if opfamily has an operator for the test strategy and the
             * datatypes.
             */
            if (test_strategy == BTNE)
            {
                test_op = get_opfamily_member(opfamily_id,
                                              pred_op_info->oprighttype,
                                              clause_op_info->oprighttype,
                                              BTEqualStrategyNumber);
                if (OidIsValid(test_op))
                    test_op = get_negator(test_op);
            }
            else
            {
                test_op = get_opfamily_member(opfamily_id,
                                              pred_op_info->oprighttype,
                                              clause_op_info->oprighttype,
                                              test_strategy);
            }
 
            if (!OidIsValid(test_op))
                continue;
 
            /*
             * Last check: test_op must be immutable.
             *
             * Note that we require only the test_op to be immutable, not the
             * original clause_op.  (pred_op is assumed to have been checked
             * immutable by the caller.)  Essentially we are assuming that the
             * opfamily is consistent even if it contains operators that are
             * merely stable.
             */
            if (op_volatile(test_op) == PROVOLATILE_IMMUTABLE)
            {
                found = true;
                break;
            }
        }
 
        if (found)
            break;
    }
 
    list_free_deep(pred_op_infos);
    list_free_deep(clause_op_infos);
 
    if (!found)
    {
        /* couldn't find a suitable comparison operator */
        test_op = InvalidOid;
    }
 
    /*
     * If we think we were able to prove something about same-subexpressions
     * cases, check to make sure the clause_op is immutable before believing
     * it completely.  (Usually, the clause_op would be immutable if the
     * pred_op is, but it's not entirely clear that this must be true in all
     * cases, so let's check.)
     */
    if (same_subexprs &&
        op_volatile(clause_op) != PROVOLATILE_IMMUTABLE)
        same_subexprs = false;
 
    /* Cache the results, whether positive or negative */
    if (refute_it)
    {
        cache_entry->refute_test_op = test_op;
        cache_entry->same_subexprs_refutes = same_subexprs;
        cache_entry->have_refute = true;
    }
    else
    {
        cache_entry->implic_test_op = test_op;
        cache_entry->same_subexprs_implies = same_subexprs;
        cache_entry->have_implic = true;
    }
 
    return cache_entry;
}

References Assert, BT_implic_table, BT_implies_table, BT_refute_table, BT_refutes_table, BTEqualStrategyNumber, BTNE, CacheRegisterSyscacheCallback(), ctl, get_negator(), get_op_btree_interpretation(), get_opfamily_member(), HASH_BLOBS, hash_create(), HASH_ELEM, HASH_ENTER, hash_search(), OprProofCacheEntry::have_implic, OprProofCacheEntry::have_refute, OprProofCacheEntry::implic_test_op, InvalidateOprProofCacheCallBack(), InvalidOid, sort-test::key, lfirst, list_free_deep(), NIL, OidIsValid, op_volatile(), OpBtreeInterpretation::opfamily_id, OpBtreeInterpretation::oplefttype, OpBtreeInterpretation::oprighttype, OprProofCacheHash, OprProofCacheEntry::refute_test_op, OprProofCacheEntry::same_subexprs_implies, OprProofCacheEntry::same_subexprs_refutes, and OpBtreeInterpretation::strategy.

Referenced by get_btree_test_op(), and operator_same_subexprs_lookup().

operator_predicate_proof()

static bool operator_predicate_proof ( Expr *  predicate, Node *  clause, bool  refute_it, bool  weak  )

static

Definition at line 1779 of file predtest.c.

{
    OpExpr     *pred_opexpr,
               *clause_opexpr;
    Oid         pred_collation,
                clause_collation;
    Oid         pred_op,
                clause_op,
                test_op;
    Node       *pred_leftop,
               *pred_rightop,
               *clause_leftop,
               *clause_rightop;
    Const      *pred_const,
               *clause_const;
    Expr       *test_expr;
    ExprState  *test_exprstate;
    Datum       test_result;
    bool        isNull;
    EState     *estate;
    MemoryContext oldcontext;
 
    /*
     * Both expressions must be binary opclauses, else we can't do anything.
     *
     * Note: in future we might extend this logic to other operator-based
     * constructs such as DistinctExpr.  But the planner isn't very smart
     * about DistinctExpr in general, and this probably isn't the first place
     * to fix if you want to improve that.
     */
    if (!is_opclause(predicate))
        return false;
    pred_opexpr = (OpExpr *) predicate;
    if (list_length(pred_opexpr->args) != 2)
        return false;
    if (!is_opclause(clause))
        return false;
    clause_opexpr = (OpExpr *) clause;
    if (list_length(clause_opexpr->args) != 2)
        return false;
 
    /*
     * If they're marked with different collations then we can't do anything.
     * This is a cheap test so let's get it out of the way early.
     */
    pred_collation = pred_opexpr->inputcollid;
    clause_collation = clause_opexpr->inputcollid;
    if (pred_collation != clause_collation)
        return false;
 
    /* Grab the operator OIDs now too.  We may commute these below. */
    pred_op = pred_opexpr->opno;
    clause_op = clause_opexpr->opno;
 
    /*
     * We have to match up at least one pair of input expressions.
     */
    pred_leftop = (Node *) linitial(pred_opexpr->args);
    pred_rightop = (Node *) lsecond(pred_opexpr->args);
    clause_leftop = (Node *) linitial(clause_opexpr->args);
    clause_rightop = (Node *) lsecond(clause_opexpr->args);
 
    if (equal(pred_leftop, clause_leftop))
    {
        if (equal(pred_rightop, clause_rightop))
        {
            /* We have x op1 y and x op2 y */
            return operator_same_subexprs_proof(pred_op, clause_op, refute_it);
        }
        else
        {
            /* Fail unless rightops are both Consts */
            if (pred_rightop == NULL || !IsA(pred_rightop, Const))
                return false;
            pred_const = (Const *) pred_rightop;
            if (clause_rightop == NULL || !IsA(clause_rightop, Const))
                return false;
            clause_const = (Const *) clause_rightop;
        }
    }
    else if (equal(pred_rightop, clause_rightop))
    {
        /* Fail unless leftops are both Consts */
        if (pred_leftop == NULL || !IsA(pred_leftop, Const))
            return false;
        pred_const = (Const *) pred_leftop;
        if (clause_leftop == NULL || !IsA(clause_leftop, Const))
            return false;
        clause_const = (Const *) clause_leftop;
        /* Commute both operators so we can assume Consts are on the right */
        pred_op = get_commutator(pred_op);
        if (!OidIsValid(pred_op))
            return false;
        clause_op = get_commutator(clause_op);
        if (!OidIsValid(clause_op))
            return false;
    }
    else if (equal(pred_leftop, clause_rightop))
    {
        if (equal(pred_rightop, clause_leftop))
        {
            /* We have x op1 y and y op2 x */
            /* Commute pred_op that we can treat this like a straight match */
            pred_op = get_commutator(pred_op);
            if (!OidIsValid(pred_op))
                return false;
            return operator_same_subexprs_proof(pred_op, clause_op, refute_it);
        }
        else
        {
            /* Fail unless pred_rightop/clause_leftop are both Consts */
            if (pred_rightop == NULL || !IsA(pred_rightop, Const))
                return false;
            pred_const = (Const *) pred_rightop;
            if (clause_leftop == NULL || !IsA(clause_leftop, Const))
                return false;
            clause_const = (Const *) clause_leftop;
            /* Commute clause_op so we can assume Consts are on the right */
            clause_op = get_commutator(clause_op);
            if (!OidIsValid(clause_op))
                return false;
        }
    }
    else if (equal(pred_rightop, clause_leftop))
    {
        /* Fail unless pred_leftop/clause_rightop are both Consts */
        if (pred_leftop == NULL || !IsA(pred_leftop, Const))
            return false;
        pred_const = (Const *) pred_leftop;
        if (clause_rightop == NULL || !IsA(clause_rightop, Const))
            return false;
        clause_const = (Const *) clause_rightop;
        /* Commute pred_op so we can assume Consts are on the right */
        pred_op = get_commutator(pred_op);
        if (!OidIsValid(pred_op))
            return false;
    }
    else
    {
        /* Failed to match up any of the subexpressions, so we lose */
        return false;
    }
 
    /*
     * We have two identical subexpressions, and two other subexpressions that
     * are not identical but are both Consts; and we have commuted the
     * operators if necessary so that the Consts are on the right.  We'll need
     * to compare the Consts' values.  If either is NULL, we can't do that, so
     * usually the proof fails ... but in some cases we can claim success.
     */
    if (clause_const->constisnull)
    {
        /* If clause_op isn't strict, we can't prove anything */
        if (!op_strict(clause_op))
            return false;
 
        /*
         * At this point we know that the clause returns NULL.  For proof
         * types that assume truth of the clause, this means the proof is
         * vacuously true (a/k/a "false implies anything").  That's all proof
         * types except weak implication.
         */
        if (!(weak && !refute_it))
            return true;
 
        /*
         * For weak implication, it's still possible for the proof to succeed,
         * if the predicate can also be proven NULL.  In that case we've got
         * NULL => NULL which is valid for this proof type.
         */
        if (pred_const->constisnull && op_strict(pred_op))
            return true;
        /* Else the proof fails */
        return false;
    }
    if (pred_const->constisnull)
    {
        /*
         * If the pred_op is strict, we know the predicate yields NULL, which
         * means the proof succeeds for either weak implication or weak
         * refutation.
         */
        if (weak && op_strict(pred_op))
            return true;
        /* Else the proof fails */
        return false;
    }
 
    /*
     * Lookup the constant-comparison operator using the system catalogs and
     * the operator implication tables.
     */
    test_op = get_btree_test_op(pred_op, clause_op, refute_it);
 
    if (!OidIsValid(test_op))
    {
        /* couldn't find a suitable comparison operator */
        return false;
    }
 
    /*
     * Evaluate the test.  For this we need an EState.
     */
    estate = CreateExecutorState();
 
    /* We can use the estate's working context to avoid memory leaks. */
    oldcontext = MemoryContextSwitchTo(estate->es_query_cxt);
 
    /* Build expression tree */
    test_expr = make_opclause(test_op,
                              BOOLOID,
                              false,
                              (Expr *) pred_const,
                              (Expr *) clause_const,
                              InvalidOid,
                              pred_collation);
 
    /* Fill in opfuncids */
    fix_opfuncids((Node *) test_expr);
 
    /* Prepare it for execution */
    test_exprstate = ExecInitExpr(test_expr, NULL);
 
    /* And execute it. */
    test_result = ExecEvalExprSwitchContext(test_exprstate,
                                            GetPerTupleExprContext(estate),
                                            &isNull);
 
    /* Get back to outer memory context */
    MemoryContextSwitchTo(oldcontext);
 
    /* Release all the junk we just created */
    FreeExecutorState(estate);
 
    if (isNull)
    {
        /* Treat a null result as non-proof ... but it's a tad fishy ... */
        elog(DEBUG2, "null predicate test result");
        return false;
    }
    return DatumGetBool(test_result);
}

References OpExpr::args, CreateExecutorState(), DatumGetBool(), DEBUG2, elog, equal(), EState::es_query_cxt, ExecEvalExprSwitchContext(), ExecInitExpr(), fix_opfuncids(), FreeExecutorState(), get_btree_test_op(), get_commutator(), GetPerTupleExprContext, InvalidOid, is_opclause(), IsA, linitial, list_length(), lsecond, make_opclause(), MemoryContextSwitchTo(), OidIsValid, op_strict(), operator_same_subexprs_proof(), and OpExpr::opno.

Referenced by predicate_implied_by_simple_clause(), and predicate_refuted_by_simple_clause().

operator_same_subexprs_lookup()

static bool operator_same_subexprs_lookup ( Oid  pred_op, Oid  clause_op, bool  refute_it  )

static

Definition at line 2305 of file predtest.c.

{
    OprProofCacheEntry *cache_entry;
 
    cache_entry = lookup_proof_cache(pred_op, clause_op, refute_it);
    if (refute_it)
        return cache_entry->same_subexprs_refutes;
    else
        return cache_entry->same_subexprs_implies;
}

References lookup_proof_cache(), OprProofCacheEntry::same_subexprs_implies, and OprProofCacheEntry::same_subexprs_refutes.

Referenced by operator_same_subexprs_proof().

operator_same_subexprs_proof()

static bool operator_same_subexprs_proof ( Oid  pred_op, Oid  clause_op, bool  refute_it  )

static

Definition at line 2032 of file predtest.c.

{
    /*
     * A simple and general rule is that the predicate is proven if clause_op
     * and pred_op are the same, or refuted if they are each other's negators.
     * We need not check immutability since the pred_op is already known
     * immutable.  (Actually, by this point we may have the commutator of a
     * known-immutable pred_op, but that should certainly be immutable too.
     * Likewise we don't worry whether the pred_op's negator is immutable.)
     *
     * Note: the "same" case won't get here if we actually had EXPR1 clause_op
     * EXPR2 and EXPR1 pred_op EXPR2, because the overall-expression-equality
     * test in predicate_implied_by_simple_clause would have caught it.  But
     * we can see the same operator after having commuted the pred_op.
     */
    if (refute_it)
    {
        if (get_negator(pred_op) == clause_op)
            return true;
    }
    else
    {
        if (pred_op == clause_op)
            return true;
    }
 
    /*
     * Otherwise, see if we can determine the implication by finding the
     * operators' relationship via some btree opfamily.
     */
    return operator_same_subexprs_lookup(pred_op, clause_op, refute_it);
}

References get_negator(), and operator_same_subexprs_lookup().

Referenced by operator_predicate_proof().

predicate_classify()

static PredClass predicate_classify ( Node *  clause, PredIterInfo  info  )

static

Definition at line 826 of file predtest.c.

{
    /* Caller should not pass us NULL, nor a RestrictInfo clause */
    Assert(clause != NULL);
    Assert(!IsA(clause, RestrictInfo));
 
    /*
     * If we see a List, assume it's an implicit-AND list; this is the correct
     * semantics for lists of RestrictInfo nodes.
     */
    if (IsA(clause, List))
    {
        info->startup_fn = list_startup_fn;
        info->next_fn = list_next_fn;
        info->cleanup_fn = list_cleanup_fn;
        return CLASS_AND;
    }
 
    /* Handle normal AND and OR boolean clauses */
    if (is_andclause(clause))
    {
        info->startup_fn = boolexpr_startup_fn;
        info->next_fn = list_next_fn;
        info->cleanup_fn = list_cleanup_fn;
        return CLASS_AND;
    }
    if (is_orclause(clause))
    {
        info->startup_fn = boolexpr_startup_fn;
        info->next_fn = list_next_fn;
        info->cleanup_fn = list_cleanup_fn;
        return CLASS_OR;
    }
 
    /* Handle ScalarArrayOpExpr */
    if (IsA(clause, ScalarArrayOpExpr))
    {
        ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
        Node       *arraynode = (Node *) lsecond(saop->args);
 
        /*
         * We can break this down into an AND or OR structure, but only if we
         * know how to iterate through expressions for the array's elements.
         * We can do that if the array operand is a non-null constant or a
         * simple ArrayExpr.
         */
        if (arraynode && IsA(arraynode, Const) &&
            !((Const *) arraynode)->constisnull)
        {
            ArrayType  *arrayval;
            int         nelems;
 
            arrayval = DatumGetArrayTypeP(((Const *) arraynode)->constvalue);
            nelems = ArrayGetNItems(ARR_NDIM(arrayval), ARR_DIMS(arrayval));
            if (nelems <= MAX_SAOP_ARRAY_SIZE)
            {
                info->startup_fn = arrayconst_startup_fn;
                info->next_fn = arrayconst_next_fn;
                info->cleanup_fn = arrayconst_cleanup_fn;
                return saop->useOr ? CLASS_OR : CLASS_AND;
            }
        }
        else if (arraynode && IsA(arraynode, ArrayExpr) &&
                 !((ArrayExpr *) arraynode)->multidims &&
                 list_length(((ArrayExpr *) arraynode)->elements) <= MAX_SAOP_ARRAY_SIZE)
        {
            info->startup_fn = arrayexpr_startup_fn;
            info->next_fn = arrayexpr_next_fn;
            info->cleanup_fn = arrayexpr_cleanup_fn;
            return saop->useOr ? CLASS_OR : CLASS_AND;
        }
    }
 
    /* None of the above, so it's an atom */
    return CLASS_ATOM;
}

References ScalarArrayOpExpr::args, ARR_DIMS, ARR_NDIM, arrayconst_cleanup_fn(), arrayconst_next_fn(), arrayconst_startup_fn(), arrayexpr_cleanup_fn(), arrayexpr_next_fn(), arrayexpr_startup_fn(), ArrayGetNItems(), Assert, boolexpr_startup_fn(), CLASS_AND, CLASS_ATOM, CLASS_OR, PredIterInfoData::cleanup_fn, DatumGetArrayTypeP, is_andclause(), is_orclause(), IsA, list_cleanup_fn(), list_length(), list_next_fn(), list_startup_fn(), lsecond, MAX_SAOP_ARRAY_SIZE, PredIterInfoData::next_fn, PredIterInfoData::startup_fn, and ScalarArrayOpExpr::useOr.

Referenced by predicate_implied_by_recurse(), and predicate_refuted_by_recurse().

predicate_implied_by()

bool predicate_implied_by	(	List *	predicate_list,
		List *	clause_list,
		bool	weak
	)

Definition at line 152 of file predtest.c.

{
    Node       *p,
               *c;
 
    if (predicate_list == NIL)
        return true;            /* no predicate: implication is vacuous */
    if (clause_list == NIL)
        return false;           /* no restriction: implication must fail */
 
    /*
     * If either input is a single-element list, replace it with its lone
     * member; this avoids one useless level of AND-recursion.  We only need
     * to worry about this at top level, since eval_const_expressions should
     * have gotten rid of any trivial ANDs or ORs below that.
     */
    if (list_length(predicate_list) == 1)
        p = (Node *) linitial(predicate_list);
    else
        p = (Node *) predicate_list;
    if (list_length(clause_list) == 1)
        c = (Node *) linitial(clause_list);
    else
        c = (Node *) clause_list;
 
    /* And away we go ... */
    return predicate_implied_by_recurse(c, p, weak);
}

References linitial, list_length(), NIL, and predicate_implied_by_recurse().

Referenced by add_predicate_to_index_quals(), build_paths_for_OR(), check_index_predicates(), choose_bitmap_and(), ConstraintImpliedByRelConstraint(), create_bitmap_scan_plan(), create_bitmap_subplan(), create_indexscan_plan(), infer_arbiter_indexes(), and test_predtest().

predicate_implied_by_recurse()

static bool predicate_implied_by_recurse ( Node *  clause, Node *  predicate, bool  weak  )

static

Definition at line 290 of file predtest.c.

{
    PredIterInfoData clause_info;
    PredIterInfoData pred_info;
    PredClass   pclass;
    bool        result;
 
    /* skip through RestrictInfo */
    Assert(clause != NULL);
    if (IsA(clause, RestrictInfo))
        clause = (Node *) ((RestrictInfo *) clause)->clause;
 
    pclass = predicate_classify(predicate, &pred_info);
 
    switch (predicate_classify(clause, &clause_info))
    {
        case CLASS_AND:
            switch (pclass)
            {
                case CLASS_AND:
 
                    /*
                     * AND-clause => AND-clause if A implies each of B's items
                     */
                    result = true;
                    iterate_begin(pitem, predicate, pred_info)
                    {
                        if (!predicate_implied_by_recurse(clause, pitem,
                                                          weak))
                        {
                            result = false;
                            break;
                        }
                    }
                    iterate_end(pred_info);
                    return result;
 
                case CLASS_OR:
 
                    /*
                     * AND-clause => OR-clause if A implies any of B's items
                     *
                     * Needed to handle (x AND y) => ((x AND y) OR z)
                     */
                    result = false;
                    iterate_begin(pitem, predicate, pred_info)
                    {
                        if (predicate_implied_by_recurse(clause, pitem,
                                                         weak))
                        {
                            result = true;
                            break;
                        }
                    }
                    iterate_end(pred_info);
                    if (result)
                        return result;
 
                    /*
                     * Also check if any of A's items implies B
                     *
                     * Needed to handle ((x OR y) AND z) => (x OR y)
                     */
                    iterate_begin(citem, clause, clause_info)
                    {
                        if (predicate_implied_by_recurse(citem, predicate,
                                                         weak))
                        {
                            result = true;
                            break;
                        }
                    }
                    iterate_end(clause_info);
                    return result;
 
                case CLASS_ATOM:
 
                    /*
                     * AND-clause => atom if any of A's items implies B
                     */
                    result = false;
                    iterate_begin(citem, clause, clause_info)
                    {
                        if (predicate_implied_by_recurse(citem, predicate,
                                                         weak))
                        {
                            result = true;
                            break;
                        }
                    }
                    iterate_end(clause_info);
                    return result;
            }
            break;
 
        case CLASS_OR:
            switch (pclass)
            {
                case CLASS_OR:
 
                    /*
                     * OR-clause => OR-clause if each of A's items implies any
                     * of B's items.  Messy but can't do it any more simply.
                     */
                    result = true;
                    iterate_begin(citem, clause, clause_info)
                    {
                        bool        presult = false;
 
                        iterate_begin(pitem, predicate, pred_info)
                        {
                            if (predicate_implied_by_recurse(citem, pitem,
                                                             weak))
                            {
                                presult = true;
                                break;
                            }
                        }
                        iterate_end(pred_info);
                        if (!presult)
                        {
                            result = false; /* doesn't imply any of B's */
                            break;
                        }
                    }
                    iterate_end(clause_info);
                    return result;
 
                case CLASS_AND:
                case CLASS_ATOM:
 
                    /*
                     * OR-clause => AND-clause if each of A's items implies B
                     *
                     * OR-clause => atom if each of A's items implies B
                     */
                    result = true;
                    iterate_begin(citem, clause, clause_info)
                    {
                        if (!predicate_implied_by_recurse(citem, predicate,
                                                          weak))
                        {
                            result = false;
                            break;
                        }
                    }
                    iterate_end(clause_info);
                    return result;
            }
            break;
 
        case CLASS_ATOM:
            switch (pclass)
            {
                case CLASS_AND:
 
                    /*
                     * atom => AND-clause if A implies each of B's items
                     */
                    result = true;
                    iterate_begin(pitem, predicate, pred_info)
                    {
                        if (!predicate_implied_by_recurse(clause, pitem,
                                                          weak))
                        {
                            result = false;
                            break;
                        }
                    }
                    iterate_end(pred_info);
                    return result;
 
                case CLASS_OR:
 
                    /*
                     * atom => OR-clause if A implies any of B's items
                     */
                    result = false;
                    iterate_begin(pitem, predicate, pred_info)
                    {
                        if (predicate_implied_by_recurse(clause, pitem,
                                                         weak))
                        {
                            result = true;
                            break;
                        }
                    }
                    iterate_end(pred_info);
                    return result;
 
                case CLASS_ATOM:
 
                    /*
                     * atom => atom is the base case
                     */
                    return
                        predicate_implied_by_simple_clause((Expr *) predicate,
                                                           clause,
                                                           weak);
            }
            break;
    }
 
    /* can't get here */
    elog(ERROR, "predicate_classify returned a bogus value");
    return false;
}

References Assert, CLASS_AND, CLASS_ATOM, CLASS_OR, elog, ERROR, IsA, iterate_begin, iterate_end, predicate_classify(), and predicate_implied_by_simple_clause().

Referenced by predicate_implied_by(), and predicate_refuted_by_recurse().

predicate_implied_by_simple_clause()

static bool predicate_implied_by_simple_clause ( Expr *  predicate, Node *  clause, bool  weak  )

static

Definition at line 1098 of file predtest.c.

{
    /* Allow interrupting long proof attempts */
    CHECK_FOR_INTERRUPTS();
 
    /*
     * A simple and general rule is that a clause implies itself, hence we
     * check if they are equal(); this works for any kind of expression, and
     * for either implication definition.  (Actually, there is an implied
     * assumption that the functions in the expression are immutable --- but
     * this was checked for the predicate by the caller.)
     */
    if (equal((Node *) predicate, clause))
        return true;
 
    /* Next we have some clause-type-specific strategies */
    switch (nodeTag(clause))
    {
        case T_OpExpr:
            {
                OpExpr     *op = (OpExpr *) clause;
 
                /*----------
                 * For boolean x, "x = TRUE" is equivalent to "x", likewise
                 * "x = FALSE" is equivalent to "NOT x".  These can be worth
                 * checking because, while we preferentially simplify boolean
                 * comparisons down to "x" and "NOT x", the other form has to
                 * be dealt with anyway in the context of index conditions.
                 *
                 * We could likewise check whether the predicate is boolean
                 * equality to a constant; but there are no known use-cases
                 * for that at the moment, assuming that the predicate has
                 * been through constant-folding.
                 *----------
                 */
                if (op->opno == BooleanEqualOperator)
                {
                    Node       *rightop;
 
                    Assert(list_length(op->args) == 2);
                    rightop = lsecond(op->args);
                    /* We might never see null Consts here, but better check */
                    if (rightop && IsA(rightop, Const) &&
                        !((Const *) rightop)->constisnull)
                    {
                        Node       *leftop = linitial(op->args);
 
                        if (DatumGetBool(((Const *) rightop)->constvalue))
                        {
                            /* X = true implies X */
                            if (equal(predicate, leftop))
                                return true;
                        }
                        else
                        {
                            /* X = false implies NOT X */
                            if (is_notclause(predicate) &&
                                equal(get_notclausearg(predicate), leftop))
                                return true;
                        }
                    }
                }
            }
            break;
        default:
            break;
    }
 
    /* ... and some predicate-type-specific ones */
    switch (nodeTag(predicate))
    {
        case T_NullTest:
            {
                NullTest   *predntest = (NullTest *) predicate;
 
                switch (predntest->nulltesttype)
                {
                    case IS_NOT_NULL:
 
                        /*
                         * If the predicate is of the form "foo IS NOT NULL",
                         * and we are considering strong implication, we can
                         * conclude that the predicate is implied if the
                         * clause is strict for "foo", i.e., it must yield
                         * false or NULL when "foo" is NULL.  In that case
                         * truth of the clause ensures that "foo" isn't NULL.
                         * (Again, this is a safe conclusion because "foo"
                         * must be immutable.)  This doesn't work for weak
                         * implication, though.  Also, "row IS NOT NULL" does
                         * not act in the simple way we have in mind.
                         */
                        if (!weak &&
                            !predntest->argisrow &&
                            clause_is_strict_for(clause,
                                                 (Node *) predntest->arg,
                                                 true))
                            return true;
                        break;
                    case IS_NULL:
                        break;
                }
            }
            break;
        default:
            break;
    }
 
    /*
     * Finally, if both clauses are binary operator expressions, we may be
     * able to prove something using the system's knowledge about operators;
     * those proof rules are encapsulated in operator_predicate_proof().
     */
    return operator_predicate_proof(predicate, clause, false, weak);
}

References NullTest::arg, OpExpr::args, Assert, CHECK_FOR_INTERRUPTS, clause_is_strict_for(), DatumGetBool(), equal(), get_notclausearg(), IS_NOT_NULL, is_notclause(), IS_NULL, IsA, linitial, list_length(), lsecond, nodeTag, NullTest::nulltesttype, operator_predicate_proof(), and OpExpr::opno.

Referenced by predicate_implied_by_recurse().

predicate_refuted_by()

bool predicate_refuted_by	(	List *	predicate_list,
		List *	clause_list,
		bool	weak
	)

Definition at line 222 of file predtest.c.

{
    Node       *p,
               *c;
 
    if (predicate_list == NIL)
        return false;           /* no predicate: no refutation is possible */
    if (clause_list == NIL)
        return false;           /* no restriction: refutation must fail */
 
    /*
     * If either input is a single-element list, replace it with its lone
     * member; this avoids one useless level of AND-recursion.  We only need
     * to worry about this at top level, since eval_const_expressions should
     * have gotten rid of any trivial ANDs or ORs below that.
     */
    if (list_length(predicate_list) == 1)
        p = (Node *) linitial(predicate_list);
    else
        p = (Node *) predicate_list;
    if (list_length(clause_list) == 1)
        c = (Node *) linitial(clause_list);
    else
        c = (Node *) clause_list;
 
    /* And away we go ... */
    return predicate_refuted_by_recurse(c, p, weak);
}

References linitial, list_length(), NIL, and predicate_refuted_by_recurse().

Referenced by gen_partprune_steps_internal(), relation_excluded_by_constraints(), and test_predtest().

predicate_refuted_by_recurse()

static bool predicate_refuted_by_recurse ( Node *  clause, Node *  predicate, bool  weak  )

static

Definition at line 531 of file predtest.c.

{
    PredIterInfoData clause_info;
    PredIterInfoData pred_info;
    PredClass   pclass;
    Node       *not_arg;
    bool        result;
 
    /* skip through RestrictInfo */
    Assert(clause != NULL);
    if (IsA(clause, RestrictInfo))
        clause = (Node *) ((RestrictInfo *) clause)->clause;
 
    pclass = predicate_classify(predicate, &pred_info);
 
    switch (predicate_classify(clause, &clause_info))
    {
        case CLASS_AND:
            switch (pclass)
            {
                case CLASS_AND:
 
                    /*
                     * AND-clause R=> AND-clause if A refutes any of B's items
                     *
                     * Needed to handle (x AND y) R=> ((!x OR !y) AND z)
                     */
                    result = false;
                    iterate_begin(pitem, predicate, pred_info)
                    {
                        if (predicate_refuted_by_recurse(clause, pitem,
                                                         weak))
                        {
                            result = true;
                            break;
                        }
                    }
                    iterate_end(pred_info);
                    if (result)
                        return result;
 
                    /*
                     * Also check if any of A's items refutes B
                     *
                     * Needed to handle ((x OR y) AND z) R=> (!x AND !y)
                     */
                    iterate_begin(citem, clause, clause_info)
                    {
                        if (predicate_refuted_by_recurse(citem, predicate,
                                                         weak))
                        {
                            result = true;
                            break;
                        }
                    }
                    iterate_end(clause_info);
                    return result;
 
                case CLASS_OR:
 
                    /*
                     * AND-clause R=> OR-clause if A refutes each of B's items
                     */
                    result = true;
                    iterate_begin(pitem, predicate, pred_info)
                    {
                        if (!predicate_refuted_by_recurse(clause, pitem,
                                                          weak))
                        {
                            result = false;
                            break;
                        }
                    }
                    iterate_end(pred_info);
                    return result;
 
                case CLASS_ATOM:
 
                    /*
                     * If B is a NOT-type clause, A R=> B if A => B's arg
                     *
                     * Since, for either type of refutation, we are starting
                     * with the premise that A is true, we can use a strong
                     * implication test in all cases.  That proves B's arg is
                     * true, which is more than we need for weak refutation if
                     * B is a simple NOT, but it allows not worrying about
                     * exactly which kind of negation clause we have.
                     */
                    not_arg = extract_not_arg(predicate);
                    if (not_arg &&
                        predicate_implied_by_recurse(clause, not_arg,
                                                     false))
                        return true;
 
                    /*
                     * AND-clause R=> atom if any of A's items refutes B
                     */
                    result = false;
                    iterate_begin(citem, clause, clause_info)
                    {
                        if (predicate_refuted_by_recurse(citem, predicate,
                                                         weak))
                        {
                            result = true;
                            break;
                        }
                    }
                    iterate_end(clause_info);
                    return result;
            }
            break;
 
        case CLASS_OR:
            switch (pclass)
            {
                case CLASS_OR:
 
                    /*
                     * OR-clause R=> OR-clause if A refutes each of B's items
                     */
                    result = true;
                    iterate_begin(pitem, predicate, pred_info)
                    {
                        if (!predicate_refuted_by_recurse(clause, pitem,
                                                          weak))
                        {
                            result = false;
                            break;
                        }
                    }
                    iterate_end(pred_info);
                    return result;
 
                case CLASS_AND:
 
                    /*
                     * OR-clause R=> AND-clause if each of A's items refutes
                     * any of B's items.
                     */
                    result = true;
                    iterate_begin(citem, clause, clause_info)
                    {
                        bool        presult = false;
 
                        iterate_begin(pitem, predicate, pred_info)
                        {
                            if (predicate_refuted_by_recurse(citem, pitem,
                                                             weak))
                            {
                                presult = true;
                                break;
                            }
                        }
                        iterate_end(pred_info);
                        if (!presult)
                        {
                            result = false; /* citem refutes nothing */
                            break;
                        }
                    }
                    iterate_end(clause_info);
                    return result;
 
                case CLASS_ATOM:
 
                    /*
                     * If B is a NOT-type clause, A R=> B if A => B's arg
                     *
                     * Same logic as for the AND-clause case above.
                     */
                    not_arg = extract_not_arg(predicate);
                    if (not_arg &&
                        predicate_implied_by_recurse(clause, not_arg,
                                                     false))
                        return true;
 
                    /*
                     * OR-clause R=> atom if each of A's items refutes B
                     */
                    result = true;
                    iterate_begin(citem, clause, clause_info)
                    {
                        if (!predicate_refuted_by_recurse(citem, predicate,
                                                          weak))
                        {
                            result = false;
                            break;
                        }
                    }
                    iterate_end(clause_info);
                    return result;
            }
            break;
 
        case CLASS_ATOM:
 
            /*
             * If A is a strong NOT-clause, A R=> B if B => A's arg
             *
             * Since A is strong, we may assume A's arg is false (not just
             * not-true).  If B weakly implies A's arg, then B can be neither
             * true nor null, so that strong refutation is proven.  If B
             * strongly implies A's arg, then B cannot be true, so that weak
             * refutation is proven.
             */
            not_arg = extract_strong_not_arg(clause);
            if (not_arg &&
                predicate_implied_by_recurse(predicate, not_arg,
                                             !weak))
                return true;
 
            switch (pclass)
            {
                case CLASS_AND:
 
                    /*
                     * atom R=> AND-clause if A refutes any of B's items
                     */
                    result = false;
                    iterate_begin(pitem, predicate, pred_info)
                    {
                        if (predicate_refuted_by_recurse(clause, pitem,
                                                         weak))
                        {
                            result = true;
                            break;
                        }
                    }
                    iterate_end(pred_info);
                    return result;
 
                case CLASS_OR:
 
                    /*
                     * atom R=> OR-clause if A refutes each of B's items
                     */
                    result = true;
                    iterate_begin(pitem, predicate, pred_info)
                    {
                        if (!predicate_refuted_by_recurse(clause, pitem,
                                                          weak))
                        {
                            result = false;
                            break;
                        }
                    }
                    iterate_end(pred_info);
                    return result;
 
                case CLASS_ATOM:
 
                    /*
                     * If B is a NOT-type clause, A R=> B if A => B's arg
                     *
                     * Same logic as for the AND-clause case above.
                     */
                    not_arg = extract_not_arg(predicate);
                    if (not_arg &&
                        predicate_implied_by_recurse(clause, not_arg,
                                                     false))
                        return true;
 
                    /*
                     * atom R=> atom is the base case
                     */
                    return
                        predicate_refuted_by_simple_clause((Expr *) predicate,
                                                           clause,
                                                           weak);
            }
            break;
    }
 
    /* can't get here */
    elog(ERROR, "predicate_classify returned a bogus value");
    return false;
}

References Assert, CLASS_AND, CLASS_ATOM, CLASS_OR, elog, ERROR, extract_not_arg(), extract_strong_not_arg(), IsA, iterate_begin, iterate_end, predicate_classify(), predicate_implied_by_recurse(), and predicate_refuted_by_simple_clause().

Referenced by predicate_refuted_by().

predicate_refuted_by_simple_clause()

static bool predicate_refuted_by_simple_clause ( Expr *  predicate, Node *  clause, bool  weak  )

static

Definition at line 1225 of file predtest.c.

{
    /* Allow interrupting long proof attempts */
    CHECK_FOR_INTERRUPTS();
 
    /*
     * A simple clause can't refute itself, so unlike the implication case,
     * checking for equal() clauses isn't helpful.
     *
     * But relation_excluded_by_constraints() checks for self-contradictions
     * in a list of clauses, so that we may get here with predicate and clause
     * being actually pointer-equal, and that is worth eliminating quickly.
     */
    if ((Node *) predicate == clause)
        return false;
 
    /* Next we have some clause-type-specific strategies */
    switch (nodeTag(clause))
    {
        case T_NullTest:
            {
                NullTest   *clausentest = (NullTest *) clause;
 
                /* row IS NULL does not act in the simple way we have in mind */
                if (clausentest->argisrow)
                    return false;
 
                switch (clausentest->nulltesttype)
                {
                    case IS_NULL:
                        {
                            switch (nodeTag(predicate))
                            {
                                case T_NullTest:
                                    {
                                        NullTest   *predntest = (NullTest *) predicate;
 
                                        /*
                                         * row IS NULL does not act in the
                                         * simple way we have in mind
                                         */
                                        if (predntest->argisrow)
                                            return false;
 
                                        /*
                                         * foo IS NULL refutes foo IS NOT
                                         * NULL, at least in the non-row case,
                                         * for both strong and weak refutation
                                         */
                                        if (predntest->nulltesttype == IS_NOT_NULL &&
                                            equal(predntest->arg, clausentest->arg))
                                            return true;
                                    }
                                    break;
                                default:
                                    break;
                            }
 
                            /*
                             * foo IS NULL weakly refutes any predicate that
                             * is strict for foo, since then the predicate
                             * must yield false or NULL (and since foo appears
                             * in the predicate, it's known immutable).
                             */
                            if (weak &&
                                clause_is_strict_for((Node *) predicate,
                                                     (Node *) clausentest->arg,
                                                     true))
                                return true;
 
                            return false;   /* we can't succeed below... */
                        }
                        break;
                    case IS_NOT_NULL:
                        break;
                }
            }
            break;
        default:
            break;
    }
 
    /* ... and some predicate-type-specific ones */
    switch (nodeTag(predicate))
    {
        case T_NullTest:
            {
                NullTest   *predntest = (NullTest *) predicate;
 
                /* row IS NULL does not act in the simple way we have in mind */
                if (predntest->argisrow)
                    return false;
 
                switch (predntest->nulltesttype)
                {
                    case IS_NULL:
                        {
                            switch (nodeTag(clause))
                            {
                                case T_NullTest:
                                    {
                                        NullTest   *clausentest = (NullTest *) clause;
 
                                        /*
                                         * row IS NULL does not act in the
                                         * simple way we have in mind
                                         */
                                        if (clausentest->argisrow)
                                            return false;
 
                                        /*
                                         * foo IS NOT NULL refutes foo IS NULL
                                         * for both strong and weak refutation
                                         */
                                        if (clausentest->nulltesttype == IS_NOT_NULL &&
                                            equal(clausentest->arg, predntest->arg))
                                            return true;
                                    }
                                    break;
                                default:
                                    break;
                            }
 
                            /*
                             * When the predicate is of the form "foo IS
                             * NULL", we can conclude that the predicate is
                             * refuted if the clause is strict for "foo" (see
                             * notes for implication case).  That works for
                             * either strong or weak refutation.
                             */
                            if (clause_is_strict_for(clause,
                                                     (Node *) predntest->arg,
                                                     true))
                                return true;
                        }
                        break;
                    case IS_NOT_NULL:
                        break;
                }
 
                return false;   /* we can't succeed below... */
            }
            break;
        default:
            break;
    }
 
    /*
     * Finally, if both clauses are binary operator expressions, we may be
     * able to prove something using the system's knowledge about operators.
     */
    return operator_predicate_proof(predicate, clause, true, weak);
}

References NullTest::arg, CHECK_FOR_INTERRUPTS, clause_is_strict_for(), equal(), IS_NOT_NULL, IS_NULL, nodeTag, NullTest::nulltesttype, and operator_predicate_proof().

Referenced by predicate_refuted_by_recurse().

Variable Documentation

BT_implic_table

const StrategyNumber BT_implic_table[6][6]

static

Initial value:

= {
 
    {BTGE, BTGE, none, none, none, BTGE},   
    {BTGT, BTGE, none, none, none, BTGT},   
    {BTGT, BTGE, BTEQ, BTLE, BTLT, BTNE},   
    {none, none, none, BTLE, BTLT, BTLT},   
    {none, none, none, BTLE, BTLE, BTLE},   
    {none, none, none, none, none, BTEQ}    
}

Definition at line 1698 of file predtest.c.

Referenced by lookup_proof_cache().

BT_implies_table

const bool BT_implies_table[6][6]

static

Initial value:

= {
 
    {true, true, none, none, none, true},   
    {none, true, none, none, none, none},   
    {none, true, true, true, none, none},   
    {none, none, none, true, none, none},   
    {none, none, none, true, true, true},   
    {none, none, none, none, none, true}    
}

Definition at line 1672 of file predtest.c.

Referenced by lookup_proof_cache().

BT_refute_table

const StrategyNumber BT_refute_table[6][6]

static

Initial value:

= {
 
    {none, none, BTGE, BTGE, BTGE, none},   
    {none, none, BTGT, BTGT, BTGE, none},   
    {BTLE, BTLT, BTNE, BTGT, BTGE, BTEQ},   
    {BTLE, BTLT, BTLT, none, none, none},   
    {BTLE, BTLE, BTLE, none, none, none},   
    {none, none, BTEQ, none, none, none}    
}

Definition at line 1711 of file predtest.c.

Referenced by lookup_proof_cache().

BT_refutes_table

const bool BT_refutes_table[6][6]

static

Initial value:

= {
 
    {none, none, true, true, true, none},   
    {none, none, none, none, true, none},   
    {true, none, none, none, true, true},   
    {true, none, none, none, none, none},   
    {true, true, true, none, none, none},   
    {none, none, true, none, none, none}    
}

Definition at line 1685 of file predtest.c.

Referenced by lookup_proof_cache().

OprProofCacheHash

HTAB* OprProofCacheHash = NULL

static

Definition at line 2093 of file predtest.c.

Referenced by InvalidateOprProofCacheCallBack(), and lookup_proof_cache().