一句话总结

帝国理工学院提出 BOSS，一种基于部分查询求值以及统一查询计划与数据交换格式的数据库内核组合架构。该架构将 Apache Arrow、ArrayFire 和 Velox 等组件连接成一个混合式数据库管理系统，相对于纯 CPU 的 Velox 实现了显著的性能提升，并在部分查询上超过了纯 GPU 的 HeavyDB。

核心贡献

• 一种可组合的数据库架构，通过部分查询求值以及统一查询计划与数据交换格式，将独立设计的存储、处理和规划组件连接起来。

• 该架构在 BOSS 中得到实例化。BOSS 是一个关系型数据管理系统，集成了 Apache Arrow 存储、GPU 加速的 ArrayFire 内核以及面向 CPU 的 Velox 内核，并在完整系统中支持运行时机会式算子卸载。

• 实验评估表明，该架构几乎不引入额外开销，BOSS 相对纯 CPU 的 Velox 改善了性能，并在部分查询上超过了高度优化的纯 GPU 系统 HeavyDB。

引言

现代数据管理系统已经覆盖完整的数据生命周期，支持事务型和分析型工作负载、数据清洗、模型训练、图数据、JSON 数据、键值数据，以及 CPU、GPU、智能存储设备、FPGA、TPU 和其他专用集成电路等专用硬件。这一点之所以重要，是因为应用程序越来越需要一个可扩展的平台，用于利用异构资源，而不是为每种工作负载或每种设备手工构建专用系统。

现有方法存在一种权衡：扩展 DMS 内核可以带来性能，但需要大量工程投入，并且通常只能支持异构性的狭窄部分；将库封装为 UDF 更简单，但通常会降低执行速度。可组合设计能够减少开发成本，但组合不同内核仍然困难，因为它们使用不同的执行模型、API、状态管理、元数据处理以及数据交换格式。

作者利用部分查询求值将数据库内核组合为流水线。查询以及数据和代码会在统一的内存表示中依次经过各个阶段，从而允许每个内核尽可能执行那些能够带来收益的算子，并将剩余算子留给后续内核。作者还引入了统一的物理格式，以及一个包含类型系统、领域特定语言和内存管理模型的编译期编程框架，用于以较少样板代码和较低运行时开销集成不同内核。作者通过将 Apache Arrow、Velox 和 ArrayFire 组合成一个完整分析系统来证明这一方法，其性能可与单体式设计相媲美。

数据集

• 作者通过项目仓库 https://github.com/lsds/MultiKernelBOSS 提供源代码、数据及相关工件。
• 所提供的文本没有说明数据集组成、子集大小、数据来源、过滤规则、模式、统计信息、裁剪策略、元数据构造，以及训练划分和处理细节。

方法

可组合引擎架构与部分查询求值

作者采用一种可组合的数据管理架构，避免使用单一单体式查询内核。相反，查询处理被拆分为若干引擎，这些引擎可以独立设计、集成，或从现有系统中采用。每个引擎接收一个查询表达式，并返回另一个查询表达式；该输出表达式在语义上等价于输入表达式，但更接近最终结果。形式化地，每个引擎 $E_i$Ei​ 将 $Q_i$Qi​ 映射为 $Q_{i+1}$Qi+1​，同时保持查询语义，流水线持续执行，直到最终表达式中不再包含需要求值的剩余算子。

系统有意不将 SQL 用作中间表示，因为基于文本的操纵会引入解析、转换和序列化开销。相反，框架使用统一内存表示来处理数据和代码。这使得引擎之间能够以极低的转换成本交换关系数据、谓词、表符号和局部计划。分阶段查询求值流程如下图所示：

该框架遵循四条设计原则。第一，框架保持中立，不对内核强制固定执行模型、内存模型、并发模型或物理数据布局。因此，Volcano 风格处理器、向量化内核、即时编译引擎和批处理内核可以在同一接口下集成。第二，框架最小化样板代码。这很关键，因为内核封装器通常需要大量代码来处理数据转换、传输调度、所有权控制和结果处理。第三，框架追求零拷贝和最小转换，并利用许多高性能内核已经使用 C 风格数组表示批量数据这一事实。第四，框架遵循语言优先于库的原则：编排逻辑直接以宿主编程语言表达，而不是依赖重型运行时库，从而允许跨内核边界进行内联、循环展开和向量化等编译器优化。

