【MySQL进阶】多表连接的原理
【MySQL进阶】多表连接的原理
[TOC]
前言
搞数据库一个避不开的概念就是 Join ，翻译成中文就是 连接 。相信很多小伙伴在初学连接的时候有些一脸懵逼，理解了连接的语义之后又可能不明白各个表中的记录到底是怎么连起来的，以至于在使用的时候常常陷入下边两种误区：
- 业务至上，管他三七二十一，再复杂的查询也用在一个连接语句中搞定。
- 敬而远之，上次 的慢查询就是因为使用了连接导致的，以后再也不敢用了。
我们先建立两个简单的表并给它们填充一点数据：
mysql> CREATE TABLE t1 (m1 int, n1 char(1));
Query OK, 0 rows affected (0.02 sec)
mysql> CREATE TABLE t2 (m2 int, n2 char(1));
Query OK, 0 rows affected (0.02 sec)
mysql> INSERT INTO t1 VALUES(1, 'a'), (2, 'b'), (3, 'c');
Query OK, 3 rows affected (0.00 sec)
Records: 3 Duplicates: 0 Warnings: 0
mysql> INSERT INTO t2 VALUES(2, 'b'), (3, 'c'), (4, 'd');
Query OK, 3 rows affected (0.00 sec
我们成功建立了 t1 、 t2 两个表，这两个表都有两个列，一个是 INT 类型的，一个是 CHAR(1) 类型的，填充好数据的两个表长这样：
一：连接简介
1：连接的本质
**连接 的本质就是把各个连接表中的记录都取出来依次匹配的组合加入结果集并返回给用户。**所以我们把 t1 和 t2 两个表连接起来的过程如下图所示：
这个过程看起来就是把 t1 表的记录和 t2 的记录连起来组成新的更大的记录，所以这个查询过程称之为连接查询。连接查询的结果集中包含一个表中的每一条记录与另一个表中的每一条记录相互匹配的组合，像这样的结果集就可以称之为 笛卡尔积 。因为表 t1 中有3条记录，表 t2 中也有3条记录，所以这两个表连接之后的笛卡尔积就有 3×3=9 行记录。
2：连接过程简介
如果我们乐意，我们可以连接任意数量张表，但是如果没有任何限制条件的话，这些表连接起来产生的 笛卡尔积 可能是非常巨大的。比方说3个100行记录的表连接起来产生的 笛卡尔积 就有100×100×100=1000000 行数据！所以在连接的时候过滤掉特定记录组合是有必要的，在连接查询中的过滤条件可以分成两种：
涉及单表的条件
我们称为 搜索条件 ，比如 t1.m1 > 1是只针对 t1 表的过滤条件， t2.n2 < 'd' 是只针对 t2 表的过滤条件。
涉及两表的条件
这种过滤条件我们之前没见过，比如 t1.m1 = t2.m2 、 t1.n1 > t2.n2 等，这些条件中涉及到了两个表，我们稍后会仔细分析这种过滤条件是如何使用的哈
下边我们就要看一下携带过滤条件的连接查询的大致执行过程了，比方说下边这个查询语句：
SELECT * FROM t1, t2 WHERE t1.m1 > 1 AND t1.m1 = t2.m2 AND t2.n2 < 'd';
在这个查询中我们指明了这三个过滤条件
- t1.m1 > 1
- t1.m1 = t2.m2
- t2.n2 < 'd'
那么这个连接查询的大致执行过程如下：
首先确定第一个需要查询的表，这个表称之为 驱动表 。只需要选取代价最小的那种访问方法去执行单表查询语句就好了（就是说从const、ref、ref_or_null、range、index、all这些执行方法中选取代价最小的去执行查询）。此处假设使用 t1 作为驱动表，那么就需要到 t1 表中找满足 t1.m1 > 1 的记录，因为表中的数据太少，我们也没在表上建立二级索引，所以此处查询 t1 表的访问方法就设定为 all 吧，也就是采用全表扫描的方式执行单表查询。所以查询过程就如下图所示：
我们可以看到， t1 表中符合 t1.m1 > 1 的记录有两条。
针对上一步骤中从驱动表产生的结果集中的每一条记录，分别需要到 t2 表中查找匹配的记录，所谓 匹配的记录 ，指的是符合过滤条件的记录。因为是根据 t1 表中的记录去找 t2 表中的记录，所以 t2 表也可以被称之为 被驱动表 。上一步骤从驱动表中得到了2条记录，所以需要查询2次 t2 表。此时涉及两个表的列的过滤条件 t1.m1 = t2.m2 就派上用场了：
- 当 t1.m1 = 2 时，过滤条件 t1.m1 = t2.m2 就相当于 t2.m2 = 2 ，所以此时 t2 表相当于有了 t2.m2 = 2 、 t2.n2 < 'd' 这两个过滤条件，然后到 t2 表中执行单表查询
- 当 t1.m1 = 3 时，过滤条件 t1.m1 = t2.m2 就相当于 t2.m2 = 3 ，所以此时 t2 表相当于有了 t2.m2 = 3 、 t2.n2 < 'd' 这两个过滤条件，然后到 t2 表中执行单表查询
所以整个连接查询的执行过程就如下图所示：
从上边两个步骤可以看出来，我们上边唠叨的这个两表连接查询共需要查询1次 t1 表，2次 t2 表。当然这是在特定的过滤条件下的结果，如果我们把 t1.m1 > 1 这个条件去掉，那么从 t1 表中查出的记录就有3条，就需要查询3次 t2 表了。也就是说在两表连接查询中，驱动表只需要访问一次，被驱动表可能被访问多次。
二：连接的原理
1：嵌套循环连接（Nested-Loop Join）
我们前边说过，对于两表连接来说，驱动表只会被访问一遍，但被驱动表却要被访问到好多遍，具体访问几遍取决于对驱动表执行单表查询后的结果集中的记录条数。对于内连接来说，选取哪个表为驱动表都没关系，而外连接的驱动表是固定的，也就是说左（外）连接的驱动表就是左边的那个表，右（外）连接的驱动表就是右边的那个表。我们上边已经大致介绍过 t1 表和 t2 表执行内连接查询的大致过程，我们温习一下：
选取驱动表，使用与驱动表相关的过滤条件，选取代价最低的单表访问方法来执行对驱动表的单表 查询。
对上一步骤中查询驱动表得到的结果集中每一条记录，都分别到被驱动表中查找匹配的记录。
通用的两表连接过程如下图所示：
如果有3个表进行连接的话，那么 步骤2 中得到的结果集就像是新的驱动表，然后第三个表就成为了被驱动表，重复上边过程，也就是 步骤2 中得到的结果集中的每一条记录都需要到 t3 表中找一找有没有匹配的记录，用伪代码表示一下这个过程就是这样：
for each row in t1 { #此处表示遍历满足对t1单表查询结果集中的每一条记录
for each row in t2 { #此处表示对于某条t1表的记录来说，遍历满足对t2单表查询结果集中的每一条记录
for each row in t3 { #此处表示对于某条t1和t2表的记录组合来说，对t3表进行单表查询
if row satisfies join conditions, send to client
}
}
}
这个过程就像是一个嵌套的循环，所以这种驱动表只访问一次，但被驱动表却可能被多次访问，访问次数取决于对驱动表执行单表查询后的结果集中的记录条数的连接执行方式称之为 嵌套循环连接 （ Nested-Loop Join ），这是最简单，也是最笨拙的一种连接查询算法。
2：使用索引加快连接速度
我们知道在 嵌套循环连接 的 步骤2 中可能需要访问多次被驱动表，如果访问被驱动表的方式都是全表扫描的话，妈呀，那得要扫描好多次呀～～～ 但是别忘了，查询 t2 表其实就相当于一次单表扫描，我们可以利用索引来加快查询速度哦。回顾一下最开始介绍的 t1 表和 t2 表进行内连接的例子：
SELECT * FROM t1, t2 WHERE t1.m1 > 1 AND t1.m1 = t2.m2 AND t2.n2 < 'd';
我们使用的其实是 嵌套循环连接 算法执行的连接查询，再把上边那个查询执行过程表拉下来给大家看一下：
查询驱动表 t1 后的结果集中有两条记录， 嵌套循环连接 算法需要对被驱动表查询2次：
当 t1.m1 = 2 时，去查询一遍 t2 表，对 t2 表的查询语句相当于：
SELECT * FROM t2 WHERE t2.m2 = 2 AND t2.n2 < 'd'当 t1.m1 = 3 时，再去查询一遍 t2 表，此时对 t2 表的查询语句相当于：
SELECT * FROM t2 WHERE t2.m2 = 3 AND t2.n2 < 'd';
可以看到，原来的 t1.m1 = t2.m2 这个涉及两个表的过滤条件在针对 t2 表做查询时关于 t1 表的条件就已经确定了，所以我们只需要单单优化对 t2 表的查询了，上述两个对 t2 表的查询语句中利用到的列是 m2 和 n2 列，我们可以：
在 m2 列上建立索引，因为对 m2 列的条件是等值查找，比如 t2.m2 = 2 、 t2.m2 = 3 等，所以可能使用到ref 的访问方法，假设使用 ref 的访问方法去执行对 t2 表的查询的话，需要回表之后再判断 t2.n2 < d 这个条件是否成立。
这里有一个比较特殊的情况，就是假设 m2 列是 t2 表的主键或者唯一二级索引列，那么使用 t2.m2 = 常数值 这样的条件从 t2 表中查找记录的过程的代价就是常数级别的。我们知道在单表中使用主键值或者唯一二级索引列的值进行等值查找的方式称之为 const ，而设计 MySQL 的大叔把在连接查询中对被驱动表使用主键值或者唯一二级索引列的值进行等值查找的查询执行方式称之为： eq_ref 。
在 n2 列上建立索引，涉及到的条件是 t2.n2 < 'd' ，可能用到 range 的访问方法，假设使用 range 的访问方法对 t2 表的查询的话，需要回表之后再判断在 m2 列上的条件是否成立。
假设 m2 和 n2 列上都存在索引的话，那么就需要从这两个里边儿挑一个代价更低的去执行对 t2 表的查询。当然，建立了索引不一定使用索引，只有在 二级索引 + 回表 的代价比全表扫描的代价更低时才会使用索引。
3：基于块的嵌套循环连接（Block Nested-Loop Join）
扫描一个表的过程其实是先把这个表从磁盘上加载到内存中，然后从内存中比较匹配条件是否满足。现实生活中的表可不像 t1 、 t2 这种只有3条记录，成千上万条记录都是少的，几百万、几千万甚至几亿条记录的表到处都是。内存里可能并不能完全存放的下表中所有的记录，所以在扫描表前边记录的时候后边的记录可能还在磁盘上，等扫描到后边记录的时候可能内存不足，所以需要把前边的记录从内存中释放掉。我们前边又说过，采用 嵌套循环连接 算法的两表连接过程中，被驱动表可是要被访问好多次的，如果这个被驱动表中的数据特别多而且不能使用索引进行访问，那就相当于要从磁盘上读好几次这个表，这个 I/O 代价就非常大了，所以我们得想办法：尽量减少访问被驱动表的次数。
当被驱动表中的数据非常多时，每次访问被驱动表，被驱动表的记录会被加载到内存中，在内存中的每一条记录只会和驱动表结果集的一条记录做匹配，之后就会被从内存中清除掉。然后再从驱动表结果集中拿出另一条记录，再一次把被驱动表的记录加载到内存中一遍，周而复始，驱动表结果集中有多少条记录，就得把被驱动表从磁盘上加载到内存中多少次。所以我们可不可以在把被驱动表的记录加载到内存的时候，一次性和多条驱动表中的记录做匹配，这样就可以大大减少重复从磁盘上加载被驱动表的代价了。所以设计 MySQL 的大叔提出了一个join buffer 的概念， join buffer 就是执行连接查询前申请的一块固定大小的内存，先把若干条驱动表结果集中的记录装在这个 join buffer 中，然后开始扫描被驱动表，每一条被驱动表的记录一次性和 join buffer 中的多条驱动表记录做匹配，因为匹配的过程都是在内存中完成的，所以这样可以显著减少被驱动表的 I/O 代价。使用 join buffer 的过程如下图所示：
最好的情况是 join buffer 足够大，能容纳驱动表结果集中的所有记录，这样只需要访问一次被驱动表就可以完成连接操作了。设计 MySQL 的大叔把这种加入了 join buffer 的嵌套循环连接算法称之为 基于块的嵌套连接（Block Nested-Loop Join）算法。
另外需要注意的是，驱动表的记录并不是所有列都会被放到 join buffer 中，只有查询列表中的列和过滤条件中的列才会被放到 join buffer 中，所以再次提醒我们，最好不要把 * 作为查询列表，只需要把我们关心的列放到查询列表就好了，这样还可以在 join buffer 中放置更多的记录呢哈。