从优化器的角度CTE的复杂度来自：

1. 对query树中引用到CTE的地方都进行inline展开的好处是：可以结合CTE在计划树中上下文进一步的优化（下推，join顺序等），坏处是：CTE被重复执行了；
2. 对引用到CTE的地方不进行inline展开的好处是：CTE只执行了一次，但是引用CTE上下文中的predicate无法下推了，比如有索引的情况下，无法使用索引；
3. 在MPP中，引用CTE不同上下文中，对CTE的prop物理属性要求不同，有些属性可以合并。比如：有的地方要求升序，有的地方要求hash分布等；

ORCA优化器对CTE的优化方法：

1. 在ORCA的框架中实现CTE的优化，而不像其他优化器在插件或者外围逻辑中进行多个阶段的优化；
2. 引入CTEAnchor，Sequence，CTEProducer和CTEConsumer来描述CTE；
3. 使用MEMO对inline和非inline进行枚举；
4. 对CTEProducer和CTEConsumer上下文中的prop进行枚举；
5. 上述优化后，可能使得部分CETConsumer得到inline展开，部分CTEConsumer不展开；公共prop属性下推到CTEProducer中；
6. CTE技术还用于优化其他SQL场景，如：对多个列distinct；消除公共表达式；
7. CTE执行器：
   CTEProducer对应Material算子或sort算子；CTEConsumer对应SharedScan算子；
   CTEConsumer只会从本进程或者本host的CTEProducer上消费，不会跨host；
   CTEProducer生产完数据后通知所有CTEConsumer（文件名和消息）；
   包含CTEConsumer的进程在执行前依据CTEProducer的通知进行校验；

ABSTRACT

大数据分析场景中的query是很复杂的，通常一个query中不同的位置使用相同的子查询，也就是CTE（ Common Table Expressions）。CTE可以是用户显示高级查询，也可能是各个子业务间互相调用导致了大量的CTE。在MPP中CTE的挑战比单机更加大，因为数据天然是分布式存储的，同时数据量非常大，因此对于CTE优化就很有必要。

本文介绍基于Orac优化器框架上的CTE相关优化。

1. INTRODUCTION

CTE可以看做是一个query级别的临时表，使用CTE有两个目的：

1. 简化sql的逻辑，提高可读性；

2. 提取公因式，消除重复执行，提高性能；

例子：

WITH v as (SELECT i_brand, i_current_price, max(i_units) m
        FROM item
        WHERE i_color = 'red'
        GROUP BY i_brand, i_current_price)
SELECT * FROM v
WHERE m < 100
            AND v.i_current_price IN (SELECT min(i_current_price)                                                                         FROM v WHERE m > 5);

上述例子中CTE(v)出现了两次，简单的执行策略是在所有出现v的地方进行展开，但是执行了两次，也可以考虑对CTE进行优化只执行一次。

CTE可以建模成producer/consumer模型，

2种可能的方案：

1. 通过rewrite，对CE展开，又回到执行多次的老路子，单也不是完全都是坏处，展开后可以结合CTE出现的上下文进一步的优化；

2. 对CTE单独执行和优化，结果存在内存或者disk上，问题是当内存放不下时需要有IO，或者通过网络传给引用它的进程；另外，对所有使用CTE的地方只做一次优化执行，可能会失去进一步优化的机会；

1.1 Challanges

1.1.1 死锁

MPP中一个query中的不同部分在不同process执行，形成pipeline，一个process等待其他process产生数据；

CTE做为producer在一个process执行，那么，consumer在另外的进程执行，就需要等待该CTE进程；

当存在多个CTE时，需要保证产生的plan没有互相等待的process，否则就会死锁；

1.1.2 对CTE是否内联的枚举

tpc-ds的sql-13

WITH v as (SELECT i_brand, i_color FROM item
                        WHERE i_current_price < 1000)
SELECT v1.*
FROM v v1, v v2, v v3
WHERE v1.i_brand = v2.i_brand AND v2.i_brand = v3.i_brand AND v3.i_color = ’red’;

