SQL 查询优化原理与 Volcano Optimizer 介绍

随着大数据相关技术的发展，SQL 作为一种成熟的查询语言又逐渐回到人们视野的中心来，被称为 NewSQL 的新型关系型数据库更是蓬勃发展。 作为一种声明式编程语言，将 SQL 转化为可以高效执行的任务对于 OLAP 任务来说是至关重要的。 本文将尝试对相关的技术原理进行一次总结。

本文将重点着眼于对 Volcano(Cascades) Optimizer的详细介绍上，这是因为 Volcano 模型不但十分流行， 更是被 Apache Calcite 这一优秀的开源框架所实现了。 我们因此可以通过直接阅读 Calcite 的源码来了解算法执行的内部细节。

尽管 Apache Calcite 这一项目并不是经常出现在人们眼前，但却是 Apache 数据平台技术栈当中及其有价值的组件。 它提供了一套 SQL 的解析与执行接口，包含了 SQL 查询和执行相关的一系列任务的执行代码。 使用者只需要将自己的数据模型 Plugin 到 Calcite 当中，就可以得到 SQL 查询的能力。 包括 Apache Storm, Apache Flink, Apache Kylin 和 Apache Drill 等项目都使用它完成 SQL 解析或执行的操作。

遗憾的是，除了相关论文之外，其文档等对于内部细节的介绍都不够充分。 本文作为对其部分代码细节进行阅读之后的浅显总结，同时也希望能为各位读者使用 Calcite 有所帮助。

另外值得注意的是，本文使用 Volcano Optimizer 代指 Volcano 和 Cascades 两种算法， 一个是因为二者是一脉相承的关系，很多基本思想是一样的，另外一点是很多有关 Volcano 优化器的相关信息其实是由 Cascades 相关的 Paper 总结和介绍的。

SQL 查询优化的目的

SQL 查询优化在 OLAP 应用当中至关重要的主要原因在于 SQL 是一种声明式(Declarative)的编程语言， 相比一般的编程语言描述的是程序执行的过程，这类编程语言则是描述问题或者需要的结果本身。 具体的执行步骤则交由程序自己决定。

从使用的角度，SQL 作为一种可以被非相关技术人员快速入手的编程语言， 其主要优点就在于即使用户因并不了解数据库内部的实现细节而写出来十分糟糕的查询语句， 只要表达的意思准确清楚，数据库就可以在一定程度上将其转化为合理的执行方案高效的返回结果， 极大的降低了使用门槛。因此一个好的查询优化器，也是关系型数据库重要的卖点之一。

从技术的角度来说，通过对用户输入的查询进行优化，实现更优的执行步骤规划 数据库可以实现更快的执行和更少的 IO 消耗。从而节约资源提高性能。

SQL 查询优化的基本原理

SQL 作为一项图灵奖级别的发明，其重要意义不单单是发明了一种可以用作数据查询的语言， 更重要的一点是发明了关系代数(Relation Algebra)这一工具， 使得计算机理解和处理查询的语义更加方便。SQL 查询语句的优化也是基于关系代数这一模型。

所谓关系代数，是 SQL 从语句到执行计划的一种中间表示。首先它不是单纯的抽象语法树(AST)， 而是一种经过进一步处理得到的中间表示(可以类比一般编程语言的 IR)。SQL 优化的本质是对关系代数的优化。

关于关系代数的具体内容这里不再赘述，我们直接来看一个例子。假设我们有如下的 SQL:

1
2
3
4
SELECT pv.siteId, user.nickame
FROM pv JOIN user
ON pv.siteId = user.siteId AND pv.userId = user.id
WHERE pv.siteId = 123;

上述 SQL 假定我们有两个数据表pv和user，前者记录了用户的 Pageview 访问， 后者是用户信息表。这两张表可以使用siteId和userId(user.id)连立合并起来， 这样我们就既可以查到用户的 PV 信息，又可以将 PV 信息对应到用户资料。

将上述 SQL 表示成关系代数，可能是如下形式:

Relation Algebra

可以看到，上述关系代数将 SQL 表示成树形的结构，树形结构的叶子结点是 SCAN 算子， 负责从储存设备将表中的信息读出。之后两个表的数据被输送到 JOIN 算子中实现合并计算。 JOIN 得到的数据又被输入一个 FILTER 算子中执行 WHERE 语句的条件(即过滤操作)。 最后的顶层算子是 PROJECT 算子，这个算子可以将输入数据当中的指定列取出，也可以对这些列进行重命名。

