Home Posts Tags

Contents

Paper Reading: Efficiently Compiling Efficient Query Plans for Modern Hardware

frankma included in database paper
   3630 words   8 minutes 

这篇paper是 Efficiently Compiling Efficient Query Plans for Modern Hardware, in VLDB, 2011。

对应15-721的Query Compilation & Code Generation部分，主要涉及数据库的查询编译技术，以提高现代硬件条件下的 查询引擎性能。

Introduction

随着现代CPU的进化，数据库在执行性能方面也在不断进化，常见的2类优化方向：向量化 和 编译执行。向量化在之前的MonetDB/X100有具体介绍，这篇主要介绍HyPer的CodeGen技术。

数据库如何执行一个query：传统的volcano处理模型，也叫做iterator模型，会重复调用算子的next方法来消费input并生成tuple结果。各个算子之间也比较容易组合。同时volcano出现在I/O是主要性能瓶颈的时代，因此在现代硬件水平下，它的一些问题也凸显出来了：

  • next 方法需要应用在 查询数据的每个tuple上，存在大量虚函数调用，影响现代CPU的分支预测，造成IPC降低
  • poor code locality(较差的代码局部性)，因为tuple-at-one-time，多个算子函数作用在一个tuple上，可能导致算子A执行完，刚进入cache的数据就冷却了，于是在第二次进入算子A，又要重新加载数据到register/cache中。因此，如果程序具有较高的局部性，大量的数据访问都在register/cache中，可以带来巨大的性能提升

因此，现代数据库系统采用 block tuples 的数据组织方式，以减少函数调用次数。然而，它也会带来一些问题：

  • 丢失了 iterator模型 的优势，pipeline data：一个tuple的数据放在 register 中，供各个算子消费使用，而不需要对数据copy或物化传递
  • 采用了block data的方式后，数据量变大就必须物化在cache/memory中，才能供下个算子使用，同时也需要更多的指令来完成，register <-> cache/memory 之间的转换

如下图，比较了tuple-at-a-time、column-at-a-time、vector-at-atime 和 Hand-Coded Program查询性能比较：

  • tuple-at-a-time查询时间最长，它受限于大量函数调用cost
  • 随着vector size增大，达到MonetDB最好点，这时候 函数调用cost已经被分担的较低了，同时loop-pipelining也提高了性能
  • column-at-a-time，是vector size的极端情况，这时候 数据量已经超过 CPU cache了，需要引入extra memory I/O，从而也影响到了查询性能
  • Hand-Coded Program，具有最好的执行性能，后面后详细介绍
/images/efficiently-compiling-efficient-query-plans-for-modern-hardware/figure1.jpg
Hand-Coded Performance

编译执行技术 相比 传统的 volcano-style 几个重要的区别：

  • 以数据为中心处理，而不是以operator为中心(数据在算子之间传递)。data centric的含义是，数据尽可能长时间的保存在CPU register中，从而提高data和code locality。为了实现这个目标，算子的边界会变得模糊
  • 数据不在是 pull 模型在operator之间传递，而是 operator push 数据
  • 使用LLVM做CodeGen

Query Compiler

Query Processing Architecture

为了最大化查询性能，必须最大化 data和code locality。而阻碍locality的算子，我们称为 pipeline-breaker：一个operator在处理input data时，需要将data移出register进行materialize，则它就是一个pipeline-breaker。

为了最大化locality，需要将数据尽可能keep在register中，如下两种方式的问题：

  • 经典的iterator模型：大量函数调用，导致register占用(函数入参/返回值)，导致input data无法一直keep在register中，造成pipeline-breaker，参考go-register-calling-background
  • chunk-based模型：虽然减轻了函数调用次数，但chunk的数据超过register的capacity，因此也是pipeline-breaker

总结下来：

任何基于 iterator-style 的处理范式，都会有pipeline-breaker的风险。因为它为了提供一个 基于迭代器的视图，必须为任意复杂度的operator的输出 提供一个线性化访问接口，因此数据不能一直存在register中，需要在各个operator之间传递，因此容易产生pipeline-breaker。

改进策略：

改变数据流方向，不再采用pull模型，而是push模型：从一个pipeline-breaker push数据到下一个pipeline-breaker。一次push之前，可能经过多个operators，它们会compile到一个code function中，这样当一个tuple放入register后，能够最大化的提升locality，减少memory访问次数。而pipeline-breakers之间需要materialize的数据，则依然保持正常。

