一、表连接的简介

create table t1(m1 int, n1 char(1));
create table t2(m2 int, n2 char(1));

insert into t1 values(1,'a'),(2,'b'),(3,'c');
insert into t2 values(2,'b'),(3,'c'),(4,'d');

t1表数据如下

t2表数据如下

我们知道，所谓表连接就是把各个表中的记录都取出来进行依次匹配，最后把匹配组合的记录一起发送给客户端。比如下面把t1表和t2表连接起来的过程如下图

什么是连接查询？

比如上面t1和t2表的记录连接起来组成一个新的更大的记录，这个查询过程就称为连接查询。

什么是笛卡尔积？

如果连接查询的结果集中包含一个表中的每一条记录与另一个表中的每一条记录相互匹配组合的记录，那么这样的结果集就可以称为笛卡尔积。

# 这三者效果一样，只要不写条件，就产生笛卡尔积，结果集的数量一样。
select * from t1, t2;
# 内连接
select * from t1 inner join t2;
# 全连接
select * from t1 cross join t2;

表t1中有3条记录，表t2中也有3条记录，两个表连接后的笛卡尔积就有3 x 3 = 9条记录，只要把两个表的记录数相乘，就能得到笛卡尔积的数量。

二、表连接的过程

笛卡尔积也是一个很大的问题，不加限制条件，结果集的数量就会很大。比如你在开发过程中需要2个表的连接，表1有20000条记录，表2有10000条记录，表3有100条记录，那么3张表连接后产生的笛卡尔积就有20000 x 10000 x 100 = 20000000000条记录（两百亿条记录）。

所以在连接时过滤掉特定的记录组合是很有必要的，为了避免笛卡尔积，一定要在表连接的时候加上条件！

下面来看一下有过滤条件的表连接的执行过程。

# 下面两种写法都一样，执行效率没有区别，看看自己习惯于哪种写法
select * from t1 join t2 on t1.m1 > 1 and t1.m1 = t2.m2 and t2.n2 < 'd';

select * from t1, t2 where t1.m1 > 1 and t1.m1 = t2.m2 and t2.n2 < 'd';

注意：先说明条件的概念，要区分什么是连接条件和过滤条件！！

连接条件是针对两张表而言的，比如t1.m1 = t2.m2、t1.n1 > t2.n2，表达式两边是两个表的字段比较。

过滤条件是针对单表而言的，比如t1.m1 > 1是针对t1表的过滤条件，t2.n2 < 'd'是针对t2表的过滤条件。

1.首先确定第一个需要查询的表，这个表称之为驱动表。

在单表中选择代价最小的查询方式，简单理解就是走合适的索引即可。此处假设使用t1作为驱动表，那么就需要到t1表中找满足过滤条件t1.m1 > 1的记录，因为表中的数据太少，我们也没在表上建立索引，所以此处查询t1表的查询的方式就是all，也就是采用全表扫描的方式执行单表查询，筛选出符合条件的驱动表记录。

这里筛选出来的t1驱动表记录有2条。

2.从第1步中驱动表筛选出来的每一条记录，都要到t2表中查询匹配记录。

匹配记录就是找到满足连接条件和过滤条件的记录。因为是根据t1表中的记录去找t2表中的记录，所以t2表也可以称为被驱动表。上一步从驱动表筛选出了2条记录，意味着需要从头到尾将t2表查询2次，此时就得看两表之间的连接条件了，这里就是t1.m1 = t2.m2。

对于从t1表查询得到的第一条记录，而这条记录t1.m1=2，根据连接条件t1.m1 = t2.m2，就相当于在t2表加上过滤条件t2.m2 = 2，此时t2表相当于有了两个过滤条件t2.m2 = 2 and t2.n2 < 'd'，然后到t2表执行单表查询，每当匹配到满足条件的一条记录后立即返回给MySQL客户端，以此类推。

所以整个连接查询的执行过程如下：

最后连接查询的结果只有2条记录。

如果把t1.m1 > 1这个过滤条件去掉了，那么从t1表查出的记录就有3条，就需要从头到尾扫3次t2表了。

其实这个流程的套路就是用伪代码说明非常合适，你细品，看懂这个伪代码，你就理解了表连接的步骤。

for  筛选 驱动表 满足条件的每条记录 {
    for 筛选 被驱动表 满足条件的每条记录 {
        发送到MySQL客户端;
    }
}

从这个伪代码可以看出，驱动表的每一条记录都会尝试遍历被驱动表的每条记录并匹配连接，每成功连接一条就返回给MySQL客户端。

总结：

1.在两表连接查询中，驱动表只需访问一次，而被驱动表可能需要访问多次。

