The Cascades Framework for Query Optimization

这篇paper是前一篇Volcano optimizer的后续,其涉及的概念和优化思路是一脉相承的,在阅读本篇之前,最好对Volcano optimizer有足够的了解,详见文章Volcano优化器框架。

从前文的介绍中可以看到,Volcano给出了一个具有扩展性和通用性的查询优化器生成框架的设计理念,和一个粗粒度的搜索算法,但整篇paper在工程实现方面基本没有描述。Cascades则是对Volcano做了很多改进,给出了工程实现相关的一些细节,比如用面向对象方式,提供了相关的数据结构定义,搜索流程等。

不过总的来说,这篇paper仍是非常抽象的,如果有同学希望在有工程实现上有所借鉴,可以看看<<EFFICIENCY IN THE COLUMBIA DATABASE QUERY OPTIMIZER >>这篇硕士论文,里面有更详尽的框架和代码级别设计。另外一些开源的Cascades优化器如Calcite、Orca等也很值得参考,其中Orca是严格的遵照了这篇paper来定义其内部数据结构的。

Paper

论文首先描述了对Volcano的内容作了哪些改进或者扩充:

  1. Rules(transformation rules/implementation rules)实现为对象。
  2. 用Group这个对象来描述logical等价类,也就是logical expression。
  3. 可以扩展针对schema/query 特性的rules
  4. Enforcer的添加也通过rules来描述
  5. Transformation rules通过pattern来匹配并判断是否可以apply
  6. Predicates成为了独立的operator,而不再是operator arguments,这样可以做predicate placement这样的等价变换
  7. 通过在apply transformation rule时,对下层group按需做exploration,等于在做等价变化的过程,按需增量的进行了下层算子的逻辑/物理变换,这样transformation/implementation rules的apply就交错了起来,而不是Volcano paper中使用的先做transformation再考虑implementation的二阶段模式。
  8. Search过程中引入guidance的概念,可以指导rules的应用策略。
  9. Rules可以有promise,表示其优先级。
  10. 将Search流程划分为多个阶段并抽象出task的概念,task是优化过程中的调度主体,不同task之间具有依赖关系形成DAG(有向无环图),这样可以做并行Search。

基本概念

Operator

operator不严格分为logical/physical,只是描述一种特定的操作,感觉上是用来描述每种expr所对应特性的信息载体。

Expr

一个抽象的Tree接口,表示一个plan中的特定子树片段,包含描述自身的operator + 描述输入节点的input group,基于expr需要做去重,避免在Memo中重复生成相同的(子)计划。

Group

逻辑等价类,其中包含具有相同逻辑输出属性的expr的集合。

Memo

以上各种结构的全局容器,通过search可能不断生成新的group/expr/operator,但都包含在这个Memo结构中,Memo负责消除重复结构,减小memory footprint。

Search guidance

针对rule,可以有特定的启发式guidance,控制rule是否做apply,或者是否需要多个rule组合apply。

Pattern

如果某个transformation rule是否可以apply,其所要求的plan tree的一个片段的“样式”。

例如,一个transformation rule是predicate pushdown,那它所要求的pattern就必须是

如果算子树上是join -> join,则不满足这个pattern而无法应用这个rule。

Substitution

在满足某个pattern后,就可以通过transformation生成新的expr tree,substitution用来描述转换后的expr。例如上图中的pattern,转换后的substitution就是

Rule

每个rule(logical/physical),有pattern(before) -> substitute(after)的映射,前后两个都是expr tree。

Transformation rule必须完整apply,形成tree level的变形。

Implementation rule只对current expr node应用,下层仍是input group。

Enforcer rule则不需要特定的pattern,只是按照物理属性要求添加特定物理操作。

搜索框架

优化过程被拆分为一些固定的步骤,每个步骤用task来描述,task之间有依赖和调用关系,当一个线程独立执行时,可以把所有task组织为一个stack,形成task间的递归调用,如果想做到并行执行,task间可以构成graph。

上图中涉及到了大部分Cascades中的基本概念,几个流程解释如下:

-> Optimize Group是整个递归的入口,带有Optimization Goal(cost limit + physical props)
   实际就是对group所包含的expr,依次调用Optimize Expr
   /* 注: 关于goal的描述参看上篇文章中Volcano optimizer的算法部分 */
   -> Optimize Expr
      -> apply transformation rule生成新expr,针对新expr,递归调用Optimize Expr
         apply transformation rule也可能生成新group,对新group,调用Explore Group
         -> Explore Group,就是在group内调用Explore Expr,生成该group内更多的expr
      -> apply implementation rule转换为物理operator,再基于该operator的cost/input requirement
         形成新的Optimization Goal,递归到children group,调用Optimize Group

从上述可以看到,整个过程中存在大量的递归,ExploreGroup和ExploreExpr负责生成后续可被优化的对象并放入Memo中,他们是transformation的产物。而具体的优化则是针对每个group内的每个expr,执行transformation或implementation。

看起来这和Volcano中算法描述的流程没有什么差别,只是把它和特定的结构对应了起来,但这里有几个要注意的点:

  1. 由于transformation rule是整个expr tree拓扑结构的转换,因此必须整体apply,implementation rule则可以一个node一个node的来。因此在apply transformation rule时,要求能转换所有符合pattern的expr!才能枚举尽可能的搜索空间,rule的应用才是完全的。
  2. Volcano会有单独阶段做全量的tranformation,生成所有等价group + expr,而通过对paper中一段比较晦涩描述的理解,Cascade是在apply rule前,要把pattern中匹配的subtree部分,作为目标sub pattern,对subgroup进行explore,生成所有可以满足这个sub pattern的等价expr!! 在explore完成后,才能开始对匹配的expr,做transform,这样等于做到了按需transform。
  3. 为了保证不重复,每个group要维护pattern memory,保证一个pattern不explore两次,每个expr要维护rule memory,保证每个rule不对其apply两次。每个新生成的Group/Expr,也要保证在Memo中没有重复的,因此需要对transform之后的expr tree,做去重判断。

总结

Cascade论文虽然给出了结构和流程定义,但其提出的机制变得更为灵活,也更加复杂,因此业界很多的实现方式都做了简化,比如TiDB / Orca,据我了解并没有把transformation和implementation交错起来,而是2-pass,先做transformation生成有效的expression,再做implement的优化。而且promise + search guidance也都是复杂的优化,需要比较完备的支持策略才能使用。

论文总体上只是给出了一个指导性的设计框架,丰富了一些理念,但仍然是过于抽象了,粒度很粗,后续通过对Orca论文的阅读,会有一个更加直观的理解。

上一篇:[New Portal]Windows Azure Storage (14) 使用Azure Blob的PutBlock方法,实现文件的分块、离线上传


下一篇:Adaptive and Big Data Scale Parallel Execution in Oracle