Thread: Question about partial functional indexes and the query planner

Brian Dunavant <brian@omniti.com> writes:
> I am using a partial functional index on a table where F(a) = a.  Querying
> whre F(a) = a hits the index as expected.  However the reverse statement a
> = F(a) does not.  I have verified this in 9.3.4.
> Is this a deficiency with the query planner, or are these not actually
> equivalent?  I've been stumped on it.

Interesting.  The reason this doesn't work is that predicate_implied_by()
fails to prove "a = b" given "b = a", at least in the general case.
It will figure that out if either a or b is a constant, but not if
neither one is.  The fact that it works with constants might explain
the lack of previous complaints, but this is still pretty surprising
given the amount of knowledge about equality that the system evinces
otherwise.  (I'm also wondering whether the EquivalenceClass logic
might not sometimes rewrite "a = b" into "b = a", causing a failure
of this sort even when the user *had* phrased his query consistently.)

It would be fairly straightforward to add a proof rule along the lines of
"if both expressions are binary opclauses, and the left input expression
of each one is equal() to the right input of the other, and the operators
are each other's commutators, then the implication holds".

An objection might be made that this would add noticeably to the cost of
failing proofs, but I think it wouldn't be that bad, especially if we did
the syscache lookup for the commutator check last.  In most scenarios the
equal() checks would fail pretty quickly when the proof rule doesn't
apply.  Also, I believe that in the case where a or b is a constant,
even though we can make the proof already, this approach would succeed
noticeably more quickly than btree_predicate_proof() can.  (Worth noting
also is that predicate_implied_by() isn't even used unless you have
things like partial indexes involved, so that its cost is not especially
relevant to "simple" queries.)

I'd be inclined to add some similar proof rules to predicate_refuted_by,
along the lines of "a op1 b refutes a op2 b if op1 is op2's negator" and
"a op1 b refutes b op2 a if op1 is the negator of op2's commutator".
Again, the code is currently unable to make such deductions unless a or b
is a constant.

Given the lack of previous complaints, I'm not sure this amounts to
a back-patchable bug, but it does seem like something worth fixing
going forward.

            regards, tom lane

On Tue, Jun 10, 2014 at 7:19 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Given the lack of previous complaints, I'm not sure this amounts to
> a back-patchable bug, but it does seem like something worth fixing
> going forward.

Agreed, although I'd be willing to see us slip it into 9.4.  It's
doubtful that anyone will get upset if their query plans change
between beta1 and beta2, but the same cannot be said for released
branches.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:
> On Tue, Jun 10, 2014 at 7:19 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Given the lack of previous complaints, I'm not sure this amounts to
>> a back-patchable bug, but it does seem like something worth fixing
>> going forward.

> Agreed, although I'd be willing to see us slip it into 9.4.  It's
> doubtful that anyone will get upset if their query plans change
> between beta1 and beta2, but the same cannot be said for released
> branches.

After further thought about this I realized that there's another category
of proof possibilities that is pretty simple to add while we're at it.
Namely, once we've found that both subexpressions of the two operator
clauses are equal(), we can use btree opclass relationships to prove that,
say, "x < y implies x <= y" or "x < y refutes x > y", independently of
just what x and y are.  (Well, they have to be immutable expressions, but
we'd not get this far if they're not.)  We already had pretty nearly all
of the machinery for that, but again it was only used for proving cases
involving comparisons to constants.

A little bit of refactoring later, I offer the attached draft patch.
I'm thinking this is probably more than we want to slip into 9.4
at this point, but I'll commit it to HEAD soon if there are not
objections.

            regards, tom lane

diff --git a/src/backend/optimizer/util/predtest.c b/src/backend/optimizer/util/predtest.c
index 9d61a4d..039221f 100644
*** a/src/backend/optimizer/util/predtest.c
--- b/src/backend/optimizer/util/predtest.c
*************** static bool predicate_refuted_by_simple_
*** 95,102 ****
  static Node *extract_not_arg(Node *clause);
  static Node *extract_strong_not_arg(Node *clause);
  static bool list_member_strip(List *list, Expr *datum);
! static bool btree_predicate_proof(Expr *predicate, Node *clause,
!                       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);

--- 95,106 ----
  static Node *extract_not_arg(Node *clause);
  static Node *extract_strong_not_arg(Node *clause);
  static bool list_member_strip(List *list, Expr *datum);
! static bool operator_predicate_proof(Expr *predicate, Node *clause,
!                          bool refute_it);
! 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);

