三国赵云传数据+Postgres解析一篇SIGMOD2019论文的agg递归CTE

Contents hide

标题党实锤了。这也是我博客中第一篇用中文写的技术文章。坚持用英文写博客，并不是崇洋媚外，只是为了跟各国同事之间交流技术方便一些。那么这次为啥选择母语，因为原始论文里的例子一点也不好玩，我选择三国赵云传的一个数据来作例子，那不妨就写得幽默一代呢，放飞自我放飞的根本一些。

论文是这篇: RaSQL: Greater Power and Performance for Big Data Analytics with Recursive-aggregate-SQL on Spark, SIGMOD 19.

递归CTE查询

递归CTE查询是现代SQL的一个重要语句，它借鉴了Datalog|Prolog等逻辑式编程语言的表达能力，使得SQL处理递归、迭代的能力得到很大提升。之前我在修复Greenplum Database的subqueryscan的locus问题中，意外的接触到了这块逻辑（回归测试fail），花了一点时间研究，并修复在MPP数据库里递归CTE的一些小问题。之前的探索，整理成了博文： Dijkstra via SQL: a glance at Recursive CTE. 以及给Greenplum提交的相关PR是: Set Recursive CTE plan’s flow correctly. #8859 有兴趣的可以参考。

下面的例子是基于Postgres展示最简单的递归CTE:

explain with recursive t(n) as (
  select 
    1 
  union all 
  select 
    n + 1 
  from 
    t 
  where 
    n < 10
) 
select 
  * 
from 
  t;

              QUERY PLAN
-----------------------------------------
 CTE Scan on tt
   CTE tt
     ->  Recursive Union
           ->  Result
           ->  WorkTable Scan on tt tt_1
                 Filter: (n < 10)

Postgres用worktable scan实现递归CTE表的扫描，用Recursive Union这个plannode去实现fixpoint语义。Recursive Union这个plannode很可能是唯二的同时有两个子树的plannode。大致了流程如下:

用非递归部分语句初始化worktable，记为wk = w0
基于wk的数据执行worktablescan，产生的结果记为w1, 替换wk = w1
如果wk是空集，则go to 4, 否则go to 2
把所有w0, w1, w2, … wn用union拼接起来

SQL的标准似乎(这里用似乎是因为我没有去搜索标准)不支持在递归部分写Agg，关于这一点原因，我也没有去调研，但我和同事们有一些不成熟的推测，这里就不表了。比如下面的语句就会变报错:

gpadmin=# explain (costs off) with recursive tt(n) as (
  select
    1
  union all
  select
    max(n + 1)
  from
    tt
  where
    n < 10
)
select
  *
from
  tt;
ERROR:  aggregate functions are not allowed in a recursive query's recursive term
LINE 6:     max(n + 1)
            ^

那句报错发生在Postgres的语义分析阶段的一个检查，如果当前的select statement有agg，那么它的rangetable里的不允许出现递归CTE的RTE。这块代码在函数parseCheckAggregates里。

SIGMOD论文的导读

我们大概知道了一个事实，SQL里的递归CTE不支持递归部分有agg，这篇论文的创新点就是开发这样一个功能。它基于Spark SQL，扩展了SQL语法并赋予新的语义，使得可以在递归CTE里使用agg。这样的好处是，原本得扫描完整个worktable，然后再做agg，如果在扫描worktable的过程中就可以做agg，数据量会减少很多，从而提升速度。

论文指出新语法避免了代码冗余，且提升可读性。我本人保留意见，请参考后面实例分析。同时，我并不觉得扩展语法是很好的开发方式，既然语义相同，这类工作可以交给查询优化器去完成。

论文后面围绕着spark的执行器模型，讨论了实现。那部分我并没有仔细阅读。因此，接下来的实例分析，紧扣着论文的Section2的Q1和Q2两个语句。

三国赵云传的数据例子

论文基于递归CTE的经典例子BOM来讨论新语法和语义。我觉得BOM的例子不够欢乐，我一下子就想到了三国赵云传的武器炼化攻略了。这个例子很明显欢乐很多。下面的分析，我会完全几乎这个例子。

