MYSQL 连接查询算法：JOIN语句在 MYSQL 内部到底是

作者: 今天你敲代码了吗 | 来源:发表于2020-08-17 22:19 被阅读0次

前言

我们从一个问题引入今天的主题。

在日常业务开发中，我们可能经常听到 DBA 对我们说“不要”（注意：不是禁止）使用 join，那么为什么 DBA 对 join 这么抵触呢？是 join 本身有问题，还是我们使用的方式不对。

其实这涉及到 join 语句在 MYSQL 内部到底是怎么执行的。

这就是我们今天要讲的内容。

预备知识点

STRAIGHT_JOIN

STRAIGHT_JOIN与 JOIN 类似，不同之处在于总是在右表之前读取左表。也就是说强制把左表当做驱动表。

删除存储过程/函数

MySQL 中使用 DROP PROCEDURE 语句来删除存储过程；使用 DROP FUNCTION 语句来删除存储函数。

语法为：

DROP {PROCEDURE | FUNCTION} [IF EXISTS] sp_name

IF EXISTS 子句是 MySQL 的扩展。如果过程或功能不存在，则可以防止发生错误。

delimiter

delimiter 是 MYSQL 分隔符，在 MYSQL 客户端中分隔符默认是分号 ;。如果一次输入的语句较多，并且语句中间有分号，这时需要新指定一个特殊的分隔符。

其实就是告诉 MYSQL 解释器，该段命令是否已经结束了，MYSQL 是否可以执行了。默认情况下，delimiter 是分号 ;。在命令行客户端中，如果有一行命令以分号结束，那么回车后，MYSQL 将会执行该命令。

buffer pool

MYSQL 服务器启动的时候向操作系统申请一块连续的内存，这个就是 buffer pool
默认情况下 buffer pool 只有 128M 大小,可以通过 innodb_buffer_pool_size 修改，该参数的单位是字节。
最小值只能是 5M。

数据准备

为了便于量化分析，我们创建了两张表：商品表 和 商品扩展表。其中商品表 1000 条数据，商品扩展表 100 条数据。商品表和商品扩展表是一一对应的。

