14-基于规则的优化

14.2 外连接消除

外连接和内连接的本质区别就是：对于外连接的驱动表的记录来说，如果无法在被驱动表中找到匹配ON子句中的过滤条件的记录，那么该记录仍然会被加入到结果集中，对应的被驱动表记录的各个字段使用NULL值填充；而内连接的驱动表的记录如果无法在被驱动表中找到匹配ON子句中的过滤条件的记录，那么该记录会被舍弃

比如下面两个表t1、t2

mysql> select * from t1;
+------+------+
| m1   | n1   |
+------+------+
|    1 | a    |
|    2 | b    |
|    3 | c    |
+------+------+
    
mysql> select * from t2;
+------+------+
| m2   | n2   |
+------+------+
|    2 | b    |
|    3 | c    |
|    4 | d    |
+------+------+

使用外连接，没匹配上的会填充NULl

mysql> select * from t1 left join t2 on t1.m1 = t2.m2;
+------+------+------+------+
| m1   | n1   | m2   | n2   |
+------+------+------+------+
|    1 | a    | NULL | NULL |
|    2 | b    |    2 | b    |
|    3 | c    |    3 | c    |
+------+------+------+------+

使用内连接，没匹配上的就舍弃

mysql> select * from t1 inner join t2 on t1.m1 = t2.m2;
+------+------+------+------+
| m1   | n1   | m2   | n2   |
+------+------+------+------+
|    2 | b    |    2 | b    |
|    3 | c    |    3 | c    |
+------+------+------+------+

只要我们在搜索条件中指定关于被驱动表相关列的值不为NULL，那么外连接中在被驱动表中找不到符合ON子句条件的驱动表记录也就被排除出最后的结果集了，在这种情况下，外连接和内连接也就没有什么区别了

mysql> select * from t1 left join t2 on t1.m1 = t2.m2 where t2.n2 is not null;
+------+------+------+------+
| m1   | n1   | m2   | n2   |
+------+------+------+------+
|    2 | b    |    2 | b    |
|    3 | c    |    3 | c    |
+------+------+------+------+

或者这样

mysql> select * from t1 left join t2 on t1.m1 = t2.m2 where t2.m2 = 2;
+------+------+------+------+
| m1   | n1   | m2   | n2   |
+------+------+------+------+
|    2 | b    |    2 | b    |
+------+------+------+------+

这种在外连接查询中，指定的WHERE子句中包含被驱动表中的列不为NULL值的条件称之为空值拒绝

在被驱动表的WHERE子句符合空值拒绝的条件后，外连接和内连接可以相互转换。这种转换带来的好处就是查询优化器可以通过评估表的不同连接顺序的成本，选出成本最低的那种连接顺序来执行查询

14.3 子查询优化

放在FROM子句后面的子查询称为派生表

1、按返回的结果集区分子查询

• 标量子查询：只返回一个单一值的子查询

SELECT (SELECT m1 FROM t1 LIMIT 1);
SELECT * FROM t1 WHERE m1 = (SELECT MIN(m2) FROM t2);

• 行子查询：返回一条记录的子查询，包含多个列

SELECT * FROM t1 WHERE (m1, n1) = (SELECT m2, n2 FROM t2 LIMIT 1);

• 列子查询：查询出一个列的数据

SELECT * FROM t1 WHERE m1 IN (SELECT m2 FROM t2);

• 表子查询：子查询的结果既包含很多条记录，又包含很多个列

SELECT * FROM t1 WHERE (m1, n1) IN (SELECT m2, n2 FROM t2);

2、按与外层查询关系来区分子查询

• 不相关子查询：如果子查询可以单独运行出结果，而不依赖于外层查询的值

• 相关子查询：子查询的执行需要依赖于外层查询的值

SELECT * FROM t1 WHERE m1 IN (SELECT m2 FROM t2 WHERE n1 = n2);

3、子查询在布尔表达式中的使用

• 使用=、>、<、>=、<=、<>、!=、<=>作为布尔表达式的操作符

