这篇精干的paper介绍了IBM DB2基于window function对相关子查询进行解相关的等价变换。

基本概念

例如SQL:

SELECT emp_id, emp_name, dept_name
FROM employee E, department D
WHERE E.dept_num = D.dept_num AND
E.state = ‘CALIFORNIA’ AND
E.salary > (SELECT AVG(salary)
FROM employee E1
WHERE E1.dept_num = D.dept_num);

其原始的语义就是对外层查询的每一行结果(E join D)，获取其相关列D.dept_num的值(d)，代入到相关子查询中，内层所有在E1.dept_num上具有相同对应值(d)的行，作为满足相关条件的过滤结果，计算一次聚集。然后基于聚集的结果对外层的该行进行过滤判断(E.salary > AVG(sal))。

DB2在之前的paper中提到了一种magic de-correlation的变换，利用了所谓的magic set。根据相关子查询的语义，将外表相关列的每一个唯一值组成一个magic set，拉入到内层来与内表join，join的结果其实就等同于外表每个相关值所对应的内表行，组合在了一起。这样在对各个组各自聚集，聚集的结果是以外表的相关列为分组的，因此就完成了去相关，计算结果再与外表join就可以了。

从上图可以看到，提取出magic set与内表做join的过程，就等价于用外表每一个相关值在内表依次进行过滤的过程，这样计算出的每个分组聚集结果就是每次带入相关value计算的聚集结果。将结果与外层再基于相关列做join，等于还原了针对外表每一行都要计算的语义，恢复原始结果。

WinMagic也是这个思路，只是在满足某些特定条件下，可以更进一步，去掉内/外层中的common table，使其只需要计算一次就可以了。

关于window function的介绍这里就不赘述了，可以参考MySQL reference的介绍 。这里就先假设大家都了解window function了。

WinMagic Transformation

前提条件

1. 子查询中有aggregation，这样window function才有意义。
   
2. 由于改变了整个查询的执行流程，不能存在有side effect的函数，也就是在不同执行流程下结果会不同的函数，例如RAND()这样的function。
   
3. subquery中不能有Top-N这种截断性的操作，会破坏内外层数据的一致性。
   
4. 内层aggregation具有等价的window function，例如min/max/sum/count，而没有aggr(distinct ...)的聚集计算(window function不支持distinct）。
   
5. 外层和内层之间，存在subsume关系！！（外层在join table/condition上，包含内层），这个条件可以放宽：
   

内层如果有其他非相关表，必须是lossless join，保证内层相关表的数据不会由于join丢失/增加

内层相关表可以有更多的单表限定条件，在转换时，需要通过在window aggregation时，利用CASE …. WHEN这样的条件判断，来保证数据能够按照原语义被过滤。

关于这种特殊情况，我们一会可以通过示例看下。

转换过程

1. 内层aggregation -> window aggregation，并以内层相关列作为partition by列。
   
2. 把外层相关表压入到内层中，与内层表做join，这是在解相关，但这里要区分对待：
   

2.1 如果外层相关列是个主键/唯一键列，则拉入内层，也不会导致内表数据量增加（内层每一行，最多join上外层一行），由于外层中也有这个内层表以及表上的过滤条件（subsume关系）。内层过滤掉的数据外层也一样过滤掉了，数据内外是一致的，这时window partition列是[内层相关列]。

2.2 外层相关列不是主键/唯一列，拉入内层后，内层表数据量会由于join而变多（重复的外层相关列），此时仍需要保证”对外表每一行，内表做一次聚集“的语义，因此window partition列是 [外表主键，内层相关列]。

3. 由于外层subsume内层，而且内层包含了所有common table，这时外层的common table就可以去掉了，只剩下非相关table，再与子查询去相关后的derived table做join。这样就去掉了对common table的重复执行。

用一个具体的示例来说明这个过程：

SELECT SUM(l_extendedprice) / 7.0 AS avg_yearly
FROM tpcd.lineitem, tpcd.part
WHERE p_partkey = l_partkey AND
p_brand = 'Brand#23' AND
p_container = 'MED BOX' AND
l_quantity <
(SELECT 0.2*avg(l_quantity)
 FROM tpcd.lineitem
 WHERE l_partkey = p_partkey);

观察以上query，内外层都包含tpcd.lineitem这个表，相关条件在l_partkey = p_partkey。

如上示例符合2.1中的情况，即相关列是外层表part的主键列，因此window function只需要partition by p_partkey。

1将外层的part推入内层，2与lineitem做join，等于在外层/内层，都有lineitem join part这个操作，产生了相同的结果集（外层由于可能有更多条件，可能数据会更少，但没有关系，可以把这些额外条件认为在join之后再计算）。3在join结果上基于相关列做partitioned window function的计算，实际上就是基于每个相关值，计算一个局部聚集结果。4将聚集结果作为附加列添加在join结果的最后。5由于内外层subsume的关系，内层join的结果也是外层join的结果，并附加了基于相关性计算的内层聚集结果作为额外一列。这时再应用外层其他条件，对结果继续过滤就可以了。

这里把外层推入后，最主要的一个优化就是内层part join lineitem的结果就是外层common tables join的结果。因此只需要在内层计算一次，结果以derived table的形式复用到外层就可以了，避免了内外层的重复计算。

转换后的query变为

WITH WinMagic AS
(SELECT l_extendedprice, l_quantity,
avg(l_quantity)over(partition by p_partkey)
AS avg_l_quantity
FROM tpcd.lineitem, tpcd.part
WHERE p_partkey = l_partkey and
p_brand = 'Brand#23' and
p_container = 'MED BOX' )
SELECT SUM(l_extendedprice) / 7.0 as avg_yearly
FROM WinMagic
WHERE l_quantity < 0.2 * avg_l_quantity;

对于2.2的情况，思路是完全一样的，只是原始语义中，是外层的一行带入到内层做一次聚集，因此应该仍保证这一点，在内层算window aggregation时考虑外层主键 + 内层相关列。

前面提到了如果内层有比外层更多的过滤条件怎么办？仍然从语义的角度出发，也就是在内层做join时，有些行会被内层的额外条件过滤掉，但是为了满足内外层数据一致的特性，仍然是需要原样做join的，只是那些过滤掉的行不参与window aggregation的计算就可以了。

可以通过类似sum(case when pred is true then value else NULL) 这样的方式，来保证不满足predicate的行不计入聚集结果中。

通用形态

将上面描述的内容泛化，WinMagic的通用形式如下：

1. T1, T2, T3, T4是一组表(table/view)。
   
2. 在内层，T1是内层非subsume的无关表，与T3(相关表)必须是lossless join。
   
3. T2是外层无关表，不能与T4(相关表)直接join。这里应该是为了保证T3 Join T4这个内外层操作在数据上的一致性。
   

那么转换时，T4 pushdown 到子查询中计算window function，完成解相关+转为derived table，外层的T3 join T4就不需要了，这个derived table(WinMagic)与T2 join即可。

总结

WinMagic的本质是，外层已经包含了内层的相关表，所以可以直接复用下推后内层T3 join T4的结果来计算聚集，以window function的形式将聚集结果作为附加列加在结果上，然后外层基于这个结果再进行后续计算。

可以看到，这个变换还是非常简单的。目前PolarDB也实现了这个win magic的等价变换，基于完全相同的思路。