示例表

CREATE TABLE single_table (
    id INT NOT NULL AUTO_INCREMENT,
    key1 VARCHAR(100),
    key2 INT,
    key3 VARCHAR(100),
    key_part1 VARCHAR(100),
    key_part2 VARCHAR(100),
    key_part3 VARCHAR(100),
    common_field VARCHAR(100),
    PRIMARY KEY (id),
    KEY idx_key1 (key1),
    UNIQUE KEY idx_key2 (key2),
    KEY idx_key3 (key3),
    KEY idx_key_part(key_part1, key_part2, key_part3)
) Engine=InnoDB CHARSET=utf8;

小白们眼中子查询的执行方式

如果该子查询是不相关子查询，比如下边这个查询：

SELECT * FROM s1 
    WHERE key1 IN (SELECT common_field FROM s2);

先单独执行(SELECT common_field FROM s2)这个子查询。
然后在将上一步子查询得到的结果当作外层查询的参数再执行外层查询SELECT * FROM s1 WHERE key1 IN (…)。

如果该子查询是相关子查询，比如下边这个查询：

SELECT * FROM s1 
    WHERE key1 IN (SELECT common_field FROM s2 WHERE s1.key2 = s2.key2);

先从外层查询中获取一条记录，本例中也就是先从s1表中获取一条记录。
然后从上一步骤中获取的那条记录中找出子查询中涉及到的值，本例中就是从s1表中获取的那条记录中找出s1.key2列的值，然后执行子查询。
最后根据子查询的查询结果来检测外层查询WHERE子句的条件是否成立，如果成立，就把外层查询的那条记录加入到结果集，否则就丢弃。
再次执行第一步，获取第二条外层查询中的记录，依次类推～

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

使用到标量子查询或者行子查询的场景:

SELECT子句中，我们前边说过的在查询列表中的子查询必须是标量子查询。
子查询使用=、>、<、>=、<=、<>、!=、<=>等操作符和某个操作数组成一个布尔表达式，这样的子查询必须是标量子查询或者行子查询。

不相关标量子查询或者行子查询:

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

它的执行方式:

先单独执行(SELECT common_field FROM s2 WHERE key3 = ‘a’ LIMIT 1)这个子查询。
然后在将上一步子查询得到的结果当作外层查询的参数再执行外层查询SELECT * FROM s1 WHERE key1 = …。

对于相关的标量子查询或者行子查询:

SELECT * FROM s1 WHERE 
    key1 = (SELECT common_field FROM s2 WHERE s1.key3 = s2.key3 LIMIT 1);

它的执行方式:

先从外层查询中获取一条记录，本例中也就是先从s1表中获取一条记录。
然后从上一步骤中获取的那条记录中找出子查询中涉及到的值，本例中就是从s1表中获取的那条记录中找出s1.key3列的值，然后执行子查询。
最后根据子查询的查询结果来检测外层查询WHERE子句的条件是否成立，如果成立，就把外层查询的那条记录加入到结果集，否则就丢弃。
再次执行第一步，获取第二条外层查询中的记录，依次类推～

IN子查询优化

物化表

对于不相关的IN子查询:

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

如果单独执行子查询后的结果集太多的话，就会导致这些问题：

结果集太多，可能内存中都放不下～
对于外层查询来说，如果子查询的结果集太多，那就意味着IN子句中的参数特别多，这就导致：
- 无法有效的使用索引，只能对外层查询进行全表扫描。(回表成本)
- 在对外层查询执行全表扫描时，由于IN子句中的参数太多，这会导致检测一条记录是否符合和IN子句中的参数匹配花费的时间太长。(每条记录在检测是否符合 IN 时, 时间复杂度为 O(n), 所有的就是 O(m*n))

于是乎设计MySQL的大叔想了一个招：不直接将不相关子查询的结果集当作外层查询的参数，而是将该结果集写入一个临时表里。写入临时表的过程是这样的：

该临时表的列就是子查询结果集中的列。
写入临时表的记录会被去重。
一般情况下子查询结果集不会大的离谱，所以会为它建立基于内存的使用Memory存储引擎的临时表，而且会为该表建立哈希索引。
- IN语句的本质就是判断某个操作数在不在某个集合里，如果集合中的数据建立了哈希索引，那么这个匹配的过程就是超级快的。
如果子查询的结果集非常大，超过了系统变量tmp_table_size或者max_heap_table_size，临时表会转而使用基于磁盘的存储引擎来保存结果集中的记录，索引类型也对应转变为B+树索引。

