本文正在参与「金石计划」

JOIN是一种十分常见的操作，用于将两个或多个表中的数据合并到一个成果集中。

MySQL JOIN类型

MySQL支撑多种JOIN类型，下面是每种JOIN类型的简要概述:

INNER JOIN：将两个表中契合条件的行组合在一起。回来的成果集只包含满意衔接条件的行，即两个表中都存在的行。一般简写成JOIN
LEFT JOIN：回来左表中的一切行以及契合条件的右表中的行。假如右表中没有匹配的行，则用NULL填充。
RIGHT JOIN：回来右表中的一切行以及契合条件的左表中的行。假如左表中没有匹配的行，则用NULL填充
FULL OUTER JOIN：回来左表和右表中的一切行，假如一个表中没有匹配的行，则用NULL填充。
CROSS JOIN：回来两个表中的一切或许的组合，也称为笛卡尔积。

`MySQL JOIN` 算法

在了解完 MySQL JOIN类型概念之后，咱们来了解 MySQL JOIN 算法，在之前的版别只支撑Nested Loop Join这一种算法，在 MySQL 8.0.18之后支撑 Hash Join算法。

`Nested-Loop Join` 算法

履行流程

假定两个表一个 user 用户表，一个 order 订单表，需求查询用户的一切订单信息，表结构如下:

CREATE TABLE `user` (
  `id` int(11) NOT NULL COMMENT '主键id',
  `name` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT '用户称号',
  `age` int(255) DEFAULT NULL COMMENT '年龄',
  `user_code` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT '用户编号',
  PRIMARY KEY (`id`),
  KEY `idx_user_code` (`user_code`) USING BTREE COMMENT '用户编号索引'
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='用户表';
CREATE TABLE `order` (
  `id` int(11) NOT NULL AUTO_INCREMENT COMMENT '主键id',
  `order_name` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT '订单称号',
  `user_code` varchar(11) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT '用户编号',
  PRIMARY KEY (`id`),
  KEY `idx_user_code` (`user_code`) USING BTREE COMMENT '用户编号索引'
) ENGINE=InnoDB AUTO_INCREMENT=10 DEFAULT CHARSET=utf8 COMMENT='订单表';

其间 user_code是衔接字段，也是索引。SQL 如下：

mysql> SELECT
	u.`name`,
	u.user_code,
	o.order_name 
FROM
	`user` u
	JOIN `order` o ON u.user_code = o.user_code;
+------+-----------+------------+
| name | user_code | order_name |
+------+-----------+------------+
| 李   | 002       | 订单1      |
| 李   | 002       | 订单2      |
| 李   | 002       | 订单3      |
| 李   | 002       | 订单4      |
| 李   | 002       | 订单5      |
| 李   | 002       | 订单6      |
| 李   | 002       | 订单7      |
| 李   | 002       | 订单8      |
| 李   | 002       | 订单9      |
+------+-----------+------------+
9 rows in set (0.08 sec)

看一下这条句子的explain成果

这个句子的履行流程如下：

从表order中读入一行数据；
从数据行中，取出user_code字段到表user里去查找；
user表根据索引找到满意条件的行字段，跟上面的数据行组成一行；
重复履行步骤1到3，直到表user的结尾循环结束。

作业原理

这个进程就跟咱们写程序时的嵌套查询，一般称为Nested-Loop Join (NLJ)，是一种最基本的Join算法，它经过对两个表进行嵌套循环来查找匹配的行。具体来说，它从一个表中取出一行，然后在另一个表中扫描一切行，查找与之匹配的行。类似于这样:

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
    }
  }
}

时刻复杂度剖析

这个进程将会对每一行进行一次比较，因而它的时刻复杂度为： $O (m * n)$ ，其间 m 和 n 分别是两个表的行数。

假定被驱动表的行数是M。每次在被驱动表查一行数据，要先搜索索引a，再搜索主键索引。每次搜索一棵树近似复杂度是 $l o g M$ ，所以在被驱动表上查一行的时刻复杂度是 $2 * l o g M$ 。

假定驱动表的行数是N，履行进程就要扫描驱动表N行，然后关于每一行，到被驱动表上匹配一次。因而整个履行进程，近似复杂度是 $N + N * 2 * l o g M$ 。 N对扫描行数的影响更大，因而应该让小表来做驱动表。关于大型数据集来说，它的功能会变得十分慢，由于它需求对一个表的每一行都扫描另一个表。

`Block Nested-Loop Join` 算法

履行流程

接下来，咱们删除去索引，再看看被驱动表用不上索引的状况

