Table of Contents
- 1. 嵌套查询的分类和优化概述
- 2. Kim: On Optimizing an SQL-like Nested Query
- 3. Kiessling, SQL-Like and Quel-like correlation queries with aggregates revisited
- 4. Ganski, Wong: Optimization of Nested SQL Queries Revisited
- 5. 总结
嵌套查询是 SQL 中表达能力很强的一种机制，既给应用带来了方便也给查询优化带来了很大的挑战。本文总结一下经典的单机系统对嵌套查询的优化。
1 嵌套查询的分类和优化概述
比较好的分类和处理了典型嵌套查询的经典文献是 Kim 的 On Optimizing an SQL-like Nested Query 1。不过 Kim 的算法很快被发现在特定场景下存在一些小缺陷，需要打补丁修复。例如 Ganski 等对此做了改进 2。SQL 语言的进化过程中不断引入的新特性，也会影响到嵌套查询的处理，例如某些系统支持的 LIMIT 语句。具体产品中的实现可以从 ORACLE 的博客中得到一些启示：3，4。
2 Kim: On Optimizing an SQL-like Nested Query
Kim 定义了嵌套查询的 5 种基本形式并给出了转换算法。最后组合成一个通用算法来处理任意复杂的嵌套查询（一般称为嵌套查询的非嵌套化）。在一个 SQL 语句中访问多个表的典型机制为： 连接谓词（JOIN）、嵌套谓词、除法谓词。非嵌套化就是把其他两种形式的查询转换为 JOIN。嵌套谓词会形成 4 种形式的嵌套查询，而除法谓词会形成另 1 种形式的嵌套查询，因此总共是 5 种。考虑到除法几乎没有系统实现它，后续可以略过。
2.1 嵌套查询的分类
首先，定义嵌套的层数。如果查询中只有一个查询块（SELECT、FROM、WHERE），显然不存在嵌套查询，此时嵌套的层数为0。如果查询中有两个查询块，外查询的叫做外部块，内查询的叫做内部块，此时嵌套层数为1。查询块嵌套的层次数显然可以更多，而且一个 WHERE 条件中可以有多个嵌套的子查询。查询块的 FROM 子句后面可以出现多个表。WHERE 条件以及子查询的结果列也可以出现多个，例如：(SNO, SNAME) = (SELECT SNO, SNAME FROM SUPPLY)。Kim 划分嵌套查询种类是从子查询有没有连接条件以及聚集函数这两个角度考虑的。
2.1.1 A 类
内查询块没有对外查询块的表的引用（非相关子查询），并且查询结果是聚集函数（不带 GROUP BY，结果集是单行）。
SELECT SNO
FROM SHIPMENT
WHERE PNO = (SELECT MAX(PNO)
FROM PART
WHERE PRICE > 25)
SELECT SNO FROM SHIPMENT WHERE PNO = (SELECT MAX(PNO) FROM PART WHERE PRICE > 25)
2.1.2 N 类
内查询块没有对外查询块的表的引用（非相关子查询），并且查询结果没有聚集函数（结果集是很可能是多行）。
SELECT SNO
FROM SHIPMENT
WHERE PNO IN (SELECT PNO
FROM PART
WHERE PRICE > 25)
SELECT SNO FROM SHIPMENT WHERE PNO IN (SELECT PNO FROM PART WHERE PRICE > 25)
2.1.3 J 类
内查询块有对外查询块的表的引用（相关子查询），并且查询结果没有聚集函数。
SELECT SNO
FROM SHIPMENT
WHERE PNO IN (SELECT PNO
FROM PROJECT
WHERE SHIPMENT.SNO = PROJECT.JNO AND JLOC = 'NEW YORK')
SELECT SNO FROM SHIPMENT WHERE PNO IN (SELECT PNO FROM PROJECT WHERE SHIPMENT.SNO = PROJECT.JNO AND JLOC = 'NEW YORK')
2.1.4 JA 类
内查询块有对外查询块的表的引用（相关子查询），并且查询结果集有聚集函数。
SELECT SNO
FROM SHIPMENT
WHERE PNO = (SELECT MAX(PNO)
FROM PROJECT
WHERE PROJECT.JNO = SHIPMENT.JNO AND JLOC = 'NEW YORK')
SELECT SNO FROM SHIPMENT WHERE PNO = (SELECT MAX(PNO) FROM PROJECT WHERE PROJECT.JNO = SHIPMENT.JNO AND JLOC = 'NEW YORK')
2.1.5 D 类
连接谓词与除法谓词一起形成的查询中，带有两个内查询块。任何一个的连接谓词引用了外查询块都会形成 D 型嵌套查询。
SELECT SNAME
FROM SUPPLIER
WHERE (SELECT PNO
FROM SHIPMENT
WHERE SHIPMENT.SNO = SUPPLIER.SNO)
CONTAINS
(SELECT PNO
FROM PART
WHERE COLOR = 'RED' AND PRICE > 25)
2.2 嵌套查询的优化
如果采用最简单直接的执行算法，对外查询块的每条记录，需要执行内查询块一次。A 类查询的子查询可以只计算一次，因此不再需要做特殊的转换或优化。N 类没有这么直接的优化，有必要做优化。J、JA、D 类存在类似的问题。
N 类的嵌套查询可以被等价转换为连接。对于子查询可能会产生的重复值，可通过 semi-join 来消除。op 可以是 IN 或标量操作符。（注意，标量运算符要求结果集是单行。）嵌套1层的转换算法比较直接，命名为 NEST-N-J。J 类的嵌套查询也可以用类似的算法来转换。对于 NOT IN 操作符，要采用 anti-join。而且，对于 J 类的查询，还要确保 anti-join 的计算是发生在 join 条件之后。
JA 类的查询可以引入一个做聚集运算的临时表来等价转换为 J 类查询，算法命名为 NEST-JA。op 是个标量操作（因此不需要考虑重复值），查询最终被转换为 join。多层嵌套的 JA 类查询也可以被转换为 J 类查询。
3 Kiessling, SQL-Like and Quel-like correlation queries with aggregates revisited
略。
4 Ganski, Wong: Optimization of Nested SQL Queries Revisited
解决了 Kim 算法 NEST-JA 中的缺陷，并扩展到 SQL 中常见的子句，包括 EXISTS、NOT EXISTS、ANY、ALL 等。
4.1 COUNT
SELECT PNUM FROM PARTS WHERE QOH = (SELECT COUNT(SHIPDATE) FROM SUPPLY WHERE SUPPLY.PNUM = PARTS.PNUM AND SHIPDATE < '1-1-80')
算法引入的临时表在处理聚集函数时会丢失掉记录，从而导致最终结果少了。临时表丢失记录的问题可以通过外连接解决。如果内查询中用的是 COUNT(*)，还需要在转换时改成 COUNT(col)，以避免因为外连接引入的 NULL 导致的计数增加。
4.2 非等值条件
类似的，非等值条件也存在丢失信息的问题，也可以通过连接来解决（如果是 COUNT，则要用外连接）。
4.3 重复值
如果连接的列上有重复值，连接操作会放大结果集的记录数。不过它们只可能影响 COUNT、AVG、SUM，而不会影响 MAX、MIN。在产生临时表之前还要加一步，投影去掉连接列上的重复值。
5 总结
容易发现，嵌套查询的非嵌套化未必是最优的，Kim 等的论文中都有代价分析。逐步改进（打补丁）的做法也逐步增加了转换后查询的处理代价，需要代价优化器来判断转换是否有必要。
Footnotes:
1
Kim, On Optimizing an SQL-like Nested Query.
2
R.A. Ganski etc., Optimization of nested SQL queries revisited.
3
https://blogs.oracle.com/optimizer/entry/optimizer_transformations_subquery_unesting_part_1
4
https://blogs.oracle.com/optimizer/entry/optimizer_transformations_subquery_unesting_part_2