共计 5856 个字符，预计需要花费 15 分钟才能阅读完成。
6 月 19 日，Greenplum 原厂内核研发郭峰和大家直播分享了《深入浅出 Greenplum 内核》系列直播的第三期《Greenplum 内核揭秘之查询优化》。没有参加活动的小伙伴也不用失望，我们已经将视频上传至 Greenplum 中文社区 B 站频道，通过点击这里即可观看。本文概括了文章的精华内容，欢迎留言交流。
直播视频（腾讯频道）
https://v.qq.com/x/page/i3107m0gi47.html
本文将主要包括两大部分，第一部分是查询优化器的介绍，第二部分是查询优化的具体处理过程，整个过程将被分为四个阶段：查询树的预处理，扫描 / 连接优化，扫描 / 连接之外的优化，计划树的后处理，我们将在本文中一一展开。
首先我们来介绍一下查询优化器是做什么的。对于给定的查询语句，查询优化器会找到“代价”最小的查询计划。这里的“代价”在不同的应用场景会有不同的维度或者是定义，比如可能是找到一个执行时间最短，或者找到一个执行占用资源最少的查询计划。
对于同一个查询语句，一般可以由多种方式去执行，因此查询优化器尽可能去遍历每一种可能的执行方式，找到“代价”最小的执行方式，并把它转换成可执行的计划树。
下图是一个例子，A JOIN B on a.i = b.i，对于这个 Query，我们有几种执行方式，这里我们来介绍三种执行方式。第一种执行方式中，我们可以先对 b 做一个索引扫描，再对 a 做一个顺序扫描，再去执行一个 Nested Loop。第二种执行方式中，我们可以对 a 做一个顺序扫描，把扫描的结果建一个哈希表，再对 b 做一个顺序扫描，最后用 Hash Join 得到一个结果。第三种方式是对 a 做一个顺序扫描，根据 a.i 为序的键值做一个 sort 排序，再对 b 做一个索引扫描，最后做一个 Merge Join，得到最后的结果。
大家可以看到这三种执行方式，后面的“代价”（cost）信息是不同的，优化器会根据 cost 信息选出一个“代价”最小的方式，形成最后的执行方案。
前面介绍了查询优化器，这里我们再来介绍一下查询计划。一个查询计划就是一个由计划节点组成的树，每个计划节点代表了一个特定类型的处理操作，计划节点中包含了执行器执行所需的全部信息。在执行时，计划节点产生输出元组，一般来说，扫描节点从数据表中获取输入元组，大部分其他节点从它们的子计划节点中获取输入元组，并处理产生输出元组。
计划节点可以分为三个类型，
- 扫描节点
包括顺序扫描，索引扫描，位图扫描等；
- 连接节点
包括 Nestloop，hash，merge 等；
- 非 SPJ 节点
包括 Sort，aggregate，set operations（UNION 等）
下面我们再来看一个例子。对于例子中的 Query，查询计划就如下图所示，其中 Seq Scan on a 和 Seq Scan on b 都是扫描节点，扫描的结果去做 Hash Join，是一个连接节点。Hash Join 之上，做了一个 HashAggregate，这是一个聚集节点，最后再对聚集的节点做排序，这是一个排序节点。
在讲完查询优化和查询计划，我们再来看一下 Greenplum 查询优化的具体处理过程。Greenplum 查询优化主要包括四个阶段，具体过程请看下图。
接下来我们来逐一解析这四个阶段分别做了什么。
1. 简化常量表达式
在表达式中，有一些常量表达式，在做计划时，可以对其做一些简化，例如对于函数表达式，可以对下图的两种类型做简化：
- 函数本身是严格的
如果一个表达式的输入是 NULL，输出也是 NULL 或者是 FALSE，在这种情况下，我们就可以说这个函数就是“严格”的。我们可以通过 CATELOG 表中的属性，来查看某个函数是否是严格的，如果函数本身是严格的，并且输入的参数中包含一个 NULL 值，在做计划时，就可以用 NULL 来代替这个函数表达式。
- 函数本身是“IMMUTABLE”
函数是”IMMUTABLE”是指如果输入是固定的，则输出也是不变的。我们也可以通过 CATELOG 表中的属性查看这个函数是否是“IMMUTABLE”。如果函数本身是“IMMUTABLE”的，并且输入参数全都是常量，则可以先求值，并用常量去代替函数表达式。
对于布尔表达式，在一些情况下也可以坐简化，比如下图的两种情况。
对于 CASE 表达式，如果某个分支条件是一个常量的话，也可以做简化。比如下图的这个例子中的 2 +2=4，可以把整个 CASE 表达式简化为 x +1。虽然在 else 里与 1 /0，但是由于我们做了简化，因此表达式就不会报这样的除 0 的错误。
我们为什么要在做计划这个阶段去简化常量表达式呢？通过简化常量表达式可以带来以下好处：
- 仅需做一次计算，而不是为每行元组都做一次计算
- 视图展开和函数内联都可能会带来新的常量表达式简化的机会
- 简化常量表达式也为统计信息类的函数减少了计算量
2. 内联简单的 SQL 函数
查询树的预处理在早期做的第二件事是内联简单的 SQL 函数，比如下图的例子中，SELECT incr4(a) FROM foo 可以内联成 SELECT a+4 FROM foo。而这里不止做了个内联，还做了个常量表达式的简化。
通过内联简单的 SQL 函数，可以
- 避免 SQL 函数调用的代价
- 为简化常量表达式提供新的机会
3. 提升子链接
子链接是指出现在表达式中的子查询，通常出现在 WHERE 或者 JOIN/ON 子句中。
比如下面这个例子中，子查询出现在了一个 WHERE 子句中，因此就被归类为一个子链接，在这种情况下，我们就可以把一个 EXISTS 的子链接变成一个 SEMI JOIN。
SELECT * FROM foo WHERE EXISTS (SELECT 1 FROM bar WHERE foo.a = bar.c);下图是转换之前的查询树，从图中我们可以看到，EXISTS_SUBLINK 在转换之前出现在 WHERE 的约束条件中。
在转换后，这个子链接就变成了一个 SEMI JOIN，这就是一个子链接的提升过程。
4. 提升子查询
子查询一般是以范围表的方式存在，通常出现在 FROM 子句中。在例子中的子查询出现在了 FROM 后面，在提升后，这个查询语句是对三个表做内连接，我们可以以任何顺序对这三个表做内连接，同时，我们观察到 foo 和 bar 之间有个连接条件，因此我们想先对 foo 和 bar 做内连接，再对 baz 做连接，从而得到一个更好的查询计划。而在提升之前，我们就不得不对 bar 和 baz 做连接。
SELECT * FROM foo JOIN (SELECT bar.c FROM bar JOIN baz ON TRUE) AS sub ON foo.a = sub.c;下图是提升之前的查询树的内部结构图。我们可以看到 SUBSELECT 是属于父查询的一个范围表中的一项。
而提升之后，我们可以看到三个表就变成了三个内连接的关系，这样我们就可以对三个表任意的交换顺序，从而找到一个代价最低的查询计划。
通过把子查询提升到父查询之中，就可以使子查询参与整个计划搜索空间，从而找到更好的执行计划。否则，我们不得不为子查询单独做计划，然后在为父查询做计划时把子查询当做是一个“黑盒子”。
5. 消除外连接
消除外连接也是在预处理过程中做的一项很重要的事情。首先我们来看一下下图的两个表：学生表和选课表。学生表中我们有两个学生，选课表中我们有一个学号为 1 的学生，选了编号为 100 的课，得了 60 分。如果我们希望找出哪个学生选了哪些课，得了多少分，我们会对这两个表做连接。如果我们用 INNER JOIN 来做连接，则得到第一个表格的结果，只有一名选了课的学生的信息。如果对 LEFT JOIN，我们发现不仅有已经选了课的 1 号学生，2 号学生虽然没有选课，但是也出现在了结果中，只不过他的选课我们用 NULL 来填充。如果在这个左连接后面加一个 WHERE 条件，结果和 INNER JOIN 一样。在这种情况下，我们就可以把 LEFT JOIN 变成一个 INNER JOIN。
总结一下：外连接的上层有“严格”的约束条件，且该约束条件限定了来自 nullable side 的某一变量为非 NULL 值，则外连接可以转换成内连接。
SELECT ... FROM foo LEFT JOIN bar ON (...) WHERE bar.d = 42;现在我们来看消除外连接的第二种情况。首先我们做了个 LEFT JOIN，则出来两个结果，其中没有选课的学生的选课信息为 NULL。接着我们又做了个 LEFT JOIN，并加了个 WHERE 条件，限定 enrolled.sid is null，此时就把前面的结果中选课信息不为 NULL 的结果过滤了。此时这个 LEFT JOIN 做的就是 ANTI JOIN 的事情。
当我们查看语句的计划，我们会发现 Greenplum 已经把它变成了一个 ANTI JOIN。这里就是消除外连接的第二种情况。
外连接本身有“严格”的连接条件，且该连接条件引用了来自 nullable side 的某一变量，且该变量被上层的约束条件限定为 NULL 值，则外连接可以转换成反半连接(Anti Join)。
SELECT * FROM foo LEFT JOIN bar ON foo.a = bar.c WHERE bar.c IS NULL;第一阶段：查询树预处理（后 期）
在早期，我们对查询树本身做了一些转换，在查询树预处理的后期，我们会做以下的事情：
- 分发 WHERE 和 JOIN/ON 约束条件
- 收集关于连接顺序限制的信息
- 消除无用连接
- etc.
1. 分发约束条件
我们来看下分发约束条件，一般来说，我们期望可以尽可能的下推约束条件。如果只有内连接，我们可以把一个约束条件下推到它的“自然语义”位置。如果存在外连接，那么约束条件的下推可能会受到阻碍，从而无法下推到它的“自然语义”位置。对于被外连接阻碍的约束条件，我们通过让它的“required_relids”包含进外连接所需要的所有基表，从而避免该约束条件被下推到外连接之下。
首先，我们来看一下哪些约束条件会被外连接阻碍。先看第一种情况，左边的例子中，这个约束条件只引用了一个 student 表，那我们是否可以把它下推到对这个 student 表的扫描上呢。在 Greenplum 的计划中，student.sage = 18 这个约束条件并没有被下推到对 student 的扫描上，而保留在了 student 和 enrolled 的外连接做 JOIN 的这一层，这就是被外连接阻碍的一个例子。
在右边的 Query 中，我们做了一些改动，用了一个子查询的形式，通过查看计划，我们成功的将 sage=18 下推到了 student 这张表上，用这个计划进行执行，我们发现生成结果和左边的结果不一样。
如果外连接本身的连接条件引用了 non-nullable side 的表，那么该连接条件不能下推到外连接之下，否则我们可能会丢失一些 null-extended 元组。
我们再来看一下会被外连接阻碍的第二种情况。首先我们看一下左边，我们可以看到这个约束条件只引用了 enrolled 这个表。那我们是否可以把这个约束条件下推到对 enrolled 表的扫描上呢。当我们看查询计划时，我们发现，它并没有这么做，而是保留到了连接这一层。执行后，我们发现它的结果只有一行结果。
当我们如上图右边所示，变换一下 SQL 语句，希望把约束条件下推，我们发现在 plan 中，成功的把约束条件下推到对 enrolled 表的扫描上，但是执行结果和左边不一样，多了一行结果。
如果外连接上层的约束条件引用了 nullable side 的变量，那么该约束条件不能下推到外连接之下，否则可能会多出一下 null-extended 元组。
2. 连接顺序限制
当有外连接存在时，就不可以随意的交换连接顺序，因为外连接会在一定程度上限制连接顺序的交换。非 FULL-JOIN 可以和一个外连接的左端 (LHS) 自由结合，通常非 FULL-JOIN 不可以和外连接的右端 (RHS) 结合。大家可以看一下下图的两个例子。在左边的例子中，大家可以从查询计划中看到，a 和 c 先做了个 inner join，然后在和 b 做了个 left join。而右边的例子中，大家可以看到查询计划中，虽然 a 和 b 并没有连接条件，依然对 a 和 b 做了 left join，再和 c 做了个 INNER JOIN。
3. 消除无用连接
在预处理的后期，做的另一个事情就是消除无用连接。如果满足下图中的三个条件，无用连接可以被消除。下图的这个例子中，这个 LEFT JOIN 就可以被消除。
第二阶段：扫描 / 连接优化
在这一阶段中，主要处理查询语句中 FROM 和 WHERE 部分，同时也会考虑到 ORDER BY 信息。这一部分都是由“代价”来驱动的。
扫描 / 连接优化是这样做的：
- 首先为基表确定扫描路径，估计扫描路径的代价和大小
- 利用动态规划算法，搜索整个连接顺序空间，生成连接路径
- 在搜索连接顺序空间时，需要考虑到由外连接带来的连接顺序的限制
在动态规划的过程中，
- 首先为每一个基表生成扫描路径
- 为所有可能的两个表的连接生成连接路径
- 为所有可能的三个表的连接生成连接路径
- 为所有可能的四个表的连接生成连接路径
- …
- 直到所有基表都连接在了一起
大家可以发现，这个动态规划是 level by level 来完成的。下图是 SELECT * FROM A JOIN (B JOIN C ON B.j =C.j) ON A.i = B.i 的动态规划过程。
其实这个过程，“代价”是非常高的，n 个表的连接，理论上有 n! 个不同的连接顺序，遍历所有可能的连接顺序是不可行的。我们使用一些启发式办法，减少搜索空间。对于不存在连接条件的两个表，尽量不做连接，把一个大的问题，分解成多个子问题。比如下图中的这个例子中，我们将 10 个表的连接变成了多个小问题。再对每个子问题做动态规划的过程，降低了复杂度。
第三阶段：扫描 / 连接之外的优化
在这个阶段，我们会做以下的处理：
- 处理 GROUP BY, aggregation, window functions, DISTINCT
- 处理集合操作，UNION/INTERSECT/EXCEPT
- 如果 ORDER BY 需要，添加最后的 SORT 节点
- 添加 LockRows, Limit, ModifyTable 节点
做完这一步，我们几乎得到了一个完整的计划树。但我们还需要做一些后处理。
第四阶段 计划树的后处理
在这一阶段，我们需要把代价最小的路径转换成计划树，并且调整计划树中的一些细节：
- 展平子查询的范围表
- 把上层计划节点中的变量变成 OUTER_VAR 或是 INNER_VAR 的形式，来指向子计划的输出
- 删除不必要的 SubqueryScan, Append 等节点
做完这一步，我们就得到了完整的计划树，并可以将该计划树交予执行器去执行。
这就是查询优化的所有内容，欢迎大家继续关注《深入浅出 Greenplum 内核》系列后面的直播内容。
