Separate predicate-testing code out of indxpath.c, making it a module

in its own right.  As proposed by Simon Riggs, but with some editorializing
of my own.

7 files changed, 728 insertions, 685 deletions

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 1b488d191e8..9c1874d5907 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -9,7 +9,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.182 2005/06/09 04:18:59 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.183 2005/06/10 22:25:36 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -17,30 +17,22 @@
 
 #include <math.h>
 
-#include "access/nbtree.h"
-#include "catalog/pg_amop.h"
-#include "catalog/pg_namespace.h"
+#include "access/skey.h"
 #include "catalog/pg_opclass.h"
 #include "catalog/pg_operator.h"
-#include "catalog/pg_proc.h"
 #include "catalog/pg_type.h"
-#include "executor/executor.h"
 #include "nodes/makefuncs.h"
 #include "optimizer/clauses.h"
 #include "optimizer/cost.h"
 #include "optimizer/pathnode.h"
 #include "optimizer/paths.h"
+#include "optimizer/predtest.h"
 #include "optimizer/restrictinfo.h"
-#include "optimizer/var.h"
-#include "parser/parse_expr.h"
-#include "rewrite/rewriteManip.h"
 #include "utils/builtins.h"
-#include "utils/catcache.h"
 #include "utils/lsyscache.h"
 #include "utils/memutils.h"
 #include "utils/pg_locale.h"
 #include "utils/selfuncs.h"
