这篇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的内容作了哪些改进或者扩充：
- Rules(transformation rules/implementation rules)实现为对象。
- 用Group这个对象来描述logical等价类，也就是logical expression。
- 可以扩展针对schema/query 特性的rules
- Enforcer的添加也通过rules来描述
- Transformation rules通过pattern来匹配并判断是否可以apply
- Predicates成为了独立的operator，而不再是operator arguments，这样可以做predicate placement这样的等价变换
- 通过在apply transformation rule时，对下层group按需做exploration，等于在做等价变化的过程，按需增量的进行了下层算子的逻辑/物理变换，这样transformation/implementation rules的apply就交错了起来，而不是Volcano paper中使用的先做transformation再考虑implementation的二阶段模式。
- Search过程中引入guidance的概念，可以指导rules的应用策略。
- Rules可以有promise，表示其优先级。
- 将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中算法描述的流程没有什么差别，只是把它和特定的结构对应了起来，但这里有几个要注意的点：
- 由于transformation rule是整个expr tree拓扑结构的转换，因此必须整体apply，implementation rule则可以一个node一个node的来。因此在apply transformation rule时，要求能转换所有符合pattern的expr！才能枚举尽可能的搜索空间，rule的应用才是完全的。
- Volcano会有单独阶段做全量的tranformation，生成所有等价group + expr，而通过对paper中一段比较晦涩描述的理解，Cascade是在apply rule前，要把pattern中匹配的subtree部分，作为目标sub pattern，对subgroup进行explore，生成所有可以满足这个sub pattern的等价expr!! 在explore完成后，才能开始对匹配的expr，做transform，这样等于做到了按需transform。
- 为了保证不重复，每个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论文的阅读，会有一个更加直观的理解。
