Bug #78993 Optimizer use index scan instead of range scan by mistake
Submitted: 28 Oct 2015 3:15 Modified: 1 Feb 2016 15:54
Reporter: zhang yingqiang (OCA) Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S3 (Non-critical)
Version:5.6.16 5.6.26, 5.6.27 OS:Any
Assigned to: CPU Architecture:Any
Tags: Optimizer, regression

[28 Oct 2015 3:15] zhang yingqiang
Description:
We take the repeatiable case as an example:
    1st: the optimizer chose the index "iabc", and set the tab->quick
    2nd: the optimizer try to use ic for optimize "order by limit" in SQL_SELECT::test_quick_select
        in the function  SQL_SELECT::test_quick_select, optimizer clean the select->quick for index 'iabc'; but don't chose ic at last (do not generate the new quick). Here we lost select->quick for index 'iabc', and can not range scan iabc by range any more, we only can use index scan(in make_join_readinfo).
    

How to repeat:
create table t1(id int auto_increment primary key, a int, b int, c int, v varchar(1000), key iabc(a,b,c), key ic(c)) engine = innodb;

insert into t1 select null,null,null,null,null;
insert into t1 select null,null,null,null,null from t1;
insert into t1 select null,null,null,null,null from t1;
insert into t1 select null,null,null,null,null from t1;
insert into t1 select null,null,null,null,null from t1;
insert into t1 select null,null,null,null,null from t1;

update t1 set a=id/2, b=id/4, c=6-id/8, v=repeat('a',1000);

explain select id from t1 where a<3 and b in (1, 13) and c>=3 order by c desc limit 2;
explain select id from t1 force index (iabc) where a<3 and b in (1, 13) and c>=3 order by c desc limit 2;

drop table t1;

Suggested fix:
We should restore the quick, if we do not chang the chosen index in SQL_SELECT::test_quick_select.

Here is the patch:

diff --git a/sql/opt_range.cc b/sql/opt_range.cc
index c22a6f0..91799c7 100644
--- a/sql/opt_range.cc
+++ b/sql/opt_range.cc
@@ -2616,7 +2616,8 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use,
                      (ulong) keys_to_use.to_ulonglong(), (ulong) prev_tables,
                      (ulong) const_tables));
 
-  set_quick(NULL);
+  QUICK_SELECT_I *orig_quick= quick;
+  quick= NULL;
   needed_reg.clear_all();
   quick_keys.clear_all();
   if (keys_to_use.is_clear_all())
@@ -2943,11 +2944,16 @@ free_mem:
 
   DBUG_EXECUTE("info", print_quick(quick, &needed_reg););
 
+  int ret= records ? MY_TEST(quick) : -1;
+  if (ret == 0)
+    quick= orig_quick;
+  else
+    delete orig_quick;
   /*
     Assume that if the user is using 'limit' we will only need to scan
     limit rows if we are using a key
   */
