MySQL Join原理分析(缓冲块嵌套与索引嵌套循环)

场景假设

A表(1000条数据)left join B表(1000条数据)。

嵌套循环(Nested-Loop Join)

  • 极简概括:顾名思义多层循环叠加,由于MySQL条数数量有限,所用for循环而不用while,在MySQL中就是多层for循环。
  • 性能问题:MySQL使用这种作为join方式最简单,A表joinB表每次join查询都需要一百万次内部关联,每次关联都需要取一条数据,进行一次IO,若要再关联C表的1000条,得10亿次内部查询,每个表的数量不过1k,因此需要优化算法。
  • 附加概念
    • 外层循环:从外表中选择一行。
    • 内层循环:对于一行外表的一次循环,MySQL会在内表中逐行搜索匹配的行。

缓冲块

  • 极简概括:缓冲块指的是内存中的数据块,当数据库进行读取或写入操作时,通常会将数据加载到缓冲块中进行处理,以减少对磁盘的访问频率,类比开发中的Redis的作用。

缓冲款嵌套循环(Block Nested-Loop Join)

  • 极简概括:取出一批数据放入内存中,再对这一批数据进行匹配操作,分批处理(若放不下)+内存的性能优势,能减少io操作。
  • 补充:这块内存有个专业的名词,叫做join buffer,使用show variables like 'join_buffer%'便可查看大小(默认256KB)。可以随便找一个或者两个表试一试,将无索引的列作为join on的关系关联起来,用explain 查看Extra列,就会显示Using join buffer (Block Nested Loop)。

索引嵌套循环(Index Nested-Loop Join)

  • 前提:所被关联的列,必须有索引。
  • 原理:利用B+tree的非线性多路查找思路快速定位目标数据,定位到的数据作为主动关联(A表)或者被关联(B表)的成员,这意味着不用逐行遍历,从而提升性能。
  • 举例:A 关联 B,假设通过id字段关联,原先需要百万次的内部关联,受where条件影响(实际开发大概率会用),只查询出了50条结果。
  • 逐步剖析(包含主观推理,实际情况有待考证):
    1. 通过下文,知道SQL执行的顺序是from->join->on->where->group by->having->select->order by->limit,因此会生成一个百万级的临时表(此时还没有走到过滤或筛选操作的逐行对比流程)。
      但是也不一定,MySQL优化器会根据当前的索引和数据情况,也可能先把A或B表where后内部产生的临时表(50条),再与另一张表join,从而优化性能,(MySQL优化器为了性能,可以不按照SQL国际标准来运行,这种概率较大)。
    2. 筛选出来50条数据作为临时表,进行下游环节的处理。
    3. 分析第1步的内部行为:从下文知道1000条数据,MySQL B+tree大概率为2层,也就是50*2 = 100次IO(在树上查找),然后根据这50条数据join另一张表,由于关联字段都是加索引的id字段,所以另一张表的算法一致,另一张表也经历了100次内部IO,所以加起来是200次内部IO,也可以近似的理解为200次内部关联。

SQL执行顺序的逻辑

  1. from用于确定操作对象,放第一位毋庸置疑。
  2. join和on用于关联,后面的各种处理逻辑依附于关联后内部创建的临时表,先生成数据集,才能为后续处理做基础。
  3. where用于筛选,可以减少后续操作的数据量,提高查询性能。
  4. group by用于对数据进行分类汇总,不放where前面,是为了避免分组后的数据被where过滤掉(分组分了个寂寞),造成算力浪费和内存资源(数据量大还是很消耗算力和内存的)的问题。
  5. having用于对分组结果进行过滤,所以要在group by之后。
  6. select用于决定迭代显示那些列,而不是限制只有这些列才可以参与处理,上游的各种操作(如复杂的where条件)不能受7. select字段的影响,这也是where后面跟的字段,不必在select出现的原因。select的本意是处理数据后仅仅返回这些字段,而不是决定只有这些字段进行数据处理,所以必定要放偏后的位置。
  7. order by用于结果进行排序,肯定是结果处理后才排序的,理由和group by相似。
  8. limit用于限制返回结果的行数和偏移量,必须是等筛选完分组完拍完序之后再限制,否则可能导致结果有误。

根据表行数量评估B+tree层数算法

先排除一些元数据的存储:数据存储在页上,每页大小16KB,每页需要开辟一些新的空间来存储元数据(例如指向上一页下一页的指针),页头存储文件头38字节,页面头56字节,最小记录和最大记录26个字节,为了保证不出错,出现了校验和的机制,这块功能的存储被放到了页尾,占8个字节。页里的数据呢,为了方便查找每行的数据,所以包含页目录(采用二分法,把查询复杂度从O(n)优化为O(log n)),这也占空间,这些可以粗略的估计为占用了1KB。

声明代数:假设非叶子节点指向叶子节点的指针数量为X,叶子节点能够容纳的行数为Y,B+tree层数为Z,那么能存储的总行数就是Xz-1 * Y。

计算X:主键假设用bigint,占8个字节,页号这个元数据占4个字节,非叶子节点一条数据占12个字节,15KB / 12B = 1280。
计算Y:假设一个行数据为1KB,也就是说可以放15条数据。

若Z为1:12800 * 15 = 15行
若Z为2:12801 * 15 = 19200行
若Z为3:12802 * 15 = 24576000行
若Z为3:12803 * 15 = 31457280000行

但是这是理想情况,很多主键id都用无符号int,能节省4个字节,行数大小也不确定,所以这是个理论值,究竟是多少,需要根据实际情况讨论。

推荐阅读:

SQL语句执行顺序相关问题

MySQL索引底层原理相关问题自总结(难度对标18K-25K薪资,已总结80+,持续更新中)

热门相关:一路向南   完美性爱的味道   别人的妻子   痞子校花   奇异画师