嵌套查询的查询优化

Table of Contents

嵌套查询是 SQL 中表达能力很强的一种机制，既给应用带来了方便也给查询优化带来了很大的挑战。本文总结一下经典的单机系统对嵌套查询的优化，来体现这个领域的复杂性。至于更加通用的查询改写机制，尤其是任意相关子查询的改写，留待以后的文章进行总结。

1 嵌套查询的分类和优化概述

比较好的分类和处理了典型嵌套查询的经典文献是 Kim 的 On Optimizing an SQL-like Nested Query 1。不过 Kim 的算法很快被发现在特定场景下存在一些小缺陷 2，需要打补丁修复。例如 Ganski 等对此做了改进 3。SQL 语言的进化过程中不断引入的新特性，也会影响到嵌套查询的处理，例如现在不少系统支持的 LIMIT 语句。具体产品中的实现可以从 ORACLE 的博客中得到一些启示：4，5。

2 Kim: On Optimizing an SQL-like Nested Query

Kim 定义了嵌套查询的 5 种基本形式并给出了转换算法。最后组合成一个通用算法来处理任意复杂的嵌套查询（一般称为嵌套查询的非嵌套化）。在一个 SQL 语句中访问多个表的典型机制为：连接谓词（JOIN）、嵌套谓词、除法谓词。非嵌套化就是把其他两种形式的查询转换为 JOIN。嵌套谓词会形成 4 种形式的嵌套查询，而除法谓词会形成另 1 种形式的嵌套查询，因此总共是 5 种。考虑到除法几乎没有系统实现它，后续可以略过。

2.1 嵌套查询的分类

首先，明确一下查询块的含义。一般而言，一个带有 SELECT、FROM、WHERE 三种子句的查询才是一个完整的查询。因此，这样的一个查询被称为一个查询块（Query Block，QB）。不过也存在一些别的情况，例如很多系统里头允许 SELECT 后面不带 FROM；HAVING 也会起到类似 WHERE 的作用。简单一点看，一个 SELECT 子句就代表了一个查询块；WHERE 子句和 HAVING 子句是联系不同查询块的纽带。

其次，定义嵌套的层数。如果查询中只有一个查询块，显然不存在嵌套查询，此时嵌套的层数为0。如果查询中有两个查询块，外查询的叫做外部块，内查询的叫做内部块，此时嵌套层数为1。查询块嵌套的层次数显然可以更多，而且一个 WHERE 条件中可以有多个嵌套的子查询。查询块的 FROM 子句后面可以出现多个表。WHERE 条件以及子查询的结果列也可以出现多个，例如：(SNO, SNAME) = (SELECT SNO, SNAME FROM SUPPLY)。Kim 划分嵌套查询种类是从子查询有没有连接条件以及聚集函数这两个角度考虑的。

最后，定义子查询的相关性。SQL 语句的书写是自顶向下（或者说从外到内）的，外层查询块可以引用内层查询块的结果列，内层查询块也可以应用外层查询块中表的列。这种相互的引用就形成了所谓的相关性。外层查询引用内层查询的结果列就像程序设计语言中外层函数引用内层函数的返回值一样自然。而内层查询块引用外层查询的表的列类似程序设计语言中内层函数引用全局变量（或某些语言中外层函数的局部变量）。只要内层查询引用了外层查询的列，就称为该内层查询与对应的外层查询相关（Correlated），该内层查询是一个相关子查询。此时，整个查询就被称为相关查询。如果整个查询中都找不到相关子查询，则整个查询就被称为非相关查询。

针对嵌套查询，最简单直接的执行方法是从外到内，对外查询的每一条记录，执行子查询。这种方法也被称为 Nested Iteration，它也是 SQL 定义语句语义所采用的方法。容易发现，非相关子查询还有别的执行方法，例如可以将子查询先执行好并将结果保存下来称为临时表；甚至还可以给保存的临时表增加索引以加速后续操作。显然，相关子查询的执行和改写都是最复杂的。

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 嵌套查询的优化

如果采用最简单直接的执行算法，对外查询块的每条记录，需要执行内查询块一次（Nested Iteration）。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

这是 Berkeley 的技术报告，主要是发现了 Kim 算法中对 JA 类查询优化的 Bug。也说明了 QUEL 中不存在类似的问题，只是在 SQL 中有问题。其根本原因是 SQL 中聚集函数的语义带来的。COUNT 在遇到不满足条件的记录时，会返回 0 而不是 NULL；这与其他的聚集函数 MAX 等不一样。感兴趣的读者请直接阅读论文，或者想一想下面的例子。

CREATE TABLE DEPT(DNO INT, BUDGET INT, PRIMARY KEY(DNO));

CREATE TABLE EMP(ENO INT, DNO INT, PRIMARY KEY(ENO), FOREIGN KEY(DNO) REFERENCES DEPT.DNO);

SELECT D.* 
FROM DEPT D 
WHERE D.BUDGET <= (SELECT COUNT(E.ENO) * 100 
                   FROM EMP E 
                   WHERE E.DNO = D.DNO);

SELECT * 
FROM (SELECT D.*, COUNT(E.ENO) AS CNT 
      FROM DEPT D, EMP E 
      WHERE D.DNO = E.DNO
      GROUP BY D.DNO) AS T 
WHERE T.BUDGET <= CNT * 100;

这类例子非常经典，也被称为The COUNT Bug，每个号称搞查询优化的人都应该深入了解。

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 等的论文中都有代价分析。逐步改进（打补丁）的做法也逐步增加了转换后查询的处理代价，更需要代价优化器来判断转换是否有必要。虽然上面提到的各种算法并没有彻底解决全部的嵌套查询优化，但是它们是更通用的算法的基础。在后续的研究和开发中，SQL Server 6、HyPer 7 等做出了更加完善和通用的解决方案。

参考文献

Kim, On Optimizing an SQL-like Nested Query.
R.A. Ganski etc., Optimization of nested SQL queries revisited.
Kiessling, SQL-like and Quel-like Correlation Queries with Aggregates Revisited
https://blogs.oracle.com/optimizer/entry/optimizer_transformations_subquery_unesting_part_1
https://blogs.oracle.com/optimizer/entry/optimizer_transformations_subquery_unesting_part_2
Galindo Legaria, Parameterized Queries and Nesting Equivalencies
T Neumann, A Kemper, Unnesting Arbitrary Queries

Written on March 31, 2016