On Mon, 2005-06-27 at 01:41 +0100, Simon Riggs wrote:
> I enclose a fully working implementation of Constraint Exclusion, a very
> basic form of Partitioning. Initial review is requested, to allow us all
> to assess what further work is required on this prior to Beta freeze.
>
> Patch against current cvstip; passes make check and all special tests.
It has been pointed out to me that the patch has a minor, yet basic
error in the planning. This has now been corrected in this patch.
It appears that my midnight-patch submission was not such a good idea
after all. My full and sincere apologies to anybody that tried and
failed on that patch. To err is human...
I have also now filled the gap for when all relations are excluded,
mentioned as question 1 in my original post.
I have now re-tested the patch against cvstip...
The special tests files are unchanged.
Performance tests and comments welcome.
Best Regards, Simon Riggs
Index: src/backend/commands/explain.c
===================================================================
RCS file: /projects/cvsroot/pgsql/src/backend/commands/explain.c,v
retrieving revision 1.137
diff -c -c -r1.137 explain.c
*** src/backend/commands/explain.c 4 Jun 2005 02:07:09 -0000 1.137
--- src/backend/commands/explain.c 18 Jul 2005 12:32:11 -0000
***************
*** 58,63 ****
--- 58,67 ----
const char *outer_name, int outer_varno, Plan *outer_plan,
const char *inner_name, int inner_varno, Plan *inner_plan,
StringInfo str, int indent, ExplainState *es);
+ static void show_result_qual(List *qual, const char *qlabel,
+ const char *outer_name, int outer_varno, Plan *outer_plan,
+ const char *inner_name, int inner_varno, Plan *inner_plan,
+ StringInfo str, int indent, ExplainState *es);
static void show_sort_keys(List *tlist, int nkeys, AttrNumber *keycols,
const char *qlabel,
StringInfo str, int indent, ExplainState *es);
***************
*** 786,792 ****
str, indent, es);
break;
case T_Result:
! show_upper_qual((List *) ((Result *) plan)->resconstantqual,
"One-Time Filter",
"subplan", OUTER, outerPlan(plan),
"", 0, NULL,
--- 790,796 ----
str, indent, es);
break;
case T_Result:
! show_result_qual((List *) ((Result *) plan)->resconstantqual,
"One-Time Filter",
"subplan", OUTER, outerPlan(plan),
"", 0, NULL,
***************
*** 1088,1093 ****
--- 1092,1127 ----
}
/*
+ * Show a qualifier expression for the special case of a Result node
+ */
+ static void
+ show_result_qual(List *qual, const char *qlabel,
+ const char *outer_name, int outer_varno, Plan *outer_plan,
+ const char *inner_name, int inner_varno, Plan *inner_plan,
+ StringInfo str, int indent, ExplainState *es)
+ {
+ int i;
+
+ /*
+ * If the qual is NIL, then Result node will treat that as false.
+ * Bypasses an eval step when we have passed a known-false qual
+ * through to the Result node at planning time.
+ */
+ if (qual == NIL)
+ {
+ /* And add to str */
+ for (i = 0; i < indent; i++)
+ appendStringInfo(str, " ");
+ appendStringInfo(str, " %s: false\n", qlabel);
+ }
+ else
+ show_upper_qual(qual, qlabel,
+ outer_name, outer_varno, outer_plan,
+ inner_name, inner_varno, inner_plan,
+ str, indent, es);
+ }
+
+ /*
* Show the sort keys for a Sort node.
*/
static void
Index: src/backend/executor/nodeResult.c
===================================================================
RCS file: /projects/cvsroot/pgsql/src/backend/executor/nodeResult.c,v
retrieving revision 1.31
diff -c -c -r1.31 nodeResult.c
*** src/backend/executor/nodeResult.c 24 Apr 2005 15:32:07 -0000 1.31
--- src/backend/executor/nodeResult.c 18 Jul 2005 12:32:11 -0000
***************
*** 79,85 ****
*/
if (node->rs_checkqual)
{
! bool qualResult = ExecQual((List *) node->resconstantqual,
econtext,
false);
--- 79,88 ----
*/
if (node->rs_checkqual)
{
! bool qualResult = false;
!
! if (node->resconstantqual != NULL)
! qualResult = ExecQual((List *) node->resconstantqual,
econtext,
false);
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 18 Jul 2005 12:32:13 -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,55 ----
/* 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 void propagate_rel_size( RelOptInfo *rel, RelOptInfo *childrel);
+ static bool RelationExclude(RelOptInfo *rel, Oid childOID);
+ static List *prepConstrQual(char *ConstrString);
static void set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
Index rti, RangeTblEntry *rte);
static void set_function_pathlist(PlannerInfo *root, RelOptInfo *rel,
***************
*** 250,255 ****
--- 256,268 ----
Oid parentOID = rte->relid;
List *subpaths = NIL;
ListCell *il;
+ bool makeChildPlan = false;
+
+ bool saveFirstPlan = false;
+ RelOptInfo *saverel;
+ int num_rels = 0;
+ int num_rels_included = 0;
+ RelOptInfo *childrel;
/*
* XXX for now, can't handle inherited expansion of FOR UPDATE/SHARE;
***************
*** 275,283 ****
int childRTindex = lfirst_int(il);
RangeTblEntry *childrte;
Oid childOID;
! RelOptInfo *childrel;
! ListCell *parentvars;
! ListCell *childvars;
childrte = rt_fetch(childRTindex, root->parse->rtable);
childOID = childrte->relid;
--- 288,295 ----
int childRTindex = lfirst_int(il);
RangeTblEntry *childrte;
Oid childOID;
!
! num_rels++;
childrte = rt_fetch(childRTindex, root->parse->rtable);
childOID = childrte->relid;
***************
*** 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.
--- 303,309 ----
/*
* 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 */
--- 315,552 ----
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
! */
! makeChildPlan = !RelationExclude(childrel, childOID);
!
! if (!makeChildPlan && num_rels == 1)
! saveFirstPlan = true;
!
! if (makeChildPlan || saveFirstPlan)
! {
! /*
! * 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);
!
! if (saveFirstPlan)
! {
! saverel = childrel;
! saveFirstPlan = false;
! }
! else
! {
! num_rels_included++;
! subpaths = lappend(subpaths, childrel->cheapest_total_path);
! propagate_rel_size(rel, childrel);
! }
! }
! }
!
! /*
! * If all rels excluded, then put in a Result node. Use the subpath to
! * first (parent) relation so that we always have at least one relation
! * for the query
! */
! if (num_rels_included == 0)
! {
! /*
! * We pass through a NIL list, which the Result node interprets as
! * false at execution time. This is easier than setting up a
! * qual node, passing it through and then have it evaluate to false
! */
! List *falsequal = NIL;
!
! /*
! * Reset rel's size information which we zeroed earlier to avoid
! * double counting. We know we will never execute this path
! * but best not to leave strange values in the plan, which
! * somebody may need later...
! */
! propagate_rel_size(rel, saverel);
!
! add_path(rel, (Path *) create_result_path(rel,
! saverel->cheapest_total_path, falsequal));
! }
! else
! {
! /*
! * Build an Append path and use 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);
! }
! /*
! * Propagate size information from the child back to the parent.
! * For simplicity, we use the largest widths from any child as the
! * parent estimates.
! */
! static void
! propagate_rel_size( RelOptInfo *rel, RelOptInfo *childrel)
! {
! ListCell *parentvars;
! ListCell *childvars;
! 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];
}
}
+ }
+
+
+ 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);
+
+ if (relation->rd_att->constr != NULL)
+ {
+ 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);
+
+ /* If the relation has no constraints, we cannot exclude it */
+ if (num_check == 0)
+ return false;
+
+ /* 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;
+ }
+ }
+
+ 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 18 Jul 2005 12:32:14 -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.274
diff -c -c -r1.274 guc.c
*** src/backend/utils/misc/guc.c 14 Jul 2005 05:13:42 -0000 1.274
--- src/backend/utils/misc/guc.c 18 Jul 2005 12:32:19 -0000
***************
*** 436,441 ****
--- 436,451 ----
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 18 Jul 2005 12:32:21 -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 18 Jul 2005 12:32:21 -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 */
Index: src/test/regress/expected/rangefuncs.out
===================================================================
RCS file: /projects/cvsroot/pgsql/src/test/regress/expected/rangefuncs.out,v
retrieving revision 1.11
diff -c -c -r1.11 rangefuncs.out
*** src/test/regress/expected/rangefuncs.out 21 Apr 2005 19:18:13 -0000 1.11
--- src/test/regress/expected/rangefuncs.out 18 Jul 2005 12:32:22 -0000
***************
*** 1,16 ****
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)
CREATE TABLE foo2(fooid int, f2 int);
INSERT INTO foo2 VALUES(1, 11);
--- 1,17 ----
SELECT name, setting FROM pg_settings WHERE name LIKE 'enable%';
! 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);
---------------------------(end of broadcast)---------------------------
TIP 3: Have you checked our extensive FAQ?
http://www.postgresql.org/docs/faq