全部内联和全部都不内联都不是最优的：

1. 都不内联，CTE仅仅执行一次，但是在where条件中没有用到index的优势；
2. 全部内联，CTE(v)被执行多次；
3. 部分内联，where中的v3.i_color='red'可以使用index；
   
   Optimizer的方法论：
4. 对CTE是否内联进行枚举；
5. 计算每个可能的cost，通过cost来选择；

1.1.3 CTE上下文的优化

CTE的优化要考虑它被引用到的上下文能否进一步优化，否则就会错失一些优化的机会，比如：

1. 在所有消费CTE的地方都有filter，显然可以pushdown到CTE中的；
2. 在所有的消费者都要求CTE的result是re-partitioned或者sorted，下推后也能减少重复的re-partitioned或者sorted；
3. 不能简单的每个引用到CTE的地方都进行一次re-optimier，否则search space会膨胀；
4. 优化器需要把CTE当做普通的query一部分来优化，提前剪枝；

1.2 orca中对CTE的优化方法

基于Orca对非递归的CTE进行了形式化表达和优化：

1. orca framework支持基于上下文的CTE优化；
2. 仅在需要的时候才进行re-optimizer，比如fitler或者sort的下推，减少search space；
3. 基于cost-base的算法来决定是否对CTE进行展开；
4. 减少plan的search space，加速plan的执行，比如：下推fitler和sor到CTE，如果CTE被引用一次则始终展开；
5. 消除掉没有被引用的CTE；
6. 避免死锁，保证CTE的producer在consumer之前执行；

2. RELATED WORK

在sql查询和优化器领域中对CTE的优化已经有的一些研究成果。

不同优化器对CTE的优化

SCOPE优化器：2-phase的优化过程

1. 阶段1：record，记录所有引用CTE的physical properties，比如：data partitioning和sorting；
2. 阶段2：re-optimization，在所有属性中找最小公共祖先（physical properties是一个树状结构），然后把公共的部分下推到CTE；

Orca的做法

1. 把CTE当做一等公民，query的一部分，无需re-optimization的过程；
2. 无需通过搜索最小公共祖先来得到CTE的 entry point；
3. 可以提前剪枝：消除了re-optimization；

PostgresSQL优化器

把CTE当做复杂查询的一个subquery，单独优化出一个subplan。如前面所说，这样会措施一些优化的时机：

• 内联 CTE；
• 当所有引用CTE的node上有相同的physical properties，无法enforce到CTE里面；
• pushdown；

Oracle优化器

1. 既可以，把subquery结果集存储为temp table，可以被所有引用CTE的地方多次引用;
2. 也可以，把CTE内联到所有引用的地方；
3. 可以通过query hint执行:MATERIALIZE或者INLINE来干预优化器行为；

其他优化器

HP vertica和PDW都是把CTE做为temp table处理；

基于materialized view的优化

传统db对基于物化视图的优化已经有了一些研究成果。

和Orca对CTE是否inline的算法类似：基于cost-driven来决定是否使用物化视图；

不同点有：

1. materialized view是通过match算法来决定是否使用（隐式），而CTE是显示的在query中被引用到了；
2. View match算法可以捕获query中的公共subquery是否匹配了一个view，并决定是否要替换成view（在query中找到共性的部分）；
3. orca 的做法：

• orca的CTE frame也可以支持对subquery的捕获；
• 同时，orca支持上下文优化（下推等），而物化视图无法下推（物化视图的创建独立于query）；

3. Background

3.1 Massively Parallel Processing

现代scale-out的数据库设计遵循2个方法论：shared 和 MPP。都是share-nothing的架构，每个node有自己独立的存储和内存，都是水平扩展。

1. Shared系统：
   优化目标是：尽量在小的数据集上执行sql，shared之间的communication尽量少；
   Nodes可以跨机房和甚至跨洲；
