From d007a95055b9b649b74b5d25aa4d2b46f3eca21c Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Sat, 23 Jul 2005 21:05:48 +0000 Subject: [PATCH] Simple constraint exclusion. For now, only child tables of inheritance scans are candidates for exclusion; this should be fixed eventually. Simon Riggs, with some help from Tom Lane. --- doc/src/sgml/runtime.sgml | 52 +- src/backend/optimizer/path/allpaths.c | 40 +- src/backend/optimizer/plan/createplan.c | 27 +- src/backend/optimizer/plan/planagg.c | 3 +- src/backend/optimizer/util/plancat.c | 82 +++- src/backend/optimizer/util/predtest.c | 450 +++++++++++++++--- src/backend/utils/misc/guc.c | 12 +- src/backend/utils/misc/postgresql.conf.sample | 1 + src/bin/psql/tab-complete.c | 3 +- src/include/nodes/relation.h | 20 +- src/include/optimizer/cost.h | 3 +- src/include/optimizer/plancat.h | 4 +- src/include/optimizer/predtest.h | 4 +- src/test/regress/expected/rangefuncs.out | 25 +- 14 files changed, 621 insertions(+), 105 deletions(-) diff --git a/doc/src/sgml/runtime.sgml b/doc/src/sgml/runtime.sgml index 4cae3fa894..4f24a6e876 100644 --- a/doc/src/sgml/runtime.sgml +++ b/doc/src/sgml/runtime.sgml @@ -1,5 +1,5 @@ @@ -2278,6 +2278,56 @@ archive_command = 'copy "%p" /mnt/server/archivedir/"%f"' # Windows + + enable_constraint_exclusion (boolean) + + constraint exclusion + + + enable_constraint_exclusion configuration parameter + + + + Enables or disables the query planner's use of table constraints. + The default is off. + + + + When this parameter is on, the planner compares query + conditions to table CHECK constraints, and omits scanning tables + for which the conditions contradict the constraints. (Presently + this is done only for child tables of inheritance scans.) For + example: + + +CREATE TABLE parent(key integer, ...); +CREATE TABLE child1000(check (key between 1000 and 1999)) INHERITS(parent); +CREATE TABLE child2000(check (key between 2000 and 2999)) INHERITS(parent); +... +SELECT * FROM parent WHERE key = 2400; + + + With constraint exclusion enabled, this SELECT will not scan + child1000 at all. This can improve performance when + inheritance is used to build partitioned tables. + + + + Currently, enable_constraint_exclusion defaults to + off, because it creates a risk of wrong answers when + query plans are cached: if a table constraint is changed or dropped, + the previously generated plan may now be wrong, and there is no + built-in mechanism to force re-planning. (This deficiency will + probably be addressed in a future + PostgreSQL release.) Another reason + for keeping it off is that the constraint checks are relatively + expensive to make, and in many circumstances will yield no savings. + It is recommended to turn this on only if you are actually using + partitioned tables designed to take advantage of the feature. + + + + from_collapse_limit (integer) diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 25bd55dadf..124534914f 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -8,13 +8,14 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.134 2005/06/10 03:32:21 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.135 2005/07/23 21:05:46 tgl Exp $ * *------------------------------------------------------------------------- */ #include "postgres.h" +#include "nodes/makefuncs.h" #ifdef OPTIMIZER_DEBUG #include "nodes/print.h" #endif @@ -25,6 +26,7 @@ #include "optimizer/paths.h" #include "optimizer/plancat.h" #include "optimizer/planner.h" +#include "optimizer/predtest.h" #include "optimizer/prep.h" #include "optimizer/var.h" #include "parser/parsetree.h" @@ -34,6 +36,7 @@ /* These parameters are set by GUC */ +bool enable_constraint_exclusion = false; bool enable_geqo = false; /* just in case GUC doesn't set it */ int geqo_threshold; @@ -311,7 +314,37 @@ set_inherited_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, childOID); /* - * Now compute child access paths, and save the cheapest. + * If we can prove we don't need to scan this child via constraint + * exclusion, just ignore it. (We have to have converted the + * baserestrictinfo Vars before we can make the test.) + */ + if (enable_constraint_exclusion) + { + List *constraint_pred; + + constraint_pred = get_relation_constraints(childOID, childrel); + /* + * We do not currently enforce that CHECK constraints contain + * only immutable functions, so it's necessary to check here. + * We daren't draw conclusions from plan-time evaluation of + * non-immutable functions. + */ + if (!contain_mutable_functions((Node *) constraint_pred)) + { + /* + * The constraints are effectively ANDed together, so we can + * just try to refute the entire collection at once. This may + * allow us to make proofs that would fail if we took them + * individually. + */ + if (predicate_refuted_by(constraint_pred, + childrel->baserestrictinfo)) + continue; + } + } + + /* + * Compute the child's access paths, and save the cheapest. */ set_plain_rel_pathlist(root, childrel, childrte); @@ -345,7 +378,8 @@ set_inherited_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, /* * Finally, build Append path and install it as the only access path - * for the parent rel. + * for the parent rel. (Note: this is correct even if we have zero + * or one live subpath due to constraint exclusion.) */ add_path(rel, (Path *) create_append_path(rel, subpaths)); diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index 589bebef69..6c4c345ca8 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -10,7 +10,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.194 2005/07/15 22:02:51 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.195 2005/07/23 21:05:46 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -40,7 +40,7 @@ static List *build_relation_tlist(RelOptInfo *rel); static bool use_physical_tlist(RelOptInfo *rel); static void disuse_physical_tlist(Plan *plan, Path *path); static Join *create_join_plan(PlannerInfo *root, JoinPath *best_path); -static Append *create_append_plan(PlannerInfo *root, AppendPath *best_path); +static Plan *create_append_plan(PlannerInfo *root, AppendPath *best_path); static Result *create_result_plan(PlannerInfo *root, ResultPath *best_path); static Material *create_material_plan(PlannerInfo *root, MaterialPath *best_path); static Plan *create_unique_plan(PlannerInfo *root, UniquePath *best_path); @@ -435,7 +435,7 @@ create_join_plan(PlannerInfo *root, JoinPath *best_path) * * Returns a Plan node. */ -static Append * +static Plan * create_append_plan(PlannerInfo *root, AppendPath *best_path) { Append *plan; @@ -443,6 +443,25 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path) List *subplans = NIL; ListCell *subpaths; + /* + * It is possible for the subplans list to contain only one entry, + * or even no entries. Handle these cases specially. + * + * XXX ideally, if there's just one entry, we'd not bother to generate + * an Append node but just return the single child. At the moment this + * does not work because the varno of the child scan plan won't match + * the parent-rel Vars it'll be asked to emit. + */ + if (best_path->subpaths == NIL) + { + /* Generate a Result plan with constant-FALSE gating qual */ + return (Plan *) make_result(tlist, + (Node *) list_make1(makeBoolConst(false, + false)), + NULL); + } + + /* Normal case with multiple subpaths */ foreach(subpaths, best_path->subpaths) { Path *subpath = (Path *) lfirst(subpaths); @@ -452,7 +471,7 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path) plan = make_append(subplans, false, tlist); - return plan; + return (Plan *) plan; } /* diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c index 0a47799707..0208e91053 100644 --- a/src/backend/optimizer/plan/planagg.c +++ b/src/backend/optimizer/plan/planagg.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/plan/planagg.c,v 1.5 2005/06/05 22:32:56 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/plan/planagg.c,v 1.6 2005/07/23 21:05:46 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -184,7 +184,6 @@ optimize_minmax_aggregates(PlannerInfo *root, List *tlist, Path *best_path) */ if (IsA(best_path, ResultPath)) { - Assert(((ResultPath *) best_path)->subpath != NULL); constant_quals = ((ResultPath *) best_path)->constantqual; /* no need to do this more than once: */ constant_quals = order_qual_clauses(root, constant_quals); diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c index 067e9f701c..d1656350f2 100644 --- a/src/backend/optimizer/util/plancat.c +++ b/src/backend/optimizer/util/plancat.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/util/plancat.c,v 1.112 2005/06/13 23:14:48 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/plancat.c,v 1.113 2005/07/23 21:05:47 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -25,6 +25,7 @@ #include "nodes/makefuncs.h" #include "optimizer/clauses.h" #include "optimizer/plancat.h" +#include "optimizer/prep.h" #include "optimizer/tlist.h" #include "parser/parsetree.h" #include "parser/parse_expr.h" @@ -359,6 +360,85 @@ estimate_rel_size(Relation rel, int32 *attr_widths, } } + +/* + * get_relation_constraints + * + * Retrieve the CHECK constraint expressions of the given relation. + * + * Returns a List (possibly empty) of constraint expressions. Each one + * has been canonicalized, and its Vars are changed to have the varno + * indicated by rel->relid. This allows the expressions to be easily + * compared to expressions taken from WHERE. + * + * Note: at present this is invoked at most once per relation per planner + * run, and in many cases it won't be invoked at all, so there seems no + * point in caching the data in RelOptInfo. + */ +List * +get_relation_constraints(Oid relationObjectId, RelOptInfo *rel) +{ + List *result = NIL; + Index varno = rel->relid; + Relation relation; + TupleConstr *constr; + + /* + * We assume the relation has already been safely locked. + */ + relation = heap_open(relationObjectId, NoLock); + + constr = relation->rd_att->constr; + if (constr != NULL) + { + int num_check = constr->num_check; + int i; + + for (i = 0; i < num_check; i++) + { + Node *cexpr; + + cexpr = stringToNode(constr->check[i].ccbin); + + /* + * Run each expression through const-simplification and + * canonicalization. This is not just an optimization, but is + * necessary, because we will be comparing it to + * similarly-processed qual clauses, and may fail to detect valid + * matches without this. This must match the processing done to + * qual clauses in preprocess_expression()! (We can skip the + * stuff involving subqueries, however, since we don't allow any + * in check constraints.) + */ + cexpr = eval_const_expressions(cexpr); + + cexpr = (Node *) canonicalize_qual((Expr *) cexpr); + + /* + * Also mark any coercion format fields as "don't care", so that + * we can match to both explicit and implicit coercions. + */ + set_coercionform_dontcare(cexpr); + + /* Fix Vars to have the desired varno */ + if (varno != 1) + ChangeVarNodes(cexpr, 1, varno, 0); + + /* + * Finally, convert to implicit-AND format (that is, a List) + * and append the resulting item(s) to our output list. + */ + result = list_concat(result, + make_ands_implicit((Expr *) cexpr)); + } + } + + heap_close(relation, NoLock); + + return result; +} + + /* * build_physical_tlist * diff --git a/src/backend/optimizer/util/predtest.c b/src/backend/optimizer/util/predtest.c index 38c43ea027..9628f9186e 100644 --- a/src/backend/optimizer/util/predtest.c +++ b/src/backend/optimizer/util/predtest.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/util/predtest.c,v 1.1 2005/06/10 22:25:36 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/predtest.c,v 1.2 2005/07/23 21:05:47 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -27,7 +27,11 @@ static bool predicate_implied_by_recurse(Node *clause, Node *predicate); +static bool predicate_refuted_by_recurse(Node *clause, Node *predicate); static bool predicate_implied_by_simple_clause(Expr *predicate, Node *clause); +static bool predicate_refuted_by_simple_clause(Expr *predicate, Node *clause); +static bool btree_predicate_proof(Expr *predicate, Node *clause, + bool refute_it); /* @@ -35,12 +39,19 @@ static bool predicate_implied_by_simple_clause(Expr *predicate, Node *clause); * 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. + * 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. + * + * We assume the predicate has already been checked to contain only + * immutable functions and operators. (In current use this is true + * because the predicate is part of an index predicate that has passed + * CheckPredicate().) We dare not make deductions based on non-immutable + * functions, because they might change answers between the time we make + * the plan and the time we execute the plan. */ bool predicate_implied_by(List *predicate_list, List *restrictinfo_list) @@ -70,6 +81,44 @@ predicate_implied_by(List *predicate_list, List *restrictinfo_list) return true; } +/* + * predicate_refuted_by + * Recursively checks whether the clauses in restrictinfo_list refute + * the given predicate (that is, prove it false). + * + * This is NOT the same as !(predicate_implied_by), though it 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 might fail to prove an implication that is + * valid, but no worse consequences will ensue. + * + * We assume the predicate has already been checked to contain only + * immutable functions and operators. We dare not make deductions based on + * non-immutable functions, because they might change answers between the + * time we make the plan and the time we execute the plan. + */ +bool +predicate_refuted_by(List *predicate_list, List *restrictinfo_list) +{ + if (predicate_list == NIL) + return false; /* no predicate: no refutation is possible */ + if (restrictinfo_list == NIL) + return false; /* no restriction: refutation must fail */ + + /* + * Unlike the implication case, predicate_refuted_by_recurse needs to + * be able to see the top-level AND structure on both sides --- otherwise + * it will fail to handle the case where one restriction clause is an OR + * that can refute the predicate AND as a whole, but not each predicate + * clause separately. + */ + return predicate_refuted_by_recurse((Node *) restrictinfo_list, + (Node *) predicate_list); +} /*---------- * predicate_implied_by_recurse @@ -240,9 +289,271 @@ predicate_implied_by_recurse(Node *clause, Node *predicate) } } +/*---------- + * predicate_refuted_by_recurse + * Does the predicate refutation test for non-NULL restriction and + * predicate clauses. + * + * The logic followed here is ("R=>" means "refutes"): + * atom A R=> atom B iff: predicate_refuted_by_simple_clause says so + * atom A R=> AND-expr B iff: A R=> any of B's components + * atom A R=> OR-expr B iff: A R=> each of B's components + * AND-expr A R=> atom B iff: any of A's components R=> B + * AND-expr A R=> AND-expr B iff: A R=> any of B's components, + * *or* any of A's components R=> B + * AND-expr A R=> OR-expr B iff: A R=> each of B's components + * OR-expr A R=> atom B iff: each of A's components R=> B + * OR-expr A R=> AND-expr B iff: each of A's components R=> any of B's + * OR-expr A R=> OR-expr B iff: A R=> each of B's components + * + * Other comments are as for predicate_implied_by_recurse(), except that + * we have to handle a top-level AND list on both sides. + *---------- + */ +static bool +predicate_refuted_by_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; + + /* Ditto for predicate AND-clause and List */ + if (and_clause(predicate)) + predicate = (Node *) ((BoolExpr *) predicate)->args; + + if (IsA(clause, List)) + { + if (IsA(predicate, List)) + { + /* AND-clause R=> AND-clause if A refutes any of B's items */ + /* Needed to handle (x AND y) R=> ((!x OR !y) AND z) */ + foreach(item, (List *) predicate) + { + if (predicate_refuted_by_recurse(clause, lfirst(item))) + return true; + } + /* Also check if any of A's items refutes B */ + /* Needed to handle ((x OR y) AND z) R=> (!x AND !y) */ + foreach(item, (List *) clause) + { + if (predicate_refuted_by_recurse(lfirst(item), predicate)) + return true; + } + return false; + } + else if (or_clause(predicate)) + { + /* AND-clause R=> OR-clause if A refutes each of B's items */ + foreach(item, ((BoolExpr *) predicate)->args) + { + if (!predicate_refuted_by_recurse(clause, lfirst(item))) + return false; + } + return true; + } + else + { + /* AND-clause R=> atom if any of A's items refutes B */ + foreach(item, (List *) clause) + { + if (predicate_refuted_by_recurse(lfirst(item), predicate)) + return true; + } + return false; + } + } + else if (or_clause(clause)) + { + if (or_clause(predicate)) + { + /* OR-clause R=> OR-clause if A refutes each of B's items */ + foreach(item, ((BoolExpr *) predicate)->args) + { + if (!predicate_refuted_by_recurse(clause, lfirst(item))) + return false; + } + return true; + } + else if (IsA(predicate, List)) + { + /* + * OR-clause R=> AND-clause if each of A's items refutes any of + * B's items. + */ + foreach(item, ((BoolExpr *) clause)->args) + { + Node *citem = lfirst(item); + ListCell *item2; + + foreach(item2, (List *) predicate) + { + if (predicate_refuted_by_recurse(citem, lfirst(item2))) + break; + } + if (item2 == NULL) + return false; /* citem refutes nothing */ + } + return true; + } + else + { + /* OR-clause R=> atom if each of A's items refutes B */ + foreach(item, ((BoolExpr *) clause)->args) + { + if (!predicate_refuted_by_recurse(lfirst(item), predicate)) + return false; + } + return true; + } + } + else + { + if (IsA(predicate, List)) + { + /* atom R=> AND-clause if A refutes any of B's items */ + foreach(item, (List *) predicate) + { + if (predicate_refuted_by_recurse(clause, lfirst(item))) + return true; + } + return false; + } + else if (or_clause(predicate)) + { + /* atom R=> OR-clause if A refutes each of B's items */ + foreach(item, ((BoolExpr *) predicate)->args) + { + if (!predicate_refuted_by_recurse(clause, lfirst(item))) + return false; + } + return true; + } + else + { + /* atom R=> atom is the base case */ + return predicate_refuted_by_simple_clause((Expr *) predicate, + clause); + } + } +} + + +/*---------- + * predicate_implied_by_simple_clause + * Does the predicate implication test for a "simple clause" predicate + * and a "simple clause" restriction. + * + * We return TRUE if able to prove the implication, FALSE if not. + * + * 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 the caller.) + * + * 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.) + * + * Finally, we may be able to deduce something using knowledge about btree + * operator classes; this is encapsulated in btree_predicate_proof(). + *---------- + */ +static bool +predicate_implied_by_simple_clause(Expr *predicate, Node *clause) +{ + /* 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... */ + } + + /* Else try btree operator knowledge */ + return btree_predicate_proof(predicate, clause, false); +} + +/*---------- + * predicate_refuted_by_simple_clause + * Does the predicate refutation test for a "simple clause" predicate + * and a "simple clause" restriction. + * + * We return TRUE if able to prove the refutation, FALSE if not. + * + * Unlike the implication case, checking for equal() clauses isn't + * helpful. (XXX is it worth looking at "x vs NOT x" cases? Probably + * not seeing that canonicalization tries to get rid of NOTs.) + * + * When the predicate is of the form "foo IS NULL", we can conclude that + * the predicate is refuted if the clause is a strict operator or function + * that has "foo" as an input. See notes for implication case. + * + * Finally, we may be able to deduce something using knowledge about btree + * operator classes; this is encapsulated in btree_predicate_proof(). + *---------- + */ +static bool +predicate_refuted_by_simple_clause(Expr *predicate, Node *clause) +{ + /* First try the IS NULL case */ + if (predicate && IsA(predicate, NullTest) && + ((NullTest *) predicate)->nulltesttype == IS_NULL) + { + Expr *isnullarg = ((NullTest *) predicate)->arg; + + if (is_opclause(clause) && + list_member(((OpExpr *) clause)->args, isnullarg) && + op_strict(((OpExpr *) clause)->opno)) + return true; + if (is_funcclause(clause) && + list_member(((FuncExpr *) clause)->args, isnullarg) && + func_strict(((FuncExpr *) clause)->funcid)) + return true; + return false; /* we can't succeed below... */ + } + + /* Else try btree operator knowledge */ + return btree_predicate_proof(predicate, clause, true); +} + /* - * Define an "operator implication table" for btree operators ("strategies"). + * Define an "operator implication table" for btree operators ("strategies"), + * and a similar table for refutation. * * The strategy numbers defined by btree indexes (see access/skey.h) are: * (1) < (2) <= (3) = (4) >= (5) > @@ -263,8 +574,21 @@ predicate_implied_by_recurse(Node *clause, Node *predicate) * 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. + * For example, if clause is "Quantity > 10" and pred is "Quantity > 5" + * then we test "5 <= 10" which evals to true, so clause implies pred. + * + * Similarly, the interpretation of a BT_refute_table entry is: + * + * If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you + * want to determine whether "ATTR target_op CONST2" must be false, then + * you can use "CONST2 test_op CONST1" as a test. If this test returns true, + * then the target expression must be false; if the test returns false, then + * the target expression may be true. + * + * For example, 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. */ #define BTLT BTLessStrategyNumber @@ -274,58 +598,60 @@ predicate_implied_by_recurse(Node *clause, Node *predicate) #define BTGT BTGreaterStrategyNumber #define BTNE 6 -static const StrategyNumber - BT_implic_table[6][6] = { +static const StrategyNumber BT_implic_table[6][6] = { /* * The target operator: * - * LT LE EQ GE GT NE + * LT LE EQ GE GT NE */ - {BTGE, BTGE, 0, 0, 0, BTGE}, /* LT */ - {BTGT, BTGE, 0, 0, 0, BTGT}, /* LE */ + {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 */ + {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_implied_by_simple_clause - * Does the predicate implication test for a "simple clause" predicate - * and a "simple clause" restriction. + * btree_predicate_proof + * Does the predicate implication or refutation test for a "simple clause" + * predicate and a "simple clause" restriction, when both are simple + * operator clauses using related btree operators. * - * 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 refute_it == false, we want to prove the predicate true; + * when refute_it == true, we want to prove the predicate false. + * (There is enough common code to justify handling these two cases + * in one routine.) We return TRUE if able to make the proof, FALSE + * if not able to prove it. * - * 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 + * What we look for here is 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 + * operator class. We use the above operator implication tables 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 -predicate_implied_by_simple_clause(Expr *predicate, Node *clause) +btree_predicate_proof(Expr *predicate, Node *clause, bool refute_it) { Node *leftop, *rightop; @@ -356,29 +682,8 @@ predicate_implied_by_simple_clause(Expr *predicate, Node *clause) 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 + * Both expressions must be 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. @@ -579,7 +884,11 @@ predicate_implied_by_simple_clause(Expr *predicate, Node *clause) /* * Look up the "test" strategy number in the implication table */ - test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1]; + if (refute_it) + test_strategy = BT_refute_table[clause_strategy - 1][pred_strategy - 1]; + else + test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1]; + if (test_strategy == 0) { /* Can't determine implication using this interpretation */ @@ -608,13 +917,10 @@ predicate_implied_by_simple_clause(Expr *predicate, Node *clause) * 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 ... + * original clause_op. (pred_op is assumed to have been checked + * immutable by the caller.) 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) { @@ -663,7 +969,7 @@ predicate_implied_by_simple_clause(Expr *predicate, Node *clause) if (isNull) { - /* Treat a null result as false ... but it's a tad fishy ... */ + /* Treat a null result as non-proof ... but it's a tad fishy ... */ elog(DEBUG2, "null predicate test result"); return false; } diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c index 20ebfee712..6400ef566b 100644 --- a/src/backend/utils/misc/guc.c +++ b/src/backend/utils/misc/guc.c @@ -10,7 +10,7 @@ * Written by Peter Eisentraut . * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/utils/misc/guc.c,v 1.276 2005/07/21 18:06:12 momjian Exp $ + * $PostgreSQL: pgsql/src/backend/utils/misc/guc.c,v 1.277 2005/07/23 21:05:47 tgl Exp $ * *-------------------------------------------------------------------- */ @@ -435,6 +435,16 @@ static struct config_bool ConfigureNamesBool[] = &enable_hashjoin, true, NULL, NULL }, + { + {"enable_constraint_exclusion", PGC_USERSET, QUERY_TUNING_OTHER, + gettext_noop("Enables the planner's use of constraints in queries."), + gettext_noop("Constraints will be examined to exclude tables " + "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."), diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample index dc06658e7f..db8c28814d 100644 --- a/src/backend/utils/misc/postgresql.conf.sample +++ b/src/backend/utils/misc/postgresql.conf.sample @@ -173,6 +173,7 @@ # - Other Planner Options - #default_statistics_target = 10 # range 1-1000 +#enable_constraint_exclusion = off #from_collapse_limit = 8 #join_collapse_limit = 8 # 1 disables collapsing of explicit JOINs diff --git a/src/bin/psql/tab-complete.c b/src/bin/psql/tab-complete.c index 648ccadd4f..64737ac007 100644 --- a/src/bin/psql/tab-complete.c +++ b/src/bin/psql/tab-complete.c @@ -3,7 +3,7 @@ * * Copyright (c) 2000-2005, PostgreSQL Global Development Group * - * $PostgreSQL: pgsql/src/bin/psql/tab-complete.c,v 1.133 2005/06/22 21:14:30 tgl Exp $ + * $PostgreSQL: pgsql/src/bin/psql/tab-complete.c,v 1.134 2005/07/23 21:05:47 tgl Exp $ */ /*---------------------------------------------------------------------- @@ -540,6 +540,7 @@ psql_completion(char *text, int start, int end) "dynamic_library_path", "effective_cache_size", "enable_bitmapscan", + "enable_constraint_exclusion", "enable_hashagg", "enable_hashjoin", "enable_indexscan", diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h index 2f906c6a47..88e535dc9b 100644 --- a/src/include/nodes/relation.h +++ b/src/include/nodes/relation.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.116 2005/07/02 23:00:42 tgl Exp $ + * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.117 2005/07/23 21:05:48 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -516,6 +516,9 @@ typedef struct TidPath * AppendPath represents an Append plan, ie, successive execution of * several member plans. Currently it is only used to handle expansion * of inheritance trees. + * + * Note: it is possible for "subpaths" to contain only one, or even no, + * elements. These cases are optimized during create_append_plan. */ typedef struct AppendPath { @@ -524,10 +527,17 @@ typedef struct AppendPath } AppendPath; /* - * ResultPath represents use of a Result plan node, either to compute a - * variable-free targetlist or to gate execution of a subplan with a - * one-time (variable-free) qual condition. Note that in the former case - * path.parent will be NULL; in the latter case it is copied from the subpath. + * ResultPath represents use of a Result plan node. There are several + * applications for this: + * * To compute a variable-free targetlist (a "SELECT expressions" query). + * In this case subpath and path.parent will both be NULL. constantqual + * might or might not be empty ("SELECT expressions WHERE something"). + * * To gate execution of a subplan with a one-time (variable-free) qual + * condition. path.parent is copied from the subpath. + * * To substitute for a scan plan when we have proven that no rows in + * a table will satisfy the query. subpath is NULL but path.parent + * references the not-to-be-scanned relation, and constantqual is + * a constant FALSE. * * Note that constantqual is a list of bare clauses, not RestrictInfos. */ diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h index 5b6d282425..a6988e4599 100644 --- a/src/include/optimizer/cost.h +++ b/src/include/optimizer/cost.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/cost.h,v 1.68 2005/06/05 22:32:58 tgl Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/cost.h,v 1.69 2005/07/23 21:05:48 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -49,6 +49,7 @@ extern bool enable_hashagg; 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); diff --git a/src/include/optimizer/plancat.h b/src/include/optimizer/plancat.h index f8ecd36110..8a4c1e4941 100644 --- a/src/include/optimizer/plancat.h +++ b/src/include/optimizer/plancat.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/plancat.h,v 1.36 2005/06/05 22:32:58 tgl Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/plancat.h,v 1.37 2005/07/23 21:05:48 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -19,6 +19,8 @@ extern void get_relation_info(Oid relationObjectId, RelOptInfo *rel); +extern List *get_relation_constraints(Oid relationObjectId, RelOptInfo *rel); + extern List *build_physical_tlist(PlannerInfo *root, RelOptInfo *rel); extern List *find_inheritance_children(Oid inhparent); diff --git a/src/include/optimizer/predtest.h b/src/include/optimizer/predtest.h index cfa58f650a..0fc0d0f447 100644 --- a/src/include/optimizer/predtest.h +++ b/src/include/optimizer/predtest.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/predtest.h,v 1.1 2005/06/10 22:25:37 tgl Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/predtest.h,v 1.2 2005/07/23 21:05:48 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -19,5 +19,7 @@ extern bool predicate_implied_by(List *predicate_list, List *restrictinfo_list); +extern bool predicate_refuted_by(List *predicate_list, + List *restrictinfo_list); #endif /* PREDTEST_H */ diff --git a/src/test/regress/expected/rangefuncs.out b/src/test/regress/expected/rangefuncs.out index 7b70766742..3172d16b88 100644 --- a/src/test/regress/expected/rangefuncs.out +++ b/src/test/regress/expected/rangefuncs.out @@ -1,16 +1,17 @@ SELECT name, setting FROM pg_settings WHERE name LIKE 'enable%'; - name | setting --------------------+--------- - enable_bitmapscan | on - enable_hashagg | on - enable_hashjoin | on - enable_indexscan | on - enable_mergejoin | on - enable_nestloop | on - enable_seqscan | on - enable_sort | on - enable_tidscan | on -(9 rows) + name | setting +-----------------------------+--------- + enable_bitmapscan | on + enable_constraint_exclusion | off + enable_hashagg | on + enable_hashjoin | on + enable_indexscan | on + enable_mergejoin | on + enable_nestloop | on + enable_seqscan | on + enable_sort | on + enable_tidscan | on +(10 rows) CREATE TABLE foo2(fooid int, f2 int); INSERT INTO foo2 VALUES(1, 11); -- 2.40.0