CREATE TABLE `goods` (
    `id` int(10) NOT NULL AUTO_INCREMENT,
    `goods_id` int(10) unsigned NOT NULL DEFAULT '0' COMMENT '商品id',
    `goods_name` varchar(128) NOT NULL DEFAULT '' COMMENT '商品名',
    PRIMARY KEY (`id`),
    KEY `idx_goods_id` (`goods_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT='商品表';

drop procedure insert_goods_data;

delimiter ;;

create procedure insert_goods_data()

begin declare i int;

declare goods_name CHAR(6);

set i = 1;

while (i <= 1000) do

set goods_name = concat('商品',i);

insert into goods (id, goods_id, goods_name) values (i, i, goods_name);

set i=i+1;

end while;

end;;

delimiter ;

call insert_goods_data();

CREATE TABLE `goods_extend` (
    `id` int(10) NOT NULL AUTO_INCREMENT,
    `goods_id` int(10) unsigned NOT NULL DEFAULT '0' COMMENT '商品id',
    `goods_name` varchar(128) NOT NULL DEFAULT '' COMMENT '商品名',
    `create_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
    `modify_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '修改时间',
    PRIMARY KEY (`id`),
    KEY `idx_goods_id` (`goods_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT='商品扩展表';

drop procedure insert_goods_extend_data;

delimiter ;;

create procedure insert_goods_extend_data()

begin declare i int;

declare goods_name CHAR(6);

set i = 1;

while (i <= 100) do

set goods_name = concat('商品',i);

insert into goods_extend (id, goods_id, goods_name) values (i, i, concat('商品',i));

set i=i+1;

end while;

end;;

delimiter ;

call insert_goods_extend_data();

执行过程分析

有了上面的数据，我们就可以对 join 命令的执行过程进行分析了。

一般情况下，我们查看 MYSQL 执行过程都是通过 explain，explain 提供了 MYSQL 如何执行查询语句的信息。

为了更直观的展示，我们使用 straight_join 强制使用 goods_extend 表作为驱动表。

mysql> explain select * from goods_extend straight_join goods on goods.goods_id = goods_extend.goods_id;
+----+-------------+--------------+------------+------+---------------+--------------+---------+--------------------------------+------+----------+-------+
| id | select_type | table        | partitions | type | possible_keys | key          | key_len | ref                            | rows | filtered | Extra |
+----+-------------+--------------+------------+------+---------------+--------------+---------+--------------------------------+------+----------+-------+
|  1 | SIMPLE      | goods_extend | NULL       | ALL  | idx_goods_id  | NULL         | NULL    | NULL                           |  100 |   100.00 | NULL  |
|  1 | SIMPLE      | goods        | NULL       | ref  | idx_goods_id  | idx_goods_id | 4       | example2.goods_extend.goods_id |    1 |   100.00 | NULL  |
+----+-------------+--------------+------------+------+---------------+--------------+---------+--------------------------------+------+----------+-------+
2 rows in set, 1 warning (0.00 sec)

从上面可以看出，驱动表 goods_extend 查询的是全表，被驱动表 goods 的查询类型为 ref，之前我们有在 mysql explain 详解讲过，type 为 ref 的情形是 join 连接，命中 普通索引。从上面的语句我们还可以看到，goods 表扫描的行数为 1，这也正好对应着 ref 的 等值连接 特性，说明是一行一行查询的。

因此，这条查询语句的执行过程是这样的：

从表 goods_extend 中读取一行数据 R；
从数据行 R 中取出字段 goods_id 并到 goods 表里去查找。
取出表 goods 表中满足条件的行，和 R 组成一行，作为结果集的一部分；
重复执行步骤 1 到 3，直到表 goods_extend 的末尾循环结束。

这个过程是先遍历表 goods_extend，然后根据从表 goods_extend 中取出的每行数据中的 goods_id 值，去表 goods 中查找满足条件的记录。在形式上，这个过程跟我们写程序时的嵌套查询类似。

实际上，这正是 MYSQL 内部执行表之间连接的算法。MYSQL 使用嵌套循环算法，或者是在嵌套循环算法之上优化、变体的算法来执行表之间的连接。

Nested-Loop Join 算法

NLJ 算法是一种简单的嵌套循环连接算法。该算法每次从外面的循环中的表读取行，并将每行传递给内层循环中，用于处理该层循环中的表。

假设有三个表 t1，t2，t3 要进行连接，连接类型如下：

Table   Join Type
t1      range
t2      ref
t3      ALL

如果使用了一个简单的 NLJ 算法，连接过程可能如下：

for each row in t1 matching range {
  for each row in t2 matching reference key {
    for each row in t3 {
      if row satisfies join conditions, send to client
    }
  }
}

上面的例子呢，因为我们用上了被驱动表的索引，所以我们称之为“Index Nested-Loop Join”。

它对应的流程如下图所示：

在这个流程中：

我们对驱动表 goods_extend 做了全表扫描，这个过程总共扫描了 100 行。
对于每一行 R，需要根据 goods_id 字段去 goods 表查找，走的是树搜索过程。因为我们构造的数据都是一一对应的，每次扫描的过程都是一行，总共扫描 100 行。
所以整个执行过程共扫描 200 行。

问题解答

现在的话，我们再来看一下之前提的问题：能不能用 join？

假设我们不用 join，那我们就只能单表查询。具体的实现为：

执行 select * from goods_extend，查出表 goods_extend 的所有数据，共 100 行。
循环遍历 100 行数据：
1. 从每一行 R 中取出字段 goods_id 的值 R.goods_id；
2. 执行 select * from goods where goods_id = R.goods_id；
3. 把返回的结果和 R 构成结果集的一行。

可以看到，在这个查询过程中，也是扫描了 200 行，但是总共执行了 100+1 条语句，比直接 join 多了 100 次交互。除此之外，客户端还要自己拼接 SQL 语句和结果。

显然，这么做不如直接 join 好。

这个时候，我们可以回答了，可以使用 join。

既然可以使用 join，为什么 DBA 对 join 语句还这么抵触呢？

那么我们就来具体分析一下。

NLJ 存在的问题

我们来分析一下上述的查询请求，在上述 join 语句的执行过程中，驱动表走的是全表扫描，而被驱动表走的是树搜索。

假设被驱动表的行数是 M，走的是普通索引树搜索（比主键索引树多一次回表操作）。每次在被驱动表中查询一行数据，需要先搜索普通索引 idx，然后再搜索主键索引。每次搜索一棵树近似复杂度是以 2 为底的 M 的对数，记为 log2(M)，所以在被驱动表上查一行的时间复杂度是 2*log2(M)。

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

因此整个执行过程，近似复杂度是 N + N2log2(M)。

我们可以看到 N 对结果的影响非常大。N 是什么呢，N 是驱动表的行数，所以说，日常查询使用 join 虽然比不使用 join 要好，但是我们应该要会用 join，才能让 join 请求速度更快，性能更好。

到这里我们得出了两个结论：

使用 JOIN，性能比强行拆成多个单表执行 SQL 语句的性能要好。
驱动表时全表扫描，因此应该选择小表作为驱动表。

Simple Nested-Loop Join

我们想一想使用 JOIN 是否还有什么潜在的问题（限制）。

上面的请求中，我们使用了索引 goods_id，所以被驱动表一次访问一行就能够获取到数据。

如果连接的字段没有索引呢，比如下面的请求：

select * from goods_extend straight_join goods on goods_extend.goods_name = goods.goods_name;

goods 表中 goods_name 没有索引，所以要走全表扫描，总共有 1000 行，因此总共要扫描 100 * 1000 次。

mysql> explain select * from goods_extend straight_join goods on goods_extend.goods_name = goods.goods_name;
+----+-------------+--------------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
| id | select_type | table        | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                      |
+----+-------------+--------------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
|  1 | SIMPLE      | goods_extend | NULL       | ALL  | NULL          | NULL | NULL    | NULL |  100 |   100.00 | NULL                                       |
|  1 | SIMPLE      | goods        | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 1000 |    10.00 | Using where; Using join buffer (Block Nested Loop) |
+----+-------------+--------------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
2 rows in set, 1 warning (0.00 sec)

事实上，这是另外一个算法，叫做 Simple Nested-Loop Join。看起来和 NLJ 算法一样，但是由于没有走索引，导致算法太笨重了。

当然 MYSQL 也没有使用 Simple Nested-Loop Join 算法。这点我们可以很清楚的意识到，假设有两张表做 JOIN 操作，每张表有 100 万条数据。这两张表应该算是小表（按照实际生产环境来看），但是如果没有索引，使用 Simple Nested-Loop Join 算法来进行 JOIN 的话，就要扫描 100万 * 100万 = 10000亿行了，这可不得了了。

BNL（Block Nested-Loop Join）

那么 MYSQL 如何处理这种无索引的 JOIN 操作呢。

事实上，MYSQL 采用另外一种叫做 Block Nested-Loop Join 的算法来处理无索引 JOIN 操作。

BNL（块嵌套循环）通过缓存外部循环中读取的行来减少必须读取内部循环中的表的次数。

例如，如果将外部表中的 10 行放入缓存区中并传递到内部循环中，那么就可以将内部循环中读取的每一行与缓存区中的 10 行进行比较。

该操作能将内部表读取次数减少一个数量级。

该算法的执行流程如下：

for each row in t1 matching range {
  for each row in t2 matching reference key {
    store used columns from t1, t2 in join buffer
    if buffer is full {
      for each row in t3 {
        for each t1, t2 combination in join buffer {
          if row satisfies join conditions, send to client
        }
      }
      empty join buffer
    }
  }
}

if buffer is not empty {
  for each row in t3 {
    for each t1, t2 combination in join buffer {
      if row satisfies join conditions, send to client
    }
  }
}

注意：从 MYSQL 8.0.20 开始，MYSQL 不再使用块嵌套循环，并且在以前使用过嵌套循环的所有情况都使用 hash join

我们再来看一下上面的请求：

mysql> explain select * from goods_extend straight_join goods on goods_extend.goods_name = goods.goods_name;
+----+-------------+--------------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
| id | select_type | table        | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                      |
+----+-------------+--------------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
|  1 | SIMPLE      | goods_extend | NULL       | ALL  | NULL          | NULL | NULL    | NULL |  100 |   100.00 | NULL                                       |
|  1 | SIMPLE      | goods        | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 1000 |    10.00 | Using where; Using join buffer (Block Nested Loop) |
+----+-------------+--------------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
2 rows in set, 1 warning (0.00 sec)

该算法请求流程如下：

把表 goods_extend 表中的数据读入缓冲区 join_buffer 中，由于我们这个语句写的是 select * ，因此要把整个表 goods_extend 放入到内存中。
扫描表 goods，把表 goods 中的每行取出来，和 join_buffer 中的数据进行对比，满足 join 条件的，作为结果集的一部分返回。

同 simple NLJ 比较

那么为什么 BNL 会比 Simple Nested-Loop Join 快呢？

我们来分析一下，在这个过程中，对表 goods 和 goods_extend 都做了一次全表扫描，因此总的扫描行数是 1100。由于 join_buffer 是以无序数组的方式组织的，因此对表 goods 的每一行，都要做 100 次判断，总共要判断的次数是：100 * 1000 = 10 万次。

前面我们也看到了，使用 Simple Nested-Loop Join 算法进行查询，扫描的行数是 10 万行。因此，从时间复杂度的角度来看，这两个算法是一样的。但是 BNL 算法的这 10 万次判断是在内存中操作，所以速度会更快，性能会更好。

有些人看到这块，可能又有疑惑了，Simple NLJ 也是在内存中比较的啊，而且都是比较了 10 万次，为什么 BNL 会更快呢？

是因为 MYSQL 在对被驱动表做全表扫描的时候，如果数据没有在 Buffer Pool 中，就需要等待这部分数据从磁盘中读入，从磁盘中读入数据到内存中，就会影响正常业务 Buffer Pool 命中率，而且这个算法天然会对被驱动表的数据做多次访问，更容易将这些数据页放到 Buffer Pool 的头部。

而且即使被驱动表数据都在内存中，每次查找“下一个记录的操作”，都是类似指针操作。而 join_buffer 中是数组，遍历的成本更低。所以说，BNL 算法的性能会更好。

驱动表选择

我们再来看一下，这个情况下应该选择哪个表做为驱动表。

假设小表的行数是 N，大表的行数是 M，那么在这个算法里：

两个表都做一次全表扫描，所以总的扫描行数是 M+N；
内存中的判断次数是 M * N。

可以看到，调换这两个算式中的 M 和 N 没差别，因此这个时候选择大表还是小表做驱动表，执行耗时是一样的。

这个时候，你可能有另外一个疑问了，缓冲区 join_buffer 放不下驱动表的全部数据怎么办？

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

假设我们的 join_buffer 只能放入 80 行数据，而我们的 goods_extend 表有 100 行数据，执行过程则为：

扫描表 goods_extend，顺序读取数据行放入 join_buffer 中，放完 80 行 join_buffer 满了，执行第 2 步。
扫描表 goods，把表 goods 中的每一行取出来，跟 join_buffer 中的数据做对比，满足 join 条件的，作为结果集的一部分返回。
清空 join_buffer；
继续扫描表 goods_extend，顺序读取剩下的 20 行数据放入 join_buffer 中，继续执行第二步；

执行流程图也就变成了这样：

图中的步骤 4 和 5 表示清空 join_buffer 再复用。

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

可以看到，这时候由于表 goods_extend 被分成了两次放入 join_buffer 中，导致表 goods 会被扫描两次，虽然分成两次放入 join_buffer，但是判断等值条件的次数还是不变的，依然是（80 + 20）* 1000 = 10 万次。

我们再来看一下，在这种情况下驱动表的选择问题。

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

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

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

扫描行数是 N + α N M；
内存判断 N * M 次。

显然，内存判断次数是不受选择哪个表作为驱动表影响的。而考虑到扫描行数，在 M 和 N 大小确定的情况下，N 小一些，整个算式的结果会更小。

所以结论是，应该选择小表作为驱动表。

另外，我们也可以发现，在 N + α N M 这个算式中，α 才是影响扫描行数的关键因素，这个值越小越好。

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

这就是为什么，你可能会看到一些建议告诉你，如果你的 join 语句很慢，就把 join_buffer_size 改大。

hash join

我们上文也提到了，从MySQL 8.0.18 开始，MySQL 对任何查询都具有相等连接条件且不使用索引的查询使用哈希连接。

比如上面 BNL 的例子，我们在 MYSQL 8 下执行，执行的结果如下：

mysql> explain select * from goods_extend straight_join goods on goods_extend.goods_name = goods.goods_name;
+----+-------------+--------------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
| id | select_type | table        | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                      |
+----+-------------+--------------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
|  1 | SIMPLE      | goods_extend | NULL       | ALL  | NULL          | NULL | NULL    | NULL |  100 |   100.00 | NULL                                       |
|  1 | SIMPLE      | goods        | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 1000 |    10.00 | Using where; Using join buffer (hash join) |
+----+-------------+--------------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
2 rows in set, 1 warning (0.00 sec)

从 Extra 字段可以看到 Using join buffer (hash join)，这说明使用的哈希链接。

小表

我们现在再来看一下，什么是小表。

上述情况我们的小表都是 goods_extend，那么表行数少的表就是小表吗？

我们来看一下下面的这个例子：

mysql> select * from goods_extend straight_join goods on goods_extend.goods_name = goods.goods_name where goods.goods_id <= 50;

mysql> select * from goods straight_join goods_extend on goods_extend.goods_name = goods.goods_name where goods.goods_id <= 50;

注意：为了让两条语句的被驱动表都用不上索引，所以 join 字段都使用了没有索引的字段 goods_name。

相比于第一个语句，第二个语句 join_buffer 只需要放入 goods 表的前 50 行，显然是更好的。所以这里的 “goods 的前 50 行” 是那个相对小的表，也就是“小表”。

我们再来看另外一组例子：

mysql> select goods_extend.goods_name, goods.* from goods_extend straight_join goods on (goods_extend.goods_name = goods.goods_name) where goods.id <= 100;

mysql> select goods_extend.goods_name, goods.* from goods straight_join goods_extend on (goods_extend.goods_name = goods.goods_name) where goods.id <= 100;

这个例子中，表 goods_extend 和 goods 都是只有 100 行参加 join，但是这两条语句每次查询放入 join_buffer 中的数据是不一样的：

表 goods_extend 只查字段 goods_name，因此如果把 goods_extend 放入到 join_buffer 中只需要放入 goods_name 的值；
表 goods 需要查询所有的字段，因此如果把表 goods 放入到 join_buffer 中的话，就需要放入所有字段。

因此，在上述查询中我们应该选择 goods_extend 表作为驱动表，也就是说，“只需要一列参与 join 的表” 是哪个相对小的表。

因此，在决定哪个表作为驱动表的时候，应该是两个表按照各自的条件过滤，过滤完成之后，计算参与 join 的各个字段的总数据量，数据量小的那个表，就是“小表”，应该作为驱动表。

总结

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

大家看完有什么不懂的可以在下方留言讨论也可以关注.

谢谢你的观看。

觉得文章对你有帮助的话记得关注我点个赞支持一下！

链接：https://juejin.im/post/6861855202913058829