开发者社区> 游客ebdjhbkyk4vb4> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

《Orca: A Modular Query Optimizer Architecture for Big Data》

简介: Orca: A Modular Query Optimizer Architecture for Big Data
+关注继续查看

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对象;image.png

总结,数据库内核需要提供3类接口:

  1. Query2DXL把parse tree转成DXL(CTranslatorQueryToDXL::TranslateSelectQueryToDXL);
  2. DXL2Plan把DXL转成可执行的Plan(CTranslatorDXLToPlStmt::GetPlannedStmtFromDXL);
  3. MD provider把metadata转成DXL(CMDProviderRelcache::GetMDObj);

ORCA内部组件

image.png

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;image.png

Logical Expr

DXL query传入ORCA,解析成内存中的logical exprssion,存入Memo中,做为Memo的初始状态。

这个SQL对应3个group,group 0称为root group。

Inner Join[1, 2]自节点是group1和group2。

image.png

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共享一份统计。

image.png

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;image.png

下图中:

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

image.png

最优计划的输出过程:

  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之间维护前后依赖关系,没有依赖关系可以并行;

image.png

因为是top-down的进行优化,父节点的job会先进入queue中,会触发子节点的优化(后序遍历递归);

子节点job没有执行完之前,不会调度执行父节点的job;

状态机

每个job通过状态机描述状态,search engine推送消息状态机的推动状态转变。每种job对应一个状态的定义。

image.png

状态转换如下:

image.png

状态机和Group的关系是多对一的关系。

如何调度GroupExpressions?

一个group上会有不同阶段的状态机,同一个group在多个(3阶段)状态机中会被调度执行:每个阶段的group状态机都保留了exp列表的迭代器;

image.png

各个goup上状态机的关系

image.png

5. METADATA EXCHANGE

Orca能和不同的外部系统沟通。在优化一条SQL期间所有meta缓存在内存中,以便在同一个SQL优化过程中,对同一个元数据多次访问。当优化执行结束,缓存清空。

image.png

此外,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即可。

image.png

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和真实执行的时间,这两组数据之间计算出相关性分数(重要计划,距离等因素)。

image.png

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;image.png

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数据系统优化器的开发。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Firefox开发者工具里的CSS Flexbox Inspector
Firefox开发者工具里的CSS Flexbox Inspector
41 0
monogdb操作system.*权限
__system root system.*
632 0
SpringBoot_03_依赖本地jar
一、方法一 1、说明 用Maven打到本地仓库,然后直接引入 2、参考资料 Springboot 打Jar包,Maven完美解决本地Jar包自动打入Springboot Jar包中 3、执行maven打包命令进行打包 mvn install:install-file -Dfile=alipay-sdk-java20180309170622.
1000 0
Conway's Law – A Theoretical Basis for the Microservice Architecture
Microservices architecture is a new concept that has become very popular and has become a hot topic of research recently.
3641 0
SOS does not support the current target architecture解决方法
客户提交一个dump文件,WinDbg加载时出现大量WARNING,加载对应版本的SOS后执行相应命令提示”SOS does not support the current target architecture”。
1627 0
Generic P2P Architecture, Tutorial and Example - CodeProject
Generic P2P Architecture, Tutorial and Example By dzzxyz | 15 Mar 2004 Generic P2P architecture, tutorial and example that covers basic P2P strategy.
1295 0
84
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载