*************** arrayexpr_cleanup_fn(PredIterInfo info)
*** 1025,1032 ****
   * we are within an AND/OR subtree of a WHERE clause.  (Again, "foo" is
   * already known immutable, so the clause will certainly always fail.)
   *
!  * Finally, we may be able to deduce something using knowledge about btree
!  * operator families; this is encapsulated in btree_predicate_proof().
   *----------
   */
  static bool
--- 1029,1037 ----
   * we are within an AND/OR subtree of a WHERE clause.  (Again, "foo" is
   * already known immutable, so the clause will certainly always fail.)
   *
!  * Finally, 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
*** 1060,1067 ****
          return false;            /* we can't succeed below... */
      }

!     /* Else try btree operator knowledge */
!     return btree_predicate_proof(predicate, clause, false);
  }

  /*----------
--- 1065,1072 ----
          return false;            /* we can't succeed below... */
      }

!     /* Else try operator-related knowledge */
!     return operator_predicate_proof(predicate, clause, false);
  }

  /*----------
*************** predicate_implied_by_simple_clause(Expr
*** 1083,1090 ****
   * these cases is to support using IS NULL/IS NOT NULL as partition-defining
   * constraints.)
   *
!  * Finally, we may be able to deduce something using knowledge about btree
!  * operator families; this is encapsulated in btree_predicate_proof().
   *----------
   */
  static bool
--- 1088,1096 ----
   * these 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
*** 1148,1155 ****
          return false;            /* we can't succeed below... */
      }

!     /* Else try btree operator knowledge */
!     return btree_predicate_proof(predicate, clause, true);
  }


--- 1154,1161 ----
          return false;            /* we can't succeed below... */
      }

!     /* Else try operator-related knowledge */
!     return operator_predicate_proof(predicate, clause, true);
  }


*************** list_member_strip(List *list, Expr *datu
*** 1239,1277 ****


  /*
!  * Define an "operator implication table" for btree operators ("strategies"),
!  * and a similar table for refutation.
   *
   * The strategy numbers defined by btree indexes (see access/skey.h) are:
!  *        (1) <    (2) <=     (3) =     (4) >=   (5) >
!  * 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().)
   *
!  * 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.
   *
   * For example, if clause is "Quantity > 10" and pred is "Quantity > 5"
   * then we test "5 <= 10" which evals to true, so clause implies pred.
   *
   * Similarly, the interpretation of a BT_refute_table entry is:
   *
!  *     If you know, for some ATTR, that "ATTR given_op CONST1" is true, and you
!  *     want to determine whether "ATTR target_op CONST2" must be false, then
   *     you can use "CONST2 test_op CONST1" as a test.  If this test returns true,
!  *     then the target expression must be false; if the test returns false, then
!  *     the target expression may be true.
   *
   * For example, if clause is "Quantity > 10" and pred is "Quantity < 5"
   * then we test "5 <= 10" which evals to true, so clause refutes pred.
--- 1245,1297 ----


  /*
!  * Define "operator implication tables" for btree operators ("strategies"),
!  * and similar tables for refutation.
   *
   * 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 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.
*************** list_member_strip(List *list, Expr *datu
*** 1286,1325 ****
  #define BTGT BTGreaterStrategyNumber
  #define BTNE ROWCOMPARE_NE

  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 */
  };

  static const StrategyNumber BT_refute_table[6][6] = {
  /*
!  *            The target operator:
!  *
   *     LT    LE     EQ    GE     GT    NE
   */
!     {0, 0, BTGE, BTGE, BTGE, 0},    /* LT */
!     {0, 0, BTGT, BTGT, BTGE, 0},    /* LE */
      {BTLE, BTLT, BTNE, BTGT, BTGE, BTEQ},        /* EQ */
!     {BTLE, BTLT, BTLT, 0, 0, 0},    /* GE */
!     {BTLE, BTLE, BTLE, 0, 0, 0},    /* GT */
!     {0, 0, BTEQ, 0, 0, 0}        /* NE */
  };


  /*
!  * btree_predicate_proof
   *      Does the predicate implication or refutation test for a "simple clause"
!  *      predicate and a "simple clause" restriction, when both are simple
!  *      operator clauses using related btree operators.
   *
   * When refute_it == false, we want to prove the predicate true;
   * when refute_it == true, we want to prove the predicate false.
--- 1306,1372 ----
  #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.
*************** static const StrategyNumber BT_refute_ta
*** 1327,1358 ****
   * in one routine.)  We return TRUE if able to make the proof, FALSE
   * if not able to prove it.
   *
!  * What we look for here is binary boolean opclauses of the form
!  * "foo op constant", where "foo" is the same in both clauses.  The operators
!  * and constants can be different but the operators must be in the same btree
!  * operator family.  We use the above operator implication tables to
!  * derive implications between nonidentical clauses.  (Note: "foo" is known
!  * immutable, and constants are surely immutable, but we have to check that
!  * the operators are too.  As of 8.0 it's possible for opfamilies to contain
!  * operators that are merely stable, and we dare not make deductions with
!  * these.)
   */
  static bool