显然，关系代数本身就一定程度上体现了 SQL 查询的计算方案。 一般来说，实际的数据库实现还存在逻辑代数处理阶段和物理实现处理阶段， 这两个阶段使用的算子不同。数据流动也存在 Pull 模式和 Push 模式两种。 在这里我们先略去对这些信息的讨论，单纯研究如何通过关系代数优化执行方案。

观察上述关系代数的表示，我们发现最终的结果只需要使用到pv.siteId、pv.userId user.id和user.nickname四列数据。即使我们的表有几十列其他的数据，也对最终的结果没有影响。 将这些表的其他列读取出来向上传输和计算是一种浪费。如果我们的表支持高效地只读取需要的列， 那么从一开始就这么做会大大提高性能。下图描述了这种变换:

Projection Pushdown

通过只读取特定列来减少 IO 损耗、增加执行性能的技巧正是现今流行的列式储存的优点。

继续观察我们的关系代数树，可以发现对于pv表有一个条件过滤操作。 假设我们的pv表在siteId这一列创建了索引，或者这个表在就是按照这一列的值分散储存的。 在这种情况下，显然我们可以做到在 SCAN 的时候直接找到对应 siteId 所在的区域， 只读取符合匹配条件的数据出来。避免读取不相关siteId的数据可以极大地减少 IO 和提高性能。

Predicate Pushdown

上图描绘了这种变换。实际上，这种变换被称为谓词下推(Predicate Pushdown)， 是普遍应用在各种文件储存格式(ORC、Parquet)和各种 SQL 数据引擎(Hive、Kylin) 上的常见的查询优化方式。

通过上面的几步，我们成功将最初的关系代数模型化简成为一种更为简单高效， 实际效果却完全一样的关系代数。最后的结果是一种相比之前更优的执行方案， 因此也就实现了我们进行查询优化的目的。

总结使用关系代数进行查询优化的要点:

  1. SQL 查询可以表示成关系代数
  2. 关系代数作为一种树形的结构，实质上也可以表示查询的物理实现方案流程
  3. 关系代数可以进行局部的等价变换，变换前后返回的结果不变但执行的成本不同
  4. 通过寻找执行成本最低的关系代数表示，我们就可以将一个 SQL 查询优化成更为高效的方案

此外，很重要的一点是: 实现关系代数的化简和优化，依赖于数据系统的物理性质，如

  1. 储存设备的特性(顺序读性能如何？随机读性能如何？吞吐量如何)
  2. 储存内容的格式和排列(列式储存？行式储存？是否以某列进行分片？)
  3. 包含的元数据和预计算结果(是否存在索引？是否存在物化视图？)
  4. 聚合和计算单元的特性(单线程？并发计算？分布式计算？特殊加速硬件？)

综上所述，对 SQL 查询进行优化，既要在原先逻辑算子的基础上进行变换， 又要考虑物理实现的特性，这就是为什么很多查询系统存在逻辑方案和物理方案的区别的原因。 在优化时，往往存在一个从逻辑方案到物理方案进行转变的阶段。

事实上，从逻辑方案到物理方案的变换也可以划归为一种关系代数的优化问题。 本质上仍然是按照一定的规则将原模型当中的局部等价地转换成一种可以物理执行的模型或算子。 一个最简单的例子就是 JOIN 方案的选择：

Physical Plan

如上图所示，JOIN 算子只描述了两个表需要进行 JOIN 的逻辑，但是并没有指定 JOIN 的实现方案。 右边的 HASH JOIN 和 SORT JOIN 代表着 JOIN 操作的两种不同的实现方案。 两种方案在不同的场景下各有优劣，需要根据实际输入数据的特点进行选择。 然而尽管是从逻辑算子到物理算子的变换，其基本原理仍然是根据一定的规则进行代换而已， 与逻辑算子之间的代换并无本质差别。

另一种具有代表性的优化方案是 SORT LIMIT 的实现方案。假设一个查询会将数据进行排序， 然后 LIMIT 取最高的几个值。当取得的值比较少的时候，显然可以采取一定的措施避免对全部数据进行排序 (使用堆缓冲等)。鉴于排序是一种耗费很多的操作，对其进行优化很有价值。下图展示了一种优化方法:

Top-N

上述优化证明了进行关系代数的变换时，往往不一定是一对一的关系。很多情况下可以将多个算子合并成一个算子。 实际上将一个算子进行拆分形成多个算子的场景也是有的。

SQL 查询优化的基础算法

基于规则的优化算法

前面的例子探索了 SQL 语句进行优化的过程。 将这一过程形式化的总结出来就得到了基于规则的优化方法。

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

