Efficiently Compiling Efficient Query Plans for Modern Hardware（解读）

个人理解总结说明

直接将SQL语言通过优化器转成对应的树形执行逻辑，基本上在数据流上已经比较好了；

但是效率相比手写（专家）差的较多，通过LLVM将树形执行逻辑（OptimizedPlan）进行二次优化转成机器码执行，进一步提高效率；

本文讲的主要还是在一个单节点物理机， 涉及到分布式shuffle逻辑又有些不太一样；所以目前业界的分布式数据仓库只有少部分参考了文章的方式。

ABSTRACT

随着主内存容量的增长，查询性能越来越取决于查询处理本身的原始 CPU 成本。经典的迭代器式查询处理技术虽然非常简单且灵活，但由于缺乏局部性和频繁的指令预测错误，在现代 CPU 上表现不佳。过去已经提出了几种技术来改善这种情况，例如面向批处理的处理或向量化元组处理，但即使是这些技术也经常被手工编写的执行计划超越。在这项工作中，我们提出了一种新颖的编译策略，利用 LLVM 编译器框架将查询转换为紧凑且高效的机器代码。通过追求良好的代码和数据局部性以及可预测的分支布局，生成的代码经常能够与手工编写的 C++ 代码相媲美。我们将这些技术集成到 HyPer 主内存数据库系统中，并展示了其在仅需适度编译时间的情况下，能够实现卓越的查询性能。

1. INTRODUCTION

大多数数据库系统会将给定的查询转换为（物理）代数表达式，然后开始评估该代数表达式以生成查询结果。执行这些代数计划的传统方式是迭代器模型 [8]，有时也称为火山式处理 [4]：每个物理代数运算符在概念上从其输入生成一个元组流，并允许通过重复调用运算符的 next 函数来迭代该元组流。

这是一个非常简洁且简单的接口，允许轻松组合任意运算符，但它显然源自一个查询处理主要由 I/O 主导、CPU 消耗不那么重要的时代：首先，next 函数将为生成的每个中间或最终结果元组调用，即数百万次。其次，next 调用通常是虚函数调用或通过函数指针的调用。因此，这种调用比常规调用更昂贵，并且会降低现代 CPU 的分支预测能力。第三，这种模型通常导致代码局部性差和复杂的簿记工作。通过考虑对压缩关系的简单表扫描可以看出这一点。由于必须一次生成一个元组，表扫描运算符必须记住当前元组在压缩流中的位置，并在请求下一个元组时跳转到相应的解压缩代码。

这些观察结果导致一些现代系统偏离了这种纯迭代器模型，要么在内部（例如，通过一次解压缩多个元组，然后仅迭代解压缩后的数据），要么在外部通过在每次 next 调用中生成多个元组 [11]，甚至一次生成所有元组 [1]。这种面向块的处理将调用另一个运算符的成本分摊到大量生成的元组上，使得调用成本变得可以忽略不计。然而，它也消除了迭代器模型的一个主要优势，即数据流水线化的能力。流水线化意味着运算符可以将其数据传递给父运算符，而无需复制或以其他方式物化数据。例如，选择是流水线化运算符，因为它们只是传递元组而不修改它们。但更复杂的运算符（如连接）也可以流水线化，至少在其一个输入侧。当在一次调用中生成多个元组时，这种纯流水线化通常无法再使用，因为元组必须在某处物化以便访问。这种物化具有其他优势，例如允许向量化操作 [2]，但总的来说，缺乏流水线化是非常不幸的，因为它会消耗更多的内存带宽。

图1

在这方面，一个有趣的观察是，手工编写的程序明显优于甚至非常快的向量化系统，如图 1 所示（最初来自 [16]）。在某种程度上，这当然是意料之中的，因为人类可能会使用数据库管理系统永远想不到的技巧。另一方面，图中的查询是一个简单的聚合查询，人们会认为只有一种合理的方式来评估此查询。因此，现有的查询评估方案显然不够优化。

代数运算符模型对于查询的推理非常有用，但在查询处理过程中展示运算符结构并不一定是一个好主意。因此，在本文中，我们提出了一种查询编译策略，该策略在几个重要方面与现有方法不同：

• 处理以数据为中心，而不是以运算符为中心。数据的处理方式使得我们能够尽可能长时间地将其保留在 CPU 寄存器中。为了实现这一目标，运算符的边界被模糊化。
• 数据不是由运算符拉取，而是被推送到运算符。这导致代码和数据局部性显著改善。
• 查询使用优化的 LLVM 编译器框架 [7] 编译为本地机器代码