在最低层，框架使用一个可扩展的封闭世界动态类型系统。该类型系统扩展了标准 tagged union 表示，并加入一组可在编译期配置的原子类型。最小核心可以包含布尔值、整数、浮点值和字符串等类型，而内核特定扩展可以加入张量对象、GPU 内存缓冲区或其他专用数据载体。由于给定可执行文件会固定完整类型集合，编译器可以生成静态分派代码，同时仍支持需要自定义内部类型的内核。这样既避免了固定类型系统的全局刚性，也防止了运行时类型灵活性无限扩张。

对于批量数据交换，框架使用受内存管理的 span。span 是围绕 C 风格数组的轻量封装，并不规定特定所有权模型。其释放行为由一个函数指针和一个不透明负载定义。当 span 被销毁时，该函数可以释放底层数组、解除文件映射、减少引用计数，或者在 span 仅借用内存时不执行任何操作。span 被设计为只能移动的类型，因此所有权转移是显式的，并由编译器强制执行。若在移动后使用 span，会触发编译警告或错误，从而保持所有权模型简单可靠，同时避免引入广泛引用计数。

数据、代码、计划和动态行为通过半静态类型表达式统一表示。这些表达式将符号表达式进行泛化，包含三类参数：静态类型参数、使用封闭世界原子系统的动态类型参数，以及表示同类型元素集合的 span 参数。表达式具有一个符号头，可以表示值、列、关系、算子或未求值的计划片段。API 提供一条较慢的统一路径，将所有参数作为动态原子暴露；同时提供一条快速路径，直接访问静态参数和 span。这样既支持正确性关键的计划操纵，也支持性能关键的处理循环。

表达式结构变更通过破坏性分解避免昂贵拷贝。由于表达式可能包含只能移动的 span，因此表达式本身也不可拷贝且只能移动。然而，不再需要的表达式可以被分解为头、静态参数、动态参数和 span。所得元组随后可以重组为具有修改后结构的新表达式。这一模式允许投影、列删除和计划重写等操作在不复制底层列数组的情况下更新表达式结构。

为了降低封装器复杂度，框架通过半静态分派合成内核交互代码。内核通常需要适用于许多静态类型的泛型算子，但 C++ 并未针对静态模板展开提供完整动态分派。框架的做法是在编译期限制类型全集，并提前展开特定类型的代码路径。在运行时，框架会将动态表达式参数与已知静态类型参数进行匹配检查。如果类型匹配，框架将数据移动到静态类型算子调用中，且不进行不必要的拷贝。如果类型不匹配，表达式原样返回，并传递给后续引擎。这实现了机会式内核执行，而无需调用者显式指定算子分配。

框架还包含一个嵌入式表达式领域特定语言。在宿主语言中，重载语法构造能够简洁地创建符号和表达式，减少构建列、表、谓词和局部计划的冗余代码。这使得算子实现更紧凑，同时保留对底层表示的直接控制。相同抽象支持 GPU、CPU、存储和关系型内核，而无需每个内核重新实现计划表示、传输逻辑或类型分派代码。

在已实现系统中，BOSS 组合三个引擎：基于 Apache Arrow 的存储引擎、基于 ArrayFire 的 GPU 引擎，以及基于 Velox 的 CPU 引擎。初始查询首先由存储引擎处理，该引擎用包含实际存储数据的表达式替换表和列符号。随后，GPU 引擎机会式地求值那些能够从 GPU 加速中受益的子表达式。最后，CPU 引擎求值剩余算子并返回最终结果。无需显式将算子分配给某个引擎；编排逻辑只是流水线中引擎的执行顺序。分阶段执行轨迹如下所示：

