MySQL Join工作原理

代码语言：javascript复制

CREATE TABLE `t2` (
  `id` int(11) NOT NULL,
  `a` int(11) DEFAULT NULL,
  `b` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `a` (`a`)
) ENGINE=InnoDB;

drop procedure idata;
delimiter ;;
create procedure idata()
begin
  declare i int;
  set i=1;
  while(i<=1000)do
    insert into t2 values(i, i, i);
    set i=i 1;
  end while;
end;;
delimiter ;
call idata();

create table t1 like t2;
insert into t1 (select * from t2 where id<=100)

Index Nested-Loop Join

代码语言：javascript复制

select * from t1 straight_join t2 on t1.a=t2.a;

这里使用straight_join，如果我们直接使用join，MySQL优化器可能选t1或t2作为驱动表，但是使用straight_join，会强制t1作为驱动表，t2是被驱动表。

通过explain，我们可以看出，在join的过程中用上了被驱动表t2的索引a，整个语句的执行流程如下：

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

驱动表是全表扫描，因此需要扫描100行
对于每一行R，根据a字段去表t2查找，走的是树搜锁过程，由于我们构造的数据一一对应，因此每次只扫描1行，总共也是100行
整个执行流程，扫描了200行

对于上面的查询来说，如果不用join，会多100次交互，不如join效果好。

如何选择驱动表？

先说结论，一定要让小表做驱动表。

假设被驱动表的行数为M，每次在被驱动表上查询的时候，先搜索索引a，再搜索主键索引，每棵索引树的搜索复杂度可以记为以2为底的M对数，记为log2(M)，由于需要搜索两棵索引树，因此被驱动表上的复杂度为2*log2(M)。

假设驱动表的行数为N，每执行过程中要扫描N行，对于我们构造的表每一行到被驱动表上只匹配一次，因此整个执行的复杂度=N N * 2 * log2(M)。

可以看出N的大小对扫描行数影响更大，因此需要让小表做驱动表。

Block Nested-Loop Join

Index Nested-Loop Join是在被驱动表有索引的情况下，如果被驱动表上没有可用的索引，算法的流程如下：

将表t1的数据读入线程内存join_buffer中，由于这里是select *，因此是把整个表t1放入内存
扫描t2，把表t2中的每一行取出来，跟join_buffer中的数据做对比，满足join条件的会作为结果集的一部分进行返回

代码语言：javascript复制

explain select * from t1 straight_join t2 on t1.a=t2.b;

在整个过程对表t1和t2做了一次全表扫描，因此扫描行数为1100行，由于join_buffer是无序的数组，因此对于表t2中的每一行，都要做100次判断，因此在内存中的判断次数是100*1000 = 10w次，但由于是在内存中进行，速度上还可以接受。

假设小表的行数为N，大表的行数为M，所以总扫描行数是M N，总判断次数是N*M，因此这种情况下，大表和小表哪个做驱动表都是一样的耗时。

join_buffer的大小是由join_buffer_size决定，默认值是256K。

代码语言：javascript复制

show global variables like 'join_buffer_size';

如果驱动表过大，join_buffer无法放下的话，就需要分段存放，执行过程如下：

扫描t1，顺序读取数据放入join_buffer中，如果join_buffer满了，进行第2步
扫描t2，把t2中的每一行取出来，跟join_buffer中的数据做对比，满足join条件的作为结果集的一部分返回
清空join_buffer
继续进行1-2步，直到所有数据取数完毕

假设驱动表的行数为N，需要K次可以完成，N越大，K越多，假设K= µ * N，µ的取值范围是(0,1)，因此该算法执行过程中：

扫描行数是N µ * N * M
内存判断N*M次

在上述扫描行数，µ是影响行数的关键因素，这个值越小越好，在N固定的情况下，join_buffer_size越大，一次放入的行越多，分成的段数越少，对被驱动表的扫描行数也越少，如果join很慢，可以适当考虑改大join_buffer_size。

BNL算法问题

假设被驱动表是个很大的数据表，将会导致以下问题：

IO压力大
降低内存命中率

如果多次扫描大的被驱动表，由于我们的join语句在不停地循环读磁盘和淘汰数据页，进入old区域的数据页很可能在1s之内被淘汰，此时业务正常访问的数据页也会被淘汰，没有机会进入young区域，因此会导致young区域的数据页没办法合理的进行淘汰。

因此大表join在语句结束以后，对IO的影响结束，但是对于Buffer Pool的影响就是持续性的，需要依靠后续的查询请求慢慢恢复内存命中率。

如何使用join？

如果可以使用Index Nested-Loop Join算法（用上被驱动表上的索引）其实没有问题
如果使用Block Nested-Loop Join算法，尽量不要对大表进行join，这样可能会导致扫描行数过多，占用大量系统资源
在join的时候尽量选择小表做驱动表
在判断哪个表是小表的时候应该是按照两个表各自的条件过滤，过滤完成以后，计算参与join的各个字段的总数据量，数据量小的那个就是小表

nest 编程算法

0 人点赞