join语句优化

示例表

create table t1(id int primary key, a int, b int, index(a));  
create table t2 like t1;  
drop procedure idata;  
delimiter ;;  
create procedure idata()
begin
    declare i int;
    set i=1;
    while(i<=1000) do
        insert into t1 values(i, 1001-i, i);
        set i=i+1;
    end while;  

    set i=1;
    while(i<=1000000)do
        insert into t2 values(i, i, i);
        set i=i+1;
    end while;
end;;
delimiter ;
call idata();
-- 表t1插入1000行数据，字段a是逆序的；t2中插入了100万行数据。

Multi-Range Read(MRR)优化

MRR优化的主要目的是尽量使用顺序读盘。

回表是指，InnoDB在普通索引a上查到主键id的值后，再根据一个个主键id的值到主键索引上去查整行数据的过程。

主键索引是一棵B+树，在这棵树上，每次只能根据一个主键id查到一行数据。因此回表是一行行搜索主键索引的。

select * from t1 where a>=1 and a<=100;

如果随着a的值递增顺序查询的话，id的值就变成随机的，那么就会出现随机访问，性能相对较差。虽然“按行查”这个机制不能改，但是调整查询的顺序，还是能够加速的。

大多数的数据都是按照主键递增顺序插入得到的，可以认为，按照主键递增顺序查询的话，对磁盘的读比较接近顺序读，能够提升性能。MRR优化的设计思路。

1. 根据索引a，定位到满足条件的记录，将id值放入read_rnd_buffer中；
2. 将read_ran_buffer中的id进行递增排序；
3. 排序后的id数组，依次到主键id索引中查记录，并作为结果返回。

read_rnd_buffer的大小是由read_rnd_buffer_size参数控制的。如果步骤1中，read_rnd_buffer放满了，就会先执行完步骤2和3，然后清空read_rnd_buffer。之后继续找索引a的下个记录，并继续循环。

如果想要稳定的使用MRR优化，需要设置set optimizer_switch=”mrr_cost_based=off”。(优化器策略，判断消耗的时候，会更倾向于不使用MRR)

id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	simple	t2	null	range	a	a	5	null	101	100.00	Using index condition;Using MRR

explain结果中，Extra字段的Using MRR，表示用上了MRR优化。而且由于在read_rnd_buffer中按照id做了排序，所以最后得到的结果集也是按照主键id递增的。

MRR能够提升性能的核心在于，这条查询语句在索引a上做的是一个范围查询(多值查询)，可以得到足够多的主键id。这样通过排序以后，再去主键索引查数据，才能体现出“顺序性”的优势。(注意MRR优化是按照主键id排序，如果语句使用了索引a，结果还要对a排序，就不使用MRR优化了，否则回表完还要增加额外的排序过程，得不偿失)

Batched Key Access

MySQL在5.6版本后引入Batched Key Access(BKA)算法。BKA算法是对NLJ(Index Nested-Loop Join)算法的优化。

NLJ算法执行的逻辑是：从驱动表t1，一行行的取出a的值，再到被驱动表t2去做join。对于表t2来说，每次都是匹配一个值。MRR的优势就用不上了。

从表t1里 一次性的多拿些行出来，先放到一个临时内存-join_buffer中。join_buffer在BNL算法里的作用，是暂存驱动表的数据，在NLJ算法中并没有用，可以复用join_buffer到BKA算法中。

如果要使用BKA优化算法，需要先设置set optimizer_switch=’mrr=on,mrr_cost_based=off,batched_key_access=on’。（BKA算法的优化依赖于MRR）

BNL算法的性能问题

使用Block Nested-Loop Join(BNL)算法时，可能会对被驱动表做多次扫描。如果被驱动表是一个大的冷数据表，会导致IO压力大。

InnoDB对Buffer Pool的LRU算法做了优化：第一次从磁盘读入内存的数据页，会先放在old区域，如果1秒之后这个数据页就不再被访问了，就不会被移动到LRU链表头部，这样对Buffer Pool的命中率影响不大。

但是如果一个使用BNL算法的join语句，多次扫描一个冷表，而且这个语句执行时间超过1秒，就会在再次扫描冷表的时候，把冷表的数据页移到LRU链表头部。(冷表的数据量小于整个Buffer Pool的3/8，能够完全放入old区域)。如果冷表很大，业务正常访问的数据页，没有机会进入young区域。

由于优化机制的存在，一个正常访问的数据页，要进入young区域，需要隔一秒后再次被访问到。但是，由于join语句在循环读磁盘和淘汰内存页，进入old区域的数据页，很可能在1秒之内就被淘汰了。这样会导致这个MySQL实例的Buffer Pool在这段时间内，young区域的数据页没有被合理的淘汰掉。

以上两种情况都会影响Buffer Pool的正常运作。

大表join操作虽然对IO有影响，但是在语句执行结束后，对IO的影响也就结束了。但是，对Buffer Pool的影响就是持续性的，需要依靠后续的查询请求慢慢恢复内存命中率。

解决方案：增大join_buffer_size的值，减少对被驱动表的扫描次数。

BNL算法对系统的影响包括三个方面：

1. 可能会多次扫描被驱动表，占用磁盘IO资源；
2. 判断join条件需要执行M*N次对别(M、N分别是两张表的行数)，如果是大表就会占用非常多的CPU资源；
3. 可能会导致Buffer Pool的热数据被淘汰，影响内存命中率。

