背景

PolarDB-X 是一个存储计算分离架构的分布式 HTAP 数据库，包含计算节点（Compute Node, CN）和数据节点（Data Node, DN）。存储计算分离架构中，CN 节点获得了接近无限的 scale out 能力，代价是引入了 CN 与 DN 通信的网络开销。下图以TPCH 测试集的部分 SQL 为例，对比了下发查询到 DN 执行（下推）和拉取数据到 CN 节点执行（不下推）的执行时间。

注：测试基于1.0早期版本，为了模拟下推 SQL 在 DN 上的执行策略，CN 未开启全部优化规则

可以看到 Q2,Q11,Q13,Q17 下推后返回的结果集显著减小，执行时间缩短。也就是说，通过将查询直接下发到 DN 上执行，CN 仅做结果转发，可以减少 CN 和 DN 间多次网络交互带来的延迟。我们把这种“将查询下发到 DN 上执行”的能力，称为计算下推。

“下推”是数据库管理系统优化查询性能的一种思路，单机数据库支持谓词下推和投影下推，通过将 Filter 和 Project 算子在算子树中向下移动，提前对行/列进行裁剪，减少后续计算处理的数据量。Filter/Project 下推基本上不会产生副作用，因此单机数据库通常在 RBO 中完成这两项优化。对于分布式数据库，计算下推能否继续沿用单机数据库的执行思路？从三个角度可以看出区别

下推哪些内容?

分布式数据库中，计算下推的目标是减少网络交互产生的开销，因此需要能够支持包括 Join/Agg/子查询 在内的全部种类的算子。

哪种场景需要计算下推？

存储计算分离架构下，CN/DN 节点部署在不同类型的机器上，CN 偏重计算，DN 偏重存储。TP 类查询侧重吞吐，对计算资源消耗不高，适合下发到 DN 上执行，提供与单机数据库接近的执行效率。而对于计算密集型的 AP 类查询，下推过多复杂算子到 DN 节点，反而可能导致查询性能下降。上图中 Q15 就是一个例子，下推 Agg/Join 后中间结果仍有50w+，网络开销没有减少，同时受制于 DN 节点有限的计算，整体执行时间不降反升。

计算下推不是“银弹”，合理使用才能获得最大的收益。PolarDB-X 提供面向 HTAP 的 CBO，能够基于代价充分考虑存储(如存储的计算模型)及数据(是否具有索引)等特性，准确评估计算下推对查询性能的影响。受篇幅限制，本文主要介绍枚举算法，代价估计相关内容，请关注专栏后续文章。

RBO 还是 CBO ？

分布式数据库中的计算下推通常在 CBO 完成。与单机数据库在 RBO 中支持下推的方案相比，CBO 能通过代价评估，避免由于过多下推复杂算子导致的查询性能下降。具体来说，CBO 由 计划空间、枚举算法、代价估计 三部分组成。在 PolarDB-X 的实现里，枚举算法模块中增加了算子下推的规则，代价估计模块能够充分考虑存储和数据的特性给出下推后计划的代价，CBO 进行计算下推的过程可以简述为 “在枚举过程中尝试下推各个算子，并通过代价比较得到最优解”。

PolarDB-X 中 RBO 和 CBO 接收相同算子构成的逻辑计划作为输入，CBO 通过枚举算法生成下推的执行计划时，使用与 RBO 相同的变换规则。因此，为了便于描述，下文从 RBO 视角出发进行阐述。

查询改写

查询改写的两个目标：

1. 查询改写优化：子查询消除，外链接消除，条件简化 等
2. 算子下推：将查询划分为可以下发到 DN 上执行的分布式查询（Distributed Query）和在 CN 节点中执行的本地查询（Local Query）两部分。其中分布式查询涉及的算子统一封装在 LogicalView 算子中

算子下推包括：

1. 谓词下推/列裁剪：将 Filter / Project 算子下推至 MySQL
2. Join Clustering：将 Join 按照拆分信息重排保证尽可能下推
3. Join 下推：根据拆分信息下推 Join
4. Sort 下推：将 Sort 拆分成两阶段的 Sort + Merge 并下推
5. Agg 下推：将 Agg 拆分成两阶段的 PartialAgg + GlobalAgg 并下推
6. 子查询下推：将 Semi/Anti Join 按照拆分信息重新改写为子查询下推

查询改写框架

采用启发式搜索，规则分为多组，执行时按顺序应用所有规则组，组内规则重复迭代，若一轮迭代结束后没有任何规则被应用，该组规则执行完成

上图以 PushJoinRule 为例，展示了框架的工作流程

• 规则中定义了匹配怎样的算子结构，PushJoinRule 匹配 Join(LogicalView(黄), LogicalView(红))
• 查询改写流程首先遍历算子树，在匹配成功的算子上应用规则，将 Join 下压到 LogicalView(黑) 中
• 更新逻辑计划后进入下一轮迭代，三次应用 PushJoinRule 后所有算子都压入 LogicalView，不再命中任何规则，查询改写结束

算子下推

子查询消除/下推：与单机数据库相同，PolarDB-X 通过将子查询转换为 Semi / Anti Join 来消除子查询。使用PushJoinRule 找到能够下推的 Semi / Anti Join，将其还原为子查询后压入 LogicalView。根据子查询类别的不同，有不同的改写策略，详见：子查询漫谈

谓词下推/列裁剪：将 Filter / Project 算子压入 LogicalView，下推的 Filter 还会用于后续的分区裁剪

