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

Mysql实战-Join算法底层原理

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

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

1. 简单嵌套循环连接 SNL （ Simple Nested-Loop Join）
2. 块嵌套循环连接 INL（ Block Nested-Loop Join）
3. 索引嵌套循环连接 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
1

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

for(User u: User){
    for(Class c: Class){
        if(u.id == c.userId){
        //     得到匹配数据
        }
    }
}
1
2
3
4
5
6
7

可以用下面的图来简单的解释一下

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

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

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

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

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

查询结果

那么我们的 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
1
2
3
4

查询过程分析

• 首先扫描 驱动表，然后读取一定长度的数据存储到 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

我们可以用下面的图来简单介绍下 块循环的逻辑

3. Index Nested-Loop Join 索引嵌套循环连接

上面我们讲解了 块嵌套循环连接，需要把驱动表的数据加入join buffer来进行匹配，同样非常耗时，我们有其他优化方法吗？这就引出了 Index Nested-Loop Join 索引嵌套循环连接

ndex Nested-Loop Join 索引嵌套循环连接
顾名思义就是必须有索引才行，而且是驱动表上必须有索引，通过使用索引减少扫描的次数来提高查询效率的

我们给驱动表 需要连接的列加上索引，这样匹配的过程就会非常的快

• 首先 驱动表会根据关联字段的索引进行查询，当索引是否命中数据，直接进行回表查询该条记录
• 驱动表会根据关联字段的索引进行查询，当索引上找到符合的值，才会进行回表查询
• 如果非驱动表的关联字段是主键的话，查询效率非常高(主键索引结构的叶子结点包含了完整的行数据)，
• 非驱动表的关联字段如果不是主键，每次匹配到索引后都需要进行一次回表查询，性能弱于主键的查询

索引嵌套循环连接用可以用下面的图来简单描述

---

至此，我们彻底的了解了 join算法的底层原理，也明确直到了三种方法的优劣，有助于我们再分析索引的时候，更快的定位出问题，进行索引优化