数据库查询优化器的搜索技术，基本上分为了基于动态规划的bottom-up search(详见文章System-R论文解读)和基于Cascades/Volcano的top-down search两个流派，这篇文章我们来看一下Cascades的前身也就是Volcano优化器框架的paper。
提到Volcano，可能大家想到的更多是基于Iterator tree的火山模型执行框架，但其实Volcano 是一个包含了优化框架和执行框架的research project。而Volcano optimizer framework是其中最为核心的一部分，其目标是构建具有完全扩展性的优化器生成器，也就是说，它并不是一个具体的优化器实现，而是一个如何构建优化器的框架，只要遵循其方法论，插入符合自身需求的组件，就可以实现一个优化器。
业界很多数据库系统采用了这种Volcano/Cascades的优化器，例如Spark / Impala / Greemplum / SQL Server ...
基础知识
对于寻求最优解这个问题，最优化理论和局部最优解以及全局最优解的概念在介绍System-R paper的文章中已经提及，不熟悉这个概念的同学可以参看这里。
但Volcano与System-R的Search engine有所不同的是，它的搜索路径是自顶向下的，也就是先从关系算子树的顶层开始，以深度优先的方式来向下遍历，遍历过程中进行剪枝，具体逻辑会在后续详述。
Paper
这篇paper总体来说比较抽象，因为主要讲的是一个方法论，比如说，它说明了想要构建一个具有扩展性的查询优化器，需要关注的都有哪些，例如设计原则/设计输入，同时也讲到了optimizer中可能包含的组件，以及最为核心的Search engine等，文中的概念对于后续理解Cascades框架是非常有帮助的，因为基本概念是一样的，且Search算法也较为接近，我们详细看下：
设计目标
总体来说，其设计目标生成具有通用性以及扩展性的优化器，优化所使用的data model、cost model等，完全不做限制。
- 作为一个独立模块存在
- 可扩展性: 逻辑operator 、物理algorithm、算子输出的property、基础cost model等。
- 可应用启发式的等价规则 + data model自身蕴含的语义，来指导对plan space的搜索过程。
设计框架
最高层的抽象就如上图所示，只要给定Model Specification，就可以生成一个Optimizer来执行优化流程，而在Model Specification中，就是要指定data model, operator, property, rules等等。
输入到优化器的查询（上图最左侧），以一种代数运算树的形态来描述（对应到我们最常见的关系代数，输入可以认为是AST）。
其中每种代数运算，都要定义三元组： 逻辑operator + 等价变换规则 + 物理实现算法
逻辑operator 是代数运算的描述，这样足够抽象，不同data model的运算都可以表示，operator基于data set做运算，输出也是data set，传递到下一个operator，比如下图中，GET就是一个逻辑操作。
Volcano optimizer把operator分离成logical和physical两个概念，这样更加灵活，可以各自扩展，优化器的工作，就是把logical operator tree转换为physical operator tree，形成最终的物理执行计划。
等价变换规则使用transformation rules来描述，用于在logical operator间转换，将logical operator tree转换为完全等价的形态。（以关系代数为例，join的交换律结合律或者分配律，都属于这个范畴)
物理实现算法使用implementation rules来描述，表示每个logical operator执行的physical algorithm（以关系代数为例，逻辑上的join运算，可以转换为hash join / nested loop join / sort merge join ...），选定了物理实现算法后，就完成了logical operator到physical operator的转换，如下图，INDEX_SCAN就是一种具体的GET实现。
框架中各种rules是相互独立的，各自可扩展，结合起来被search engine使用。
Search Engine
Search Engine是本篇paper的核心，要了解算法原理，需要先进一步熟悉下logical operator和physical operator的细节，在paper中，对两种operator分别定义了如下含义：
Logical Operator
- Operator set，也就是可以描述在目标data model上可以执行的代数运算合。
- Transformation rules + Condition，对每条等价变换规则，在满足condition时才可以应用。
- Logical properties : 逻辑属性，用来描述代数运算的输出所具有的一些特征，这些特征与运算的具体执行方式无关，是逻辑的，例如输出的行数，结果集的schema等。
Physical Operator
- Algorithm + Enforcer set，即可应用的物理实现算法 + 可添加的Enforcer集合。
- Implementation rules + Condition，满足Condition的前提下，可以尝试该物理算法。
- Cost model + Cost formula，基于cost选择最优的物理算法。
- Physical property，与logical property对应，物理属性是选择了特定的算法实现后，输出的数据所具有的物理上的特性，例如数据是否有序、是否具有唯一性，数据在多机上的分布情况等，不同的物理算法，会决定执行该operator产生的物理属性，例如sort merge join会在join key上产生有序属性。
- Applicability function : 决定一个物理算法，其输出是否可以满足要求父算子对自身的physical property要求，且决定它对自身的输入具有什么样的physical property要求。
- Enforcer是search engine中一个重要的概念，它用来强制产生某种物理属性。例如上层是join算子，在枚举时会考虑使用sort merge join的物理执行方式(Implementation），但当递归到下层时，子节点可以选择table scan（无序输出），或者index scan（目标序输出），当选择table scan时，由于输出不满足父算子对自身输出的物理属性要求，就可以通过Order Enforcer来产生目标输出，Enforcer表示了排序这个操作，同时也包含了排序操作会产生的代价。
Equivalent Class
在上一篇文章中，我们提到了等价类的概念。但请不要与Volcano中的等价类混淆，在Volcano中，等价类具有更加丰富的语义，它区分为逻辑等价类与物理等价类。
具有相同逻辑输出属性的operator集合，构成一个逻辑等价类，也就是说无论怎样进行transform，只要逻辑属性没有变化，就仍然属于一个等价类内部。如上图所示，在AB这个虚框中，无论是A join B还是B join A，无论join之后的数据是否在A.X上是否有序，它们都属于一个逻辑等价类。这个逻辑等价类的概念，是用来对等价变换划定边界的，在top-down的搜索中，不同的等价类节点构成了不同的搜索路径，在search算法中，一个逻辑等价类叫做一个logical expression。
具有相同物理输出属性的operator集合，构成一个物理等价类，如上图所示，每个实框都是一个物理等价类，而sort<A.X>这样的操作，就是由Enforcer来完成的，它为一个物理operator增加新的物理属性。物理等价类的作用和System-R中的等价类一致，构成了一个局部子问题，并可以通过选择局部最优解来在搜索中剪枝。
Search Algorithm
搜索算法是这篇paper的核心，我们可以先看下伪代码，然后通过一个CMU 15-721课程中的示例来说明。
/* LogExpr，即当前所面对的Logical Expression，对应一个Logical等价类 PhysProp，对其所应具有的物理输出属性的要求 CostLimit，计划中剩余的cost配额 Return 在当前LogExpr内，满足该PhysProp的代价最低的物理operator */ FindBestPlan (LogExpr, PhysProp, CostLimit) returns Plan,Cost /* step 1 使用(logical expression + property)作为key,在hash lookup table中查找是否已有最优计划 如果已有： -> 满足cost limit，返回给上层 -> 不满足cost limit，返回查找失败，表示这个子节点无法选出满足要求的局部最优解 */ 1. If the pair LogExpr and PhysProp is in the look-up table if its state is “in progress” , then ignore and return else if the cost in the look-up table < CostLimit , then return Plan and Cost else , return failure /* step 2 - 3 hash lookup table没找到，则做优化，允许3种move -> 在transformation rules中，尝试apply，转换为新的logical expression， 并基于新的logical expression，在本层递归调用FindBestPlan -> 在implementation rules中，找满足prop要求的algorithm，根据cost formula + cardinality 计算cost，并使用applicability function确定input operator的prop要求， 递归到下层调用FindBestPlan，累计其返回值得到本层总的代价，过程中可以用Cost Limit做pruning -> 找可以满足prop要求的enforcer，计算cost，根据enforcer改变对下层logic expr的prop要求， 递归到下层调用FindBestPlan计算cost */ 2. Create the set of possible "moves" from: - applicable transformations - algorithms that give the required PhysProp - enforcers for required PhysProp 3. Order the set of moves by promise; and for the most promising moves: if the move uses a transformation Apply the transformation creating NewLogExpr Call FindBestPlan (NewLogExpr, PhysProp, CostLimit) else if the move uses an algorithm For each input i while TotalCost < CostLimit Determine required physical properties PP for i Cost = FindBestPlan (i, PP, CostLimit − cost of algorithm) else /* move uses an enforcer */ Modify PhysProp for enforced property Call FindBestPlan for LogExpr with new PhysProp (cost less enforcing) /* step 5 - 6 将获取到的LogExpr和局部最优plan记录在hash lookup table中，后续递归回来可能再访问到相同的logical expression, 直接获取局部最优解即可 */ 5. If LogExpr is not in the look-up table, then insert LogExpr into the look-up table 6. Insert PhysProp and best plan found into look-up table /* step 7 在本次递归中，返回局部最优解和该最优解的cost */ 7. Return best Plan and Cost
示例： 三表join，且要求输出在ARTIST.ID表上有序
Step1. 枚举各种可能的logical expressions:
Step2. 从top logical expression开始，深度优先向下递归，考虑可能的physical implementation rule，算子的不同物理实现会对下层的logical expression产生不同的physical property要求，在下图中，SM_JOIN会对两个输入各自在join key上产生order属性，其输出可以产生ARTIST.ID的有序属性。
另一种物理算法HASH_JOIN：
则由于无法产生有序输出，无法直接作为top node的下层节点，这时就需要enforcer来发挥作用：
通过QUICKSORT这个enforcer来满足有序的物理属性要求，此时HASH_JOIN就可以使用了，那么SM_JOIN和HASH_JOIN + QUICKSORT就构成了一个物理等价类，要基于子树的cost，从中来选择优胜者。
当各种logical expression都递归处理后，整个search过程就结束了。
Memorization
以上图中的ARTIST这个logical expression为例，它会在递归过程中被多次处理到，这就是hash lookup table发挥作用的时候，在lookup table中把[ARTIST + 某种物理属性]组合的最优解记下来，后续再碰到这个[logical expression+对应物理属性]时，就可以直接获取已记录的局部最优解。
Top-down Vs. Bottom-up
两种search engine孰优孰略已经被讨论了很久而没有定论，实际上两者覆盖的范畴并不完全相同。
Top-down win：
- Volcano的算法中，包含了logical transformation的过程，因此可以去做等价变化，这不仅限于join ordering，各种类型的query transformation（例如group by placement, filter pushdown...）理论上都可以在top-down的search过程中完成，但bottom-up主要还是针对join ordering，描述等价变换比较困难。
- Top-down的search方法，有一个最大的优点，就是可以做branch-and-bound pruning，由于每递归到一个logical expression，总是带有目标的属性的，因此可以只针对满足这个属性的目标来枚举，而bottom-up枚举时，父节点的情况并不清楚，因此当前节点需要枚举各种可能的物理输出属性，没法只针对一个"branch"，此外由于向下有cost limit这个参数，在深度优先的递归时，一但cost limit无法满足要求就可以立即终止，形成了bound pruning。
Bottom-up win：
- 由于覆盖的search space更大，top-down搜索花费的时间和空间overhead更大，这也是为什么更多大数据生态的系统或者数仓系统会使用这种优化器，由于查询更复杂且涉及的数据量更大，它牺牲了较多的优化时间来换取更优的查询计划。在像SQL Server这样要处理事务型workload的系统中，优化分为了多个阶段，这样可以基于走一些fast path或者基于某些规则提前结束搜索。