设计MySQL的大叔把这个将子查询结果集中的记录保存到临时表的过程称之为物化（英文名：Materialize）。为了方便起见，我们就把那个存储子查询结果集的临时表称之为物化表。正因为物化表中的记录都建立了索引（基于内存的物化表有哈希索引，基于磁盘的有B+树索引），通过索引执行IN语句判断某个操作数在不在子查询结果集中变得非常快，从而提升了子查询语句的性能。

时间复杂度变为 O(1) 或 O(logN).

物化表转连接

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

有两个角度理解:

从表s1的角度来看待，整个查询的意思其实是：对于s1表中的每条记录来说，如果该记录的key1列的值在子查询对应的物化表中，则该记录会被加入最终的结果集。

从子查询物化表的角度来看待，整个查询的意思其实是：对于子查询物化表的每个值来说，如果能在s1表中找到对应的key1列的值与该值相等的记录，那么就把这些记录加入到最终的结果集。

也就是说其实上边的查询就相当于表s1和子查询物化表materialized_table进行内连接：

SELECT s1.* FROM s1 INNER JOIN materialized_table ON key1 = m_val;

查询优化器可以评估不同连接顺序需要的成本是多少，选取成本最低的那种查询方式执行查询。我们分析一下上述查询中使用外层查询的表s1和物化表materialized_table进行内连接的成本都是由哪几部分组成的：

如果使用s1表作为驱动表的话，总查询成本由下边几个部分组成：

物化子查询时需要的成本
扫描s1表时的成本
s1表中的记录数量 × 通过m_val = xxx对materialized_table表进行单表访问的成本（我们前边说过物化表中的记录是不重复的，并且为物化表中的列建立了索引，所以这个步骤显然是非常快的）。

如果使用materialized_table表作为驱动表的话，总查询成本由下边几个部分组成：

物化子查询时需要的成本
扫描物化表时的成本
物化表中的记录数量 × 通过key1 = xxx对s1表进行单表访问的成本（非常庆幸key1列上建立了索引，所以这个步骤是非常快的）。

将子查询转换为semi-join

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

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

不物化, 直接连接, 但是有去重操作.

假设MySQL内部是这么改写上边的子查询的：

SELECT s1.* FROM s1 SEMI JOIN s2
    ON s1.key1 = s2.common_field
    WHERE key3 = 'a';

怎么实现这种所谓的半连接呢?

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

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

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

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

DuplicateWeedout execution strategy （重复值消除）

对于这个查询来说：

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表中的记录已经加入过最终的结果集，这里直接把它丢弃就好了，这种使用临时表消除semi-join结果集中的重复值的方式称之为DuplicateWeedout。

LooseScan execution strategy （松散扫描）

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

在子查询中，对于s2表的访问可以使用到key1列的索引，而恰好子查询的查询列表处就是key1列，这样在将该查询转换为半连接查询后，如果将s2作为驱动表执行查询的话，那么执行过程就是这样：

s2 作为驱动表的原因可能是因为子查询的结果集数量少.

上面的 WHERE key1 > 'a' AND key1 < 'b' 与图中不符.

如图所示，在s2表的idx_key1索引中，值为’aa’的二级索引记录一共有3条，那么只需要取第一条的值到s1表中查找s1.key3 = ‘aa’的记录，如果能在s1表中找到对应的记录，那么就把对应的记录加入到结果集。依此类推，其他值相同的二级索引记录，也只需要取第一条记录的值到s1表中找匹配的记录，这种虽然是扫描索引，但只取值相同的记录的第一条去做匹配操作的方式称之为松散扫描。

Semi-join Materialization execution strategy

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

FirstMatch execution strategy （首次匹配）

就是说先取一条外层查询的中的记录，然后到子查询的表中寻找符合匹配条件的记录，如果能找到一条，则将该外层查询的记录放入最终的结果集并且停止查找更多匹配的记录，如果找不到则把该外层查询的记录丢弃掉；然后再开始取下一条外层查询中的记录，重复上边这个过程。

对于某些使用IN语句的相关子查询，比方这个查询：

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

它也可以很方便的转为半连接，转换后的语句类似这样：

SELECT s1.* FROM s1 SEMI JOIN s2 
    ON s1.key1 = s2.common_field AND s1.key3 = s2.key3;

然后就可以使用我们上边介绍过的DuplicateWeedout、LooseScan、FirstMatch等半连接执行策略来执行查询，当然，如果子查询的查询列表处只有主键或者唯一二级索引列，还可以直接使用table pullout的策略来执行查询，但是需要大家注意的是，由于相关子查询并不是一个独立的查询，所以不能转换为物化表来执行查询。

semi-join的适用条件

只有形如这样的查询才可以被转换为semi-join：

SELECT ... FROM outer_tables 
    WHERE expr IN (SELECT ... FROM inner_tables ...) AND ...

SELECT ... FROM outer_tables 
    WHERE (oe1, oe2, ...) IN (SELECT ie1, ie2, ... FROM inner_tables ...) AND ...