整体框架生成的代码对现代 CPU 架构非常友好，因此可以与手工编码的查询执行计划的速度相媲美。在某些情况下，我们甚至可以超越手工编写的代码，因为使用 LLVM 汇编语言可以实现一些在高级编程语言（如 C++）中难以实现的技巧。此外，通过使用成熟的编译器框架，我们可以从未来的编译器、代码优化和硬件改进中受益，而其他将处理优化集成到查询引擎本身的方法则必须手动更新其系统。我们通过将这些技术集成到 HyPer 主内存数据库管理系统 [5] 中，并与其他系统进行各种比较，展示了这些技术的影响。

本文的其余部分结构如下：我们首先在第 2 节讨论相关工作。然后在第 3 节解释我们编译框架的整体架构。第 4 节更详细地讨论了代数运算符的实际代码生成。第 5 节解释了如何将不同的高级处理技术集成到框架中。随后，我们在第 6 节展示了对我们技术的广泛评估，并在第 7 节得出结论。

2. RELATED WORK

经典的迭代器模型用于查询评估的提出时间较早 [8]，并通过 Volcano 系统 [4] 得到了广泛普及。如今，它是最常用的执行策略，因为它灵活且非常简单。在查询处理主要由磁盘 I/O 主导时，迭代器模型运行良好。然而，随着 CPU 消耗成为一个问题，一些系统尝试通过传递元组块来减少迭代器模型的高调用成本 [11]。这大大减少了函数调用的次数，但导致了额外的物化成本。

现代主内存数据库系统重新审视了这个问题，因为对它们来说，CPU 成本是一个关键问题。MonetDB 系统 [1, 9] 走向了另一个极端，物化所有中间结果，从而消除了重复调用输入运算符的需要。除了简化运算符交互外，物化还有其他优势，但也会带来显著的成本。MonetDB/X100 系统 [1]（后来演变为 VectorWise）选择了一种折衷方案，通过传递大数据向量并在每个数据块上以向量化方式评估查询。这提供了出色的性能，但如图 1 所示，仍然无法达到手工编写代码的速度。

另一种改进查询处理的方法是将查询编译为某种可执行格式，而不是使用解释器结构。在 [13] 中，作者提出将查询逻辑编译为 Java 字节码，从而可以利用 Java JVM。然而，这种方法相对较重，并且他们仍然使用迭代器模型，这限制了其优势。最近关于 HIQUE 系统的工作提出使用代码模板将查询编译为 C 代码 [6]。HIQUE 通过在运算符执行中内联结果物化来消除迭代器模型。然而，与我们的提议不同，运算符的边界仍然清晰可见。此外，生成的 C 代码的编译成本相当高 [6]。

除了这些更通用的方法外，还提出了许多单独的技术来加速查询处理。一项重要的工作是减少分支的影响，其中 [14] 展示了如何组合合取谓词，以便在分支数量和评估谓词数量之间达到最佳权衡。其他工作则通过使用 SIMD 指令来更高效地处理单个表达式 [12, 15]。

3. THE QUERY COMPILER

3.1 Query Processing Architecture

我们提出了一种非常不同的查询处理（以及相应的查询编译）架构。为了最大化查询处理性能，我们必须确保最大程度地提高数据和代码的局部性。为了说明这一点，我们首先给出一个比标准数据库系统更严格的流水线中断器的定义：如果一个代数运算符将传入的元组从 CPU 寄存器中取出，那么它对于给定的输入侧来说就是一个流水线中断器。如果它在继续处理之前物化了来自该侧的所有传入元组，那么它就是一个完全流水线中断器。

这个定义稍显简化，因为单个元组可能已经太大而无法放入可用的 CPU 寄存器中，但目前我们假设我们有足够多的寄存器来容纳所有输入属性。我们将在第 4 节中更详细地讨论这一点。关键是我们认为将数据溢出到内存中是一种流水线中断操作。在查询处理过程中，所有数据应尽可能长时间地保留在 CPU 寄存器中。

现在的问题是，我们如何组织查询处理，以便数据可以尽可能长时间地保留在 CPU 寄存器中？经典的迭代器模型显然不适合这一点，因为元组通过函数调用传递给任意函数——这总是会导致寄存器内容被逐出。面向块的执行模型在函数边界之间的传递较少，但它们显然也会中断流水线，因为它们生成的元组批次超出了寄存器的容量。事实上，任何从输入运算符中拉取数据的迭代器式处理范式都有可能中断流水线，因为通过提供基于迭代器的视图，它必须为任意复杂的关系运算符的输出提供线性化的访问接口。有时，运算符可以廉价地生成少量输出元组，而无需复制。

