Constraint Exclusion (Partitioning) - Initial Review requested

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);