Bug #54802 'NOT BETWEEN' evaluation is incorrect
Submitted: 25 Jun 2010 11:34 Modified: 15 Oct 2010 13:30
Reporter: Ole John Aske Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S2 (Serious)
Version:5.0.92-bzr, 5.1.37, 5.1.49, 5.5.6-m3 OS:Any
Assigned to: Alexey Kopytov CPU Architecture:Any
Triage: Triaged: D2 (Serious)

[25 Jun 2010 11:34] Ole John Aske
Description:
A WHERE-predicate containing NOT BETWEEN may return a truncated result set
as described in 'How to repeat'.

Explaining this query shows:

mysql> explain
    -> SELECT pk, col_int, col_int_key
    ->  FROM W AS table1
    ->  WHERE NOT (4 BETWEEN col_int AND col_int_key);
+----+-------------+--------+-------+---------------+-------------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key         | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+-------------+---------+------+------+-------------+
|  1 | SIMPLE      | table1 | range | col_int_key   | col_int_key | 5       | NULL |    2 | Using where |
+----+-------------+--------+-------+---------------+-------------+---------+------+------+-------------+
1 row in set (0.00 sec)

Using a 'range' access to evaluate a *not* between looks suspicious....

How to repeat:
Load mysqldump which I will attach.

SELECT pk, col_int, col_int_key
 FROM W AS table1
 WHERE NOT (4 BETWEEN col_int AND col_int_key);

Return the (incorrect) result set 

+----+---------+-------------+
| pk | col_int | col_int_key |
+----+---------+-------------+
|  4 |       8 |           1 |
| 23 |       2 |           1 |
+----+---------+-------------+
2 rows in set (0.00 sec)

Then, apply the BETWEEN rewrite rule:

 'X BETWEEN <low> AND <high>' -> 'X >= <low> AND X <= <high>'

SELECT pk, col_int, col_int_key
 FROM W AS table1
 WHERE NOT (4 >= col_int AND 4 <= col_int_key);
+----+---------+-------------+
| pk | col_int | col_int_key |
+----+---------+-------------+
|  1 |      46 |           8 |
|  2 |       9 |          30 |
|  4 |       8 |           1 |
|  5 |      29 |          44 |
|  6 |      29 |           5 |
|  7 |      43 |          17 |
|  8 |      42 |          16 |
|  9 |       5 |          13 |
| 10 |      27 |          22 |
| 11 |      25 |           9 |
| 12 |      16 |           5 |
| 14 |      35 |          40 |
| 15 |       7 |          20 |
| 16 |      13 |          50 |
| 17 |      29 |           9 |
| 18 |      37 |          16 |
| 19 |      20 |          11 |
| 20 |      17 |          10 |
| 21 |      10 |          20 |
| 22 |      25 |          31 |
| 23 |       2 |           1 |
| 24 |      46 |        NULL |
| 25 |      50 |          28 |
| 26 |      30 |          36 |
+----+---------+-------------+
24 rows in set (0.00 sec)

Which is the correct result set.
[25 Jun 2010 11:35] Ole John Aske
mysqldump of database

Attachment: spj_myisam.sql (text/x-sql), 115.98 KiB.

[25 Jun 2010 12:36] Valeriy Kravchuk
Verified just as described:

valeriy-kravchuks-macbook-pro:5.1 openxs$ bin/mysql -uroot testReading table information for completion of table and column names
You can turn off this feature to get a quicker startup with -A

Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 4
Server version: 5.1.49-debug Source distribution

Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved.
This software comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to modify and redistribute it under the GPL v2 license

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql> explain SELECT pk, col_int, col_int_key
    ->  FROM W AS table1
    ->  WHERE NOT (4 BETWEEN col_int AND col_int_key);
+----+-------------+--------+-------+---------------+-------------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key         | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+-------------+---------+------+------+-------------+
|  1 | SIMPLE      | table1 | range | col_int_key   | col_int_key | 5       | NULL |    2 | Using where |
+----+-------------+--------+-------+---------------+-------------+---------+------+------+-------------+
1 row in set (0.09 sec)

mysql> SELECT pk, col_int, col_int_key
    ->  FROM W AS table1
    ->  WHERE NOT (4 BETWEEN col_int AND col_int_key);