因此，我们反转了数据流控制的方向。我们不是向上拉取元组，而是将它们推送到消费者运算符。在推送元组时，我们继续推送，直到到达下一个流水线中断器。因此，数据总是从一个流水线中断器推送到另一个流水线中断器。位于两者之间的运算符将元组保留在 CPU 寄存器中，因此计算成本非常低。此外，在基于推送的架构中，复杂的控制流逻辑通常位于紧密循环之外，这减少了寄存器压力。由于典型的流水线中断器无论如何都必须物化元组，因此我们生成的执行计划可以最大限度地减少内存访问次数。

图3

作为一个示例，请考虑图 3 中的执行计划（Γ 表示分组运算符）。相应的 SQL 查询如图 2 所示。它从 R2 中选择一些元组，按 z 分组，将结果与 R3 连接，然后将该结果与 R1 中的一些元组连接。在经典的运算符模型中，最顶层的连接将通过首先反复向其左输入请求元组，将每个元组放入哈希表中，然后向其右输入请求元组并为每个表探测哈希表来生成元组。输入侧本身将以类似的方式递归操作。当更仔细地查看此示例中的数据流时，我们会发现原则上元组总是从一个物化点传递到另一个物化点。连接 a = b 将其左输入的元组物化到哈希表中，并从物化状态（即从 R1 的扫描）接收它们。中间的筛选操作对元组进行流水线处理，不进行物化。这些物化点（即流水线边界）如图 3 右侧所示。

图4

由于我们无论如何都必须在某个时刻物化元组，因此我们建议以这样的方式编译查询：所有流水线操作都在 CPU 中纯粹执行（即不进行物化），而执行本身从一个物化点转移到另一个物化点。我们运行示例的相应编译如图 4 所示。（请注意，我们假设完全在内存中进行计算，以保持示例的可读性。）除了初始化之外，代码由四个片段组成，这些片段对应于代数计划中的流水线片段：第一个片段从 R1 中筛选元组并将其放入 Ba,b 的哈希表中，第二个片段对 R2 和 Γz 执行相同的操作，第三个片段将 Γz 的结果转移到 Bz=c 的哈希表中。第四个也是最后一个片段将 R3 的元组沿连接哈希表传递并生成结果。所有四个片段本身都是强流水线化的，因为它们可以将元组保留在 CPU 寄存器中，并且仅访问内存以检索新元组或物化其结果。此外，我们具有非常好的代码局部性，因为小的代码片段在紧密循环中处理大量数据。因此，我们可以预期从这种评估方案中获得非常好的性能。事实上，正如我们将在第 6 节中看到的那样，这种查询评估方法大大优于基于迭代器的评估。现在的主要挑战是将给定的代数执行计划转换为这样的代码片段。我们将在下一节中首先讨论高级翻译，然后在第 4 节中解释实际的代码生成。

3.2 Compiling Algebraic Expressions

观察图 4 中的查询代码时，我们注意到运算符之间的边界变得模糊。例如，第一个片段将 R1 的扫描、筛选条件 σx=7 以及 Bc=z 的构建部分合并为一个代码片段。查询执行代码不再以运算符为中心，而是以数据为中心：每个代码片段在执行流水线的一部分中执行所有可以完成的操作，然后将结果物化到下一个流水线中断器中。单个运算符的逻辑可能会（并且很可能）分散在多个代码片段中，这使得查询编译比通常更加复杂。此外，这些代码片段的结构非常不规则。例如，对于二元流水线中断器，物化来自左侧的输入元组与物化来自右侧的输入元组会有很大不同。在迭代器模型中，所有操作都是一个简单的 next 调用，但在这里，复杂的运算符逻辑直接影响代码生成。需要注意的是，这是一个优势，而不是这种方法的限制！迭代器模型有一个简洁的接口，但它通过使用虚函数调用和频繁的内存访问为此付出了代价。通过暴露运算符结构，我们可以生成接近最优的汇编代码，因为我们生成了与给定情况完全相关的指令，并且可以将所有相关值保留在 CPU 寄存器中。正如我们将在下面看到的，保持代码可维护性和可理解性所需的抽象是存在的，即所有运算符都提供统一的接口，但这些抽象仅存在于查询编译器本身中。生成的代码暴露了所有细节（出于效率原因），但这没有问题，因为代码是自动生成的。

从查询编译器的角度来看，运算符提供的接口几乎与迭代器模型一样简单。从概念上讲，每个运算符提供两个函数：

• produce()

• consume(attributes,source)