2. MPP系统：
   以并行执行的方式优化query。nodes经常分布在同一个数据中心，每个query都访问所有的node；
   优化器产生的plan中包含显示的data move的指令，而且data move的成本也在优化的cost model中；
   以pipeline的方式分阶段执行；
   GPDB中的Motion operator用来在segment之间传输数据。Motion operator做为不同进程之间收/发数据的边界算子。
   把Motion做为算子，plan的一部分，以通用的数据库的方式解决了数据分布的问题，其他plan node仍然沿用之前的逻辑，在需要从其他节点收数据时通过motion来获取数据；
   Motion对db屏蔽了数据分布的细节；

3.2 query optimization in orca

orca是gpdb的优化器，基于cascades framework的top-down的优化器；

几个概念：

1. Memo: 以特定的编码格式存储plan space， Memo由groups组成；
2. Group expression：每个group内的逻辑等价表达式（logical equivalent expression）；
3. 每个group表示一个logical operator；
4. Group以树状组织；
5. search path的产生通过transformation rules：
   logical: 等价表达式，比如（A join B） = （B join A）；
   Physical: 对已有逻辑表达式的physical implementation转换，比如（A hashjoin B），（A nestloop join B）；
   通过rules新产生的expression和group再次加入到Memo中，（队列）；
6. enforcer：在优化过程中，一个operator可能向子节点请求physical properties（sort或者data distribution），一个子节点plan可能满足这个properties，比如：indexScan满足sort；也可能不满足，那么就需要对这个plan进行enforcer，使得它具有这个property；

4. CTE在orca中的表达

为了在ORCA中表达CTE，对CTE形式化描述，引入4个CTE相关的operator:

1. CTEProducer：独立于main query的logical tree的根节点，一个CTE对应一个producer；
2. CTEConsumer：main query中引用CTE的地方；
3. CTEAnchor：原query的parse tree中，定义CTE的node。CTE只能被改CTEAnchor的子树引用；
4. Sequence：这是一个二元操作符，先执行左节点，再执行右节点，并把右节点做为返回值。此外，orca还使用Sequence来优化partition tables《Optimizing Queries over Partitioned Tables in MPP Systems》；

通过下面的例子来说明ORCA中如何描述CTE的结构。

WITH v AS (SELECT i_brand FROM item WHERE i_color = ’red’)
SELECT * FROM v as v1, v as v2
WHERE v1.i brand = v2.i brand;

1. 左边：为CTE的定义，其中根节点是CTEProdcer，并且id=0；
2. 右边：CTEAnchor是main query中CTE定义的地方，CTEConsumer是引用的地方，其id=0；

1. 左边，CTE被内联的执行计划；
2. 右边，CTE不内联的计划，逻辑操作符CTEAnchor被Sequence替换，保证producer先于consumer执行；
   左节点：CTEProducer会先被执行；
   右节点：是main query，做为返回值；

如何表达嵌套CTE

下面SQL中CTE-w嵌套在CTE-v中：

WITH  v as (SELECT i_current_price p FROM item
                        WHERE i_color = ’red’),
            w as (SELECT v1.p FROM v as v1, v as v2 
                        WHERE v1.p < v2.p)
SELECT * FROM v as v3, w as w1, w as w2
WHERE v3.p < w1.p + w2.p;

5. CTE的执行和死锁

在执行时需要给plan的不同子树创建依赖关系，避免死锁；

一种方式方法是：把CTEProduer做为CTEConsumer的孩子节点：

1. 先在不考虑CTE表达式，优化query；
2. 优化CTE；
3. 对于SQL中的每个CTE（一个SQL中定义了多个CTE） ：

1. 以execution order遍历main query；
2. 在第一个CTEConsumer下面挂上相应CTEProducer，否则会死锁；
   下图中，把CTEProducer挂在第2个consumer下面，导致：第一个consumer在等produer，而CTEProduer在右节点上得不到执行，产生死锁；

即使把CTEProducer放在了第一个CTEConsumer下面，在执行时也可能产生死锁。比如：

CTEProducer在右子树上；