2.并不是将所有满足过滤条件的驱动表记录先查询出来放到一个地方，然后再去被驱动表查询的（因为如果满足过滤条件的驱动表很大，需要的临时存储空间就会非常大）。而是每获得一条满足过滤条件的驱动表记录，就立即到被驱动表中查询匹配的记录。

三、内连接和外连接

1. 内连接

上面第二节所讲的，都是内连接。

先建立2张表，后续根据这2张表来讲解。

CREATE TABLE student (
    stu_no INT NOT NULL AUTO_INCREMENT COMMENT '学号',
    name VARCHAR(5) COMMENT '姓名',
    major VARCHAR(30) COMMENT '专业',
    PRIMARY KEY (stu_no)
) Engine=InnoDB CHARSET=utf8mb4 COMMENT '学生信息表';

CREATE TABLE score (
    stu_no INT COMMENT '学号',
    subject VARCHAR(30) COMMENT '科目',
    score TINYINT COMMENT '成绩',
    PRIMARY KEY (stu_no, subject)
) Engine=InnoDB CHARSET=utf8mb4 COMMENT '学生成绩表';

插入一些数据

insert into student values(20210901, '王大个', '软件工程');
insert into student values(20210902, '刘帅哥', '物联网工程');
insert into student values(20210903, '张小伟', '电子工程');

insert into score values(20210901, '数据结构', 92);
insert into score values(20210901, '计算机网络', 94);
insert into score values(20210902, '计算机网络', 88);
insert into score values(20210902, '数据结构', 80);

student表数据如下：

score表数据如下：

如果想要把学生的成绩都查出来，就需要表连接(score表中没有姓名，所以不能只查score表)，连接过程就是从student表取出记录，然后在score表中查找number相同的成绩记录，连接条件是student.stu_no= score.stu_no;

select * from student join score where student.stu_no = score.stu_no;

表连接的全部字段就在这里了，字段有点多，stu_no是重复的，我们修改一下

select s1.stu_no, s1.name, s2.subject, s2.score from student as s1 join score as s2 on s1.stu_no = s2.stu_no;

可以看到，学生的各科成绩都被查出来了。但是张小伟(学号为20210903的同学)因为缺考，在score表中没有记录。要是老师想查看所有学生的成绩(包括缺考的同学)该怎么办呢？也就是说，哪怕成绩为空，也要显示这位同学在这个表里面，咱们不能把他给踢了吧！

这个问题就化为这个模型：对于驱动表中的某条记录，哪怕根据连接条件或者过滤条件在被驱动表中没有找到对应的记录，也还是要把该驱动表的记录加到结果集。

这就是内连接的局限性。

其实我们想要看到的结果集是这样的

为了解决这个问题，就有了内连接和外连接的区别。

对于内连接来说，若驱动表中的记录按照连接条件或者过滤条件在被驱动表中找不到匹配的记录，则该记录不会加入到最后的结果集。

前面提到的都是内连接，比如前面例子中，当t1.m1 = 2时，根据连接条件t1.m1 = t2.m2，在被驱动表中如果没有记录满足过滤条件t2.m2 = 2 and t2.n2 < 'd'，驱动表的记录就不会加到最后的结果集。

注意：我们说过，内连接语法有很多种。对于内连接来说，连接条件选择on或者where都可以，凡是不符合on子句或者where子句条件的记录都会被过滤掉，不会被连接，更不会在最后的结果集。

# 以下三者效果一样，当用join进行内连接时，条件用on或者where连接都可以。
select * from student join score on student.stu_no= score.stu_no;

select * from student join score where student.stu_no= score.stu_no;

select * from student, score where student.stu_no= score.stu_no;

2. 外连接

对于外连接来说，即使驱动表中的记录按照连接条件和过滤条件在被驱动表中找不到匹配的记录，该记录也仍然需要加入到结果集。

对于外连接来说，又有左(外)连接和右(外)连接的区别

左(外)连接：选取左侧的表为驱动表。

右(外)连接：选取右侧的表为驱动表。

重点强调：对于内连接来说，选取哪个表为驱动表都没关系。而外连接的驱动表是固定的，左(外)连接的驱动表就是左边那个表，右(外)连接的驱动表就是右边那个表。

左(外)连接的语法：

比如要把t1表和t2表进行左连接查询。

select * from t1 
left [outer] join t2
on 条件
[where 普通过滤条件]

# 注意这个on条件包括连接条件和驱动表与被驱动表的单表过滤条件。
# []括号代表可以省略

左表所有记录都会有，右表没有与之匹配的则用NULL填充。

对于外连接来说，on和where是有区别的。

即使被驱动表中的记录无法匹配on子句的条件，该驱动表的记录仍然是满足条件的一条记录，对应被驱动表的各个字段用NULL填充。