从概念上讲，produce 函数要求运算符生成其结果元组，然后通过调用其 consume 函数将这些元组推送到消费运算符。对于我们的运行示例，查询将通过调用 Ba=b.produce 来执行。这个 produce 函数将调用 σx=7.produce 来填充其哈希表，而 σ 运算符将调用 R1.produce 来访问关系。R1 是运算符树中的叶子节点，即它可以自己生成元组。因此，它扫描关系 R1，并为每个元组加载所需的属性并调用 σx=7.consume(attributes, R1) 将元组传递给筛选操作。筛选操作过滤元组，如果符合条件，则通过调用 Ba=b(attributes, σx=7) 将其传递。连接操作看到它从左侧获取元组，因此将它们存储在哈希表中。在 R1 的所有元组生成后，控制流返回到连接操作，它将调用 Bc=z.produce 从探测侧获取元组，依此类推。

图5

然而，这个 produce/consume 接口只是一个心智模型。这些函数并不显式存在，它们仅用于代码生成。在编译 SQL 查询时，查询首先像往常一样被处理，即查询被解析、转换为代数表达式，并对代数表达式进行优化。只有在此之后，我们才偏离标准方案。最终的代数计划不会被翻译为可执行的物理代数，而是被编译为命令式程序。只有这个编译步骤在内部使用 produce/consume 接口来生成所需的命令式代码。这种代码生成模型如图 5 所示。它展示了一个非常简单的翻译方案，将 B、σ 和扫描操作转换为伪代码。读者可以验证，将图 5 中的规则应用于图 3 中的运算符树将生成图 4 中的伪代码（除了变量名称和内存初始化的差异）。当然，实际的翻译代码要复杂得多，因为我们必须跟踪加载的属性、涉及的运算符状态、相关子查询中的属性依赖关系等，但原则上，这种简单的映射已经展示了我们如何将代数表达式翻译为命令式代码。我们在附录 A 中提供了更详细的运算符翻译。由于这些代码片段每次都在某些数据块上操作，因此具有非常好的局部性，生成的代码被证明可以高效执行。

4. CODE GENERATION

图6

4.1 Generating Machine Code

到目前为止，我们只讨论了将代数表达式翻译为伪代码，但在实践中，我们希望将查询编译为机器代码。最初，我们尝试从查询生成 C++ 代码，并在运行时通过编译器将其编译为共享库。编译为 C++ 代码很有吸引力，因为 C++ 代码可以直接访问我们数据库系统的数据结构和代码，而数据库系统也是用 C++ 编写的。然而，这种方法有几个缺点。首先，优化 C++ 编译器非常慢，编译一个复杂的查询可能需要几秒钟。其次，C++ 无法完全控制生成的代码，这可能导致性能不理想。特别是，溢出标志等不可用。相反，我们使用低级虚拟机（LLVM）编译器框架 [7] 生成可移植的汇编代码，然后可以使用 LLVM 提供的优化 JIT 编译器直接执行。虽然生成汇编代码最初听起来可能令人望而生畏，但使用 LLVM 生成汇编代码比手动编写要稳健得多。例如，LLVM 通过提供无限数量的寄存器（尽管是单静态赋值形式）隐藏了寄存器分配的问题。因此，我们可以假设为元组中的每个属性都有一个 CPU 寄存器可用，这大大简化了工作。此外，LLVM 汇编器是跨机器架构可移植的，因为只有 LLVM JIT 编译器将可移植的 LLVM 汇编器翻译为依赖于架构的机器代码。此外，LLVM 汇编器是强类型的，这捕获了我们原始文本 C++ 代码生成中隐藏的许多错误。最后，LLVM 是一个功能强大的优化编译器，可以生成极快的机器代码，通常只需要几毫秒即可完成查询编译，而 C 或 C++ 编译器则需要几秒钟（参见第 6 节和 [6]）。

尽管如此，我们并不希望在 LLVM 汇编器中实现完整的查询处理逻辑。首先，编写汇编代码比使用 C++ 这样的高级语言更繁琐；其次，许多数据库逻辑（如索引结构）已经用 C++ 编写。但我们可以轻松地将 LLVM 和 C++ 混合使用，因为 C++ 方法可以直接从 LLVM 调用，反之亦然。（对于编译器来说，这两种代码没有区别，因为它们都生成本地机器代码，并且都具有强类型的原型。）这导致了一种混合执行模型，如图 6 所示。查询处理的复杂部分（例如，复杂的数据结构管理或溢出到磁盘）用 C++ 编写，并形成图 6 中的齿轮。不同的运算符通过 LLVM 代码连接在一起，形成图 6 中的链条。C++“齿轮”是预编译的；只有用于组合它们的 LLVM“链条”是动态生成的。因此，我们实现了非常低的查询编译时间。在具体示例中，扫描的复杂部分（例如，定位数据结构，确定接下来要扫描的内容）用 C++ 实现，这段 C++ 代码“驱动”执行流水线。但元组访问本身以及进一步的元组处理（筛选、哈希表中的物化）是用 LLVM 汇编代码实现的。C++ 代码会不时被调用（例如，在分配更多内存时），但 C++ 部分的交互由 LLVM 控制。如果涉及复杂运算符（如排序），控制可能会在某个时刻完全回到 C++，但一旦复杂逻辑结束并且需要批量处理元组时，LLVM 会再次接管。为了获得最佳性能，重要的是热路径（即对 99% 的元组执行的代码）是纯 LLVM 的。不时调用 C++（例如，切换到新页面时）是可以的，其成本可以忽略不计，但大部分处理必须在 LLVM 中完成。在 LLVM 中运行时，我们可以始终将元组保留在 CPU 寄存器中，这几乎是我们能达到的最快速度。当调用外部函数时，所有寄存器都必须溢出到内存中，这有些昂贵。当然，从绝对意义上来说，这非常便宜，因为寄存器会溢出到堆栈中，而堆栈通常在缓存中，但如果这种情况发生数百万次，就会变得明显。

