Goetz

查询优化器#xff0c;接着分析查询…数据库中查询优化器是数据库的核心组件其决定着

SQL

语句进行各种规则优化生成最优的执行计划并交由执行器执行。

优化器对于

SQL

语句经过语法和词法解析生成抽象语法树(AST)经过基于规则的查询优化Rule-Based

基于规则的优化方法的要点在于结构匹配和替换。

应用规则的算法一般需要先在关系代数结构上匹配一部分局部的结构再根据结构的特点进行变换乃至替换操作。

现阶段主流的方法都是基于成本Cost估算的方法。

给定某一关系代数代表的执行方案对这一方案的执行成本进行估算最终选择估算成本最低的方案。

尽管被称为基于成本的方法这类算法仍然往往要结合规则进行方案的探索。

基于成本的方法其实是通过不断的应用规则进行变换得到新的执行方案然后对比方案的成本优劣进行最终选择。

所示开销模型使用收集到的统计信息以及构造的不同开销公式估计某个特定查询计划的成本帮助优化器从众多备选方案中找到开销最低的计划。

SQL

关系代数可以进行局部的等价变换变换前后返回的结果不变但是执行成本不同

SQL

寻找执行成本最低的关系代数表示可以分为基于动态规划的自底向上和基于

Cascades/Volcano

自底向上搜索从叶子节点开始计算最低成本并利用已经计算好的子树成本计算出母树的成本就可以得到最优方案

自顶向下搜索先从关系算子树的顶层开始以深度优先的方式来向下遍历遍历过程中进行剪枝。

自底向上的优化器从零开始构建最优计划这类方法通常采用动态规划策略进行优化采用这类方法的优化器包括

IBMSystem

框架采用自顶向下的方式进行枚举因此枚举过程中可能产生大量的重复计划。

为了防止出现重复枚举Cascades

框架采用

采用一个类似树状实际是一个图状的数据结构它的每个节点对应一个组每个组的成员通过链表组织起来

Transformation

GET(b)的物理算子我们可以估算每个物理算子的代价选取其中最优的算子保留下来。

结构体中还包含一个哈希表exprHT它以表达式为哈希表的键用来快速查找某个表达式是否已经存在于

Memo

采用自顶向下的方式来进行优化以计划树的根节点为输入递归地优化每个节点或表达式组。

如图所示整个优化过程从

Group

时依次优化每个组员在优化每个组员时依次递归地优化每个子节点。

依次估算当前组里每个表达式

cost(e)选择最低得代价结果保存在