该子查询必须是和IN语句组成的布尔表达式，并且在外层查询的WHERE或者ON子句中出现。
外层查询也可以有其他的搜索条件，只不过和IN子查询的搜索条件必须使用AND连接起来。
该子查询必须是一个单一的查询，不能是由若干查询由UNION连接起来的形式。
该子查询不能包含GROUP BY或者HAVING语句或者聚集函数。

不适用于semi-join的情况

外层查询的WHERE条件中有其他搜索条件与IN子查询组成的布尔表达式使用OR连接起来

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

使用NOT IN而不是IN的情况

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

在SELECT子句中的IN子查询的情况

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

子查询中包含GROUP BY、HAVING或者聚集函数的情况

SELECT * FROM s1 
    WHERE key2 IN (SELECT COUNT(*) FROM s2 GROUP BY key1);

子查询中包含UNION的情况

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

MySQL仍然留了两手绝活来优化不能转为semi-join查询的子查询:

对于不相关子查询来说，可以尝试把它们物化之后再参与查询
- 请注意这里将子查询物化之后不能转为和外层查询的表的连接，只能是先扫描s1表，然后对s1表的某条记录来说，判断该记录的key1值在不在物化表中。

# NOT IN 不能 semi-join
SELECT * FROM s1 
    WHERE key1 NOT IN (SELECT common_field FROM s2 WHERE key3 = 'a')

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

outer_expr IN (SELECT inner_expr FROM ... WHERE subquery_where)

# 可以被转换为
EXISTS (SELECT inner_expr FROM ... WHERE subquery_where AND outer_expr=inner_expr)

为啥要转换呢？这是因为不转换的话可能用不到索引，比方说下边这个查询：

SELECT * FROM s1
    WHERE key1 IN (SELECT key3 FROM s2 where s1.common_field = s2.common_field) 
        OR key2 > 1000;

这个查询中的子查询是一个相关子查询，而且子查询执行的时候不能使用到索引，但是将它转为EXISTS子查询后却可以使用到索引：

转为EXISTS子查询时便可以使用到s2表的idx_key3索引了。

SELECT * FROM s1
    WHERE EXISTS (SELECT 1 FROM s2 where s1.common_field = s2.common_field AND s2.key3 = s1.key1) 
        OR key2 > 1000;

ANY/ALL子查询优化

如果ANY/ALL子查询是不相关子查询的话，它们在很多场合都能转换成我们熟悉的方式去执行，比方说：

原始表达式转换为< ANY (SELECT inner_expr …) < (SELECT MAX(inner_expr) …)
> ANY (SELECT inner_expr …) > (SELECT MIN(inner_expr) …)
< ALL (SELECT inner_expr …) < (SELECT MIN(inner_expr) …)
> ALL (SELECT inner_expr …) > (SELECT MAX(inner_expr) …)

[NOT] EXISTS子查询的执行

如果[NOT] EXISTS子查询是不相关子查询，可以先执行子查询，得出该[NOT] EXISTS子查询的结果是TRUE还是FALSE，并重写原先的查询语句，比如对这个查询来说：

SELECT * FROM s1 
    WHERE EXISTS (SELECT 1 FROM s2 WHERE key1 = 'a') 
        OR key2 > 100;

因为这个语句里的子查询是不相关子查询，所以优化器会首先执行该子查询，假设该EXISTS子查询的结果为TRUE，那么接着优化器会重写查询为：

SELECT * FROM s1 
    WHERE TRUE OR key2 > 100;

# 进一步简化后就变成了
SELECT * FROM s1 
    WHERE TRUE;

对于相关的[NOT] EXISTS子查询来说，比如这个查询：

SELECT * FROM s1 
    WHERE EXISTS (SELECT 1 FROM s2 WHERE s1.common_field = s2.common_field);

很不幸，这个查询只能按照我们年少时的那种执行相关子查询的方式来执行。不过如果[NOT] EXISTS子查询中如果可以使用索引的话，那查询速度也会加快不少，比如：

SELECT * FROM s1 
    WHERE EXISTS (SELECT 1 FROM s2 WHERE s1.common_field = s2.key1);

对于派生表的优化

把子查询放在外层查询的FROM子句后，那么这个子查询的结果相当于一个派生表:

SELECT * FROM  (
        SELECT id AS d_id,  key3 AS d_key3 FROM s2 WHERE key1 = 'a'
    ) AS derived_s1 WHERE d_key3 = 'a';

对于含有派生表的查询，MySQL提供了两种执行策略：

把派生表物化
将派生表和外层的表合并，也就是将查询重写为没有派生表的形式

MySQL 是怎样运行的

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

示例表