Bug #70021 Poor execution of a plan with unnecessary "range checked for each record"
Submitted: 13 Aug 2013 20:52 Modified: 3 Oct 2013 13:38
Reporter: Igor Babaev Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S5 (Performance)
Version:5.6.13 OS:Any
Assigned to: Jørgen Løland CPU Architecture:Any

[13 Aug 2013 20:52] Igor Babaev
Description:
In MySQL 5.6.13 (and, probably, in all other releases, as well as in all releases of minor versions) we can observe extremely poor performance for queries like:
select * from t2 left join t1 on (t1.key1 < 3 or t1.key1 > 1020) and t1.key2 < t2.a;
For this query we would expect almost the same performance as for the query select * from t2 left join t1 on (t1.key1 < 3 or t1.key1 > 1020);
In fact the first query produces a much worse execution plan:
mysql> explain
    -> select * from t2 left join t1 on (t1.key1 < 3 or t1.key1 > 1020) and t1.key2 < t2.a;
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                                          |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------------+
|  1 | SIMPLE      | t2    | ALL   | NULL          | NULL | NULL    | NULL |   64 | NULL                                           |
|  1 | SIMPLE      | t1    | range | i2            | i1   | 4       | NULL |    6 | Range checked for each record (index map: 0x2) |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------------+

It's clear that "Range checked for each record" is not needed here.
One can check in the debugger that for each record the same range scan is chosen, and this is exactly the scan chosen for the second query:
mysql> explain
    -> select * from t2 left join t1 on (t1.key1 < 3 or t1.key1 > 1020);
+----+-------------+-------+-------+---------------+------+---------+------+------+----------------------------------------------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                                              |
+----+-------------+-------+-------+---------------+------+---------+------+------+----------------------------------------------------+
|  1 | SIMPLE      | t2    | ALL   | NULL          | NULL | NULL    | NULL |   64 | NULL                                               |
|  1 | SIMPLE      | t1    | range | i1            | i1   | 4       | NULL |    6 | Using where; Using join buffer (Block Nested Loop) |
+----+-------------+-------+-------+---------------+------+---------+------+------+----------------------------------------------------+

How to repeat:
The problem can be reproduced with the following test case:

create table t1( key1 int not null, INDEX i1(key1) );
insert into t1 values (1),(2),(3),(4),(5),(6),(7),(8);
insert into t1 select key1+8 from t1; 
insert into t1 select key1+16 from t1; 
insert into t1 select key1+32 from t1; 
insert into t1 select key1+64 from t1; 
insert into t1 select key1+128 from t1; 
insert into t1 select key1+256 from t1; 
insert into t1 select key1+512 from t1; 

alter table t1 add key2 int not null, add index i2(key2);
update t1 set key2=key1;
analyze table t1;

create table t2 (a int);
insert into t2 values (1),(2),(3),(4),(5),(6),(7),(8);
insert into t2 select a+16 from t2;
insert into t2 select a+32 from t2;
insert into t2 select a+64 from t2;

explain
select * from t2 left join t1 on (t1.key1 < 3 or t1.key1 > 1020);
select * from t2 left join t1 on (t1.key1 < 3 or t1.key1 > 1020);
explain
select * from t2 left join t1 on (t1.key1 < 3 or t1.key1 > 1020) and t1.key2 < t2.a;
select * from t2 left join t1 on (t1.key1 < 3 or t1.key1 > 1020) and t1.key2 < t2.a;

drop table t1,t2;
[14 Aug 2013 8:24] Umesh Shastry
Hello Igor,

Thank you for the bug report and the test case. 
Verified as described on recent 5.6.13.

Thanks,
Umesh
[14 Aug 2013 18:41] Sinisa Milivojevic
I must say that I am impressed with a quality of this bug report.

You must be definitely somebody very familiar with our code ???

Thank you very much !!!
[3 Oct 2013 13:38] Paul Dubois
Noted in 5.7.3 changelog.

Information was not transferred between two optimizer modules because
there were duplicate variables for the same information. This could
lead to suboptimal query execution plans and incorrect query results.