简言之，对于外连接，驱动表的记录一定都有，被驱动表不匹配就用NULL填充。

而where过滤条件是在记录连接过后的普通过滤条件，即连接的记录会再次判断是否符合条件，不符合就从结果集中剔除。

回到刚刚的问题，要把所有学生成绩显示出来(包括缺考的学生)

select s1.stu_no, s1.name, s2.subject, s2.score from student as s1 
left join 
score as s2 
on s1.stu_no = s2.stu_no;

从上面结果集可以看出，虽然张小伟缺考，但是还是在结果集中，只不过对应的科目成绩用NULL填充。

右(外)连接的语法

select * from t1 
right [outer] join t2
on 条件
[where 普通过滤条件]

# 注意这个on条件包括连接条件和驱动表与被驱动表的单表过滤条件。
# []括号代表可以省略

右连接中，驱动表是右边的表，被驱动表是左边的表，右表所有记录都会有，左表没有与之匹配的则用NULL填充。这里就不举例了。

四、表连接的原理

1. 简单的嵌套循环连接（Simple Nested-Loop Join）

我们前边说过，对于两表连接来说，驱动表只会访问一遍，但被驱动表要被访问到好多遍，具体访问几遍取决于驱动表执行单表查询后满足条件的记录条数。

假设t1表和t2表都没有索引，t1表和t2表内连接的大致过程如下：

步骤1：选取驱动表t1，使用与驱动表t1相关的过滤条件，选取成本最低的单表访问方法来执行对驱动表的单表查询。（根据你的索引和记录数量，查询优化器会选择成本最低的访问方法，这里没有索引则全表扫描）

步骤2：对上一步中查询驱动表得到的每一条满足条件的记录，都分别到被驱动表t2中查找匹配的记录。

具体细节在第二节说过，这里就不细致展开。

如果有第3个表t3进行连接的话，那么总体查询过程就是，查找t1表满足单表过滤条件的第一条记录，匹配连接t2表满足单表过滤条件的第一条记录(此时驱动表是t1，被驱动表是t2)，然后匹配连接t3表满足单表过滤条件的第1条记录(此时驱动表是t2，被驱动表是t3)，将这条满足所有条件的一条记录返回给MySQL客户端；前面条件不变，接着匹配连接t3表满足单表过滤条件的第2条记录......

这个过程最适合用伪代码来说明了

for 筛选t1表满足条件的每条记录:
    for 筛选t2表满足条件的每条记录:
        for 筛选t3表满足条件的每条记录:
            if 连接条件满足:
                发送到MySQL客户端

这个过程就像是一个嵌套的循环，驱动表每一条记录，都要从头到尾扫描一遍被驱动表去尝试匹配。这种连接执行方式称之为简单的嵌套循环连接（Simple Nested-Loop Join），这是比较笨拙的一种连接查询算法。自MySQL的早期版本以来，这种基本的连接算法就已经存在。在MySQL 3.x和4.x中，这种连接方法已经可以使用。

注意：对于嵌套循环连接算法来说，每当从驱动表获得一条记录，就根据这条记录立即到被驱动表查一次，如果得到匹配连接记录，那就把这条连接的记录立即发送给MySQL客户端，而不是等查询完所有结果后才返回。然后再到被驱动表获取下一条符合条件的记录，直到被驱动表遍历完成，就切换到驱动表的下一条记录再次遍历被驱动表的每条记录，以此类推。

简单嵌套循环连接算法在没有合适索引的情况下效率较低，但是在实际使用中，查询优化器通常会采用更高级的算法，如基于索引的连接（如Block Nested Loop Join，Index Nested Loop Join）或者哈希连接（Hash Join）等，以提高查询性能。因此，在实际使用中，我们应该尽量优化表结构、使用适当的索引，以便查询优化器可以选择更高效的连接算法。

2. 基于索引的嵌套循环连接（Index Nested-Loop Join）

在上一小节嵌套循环连接的步骤2中可能需要访问多次被驱动表，如果访问被驱动表的方式都是全表扫描，扫描次数就非常多。

幸好MySQL优化器会找出所有可以用来执行该语句的方案，并会对比之后找出成本最低的方案，简单理解就是使用哪个索引最好。所以既然会多次访问被驱动表，索引好不好就是性能的瓶颈。

查询被驱动表其实就相当于一次单表扫描，那么我们可以利用索引来加快查询速度。

回到最开始介绍的t1表和t2表进行内连接的例子：

select * from t1 join t2 on t1.m1 > 1 and t1.m1 = t2.m2 and t2.n2 < 'd';

这其实是嵌套循环连接算法执行的连接查询，再把上边那个查询执行过程拿下来给大家看一下：

