高级数据库十五：查询优化器（一）

刺骨的言语ヽ痛彻心扉 2022-06-02 05:40 383阅读 0赞

# Optimizer Implementation(Part I) #

## 背景 ##

在讲述这个优化器的时候，就必须先了解查询过程。在本系列的[数据库四：浅谈数据库查询过程（Query Processing）][Query Processing]中大致地说明了一下数据库的查询过程，但是没提到查询优化器的具体策略与实现。

对于查询而言，我们期望优化器的作用是找到最小代价的正确执行方案。但是这是一个NP完全问题，所以没有一个优化器能够真正地找到真正的最佳方案。

关于OLTP的查询优化会更加简单，一般来说选取最好的索引，JOIN操作也大多使用外键，用一些简单的策略就行。

比如，大家可以画一棵关系代数查询树，如果我们将选择操作尽可能下放到深处，则在进行笛卡尔乘或者JOIN的时候，参与运算的数据就少了。这就是heuristic optimazation。

![15151034938509.jpg][]

所以在这儿我们将说明OLAP查询的优化策略。

## 优化器基础 ##

### 优化器粒度 ###

单查询

*  更小的搜索空间。
 *  DBMS不能在查询中重复使用结果。
 *  为了解决资源争夺问题，成本模型必须考虑当前正在运行的内容。

多查询

*  如果有很多类似的查询，效率会更高。
 *  搜索空间要大得多。
 *  用于扫描共享（之后的文章会提到，大致就是多个查询共用一个扫描表的结果，而不是各自扫描一次）

### 优化时间 ###

静态优化

*  在执行之前选择最佳计划。
 *  计划质量取决于成本模型的准确性。
 *  可以使用准备好的支票分摊执行。

动态优化

*  主要在流式数据的时候使用
 *  查询执行时，即时选择运营商计划。
 *  将重新优化多次执行。
 *  难以实现/调试（非确定性）

混合优化

*  使用静态算法编译。
 *  如果估计>阈值的误差，则重新优化。

### 计划稳定 ###

提示

*  运行数据库系统管理员帮助优化器进行决策，比如，我希望用hash表进行JOIN等
 *  mysql、sqlserver似乎都支持这种方法

固定优化器版本

*  设置优化器版本号并将查询逐个迁移到新优化器。比如，虽然用了新版本的数据库，但是对于某种特定的查询，我们发现了旧版本的优化器似乎更快，则可以将版本调回去。

向后兼容的计划

*  从旧版本保存备份查询计划，并将其提供给新的DBMS。

## 优化器搜索策略 ##

### Heuristics ###

论文[Query Processing In A Relational Database Management System][]

之前举了一个关系代数查询树的例子，说的就是Heuristics优化方法。它定义了一些规则，通过静态的方式来进行优化：

*  尽早进行选择，越严格的限制应该越早进行
 *  在连接之前执行所有选择
 *  谓词/限制/投影下推
 *  基于基数加入排序

Oracle在早起非常受欢迎的原因就是因为它使用了这种方法。

优点：

*  易于实施和调试。
 *  效果相当好，对于简单的查询很快。

缺点：

*  依靠玄学常数来预测计划决策的有效性。
 *  当操作之间存在复杂的相互依赖关系时，几乎不可能产生好的查询计划。

### Heuristics + Cost-based Join Order Search ###

论文[Access path selection in a relational database management system][]

使用静态规则执行初始优化,然后使用动态规划来确定表格的最佳连接顺序。

*  第一个基于成本的查询优化器
 *  使用分而治之搜索方法进行自底向上（向前链接）

现在也非常常用的技术，MySQL、SQLite都用这个。

#### SYSTEM R OPTIMIZER ####

![15151168530429.jpg][]

假设都没有索引，则得到数据的方式就是线性扫描。

然后将所有的JOIN操作的可能性都列出来，并找出最少代价的JOIN策略。其中也包括每个具体的JOI操作的算法。

![15151169546928.jpg][]

因为有ORDER BY，所以要进行排序

![15151170311352.jpg][]

优点：

*  通常找到一个合理的计划，而不必执行详尽的搜索。

缺点：

*  所有与启发式方法相同的问题。
 *  左深连接树并不总是最佳的。
 *  必须考虑成本模型中数据的物理属性（例如排序顺序）。

### Randomized Algorithms ###

执行随机遍历查询的所有可能（有效）计划的解决方案空间。  
继续搜索，直到达到代价阈值或优化器运行一段特定的时间。