这里的子查询只能是标量子查询或者行子查询，例如

-- 操作数 comparison_operator (子查询)
SELECT * FROM t1 WHERE m1 < (SELECT MIN(m2) FROM t2);
SELECT * FROM t1 WHERE (m1, n1) = (SELECT m2, n2 FROM t2 LIMIT 1);

• [NOT] IN/ANY/SOME/ALL子查询

（1）IN或者NOT IN

-- 操作数 [NOT] IN (子查询)
SELECT * FROM t1 WHERE (m1, n2) IN (SELECT m2, n2 FROM t2);

（2）ANY/SOME

只要子查询结果集中存在某个值和给定的操作数做comparison_operator比较结果为TRUE，那么整个表达式的结果就为TRUE

-- 操作数 comparison_operator ANY/SOME(子查询)
SELECT * FROM t1 WHERE m1 > ANY(SELECT m2 FROM t2);

=ANY相当于判断子查询结果集中是否存在某个值和给定的操作数相等，它的含义和IN是相同的

（3）ALL

子查询结果集中所有的值和给定的操作数做comparison_operator比较结果为TRUE，那么整个表达式的结果就为TRUE

-- 操作数 comparison_operator ALL(子查询)
SELECT * FROM t1 WHERE m1 > ALL(SELECT m2 FROM t2);

• EXISTS子查询

有时候我们仅仅需要判断子查询的结果集中是否有记录，而不在乎记录具体是什么

SELECT * FROM t1 WHERE EXISTS (SELECT 1 FROM t2);

对于子查询(SELECT 1 FROM t2)来说，我们并不关心这个子查询最后到底查询出的结果是什么，所以查询列表里填*、某个列名都无所谓，我们真正关心的是子查询的结果集中是否存在记录。也就是说只要(SELECT 1 FROM t2)这个查询中有记录，那么整个EXISTS表达式的结果就为 TRUE

14.3.2 子查询在MySQL中是怎么执行的

2、标量子查询、行子查询的执行方式

对于包含不相关的标量子查询或者行子查询的查询语句来说，MySQL会分别独立的执行外层查询和子查询，就当作两个单表查询就好了

3、IN子查询优化

（1）物化表的提出

对于不相关的IN子查询，如果单独执行子查询后的结果集太多，可能内存中放不下

所以，MySQL不直接将不相关子查询的结果集当作外层查询的参数，而是将该结果集写入一个临时表里，并建立索引

• 该临时表的列就是子查询结果集中的列

• 写入临时表的记录会被去重

• 将子查询结果集中的记录保存到临时表的过程称之为物化
• 存储子查询结果集的临时表称之为物化表

正因为物化表中的记录都建立了索引（基于内存的物化表有哈希索引，基于磁盘的有B+树索引），通过索引执行IN语句判断某个操作数在不在子查询结果集中变得非常快，从而提升了子查询语句的性能

（2）物化表转连接

将s1表和s2表进行半连接的意思就是：对于s1表的某条记录来说，我们只关心在s2表中是否存在与之匹配的记录是否存在，而不关心具体有多少条记录与之匹配，最终的结果集中只保留s1表的记录

半连接的方法

• Table pullout（子查询中的表上拉）

当子查询的查询列表处只有主键或者唯一索引列时，可以直接把子查询中的表上拉到外层查询的FROM 子句中，并把子查询中的搜索条件合并到外层查询的搜索条件中

SELECT * FROM s1
    WHERE key2 IN (SELECT key2 FROM s2 WHERE key3 = 'a');

由于key2列是s2表的唯一二级索引列，所以我们可以直接把s2表上拉到外层查询的FROM子句中，并且把子查询中的搜索条件合并到外层查询的搜索条件中

SELECT s1.* FROM s1 INNER JOIN s2      
    ON s1.key2 = s2.key2
    WHERE s2.key3 = 'a';

• Duplicate Weedout （重复值消除）

对于这个查询来说：