查询驱动表t1后的结果集中有2条记录，嵌套循环连接算法需要查询被驱动表2次：

当t1.m1 = 2时，去查询一遍t2表，对t2表的查询语句相当于：

select * from t2 where t2.m2 = 2 and t2.n2 < 'd';

当t1.m1 = 3时，再去查询一遍t2表，此时对t2表的查询语句相当于：

select * from t2 where t2.m2 = 3 and t2.n2 < 'd';

可以看到，原来的t1.m1 = t2.m2这个涉及两个表的过滤条件在针对t2表进行查询时，选出t1表的一条记录之后，t2表的条件就已经确定了，即t2.m2 = 常数值，所以我们只需要优化对t2表的查询即可，上述两个对t2表的查询语句中利用到的列是m2和n2列，我们可以进行如下尝试：

在m2列上建立索引，因为对m2列的条件是等值查找，比如t2.m2 = 2、t2.m2 = 3等，所以可能使用到ref的访问方法，假设使用ref的访问方法去执行对t2表的查询的话，需要回表之后再判断t2.n2 < 'd'这个条件是否成立。
在n2列上建立索引，涉及到的条件是t2.n2 < 'd'，可能用到range的访问方法，假设使用range的访问方法对t2表进行查询，需要在回表之后再判断在m2列的条件是否成立。

假设m2和n2列上都存在索引，那么就需要从这两个里面挑一个代价更低的索引来查询t2表。也有可能不使用m2和n2列的索引，只有在非聚集索引 + 回表的代价比全表扫描的代价更低时才会使用索引。

Index Nested-Loop Join与Simple Nested-Loop Join的不同就是被驱动表加了索引，后面只说Index Nested-Loop Join。Index Nested-Loop Join在早期的MySQL版本中就已经实现。MySQL 3.x和4.x的优化器已经可以根据可用索引来选择这种连接方法。

扩展思考：我们分析一下整个查询过程中的扫描次数

eg1：假设驱动表全表扫描，行数为N，被驱动表使用索引查找，行数为M，B+树索引的深度为h。

索引查找次数：对于B+树索引，查找一行数据的扫描次数大致等于树的深度。设树的深度为h，那么索引查找次数约为h。
回表次数：当使用非聚集索引查找到目标行后，还需要回表查询聚集索引（通常是主键索引）以获取完整的记录。这个过程中，再次通过聚集索引查找，扫描次数也大致为h。

因此，被驱动表上查找一行数据的总扫描次数大约为2 * h。

驱动表全表扫描次数：N
对于驱动表的每一行记录，到被驱动表上进行索引查找，扫描次数约为：N * 2 * h

所以，整个查询过程的总扫描次数为：N + N * 2 * h = N * (1 + 2 * h)。

根据这个计算方法，我们可以看到N（驱动表行数）对扫描行数的影响更大，因此在执行连接查询时，如果被驱动表可以使用索引，我们应该选择数据量小的表作为驱动表。

注意：这个计算方法仅作为一个基本示例，实际情况可能更复杂，具体取决于索引类型、树的深度、数据分布等因素。

eg2：假设驱动表全表扫描，行数为N，被驱动表不使用索引也是全表扫描，行数为M。

驱动表全表扫描次数：N
对于驱动表的每一行记录，到被驱动表上进行全表扫描查找，扫描次数约为：N * M

所以，整个查询过程的总扫描次数为：N + N * M = N * (1 + M)

在这种情况下，我们可以看到N（驱动表行数）和M（被驱动表行数）都会对扫描行数产生较大的影响。为了提高查询效率，我们应该尽量选择数据量小的表作为驱动表。然而，在实际应用中，我们通常会为被驱动表添加适当的索引以提高查询性能。

注意：实际情况可能更复杂，具体取决于数据分布、查询条件等因素。在实际应用中，查询优化器会根据统计信息和成本模型来选择最佳的执行计划。

3. 基于块的嵌套循环连接（Block Nested-Loop Join）

扫描一个表的过程其实是先把这个表从磁盘上加载到内存中，然后从内存中比较匹配条件是否满足。

实际开发中的表可不像t1、t2这种只有3条记录，几千万甚至几亿条记录的表到处都是。现在假设我们不能使用索引加快被驱动表的查询过程，所以对于驱动表的每一条记录，都需要对被驱动表进行全表扫描。而对被驱动表全表扫描时，可能表前面的记录还在内存中，表后边的记录可能还在磁盘上。等扫描到后边记录的时候，可能由于内存不足，所以需要把表前面的记录从内存中释放掉给正在扫描的记录腾地方，这样就非常消耗性能。

采用嵌套循环连接算法的两表连接过程中，被驱动表是要被访问好多次的，所以我们得想办法，尽量减少被驱动表的访问次数。

