MegaWise技术初探：面向异构计算的查询优化与编译

近两年，我们团队在研发基于异构计算的新型OLAP数据库系统--MegaWise，这是一个处于“异构计算”与“大数据分析”交叉领域的工作。当前该系统已经完成0.5.0版，希望借此文介绍我们现有的一些技术探索。

1．为什么要在“异构计算”与“大数据分析”上面做工作

我想以一个真实的案例展开今天的内容。在今年的二月份，我们遇到一个做电信行业数据分析的客户，他们讲了这样一个问题：“我们现在主要的计算任务是上下行请求包与响应包的匹配，做一个省的数据，用了800台机器。流进来的数据太多了，800台机器没干别的，就做匹配。我们也尝试去做用户画像、网络调度优化，但实时的运算量太大了，按现有的技术，仅扩充集群的投入就盖过预期收入了，没法做。”

现在不少行业都在进行数字化转型，大家都认识到数据是新时代的石油。但挖油这个事情如果可行，必须满足一个硬性条件，即收入至少能够盖住挖油的设备成本与维护成本。除此之外，数据这种新型石油的价值还具有时效性，即数据自产生起，其蕴藏的价值随时间流逝快速递减。

相比传统的CPU并行计算，异构计算大的优势是更高的运算效率、更高的性价比与更低的延迟。从这个角度看，异构加速技术在降低数据分析成本、提高数据挖掘速度两方面均有巨大潜力。在经济可行性的层面，异构计算犹如一把钥匙，这把钥匙可以极大的扩展各行业数字化的疆土。

但异构计算绝非免费午餐。异构加速器在提供硬件红利的同时，也暴露了大量复杂性。在OLAP数据库这类数据分析系统中，异构加速器的复杂度需要在查询优化、编译、调度、内存管理等多个层面进行考虑，几乎贯穿了数据分析的整个过程。

2．系统架构

图1 MegaWise系统架构

为了方便讨论，这里先给出MegaWise的整体架构。MegaWise主要包含计算与数据管理两方面内容。如图1所示，计算流程由Master与Worker共同完成。来自客户端的SQL请求经由Master的解析器（Parser）、查询优化器（Optimizer）与调度器（Scheduler），分别完成对SQL语句的三次转换。其中Parser完成SQL语句串到抽象语法树（AST）的转换。Optimizer完成抽象语法树到执行计划（Plan）的转换。这里执行计划是一个DAG，其中每个节点表示一个算子，节点间的有向连接表示算子间的依赖关系。根据关系代数的规则、优化规则与代价模型，Optimizer负责找出具有优（或局部优）执行效率的计划。后Scheduler完成执行计划到任务图的转换。这里任务图是与执行计划同拓扑的DAG，Scheduler在任务图中增加了运行时语义，如操作数的位置描述、算子的执行上下文等。

在调度与执行的过程中，Scheduler以数据并行的方式将每个算子的计算子任务发送至Worker。Worker中的算子编译器（Operator Compiler）根据算子描述编译IR及目标代码。Task Scheduler根据数据局部性选出若干计算子任务，将其推送至执行流水线（Execution Pipeline）。执行流水线包括元数据准备、数据准备、算子编译、内核执行、处理输出等阶段，各计算子任务在流水线中以多阶段的方式驱动执行。

数据管理主要包含元数据服务（Metadata Provider）、数据缓存、存储引擎对接三部分。在数据缓存的设计中，我们采用列式存储，以Apache Arrow为基础，在其上构建缓存系统，以支撑主存层与GPU显存层的数据服务。

鉴于篇幅，本文主要介绍查询优化与算子编译的相关技术，这也是我个人觉得很有意思的部分之一。

3. 基本问题与基本思路

异构计算架构与通用计算架构明显的区别是提供了多种运算设备，而MegaWise需要回答的两类基本问题是：

1） 如何为具有不同负载特征的计算任务选择适合的运算设备。

2） 如何将计算任务组织成适合某种运算设备的形式。

图2 CPU与GPU的计算流程

图2对比了CPU与GPU的计算流程。相比于CPU，GPU可以对运算进行加速，但会产生主存-显存间数据拷贝及启动kernel的开销。因此，基于GPU实现的算子通常适合运算密集型任务，基于CPU实现的算子通常适合小任务以及访存密集型任务。这几类负载特性通常可以在查询优化器中得到有效处理：面向典型负载构建优化规则，如果任务满足负载特性，则按照优化规则选择适合的运算设备。

