MySQL Bugs: #58834: 'range access' may incorrectly filter away qualifying rows

Bug #58834	'range access' may incorrectly filter away qualifying rows
Submitted:	9 Dec 2010 8:15	Modified:	3 Jun 2011 2:04
Reporter:	Ole John Aske	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	5.6.2-m5, 5.5.9, 5.1.56	OS:	Any
Assigned to:		CPU Architecture:	Any

Description:
Mysql Cluster incorrectly filters away rows from the resultset when using the 'range' access method, and the condition is an 'OR* between multiple predicate terms.

How to repeat:
create table t1(k1 int, k2 int, primary key(k1,k2)) engine = ndb;

insert into  t1 values (6,3), (8,21);

explain
select * from t1
where  k1 <> 6 OR
      (k1 <> 8 AND k2 = 5);
--> Empty set (0.01 sec)

The row (8,21) should have been returned as it qualifies on 'k1 <> 6'

Verified, happens with both condition pushdown ON or OFF

Changed category from Cluster to Optimizer after investigation of this bug. Looking at debug trace, we find that the following sub-ranges has been
extracted from the predicate 'k1 <> 6 OR (k1 <> 8 AND k2 = 5)'

..................
T@15   : 14:30:11.731206 | | | | | | | | | | >print_quick
quick range select, key PRIMARY, length: 8
  X < 6
  6/5 <= X <= 6/5
  6 < X < 8
  8/5 <= X <= 8/5
  8 < X
.................

The sub range '8/5 <= X <= 8/5' is incorrect as it should have been eliminated by 'k1 <> 6'. Furthermore, eliminating this sub range should cause the enclosing ranges to be concatenated into the total sub range list:

  X < 6
  6/5 <= X <= 6/5
  6 < X

Request retriage as category changed and this bug may affect a broader range of customers.

Similar non-Cluster testcase: (Need more rows to trigger usage of 'range' access):

CREATE TABLE t10(
  K INT NOT NULL AUTO_INCREMENT,
  I INT, J INT,
  PRIMARY KEY(K),
  KEY(I,J)
);
INSERT INTO t10(I,J) VALUES (6,1),(6,2),(6,3),(6,4),(6,5),(6,6),(6,7),(6,8),(6,9),(6,0);

CREATE TABLE t100 LIKE t10;
INSERT INTO t100(I,J)
  SELECT X.I, X.K+(10*Y.K) FROM t10 AS X,t10 AS Y;

# Insert offending value:
INSERT INTO t100(I,J) VALUES(8,26);

#Verify that 'range' access will be used
EXPLAIN
 SELECT * FROM t100
 WHERE  I <> 6 OR
       (I <> 8 AND J = 5);
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | t100  | range | I             | I    | 10      | NULL |    6 | Using where |
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+

# With 'range' access the row '8,26' is not selected
SELECT * FROM t100
  WHERE  I <> 6 OR
        (I <> 8 AND J = 5);
Empty set (0.01 sec)

# Then without 'range' on index(I)
SELECT * FROM t100 IGNORE INDEX(I)
  WHERE  I <> 6 OR
        (I <> 8 AND J = 5);
+-----+------+------+
| K   | I    | J    |
+-----+------+------+
| 101 |    8 |   26 |
+-----+------+------+

Changed status to 'open' as we need to check which version is affected, or of it is a regression - See new non-Cluster testcase.

Also changed Synopsis to reflect that this is not a Cluster specific bug.

Updated 'Version' which those versions I have reproduced the error on. Not tested < 5.1.

Verified with current mysql-5.1 on Mac OS X:

macbook-pro:5.1 openxs$ bin/mysql -uroot test
Reading 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 3
Server version: 5.1.56-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> CREATE TABLE t10(
    ->   K INT NOT NULL AUTO_INCREMENT,
    ->   I INT, J INT,
    ->   PRIMARY KEY(K),
    ->   KEY(I,J)
    -> );
Query OK, 0 rows affected (0.05 sec)

mysql> INSERT INTO t10(I,J) VALUES (6,1),(6,2),(6,3),(6,4),(6,5),(6,6),(6,7),(6,8),(6,9),(6,0);
Query OK, 10 rows affected (0.00 sec)
Records: 10  Duplicates: 0  Warnings: 0

mysql> CREATE TABLE t100 LIKE t10;
Query OK, 0 rows affected (0.09 sec)

mysql> INSERT INTO t100(I,J)
    ->   SELECT X.I, X.K+(10*Y.K) FROM t10 AS X,t10 AS Y;
Query OK, 100 rows affected (0.00 sec)
Records: 100  Duplicates: 0  Warnings: 0

mysql> INSERT INTO t100(I,J) VALUES(8,26);
Query OK, 1 row affected (0.00 sec)

mysql> EXPLAIN
    ->  SELECT * FROM t100
    ->  WHERE  I <> 6 OR
    ->        (I <> 8 AND J = 5);
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | t100  | range | I             | I    | 10      | NULL |    6 | Using where |
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
1 row in set (0.02 sec)

mysql> SELECT * FROM t100
    ->   WHERE  I <> 6 OR
    ->         (I <> 8 AND J = 5);
Empty set (0.00 sec)

mysql> SELECT * FROM t100 IGNORE INDEX(I)
    ->   WHERE  I <> 6 OR
    ->         (I <> 8 AND J = 5);
+-----+------+------+
| K   | I    | J    |
+-----+------+------+
| 101 |    8 |   26 |
+-----+------+------+
1 row in set (0.00 sec)

Noted in 5.6.3 changelog.

The range created by the optimizer when OR-ing two conditions could
be incorrect, causing incorrect query results. 

CHANGESET - http://lists.mysql.com/commits/137696