驱动表中满足筛选条件的有多少条记录，就得把被驱动表中的所有记录从磁盘上加载到内存中多少次。

读磁盘代价太大，能不能在内存中操作呢？于是一个Join Buffer（连接缓冲区）的概念就出现了，Join Buffer就是执行连接查询前申请的一块固定大小的内存（默认256K），先把满足条件的若干条驱动表的记录装在这个Join Buffer中，然后开始扫描被驱动表，每一条被驱动表的记录一次性与Join Buffer中的所有记录进行匹配，因为匹配的过程都是在内存中完成的，所以这样可以显著减少被驱动表的I/O代价。使用Join Buffer的过程如下图所示：

为什么Join Buffer要装驱动表而不是被驱动表呢？上面说过，小表作为驱动表，Join Buffer装小表更容易装得下，下一节会讲这个原因。

其实很好记忆，想想笛卡尔积顺序也很奇妙。笛卡尔积的顺序就是一条被驱动表记录匹配多条驱动表记录的顺序，而不是一条驱动表记录去匹配被驱动表的记录的顺序，你看看这个顺序是不是很神奇，可以自行键两张表连接看看笛卡尔积，观察一下。

笛卡尔积顺序是
1 a 2 b
2 b 2 b
3 c 2 b
.....
而不是
1 a 2 b
1 a 3 c
1 a 4 d
...
你发现了吗？

其实最好的情况是Join Buffer足够大，能容纳驱动表结果集中的所有记录，这样只需要访问一次被驱动表就可以完成连接操作了。这种加入了Join Buffer的嵌套循环连接算法称之为基于块的嵌套连接（Block Nested-Loop Join）算法。MySQL 4.1中引入了Block Nested-Loop Join算法，提高了连接查询的性能。这种连接算法利用了join buffer来加速连接过程。

这个Join Buffer的大小是可以通过启动参数或者系统变量join_buffer_size进行配置，默认大小为262144字节（也就是256KB），最小可以设置为128字节。对于被驱动表，最好是为被驱动表加上效率高的索引，如果实在不能使用索引，可以尝试调大join_buffer_size的值来对连接查询进行优化。

另外需要注意的是，只有满足条件的select中的列才会被放到Join Buffer中，所以再次提醒我们，最好不要把*作为查询列表，这样还可以在Join Buffer中放置更多的记录。

4. Nested-Loop Join和Block Nested-Loop Join对比说明

假设t1表的行数是N，t2表的行数是M，t1表是小表，即N < M

Simple Nested-Loop Join算法：

驱动表的每一条记录都会去被驱动表逐一匹配，所以总的扫描行数是N * M（开头说了，扫描表就是把表从磁盘加载到内存中）；
内存中的判断次数是N * M（扫描一次就会在内存中判断一次）。

别纠结了，这种方法太笨了，不管选择哪个表作为驱动表，最后扫描和内存中判断的成本都是一样的。

Index Nested-Loop Join算法

该算法被驱动表的查询条件字段加上了合适的索引。

驱动表的每一条记录都会去被驱动表逐一匹配，所以总的扫描行数是N * log M（扫描行数不变，但是因为被驱动表有索引，扫描速度会大大增加）；
内存中的判断次数是M * N（扫描一次就会在内存中判断一次）。

Block Nested-Loop Join算法：

该算法又得区分Join Buffer装得下和装不下的情况。

Join Buffer装得下的情况

t1表和t2表都做一次全表扫描，将t1表记录都装入Join Buffer，总的扫描行数是M + N（开头说了，扫描表就是把表从磁盘加载到内存中，驱动表扫描M行一次性装到Join Buffer，被驱动表扫描一行会在Join Buffer进行比较，最终扫描N行）；
内存中的判断次数是M * N，由于Join Buffer是以无序数组的方式组织的，因此对t2表中的每一行数据，都要与Join Buffer中的记录相比较。

可以看到，调换这两个算式中的M和N没差别，因此这时候选择t1还是t2表做驱动表，成本都是一样的。

Join Buffer装不下的情况

我们先用直观的数据说明过程，假如表t1是100行，而Join Buffer放不下，此时就分段放，执行过程就变成了：

扫描表t1，顺序读取数据行放入Join Buffer中，放完第80行Join Buffer满了，继续第2步；
扫描表t2，把t2中的每一行取出来，跟Join Buffer中的所有记录做对比，满足join条件的，返回该条记录给MySQL客户端；
清空Join Buffer；
继续扫描表t1，顺序读取最后的20行数据放入Join Buffer中，继续执行第2步。

这个流程体现出了这个算法名字中“Block”的由来，表示“分块的join”。