ALTER TABLE `user` DROP INDEX `idx_user_code`;
EXPLAIN SELECT
	u.`name`,
	u.user_code,
	o.order_name 
FROM
	`user` u
	JOIN `order` o ON u.user_code = o.user_code

再看一下这条句子的explain成果,多了一个 Using join buffer (Block Nested Loop)

这个时分句子的履行流程如下：

从表user中读入name，user_code字段数据放到线程内存join_buffer中
扫描表order表，把表order中的每一行取出来，跟join_buffer中的数据做比照，满意join条件的，作为成果集的一部分回来。

作业原理

Join Buffer是一种内存缓存，并在查询完成后释放,它能够在履行时缓存Join的中心成果。join_buffer 的巨细是由参数join_buffer_size设定的，默认值是256k。

mysql> show variables like '%join_buffer_size%';
+------------------+---------+
| Variable_name    | Value   |
+------------------+---------+
| join_buffer_size | 1048576 |
+------------------+---------+
1 row in set (0.10 sec)

那假如Join Buffer中放不下表user的一切数据话会怎样处理呢？ 策略很简单，便是分段，每次清空join_buffer；

for each row in t1 matching range {
    store used columns from t1 in join buffer
    ## 假如buffer满了
	if buffer is full {
      for each row in t2 {
        for each t1 combination in join buffer {
		  ## 假如行满意衔接条件，则发送到客户端
          if row satisfies join conditions, send to client
        }
      }
	  ## 清空buffer
      empty join buffer
    }
}
if buffer is not empty {
  for each row in t2 {
    for each t1 combination in join buffer {
      if row satisfies join conditions, send to client
    }
  }
}

时刻复杂度剖析

能够看到，在这个进程中，对表user和order都做了一次全表扫描。因而它的时刻复杂度为： $O (M + N)$ 。由于join_buffer是以无序数组的方法组织的，因而对表order中的每一行，都要做判别。假定小表的行数是N，大表的行数是M，那么在这个算法里：

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

Block Nested-Loop Join(BNL)是一种优化的NLJ算法，BNL 经过将一个表分成多个块（block），然后逐个块与另一个表进行Join操作，然后削减了不必要的重复扫描和比较。它能够进步NLJ在处理大数据集时的功能,可是会占用过多的CPU资源。会屡次扫描被驱动表，占用磁盘IO资源。

`Hash Join` 算法

Beginning with MySQL 8.0.20, support for block nested loop is removed, and the server employs a hash join wherever a block nested loop would have been used previously.(dev.mysql.com/doc/refman/…)

从 MySQL 8.0.20 开端，删除了BNL算法，运用了Hash Join 算法代替。

履行流程

咱们以下面官方比如为准：

SELECT
	given_name,country_name 
FROMpersons
JOIN countries 
ON persons.country_id = countries.country_id;

hash join 分为两个阶段; build 构建阶段和 probe 勘探阶段。

`build` 构建

在构建阶段，MySQL运用Join字段作为哈希表Key，在内存中构建Hash 表。

正常状况MySQL会选择成果集较小（以字节为单位，而不是行数）的去构建。比如上面会对 countries.country_id 进行 hash 核算：hash(countries.country_id) 然后将值放入内存中 hash table 的相应方位。将一切行存储在哈希表中后，构建阶段就完成了。

`probe` 勘探阶段

在勘探阶段，MySQL逐行遍历被驱动表，然后核算join条件的hash值，并在hash表中查找，假如匹配，则输出给客户端，否则跳过。一切内表记载遍历完，则整个进程就结束了。

比如上面遍历persons 表中每行数据，然后取出Join字段的值进行 hash 核算；hash(persons.country_id)，然后去内存中 hash table 中进行查找，匹配成功会发送给客户端。

内存中hash表的巨细是由参数join_buffer_size 操控的，可是，假如构建hash table 内存大于可用内存，会发生什么状况？

当内存在build构建阶段变满时，服务器会将其他的构建写入磁盘上的多个文件中。同时会设置文件的数量，确保最大的文件的巨细与join_buffer_size共同。

每行数据写入哪个块文件是经过核算 join 特点的哈希来确认的。请注意，在下图中，运用的哈希函数与内存中生成阶段运用的哈希函数不同。咱们稍后会理解为什么

在勘探阶段，服务器关于persons 表每一行数据运用相同的hash算法进行分区。这样，咱们就能够确认两个输入之间的匹配行将坐落同一对文件中。

勘探阶段完成后，开端从磁盘读取文件。首先会将build构建阶段的第一个文件，也便是下图中的左面的文件，加载到内存中哈希表中。这就解释了为什么期望最大的文件巨细与内存共同，接着读取在勘探阶段生成的文件，下图中右边的文件，在内存哈希表中进行匹配，就像之前内存操作一样。处理第一个文件后，移动到下一块文件，持续，直到处理完一切文件。