基于规则的简单分类对于典型负载虽然有效，但在实际的数据分析场景中往往难以充分发挥异构计算的能力。在生产环境下，数据量级通常在百GB以上。因此对于运算密集型任务，即便采用了GPU加速，任务的执行时间依然较长。而在现实情况中，主存-显存间数据拷贝时间与GPU运算时间在同一个量级或拷贝时间比运算时间高一个量级的情况非常普遍。面对这类负载，需要考虑对计算任务进行重新组织，从而更好的适应GPU的计算流程。在MegaWise中，我们主要以算子融合的方式对任务进行重组，通过CodeGen将连续的算子串动态编译成一个融合算子，从而避免算子间中间结果的产生以及主存-显存间的数据拷贝。

这里以一个例子综合讨论上述情形。考虑如下SQL：

这条SQL描述了一个地理信息查询的场景。给定时间区间、地理范围、目标的特征向量，要求在给定的时空范围内，找出与目标相似度大于0.9的记录并计数。为方便讨论，这里暂不考虑分区与索引。

这条SQL在经过Parser解析后，主要包含3个过滤算子和1个聚合算子：

1） SCAN_0：time > t_begin AND time < t_end

2） SCAN_1：ST_DWithin (location, given_location, 10000)

3） SCAN_2：InnerProduct (feature, given_feature) > 0.9

4） AGG：count

首先考虑算子内的计算任务重组。在SCAN_0中，需要按time列进行过滤。其中时间类型的比较可以通过GPU进行加速。然而我们不想分别计算time > t_begin 与 time < t_end两个表达式，因为这意味着中间会产生两个bitmap过滤表，并需要对两个过滤表进行&操作，以完成time > t_begin AND time < t_end。通过CodeGen，我们可以对两个过滤条件进行合并，从而减少kernel launch的次数与中间数据的产生。类似的， SCAN_2中特征相似度的计算与其后的比较操作也可以进行合并，从而提高GPU处理效率。

算子间的任务重组主要是算子融合。例子中SCAN_2与AGG可以安全的融合。融合后的算子在一个kernel内连续完成InnerProduct、>、count三个操作。

查询优化器给出的执行计划如图3所示：

 图3 执行计划示意

SCAN_0与SCAN_1为GPU算子，计算过程中将表达式的输入相关列拷贝至显存，并输出bitmap作为过滤条件。SCAN_0与SCAN_1后面紧接FILTER算子。FILTER是CPU算子，负责按照bitmap对列数据进行选取并重新组织成稠密形式。SCAN_2+AGG是一个GPU的融合算子，输入特征向量并计算出部分计数。后的AGG REDUCE将所有子任务的计数进行合并，输出终结果。

4．SIMD与算子融合

SIMD是GPU算子融合的核心问题。在上述例子中，从语义正确性的角度看，是可以将SCAN_0、SCAN_1、SCAN_2、AGG四个算子融合成一个算子的。但从执行性能的角度看，是否应该做融合在很大程度上依赖于数据分布。

假设我们对原始数据预先建立了时空分区。在进行数值运算前，原始输入会先根据分区条件进行一遍过滤。因此，在被筛选出的分区中进行SCAN_0、SCAN_1，过滤比例会比较低。在运算层面看，大多数数据可以通过SCAN中的if条件，因此是SIMD友好的。在这种情况下，将SCAN_0、SCAN_1、SCAN_2、AGG融合成一个算子是合理的。此时只需将相关数据列同时送至GPU，并在一个kernel内完成所有的计算步骤。

本例中，决定是否做算子融合只需参考各分区中time、location两列数据的histogram。实际的算子融合组合比较复杂，如SCAN-SCAN，SCAN-AGG，SCAN-HASH，JOIN-AGG，SORT-LIMIT，SCAN-LIMIT，JOIN-JOIN，以及上述组合的嵌套组合。其中SCAN、JOIN等算子因为包含if分支，会导致融合计算步骤的提前终止，在融合深度过大后， GPU利用率会显著下降，见图4。

图4. SIMD vs. 算子融合

