Mysql join 算法原理

小咪咪 2022-12-02 01:08 67阅读 0赞

优先看原文哟：[https://zhuanlan.zhihu.com/p/54275505][https_zhuanlan.zhihu.com_p_54275505]

了解join 算法原理之前你可能还需要了解：

mysql索引原理：[勤劳的小手：平衡二叉树、B树、B+树、B\*树 理解其中一种你就都明白了][B_B_B_]

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

简单来说嵌套循环连接算法就是一个双层for 循环 ，通过循环外层表的行数据，逐个与内层表的所有行数据进行比较来获取结果，当执行select \* from user tb1 left join level tb2 on tb1.id=tb2.user\_id

时，我们会按类似下面代码的思路进行数据匹配：

![format_png][]

**整个匹配过程会如下图：**

![format_png 1][]

**特点：**

Nested-Loop Join 简单粗暴容易理解，就是通过双层循环比较数据来获得结果，但是这种算法显然太过于粗鲁，如果每个表有1万条数据，那么对数据比较的次数=1万 \* 1万 =1亿次，很显然这种查询效率会非常慢。

当然mysql 肯定不会这么粗暴的去进行表的连接，所以就出现了后面的两种对Nested-Loop Join 优化算法，在执行join 查询时mysql 会根据情况选择 后面的两种优join优化算法的一种进行join查询。

## **Index Nested-Loop Join（索引嵌套循环连接）** ##

Index Nested-Loop Join其优化的思路 主要是为了减少内层表数据的匹配次数， 简单来说Index Nested-Loop Join 就是通过外层表匹配条件 直接与内层表索引进行匹配，避免和内层表的每条记录去进行比较， 这样极大的减少了对内层表的匹配次数，从原来的匹配次数=外层表行数 \* 内层表行数,变成了 外层表的行数 \* 内层表索引的高度，极大的提升了 join的性能。

**案例：**

如SQL：select \* from user tb1 left join level tb2 on tb1.id=tb2.user\_id

当level 表的 user\_id 为索引的时候执行过程会如下图：

![format_png 2][]

**注意：使用Index Nested-Loop Join** **算法的前提是匹配的字段必须建立了索引。**

**Block Nested-Loop Join（缓存块嵌套循环连接）**

**Block Nested-Loop Join** 其优化思路是减少外层表的循环次数，**Block Nested-Loop Join** 通过一次性缓存多条数据，把参与查询的列缓存到join buffer 里，,然后拿join buffer里的数据批量与内层表的数据进行匹配，从而减少了外层循环的次数，当我们不使用**Index Nested-Loop Join**的时候，默认使用的是**Block Nested-Loop Join**。

**案例：**

如SQL：select \* from user tb1 left join level tb2 on tb1.id=tb2.user\_id

当level 表的 user\_id 不为索引的时候执行过程会如下图：

![format_png 3][]

**注意：**

1、使用**Block Nested-Loop Join** 算法需要[开启优化器管理配置的optimizer\_switch的设置block\_nested\_loop为on ][optimizer_switch_block_nested_loop_on]默认为开启，如果关闭则使用Simple Nested-Loop Join 算法；

通过指令：Show variables like 'optimizer\_switc%'; 查看配置

![format_png 4][]

2、设置join buffer 的大小

通过join\_buffer\_size参数可设置join buffer的大小

指令：Show variables like 'join\_buffer\_size%';

![format_png 5][]

## **Join 算法总结** ##

不论是Index Nested-Loop Join 还是 Block Nested-Loop Join 都是在Simple Nested-Loop Join

的算法的基础上 减少嵌套的循环次数， 不同的是 Index Nested-Loop Join 是通过索引的机制减少内层表的循环次数，Block Nested-Loop Join 是通过一次缓存多条数据批量匹配的方式来减少外层表的循环次数，通过 理解join 的算法原理我们可以得出以下表连接查询的优化思路。

1、永远用小结果集驱动大结果集(其本质就是减少外层循环的数据数量)

2、为匹配的条件增加索引(减少内层表的循环次数)

3、增大join buffer size的大小（一次缓存的数据越多，那么外层表循环的次数就越少）

4、减少不必要的字段查询（字段越少，join buffer 所缓存的数据就越多，外层表的循环次数就越少）

[https_zhuanlan.zhihu.com_p_54275505]: https://zhuanlan.zhihu.com/p/54275505
[B_B_B_]: https://zhuanlan.zhihu.com/p/27700617
[format_png]: /images/20221123/3e1282054fd1401aaae5631d996d967f.png
[format_png 1]: /images/20221123/389af18ea8484327823334d1b0ee1220.png
[format_png 2]: /images/20221123/8212f89e333f441aaf695a03a67ebc36.png
[format_png 3]: /images/20221123/1b79b1fdeefc49b2b46d79a4910103bc.png
[optimizer_switch_block_nested_loop_on]: https://link.zhihu.com/?target=https%3A//link.juejin.im/%3Ftarget%3Dhttp%3A//click.aliyun.com/m/40952/
[format_png 4]: /images/20221123/e64fad29693a43d79bd709084f0008ef.png
[format_png 5]: /images/20221123/75bda12f742b4b3cb389ca4bf4a421fc.png