一文详细讲清楚 MySQL为什么是小表驱动大表？

前言

MySQL在多表关联中，总是优先选用小表做为驱动表。
今天我试着用扫描行数与时间复杂度两个衡量指标来说明一下为什么MySQL选小表当驱动表。

Nested Loop join 实现方式

1、Index Nested-LoopJoin

当我们被驱动表上关联字段有索引时，Nested Loop join选用的连接方式

Index Nested-LoopJoin 的伪代码如下：

for (int i = 1; i <= t1.recordcount; i++) { 
  if (t2.seek(key)) -- t2表这里走的是BTREE的索引查找    
      resultList.add(t1.col,t2.col)  
}

我们知道一棵树高为3的Btree 如果主键为bigint 存放的记录就已到千万级别了
所以t2表的btree树索引查询。最多3次node查找就能找到数据节点了。
假定T1表为N行，T2表为M行
则时间复杂度为O(N)，扫描行数就为N*3左右

我们假设t1表为N = 100行，t2表为M = 10000行

则小表驱动大表的伪算法如下：

for (int i = 1; i <= 100; i++) { 
  if (t2.seek(key))       
      resultList.add(t1.col,t2.col)  
}

扫描行数为： 100 * 3 = 300
时间复杂度为O(t1表的行数)

则大表驱动小表的伪算法如下：

for (int i = 1; i <= 10000; i++) { 
  if (t2.seek(key))       
      resultList.add(t1.col,t2.col)  
}

我们假设小表的树高只有2
扫描行数为： 10000 * 2 = 20000
时间复杂度为O(t2表的行数)

所以在Index Nested-LoopJoin 连接方式下
时间复杂度要么为O(N),要么为O(M) 当然N,M哪个小用哪个。所以就是小表驱动大表
从上面举例的扫描行数，也能看出在我举例的数据情况下有60倍的区别。

2、Block Nested-Loop

当我们被驱动表上关联字段没有索引时，Nested Loop join选用的连接方式（8.0.18之前，之后的版本采用Hash Join）

Block Nested-Loop–伪代码

for (int i = 1; i <= t1.recordcount; i++) { 
   addJoinBuffer(i++; if buff.full break;)
   for(int j = 1; j <= t2.recordcount;j++) {       
      if (t1.key =t2.key)         
        resultList.add(t1.col,t2.col)     
   }
}

我们假设join buffer刚好一次能装100条记录

如果是小表驱动大表
那么扫描行数就是 100 + 10000;

如果是大表驱动小表 就是
10000 + (10000/100) *100

所以在BNL算法下，虽然相差倍数没有那大。也是小表驱动大表扫描行数更少。

结论

无论Nested Loop join 采用哪种连接算法。都是小表驱动大表扫描行数更少。