Pattern Match

值得注意的是，由于变换规则要保持关系代数语义不变的大前提没有改变， 因此被匹配的部分即使内部结构完全被替换，其跟外部的接口也要保持一致性：

  1. 向上输出的数据内容和类型不变
  2. 下层接受输入的数量和类型不变

基于成本的优化算法

基于规则的优化算法在实际使用中仍然面对很多问题:

  1. 变换规则的选择问题：哪些规则应该被应用？以什么顺序被使用？
  2. 变换效果评价的问题：经过变换的查询性能是否会变好？多种可能的方案哪个更优？

对于上述问题，不同的算法给出了不同的答案。最朴素的方法是人工定义一些规则的优先级， 每次按照固定的优先级选择规则进行变换直到最后得到结果。这种方法往往无法得到最优的方法， 灵活性也比较差。

现阶段主流的方法都是基于成本(Cost)估算的方法。也就是说，给定某一关系代数代表的执行方案， 将会对这一方案的执行成本进行估算，最终选择估算成本最低的方案。

尽管被称为基于成本的方法，这类算法仍然往往要结合规则进行方案的探索。也就是说， 基于成本的方法其实是通过不断的应用规则进行变换得到新的执行方案， 然后对比方案的成本优劣进行最终选择。

Plan Exploring

上图展示了这一过程。其中，每一次关系代数的变换都是由于应用了不同的规则， 应用了某一规则之后还可以接下来应用其他规则，直到所有变化都被穷尽了为止。 对于每一种方案我们都可以计算得到一个估计的成本，如果可以计算出所有可能的变化， 我们就可以得到最优的方案。

显然，要不重复地遍历所有不同的关系代数表示本身就是一项相对棘手的算法问题， 即使实现了这样枚举的功能，其巨大的搜索空间也消耗很多计算力——查询优化本身是为了提高查询性能， 如果优化算法本身的性能堪忧，则执行这一步骤的意义就消失了。

接下来就讨论一种可以较好地解决上述问题的系统: Volcano Optimizer。

Volcano Optimizer

Volcano Optimizer 是一种基于成本的优化算法，其目的是基于一些假设和工程算法的实现， 在获得成本较优的执行方案的同时，可以通过剪枝和缓存中间结果(动态规划)的方法降低计算消耗。 这一章在介绍 Volcano Optimizer 的同时也将会引入很多对 Calcite 当中概念的讨论。

成本最优假设

成本最优假设是理解 Volcano Optimizer 实现的要点之一。这一假设认为， 在最优的方案当中，取局部的结构来看其方案也是最优的。

成本最优假设利用了贪心算法的思想，在计算的过程中， 如果一个方案是由几个局部区域组合而成，那么在计算总成本时， 我们只考虑每个局部目前已知的最优方案和成本即可。

换句话说，在 Volcano 优化算法下，下图所表示的关系代数的计算成本，大体上正比于各个部分计算成本的和。 这一假设不仅应用于单个 Operator 节点之间，也应用于子树之间和被规则匹配的区域内外。

Cumulative Cost

对于成本最优假设的另一种更直观的描述是，如果关系代数局部的某个输入的计算成本上升， 那么这一子树的整体成本趋向于上升，反之则会下降。也即是在上图右侧有

$$Cost(A) \sim Cost(B) + Cost(C)$$

上述假设对于大部分关系代数算子都是有效的，但是并非百分之一百准确。 对于部分反例的处理方法将会在后文进一步介绍。

动态规划算法与等价集合

由于引入了成本最优假设，在优化过程中我们就可以对任意子树目前已知的最优方案和最优成本进行缓存。 此后在计算的过程中，如果需要利用这一子树，可以直接使用之前缓存的结果。这里应用了动态规划算法的思想。

要实现这一算法，只需要建立缓存结果到子树双向映射即可。在 Calcite 的实现当中，一颗子树使用其根结点作为代表。 某一棵子树所有可能的变换方案组成的集合被称为等价集合(Equivalent Set)， 等价集合将会维护自身元素当中具有最优成本的方案。

Equivalent Set

等价集合在 Calcite 当中对应的是RelSet类。

对每一颗子树都枚举其等价集合的内容会十分耗费空间。其实，对于某一棵以 A 为根结点的子树来说， 我们只关心 A 本身和包含 A 了的匹配内的节点。对于 A 和包含 A 的匹配之外的部分， 我们可以直接链接到子树对应的等价集合当中。基于成本最优假设，在计算方案成本的时候， 我们还可以直接从这些部分的等价集合中选取最佳方案。