-#include "utils/syscache.h"
 
 
 /*
@@ -68,8 +60,6 @@ static bool match_clause_to_indexcol(IndexOptInfo *index,
 						 Relids outer_relids);
 static Oid indexable_operator(Expr *clause, Oid opclass,
 				   bool indexkey_on_left);
-static bool pred_test_recurse(Node *clause, Node *predicate);
-static bool pred_test_simple_clause(Expr *predicate, Node *clause);
 static Relids indexable_outerrelids(RelOptInfo *rel);
 static bool matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel,
 							  Relids outer_relids);
@@ -266,8 +256,8 @@ find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
 				all_clauses = list_concat(list_copy(clauses),
 										  outer_clauses);
 
-			if (!pred_test(index->indpred, all_clauses) ||
-				pred_test(index->indpred, outer_clauses))
+			if (!predicate_implied_by(index->indpred, all_clauses) ||
+				predicate_implied_by(index->indpred, outer_clauses))
 				continue;
 		}
 
@@ -497,9 +487,9 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
 	 * as can happen if there are multiple possibly usable indexes.  For
 	 * this we look only at plain IndexPath inputs, not at sub-OR clauses.
 	 * And we consider an index redundant if all its index conditions were
-	 * already used by earlier indexes.  (We could use pred_test() to have
-	 * a more intelligent, but much more expensive, check --- but in most
-	 * cases simple pointer equality should suffice, since after all the
+	 * already used by earlier indexes.  (We could use predicate_implied_by
+	 * to have a more intelligent, but much more expensive, check --- but in
+	 * most cases simple pointer equality should suffice, since after all the
 	 * index conditions are all coming from the same RestrictInfo lists.)
 	 *
 	 * XXX is there any risk of throwing away a useful partial index here
@@ -867,40 +857,6 @@ check_partial_indexes(PlannerInfo *root, RelOptInfo *rel)
 	List	   *restrictinfo_list = rel->baserestrictinfo;
 	ListCell   *ilist;
 
-	foreach(ilist, rel->indexlist)
-	{
-		IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
-
-		/*
-		 * If this is a partial index, we can only use it if it passes the
-		 * predicate test.
-		 */
-		if (index->indpred == NIL)
-			continue;			/* ignore non-partial indexes */
-
-		index->predOK = pred_test(index->indpred, restrictinfo_list);
-	}
-}
-
-/*
- * pred_test
- *	  Does the "predicate inclusion test" for partial indexes.
- *
- *	  Recursively checks whether the clauses in restrictinfo_list imply
- *	  that the given predicate is true.
- *
- *	  The top-level List structure of each list corresponds to an AND list.
- *	  We assume that eval_const_expressions() has been applied and so there
- *	  are no un-flattened ANDs or ORs (e.g., no AND immediately within an AND,
- *	  including AND just below the top-level List structure).
- *	  If this is not true we might fail to prove an implication that is
- *	  valid, but no worse consequences will ensue.
- */
-bool
-pred_test(List *predicate_list, List *restrictinfo_list)
-{
-	ListCell   *item;
-
 	/*
 	 * Note: if Postgres tried to optimize queries by forming equivalence
 	 * classes over equi-joined attributes (i.e., if it recognized that a
@@ -908,631 +864,24 @@ pred_test(List *predicate_list, List *restrictinfo_list)
 	 * an index on c.d), then we could use that equivalence class info
 	 * here with joininfo lists to do more complete tests for the usability
 	 * of a partial index.	For now, the test only uses restriction
-	 * clauses (those in restrictinfo_list). --Nels, Dec '92
+	 * clauses (those in baserestrictinfo). --Nels, Dec '92
 	 *
 	 * XXX as of 7.1, equivalence class info *is* available.  Consider
 	 * improving this code as foreseen by Nels.
 	 */
 
-	if (predicate_list == NIL)
-		return true;			/* no predicate: the index is usable */
-	if (restrictinfo_list == NIL)
-		return false;			/* no restriction clauses: the test must
-								 * fail */
-
-	/*
-	 * In all cases where the predicate is an AND-clause, pred_test_recurse()
-	 * will prefer to iterate over the predicate's components.  So we can
-	 * just do that to start with here, and eliminate the need for
-	 * pred_test_recurse() to handle a bare List on the predicate side.
-	 *
-	 * Logic is: restriction must imply each of the AND'ed predicate items.
-	 */
-	foreach(item, predicate_list)
-	{
-		if (!pred_test_recurse((Node *) restrictinfo_list, lfirst(item)))
-			return false;
-	}
-	return true;
-}
-
-
-/*----------
- * pred_test_recurse
- *	  Does the "predicate inclusion test" for non-NULL restriction and
- *	  predicate clauses.
- *
- * The logic followed here is ("=>" means "implies"):
- *	atom A => atom B iff:			pred_test_simple_clause says so
- *	atom A => AND-expr B iff:		A => each of B's components
- *	atom A => OR-expr B iff:		A => any of B's components
- *	AND-expr A => atom B iff:		any of A's components => B
- *	AND-expr A => AND-expr B iff:	A => each of B's components
- *	AND-expr A => OR-expr B iff:	A => any of B's components,
- *									*or* any of A's components => B
- *	OR-expr A => atom B iff:		each of A's components => B
- *	OR-expr A => AND-expr B iff:	A => each of B's components
- *	OR-expr A => OR-expr B iff:		each of A's components => any of B's
- *
- * An "atom" is anything other than an AND or OR node.  Notice that we don't
- * have any special logic to handle NOT nodes; these should have been pushed
- * down or eliminated where feasible by prepqual.c.
- *
- * We can't recursively expand either side first, but have to interleave
- * the expansions per the above rules, to be sure we handle all of these
- * examples:
- *		(x OR y) => (x OR y OR z)
- *		(x AND y AND z) => (x AND y)
- *		(x AND y) => ((x AND y) OR z)
- *		((x OR y) AND z) => (x OR y)
- * This is still not an exhaustive test, but it handles most normal cases
- * under the assumption that both inputs have been AND/OR flattened.
- *
- * A bare List node on the restriction side is interpreted as an AND clause,
- * in order to handle the top-level restriction List properly.  However we
- * need not consider a List on the predicate side since pred_test() already
- * expanded it.
- *
- * We have to be prepared to handle RestrictInfo nodes in the restrictinfo
- * tree, though not in the predicate tree.
- *----------
- */
-static bool
-pred_test_recurse(Node *clause, Node *predicate)
-{
-	ListCell   *item;
-
-	Assert(clause != NULL);
-	/* skip through RestrictInfo */
-	if (IsA(clause, RestrictInfo))
-	{
-		clause = (Node *) ((RestrictInfo *) clause)->clause;
-		Assert(clause != NULL);
-		Assert(!IsA(clause, RestrictInfo));
-	}
-	Assert(predicate != NULL);
-
-	/*
-	 * Since a restriction List clause is handled the same as an AND clause,
-	 * we can avoid duplicate code like this:
-	 */
-	if (and_clause(clause))
-		clause = (Node *) ((BoolExpr *) clause)->args;
-
-	if (IsA(clause, List))
-	{
-		if (and_clause(predicate))
-		{
-			/* AND-clause => AND-clause if A implies each of B's items */
-			foreach(item, ((BoolExpr *) predicate)->args)
-			{
-				if (!pred_test_recurse(clause, lfirst(item)))
-					return false;
-			}
-			return true;
-		}
-		else if (or_clause(predicate))
-		{
-			/* AND-clause => OR-clause if A implies any of B's items */
-			/* Needed to handle (x AND y) => ((x AND y) OR z) */
-			foreach(item, ((BoolExpr *) predicate)->args)
-			{
-				if (pred_test_recurse(clause, lfirst(item)))
-					return true;
-			}
-			/* Also check if any of A's items implies B */
-			/* Needed to handle ((x OR y) AND z) => (x OR y) */
-			foreach(item, (List *) clause)
-			{
-				if (pred_test_recurse(lfirst(item), predicate))
-					return true;
-			}
-			return false;
-		}
-		else
-		{
-			/* AND-clause => atom if any of A's items implies B */
-			foreach(item, (List *) clause)
-			{
-				if (pred_test_recurse(lfirst(item), predicate))
-					return true;
-			}
-			return false;
-		}
-	}
-	else if (or_clause(clause))
-	{
-		if (or_clause(predicate))
-		{
-			/*
-			 * OR-clause => OR-clause if each of A's items implies any of
-			 * B's items.  Messy but can't do it any more simply.
-			 */
-			foreach(item, ((BoolExpr *) clause)->args)
-			{
-				Node	   *citem = lfirst(item);
-				ListCell   *item2;
-
-				foreach(item2, ((BoolExpr *) predicate)->args)
-				{
-					if (pred_test_recurse(citem, lfirst(item2)))
-						break;
-				}
-				if (item2 == NULL)
-					return false; /* doesn't imply any of B's */
-			}
-			return true;
-		}
-		else
-		{
-			/* OR-clause => AND-clause if each of A's items implies B */
-			/* OR-clause => atom if each of A's items implies B */
-			foreach(item, ((BoolExpr *) clause)->args)
-			{
-				if (!pred_test_recurse(lfirst(item), predicate))
-					return false;
-			}
-			return true;
-		}
-	}
-	else
-	{
-		if (and_clause(predicate))
-		{
-			/* atom => AND-clause if A implies each of B's items */
-			foreach(item, ((BoolExpr *) predicate)->args)
-			{
-				if (!pred_test_recurse(clause, lfirst(item)))
-					return false;
-			}
-			return true;
-		}
-		else if (or_clause(predicate))
-		{
-			/* atom => OR-clause if A implies any of B's items */
-			foreach(item, ((BoolExpr *) predicate)->args)
-			{
-				if (pred_test_recurse(clause, lfirst(item)))
-					return true;
-			}
-			return false;
-		}
-		else
-		{
-			/* atom => atom is the base case */
-			return pred_test_simple_clause((Expr *) predicate, clause);
-		}
-	}
-}
-
-
-/*
- * Define an "operator implication table" for btree operators ("strategies").
- *
- * The strategy numbers defined by btree indexes (see access/skey.h) are:
- *		(1) <	(2) <=	 (3) =	 (4) >=   (5) >
- * and in addition we use (6) to represent <>.	<> is not a btree-indexable
- * operator, but we assume here that if the equality operator of a btree
- * opclass has a negator operator, the negator behaves as <> for the opclass.
- *
- * The interpretation of:
- *
- *		test_op = BT_implic_table[given_op-1][target_op-1]
- *
- * where test_op, given_op and target_op are strategy numbers (from 1 to 6)
- * of btree operators, is as follows:
- *
- *	 If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you
- *	 want to determine whether "ATTR target_op CONST2" must also be true, then
- *	 you can use "CONST2 test_op CONST1" as a test.  If this test returns true,
- *	 then the target expression must be true; if the test returns false, then
- *	 the target expression may be false.
- *
- * An entry where test_op == 0 means the implication cannot be determined,
- * i.e., this test should always be considered false.
- */
-
-#define BTLT BTLessStrategyNumber
-#define BTLE BTLessEqualStrategyNumber
-#define BTEQ BTEqualStrategyNumber
-#define BTGE BTGreaterEqualStrategyNumber
-#define BTGT BTGreaterStrategyNumber
-#define BTNE 6
-
-static const StrategyNumber
-			BT_implic_table[6][6] = {
-/*
- *			The target operator:
- *
- *	   LT	LE	   EQ	 GE    GT	 NE
- */
-	{BTGE, BTGE, 0, 0, 0, BTGE},	/* LT */
-	{BTGT, BTGE, 0, 0, 0, BTGT},	/* LE */
-	{BTGT, BTGE, BTEQ, BTLE, BTLT, BTNE},		/* EQ */
-	{0, 0, 0, BTLE, BTLT, BTLT},	/* GE */
-	{0, 0, 0, BTLE, BTLE, BTLE},	/* GT */
-	{0, 0, 0, 0, 0, BTEQ}		/* NE */
-};
-
-
-/*----------
- * pred_test_simple_clause
- *	  Does the "predicate inclusion test" for a "simple clause" predicate
- *	  and a "simple clause" restriction.
- *
- * We have three strategies for determining whether one simple clause
- * implies another:
- *
- * A simple and general way is to see if they are equal(); this works for any
- * kind of expression.	(Actually, there is an implied assumption that the
- * functions in the expression are immutable, ie dependent only on their input
- * arguments --- but this was checked for the predicate by CheckPredicate().)
- *
- * When the predicate is of the form "foo IS NOT NULL", we can conclude that
- * the predicate is implied if the clause is a strict operator or function
- * that has "foo" as an input.	In this case the clause must yield NULL when
- * "foo" is NULL, which we can take as equivalent to FALSE because we know
- * we are within an AND/OR subtree of a WHERE clause.  (Again, "foo" is
- * already known immutable, so the clause will certainly always fail.)
- *
- * Our other way works only for binary boolean opclauses of the form
- * "foo op constant", where "foo" is the same in both clauses.	The operators
- * and constants can be different but the operators must be in the same btree
- * operator class.	We use the above operator implication table to be able to
- * derive implications between nonidentical clauses.  (Note: "foo" is known
- * immutable, and constants are surely immutable, but we have to check that
- * the operators are too.  As of 8.0 it's possible for opclasses to contain
- * operators that are merely stable, and we dare not make deductions with
- * these.)
- *
- * Eventually, rtree operators could also be handled by defining an
- * appropriate "RT_implic_table" array.
- *----------
- */
-static bool
-pred_test_simple_clause(Expr *predicate, Node *clause)
-{
-	Node	   *leftop,
-			   *rightop;
-	Node	   *pred_var,
-			   *clause_var;
-	Const	   *pred_const,
-			   *clause_const;
-	bool		pred_var_on_left,
-				clause_var_on_left,
-				pred_op_negated;
-	Oid			pred_op,
-				clause_op,
-				pred_op_negator,
-				clause_op_negator,
-				test_op = InvalidOid;
-	Oid			opclass_id;
-	bool		found = false;
-	StrategyNumber pred_strategy,
-				clause_strategy,
-				test_strategy;
-	Oid			clause_subtype;
-	Expr	   *test_expr;
-	ExprState  *test_exprstate;
-	Datum		test_result;
-	bool		isNull;
-	CatCList   *catlist;
-	int			i;
-	EState	   *estate;
-	MemoryContext oldcontext;
-
-	/* First try the equal() test */
-	if (equal((Node *) predicate, clause))
-		return true;
-
-	/* Next try the IS NOT NULL case */
-	if (predicate && IsA(predicate, NullTest) &&
-		((NullTest *) predicate)->nulltesttype == IS_NOT_NULL)
-	{
-		Expr	   *nonnullarg = ((NullTest *) predicate)->arg;
-
-		if (is_opclause(clause) &&
-			list_member(((OpExpr *) clause)->args, nonnullarg) &&
-			op_strict(((OpExpr *) clause)->opno))
-			return true;
-		if (is_funcclause(clause) &&
-			list_member(((FuncExpr *) clause)->args, nonnullarg) &&
-			func_strict(((FuncExpr *) clause)->funcid))
-			return true;
-		return false;			/* we can't succeed below... */
-	}
-
-	/*
-	 * Can't do anything more unless they are both binary opclauses with a
-	 * Const on one side, and identical subexpressions on the other sides.
-	 * Note we don't have to think about binary relabeling of the Const
-	 * node, since that would have been folded right into the Const.
-	 *
-	 * If either Const is null, we also fail right away; this assumes that
-	 * the test operator will always be strict.
-	 */
-	if (!is_opclause(predicate))
-		return false;
-	leftop = get_leftop(predicate);
-	rightop = get_rightop(predicate);
-	if (rightop == NULL)
-		return false;			/* not a binary opclause */
-	if (IsA(rightop, Const))
-	{
-		pred_var = leftop;
-		pred_const = (Const *) rightop;
-		pred_var_on_left = true;
-	}
-	else if (IsA(leftop, Const))
-	{
-		pred_var = rightop;
-		pred_const = (Const *) leftop;
-		pred_var_on_left = false;
-	}
-	else
-		return false;			/* no Const to be found */
-	if (pred_const->constisnull)
-		return false;
-
-	if (!is_opclause(clause))
-		return false;
-	leftop = get_leftop((Expr *) clause);
-	rightop = get_rightop((Expr *) clause);
-	if (rightop == NULL)
-		return false;			/* not a binary opclause */
-	if (IsA(rightop, Const))
-	{
-		clause_var = leftop;
-		clause_const = (Const *) rightop;
-		clause_var_on_left = true;
-	}
-	else if (IsA(leftop, Const))
-	{
-		clause_var = rightop;
-		clause_const = (Const *) leftop;
-		clause_var_on_left = false;
-	}
-	else
-		return false;			/* no Const to be found */
-	if (clause_const->constisnull)
-		return false;
-
-	/*
-	 * Check for matching subexpressions on the non-Const sides.  We used
-	 * to only allow a simple Var, but it's about as easy to allow any
-	 * expression.	Remember we already know that the pred expression does
-	 * not contain any non-immutable functions, so identical expressions
-	 * should yield identical results.
-	 */
-	if (!equal(pred_var, clause_var))
-		return false;
-
-	/*
-	 * Okay, get the operators in the two clauses we're comparing. Commute
-	 * them if needed so that we can assume the variables are on the left.
-	 */
-	pred_op = ((OpExpr *) predicate)->opno;
-	if (!pred_var_on_left)
-	{
-		pred_op = get_commutator(pred_op);
-		if (!OidIsValid(pred_op))
-			return false;
-	}
-
-	clause_op = ((OpExpr *) clause)->opno;
-	if (!clause_var_on_left)
-	{
-		clause_op = get_commutator(clause_op);
-		if (!OidIsValid(clause_op))
-			return false;
-	}
-
-	/*
-	 * Try to find a btree opclass containing the needed operators.
-	 *
-	 * We must find a btree opclass that contains both operators, else the
-	 * implication can't be determined.  Also, the pred_op has to be of
-	 * default subtype (implying left and right input datatypes are the
-	 * same); otherwise it's unsafe to put the pred_const on the left side
-	 * of the test.  Also, the opclass must contain a suitable test
-	 * operator matching the clause_const's type (which we take to mean
-	 * that it has the same subtype as the original clause_operator).
-	 *
-	 * If there are multiple matching opclasses, assume we can use any one to
-	 * determine the logical relationship of the two operators and the
-	 * correct corresponding test operator.  This should work for any
-	 * logically consistent opclasses.
-	 */
-	catlist = SearchSysCacheList(AMOPOPID, 1,
-								 ObjectIdGetDatum(pred_op),
-								 0, 0, 0);
-
-	/*
-	 * If we couldn't find any opclass containing the pred_op, perhaps it
-	 * is a <> operator.  See if it has a negator that is in an opclass.
-	 */
-	pred_op_negated = false;
-	if (catlist->n_members == 0)
-	{
-		pred_op_negator = get_negator(pred_op);
-		if (OidIsValid(pred_op_negator))
-		{
-			pred_op_negated = true;
-			ReleaseSysCacheList(catlist);
-			catlist = SearchSysCacheList(AMOPOPID, 1,
-									   ObjectIdGetDatum(pred_op_negator),
-										 0, 0, 0);
-		}
-	}
-
-	/* Also may need the clause_op's negator */
-	clause_op_negator = get_negator(clause_op);
-
-	/* Now search the opclasses */
-	for (i = 0; i < catlist->n_members; i++)
-	{
-		HeapTuple	pred_tuple = &catlist->members[i]->tuple;
-		Form_pg_amop pred_form = (Form_pg_amop) GETSTRUCT(pred_tuple);
-		HeapTuple	clause_tuple;
-
-		opclass_id = pred_form->amopclaid;
-
-		/* must be btree */
-		if (!opclass_is_btree(opclass_id))
-			continue;
-		/* predicate operator must be default within this opclass */
-		if (pred_form->amopsubtype != InvalidOid)
-			continue;
-
-		/* Get the predicate operator's btree strategy number */
-		pred_strategy = (StrategyNumber) pred_form->amopstrategy;
-		Assert(pred_strategy >= 1 && pred_strategy <= 5);
-
-		if (pred_op_negated)
-		{
-			/* Only consider negators that are = */
-			if (pred_strategy != BTEqualStrategyNumber)
-				continue;
-			pred_strategy = BTNE;
-		}
-
-		/*
-		 * From the same opclass, find a strategy number for the
-		 * clause_op, if possible
-		 */
-		clause_tuple = SearchSysCache(AMOPOPID,
-									  ObjectIdGetDatum(clause_op),
-									  ObjectIdGetDatum(opclass_id),
-									  0, 0);
-		if (HeapTupleIsValid(clause_tuple))
-		{
-			Form_pg_amop clause_form = (Form_pg_amop) GETSTRUCT(clause_tuple);
-
-			/* Get the restriction clause operator's strategy/subtype */
-			clause_strategy = (StrategyNumber) clause_form->amopstrategy;
-			Assert(clause_strategy >= 1 && clause_strategy <= 5);
-			clause_subtype = clause_form->amopsubtype;
-			ReleaseSysCache(clause_tuple);
-		}
-		else if (OidIsValid(clause_op_negator))
-		{
-			clause_tuple = SearchSysCache(AMOPOPID,
-									 ObjectIdGetDatum(clause_op_negator),
-										  ObjectIdGetDatum(opclass_id),
-										  0, 0);
-			if (HeapTupleIsValid(clause_tuple))
-			{
-				Form_pg_amop clause_form = (Form_pg_amop) GETSTRUCT(clause_tuple);
-
-				/* Get the restriction clause operator's strategy/subtype */
-				clause_strategy = (StrategyNumber) clause_form->amopstrategy;
-				Assert(clause_strategy >= 1 && clause_strategy <= 5);
-				clause_subtype = clause_form->amopsubtype;
-				ReleaseSysCache(clause_tuple);
-
-				/* Only consider negators that are = */
-				if (clause_strategy != BTEqualStrategyNumber)
-					continue;
-				clause_strategy = BTNE;
-			}
-			else
-				continue;
-		}
-		else
-			continue;
-
-		/*
-		 * Look up the "test" strategy number in the implication table
-		 */
-		test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1];
-		if (test_strategy == 0)
-		{
-			/* Can't determine implication using this interpretation */
-			continue;
-		}
-
-		/*
-		 * See if opclass has an operator for the test strategy and the
-		 * clause datatype.
-		 */
-		if (test_strategy == BTNE)
-		{
-			test_op = get_opclass_member(opclass_id, clause_subtype,
-										 BTEqualStrategyNumber);
-			if (OidIsValid(test_op))
-				test_op = get_negator(test_op);
-		}
-		else
-		{
-			test_op = get_opclass_member(opclass_id, clause_subtype,
-										 test_strategy);
-		}
-		if (OidIsValid(test_op))
-		{
-			/*
-			 * Last check: test_op must be immutable.
-			 *
-			 * Note that we require only the test_op to be immutable, not the
-			 * original clause_op.	(pred_op must be immutable, else it
-			 * would not be allowed in an index predicate.)  Essentially
-			 * we are assuming that the opclass is consistent even if it
-			 * contains operators that are merely stable.
-			 */
-			if (op_volatile(test_op) == PROVOLATILE_IMMUTABLE)
-			{
-				found = true;
-				break;
-			}
-		}
-	}
-
-	ReleaseSysCacheList(catlist);
-
-	if (!found)
+	foreach(ilist, rel->indexlist)
 	{
-		/* couldn't find a btree opclass to interpret the operators */
-		return false;
-	}
-
-	/*
-	 * Evaluate the test.  For this we need an EState.
-	 */
-	estate = CreateExecutorState();
-
-	/* We can use the estate's working context to avoid memory leaks. */
-	oldcontext = MemoryContextSwitchTo(estate->es_query_cxt);
-
-	/* Build expression tree */
-	test_expr = make_opclause(test_op,
-							  BOOLOID,
-							  false,
-							  (Expr *) pred_const,
-							  (Expr *) clause_const);
-
-	/* Prepare it for execution */
-	test_exprstate = ExecPrepareExpr(test_expr, estate);
-
-	/* And execute it. */
-	test_result = ExecEvalExprSwitchContext(test_exprstate,
-										  GetPerTupleExprContext(estate),
-											&isNull, NULL);
-
-	/* Get back to outer memory context */
-	MemoryContextSwitchTo(oldcontext);
+		IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
 