+----+---------+-------------+
| pk | col_int | col_int_key |
+----+---------+-------------+
|  4 |       8 |           1 |
| 23 |       2 |           1 |
+----+---------+-------------+
2 rows in set (0.00 sec)

mysql> SELECT pk, col_int, col_int_key  FROM W AS table1  WHERE NOT ((4 >= col_int) AND (4 <= col_int_key));
+----+---------+-------------+
| pk | col_int | col_int_key |
+----+---------+-------------+
|  1 |      46 |           8 |
|  2 |       9 |          30 |
|  4 |       8 |           1 |
|  5 |      29 |          44 |
|  6 |      29 |           5 |
|  7 |      43 |          17 |
|  8 |      42 |          16 |
|  9 |       5 |          13 |
| 10 |      27 |          22 |
| 11 |      25 |           9 |
| 12 |      16 |           5 |
| 14 |      35 |          40 |
| 15 |       7 |          20 |
| 16 |      13 |          50 |
| 17 |      29 |           9 |
| 18 |      37 |          16 |
| 19 |      20 |          11 |
| 20 |      17 |          10 |
| 21 |      10 |          20 |
| 22 |      25 |          31 |
| 23 |       2 |           1 |
| 24 |      46 |        NULL |
| 25 |      50 |          28 |
| 26 |      30 |          36 |
+----+---------+-------------+
24 rows in set (0.00 sec)

mysql> explain SELECT pk, col_int, col_int_key  FROM W AS table1  WHERE NOT ((4 >= col_int) AND (4 <= col_int_key));
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | table1 | ALL  | col_int_key   | NULL | NULL    | NULL |   26 | Using where |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
1 row in set (0.00 sec)
[25 Jun 2010 12:39] Valeriy Kravchuk
Same problem with 5.0.92:

valeriy-kravchuks-macbook-pro:5.0 openxs$ bin/mysql -uroot testReading table information for completion of table and column names
You can turn off this feature to get a quicker startup with -A

Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 2
Server version: 5.0.92-debug Source distribution

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql> SELECT pk, col_int, col_int_key
    ->  FROM W AS table1
    ->  WHERE NOT (4 BETWEEN col_int AND col_int_key);
+----+---------+-------------+
| pk | col_int | col_int_key |
+----+---------+-------------+
|  4 |       8 |           1 | 
| 23 |       2 |           1 | 
+----+---------+-------------+
2 rows in set (0.01 sec)

mysql> explain SELECT pk, col_int, col_int_key
    ->  FROM W AS table1
    ->  WHERE NOT (4 BETWEEN col_int AND col_int_key);
+----+-------------+--------+-------+---------------+-------------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key         | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+-------------+---------+------+------+-------------+
|  1 | SIMPLE      | table1 | range | col_int_key   | col_int_key | 5       | NULL |    2 | Using where | 
+----+-------------+--------+-------+---------------+-------------+---------+------+------+-------------+
1 row in set (0.00 sec)

and current mysql-trunk:

valeriy-kravchuks-macbook-pro:trunk openxs$ bin/mysql -uroot testReading table information for completion of table and column names
You can turn off this feature to get a quicker startup with -A

Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 2
Server version: 5.5.6-m3-debug Source distribution

Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved.
This software comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to modify and redistribute it under the GPL v2 license

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql> explain SELECT pk, col_int, col_int_key  FROM W AS table1  WHERE NOT (4 BETWEEN col_int AND col_int_key);
+----+-------------+--------+-------+---------------+-------------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key         | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+-------------+---------+------+------+-------------+
|  1 | SIMPLE      | table1 | range | col_int_key   | col_int_key | 5       | NULL |    2 | Using where |
+----+-------------+--------+-------+---------------+-------------+---------+------+------+-------------+
1 row in set (0.10 sec)

mysql> SELECT pk, col_int, col_int_key  FROM W AS table1  WHERE NOT (4 BETWEEN col_int AND col_int_key);
+----+---------+-------------+
| pk | col_int | col_int_key |
+----+---------+-------------+
|  4 |       8 |           1 |
| 23 |       2 |           1 |
+----+---------+-------------+
2 rows in set (0.00 sec)
[24 Aug 2010 15:52] Bugs System
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/commits/116677