赵云传里的终极武器都是炼化所得，比如龙胆枪，你就得用化影戟+紫水晶+白虎之魂+龙卷风笺去铁匠那里炼化得到。而化影戟可以通过方天画戟+浑元画戟炼化得到。这些需要炼化得到的装备，称之为compound装备。有一些装备是在某些关卡获得的，它们不能（不需要）经过炼化，应该称它们为atom装备，比如紫水晶。

上面的这种依赖关系，我们把它存在一个数据库的表(peifang)里，这个表有两列peifang(part text, subpart text). compound装备就是出现在第一列的装备。atom装备就是没有出现在第一列的。为了简化，我做了一个强制要求，每个compound装备，只有一种炼化配方。

我们打游戏的时候，老算着，我啥时候能得到龙胆枪啊，我啥时候能用上七星剑？七星剑需要用倚天剑炼化（所以七星剑是compound装备），倚天剑是救了华佗后，在客栈跟一个书生用两万两银子买到（所以倚天剑是atom装备）。。。OK，模型就是，每个atom装备又一个关卡号，表明第几关，你可以获取。这个表叫做base表，也有两列base(part text, round int).

这两个表就存够了信息，作为云迷，实在想知道最快啥时候可以用上龙胆枪？我们需要写一个SQL来完成这个任务。这里的数学逻辑是，符合装备最快得到的关卡号是它虽有子部件里最晚得到的关卡号。

这部分数据，我用python预处理后倒入到了Postgres，一瞥如下（关卡号是我随机生成的。。。）:

gpadmin=# select * from peifang where part = '龙胆枪';
  part  | subpart
--------+----------
 龙胆枪 | 化影戟
 龙胆枪 | 紫水晶
 龙胆枪 | 白虎之魂
 龙胆枪 | 龙卷风笺
(4 rows)

gpadmin=# select * from peifang where part = '化影戟';
  part  | subpart
--------+----------
 化影戟 | 方天画戟
 化影戟 | 浑元画戟
(2 rows)

gpadmin=# select * from base limit 1;
  part  | round
--------+-------
 金锁甲 |     9
(1 row)

传统的SQL如何处理

传统的SQL需要通过递归CTE搜索出每个部件的所有子部件，然后在外层使用agg操作，得到每个装备的最长时间。

代码如下:

with recursive tt(part, round) as (
  select part, round from base
  union
  select peifang.part, tt.round
  from tt, peifang
  where tt.part = peifang.subpart
)
select part, max(round) from tt group by part;

递归CTE的编程技术需要训练和学习，本质上是要有迭代的思想。

论文的贡献

全部扫描得到了结构后再做agg，效率不太好。能不能把agg推到递归CTE里头去呢？

这篇论文发明了一个语法糖衣，如下：

with recursive tt(part, max() round) as (
  select part, round from base
  union
  select peifang.part, tt.round
  from tt, peifang
  where tt.part = peifang.subpart
)
select part, round from tt;

论文在递归cte的地方加了一个max()语法，然后基于implicit group rules，上面的语句，在任何select的地方:

对投影处理：如果投影列被声明了agg，如上文的max() round, 则但凡出现了round位置的地方自动使用max
对groupby的处理：只要没有被声明agg的列，一律必须出现在group by里

如此这般，上面的语句实际上是：

with recursive tt(part, round) as (
  select part, max(round) from base group by part 
  union
  select peifang.part, max(tt.round)
  from tt, peifang
  where tt.part = peifang.subpart
  group by peifang.part
)
select part, max(round) from tt group by part;

新语法糖这么多地方需要脑补，我本人对增加可读性的优点，实在是保留意见。

直接把上面展开后的语句丢进Postgres，会报错，如下：

gpadmin=# with recursive tt(part, round) as (
  select part, max(round) from base group by part
  union
  select peifang.part, max(tt.round)
  from tt, peifang
  where tt.part = peifang.subpart
  group by peifang.part
)
select part, max(round) from tt group by part;
ERROR:  aggregate functions are not allowed in a recursive query's recursive term
LINE 4:   select peifang.part, max(tt.round)
                               ^