-	/* Release all the junk we just created */
-	FreeExecutorState(estate);
+		if (index->indpred == NIL)
+			continue;			/* ignore non-partial indexes */
 
-	if (isNull)
-	{
-		/* Treat a null result as false ... but it's a tad fishy ... */
-		elog(DEBUG2, "null predicate test result");
-		return false;
+		index->predOK = predicate_implied_by(index->indpred,
+											 restrictinfo_list);
 	}
-	return DatumGetBool(test_result);
 }
 
-
 /****************************************************************************
  *				----  ROUTINES TO CHECK JOIN CLAUSES  ----
  ****************************************************************************/
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 5c1142cd0e1..76812e2e4b3 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.191 2005/06/05 22:32:55 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.192 2005/06/10 22:25:36 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -22,9 +22,9 @@
 #include "nodes/nodeFuncs.h"
 #include "optimizer/clauses.h"
 #include "optimizer/cost.h"
-#include "optimizer/paths.h"
 #include "optimizer/plancat.h"
 #include "optimizer/planmain.h"
+#include "optimizer/predtest.h"
 #include "optimizer/restrictinfo.h"
 #include "optimizer/tlist.h"
 #include "optimizer/var.h"
@@ -782,8 +782,8 @@ create_indexscan_plan(PlannerInfo *root,
 	 * spot duplicate RestrictInfos, so we try that first.  In some situations
 	 * (particularly with OR'd index conditions) we may have scan_clauses
 	 * that are not equal to, but are logically implied by, the index quals;
-	 * so we also try a pred_test() check to see if we can discard quals
-	 * that way.
+	 * so we also try a predicate_implied_by() check to see if we can discard
+	 * quals that way.
 	 *
 	 * While at it, we strip off the RestrictInfos to produce a list of
 	 * plain expressions.
@@ -796,7 +796,8 @@ create_indexscan_plan(PlannerInfo *root,
 		Assert(IsA(rinfo, RestrictInfo));
 		if (list_member_ptr(nonlossy_indexquals, rinfo))
 			continue;
-		if (pred_test(list_make1(rinfo->clause), nonlossy_indexquals))
+		if (predicate_implied_by(list_make1(rinfo->clause),
+								 nonlossy_indexquals))
 			continue;
 		qpqual = lappend(qpqual, rinfo->clause);
 	}
@@ -878,7 +879,7 @@ create_bitmap_scan_plan(PlannerInfo *root,
 	 * clauses, so we try that first.  In some situations (particularly with
 	 * OR'd index conditions) we may have scan_clauses that are not equal to,
 	 * but are logically implied by, the index quals; so we also try a
-	 * pred_test() check to see if we can discard quals that way.
+	 * predicate_implied_by() check to see if we can discard quals that way.
 	 */
 	qpqual = NIL;
 	foreach(l, scan_clauses)
@@ -887,7 +888,8 @@ create_bitmap_scan_plan(PlannerInfo *root,
 
 		if (list_member(indexquals, clause))
 			continue;
-		if (pred_test(list_make1(clause), indexquals))
+		if (predicate_implied_by(list_make1(clause),
+								 indexquals))
 			continue;
 		qpqual = lappend(qpqual, clause);
 	}
diff --git a/src/backend/optimizer/util/Makefile b/src/backend/optimizer/util/Makefile
index 6d84e51ee96..15799f8b4e1 100644
--- a/src/backend/optimizer/util/Makefile
+++ b/src/backend/optimizer/util/Makefile
@@ -4,7 +4,7 @@
 #    Makefile for optimizer/util
 #
 # IDENTIFICATION
-#    $PostgreSQL: pgsql/src/backend/optimizer/util/Makefile,v 1.15 2003/11/29 19:51:51 pgsql Exp $
+#    $PostgreSQL: pgsql/src/backend/optimizer/util/Makefile,v 1.16 2005/06/10 22:25:36 tgl Exp $
 #
 #-------------------------------------------------------------------------
 
@@ -12,8 +12,8 @@ subdir = src/backend/optimizer/util
 top_builddir = ../../../..
 include $(top_builddir)/src/Makefile.global
 
-OBJS = restrictinfo.o clauses.o plancat.o \
-       joininfo.o pathnode.o relnode.o tlist.o var.o
+OBJS = clauses.o joininfo.o pathnode.o plancat.o predtest.o \
+       relnode.o restrictinfo.o tlist.o var.o
 
 all: SUBSYS.o
 
diff --git a/src/backend/optimizer/util/predtest.c b/src/backend/optimizer/util/predtest.c
new file mode 100644
index 00000000000..38c43ea027c
--- /dev/null
+++ b/src/backend/optimizer/util/predtest.c
@@ -0,0 +1,671 @@
+/*-------------------------------------------------------------------------
+ *
+ * predtest.c
+ *	  Routines to attempt to prove logical implications between predicate
+ *	  expressions.
+ *
+ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/util/predtest.c,v 1.1 2005/06/10 22:25:36 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "catalog/pg_amop.h"
+#include "catalog/pg_proc.h"
+#include "catalog/pg_type.h"
+#include "executor/executor.h"
+#include "optimizer/clauses.h"
+#include "optimizer/predtest.h"
+#include "utils/catcache.h"
+#include "utils/lsyscache.h"
+#include "utils/syscache.h"
+
+
+static bool predicate_implied_by_recurse(Node *clause, Node *predicate);
+static bool predicate_implied_by_simple_clause(Expr *predicate, Node *clause);
+
+
+/*
+ * predicate_implied_by
+ *	  Recursively checks whether the clauses in restrictinfo_list imply
+ *	  that the given predicate is true.
+ *
+ *	  The top-level List structure of each list corresponds to an AND list.
+ *	  We assume that eval_const_expressions() has been applied and so there
+ *	  are no un-flattened ANDs or ORs (e.g., no AND immediately within an AND,
+ *	  including AND just below the top-level List structure).
+ *	  If this is not true we might fail to prove an implication that is
+ *	  valid, but no worse consequences will ensue.
+ */
+bool
+predicate_implied_by(List *predicate_list, List *restrictinfo_list)
+{
+	ListCell   *item;
+
+	if (predicate_list == NIL)
+		return true;			/* no predicate: implication is vacuous */
+	if (restrictinfo_list == NIL)
+		return false;			/* no restriction: implication must fail */
+
+	/*
+	 * In all cases where the predicate is an AND-clause,
+	 * predicate_implied_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 must imply each of the AND'ed predicate items.
+	 */
+	foreach(item, predicate_list)
+	{
+		if (!predicate_implied_by_recurse((Node *) restrictinfo_list,
+										  lfirst(item)))
+			return false;
+	}
+	return true;
+}
+
+
+/*----------
+ * predicate_implied_by_recurse
+ *	  Does the predicate implication test for non-NULL restriction and
+ *	  predicate clauses.
+ *
+ * The logic followed here is ("=>" means "implies"):
+ *	atom A => atom B iff:			predicate_implied_by_simple_clause says so
+ *	atom A => AND-expr B iff:		A => each of B's components
+ *	atom A => OR-expr B iff:		A => any of B's components
+ *	AND-expr A => atom B iff:		any of A's components => B
+ *	AND-expr A => AND-expr B iff:	A => each of B's components
+ *	AND-expr A => OR-expr B iff:	A => any of B's components,
+ *									*or* any of A's components => B
+ *	OR-expr A => atom B iff:		each of A's components => B
+ *	OR-expr A => AND-expr B iff:	A => each of B's components
+ *	OR-expr A => OR-expr B iff:		each of A's components => any of B's
+ *
+ * An "atom" is anything other than an AND or OR node.  Notice that we don't
+ * have any special logic to handle NOT nodes; these should have been pushed
+ * down or eliminated where feasible by prepqual.c.
+ *
+ * We can't recursively expand either side first, but have to interleave
+ * the expansions per the above rules, to be sure we handle all of these
+ * examples:
+ *		(x OR y) => (x OR y OR z)
+ *		(x AND y AND z) => (x AND y)
+ *		(x AND y) => ((x AND y) OR z)
+ *		((x OR y) AND z) => (x OR y)
+ * This is still not an exhaustive test, but it handles most normal cases
+ * under the assumption that both inputs have been AND/OR flattened.
+ *
+ * A bare List node on the restriction side is interpreted as an AND clause,
+ * in order to handle the top-level restriction List properly.  However we
+ * need not consider a List on the predicate side since predicate_implied_by()
+ * already expanded it.
+ *
+ * We have to be prepared to handle RestrictInfo nodes in the restrictinfo
+ * tree, though not in the predicate tree.
+ *----------
+ */
+static bool
+predicate_implied_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;
+
+	if (IsA(clause, List))
+	{
+		if (and_clause(predicate))
+		{
+			/* AND-clause => AND-clause if A implies each of B's items */
+			foreach(item, ((BoolExpr *) predicate)->args)
+			{
+				if (!predicate_implied_by_recurse(clause, lfirst(item)))
+					return false;
+			}
+			return true;
+		}
+		else if (or_clause(predicate))
+		{
+			/* AND-clause => OR-clause if A implies any of B's items */
+			/* Needed to handle (x AND y) => ((x AND y) OR z) */
+			foreach(item, ((BoolExpr *) predicate)->args)
+			{
+				if (predicate_implied_by_recurse(clause, lfirst(item)))
+					return true;
+			}
+			/* Also check if any of A's items implies B */
+			/* Needed to handle ((x OR y) AND z) => (x OR y) */
+			foreach(item, (List *) clause)
+			{
+				if (predicate_implied_by_recurse(lfirst(item), predicate))
+					return true;
+			}
+			return false;
+		}
+		else
+		{
+			/* AND-clause => atom if any of A's items implies B */
+			foreach(item, (List *) clause)
+			{
+				if (predicate_implied_by_recurse(lfirst(item), predicate))
+					return true;
+			}
+			return false;
+		}
+	}
+	else if (or_clause(clause))
+	{
+		if (or_clause(predicate))
+		{
+			/*
+			 * OR-clause => OR-clause if each of A's items implies any of
+			 * B's items.  Messy but can't do it any more simply.
+			 */
+			foreach(item, ((BoolExpr *) clause)->args)
+			{
+				Node	   *citem = lfirst(item);
+				ListCell   *item2;
+
+				foreach(item2, ((BoolExpr *) predicate)->args)
+				{
+					if (predicate_implied_by_recurse(citem, lfirst(item2)))
+						break;
+				}
+				if (item2 == NULL)
+					return false; /* doesn't imply any of B's */
+			}
+			return true;
+		}
+		else
+		{
+			/* OR-clause => AND-clause if each of A's items implies B */
+			/* OR-clause => atom if each of A's items implies B */
+			foreach(item, ((BoolExpr *) clause)->args)
+			{
+				if (!predicate_implied_by_recurse(lfirst(item), predicate))
+					return false;
+			}
+			return true;
+		}
+	}
+	else
+	{
+		if (and_clause(predicate))
+		{
+			/* atom => AND-clause if A implies each of B's items */
+			foreach(item, ((BoolExpr *) predicate)->args)
+			{
+				if (!predicate_implied_by_recurse(clause, lfirst(item)))
+					return false;
+			}
+			return true;
+		}
+		else if (or_clause(predicate))
+		{
+			/* atom => OR-clause if A implies any of B's items */
+			foreach(item, ((BoolExpr *) predicate)->args)
+			{
+				if (predicate_implied_by_recurse(clause, lfirst(item)))
+					return true;
+			}
+			return false;
+		}
+		else
+		{
+			/* atom => atom is the base case */
+			return predicate_implied_by_simple_clause((Expr *) predicate,
+													  clause);
+		}
+	}
+}
+
+
+/*
+ * Define an "operator implication table" for btree operators ("strategies").
+ *
+ * The strategy numbers defined by btree indexes (see access/skey.h) are:
+ *		(1) <	(2) <=	 (3) =	 (4) >=   (5) >
+ * and in addition we use (6) to represent <>.	<> is not a btree-indexable
+ * operator, but we assume here that if the equality operator of a btree
+ * opclass has a negator operator, the negator behaves as <> for the opclass.
+ *
+ * The interpretation of:
+ *
+ *		test_op = BT_implic_table[given_op-1][target_op-1]
+ *
+ * where test_op, given_op and target_op are strategy numbers (from 1 to 6)
+ * of btree operators, is as follows:
+ *
+ *	 If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you
+ *	 want to determine whether "ATTR target_op CONST2" must also be true, then
+ *	 you can use "CONST2 test_op CONST1" as a test.  If this test returns true,
+ *	 then the target expression must be true; if the test returns false, then
+ *	 the target expression may be false.
+ *
+ * An entry where test_op == 0 means the implication cannot be determined,
+ * i.e., this test should always be considered false.
+ */
+
+#define BTLT BTLessStrategyNumber
+#define BTLE BTLessEqualStrategyNumber
+#define BTEQ BTEqualStrategyNumber
+#define BTGE BTGreaterEqualStrategyNumber
+#define BTGT BTGreaterStrategyNumber
+#define BTNE 6
+
+static const StrategyNumber
+			BT_implic_table[6][6] = {
+/*
+ *			The target operator:
+ *
+ *	 LT    LE    EQ GE GT NE
+ */
+	{BTGE, BTGE, 0, 0, 0, BTGE},			/* LT */
+	{BTGT, BTGE, 0, 0, 0, BTGT},			/* LE */
+	{BTGT, BTGE, BTEQ, BTLE, BTLT, BTNE},	/* EQ */
+	{0, 0, 0, BTLE, BTLT, BTLT},			/* GE */
+	{0, 0, 0, BTLE, BTLE, BTLE},			/* GT */
+	{0, 0, 0, 0, 0, BTEQ}					/* NE */
+};
+
+
+/*----------
+ * predicate_implied_by_simple_clause
+ *	  Does the predicate implication test for a "simple clause" predicate
+ *	  and a "simple clause" restriction.
+ *
+ * We have three strategies for determining whether one simple clause
+ * implies another:
+ *
+ * A simple and general way is to see if they are equal(); this works for any
+ * kind of expression.	(Actually, there is an implied assumption that the
+ * functions in the expression are immutable, ie dependent only on their input
+ * arguments --- but this was checked for the predicate by CheckPredicate().)
+ *
+ * When the predicate is of the form "foo IS NOT NULL", we can conclude that
+ * the predicate is implied if the clause is a strict operator or function
+ * that has "foo" as an input.	In this case the clause must yield NULL when
+ * "foo" is NULL, which we can take as equivalent to FALSE because we know
+ * we are within an AND/OR subtree of a WHERE clause.  (Again, "foo" is
+ * already known immutable, so the clause will certainly always fail.)
+ *
+ * Our other way works only for binary boolean opclauses of the form
+ * "foo op constant", where "foo" is the same in both clauses.	The operators
+ * and constants can be different but the operators must be in the same btree
+ * operator class.	We use the above operator implication table to be able to
+ * derive implications between nonidentical clauses.  (Note: "foo" is known
+ * immutable, and constants are surely immutable, but we have to check that
+ * the operators are too.  As of 8.0 it's possible for opclasses to contain
+ * operators that are merely stable, and we dare not make deductions with
+ * these.)
+ *
+ * Eventually, rtree operators could also be handled by defining an
+ * appropriate "RT_implic_table" array.
+ *----------
+ */
+static bool
+predicate_implied_by_simple_clause(Expr *predicate, Node *clause)
+{
+	Node	   *leftop,
+			   *rightop;
+	Node	   *pred_var,
+			   *clause_var;
+	Const	   *pred_const,
+			   *clause_const;
+	bool		pred_var_on_left,
+				clause_var_on_left,
+				pred_op_negated;
+	Oid			pred_op,
+				clause_op,
+				pred_op_negator,
+				clause_op_negator,
+				test_op = InvalidOid;
+	Oid			opclass_id;
+	bool		found = false;
+	StrategyNumber pred_strategy,
+				clause_strategy,
+				test_strategy;
+	Oid			clause_subtype;
+	Expr	   *test_expr;
+	ExprState  *test_exprstate;
+	Datum		test_result;
+	bool		isNull;
+	CatCList   *catlist;
+	int			i;
+	EState	   *estate;
+	MemoryContext oldcontext;
+
+	/* First try the equal() test */
+	if (equal((Node *) predicate, clause))
+		return true;
+
+	/* Next try the IS NOT NULL case */
+	if (predicate && IsA(predicate, NullTest) &&
+		((NullTest *) predicate)->nulltesttype == IS_NOT_NULL)
+	{
+		Expr	   *nonnullarg = ((NullTest *) predicate)->arg;
+
+		if (is_opclause(clause) &&
+			list_member(((OpExpr *) clause)->args, nonnullarg) &&
+			op_strict(((OpExpr *) clause)->opno))
+			return true;
+		if (is_funcclause(clause) &&
+			list_member(((FuncExpr *) clause)->args, nonnullarg) &&
+			func_strict(((FuncExpr *) clause)->funcid))
+			return true;
+		return false;			/* we can't succeed below... */
+	}
+
+	/*
+	 * Can't do anything more unless they are both binary opclauses with a
+	 * Const on one side, and identical subexpressions on the other sides.
+	 * Note we don't have to think about binary relabeling of the Const
+	 * node, since that would have been folded right into the Const.
+	 *
+	 * If either Const is null, we also fail right away; this assumes that
+	 * the test operator will always be strict.
+	 */
+	if (!is_opclause(predicate))
+		return false;
+	leftop = get_leftop(predicate);
+	rightop = get_rightop(predicate);
+	if (rightop == NULL)
+		return false;			/* not a binary opclause */
+	if (IsA(rightop, Const))
+	{
+		pred_var = leftop;
+		pred_const = (Const *) rightop;
+		pred_var_on_left = true;
+	}
+	else if (IsA(leftop, Const))
+	{
+		pred_var = rightop;
+		pred_const = (Const *) leftop;
+		pred_var_on_left = false;
+	}
+	else
+		return false;			/* no Const to be found */
+	if (pred_const->constisnull)
+		return false;
+
+	if (!is_opclause(clause))
+		return false;
+	leftop = get_leftop((Expr *) clause);
+	rightop = get_rightop((Expr *) clause);
+	if (rightop == NULL)
+		return false;			/* not a binary opclause */
+	if (IsA(rightop, Const))
+	{
+		clause_var = leftop;
+		clause_const = (Const *) rightop;
+		clause_var_on_left = true;
+	}
+	else if (IsA(leftop, Const))
+	{
+		clause_var = rightop;
+		clause_const = (Const *) leftop;
+		clause_var_on_left = false;
+	}
+	else
+		return false;			/* no Const to be found */
+	if (clause_const->constisnull)
+		return false;
+
+	/*
+	 * Check for matching subexpressions on the non-Const sides.  We used
+	 * to only allow a simple Var, but it's about as easy to allow any
+	 * expression.	Remember we already know that the pred expression does
+	 * not contain any non-immutable functions, so identical expressions
+	 * should yield identical results.
+	 */
+	if (!equal(pred_var, clause_var))
+		return false;
+
+	/*
+	 * Okay, get the operators in the two clauses we're comparing. Commute
+	 * them if needed so that we can assume the variables are on the left.
+	 */
+	pred_op = ((OpExpr *) predicate)->opno;
+	if (!pred_var_on_left)
+	{
+		pred_op = get_commutator(pred_op);
+		if (!OidIsValid(pred_op))
+			return false;
+	}
+
+	clause_op = ((OpExpr *) clause)->opno;
+	if (!clause_var_on_left)
+	{
+		clause_op = get_commutator(clause_op);
+		if (!OidIsValid(clause_op))
+			return false;
+	}
+
+	/*
+	 * Try to find a btree opclass containing the needed operators.
+	 *
+	 * We must find a btree opclass that contains both operators, else the
+	 * implication can't be determined.  Also, the pred_op has to be of
+	 * default subtype (implying left and right input datatypes are the
+	 * same); otherwise it's unsafe to put the pred_const on the left side
+	 * of the test.  Also, the opclass must contain a suitable test
+	 * operator matching the clause_const's type (which we take to mean
+	 * that it has the same subtype as the original clause_operator).
+	 *
+	 * If there are multiple matching opclasses, assume we can use any one to
+	 * determine the logical relationship of the two operators and the
+	 * correct corresponding test operator.  This should work for any
+	 * logically consistent opclasses.
+	 */
+	catlist = SearchSysCacheList(AMOPOPID, 1,
+								 ObjectIdGetDatum(pred_op),
+								 0, 0, 0);
+
+	/*
+	 * If we couldn't find any opclass containing the pred_op, perhaps it
+	 * is a <> operator.  See if it has a negator that is in an opclass.
+	 */
+	pred_op_negated = false;
+	if (catlist->n_members == 0)
+	{
+		pred_op_negator = get_negator(pred_op);
+		if (OidIsValid(pred_op_negator))
+		{
+			pred_op_negated = true;
+			ReleaseSysCacheList(catlist);
+			catlist = SearchSysCacheList(AMOPOPID, 1,
+									   ObjectIdGetDatum(pred_op_negator),
+										 0, 0, 0);
+		}
+	}
+
+	/* Also may need the clause_op's negator */
+	clause_op_negator = get_negator(clause_op);
+
+	/* Now search the opclasses */
+	for (i = 0; i < catlist->n_members; i++)
+	{
+		HeapTuple	pred_tuple = &catlist->members[i]->tuple;
+		Form_pg_amop pred_form = (Form_pg_amop) GETSTRUCT(pred_tuple);
+		HeapTuple	clause_tuple;
+
+		opclass_id = pred_form->amopclaid;
+
+		/* must be btree */
+		if (!opclass_is_btree(opclass_id))
+			continue;
+		/* predicate operator must be default within this opclass */
+		if (pred_form->amopsubtype != InvalidOid)
+			continue;
+
+		/* Get the predicate operator's btree strategy number */
+		pred_strategy = (StrategyNumber) pred_form->amopstrategy;
+		Assert(pred_strategy >= 1 && pred_strategy <= 5);
+
+		if (pred_op_negated)
+		{
+			/* Only consider negators that are = */
+			if (pred_strategy != BTEqualStrategyNumber)
+				continue;
+			pred_strategy = BTNE;
+		}
+
+		/*
+		 * From the same opclass, find a strategy number for the
+		 * clause_op, if possible
+		 */
+		clause_tuple = SearchSysCache(AMOPOPID,
+									  ObjectIdGetDatum(clause_op),
+									  ObjectIdGetDatum(opclass_id),
+									  0, 0);
+		if (HeapTupleIsValid(clause_tuple))
+		{
+			Form_pg_amop clause_form = (Form_pg_amop) GETSTRUCT(clause_tuple);
+
+			/* Get the restriction clause operator's strategy/subtype */
+			clause_strategy = (StrategyNumber) clause_form->amopstrategy;
+			Assert(clause_strategy >= 1 && clause_strategy <= 5);
+			clause_subtype = clause_form->amopsubtype;
+			ReleaseSysCache(clause_tuple);
+		}
+		else if (OidIsValid(clause_op_negator))
+		{
+			clause_tuple = SearchSysCache(AMOPOPID,
+									 ObjectIdGetDatum(clause_op_negator),
+										  ObjectIdGetDatum(opclass_id),
+										  0, 0);
+			if (HeapTupleIsValid(clause_tuple))
+			{
+				Form_pg_amop clause_form = (Form_pg_amop) GETSTRUCT(clause_tuple);
+
+				/* Get the restriction clause operator's strategy/subtype */
+				clause_strategy = (StrategyNumber) clause_form->amopstrategy;
+				Assert(clause_strategy >= 1 && clause_strategy <= 5);
+				clause_subtype = clause_form->amopsubtype;
+				ReleaseSysCache(clause_tuple);
+
+				/* Only consider negators that are = */
+				if (clause_strategy != BTEqualStrategyNumber)
+					continue;
+				clause_strategy = BTNE;
+			}
+			else
+				continue;
+		}
+		else
+			continue;
+
+		/*
+		 * Look up the "test" strategy number in the implication table
+		 */
+		test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1];
+		if (test_strategy == 0)
+		{
+			/* Can't determine implication using this interpretation */
+			continue;
+		}
+
+		/*
+		 * See if opclass has an operator for the test strategy and the
+		 * clause datatype.
+		 */
+		if (test_strategy == BTNE)
+		{
+			test_op = get_opclass_member(opclass_id, clause_subtype,
+										 BTEqualStrategyNumber);
+			if (OidIsValid(test_op))
+				test_op = get_negator(test_op);
+		}
+		else
+		{
+			test_op = get_opclass_member(opclass_id, clause_subtype,
+										 test_strategy);
+		}
+		if (OidIsValid(test_op))
+		{
+			/*
+			 * Last check: test_op must be immutable.
+			 *
+			 * Note that we require only the test_op to be immutable, not the
+			 * original clause_op.	(pred_op must be immutable, else it
+			 * would not be allowed in an index predicate.)  Essentially
+			 * we are assuming that the opclass is consistent even if it
+			 * contains operators that are merely stable.
+			 *
+			 * 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;
+			}
+		}
+	}
+
+	ReleaseSysCacheList(catlist);
+
+	if (!found)
+	{
+		/* couldn't find a btree opclass to interpret the operators */
+		return false;
+	}
+
+	/*
+	 * Evaluate the test.  For this we need an EState.
+	 */
+	estate = CreateExecutorState();
+
+	/* We can use the estate's working context to avoid memory leaks. */
+	oldcontext = MemoryContextSwitchTo(estate->es_query_cxt);
+
+	/* Build expression tree */
+	test_expr = make_opclause(test_op,
+							  BOOLOID,
+							  false,
+							  (Expr *) pred_const,
+							  (Expr *) clause_const);
+
+	/* Prepare it for execution */
+	test_exprstate = ExecPrepareExpr(test_expr, estate);
+
+	/* And execute it. */
+	test_result = ExecEvalExprSwitchContext(test_exprstate,
+										  GetPerTupleExprContext(estate),
+											&isNull, NULL);
+
+	/* Get back to outer memory context */
+	MemoryContextSwitchTo(oldcontext);
+
+	/* Release all the junk we just created */
+	FreeExecutorState(estate);
+
+	if (isNull)
+	{
+		/* Treat a null result as false ... but it's a tad fishy ... */
+		elog(DEBUG2, "null predicate test result");
+		return false;
+	}
+	return DatumGetBool(test_result);
+}
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index 12157fb4d9d..0b03f27c39c 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -15,7 +15,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/utils/adt/selfuncs.c,v 1.180 2005/06/05 22:32:57 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/utils/adt/selfuncs.c,v 1.181 2005/06/10 22:25:36 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -4221,12 +4221,11 @@ genericcostestimate(PlannerInfo *root,
 	 * of partial redundancy (such as "x < 4" from the qual and "x < 5"
 	 * from the predicate) will be recognized and handled correctly by
 	 * clauselist_selectivity().  This assumption is somewhat fragile,
-	 * since it depends on pred_test() and clauselist_selectivity() having
-	 * similar capabilities, and there are certainly many cases where we
-	 * will end up with a too-low selectivity estimate.  This will bias
-	 * the system in favor of using partial indexes where possible, which
-	 * is not necessarily a bad thing.	But it'd be nice to do better
-	 * someday.
+	 * since it depends on predicate_implied_by() and clauselist_selectivity()
+	 * having similar capabilities, and there are certainly many cases where
+	 * we will end up with a too-low selectivity estimate.  This will bias the
+	 * system in favor of using partial indexes where possible, which is not
+	 * necessarily a bad thing. But it'd be nice to do better someday.
 	 *
 	 * Note that index->indpred and indexQuals are both in implicit-AND form,
 	 * so ANDing them together just takes merging the lists.  However,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index f0c2e64599f..be46bf53dd4 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.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/paths.h,v 1.84 2005/06/05 22:32:58 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/optimizer/paths.h,v 1.85 2005/06/10 22:25:37 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -49,7 +49,6 @@ extern bool match_index_to_operand(Node *operand, int indexcol,
 extern List *expand_indexqual_conditions(IndexOptInfo *index,
 										 List *clausegroups);
 extern void check_partial_indexes(PlannerInfo *root, RelOptInfo *rel);
-extern bool pred_test(List *predicate_list, List *restrictinfo_list);
 extern List *flatten_clausegroups_list(List *clausegroups);
 
 /*
diff --git a/src/include/optimizer/predtest.h b/src/include/optimizer/predtest.h
new file mode 100644
index 00000000000..cfa58f650a1
--- /dev/null
+++ b/src/include/optimizer/predtest.h
@@ -0,0 +1,23 @@
+/*-------------------------------------------------------------------------
+ *
+ * predtest.h
+ *	  prototypes for predtest.c
+ *
+ *
+ * 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 $
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef PREDTEST_H
+#define PREDTEST_H
+
+#include "nodes/primnodes.h"
+
+
+extern bool predicate_implied_by(List *predicate_list,
+								 List *restrictinfo_list);
+
+#endif   /* PREDTEST_H */