[大数据]MySQL Join原理

一、背景

Join方式连接多个表，本质就是各个表之间数据的循环匹配。MySQL 5.5版本之前，MySQL只支持一种表间关联方式，就是嵌套循环(Nexted Loop Join)。如果关联表的数据量很大，则Join关联的执行时间会非常长。在MySQL 5.5以后的版本中，MySQL通过引入BNLJ算法来优化嵌套执行。

二、驱动表和被驱动表

驱动表就是主表，被驱动表就是从表、非驱动表。

1. 内连接情景

SELECT * FROM A JOIN B ON ...

A一定是驱动表？不一定，优化器会根据你查询语句做优化，决定先查哪张表。先查询的那张表就是驱动表，反之是被驱动表。通过EXPLAIN关键字可以查看。

2. 外连接情景

SELECT * FROM A LEFT JOIN B ON ...
或
SELECT * FROM A RIGHT JOIN B ON ...

通常A是驱动表，B是被驱动表，但也存在特殊情况会被优化器优化，比如SQL可能被优化为内连接，使得B为驱动表，A为被驱动表。

三、连接算法

1. Simple Nest-Loop Join(简单嵌套循环连接)

假设有A,B两张表，无索引，A为驱动表，B为非驱动表，从表A中取出一条数据a1，遍历B表，将匹配的数据放到result，以此类推，驱动表A中每一条记录与表B的记录进行匹配，如下图：

从上图中可以看到，假设A表数据100条，表B数据1000条，B表读取次数就是B*A=10万次，这个效率是非常低的，具体开销如下：

2. Index Nested-Loop Join(索引嵌套)

Index Nested-Loop Join 优化的思路主要是为了减少内层数据的匹配次数，所以要求被驱动表上必须有索引才行。通过驱动表匹配条件直接与被驱动表索引进行匹配，避免和被驱动表每条记录去进行比较，这样就减少了对被驱动表的匹配次数。

驱动表中每条记录通过被驱动表的索引进行访问，因为索引查询的成本是比较固定的，故MySQL优化器会倾向于使用记录数少的表作为驱动表。

如果被驱动表加索引，效率是非常高的，但如果索引不是主键索引，还得进行一次回表查询。相比，被驱动表的索引是主键索引，效率会更高。

3. Block Nested-Loop Join(块嵌套循环连接)

如果存在索引，那么会使用Index的方式进行Join，如果Join的列没有索引，被驱动表要扫描的次数太多了。每次访问被驱动表，其表中的记录都会被加载到内存中，然后再从驱动表中取一条与其匹配，匹配结束后清除内存，然后再从驱动表中加载一条记录，再把被驱动表的记录加载到内存匹配，这样周而复始，大大增加了IO次数。为了减少被驱动表的IO次数，就出现了Block Nested-Loop Join的方式。
Block Nested-Loop Join方式不再是逐条获取驱动表的数据，而是一块一块的获取，引入了 join buffer 缓冲区，将驱动表 join 相关的部分数据列(大小受 join buffer 的限制)缓冲到 join buffer 中，然后全表扫描被驱动表，被驱动表的每一条记录一次性和 join buffer 中的所有驱动表记录进行匹配(内存中操作)，将简单嵌套循环中的多次比较合并成一次，降低了被驱动表的访问频率。

注意：
????这里缓存的不只是关联表的列，SELECT后面的列也会缓存起来。
????在一个有N个Join关联的SQL中会分配N-1个 join buffer 。所以查询时尽量减少不必要的字段，可以让 join buffer 中存放更多的列。

参数设置：

• block_nest_loop

通过show variables like '%optimizer_switch%'查看block_nested_loop状态。默认是开启的。

show variables like '%optimizer_switch%'
--结果中含有 block_nested_loop=on

• join_buffer_size
  驱动表能不能一次加载完，要看 join buffer 能不能存储所有的数据，默认情况下 join_buffer_size = 256k。可通过show variables like '%join_buffer%'查询 join buffer 大小。
  
  join_buffer_size的最大值在32位系统可以申请4G，而在64位系统下可以申请大于4G的 join buffer 空间（64位Windows除外，其最大值会被截断为4G并发出警告）。

四、小结

1、整体效率比较：INLJ > BNLJ > SNLJ
2、永远用小结果集驱动大结果集即小表驱动大表(其本质就是减少驱动表循环的数据数量)，这里的大小表衡量标准是 表行数 * 每行大小
3、为被驱动表匹配的条件增加索引(减少被驱动表的循环匹配次数)
4、增大 join buffer size 的大小(一次缓存的数据越多，那么被驱动表的扫描次数就越少)
5、减少驱动表不必要的字段查询(字段越少，join buffer 所缓存的数据就越多)

五、Hash Join

从MySQL 8.0.20 版本开始将废弃BNLJ，因为从MySQL 8.018 版本开始加入了 hash join ，默认都会使用 hash join 。

Nest Loop :
????对于被连接的数据子集较小的情况是较好的选择。
Hash Join :
Hash Join是做大数据集连接时的常用方式，优化器使用两个表中较小的表利用 Join Key 在内存中建立 散列表 ，然后扫描较大的表探测散列表，找出与 Hash表匹配的行。

• 这种方式使用于较小的表完全可以放在内存中的情况，这样总成本就是访问两个表的成本之和。
• 在表很大的情况下并不能完全放在内存，这时优化器会将它分割成 若干个不同的分区 ，不能放入内存的部分就把该分区写入磁盘的临时段，此时要求有较大的临时段从而尽量提高 I/O 的性能。
• 它能够很好的工作于没有索引的大表和并行查询的环境中，并提供最好的性能。大多数人都说它是Join的重型升降机。Hash Join 只能应用于等值连接，这是由Hash的特点决定的。