NLJoin的时候，左子树‘i_current_price=1000’输出的tuples为0；

那么，右子树会被忽略，CTEProducer不会被执行；

6. plan enumeration

前面提到过CTE的inline与否需要取决于代价，因此需要枚举出CTE在不同引用地方inline前后的计划树代价。

Orca中是如何枚举CTE的呢？

下图是初始的逻辑查询在Memo中的结构，每个编号就是一个memo group；

6.1 transformation rules

transformation rule：可以看做Memo Group一个输入（或者一个函数），该group根据这个规则产生另一些expression放在同一个memo group中；

对于每个CTE，都会产生inlining和not inlining；

例子：

1. 第一个被应用的rules是CTEAnchor operator：
   产生：Sequence operator，左子树比右子树先执行，并且左子树是CTEProducer，右子树是原来CTEAnchor的子树；
2. 第二个rule也是作用到了CTEAnchor:
   产生：NoOp operator：只有一个子树，就是原来CTEAnchor的子树；
3. 第三个rule是作用于CTEConsumer：
   产生：CTE的一个展开，其中CTE的根Select在同一个group中，而子树在新的group中；

该方法产生的plan树的组合中并不都是合法的，比如：

1. a和 b都没有CTEproducer；
2. c有一个CTEProducer，没有CTEConsumer；
3. d中的plan是合理的，但是只有一个CTEConsumer，不是一个优秀的plan；

通过Memo的机制来表达不同的plan，基于cost-based选择是否inline；

同一个main query中，不同的CTE，可能有的inline，而有的不inline；

Inline的好处是能进行普通query的优化，比如：下推，distribution，sorting：

• CTEConsumer上游有predicate: i_color='red’；
• Orca在下推时尽量远的下推predicate；

6.2 avoid invalid plans

通过orca的2个机制来避免CTEProducer和CTEConsumer无效的plan：

1. Pass down query requiremetns；
2. Deriving plan properties;

算法如下：

CTESpec是描述一个CTE的属性(id, type)构成，比如：(1, 'c')，cteid=1，类型是：consumer。

1. 先计算自身的CTESpec；
2. 遍历所有子节点
   计算对于该自子节点的CTESpec的请求，输入是：前面兄弟节点的prop（包括自身），来自父节点的req，得到该子节点应该满足的prop；
   递归向子节点调用该函数；
3. 逐个校验该子树得到的prop和父节点的请求，是否match；

ComputeCTESpece：是所有操作符的虚函数，但是只有CTEProducer和CTEConsumer这连个操作符有函数值，就是对应的cteid和类型；

Request()函数：计算出针对该子节点的新的CTEspec，输入是前面兄弟节点的prop（包括自身），来自父节点的req，规则是：

1. 返回父节点没有的spec，但是前序兄弟节点有的spec。比如图8中d的Sequence操作符，它的左子节点返回(0, p)，combine到specList中，在计算右子节点时request函数就函数了(0, c)做为对右子节点的请求；
2. 返回父节点有的spec，但是前序子节点没有满足的spec，比如上面所说的右子节点的(0, c)在join的左子节点的SELECT中满足不了，在计算右子节点时request函数就函数了(0, c)做为对右子节点的请求；
   Combine()函数：负责把子节点DeriveCTE返回的spec（子节点根据自身情况，以及请求，返回能满足请求的spec，是请求的子集），和逐个的累加。如果发现有一对CTEProducer和CTEConsumer就从specList中去除掉。
   Satisfies()函数：比对父节点收到的CTEspec请求和所有子节点Derive返回的CTEspec是否匹配。

6.3 Optimizations Across Consumers

通过前面的方法可以枚举出所有CTE是否inline的计划，本小节讲述其他优化CTE的方法。

6.3.1 Predicate Push-down

WITH v as (SELECT i_brand, i_color FROM item
                        WHERE i_current_price < 50)
SELECT * FROM v v1, v v2
WHERE v1.i_brand = v2.i_brand
AND v1.i_color = ’red’
AND v2.i_color = ’blue’;

