嵌套子查询的背景

实践中，经常会遇到多层嵌套的SQL，并且多层嵌套之间包含有聚集函数，执行这类SQL的最简单的方法就是一层一层嵌套执行，类似于Nested Loop Join，对于外查询的每一行数据，就要将子查询执行一遍，如果子查询还有孙查询，子查询中的每一行，还要将孙查询执行一遍，……，显尔易见，这种执行方式的效率通常都比较低，尤其是当表的数据量很大时，对性能的影响非常明显。

 下面是一个嵌套查询的简单例子:

Select R.a
 from R
 where R.b >= (select sum(S.d)
      from S
      where R.c = S.c);

对于这个非常简单的例子，我们以嵌套执行的方式来模拟一下执行的过程。

1. 从表R中读取一行数据(a,b,c)，然后执行子查询；
2. 子查询的执行过程如下：
   1. 子查询从表S中读取一行数据(c,d,e)；
   2.  然后判断R.c 是否与S.c相等，若相等，则计算sum；否则跳过此行数据；
   3.  读取表S中的下一行数据，然后跳转2.2）处理数据，直到S中的所有数据处理完毕。
3. 子查询执行完毕后得到最终的sum值，此时就可以比较R.b与sum值的大小，若R.b大于sum值，输出R.a，否则不输出。
4. 然后跳转到步骤一，继续读取R表中的下一行数据，跳转2）继续执行，直到R表中的所有数据完成。

嵌套子查询的代价分析

若不考虑读取数据的代价，我们来简单计算一下：

假设R表中有1000行数据，在S表中有10000行数据，S表的c列的NDV(Number of Distinct Value)值为100，也就是说，S表中的c列中的每一个值大约重复100次。

那么子查询就要被执行1000次，即使前一次和当前这次R.c是相同的值，也就是说要做1000次的sum求值，则这1000次sum求值之中，有很多次其实是相同的，完全可以避免。

简单的Unnesting算法

一种很容易想到的方法就是：能不能把每次计算的sum值cache起来，当后而再遇到相同的S.c值时，直接取就可以了。没错，这种方法可以大大减少子查询的执行次数，但依然要将子查询执行很多次，也就意味着，需要将S表读取很多次，可不可以只读取一次S表呢？方法当然是有的，比如下面的做法:

1. 首先我们将子查询按S.c分组，每组S.c对应外查询中R.c，然后对每个S.c分组进行sum计算，将结果保存到一个临时表中，比如tmp1中，为便于改写，我们以view来代替临时表：

对应的SQL为：

Create view v1 as 
 Select S.c, sum(S.d) as total
  from S
  group by S.c;

那么v1表中的数据如下表所示：

1. 然后将R表与步骤一中产生的view v1进行连接，连接条件为R.c = v1.c and R.b >= v1.total，对应的SQL为：

Select R.a
 from R, v1
 where R.c = v1.c and R.b >= v1.total;

通过这种方法，子查询中的表S只需要做一次，Sum值也不需要重复计算，从而避免了子查询的嵌套执行问题。而且这种方法还可以扩展到更多层的嵌套子查询中。

比如：

Select R.a
 from R
 where R.b >= (select sum(S.d)
      from S
      where R.c = S.c
       and S.e > (select avg(T.g)
           from T
           where S.f = T.f));

解嵌套的过程如下所示：

1. 生成最里层子查询的view v2;

 create view v2 as 
  select T.f as f, avg(T.g) as v
   from T
   group by T.f;

1. 生成中间层的子查询的view v1;

 create view v1 as 
  select S.c as c, sum(S.d) as total
   from S, V2
   where S.f = V2.f and S.e > V2.v;

1. 生成最终结果的查询如下：

select R.a
 from R, v2
 where R.c = V2.c and R.b >= v1.total;

规则非常简单，也易于理解和实现，但是愿望是好的，但现实却不是那么完美，这种方法并不能简单的就被应用到所有嵌套子查询上，下面我们就来分析一下哪些情况是不是被直接应用的。其中最著名最引人注目的就是传说中著名的count陷井。

传说中的count陷井

再来看最初的那个简单例子，只是把其中的sum换成count，如下所示：

Select R.a
 from R
 where R.b >= (select count(*)
      from S
      where R.c = S.c);

那么利用上述的解嵌套算法，将此SQL分成以下2部分：

1）创建一个view v1;

Create view v1 as 
 select S.c as c, count(*) as cnt
  from S
  group by S.c;

2) 产生最终结果的语句

Select R.a 
 from R
 where R.c = v1.c and R.b >= v1.cnt;

貌似没有什么不同，但如果考虑一下这个场景，情况就大不一样了。

如果对于R中有一行数据中的R.c，却在S表中的S.c中没有，也就是说对于R.c的值，通过v1并不能产生对应的分组，如下图所示：

表R

