Optimizer misses equality from x >= y AND x <= y join predicate

This is an optimizer performance issue for equality-equivalent join predicates.

The attached testcase creates three InnoDB tables with 1000 rows each. All columns involved in the compared join predicates are declared as BIGINT NOT NULL. Therefore, in this testcase, the predicates below are equality-equivalent without involving NULL semantics. The final query returns 10 rows.

The following predicate forms are logically equivalent in this testcase:

• Equality form:

  t3.c0 = t1.c1

  AND t3.c1 = t2.c1

• BETWEEN-equivalent form:

  t3.c0 BETWEEN t1.c1 AND t1.c1

  AND t3.c1 BETWEEN t2.c1 AND t2.c1

• NOT <> equivalent form:

  NOT (t3.c0 <> t1.c1)

  AND NOT (t3.c1 <> t2.c1)

• >= and <= equivalent form:

  t3.c0 >= t1.c1 AND t3.c0 <= t1.c1

  AND t3.c1 >= t2.c1 AND t3.c1 <= t2.c1

The equality, BETWEEN, and NOT <> forms all return the same 10 rows and use good ref/index lookup plans. On my machine they run in about 3 ms.

However, the logically equivalent >= and <= form returns the same 10 rows and checksum, but the optimizer chooses a much worse plan:

t1: index

t2: range, Using join buffer (flat, BNL join)

t3: ALL, Range checked for each record

ANALYZE shows that this plan takes about 10199 ms on my machine, with 1,000,000 loops for t3 and about 8,003,000 pages accessed.

The performance difference is roughly:

equality form:        about 3.05 ms

BETWEEN x AND x form: about 2.80 ms

NOT <> form:          about 3.12 ms

>= AND <= form:       about 10199 ms

This suggests that MariaDB can recognize equality, BETWEEN x AND x, and NOT(x <> y) as equality-like join predicates, but does not normalize the equivalent x >= y AND x <= y form into an equality/ref join condition.

Expected behavior: because the compared columns are BIGINT NOT NULL in this testcase, x >= y AND x <= y should be recognized as equality-equivalent to x = y, so the optimizer can use the same ref access path as the equality, BETWEEN, and NOT <> forms instead of falling back to BNL plus range-checked-for-each-record.

A possible fix would be to extend equality propagation or predicate normalization so that predicates of the form:

x >= y AND x <= y

can be treated as equality-equivalent to:

x = y

when this transformation is semantically valid. When such predicates compare columns from different tables, the optimizer should be able to use them as equality join predicates and choose ref access.