到这里也理解了，假如咱们对两个操作运用相同的哈希函数，那么在将构建文件加载到哈希表中时，咱们会得到一个十分糟糕的哈希表，由于同一个文件中的一切行都将哈希为相同的值。

如何运用

在MySQL 8.0.20之前，运用 EXPLAIN FORMAT=tree 来查看是否将运用Hash Join算法。

mysql> EXPLAIN   FORMAT=tree  SELECT
	u.`name`,
	u.user_code,
	o.order_name 
FROM
	`user` u
	JOIN `order` o ON u.user_code = o.user_code;
+-------------------------------------------------------------+
| EXPLAIN                                                           
+-------------------------------------------------+
| -> Inner hash join (u.user_code = o.user_code)  (cost=7.50 rows=7)
    -> Table scan on o  (cost=0.05 rows=9)
    -> Hash
        -> Table scan on u  (cost=0.95 rows=7)
+-----------------------------------------------------------+
1 row in set (0.04 sec)

时刻复杂度剖析

全体上对驱动表遍历1次(驱动表有M行记载)，被驱动表遍历1次(被驱动表有N行记载)。因而它的时刻复杂度为： $O (M + N)$ 。它一般比嵌套循环算法(NLJ)更有用，尤其是在其间一个成果集能够完全放入join_buffer内存的状况下。

`MySQL JOIN` 优化

NLJ算法优化

为了优化Nested-Loop Join的功能，尽或许削减 Join 句子中的 Nested Loop 的循环总次数，便是让驱动表的成果集尽或许的小。关于很多表的相关经过应用层拆分成多个句子然后再拼接查询成果更便利，而且功能也不会差。

在join的时分清晰知道哪张表是小表的时分,能够用straight_join写法固定衔接驱动方法

BNL算法优化

运用Block Nested-Loop Join(BNL)算法时，或许会对被驱动表做屡次扫描,占用磁盘IO资源，并且需求履行 $M * N$ 次比照可是会占用过多的CPU资源。

优化的常见做法是，给被驱动表的join字段加上索引，把BNL算法转成NLJ算法。

无法设置索引的状况能够经过设置join_buffer_size参数来操控Join Buffer的巨细，以削减分段查询次数

`Hash Join`算法优化

Hash Join算法在从 MySQL 8.0.18 以后才会用到，也是为了代替上面的BNJ算法。

当哈希表所需的内存量超越join_buffer_size巨细，会运用磁盘的文件进行处理，所以增加 join_buffer_size值避免生成文件能够极大提高查询速度。

参考

MySQL :: Hash join in MySQL 8
MySQL :: MySQL 8.0 Reference Manual :: 8.2.1.4 Hash Join Optimization
MySQL :: MySQL 8.0 Reference Manual :: 8.2.1.7 Nested-Loop Join Algorithms
MySQL 实战 45 讲

一文详解MySQL——Join的使用优化

MySQL JOIN类型

`MySQL JOIN` 算法

`Nested-Loop Join` 算法

履行流程

作业原理

时刻复杂度剖析

`Block Nested-Loop Join` 算法

履行流程

作业原理

时刻复杂度剖析

`Hash Join` 算法

履行流程

`build` 构建

`probe` 勘探阶段

如何运用

时刻复杂度剖析

`MySQL JOIN` 优化

NLJ算法优化

BNL算法优化

`Hash Join`算法优化

参考

作者信息

推广

一文详解MySQL——Join的使用优化

MySQL JOIN类型

MySQL JOIN 算法

Nested-Loop Join 算法

履行流程

作业原理

时刻复杂度剖析

Block Nested-Loop Join 算法

履行流程

作业原理

时刻复杂度剖析

Hash Join 算法

履行流程

build 构建

probe 勘探阶段

如何运用

时刻复杂度剖析

MySQL JOIN 优化

NLJ算法优化

BNL算法优化

Hash Join算法优化

参考

相关文章

对比PyTorch、TensorFlow、JAX、Theano，我发现都在关注两大问题

Objective-C Runtime 开发

商汤 ChatGPT「商量」炸场！秒生 6K 神图，代码提速 62%，现场直播怼脸

2023 re:Invent 用 Amazon Q 打造你的知识库

作者信息

推广

`MySQL JOIN` 算法

`Nested-Loop Join` 算法

`Block Nested-Loop Join` 算法

`Hash Join` 算法

`build` 构建

`probe` 勘探阶段

`MySQL JOIN` 优化

`Hash Join`算法优化