-  DBUG_RETURN(records ? MY_TEST(quick) : -1);
+  DBUG_RETURN(ret);
 }
 
 /****************************************************************************
[28 Oct 2015 5:01] MySQL Verification Team
Hello zhang yingqian,

Thank you for the report and contribution.
Verified as described with 5.6.27 build.

Thanks,
Umesh
[28 Oct 2015 5:03] MySQL Verification Team
// only 5.6 seems to use index type

// 5.1.77

mysql> explain select id from t1 where a<3 and b in (1, 13) and c>=3 order by c desc limit 2;
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                                    |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
|  1 | SIMPLE      | t1    | range | iabc,ic       | iabc | 5       | NULL |    3 | Using where; Using index; Using filesort |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
1 row in set (0.00 sec)

mysql> explain select id from t1 force index (iabc) where a<3 and b in (1, 13) and c>=3 order by c desc limit 2;
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                                    |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
|  1 | SIMPLE      | t1    | range | iabc          | iabc | 5       | NULL |    3 | Using where; Using index; Using filesort |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
1 row in set (0.00 sec)

// 5.5.47 

mysql> explain select id from t1 where a<3 and b in (1, 13) and c>=3 order by c desc limit 2;
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                                    |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
|  1 | SIMPLE      | t1    | range | iabc,ic       | iabc | 5       | NULL |    3 | Using where; Using index; Using filesort |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
1 row in set (0.00 sec)

mysql> explain select id from t1 force index (iabc) where a<3 and b in (1, 13) and c>=3 order by c desc limit 2;
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                                    |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
|  1 | SIMPLE      | t1    | range | iabc          | iabc | 5       | NULL |    3 | Using where; Using index; Using filesort |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
1 row in set (0.00 sec)
[28 Oct 2015 5:04] MySQL Verification Team
// 5.6.27

mysql> explain select id from t1 where a<3 and b in (1, 13) and c>=3 order by c desc limit 2;
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                                    |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
|  1 | SIMPLE      | t1    | index | iabc,ic       | iabc | 15      | NULL |   32 | Using where; Using index; Using filesort |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
1 row in set (0.00 sec)

mysql> explain select id from t1 force index (iabc) where a<3 and b in (1, 13) and c>=3 order by c desc limit 2;
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                                    |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
|  1 | SIMPLE      | t1    | range | iabc          | iabc | 5       | NULL |    3 | Using where; Using index; Using filesort |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
1 row in set (0.00 sec)

// 5.7.9 

mysql> explain select id from t1 where a<3 and b in (1, 13) and c>=3 order by c desc limit 2;
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+------------------------------------------+
| id | select_type | table | partitions | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                    |
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+------------------------------------------+
|  1 | SIMPLE      | t1    | NULL       | range | iabc,ic       | iabc | 5       | NULL |    4 |    10.62 | Using where; Using index; Using filesort |
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+------------------------------------------+
1 row in set, 1 warning (0.01 sec)

mysql> explain select id from t1 force index (iabc) where a<3 and b in (1, 13) and c>=3 order by c desc limit 2;
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+------------------------------------------+
| id | select_type | table | partitions | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                    |
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+------------------------------------------+
|  1 | SIMPLE      | t1    | NULL       | range | iabc          | iabc | 5       | NULL |    4 |     6.67 | Using where; Using index; Using filesort |
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+------------------------------------------+
1 row in set, 1 warning (0.00 sec)

// 5.7.10

mysql> explain select id from t1 where a<3 and b in (1, 13) and c>=3 order by c desc limit 2;
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+------------------------------------------+
| id | select_type | table | partitions | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                    |
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+------------------------------------------+
|  1 | SIMPLE      | t1    | NULL       | range | iabc,ic       | iabc | 5       | NULL |    4 |    10.62 | Using where; Using index; Using filesort |
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+------------------------------------------+
1 row in set, 1 warning (0.00 sec)

mysql> explain select id from t1 force index (iabc) where a<3 and b in (1, 13) and c>=3 order by c desc limit 2;
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+------------------------------------------+
| id | select_type | table | partitions | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                    |
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+------------------------------------------+
|  1 | SIMPLE      | t1    | NULL       | range | iabc          | iabc | 5       | NULL |    4 |     6.67 | Using where; Using index; Using filesort |
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+------------------------------------------+
1 row in set, 1 warning (0.00 sec)
[28 Oct 2015 6:06] zhang yingqiang
This bug result in full index scan, it cost too much CPU and IO !!
I also check the test case in 5.7.8, there is no such problem.
[3 Nov 2015 14:06] qinglin zhang
fix for order by limt cause

Attachment: a.diff (application/octet-stream, text), 1.20 KiB.

[3 Nov 2015 14:16] qinglin zhang
just part of code, which we may calculate the cost by considering read plan before.

Attachment: a.diff (application/octet-stream, text), 1.25 KiB.

[1 Feb 2016 15:54] Paul DuBois
Noted in 5.7.6 changelog.

For queries that combine ORDER BY with LIMIT, the optimizer may
switch to an index that applies to the ORDER BY. In some cases, the 
decision to switch was based on a heuristic rather than on cost. The 
optimizer now uniformly makes the decision whether to switch on a
cost basis. This should result in better performanance when switching
would cause a query to read an entire index or a large part of it to
find qualifying rows.
[20 Aug 2017 9:24] WANG GUANGYOU
// 5.7.10

mysql> explain select id from t1 where a<3 and b in (1, 13) and c>=3 order by c desc limit 2;
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+------------------------------------------+
| id | select_type | table | partitions | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                    |
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+------------------------------------------+
|  1 | SIMPLE      | t1    | NULL       | range | iabc,ic       | iabc | 5       | NULL |    4 |    10.62 | Using where; Using index; Using filesort |
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+------------------------------------------+
1 row in set, 1 warning (0.00 sec)

this worked in 5.7.10 for it does not trigger LOW_LIMIT branch. 
Cheers!  I check the code, the Heuristic algorithm is moved in order by limit case .   We are deeply troubled in this bug at MeiTuanDianPing in MySQL5.6.