Orca: A Modular Query Optimizer Architecture for Big Data

这个系统是用来替换GP/Pivotal原来的Planner的,强调如何实现一个模块化的Query Optimizer,关注于包括:模块化,扩展性,利用多核,可验证性(或者说可调试性),以及性能几个方面。

整个Orc内部结构以及位于系统中的位置如下:

可以看到整个过程都是非常模块化的,把所有和外部系统都规定好了接口和数据交换格式。

orca-arch.png

在上面Orca Arch图里面,有几个关键的概念:

在开始进行搜索优化之前,一个逻辑计划的表示其实分成了好几个部分(可以认为是fragment)。每个部分是个子树,我们叫做group,里面每个可能的实现叫做group expr(group表达式)。考虑到转换和重写,所以一个group里面可能会存在多个group expressions.

经典的优化器就是,到了这一步,我们就对group expression进行cost计算,然后选择最优解。我理解Orca的不同地方在于,如果在这些group expr上施加某些限制(enforcement)的话,虽然sub expr cost更高了,但是可能整体的cost会更低。一个例子就是,如果对sub expr加入某个hash parittion的话,虽然多了一次shuffle, 但是在join的时候效率可能会更高。

orca-init-group.png

整个Optimization过程分为下面几个部分,

关于测试方面,我觉得Orca做的也很不错,一个是正确性验证,一个是性能回归。

正确性验证的话,考虑到Orca可以做到相对比较独立,所以完全可以把Query + MD + Plan放到一个文件里面,这对于调试来说就方便了不少。

性能回归的话,考虑到这个memo空间会比较大,所以Orca会进行plan采样(不知道是对root plan采样还是也可以对sub plan采样),拿这些采样去线上跑观察实际运行时间,然后验证自己的cost是否可信。具体来说,如果两个plan p1, p2, 如果cost(p1) < cost(p2), 但是运行时间p2远小于p1的话,那么就值得分析一下具体原因了。