漫谈分布式系统 (20)：基于规则的优化

这是《漫谈分布式系统》系列的第 20 篇，预计会写 30 篇左右。每篇文末有为懒人准备的 TL;DR，还有给勤奋者的关联阅读。扫描文末二维码，关注公众号，听我娓娓道来。也欢迎转发朋友圈分享给更多人。

细节是负担，甩掉有代价

前面几篇文章，我们讲到，MapReduce 和 Spark 在引入 SQL 之后，诞生了 Hive 和 Spark SQL，大大提升了开发性能。

然后又讲到，受 Shuffle 性能优化的启发，对 SQL Join 的性能做了一些优化。

在讲 Join 性能优化的时候，虽然我没明说，但也能隐约感觉到一个不好的趋势。

那就是， SQL 这种声明式的语言，通过隐藏实现细节，减轻了开发成本。但也同样因为隐藏实现细节，失去了主动优化性能的可能 。

一条 SQL 性能的好坏，很大程度上，已经不受开发者的控制了。

这样也没错，毕竟开发者的水平参差不齐，都去手写 MR 和操作 RDD，肯定有人能写的性能很好，但大部分人恐怕都需要花非常多的时间去积累经验。

所以， 把性能优化的主动权交给 SQL 引擎，再集思广益，把常见的优化经验都统一实现掉，也不失为好的选择 。

细节是负担，甩掉有代价。但我们可以用经验来弥补这个代价 。

在 SQL 里，这些经验被总结为规则，这一类性能优化操作在查询优化器（Query Optimizator）里完成，也就是我们今天要讲的 基于规则的优化（Rule Based Optimization） ，简称 RBO 。

向旧技术取经

一个很现实又略显沮丧的事实是，计算机界尤其是互联网界的很多所谓新东西，都只是旧技术和新场景的组合，再套上个炫酷的名字而已，所谓新瓶装旧酒 。

虽然要解决很多我们前面文章讲过的问题，但分布式领域的 SQL，本质上也只是传统关系数据库的 SQL 在多机扩展下的实现而已。

但幸运的是，这也意味着，在传统关系数据库库里已经积累了很多年的经验，也可以继续在分布式 SQL 里用到。包括 RBO 。

上图是 Oracle 支持一些的 RBO Path。Oracle 会对查询语句按照支持的规则去解析和匹配，然后选择优先级最高的执行，编号越小，优先级越大。

以 Path 1 和 Path 15为例。当我们通过 Rowid 查询一条数据时，由于主键有索引，显然走索引会比全表扫描要快的多，因此会自动选择 Path 1 而不是 Paht 15。

只要把这些久经考验的规则依葫芦画瓢实现一遍，分布式下的 SQL 就有了基础了 RBO 了。

下面看下我们前面重点关注的 Hive 和 Spark SQL 的情况。

既然 RBO 是个非常套路固定的东西，而 Hive 作为 Apache 开源项目的代表之一，就没有选择造轮子，而是使用了著名的 Apache Calcite 作为优化器（包括下一篇要讲的 CBO）。关于 Calcite，我之前写过几篇文章，链接会贴在文末，这里就不重复了。

下面这张图，我截取了部分目前 Calcite 支持的 rules，感兴趣的可以自己去看实现，具体对应的是 Calcite 的 HepPlanner 和 org.apache.calcite.plan.hep 包。

而对于 Spark，我前面的文章也说过，Spark 是个非常有野心的项目。所以并没有直接用现成的 Calcite，而是造了个叫 Catalyst 的轮子。

在 Spark SQL 的 org.apache.spark.sql.catalyst.optimizer.Optimizer 类中，可以看到也定义了很多规则：

有了这些规则，Hive 和 Spark SQL 就能实现非常多的常见优化了，最基本的性能保证就有了，再差的新手写出的 SQl，性能也有底线了。

规则是怎么生效的

从编译原理中我们知道，一个 parser 对一段程序处理后，会输出一个抽象语法树（AST）。SQL 也是一门语言，最终要编译成底层执行引擎能处理的样子。