假设从 A 起，可以应用两种不同的变换规则，如下图所示:

Equivalent Set Building

则除了 A 本身和规则匹配到的部分，其他部分的计算就可以通过递推的方式实现 具体来说，对应上述三种情况，会计算等价集合的元素：

  1. A 节点结合 B、C 节点等价集合的最优元素和成本
  2. A、C 转化后的节点结合 B、E、F 节点对应等价集合当中的最优元素和成本
  3. A、B 转换后的节点结合 C、D、E 节点对应等价集合当中的最优元素和成本

A 所代表的子树对应的最优方案也即是从上述三种方案中选取。

通过链接到子树优化方案的技巧，我们的算法缩减了状态空间、节省了计算量和储存空间。 下图展示了链接到子方案的大致思路。

Equivalent Set Structure

当然，在关系代数表示中不相邻的部分也可能具有重复的结构，Calcite 在实现的过程中考虑了这种情况， 将会在合适的时候对等价集合进行合并操作，也会出现树中两个不同子树的根指向了同一个等价集合的现象。

要实现树结构的相等计算和查询计算也比较复杂，Calcite 采用了最简单的递归将子树的内容打印成字符串的方法进行 Hash 和比较。 因此在使用 Calcite 时要注意正确实现 RelNode 类的 getDigest 方法。保证将节点的各种属性包含在内， 防止不同的节点被认为等价。

在计算结束后要得到最后的执行方案，只需从根节点开始将原始关系代数当中的结构替换成最优方案当中的即可。

自底向上 vs. 自顶向下

在实现上述动态规划算法的时候存在两种遍历方法，一种是自底向上的动态规划算法， 一种是自顶向下的动态规划算法。

自底向上的算法最为直观：当我们试图计算节点 A 的最优方案时， 其子树上每个节点对应的等价集合和最优方案都已经计算完成了，我们只需要在 A 节点上不断寻找可以应用的规则，并利用已经计算好的子树成本计算出母树的成本，就可以得到最优方案。 事实上，包括 SQL Server 在内的一些成熟的数据库系统都采用这种方法。

然而这种方案存在一些难以解决的问题:

  1. 不方便应用剪枝技巧，在查询中可能会遇到在父亲节点的某一种方案成本很高，后续完全无需考虑的情况， 尽管如此，需要被利用的子计算都已经完成了，这部分计算因此不可避免
  2. 难以实现启发式计算和限制计算层数。由于程序要不断递归到最后才能得到比较好的方案， 因此即使计算量比较大也无法提前得到一个可行的方案并停止运行

因此，Volcano Optimizer 采取了自顶向下的计算方法，在计算开始， 每棵子树先按照原先的样子计算成本并作为初始结果。在不断应用规则的过程中，如果出现一种新的结构被加入到当前的等价集合中， 且这种等价集合具有更优的成本，这时需要向上冒泡到所有依赖这一子集合的父亲等价集合， 更新集合里每个元素的成本并得到新的最优成本和方案。

值得注意的是，在向上冒泡的过程中需要遍历父亲集合内的每一个方案，这是因为不同方案对于 Input 成本变化的敏感性不同，不能假设之前的最优方案仍然是最优的。

自顶向下的方法尽管解决了一些问题，但是也带来了对关系代数节点操作十分繁琐、 要不断维护父子等价集合的关系等问题，实现相对比较复杂。

广度优先搜索与启发式算法

如前文所述，采用自顶向下的方法之后就不需要保证子树的等价集合先被计算出来， 因此可以使用广度优先的顺序自根节点起向下遍历执行搜索任务。 在 Calcite 的实现之中，对于自某一节点开始激发的匹配规则(RuleMatch)，将会先被压入队列(RuleQueue)之中等待执行。 这样就比较方便限制搜索的层数从而提前返回结果。

如同 A* 算法应用在寻路任务当中用来加速执行一样，在引入队列之后的 Volcano Optimizer 当中也可以使用启发式算法——某一匹配规则及其产生的等价集合可以具备一定的 Importance。 用优先队列就可以在使这些规则的搜索按照重要性从高到低的顺序执行。

某一匹配规则也可以将变化后的结果设定为极高优先级，从而直接胜出而不会被其他规则所取代， 另一种个方向是给结果设定 0.0 值作为优先级，此时这一分支在未来几乎不会在被继续探索。 这也是实现自顶向下搜索实现剪枝的一种方法。促进算法收敛也是使用Importance的原因之一。

