这篇精干的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
前提条件
- 子查询中有aggregation，这样window function才有意义。
- 由于改变了整个查询的执行流程，不能存在有side effect的函数，也就是在不同执行流程下结果会不同的函数，例如RAND()这样的function。
- subquery中不能有Top-N这种截断性的操作，会破坏内外层数据的一致性。
- 内层aggregation具有等价的window function，例如min/max/sum/count，而没有aggr(distinct ...)的聚集计算(window function不支持distinct）。
- 外层和内层之间，存在subsume关系！！（外层在join table/condition上，包含内层），这个条件可以放宽：
内层如果有其他非相关表，必须是lossless join，保证内层相关表的数据不会由于join丢失/增加
内层相关表可以有更多的单表限定条件，在转换时，需要通过在window aggregation时，利用CASE …. WHEN这样的条件判断，来保证数据能够按照原语义被过滤。
关于这种特殊情况，我们一会可以通过示例看下。
转换过程
- 内层aggregation -> window aggregation，并以内层相关列作为partition by列。
- 把外层相关表压入到内层中，与内层表做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的通用形式如下：
- T1, T2, T3, T4是一组表(table/view)。
- 在内层，T1是内层非subsume的无关表，与T3(相关表)必须是lossless join。
- 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的等价变换，基于完全相同的思路。