所以 RBO 的大致过程可以理解为， 通过应用不同规则，对 AST 做等价转换 。

上篇刚讲过 join，那就一起看一个 join 的例子，搭配一个最常规的规则 -- 谓词下推（Predict Pushdown）。

首先，有这么两张表：

create table user(id int, name string);

create table order(id int, uid int, item_id int);

查询语句是这样：

select

u.id as user_id, u.name as user_name, o.id as order_id

from

user u

join

order o

on

u.id = o.uid

where

u.id > 100;

初始解析完的执行计划，是先扫描两张表，然后 join 匹配数据，最后过滤出 u.id > 100 的数据。

而谓词下推，顾名思义，就是把判断条件下推到存储引擎，提前过滤掉不需要的数据，这样就能大幅提升性能。

画成示意图是这样：

我们用 explain 语句，来看下实际的执行计划。

在 Hive 里是这样，可以看到，两张表都先做了 Filter 操作，然后才 Join。

下面这个 Spark SQL 的图看的更清楚。

在 Analyzed Logical Plan 里，是在 Join 之后才 Filter。而经过优化后的 Optimized Logical Plan 里，就变成了分别先对两表做 Filter，然后再 Join。

类似 Predicate Pushdown 这样简单又实用的规则还有很多，常见的比如 Projection Pushdown，会在扫描表的时候就把不相干的列去掉；Filter Combine 会把多个 Filter 合并之后再去过滤，等等，限于篇幅，就不再举更多的例子了。

这样，通过对一系列规则的应用，不断地对 AST 做等价转换，直至找出最优的逻辑计划。然后就可以转换成物理执行计划，交给执行引擎去处理了。

RBO 的局限性

RBO 能发挥非常不错的优化效果，是因为汇集了大量经验，并具象化为一条条可执行的规则 。

但也正是这些规则，导致了 RBO 的局限性 。

因为规则是死的：

• 规则无法穷举，虽然可以逐步完善（人是活的），但总有覆盖不到的点，

• 规则可能矛盾，各自独立的规则，不会考虑和其他规则的关系，一旦矛盾，就很难取舍，

• 规则很难确定优先级，先应用哪个后应用哪个，可能产生不一样的优化效果，

• 规则对不同的数据可能产生差距巨大的效果，

• ......

举一个例子，我们都知道一个很简单的规则，如果一个列建了索引，当以这个列为查询条件时，应该走索引，而不是全表扫描。

但是，看这样一种情况，有一张公司人员表，其中有个建有索引的字段 gender。现在要查询男性员工的地区分布，但是这个公司是个做苦力的工厂，超过 90% 的员工都是男性。那这个时候先查索引找到所有男性员工，再去查地区分布，性能就远不如直接全表扫描了。

很显然，RBO 并不能解决所有性能优化问题，甚至可能帮倒忙。

究其根本原因， 任何规则 -- 不仅是 SQL 优化里的规则 -- 作为经验的积累，都必然不能解决所有问题。因为经验是人对事物共性的归纳，在归纳的过程中必然存在样本不足、信息损耗和过度拟合的情况。这是经验的局限性，在表象上的体现，就是不灵活或者有时候失灵了 。

TL;DR

这篇文章，我们粗略了解了基于代价的优化是怎么一回事，简单提炼要点如下：

• SQL 通过隐藏实现细节，提高了开发效率，但也失去了主动优化性能的可能，

• 好在有些通用的性能优化手段，可以统一实现，即所谓基于规则的优化（RBO），

• Oracle 等传统关系数据库已经积累了非常丰富的 RBO 经验，分布式 SQL 只需要照做即可，

• RBO 本质上就是通过应用规则，对 AST 做等价变换，直至找出最优计划，

• 但 RBO 是基于经验的，而任何经验都是有缺陷的，如对不同的数据内容会产生悬殊的结果。

所以，我们需要另外的思路，来继续 SQL 性能优化。 另一种不像 RBO 这样间接归纳的思路，另一种更加直接却又灵活的思路 。

下一篇，我们一起了解下基于代价的优化（CBO）。