MySQL Bugs: #12101: Invalid outer join elimination for a query with NOT BETWEEN condition

Bug #12101	Invalid outer join elimination for a query with NOT BETWEEN condition
Submitted:	22 Jul 2005 2:57	Modified:	9 Sep 2005 20:22
Reporter:	Igor Babaev	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server	Severity:	S2 (Serious)
Version:	4.1.13, 5.0.10	OS:	Any (all)
Assigned to:	Alexander Ivanov	CPU Architecture:	Any

Description:
The query 
SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.a
  WHERE t1.a NOT BETWEEN t2.b AND t1.b; 
returns
+---+------+------+------+
| a | b    | a    | b    |
+---+------+------+------+
| 3 |    2 |    3 |    0 |
| 4 |    3 |    4 |    1 |
| 6 |    5 |    6 |    4 |
+---+------+------+------+
while an equivalent query 
SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.a
  WHERE t2.b > t1.a OR t1.a > t1.b
returns
+---+------+------+------+
| a | b    | a    | b    |
+---+------+------+------+
| 2 |    1 | NULL | NULL |
| 3 |    2 |    3 |    0 |
| 4 |    3 |    4 |    1 |
| 6 |    5 |    6 |    4 |
| 8 |    7 | NULL | NULL |
+---+------+------+------+

Aparrently the first result set is not correct.

It happens due to outer join elimination erroneously applied for the first query. This can be seen from the following EXPLAIN output:
mysql> EXPLAIN SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.a
    ->   WHERE t1.a NOT BETWEEN t2.b AND t1.b;
+----+-------------+-------+--------+---------------+---------+---------+-----------+------+-------------+
| id | select_type | table | type   | possible_keys | key     | key_len | ref       | rows | Extra       |
+----+-------------+-------+--------+---------------+---------+---------+-----------+------+-------------+
|  1 | SIMPLE      | t2    | ALL    | PRIMARY       | NULL    | NULL    | NULL      |    4 |             |
|  1 | SIMPLE      | t1    | eq_ref | PRIMARY       | PRIMARY | 4       | test.t2.a |    1 | Using where |
+----+-------------+-------+--------+---------------+---------+---------+-----------+------+-------------+

The bug can be reproduced for 4.1.13 as well, although there the EXPLAIN output does not indicate the outer join elimination.

How to repeat:
Executing the following commands can demonstrate the problem:

CREATE TABLE t1 (a int PRIMARY KEY, b int);
INSERT INTO t1 VALUES
 (1, 2), (2, 1), (3, 2), (4, 3), (5,6), (6,5), (7,8), (8,7), (9,10);
CREATE TABLE t2 (a int PRIMARY KEY, b int);
INSERT INTO t2 
  VALUES (3,0), (4,1), (6,4), (7,5);
SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.a
  WHERE t1.a NOT BETWEEN t2.b AND t1.b;
SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.a
  WHERE t2.b > t1.a OR t1.a > t1.b;

Suggested fix:
Correct calculation of the not_null_tables attribute for NOT LIKE conditions.

Correction:
Suggested fix:
Correct calculation of the not_null_tables attribute for NOT BETWEEN conditions.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/internals/29162

See also BUG#12102

ChangeSet
  1.2403 05/09/06 18:03:08 aivanov@mysql.com +6 -0
  item_cmpfunc.h:
    Fixed bugs #12101, #12102: wrong calculation of not_null_tables()
     for some expressions.
     The classes Item_func_between, Item_func_if, Item_func_in are modified.
     Item_func_between/in objects can represent now [NOT]BETWEEN/IN expressions.
     The class Item_func_opt_neg is added to factor out the functionality
     common for the modified classes Item_func_between and Item_func_in.
  item_cmpfunc.cc:
    Fixed bugs #12101, #12102: wrong calculation of not_null_tables()
     for some expressions.
     Added Item_func_between::fix_fields(), Item_func_if::fix_fields(),
     Item_func_in::fix_fields(). They correct generic calculation of
     the not_null_tables attribute when it is needed.
     Modified Item_func_between::val_int(), Item_func_in::val_int().
  opt_range.cc:
    Fixed bugs #12101, #12102: wrong calculation of not_null_tables()
     for some expressions.
     The function get_mm_tree() is modified. There cannot be NOT before
     BETWEEN/IN anymore. Rather Item_func_between/in objects can represent
     now [NOT]BETWEEN/IN expressions.
  sql_yacc.yy:
    Fixed bugs #12101, #12102: wrong calculation of not_null_tables()
     for some expressions.
     Item_func_between/in objects can represent now [NOT]BETWEEN/IN expresions.
  join_outer.result:
    Fixed some testcases results (bugs #12101, #12102)
  join_outer.test:
    Added testcases for bugs #12101, #12102

Perfomed a merge 4.1->5.0
  sql_select.cc is changed in 5.0

The fix will appear in 4.1.15 and 5.0.13

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/internals/29570

Noted in 4.1.15, 5.0.13 changelogs.