Adding upstream version 14.5.upstream/14.5upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 2224 insertions, 0 deletions

diff --git a/src/backend/optimizer/util/predtest.c b/src/backend/optimizer/util/predtest.c
new file mode 100644
index 0000000..f8be728
--- /dev/null
+++ b/src/backend/optimizer/util/predtest.c
@@ -0,0 +1,2224 @@
+/*-------------------------------------------------------------------------
+ *
+ * predtest.c
+ *	  Routines to attempt to prove logical implications between predicate
+ *	  expressions.
+ *
+ * Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *	  src/backend/optimizer/util/predtest.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "catalog/pg_proc.h"
+#include "catalog/pg_type.h"
+#include "executor/executor.h"
+#include "miscadmin.h"
+#include "nodes/makefuncs.h"
+#include "nodes/nodeFuncs.h"
+#include "nodes/pathnodes.h"
+#include "optimizer/optimizer.h"
+#include "utils/array.h"
+#include "utils/inval.h"
+#include "utils/lsyscache.h"
+#include "utils/syscache.h"
+
+
+/*
+ * Proof attempts involving large arrays in ScalarArrayOpExpr nodes are
+ * likely to require O(N^2) time, and more often than not fail anyway.
+ * So we set an arbitrary limit on the number of array elements that
+ * we will allow to be treated as an AND or OR clause.
+ * XXX is it worth exposing this as a GUC knob?
+ */
+#define MAX_SAOP_ARRAY_SIZE		100
+
+/*
+ * To avoid redundant coding in predicate_implied_by_recurse and
+ * predicate_refuted_by_recurse, we need to abstract out the notion of
+ * iterating over the components of an expression that is logically an AND
+ * or OR structure.  There are multiple sorts of expression nodes that can
+ * be treated as ANDs or ORs, and we don't want to code each one separately.
+ * Hence, these types and support routines.
+ */
+typedef enum
+{
+	CLASS_ATOM,					/* expression that's not AND or OR */
+	CLASS_AND,					/* expression with AND semantics */
+	CLASS_OR					/* expression with OR semantics */
+} PredClass;
+
+typedef struct PredIterInfoData *PredIterInfo;
+
+typedef struct PredIterInfoData
+{
+	/* node-type-specific iteration state */
+	void	   *state;
+	List	   *state_list;
+	/* initialize to do the iteration */
+	void		(*startup_fn) (Node *clause, PredIterInfo info);
+	/* next-component iteration function */
+	Node	   *(*next_fn) (PredIterInfo info);
+	/* release resources when done with iteration */
+	void		(*cleanup_fn) (PredIterInfo info);
+} PredIterInfoData;
+
+#define iterate_begin(item, clause, info)	\
+	do { \
+		Node   *item; \
+		(info).startup_fn((clause), &(info)); \
+		while ((item = (info).next_fn(&(info))) != NULL)
+
+#define iterate_end(info)	\
+		(info).cleanup_fn(&(info)); \
+	} while (0)
+
+
+static bool predicate_implied_by_recurse(Node *clause, Node *predicate,
+										 bool weak);
+static bool predicate_refuted_by_recurse(Node *clause, Node *predicate,
+										 bool weak);
+static PredClass predicate_classify(Node *clause, PredIterInfo info);
+static void list_startup_fn(Node *clause, PredIterInfo info);
+static Node *list_next_fn(PredIterInfo info);
+static void list_cleanup_fn(PredIterInfo info);
+static void boolexpr_startup_fn(Node *clause, PredIterInfo info);
+static void arrayconst_startup_fn(Node *clause, PredIterInfo info);
+static Node *arrayconst_next_fn(PredIterInfo info);
+static void arrayconst_cleanup_fn(PredIterInfo info);
+static void arrayexpr_startup_fn(Node *clause, PredIterInfo info);
+static Node *arrayexpr_next_fn(PredIterInfo info);
+static void arrayexpr_cleanup_fn(PredIterInfo info);
+static bool predicate_implied_by_simple_clause(Expr *predicate, Node *clause,
+											   bool weak);
+static bool predicate_refuted_by_simple_clause(Expr *predicate, Node *clause,
+											   bool weak);
+static Node *extract_not_arg(Node *clause);
+static Node *extract_strong_not_arg(Node *clause);
+static bool clause_is_strict_for(Node *clause, Node *subexpr, bool allow_false);
+static bool operator_predicate_proof(Expr *predicate, Node *clause,
+									 bool refute_it, bool weak);
+static bool operator_same_subexprs_proof(Oid pred_op, Oid clause_op,
+										 bool refute_it);
+static bool operator_same_subexprs_lookup(Oid pred_op, Oid clause_op,
+										  bool refute_it);
+static Oid	get_btree_test_op(Oid pred_op, Oid clause_op, bool refute_it);
+static void InvalidateOprProofCacheCallBack(Datum arg, int cacheid, uint32 hashvalue);
+
+
+/*
+ * predicate_implied_by
+ *	  Recursively checks whether the clauses in clause_list imply that the
+ *	  given predicate is true.
+ *
+ * We support two definitions of implication:
+ *
+ * "Strong" implication: A implies B means that truth of A implies truth of B.
+ * We use this to prove that a row satisfying one WHERE clause or index
+ * predicate must satisfy another one.
+ *
+ * "Weak" implication: A implies B means that non-falsity of A implies
+ * non-falsity of B ("non-false" means "either true or NULL").  We use this to
+ * prove that a row satisfying one CHECK constraint must satisfy another one.
+ *
+ * Strong implication can also be used to prove that a WHERE clause implies a
+ * CHECK constraint, although it will fail to prove a few cases where we could
+ * safely conclude that the implication holds.  There's no support for proving
+ * the converse case, since only a few kinds of CHECK constraint would allow
+ * deducing anything.
+ *
+ * The top-level List structure of each list corresponds to an AND list.
+ * We assume that eval_const_expressions() has been applied and so there
+ * are no un-flattened ANDs or ORs (e.g., no AND immediately within an AND,
+ * including AND just below the top-level List structure).
+ * If this is not true we might fail to prove an implication that is
+ * valid, but no worse consequences will ensue.
+ *
+ * We assume the predicate has already been checked to contain only
+ * immutable functions and operators.  (In many current uses this is known
+ * true because the predicate is part of an index predicate that has passed
+ * CheckPredicate(); otherwise, the caller must check it.)  We dare not make
+ * deductions based on non-immutable functions, because they might change
+ * answers between the time we make the plan and the time we execute the plan.
+ * Immutability of functions in the clause_list is checked here, if necessary.
+ */
+bool
+predicate_implied_by(List *predicate_list, List *clause_list,
+					 bool weak)
+{
+	Node	   *p,
+			   *c;
+
+	if (predicate_list == NIL)
+		return true;			/* no predicate: implication is vacuous */
+	if (clause_list == NIL)
+		return false;			/* no restriction: implication must fail */
+
+	/*
+	 * If either input is a single-element list, replace it with its lone
+	 * member; this avoids one useless level of AND-recursion.  We only need
+	 * to worry about this at top level, since eval_const_expressions should
+	 * have gotten rid of any trivial ANDs or ORs below that.
+	 */
+	if (list_length(predicate_list) == 1)
+		p = (Node *) linitial(predicate_list);
+	else
+		p = (Node *) predicate_list;
+	if (list_length(clause_list) == 1)
+		c = (Node *) linitial(clause_list);
+	else
+		c = (Node *) clause_list;
+
+	/* And away we go ... */
+	return predicate_implied_by_recurse(c, p, weak);
+}
+
+/*
+ * predicate_refuted_by
+ *	  Recursively checks whether the clauses in clause_list refute the given
+ *	  predicate (that is, prove it false).
+ *
+ * This is NOT the same as !(predicate_implied_by), though it is similar
+ * in the technique and structure of the code.
+ *
+ * We support two definitions of refutation:
+ *
+ * "Strong" refutation: A refutes B means truth of A implies falsity of B.
+ * We use this to disprove a CHECK constraint given a WHERE clause, i.e.,
+ * prove that any row satisfying the WHERE clause would violate the CHECK
+ * constraint.  (Observe we must prove B yields false, not just not-true.)
+ *
+ * "Weak" refutation: A refutes B means truth of A implies non-truth of B
+ * (i.e., B must yield false or NULL).  We use this to detect mutually
+ * contradictory WHERE clauses.
+ *
+ * Weak refutation can be proven in some cases where strong refutation doesn't
+ * hold, so it's useful to use it when possible.  We don't currently have
+ * support for disproving one CHECK constraint based on another one, nor for
+ * disproving WHERE based on CHECK.  (As with implication, the last case
+ * doesn't seem very practical.  CHECK-vs-CHECK might be useful, but isn't
+ * currently needed anywhere.)
+ *
+ * The top-level List structure of each list corresponds to an AND list.
+ * We assume that eval_const_expressions() has been applied and so there
+ * are no un-flattened ANDs or ORs (e.g., no AND immediately within an AND,
+ * including AND just below the top-level List structure).
+ * If this is not true we might fail to prove an implication that is
+ * valid, but no worse consequences will ensue.
+ *
+ * We assume the predicate has already been checked to contain only
+ * immutable functions and operators.  We dare not make deductions based on
+ * non-immutable functions, because they might change answers between the
+ * time we make the plan and the time we execute the plan.
+ * Immutability of functions in the clause_list is checked here, if necessary.
+ */
+bool
+predicate_refuted_by(List *predicate_list, List *clause_list,
+					 bool weak)
+{
+	Node	   *p,
+			   *c;
+
+	if (predicate_list == NIL)
+		return false;			/* no predicate: no refutation is possible */
+	if (clause_list == NIL)
+		return false;			/* no restriction: refutation must fail */
+
+	/*
+	 * If either input is a single-element list, replace it with its lone
+	 * member; this avoids one useless level of AND-recursion.  We only need
+	 * to worry about this at top level, since eval_const_expressions should
+	 * have gotten rid of any trivial ANDs or ORs below that.
+	 */
+	if (list_length(predicate_list) == 1)
+		p = (Node *) linitial(predicate_list);
+	else
+		p = (Node *) predicate_list;
+	if (list_length(clause_list) == 1)
+		c = (Node *) linitial(clause_list);
+	else
+		c = (Node *) clause_list;
+
+	/* And away we go ... */
+	return predicate_refuted_by_recurse(c, p, weak);
+}
+
+/*----------
+ * 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 during eval_const_expressions().
+ *
+ * All of these rules apply equally to strong or weak implication.
+ *
+ * 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.
+ *
+ * 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,
+							 bool weak)
+{
+	PredIterInfoData clause_info;
+	PredIterInfoData pred_info;
+	PredClass	pclass;
+	bool		result;
+
+	/* skip through RestrictInfo */
+	Assert(clause != NULL);
+	if (IsA(clause, RestrictInfo))
+		clause = (Node *) ((RestrictInfo *) clause)->clause;
+
+	pclass = predicate_classify(predicate, &pred_info);
+
+	switch (predicate_classify(clause, &clause_info))
+	{
+		case CLASS_AND:
+			switch (pclass)
+			{
+				case CLASS_AND:
+
+					/*
+					 * AND-clause => AND-clause if A implies each of B's items
+					 */
+					result = true;
+					iterate_begin(pitem, predicate, pred_info)
+					{
+						if (!predicate_implied_by_recurse(clause, pitem,
+														  weak))
+						{
+							result = false;
+							break;
+						}
+					}
+					iterate_end(pred_info);
+					return result;
+
+				case CLASS_OR:
+
+					/*
+					 * AND-clause => OR-clause if A implies any of B's items
+					 *
+					 * Needed to handle (x AND y) => ((x AND y) OR z)
+					 */
+					result = false;
+					iterate_begin(pitem, predicate, pred_info)
+					{
+						if (predicate_implied_by_recurse(clause, pitem,
+														 weak))
+						{
+							result = true;
+							break;
+						}
+					}
+					iterate_end(pred_info);
+					if (result)
+						return result;
+
+					/*
+					 * Also check if any of A's items implies B
+					 *
+					 * Needed to handle ((x OR y) AND z) => (x OR y)
+					 */
+					iterate_begin(citem, clause, clause_info)
+					{
+						if (predicate_implied_by_recurse(citem, predicate,
+														 weak))
+						{
+							result = true;
+							break;
+						}
+					}
+					iterate_end(clause_info);
+					return result;
+
+				case CLASS_ATOM:
+
+					/*
+					 * AND-clause => atom if any of A's items implies B
+					 */
+					result = false;
+					iterate_begin(citem, clause, clause_info)
+					{
+						if (predicate_implied_by_recurse(citem, predicate,
+														 weak))
+						{
+							result = true;
+							break;
+						}
+					}
+					iterate_end(clause_info);
+					return result;
+			}
+			break;
+
+		case CLASS_OR:
+			switch (pclass)
+			{
+				case CLASS_OR:
+
+					/*
+					 * 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.
+					 */
+					result = true;
+					iterate_begin(citem, clause, clause_info)
+					{
+						bool		presult = false;
+
+						iterate_begin(pitem, predicate, pred_info)
+						{
+							if (predicate_implied_by_recurse(citem, pitem,
+															 weak))
+							{
+								presult = true;
+								break;
+							}
+						}
+						iterate_end(pred_info);
+						if (!presult)
+						{
+							result = false; /* doesn't imply any of B's */
+							break;
+						}
+					}
+					iterate_end(clause_info);
+					return result;
+
+				case CLASS_AND:
+				case CLASS_ATOM:
+
+					/*
+					 * OR-clause => AND-clause if each of A's items implies B
+					 *
+					 * OR-clause => atom if each of A's items implies B
+					 */
+					result = true;
+					iterate_begin(citem, clause, clause_info)
+					{
+						if (!predicate_implied_by_recurse(citem, predicate,
+														  weak))
+						{
+							result = false;
+							break;
+						}
+					}
+					iterate_end(clause_info);
+					return result;
+			}
+			break;
+
+		case CLASS_ATOM:
+			switch (pclass)
+			{
+				case CLASS_AND:
+
+					/*
+					 * atom => AND-clause if A implies each of B's items
+					 */
+					result = true;
+					iterate_begin(pitem, predicate, pred_info)
+					{
+						if (!predicate_implied_by_recurse(clause, pitem,
+														  weak))
+						{
+							result = false;
+							break;
+						}
+					}
+					iterate_end(pred_info);
+					return result;
+
+				case CLASS_OR:
+
+					/*
+					 * atom => OR-clause if A implies any of B's items
+					 */
+					result = false;
+					iterate_begin(pitem, predicate, pred_info)
+					{
+						if (predicate_implied_by_recurse(clause, pitem,
+														 weak))
+						{
+							result = true;
+							break;
+						}
+					}
+					iterate_end(pred_info);
+					return result;
+
+				case CLASS_ATOM:
+
+					/*
+					 * atom => atom is the base case
+					 */
+					return
+						predicate_implied_by_simple_clause((Expr *) predicate,
+														   clause,
+														   weak);
+			}
+			break;
+	}
+
+	/* can't get here */
+	elog(ERROR, "predicate_classify returned a bogus value");
+	return false;
+}
+
+/*----------
+ * predicate_refuted_by_recurse
+ *	  Does the predicate refutation test for non-NULL restriction and
+ *	  predicate clauses.
+ *
+ * The logic followed here is ("R=>" means "refutes"):
+ *	atom A R=> atom B iff:			predicate_refuted_by_simple_clause says so
+ *	atom A R=> AND-expr B iff:		A R=> any of B's components
+ *	atom A R=> OR-expr B iff:		A R=> each of B's components
+ *	AND-expr A R=> atom B iff:		any of A's components R=> B
+ *	AND-expr A R=> AND-expr B iff:	A R=> any of B's components,
+ *									*or* any of A's components R=> B
+ *	AND-expr A R=> OR-expr B iff:	A R=> each of B's components
+ *	OR-expr A R=> atom B iff:		each of A's components R=> B
+ *	OR-expr A R=> AND-expr B iff:	each of A's components R=> any of B's
+ *	OR-expr A R=> OR-expr B iff:	A R=> each of B's components
+ *
+ * All of the above rules apply equally to strong or weak refutation.
+ *
+ * In addition, if the predicate is a NOT-clause then we can use
+ *	A R=> NOT B if:					A => B
+ * This works for several different SQL constructs that assert the non-truth
+ * of their argument, ie NOT, IS FALSE, IS NOT TRUE, IS UNKNOWN, although some
+ * of them require that we prove strong implication.  Likewise, we can use
+ *	NOT A R=> B if:					B => A
+ * but here we must be careful about strong vs. weak refutation and make
+ * the appropriate type of implication proof (weak or strong respectively).
+ *
+ * Other comments are as for predicate_implied_by_recurse().
+ *----------
+ */
+static bool
+predicate_refuted_by_recurse(Node *clause, Node *predicate,
+							 bool weak)
+{
+	PredIterInfoData clause_info;
+	PredIterInfoData pred_info;
+	PredClass	pclass;
+	Node	   *not_arg;
+	bool		result;
+
+	/* skip through RestrictInfo */
+	Assert(clause != NULL);
+	if (IsA(clause, RestrictInfo))
+		clause = (Node *) ((RestrictInfo *) clause)->clause;
+
+	pclass = predicate_classify(predicate, &pred_info);
+
+	switch (predicate_classify(clause, &clause_info))
+	{
+		case CLASS_AND:
+			switch (pclass)
+			{
+				case CLASS_AND:
+
+					/*
+					 * AND-clause R=> AND-clause if A refutes any of B's items
+					 *
+					 * Needed to handle (x AND y) R=> ((!x OR !y) AND z)
+					 */
+					result = false;
+					iterate_begin(pitem, predicate, pred_info)
+					{
+						if (predicate_refuted_by_recurse(clause, pitem,
+														 weak))
+						{
+							result = true;
+							break;
+						}
+					}
+					iterate_end(pred_info);
+					if (result)
+						return result;
+
+					/*
+					 * Also check if any of A's items refutes B
+					 *
+					 * Needed to handle ((x OR y) AND z) R=> (!x AND !y)
+					 */
+					iterate_begin(citem, clause, clause_info)
+					{
+						if (predicate_refuted_by_recurse(citem, predicate,
+														 weak))
+						{
+							result = true;
+							break;
+						}
+					}
+					iterate_end(clause_info);
+					return result;
+
+				case CLASS_OR:
+
+					/*
+					 * AND-clause R=> OR-clause if A refutes each of B's items
+					 */
+					result = true;
+					iterate_begin(pitem, predicate, pred_info)
+					{
+						if (!predicate_refuted_by_recurse(clause, pitem,
+														  weak))
+						{
+							result = false;
+							break;
+						}
+					}
+					iterate_end(pred_info);
+					return result;
+
+				case CLASS_ATOM:
+
+					/*
+					 * If B is a NOT-type clause, A R=> B if A => B's arg
+					 *
+					 * Since, for either type of refutation, we are starting
+					 * with the premise that A is true, we can use a strong
+					 * implication test in all cases.  That proves B's arg is
+					 * true, which is more than we need for weak refutation if
+					 * B is a simple NOT, but it allows not worrying about
+					 * exactly which kind of negation clause we have.
+					 */
+					not_arg = extract_not_arg(predicate);
+					if (not_arg &&
+						predicate_implied_by_recurse(clause, not_arg,
+													 false))
+						return true;
+
+					/*
+					 * AND-clause R=> atom if any of A's items refutes B
+					 */
+					result = false;
+					iterate_begin(citem, clause, clause_info)
+					{
+						if (predicate_refuted_by_recurse(citem, predicate,
+														 weak))
+						{
+							result = true;
+							break;
+						}
+					}
+					iterate_end(clause_info);
+					return result;
+			}
+			break;
+
+		case CLASS_OR:
+			switch (pclass)
+			{
+				case CLASS_OR:
+
+					/*
+					 * OR-clause R=> OR-clause if A refutes each of B's items
+					 */
+					result = true;
+					iterate_begin(pitem, predicate, pred_info)
+					{
+						if (!predicate_refuted_by_recurse(clause, pitem,
+														  weak))
+						{
+							result = false;
+							break;
+						}
+					}
+					iterate_end(pred_info);
+					return result;
+
+				case CLASS_AND:
+
+					/*
+					 * OR-clause R=> AND-clause if each of A's items refutes
+					 * any of B's items.
+					 */
+					result = true;
+					iterate_begin(citem, clause, clause_info)
+					{
+						bool		presult = false;
+
+						iterate_begin(pitem, predicate, pred_info)
+						{
+							if (predicate_refuted_by_recurse(citem, pitem,
+															 weak))
+							{
+								presult = true;
+								break;
+							}
+						}
+						iterate_end(pred_info);
+						if (!presult)
+						{
+							result = false; /* citem refutes nothing */
+							break;
+						}
+					}
+					iterate_end(clause_info);
+					return result;
+
+				case CLASS_ATOM:
+
+					/*
+					 * If B is a NOT-type clause, A R=> B if A => B's arg
+					 *
+					 * Same logic as for the AND-clause case above.
+					 */
+					not_arg = extract_not_arg(predicate);
+					if (not_arg &&
+						predicate_implied_by_recurse(clause, not_arg,
+													 false))
+						return true;
+
+					/*
+					 * OR-clause R=> atom if each of A's items refutes B
+					 */
+					result = true;
+					iterate_begin(citem, clause, clause_info)
+					{
+						if (!predicate_refuted_by_recurse(citem, predicate,
+														  weak))
+						{
+							result = false;
+							break;
+						}
+					}
+					iterate_end(clause_info);
+					return result;
+			}
+			break;
+
+		case CLASS_ATOM:
+
+			/*
+			 * If A is a strong NOT-clause, A R=> B if B => A's arg
+			 *
+			 * Since A is strong, we may assume A's arg is false (not just
+			 * not-true).  If B weakly implies A's arg, then B can be neither
+			 * true nor null, so that strong refutation is proven.  If B
+			 * strongly implies A's arg, then B cannot be true, so that weak
+			 * refutation is proven.
+			 */
+			not_arg = extract_strong_not_arg(clause);
+			if (not_arg &&
+				predicate_implied_by_recurse(predicate, not_arg,
+											 !weak))
+				return true;
+
+			switch (pclass)
+			{
+				case CLASS_AND:
+
+					/*
+					 * atom R=> AND-clause if A refutes any of B's items
+					 */
+					result = false;
+					iterate_begin(pitem, predicate, pred_info)
+					{
+						if (predicate_refuted_by_recurse(clause, pitem,
+														 weak))
+						{
+							result = true;
+							break;
+						}
+					}
+					iterate_end(pred_info);
+					return result;
+
+				case CLASS_OR:
+
+					/*
+					 * atom R=> OR-clause if A refutes each of B's items
+					 */
+					result = true;
+					iterate_begin(pitem, predicate, pred_info)
+					{
+						if (!predicate_refuted_by_recurse(clause, pitem,
+														  weak))
+						{
+							result = false;
+							break;
+						}
+					}
+					iterate_end(pred_info);
+					return result;
+
+				case CLASS_ATOM:
+
+					/*
+					 * If B is a NOT-type clause, A R=> B if A => B's arg
+					 *
+					 * Same logic as for the AND-clause case above.
+					 */
+					not_arg = extract_not_arg(predicate);
+					if (not_arg &&
+						predicate_implied_by_recurse(clause, not_arg,
+													 false))
+						return true;
+
+					/*
+					 * atom R=> atom is the base case
+					 */
+					return
+						predicate_refuted_by_simple_clause((Expr *) predicate,
+														   clause,
+														   weak);
+			}
+			break;
+	}
+
+	/* can't get here */
+	elog(ERROR, "predicate_classify returned a bogus value");
+	return false;
+}
+
+
+/*
+ * predicate_classify
+ *	  Classify an expression node as AND-type, OR-type, or neither (an atom).
+ *
+ * If the expression is classified as AND- or OR-type, then *info is filled
+ * in with the functions needed to iterate over its components.
+ *
+ * This function also implements enforcement of MAX_SAOP_ARRAY_SIZE: if a
+ * ScalarArrayOpExpr's array has too many elements, we just classify it as an
+ * atom.  (This will result in its being passed as-is to the simple_clause
+ * functions, many of which will fail to prove anything about it.) Note that we
+ * cannot just stop after considering MAX_SAOP_ARRAY_SIZE elements; in general
+ * that would result in wrong proofs, rather than failing to prove anything.
+ */
+static PredClass
+predicate_classify(Node *clause, PredIterInfo info)
+{
+	/* Caller should not pass us NULL, nor a RestrictInfo clause */
+	Assert(clause != NULL);
+	Assert(!IsA(clause, RestrictInfo));
+
+	/*
+	 * If we see a List, assume it's an implicit-AND list; this is the correct
+	 * semantics for lists of RestrictInfo nodes.
+	 */
+	if (IsA(clause, List))
+	{
+		info->startup_fn = list_startup_fn;
+		info->next_fn = list_next_fn;
+		info->cleanup_fn = list_cleanup_fn;
+		return CLASS_AND;
+	}
+
+	/* Handle normal AND and OR boolean clauses */
+	if (is_andclause(clause))
+	{
+		info->startup_fn = boolexpr_startup_fn;
+		info->next_fn = list_next_fn;
+		info->cleanup_fn = list_cleanup_fn;
+		return CLASS_AND;
+	}
+	if (is_orclause(clause))
+	{
+		info->startup_fn = boolexpr_startup_fn;
+		info->next_fn = list_next_fn;
+		info->cleanup_fn = list_cleanup_fn;
+		return CLASS_OR;
+	}
+
+	/* Handle ScalarArrayOpExpr */
+	if (IsA(clause, ScalarArrayOpExpr))
+	{
+		ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
+		Node	   *arraynode = (Node *) lsecond(saop->args);
+
+		/*
+		 * We can break this down into an AND or OR structure, but only if we
+		 * know how to iterate through expressions for the array's elements.
+		 * We can do that if the array operand is a non-null constant or a
+		 * simple ArrayExpr.
+		 */
+		if (arraynode && IsA(arraynode, Const) &&
+			!((Const *) arraynode)->constisnull)
+		{
+			ArrayType  *arrayval;
+			int			nelems;
+
+			arrayval = DatumGetArrayTypeP(((Const *) arraynode)->constvalue);
+			nelems = ArrayGetNItems(ARR_NDIM(arrayval), ARR_DIMS(arrayval));
+			if (nelems <= MAX_SAOP_ARRAY_SIZE)
+			{
+				info->startup_fn = arrayconst_startup_fn;
+				info->next_fn = arrayconst_next_fn;
+				info->cleanup_fn = arrayconst_cleanup_fn;
+				return saop->useOr ? CLASS_OR : CLASS_AND;
+			}
+		}
+		else if (arraynode && IsA(arraynode, ArrayExpr) &&
+				 !((ArrayExpr *) arraynode)->multidims &&
+				 list_length(((ArrayExpr *) arraynode)->elements) <= MAX_SAOP_ARRAY_SIZE)
+		{
+			info->startup_fn = arrayexpr_startup_fn;
+			info->next_fn = arrayexpr_next_fn;
+			info->cleanup_fn = arrayexpr_cleanup_fn;
+			return saop->useOr ? CLASS_OR : CLASS_AND;
+		}
+	}
+
+	/* None of the above, so it's an atom */
+	return CLASS_ATOM;
+}
+
+/*
+ * PredIterInfo routines for iterating over regular Lists.  The iteration
+ * state variable is the next ListCell to visit.
+ */
+static void
+list_startup_fn(Node *clause, PredIterInfo info)
+{
+	info->state_list = (List *) clause;
+	info->state = (void *) list_head(info->state_list);
+}
+
+static Node *
+list_next_fn(PredIterInfo info)
+{
+	ListCell   *l = (ListCell *) info->state;
+	Node	   *n;
+
+	if (l == NULL)
+		return NULL;
+	n = lfirst(l);
+	info->state = (void *) lnext(info->state_list, l);
+	return n;
+}
+
+static void
+list_cleanup_fn(PredIterInfo info)
+{
+	/* Nothing to clean up */
+}
+
+/*
+ * BoolExpr needs its own startup function, but can use list_next_fn and
+ * list_cleanup_fn.
+ */
+static void
+boolexpr_startup_fn(Node *clause, PredIterInfo info)
+{
+	info->state_list = ((BoolExpr *) clause)->args;
+	info->state = (void *) list_head(info->state_list);
+}
+
+/*
+ * PredIterInfo routines for iterating over a ScalarArrayOpExpr with a
+ * constant array operand.
+ */
+typedef struct
+{
+	OpExpr		opexpr;
+	Const		constexpr;
+	int			next_elem;
+	int			num_elems;
+	Datum	   *elem_values;
+	bool	   *elem_nulls;
+} ArrayConstIterState;
+
+static void
+arrayconst_startup_fn(Node *clause, PredIterInfo info)
+{
+	ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
+	ArrayConstIterState *state;
+	Const	   *arrayconst;
+	ArrayType  *arrayval;
+	int16		elmlen;
+	bool		elmbyval;
+	char		elmalign;
+
+	/* Create working state struct */
+	state = (ArrayConstIterState *) palloc(sizeof(ArrayConstIterState));
+	info->state = (void *) state;
+
+	/* Deconstruct the array literal */
+	arrayconst = (Const *) lsecond(saop->args);
+	arrayval = DatumGetArrayTypeP(arrayconst->constvalue);
+	get_typlenbyvalalign(ARR_ELEMTYPE(arrayval),
+						 &elmlen, &elmbyval, &elmalign);
+	deconstruct_array(arrayval,
+					  ARR_ELEMTYPE(arrayval),
+					  elmlen, elmbyval, elmalign,
+					  &state->elem_values, &state->elem_nulls,
+					  &state->num_elems);
+
+	/* Set up a dummy OpExpr to return as the per-item node */
+	state->opexpr.xpr.type = T_OpExpr;
+	state->opexpr.opno = saop->opno;
+	state->opexpr.opfuncid = saop->opfuncid;
+	state->opexpr.opresulttype = BOOLOID;
+	state->opexpr.opretset = false;
+	state->opexpr.opcollid = InvalidOid;
+	state->opexpr.inputcollid = saop->inputcollid;
+	state->opexpr.args = list_copy(saop->args);
+
+	/* Set up a dummy Const node to hold the per-element values */
+	state->constexpr.xpr.type = T_Const;
+	state->constexpr.consttype = ARR_ELEMTYPE(arrayval);
+	state->constexpr.consttypmod = -1;
+	state->constexpr.constcollid = arrayconst->constcollid;
+	state->constexpr.constlen = elmlen;
+	state->constexpr.constbyval = elmbyval;
+	lsecond(state->opexpr.args) = &state->constexpr;
+
+	/* Initialize iteration state */
+	state->next_elem = 0;
+}
+
+static Node *
+arrayconst_next_fn(PredIterInfo info)
+{
+	ArrayConstIterState *state = (ArrayConstIterState *) info->state;
+
+	if (state->next_elem >= state->num_elems)
+		return NULL;
+	state->constexpr.constvalue = state->elem_values[state->next_elem];
+	state->constexpr.constisnull = state->elem_nulls[state->next_elem];
+	state->next_elem++;
+	return (Node *) &(state->opexpr);
+}
+
+static void
+arrayconst_cleanup_fn(PredIterInfo info)
+{
+	ArrayConstIterState *state = (ArrayConstIterState *) info->state;
+
+	pfree(state->elem_values);
+	pfree(state->elem_nulls);
+	list_free(state->opexpr.args);
+	pfree(state);
+}
+
+/*
+ * PredIterInfo routines for iterating over a ScalarArrayOpExpr with a
+ * one-dimensional ArrayExpr array operand.
+ */
+typedef struct
+{
+	OpExpr		opexpr;
+	ListCell   *next;
+} ArrayExprIterState;
+
+static void
+arrayexpr_startup_fn(Node *clause, PredIterInfo info)
+{
+	ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
+	ArrayExprIterState *state;
+	ArrayExpr  *arrayexpr;
+
+	/* Create working state struct */
+	state = (ArrayExprIterState *) palloc(sizeof(ArrayExprIterState));
+	info->state = (void *) state;
+
+	/* Set up a dummy OpExpr to return as the per-item node */
+	state->opexpr.xpr.type = T_OpExpr;
+	state->opexpr.opno = saop->opno;
+	state->opexpr.opfuncid = saop->opfuncid;
+	state->opexpr.opresulttype = BOOLOID;
+	state->opexpr.opretset = false;
+	state->opexpr.opcollid = InvalidOid;
+	state->opexpr.inputcollid = saop->inputcollid;
+	state->opexpr.args = list_copy(saop->args);
+
+	/* Initialize iteration variable to first member of ArrayExpr */
+	arrayexpr = (ArrayExpr *) lsecond(saop->args);
+	info->state_list = arrayexpr->elements;
+	state->next = list_head(arrayexpr->elements);
+}
+
+static Node *
+arrayexpr_next_fn(PredIterInfo info)
+{
+	ArrayExprIterState *state = (ArrayExprIterState *) info->state;
+
+	if (state->next == NULL)
+		return NULL;
+	lsecond(state->opexpr.args) = lfirst(state->next);
+	state->next = lnext(info->state_list, state->next);
+	return (Node *) &(state->opexpr);
+}
+
+static void
+arrayexpr_cleanup_fn(PredIterInfo info)
+{
+	ArrayExprIterState *state = (ArrayExprIterState *) info->state;
+
+	list_free(state->opexpr.args);
+	pfree(state);
+}
+
+
+/*----------
+ * predicate_implied_by_simple_clause
+ *	  Does the predicate implication test for a "simple clause" predicate
+ *	  and a "simple clause" restriction.
+ *
+ * We return true if able to prove the implication, false if not.
+ *
+ * We have three strategies for determining whether one simple clause
+ * implies another:
+ *
+ * A simple and general way is to see if they are equal(); this works for any
+ * kind of expression, and for either implication definition.  (Actually,
+ * there is an implied assumption that the functions in the expression are
+ * immutable --- but this was checked for the predicate by the caller.)
+ *
+ * If the predicate is of the form "foo IS NOT NULL", and we are considering
+ * strong implication, we can conclude that the predicate is implied if the
+ * clause is strict for "foo", i.e., it must yield false or NULL when "foo"
+ * is NULL.  In that case truth of the clause ensures that "foo" isn't NULL.
+ * (Again, this is a safe conclusion because "foo" must be immutable.)
+ * This doesn't work for weak implication, though.
+ *
+ * Finally, if both clauses are binary operator expressions, we may be able
+ * to prove something using the system's knowledge about operators; those
+ * proof rules are encapsulated in operator_predicate_proof().
+ *----------
+ */
+static bool
+predicate_implied_by_simple_clause(Expr *predicate, Node *clause,
+								   bool weak)
+{
+	/* Allow interrupting long proof attempts */
+	CHECK_FOR_INTERRUPTS();
+
+	/* First try the equal() test */
+	if (equal((Node *) predicate, clause))
+		return true;
+
+	/* Next try the IS NOT NULL case */
+	if (!weak &&
+		predicate && IsA(predicate, NullTest))
+	{
+		NullTest   *ntest = (NullTest *) predicate;
+
+		/* row IS NOT NULL does not act in the simple way we have in mind */
+		if (ntest->nulltesttype == IS_NOT_NULL &&
+			!ntest->argisrow)
+		{
+			/* strictness of clause for foo implies foo IS NOT NULL */
+			if (clause_is_strict_for(clause, (Node *) ntest->arg, true))
+				return true;
+		}
+		return false;			/* we can't succeed below... */
+	}
+
+	/* Else try operator-related knowledge */
+	return operator_predicate_proof(predicate, clause, false, weak);
+}
+
+/*----------
+ * predicate_refuted_by_simple_clause
+ *	  Does the predicate refutation test for a "simple clause" predicate
+ *	  and a "simple clause" restriction.
+ *
+ * We return true if able to prove the refutation, false if not.
+ *
+ * Unlike the implication case, checking for equal() clauses isn't helpful.
+ * But relation_excluded_by_constraints() checks for self-contradictions in a
+ * list of clauses, so that we may get here with predicate and clause being
+ * actually pointer-equal, and that is worth eliminating quickly.
+ *
+ * When the predicate is of the form "foo IS NULL", we can conclude that
+ * the predicate is refuted if the clause is strict for "foo" (see notes for
+ * implication case), or is "foo IS NOT NULL".  That works for either strong
+ * or weak refutation.
+ *
+ * A clause "foo IS NULL" refutes a predicate "foo IS NOT NULL" in all cases.
+ * If we are considering weak refutation, it also refutes a predicate that
+ * is strict for "foo", since then the predicate must yield false or NULL
+ * (and since "foo" appears in the predicate, it's known immutable).
+ *
+ * (The main motivation for covering these IS [NOT] NULL cases is to support
+ * using IS NULL/IS NOT NULL as partition-defining constraints.)
+ *
+ * Finally, if both clauses are binary operator expressions, we may be able
+ * to prove something using the system's knowledge about operators; those
+ * proof rules are encapsulated in operator_predicate_proof().
+ *----------
+ */
+static bool
+predicate_refuted_by_simple_clause(Expr *predicate, Node *clause,
+								   bool weak)
+{
+	/* Allow interrupting long proof attempts */
+	CHECK_FOR_INTERRUPTS();
+
+	/* A simple clause can't refute itself */
+	/* Worth checking because of relation_excluded_by_constraints() */
+	if ((Node *) predicate == clause)
+		return false;
+
+	/* Try the predicate-IS-NULL case */
+	if (predicate && IsA(predicate, NullTest) &&
+		((NullTest *) predicate)->nulltesttype == IS_NULL)
+	{
+		Expr	   *isnullarg = ((NullTest *) predicate)->arg;
+
+		/* row IS NULL does not act in the simple way we have in mind */
+		if (((NullTest *) predicate)->argisrow)
+			return false;
+
+		/* strictness of clause for foo refutes foo IS NULL */
+		if (clause_is_strict_for(clause, (Node *) isnullarg, true))
+			return true;
+
+		/* foo IS NOT NULL refutes foo IS NULL */
+		if (clause && IsA(clause, NullTest) &&
+			((NullTest *) clause)->nulltesttype == IS_NOT_NULL &&
+			!((NullTest *) clause)->argisrow &&
+			equal(((NullTest *) clause)->arg, isnullarg))
+			return true;
+
+		return false;			/* we can't succeed below... */
+	}
+
+	/* Try the clause-IS-NULL case */
+	if (clause && IsA(clause, NullTest) &&
+		((NullTest *) clause)->nulltesttype == IS_NULL)
+	{
+		Expr	   *isnullarg = ((NullTest *) clause)->arg;
+
+		/* row IS NULL does not act in the simple way we have in mind */
+		if (((NullTest *) clause)->argisrow)
+			return false;
+
+		/* foo IS NULL refutes foo IS NOT NULL */
+		if (predicate && IsA(predicate, NullTest) &&
+			((NullTest *) predicate)->nulltesttype == IS_NOT_NULL &&
+			!((NullTest *) predicate)->argisrow &&
+			equal(((NullTest *) predicate)->arg, isnullarg))
+			return true;
+
+		/* foo IS NULL weakly refutes any predicate that is strict for foo */
+		if (weak &&
+			clause_is_strict_for((Node *) predicate, (Node *) isnullarg, true))
+			return true;
+
+		return false;			/* we can't succeed below... */
+	}
+
+	/* Else try operator-related knowledge */
+	return operator_predicate_proof(predicate, clause, true, weak);
+}
+
+
+/*
+ * If clause asserts the non-truth of a subclause, return that subclause;
+ * otherwise return NULL.
+ */
+static Node *
+extract_not_arg(Node *clause)
+{
+	if (clause == NULL)
+		return NULL;
+	if (IsA(clause, BoolExpr))
+	{
+		BoolExpr   *bexpr = (BoolExpr *) clause;
+
+		if (bexpr->boolop == NOT_EXPR)
+			return (Node *) linitial(bexpr->args);
+	}
+	else if (IsA(clause, BooleanTest))
+	{
+		BooleanTest *btest = (BooleanTest *) clause;
+
+		if (btest->booltesttype == IS_NOT_TRUE ||
+			btest->booltesttype == IS_FALSE ||
+			btest->booltesttype == IS_UNKNOWN)
+			return (Node *) btest->arg;
+	}
+	return NULL;
+}
+
+/*
+ * If clause asserts the falsity of a subclause, return that subclause;
+ * otherwise return NULL.
+ */
+static Node *
+extract_strong_not_arg(Node *clause)
+{
+	if (clause == NULL)
+		return NULL;
+	if (IsA(clause, BoolExpr))
+	{
+		BoolExpr   *bexpr = (BoolExpr *) clause;
+
+		if (bexpr->boolop == NOT_EXPR)
+			return (Node *) linitial(bexpr->args);
+	}
+	else if (IsA(clause, BooleanTest))
+	{
+		BooleanTest *btest = (BooleanTest *) clause;
+
+		if (btest->booltesttype == IS_FALSE)
+			return (Node *) btest->arg;
+	}
+	return NULL;
+}
+
+
+/*
+ * Can we prove that "clause" returns NULL (or FALSE) if "subexpr" is
+ * assumed to yield NULL?
+ *
+ * In most places in the planner, "strictness" refers to a guarantee that
+ * an expression yields NULL output for a NULL input, and that's mostly what
+ * we're looking for here.  However, at top level where the clause is known
+ * to yield boolean, it may be sufficient to prove that it cannot return TRUE
+ * when "subexpr" is NULL.  The caller should pass allow_false = true when
+ * this weaker property is acceptable.  (When this function recurses
+ * internally, we pass down allow_false = false since we need to prove actual
+ * nullness of the subexpression.)
+ *
+ * We assume that the caller checked that least one of the input expressions
+ * is immutable.  All of the proof rules here involve matching "subexpr" to
+ * some portion of "clause", so that this allows assuming that "subexpr" is
+ * immutable without a separate check.
+ *
+ * The base case is that clause and subexpr are equal().
+ *
+ * We can also report success if the subexpr appears as a subexpression
+ * of "clause" in a place where it'd force nullness of the overall result.
+ */
+static bool
+clause_is_strict_for(Node *clause, Node *subexpr, bool allow_false)
+{
+	ListCell   *lc;
+
+	/* safety checks */
+	if (clause == NULL || subexpr == NULL)
+		return false;
+
+	/*
+	 * Look through any RelabelType nodes, so that we can match, say,
+	 * varcharcol with lower(varcharcol::text).  (In general we could recurse
+	 * through any nullness-preserving, immutable operation.)  We should not
+	 * see stacked RelabelTypes here.
+	 */
+	if (IsA(clause, RelabelType))
+		clause = (Node *) ((RelabelType *) clause)->arg;
+	if (IsA(subexpr, RelabelType))
+		subexpr = (Node *) ((RelabelType *) subexpr)->arg;
+
+	/* Base case */
+	if (equal(clause, subexpr))
+		return true;
+
+	/*
+	 * If we have a strict operator or function, a NULL result is guaranteed
+	 * if any input is forced NULL by subexpr.  This is OK even if the op or
+	 * func isn't immutable, since it won't even be called on NULL input.
+	 */
+	if (is_opclause(clause) &&
+		op_strict(((OpExpr *) clause)->opno))
+	{
+		foreach(lc, ((OpExpr *) clause)->args)
+		{
+			if (clause_is_strict_for((Node *) lfirst(lc), subexpr, false))
+				return true;
+		}
+		return false;
+	}
+	if (is_funcclause(clause) &&
+		func_strict(((FuncExpr *) clause)->funcid))
+	{
+		foreach(lc, ((FuncExpr *) clause)->args)
+		{
+			if (clause_is_strict_for((Node *) lfirst(lc), subexpr, false))
+				return true;
+		}
+		return false;
+	}
+
+	/*
+	 * CoerceViaIO is strict (whether or not the I/O functions it calls are).
+	 * Likewise, ArrayCoerceExpr is strict for its array argument (regardless
+	 * of what the per-element expression is), ConvertRowtypeExpr is strict at
+	 * the row level, and CoerceToDomain is strict too.  These are worth
+	 * checking mainly because it saves us having to explain to users why some
+	 * type coercions are known strict and others aren't.
+	 */
+	if (IsA(clause, CoerceViaIO))
+		return clause_is_strict_for((Node *) ((CoerceViaIO *) clause)->arg,
+									subexpr, false);
+	if (IsA(clause, ArrayCoerceExpr))
+		return clause_is_strict_for((Node *) ((ArrayCoerceExpr *) clause)->arg,
+									subexpr, false);
+	if (IsA(clause, ConvertRowtypeExpr))
+		return clause_is_strict_for((Node *) ((ConvertRowtypeExpr *) clause)->arg,
+									subexpr, false);
+	if (IsA(clause, CoerceToDomain))
+		return clause_is_strict_for((Node *) ((CoerceToDomain *) clause)->arg,
+									subexpr, false);
+
+	/*
+	 * ScalarArrayOpExpr is a special case.  Note that we'd only reach here
+	 * with a ScalarArrayOpExpr clause if we failed to deconstruct it into an
+	 * AND or OR tree, as for example if it has too many array elements.
+	 */
+	if (IsA(clause, ScalarArrayOpExpr))
+	{
+		ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
+		Node	   *scalarnode = (Node *) linitial(saop->args);
+		Node	   *arraynode = (Node *) lsecond(saop->args);
+
+		/*
+		 * If we can prove the scalar input to be null, and the operator is
+		 * strict, then the SAOP result has to be null --- unless the array is
+		 * empty.  For an empty array, we'd get either false (for ANY) or true
+		 * (for ALL).  So if allow_false = true then the proof succeeds anyway
+		 * for the ANY case; otherwise we can only make the proof if we can
+		 * prove the array non-empty.
+		 */
+		if (clause_is_strict_for(scalarnode, subexpr, false) &&
+			op_strict(saop->opno))
+		{
+			int			nelems = 0;
+
+			if (allow_false && saop->useOr)
+				return true;	/* can succeed even if array is empty */
+
+			if (arraynode && IsA(arraynode, Const))
+			{
+				Const	   *arrayconst = (Const *) arraynode;
+				ArrayType  *arrval;
+
+				/*
+				 * If array is constant NULL then we can succeed, as in the
+				 * case below.
+				 */
+				if (arrayconst->constisnull)
+					return true;
+
+				/* Otherwise, we can compute the number of elements. */
+				arrval = DatumGetArrayTypeP(arrayconst->constvalue);
+				nelems = ArrayGetNItems(ARR_NDIM(arrval), ARR_DIMS(arrval));
+			}
+			else if (arraynode && IsA(arraynode, ArrayExpr) &&
+					 !((ArrayExpr *) arraynode)->multidims)
+			{
+				/*
+				 * We can also reliably count the number of array elements if
+				 * the input is a non-multidim ARRAY[] expression.
+				 */
+				nelems = list_length(((ArrayExpr *) arraynode)->elements);
+			}
+
+			/* Proof succeeds if array is definitely non-empty */
+			if (nelems > 0)
+				return true;
+		}
+
+		/*
+		 * If we can prove the array input to be null, the proof succeeds in
+		 * all cases, since ScalarArrayOpExpr will always return NULL for a
+		 * NULL array.  Otherwise, we're done here.
+		 */
+		return clause_is_strict_for(arraynode, subexpr, false);
+	}
+
+	/*
+	 * When recursing into an expression, we might find a NULL constant.
+	 * That's certainly NULL, whether it matches subexpr or not.
+	 */
+	if (IsA(clause, Const))
+		return ((Const *) clause)->constisnull;
+
+	return false;
+}
+
+
+/*
+ * Define "operator implication tables" for btree operators ("strategies"),
+ * and similar tables for refutation.
+ *
+ * The strategy numbers defined by btree indexes (see access/stratnum.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 an equality operator of a btree
+ * opfamily has a negator operator, the negator behaves as <> for the opfamily.
+ * (This convention is also known to get_op_btree_interpretation().)
+ *
+ * BT_implies_table[] and BT_refutes_table[] are used for cases where we have
+ * two identical subexpressions and we want to know whether one operator
+ * expression implies or refutes the other.  That is, if the "clause" is
+ * EXPR1 clause_op EXPR2 and the "predicate" is EXPR1 pred_op EXPR2 for the
+ * same two (immutable) subexpressions:
+ *		BT_implies_table[clause_op-1][pred_op-1]
+ *			is true if the clause implies the predicate
+ *		BT_refutes_table[clause_op-1][pred_op-1]
+ *			is true if the clause refutes the predicate
+ * where clause_op and pred_op are strategy numbers (from 1 to 6) in the
+ * same btree opfamily.  For example, "x < y" implies "x <= y" and refutes
+ * "x > y".
+ *
+ * BT_implic_table[] and BT_refute_table[] are used where we have two
+ * constants that we need to compare.  The interpretation of:
+ *
+ *		test_op = BT_implic_table[clause_op-1][pred_op-1]
+ *
+ * where test_op, clause_op and pred_op are strategy numbers (from 1 to 6)
+ * of btree operators, is as follows:
+ *
+ *	 If you know, for some EXPR, that "EXPR clause_op CONST1" is true, and you
+ *	 want to determine whether "EXPR pred_op CONST2" must also be true, then
+ *	 you can use "CONST2 test_op CONST1" as a test.  If this test returns true,
+ *	 then the predicate expression must be true; if the test returns false,
+ *	 then the predicate expression may be false.
+ *
+ * For example, if clause is "Quantity > 10" and pred is "Quantity > 5"
+ * then we test "5 <= 10" which evals to true, so clause implies pred.
+ *
+ * Similarly, the interpretation of a BT_refute_table entry is:
+ *
+ *	 If you know, for some EXPR, that "EXPR clause_op CONST1" is true, and you
+ *	 want to determine whether "EXPR pred_op CONST2" must be false, then
+ *	 you can use "CONST2 test_op CONST1" as a test.  If this test returns true,
+ *	 then the predicate expression must be false; if the test returns false,
+ *	 then the predicate expression may be true.
+ *
+ * For example, if clause is "Quantity > 10" and pred is "Quantity < 5"
+ * then we test "5 <= 10" which evals to true, so clause refutes pred.
+ *
+ * An entry where test_op == 0 means the implication cannot be determined.
+ */
+
+#define BTLT BTLessStrategyNumber
+#define BTLE BTLessEqualStrategyNumber
+#define BTEQ BTEqualStrategyNumber
+#define BTGE BTGreaterEqualStrategyNumber
+#define BTGT BTGreaterStrategyNumber
+#define BTNE ROWCOMPARE_NE
+
+/* We use "none" for 0/false to make the tables align nicely */
+#define none 0
+
+static const bool BT_implies_table[6][6] = {
+/*
+ *			The predicate operator:
+ *	 LT    LE	 EQ    GE	 GT    NE
+ */
+	{true, true, none, none, none, true},	/* LT */
+	{none, true, none, none, none, none},	/* LE */
+	{none, true, true, true, none, none},	/* EQ */
+	{none, none, none, true, none, none},	/* GE */
+	{none, none, none, true, true, true},	/* GT */
+	{none, none, none, none, none, true}	/* NE */
+};
+
+static const bool BT_refutes_table[6][6] = {
+/*
+ *			The predicate operator:
+ *	 LT    LE	 EQ    GE	 GT    NE
+ */
+	{none, none, true, true, true, none},	/* LT */
+	{none, none, none, none, true, none},	/* LE */
+	{true, none, none, none, true, true},	/* EQ */
+	{true, none, none, none, none, none},	/* GE */
+	{true, true, true, none, none, none},	/* GT */
+	{none, none, true, none, none, none}	/* NE */
+};
+
+static const StrategyNumber BT_implic_table[6][6] = {
+/*
+ *			The predicate operator:
+ *	 LT    LE	 EQ    GE	 GT    NE
+ */
+	{BTGE, BTGE, none, none, none, BTGE},	/* LT */
+	{BTGT, BTGE, none, none, none, BTGT},	/* LE */
+	{BTGT, BTGE, BTEQ, BTLE, BTLT, BTNE},	/* EQ */
+	{none, none, none, BTLE, BTLT, BTLT},	/* GE */
+	{none, none, none, BTLE, BTLE, BTLE},	/* GT */
+	{none, none, none, none, none, BTEQ}	/* NE */
+};
+
+static const StrategyNumber BT_refute_table[6][6] = {
+/*
+ *			The predicate operator:
+ *	 LT    LE	 EQ    GE	 GT    NE
+ */
+	{none, none, BTGE, BTGE, BTGE, none},	/* LT */
+	{none, none, BTGT, BTGT, BTGE, none},	/* LE */
+	{BTLE, BTLT, BTNE, BTGT, BTGE, BTEQ},	/* EQ */
+	{BTLE, BTLT, BTLT, none, none, none},	/* GE */
+	{BTLE, BTLE, BTLE, none, none, none},	/* GT */
+	{none, none, BTEQ, none, none, none}	/* NE */
+};
+
+
+/*
+ * operator_predicate_proof
+ *	  Does the predicate implication or refutation test for a "simple clause"
+ *	  predicate and a "simple clause" restriction, when both are operator
+ *	  clauses using related operators and identical input expressions.
+ *
+ * When refute_it == false, we want to prove the predicate true;
+ * when refute_it == true, we want to prove the predicate false.
+ * (There is enough common code to justify handling these two cases
+ * in one routine.)  We return true if able to make the proof, false
+ * if not able to prove it.
+ *
+ * We mostly need not distinguish strong vs. weak implication/refutation here.
+ * This depends on the assumption that a pair of related operators (i.e.,
+ * commutators, negators, or btree opfamily siblings) will not return one NULL
+ * and one non-NULL result for the same inputs.  Then, for the proof types
+ * where we start with an assumption of truth of the clause, the predicate
+ * operator could not return NULL either, so it doesn't matter whether we are
+ * trying to make a strong or weak proof.  For weak implication, it could be
+ * that the clause operator returned NULL, but then the predicate operator
+ * would as well, so that the weak implication still holds.  This argument
+ * doesn't apply in the case where we are considering two different constant
+ * values, since then the operators aren't being given identical inputs.  But
+ * we only support that for btree operators, for which we can assume that all
+ * non-null inputs result in non-null outputs, so that it doesn't matter which
+ * two non-null constants we consider.  If either constant is NULL, we have
+ * to think harder, but sometimes the proof still works, as explained below.
+ *
+ * We can make proofs involving several expression forms (here "foo" and "bar"
+ * represent subexpressions that are identical according to equal()):
+ *	"foo op1 bar" refutes "foo op2 bar" if op1 is op2's negator
+ *	"foo op1 bar" implies "bar op2 foo" if op1 is op2's commutator
+ *	"foo op1 bar" refutes "bar op2 foo" if op1 is negator of op2's commutator
+ *	"foo op1 bar" can imply/refute "foo op2 bar" based on btree semantics
+ *	"foo op1 bar" can imply/refute "bar op2 foo" based on btree semantics
+ *	"foo op1 const1" can imply/refute "foo op2 const2" based on btree semantics
+ *
+ * For the last three cases, op1 and op2 have to be members of the same btree
+ * operator family.  When both subexpressions are identical, the idea is that,
+ * for instance, x < y implies x <= y, independently of exactly what x and y
+ * are.  If we have two different constants compared to the same expression
+ * foo, we have to execute a comparison between the two constant values
+ * in order to determine the result; for instance, foo < c1 implies foo < c2
+ * if c1 <= c2.  We assume it's safe to compare the constants at plan time
+ * if the comparison operator is immutable.
+ *
+ * Note: all the operators and subexpressions have to be immutable for the
+ * proof to be safe.  We assume the predicate expression is entirely immutable,
+ * so no explicit check on the subexpressions is needed here, but in some
+ * cases we need an extra check of operator immutability.  In particular,
+ * btree opfamilies can contain cross-type operators that are merely stable,
+ * and we dare not make deductions with those.
+ */
+static bool
+operator_predicate_proof(Expr *predicate, Node *clause,
+						 bool refute_it, bool weak)
+{
+	OpExpr	   *pred_opexpr,
+			   *clause_opexpr;
+	Oid			pred_collation,
+				clause_collation;
+	Oid			pred_op,
+				clause_op,
+				test_op;
+	Node	   *pred_leftop,
+			   *pred_rightop,
+			   *clause_leftop,
+			   *clause_rightop;
+	Const	   *pred_const,
+			   *clause_const;
+	Expr	   *test_expr;
+	ExprState  *test_exprstate;
+	Datum		test_result;
+	bool		isNull;
+	EState	   *estate;
+	MemoryContext oldcontext;
+
+	/*
+	 * Both expressions must be binary opclauses, else we can't do anything.
+	 *
+	 * Note: in future we might extend this logic to other operator-based
+	 * constructs such as DistinctExpr.  But the planner isn't very smart
+	 * about DistinctExpr in general, and this probably isn't the first place
+	 * to fix if you want to improve that.
+	 */
+	if (!is_opclause(predicate))
+		return false;
+	pred_opexpr = (OpExpr *) predicate;
+	if (list_length(pred_opexpr->args) != 2)
+		return false;
+	if (!is_opclause(clause))
+		return false;
+	clause_opexpr = (OpExpr *) clause;
+	if (list_length(clause_opexpr->args) != 2)
+		return false;
+
+	/*
+	 * If they're marked with different collations then we can't do anything.
+	 * This is a cheap test so let's get it out of the way early.
+	 */
+	pred_collation = pred_opexpr->inputcollid;
+	clause_collation = clause_opexpr->inputcollid;
+	if (pred_collation != clause_collation)
+		return false;
+
+	/* Grab the operator OIDs now too.  We may commute these below. */
+	pred_op = pred_opexpr->opno;
+	clause_op = clause_opexpr->opno;
+
+	/*
+	 * We have to match up at least one pair of input expressions.
+	 */
+	pred_leftop = (Node *) linitial(pred_opexpr->args);
+	pred_rightop = (Node *) lsecond(pred_opexpr->args);
+	clause_leftop = (Node *) linitial(clause_opexpr->args);
+	clause_rightop = (Node *) lsecond(clause_opexpr->args);
+
+	if (equal(pred_leftop, clause_leftop))
+	{
+		if (equal(pred_rightop, clause_rightop))
+		{
+			/* We have x op1 y and x op2 y */
+			return operator_same_subexprs_proof(pred_op, clause_op, refute_it);
+		}
+		else
+		{
+			/* Fail unless rightops are both Consts */
+			if (pred_rightop == NULL || !IsA(pred_rightop, Const))
+				return false;
+			pred_const = (Const *) pred_rightop;
+			if (clause_rightop == NULL || !IsA(clause_rightop, Const))
+				return false;
+			clause_const = (Const *) clause_rightop;
+		}
+	}
+	else if (equal(pred_rightop, clause_rightop))
+	{
+		/* Fail unless leftops are both Consts */
+		if (pred_leftop == NULL || !IsA(pred_leftop, Const))
+			return false;
+		pred_const = (Const *) pred_leftop;
+		if (clause_leftop == NULL || !IsA(clause_leftop, Const))
+			return false;
+		clause_const = (Const *) clause_leftop;
+		/* Commute both operators so we can assume Consts are on the right */
+		pred_op = get_commutator(pred_op);
+		if (!OidIsValid(pred_op))
+			return false;
+		clause_op = get_commutator(clause_op);
+		if (!OidIsValid(clause_op))
+			return false;
+	}
+	else if (equal(pred_leftop, clause_rightop))
+	{
+		if (equal(pred_rightop, clause_leftop))
+		{
+			/* We have x op1 y and y op2 x */
+			/* Commute pred_op that we can treat this like a straight match */
+			pred_op = get_commutator(pred_op);
+			if (!OidIsValid(pred_op))
+				return false;
+			return operator_same_subexprs_proof(pred_op, clause_op, refute_it);
+		}
+		else
+		{
+			/* Fail unless pred_rightop/clause_leftop are both Consts */
+			if (pred_rightop == NULL || !IsA(pred_rightop, Const))
+				return false;
+			pred_const = (Const *) pred_rightop;
+			if (clause_leftop == NULL || !IsA(clause_leftop, Const))
+				return false;
+			clause_const = (Const *) clause_leftop;
+			/* Commute clause_op so we can assume Consts are on the right */
+			clause_op = get_commutator(clause_op);
+			if (!OidIsValid(clause_op))
+				return false;
+		}
+	}
+	else if (equal(pred_rightop, clause_leftop))
+	{
+		/* Fail unless pred_leftop/clause_rightop are both Consts */
+		if (pred_leftop == NULL || !IsA(pred_leftop, Const))
+			return false;
+		pred_const = (Const *) pred_leftop;
+		if (clause_rightop == NULL || !IsA(clause_rightop, Const))
+			return false;
+		clause_const = (Const *) clause_rightop;
+		/* Commute pred_op so we can assume Consts are on the right */
+		pred_op = get_commutator(pred_op);
+		if (!OidIsValid(pred_op))
+			return false;
+	}
+	else
+	{
+		/* Failed to match up any of the subexpressions, so we lose */
+		return false;
+	}
+
+	/*
+	 * We have two identical subexpressions, and two other subexpressions that
+	 * are not identical but are both Consts; and we have commuted the
+	 * operators if necessary so that the Consts are on the right.  We'll need
+	 * to compare the Consts' values.  If either is NULL, we can't do that, so
+	 * usually the proof fails ... but in some cases we can claim success.
+	 */
+	if (clause_const->constisnull)
+	{
+		/* If clause_op isn't strict, we can't prove anything */
+		if (!op_strict(clause_op))
+			return false;
+
+		/*
+		 * At this point we know that the clause returns NULL.  For proof
+		 * types that assume truth of the clause, this means the proof is
+		 * vacuously true (a/k/a "false implies anything").  That's all proof
+		 * types except weak implication.
+		 */
+		if (!(weak && !refute_it))
+			return true;
+
+		/*
+		 * For weak implication, it's still possible for the proof to succeed,
+		 * if the predicate can also be proven NULL.  In that case we've got
+		 * NULL => NULL which is valid for this proof type.
+		 */
+		if (pred_const->constisnull && op_strict(pred_op))
+			return true;
+		/* Else the proof fails */
+		return false;
+	}
+	if (pred_const->constisnull)
+	{
+		/*
+		 * If the pred_op is strict, we know the predicate yields NULL, which
+		 * means the proof succeeds for either weak implication or weak
+		 * refutation.
+		 */
+		if (weak && op_strict(pred_op))
+			return true;
+		/* Else the proof fails */
+		return false;
+	}
+
+	/*
+	 * Lookup the constant-comparison operator using the system catalogs and
+	 * the operator implication tables.
+	 */
+	test_op = get_btree_test_op(pred_op, clause_op, refute_it);
+
+	if (!OidIsValid(test_op))
+	{
+		/* couldn't find a suitable comparison operator */
+		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,
+							  InvalidOid,
+							  pred_collation);
+
+	/* Fill in opfuncids */
+	fix_opfuncids((Node *) test_expr);
+
+	/* Prepare it for execution */
+	test_exprstate = ExecInitExpr(test_expr, NULL);
+
+	/* And execute it. */
+	test_result = ExecEvalExprSwitchContext(test_exprstate,
+											GetPerTupleExprContext(estate),
+											&isNull);
+
+	/* Get back to outer memory context */
+	MemoryContextSwitchTo(oldcontext);
+
+	/* Release all the junk we just created */
+	FreeExecutorState(estate);
+
+	if (isNull)
+	{
+		/* Treat a null result as non-proof ... but it's a tad fishy ... */
+		elog(DEBUG2, "null predicate test result");
+		return false;
+	}
+	return DatumGetBool(test_result);
+}
+
+
+/*
+ * operator_same_subexprs_proof
+ *	  Assuming that EXPR1 clause_op EXPR2 is true, try to prove or refute
+ *	  EXPR1 pred_op EXPR2.
+ *
+ * Return true if able to make the proof, false if not able to prove it.
+ */
+static bool
+operator_same_subexprs_proof(Oid pred_op, Oid clause_op, bool refute_it)
+{
+	/*
+	 * A simple and general rule is that the predicate is proven if clause_op
+	 * and pred_op are the same, or refuted if they are each other's negators.
+	 * We need not check immutability since the pred_op is already known
+	 * immutable.  (Actually, by this point we may have the commutator of a
+	 * known-immutable pred_op, but that should certainly be immutable too.
+	 * Likewise we don't worry whether the pred_op's negator is immutable.)
+	 *
+	 * Note: the "same" case won't get here if we actually had EXPR1 clause_op
+	 * EXPR2 and EXPR1 pred_op EXPR2, because the overall-expression-equality
+	 * test in predicate_implied_by_simple_clause would have caught it.  But
+	 * we can see the same operator after having commuted the pred_op.
+	 */
+	if (refute_it)
+	{
+		if (get_negator(pred_op) == clause_op)
+			return true;
+	}
+	else
+	{
+		if (pred_op == clause_op)
+			return true;
+	}
+
+	/*
+	 * Otherwise, see if we can determine the implication by finding the
+	 * operators' relationship via some btree opfamily.
+	 */
+	return operator_same_subexprs_lookup(pred_op, clause_op, refute_it);
+}
+
+
+/*
+ * We use a lookaside table to cache the result of btree proof operator
+ * lookups, since the actual lookup is pretty expensive and doesn't change
+ * for any given pair of operators (at least as long as pg_amop doesn't
+ * change).  A single hash entry stores both implication and refutation
+ * results for a given pair of operators; but note we may have determined
+ * only one of those sets of results as yet.
+ */
+typedef struct OprProofCacheKey
+{
+	Oid			pred_op;		/* predicate operator */
+	Oid			clause_op;		/* clause operator */
+} OprProofCacheKey;
+
+typedef struct OprProofCacheEntry
+{
+	/* the hash lookup key MUST BE FIRST */
+	OprProofCacheKey key;
+
+	bool		have_implic;	/* do we know the implication result? */
+	bool		have_refute;	/* do we know the refutation result? */
+	bool		same_subexprs_implies;	/* X clause_op Y implies X pred_op Y? */
+	bool		same_subexprs_refutes;	/* X clause_op Y refutes X pred_op Y? */
+	Oid			implic_test_op; /* OID of the test operator, or 0 if none */
+	Oid			refute_test_op; /* OID of the test operator, or 0 if none */
+} OprProofCacheEntry;
+
+static HTAB *OprProofCacheHash = NULL;
+
+
+/*
+ * lookup_proof_cache
+ *	  Get, and fill in if necessary, the appropriate cache entry.
+ */
+static OprProofCacheEntry *
+lookup_proof_cache(Oid pred_op, Oid clause_op, bool refute_it)
+{
+	OprProofCacheKey key;
+	OprProofCacheEntry *cache_entry;
+	bool		cfound;
+	bool		same_subexprs = false;
+	Oid			test_op = InvalidOid;
+	bool		found = false;
+	List	   *pred_op_infos,
+			   *clause_op_infos;
+	ListCell   *lcp,
+			   *lcc;
+
+	/*
+	 * Find or make a cache entry for this pair of operators.
+	 */
+	if (OprProofCacheHash == NULL)
+	{
+		/* First time through: initialize the hash table */
+		HASHCTL		ctl;
+
+		ctl.keysize = sizeof(OprProofCacheKey);
+		ctl.entrysize = sizeof(OprProofCacheEntry);
+		OprProofCacheHash = hash_create("Btree proof lookup cache", 256,
+										&ctl, HASH_ELEM | HASH_BLOBS);
+
+		/* Arrange to flush cache on pg_amop changes */
+		CacheRegisterSyscacheCallback(AMOPOPID,
+									  InvalidateOprProofCacheCallBack,
+									  (Datum) 0);
+	}
+
+	key.pred_op = pred_op;
+	key.clause_op = clause_op;
+	cache_entry = (OprProofCacheEntry *) hash_search(OprProofCacheHash,
+													 (void *) &key,
+													 HASH_ENTER, &cfound);
+	if (!cfound)
+	{
+		/* new cache entry, set it invalid */
+		cache_entry->have_implic = false;
+		cache_entry->have_refute = false;
+	}
+	else
+	{
+		/* pre-existing cache entry, see if we know the answer yet */
+		if (refute_it ? cache_entry->have_refute : cache_entry->have_implic)
+			return cache_entry;
+	}
+
+	/*
+	 * Try to find a btree opfamily containing the given operators.
+	 *
+	 * We must find a btree opfamily that contains both operators, else the
+	 * implication can't be determined.  Also, the opfamily must contain a
+	 * suitable test operator taking the operators' righthand datatypes.
+	 *
+	 * If there are multiple matching opfamilies, 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 opfamilies.
+	 *
+	 * Note that we can determine the operators' relationship for
+	 * same-subexprs cases even from an opfamily that lacks a usable test
+	 * operator.  This can happen in cases with incomplete sets of cross-type
+	 * comparison operators.
+	 */
+	clause_op_infos = get_op_btree_interpretation(clause_op);
+	if (clause_op_infos)
+		pred_op_infos = get_op_btree_interpretation(pred_op);
+	else						/* no point in looking */
+		pred_op_infos = NIL;
+
+	foreach(lcp, pred_op_infos)
+	{
+		OpBtreeInterpretation *pred_op_info = lfirst(lcp);
+		Oid			opfamily_id = pred_op_info->opfamily_id;
+
+		foreach(lcc, clause_op_infos)
+		{
+			OpBtreeInterpretation *clause_op_info = lfirst(lcc);
+			StrategyNumber pred_strategy,
+						clause_strategy,
+						test_strategy;
+
+			/* Must find them in same opfamily */
+			if (opfamily_id != clause_op_info->opfamily_id)
+				continue;
+			/* Lefttypes should match */
+			Assert(clause_op_info->oplefttype == pred_op_info->oplefttype);
+
+			pred_strategy = pred_op_info->strategy;
+			clause_strategy = clause_op_info->strategy;
+
+			/*
+			 * Check to see if we can make a proof for same-subexpressions
+			 * cases based on the operators' relationship in this opfamily.
+			 */
+			if (refute_it)
+				same_subexprs |= BT_refutes_table[clause_strategy - 1][pred_strategy - 1];
+			else
+				same_subexprs |= BT_implies_table[clause_strategy - 1][pred_strategy - 1];
+
+			/*
+			 * Look up the "test" strategy number in the implication table
+			 */
+			if (refute_it)
+				test_strategy = BT_refute_table[clause_strategy - 1][pred_strategy - 1];
+			else
+				test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1];
+
+			if (test_strategy == 0)
+			{
+				/* Can't determine implication using this interpretation */
+				continue;
+			}
+
+			/*
+			 * See if opfamily has an operator for the test strategy and the
+			 * datatypes.
+			 */
+			if (test_strategy == BTNE)
+			{
+				test_op = get_opfamily_member(opfamily_id,
+											  pred_op_info->oprighttype,
+											  clause_op_info->oprighttype,
+											  BTEqualStrategyNumber);
+				if (OidIsValid(test_op))
+					test_op = get_negator(test_op);
+			}
+			else
+			{
+				test_op = get_opfamily_member(opfamily_id,
+											  pred_op_info->oprighttype,
+											  clause_op_info->oprighttype,
+											  test_strategy);
+			}
+
+			if (!OidIsValid(test_op))
+				continue;
+
+			/*
+			 * 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 is assumed to have been checked
+			 * immutable by the caller.)  Essentially we are assuming that the
+			 * opfamily is consistent even if it contains operators that are
+			 * merely stable.
+			 */
+			if (op_volatile(test_op) == PROVOLATILE_IMMUTABLE)
+			{
+				found = true;
+				break;
+			}
+		}
+
+		if (found)
+			break;
+	}
+
+	list_free_deep(pred_op_infos);
+	list_free_deep(clause_op_infos);
+
+	if (!found)
+	{
+		/* couldn't find a suitable comparison operator */
+		test_op = InvalidOid;
+	}
+
+	/*
+	 * If we think we were able to prove something about same-subexpressions
+	 * cases, check to make sure the clause_op is immutable before believing
+	 * it completely.  (Usually, the clause_op would be immutable if the
+	 * pred_op is, but it's not entirely clear that this must be true in all
+	 * cases, so let's check.)
+	 */
+	if (same_subexprs &&
+		op_volatile(clause_op) != PROVOLATILE_IMMUTABLE)
+		same_subexprs = false;
+
+	/* Cache the results, whether positive or negative */
+	if (refute_it)
+	{
+		cache_entry->refute_test_op = test_op;
+		cache_entry->same_subexprs_refutes = same_subexprs;
+		cache_entry->have_refute = true;
+	}
+	else
+	{
+		cache_entry->implic_test_op = test_op;
+		cache_entry->same_subexprs_implies = same_subexprs;
+		cache_entry->have_implic = true;
+	}
+
+	return cache_entry;
+}
+
+/*
+ * operator_same_subexprs_lookup
+ *	  Convenience subroutine to look up the cached answer for
+ *	  same-subexpressions cases.
+ */
+static bool
+operator_same_subexprs_lookup(Oid pred_op, Oid clause_op, bool refute_it)
+{
+	OprProofCacheEntry *cache_entry;
+
+	cache_entry = lookup_proof_cache(pred_op, clause_op, refute_it);
+	if (refute_it)
+		return cache_entry->same_subexprs_refutes;
+	else
+		return cache_entry->same_subexprs_implies;
+}
+
+/*
+ * get_btree_test_op
+ *	  Identify the comparison operator needed for a btree-operator
+ *	  proof or refutation involving comparison of constants.
+ *
+ * Given the truth of a clause "var clause_op const1", we are attempting to
+ * prove or refute a predicate "var pred_op const2".  The identities of the
+ * two operators are sufficient to determine the operator (if any) to compare
+ * const2 to const1 with.
+ *
+ * Returns the OID of the operator to use, or InvalidOid if no proof is
+ * possible.
+ */
+static Oid
+get_btree_test_op(Oid pred_op, Oid clause_op, bool refute_it)
+{
+	OprProofCacheEntry *cache_entry;
+
+	cache_entry = lookup_proof_cache(pred_op, clause_op, refute_it);
+	if (refute_it)
+		return cache_entry->refute_test_op;
+	else
+		return cache_entry->implic_test_op;
+}
+
+
+/*
+ * Callback for pg_amop inval events
+ */
+static void
+InvalidateOprProofCacheCallBack(Datum arg, int cacheid, uint32 hashvalue)
+{
+	HASH_SEQ_STATUS status;
+	OprProofCacheEntry *hentry;
+
+	Assert(OprProofCacheHash != NULL);
+
+	/* Currently we just reset all entries; hard to be smarter ... */
+	hash_seq_init(&status, OprProofCacheHash);
+
+	while ((hentry = (OprProofCacheEntry *) hash_seq_search(&status)) != NULL)
+	{
+		hentry->have_implic = false;
+		hentry->have_refute = false;
+	}
+}