包含Count陷井的嵌套子查询的unnesting算法

话接上回，包含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方法。

Groupby-having方法的代价分析

同样假设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）采用Groupby-having转换后的SQL，首先对R表和S表做Left JOIN，且S表的c列的NDV是100，因此Left Join后的结果大约是1000 * 100 = 100000行，然后做group by求count后，进行having条件的过滤。

显然如果数据量比较大时，这种方法放大了中间结果，也增大了聚集的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