高级数据库十六：查询优化器（二）

客官°小女子只卖身不卖艺 2022-06-02 06:55 209阅读 0赞

# Optimizer Implementation(Part II) #

在这儿解释一下，逻辑查询计划或者逻辑计划指的是关系代数层面的查询语句；物理查询计划或者物理计划指的是具体查询层面的查询算法，具体到每一个[JOIN的算法选择][JOIN]，每一个SELECT操作的算法实现（scan或者index）。

## 瀑布模型（Cascades） ##

### 分层搜索（STRATIFIED SEARCH） ###

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

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

然后执行基于成本的搜索以将逻辑计划映射到物理计划，在不同的优化器设计中会有不同的方式去实现。

### POSTGRES OPTIMIZER ###

为查询优化强加一个严格的工作流程：

*  第一阶段用启发式进行初始重写
 *  然后执行基于查询成本的搜索以查找最佳JOIN顺序。
 *  其他一切都被视为“附加”。
 *  然后递归下降到子查询。

因为程序的执行顺序必须保持一定，所以程序难以修改或扩展。如果上面的状态改变了，那么也将会影响到下面的子查询。

### UNIFIED SEARCH ###

没有像上面两个方式一样一般有多个阶段的不同算法，而是将所有的东西都一同丢进一个搜索空间来进行搜索。

所以在某种程度上来说，它非常容易实现。

统一逻辑- 逻辑和逻辑- 物理转换的概念。不需要单独的阶段，因为一切都是转化。

这种方法会产生非常多的转换，因此大量使用记忆化搜索来减少冗余工作。

### VOLCANO OPTIMIZER ###

论文[The Volcano Optimizer Generator: Extensibility and Efficient Search][The Volcano Optimizer Generator_ Extensibility and Efficient Search]

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

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

优点：

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

缺点：

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

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

自上而下的优化：从你想要的最终结果开始，然后决定你想要加入什么特殊的操作，最后在搜索树上寻找最适合你的目标。

*  比如，若是SQL中有`ORDER BY`这样的命令，那么你就希望在其中有一些部分用的是Sort Merge Join，尽管他的耗时会比hash表大，但是它的排序效果是用户想要的。
 *  因为可能会重复搜索相同的状态，所以需要用记忆化的方式去做。会占用较大的内存。

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

*  在搜索评估的过程中，如果已经完成了一个状态的评估，我们就不会再计算这个状态的情况；这和自上而下的优化是不同的。

关于记忆化的问题，大家可以研究一下动态规划中使用记忆化和不使用记忆化的更新方式。简单的例子，可以看看矩阵连乘优化的区间dp，看看递归版本和递推版本。

### 例子 ###

![15152737387864.jpg][]

对于以上的scheme，我们执行如下的查询，查询出，所有名为“Andy’s OG Remix”的专辑的作者的姓名，并按照他们的id排序。

SELECT ARTIST.NAME
     FROM ARTIST, APPEARS, ALBUM
    WHERE ARTIST.ID=APPEARS.ARTIST_ID
     AND APPEARS.ALBUM_ID=ALBUM.ID
     AND ALBUM.NAME="Andy's OG Remix"
    ORDER BY ARTIST.ID

首先，我们先将最终目标的逻辑查询计划写出来（关系代数以及其他限制）。

然后使用其他的规则去产生新的搜索树节点，其中包括了逻辑查询计划向逻辑查询计划的转化，如，等价的逻辑查询计划的转化，`JOIN(A,B) to JOIN(B,A)`；也包括了逻辑查询计划向物理查询计划的转化，如，对于每个操作的物理实现的选择，`JOIN(A,B) to HASH_JOIN(A,B)`。

![15152742621639.jpg][]

根据特性对其进行剪枝搜索，比如，我们最终的查询要求是有序的，所以我们不选择HASH-JOIN而是选SORT-MERGE-JOIN。

![15152749659202.jpg][]

当然，我们也能用HASH-JOIN加上排序算法。但是，假设我们已经评估过了HASH-JOIN的代价，并且它的代价加上排序的代价已经大于了SM-JOIN的代价，那么就进行剪枝，我们不需要继续递归。

### SEARCH TERMINATION ###

方法＃1：Wall-clock Time

*  优化器运行一段时间后停止。

方法＃2：Cost Threshold

*  优化器找到一个成本低于某个阈值的计划时停止。

方法3：Transformation Exhaustion

*  当没有更多的方法来转换目标计划时停止。通常每组完成。

## Pivotal Orca ##

论文[Orca: A Modular Query Optimizer Architecture for Big Data][Orca_ A Modular Query Optimizer Architecture for Big Data]

一种Cascades的实现。

→最初是为Greenplum写的。  
→扩展以支持HAWQ。

DBMS可以通过实现API来使用Orca来发送目录+统计信息+逻辑计划，然后检索物理计划。

支持多线程搜索。

### ORCA – ENGINEERING ###

问题＃1：远程调试

→每当发生错误时自动转储优化器的状态（带有输入）。  
→转储足以将优化器稍后恢复为完全相同的状态，以便进一步调试。

问题＃2：优化精度

→自动检查两个方案的估算成本的排序是否与实际执行成本相符。

## 参考资料 ##

[课件][Link 1]

[JOIN]: https://en.wikipedia.org/wiki/Join_%28SQL%29#Join_algorithms
[The Volcano Optimizer Generator_ Extensibility and Efficient Search]: http://15721.courses.cs.cmu.edu/spring2017/papers/14-optimizer1/graefe-icde1993.pdf
[15152737387864.jpg]: https://lh3.googleusercontent.com/-_59Mz_VVVgs/WlFyFXcEVyI/AAAAAAAAAdQ/ql72dyf0ccQKro-uDhYV1ShxXyuc9KVPQCHMYCw/I/15152737387864.jpg
[15152742621639.jpg]: https://lh3.googleusercontent.com/-dL6DKAwUzF8/WlFyF2xjy-I/AAAAAAAAAdU/ZSMo22bNhIIAbWyuQYAuZcKraUuw0kHwACHMYCw/I/15152742621639.jpg
[15152749659202.jpg]: https://lh3.googleusercontent.com/-QXXhf7fmsaQ/WlFyGSH5D7I/AAAAAAAAAdY/ZgYMwfXu2G8F9xJEGGY8jh4Bib8iq5bZgCHMYCw/I/15152749659202.jpg
[Orca_ A Modular Query Optimizer Architecture for Big Data]: http://15721.courses.cs.cmu.edu/spring2017/papers/15-optimizer2/p337-soliman.pdf
[Link 1]: http://15721.courses.cs.cmu.edu/spring2017/slides/15-optimizer2.pdf