Index: src/backend/optimizer/path/allpaths.c =================================================================== RCS file: /projects/cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v retrieving revision 1.134 diff -c -c -r1.134 allpaths.c *** src/backend/optimizer/path/allpaths.c 10 Jun 2005 03:32:21 -0000 1.134 --- src/backend/optimizer/path/allpaths.c 26 Jun 2005 23:32:58 -0000 *************** *** 18,30 **** --- 18,33 ---- #ifdef OPTIMIZER_DEBUG #include "nodes/print.h" #endif + #include "access/heapam.h" #include "optimizer/clauses.h" #include "optimizer/cost.h" #include "optimizer/geqo.h" #include "optimizer/pathnode.h" #include "optimizer/paths.h" #include "optimizer/plancat.h" + #include "optimizer/planmain.h" #include "optimizer/planner.h" + #include "optimizer/predtest.h" #include "optimizer/prep.h" #include "optimizer/var.h" #include "parser/parsetree.h" *************** *** 35,49 **** /* These parameters are set by GUC */ bool enable_geqo = false; /* just in case GUC doesn't set it */ int geqo_threshold; - static void set_base_rel_pathlists(PlannerInfo *root); static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte); static void set_inherited_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte, List *inheritlist); static void set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte); static void set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, --- 38,54 ---- /* These parameters are set by GUC */ bool enable_geqo = false; /* just in case GUC doesn't set it */ + bool enable_constraint_exclusion = false; int geqo_threshold; static void set_base_rel_pathlists(PlannerInfo *root); static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte); static void set_inherited_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte, List *inheritlist); + static List *prepConstrQual(char *ConstrString); + static bool RelationExclude(RelOptInfo *rel, Oid childOID); static void set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte); static void set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, *************** *** 250,255 **** --- 255,261 ---- Oid parentOID = rte->relid; List *subpaths = NIL; ListCell *il; + int num_relations_included = 0; /* * XXX for now, can't handle inherited expansion of FOR UPDATE/SHARE; *************** *** 291,297 **** /* * Copy the parent's targetlist and restriction quals to the ! * child, with attribute-number adjustment as needed. We don't * bother to copy the join quals, since we can't do any joining of * the individual tables. Also, we just zap attr_needed rather * than trying to adjust it; it won't be looked at in the child. --- 297,303 ---- /* * Copy the parent's targetlist and restriction quals to the ! * child. targetlist has attribute-number adjustment if needed. We don't * bother to copy the join quals, since we can't do any joining of * the individual tables. Also, we just zap attr_needed rather * than trying to adjust it; it won't be looked at in the child. *************** *** 303,356 **** childRTindex, childOID); childrel->attr_needed = NULL; ! childrel->baserestrictinfo = (List *) ! adjust_inherited_attrs((Node *) rel->baserestrictinfo, parentRTindex, parentOID, childRTindex, childOID); ! /* ! * Now compute child access paths, and save the cheapest. ! */ ! set_plain_rel_pathlist(root, childrel, childrte); ! subpaths = lappend(subpaths, childrel->cheapest_total_path); ! /* ! * Propagate size information from the child back to the parent. ! * For simplicity, we use the largest widths from any child as the ! * parent estimates. ! */ ! rel->rows += childrel->rows; ! if (childrel->width > rel->width) ! rel->width = childrel->width; ! forboth(parentvars, rel->reltargetlist, ! childvars, childrel->reltargetlist) ! { ! Var *parentvar = (Var *) lfirst(parentvars); ! Var *childvar = (Var *) lfirst(childvars); ! if (IsA(parentvar, Var) &&IsA(childvar, Var)) ! { ! int pndx = parentvar->varattno - rel->min_attr; ! int cndx = childvar->varattno - childrel->min_attr; ! if (childrel->attr_widths[cndx] > rel->attr_widths[pndx]) ! rel->attr_widths[pndx] = childrel->attr_widths[cndx]; ! } ! } ! } /* ! * Finally, build Append path and install it as the only access path ! * for the parent rel. */ ! add_path(rel, (Path *) create_append_path(rel, subpaths)); ! /* Select cheapest path (pretty easy in this case...) */ ! set_cheapest(rel); } /* quick-and-dirty test to see if any joining is needed */ --- 309,492 ---- childRTindex, childOID); childrel->attr_needed = NULL; ! ! /* ! * Don't adjust the attr numbers yet, they are needed for ! * comparison in RelationExclude ! */ ! childrel->baserestrictinfo = rel->baserestrictinfo; ! ! /* ! * At this point we have a child RelOptInfo and the restrictinfo ! * we need to decide whether to eliminate the partition ! * completely at planning time ! */ ! if (!RelationExclude(childrel, childOID)) ! { ! num_relations_included++; ! ! /* ! * Now that we have compared Restriction quals with constraint ! * predicates we can adjust the childs attribute-numbers if needed. ! */ ! childrel->baserestrictinfo = (List *) ! adjust_inherited_attrs((Node *) rel->baserestrictinfo, parentRTindex, parentOID, childRTindex, childOID); ! /* ! * Now compute child access paths, and save the cheapest. ! */ ! set_plain_rel_pathlist(root, childrel, childrte); ! ! subpaths = lappend(subpaths, childrel->cheapest_total_path); ! ! /* ! * Propagate size information from the child back to the parent. ! * For simplicity, we use the largest widths from any child as the ! * parent estimates. ! */ ! rel->rows += childrel->rows; ! if (childrel->width > rel->width) ! rel->width = childrel->width; ! ! forboth(parentvars, rel->reltargetlist, ! childvars, childrel->reltargetlist) ! { ! Var *parentvar = (Var *) lfirst(parentvars); ! Var *childvar = (Var *) lfirst(childvars); ! ! if (IsA(parentvar, Var) &&IsA(childvar, Var)) ! { ! int pndx = parentvar->varattno - rel->min_attr; ! int cndx = childvar->varattno - childrel->min_attr; ! ! if (childrel->attr_widths[cndx] > rel->attr_widths[pndx]) ! rel->attr_widths[pndx] = childrel->attr_widths[cndx]; ! } ! } ! } ! } ! /* ! * Finally, build Append path and install it as the only access path ! * for the parent rel. ! * ! * XXX if (num_relations_included == 1) then just use the subpath ! */ ! add_path(rel, (Path *) create_append_path(rel, subpaths)); ! /* Select cheapest path (pretty easy in this case...) */ ! set_cheapest(rel); ! } ! static bool ! RelationExclude(RelOptInfo *rel, Oid childOID) ! { ! List *restrictinfo_list = rel->baserestrictinfo; ! List *constraint_pred; ! bool exclude = false; ! ! Relation relation; ! ! uint16 num_check = 0; ! ConstrCheck *check; /* array */ ! uint16 i; ! ! /* If we aren't enabled to exclude relations, get out of here */ ! if (!enable_constraint_exclusion) ! return false; ! ! /* ! * Get Constraints info from relcache ! * This could have been done when the RelOptInfo was originally built ! * though that would mean storing that information for all queries ! * rather than just this specialised case ! */ ! relation = heap_open(childOID, AccessShareLock); ! ! num_check = relation->rd_att->constr->num_check; ! if (num_check > 0) ! { ! check = (ConstrCheck *) ! palloc(num_check * sizeof(ConstrCheck)); ! ! for (i = 0; i < num_check; i++) ! { ! check[i].ccbin = ! MemoryContextStrdup(CurrentMemoryContext, ! relation->rd_att->constr->check[i].ccbin); ! check[i].ccname = ! MemoryContextStrdup(CurrentMemoryContext, ! relation->rd_att->constr->check[i].ccname); ! } ! } ! heap_close(relation, AccessShareLock); ! ! /* Loop over the constraints, checking them against the query */ ! for (i = 0; i < num_check; i++) ! { ! /* prepare the constraint for comparison */ ! constraint_pred = prepConstrQual(check[i].ccbin); ! ! /* ! * Constraints must be ALL true for rows in the relation, so we ! * treat refutation the same way we would treat the constraints ! * if they were ANDed together to make a single predicate... ! * any provable refutation is sufficient to exclude the relation ! * from the query. ! */ ! if (predicate_refuted_by(constraint_pred, restrictinfo_list)) ! { ! exclude = true; ! break; ! } ! } ! if (num_check > 0) ! pfree(check); ! return exclude; ! } ! ! /* ! * Prepare the Constraint for use in comparison to query qual clauses ! * ! * Currently identical to code in relcache.c:RelationGetIndexPredicate ! */ ! static List * ! prepConstrQual(char *ConstrString) ! { ! List *result; ! ! result = (List *) stringToNode(ConstrString); /* ! * Run the expression through canonicalize_qual and ! * eval_const_expressions. This is not just an optimization, but is ! * necessary, because the planner will be comparing it to ! * similarly-processed qual clauses, and may fail to detect valid ! * matches without this. ! */ ! result = (List *) canonicalize_qual((Expr *) result); ! ! result = (List *) eval_const_expressions((Node *) result); ! ! /* ! * Also mark any coercion format fields as "don't care", so that the ! * planner can match to both explicit and implicit coercions. */ ! set_coercionform_dontcare((Node *) result); ! /* Also convert to implicit-AND format */ ! result = make_ands_implicit((Expr *) result); ! ! /* May as well fix opfuncids too */ ! fix_opfuncids((Node *) result); ! ! return result; } /* quick-and-dirty test to see if any joining is needed */ Index: src/backend/optimizer/util/predtest.c =================================================================== RCS file: /projects/cvsroot/pgsql/src/backend/optimizer/util/predtest.c,v retrieving revision 1.1 diff -c -c -r1.1 predtest.c *** src/backend/optimizer/util/predtest.c 10 Jun 2005 22:25:36 -0000 1.1 --- src/backend/optimizer/util/predtest.c 26 Jun 2005 23:33:00 -0000 *************** *** 27,34 **** --- 27,40 ---- static bool predicate_implied_by_recurse(Node *clause, Node *predicate); + static ThreeVLProof predicate_refuted_by_recurse(Node *clause, Node *predicate); + static bool predicate_implied_by_simple_clause(Expr *predicate, Node *clause); + static ThreeVLProof + predicate_simple_proof(Expr *predicate, Node *clause, + RequiredProof reqd_proof); + /* * predicate_implied_by *************** *** 70,75 **** --- 76,126 ---- return true; } + /* + * predicate_refuted_by + * Recursively checks whether the clauses in restrictinfo_list refute + * the given predicate. + * + * This is NOT the same as !(predicate_implied_by), though is similar in + * the technique and structure of the code. + * + * 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 will report a refutation when we should not + * have done so, be careful to ensure this is done correctly. + */ + bool + predicate_refuted_by(List *predicate_list, List *restrictinfo_list) + { + ListCell *item; + + if (predicate_list == NIL) + return false; /* no predicate: no refutation is possible */ + if (restrictinfo_list == NIL) + return false; /* no restriction: refutation must fail */ + + /* + * In all cases where the predicate is an AND-clause, + * predicate_refuted_by_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 predicate_implied_by_recurse() to handle + * a bare List on the predicate side. + * + * Logic is: restriction could imply any of the AND'ed predicate items. + * + */ + foreach(item, predicate_list) + { + if (predicate_refuted_by_recurse((Node *) restrictinfo_list, + lfirst(item)) == PROVABLY_FALSE) + return true; + } + return false; + } /*---------- * predicate_implied_by_recurse *************** *** 240,248 **** } } /* ! * 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) > --- 291,508 ---- } } + /*---------- + * predicate_refuted_by_recurse + * Does the predicate refutation test for non-NULL restriction and + * predicate clauses. + * + * Uses three valued logic (ThreeVL), but otherwise very similar in structure + * to predicate_implied_by_recurse() + * + * Refutation is only possible for fairly simple predicates such as + * Range partitioning + * A1 [AND A2 [AND A3 [...]]] + * List partitioning + * A1 [OR A2 [OR A3 [...]]] i.e. an IN list + * Mixed Range and List partitioning + * A1 [AND A2 [AND A3 [...]]] OR B1 [OR B2 [OR B3 [OR B4 [...]]]] + * + * This restriction is by design because of the overhead of refutation for + * large predicates increases dramatically. We must search the whole clause for + * refutation to allow partitioning to work for complex queries. + *---------- + */ + static ThreeVLProof + predicate_refuted_by_recurse(Node *clause, Node *predicate) + { + ListCell *item; + bool refuted = false; + bool proven = false; + int noinfer = 0; + + 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 (or_clause(predicate)) + { + /* OR-clause R=> atom if all of A's items refutes B */ + /* 3 valued truth table: + * + * PROVABLY_TRUE NO_INFERENCE PROVABLY_FALSE + * PROVABLY_TRUE PROVABLY_TRUE PROVABLY_TRUE PROVABLY_TRUE + * NO_INFERENCE PROVABLY_TRUE NO_INFERENCE NO_INFERENCE + * PROVABLY_FALSE PROVABLY_TRUE NO_INFERENCE PROVABLY_FALSE + */ + foreach(item, ((BoolExpr *) predicate)->args) + { + switch (predicate_refuted_by_recurse(clause,lfirst(item))) + { + case PROVABLY_TRUE: + return PROVABLY_TRUE; + case PROVABLY_FALSE: + break; + case NO_INFERENCE: + noinfer++; + break; + default: + /* Shouldn't happen */ + break; + } + } + return (noinfer == 0) ? PROVABLY_FALSE : NO_INFERENCE; + } + else + { + /* AND-clause R=> atom if any of A's items refutes B */ + /* 3 valued truth table: + * + * PROVABLY_TRUE NO_INFERENCE PROVABLY_FALSE + * PROVABLY_TRUE PROVABLY_TRUE PROVABLY_TRUE PROVABLY_FALSE + * NO_INFERENCE PROVABLY_TRUE NO_INFERENCE PROVABLY_FALSE + * PROVABLY_FALSE PROVABLY_FALSE PROVABLY_FALSE PROVABLY_FALSE + */ + foreach(item, (List *) clause) + { + switch (predicate_refuted_by_recurse(lfirst(item),predicate)) + { + case PROVABLY_TRUE: + proven = true; + break; + case PROVABLY_FALSE: + return PROVABLY_FALSE; + case NO_INFERENCE: + break; + default: + /* Shouldn't happen */ + break; + } + } + return (proven) ? PROVABLY_TRUE : NO_INFERENCE; + } + } + else if (or_clause(clause)) + { + if (or_clause(predicate)) + { + /* + * OR-clause R=> OR-clause if all of A's items refutes all of + * B's items. So we use the AND truth table + * 3 valued truth table: + * + * PROVABLY_TRUE NO_INFERENCE PROVABLY_FALSE + * PROVABLY_TRUE PROVABLY_TRUE PROVABLY_TRUE PROVABLY_FALSE + * NO_INFERENCE PROVABLY_TRUE NO_INFERENCE PROVABLY_FALSE + * PROVABLY_FALSE PROVABLY_FALSE PROVABLY_FALSE PROVABLY_FALSE + */ + foreach(item, ((BoolExpr *) clause)->args) + { + Node *citem = lfirst(item); + ListCell *item2; + + foreach(item2, ((BoolExpr *) predicate)->args) + { + switch (predicate_refuted_by_recurse(citem, lfirst(item2))) + { + case PROVABLY_TRUE: + proven = true; + break; + case PROVABLY_FALSE: + return PROVABLY_FALSE; + case NO_INFERENCE: + break; + default: + break; + } + } + } + return (proven) ? PROVABLY_TRUE : NO_INFERENCE; + } + else + { + /* OR-clause R=> atom if all of A's items refutes B */ + /* 3 valued truth table: + * + * PROVABLY_TRUE NO_INFERENCE PROVABLY_FALSE + * PROVABLY_TRUE PROVABLY_TRUE PROVABLY_TRUE PROVABLY_TRUE + * NO_INFERENCE PROVABLY_TRUE NO_INFERENCE NO_INFERENCE + * PROVABLY_FALSE PROVABLY_TRUE NO_INFERENCE PROVABLY_FALSE + */ + foreach(item, ((BoolExpr *) clause)->args) + { + switch (predicate_refuted_by_recurse(lfirst(item),predicate)) + { + case PROVABLY_TRUE: + return PROVABLY_TRUE; + case PROVABLY_FALSE: + break; + case NO_INFERENCE: + noinfer++; + break; + default: + /* Shouldn't happen */ + break; + } + } + return (noinfer == 0) ? PROVABLY_FALSE : NO_INFERENCE; + } + } + else + { + if (or_clause(predicate)) + { + /* atom R=> OR-clause if A refutes all of B's items */ + /* 3 valued truth table: + * + * PROVABLY_TRUE NO_INFERENCE PROVABLY_FALSE + * PROVABLY_TRUE PROVABLY_TRUE PROVABLY_TRUE PROVABLY_TRUE + * NO_INFERENCE PROVABLY_TRUE NO_INFERENCE PROVABLY_FALSE + * PROVABLY_FALSE PROVABLY_TRUE PROVABLY_FALSE PROVABLY_FALSE + */ + foreach(item, ((BoolExpr *) predicate)->args) + { + switch (predicate_refuted_by_recurse(clause, lfirst(item))) + { + case PROVABLY_TRUE: + return PROVABLY_TRUE; + case PROVABLY_FALSE: + refuted = true; + break; + case NO_INFERENCE: + break; + default: + /* Shouldn't happen */ + break; + } + } + return (refuted) ? PROVABLY_FALSE : NO_INFERENCE; + } + else + { + /* atom R=> atom is the base case */ + return predicate_simple_proof((Expr *) predicate, clause, REFUTE); + } + } + } /* ! * Define an "operator implication table" for btree operators ("strategies"), ! * and a similar table for refutation also. * * The strategy numbers defined by btree indexes (see access/skey.h) are: * (1) < (2) <= (3) = (4) >= (5) > *************** *** 252,268 **** * * 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. */ --- 512,544 ---- * * The interpretation of: * ! * test_op = BT_[implic|refute]_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: * + * implic * 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. * + * e.g. if clause is Quantity > 10 + * and pred is Quantity > 5 + * then we test "5 <= 10" which evals to true, so clause => pred + * + * refute + * If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you + * want to determine whether "ATTR target_op CONST2" can be refuted, then + * you can use "CONST2 test_op CONST1" as a test. If this test returns true, + * then the target expression can be refuted; if the test returns false, then + * the target expression cannot be refuted. + * + * e.g. if clause is Quantity > 10 + * and pred is Quantity < 5 + * then we test "5 <= 10" which evals to true, so clause refutes pred + * * An entry where test_op == 0 means the implication cannot be determined, * i.e., this test should always be considered false. */ *************** *** 279,297 **** /* * 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 */ }; /*---------- ! * predicate_implied_by_simple_clause * Does the predicate implication test for a "simple clause" predicate * and a "simple clause" restriction. * --- 555,587 ---- /* * 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 */ }; + static const StrategyNumber + BT_refute_table[6][6] = { + /* + * The target operator: + * + * LT LE EQ GE GT NE + */ + {0 , 0 , BTGE, BTGE, BTGE, 0 }, /* LT */ + {0 , 0 , BTGT, BTGT, BTGE, 0 }, /* LE */ + {BTLE, BTLT, BTNE, BTGT, BTGE, BTEQ}, /* EQ */ + {BTLE, BTLT, BTLT, 0 , 0 , 0 }, /* GE */ + {BTLE, BTLE, BTLE, 0 , 0 , 0 }, /* GT */ + {0 , 0 , BTEQ, 0 , 0 , 0 } /* NE */ + }; /*---------- ! * predicate_simple_proof_clause * Does the predicate implication test for a "simple clause" predicate * and a "simple clause" restriction. * *************** *** 324,331 **** * appropriate "RT_implic_table" array. *---------- */ ! static bool ! predicate_implied_by_simple_clause(Expr *predicate, Node *clause) { Node *leftop, *rightop; --- 614,622 ---- * appropriate "RT_implic_table" array. *---------- */ ! static ThreeVLProof ! predicate_simple_proof(Expr *predicate, Node *clause, ! RequiredProof reqd_proof) { Node *leftop, *rightop; *************** *** 358,380 **** /* 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... */ } /* --- 649,683 ---- /* First try the equal() test */ if (equal((Node *) predicate, clause)) ! return PROVABLY_TRUE; ! /* Next try the case for IS NOT NULL or IS NULL */ ! if (predicate && IsA(predicate, NullTest)) ! { Expr *nonnullarg = ((NullTest *) predicate)->arg; ! if (((NullTest *) predicate)->nulltesttype == IS_NOT_NULL) ! { ! if (is_opclause(clause) && ! list_member(((OpExpr *) clause)->args, nonnullarg) && ! op_strict(((OpExpr *) clause)->opno)) ! return PROVABLY_TRUE; ! if (is_funcclause(clause) && ! list_member(((FuncExpr *) clause)->args, nonnullarg) && ! func_strict(((FuncExpr *) clause)->funcid)) ! return PROVABLY_TRUE; ! return NO_INFERENCE; /* we can't succeed below... */ ! } else ! { ! if (is_opclause(clause) && ! list_member(((OpExpr *) clause)->args, nonnullarg) && ! op_strict(((OpExpr *) clause)->opno)) ! return PROVABLY_FALSE; ! if (is_funcclause(clause) && ! list_member(((FuncExpr *) clause)->args, nonnullarg) && ! func_strict(((FuncExpr *) clause)->funcid)) ! return PROVABLY_FALSE; ! return NO_INFERENCE; /* we can't succeed below... */ ! } } /* *************** *** 387,397 **** * 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; --- 690,700 ---- * the test operator will always be strict. */ if (!is_opclause(predicate)) ! return NO_INFERENCE; leftop = get_leftop(predicate); rightop = get_rightop(predicate); if (rightop == NULL) ! return NO_INFERENCE; /* not a binary opclause */ if (IsA(rightop, Const)) { pred_var = leftop; *************** *** 405,420 **** 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; --- 708,723 ---- pred_var_on_left = false; } else ! return NO_INFERENCE; /* no Const to be found */ if (pred_const->constisnull) ! return NO_INFERENCE; if (!is_opclause(clause)) ! return NO_INFERENCE; leftop = get_leftop((Expr *) clause); rightop = get_rightop((Expr *) clause); if (rightop == NULL) ! return NO_INFERENCE; /* not a binary opclause */ if (IsA(rightop, Const)) { clause_var = leftop; *************** *** 428,436 **** 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 --- 731,739 ---- clause_var_on_left = false; } else ! return NO_INFERENCE; /* no Const to be found */ if (clause_const->constisnull) ! return NO_INFERENCE; /* * Check for matching subexpressions on the non-Const sides. We used *************** *** 440,446 **** * should yield identical results. */ if (!equal(pred_var, clause_var)) ! return false; /* * Okay, get the operators in the two clauses we're comparing. Commute --- 743,749 ---- * should yield identical results. */ if (!equal(pred_var, clause_var)) ! return NO_INFERENCE; /* * Okay, get the operators in the two clauses we're comparing. Commute *************** *** 451,457 **** { pred_op = get_commutator(pred_op); if (!OidIsValid(pred_op)) ! return false; } clause_op = ((OpExpr *) clause)->opno; --- 754,760 ---- { pred_op = get_commutator(pred_op); if (!OidIsValid(pred_op)) ! return NO_INFERENCE; } clause_op = ((OpExpr *) clause)->opno; *************** *** 459,465 **** { clause_op = get_commutator(clause_op); if (!OidIsValid(clause_op)) ! return false; } /* --- 762,768 ---- { clause_op = get_commutator(clause_op); if (!OidIsValid(clause_op)) ! return NO_INFERENCE; } /* *************** *** 579,594 **** /* * 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) { --- 882,909 ---- /* * Look up the "test" strategy number in the implication table */ ! switch (reqd_proof) ! { ! case IMPLY: ! test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1]; ! break; ! case REFUTE: ! test_strategy = BT_refute_table[clause_strategy - 1][pred_strategy - 1]; ! break; ! default: ! /* Shouldn't happen */ ! break; ! } ! 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.range */ if (test_strategy == BTNE) { *************** *** 607,626 **** /* * 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. ! * ! * XXX the above reasoning doesn't hold anymore if this routine ! * is used to prove things that are not index predicates ... */ ! if (op_volatile(test_op) == PROVOLATILE_IMMUTABLE) ! { ! found = true; ! break; ! } } } --- 922,941 ---- /* * Last check: test_op must be immutable. * ! * If this routine is used to prove things that are index preds ! * then we require only the test_op to be immutable, not the ! * original clause_op. In general, we must test clause_op also. ! * (pred_op must be immutable, else it would not be allowed in a ! * 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 && ! ( reqd_proof == IMPLY || ! op_volatile(clause_op) == PROVOLATILE_IMMUTABLE)) ! { ! found = true; ! break; ! } } } *************** *** 628,635 **** if (!found) { ! /* couldn't find a btree opclass to interpret the operators */ ! return false; } /* --- 943,950 ---- if (!found) { ! /* couldn't find a btree opclass to interpret the operators */ ! return NO_INFERENCE; } /* *************** *** 665,671 **** { /* Treat a null result as false ... but it's a tad fishy ... */ elog(DEBUG2, "null predicate test result"); ! return false; } ! return DatumGetBool(test_result); } --- 980,1004 ---- { /* Treat a null result as false ... but it's a tad fishy ... */ elog(DEBUG2, "null predicate test result"); ! return NO_INFERENCE; } ! ! if (reqd_proof == REFUTE) ! if (DatumGetBool(test_result)) ! return PROVABLY_FALSE; ! else ! return PROVABLY_TRUE; ! else ! if (DatumGetBool(test_result)) ! return PROVABLY_TRUE; ! else ! return PROVABLY_FALSE; ! } ! ! static bool ! predicate_implied_by_simple_clause(Expr *predicate, Node *clause) ! { ! /* Interpret the 3VL logic as to whether we have proven implication */ ! return (predicate_simple_proof(predicate, clause, IMPLY) ! == PROVABLY_TRUE) ? true : false; } Index: src/backend/utils/misc/guc.c =================================================================== RCS file: /projects/cvsroot/pgsql/src/backend/utils/misc/guc.c,v retrieving revision 1.270 diff -c -c -r1.270 guc.c *** src/backend/utils/misc/guc.c 26 Jun 2005 19:16:06 -0000 1.270 --- src/backend/utils/misc/guc.c 26 Jun 2005 23:33:05 -0000 *************** *** 431,436 **** --- 431,446 ---- true, NULL, NULL }, { + {"enable_constraint_exclusion", PGC_USERSET, QUERY_TUNING_METHOD, + gettext_noop("Enables the planner's use of constraints in queries."), + gettext_noop("Constraints on tables will be used to exclude relations" + "that can be proven not to be required to produce" + "a correct result for the query.") + }, + &enable_constraint_exclusion, + false, NULL, NULL + }, + { {"geqo", PGC_USERSET, QUERY_TUNING_GEQO, gettext_noop("Enables genetic query optimization."), gettext_noop("This algorithm attempts to do planning without " Index: src/include/optimizer/cost.h =================================================================== RCS file: /projects/cvsroot/pgsql/src/include/optimizer/cost.h,v retrieving revision 1.68 diff -c -c -r1.68 cost.h *** src/include/optimizer/cost.h 5 Jun 2005 22:32:58 -0000 1.68 --- src/include/optimizer/cost.h 26 Jun 2005 23:33:06 -0000 *************** *** 49,54 **** --- 49,56 ---- extern bool enable_nestloop; extern bool enable_mergejoin; extern bool enable_hashjoin; + extern bool enable_constraint_exclusion; + extern double clamp_row_est(double nrows); extern void cost_seqscan(Path *path, PlannerInfo *root, RelOptInfo *baserel); Index: src/include/optimizer/predtest.h =================================================================== RCS file: /projects/cvsroot/pgsql/src/include/optimizer/predtest.h,v retrieving revision 1.1 diff -c -c -r1.1 predtest.h *** src/include/optimizer/predtest.h 10 Jun 2005 22:25:37 -0000 1.1 --- src/include/optimizer/predtest.h 26 Jun 2005 23:33:06 -0000 *************** *** 19,23 **** --- 19,38 ---- extern bool predicate_implied_by(List *predicate_list, List *restrictinfo_list); + extern bool predicate_refuted_by(List *predicate_list, + List *restrictinfo_list); + + typedef enum ThreeVLProof + { + PROVABLY_TRUE, + PROVABLY_FALSE, + NO_INFERENCE + } ThreeVLProof; + + typedef enum RequiredProof + { + IMPLY, + REFUTE + } RequiredProof; #endif /* PREDTEST_H */