| 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: | |
| 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 |
[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.
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.