4.2 Complex Operators

虽然为扫描和选择操作生成代码相对简单，但在为更复杂的运算符（如排序或连接）生成代码时需要格外小心。首先需要注意的是，与本文中目前看到的简单示例不同，将复杂查询编译为单个函数既不可能也不可取。这有多个原因。首先，从实际角度来看，LLVM 代码很可能会在某个时刻调用 C++ 代码，从而接管控制流。例如，外部排序运算符会使用 LLVM 生成初始运行，但可能会在 C++ 中控制合并阶段，并根据需要调用 LLVM 函数。其次，将完整的查询逻辑内联到单个函数中可能导致代码呈指数级增长。例如，外连接会在两种不同情况下调用其消费者：首先是在找到匹配项时，其次是在生成 NULL 值时。可以在这两种情况下直接包含消费者代码，但外连接的级联会导致代码呈指数级增长。因此，在 LLVM 内部定义函数是有意义的，这些函数可以从 LLVM 代码中的位置调用。同样，必须确保热路径不跨越函数边界。因此，代数表达式的流水线片段应生成一个紧凑的 LLVM 代码片段。

这种对多个函数的需求影响了我们生成代码的方式。特别是，我们必须跟踪所有属性，并记住它们当前是否在寄存器中可用。将属性物化到内存中是一个有意的决定，类似于将元组溢出到磁盘。当然，从性能角度来看，内存中的物化相对较快，但从代码角度来看，物化是一个非常复杂的步骤，应尽可能避免。

不幸的是，为实际查询生成的汇编代码很快就会变得复杂，这使我们无法在此展示完整的计划，但作为说明，我们包含了一个小的 LLVM 片段，展示了我们运行示例中 Γz;count(∗)(σy=3(R2)) 部分的主要机制（如图 7 所示）：LLVM 代码由 C++ 代码为每个数据片段（即连续存储的元组序列）调用。LLVM 代码首先加载它希望在处理期间访问的列的指针。然后，它循环遍历当前片段中包含的所有元组（代码省略）。对于每个这样的元组，它将属性 y 加载到寄存器中并检查谓词。如果谓词为假，则继续循环。否则，它将属性 z 加载到寄存器中并计算哈希值。使用此哈希值，它查找相应的哈希条目（使用 C++ 数据结构，这些结构在 LLVM 中可见），并遍历条目（代码省略）。如果未找到匹配的组，则检查是否可以确保有足够的空闲空间来分配新组。如果没有，则调用 C++ 函数以提供新内存并根据需要溢出到磁盘。这样，热代码路径完全保留在 LLVM 中，主要由 %then 块内的代码以及相应的哈希表迭代组成。请注意，LLVM 调用直接调用本机 C++ 方法（使用修饰名称 @ZN...），没有额外的包装器。因此，C++ 和 LLVM 可以直接交互而不会影响性能。

4.3 Performance Tuning

使用上述策略生成的 LLVM 代码非常快。主要工作是在元组上的紧密循环中完成的，这有助于良好的内存预取和准确的分支预测。事实上，代码如此之快，以至于突然之间，代码片段成为了瓶颈，而这些片段在其他代码较慢时相对不重要。一个突出的例子是哈希。例如，对于 TPC-H 查询 1（基本上是一个扫描和基于哈希的聚合），我们初始计划中超过 50% 的时间都花在了哈希上，尽管我们只对两个简单的值进行哈希。另一个关键问题是分支。在现代 CPU 上，只要分支预测有效，即分支几乎从不或几乎总是被采用，分支就非常便宜。然而，被采用概率为 50% 的分支会破坏分支预测，并且非常昂贵。因此，查询编译器必须生成允许良好分支预测的代码。