SELECT * FROM s1
    WHERE key1 IN (SELECT common_field FROM s2 WHERE key3 = 'a');

转换为半连接查询后，s1表中的某条记录可能在s2表中有多条匹配的记录，所以该条记录可能多次被添加到最后的结果集中，为了消除重复，我们可以建立一个临时表

CREATE TABLE tmp (
    id PRIMARY KEY  
);

这样在执行连接查询的过程中，每当某条s1表中的记录要加入结果集时，就首先把这条记录的id值加入到这个临时表里，如果添加成功，说明之前这条s1表中的记录并没有加入最终的结果集，现在把该记录添加到最终的结果集；如果添加失败，说明这条之前这条s1表中的记录已经加入过最终的结果集，这里直接把它丢弃就好了

• LooseScan（松散扫描）

SELECT * FROM s1
    WHERE key3 IN (SELECT key1 FROM s2 WHERE key1 > 'a' AND key1 < 'b');

在子查询中，对于s2表的访问可以使用到key1列的索引，而恰好子查询的查询列表处就是key1列，这样在将该查询转换为半连接查询后，如果将s2作为驱动表执行查询的话,在s2表的idx_key1索引中，值为'aa'的二级索引记录一共有3条，那么只需要取第一条的值到s1表中查找 s1.key3 = 'aa'的记录，如果能在s1表中找到对应的记录，那么就把对应的记录加入到结果集。依此类推，其他值相同的二级索引记录，也只需要取第一条记录的值到s1表中找匹配的记录，这种虽然是扫描索引，但只取值相同的第一条记录去执行匹配的方式称之为LooseScan

• Semi-join Materialization（半连接物化）

之前介绍的先把外层查询的IN子句中的不相关子查询进行物化，然后再进行外层查询的表和物化表的连接本质上也算是一种semi-join，只不过由于物化表中没有重复的记录，所以可以直接将子查询转为连接查询

• FirstMatch（首次匹配）

FirstMatch是一种最原始的半连接执行方式，就是先取一条外层查询的中的记录，然后到子查询的表中寻找符合匹配条件的记录，如果能找到一条，则将该外层查询的记录放入最终的结果集并且停止查找更多匹配的记录，如果找不到则把该外层查询的记录丢弃掉；然后再开始取下一条外层查询中的记录

由于相关子查询并不是一个独立的查询，所以不能转换为物化表来执行查询

如果不能转为半连接，可以有两种方法

• 对于不相关子查询，可以尝试把它们物化之后再参与查询

SELECT * FROM s1
    WHERE key1 NOT IN (SELECT common_field FROM s2 WHERE key3 = 'a')

先将子查询物化，然后再判断key1是否在物化表的结果集中可以加快查询执行的速度

• 不管子查询是相关的还是不相关的，都可以把IN子查询尝试专为EXISTS子查询

6、对于派生表的优化

• 派生表物化

我们可以将派生表的结果集写到一个内部的临时表中，然后就把这个物化表当作普通表一样参与查询

延迟物化：在查询中真正使用到派生表时才回去尝试物化派生表，而不是还没开始执行查询呢就把派生表物化掉

• 将派生表与外层查询合并

SELECT * FROM (
        SELECT * FROM s1 WHERE key1 = 'a'      
    ) AS derived_s1 INNER JOIN s2
    ON derived_s1.key1 = s2.key1
    WHERE s2.key2 = 1;

合并为

SELECT * FROM s1 INNER JOIN s2
    ON s1.key1 = s2.key1
    WHERE s1.key1 = 'a' AND s2.key2 = 1;

当派生表中有这些函数或语句时，就不可以和外层查询合并

• 聚集函数，比如MAX()、MIN()、SUM()
• DISTINCT
• GROUP BY
• HAVING
• LIMIT
• UNION 或者 UNION ALL
• 派生表对应的子查询的SELECT子句中含有另一个子查询

MySQL在执行带有派生表的时候，优先尝试把派生表和外层查询合并掉，如果不行的话，再把派生表物化掉执行查询