数据库内核杂谈（八）：数据库优化器（下）

本篇文章选自数据库内核杂谈系列文章。

在上一篇文章中，我们介绍了优化器的大概并且讲解了一系列通过语句重写来对查询进行优化的方法。文末也留了一个坑：当语句中涉及到多个表的 join 时，优化器该如何决定 join 的顺序(join ordering)来找到最优解呢？这期，我们接着这个话题往下说。

答案就是，优化器也只能尽力而为。上一篇文章中我们提到过 n 个表的 join 搜索空间高达 4^n，理论上只有穷尽搜索空间，才能保证找到最优解。但即便有时间和能力穷尽搜索空间，也未必能找到最优解(此为后话，暂且不表)。因此优化器的主要职责是，在资源限制内，这里资源可以是计算资源或者优化时间，找到尽可能足够好的执行计划。

启发式算法(Heuristic approach)

4^n 的搜索空间实在太大了，首先要做的就是，减小搜索空间。数据库的先贤们，想到了应用启发式算法(heuristic approach)来降低搜素空间。比如，最早的 Volcano Optimizer 里，就提出了对于 Join-order，只考虑 left-deep-tree，即所有的右子树必须是一个实体表。可能解释起来不太直观，对应下面三张不同的 join-order 的树形结构，就一目了然了。

left-deep-tree

bushy-tree 1

bushy-tree 2

其中图 1 就是 left-deep-tree，图 2 和图 3 称为 bushy-tree。那为什么只选择 left-deep-tree？要知道，即使是 left-deep-tree，搜素空间也有 n！。我自己的理解是结构比较简单，执行计划也很直观：左边的表不断和右边的表 join 生成新的 intermediate 表(中间表)，然后不断递归。在讲 join 实现的那章时，我们提到过，大部分情况下都会使用 HashJoin。如果能够使得左边的 result set 一直很小，从而建立的 Hash 表能一直存放在内存中的话，对于全部右子树的表，只要进行一次全表扫描，即可得到最终结果。因此，右子树的 table order 就不是特别影响运行时间了(因为总是得至少进行一次全表扫描的)。这种情况下，已经算是很优的执行计划了。

说完了优点，再来看看 left-deep-tree 有什么不好的地方？ 那就是不能同时执行多个 join。如果按图 3 中的 bushy-tree 2，那 A 和 B， C 和 D 可以同时进行 join。对于现在服务器配备多个 CPU 和大内存作为计算资源，考虑 bushy tree，肯定是会有更多的优化可能的。反之，也可能因为早期的服务器并没有那么多计算资源，本来也并不考虑对一个 SQL 查询进行并行执行，因此采用 left-deep-tree 的 heuristic，也就说得通了。

因此，left-deep-tree 的 join ordering 优化关键在于能够让左边的结果集, 从一开始的叶节点以及后续的所有 intermediate result 越来越小，最好能一直 fit in memory，这样就能保证所有的右子树表只需要进行一次全表扫描。要如何选择哪个表放在哪个位置呢？我们需要一些概率统计的知识。

Cardinality Estimation

Cardinality estimation，就是用来预测单个表的 selection cardinality 和 2 个表的 join cardinality 的技术。首先，简单介绍一些术语。

Selection cardinality: SC(P, R)

表示当 predicate 是 P 的时候，对于表 R，最后大约会有多少条 row 输出。

举个例子，对于表 student, 假设 P 为 major = ‘CS’, 相当于我们要计算下面这个 SQL 有多少 row 输出。

SELECT * FROM student WHERE major = 'CS';

要对输出进行预测，我们先要对表收集一些基本的元信息。有哪些信息呢？1）对于表 student，首先需要知道总共有多少 row；2）对于 student 表中的每个 column，总共有多少个 distinct value。你可能会想， 数据库是什么收集这些数据的呢？ 有些数据库会不定期地自动更新每个表以及每个 column 的统计信息，一般都还提供相关的语句来让数据库对某个表做元数据的统计：analyze TABLE 语句。有了这两个信息，那我们怎么计算 selection cardinality，再来看下面这个公式。