在生成汇编代码时，这些问题需要格外注意。如前所述，我们将所有元组属性保留在（虚拟）CPU 寄存器中。对于字符串，我们将长度和指向字符串本身的指针保留在寄存器中。通常，我们尽可能晚地加载属性，即在我们需要该属性时或当我们无论如何都可以免费获取它时，因为我们必须访问相应的内存。对于派生属性的计算也是如此。然而，当这些值在关键路径上需要时（例如，当使用哈希值访问哈希表时），提前计算这些值以隐藏计算延迟是有意义的。同样，分支的布局应使其适合超高效的 CPU 执行。例如，以下（高级）代码片段对预测不太友好：

问题在于 while 混合了两件事，即检查是否存在此哈希值的条目，以及检查我们是否到达了冲突链表的末尾。第一种情况几乎总是为真，因为我们期望哈希表已填充，而第二种情况几乎总是为假，因为我们的冲突链表非常短。因此，以下代码片段对预测更友好：

当然，我们的代码使用 LLVM 分支而不是 C++ 循环，但在那里也是如此，当生成这样的代码时，分支预测会显著改善。这种代码布局对查询处理有显著影响，在我们的实验中，仅改变分支结构就使哈希表查找速度提高了 20% 以上。

当然，所有这些问题都使代码生成复杂化。但总的来说，避免这些陷阱所需的努力并不太严重。LLVM 代码无论如何都会生成，并且在代码生成器上花费一次努力将为所有后续查询带来回报。代码生成器相对紧凑。在我们的实现中，SQL-92 所需的所有代数运算符的代码生成大约需要 11,000 行代码，这并不算多。

5. ADVANCED PARALLELIZATION TECHNIQUES

在前面的章节中，我们讨论了如何将查询编译为以数据为中心的执行程序。通过组织数据流和控制流，使得元组直接从一个流水线断点推送到另一个断点，并尽可能长时间地将数据保留在寄存器中，我们获得了出色的数据局部性。然而，这并不意味着我们必须线性地处理元组，一次一个元组。我们的初始实现是推送单个元组，这已经表现得非常好，但更高级的处理技术可以非常自然地集成到通用框架中。我们现在来看其中的几种。

传统的块处理 [11] 有一个很大的缺点，即会创建额外的内存访问。然而，一次处理多个元组确实是一个非常好的主意，只要我们可以将整个块保留在寄存器中。特别是在使用 SIMD 寄存器时，通常就是这种情况。一次处理多个元组有几个优点：首先，当然，它允许在现代 CPU 上使用 SIMD 指令 [15]，这可以大大加快处理速度。其次，它可以帮助延迟分支，因为可以在不立即执行分支的情况下评估和组合谓词 [12, 14]。严格来说，[14] 中的技术对于单个元组已经非常有用，但对于元组块的效果可能更大。这种将值打包到（大）寄存器中的块处理风格非常自然地适合我们的框架，因为运算符总是将寄存器值传递给它们的消费者。LLVM 直接允许将 SIMD 值建模为向量类型，因此对整体代码生成框架的影响相对较小。

图7

SIMD 指令是一种元组间并行性，即用一条指令处理多个元组。现代 CPU 相关的第二种并行性是多核处理。几乎所有数据库系统都会利用多核架构进行查询间并行性，但随着现代 CPU 上可用核心数量的增加，查询内并行性变得更加重要。原则上，这是一个经过充分研究的问题 [10, 3]，通常通过划分运算符的输入、独立处理每个分区，然后合并所有分区的结果来解决。对于我们的代码生成框架，这种并行性几乎不需要代码更改即可支持。如图 7 所示，代码始终在数据片段上操作，这些片段在紧密循环中处理，并物化到下一个流水线断点。通常，片段由存储系统确定，但它们也可以来自并行化决策。只需要一些额外的逻辑来合并各个结果。请注意，“并行化决策”本身是一个难题！拆分和合并数据流是昂贵的，优化器必须小心引入并行性。这超出了本文的范围。但对于未来的工作来说，这是一个非常相关的问题，因为核心数量正在增加。

6. EVALUATION

我们已在 HyPer 内存数据库管理系统 [5] 和基于磁盘的 DBMS 中实现了本文提出的技术。我们发现，无论是在纯内存中操作还是在需要时溢出到磁盘，这些技术都表现得非常出色。然而，由于查询性能还受到存储系统差异等其他因素的显著影响，因此很难精确衡量我们的编译技术相对于其他方法的影响。因此，评估分为两部分：我们在此包括一个完整的系统比较，包括对生成代码的分析。附录 B 中包含了一个针对特定操作符行为的微基准测试。

