1.概述

MySQL的JOIN原理是基于索引和算法的。在执行JOIN查询时，MySQL会根据连接字段上的索引来查找匹配的记录。

这种算法在链接查询的时候，驱动表会根据关联字段的索引进行查找，当在索引上找到了符合的值，再回表进行查询，也就是只有当匹配到索引以后才会进行回表。

在进行JOIN查询时，MySQL还采用了一些优化策略来提高查询性能，例如使用嵌套循环连接算法（Nested-Loop Join）和索引优化技术。

1 2	嵌套循环连接算法按照指定的连接方式执行查询，不会自己选择驱动表。当连接字段上有索引时，MySQL会使用索引来加速查找过程

2.表结构定义

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)

可以看到，这两个表都有一个主键索引 id 和一个索引 a，字段 b 上无索引。存储过程 idata() 在表 t1 里插入的是 100 行数据,往表 t2 里插入了 1000 行数据

3.Index Nested-Loop Join

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

为了便于分析执行过程中的性能问题，我改用straight_join让 MySQL 使用固定的连接方式执行查询，这样优化器只会按照我们指定的方式去 join。在这个语句里，t1 是驱动表，t2 是被驱动表

如果直接使用 join 语句，MySQL 优化器可能会选择表 t1 或 t2 作为驱动表，这样会影响我们分析 SQL 语句的执行过程

INL算法步骤为先遍历表 t1，然后根据从表 t1 中取出的每行数据中的 a 值，去表 t2 中查找满足条件的记录。在形式上，这个过程就跟我们写程序时的嵌套查询类似，并且可以用上被驱动表的索引

查询复杂度

在INL算法程中，驱动表是走全表扫描，而被驱动表是走树搜索。

假设被驱动表的行数是 M。每次在被驱动表查一行数据，要先搜索索引 a，再搜索主键索引。每次搜索一棵树近似复杂度是以 2 为底的 M 的对数，
记为 $\log_2 M$ ，所以在被驱动表上查一行的时间复杂度是 $2*\log_2 M$ 。

假设驱动表的行数是 N，执行过程就要扫描驱动表 N 行，然后对于每一行，到被驱动表上匹配一次。

因此整个执行过程，近似复杂度是 $N+N*2*\log_2 M$

4.Simple Nested-Loop Join

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

若把SQL 语句改成这样，
由于表 t2 的字段 b 上没有索引，因此再用上图的执行流程时，每次到 t2 去匹配的时候，就要做一次全表扫描。
复杂度是 M * N。对应示例这个 SQL 请求就要扫描表 t2 多达 100 次，总共扫描100*1000=10w 行

MySQL 没有使用 Simple Nested-Loop Join 算法，而是使用了另一个叫作 Block Nested-Loop Join的算法，简称 BNL

5. Block Nested-Loop Join

join_buffer是一个用于存储连接操作（join）中临时数据的缓冲区。当执行连接操作时，MySQL将从连接的表中读取数据，并临时存储在join_buffer中，以便执行连接操作的计算和比较

当没有索引时才会直接使用 BNL

1. 算法大致流程如下：

把表 t1 的数据读入线程内存 join_buffer 中，由于我们这个语句中写的是select *，因此是把整个表 t1 放入了内存
扫描表 t2，把表 t2 中的每一行取出来，跟 join_buffer 中的数据做对比，满足 JOIN 条件的，作为结果集的一部分返回

2. 复杂度分析：

在这个过程中，对表 t1 和 t2 都做了一次全表扫描，因此总的扫描行数是 1100。由于 join_buffer 是以无序数组的方式组织的，因此对表 t2 中的每一行，都要做 100 次判断，总共需要在内存中做的判断次数是：100*1000=10 万次

join_buffer 的大小是由参数 join_buffer_size 设定的，默认值是 256k。
如果放不下表 t1 的所有数据话，策略很简单，就是分块放

假设，驱动表的数据行数是 N，需要分 K 段才能完成算法流程，被驱动表的数据行数是 M。

注意，这里的 K 不是常数，N 越大 K 就会越大，因此把 K 表示为λ*N，显然λ的取值范围是 (0,1)。

所以，在这个算法的执行过程中：

扫描行数是 N+λNM
内存判断 N*M 次

3. SNL与BNL对比

SNL/BNL 算法对系统的影响主要包括三个方面

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

6. Batched Key Access

MySQL 在 5.6 版本后开始引入的 Batched KEY Access(BKA) 算法。这个 BKA 算法，其实就是结合了BNL的 join buffer 和索引使用

对于多表join语句，当MySQL使用索引访问第二个join表的时候，使用一个join buffer来收集第一个操作对象生成的相关列值。BKA构建好key后，批量传给引擎层做索引查找。key是通过MRR接口提交给引擎的. 这样，MRR使得查询更有效率。

大致的过程如下:

BKA使用join buffer保存由join的第一个操作产生的符合条件的数据。
然后BKA算法构建key来访问被连接的表，并批量使用MRR接口提交keys到数据库存储引擎去查找。
提交keys之后，MRR使用最佳的方式来获取行并反馈给BKA

BKA使用join buffer size来确定buffer的大小，buffer越大，访问被join的表/内部表就越顺序。

官方文档

BNL和BKA,MRR的关系

BNL和BKA都是批量的提交一部分结果集给下一个被join的表(标记为T)，从而减少访问表T的次数，那么它们有什么区别呢？BNL和BKA的思想是类似的,详情见:《nest-loop-join官方手册》

BNL比BKA出现的早，BKA直到5.6才出现，而BNL至少在5.1里面就存在。
BNL主要用于当被join的表上无索引，Join buffering can be used when the join is of type ALL or index (in other words, when no possible keys can be used, and a full
scan is done, of either the data or index rows, respectively)
BKA主要是指在被join表上有索引可以利用，那么就在行提交给被join的表之前，对这些行按照索引字段进行排序，因此减少了随机IO，排序这才是两者最大的区别，但是如果被join的表没用索引呢？那就使用BNL了。
BKA实现的过程中就是通过传递keys给MRR接口，本质上还是在MRR里面实现，下面这幅图则展示了它们之间的关系:

7.Hash Join

Mysql 8.0 之后引入了Hash join
用于没有索引的时候，对驱动表进行hash操作。这样只用循环被驱动表一次即可。但是创建驱动表的hash是耗费很多资源的，所以要优化器去判断是否使用

mysql Join原理