The Volcano Optimizer Generator -- Extensibility and Efficient Search

The Volcano Optimizer Generator: Extensibility and Efficient Search

0x00 引言

Volcano风格的优化器以及后面的Cascades是数据库优化器比较有名的设计。现在不少的数据库以及一些相关的框架有使用。Volcano是一种Unified Search的优化器，统一逻辑查询到逻辑查询以及逻辑查询到物理查询的操作。例如IBM的STARBURST优化器的设计是一种Stratified Search的优化器，这类优化器会先有一个查询重写的阶段，将逻辑查询重写之后在将逻辑查询转化为物理查询。Volcano容易添加新的操作和等价规则，使用基于branch-and-bound搜索的Top-down的方法。Volcano遵循下面的一些设计原则，

查询处理都是基于关系代数；
使用规则和模式来处理等价转换；
不使用中间表示状态，直接讲查询转换为计划，没有中间表示状态；
使用编译的方式而不是解释的方式(这里应该指的是优化器，而不是指SQL语句，优化器没有涉及到SQL语句)；
使用动态规划的搜索方式；

volcano-paradigm

0x01 基本设计

用户查询在Volcano中的优化从代数表达式(树)开始(优化器的输入)，这个代数表达式(树)由用户接口的输入(一般就是SQL语言)被Parser转化而来，Parser和优化器没有什么关系。这个代数表达式(树)有一系列的逻辑操作组成(logical operators )。一个Operator会有0个或者更加多的输入，输入的数量是没有限制的。优化器的输出就是查询计划。另外就是一组的算法，表示了在数据存储上面的一些操作。Volcano的一些设计，

优化操作就是将逻辑的代数表达式转换为优化的等价的物理代数表达式，在优化的过程中，Operator的顺序是可能会被改变的，具体实现的算法会从算法的集合中选取。为了保证转换的等价性，这个使用了转换规则的概念，比如有些操作满足交换律和结合律。这些规矩可能会附加条件(condition code)，多个的逻辑Operator可能会被映射到一个物理的Operator。
```
Logical → Logical:
JOIN(A,B) to JOIN(B,A)
Logical → Physical: 
JOIN(A,B) to HASH_JOIN(A,B)
```

表达式的结果被称为Properties。逻辑的Properties包括了Schema, Expected Size等之类的，物理Properties包含了排序的顺序，分区等的信息，取决于算法，

 When optimizing a many-sorted algebra, the logical properties also include the type (or sort) of an intermediate result, which can be inspected by a rule's condition code to ensure that rules are only applied to expressions of the correct type. Logical properties are attached to equivalence classes - sets of equivalent logical expressions and plans - whereas physical properties are attached to specific plans and algorithm choices.

在每一个中间结果中，物理Properties会由一个Physical Property Vector表示。这个有优化器的实现者决定，会被视为一个抽象的数据类型被Volcano优化生成器和搜索引擎使用。
一些物理代数上面的Operator没有对应的逻辑代数对应，比如解压缩等。这些Operator的存在是为了满足其输出满足一定的物理Properties，以便于后面的查询处理操作使用。这样的Operato被称之为Enforcers。
每一个优化从一个逻辑表达式和一个Physical Property Vector着手，通过规则匹配(规则可能带有Condition Code)，调用Applicability函数决定是否有算法or Enforcer可以满足要求。Applicability用于决定算法输入必须满足的Physical Property Vector，比如Merge Join是要求排序的。
在优化器决定使用一个算法和Enforcer的时候，它调用对应的cost函数去估算使用其的开销。这样一般就是为了选择最优的方案。

总结一下实现这个优化器需要提供下面的一些东西，

(1) a set of logical operators, 
(2) algebraic transformation rules, possibly with condition code, 
(3) a set of algorithms and enforcers, 
(4) implementation rules, possibly with condition code, 
(5) an ADT "cost" with functions for basic arithmetic and comparison, 
(6) an ADT "logical properties," 
(7) an ADT "physical property vector" including comparisons functions (equality and cover), 
(8) an applicability function for each algorithm and enforcer, 
(9) a cost function for each algorithm and enforcer, 
(10) a property function for each operator, algorithm, and enf

0x02 搜索引擎