把一个CTEProducer对应所有的CTEConsumer的predicate，下推到该CTEProducer上，条件通过OR组合起来，减少物化的数据量。

注意：因为下推到CTEProducer的predicate是通过OR连接的，因此CTEConsumer仍然需要执行原来的predicate。

6.3.2 Always Inlining Single-use CTEs

只有一个CTEConsumer的CTE，永远进行inline。

WITH v as (SELECT i_color FROM item WHERE i_current_price < 50)
SELECT * FROM v
WHERE v.i color = ’red’;

6.3.3 Elimination of unused CTEs

消除没有使用到的CTE

WITH v as (SELECT i_color FROM item WHERE i_current_price < 50)
SELECT * FROM item
WHERE item.i color = ’red’;

7. CONTEXTUALIZED OPTIMIZATION

在ORCA中对CTE的inline与否进行枚举之后，进一步，plan中不同部位的CTEConsumer使用不同的优化方案（inline和非inline，下推等）

7.1 Enforcing Physical Properties

orca中对计划树空间的优化是通过topdown的发送optimization-request来驱动完成的，optimization-request是指：sort oder；distribution；rewindability；CTE；partition。

下面以distribution为例子。

CTE需要在不同的上下文中满足不同的Physical Properties。

7.1.1 Producer Context

CTEProducer可以无需考虑CTEConsumer在什么上下文中被引用到。

上图中，

1. Sequence算子对CTEProducer发射ANY的prop请求，返回Hashed(i_sk)的prop(表item的分布方式)；
2. 上述的prop发送到右子树中（结合自身prop和父节点的prop），右子树中的CTEConsumer根据物理prop是否满足插入相应的Redistribute；
   该CTE的结果被hash分发了两次，而且hash的表达式也是一样的。

7.1.2 Consumer Context

提取公因式：在所有CTEConsumer出现的地方，可能有相同的prop请求，这些相同的prop请求可以在CTEProducer中进行enforce。

1. 第一个CTEConsumer算子向sequence算子发送它自己收到的prop请求（因为sequence是CTEAnchor，是该CTEproducer的父节点），这个请求和不同的prop请求有区别：仅仅发送给CTEProducer来处理；
2. CTEProducer收到这个Hashed(i_brand)请求之后在自己的子树中插入Redistribute(i_brand)，使得自己满足这个prop；
3. 再次对CTEConsumer进行enforce时，它们的CTEProducer就已经有了Hased(i_brand)属性了，因此就无需做两次hash分布了。

该基于上下文的enforce和前面的CTE是否inline的枚举是正交的，最终优化器可能会选出：

1. 部分cte被inline，部分cte没有inline；
2. CTEProducer上的prop可能是多个CTEConsumer的prop的一个超集；
3. 对于哪些CTEConsumer要求的prop，CTEProducer中没有的，则会加上新的CTEProducer和prop；

通过把CTE做为orca的核心流程，避免了CTE的多个阶段优化，可以利用orca的剪枝：在发现一个cost之后，对CTE进行后续优化时估计的cost比当前的还大就把复杂CTE的优化剪枝掉。

7.2 Cost Estimation

CTEProducer和CTEConsumer的代价分开计算：

1. CTEProducer代价是CTE自身的代价，加上物化写磁盘的代价；
2. CTEConsumer代价是从读取物化结果的代价，类似scan算子；

8. CTE-BASED OPTIMIZATIONS

8.1 CTE-Generating Transformations

ORCA中利用对CTE的优化算法，可以把其他SQL计算先隐式的转成CTE，入：windown function, full outer join, distinct agg。

SELECT COUNT(DISTINCT cs_item_sk), AVG(DISTINCT cs_qty)
FROM catalog_sales
WHERE cs_net_profit > 1000

上述SQL中对两个不同列做distinct。MPP中对单个列做disticnt时，先hash到不同的计算节点，然后每个计算节点再去重，然后再汇总；