现在总结一下这个过程。驱动表t1的数据行数是N，假设需要分K次才能完成算法流程，被驱动表t2的数据行数是M。

注意，这里的K不是常数，N越大K就会越大。所以，在这个执行过程中：

扫描行数是N + K * M，每次装完一次Join Buffer，被驱动表t2的M条记录就会从头到尾去Join Buffer匹配，Join Buffer需要装K次，则扫描K次t2表；
内存判断N * M次，由于Join Buffer是以无序数组的方式组织的，因此对t2表中的每一行数据，都要与Join Buffer中的记录相比较。

显然，内存判断次数是不受选择哪个表作为驱动表影响的。而扫描行数考虑到Join Buffer的大小，在M和N大小确定的情况下，驱动表的数据行数N小一些，则分段K就少一些，那么整个表达式的结果会更小。

总结：如果Join Buffer能装任意一张表里的所有数据，那么不管选择哪个表作为驱动表，执行成本都一样。对于Join Buffer一次装不下驱动表的情况下，应该让小表当驱动表，因为小表记录总行数N越小，Join Buffer装完所需的次数K就越小，在N + K * M这个式子里，表达式的值越小。

刚刚我们说了N越大，分段数K越大。那么N固定的时候，什么参数会影响K的大小呢？答案是join_buffer_size。join_buffer_size越大，Join Buffer中一次可以放入的行越多，分成的段数K也就越少，对被驱动表的全表扫描次数就越少。

join_buffer_size默认256K，我所在的公司配置的是4M。

1.不能使用被驱动表的索引，只能使用Block Nested-Loop Join算法，这样的语句就尽量不要使用
2.Explain下，没用Index Nested-Loop 的全要优化

综上：从上面1234小节来看，无论哪种情况，总是应该选择小表作为驱动表。并且两张表有个各自的索引，这样表连接才能达到更好的性能。在内连接中，你可以使用STRAIGHT_JOIN替换JOIN，这样在内连接中就是强制左表为驱动表，但应该谨慎使用。在大多数情况下，MySQL优化器可以自动选择一个合适的驱动表。只有在优化器做出错误选择时，或者你有充分理由相信手动选择驱动表会带来性能提升时，才应该考虑使用STRAIGHT_JOIN。

5. 哈希连接（Hash Join）

哈希连接（Hash Join）是另一种连接算法，尤其在处理大表连接时表现出较高的效率。哈希连接是在MySQL 8.0.18才引入的

以下是对哈希连接的详细介绍和举例分析：

哈希连接分为两个阶段：构建哈希表（Build phase）和探测哈希表（Probe phase）。

构建哈希表阶段：

在这个阶段，数据库首先选择一个表作为构建哈希表的驱动表，通常是连接操作中较小的表。接着，数据库遍历驱动表的所有行，针对连接条件中的键值（例如：t1.key = t2.key）计算哈希值，并根据哈希值将这些行存储在哈希表中。哈希表会按照哈希值将记录分组存储，具有相同哈希值的记录会放在同一个桶（Bucket）中。

探测哈希表阶段：

探测阶段开始时，数据库会遍历另一个表（即非驱动表，通常是较大的表）。对于这个表的每一行，数据库会计算连接条件中的键值的哈希值。然后，数据库会在哈希表中搜索具有相同哈希值的桶。在找到对应桶后，数据库会检查桶内的所有记录，逐一进行等值匹配。如果找到匹配的记录，则将这对记录作为连接结果的一部分返回。

假设有两张表，如下:

orders 表：

order_id | customer_id | order_amount
-------- | ----------- | ------------
1        | 101         | 100
2        | 104         | 200
3        | 102         | 150
4        | 103         | 120
5        | 101         | 90
6        | 106         | 180

customers 表：

customer_id | customer_name
----------- | -------------
101         | Alice
102         | Bob
103         | Charlie
104         | David
105         | Eve
106         | Frank

为了简化，假设哈希函数是 hash(customer_id) = customer_id % 3，我们得到以下哈希表：

Bucket 0: [(102, Bob), (105, Eve)]
Bucket 1: [(101, Alice), (104, David)]
Bucket 2: [(103, Charlie), (106, Frank)]

现在我们遍历 orders 表。对于每个记录，我们计算其 customer_id 的哈希值，然后在哈希表中找到相应的桶。如果找到匹配的记录，我们将 orders 表和 customers 表的记录组合在一起，形成连接结果。