SC(P, R) = N_R * SEL(P, R) 

这边 SEL§ 就是统计意义上每个 row 满足 P 的概率。那怎么计算 SEL§呢。假设 P 很简单，只是单个 column 的 equality，比如上述示例 major = ‘CS’。基于 distinct value 的信息，我们假设 V(major, student)总共有 10 个专业，在此基础上，我们进一步假设数据均匀分布，那 major = 'CS’的概率就是 10%, 即 SEL(major = ‘CS’, student) = 10% 。如果 N_R = 100。那我们就可以推算出 SC(major = ‘CS’, student)约等于 10 条输出。是不是挺简单的，下面来看一些复杂的 predicate 的预测。

如果 P 并不是简单的 equality join，比如 age != 30。假设 SEL(age = 30, student) = 90%, 可以通过 negation 推算出 SEL(age != 30, student) = 10%

如果 P 是 age > 30 呢？这时候就需要用到大于 30 的 age 还有多少个 distinct value，我们假设 age 总共有 10 个 distinct value，且大于 30 的还有 4 个值，再次基于数据均匀分布假设，就可以推算出 SEL(age > 30, student) = 40%。

再来看更复杂一些的 predicate,如牵涉多个 column 的。如果是 P 是 age = 30 and major = ‘CS’。这里，我们需要一个新的假设，朴素贝叶斯定理假设条件互相独立。则 SEL(age = 30 ^ major = ‘CS’, student) = SEL(age = 30, student) * SEL(major = ‘CS’, student)。

如果 predicate 的 condition 是 disjunction，如 SEL(age = 30 V major = ‘CS’, student) = SEL(age = 30, student) + SEL(major = ‘CS’, student) - SEL(age = 30, student) * SEL(major = ‘CS’, student)。可以根据下图来推出这个公式:

disjunction

SEL * FROM R1, R2 WHERE R1.a = R2.a;

由于本人数学实在不好，就直接给出公式了：

JC(R1, R2, R1.a = R2.a) = N_R * N_S / max(V(a, R), V(a, S))

其中 V(a, R)就是指对于表 R 中 column a，一共有多少个 distinct value。

刚刚我们通过示例讲解了许多计算 selection cardinality 和 join cardinality 的方法。但刚才所有的计算假设都是数据是均匀分布(uniformly distributed)。现实情况肯定不会这么容易，比如我们计算 major = 'CS’的 student，CS 专业的学生肯定比其他专业学生要多一些。 那有什么办法可以改进吗？另一种常见的对 column 的值分布进行统计的方法就是使用 Histogram。Histogram 呢，除了统计有哪些 distinct value，还记录了这些 value 分别出现了几次，下图给出了一个 Histogram 统计的示例。

Histogram example

Histogram 通过存储更多的信息来统计更精确的数值分布。但很多情况下，统计并不需要那么精确。工程方面要在使用资源和准确性里找平衡。后来，又有大牛提出了HyperLogLog，是一种占用资源少，但能给出较为准确的近似结果的 cardinality estimator。

总结一下，有了 cardinality estimation，我们终于能预测哪两个表 join 后的 cardinality 比较小，可以用来决定 join ordering 了。但同时也发现，cardinality estimation 给出的只是预测结果，这也是为什么文章开头的时候谈到，即使能够穷尽搜索空间，依然不一定能找到最优解的原因。因为预测的结果是有出入的，并且随着 join 变得更复杂， 层级越多，越往上的误差就越大。

Cardinality estimation 仅仅是帮助决定了 join ordering，相当于 logical operator tree 上，不同的表分别应该放在哪个位置。但对于每个 logical operator，最后还需要变换成 physical operator (物理算子)才算完成最终的优化。如，对与 TableScan 这个逻辑算子，它对应的 physical operator 有 SequentialScan 和 IndexScan，应该用哪个？ 对于 JoinOperator，到底是用 NestedLoopJoin, SortMergeJoin，还是 HashJoin 呢？下面，我们介绍第二个关键技术。