当有多个列需要distinct时，该算法效率不高，因为有多个不同的列需要重分布，就需要逐个的按照不同的列做hash重分布+去重。多次读取表并执行predicate。

可以借助CTE把多个distinct逻辑转成：join + 多个CTEConsumer。可以一次计算输入，结果给多个distinct使用。join的作用是把多个distinct结果拼在一行tuple上输出。只执行一次CTEProducer（扫描+predicate），一个CTEConsumer具体的执行一个distinct，不同的distinct间也可以并行。

如果对更多的列做distinct，可以join更多的CTEConsumer。

8.2 Common Subexpression Elimination

CTE还可以用于优化公共表达式，消除重复的表达式。

SELECT *
FROM (SELECT i_brand, count(*) as b
                FROM item GROUP BY i_brand HAVING count(*) > 10) t1,
            (SELECT i_brand, count(*) as b
                FROM item GROUP BY i_brand HAVING count(*) > 20) t2
WHERE t1.i brand <> t2.i brand;

上述SQL中有重复的子表达式，重复子表达式可以通过table signature算法找出来。公共的子表达式使用CTEProducer和CTEConsumer来替代。

1. 计算出公共表达式集合M；
2. 对于每个m，插入CTEProducer和id；
3. 递归插入CTEConsumer；
4. 在最小公共祖先处插入CTEAnchor；

9. EXECUTION

CTEConsumer只从本地的CTEProducer读取tuple，如果需要重分布，则在CTEConsumer上面插入相应的算子，CTEConsumer永远不会从其他host直接去读CTEProducer。

在执行器中CTEConsumer对应的是SharedScan算子，CTEProducer对应的是Materialize（Spool）或Sort算子。

一个CTEProducer会有多个CTEConsumer消费者，可能在一个进程中，也可能在本host上的不同的进程中，通过cteid来识别。此外，执行器需要保证CTEConsumer能够等到CTEProducer的数据：每个CTEProducer上记录有几个CTEConsumer在本进程内部，和跨进程有几个CTEConsumer。

含有CTEProducer的进程在生产完数据后，会通知对应所有的CTEConsumer（本进程或者跨进程），包含CTEConsumer算子的进程在执行前会检查是否所有的CTEConsumer算子都得到了通知。

CTEProducer的输出物化到TupleStore中，TupleStore提供了一个迭代器，可以根据work_mem开决定在内存中还是写入到磁盘上。

如果CTEProducer和CTEConsumer在一个进程中，且数据量不大时，可以直接读取内存。如果在不同的进程中，则一定会物化到磁盘上，同时CTEProducer通知CTEConsumer时，会把文件名发送过去。

另外一个优化，如果CTEProducer的输出是有序的则无需物化算子Spool，因为sort算子的结果集本身就是物化的。

还可以通过CTEProducer的lazy执行来优化执行过程，在CTEConsumer第一次消费数据时跳转到CTEProducer的执行流程中。如果不在一个进程中，则需要Coordinator来协调，CTEProducer和CTEConsumer异步的执行，每次只生产一部分数据。但是对优化器的代价评估的挑战就变大了，优化器需要评估出究竟有多少数据落盘。

10. EXPERIMENTS

10.1 Setup

48G内存，SAS RAID-5，Linux 5.5，TPC-DS 5TB数据，测试SQL是其中有CTE的48条。

10.2 Comparing Orca against the Planner

使用ORCA后执行效率提升43%。

80%的SQL中，无论是短SQL还是长时间SQL都能得到提速。

原因分析：

1. 避免CTE的重复inline的计算量；
2. 消除重复公共表达式的计算量；

10.3 Cost-based Inlining

比较基于cost-base的CTE优化和启发优化的性能

1. 几乎inline比（不inline+下推）的性能要差；
2. inline性能好的场景是：CTE返回的结果集较小（重复执行的代价小）；或者只有一个consumer；
3. 使用inline时14a有44%的回退；
4. 基于cost-based总能得到最优性能；