论文对这一例子的语义描述如下算法：

我们要仔细看清楚了，上面的算法，跳出循环后，最后一件事一定是max操作，而不是union，这也是为啥上面的展开，在最下头也需要做agg。

瞒天过海：Postgres真的做不到么？

论文看到这里，我有两个困惑:

Postgres的处理递归CTE查询计划框架，完全没有限制agg，明明是可以支持的
我在用Postgres编程Dijkstra算法的时候，不是也用agg，我还用了窗口函数呢

那么Postgres一定很早就能做这个论文里说的事儿了。问题在哪儿呢？为啥会报错？

我的探索办法是简化我的dijkstra算法的SQL脚本，简化到不能再简化为止，看SQL代码有啥规律。简化到不能简化为止的代码（不考虑算法正确了，只考虑语义分析）：

explain
with recursive sp(a, d) as
(
  select a, d from known
  union all
  select a, d
  from
  (
    select
    a, min(d) as d
    from
    (
      select
        sp.a as a,
        sp.d as d
      from
        sp, roadmap_sym as rm
    ) x
    group by a
  )y
)
select * from sp limit 1;

这我就基本已经看出问题在哪儿了：只需要把worktable scan的部分包装在一个子查询里，就可以瞒天过海，骗过Postgres了。然后我用gdb去debug Postgres，发现了在函数parseCheckAggregates的坚持逻辑是，当前如果有agg，则在range里不允许有递归CTE的RTE。然而，上面的例子，agg发生的那层select，rangetable里只有一个range_select,然后Postgres并没有递归去检查range_select（是否是这么设计的？目前未知），从而瞒天过海了。但是这个子查询没有任何语义上的区别。

利用上面的兵法，我们改写SQL如下：

explain
with recursive tt(part, round) as (
  select part, max(round) as round from base group by part
  union
  select part, round
  from
  (
    select part, max(round) as round
    from
    (
      select peifang.part as part, tt.round as round
      from tt, peifang
      where tt.part = peifang.subpart
    )x
    group by part
  )y
)
select part, max(round) from tt group by part;

                           QUERY PLAN
----------------------------------------------------------------
 GroupAggregate
   Group Key: tt.part
   CTE tt
     ->  Recursive Union
           ->  HashAggregate
                 Group Key: base.part
                 ->  Seq Scan on base
           ->  HashAggregate
                 Group Key: peifang.part
                 ->  Hash Join
                       Hash Cond: (tt_1.part = peifang.subpart)
                       ->  WorkTable Scan on tt tt_1
                       ->  Hash
                             ->  Seq Scan on peifang
   ->  CTE Scan on tt

完美的查询计划。

我们执行一下，看看心仪的龙胆枪在啥时候可以获取？

  part  | max
--------+-----
 龙胆枪 |  16

哈哈，在第16关就可以获取了呢。

这里的结论就是，Postgres可以完成这篇论文里的功能：把agg下推到递归CTE里。如果这对Postgres是合理的，那么我们有理由任何，这类优化，应该交给planner去做，要么是CBO要么是RBO，显然，扩展语法，不是上策。

论文其他部分的思考

论文后面介绍了一些可以下推的agg需要满足的性质，这部分数学原理是其他论文的贡献。后面的实现是基于spark的，暂时我也没有仔细阅读。论文配套了其他很多例子，我也没有一一去过。有时间会去参考下spark执行器的实现。因此这部分并没有评测。

Greenplum对递归CTE的支持还有限，在语义分析阶段会禁止掉非常多的功能。如果在MPP数据库里完美的支持递归CTE，有时间的话，还需要系统的思考研究。目前我的经验是，Greenplum可能需要修改Postgres为此设计的执行器，因为Postgres是单机数据库，Recursive Union这个执行器节点和下面的worktable scan的执行器部分在一个进程里，Postgres的执行器代码依赖了这一点。Greenplum的motion会切片查询计划，有可能违背这一点。

Thoughts on Computing

英雄无岁，江湖无辈