从优化器的角度CTE的复杂度来自：
- 对query树中引用到CTE的地方都进行inline展开的好处是：可以结合CTE在计划树中上下文进一步的优化（下推，join顺序等），坏处是：CTE被重复执行了；
- 对引用到CTE的地方不进行inline展开的好处是：CTE只执行了一次，但是引用CTE上下文中的predicate无法下推了，比如有索引的情况下，无法使用索引；
- 在MPP中，引用CTE不同上下文中，对CTE的prop物理属性要求不同，有些属性可以合并。比如：有的地方要求升序，有的地方要求hash分布等；
ORCA优化器对CTE的优化方法：
- 在ORCA的框架中实现CTE的优化，而不像其他优化器在插件或者外围逻辑中进行多个阶段的优化；
- 引入CTEAnchor，Sequence，CTEProducer和CTEConsumer来描述CTE；
- 使用MEMO对inline和非inline进行枚举；
- 对CTEProducer和CTEConsumer上下文中的prop进行枚举；
- 上述优化后，可能使得部分CETConsumer得到inline展开，部分CTEConsumer不展开；公共prop属性下推到CTEProducer中；
- CTE技术还用于优化其他SQL场景，如：对多个列distinct；消除公共表达式；
- 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’;
全部内联和全部都不内联都不是最优的：
- 都不内联，CTE仅仅执行一次，但是在where条件中没有用到index的优势；
- 全部内联，CTE(v)被执行多次；
- 部分内联，where中的v3.i_color='red'可以使用index；
Optimizer的方法论： - 对CTE是否内联进行枚举；
- 计算每个可能的cost，通过cost来选择；
1.1.3 CTE上下文的优化
CTE的优化要考虑它被引用到的上下文能否进一步优化，否则就会错失一些优化的机会，比如：
- 在所有消费CTE的地方都有filter，显然可以pushdown到CTE中的；
- 在所有的消费者都要求CTE的result是re-partitioned或者sorted，下推后也能减少重复的re-partitioned或者sorted；
- 不能简单的每个引用到CTE的地方都进行一次re-optimier，否则search space会膨胀；
- 优化器需要把CTE当做普通的query一部分来优化，提前剪枝；
1.2 orca中对CTE的优化方法
基于Orca对非递归的CTE进行了形式化表达和优化：
- orca framework支持基于上下文的CTE优化；
- 仅在需要的时候才进行re-optimizer，比如fitler或者sort的下推，减少search space；
- 基于cost-base的算法来决定是否对CTE进行展开；
- 减少plan的search space，加速plan的执行，比如：下推fitler和sor到CTE，如果CTE被引用一次则始终展开；
- 消除掉没有被引用的CTE；
- 避免死锁，保证CTE的producer在consumer之前执行；
2. RELATED WORK
在sql查询和优化器领域中对CTE的优化已经有的一些研究成果。
不同优化器对CTE的优化
SCOPE优化器：2-phase的优化过程
- 阶段1：record，记录所有引用CTE的physical properties，比如：data partitioning和sorting；
- 阶段2：re-optimization，在所有属性中找最小公共祖先（physical properties是一个树状结构），然后把公共的部分下推到CTE；
Orca的做法
- 把CTE当做一等公民，query的一部分，无需re-optimization的过程；
- 无需通过搜索最小公共祖先来得到CTE的 entry point；
- 可以提前剪枝：消除了re-optimization；
PostgresSQL优化器
把CTE当做复杂查询的一个subquery，单独优化出一个subplan。如前面所说，这样会措施一些优化的时机：
- 内联 CTE；
- 当所有引用CTE的node上有相同的physical properties，无法enforce到CTE里面；
- pushdown；
Oracle优化器
- 既可以，把subquery结果集存储为temp table，可以被所有引用CTE的地方多次引用;
- 也可以，把CTE内联到所有引用的地方；
- 可以通过query hint执行:MATERIALIZE或者INLINE来干预优化器行为；
其他优化器
HP vertica和PDW都是把CTE做为temp table处理；
基于materialized view的优化
传统db对基于物化视图的优化已经有了一些研究成果。
和Orca对CTE是否inline的算法类似：基于cost-driven来决定是否使用物化视图；
不同点有：
- materialized view是通过match算法来决定是否使用（隐式），而CTE是显示的在query中被引用到了；
- View match算法可以捕获query中的公共subquery是否匹配了一个view，并决定是否要替换成view（在query中找到共性的部分）；
- orca 的做法：
- orca的CTE frame也可以支持对subquery的捕获；
- 同时，orca支持上下文优化（下推等），而物化视图无法下推（物化视图的创建独立于query）；
3. Background
3.1 Massively Parallel Processing
现代scale-out的数据库设计遵循2个方法论：shared 和 MPP。都是share-nothing的架构，每个node有自己独立的存储和内存，都是水平扩展。
- Shared系统：
优化目标是：尽量在小的数据集上执行sql，shared之间的communication尽量少；
Nodes可以跨机房和甚至跨洲； - 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的优化器；
几个概念：
- Memo: 以特定的编码格式存储plan space， Memo由groups组成；
- Group expression：每个group内的逻辑等价表达式（logical equivalent expression）；
- 每个group表示一个logical operator；
- Group以树状组织；
- 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中，（队列）； - enforcer：在优化过程中，一个operator可能向子节点请求physical properties（sort或者data distribution），一个子节点plan可能满足这个properties，比如：indexScan满足sort；也可能不满足，那么就需要对这个plan进行enforcer，使得它具有这个property；
4. CTE在orca中的表达
为了在ORCA中表达CTE，对CTE形式化描述，引入4个CTE相关的operator:
- CTEProducer：独立于main query的logical tree的根节点，一个CTE对应一个producer；
- CTEConsumer：main query中引用CTE的地方；
- CTEAnchor：原query的parse tree中，定义CTE的node。CTE只能被改CTEAnchor的子树引用；
- 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;
- 左边：为CTE的定义，其中根节点是CTEProdcer，并且id=0；
- 右边：CTEAnchor是main query中CTE定义的地方，CTEConsumer是引用的地方，其id=0；
- 左边，CTE被内联的执行计划；
- 右边，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的孩子节点：
- 先在不考虑CTE表达式，优化query；
- 优化CTE；
- 对于SQL中的每个CTE（一个SQL中定义了多个CTE） ：
- 以execution order遍历main query；
- 在第一个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；
例子：
- 第一个被应用的rules是CTEAnchor operator：
产生：Sequence operator，左子树比右子树先执行，并且左子树是CTEProducer，右子树是原来CTEAnchor的子树； - 第二个rule也是作用到了CTEAnchor:
产生：NoOp operator：只有一个子树，就是原来CTEAnchor的子树； - 第三个rule是作用于CTEConsumer：
产生：CTE的一个展开，其中CTE的根Select在同一个group中，而子树在新的group中；
该方法产生的plan树的组合中并不都是合法的，比如：
- a和 b都没有CTEproducer；
- c有一个CTEProducer，没有CTEConsumer；
- 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：
- Pass down query requiremetns；
- Deriving plan properties;
算法如下：
CTESpec是描述一个CTE的属性(id, type)构成，比如：(1, 'c')，cteid=1，类型是：consumer。
- 先计算自身的CTESpec；
- 遍历所有子节点
计算对于该自子节点的CTESpec的请求，输入是：前面兄弟节点的prop（包括自身），来自父节点的req，得到该子节点应该满足的prop；
递归向子节点调用该函数； - 逐个校验该子树得到的prop和父节点的请求，是否match；
ComputeCTESpece：是所有操作符的虚函数，但是只有CTEProducer和CTEConsumer这连个操作符有函数值，就是对应的cteid和类型；
Request()函数：计算出针对该子节点的新的CTEspec，输入是前面兄弟节点的prop（包括自身），来自父节点的req，规则是：
- 返回父节点没有的spec，但是前序兄弟节点有的spec。比如图8中d的Sequence操作符，它的左子节点返回(0, p)，combine到specList中，在计算右子节点时request函数就函数了(0, c)做为对右子节点的请求；
- 返回父节点有的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在什么上下文中被引用到。
上图中，
- Sequence算子对CTEProducer发射ANY的prop请求，返回Hashed(i_sk)的prop(表item的分布方式)；
- 上述的prop发送到右子树中（结合自身prop和父节点的prop），右子树中的CTEConsumer根据物理prop是否满足插入相应的Redistribute；
该CTE的结果被hash分发了两次，而且hash的表达式也是一样的。
7.1.2 Consumer Context
提取公因式：在所有CTEConsumer出现的地方，可能有相同的prop请求，这些相同的prop请求可以在CTEProducer中进行enforce。
- 第一个CTEConsumer算子向sequence算子发送它自己收到的prop请求（因为sequence是CTEAnchor，是该CTEproducer的父节点），这个请求和不同的prop请求有区别：仅仅发送给CTEProducer来处理；
- CTEProducer收到这个Hashed(i_brand)请求之后在自己的子树中插入Redistribute(i_brand)，使得自己满足这个prop；
- 再次对CTEConsumer进行enforce时，它们的CTEProducer就已经有了Hased(i_brand)属性了，因此就无需做两次hash分布了。
该基于上下文的enforce和前面的CTE是否inline的枚举是正交的，最终优化器可能会选出：
- 部分cte被inline，部分cte没有inline；
- CTEProducer上的prop可能是多个CTEConsumer的prop的一个超集；
- 对于哪些CTEConsumer要求的prop，CTEProducer中没有的，则会加上新的CTEProducer和prop；
通过把CTE做为orca的核心流程，避免了CTE的多个阶段优化，可以利用orca的剪枝：在发现一个cost之后，对CTE进行后续优化时估计的cost比当前的还大就把复杂CTE的优化剪枝掉。
7.2 Cost Estimation
CTEProducer和CTEConsumer的代价分开计算：
- CTEProducer代价是CTE自身的代价，加上物化写磁盘的代价；
- 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来替代。
- 计算出公共表达式集合M；
- 对于每个m，插入CTEProducer和id；
- 递归插入CTEConsumer；
- 在最小公共祖先处插入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都能得到提速。
原因分析：
- 避免CTE的重复inline的计算量；
- 消除重复公共表达式的计算量；
10.3 Cost-based Inlining
比较基于cost-base的CTE优化和启发优化的性能
- 几乎inline比（不inline+下推）的性能要差；
- inline性能好的场景是：CTE返回的结果集较小（重复执行的代价小）；或者只有一个consumer；
- 使用inline时14a有44%的回退；
- 基于cost-based总能得到最优性能；