3489 Alexey Kopytov	2010-08-24
      Bug #54802: 'NOT BETWEEN' evaluation is incorrect
      
      Queries involving predicates of the form "const NOT BETWEEN
      not_indexed_column AND indexed_column" could return wrong data
      due to incorrect handling by the range optimizer.
      
      For "c NOT BETWEEN f1 AND f2" predicates, get_mm_tree()
      produces a disjunction of the SEL_ARG trees for "f1 > c" and
      "f2 < c". If one of the trees is empty (i.e. one of the
      arguments is not sargable) the resulting tree should be empty
      as well, since the whole expression in this case is not
      sargable.
      
      The above logic is implemented in get_mm_tree() as follows. The
      initial state of the resulting tree is NULL (aka empty). We
      then iterate through arguments and compute the corresponding
      SEL_ARG tree (either "f1 > c" or "f2 < c"). If the resulting
      tree is NULL, it is simply replaced by the generated
      tree. Otherwise it is replaced by a disjunction of itself and
      the generated tree. The obvious flaw in this implementation is
      that if the first argument is not sargable and thus produces a
      NULL tree, the resulting tree will simply be replaced by the
      tree for the second argument. As a result, "c NOT BETWEEN f1
      AND f2" will end up as just "f2 < c".
      
      Fixed by adding a check so that when the first argument
      produces an empty tree for the NOT BETWEEN case, the loop is
      aborted with an empty tree as a result. The whole idea of using
      a loop for 2 arguments does not make much sense, but it was
      probably used to avoid code duplication for several BETWEEN
      variants.
[1 Sep 2010 13:12] Bugs System
Pushed into mysql-trunk 5.6.1-m4 (revid:alik@sun.com-20100901130501-4g2k86dub29auj8y) (version source revid:alik@sun.com-20100901130012-9bmmvzcnnw6n5rw6) (merge vers: 5.6.1-m4) (pib:21)
[1 Sep 2010 13:14] Bugs System
Pushed into mysql-next-mr (revid:alik@sun.com-20100901130614-pgop3m80rmutewxn) (version source revid:alik@sun.com-20100901130033-8k19cjn6n2blm3py) (pib:21)
[1 Sep 2010 13:15] Bugs System
Pushed into mysql-5.5 5.5.7-m3 (revid:alik@sun.com-20100901125952-4hsrosoa0xreionr) (version source revid:alik@sun.com-20100901125952-4hsrosoa0xreionr) (merge vers: 5.5.7-m3) (pib:21)
[8 Sep 2010 19:19] Paul Dubois
Noted in 5.1.51, 5.5.7, 5.6.1 changelogs.

Queries involving predicates of the form "const NOT BETWEEN
not_indexed_column AND indexed_column" could return incorrect data due
to incorrect handling by the range optimizer.
[28 Sep 2010 8:49] Bugs System
Pushed into mysql-5.1 5.1.52 (revid:sunanda.menon@sun.com-20100928083322-wangbv97uobu7g66) (version source revid:sunanda.menon@sun.com-20100928083322-wangbv97uobu7g66) (merge vers: 5.1.52) (pib:21)
[14 Oct 2010 8:35] Bugs System
Pushed into mysql-5.1-telco-7.0 5.1.51-ndb-7.0.20 (revid:martin.skold@mysql.com-20101014082627-jrmy9xbfbtrebw3c) (version source revid:martin.skold@mysql.com-20101014082627-jrmy9xbfbtrebw3c) (merge vers: 5.1.51-ndb-7.0.20) (pib:21)
[14 Oct 2010 8:50] Bugs System
Pushed into mysql-5.1-telco-6.3 5.1.51-ndb-6.3.39 (revid:martin.skold@mysql.com-20101014083757-5qo48b86d69zjvzj) (version source revid:martin.skold@mysql.com-20101014083757-5qo48b86d69zjvzj) (merge vers: 5.1.51-ndb-6.3.39) (pib:21)
[14 Oct 2010 9:06] Bugs System
Pushed into mysql-5.1-telco-6.2 5.1.51-ndb-6.2.19 (revid:martin.skold@mysql.com-20101014084420-y54ecj85j5we27oa) (version source revid:martin.skold@mysql.com-20101014084420-y54ecj85j5we27oa) (merge vers: 5.1.51-ndb-6.2.19) (pib:21)
[15 Oct 2010 13:30] Jon Stephens
Already documented in the 5.1.51 changelog. Reverting to Closed state.