Cost Model

Cost Model 的主要思想是，对于每一个 Physical operator，根据输入输出的 cardinality，会被赋值一个 cost(代价)。这个 cost，通常情况下可以认为是执行这个 operator 需要的时间，当然也可以是计算资源。那如何计算这个 cost 呢？对于每个 operator，都有一个 cost formula(公式)，这个公式根据输入输出的信息，最后能计算出这个 operator 的 cost 值。

还是配合示例来讲解：对于 SequentialScan(全表扫描)，它的 cost formula 我们定义成如下：

Cost = NumRowsInTable * RowWidth * SEQ_SCAN_UNIT_COST

解释一下这个公式，因为对于全表扫描，需要读取所有的 row，因此读取时间大致正比于表的 total row * 表的 width。而最后的 coeffficient SEQ_SCAN_UNIT_COST，可以想象成是一个虚拟的时间单位。

对于 IndexScan 呢？它的 cost formula 又长成什么样呢？区别于 Sequential Scan，它不需要全表扫描，但对于从 Index 中读取满足条件的 Row，需要回到原表中读取，相当于执行了 random IO。因此，我们可以根据操作的实现，定义它 cost formula 如下：

Cost = SelectionCardinality * RowWidth * INDEX_SCAN_UNIT_COST

而这边，INDEX_SCAN_UNIT_COST 可以认为是 random IO 的 cost，所以它的值应该要比 SEQ_SCAN_UNIT_COST 要大很多。比如，我们假定 SEQ_SCAN_UNIT_COST 值为 1，那 INDEX_SCAN_UNIT_COST 就可以设为 100。先不管这样设是否准确。但有了 cost formula 的定义，我们就能计算每个 physical operator 在当前环境下的 cost 了。再来参考下面这个示例：

SELECT * FROM student WHERE major = 'CS';

现在假设，student 表对 major 建有 index，然后 student 表总共有 10000 个 row，然后假定 cardinality estimation 给出的 selection cardinality 是 500，即有 500 个 CS 学生。我们再假设 width 是 10。分别把这些信息带入 SequentialScan 和 IndexScan 的公式可得：

SequentialScan Cost = 10000 * 10 * 1 = 100000
IndexScan Cost = 500 * 10 * 100 = 500000

在这种情况下，Optimizer 就会选择 SequentialScan。但如果查询语句变了，变为 major = ‘archaeology’ (考古学)，作为一个冷门专业，cardinality estimation 预测只有 10。再分别计算 cost：

SequentialScan Cost = 10000 * 10 * 1 = 100000
IndexScan Cost = 10 * 10 * 100 = 10000

在上述情况下，optimizer 就应该选择 IndexScan。

那如何定义 cost formula 和 coefficient 的值呢？这确实是一个很难的问题。笔者曾经做过相关的 research，cost formula 是需要根据 operator 的实现来定义的。甚至一个 operator，根据不同的执行环境，都会有不同的 cost formula。cost formula 意在去 simulate 真实执行下所花掉的时间。而对于 coefficient，笔者当时提出的方法就是通过执行 mini-benchmark 来 calibrate coefficient 的值，因为不同的部署环境，网络条件和硬件资源，都会影响 coefficient。当时对一些 operator 进行了测试，calibrate 后，效果立竿见影，只可惜后来离开公司了，没能把这个 research 做完。

讲完了单个 operator，我们再来看全局。对于一个 logical operator tree，Optimizer 要做的就是，当它变换成 Physical operator tree 后，所有的 operator 的 cost 相加(也可以是有权重的相加，假定多个 operator 可以并行执行，这边我们暂且不考虑这种复杂情况)后，使得 total cost 最小，这便是 optimizer 给出的最优 physical execution plan。