在系统比较中，我们包括了在 MonetDB 1.36.5、Ingres VectorWise 1.0 和一个我们称为 DB X 的商业数据库系统上运行的实验。所有实验均在配备 64GB 主内存的双 Intel X5570 四核 CPU 上运行，操作系统为 Red Hat Enterprise Linux 5.4。我们的 C++ 代码使用 gcc 4.5.2 编译，机器代码使用 LLVM 2.8 生成。优化级别的更多细节在附录 C 中解释。

6.1 Systems Comparison

我们集成查询编译技术的 HyPer 系统设计为混合 OLTP 和 OLAP 系统，即它可以同时处理这两种工作负载。因此，我们使用 [5] 中的 TPC-CH 基准进行实验。在 OLTP 方面，它运行 TPC-C 基准测试，而在 OLAP 方面，它执行适应（略微扩展的）TPC-C 模式的 22 个 TPC-H 查询。前五个查询包含在附录 D 中。由于我们主要关注原始查询处理速度的评估，因此我们运行了一个没有并发的设置，即我们加载了 12 个仓库，然后单线程执行 TPC-C 事务，没有客户端等待时间。同样，OLAP 查询在 12 个仓库上单线程执行，没有并发更新。比较有趣的是，HyPer 最初使用手写代码片段将查询编译为 C++ 代码，这使我们能够估计 LLVM 相对于 C++ 代码的影响。

表1

我们仅在 HyPer 中运行 OLTP 部分，因为其他系统不是为 OLTP 工作负载设计的。结果如表 1 所示。如第一行所示，LLVM 版本的性能（以每秒事务数衡量）略优于优化的 C++ 代码。然而，差异很小，因为大多数 TPC-C 事务相对简单，涉及不到 30 个元组。更有趣的是编译时间，它涵盖了所有 TPC-C 脚本（使用 PL/SQL 风格的脚本语言）。编译生成的 C++ 代码比使用 LLVM 慢十倍以上，并且性能（略微）更差，这是对我们查询编译技术的有力支持。

表2

对于 OLAP 部分，我们以预准备查询的形式运行 TPC-CH 查询，并测量了热执行时间。前五个查询的结果如表 2 所示（Q2 触发了 VectorWise 中的一个错误）。DB X 明显比其他系统慢，但这并不奇怪，因为它是作为通用磁盘系统设计的（即使在这里数据适合主内存并且我们测量的是热执行时间）。其他系统都快得多，但使用 LLVM 代码生成的 HyPer 通常快 2-4 倍，具体取决于查询。C++ 后端和 LLVM 后端之间的比较特别有趣。首先，虽然 C++ 版本相当快，但 LLVM 后端生成的紧凑代码明显更快。这对于以连接为主的 Q5 不太明显，但对于其他查询，特别是聚合查询 Q1，差异很大。Q1 很好地突出了这一点，因为原则上查询非常简单，只是一个扫描和一个聚合。因此，相应的 C++ 代码看起来非常自然和高效，但根本无法与尝试将所有内容保留在寄存器中的 LLVM 版本竞争。第二个观察结果是，即使查询在交叉编译为 C++ 时相当快，但编译时间本身是不可接受的，这也是我们寻找生成 C++ 代码的替代方案的部分原因。然而，LLVM 版本的编译时间相当适中（数字包括将 SQL 字符串转换为可执行机器代码所需的所有步骤，而不仅仅是 LLVM 代码生成）。因此，更改后端显然对 HyPer 有利，无论是由于查询处理本身还是由于编译时间。

6.2 Code Quality

另一个有趣的点是生成的 LLVM 代码的质量。如上所示，原始性能显然很好，但有趣的是生成的机器代码在分支和缓存效果方面的表现如何。为了研究这些效果，我们使用 valgrind 3.6.0 的 callgrind 工具运行了所有五个查询，该工具使用二进制插装来观察分支和缓存效果。我们使用 callgrind 控制将分析限制在查询处理本身。在实验中，我们将 HyPer 的 LLVM 版本与 MonetDB 进行了比较。MonetDB 在紧凑的紧密循环中执行操作，因此可以预期其分支预测错误的数量较低。结果如表 3 所示。第一个块显示了分支数量、指令缓存未命中（I1）。这些数字是查询代码的控制流和代码局部性的指标。有几件事值得注意。首先，我们生成的 LLVM 代码包含的分支比 MonetDB 代码少得多。这并不奇怪，因为我们尝试在一个线性代码片段中生成直到下一个流水线断点的所有代码。其次，LLVM 代码的分支预测错误数量显著减少。一个例外是 Q2，但这基本上是 HyPer 的次优行为，与 LLVM 无关。（目前 HyPer 对溢出到磁盘非常悲观，并且大量复制字符串，这导致了超过 60% 的预测错误。MonetDB 避免了这些复制）。对于所有其他查询，LLVM 代码的预测错误比 MonetDB 少得多。有趣的是，MonetDB 的相对预测错误率相当好，正如 MonetDB 架构所预期的那样，但总的来说，MonetDB 执行了太多的分支，因此也有许多预测错误。