例如：Postgres的遗传算法。

优点：

*  随机跳转搜索空间允许优化器跳出局部最小值(这个地方可以去看看[遗传算法的文章][Link 1]来理解原理)。
 *  低内存开销（如果没有历史保存）。

缺点：

*  很难确定为什么DBMS可能选择了一个特定的计划。
 *  必须做额外的工作来确保查询计划是确定性的。
 *  仍然必须执行正确性规则。

#### SIMULATED ANNEALING ####

用Heuristics方发生成的最初的查询计划，然后通过SQL运算符的随机排列（例如，交换两个表的连接顺序）来产生新的解。

*  始终接受降低成本的更改
 *  只接受一个可能会增加成本的变化。
 *  拒绝违反正确性的任何更改（例如，排序顺序）

#### POSTGRES OPTIMIZER ####

更复杂的查询使用遗传算法来选择连接顺序的。

在每一轮开始时，生成查询计划的不同版本，选择成本最低的计划，并用其他计划进行排列。重复该操作。

*  变异函数只产生有效的计划。

### Stratified Search ###

首先使用转换规则重写逻辑查询计划。

*  引擎检查是否允许转换，然后才能应用。
 *  这一步从来不考虑成本。

然后执行基于成本的搜索，从而将逻辑查询计划映射到物理查询计划。

优点：

*  在快速表现的实践中运作良好。

缺点：

*  难以为转换指定优先级
 *  如果不计算多重成本估算，一些转换难以评估。
 *  规则维护是一个巨大的痛苦。

#### STARBURST OPTIMIZER ####

用此方法实现更好地System R optimizer。

阶段1：查询重写

*  计算查询的SQL块级关系微积分表示。

阶段2：计划优化

*  一旦查询重写完成，执行System RR风格的动态规划阶段。

### Unified Search ###

使用唯一的一个搜索空间，统一逻辑- 逻辑和逻辑- 物理转换的概念。 不需要单独的阶段，因为一切都是转换。

这种方法产生了更多的转换，因此大量使用memoization来减少冗余工作。

#### VOLCANO OPTIMIZER ####

通用基于成本的查询优化器，基于关系代数上的等价规则。

*  轻松添加新的操作和等价规则。
 *  计划过程中将数据的物理属性视为一流的实体。
 *  使用分枝定界搜索的自顶向下方法（反向链接）。

不过这种方法似乎只在实验室或者学校中才有用到，工业界似乎没有用过这种方式。

优点

*  使用声明性规则来生成转换。
 *  通过高效的搜索引擎实现更好的可扩展性。 减少使用记忆的冗余估计。

缺点：

*  在优化搜索之前，所有等价类都完全展开以生成所有可能的逻辑运算符。
 *  不容易修改谓词。

#### TOP-DOWN VS. BOTTOM-UP ####

自上而下的优化：从你想要的最终结果开始，然后在树上寻找最适合你的目标。

自下而上的优化：从一无所有开始，然后制定计划以达到您想要的最终结果。

[Query Processing]: http://blog.csdn.net/u013007900/article/details/78015124
[15151034938509.jpg]: https://lh3.googleusercontent.com/-m79SZMzsyAc/Wk7hzh6rRhI/AAAAAAAAAcU/6of0sDb_-e0zl93qM5um0TJBHL2iZBsBwCHMYCw/I/15151034938509.jpg
[Query Processing In A Relational Database Management System]: http://ieeexplore.ieee.org/document/718156/
[Access path selection in a relational database management system]: https://dl.acm.org/citation.cfm?id=582099
[15151168530429.jpg]: https://lh3.googleusercontent.com/-IoEUMQhWp_4/Wk7hz5g8RqI/AAAAAAAAAcY/wk4-TfP8ixUc8q-j7brlqAPtfmr8m6c8wCHMYCw/I/15151168530429.jpg
[15151169546928.jpg]: https://lh3.googleusercontent.com/-nw3fxmPJC0g/Wk7h0MSPlkI/AAAAAAAAAcc/FMgQ6-l-Gwo8gvwtQKDg14YPuMXf_YvBACHMYCw/I/15151169546928.jpg
[15151170311352.jpg]: https://lh3.googleusercontent.com/-zmFj0uWHY8Q/Wk7h0qB4XYI/AAAAAAAAAcg/l-WAEws3ErQfMZO6Vun9vKD2Q4OD84XeACHMYCw/I/15151170311352.jpg
[Link 1]: http://blog.csdn.net/u013007900/article/details/43523975