order_id=1, customer_id=101：哈希值为 1（101 % 3），在 Bucket 1 找到匹配记录 (101, Alice)，连接结果为 (1, 101, 100, 101, Alice)。
order_id=2, customer_id=104：哈希值为 1（104 % 3），在 Bucket 1 找到匹配记录 (104, David)，连接结果为 (2, 104, 200, 104, David)。
order_id=3, customer_id=102：哈希值为 0（102 % 3），在 Bucket 0 找到匹配记录 (102, Bob)，连接结果为 (3, 102, 150, 102, Bob)。
order_id=4, customer_id=103：哈希值为 2（103 % 3），在 Bucket 2 找到匹配记录 (103, Charlie)，连接结果为 (4, 103, 120, 103, Charlie)。
order_id=5, customer_id=101：哈希值为 1（101 % 3），在 Bucket 1 找到匹配记录 (101, Alice)，连接结果为 (5, 101, 90, 101, Alice)。
order_id=6, customer_id=106：哈希值为 2（106 % 3），在 Bucket 2 找到匹配记录 (106, Frank)，连接结果为 (6, 106, 180, 106, Frank)。

最后，我们得到以下连接结果：

order_id | customer_id | order_amount | customer_id | customer_name
-------- | ----------- | ------------ | ----------- | -------------
1        | 101         | 100          | 101         | Alice
2        | 104         | 200          | 104         | David
3        | 102         | 150          | 102         | Bob
4        | 103         | 120          | 103         | Charlie
5        | 101         | 90           | 101         | Alice
6        | 106         | 180          | 106         | Frank

在哈希连接中，MySQL 通常需要对两个表进行全表扫描。哈希桶用于存储来自驱动表（较小的表）的记录。每个哈希桶存储具有相同哈希值的记录。当遍历被驱动表（较大的表）时，会计算每行记录的哈希值，并检查该哈希值在驱动表的哈希桶中是否存在。如果存在匹配的哈希值，那么将这两个表的记录组合在一起，形成一个连接结果记录。

注意：哈希桶中存放的是驱动表的记录，而不是两张表连接后的记录。在连接过程中，哈希桶被用作一个中间数据结构，帮助找到匹配的行并组合成连接结果。

在使用哈希连接时，如果内存不足以容纳所有哈希桶，MySQL 可能会将部分桶溢出到磁盘，这可能会导致性能下降。因此，在使用哈希连接时需要关注内存使用情况以确保性能优化。虽然哈希连接通常需要全表扫描，但它在处理大量数据和等值连接时非常高效，特别是当两个表之间没有合适的索引可用时，因为它可以在 O(n) 时间复杂度内完成连接操作，而嵌套循环连接的时间复杂度为 O(n^2)，MySQL 优化器会根据实际情况选择最佳的连接算法。

哈希连接的优点：

当处理大表连接时，哈希连接通常比嵌套循环连接和其他连接算法更快，因为它利用哈希表的高效查找特性。
在某些情况下，哈希连接可以在内存中完成，避免磁盘I/O，从而提高性能。

哈希连接的缺点：

哈希连接需要构建哈希表，这可能需要大量内存。如果内存不足，哈希表可能需要分区并写入磁盘，这将降低性能。
哈希连接仅适用于等值连接，而在非等值连接（如大于、小于等）情况下，哈希连接不适用，实际开发中基本都是on条件的等值连接，这里就不细说非等值连接。

6. 怎样分析表连接使用了哪种连接算法？

explain语句可以提供一些关于查询执行计划的信息，从而让我们推断使用了哪种连接算法。

举个例子：

EXPLAIN SELECT * FROM orders JOIN products ON orders.product_id = products.product_id;

返回以下结果

id | select_type | table   | type  | possible_keys | key       | key_len | ref           | rows | Extra
1  | SIMPLE      | orders  | index | NULL          | idx_order | 4       | NULL          | 10   | Using index
1  | SIMPLE      | products| ref   | idx_product   | idx_product| 4       | orders.product_id | 1  | Using index

假设我们有两个表：orders 和 products，它们之间存在一个基于 product_id 的等值连接。我们将为这两个表创建一个简单的查询：

explain并不直接显示使用哪种连接算法。以下是根据explain输出推断连接算法的方法：

Simple Nested-Loop Join：
如果驱动表的type列显示为ALL或index，且被驱动表的type列也显示为ALL，而且Extra列没有Using index，则可能是Simple Nested-Loop Join。
Index Nested-Loop Join：
如果驱动表的type列显示为ref、eq_ref或range，且被驱动表的type列显示为ref、eq_ref或range，而且Extra列包含Using index，则可能是Index Nested-Loop Join。
Block Nested-Loop Join：
如果驱动表的type列显示为ALL或index，且被驱动表的type列显示为ALL，而Extra列包含Using join buffer，则可能是Block Nested-Loop Join。
Hash Join：
从MySQL 8.0.18版本开始，如果Extra列中包含Using hash join，表示MySQL正在使用哈希连接算法进行连接操作。

