MYSQL系列SQL查询之JOIN

前文学习了SQL查询，重点学习如何建索引，如何避免索引失效和慢查询优化建议。本文重点学习下JOIN相关语法

相关概念

各种JOIN

连接分为三类：内连接、外连接、全连接

内连接

JOIN
INNER JOIN

外连接

LEFT JOIN
RIGHT JOIN

全连接

FULL JOIN
MYSQL不支持，可以用UNION代替

SELECT * FROM t1
LEFT JOIN t2 ON t1.id = t2.id
UNION
SELECT * FROM t1
RIGHT JOIN t2 ON t1.id = t2.id

驱动表与被驱动表

概念解释

驱动表在SQL语句执行的过程中，总是先读取。而被驱动表在SQL语句执行的过程中，总是后读取。

如何区分驱动表和被驱动表

可以使用explain命令查看一下SQL语句的执行计划。在输出的执行计划中，排在第一行的表是驱动表，排在第二行的表是被驱动表。

left join

左表示驱动表，右表示被驱动表。
select * from A as a left join B as b on a.id = b.id;
上述A left join B

right join

右表示驱动表，左表示被驱动表。
select * from A as a right join B as b on a.id = b.id;
上述A right join B

inner join

对于inner join 而言，MySQL 会选择小表 作为驱动表，大表 作为被驱动表。

小表选择：在决定哪个表做驱动表的时候，应该是两个表按照各自的条件过滤，过滤完成之后，计算参与 join 的各个字段的总数据量，数据量小的那个表，就是“小表”，应该作为驱动表。

straight_join

用 straight_join 让 MySQL 使用固定的连接方式执行查询，这样优化器只会按照我们指定的方式去 join
左表驱动右表

JOIN执行相关概念

构造数据

mysql> CREATE TABLE `t7` (
    ->   `id` int(11) NOT NULL,
    ->   `a` int(11) DEFAULT NULL,
    ->   `b` int(11) DEFAULT NULL,
    ->   PRIMARY KEY (`id`),
    ->   KEY `a` (`a`)
    -> ) ENGINE=InnoDB;