表S

那么v1的结果：

解嵌套的查询结果：

但实际上原始SQL的正确查询结果应该是：

对比发现，解嵌套后产生的结果丢失了一条数据，为什么呢？原因在于对表R中的行(2,3,8)来说，在S表中并没有对应的S.c=8，也就不会在视图v1中产生这样一行，而对于原查询来说，当子查询执行时，发现S表中没有S.c=8，就会将count(*)计算为0，此时R.b=3显然是大于0的，所以对应的R.a=2就会作为结果输出。

进一步分析发现数据丢失主要是因为外表中的数据行在内表中没有匹配的行，而且count比较特殊，因为如果没有任何匹配行，count()的计算结果为0，而其它任何AGG聚集函数的计算结果为NULL。因此只要子查询中不包含count，其它的仍可以采用这个算法来进行解嵌套执行。

Count陷井的由来

首先再来分析一下采用之前解嵌套算法Join-view导致结果不正确的原因，原因主要有2个：

1. 当出现外表中的数据在内表中没有匹配行时，按原SQL的执行，子查询中会产生count()结果为0的行，而之前的解嵌套算法，只将内表进行group by，做count操作，显然就会丢失这些count()为0的行。
2. 外表与内表之间的连接条件对结果也有影响，比如示例中的R.b >= count()，若count为0，当R.b >= 0为true时，就会丢失这一行数据，但若R.b < 0时，并没有什么影响。

再看一组数据：

表R

注意：第2行数据，R.b的值由原来的3变成了-3。

表S

那么v1的结果：

解嵌套的查询结果：

而原始SQL的查询结果也是：

我们发现，这次由于数据的原因，导致过滤条件在遇到外表中的数据在内表中没有匹配行时为false，从而结果没有出现丢失数据的情况。但这种情况只是一个极端的情况，在实践中我们不能期望总是遇到这种情况，因此还是要有一种通用的解法才能真正解决包含count的解嵌套的问题。

LEFT OUTER JOIN解嵌套算法

因为数据丢失主要是因为外表中的数据行在内表中没有匹配的行，而具有相同特征的算子还有一个就是Left Outer Join，后面我们简称为Left Join，对于Left Join来说，当左表也称外表中的一行在右表也称内表中没有匹配行时，左表行输出，并将右表对应的列置NULL。如：

表R

表S

那么

Select R.a, R.b, R.c
 from R Left Join S 
 on R.c = S.c;

我们发现通过Left Join之后，左表也就是外表中的数据就不会丢失，因此我们就可以利用Left Join的这个特点，对原SQL进行如下改写，从而达到解嵌套的目的：

Select R.a
 from R Left Join S
 on R.c = S.c
 group by R.#, R.a
 having R.b >= count(*);

看到这个SQL，可能有人比较奇怪，group by中的这个R.#是哪来的，#是个什么东东？其实这个#代表R中的唯一一行，如果R表有主键，就可以用主键来代替它，如果没有，可以使用Row ID，总之，就是按R表中的每一行进行分组，然后计算count，判断having条件后，确定是否输出这一行。

另外在group by中还出现了R.a，如果主键中已经包含了R.a，后面的R.a就不需要了，但如果主键中不包含R.a，group by就需要包含R.a，这是为了服从严格sql_mode的标准，不然语法检查会失败。

我们以上面的R Left Join S的结果数据来解释这个group by R.#的作用。

对于R表中的第一行(1,2,5)和第二行(2,3,8)，不管在S表中有没有匹配行，都只输出了一行结果，但对于R表中的第三行(3,2,6)，在S表中却有2行数据相匹配，因此对于R表中的一行，输出了2行结果(3,2,6,6,80)和(3,2,6,6,49)。按原SQL的定义，对于同样的R.c，要计算S表中与R.c相匹配的行的count()值，对于已经Left Join的结果来说，只要简单按R的主键或Row ID分组即可进行count的计算，最终判断having条件是否满足即可确定是否输出此行。

因此结果如下所示：

也许有人会问，直接使用R.c来做分组不可以吗？答案是不行，我们改下数据，重新看一下：

表R

注意：第二行的数据Ra由2改为了1，R.c由8改为了5

表S

那么R Left JOIN S的结果为：

如果将group by按R.c分组，我们发现对于R表中的2行(1,2,5)和(2,3,5)结果被group到了同一个分组，结果就可能出现错误。

Select R.a
 from R Left Join S
 on R.c = S.c
 group by R.c, R.a
 having R.b >= count(*);

结果为：

而正确的结果应该为：

因此，选择正确的分组，即能唯一确定R表中的一行数据的主键或Row ID是最理想的选择。最后我们得到这样的结论：

