ORCA是Greenplum开源的优化器，它是C++实现的一个library，可以基于它开发属于自己的优化器（Hologres）；

完善的Cascades Framework实现；

完善的Property Enforce支持物理属性的扩展；

模块化设计容易扩展，方便实现自己的transformation规则；

ABSTRACT

ORCA是一个独立的library，应用在Greenplum和HAWQ两个产品中。

ORCA的特点：

1. 模块化设计；
2. 扩展性好；
3. 多线程优化；
4. 可验证性：开发相关工具验证，复现产生Plan的过程；
5. 更有的Plan；

ORCA ARCHITECTURE

基于Cascades优化器框架的top-down优化器，可以做为一个library运行在DB系统外部。因此可以用于多个MPP系统的构建。

DXL - DB内核如何对接ORCA

ORCA基于XML构建了一个DXL框架用于ORCA和DB内核之间的交互。

输入是：DXL的query；

输出是：DXP的plan；

流程：

1. DB内核提供一个metadata provider 类，这个类实现ORCA的接口IMDProvider；
2. 在调用ORCA时，把这个类传入做为其中一个参数；
3. ORCA内部在优化过程中通过这个类拿到meta的信息；
4. 这个类把meta组织成IMDCacheObject对象；

总结，数据库内核需要提供3类接口：

1. Query2DXL把parse tree转成DXL（CTranslatorQueryToDXL::TranslateSelectQueryToDXL）；
2. DXL2Plan把DXL转成可执行的Plan（CTranslatorDXLToPlStmt::GetPlannedStmtFromDXL）；
3. 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个阶段：

1. exploration;
2. implementation；
3. optimization；

Transformations

搜索空间的扩展是通过应用transformation规则：

1. 逻辑规则：(A, B) -> (B, A)
2. 物理规则：Join(A, B) -> HashJoin (A, B)
   规则可能会产生新的group加入到Memo中，或者新的group expr加入到相同的group中。
   每个规则都可以通过配置关闭。

Property Enforcement

Query有属性要求，具体一个Plan有固有的属性，这些属性通过形式化的property specifications来描述。

Property有3类：

1. logical：output column；
2. physical：sort order，distribution；
3. 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表示：

1. 类似oid，描述表，操作符；
2. 带有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个目标：

1. enforce；
2. 计算cost；

Optimization阶段向root group发射optimization的请求，请求描述prop：比如distribution和sort。

对于每个请求r，group expr会计算应该向子节点传递什么请求，输入是：来自父节点的r，和自身local的prop。对于同样的请求，orca会缓存防止重复计算。

1. group上有hash表：记录该group的在不同请求对应本group中最优expr；
2. 每个expr上有一个local hash：记录每个请求对应的子节点，用来最后从group树中抽取出plan

下图中：

1. 第一个请求是#1:{Singleton, <T1.a>}，结果集在master上汇总，并且结果集按照T1.a排序。
2. 左边的Groups Hash Tables是该Group下每个请求对应cost最低的GExpr编号；
3. Group中黑色矩形的Operator是enforce（distribution和sort）产生的节点；
4. Gather算子从所有segment server上收集tuple；
5. Gather Merge算子收集已经排好序的tuple，并且归并排序；
6. Redistrbute算子在segment server之间shuffle；

下图中：

1. 对group0的innerHashjoin[1,2]发送#1:{Singleton, <T1.a>}请求；
2. innerHashjoin，根据join条件t1.a=t2.b，向左右子group分贝发送Hashed(t1.a)和Hashed(t2.b）；
3. 子group收到hashed请求后：对于A，无需额外操作只需要scan；对于B，要进行rediistribte+scan；

如果prop不满足inittial请求，则要进行enforce过程；

orca实现了完善的prop enforce框架，支持每个operator定义：根据子节点的prop和自身的行为来决定是否已经满足prop，比如NLjoin的话，outer已经有序了，那么最终该nljoin就是在outer上有序的；

enforce过程产生的节点加入到正在被opt的节点同一个group中。

最优计划的输出过程：

1. 从Group Hash Table中找到#1对应的最优GExpr是8；
2. GExpr的local hash中记录了请求#1对应的子请求是#3；
3. 再次在Group Hash Table中找到#3对应的是GExpr为6；
4. GExpr6的local hash中记录了请求#3对应的子请求是#4；
5. 重复上述步骤就能把最终最优计划找到；

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个条件：

1. 找到了一个cost低于配置的cost-threshold；
2. time-out；
3. 已经遍历了所有的规则；

在优化复杂查询时，这个机制可以尽快的产生一个计划。

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倍。

1. 设置优化器time-out
   Q14在PG planner优化器中超过10000秒，而ORCA可以设置time-out，无需搜索全部计划空间。
2. 数据分partition；

ORCA和PG planner相比优势：

1. Join Ordering：有大量基于DP的join order优化算法，left-deep join tree，cardinality-based join order；
2. Correlated Subqueries：实现了子查询的Apply去关联化算法；
3. Partition Elimination：动态分区裁剪；
4. 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种并行：

1. inter-operator parallelism：pipeline
2. 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。

1. PDW每个opt请求都发送到MS-SQL进程的优化器（只管理元数据和统计，不维护用户数据）；
2. 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数据系统优化器的开发。