注意，这些推断并不是绝对的，实际上MySQL查询优化器会根据查询条件、表结构和索引等因素选择最佳的执行计划。

如果还想更准确的推断是什么连接算法，可以查看EXPLAIN FORMAT=JSON输出

EXPLAIN FORMAT=JSON SELECT * FROM orders JOIN products ON orders.product_id = products.product_id;

在输出中找到join_algorithm属性

join_algorithm属性可以具有以下值，它们分别代表不同的连接算法：

"nested_loop": 这表示MySQL正在使用简单嵌套循环连接算法（Simple Nested-Loop Join）。这是一种基本的连接方法，通过对驱动表的每一行，扫描被驱动表来找到匹配的行。它不需要索引或预排序。
"block_nested_loop": 这表示MySQL正在使用块嵌套循环连接算法（Block Nested-Loop Join）。这种算法类似于简单嵌套循环连接，但它会将驱动表的多行缓存起来，然后一次性地扫描被驱动表，以提高性能。这种方法也不需要索引或预排序。
"hash": 这表示MySQL正在使用哈希连接算法（Hash Join）。在这种方法中，MySQL首先构建一个哈希表，其中包含驱动表中的行。然后，它扫描被驱动表，并使用哈希函数找到哈希表中的匹配行。这种方法适用于等值连接，并且在处理大型数据集时效率更高。
"ref": 这表示MySQL正在使用基于索引的嵌套循环连接算法（Index Nested-Loop Join，也叫Ref Join）。这种连接方法使用被驱动表上的索引，以便更快地找到匹配的行。这种方法通常比简单嵌套循环连接更快。
"sort_merge": 这表示MySQL正在使用排序合并连接算法（Sort Merge Join）。在这种方法中，MySQL首先对驱动表和被驱动表进行排序，然后通过扫描两个已排序表来找到匹配的行。这种方法适用于非等值连接，以及在索引不可用或无法提供优势的情况下的等值连接。注意：Sort Merge Join 并未被明确实现作为一种连接算法，查询优化器将排序和合并操作在执行过程中进行，而不是作为连接算法的一部分。
"batched_key_access": 这表示MySQL正在使用批处理键访问连接算法（Batch Key Access Join）。此方法类似于基于索引的嵌套循环连接算法，但将对被驱动表的访问分组成批次，以提高性能。它适用于基于索引的连接，尤其是涉及到远程表（例如，在分布式查询中）时。

注意：Batch Key Access (BKA) Join是在MySQL 5.6版本引入的一种连接优化技术。BKA Join可以显著提高连接性能，特别是在涉及大表连接时。BKA Join使用了一种称为“多范围读”的技术，可以在一次磁盘访问中读取多个行。这种方法可以减少磁盘访问次数，从而提高查询性能。如果要启用BKA Join，需要在MySQL服务器配置中启用optimizer_switch参数的batched_key_access选项。
Batch Key Access (BKA) Join 默认不启用，你可以通过以下 SQL 语句启用 BKA Join：
SET optimizer_switch='batched_key_access=on';
这将在当前会话中启用 BKA Join。要在全局范围内启用它，你可以使用以下命令：
SET GLOBAL optimizer_switch='batched_key_access=on';
在某些情况下，MySQL 优化器可能仍然会选择其他连接算法，即使 BKA Join 是可用的。这取决于优化器评估的成本和各种连接算法的适用性。

欢迎一键三连~

有问题请留言，大家一起探讨学习

----------------------Talk is cheap, show me the code-----------------------

面试之前，MySQL表连接必须过关！——表连接的原理

一、表连接的简介

二、表连接的过程

三、内连接和外连接

1. 内连接

2. 外连接

四、表连接的原理

1. 简单的嵌套循环连接（Simple Nested-Loop Join）

2. 基于索引的嵌套循环连接（Index Nested-Loop Join）

3. 基于块的嵌套循环连接（Block Nested-Loop Join）

4. Nested-Loop Join和Block Nested-Loop Join对比说明

5. 哈希连接（Hash Join）

6. 怎样分析表连接使用了哪种连接算法？

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

面试之前，MySQL表连接必须过关！——表连接的原理

一、表连接的简介

二、表连接的过程

三、内连接和外连接

1. 内连接

2. 外连接

四、表连接的原理

1. 简单的嵌套循环连接（Simple Nested-Loop Join）

2. 基于索引的嵌套循环连接（Index Nested-Loop Join）

3. 基于块的嵌套循环连接（Block Nested-Loop Join）

4. Nested-Loop Join和Block Nested-Loop Join对比说明

5. 哈希连接（Hash Join）

6. 怎样分析表连接使用了哪种连接算法？

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像