1. 如果嵌套子查询不包含count，并且子查询中的关联列最多只与其父查询关联，不能跨父查询直接关联到祖父查询中的列(这种情况后面会专题讨论)，那么就可以自里及外一层层将嵌套子查询改写到view或临时表，从而达成解嵌套子查询的目标。
2. 如果嵌套子查询中包含count，那么可以先将外表和内表做Left JOIN，然后再对结果按外表的唯一键进行分组，将原有的内表与外表的关联关系做为having条件添加到查询中，从而达成解嵌套子查询的目标，这种方法可以简称为groupby-having方法。

LEFT OUTER JOIN方法的代价分析

 同样假设R表中有1000行数据，在S表中有10000行数据，S表的c列的NDV(Number of Distinct Value)值为100，也就是说，S表中的c列中的每一个值大约重复100次。

1. 原始SQL的子查询要被执行1000次，即使前一次和当前这次R.c是相同的值，也就是说要做1000次的sum求值，则这1000次sum求值之中，有很多次其实是相同的，完全可以避免。
2. 采用Left outer join转换后的SQL，首先对R表和S表做Left JOIN，且S表的c列的NDV是100，因此Left Join后的结果大约是1000 * 100 = 100000行，然后做group by求count后，进行having条件的过滤。
3. 显然如果数据量比较大时，这种方法放大了中间结果，也增大了聚集的cost，因此实际上要不要转换需要对转换前和转换后的代价进行比较后再来确定更好一些。

那么还有没有其它能解包含count的子查询嵌套并且代价更优的算法呢？下回我们就来介绍一种更好的解包含count的子查询嵌套的算法。

JOIN-VIEW + ANTI-JOIN算法

再来回顾一下之前利用视图或临时表的方法来解嵌套子查询的方法。

Select R.a
 from R
 where R.b >= (select sum(S.d)
      from S
      where R.c = S.c);

可以利用视图将其改写为：

1）创建视图

Create view v1 as 
 Select S.c, sum(S.d) as total
  from S
  group by S.c;

2）原SQL改写为与视图的Join

Select R.a
 from R, v1
 where R.c = v1.c and R.b >= v1.total;

前面我们已经分析过，如果将sum改为count后，这种算法就可能会导致数据丢失。数据可能丢失的原因是因为对于外表R中的数据行，若在S表中没有匹配行，那么其count为0，但并不会出现在view的结果中，当条件R.b > 0为true时，就会导致数据丢失。那么有没有一种方法，可以将这些数据找回来呢？

下面提供了一种方法，避免数据丢失，而且还不需要采用Left Join，避免中间结果集超大，聚集代价高的缺点。

对于以下包含count的SQL：

Select R.a
 from R
 where R.b >= (select count(S.*)
      from S
      where R.c = S.c);

第一步，仍采用创建视图的方法改写：

Create view v1 as 
 Select S.c, count(S.*) as cnt
  from S
  group by S.c;

关键是第二步，正常情况下R表与S表的Join，就会导致数据丢失，原因是R表的数据行可能在S表中没有匹配行，也就是说，对于S表中有匹配行的可以正常Join的数据是没有问题的。那么再来看这些匹配不上的R表的数据行，这些数据行集中到一起其实就是R表anti-join S表的结果集。因为这些在S表中匹配不到的数据行，在Join过程中都已经逐行被确定了，而且对于这些行来说，count值就是0，因此我们只要遇到了这些anti-join的数据行，直接判断条件R.b >= 0就可以了，如果满足，则输出为最终的结果集；如果不满足则忽略这一行，继续读取R表的下一行，直到R表的所有数据都处理完毕即可。

因为这种算法无法用标准的SQL语法表示出来，所以只能以一种类SQL的方式来形式化的表示，但在实践中它是很容易实现的。

第二步，采用Join-view + anti-join的方法表示：

Select R.a
 from R, v1
 where R.c = v1.c 
 and { 
        R.b >= v1.cnt   [ for JOIN ]
      OR 
        R.b >= 0        [ for Anti-Join] 
     };

JOIN-VIEW + ANTI-JOIN算法的代价分析

显然，这种实现方法，继承了Join-view方法的特点，如果内表NDV值比较小，重复值比较多的情况，可以大大减小Join的数据量，同时通过anti-join的补充，将可能丢失的数据补回来，而无需对庞大的Left Join结果集做AGG聚集操作。当然在实际应用中，还是要根据cost来决定选择哪种算法来做嵌套子查询的unnesting。

结论

这里主要是针对2层嵌套子查询的讨论，对于简单的多层嵌套子查询可以采用上述的几种算法来逐层解嵌套，但是有一些复杂的嵌套子查询，就不能简单的应用这些算法了，下章我们会继续讨论一个之前提到过的子查询隔层引用祖父查询中的关联列的示例，以及如何进行正确的unnesting它们。

参考文献

[1] Improved Unnesting Algorithms for Join Aggregate SQL Queries

[2] A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregate, and Quantifiers