0%

《The Volcano Optimizer Generator: Extensibility and Efficient Search》

# 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

# 整体视图 image.png
将data model 描述 生成为编译器代码, 和其他数据库模块 如查询引擎, 搜索引擎编译和链接在一起,生成数据库. ## 设计原则 5个基本原则

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


优化器生成器的输入

  1. parser 解析query 后,生成logic 算子组成的关系表达式, 这个作为优化器的输入,优化器输出是一个执行plan, 这个plan 是带有关系代数算法。 算法集, capability和代价 代表着data format 和物理存储结构。
  2. 优化过程是 将一个逻辑关系代数表达式 映射为一个优化的,等价的,物理关系代数表达式。 对算子进行reorder, 对实现算法进行挑选。 transformation rule 包含等价转化, 交换律, 结合律。 implementation rule 包含一些算子的算法选择。 rule language 必须支持复杂的mapping, 可以join后带projection 用一个rule来表示, 可以一个rule 来表达映射多个逻辑operator到一个物理operator, 在一个rule pattern成功匹配后, 可以attache condition code 到rule上。
  3. 用属性来描述expression的result。 逻辑属性来自逻辑关系代数表达式, 包括schema, expected size等。 物理属性来自算法, 如sort order, parition等