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

2024-05-12 07:12 由小松聊PHP进阶发表于 #数据库

场景假设

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执行顺序的逻辑

from用于确定操作对象，放第一位毋庸置疑。
join和on用于关联，后面的各种处理逻辑依附于关联后内部创建的临时表，先生成数据集，才能为后续处理做基础。
where用于筛选，可以减少后续操作的数据量，提高查询性能。
group by用于对数据进行分类汇总，不放where前面，是为了避免分组后的数据被where过滤掉（分组分了个寂寞），造成算力浪费和内存资源（数据量大还是很消耗算力和内存的）的问题。
having用于对分组结果进行过滤，所以要在group by之后。
select用于决定迭代显示那些列，而不是限制只有这些列才可以参与处理，上游的各种操作（如复杂的where条件）不能受7. select字段的影响，这也是where后面跟的字段，不必在select出现的原因。select的本意是处理数据后仅仅返回这些字段，而不是决定只有这些字段进行数据处理，所以必定要放偏后的位置。
order by用于结果进行排序，肯定是结果处理后才排序的，理由和group by相似。
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个字节，行数大小也不确定，所以这是个理论值，究竟是多少，需要根据实际情况讨论。