【MySQL】表连接为什么比子查询快

1. 前言

查了网上很多资料，最后回归官网的算法介绍。与其说对比子查询和表连接，更合适的说法是对比Nested-Loop 和 Block Nested-Loop 的时间效率。总的来说，表连接更好得触发 Block Nested-Loop算法，用空间换时间，所以单从效率的角度出发，选择表连接是个比较不错的选择。下文的伪代码全部来自于官方。

2. Nested-Loop 的算法思路

for each row in t1 matching range {
  for each row in t2 matching reference key {
    for each row in t3 {
      if row satisfies join conditions, send to client
    }
  }
}

2.1 复杂度预估

设t1,t2,t3数据量都为3行，现进行节点遍历

3. Block Nested-Loop的算法思路

如果出现了表t1, t2, t3。先缓存t1，t2表的循环产生的组合，然后循环t3。t3所有行匹配缓存，连接成功则收集到结果集。

• 现假设缓存容量足够大

for each row in t1 matching range {
  for each row in t2 matching reference key {
    store used columns from t1, t2 in join buffe
  }
}

for each row in t3 {
  for each t1, t2 combination in join buffer {
   if row satisfies join conditions, send to client
  }
}

3.1 复杂度预估

3.2 Block Nested-Loop 减少时间复杂度的思想

空间换时间

• 缓存了Nested-Loop（如下第一个图） 需要重复遍历的外层循环
  
• 观察外层循环的节点都只会被遍历一次，就进入缓存。随着数量级增大，缓存带来的提效呈线性增长
  

缓存适度使用，分片处理

• 缓存不能做成无界的，Mysq的处理方式：用全局变量限制缓存大小，最大缓存容量为分片，分片数据满后进行匹配再清掉缓存。

for each row in t1 matching range {
  for each row in t2 matching reference key {
    store used columns from t1, t2 in join buffer
    if buffer is full {
      for each row in t3 {
        for each t1, t2 combination in join buffer {
          if row satisfies join conditions, send to client
        }
      }
      empty join buffer
    }
  }
}

if buffer is not empty {
  for each row in t3 {
    for each t1, t2 combination in join buffer {
      if row satisfies join conditions, send to client
    }
  }
}

4. 子查询优化

优化子查询

原文：Development is ongoing, so no optimization tip is reliable for the long term. The following list provides some interesting tricks that you might want to play with.

释义：随着开发的演进，没有一种优化建议是长期可靠的。但是有一些有趣的技巧建议可以给到阅读者。

将子查询重写成连接

原文：A LEFT [OUTER] JOIN can be faster than an equivalent subquery because the server might be able to optimize it better—a fact that is not specific to MySQL Server alone.Today, MySQL Server and many other modern database systems offer a wide range of outer join types.

简洁释义：一个外部连接会比等价的子查询效率更高，事实上除了MySQL服务器，大多数的数据库都有这种表现。

-- 将in改写成表连接
SELECT * FROM t1 WHERE id IN (SELECT id FROM t2);

SELECT DISTINCT t1.* FROM t1, t2 WHERE t1.id=t2.id;

// --- 
-- not in 或者 not exists改写成表连接
SELECT * FROM t1 WHERE id NOT IN (SELECT id FROM t2);
SELECT * FROM t1 WHERE NOT EXISTS (SELECT id FROM t2 WHERE t1.id=t2.id);

SELECT table1.*
  FROM table1 LEFT JOIN table2 ON table1.id=table2.id
  WHERE table2.id IS NULL;

5. 参考资料

官网相关资料：
MySQL5.7 子查询
MySQL5.7 优化子查询
MySQL5.7 将子查询重写成连接
MySQL5.7 循环相关算法