存储引擎有两项主要职责。第一，它使用 Apache Arrow 列式数组将关系数据加载到内存；这些数组是 C 数组的封装器。这些数组可以通过将原始指针传入 span 构造函数转换为 BOSS span。为了保持生命周期安全，Arrow 数组的 shared pointer 会作为 span 析构函数负载传入，从而确保底层内存只在 span 销毁时才释放。第二，存储引擎执行符号替换，用存储的关系表达式替换表标识符。由于存储引擎拥有持久数据，并且生命周期长于查询执行，它可以提供非拥有型 span，而无需复制列内容。

存储布局不同于 Arrow 原生的关系级分区。Apache Arrow 按分区组织数据，每个分区包含一组列。BOSS 则采用列级分区，每列由多个连续分区组成。该布局简化了列向操作，并减少结构性冗余，因为列元数据不需要为每个分区重复。两种布局之间通过浅层转换完成转换：结构封装被重新组织，但底层数据保持原位。关系级和列级布局及其零拷贝转换如下所示：

存储引擎还处理压缩字符串字典。低基数字符串列被存储为整数键，这些整数键索引唯一字符串字典。当查询包含字符串相等谓词时，存储引擎会重写这些谓词，使下游引擎直接基于整数键操作。这避免了将字符串字典逻辑暴露给 GPU 和 CPU 关系引擎。当结果必须以字符串形式返回时，存储引擎会在输出计划周围封装一个字符串查找算子，仅在其中需要的地方将键转换回字典值。

CPU 引擎围绕 Velox 构建。Velox 使用分解列表示以向量化批次处理数据。框架提供 BOSS span 与 Velox flat vector 之间的浅层转换。flat vector 可以接管内存所有权、处理内存，并在不拷贝的情况下返回所有权。对于面向行的执行接口，多个 flat vector 会被组合为 row vector。CPU 引擎通过递归转换将 BOSS 表达式翻译为 Velox 计划节点。例如，filter 表达式可以分解为谓词和输入关系，映射为 Velox filter 节点，并与由转换后 row vector 构造的 value 节点组合。CPU 引擎求值早期阶段部分执行查询后剩下的所有剩余算子。

GPU 引擎使用 ArrayFire 作为张量处理内核。只有在能够高效映射到 ArrayFire 操作时，系统才实现关系型操作。简单投影可能变成通过破坏性分解重命名列的空操作，而算术投影则使用 ArrayFire 算术函数。选择谓词在 GPU 上被求值为位数组，并转换为位置列表。GPU 引擎不一定立即物化过滤后的关系。相反，它可以留下一个 Gather 算子，该算子将原始关系与 GPU 生成的位置列表组合，允许 CPU 引擎随后完成过滤。当并非所有谓词都能在或都应该在 GPU 上执行时，这种方式降低了跨设备传输成本。

GPU 执行面临混合求值问题。ArrayFire 张量对象通常是惰性计算代理，但使用 CPU 数据初始化它们可能会急切地将数据传输到 GPU 内存空间。这会形成一种执行图，其中一些操作是惰性的，而一些数据传输是急切的。为避免不必要传输，BOSS 将急切 GPU 传输封装在闭包中。closure 原子可以保存延迟操作，该操作只在真正需要时才会生成 ArrayFire 数组。在计划遍历期间，可被 GPU 求值的子表达式会被包装进这些闭包，并作为原子传递到下游。如果后续阶段需要 GPU 结果，就求值该闭包；否则不会执行传输。当 GPU 内存受限，或因失败或剪枝导致某些 GPU 传输变得不必要的时候，这种设计尤其重要。所得混合惰性急切求值图如下所示：

实验

评估使用 TPC-H 基准测试，在多个规模因子下比较所提出的 GPU 加速协同处理系统与基于 CPU 和纯 GPU 的数据库系统，并分别分析查询计划、GPU 内存约束以及框架开销。实验表明，跨存储、GPU 和 CPU 引擎的部分查询求值能够提升许多典型分析模式的性能，并且在数据规模超过 GPU 内存时仍然有益，而完全基于 GPU 的替代方案可能会失败或失去效率。消融实验和开销测量进一步表明，零拷贝数据交换和快速路径表达式处理对实际收益非常重要，而编排框架本身引入的开销很小。