变量说明
R表（外部表，驱动表），页数:M,记录行数:n
S表（被驱动表）,页数:N,记录行数:n
TS:顺序读
TR：随机读
Nested Loop Join
循环嵌套连接：mysql5.x都只支持NL join,这也是mysql经常被吐槽的点
外部循环中的表称为外部表（驱动表），而内部循环中表称为内部表（被驱动表），通常小表(数据行)驱动大表(数据行)，是为了降低连接次数
Simple Nested-Loop Join
执行步骤
1.外部表读取一行记录
2.连接被内部表
3.得到匹配结果
4.执行读外部表下一行记录重复连接匹配，直到表的最后一行循环结束
5.合并结果返回
即：驱动表扫描一次+m次扫描被驱动表
注：mysql并未使用简单嵌套查询
Block Nested-Loop Join
执行步骤
1.外部表读入内存join_buffer
2.内部表读取一行与外部表连接
3.得到匹配结果
4.读取外部表下一批记录读入join_buffer，直到所有行都读入内存循环结束
5.合并结果并返回
即 外部表扫描一次，内部表扫描1~多次
注：内部表扫描次数取决于join_buffer大小，如果join_buffer足够大则能一次把外部表读入join_buffer,如果join_buffer不够大则需要多次读入内存即分成多批blocks.
join_buffer_size mysql各版本默认该设置为128 或 256 或512k。以join_buffer_size 2M计算，通常一条记录4004096字节之间，可用读入5125120条记录，这里也可以引出小表的定义：大概1万行内或小于4M大小.
单独客户端查询(手动查询)也可以调整session的join_buffer_size 值
set session join_buffer_size =536870912 --设置512M
Index Nested-Loop Join
执行步骤
1.外部表读取一行记录
2.通过索引连接内部表
3.得到匹配结果
4.执行读外部表下一行记录重复连接匹配，直到表的最后一行循环结束
5.合并结果返回
即：外部表扫描一次+外部表每一行索引查询内部表
注：mysql B-树 通常树深三层，n取值为1000左右，千万级别表3次io操作即可查询
Batched Key Acess(BKA)
Multi-Range Read 步骤
1.索引查找匹配，记录id存入read_rnd_buffer
2.在read_rnd_buffe中id进行排序，规避随机IO访问
3.根据id回表查询
4.返回结果
注：优化器倾向于不使用MRR，需要设置
set optimizer_switch="mrr_cost_based=off"
BKA执行步骤
1.外部表读入内存join_buffer
2.批量的将Key（索引键值）发送到MRR）接口(read_rnd_buffer)
3.MRR通过收到的Key在read_rnd_buffer中，根据其对应的ROWID进行排序
4.根据id顺序回表查询
5.执行读取外部表下批记录连接匹配，直到所有blocks连接循环结束
5.合并结果并返回
Sort-Merge Join
归并排序连接:mysql不支持
执行步骤：
1.对关联2个表进行排序
2.读取表R与表S记录直到所有最后一行记录
3.表R与表S进行关联匹配，返回输出，表S读取下一条记录
4.如不匹配，表R读取下一条记录
5.直到最后一行记录
注：B个缓冲区用于排序
Hash Join
散列连接:mysql8.0开始支持hash join
Basic Hash Join
执行步骤
1.build:扫描外表，选取连接条件通过hash函数划分bucket构建hash table
2.Probe:扫描内表，选取连接条件通过hash函数进行bucket匹配，定位到对应的bucket，进行匹配
Grace Hash Join / Partitioned Hash Join
表在内存中无法存放，需要频繁在磁盘与内存中换进换出
执行步骤
1.build:扫描外表，如果内存放不下hash buket，2次hash 映射hash partition、hash bucket
2.Probe:扫描内表，选取连接条件通过2次hash函数进行bucket匹配，定位到对应的bucket，进行匹配
分析
磁盘的吞吐量为 100M/S ~200M/S之间 ，便于计算取160M/S ，对于16K页为0.1ms 即一次顺序读 TS:0.1ms
IOPS 为：100~150,即一次随机读为 TR:10ms
一条记录为400字节到4K字节之间，对于16K页通常存放4~40条记录，取中位数一页存放20条记录，则表页数：行数=20：1
假设值如下：
TS: 0.1ms
TR: 10 ms
m: 10000 1万条记录
n: 1000000 100万条记录
M: 0.05m 500页
N:0.05 n 5万页
c取1000，百万级别2次 内存io；记一次随机IO 10ms
小表驱动大表：SNLJ cost= 500*0.1ms +(10000 * 50000) *0.1 ms =13.89 小时
大表驱动小表: SNLJ cost= 50000*0.1ms +(1000000 * 500) *0.1 ms =13.89 小时
结论：“小表驱动大表” 成本略低于 “大表驱动小表”
以join_buffer 2M 计算，小表需要4次读入join_buffer，大表需要390次读入join_buffer
小表驱动大表： BNLJ cost=500 * 0.1 ms + (4 * 50000) * 0.1 ms = 20.05秒
大表驱动小表: BNLJ cost=50000 * 0.1 ms + (390 * 500) * 0.1 ms =24.5秒
结论：“小表驱动大表” 成本略低于 “大表驱动小表”
小表驱动大表： INLJ cost= 500 * 0.1ms + (10000 * 1 ) * 10 ms = 100.05 秒
大表驱动小表: INLJ cost= 50000 * 0.1ms + (1000000 * 1 ) * 10 ms = 2.7 小时
结论：“小表驱动大表” 成本远低于 “大表驱动小表”
小表驱动大表： INLJ cost= （500 +50000）* 0.1ms + (42000 ) * 0.1 ms = 15.15秒
结论：sort merge join 不区分大小表
HSJ:cost= (M + N)
HSJ:cost= 3 * (M + N)
小表驱动大表： INLJ cost= (50000 + 500 ) * 0.1ms = 5.05 秒
小表驱动大表： INLJ cost= 3*(50000 + 500 ) * 0.1ms = 15.15 秒
结论：hash join 需要考虑大小表能否放在内存问题，如果内存放不下，需要hash 分区，则成本更高；即还是倾向小表驱动大表
总结
1.hash join (只适用等值连接)性能最优 ，在非等值关联时适用sort merge join
2.hash join 优势这么大，nested loop join 为什么没被淘汰，存在以下几个原因：
a.返回记录行数小，驱动表、被驱动表大且有索引；被驱动表随机读成本远小于表扫描
以磁盘100M/S，iops 100 来计算，2表有条件过滤再关联二次随机读20ms,20ms表扫描才能2M数据，128个16K数据页
b.小表大表关联，有索引，关联连接区分度高
3.优化Nested loop join 的的核心思想还是添加索引，将BNL转换为INLJ/BKA
4.数据已经排序，且存在倾斜，非等值比较 sort merge join更占优
参考
https://15445.courses.cs.cmu.edu/fall2023/notes/11-joins.pdf