在查找将逻辑代数转变为最终的执行方案时，可以使用的方案的数量是很大的。Volcano使用的是在优化器中常用的动态规范的方法，加上记忆化等一些优化的方式。下面是一个算法实现的伪代码，主要就是分为两个部分，第一个就是在算法前面和最后面的if语句，这里主要就是记忆化的优化，如果之前同样的逻辑表达式 + PhysProp已经被计算了，那就可以直接使用之前的结果。Cost限制就是在搜索树上面的一个剪枝优化，Volcan在这里使用了 branch-and-bound(分支界限)的方法。接下来的循环在3中“moves”操作的集合中查找：1. 一个表达式被一饿转化规则转化为另外的表达式，2. 这个表达式一个算法加上其物理Properties要求来处理，3. Enforcer的使用可以拓展可以使用的算法，比如由于某个算法需要排序，而当前的物理Properties不能满足排序的要求，通过Enforcer排序来使得其可以使用这个要求排序的算法。在这3中情况中，都可以产生递归的调用。

FindBestPlan (LogExpr, PhysProp, Limit)
  // 记忆化优化
  if the pair LogExpr and PhysProp is in the look-up table
    if the cost in the look-up table < Limit return Plan and Cost
  else
    return failure
  /* else: optimization required */
  create the set of possible "moves" from
    applicable transformations
    algorithms that give the required PhysProp enforcers for required PhysProp
    order the set of moves by promise 
  for the most promising moves
    if the move uses a transformation
      // 转化为新的表达式，递归调用
      apply the transformation creating NewLogExpr 
      call FindBestPlan (NewLogExpr, PhysProp, Limit)
    else if the move uses an algorithm 
      TotalCost := cost of the algorithm
      for each input I while TotalCost <= Limit
        determine required physical properties PP for I 
        Cost = FindBestPlan (I, PP, Limit - TotalCost) 
        add Cost to TotalCost
    else/* move uses an enforcer */
      TotalCost := cost of the enforcer
      // 通过enforcer来改变PhysProp，拓展可以使用的算法
      modify PhysProp for enforced property
      call FindBestPlan for LogExpr with new PhysProp
  /* maintain the look-up table of explored facts */ 
  if LogExpr is not in the look-up table
    insert LogExpr into the look-up table
  insert PhysProp and best plan found into look-up table 
  return best Plan and Cost

0x03 和EXODUS的区别

EXODUS是同一个作者在Volcano的一个优化器设计的版本，Volcano也是在EXODUS的基础之上优化而来。这里总结了一些Volvano在EXODUS上面的做的一些优化：前者(EXODUS)没有区分逻辑表达式和物理表达式，也没有物理Properties的概念，没有一个通用的Cost函数等等。

0x04 The Cascades Framework for Query Optimization

Cascades是Volcano的一个优化设计的版本。在Cascades中，基于面向对象的设计。[3]这篇Paper是一个很抽象的描述，没有什么有意思的图。[4]这篇Thesis是一个Cascases风格的优化器的一个实现，更加具体一些。

在Cascades中优化算法会被分为多个部分，这个就被称为Tasks。Task可以看作是搜索的一个动作，优化的工程中会有若干的Tasks等待运行，而执行一个Task可能导致等待执行的任务增多。一个Task由于优化一组(Group)or一个表达式，会针对给出的Cost Limit和(要求必须有的or不能有的)物理Properties给出一个执行计划or一个失败，或者是无法给出满足条件的计划。Group是Cascades中一个基本的概念，表示等效的逻辑和物理表达式的集合。在前面的Volcano中，优化的过程可以被分为两个阶段，一个是使用转化规则将给定的查询转化为所有可能的逻辑表达式，第二步是优化得到实际的执行计划。Volcano这样的做的缺点就是可以导致很多无用的搜索，因而Cascades中放弃这样的做法。Cascases中一个组只用在需要的时候才会应用转换规则，

.. A group is explored using transformation rules only on demand, and it is explored only to create all members of the group that match a given pattern. Thus, exploring a group or an expression (the distinction between these two mirrors the distinction between optimizing a group or an expression) means deriving all logical expressions that match a given pattern. The pattern, which is part of the task definition, is a subtree of the rule’s antecedent or ”before”-pattern.

Cascades中同样使用记忆化的策略来避免重复的工作。另外，Cascades还引入了Guidance的概念来减少搜索的空间，这个Guidance可以有优化器自己的算法来实现，也可以是优化器实现者来实现。

cascades-tasks

参考

The Volcano Optimizer Generator: Extensibility and Efficient Search, ICDE’1993.
https://15721.courses.cs.cmu.edu/spring2017，CMU 15-721 :: Advanced Database Systems 课件.
The Cascades Framework for Query Optimization, 1995.
Yongwen Xu, Efficiency in Columbia Database Query Optimizer, M.S. Thesis, Portland State University, 1998.