ORCA是Greenplum开源的优化器，它是C++实现的一个library，可以基于它开发属于自己的优化器（Hologres）；
完善的Cascades Framework实现；
完善的Property Enforce支持物理属性的扩展；
模块化设计容易扩展，方便实现自己的transformation规则；
ABSTRACT
ORCA是一个独立的library，应用在Greenplum和HAWQ两个产品中。
ORCA的特点：
- 模块化设计；
- 扩展性好；
- 多线程优化；
- 可验证性：开发相关工具验证，复现产生Plan的过程；
- 更有的Plan；
ORCA ARCHITECTURE
基于Cascades优化器框架的top-down优化器，可以做为一个library运行在DB系统外部。因此可以用于多个MPP系统的构建。
DXL - DB内核如何对接ORCA
ORCA基于XML构建了一个DXL框架用于ORCA和DB内核之间的交互。
输入是：DXL的query；
输出是：DXP的plan；
流程：
- DB内核提供一个metadata provider 类，这个类实现ORCA的接口IMDProvider；
- 在调用ORCA时，把这个类传入做为其中一个参数；
- ORCA内部在优化过程中通过这个类拿到meta的信息；
- 这个类把meta组织成IMDCacheObject对象；
总结，数据库内核需要提供3类接口：
- Query2DXL把parse tree转成DXL（CTranslatorQueryToDXL::TranslateSelectQueryToDXL）；
- DXL2Plan把DXL转成可执行的Plan（CTranslatorDXLToPlStmt::GetPlannedStmtFromDXL）；
- MD provider把metadata转成DXL（CMDProviderRelcache::GetMDObj）；
ORCA内部组件
Memo
计划的搜索空间编码压缩成Memo结构：
- Memo内部由groups组成；
- groups内部由逻辑等价表达式组成，一个groups表达SQL中的一个节点；
- group expressions，groups内每个expr都叫做group expressions，每个group expressions有其他group做为子节点；
为何能起到压缩效果：
- group expressions和子groups组织成了一个树状结构；
- 搜索空间中的plan，如果有相同的子树结构，通过指针共享；
Search and Job Scheduler
优化器的核心之一就是如何高效的搜索plan空间。
Job Scheduler过程中的task之间维护依赖关系，没有依赖的task可以并行执行。
搜索分为3个阶段：
- exploration;
- implementation；
- optimization；
Transformations
搜索空间的扩展是通过应用transformation规则：
- 逻辑规则：(A, B) -> (B, A)
- 物理规则：Join(A, B) -> HashJoin (A, B)
规则可能会产生新的group加入到Memo中，或者新的group expr加入到相同的group中。
每个规则都可以通过配置关闭。
Property Enforcement
Query有属性要求，具体一个Plan有固有的属性，这些属性通过形式化的property specifications来描述。
Property有3类：
- logical：output column；
- physical：sort order，distribution；
- scalar：join condition中引用到的column；
在opt阶段，每个operator都可以向子节点发射property的要求。子节点在经历完opt阶段后，可能自身能满足父节点发送过来的prop要求（indexscan能提供sort属性），也可能满足不了，此时需要加入一个enforcer，已满足请求的prop。
Metadata Cache
由于元数据不经常变更，ORCA内部维护了一份缓存。
GPOS
提供ORCA的基础组件：内存管理，状态机，线程通过，异常，文件IO。
4. QUERY OPTIMIZATION
4.1 Optimization Workflow
SELECT T1.a FROM T1, T2 WHERE T1.a = T2.b ORDER BY T1.a;
T1的分布式：Hashed(T1.a)
T2的分布式：Hashed(T2.a)
DXL Query
DXL query描述了project，table，join以及meta，每个meta用Mdid表示：
- 类似oid，描述表，操作符；
- 带有version号，用来invalid过期的cache；
Logical Expr
DXL query传入ORCA，解析成内存中的logical exprssion，存入Memo中，做为Memo的初始状态。
这个SQL对应3个group，group 0称为root group。
Inner Join[1, 2]自节点是group1和group2。
Exploration
logical 规则生成等价的逻辑变换，比如：
交换律：InnerJoin[1,2]转成InnerJoin[2,1]；
子查询去关联化；
下推，上拉；
产生出来新的expr会加入到group中。
由于多个规则可能会产生相同的expr，因此memo有去重机制。
Statistics Derivation
上一步结束后产生了所有可能的逻辑搜索空间，开始进入Statistics Derivation，为每个memo group获取统计信息，列的直方图，用来统计cardinality和data skew。
统计信息只和逻辑expr相关，和物理expr无关，因此在这个阶段获取统计信息，如果放到后面物理变换之后，memo空间就变大了。
Statistics promise
一个InnerJoin的group需要计算最终这个group的cardinality，这个group下面可能有很多个逻辑等价的join，每个join的表达式可能不同，因此会计算出不同的cardinality值。
每个group选择最高promise值的表达来做为计算统计信息的目标。
如何计算promise：
- promise值和表达式相关，越少值约高，比如：InnerJoin时，表达式少最终估算的越准确，因此promise值（能承诺的统计信息）越高。表达式越多错误估计越容易被放大；
- 遍历expr，每个node计算一个confidence值，最后累加在一起；
根据promise值选择好要计算的expr后，递归的向子节点执行 Statistics Derivation，待子节点执行完后，根据子节点的统计和当前expr计算出自己的统计。
如图：
Top-down按需发射请求，Join的条件是T1.a = T2.b，因此需要T1.a和T2.b的直方图；
Bottom-up获取上面传下来的请求，通过MD Provider接口从DB内核获取，并缓存；
每个group各自管理统计，一个group共享一份统计。
Implementation
应用物理转换规则，比如：InnerJoin2HashJoin，InnerJoin2NLJoin。
Optimization
这个阶段2个目标：
- enforce；
- 计算cost；
Optimization阶段向root group发射optimization的请求，请求描述prop：比如distribution和sort。
对于每个请求r，group expr会计算应该向子节点传递什么请求，输入是：来自父节点的r，和自身local的prop。对于同样的请求，orca会缓存防止重复计算。
- group上有hash表：记录该group的在不同请求对应本group中最优expr；
- 每个expr上有一个local hash：记录每个请求对应的子节点，用来最后从group树中抽取出plan
下图中：
- 第一个请求是#1:{Singleton, <T1.a>}，结果集在master上汇总，并且结果集按照T1.a排序。
- 左边的Groups Hash Tables是该Group下每个请求对应cost最低的GExpr编号；
- Group中黑色矩形的Operator是enforce（distribution和sort）产生的节点；
- Gather算子从所有segment server上收集tuple；
- Gather Merge算子收集已经排好序的tuple，并且归并排序；
- Redistrbute算子在segment server之间shuffle；
下图中：
- 对group0的innerHashjoin[1,2]发送#1:{Singleton, <T1.a>}请求；
- innerHashjoin，根据join条件t1.a=t2.b，向左右子group分贝发送Hashed(t1.a)和Hashed(t2.b）；
- 子group收到hashed请求后：对于A，无需额外操作只需要scan；对于B，要进行rediistribte+scan；
如果prop不满足inittial请求，则要进行enforce过程；
orca实现了完善的prop enforce框架，支持每个operator定义：根据子节点的prop和自身的行为来决定是否已经满足prop，比如NLjoin的话，outer已经有序了，那么最终该nljoin就是在outer上有序的；
enforce过程产生的节点加入到正在被opt的节点同一个group中。
最优计划的输出过程：
- 从Group Hash Table中找到#1对应的最优GExpr是8；
- GExpr的local hash中记录了请求#1对应的子请求是#3；
- 再次在Group Hash Table中找到#3对应的是GExpr为6；
- GExpr6的local hash中记录了请求#3对应的子请求是#4；
- 重复上述步骤就能把最终最优计划找到；
GPORCA可以打开调试参数，输出优化的过程。
准备环境：
SET client_min_messages=log; SET optimizer_print_memo_after_optimization=on; SET optimizer_print_optimization_context=on; SET optimizer_print_memo_after_exploration=on; SET optimizer_print_memo_after_implementation=on; CREATE TABLE t(a int); EXPLAIN SELECT * FROM t t1 JOIN t t2 ON t1.a=t2.a;
优化过程如下：
ROOT Group 5 (#GExprs: 8): 0: CLogicalNAryJoin [ 0 1 4 ] 1: CLogicalInnerJoin [ 0 1 4 ] 2: CLogicalInnerJoin [ 1 0 4 ] 3: CPhysicalInnerHashJoin (High) [ 1 0 4 ] Cost Ctxts: main ctxt (stage 0)1.0, child ctxts:[6, 6], ..., cost: 862.000429 main ctxt (stage 0)1.2, child ctxts:[5, 5], ..., cost: 862.000643 main ctxt (stage 0)1.3, child ctxts:[4, 4], ..., cost: 862.000537 main ctxt (stage 0)0.3, child ctxts:[4, 4], ..., cost: 862.000537 4: CPhysicalInnerNLJoin [ 1 0 4 ] Cost Ctxts: main ctxt (stage 0)1.3, cost lower bound: 1324031.092755 PRUNED main ctxt (stage 0)0.3, cost lower bound: 1324031.116949 PRUNED 5: CPhysicalInnerHashJoin (High) [ 0 1 4 ] Cost Ctxts: main ctxt (stage 0)1.0, child ctxts:[3, 3], ..., cost: 862.000429 main ctxt (stage 0)1.2, child ctxts:[2, 2], ..., cost: 862.000643 main ctxt (stage 0)1.3, child ctxts:[0, 0], ..., cost: 862.000537 main ctxt (stage 0)0.3, child ctxts:[0, 0], ..., cost: 862.000537 6: CPhysicalInnerNLJoin [ 0 1 4 ] Cost Ctxts: main ctxt (stage 0)1.3, cost lower bound: 1324031.092755 PRUNED main ctxt (stage 0)0.3, cost lower bound: 1324031.116949 PRUNED 7: CPhysicalMotionGather(master) [ 5 ] Cost Ctxts: main ctxt (stage 0)0.0, child ctxts:[1], rows:1.000000 (group), cost: 862.000458 Grp OptCtxts: 0 (stage 0): (req CTEs: [], ...) => Best Expr:7 1 (stage 0): (req CTEs: [], ...) => Best Expr:5
Multi-Stage Optimization
多stage优化：先基于简单的xform规则找出一个计划；
然后使用这个cost做为基准，使用更加复杂的xform规则，再跑一次3阶段，这个cost可以做为剪枝的门槛；
优化结束的3个条件：
- 找到了一个cost低于配置的cost-threshold；
- time-out；
- 已经遍历了所有的规则；
在优化复杂查询时，这个机制可以尽快的产生一个计划。
Query Execution
在执行器中，以Shuffle算子为边界，把Plan拆分成子Plan，Shuffle分裂成接收端和发送端。
4.2 Parallel Query Optimization
ORCA支持多线程优化，为了达到多线程优化，实现了一个optimization job调度器。
每个优化路径的多个阶段拆分成了不同的job；
job放入到queue中；
多线程从queue中消费job；
job之间维护前后依赖关系，没有依赖关系可以并行；
因为是top-down的进行优化，父节点的job会先进入queue中，会触发子节点的优化（后序遍历递归）；
子节点job没有执行完之前，不会调度执行父节点的job；
状态机
每个job通过状态机描述状态，search engine推送消息状态机的推动状态转变。每种job对应一个状态的定义。
状态转换如下：
状态机和Group的关系是多对一的关系。
如何调度GroupExpressions？
一个group上会有不同阶段的状态机，同一个group在多个（3阶段）状态机中会被调度执行：每个阶段的group状态机都保留了exp列表的迭代器；
各个goup上状态机的关系
5. METADATA EXCHANGE
Orca能和不同的外部系统沟通。在优化一条SQL期间所有meta缓存在内存中，以便在同一个SQL优化过程中，对同一个元数据多次访问。当优化执行结束，缓存清空。
此外，ORCA实现了file-base的MD Provider，这样ORCA就可以直接运行，而不需要启动一个DB。方便开发和调试。
6. VERIFIABILITY
ORCA开了一些工具用于测试
6.1 Minimal Repros
AMPERe用于复现，调试ORCA，而不需登录到用户的DB环境。
当ORCA内部出现异常，或者计划不符合预期时，会自动把相关元数据，query，优化配置序列成xml，dump到文件。
后续可以直接回放这个xml，而不需要进入到DB中。
另外，AMPERe还可用于建立测试框架，指定特定的dump文件和期望的plan即可。
6.2 Testing Optimizer Accuracy
当修复bug或者新增功能后，如何保证产生的计划性能没有回退。
TAQO用于测试ORCA的cost model的精准度，比如cost值高的计划理论上有更长的执行时间。
比如：优化器得到顺序(p1, p3)是符合实际情况的，因为实际p3的cost比p1大，估算的p3也是比p1大。
TAQO从search space选取一下计划，比较估算的cost代价和真实的执行时间，然后比对是否符合预期。选取计划的过程就是在opt之后通过Group Hash Table串联Plan的过程。
优化器估算出来的cost和真实执行的时间，这两组数据之间计算出相关性分数（重要计划，距离等因素）。
7. EXPERIMENTS
7.1 TPC-DS Benchmark
真实决策系统中负载在TPCH中并没有描述，而TPCDS有相关负载的测试场景。
TPC-DS：25个表，429列，99条SQL，丰富的语法（WITH, window, subquery, outer join, CASE, Intersect, Except）
7.2 MPP Databases
使用GPDB来测试，对比的优化器是ORCA和内置基于PostgreSQL开发的MPP优化器。
7.2.1 Experiment Setup
网络：10Gbps
内存：48GB
磁盘：12个，600GB， SAS，RAID-5；
内核：5.5
数据量：TPC-DS 10TB
7.2.2 Performance
ORCA和PG planner这两个优化器都完整支持TPC-DS的优化。
80%有提升，整体提升5倍。
- 设置优化器time-out
Q14在PG planner优化器中超过10000秒，而ORCA可以设置time-out，无需搜索全部计划空间。 - 数据分partition；
ORCA和PG planner相比优势：
- Join Ordering：有大量基于DP的join order优化算法，left-deep join tree，cardinality-based join order；
- Correlated Subqueries：实现了子查询的Apply去关联化算法；
- Partition Elimination：动态分区裁剪；
- Common Expressions：生产者消费者CTE优化；
ORCA有部分SQL的计划性能比PG planner慢2倍，原因是ORCA的cost model还有待优化。
优化器自身的性能：平均优化时间4秒，内存200MB；
7.3 SQL on Hadoop
略
8. RELATED WORK
8.1 Query Optimization Foundations
Volcano Parallel Database
提出了parallelism in databse的方法，引入了exchange operator，支持2种并行：
- inter-operator parallelism：pipeline
- intra-operator parallelism：多进程并行扫描算子
每个算子在local data上独自执行，其他进程并行地执行相同的算子
Cascades
可扩展的优化器框架，被应用到MS-SQL Server，SCOPE，PDW，ORCA。这个框架的优势是：
1 logical和physical搜索空间分离；
通过operator，transformation规则。同时把逻辑等价expr组织成group，group之间是树状关系；
2. 转换规则按需触发，规则按照优先级使用；
在Cascades基础上提出并行优化器框架《Parallelizing Extensible Query Optimizers》，Orca就是参考此而实现的。
8.2 SQL Optimization On MPP Databases
SQL Server Parallel Data Warehouse (PDW)
先生成单机的逻辑计划，然后再加上redistribution。
- PDW每个opt请求都发送到MS-SQL进程的优化器（只管理元数据和统计，不维护用户数据）；
- MS-SQL进程返回logical 计划给DMS（Data Movement Service），给这个逻辑计划加上数据分布的约束；
Structured Computations Optimized for Parallel Execution (SCOPE)
Microsoft’s的数据分析平台，结合parallel database和mapreduce两个系统。
SCOPE是给Cosmos开发的，应用于append-only文件系统。
SAP HANA
分布式内存数据库，处理AP和TP业务。一个AP的MPP数据能产生大量的中间结果集。并发高的话能把内存吃掉，因此需要spill to disk。
Vertica
CStore的商业化MPP版本，数据组织成projection，每个projection管理部分列集合。优化器为星型/雪花型设计。当相同range的join key没有聚集时，需要把projection在所有节点上复制。
8.3 SQL On Hadoop
Hive转成mapreduce任务，满足不了交互查询。Impala，HAWQ，Presto是基于hdfs设计的新引擎支持交互式。Microsoft的PolyBase支持PDW和HDFS联邦查询。
9. SUMMARY
ORCA的目标是优化器框架，模块化设计方便了其他DB数据系统优化器的开发。