在这一基础上，Calcite 实现的 Volcano Optimizer 支持如下三种算法终止条件:

  1. 时钟: 使用最大迭代计数或最大物理执行时间作为限制
  2. 成本阈值: 当优化方案的成本低于某个阈值是结束算法(相比原始成本或固定值)
  3. 规则穷尽: 当无法再应用规则获得新的关系代数结构的时候结束算法

Trait/Physical properties vector

前文提到，Volcano Optimizer 大致基于一个“成本最优假设”。 这一假设是在进行动态规划加速计算的基础之一。然而这一假设在一些情况下并不成立。 考虑下面的情况

Sort Join with Index

如图左边是对两个表进行 SORT JOIN 的关系代数。此时从 B 和 C 读入的数据直接按照储存顺序读取， 虽然成本很低但是是乱序的。这时就需要在 SORT JOIN 算子之中进行排序操作从而需要不少的计算量。 而系统如果利用索引进行读取，虽然不是再是顺序读取而有性能损失， 但是可以获得排序好的记录。这时在 SORT JOIN 算子只需进行合并操作即可， 整体的成本由于避免了全表排序反而更优。

也就是说，虽然两个输入的成本都变高了，但是由于引入了新的特性，整体执行反而更快。 这种问题在 Volcano Optimizer 当中使用 Physical properties vector 来解决。

在 Calcite 当中，这个东西称为 Trait。一个 RelNode 可以声明自己的 Trait， 人们也可以编写规则利用输入节点的 Trait 来优化执行。

在 Calcite 当中，具有不同 Trait 的优化方案虽然都在一个RelSet当中， 却按照相同 Trait 一类的方法分别组织在RelSubset对象里。 在进行方案成本估算和匹配规则应用等需要查询等价集合的情况下，不同的RelSubset会分别被处理。 这样的设计一定程度上解决了成本最优假设失效的问题。

典型的 Trait 包括记录是否有序、是否包含 NULL 值、字符串是否都短于某一特定值等。 利用 Trait 进行查询优化的逻辑十分复杂也需要小心处理。下图展示了一个简单却典型的 Trait 的用例: 如果一个子树的输出已经按照某一列被排序，则取消掉上层重复的排序算子。

Eliminate Sort

其他

前文分步骤解释了 Volcano Optimizer 的主要算法思想，在这里再结合 Calcite 的实现列举一些值得了解的事项：

  1. 在最初的 Volcano Optimizer 论文中，算法存在逻辑优化和物理优化两个步骤， 在前者中会尽量将所有逻辑算子变换和展开。这一做法在后续的 Cascades 论文以及 Calcite 的实现中并没有体现。后两者当中，逻辑变换的规则和物理变换的规则没有本质的差别， 两者会在一轮优化当中同时使用，以期待快速从逻辑表示转换为物理执行方案。
  2. 在 Calcite 当中，可以覆写RelNode的getCost方法为自行实现的算子指定成本计算的方法， 尽管 Calcite 的 Cost 类包括 rows、IO、CPU 等多个字段，但现阶段只会比较 rows 的大小。 因此需要考虑把其他方面的成本换算为行数。
  3. 在关系代数树上查找匹配的结构是优化过程中最频繁的操作。Calcite 实现的匹配方法十分简单： 如果一个节点和某一匹配模式的根结点相互匹配，则从该节点进行一次校验。 从实践来看此方法性能较好。
  4. Calcite 默认并不进行枚举式的优化方案计算，而是结合启发式算法进行有限的搜索， 因此也不一定能返回“成本最优假设”下的最优方案。

总结

本文介绍了基于关系代数对 SQL 查询进行优化的基本原理并结合 Calcite 项目详细介绍了 Volcano Optimizer 的设计思路。笔者认为，Apache Calcite 提供的 SQL 解析、优化和执行层十分有价值，不单是学习数据库相关逻辑的极好教材， 也足以应用在各种成熟的项目当中。

除了本文介绍的查询优化算法，在查询执行过程中还有很多其他很重要的优化方式，例如

  1. Vectorized Execution 通过元素在关系代数节点之间的获取批量化以及利用 SIMD 指令集优化提高并行性从而优化执行
  2. Query Compilation 通过将优化好的执行方案通过 LLVM 等工具编译成机器码极大地加速了解释速度。 实际上 Calcite 就利用了 Janino 库来将优化后的方案编译成 JVM Bytecode 来执行
  3. 利用索引信息和物化视图来加速结果的返回

以上每种方式都十分值得研究，希望以后有机会将相关的知识总结出来与大家一起探讨。