MySQL Join- Nested-loop Join 和 MRR

nested-loop join 嵌套循环连接
simple nested-loop join  简单嵌套循环连接
index nested-loop join  索引嵌套循环连接
block nested-loop join  块嵌套循环连接

hash join 哈希连接

优化连接速度：
1. 小结果集驱动大结果集， 减少外层循环的数据量
2. 为匹配的条件增加索引， 使用索引嵌套循环连接，减少内层表的循环次数
3. 增大join buffer size, 当使用块嵌套循环连接时，一次缓存的数据越多，外层表循环的次数就越少
4. 减少不必要的字段查询, 字段越少，join buffer缓存的数据就越多，外层表缓存次数越少

snlj-n . m
inlj-n . log(2)m
blkj-n/block_size . m
hash join-n . m 等值查询，= 
merge join 非等值查询，>、<、>=、<=, 没有<>、!=

nlp

for i in (select * from t1) loop
  for j in (select * from t2) loop
    if j.col3=i.col4 then
      result.add(i,j)
    end if
    end loop
end loop

for i in (select * from t1) loop
  for j in (select * from t2) loop
    if j.col3=i.col4 then
      result.add(i,j)
      end if
    end loop
end loop

其复杂度 O(n * m)， 查询效率会非常慢

mysql 不会选择

<!-- 关闭 batched_key_access -->
mysql> set optimizer_switch='batched_key_access=off';

mysql> explain select s.*,l.* from small_table s join large_table l on s.key_col=l.key_col;
+----+-------------+-------+------------+------+---------------+-------------+---------+------------------------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key         | key_len | ref                    | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+-------------+---------+------------------------+------+----------+-------------+
|  1 | SIMPLE      | s     | NULL       | ALL  | idx_key_col   | NULL        | NULL    | NULL                   |  100 |   100.00 | Using where |
|  1 | SIMPLE      | l     | NULL       | ref  | idx_key_col   | idx_key_col | 5       | join_example.s.key_col |  206 |   100.00 | NULL        |
+----+-------------+-------+------------+------+---------------+-------------+---------+------------------------+------+----------+-------------+

<!-- 开启 batched_key_access -->
mysql> set optimizer_switch='batched_key_access=on';
mysql> explain select s.*,l.* from small_table s join large_table l on s.key_col=l.key_col ;


<!-- 开启batched_key_access, 查询被驱动表的id主键或者索引字段,bka失效，回归到inlj -->
mysql> explain select s.*,l.id from small_table s join large_table l on s.key_col=l.key_col;

select * from r join s on r.code = s.code

# 伪代码
for i in R do                                             # 扫描外表R
  store used columns as p from R in into join buffer      # 将部分或者全部R记录保存到join buffer中，记为p
  for j in S do                                           # 扫描内表S
    if j.code = p.code with join buffer and S columns then # 根据join buffer中的记录和S表的code字段进行匹配
      add j to result set                                # 将匹配到的记录添加到结果集
    end if                                              # 结束内表扫描                                
  end loop                                              # 结束外表扫描
end loop                                                # 结束查询,将所有的结果集汇总返回给客户端

snlj- n . m 笛卡尔积， 内层行数 * 外层行数
inlj- n . log(2)m 索引匹配，减少内层匹配次数，内层行数 * 外层行数 -> 外层行数 * 内层索引高度
bnlj- n/block_size . m 块嵌套循环连接，减少外层扫描次数， 外层行数 / block_size * 内层行数 + 外层行数

mysql> explain select * from t where age between 10 and 30 and name like 'abc%';
+----+-------------+-------+------------+------+---------------+---------+-------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key     | key_len | ref   | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+-------+------+----------+-------------+
|  1 | SIMPLE      | t     | NULL       | range  | idx_age       | idx_age | 5     | const |   960 |   100.00 | Using index condition |
+----+-------------+-------+------------+------+---------------+-------+------+----------+-------------+
1 row in set (0.00 sec)

mrr: on/off # 开启或关闭MRR优化
mrr_cost_based: on/off # 开启或关闭基于成本的MRR优化
read_rnd_buffer_size: 16M # 内存缓冲区大小，默认16M, 针对 myisam 引擎，会找出rowid并对其排序，对于innodn引擎，会直接排序主键值. 

索引扫描--> 生成rowid 列表 → 按物理顺序排序 rowid → 批量读取数据行

select * from a join b on a.id = b.id where a.id between 1 and 1000000000; -- 笛卡尔积 simple nested-loop join,优化成 block nested-loop join 
select * from a left join b on a.id = b.id   -- 左连接 left join, 无索引或者a有索引,都是笛卡尔积,优化成 block nested-loop join , block nested-loop join 需要驱动表读取部分数据到join buffer中


select * from a where a.age between 1 and 100000; -- 无索引,全表扫描,有索引,使用using index condition

select * from a where a.age betwween 1 and 100000 and a.name like 'abc%'; -- 范围条件, 优化成 index nested-loop join, 范围条件索引, 回表查询, 使用mrr优化, 实际都是基于cbo算法选择索引, 并不是mrr优化

select * from a left join b on a.id = b.id where a.id between 1 and 1000000000; -- 左连接, 范围条件, 优化成 index nested-loop join , 如果存在回表查询, 则使用mrr+bka优化

bka 都是基于mrr的优化， 优化范围查询，回表查询， 减少回表查询， 提高查询效率
bka 存在两个缓存区域 , join buffer 和 read_rnd_buffer, join buffer 存放部分数据， read_rnd_buffer 存放排序后的主键值， 减少回表查询， 提高查询效率

效率:
- 方式, 时间, 优点, 缺点 
- 无优化, 13s, 没有优点, 时间复杂度指数级别，特别慢
- BNL算法的join buffer优化, 5.2s, 使用join buffer减少访问被驱动表次数, 增加join buffer缓冲池的开销
- 被驱动表增加索引, 2.02s, 被驱动表关联条件的列建立索引, 将查询关联条件从无序查询优化为有序查询, 由于ID无序查询被驱动表会出现随机IO
- BKA算法优化, 1.5s, 优化范围查询, 回表查询, 使用BKA算法将访问被驱动表索引的随机IO转换成顺序IO, 需要被驱动表建立索引和使用MRR，默认情况下使用MRR成本估算很大 

构建阶段（Build Phase）：
- 选择较小的表（驱动表）作为构建表。
- 遍历构建表的每一行，对连接键计算哈希值，将记录存入哈希表中。
- 哈希表的每个桶可以存储多个记录（处理哈希冲突）。

探测阶段（Probe Phase）：
- 遍历较大的表（被驱动表）的每一行。
- 对连接键计算相同的哈希值，定位到哈希表中的对应桶。
- 在桶内逐行比较连接键，匹配成功则输出到结果集。