! btree_predicate_proof(Expr *predicate, Node *clause, bool refute_it)
  {
!     Node       *leftop,
!                *rightop;
!     Node       *pred_var,
!                *clause_var;
!     Const       *pred_const,
!                *clause_const;
!     bool        pred_var_on_left,
!                 clause_var_on_left;
      Oid            pred_collation,
                  clause_collation;
      Oid            pred_op,
                  clause_op,
                  test_op;
      Expr       *test_expr;
      ExprState  *test_exprstate;
      Datum        test_result;
--- 1374,1420 ----
   * in one routine.)  We return TRUE if able to make the proof, FALSE
   * if not able to prove it.
   *
!  * 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)
  {
!     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;
*************** btree_predicate_proof(Expr *predicate, N
*** 1361,1461 ****
      MemoryContext oldcontext;

      /*
!      * Both expressions must be binary opclauses with a Const on one side, and
!      * identical subexpressions on the other sides. Note we don't have to
!      * think about binary relabeling of the Const node, since that would have
!      * been folded right into the Const.
       *
!      * 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;

      /*
!      * They'd better have the same collation, too.
       */
!     pred_collation = ((OpExpr *) predicate)->inputcollid;
!     clause_collation = ((OpExpr *) clause)->inputcollid;
      if (pred_collation != clause_collation)
          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;
      }

      /*
!      * Lookup the comparison operator using the system catalogs and the
!      * operator implication tables.
       */
      test_op = get_btree_test_op(pred_op, clause_op, refute_it);

--- 1423,1562 ----
      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 equal subexpressions, and two other subexpressions that are
!      * not equal 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, fail.
!      */
!     if (pred_const->constisnull)
!         return false;
!     if (clause_const->constisnull)
!         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);

*************** btree_predicate_proof(Expr *predicate, N
*** 1510,1520 ****


  /*
   * 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 positive and negative results
!  * for a given pair of operators.
   */
  typedef struct OprProofCacheKey
  {
--- 1611,1664 ----


  /*
+  * 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
  {
*************** typedef struct OprProofCacheEntry
*** 1529,1560 ****

      bool        have_implic;    /* do we know the implication result? */
      bool        have_refute;    /* do we know the refutation result? */
!     Oid            implic_test_op; /* OID of the operator, or 0 if none */
!     Oid            refute_test_op; /* OID of the operator, or 0 if none */
  } OprProofCacheEntry;

  static HTAB *OprProofCacheHash = NULL;


  /*
!  * get_btree_test_op
!  *      Identify the comparison operator needed for a btree-operator
!  *      proof or refutation.
!  *
!  * Given the truth of a predicate "var pred_op const1", we are attempting to
!  * prove or refute a clause "var clause_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)
  {
      OprProofCacheKey key;
      OprProofCacheEntry *cache_entry;
      bool        cfound;
      Oid            test_op = InvalidOid;
      bool        found = false;
      List       *pred_op_infos,
--- 1673,1698 ----

      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,
*************** get_btree_test_op(Oid pred_op, Oid claus
*** 1596,1612 ****
      }
      else
      {
!         /* pre-existing cache entry, see if we know the answer */
!         if (refute_it)
!         {
!             if (cache_entry->have_refute)
!                 return cache_entry->refute_test_op;
!         }
!         else
!         {
!             if (cache_entry->have_implic)
!                 return cache_entry->implic_test_op;
!         }
      }

      /*
--- 1734,1742 ----
      }
      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;
      }

      /*
*************** get_btree_test_op(Oid pred_op, Oid claus
*** 1620,1625 ****
--- 1750,1760 ----
       * 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)
*************** get_btree_test_op(Oid pred_op, Oid claus
*** 1649,1654 ****
--- 1784,1798 ----
              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)
*************** get_btree_test_op(Oid pred_op, Oid claus
*** 1715,1733 ****
          test_op = InvalidOid;
      }

!     /* Cache the result, whether positive or negative */
      if (refute_it)
      {
          cache_entry->refute_test_op = test_op;
          cache_entry->have_refute = true;
      }
      else
      {
          cache_entry->implic_test_op = test_op;
          cache_entry->have_implic = true;
      }

!     return test_op;
  }


--- 1859,1932 ----
          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;
  }