在查询优化器中，可以基于各数据列的histogram估计算子运算中的分支（divergence）比例，从而确定算子融合的边界。部分情况下，还需要考虑中间结果行数，特别是有JOIN算子出现的情况。以JOIN-AGG或JOIN-JOIN为例，如果前面JOIN的结果较多，那么将其与后续AGG或JOIN做融合是合理的，这将避免中间结果的产生，扩大in-GPU JOIN的适用范围。

5．RBO与CBO

MegaWise的查询优化主要分为逻辑层与物理层。逻辑层的工作与传统的优化方法基本相同，如查询重写、谓词下推、调整JOIN顺序、子查询展开等。但由于需要考虑异构计算带来的变化，剪枝条件会做部分调整。

物理层的优化需要深度考虑异构计算的相关特性。与传统方案相比，主要在三个层面发生显著变化。

1） 扩展代价模型。在代价模型中，需要考虑异构计算设备在算力、访存带宽上的差异，并要考虑运算流程上的额外开销。

2） 考虑多种运算设备。针对不同的运算设备，我们为每种算子构建了多种物理实现。由于算法与运算设备的差异，各物理实现的适用范围相互交错。算子物理实现的选择主要以基于规则的方式完成。

3） 考虑算子融合。在物理层，我们构建了算子融合的组合表，根据可行的组合规则对查询优化的搜索空间进行展开，并根据2中所述规则为各种可能的组合选择适合的物理实现。

6．执行计划的动态调整

执行计划的优化失效是我们现在正在解决的一个问题，虽然这部分工作目前还没有完成，但我认为这个议题值得放到文中进行讨论。

在异构加速的OLAP中存在这样一类负载，这类负载涉及的数据处理量大而且SQL复杂。在系统层面看，SQL复杂意味着执行计划DAG中各算子节点间的依赖链较长，数据处理量大意味着数据并行的过程中子任务较多，每个算子的执行时间较长。

面对这类负载，执行计划中优化策略的准确度直接决定了异构计算的加速效果。然而在查询优化中，cardinality的估计误差通常以指数式放大，因此在四到六个算子后给出的优化策略基本上不会很准。如果执行计划的DAG高度过高，后半部分的执行计划会出现选错运算设备的情况，进而导致负优化。

针对这个问题，我们查阅了不少论文，但未发现较为有效的理论方法。在实践中，我们转向寻找系统层面的解决方案，整体思路是将查询优化本身纳入到执行计划中。首先，在查询优化器中完成对这类负载的识别。然后针对这类负载，考察cardinality的误差，在误差过大的位置插入执行计划的动态调整算子。该算子驱动查询优化器对后面未执行的计划进行重新优化，并更新Master中的任务图。

值得注意的是，除了增加“查询优化算子”，还需要考虑中间结果的元数据计算，如histogram。因此，执行计划的动态调整涉及到一套算子，其中包含采样、样本评价、元数据运算、查询优化等。

后，表1总结了本文所讨论的算子编译与查询优化的相关技术。

表1. 算子编译与查询优化的技术总结

7. 系统性能

本节的系统性能评测使用了三个典型业务场景的数据集，分别包含金融数据、网约车订单数据与移动端用户行为数据。测试共包含25条Query。测试环境与测试集的具体描述见表2。

表2. 测试环境与测试集

测试中我们将MegaWise与PostgreSQL 11进行了性能对比。结果如图5所示。在PostgreSQL中，25条Query的执行时间为6s-427s，平均执行时间为93s，MegaWise执行时间为0.14s-2.7s，平均执行时间为0.8s。与PostgreSQL相比，MegaWise的平均加速比为140x。

图5. MegaWise与PostgreSQL 11性能对比

图6给出了MegaWise加速比与PostgreSQL执行时间的关系。可以看出，对于秒级的小任务，MegaWise加速比较低，此时Query的执行时间主要为主存-显存间数据拷贝时间、kernel启动时间以及系统开销。当运算任务达到分钟级（>60s），MegaWise可以获得100x以上的加速比。

图6. MegaWise加速比与PostgresSQL执行时间的关系 

8. 后记

在构建MegaWise的过程中，团队做了不少技术探索，对于异构计算与大数据分析之间的“化学反应”也逐渐有了一些理解。异构计算确实在数据分析的若干场景中展现出不俗的潜力，但在走过无数弯路后，我们也深刻认识到异构计算并非银弹。异构计算、大数据所碰撞出的新兴技术与产业场景的磨合才刚刚拉开帷幕，而这个磨合的过程比技术本身更为重要。