Join优化

被驱动表使用了索引的情况

例如这个简单的join语句select * from t1 straight_join t2 on (t1.a=t2.a);

在这条语句里，被驱动表t2的字段a上有索引，join过程用上了这个索引，因此这个语句的执行流程是这样的：

  1. 从表t1中读入一行数据 R；
  2. 从数据行R中，取出a字段到表t2里去查找；
  3. 取出表t2中满足条件的行，跟R组成一行，作为结果集的一部分；
  4. 重复执行步骤1到3，直到表t1的末尾循环结束。

在这个join语句执行过程中，驱动表是走全表扫描，而被驱动表是走树搜索。

假设被驱动表的行数是M，驱动表的行数是N。每次在被驱动表查一行数据，要先搜索索引a，再搜索主键索引。每次搜索一棵树近似复杂度是以2为底的M的对数，记为log2M，所以整个流程近似复杂度是 N + N2log2M。

这个算法称为**Index Nested-Loop Join(NLJ)**。

显然，N对扫描行数的影响更大，因此应该让小表来做驱动表。

  1. Multi-Range Read优化（需要设置set optimizer_switch="mrr_cost_based=off"）

    MRR优化的设计思路。此时，语句的执行流程变成了这样：

    1. 根据索引a，定位到满足条件的记录，将id值放入read_rnd_buffer中;
    2. 将read_rnd_buffer中的id进行递增排序；
    3. 排序后的id数组，依次到主键id索引中查记录，并作为结果返回。

    利用顺序性的优势

  2. Batched Key Access算法（需要set optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';）

    理解了MRR性能提升的原理，我们就能理解MySQL在5.6版本后开始引入的Batched Key Acess(BKA)算法了。这个BKA算法，其实就是对NLJ算法的优化。

    大致逻辑是：为了利用上MRR优化，在从t1表中取a值的时候不再一行一行的去t2表匹配，而是存入join_buffer的缓存中再去统一利用MRR匹配取值。

    image-20230401150349127

被驱动表没有索引的情况

例如select * from t1 straight_join t2 on (t1.a=t2.b);

由于表t2的字段b上没有索引，如果再用图2的执行流程时，每次到t2去匹配的时候，就要做一次全表扫描。这个算法是正确的，叫做“Simple Nested-Loop Join”，没有索引的情况下会很笨重。

MySQL也没有使用这个Simple Nested-Loop Join算法，而是使用了另一个叫作“Block Nested-Loop Join”的算法，简称BNL。

算法的流程是这样的：

  1. 把表t1的数据读入线程内存join_buffer中，由于我们这个语句中写的是select *，因此是把整个表t1放入了内存；

  2. 扫描表t2，把表t2中的每一行取出来，跟join_buffer中的数据做对比，满足join条件的，作为结果集的一部分返回。

    如果join_buffer放不下，会分段依次放入内存进行判断。所以当没有索引的join语句很慢，就把join_buffer_size改大。

这个算法与之前的算法的区别在于：判断是内存操作，速度上会快很多，性能也更好。

BKA优化：

大致思路是：（或者直接在被驱动表加索引）

  1. 把表t2中满足条件的数据放在临时表tmp_t中；
  2. 为了让join使用BKA算法，给临时表tmp_t的字段b加上索引；
  3. 让表t1和tmp_t做join操作。
1
2
3
4
create temporary table temp_t like t1;
alter table temp_t add index(b);
insert into temp_t select * from t2 where b>=1 and b<=2000;
select * from t1 join temp_t on (t1.b=temp_t.b);