MSQL系列(九) Mysql实战-Join算法底层原理-Toy模板网

这篇具有很好参考价值的文章主要介绍了MSQL系列(九) Mysql实战-Join算法底层原理。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Mysql实战-Join算法底层原理

前面我们讲解了B+Tree的索引结构，及Mysql的存储引擎MyISAM和InnoDB,今天我们来详细讲解下Mysql的查询连接Join的算法原理

Join算法分类
在Mysql的查询过程中，我们都知道涉及多表查询，我们都会使用join来连接多个表进行查询，join的本质就是循环每个表进行匹配，join算法可以分为三种形式

简单嵌套循环连接 SNL （ Simple Nested-Loop Join）
块嵌套循环连接 INL（ Block Nested-Loop Join）
索引嵌套循环连接 INL（ Index Nested-Loop Join）

1.Simple Nested-Loop Join 简单嵌套循环

Simple Nested-Loop join(NLJ)算法

比较简单粗暴，就是通过双层循环比较数据来获取查询结果
从循环中的第一个表中一次读取一行，将每一行传递给一个嵌套循环，判断嵌套循环中匹配数据是否一致

假如两个表，每个表都有1W条数据，那么数据对比次数就是 1w*1w=1亿次，每一次扫描其实就是从硬盘中读取数据加载到内存中,也就是一次IO，目前IO是最大的瓶颈, 查询效率相当的慢

例如驱动表用户表User, 被驱动表class课程表

select * from User u left join  class c on u.id = c.user_id

相当于写了一个for循环来执行查询逻辑，伪代码可以看作

for(User u: User){
    for(Class c: Class){
        if(u.id == c.userId){
        //     得到匹配数据
        }
    }
}

可以用下面的图来简单的解释一下
MSQL系列(九) Mysql实战-Join算法底层原理,Mysql实战,mysql,join算法,Nested loop 算法,Mysql的join算法,Nested loop实现

2.Block Nested-Loop Join 块嵌套循环连接

我们知道上面的简单嵌套循环效率很低是因为他必须扫描取每一条数据，者提供是非常耗时的，所以我们为啥不能多取一点呢？

Block Nested-Loop Join 块嵌套循环连接
不再是每条每条的取，而是每次都从驱动表每次取一批数据，放到内存中，然后对这一批数据进行匹配操作，当数据操作匹配完毕，就再次从驱动表中取一批数据放到内存中，再次比较，直到数据匹配完毕，完成查询，这种方式就是 块嵌套循环连接

Mysql中对这块内存有一个专门的名词就是 join buffer，我们可以通过执行

#查看join buffer大小
show variables like '%join_buffer%'

查询结果
MSQL系列(九) Mysql实战-Join算法底层原理,Mysql实战,mysql,join算法,Nested loop 算法,Mysql的join算法,Nested loop实现
那么我们的 Join Buffer有这么一个内存空间，这里面到底存储的是什么东西呢？假如我们查询2个表 a表和b表, 这里用到了

a表的 col1列，col2列，col3列
b表的 col1列和 col2列

查询语句如下

select a.col1 from a
left join b 
on a.col2= b.col1
where a.col3 > 0 and b.col2 >0

查询过程分析

首先扫描驱动表，然后读取一定长度的数据存储到 join buffer中
join buffer中存储的不是驱动表的整行记录
join buffer中只会放驱动表参与查询的列，也就是a表的 col1列，col2列，col3列
查询的字段越少，join buffer存放的记录越多
一次存放的记录越多，I/O查询的次数就越少，效率就越高
对于 join buffer的大小，我们可以通过设置去优化设置为1M 命令 set session join_buffer_size = 1024*1024 * 1024

我们可以用下面的图来简单介绍下块循环的逻辑
MSQL系列(九) Mysql实战-Join算法底层原理,Mysql实战,mysql,join算法,Nested loop 算法,Mysql的join算法,Nested loop实现