MySQL Join工作原理
CREATE TABLE `t2` (
`id` int(11) NOT NULL,
`a` int(11) DEFAULT NULL,
`b` int(11) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `a` (`a`)
) ENGINE=InnoDB;
drop procedure idata;
delimiter ;;
create procedure idata()
begin
declare i int;
set i=1;
while(i<=1000)do
insert into t2 values(i, i, i);
set i=i+1;
end while;
end;;
delimiter ;
call idata();
create table t1 like t2;
insert into t1 (select * from t2 where id<=100)
Index Nested-Loop Join
select * from t1 straight_join t2 on t1.a=t2.a;
这里使用straight_join，如果我们直接使用join，MySQL优化器可能选t1或t2作为驱动表，但是使用straight_join，会强制t1作为驱动表，t2是被驱动表。
通过explain，我们可以看出，在join的过程中用上了被驱动表t2的索引a，整个语句的执行流程如下：
- 从表t1中读取一行
- 从数据行R中，取出a字段去表t2里面去查找
- 取出表t2中满足条件的行，跟R组成一行，作为结果集的一部分
- 重复执行步骤1-3，直到表t1的末尾循环结束
- 驱动表是全表扫描，因此需要扫描100行
- 对于每一行R，根据a字段去表t2查找，走的是树搜锁过程，由于我们构造的数据一一对应，因此每次只扫描1行，总共也是100行
- 整个执行流程，扫描了200行
对于上面的查询来说，如果不用join，会多100次交互，不如join效果好。
如何选择驱动表？
先说结论，一定要让小表做驱动表。
假设被驱动表的行数为M，每次在被驱动表上查询的时候，先搜索索引a，再搜索主键索引，每棵索引树的搜索复杂度可以记为以2为底的M对数，记为log2(M)，由于需要搜索两棵索引树，因此被驱动表上的复杂度为2*log2(M)。
假设驱动表的行数为N，每执行过程中要扫描N行，对于我们构造的表每一行到被驱动表上只匹配一次，因此整个执行的复杂度=N + N * 2 * log2(M)。
可以看出N的大小对扫描行数影响更大，因此需要让小表做驱动表。
Block Nested-Loop Join
Index Nested-Loop Join是在被驱动表有索引的情况下，如果被驱动表上没有可用的索引，算法的流程如下：
- 将表t1的数据读入线程内存join_buffer中，由于这里是select *，因此是把整个表t1放入内存
- 扫描t2，把表t2中的每一行取出来，跟join_buffer中的数据做对比，满足join条件的会作为结果集的一部分进行返回
explain select * from t1 straight_join t2 on t1.a=t2.b;
在整个过程对表t1和t2做了一次全表扫描，因此扫描行数为1100行，由于join_buffer是无序的数组，因此对于表t2中的每一行，都要做100次判断，因此在内存中的判断次数是100*1000 = 10w次，但由于是在内存中进行，速度上还可以接受。
假设小表的行数为N，大表的行数为M，所以总扫描行数是M+N，总判断次数是N*M，因此这种情况下，大表和小表哪个做驱动表都是一样的耗时。
join_buffer的大小是由join_buffer_size决定，默认值是256K。
show global variables like 'join_buffer_size';
如果驱动表过大，join_buffer无法放下的话，就需要分段存放，执行过程如下：
- 扫描t1，顺序读取数据放入join_buffer中，如果join_buffer满了，进行第2步
- 扫描t2，把t2中的每一行取出来，跟join_buffer中的数据做对比，满足join条件的作为结果集的一部分返回
- 清空join_buffer
- 继续进行1-2步，直到所有数据取数完毕
假设驱动表的行数为N，需要K次可以完成，N越大，K越多，假设K= µ * N，µ的取值范围是(0,1)，因此该算法执行过程中：
- 扫描行数是N + µ * N * M
- 内存判断N*M次
在上述扫描行数，µ是影响行数的关键因素，这个值越小越好，在N固定的情况下，join_buffer_size越大，一次放入的行越多，分成的段数越少，对被驱动表的扫描行数也越少，如果join很慢，可以适当考虑改大join_buffer_size。
BNL算法问题
假设被驱动表是个很大的数据表，将会导致以下问题：
- IO压力大
- 降低内存命中率
如果多次扫描大的被驱动表，由于我们的join语句在不停地循环读磁盘和淘汰数据页，进入old区域的数据页很可能在1s之内被淘汰，此时业务正常访问的数据页也会被淘汰，没有机会进入young区域，因此会导致young区域的数据页没办法合理的进行淘汰。
因此大表join在语句结束以后，对IO的影响结束，但是对于Buffer Pool的影响就是持续性的，需要依靠后续的查询请求慢慢恢复内存命中率。
如何使用join？
- 如果可以使用Index Nested-Loop Join算法（用上被驱动表上的索引）其实没有问题
- 如果使用Block Nested-Loop Join算法，尽量不要对大表进行join，这样可能会导致扫描行数过多，占用大量系统资源
- 在join的时候尽量选择小表做驱动表
- 在判断哪个表是小表的时候应该是按照两个表各自的条件过滤，过滤完成以后，计算参与join的各个字段的总数据量，数据量小的那个就是小表