join执行逻辑

Index Nested_Loop Join（NLJ）

Index Nested_Loop Join：被驱动表上有索引，查的就快一点

// 背景条件：t1表N条数据，t2表M条，t2表在a上有索引，N << M
select * from t1 join t2 on (t1.a=t2.a);

驱动表：t1 (小表)

被驱动表：t2，t2上有a索引，走索引再回表查询

图片来自极客时间 丁奇 MySQL实战45讲

时间复杂度：N + N * 2 * log2M

N（t1全表扫描） + （t2表要查N次）N * 2（a索引上搜索一次+回表搜索一次） * log2M(树查找)

MMR(Mutli-Range Read) 优化

正常回表都是一个一个回表查，但是如果我们是范围查，可以一组查询按主键id排序后再查（主键ID表上是有序的）就更快

在read_rnd_buffer中做排序

|

图片来自极客时间 丁奇 MySQL实战45讲

BKA(Batched Key Access)算法

按照MMR的思路，NLJ本来是从t1一条一条取数据去t2 a索引上找的，我们可以每次多取点（看join buffer的大小）到join buffer上排个序再一起MRR，去a索引上找。

Simple Nested_Loop Join

如果被驱动表上没有索引，那t1、t2都全表扫描

时间复杂度：N + N * M

Block Nested-Loop Join（BLJ）

如果被驱动表上没有索引，做点优化：join_buffer 把驱动表存到内存里，这样对比的时候快点

原先是从磁盘上一行一行的读t1，拿到a的值再去t2表上查；现在把t1整个存在内存join buffer中，在一行一行的拿t2和join buffer中的数据做比较

时间复杂度：N + M，内存判断次数：N * M

join buffer 一次放不下 驱动表

分段放，每部分都执行上面的步骤。

时间复杂度：N + K * M // K就是分成了多少段，内存判断次数：N * M

join buffer优化的影响：主要影响缓存命中率

大表join会导致冷数据进入内存缓冲区，影响正常业务缓存命中率。由于join buffer优化，导致被驱动表被多次扫描，就算lru 有young区、old区，热数据也有被顶掉的风险。所以慎用BLJ，最好在被驱动表上建索引，如果仅临时操作一次，建索引比较浪费，可以考虑使用临时表

临时表

临时表的特点：每个事务独立有的，会话结束时自动销毁，show tables访问不到；对于同名表和临时表，临时表优先级高于同名表；

对于偶尔join大表，可以考虑使用临时表

选用t1还是t2做驱动表

选按照各自条件过滤完后，数据较少的表做驱动表。

从上面的时间复杂度可以看到：join buffer能装下，选谁都行；其他情况：N的影响大于M，所以N越小越好

全表扫描性能优化

对sever层的影响

图片来自极客时间 丁奇 MySQL实战45讲

服务端并不需要保存完整的结果集，数据是一段一段传给客户端的：

1. 先取一行写道net buffer pool中。这个内存的大小由参数net_buffer_length定义，默认16KB
2. 重复，直至net buffer pool写慢，调用网络接口发出去
3. 成功，就清空net buffer，重复
4. 直至发送失败，socket send buffer写慢了，进入等待；等能写了再发

对innodb的影响：主要影响缓存命中率

buffer pool结构

buffer pool使用lru算法，对最近最少使用的数据进行淘汰。全表扫描会导致短时间内大量冷数据进入buffer pool，影响正常业务的缓存命中率。

针对全表扫描的buffer pool优化

• 若此时访问P3，由于P3在young区，所以使用之前的lru算法，移动到链表首部
• 若此时要访问一个不存在在buffer pool的数据页，依旧淘汰队尾Pm，但新插入的元素放在old区队首Px位置（// 先观察一下）
• old区的数据，每次访问前都要做判断：
  • 在链表存在时间超过1s，ok，可以移动到young队首
  • 没到1s，位置不变。innodb_old_blocks_time = 1000ms

增加old区，因为全表扫描的冷数据不会变频繁访问，所以一般就在old区，对young区正常业务的缓存影响减小。