This simple refactoring patch moves all of the code associated with
Partial Index planning into a single file. This isolates it from other
code changes that may take place over the next few months, as well as
setting the scene for a number of changes that will hopefully take place
with that code.
This should allow work to continue on this undisturbed; more work will
happen within the 8.1 window, so please approve this patch to cvstip
now.
Changes likely on this code are
- redesigning the low level routines to allow them to perform their
stuff for both Partial Index and Constraint-based elimination (aka
Partitioning...)
- allowing equivalence class re-write
- allow handling for r-tree operators
- maybe GIST also??
Better to do this change now, than try to do it when code gets more
complex.
- Passes make check on current cvstip.
- No functional code changes of any kind, just moving between modules.
Changes:
- code removal from indxpath.c
- code addition to new module predtest.c
- no changes required to header files
- update Makefile
Best Regards, Simon Riggs
Index: src/backend/optimizer/path/Makefile
===================================================================
RCS file: /projects/cvsroot/pgsql/src/backend/optimizer/path/Makefile,v
retrieving revision 1.16
diff -c -c -r1.16 Makefile
*** src/backend/optimizer/path/Makefile 29 Nov 2003 19:51:50 -0000 1.16
--- src/backend/optimizer/path/Makefile 6 Jun 2005 17:33:21 -0000
***************
*** 12,19 ****
top_builddir = ../../../..
include $(top_builddir)/src/Makefile.global
! OBJS = allpaths.o clausesel.o costsize.o indxpath.o \
! joinpath.o joinrels.o orindxpath.o pathkeys.o tidpath.o
all: SUBSYS.o
--- 12,19 ----
top_builddir = ../../../..
include $(top_builddir)/src/Makefile.global
! OBJS = allpaths.o clausesel.o costsize.o indxpath.o joinpath.o \
! joinrels.o orindxpath.o pathkeys.o predtest.o tidpath.o
all: SUBSYS.o
Index: src/backend/optimizer/path/indxpath.c
===================================================================
RCS file: /projects/cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v
retrieving revision 1.181
diff -c -c -r1.181 indxpath.c
*** src/backend/optimizer/path/indxpath.c 5 Jun 2005 22:32:55 -0000 1.181
--- src/backend/optimizer/path/indxpath.c 6 Jun 2005 17:33:23 -0000
***************
*** 68,75 ****
Relids outer_relids);
static Oid indexable_operator(Expr *clause, Oid opclass,
bool indexkey_on_left);
- static bool pred_test_recurse(Node *clause, Node *predicate);
- static bool pred_test_simple_clause(Expr *predicate, Node *clause);
static Relids indexable_outerrelids(RelOptInfo *rel);
static bool list_matches_any_index(List *clauses, RelOptInfo *rel,
Relids outer_relids);
--- 68,73 ----
***************
*** 855,1541 ****
}
/****************************************************************************
- * ---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS ----
- ****************************************************************************/
-
- /*
- * check_partial_indexes
- * Check each partial index of the relation, and mark it predOK or not
- * depending on whether the predicate is satisfied for this query.
- */
- void
- check_partial_indexes(PlannerInfo *root, RelOptInfo *rel)
- {
- List *restrictinfo_list = rel->baserestrictinfo;
- ListCell *ilist;
-
- foreach(ilist, rel->indexlist)
- {
- IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
-
- /*
- * If this is a partial index, we can only use it if it passes the
- * predicate test.
- */
- if (index->indpred == NIL)
- continue; /* ignore non-partial indexes */
-
- index->predOK = pred_test(index->indpred, restrictinfo_list);
- }
- }
-
- /*
- * pred_test
- * Does the "predicate inclusion test" for partial indexes.
- *
- * Recursively checks whether the clauses in restrictinfo_list imply
- * that the given predicate is true.
- *
- * The top-level List structure of each list corresponds to an AND list.
- * We assume that eval_const_expressions() has been applied and so there
- * are no un-flattened ANDs or ORs (e.g., no AND immediately within an AND,
- * including AND just below the top-level List structure).
- * If this is not true we might fail to prove an implication that is
- * valid, but no worse consequences will ensue.
- */
- bool
- pred_test(List *predicate_list, List *restrictinfo_list)
- {
- ListCell *item;
-
- /*
- * Note: if Postgres tried to optimize queries by forming equivalence
- * classes over equi-joined attributes (i.e., if it recognized that a
- * qualification such as "where a.b=c.d and a.b=5" could make use of
- * an index on c.d), then we could use that equivalence class info
- * here with joininfo_list to do more complete tests for the usability
- * of a partial index. For now, the test only uses restriction
- * clauses (those in restrictinfo_list). --Nels, Dec '92
- *
- * XXX as of 7.1, equivalence class info *is* available. Consider
- * improving this code as foreseen by Nels.
- */
-
- if (predicate_list == NIL)
- return true; /* no predicate: the index is usable */
- if (restrictinfo_list == NIL)
- return false; /* no restriction clauses: the test must
- * fail */
-
- /*
- * In all cases where the predicate is an AND-clause, pred_test_recurse()
- * will prefer to iterate over the predicate's components. So we can
- * just do that to start with here, and eliminate the need for
- * pred_test_recurse() to handle a bare List on the predicate side.
- *
- * Logic is: restriction must imply each of the AND'ed predicate items.
- */
- foreach(item, predicate_list)
- {
- if (!pred_test_recurse((Node *) restrictinfo_list, lfirst(item)))
- return false;
- }
- return true;
- }
-
-
- /*----------
- * pred_test_recurse
- * Does the "predicate inclusion test" for non-NULL restriction and
- * predicate clauses.
- *
- * The logic followed here is ("=>" means "implies"):
- * atom A => atom B iff: pred_test_simple_clause says so
- * atom A => AND-expr B iff: A => each of B's components
- * atom A => OR-expr B iff: A => any of B's components
- * AND-expr A => atom B iff: any of A's components => B
- * AND-expr A => AND-expr B iff: A => each of B's components
- * AND-expr A => OR-expr B iff: A => any of B's components,
- * *or* any of A's components => B
- * OR-expr A => atom B iff: each of A's components => B
- * OR-expr A => AND-expr B iff: A => each of B's components
- * OR-expr A => OR-expr B iff: each of A's components => any of B's
- *
- * An "atom" is anything other than an AND or OR node. Notice that we don't
- * have any special logic to handle NOT nodes; these should have been pushed
- * down or eliminated where feasible by prepqual.c.
- *
- * We can't recursively expand either side first, but have to interleave
- * the expansions per the above rules, to be sure we handle all of these
- * examples:
- * (x OR y) => (x OR y OR z)
- * (x AND y AND z) => (x AND y)
- * (x AND y) => ((x AND y) OR z)
- * ((x OR y) AND z) => (x OR y)
- * This is still not an exhaustive test, but it handles most normal cases
- * under the assumption that both inputs have been AND/OR flattened.
- *
- * A bare List node on the restriction side is interpreted as an AND clause,
- * in order to handle the top-level restriction List properly. However we
- * need not consider a List on the predicate side since pred_test() already
- * expanded it.
- *
- * We have to be prepared to handle RestrictInfo nodes in the restrictinfo
- * tree, though not in the predicate tree.
- *----------
- */
- static bool
- pred_test_recurse(Node *clause, Node *predicate)
- {
- ListCell *item;
-
- Assert(clause != NULL);
- /* skip through RestrictInfo */
- if (IsA(clause, RestrictInfo))
- {
- clause = (Node *) ((RestrictInfo *) clause)->clause;
- Assert(clause != NULL);
- Assert(!IsA(clause, RestrictInfo));
- }
- Assert(predicate != NULL);
-
- /*
- * Since a restriction List clause is handled the same as an AND clause,
- * we can avoid duplicate code like this:
- */
- if (and_clause(clause))
- clause = (Node *) ((BoolExpr *) clause)->args;
-
- if (IsA(clause, List))
- {
- if (and_clause(predicate))
- {
- /* AND-clause => AND-clause if A implies each of B's items */
- foreach(item, ((BoolExpr *) predicate)->args)
- {
- if (!pred_test_recurse(clause, lfirst(item)))
- return false;
- }
- return true;
- }
- else if (or_clause(predicate))
- {
- /* AND-clause => OR-clause if A implies any of B's items */
- /* Needed to handle (x AND y) => ((x AND y) OR z) */
- foreach(item, ((BoolExpr *) predicate)->args)
- {
- if (pred_test_recurse(clause, lfirst(item)))
- return true;
- }
- /* Also check if any of A's items implies B */
- /* Needed to handle ((x OR y) AND z) => (x OR y) */
- foreach(item, (List *) clause)
- {
- if (pred_test_recurse(lfirst(item), predicate))
- return true;
- }
- return false;
- }
- else
- {
- /* AND-clause => atom if any of A's items implies B */
- foreach(item, (List *) clause)
- {
- if (pred_test_recurse(lfirst(item), predicate))
- return true;
- }
- return false;
- }
- }
- else if (or_clause(clause))
- {
- if (or_clause(predicate))
- {
- /*
- * 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.
- */
- foreach(item, ((BoolExpr *) clause)->args)
- {
- Node *citem = lfirst(item);
- ListCell *item2;
-
- foreach(item2, ((BoolExpr *) predicate)->args)
- {
- if (pred_test_recurse(citem, lfirst(item2)))
- break;
- }
- if (item2 == NULL)
- return false; /* doesn't imply any of B's */
- }
- return true;
- }
- else
- {
- /* OR-clause => AND-clause if each of A's items implies B */
- /* OR-clause => atom if each of A's items implies B */
- foreach(item, ((BoolExpr *) clause)->args)
- {
- if (!pred_test_recurse(lfirst(item), predicate))
- return false;
- }
- return true;
- }
- }
- else
- {
- if (and_clause(predicate))
- {
- /* atom => AND-clause if A implies each of B's items */
- foreach(item, ((BoolExpr *) predicate)->args)
- {
- if (!pred_test_recurse(clause, lfirst(item)))
- return false;
- }
- return true;
- }
- else if (or_clause(predicate))
- {
- /* atom => OR-clause if A implies any of B's items */
- foreach(item, ((BoolExpr *) predicate)->args)
- {
- if (pred_test_recurse(clause, lfirst(item)))
- return true;
- }
- return false;
- }
- else
- {
- /* atom => atom is the base case */
- return pred_test_simple_clause((Expr *) predicate, clause);
- }
- }
- }
-
-
- /*
- * Define an "operator implication table" for btree operators ("strategies").
- *
- * The strategy numbers defined by btree indexes (see access/skey.h) are:
- * (1) < (2) <= (3) = (4) >= (5) >
- * and in addition we use (6) to represent <>. <> is not a btree-indexable
- * operator, but we assume here that if the equality operator of a btree
- * opclass has a negator operator, the negator behaves as <> for the opclass.
- *
- * The interpretation of:
- *
- * test_op = BT_implic_table[given_op-1][target_op-1]
- *
- * where test_op, given_op and target_op are strategy numbers (from 1 to 6)
- * of btree operators, is as follows:
- *
- * If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you
- * want to determine whether "ATTR target_op CONST2" must also be true, then
- * you can use "CONST2 test_op CONST1" as a test. If this test returns true,
- * then the target expression must be true; if the test returns false, then
- * the target expression may be false.
- *
- * An entry where test_op == 0 means the implication cannot be determined,
- * i.e., this test should always be considered false.
- */
-
- #define BTLT BTLessStrategyNumber
- #define BTLE BTLessEqualStrategyNumber
- #define BTEQ BTEqualStrategyNumber
- #define BTGE BTGreaterEqualStrategyNumber
- #define BTGT BTGreaterStrategyNumber
- #define BTNE 6
-
- static const StrategyNumber
- BT_implic_table[6][6] = {
- /*
- * The target operator:
- *
- * LT LE EQ GE GT NE
- */
- {BTGE, BTGE, 0, 0, 0, BTGE}, /* LT */
- {BTGT, BTGE, 0, 0, 0, BTGT}, /* LE */
- {BTGT, BTGE, BTEQ, BTLE, BTLT, BTNE}, /* EQ */
- {0, 0, 0, BTLE, BTLT, BTLT}, /* GE */
- {0, 0, 0, BTLE, BTLE, BTLE}, /* GT */
- {0, 0, 0, 0, 0, BTEQ} /* NE */
- };
-
-
- /*----------
- * pred_test_simple_clause
- * Does the "predicate inclusion test" for a "simple clause" predicate
- * and a "simple clause" restriction.
- *
- * We have three strategies for determining whether one simple clause
- * implies another:
- *
- * A simple and general way is to see if they are equal(); this works for any
- * kind of expression. (Actually, there is an implied assumption that the
- * functions in the expression are immutable, ie dependent only on their input
- * arguments --- but this was checked for the predicate by CheckPredicate().)
- *
- * When the predicate is of the form "foo IS NOT NULL", we can conclude that
- * the predicate is implied if the clause is a strict operator or function
- * that has "foo" as an input. In this case the clause must yield NULL when
- * "foo" is NULL, which we can take as equivalent to FALSE because we know
- * we are within an AND/OR subtree of a WHERE clause. (Again, "foo" is
- * already known immutable, so the clause will certainly always fail.)
- *
- * Our other way works only for binary boolean opclauses of the form
- * "foo op constant", where "foo" is the same in both clauses. The operators
- * and constants can be different but the operators must be in the same btree
- * operator class. We use the above operator implication table to be able to
- * derive implications between nonidentical clauses. (Note: "foo" is known
- * immutable, and constants are surely immutable, but we have to check that
- * the operators are too. As of 8.0 it's possible for opclasses to contain
- * operators that are merely stable, and we dare not make deductions with
- * these.)
- *
- * Eventually, rtree operators could also be handled by defining an
- * appropriate "RT_implic_table" array.
- *----------
- */
- static bool
- pred_test_simple_clause(Expr *predicate, Node *clause)
- {
- Node *leftop,
- *rightop;
- Node *pred_var,
- *clause_var;
- Const *pred_const,
- *clause_const;
- bool pred_var_on_left,
- clause_var_on_left,
- pred_op_negated;
- Oid pred_op,
- clause_op,
- pred_op_negator,
- clause_op_negator,
- test_op = InvalidOid;
- Oid opclass_id;
- bool found = false;
- StrategyNumber pred_strategy,
- clause_strategy,
- test_strategy;
- Oid clause_subtype;
- Expr *test_expr;
- ExprState *test_exprstate;
- Datum test_result;
- bool isNull;
- CatCList *catlist;
- int i;
- EState *estate;
- MemoryContext oldcontext;
-
- /* First try the equal() test */
- if (equal((Node *) predicate, clause))
- return true;
-
- /* Next try the IS NOT NULL case */
- if (predicate && IsA(predicate, NullTest) &&
- ((NullTest *) predicate)->nulltesttype == IS_NOT_NULL)
- {
- Expr *nonnullarg = ((NullTest *) predicate)->arg;
-
- if (is_opclause(clause) &&
- list_member(((OpExpr *) clause)->args, nonnullarg) &&
- op_strict(((OpExpr *) clause)->opno))
- return true;
- if (is_funcclause(clause) &&
- list_member(((FuncExpr *) clause)->args, nonnullarg) &&
- func_strict(((FuncExpr *) clause)->funcid))
- return true;
- return false; /* we can't succeed below... */
- }
-
- /*
- * Can't do anything more unless they are both binary opclauses with a
- * Const on one side, and identical subexpressions on the other sides.
- * Note we don't have to think about binary relabeling of the Const
- * node, since that would have been folded right into the Const.
- *
- * If either Const is null, we also fail right away; this assumes that
- * the test operator will always be strict.
- */
- if (!is_opclause(predicate))
- return false;
- leftop = get_leftop(predicate);
- rightop = get_rightop(predicate);
- if (rightop == NULL)
- return false; /* not a binary opclause */
- if (IsA(rightop, Const))
- {
- pred_var = leftop;
- pred_const = (Const *) rightop;
- pred_var_on_left = true;
- }
- else if (IsA(leftop, Const))
- {
- pred_var = rightop;
- pred_const = (Const *) leftop;
- pred_var_on_left = false;
- }
- else
- return false; /* no Const to be found */
- if (pred_const->constisnull)
- return false;
-
- if (!is_opclause(clause))
- return false;
- leftop = get_leftop((Expr *) clause);
- rightop = get_rightop((Expr *) clause);
- if (rightop == NULL)
- return false; /* not a binary opclause */
- if (IsA(rightop, Const))
- {
- clause_var = leftop;
- clause_const = (Const *) rightop;
- clause_var_on_left = true;
- }
- else if (IsA(leftop, Const))
- {
- clause_var = rightop;
- clause_const = (Const *) leftop;
- clause_var_on_left = false;
- }
- else
- return false; /* no Const to be found */
- if (clause_const->constisnull)
- return false;
-
- /*
- * Check for matching subexpressions on the non-Const sides. We used
- * to only allow a simple Var, but it's about as easy to allow any
- * expression. Remember we already know that the pred expression does
- * not contain any non-immutable functions, so identical expressions
- * should yield identical results.
- */
- if (!equal(pred_var, clause_var))
- return false;
-
- /*
- * Okay, get the operators in the two clauses we're comparing. Commute
- * them if needed so that we can assume the variables are on the left.
- */
- pred_op = ((OpExpr *) predicate)->opno;
- if (!pred_var_on_left)
- {
- pred_op = get_commutator(pred_op);
- if (!OidIsValid(pred_op))
- return false;
- }
-
- clause_op = ((OpExpr *) clause)->opno;
- if (!clause_var_on_left)
- {
- clause_op = get_commutator(clause_op);
- if (!OidIsValid(clause_op))
- return false;
- }
-
- /*
- * Try to find a btree opclass containing the needed operators.
- *
- * We must find a btree opclass that contains both operators, else the
- * implication can't be determined. Also, the pred_op has to be of
- * default subtype (implying left and right input datatypes are the
- * same); otherwise it's unsafe to put the pred_const on the left side
- * of the test. Also, the opclass must contain a suitable test
- * operator matching the clause_const's type (which we take to mean
- * that it has the same subtype as the original clause_operator).
- *
- * If there are multiple matching opclasses, 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 opclasses.
- */
- catlist = SearchSysCacheList(AMOPOPID, 1,
- ObjectIdGetDatum(pred_op),
- 0, 0, 0);
-
- /*
- * If we couldn't find any opclass containing the pred_op, perhaps it
- * is a <> operator. See if it has a negator that is in an opclass.
- */
- pred_op_negated = false;
- if (catlist->n_members == 0)
- {
- pred_op_negator = get_negator(pred_op);
- if (OidIsValid(pred_op_negator))
- {
- pred_op_negated = true;
- ReleaseSysCacheList(catlist);
- catlist = SearchSysCacheList(AMOPOPID, 1,
- ObjectIdGetDatum(pred_op_negator),
- 0, 0, 0);
- }
- }
-
- /* Also may need the clause_op's negator */
- clause_op_negator = get_negator(clause_op);
-
- /* Now search the opclasses */
- for (i = 0; i < catlist->n_members; i++)
- {
- HeapTuple pred_tuple = &catlist->members[i]->tuple;
- Form_pg_amop pred_form = (Form_pg_amop) GETSTRUCT(pred_tuple);
- HeapTuple clause_tuple;
-
- opclass_id = pred_form->amopclaid;
-
- /* must be btree */
- if (!opclass_is_btree(opclass_id))
- continue;
- /* predicate operator must be default within this opclass */
- if (pred_form->amopsubtype != InvalidOid)
- continue;
-
- /* Get the predicate operator's btree strategy number */
- pred_strategy = (StrategyNumber) pred_form->amopstrategy;
- Assert(pred_strategy >= 1 && pred_strategy <= 5);
-
- if (pred_op_negated)
- {
- /* Only consider negators that are = */
- if (pred_strategy != BTEqualStrategyNumber)
- continue;
- pred_strategy = BTNE;
- }
-
- /*
- * From the same opclass, find a strategy number for the
- * clause_op, if possible
- */
- clause_tuple = SearchSysCache(AMOPOPID,
- ObjectIdGetDatum(clause_op),
- ObjectIdGetDatum(opclass_id),
- 0, 0);
- if (HeapTupleIsValid(clause_tuple))
- {
- Form_pg_amop clause_form = (Form_pg_amop) GETSTRUCT(clause_tuple);
-
- /* Get the restriction clause operator's strategy/subtype */
- clause_strategy = (StrategyNumber) clause_form->amopstrategy;
- Assert(clause_strategy >= 1 && clause_strategy <= 5);
- clause_subtype = clause_form->amopsubtype;
- ReleaseSysCache(clause_tuple);
- }
- else if (OidIsValid(clause_op_negator))
- {
- clause_tuple = SearchSysCache(AMOPOPID,
- ObjectIdGetDatum(clause_op_negator),
- ObjectIdGetDatum(opclass_id),
- 0, 0);
- if (HeapTupleIsValid(clause_tuple))
- {
- Form_pg_amop clause_form = (Form_pg_amop) GETSTRUCT(clause_tuple);
-
- /* Get the restriction clause operator's strategy/subtype */
- clause_strategy = (StrategyNumber) clause_form->amopstrategy;
- Assert(clause_strategy >= 1 && clause_strategy <= 5);
- clause_subtype = clause_form->amopsubtype;
- ReleaseSysCache(clause_tuple);
-
- /* Only consider negators that are = */
- if (clause_strategy != BTEqualStrategyNumber)
- continue;
- clause_strategy = BTNE;
- }
- else
- continue;
- }
- else
- continue;
-
- /*
- * Look up the "test" strategy number in the implication table
- */
- 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 opclass has an operator for the test strategy and the
- * clause datatype.
- */
- if (test_strategy == BTNE)
- {
- test_op = get_opclass_member(opclass_id, clause_subtype,
- BTEqualStrategyNumber);
- if (OidIsValid(test_op))
- test_op = get_negator(test_op);
- }
- else
- {
- test_op = get_opclass_member(opclass_id, clause_subtype,
- test_strategy);
- }
- if (OidIsValid(test_op))
- {
- /*
- * 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 must be immutable, else it
- * would not be allowed in an index predicate.) Essentially
- * we are assuming that the opclass is consistent even if it
- * contains operators that are merely stable.
- */
- if (op_volatile(test_op) == PROVOLATILE_IMMUTABLE)
- {
- found = true;
- break;
- }
- }
- }
-
- ReleaseSysCacheList(catlist);
-
- if (!found)
- {
- /* couldn't find a btree opclass to interpret the operators */
- 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);
-
- /* Prepare it for execution */
- test_exprstate = ExecPrepareExpr(test_expr, estate);
-
- /* And execute it. */
- test_result = ExecEvalExprSwitchContext(test_exprstate,
- GetPerTupleExprContext(estate),
- &isNull, NULL);
-
- /* Get back to outer memory context */
- MemoryContextSwitchTo(oldcontext);
-
- /* Release all the junk we just created */
- FreeExecutorState(estate);
-
- if (isNull)
- {
- /* Treat a null result as false ... but it's a tad fishy ... */
- elog(DEBUG2, "null predicate test result");
- return false;
- }
- return DatumGetBool(test_result);
- }
-
-
- /****************************************************************************
* ---- ROUTINES TO CHECK JOIN CLAUSES ----
****************************************************************************/
--- 853,858 ----
/*-------------------------------------------------------------------------
*
* predtest.c
* Routines to test a predicate against a query Restriction, using
* logical proof at plan time, rather than evaluation at execution time.
*
* Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
*
* IDENTIFICATION
* $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.181 2005/06/05 22:32:55 tgl Exp $
*
*-------------------------------------------------------------------------
*/
#include "postgres.h"
#include <math.h>
#include "access/nbtree.h"
#include "catalog/pg_amop.h"
#include "catalog/pg_namespace.h"
#include "catalog/pg_opclass.h"
#include "catalog/pg_operator.h"
#include "catalog/pg_proc.h"
#include "catalog/pg_type.h"
#include "executor/executor.h"
#include "nodes/makefuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/restrictinfo.h"
#include "optimizer/var.h"
#include "parser/parse_expr.h"
#include "rewrite/rewriteManip.h"
#include "utils/builtins.h"
#include "utils/catcache.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/pg_locale.h"
#include "utils/selfuncs.h"
#include "utils/syscache.h"
static bool pred_test_recurse(Node *clause, Node *predicate);
static bool pred_test_simple_clause(Expr *predicate, Node *clause);
/****************************************************************************
* ---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS ----
****************************************************************************/
/*
* check_partial_indexes
* Check each partial index of the relation, and mark it predOK or not
* depending on whether the predicate is satisfied for this query.
*/
void
check_partial_indexes(PlannerInfo *root, RelOptInfo *rel)
{
List *restrictinfo_list = rel->baserestrictinfo;
ListCell *ilist;
foreach(ilist, rel->indexlist)
{
IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
/*
* If this is a partial index, we can only use it if it passes the
* predicate test.
*/
if (index->indpred == NIL)
continue; /* ignore non-partial indexes */
index->predOK = pred_test(index->indpred, restrictinfo_list);
}
}
/*
* pred_test
* Does the "predicate inclusion test" for partial indexes.
*
* Recursively checks whether the clauses in restrictinfo_list imply
* that the given predicate is true.
*
* The top-level List structure of each list corresponds to an AND list.
* We assume that eval_const_expressions() has been applied and so there
* are no un-flattened ANDs or ORs (e.g., no AND immediately within an AND,
* including AND just below the top-level List structure).
* If this is not true we might fail to prove an implication that is
* valid, but no worse consequences will ensue.
*/
bool
pred_test(List *predicate_list, List *restrictinfo_list)
{
ListCell *item;
/*
* Note: if Postgres tried to optimize queries by forming equivalence
* classes over equi-joined attributes (i.e., if it recognized that a
* qualification such as "where a.b=c.d and a.b=5" could make use of
* an index on c.d), then we could use that equivalence class info
* here with joininfo_list to do more complete tests for the usability
* of a partial index. For now, the test only uses restriction
* clauses (those in restrictinfo_list). --Nels, Dec '92
*
* XXX as of 7.1, equivalence class info *is* available. Consider
* improving this code as foreseen by Nels.
*/
if (predicate_list == NIL)
return true; /* no predicate: the index is usable */
if (restrictinfo_list == NIL)
return false; /* no restriction clauses: the test must
* fail */
/*
* In all cases where the predicate is an AND-clause, pred_test_recurse()
* will prefer to iterate over the predicate's components. So we can
* just do that to start with here, and eliminate the need for
* pred_test_recurse() to handle a bare List on the predicate side.
*
* Logic is: restriction must imply each of the AND'ed predicate items.
*/
foreach(item, predicate_list)
{
if (!pred_test_recurse((Node *) restrictinfo_list, lfirst(item)))
return false;
}
return true;
}
/*----------
* pred_test_recurse
* Does the "predicate inclusion test" for non-NULL restriction and
* predicate clauses.
*
* The logic followed here is ("=>" means "implies"):
* atom A => atom B iff: pred_test_simple_clause says so
* atom A => AND-expr B iff: A => each of B's components
* atom A => OR-expr B iff: A => any of B's components
* AND-expr A => atom B iff: any of A's components => B
* AND-expr A => AND-expr B iff: A => each of B's components
* AND-expr A => OR-expr B iff: A => any of B's components,
* *or* any of A's components => B
* OR-expr A => atom B iff: each of A's components => B
* OR-expr A => AND-expr B iff: A => each of B's components
* OR-expr A => OR-expr B iff: each of A's components => any of B's
*
* An "atom" is anything other than an AND or OR node. Notice that we don't
* have any special logic to handle NOT nodes; these should have been pushed
* down or eliminated where feasible by prepqual.c.
*
* We can't recursively expand either side first, but have to interleave
* the expansions per the above rules, to be sure we handle all of these
* examples:
* (x OR y) => (x OR y OR z)
* (x AND y AND z) => (x AND y)
* (x AND y) => ((x AND y) OR z)
* ((x OR y) AND z) => (x OR y)
* This is still not an exhaustive test, but it handles most normal cases
* under the assumption that both inputs have been AND/OR flattened.
*
* A bare List node on the restriction side is interpreted as an AND clause,
* in order to handle the top-level restriction List properly. However we
* need not consider a List on the predicate side since pred_test() already
* expanded it.
*
* We have to be prepared to handle RestrictInfo nodes in the restrictinfo
* tree, though not in the predicate tree.
*----------
*/
static bool
pred_test_recurse(Node *clause, Node *predicate)
{
ListCell *item;
Assert(clause != NULL);
/* skip through RestrictInfo */
if (IsA(clause, RestrictInfo))
{
clause = (Node *) ((RestrictInfo *) clause)->clause;
Assert(clause != NULL);
Assert(!IsA(clause, RestrictInfo));
}
Assert(predicate != NULL);
/*
* Since a restriction List clause is handled the same as an AND clause,
* we can avoid duplicate code like this:
*/
if (and_clause(clause))
clause = (Node *) ((BoolExpr *) clause)->args;
if (IsA(clause, List))
{
if (and_clause(predicate))
{
/* AND-clause => AND-clause if A implies each of B's items */
foreach(item, ((BoolExpr *) predicate)->args)
{
if (!pred_test_recurse(clause, lfirst(item)))
return false;
}
return true;
}
else if (or_clause(predicate))
{
/* AND-clause => OR-clause if A implies any of B's items */
/* Needed to handle (x AND y) => ((x AND y) OR z) */
foreach(item, ((BoolExpr *) predicate)->args)
{
if (pred_test_recurse(clause, lfirst(item)))
return true;
}
/* Also check if any of A's items implies B */
/* Needed to handle ((x OR y) AND z) => (x OR y) */
foreach(item, (List *) clause)
{
if (pred_test_recurse(lfirst(item), predicate))
return true;
}
return false;
}
else
{
/* AND-clause => atom if any of A's items implies B */
foreach(item, (List *) clause)
{
if (pred_test_recurse(lfirst(item), predicate))
return true;
}
return false;
}
}
else if (or_clause(clause))
{
if (or_clause(predicate))
{
/*
* 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.
*/
foreach(item, ((BoolExpr *) clause)->args)
{
Node *citem = lfirst(item);
ListCell *item2;
foreach(item2, ((BoolExpr *) predicate)->args)
{
if (pred_test_recurse(citem, lfirst(item2)))
break;
}
if (item2 == NULL)
return false; /* doesn't imply any of B's */
}
return true;
}
else
{
/* OR-clause => AND-clause if each of A's items implies B */
/* OR-clause => atom if each of A's items implies B */
foreach(item, ((BoolExpr *) clause)->args)
{
if (!pred_test_recurse(lfirst(item), predicate))
return false;
}
return true;
}
}
else
{
if (and_clause(predicate))
{
/* atom => AND-clause if A implies each of B's items */
foreach(item, ((BoolExpr *) predicate)->args)
{
if (!pred_test_recurse(clause, lfirst(item)))
return false;
}
return true;
}
else if (or_clause(predicate))
{
/* atom => OR-clause if A implies any of B's items */
foreach(item, ((BoolExpr *) predicate)->args)
{
if (pred_test_recurse(clause, lfirst(item)))
return true;
}
return false;
}
else
{
/* atom => atom is the base case */
return pred_test_simple_clause((Expr *) predicate, clause);
}
}
}
/*
* Define an "operator implication table" for btree operators ("strategies").
*
* The strategy numbers defined by btree indexes (see access/skey.h) are:
* (1) < (2) <= (3) = (4) >= (5) >
* and in addition we use (6) to represent <>. <> is not a btree-indexable
* operator, but we assume here that if the equality operator of a btree
* opclass has a negator operator, the negator behaves as <> for the opclass.
*
* The interpretation of:
*
* test_op = BT_implic_table[given_op-1][target_op-1]
*
* where test_op, given_op and target_op are strategy numbers (from 1 to 6)
* of btree operators, is as follows:
*
* If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you
* want to determine whether "ATTR target_op CONST2" must also be true, then
* you can use "CONST2 test_op CONST1" as a test. If this test returns true,
* then the target expression must be true; if the test returns false, then
* the target expression may be false.
*
* An entry where test_op == 0 means the implication cannot be determined,
* i.e., this test should always be considered false.
*/
#define BTLT BTLessStrategyNumber
#define BTLE BTLessEqualStrategyNumber
#define BTEQ BTEqualStrategyNumber
#define BTGE BTGreaterEqualStrategyNumber
#define BTGT BTGreaterStrategyNumber
#define BTNE 6
static const StrategyNumber
BT_implic_table[6][6] = {
/*
* The target operator:
*
* LT LE EQ GE GT NE
*/
{BTGE, BTGE, 0 , 0 , 0 , BTGE}, /* LT */
{BTGT, BTGE, 0 , 0 , 0 , BTGT}, /* LE */
{BTGT, BTGE, BTEQ, BTLE, BTLT, BTNE}, /* EQ */
{0 , 0 , 0 , BTLE, BTLT, BTLT}, /* GE */
{0 , 0 , 0 , BTLE, BTLE, BTLE}, /* GT */
{0 , 0 , 0 , 0 , 0 , BTEQ} /* NE */
};
/*----------
* pred_test_simple_clause
* Does the "predicate inclusion test" for a "simple clause" predicate
* and a "simple clause" restriction.
*
* We have three strategies for determining whether one simple clause
* implies another:
*
* A simple and general way is to see if they are equal(); this works for any
* kind of expression. (Actually, there is an implied assumption that the
* functions in the expression are immutable, ie dependent only on their input
* arguments --- but this was checked for the predicate by CheckPredicate().)
*
* When the predicate is of the form "foo IS NOT NULL", we can conclude that
* the predicate is implied if the clause is a strict operator or function
* that has "foo" as an input. In this case the clause must yield NULL when
* "foo" is NULL, which we can take as equivalent to FALSE because we know
* we are within an AND/OR subtree of a WHERE clause. (Again, "foo" is
* already known immutable, so the clause will certainly always fail.)
*
* Our other way works only for binary boolean opclauses of the form
* "foo op constant", where "foo" is the same in both clauses. The operators
* and constants can be different but the operators must be in the same btree
* operator class. We use the above operator implication table to be able to
* derive implications between nonidentical clauses. (Note: "foo" is known
* immutable, and constants are surely immutable, but we have to check that
* the operators are too. As of 8.0 it's possible for opclasses to contain
* operators that are merely stable, and we dare not make deductions with
* these.)
*
* Eventually, rtree operators could also be handled by defining an
* appropriate "RT_implic_table" array.
*----------
*/
static bool
pred_test_simple_clause(Expr *predicate, Node *clause)
{
Node *leftop,
*rightop;
Node *pred_var,
*clause_var;
Const *pred_const,
*clause_const;
bool pred_var_on_left,
clause_var_on_left,
pred_op_negated;
Oid pred_op,
clause_op,
pred_op_negator,
clause_op_negator,
test_op = InvalidOid;
Oid opclass_id;
bool found = false;
StrategyNumber pred_strategy,
clause_strategy,
test_strategy;
Oid clause_subtype;
Expr *test_expr;
ExprState *test_exprstate;
Datum test_result;
bool isNull;
CatCList *catlist;
int i;
EState *estate;
MemoryContext oldcontext;
/* First try the equal() test */
if (equal((Node *) predicate, clause))
return true;
/* Next try the IS NOT NULL case */
if (predicate && IsA(predicate, NullTest) &&
((NullTest *) predicate)->nulltesttype == IS_NOT_NULL)
{
Expr *nonnullarg = ((NullTest *) predicate)->arg;
if (is_opclause(clause) &&
list_member(((OpExpr *) clause)->args, nonnullarg) &&
op_strict(((OpExpr *) clause)->opno))
return true;
if (is_funcclause(clause) &&
list_member(((FuncExpr *) clause)->args, nonnullarg) &&
func_strict(((FuncExpr *) clause)->funcid))
return true;
return false; /* we can't succeed below... */
}
/*
* Can't do anything more unless they are both binary opclauses with a
* Const on one side, and identical subexpressions on the other sides.
* Note we don't have to think about binary relabeling of the Const
* node, since that would have been folded right into the Const.
*
* If either Const is null, we also fail right away; this assumes that
* the test operator will always be strict.
*/
if (!is_opclause(predicate))
return false;
leftop = get_leftop(predicate);
rightop = get_rightop(predicate);
if (rightop == NULL)
return false; /* not a binary opclause */
if (IsA(rightop, Const))
{
pred_var = leftop;
pred_const = (Const *) rightop;
pred_var_on_left = true;
}
else if (IsA(leftop, Const))
{
pred_var = rightop;
pred_const = (Const *) leftop;
pred_var_on_left = false;
}
else
return false; /* no Const to be found */
if (pred_const->constisnull)
return false;
if (!is_opclause(clause))
return false;
leftop = get_leftop((Expr *) clause);
rightop = get_rightop((Expr *) clause);
if (rightop == NULL)
return false; /* not a binary opclause */
if (IsA(rightop, Const))
{
clause_var = leftop;
clause_const = (Const *) rightop;
clause_var_on_left = true;
}
else if (IsA(leftop, Const))
{
clause_var = rightop;
clause_const = (Const *) leftop;
clause_var_on_left = false;
}
else
return false; /* no Const to be found */
if (clause_const->constisnull)
return false;
/*
* Check for matching subexpressions on the non-Const sides. We used
* to only allow a simple Var, but it's about as easy to allow any
* expression. Remember we already know that the pred expression does
* not contain any non-immutable functions, so identical expressions
* should yield identical results.
*/
if (!equal(pred_var, clause_var))
return false;
/*
* Okay, get the operators in the two clauses we're comparing. Commute
* them if needed so that we can assume the variables are on the left.
*/
pred_op = ((OpExpr *) predicate)->opno;
if (!pred_var_on_left)
{
pred_op = get_commutator(pred_op);
if (!OidIsValid(pred_op))
return false;
}
clause_op = ((OpExpr *) clause)->opno;
if (!clause_var_on_left)
{
clause_op = get_commutator(clause_op);
if (!OidIsValid(clause_op))
return false;
}
/*
* Try to find a btree opclass containing the needed operators.
*
* We must find a btree opclass that contains both operators, else the
* implication can't be determined. Also, the pred_op has to be of
* default subtype (implying left and right input datatypes are the
* same); otherwise it's unsafe to put the pred_const on the left side
* of the test. Also, the opclass must contain a suitable test
* operator matching the clause_const's type (which we take to mean
* that it has the same subtype as the original clause_operator).
*
* If there are multiple matching opclasses, 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 opclasses.
*/
catlist = SearchSysCacheList(AMOPOPID, 1,
ObjectIdGetDatum(pred_op),
0, 0, 0);
/*
* If we couldn't find any opclass containing the pred_op, perhaps it
* is a <> operator. See if it has a negator that is in an opclass.
*/
pred_op_negated = false;
if (catlist->n_members == 0)
{
pred_op_negator = get_negator(pred_op);
if (OidIsValid(pred_op_negator))
{
pred_op_negated = true;
ReleaseSysCacheList(catlist);
catlist = SearchSysCacheList(AMOPOPID, 1,
ObjectIdGetDatum(pred_op_negator),
0, 0, 0);
}
}
/* Also may need the clause_op's negator */
clause_op_negator = get_negator(clause_op);
/* Now search the opclasses */
for (i = 0; i < catlist->n_members; i++)
{
HeapTuple pred_tuple = &catlist->members[i]->tuple;
Form_pg_amop pred_form = (Form_pg_amop) GETSTRUCT(pred_tuple);
HeapTuple clause_tuple;
opclass_id = pred_form->amopclaid;
/* must be btree */
if (!opclass_is_btree(opclass_id))
continue;
/* predicate operator must be default within this opclass */
if (pred_form->amopsubtype != InvalidOid)
continue;
/* Get the predicate operator's btree strategy number */
pred_strategy = (StrategyNumber) pred_form->amopstrategy;
Assert(pred_strategy >= 1 && pred_strategy <= 5);
if (pred_op_negated)
{
/* Only consider negators that are = */
if (pred_strategy != BTEqualStrategyNumber)
continue;
pred_strategy = BTNE;
}
/*
* From the same opclass, find a strategy number for the
* clause_op, if possible
*/
clause_tuple = SearchSysCache(AMOPOPID,
ObjectIdGetDatum(clause_op),
ObjectIdGetDatum(opclass_id),
0, 0);
if (HeapTupleIsValid(clause_tuple))
{
Form_pg_amop clause_form = (Form_pg_amop) GETSTRUCT(clause_tuple);
/* Get the restriction clause operator's strategy/subtype */
clause_strategy = (StrategyNumber) clause_form->amopstrategy;
Assert(clause_strategy >= 1 && clause_strategy <= 5);
clause_subtype = clause_form->amopsubtype;
ReleaseSysCache(clause_tuple);
}
else if (OidIsValid(clause_op_negator))
{
clause_tuple = SearchSysCache(AMOPOPID,
ObjectIdGetDatum(clause_op_negator),
ObjectIdGetDatum(opclass_id),
0, 0);
if (HeapTupleIsValid(clause_tuple))
{
Form_pg_amop clause_form = (Form_pg_amop) GETSTRUCT(clause_tuple);
/* Get the restriction clause operator's strategy/subtype */
clause_strategy = (StrategyNumber) clause_form->amopstrategy;
Assert(clause_strategy >= 1 && clause_strategy <= 5);
clause_subtype = clause_form->amopsubtype;
ReleaseSysCache(clause_tuple);
/* Only consider negators that are = */
if (clause_strategy != BTEqualStrategyNumber)
continue;
clause_strategy = BTNE;
}
else
continue;
}
else
continue;
/*
* Look up the "test" strategy number in the implication table
*/
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 opclass has an operator for the test strategy and the
* clause datatype.
*/
if (test_strategy == BTNE)
{
test_op = get_opclass_member(opclass_id, clause_subtype,
BTEqualStrategyNumber);
if (OidIsValid(test_op))
test_op = get_negator(test_op);
}
else
{
test_op = get_opclass_member(opclass_id, clause_subtype,
test_strategy);
}
if (OidIsValid(test_op))
{
/*
* 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 must be immutable, else it
* would not be allowed in an index predicate.) Essentially
* we are assuming that the opclass is consistent even if it
* contains operators that are merely stable.
*/
if (op_volatile(test_op) == PROVOLATILE_IMMUTABLE)
{
found = true;
break;
}
}
}
ReleaseSysCacheList(catlist);
if (!found)
{
/* couldn't find a btree opclass to interpret the operators */
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);
/* Prepare it for execution */
test_exprstate = ExecPrepareExpr(test_expr, estate);
/* And execute it. */
test_result = ExecEvalExprSwitchContext(test_exprstate,
GetPerTupleExprContext(estate),
&isNull, NULL);
/* Get back to outer memory context */
MemoryContextSwitchTo(oldcontext);
/* Release all the junk we just created */
FreeExecutorState(estate);
if (isNull)
{
/* Treat a null result as false ... but it's a tad fishy ... */
elog(DEBUG2, "null predicate test result");
return false;
}
return DatumGetBool(test_result);
}
---------------------------(end of broadcast)---------------------------
TIP 7: don't forget to increase your free space map settings