Join 下推：

• PushJoinRule：当 Join 连接两个 LogicalView（即 Join 的左右子树都已完全下推）时，结合拆分信息判断并完成 Join 算子下推
• Join Clustering：当查询中包含超过两张表时，可能因为书写顺序导致能够下推的两张表在 Join graph 中并不相邻，进而导致 PushJoinRule 不能正常完成下推。Join Clustering 以 MultiJoin 算子作为中转，将能够下推的表相邻排列，达到最大化 Join 下推。详细过程见下图

Agg / Sort 下推: 将 Agg / Sort 算子压入 LogicalView，若 LogicalView 需要扫描多个分片，在上层保留 GlobalAgg / MergSort

算子交换：

• 算子下推是一个 bottom-up 的过程，不可下推的算子会阻挡其上的所有算子的下推，为了最大化下推算子，需要交换算子在逻辑计划中的位置。PolarDB-X 支持 Filter-Join, TopN-Join, Agg-Join, Filter-Agg, Sort-Project, Join-TableLookup 等多种算子交换规则。
• JoinTableLookupTransposeRule：PolarDB-X 支持 全局二级索引，若查询中引用的列未被索引覆盖，则需要引入 TableLookup 算子来表示回表操作。由于索引表和主表的拆分维度不同，TableLookup 算子无法下推，上层算子与 TableLookup 交换后才能继续下推。详细过程见下图

执行优化与分区裁剪

面向物理 SQL 的多阶段优化

PolarDB-X 1.0 中算子下推完成后，还需要将分布式查询从算子树转换为 SQL 语句下发给 MySQL 执行，此时算子树的结构将决定物理 SQL 的结构。为了避免在物理 SQL 中引入多层嵌套子查询进而影响 MySQL 上的执行效率，下推过程被划分为算子下推、算子交换和分区裁剪三个步骤，尽可能保证下推后的算子树在结构上与原始 SQL 相同。下图以一个三表 JOIN 为例，展示通过多阶段优化完成下推的过程

分区裁剪

得到分布式查询的算子树之后，还需要进行分区裁剪，也就是确定物理 SQL 应当下发到哪些分片上。PolarDB-X 的分区裁剪模块参考了论文 "Query Optimization by Predicate Move-Around"，支持全类型算子上的条件推导，精确裁剪冗余分区，降低执行/数据传输开销。下图以子查询为例，展示条件推导过程

业界实现

DN 对算子的支持

存储计算分离架的分布式数据库，要做计算下推，首先需要 DN 具备执行计算的能力

• CockroachDB：使用 KV 存储（Pebble）作为 DN ，支持 Filter/Limit 算子，不支持 Grouping/TopN/Join 算子。
• TiDB：DN 同样为 KV 存储（TiKV），参考 HBase 在 DN 上增加 Coprocessor，支持 Filter/Limit/Grouping/TopN 算子，支持部分常用表达式。不支持 Join 算子。
• YugabyteDB：DN（DocDB）集成了 PostgreSQL 的查询引擎，支持全部算子和表达式。
• PolarDB-X：DN 兼容 MySQL，支持全部算子和表达式。

算子下推

如上文所述，计算下推是通过变换算子树，逐个下推算子，找到最大可下推子树的过程

• 算子下推，是在算子树中 bottom-up 的逐个下压算子
• 对于多表 Join 的情况需要考虑调整 Join 顺序，将可以下推的表放在一起重组成左深树的结构，使得下推能够继续进行。
• 如果出现某个算子不能下推，后续算子需要通过算子交换来继续下推

• TopN-Join 和 Agg-Join 交换判断条件较为复杂，但部分场景下能够带来显著的性能提升。
• 支持全局索引的数据库中，回表算子经常出现，用于连接索引和主表。由于两者拆分维度不同，回表算子不能下推，其他算子需要与回表算子交换后才能继续下推

• 对于优化器中判定为不可下推的算子树，执行前还需要带入参数计算出需要扫描的 DN 分片，此时如果算子树中的所有表都落在相同的分片，则整个算子树依然可以下推，这个过程称为 Colocated push down

下表简单对比业界产品的一些优化选择，信息来自公开文档

总结

存储分离架构的分布式数据库，CN 与 DN 通过网络交互，增加 scale out 能力的同时引入了网络开销。单机数据库支持谓词下推和投影下推，优化产生的副作用极小，通常在 RBO 中执行。分布式数据库为了降低网络开销，需要下推TopN、Agg、Join 等更加复杂的算子。需要增加更多种类的下推规则，并在 CBO 中找到代价最低的计划。PolarDB-X 的实现中，DN 节点支持全类型算子，CBO 结合存储和数据的特点进行代价评估，支持 Join Clustering 、回表算子交换、Predicate Move-Round 等优化技术，能够合理的计算下推大幅降低网络开销，提升查询性能。

参考文献

[1] Query Optimization by Predicate Move-Around

[2] Query Optimization Techniques for Partitioned Tables

[3] Eager Aggregation and Lazy Aggregation

[4] The MemSQL Query Optimizer: A modern optimizer for real-time analytics in a distributed database

[5] Spanner: Becoming a SQL System

[6] Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources

[7] https://blog.yugabyte.com/5-query-pushdowns-for-distributed-sql-and-how-they-differ-from-a-traditional-rdbms/

[8] https://github.com/cockroachdb/cockroach/blob/master/docs/design.md#distributed-sql