准备工作

创建两张表，t1和t2，表结构完全相同， t2有1000行记录，t1有100行，索引字段为a。

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)

驱动表与被驱动表

执行如下SQL：

select * from t1 straight_join t2 on (t1.a=t2.a);

straight_join表示让MySQL使用固定的连接方式执行查询，优化器只会按照我们指定的方式去join，这个语句的驱动表是t1，被驱动表是t2.

执行流程分析

Index Nested-Loop Join

通过explain可以看出，被驱动表t2使用了索引a，join过程中用上了这个索引，因此这个语句的执行流程是这样：

从表t1中读入一行数据R
从数据行R中，取出a字段到表t2里去查找
取出表t2中满足条件的行，跟R组成一行，作为结果集的一部分
重复执行步骤1到3，直到表t1的最后一行

上面这个过程就像循环嵌套查询一样，并且可以用上被驱动表的索引，所以我们称之为“Index Nested-Loop Join”，简称NLJ.

总结：

对驱动表t1做了全表扫描，这个过程需要扫描100行
而对于每一行R，根据字段a去表t2查找，走的是树搜索过程，由于我们构造的数据都是一一对应的，因此每次的搜索过程都只扫描一行，也就是总共扫描100行
所以整个流程总共扫描行数是200

不使用join的流程

如果不使用join，需要单表查，

执行select * from t1，查询出表t1所有的数据，这里有100行
循环遍历这100行数据
1. 从每一行R取出字段a的值$R.a
2. 执行select * from t2 where a=$R.a
3. 把返回的结果和R构成结果集的一行

缺点
这个查询过程中也是扫描了200行，但是总共执行了101条语句，比直接join多了100次交互，并且客户端还要自己拼接SQL语句和结果，不如直接join好用

怎么选择驱动表？

首先给出结论，小表作为驱动表。

在join语句执行过程中，驱动表是走全表扫描，而被驱动表是走树搜索，假设被驱动表的行数是M，每次在被驱动表查一行数据，要先搜索索引a，再搜索主键索引，每次搜索一棵树近似复杂度是以2为底的M的对数，记为log2M，索引在被驱动表上查询一行的时间复杂度是2*log2M（因为如果不是覆盖索引，需要回表一次）。

假设驱动表的行数是N，执行过程就要扫描驱动表N行，然后对于每一行，到被驱动表上匹配一次，因此整个执行过程，近似复杂度是N + N2log2M，显然N对扫描行数的影响更大，因此应该让小表来做驱动表。

Simple Nested-Loop Join

当被驱动表连接的字段使用的是否非索引字段时，比如：

select * from t1 straught_join t2 on(t1.a = t2.b);

t2的字段b没有索引，因此也需要全表扫描，这个SQL就需要扫描t2 100次，共扫描100 1000 = 10万行。这样如果表的数据量大的话，这个算法就太笨重了。
*MySQL并没有使用这个Simple Nested-Loop Join算法，而是使用了另一个叫做“Block Nested-Loop Join”的算法。简称BNL。

Block Nested-Loop Join

如果被驱动表上没有可用的索引，就会将驱动表的数据放入线程内存join_buffer中
如果join_buffer不够大那么驱动表会被分块读入到内存然后与被驱动表的每行比较
通过join_buffer_size控制join_buffer，默认值为256K

怎么选择驱动表
当join_buffer够用时，都一样
当join_buffer不够时（常见），使用小表当驱动表

总结

如果可以使用被驱动表的索引，join语句还是有其优势的
不能使用被驱动表的索引，只能使用Block Nested-Loop Join算法，这样的语句尽量不要使用
在使用join的时候，应该让小表做驱动表

问题

如果被驱动表是一个大表，并且是一个冷数据表，除了查询过程中可能会导致IO压力大外，还会对这个MySQL服务有什么更严重的影响吗？
答案：可参考大数据量查询对MySQL的影响
如果驱动表分段，那么被驱动表就被多次读，而被驱动表又是大表，循环读取的间隔肯定得超1秒，这就会导致上篇文章提到的：“数据页在LRU_old的存在时间超过1秒，就会移到young区”。最终结果就是把大部分热点数据都淘汰了，导致“Buffer pool hit rate”命中率极低，其他请求需要读磁盘，因此系统响应变慢，大部分请求阻塞。

join底层是如何执行的，该如何优化？