数据库内核月报

数据库内核月报 - 2016 / 12

MySQL · 捉虫动态 · 5.6中ORDER BY + LIMIT 错选执行计划

Author: 令猴

问题描述

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;
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+
| 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 |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+

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 |
+----+-------------+-------+-------+---------------+------+---------+------+------+------------------------------------------+

从SELECT语句中可以看出,同样的语句,使用同样的INDEX,但使用了FORCE INDEX之后选择的执行计划不一样。当然如果数据量大的话,实际的执行性能也会差别很大。使用RANGE scan显然要优于INDEX scan的全扫描。

另外此bug引发的另一个问题是,由于使用了LIMIT语句,导致选择的INDEX不是最优的INDEX。

问题分析:

使用如下命令打开Optimizer trace

SET OPTIMIZER_TRACE_MAX_MEM_SIZE=268435456(i.e. 256M);
SET optimizer_trace="enabled=on";

执行上面的查询语句,可以看到optimizer trace的输出结果如下,请注意里面重点部位的注释(以’//’开头部分):

"considered_execution_plans": [\
              {\
                "plan_prefix": [\
                ],\
                "table": "`t1`",\
                "best_access_path": {\
                  "considered_access_paths": [\
                    {\
                      "access_type": "range",\  
					  // 这里我们可以看到,优化器通过代价选择的最佳访问方式是RANGE scan
                      "rows": 3,\
                      "cost": 2.2146,\
                      "chosen": true\
                    }\
                  ]\
                },\
                "cost_for_plan": 2.2146,\
                "rows_for_plan": 3,\
                "chosen": true\
              }\
            ]\
但是接下来我们可以看到:
       "refine_plan": [\
              {\
                "table": "`t1`",\
				
                "access_type": "index_scan"\ //这里强制使用了INDEX scan
              }\
            ]\

这里显示的是optimizer在执行优化器的第四个阶段,PLAN REFINEMENT的时候,最后选择了INDEX scan。所以我们可以大致确定错误发生的地方。另外有问题的query带有LIMIT,因此基本可以确定问题发生在了make_join_select函数中。

make_join_select函数中有下面一段逻辑:

if (!tab->const_keys.is_clear_all() &&               // 有依赖于常量的索引条件表达式
                   i == join->const_tables &&        // 是第一个非常量表
                   (join->unit->select_limit_cnt <
                    tab->position->records_read) &&  
					// 有Limit条件且需要返回的行数比估计扫描的行数少
                   !(join->select_options & OPTION_FOUND_ROWS))  // 没有SQL_CALC_FOUND_ROWS
            recheck_reason= LOW_LIMIT;  // 这里MySQL开始对Limit语句进行优化
			...
// 检查是否有RANGE scan可以使用
if ((recheck_reason != DONT_RECHECK) &&
                sel->test_quick_select(thd, usable_keys,
                                       used_tables & ~tab->table->map,
                                       (join->select_options &
                                        OPTION_FOUND_ROWS ?
                                        HA_POS_ERROR :
                                        join->unit->select_limit_cnt),
                                       false,   // don't force quick range
                                       interesting_order) < 0)
            {
这里usable_keys是描述可以用来对ORDER BY列进行索引排序的可能的所有索引的MAP。上面的函数会查找这些可用的索引是否可以进行更高效RANGE
扫描。但是通过问题query的条件表达式,这里没有找到对应的RANGE扫描,所以最后的执行计划输出只是使用了一个COVERING index.

问题解决

解决方式是需要将原来已经选好的RANGE scan与用来进行排序的索引扫描代价进行比较,比较哪种扫描方式对于增加ORDER BY操作后的代价更低,进而选择一个代价最优的扫描方式。下面是一个相关的patch。

if (!tab->const_keys.is_clear_all() &&               // 有依赖于常量的索引条件表达式
                   i == join->const_tables &&        // 是第一个非常量表
                   (join->unit->select_limit_cnt <
                    tab->position->records_read) &&  // 有Limit条件且需要返回的行数比估计的扫描的行数少
                   !(join->select_options & OPTION_FOUND_ROWS))  // 没有SQL_CALC_FOUND_ROWS
            recheck_reason= LOW_LIMIT;  //这里MySQL会去对Limit语句进行优化
			...
+              if (recheck_reason != DONT_RECHECK)
               {
-                recheck_reason= DONT_RECHECK;
+                int best_key= -1;
+                ha_rows select_limit= join->unit->select_limit_cnt;
+
+                // 对所有可用的INDEX计算排序代价,选择一个代价最优的INDEX
				 // 注意:这里的usable_keys包含所有可用索引,而不只是原来版本中只包含可以用来排序的索引
+                test_if_cheaper_ordering(tab, join->order, tab->table,
+                                         usable_keys, -1, select_limit,
+                                         &best_key, &read_direction,
+                                         &select_limit);
				 // 如果没有找到任何可用的INDEX,那就默认使用原来的扫描方式
+                if (best_key < 0)
+                  recheck_reason= DONT_RECHECK; // No usable keys
+                else
+                {
+                  // 找到一个最优的INDEX,我们只需要设置可用的INDEX,接下来查看一下是否有RANGE scan即可
+                  usable_keys.clear_all();
+                  usable_keys.set_bit(best_key);
+                  interesting_order= (read_direction == -1 ? ORDER::ORDER_DESC :
+                                      ORDER::ORDER_ASC);
+                }
               }
             }
if ((recheck_reason != DONT_RECHECK) &&
                sel->test_quick_select(thd, usable_keys,
                                       used_tables & ~tab->table->map,
                                       (join->select_options &
                                        OPTION_FOUND_ROWS ?
                                        HA_POS_ERROR :
                                        join->unit->select_limit_cnt),
                                       false,   // don't force quick range
                                       interesting_order) < 0)
            {
			...

可以看到最终效果是:

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	4	Using index condition; Using filesort