你可能会觉得，似乎对于每一个 logical operator, 选择哪一个 physical operator 是一个 local optimization 的问题。至少 Scan operator 看上去是这样的。其实并没那么简单。还记得我们说过 index Scan 带来的一个好处是什么吗？ 就是读取后的数据是有序的。有序是一个很好的属性，如果上层的 operator 对有序有需求，比如 SortMergeJoin，或者 SortGroupByAggregate，那原本需要排序的 cost 就被省去了。因此对于同一个 operator，它的 cost 不仅仅和自己的 cost formula 相关，还和它的子节点的 operator 也相关。比如对于 SortMergeJoin operator 来说，它的两个子节点都是 IndexScan, 或者是 Sequential Scan 会对它本身的 cost 产生影响，如果是 sequential scan 的话，排序的 cost 是需要计算在它的 cost formula 里的，但如果是 index scan，那排序的 cost 就为 0 了。因此，计算每个 operator 的 cost 是一个 global optimization 的问题。假定，对每个 operator，我们定义一个 aggregated cost 等于它本身的 cost 加上所有子节点的 cost。那 Optimizer 要求解的就是使得 root operator 的 aggregated cost 最小的 physical operator tree。是否有联想到什么算法了吗？ global optimization? Bingo！就是 dynamic programming。我觉得这可能是我工作中遇到的第一个真正使用 DP 解决的问题了吧：多阶段决策最优解模型；求解过程中需要多个决策阶段，每个决策阶段都会取决于最优子结构；并且，最优子结构属于重复子问题，因为会被多次使用到。上层无论是 HashJoin 或者是 SortMergeJoin 都会需要知道下层表的 SequentialScan 的 cost 是多少。因此我们需要 memorize 这个 SequentialScan 的 cost。整个计算过程自顶向下递归，对于子问题 memorize 结果，最终我们就能计算出最小的 root operator 的 aggregated cost, 以及它所对应的 physical operator tree。这就是最后 optimizer 输出的 physical execution plan。

总结

今天我们先从 join ordering 问题讲起，介绍了 cardinality estimation 技术，它通过预测 selection cardinality 和 join cardinality 来帮助决定 join ordering。然后介绍了 cost model 来对每个对应的 physical operator 计算 cost。最后通过 dynamic programming 来求解最小 cost 的 physical operator tree，以此得到最终的 physical execution plan。

终于，理论部分讲完了。这两期比较枯燥和深奥，但为了完整性，我觉得还是有必要的。最后，推荐大家一篇paper，介绍一个开源的数据库优化器 ORCA 的设计和实现(本人也是作者之一)。这是我当时第一份工作时参与的项目。

说了那么多枯燥的理论，咱们以一个小趣事结尾吧。当时我问组里的人为什么叫 ORCA(虎鲸)，是不是因为虎鲸很聪明？然后组里的头说"let me show you something"。然后打开 Youtube，放的是一段几头虎鲸围猎一群海豚的视频，场面略带血腥。头边放边说，“look at these babies, they are so smart!” 当时我也是虎躯一震。后来我仔细去查了一下，虎鲸生性残暴，喜欢虐杀。还有相关 research 说，从已经解析的虎鲸叫声中发现，大约 70%的叫声都是抱怨和咒骂。。可见脾气之暴躁。但谁让它长得萌，和大熊猫一样黑白配。所以说，这是一个看脸的世界。相对的，大白鲨，一副凶神恶煞的样子，被拉了不少仇恨。但你不知道，大白鲨，特别怕虎鲸，特别怕。

相关阅读：

数据库内核杂谈（一）：一小时实现一个基本功能的数据库

数据库内核杂谈（二）：存储“演化论”

数据库内核杂谈（三）：索引优化

数据库内核杂谈（四）：执行模式

数据库内核杂谈（五）：如何实现排序和聚合

数据库内核杂谈（六）：表的 JOIN（连接）

数据库内核杂谈（七）：数据库优化器（上）