Query OK, 0 rows affected (0.05 sec)
mysql> delimiter ;;
mysql> create procedure idata()
    -> begin
    ->   declare i int;
    ->   set i=1;
    ->   while(i     insert into t7 values(i, i, i);
    ->     set i=i+1;
    ->   end while;
    -> end;;
Query OK, 0 rows affected (0.00 sec)

mysql> delimiter ;
mysql> call idata();
Query OK, 1 row affected (4.43 sec)

mysql> create table t6 like t7;
Query OK, 0 rows affected (0.03 sec)

mysql> insert into t6 (select * from t7 where id explain select * from t6 straight_join t7 on (t6.a=t7.a);
+----+-------------+-------+------------+------+---------------+------+---------+-----------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref       | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+------+---------+-----------+------+----------+-------------+
|  1 | SIMPLE      | t6    | NULL       | ALL  | a             | NULL | NULL    | NULL      |  100 |   100.00 | Using where |
|  1 | SIMPLE      | t7    | NULL       | ref  | a             | a    | 5       | toby.t6.a |    1 |   100.00 | NULL        |
+----+-------------+-------+------------+------+---------------+------+---------+-----------+------+----------+-------------+
2 rows in set, 1 warning (0.00 sec)

在这条语句里，被驱动表 t7 的字段 a 上有索引，join 过程用上了这个索引，因此这个语句的执行流程是这样的：

这个过程是先遍历表 t6，然后根据从表 t6 中取出的每行数据中的 a 值，去表 t7 中查找满足条件的记录。在形式上，这个过程就跟我们写程序时的嵌套查询类似，并且可以用上被驱动表的索引，所以我们称之为“Index Nested-Loop Join”，简称 NLJ。

在这个流程里：

在这个 join 语句执行过程中，驱动表是走全表扫描，而被驱动表是走树搜索。

假设被驱动表的行数是 M。每次在被驱动表查一行数据，要先搜索索引 a，再搜索主键索引。每次搜索一棵树近似复杂度是以 2 为底的 M 的对数，记为 log2M，所以在被驱动表上查一行的时间复杂度是 2*log2M。

假设驱动表的行数是 N，执行过程就要扫描驱动表 N 行，然后对于每一行，到被驱动表上匹配一次。

因此整个执行过程，近似复杂度是 N + N*2*log2M。

显然，N 对扫描行数的影响更大，因此应该让小表来做驱动表。

如果你没觉得这个影响有那么“显然”， 可以这么理解：N 扩大 1000 倍的话，扫描行数就会扩大 1000 倍；而 M 扩大 1000 倍，扫描行数扩大不到 10 倍。

到这里小结一下，通过上面的分析我们得到了两个结论：

Simple Nested-Loop Join

如果被驱动表用不上索引
select * from t6 straight_join t7 on (t6.a=t7.b);
t7没有索引，走的全表扫描，总共扫描100*1000=10万行

Block Nested-Loop Join

MySQL 也没有使用这个 Simple Nested-Loop Join 算法，而是使用了另一个叫作“Block Nested-Loop Join”的算法

mysql> explain select * from t6 straight_join t7 on (t6.a=t7.b);
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+----------------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                              |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+----------------------------------------------------+
|  1 | SIMPLE      | t6    | NULL       | ALL  | a             | NULL | NULL    | NULL |  100 |   100.00 | NULL                                               |
|  1 | SIMPLE      | t7    | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 1000 |    10.00 | Using where; Using join buffer (Block Nested Loop) |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+----------------------------------------------------+
2 rows in set, 1 warning (0.00 sec)

被驱动表上没有可用的索引，算法的流程是这样的：

在这个过程中，对表 t6 和 t7 都做了一次全表扫描，因此总的扫描行数是 1100。由于 join_buffer 是以无序数组的方式组织的，因此对表 t2 中的每一行，都要做 100 次判断，总共需要在内存中做的判断次数是：100*1000=10 万次。

前面我们说过，如果使用 Simple Nested-Loop Join 算法进行查询，扫描行数也是 10 万行。因此，从时间复杂度上来说，这两个算法是一样的。但是，Block Nested-Loop Join 算法的这 10 万次判断是内存操作，速度上会快很多，性能也更好。

接下来，我们来看一下，在这种情况下，应该选择哪个表做驱动表。

假设小表的行数是 N，大表的行数是 M，那么在这个算法里：

可以看到，调换这两个算式中的 M 和 N 没差别，因此这时候选择大表还是小表做驱动表，执行耗时是一样的。

join_buffer 的大小是由参数 join_buffer_size 设定的，默认值是 256k。如果放不下表 t1 的所有数据的话，策略很简单，就是分段放。

因此，算法归纳如下：

驱动表的数据行数是 N，需要分 K 段才能完成算法流程，被驱动表的数据行数是 M。

注意，这里的 K 不是常数，N 越大 K 就会越大，因此把 K 表示为λ*N，显然λ的取值范围是 (0,1)。

所以，在这个算法的执行过程中：

在 N+λNM 这个式子里，λ才是影响扫描行数的关键因素，这个值越小越好。λ受join_buffer_size影响

Multi-Range Read 优化

mysql> create table t8(id int primary key, a int, b int, index(a));
Query OK, 0 rows affected (0.03 sec)

mysql> create table t9 like t8;
Query OK, 0 rows affected (0.03 sec)


mysql> drop procedure idata1;
ERROR 1305 (42000): PROCEDURE toby.idata1 does not exist
mysql> delimiter ;;
mysql> create procedure idata1()
    -> begin
    ->   declare i int;
    ->   set i=1;
    ->   while(i     insert into t8 values(i, 1001-i, i);
    ->     set i=i+1;
    ->   end while;
    ->
    ->   set i=1;
    ->   while(i     insert into t9 values(i, i, i);
    ->     set i=i+1;
    ->   end while;
    ->
    -> end;;
Query OK, 0 rows affected (0.01 sec)

mysql> delimiter ;
mysql>
mysql>
mysql>
mysql> call idata1();

MRR优化的主要目的是尽量使用顺序读盘

如下SQL，普通索引查询会有回表过程
select * from t8 where a>=1 and a explain select * from t8 where a>=1 and a set optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';
Query OK, 0 rows affected (0.00 sec)

mysql> explain select * from t8 where a>=1 and a=1 and t9.b=1 and b=X and t2.c>=Y and t3.c>=Z;

第一原则是要尽量使用 BKA 算法。需要注意的是，使用 BKA 算法的时候，并不是“先计算两个表 join 的结果，再跟第三个表 join”，而是直接嵌套查询的。

具体实现是：在 t1.c>=X、t2.c>=Y、t3.c>=Z 这三个条件里，选择一个经过过滤以后，数据最少的那个表，作为第一个驱动表。此时，可能会出现如下两种情况。

第一种情况，如果选出来是表 t1 或者 t3，那剩下的部分就固定了。

同时，我们还需要在第一个驱动表的字段 c 上创建索引。

第二种情况是，如果选出来的第一个驱动表是表 t2 的话，则需要评估另外两个条件的过滤效果。

总之，整体的思路就是，尽量让每一次参与 join 的驱动表的数据集，越小越好，因为这样我们的驱动表就会越小。

延伸

延伸1：使用 Block Nested-Loop Join 算法，可能会因为 join_buffer 不够大，需要对被驱动表做多次全表扫描，会产生哪些问题？

如果这个被驱动表是一个大的冷数据表，除了会导致 IO 压力大以外，还会对系统有什么影响呢？

由于 InnoDB 对 Bufffer Pool 的 LRU 算法做了优化，即：第一次从磁盘读入内存的数据页，会先放在 old 区域。如果 1 秒之后这个数据页不再被访问了，就不会被移动到 LRU 链表头部，这样对 Buffer Pool 的命中率影响就不大。

但是，如果一个使用 BNL 算法的 join 语句，多次扫描一个冷表，而且这个语句执行时间超过 1 秒，就会在再次扫描冷表的时候，把冷表的数据页移到 LRU 链表头部。

这种情况对应的，是冷表的数据量小于整个 Buffer Pool 的 3/8，能够完全放入 old 区域的情况。

如果这个冷表很大，就会出现另外一种情况：业务正常访问的数据页，没有机会进入 young 区域。

大表 join 操作虽然对 IO 有影响，但是在语句执行结束后，对 IO 的影响也就结束了。但是，对 Buffer Pool 的影响就是持续性的，需要依靠后续的查询请求慢慢恢复内存命中率。

BNL 算法对系统的影响主要包括三个方面：

参考：
1.MySQL中的各种join
2.MySQL中的驱动表和被驱动表的解读
3.MYSQL实战45讲