1、驱动表和被驱动表

SQL语句：select * from t1 straight_join t2 on (t1.a=t2.a)，其中t1、t2结构相同，两表皆有主键id、字段a和字段b。执行过程中首先会从表t1中取一行R，从R中取得字段a再到表t2中取查找，取出满足条件的行，跟R组成一行，作为结果集返回。因此，表t1称为驱动表，表t2称为被驱动表。

2、Index Nested-Loop Join

以1中SQL语句为例，如果t2.a上建了索引，那就是Index Nested-Loop Join（简称NLJ），因为在表t2查找满足条件的a时，可以使用索引快速定位。

假设驱动表的行数为N，被驱动表的行数为M，对于驱动表中的每一行，都要去被驱动表中先在a的索引树上查找（复杂度近似logM），再去主键索引上查找（复杂度近似logM），因此整个语句执行下来，复杂度近似为N+N2logM。很明显，N对复杂度的影响较大，因此选择驱动表的时候，要选择小表作驱动表（这里的前提是被驱动表可以用上索引）。

3、Block Nested-Loop Join

当被驱动表不能用上索引的时候，MySQL将使用这种方式进行join操作。这种方式扫描行数过多，会占用大量系统资源，不推荐使用。具体执行过程：
①将整个驱动表t1读入线程内存join_buffer中，如果一次放不下，将分成几部分依次放入；
②扫描被驱动表t2，把t2的每一行取出来，与join_buffer中的数据作对比，满足join条件的两个行进行组合，作为结果集的一部分返回。

还是假设驱动表的行数为N，被驱动表的行数为M。首先，将驱动表分批读入join_buffer中（假设分了A次读入），扫描驱动表行数为N，被驱动表扫描的总行数为aM，总扫描行数为N+AM，注意这里的A并不是常数，N越大，A就越大，可以设A=λN, λ∈(0, 1)，因此总扫描行数为**N+λNM**，总比较次数为NM。由此可以看出，λ对扫描行数的影响很大，如果一次就把驱动表都放入了join_buffer中，那么总扫描行数只有N+M，所以适当地把join_buffer_size改大一点，会加快join语句。尽管这样，这种方式扫描的行数仍然过多，因此不推荐使用。

4、什么是小表？

两个表按照各自的条件过滤之后，计算参与join的各字段的总数据量，数据量较小的那个表就是小表，应该作为驱动表。参与join的各字段总数据指的是驱动表中要放入join_buffer的数据，包括要参与join比较的字段和要查询的字段，比如select t1.b, t2.* from t1 straight_join t2 on (t1.b=t2.b) where t2.id<=100，只需要将t1的b字段放入join_buffer中。

5、join优化（针对NLJ）——Batched Key Access

首先介绍 Multi-Range Read( MRR )优化
这个优化的主要目的是在做范围查询时，尽量使用顺序读盘。因为大多数的数据都是按照主键递增顺序插入得到的，那么如果按照主键递增的顺序查询的话，对磁盘的读会比较接近顺序读，可以提升读性能。假设表t有主键id和字段a，a上有索引，执行语句select * from t where a >=1 and a <=100，在a索引树上，会先把a条件范围内所有的主键id都取出来，放入read_md_buffer中，然后在read_md_buffer中对主键id进行递增排序，最后再拿着主键id依次到主键索引中查询记录。

基于MRR实现的Batched Key Access算法( BKA )
原始的NLJ算法（以2为例）是从驱动表t1中一行行的取出a的值，再到被驱动表t2去做join，每次只是匹配一个值。而MRR是针对范围查询的，所以Batched Key Access算法就索性一次性从表t1中取一部分a出来，然后利用MRR算法，将表t2中索引a对应的主键id都取出来进行排序，然后进行后续操作。
操作步骤：
①取出表t1中所有的a都取出来放到join_buffer中，如果放不下则分批次进行；
②由于t1.a=t2.a，就将表t2中这些a对应的主键id都取出来放到read_md_buffer中对主键id进行递增排序；
③拿着排好序的主键id依次到主键索引中查询记录，然后作两个表的记录作拼接，返回给客户端。

使用Batched Key Access算法，需要先设置：set optimizer_switch=‘mrr=on,mrr_cost_based=off,batch_key_access=on’;

6、join优化（针对BNL）——BNL转BKA

某些情况下，我们可以直接在被驱动表上建索引，这样就变成了BKA算法。但是也有不适合直接在原表建索引的情况，比如如果经SQL语句条件过滤剩余的满足条件的行并不多，同时这又是一条低频的SQL语句，那么为这个语句在表t2上建索引就很浪费了。因此，可以考虑使用临时表。假如有SQL语句：select * from t1 join t2 on (t1.b=t2.b) where t2.b>=1 and t2.b<=1000，首先将被驱动表t2中经条件过滤后的数据放到临时表tmp_t中，然后给临时表tmp_t的字段b加上索引，再让表t1和临时表tmp_t做join操作，此时使用的是BKA算法。

对应的SQL语句为：
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<=1000;
select * from t1 join temp_t on (t1.b=temp_t.b);

小结：从join的两种优化方式来看，要想提升join语句的执行性能，都是要尽量在被驱动表上使用到索引。

7、join优化——不用join

不用join意思是，将join语句拆开，在业务端手动实现join的功能。
操作步骤：
①select * from t1; 将取得的所有行数据存入业务端的Hash表中；
②select * from t2 where b>=1 and b<=1000; 获取表t2中满足条件的1000行数据；
③把②中获取的1000行数据一行一行地取到业务端的HashMap中寻找匹配的数据(t1.b=t2.b)，满足条件的就拼接作为结果返回。