《The Volcano Optimizer Generator: Extensibility and Efficient Search》

总结

这篇论文还是一篇基本性的描述， 主要介绍优化器的很多理念，如果已经看过一些基本的优化器介绍， 这篇论文可以skip。

Abstract

数据库除了需要满足新功能还要高性能， volcano 提供高效和易扩展的工具来满足查询请求。 优化器生成器将data model， logic algebra， physical algebra 和优化规则 转化为优化器源码。 和前一代优化器生成器exodus 相比， 查询引擎更易扩展和更powerful。 他提供对non-trivial cost model 和物理属性例如sort order的高效支持。 与此同时， 高效结合了动态编程。 和其他rule based 优化系统相比， 它提供独立完整的data model和更自然的扩展性

介绍

不能因为扩展性而失去性能， 因为， 现在数据量的增速远超过数据库能力的增速， 另外一个原因，现在在跑的科学计算基于文件系统已经在运行了， 否则没有动力进行迁移。 优化和并行 是主要提供性能优势的方式。
有几个要求:

1. optimizer generator 必须是一个独立工具, 既可以在volcano 中使用, 又可以在其他项目中使用
2. 新系统必须更高效, 优化时间必须段, 并且内存消耗上也必须足够小
3. 易扩展, 可以高效添加类似sort order 和压缩status 的物理属性
4. 允许使用heuristics 和data model semantics 来指导搜索和对一些查询空间进行裁剪
5. 支持灵活的cost model， 允许为非完整的查询生成动态plan

整体视图

将data model 描述 生成为编译器代码, 和其他数据库模块 如查询引擎, 搜索引擎编译和链接在一起,生成数据库.

设计原则

5个基本原则

1. 关系系统的查询是基于关系代数算子， 通過代數算子， 代數等價規則和合适的实现算法。可以使用关系代数规则,比如各种等价变化, 如交换律,结合律. 算子消费一个或多个types 并生成出下一个operator的输入。 执行引擎基于算子， 算法消费和生成bulk types。 算子集和算法集是不同的。 选择最优的算法是优化器最重要的工作之一。 优化器生成器使用2种关系代数， 一种是逻辑，一种是物理。 通过逻辑关系代数的transformation和 基于代价的关系代数到算法的关系映射, 生成的优化器可以映射逻辑代数到物理逻辑代数算子(包含算法)的expression。
2. 通过规则来提高优化器的扩展性和模块化. rule 用一种 精简和模块化的方式来指定pattern 的knowledge 和代数原则的knowledge（比如等价转化用patterns和rules 来表达）。 专注在独立的rule上可以提高模块化， rule 可以独立从一个rule 转化为另外一个rule， 并且和search engine combine 在一起。
3. volcano generator的输入的代数等价是优化器做的各种选择（映射一个query到一个优化的等价plan），search engine 用一个合适的方式来使用这些关系代数等价转化公式， 对于那些优化器实现者来说， 这些优化器想做一些特殊控制，比如确定某些搜索或做剪枝搜索等， 有一些优化工具来做这些事情。
4. 为了获得更好的性能， 选择了对rule 进行编译来执行，没有选择解释执行，类似EXODUS 优化器生成器， 但为了提高扩展性， 使用最强参数，强参数使用解释性 pointless， 提高rule sets的扩展性， 参数化rule和他们的condition, 例如， 控制search的全面性和观察和exploit rule 应用的重复顺序。
5. 基于动态编程

优化器生成器的输入和优化操作

优化器生成器的目标就是最小化 要实现的data model的假设，操作和功能的 data modle。 这章介绍优化器的组件。优化器的输入是query， 输出是优化的执行plan。