表3

下一个块显示了缓存行为，即一级数据缓存未命中（D1）和二级数据未命中（L2d）。对于大多数查询，这两个数字非常相似，这意味着如果数据不在一级缓存中，它可能也不在二级缓存中。这是非常大的哈希表的预期行为。同样，LLVM 代码显示出非常好的数据局部性，并且比 MonetDB 有更少的缓存未命中。与分支一样，Q2 中的字符串处理降低了缓存效果，但这将在未来的 HyPer 版本中修复。对于所有其他查询，LLVM 代码的缓存未命中比 MonetDB 少得多，最多可达十倍。

最后一个块显示了执行的指令数量。这些数字大致遵循表 2 中的绝对执行时间，因此并不令人惊讶。然而，它们清楚地表明，生成的 LLVM 代码比 MonetDB 代码紧凑得多。在某种程度上，这可能源于 MonetDB 的架构，它始终在二进制关联表（BAT）上操作，因此必须多次接触元组。

7. CONCLUSION

实验表明，以数据为中心的查询处理是一种非常高效的查询执行模型。通过使用优化的 LLVM 编译器将查询编译为机器代码，数据库管理系统可以实现与手写 C++ 代码相媲美的查询处理效率。

我们实现的将代数编译为 LLVM 汇编器的编译框架紧凑且易于维护。因此，以数据为中心的编译方法对所有新的数据库项目都具有前景。通过依赖主流编译框架，数据库管理系统可以自动受益于未来编译器和处理器的改进，而无需重新设计查询引擎。

8. REFERENCES

[1] P. A. Boncz, S. Manegold, and M. L. Kersten. Database architecture evolution: Mammals flourished long before dinosaurs became extinct. PVLDB, 2(2):1648–1653, 2009.

[2] P. A. Boncz, M. Zukowski, and N. Nes. MonetDB/X100: Hyper-pipelining query execution. In CIDR, pages 225–237, 2005.

[3] J. Cieslewicz and K. A. Ross. Adaptive aggregation on chip multiprocessors. In VLDB, pages 339–350, 2007.

[4] G. Graefe and W. J. McKenna. The Volcano optimizer generator: Extensibility and efficient search. In ICDE, pages 209–218. IEEE Computer Society, 1993.

[5] A. Kemper and T. Neumann. HyPer: A hybrid OLTP&OLAP main memory database system based on virtual memory snapshots. In ICDE, pages 195–206, 2011.

[6] K. Krikellas, S. Viglas, and M. Cintra. Generating code for holistic query evaluation. In ICDE, pages 613–624, 2010.

[7] C. Lattner and V. S. Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In ACM International Symposium on Code Generation and Optimization (CGO), pages 75–88, 2004.

[8] R. A. Lorie. XRM - an extended (n-ary) relational memory. IBM Research Report, G320-2096, 1974.

[9] S. Manegold, P. A. Boncz, and M. L. Kersten. Optimizing database architecture for the new bottleneck: memory access. VLDB J., 9(3):231–246, 2000.

[10] M. Mehta and D. J. DeWitt. Managing intra-operator parallelism in parallel database systems. In VLDB, pages 382–394, 1995.

[11] S. Padmanabhan, T. Malkemus, R. C. Agarwal, and A. Jhingran. Block oriented processing of relational database operations in modern computer architectures. In ICDE, pages 567–574, 2001.

[12] V. Raman, G. Swart, L. Qiao, F. Reiss, V. Dialani, D. Kossmann, I. Narang, and R. Sidle. Constant-time query processing. In ICDE, pages 60–69, 2008.

[13] J. Rao, H. Pirahesh, C. Mohan, and G. M. Lohman. Compiled query execution engine using JVM. In ICDE, page 23, 2006.

[14] K. A. Ross. Conjunctive selection conditions in main memory. In PODS, pages 109–120, 2002.

[15] T. Willhalm, N. Popovici, Y. Boshmaf, H. Plattner, A. Zeier, and J. Schaffner. SIMD-scan: Ultra fast in-memory table scan using on-chip vector processing units. PVLDB, 2(1):385–394, 2009.

[16] M. Zukowski, P. A. Boncz, N. Nes, and S. Héman. MonetDB/X100 - a DBMS in the CPU cache. IEEE Data Eng. Bull., 28(2):17–22, 2005.