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