1. parser 解析query 后，生成logic 算子组成的关系表达式（逻辑算子是在生成优化器时 model specification 定义和编译进去的， 算子可以0个或多个input）， 这个作为优化器的输入，优化器输出是一个执行plan， 这个plan 是带有关系代数算法。 算法集， capability和代价 代表着data format 和物理存储结构。
2. 优化过程是 将一个逻辑关系代数表达式 映射为一个优化的，等价的，物理关系代数表达式。 对算子进行reorder， 对实现算法进行挑选。 transformation rule 包含等价转化， 交换律， 结合律。 用implementation rule 来确定映射算子到算法。 rule language 必须支持复杂的mapping， 可以join后带projection 用一个rule来表示， 可以一个rule 来表达映射多个逻辑operator到一个物理operator。 当pattern 匹配到算子和算法后，还需要确定所有rule的condition。 在一个rule pattern成功匹配后， 可以attache condition code 到rule上。
3. 用属性来描述expression的result。 逻辑属性来自逻辑关系代数表达式， 包括schema， expected size等。 物理属性来自算法， 如sort order， parition等。 当优化一个many-sorted 代数， 逻辑属性包含中间结果的type， 可以用一个rule的condition来检查type 来保证正确的type的rule可以用到这个expression上。逻辑属性可以attach到等价类， 一组等价的逻辑express 和plan， 而物理属性只能attach 一个plan和算法。
4. 物理属性集合对每个中间结果summarized到 物理属性vector， 由优化器的实现者来定义并被volcano 优化器生成器和search engine当作一个抽象data type。 也就是物理属性的types和semantics 可以由优化器实现者来设计。
5. 有一些物理代数不存在任何逻辑代数中， 比如sorting和decompression。 这种算子不执行逻辑数据处理但对他们的输出附加物理属性， 这些属性用于随后的query 处理算法。 我们称这种算子为enforcer， 类似starburst的glue。 enforcer 可以ensure 2个属性，甚至enforce 一个属性但destory 另外一个。 有2中enforcer sort/hash, 在并行和分布式系统中，location/paritioning 会被enforce 网络或并行算子如exchange 算子中。 在面向对象系统中， 对复杂对象进行assembledness， 使用assembly 算子作为enforcer。
6. 每一个优化目标是一个pair（逻辑express 和物理属性vector）。 为了判断是否可以在这个logic expression的root node上执行一个算法或一个enforcer， 优化器寻找合适的implementaion rule， 执行rule上关联的condition， 最后调用 applicability function， applicability function 来决定这个算法或enforce是否可以deliver 这个logic expression带物理属性， 这个物理属性满足物理属性vector， applicability function同样决定了算法输入必须满足的物理属性vector。 举例来说， 当优化一个join expression时， 它的结果应该sorted， hybrid hash join 不满足这个要求， 但merge-join 就可以满足， 因此当输入不排序时，一个enforce就会传过去， 输入排好序后， hybrid hash join 也可以。算法不能过度限制。
7. 在优化器决定用一个算法或enforcer后， 他调用算法的cost function来估算他的代价。 cost 是优化器生成器的抽象代价类型。 优化器实现者可以选择cost to be a number（以耗时为标准）， 以record（以cpu time/io count）或其他类型。 代价的算术计算和比较通过关联抽象类型cost的函数来执行。
8. 对于每个逻辑和物理的代数表达式， 逻辑和物理属性来自使用property functions。 每个逻辑算子， 算法和enforcer 都有一个property function。在优化前， 由关联逻辑算子的property function 来决定逻辑属性基于逻辑表达式。 例如， 决定中间结果的schema 可以独立于创建任意一个等价的代数表达式。 逻辑property function 同样封装selectivity 评估。相反， 像sort order 这样的物理属性仅仅在执行计划选择后才能决定。 因为一致性检查之一， 优化器确定 一个选择的plan的物理属性满足优化目标的物理属性vector。

search engine

优化器就是从相同的的执行计划中选自一个代价最小的执行plan， search engine和他的算法就是最核心的组件。 volocan 优化器生成器提供一个现成的sarch engine， search engine 可以自动link 匹配的pattern 和由data model 描述生成的rule application code。
在exodus 优化器中浪费了很多search effor， volcano 优化器生成器使用动态编程， 并且目标驱动和需求驱动。
动态编程在system r 和starburst 代价优化器等数据库中已经被使用过了。volcation 优化器生成器的search strategy 扩展了动态编程， 从关系join 优化 到通用代数查询和优化器请求， 自上而下， 目标驱动 的代数控制策略来处理 可能的plan 超过预计算的实际限制。那些部分query被认为是更大的subquery的部分， 这些部分query的等价expression和plan的动态编程。不是所有的等价expression和plan， 这些expression和plan 看起来可行在他们的sort order上。 因此subqueries的exploration和优化， 和他们的可选plan是非常直接和目标驱动的。exods/system r/starburst 关系系统都使用forward chaining， volcano 使用backward chaining， 因为，他仅仅探索那些真正在一个更大expression使用的subqueries和plan。 我们称这种算法为 directed dynamic programming. volocana 优化器的动态编程通过获得部分优化结果的大集合， 并且在后续优化决定中使用之前的优化结果。当前，当每个查询开始优化时，部分优化结果的集合会被重新初始化。 也就是 早期的部分优化结果只有在优化单查询时被使用。

代数转换系统总是包含相同表达式的各种可能。 为了减少无效的优化， 通过探测来自相同逻辑表达式和plan的多余优化， 捕获expression 和plan 在表达式和他的等价类目中的hash table。 一个等价类含2个集合， 一个等价逻辑表达式， 一个等价物理表达式（plan）。 逻辑代数表达式 搜索空间的高效和完整探索使用逻辑代数表达式， 满足物理属性要求的一个合适input plan的一个快速选择
使用plan。 一个等价类的已经优化的物理属性可以被combination ， 比如没有sorted， 在a上sorted， 在b上sort， 会保留最好的plan。