执行语句之前，需要通过理论分析和查看explain结果的方式，确认是否要使用BNL算法。如果确认优化器会使用BNL算法，就需要做优化。优化的常见做法：给被驱动表的join字段加上索引，把BNL算法转成BKA算法。

BNL转BKA

一些情况下，可以直接在被驱动表上建索引，这时就可以直接转成BKA算法了。

select * from t1 join t2 on(t1.b=t2.b) where t2.b>=1 and t2.b<=2000;

t2表中插入了100万行数据，但是经过where条件过滤后，需要参与join的只有2000行数据。这条语句同时是一个低频的SQL语句，为这个语句在表t2的字段b上创建一个索引很浪费。

使用BNL算法来join的执行流程：

1. 把表t1的所有字段取出来，存入join_buffer中。这个表只有1000行，join_buffer_size默认值是256k，可以完全存入。
2. 扫描表t2，取出每一行数据跟join_buffer中的数据进行对比，
   • 如果不满足t1.b=t2.b，则跳过；
   • 如果满足t1.b=t2.b，再判断其他条件，是否满足t2.b处于[1,2000]的条件，如果是，就作为结果集的一部分返回，否则跳过。

对于表t2的每一行，判断join是否满足的时候，都需要遍历join_buffer中的所有行。因此判断等值条件的次数是1000*100万=10亿次，这个判断的工作量很大。

id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	simple	t1	null	all	null	null	null	null	1000	100.00	Using where
1	simple	t2	null	all	null	null	null	null	998222	1.11	Using where;Using join buffer(Block Nested Loop)

explain结果中Extra字段显示使用了BNL算法。但是执行时间超过一分钟。

在表t2的字段b上创建索引会浪费资源，但是不创建索引的话语句等值条件要判断10亿次。

解决方案-临时表：

1. 把表t2中满足条件的数据放在临时表tmp_t中；
2. 为了让join使用BKA算法，给临时表tmp_t的字段b加上索引；
3. 让表t1和tmp_t做join操作。

create temporary table temp_t(id int primary key, a int, b int, index(b)) engine=innodb;  
insert into temp_t select * from t2 where b>=1 and b<=2000;  
select * from t1 join temp_t on (t1.b=temp_t.b);

执行时间大幅下降到不到1秒。

1. 执行insert语句构造temp_t表并插入数据的过程中，对表t2做了全表扫描，这里扫描的行数是100万。
2. 之后的join语句，扫描表t1，这里的扫描行数是1000；join比较过程中，做了1000次带索引的查询。(优化前需要做10亿次条件判断)

总体来看，不论是在原表上加索引，还是用有索引的临时表，思路都是让join语句能够用上被驱动表上的索引，来触发BKA算法，提升查询性能。

扩展-hash join

如果join_buffer里面维护的不是一个无序数组，而是一个哈希表的话，就不用10亿次判断，而是100万次hash查找(表t2中100w条数据)。

1. select * from t1;取得表t1的全部1000行数据，在业务端存入一个hash结构。
2. select * from t2 where b>=1 and b<=2000;获取表t2满足条件的2000行数据。
3. 把这2000行数据，一行一行的取到业务端，到hash结构的数据表中寻找匹配的数据。满足匹配的条件的整行数据，就作为结果集的一行。

理论上，这个过程会比临时表方案的执行速度还要快一些。

总结

1. BKA优化是MySQL已经内置支持的，建议默认使用。
2. BNL算法效率低，建议尽量转成BKA算法。优化的方向就是给被驱动表的关联字段加上索引。
3. 基于临时表的改进方案，对于能够提前过滤出小数据的join语句来说，效果还是很好的。
4. MySQL目前的版本还不支持hash join，但是可以配合应用端模拟出来，理论上效果好于临时表的方案。

扩展-三表join

CREATE TABLE `t1` (
 `id` int(11) NOT NULL,
 `a` int(11) DEFAULT NULL,
 `b` int(11) DEFAULT NULL,
 `c` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

create table t2 like t1;
create table t3 like t2;
insert into ... //初始化三张表的数据


select * from t1 join t2 on(t1.a=t2.a) join t3 on (t2.b=t3.b) where t1.c>=X and t2.c>=Y and t3.c>=Z;

第一原则是要尽量使用BKA算法。使用BKA算法的时候，并不是“先计算两个表join的结果，再跟第三个表join”，而是直接嵌套查询。

具体实现是：在t1.c>=X、t2.c>=Y、t3.c>=Z这三个条件里，选择一个经过过滤以后，数据最少的那个表，作为第一个驱动表。有两种情况。

第一种情况，如果选出来是表t1或者t3，那剩下的部分就固定了。

1. 如果驱动表是t1，则连接顺序是t1->t2->t3，要在被驱动表字段创建上索引，也就是t2.a和t3.b上创建索引；
2. 如果驱动表是t3，则连接顺序是t3->t2->t1，需要在t2.b和t1.a上创建索引。

同时需要再第一个驱动表的字段c上创建索引。

第二种情况，如果选出来的第一个驱动表是表t2，则需要评估另外两个条件的过滤效果。

整体的思路就是，尽量让每一次参与join的驱动表的数据集，越小越好，这样驱动表就会越小。