MySQL2_3多表查询

发表于 更新于 分类于

分析多表查询，也就是分析MySQL中连接（Join）是怎么执行的。

连接查询的大致执行过程

1
SELECT * FROM t1, t2 WHERE t1.m1 > 1 AND t1.m1 = t2.m2 AND t2.n2 < 'd';

这个查询语句包含 3 个过滤条件，大致执行过程如下：
1、确定第一个需要查询的表，称之为驱动表，InnoDB 会选取代价最小的方法去执行查询（从 const、ref、ref_or_null、range、index、all 这些执行方法中选取代价最小的去执行查询）；
2、针对从驱动表中查询出的每一条记录，分别到其他表中查询匹配的记录，这些表称为被驱动表。
因此，驱动表只会被查询一次，而被驱动表则会被查询多次。

内连接和外连接

内连接
左连接（左外连接）：左侧的表为驱动表。
右连接（右外连接）：右侧的表为驱动表。

对于外连接来说，由于驱动表中的记录即使在被驱动表中找不到符合 ON 子句条件的记录时也会被加入到结果集，所以左连接和右连接的驱动表和被驱动表的位置不能轻易互换。

连接的原理

嵌套循环连接（Nested-Loop Join）

MySQL-NestedLoopJoin算法
驱动表中查询到的每条记录都需要分别到被驱动表中查找匹配的记录，当有 3 张表进行连接时，上一步得到的结果集就会成为新的驱动表，第 3 张表则成为了新的被驱动表，重复这个过程。
这个过程就像是一个嵌套的循环，所以这种驱动表只访问一次，但被驱动表却可能被多次访问，访问次数取决于对驱动表执行单表查询后的结果集中的记录条数的连接执行方式称之为嵌套循环连接（Nested-Loop Join）。

Simple Nested-Loop Join

到被驱动表上查询的时候没有命中索引，导致每次查询都是全表扫描，时间复杂度退化为N * M。
实际上，MySQL 并没有使用这么简单粗暴的算法，而是Block Nested-Loop Join。

基于块的嵌套循环连接（Block Nested-Loop Join）

因为嵌套循环连接中，被驱动表可能被访问非常多次（现实中单表的数据量是非常大的），这个过程中涉及到随机磁盘扫描，因此效率并不高，为了减少这个 IO 代价，所以我们应该尽量减少访问被驱动表的次数。
当被驱动表中的数据非常多时，每次访问被驱动表，被驱动表的记录会被加载到内存中，在内存中的每一条记录只会和驱动表结果集的一条记录做匹配，之后就会被从内存中清除掉。然后再从驱动表结果集中拿出另一条记录，再一次把被驱动表的记录加载到内存中一遍，周而复始，驱动表结果集中有多少条记录，就得把被驱动表从磁盘上加载到内存中多少次。
优化方法是在把被驱动表的记录加载到内存的时候，一次性和多条驱动表中的记录做匹配，这样就可以大大减少重复从磁盘上加载被驱动表的代价了。join buffer就是执行连接查询前申请的一块固定大小的内存，先把若干条驱动表结果集中的记录装在这个 join buffer 中，然后开始扫描被驱动表，每一条被驱动表的记录一次性和 join buffer 中的多条驱动表记录做匹配，因为匹配的过程都是在内存中完成的，所以这样可以显著减少被驱动表的 I/O 代价。
基于块的嵌套循环连接
这种加入了 join buffer 的嵌套循环连接算法被称为基于块的嵌套循环连接（Block Nested-Loop Join）。

  • 另外需要注意的是，驱动表的记录并不是所有列都会被放到 join buffer 中，只有查询列表中的列和过滤条件中的列才会被放到 join buffer 中，所以最好不要把*作为查询列表。
  • 相对Simple Nested-Loop Join来说，Block Nested-Loop Join在时间复杂度上并没有提高，但是由于所有匹配操作都是内存操作，速度会快很多，性能也更好。
  • join buffer 的空间是有限的，如果放不下所有数据，则每次只放入一批，匹配完后清空 join buffer，再放另一批。

连接优化

  1. 索引
    对每一步得到的结果集（第一步时，这个结果集就是第一张驱动表），到被驱动表中匹配记录时，相当于执行等值查询，因此我们可以在被驱动表上的这个被关联字段上加索引来提高效率。这种在连接查询中对被驱动表使用主键值或者唯一二级索引列的值进行等值查找的查询执行方式称之为：eq_ref。
  2. 用小表作驱动表（能命中索引的情况下）
    假设驱动表的行数是 N，则遍历驱动表时间复杂度为N，假设被驱动表的行数是 M，则在被驱动表上查一行数据的时间复杂度是2 * log2(M)（这里假设索引树的基为 2，2 *是因为要先从二级索引找到记录的主键，然后再用主键从聚簇索引找到记录的其他字段），因此，join 查询的近似复杂度为N + N*2*log2M。
    显然，N 对扫描行数的影响更大，因此最好使用小表作为驱动表。
  3. 用小表作驱动表（不能命中索引，即 Block Nested-Loop Join 的情况）
    驱动表会被放入 join_buffer 中和被驱动表匹配，总的时间复杂度仍为N * M，N 被分成 K 段，K 与 N 成正比，可以表示为K = λ * N，因此，这个算法的扫描行数是N + λ * N * M，由于N * M的值不变，因此 N 越小这个算式的结果也会越小，所以，应该用小表作为驱动表。

    小表的定义：各表按查询条件过滤，最终得到的总数据量中较小的那个。

  4. 调大join_buffer_size
    上式中，除了 N 外，λ也是关键，这里λ其实主要与join_buffer_size有关，join_buffer_size越大，一次性放入 join_buffer 的行数越大，分成的段数也越少，对被驱动表的全表扫描次数也越少。

什么情况下可以使用 join

查看 explain 结果里 Extra 字段里有没有出现Block Nested Loop：

  • 如果出现，则该 join 查询属于Block Nested-Loop Join，扫描行数过多，会占用大量资源，因此这种 join 尽量不要使用；
  • 如果没有出现，说明该 join 查询属于Index Nested-Loop Join，这种 join 查询是没有问题的。

join 的进一步优化

  1. MRR（Multi-Range Read）
    普通回表过程是一行一行地查数据——普通索引上定位到主键 id、然后从主键索引上查到整行数据，一般来说这个过程是随机读磁盘的，性能比较差。
    MRR 的核心思路是将 id 先保存到read_rnd_buffer，批量、按顺序地回表，这样排序后能达到接近顺序读磁盘的效果。
  2. BKA（Batched Key Access）
    BKA 是对 NLJ 的优化。
    类似 MRR，从驱动表取值到被驱动表上执行 join 时，BKA 会先将驱动表上的记录先放到join_buffer，然后批量到执行 join 操作。
    如果要使用 BKA 优化算法的话，你需要在执行 SQL 语句之前，先设置： 
    1
    set optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';
    其中前两个参数的作用是要启用 MRR。这么做的原因是，BKA 算法的优化要依赖于 MRR。