FindBestPlan(LogExpr, PhysProp, Limit) {
    if  find LogExpr/PhyProp in HashTable {
        if  cost < limit {
            return plan/cost
        }else {
            return failure
        }
    }else  {
        //优化过程
        创建3种 可能的move {
            applicable transformations
            physprop 要求的算法
            physprop 要求的enforcer， 有时可以做exclude 物理属性vector
        }

        根据promise 对move 进行排序
        for 对于最可能promising的moves { //使用所有的move或根据规则选择部分
            if 如果这个move 使用transformation {
                使用这个transformation， 生成新的NewLogExpr；// 这个地方会标记已经使用的transform，防止重复transform
                调用FindBestPlan(NewLogExpr, PhysProp, Limit)
            }else if (move 使用算法) {
                //某个算法可以deliver 这个逻辑表达带对应的物理属性
                Totalcost ：= 算法的cost
                for each input I while Totalcost < Limit {
                    生成physical properties PP for I
                    cost = FindBestPlan(I, PP, Limit - TotalCost)
                    TotalCost += cost
                }
            }else { // enforcer
                TotalCost := cost of enforcer
                根据enforcer property 调整PhysPop
                调用 FindBestPlan(LogExpr, NewPhysProp, Limit)
            }
        }

        if LogExpr 不在look up table
            insert LogExpr  Look-up-table
        
        insert PhyProp/BestPlan into Look-up-table
        return BestPlan and cost



    }
}

starburst 使用2阶段，增加了query rewrite 阶段。 而volcano 留给了优化器实现者。
cost 限制用于减少search 范围。 一旦一个逻辑expression的完整的plan和物理属性vector， 没有更高代价的其他plan或者部分plan ， 这个完整plan可以作为优化plan。 快速找到一个相对好的plan是非常重要，即使exhaustive 扫描。 更进一步， cost limit 可以透传到subexpression， 控制优化的上限空间。
对于一些binary 算子， 输入的实际的物理属性不如input之间的一致性物理属性重要。 对于intersection的sort-based 实现， 类似merge-join的算法， 只要2个input用相同方式进行sort即可。 对于一些case， search engine 允许尝试一些物理属性vector

other related work

1. 这里提到在starburst 如何做优化， 将优化分为2个阶段， 第一个阶段，叫rewrite phase， 基本上是基于规则的，非cost base，执行nested sql queries， union， outer join， grouping， aggregation另外一个阶段cost base 优化， 比如merge nested subqueries， bundles selection， join predicate。 cost base 优化器会执行exhaustive的search在某些条件下， 比如限制搜索在左深树。 它同样使用了动态编程， 对于类似enforcer的操作叫glue， 执行sort order或者创建高效access plan 。
   1. 有2个基础性问题， 1.基于类似语法的规则，step-wise expansion（逐步膨胀） 的join expression， 举例来说， 语法依赖一个中间层， 交换join/不交换join/规则集 都是特殊定制的。 问题是不是很清楚 现有的rule 如何与算子/expansion rule 交互。 定义一个怎样的中间层来用于expansion grammar？当集成一个新的算子到cost based optimizer， 必须定义几个新的中间层和他们的grammar rule三。 这些新rule 可能和现有的rule 进行交互， 创建一个复杂和繁琐的task。 volocano 代数优化方式更自然和易懂。
   2. 当添加新算子到cost-based optimzer时， 新算子需要集成到query rewrite level。 但在query rewrite level 是有层级， 也就是他不包含cost estimation。 比如， 优化有一些欠缺， 考虑一个union 或intersection of N set， 实际上就是join n relation， 然而join优化需要遍历tree 和join ordering， 基于selectivity 和cost 进行评估。但 union/intersection 仅仅用rewrite 和交换率来进行启发式优化。 当启发式规则适用于一些transformation时（如rewriting subquery到semi join）， 但这个启发式规则不适用在query rewrite level的已经存在的关系算子，不适用一个扩展查询优化系统未来的代数算子和属性是未知的。
   3. 我们相信一个单一层， 在这层中， 所有的代数等价式和transformation 可以用一个语言来表达并且由一个优化器组件来进行执行， 在未来探索数据库代数和优化时， 他可以有延续性。
   4. 注意， volcano 优化器生成器 通过合适的ranking和moves的选择来允许 启发式transformation， 他留给优化器实现者来进行选择何时以及如何使用启发式规则和cost-sensitive 优化， 而不是像starburst 要求先验
2. sciore/sieg 批评早期的基于规则优化器， 并得出结论 模块化是优化器系统扩展性的基本要求，如 rule set 和应用的控制结构。优化的不同task，如rule 应用和selectivity 评估 应该封装在独立和合作的 experts。