如下图的pipeline-breakers例子，每个步骤都有很强的locality，其中需要和memory交互的地方只有 三个需要物化的地方 + 新tuples的读取 ：

  1. R1 经过 filter 后，物化 结果到 hashtable 中
  2. R2 经过 filter 后，执行 HashAggregation 后，物化 最终将结果到 hashtable 中
  3. 读取 第2步物化的结果，transfer到另一个 hashtable 中
  4. R3 的每个tuple 与 上面1和3步的hashtable，做probe操作，然后输入match的结果
/images/efficiently-compiling-efficient-query-plans-for-modern-hardware/figure3.jpg
Pipeline-Breakers

对应的伪代码如下：

  • 4段code fragment代表了上面4个操作步骤
  • 每个code fragment都包含了 多个operators 执行逻辑，并且fragment都不大
  • small code fragment + large data in tight loop 带来了很好的 code locality
/images/efficiently-compiling-efficient-query-plans-for-modern-hardware/figure4.png
Pipeline-Breakers

Compiling Algebraic Expressions

编译代数表达式的困难点：

基于volcano-style的计算模型，每个operator都实现了，统一定义的输入输出接口，任意operators之间也很容易组合。它是一个非常简单适用的模型(但付出的代价是，大量虚函数调用 和 内存频繁访问)。

而编译执行的区别是，operators之间的边界变得模糊了，一个fragment中可能包含多个operators，一个operator可能在多个fragments中。比如上面的第一个code fragment，包含了scan、selection 和 join的left部分。

因此，如何把多个operators处理逻辑混合起来，形成伪代码中的结构呢，文中给出了一种 抽象的定义(只负责给CodeGen用，并不是真实的方法)，每个operator提供2个接口定义：

  • produce()：如何从下层算子获取数据
  • consume(attributes, source)：produce完成后，执行本operator逻辑，将结果push到 parent operator consume方法

如何理解这两个接口的定义：一个operator相当于一个function，produce()是一个外部方法调用，consume()是当前function最后的执行调用，并返回结果。拿一个join/filter/scan的例子来说，伪代码如下：

  • join 作为最顶层的算子，调用left/right的produce，去获取下层filter算子数据
  • filter 继续调用 scan算子的produce 获取数据
  • scan 作为最底层的算子，通过filter的consume 返回数据
  • filter的consume会继续 调用join的consume，最终串起来
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

Join.produce() {
  // First, generate a loop over one side
  left_child.produce()
  // See consume for what gets generated in that loop

  // Then, generate a loop over the other side
  right_child.produce()
  // See consume for what gets generated in that loop
}

Join.consume(src) {
  if (src == left_child) {
    // This is called in a loop over the left child's result
    output << "add t into HT"
  } else {
    // This is called in a loop over the right child's result
    output << "for (t' in HT[t]) {"
      parent.consume(this)
    output << "}"
  }
}

Filter.produce() {
  // To generate a loop over its result, generate a loop over its child's result.
  child.produce();
}

Filter.consume() {
  // This is called in a loop over the child's result
  output << "if (";
    cond.produce()
  output << ") {"
    parent.consume()
  output << "}"
}

Scan.produce() {
  output << "for (tuple in T) {"
    parent.consume()
  output << "}"
}

Code Generation

真实场景下，需要编译成machine code，才能继续执行。文章提到，最开始采用的是generate C++ 的方式，在runtime阶段传递给compiler，作为shared library。然而，这种方式的问题是：编译C++的时间很慢，编译复杂的query到了秒级。

因此，文中采用了 Low Level Virtual Machine (LLVM) compiler 去生成 可移植的IR，最后通过LLVM提供的 JIT compiler 去执行。

因为，通过LLVM的方式，编译速度很快，并且它能提供很好的优化能力。实践中，LLVM主要用于tight loop的简单计算逻辑，复杂的处理逻辑还是需要C++代码具体实现。

总结

这篇作为经典的CodeGen介绍，在High Level上介绍了，传统volcano模型，到chunk-based模型，到编译执行技术带来的优势。

通过data centric + push模型算子融合，让数据尽可能长时间的保存在CPU register中，从而提高data和code locality，减少了memory访问cost。

后续还有篇Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask，更加详细的比较了 Vectorization 和 Compilation 在查询引擎中的特点，值得进一步学习。

Updated on 2022-01-20
 database, paper
Back | Home