Paper Reading: MonetDB/X100: Hyper-Pipelining Query Execution

这篇paper是 MonetDB/X100: Hyper-Pipelining Query Execution, in CIDR, 2005。

对应15-721的Query Execution & Processing部分，主要涉及数据库的向量化执行，以解决database在现代CPU上，只有较低的 IPC(instruction-per-cycle) 的问题。

Introduction

现代CPU每秒可以进行大量的计算，但前提是，这些工作是独立可并行执行的。因此，对 query-intensive 的 OLAP 数据库workloads，希望能够充分利用现代CPU的优势，实现更高的 IPC。

而调查发现，大多数DBMSs采用的传统 volcano 模型，抑制了编译器的优化，导致了较低的 IPC。

读者理解：我们知道 volcano 是一个 pull 的模型，需要从 planning tree 的顶点开始，以 tuple-at-a-time 的形式依次递推调用下去。因此，这中间存在在大量的 虚函数 调用，抑制了 CPU pipelining 的能力，从而无法实现较好的 指令级并行，导致了 IPC 偏低。

为了避免大量虚函数调用，很容易想到将 tuple-at-a-time 改变成 column-at-a-time，来一次性物化整列数据，再利用CPU pipelining能力达到高效计算。然而，物化整列数据带来了，大量内存访问，最终受限于memory bandwidth，影响CPU计算效率。

因此，文章采用了一种折中方案，设计出 MonetDB 的 新查询引擎：X100。

新引擎 采用了，vectorized query processing 模型，可以联想一下，之前paper reading中的chunk-based内存模型，它们的类似之处。

How CPUs Work

下图展示了2002年之前，每年的CPU的性能变化图，可以看出当时CPU性能，还是符合摩尔定律的描述，即预计18个月会将芯片的性能提高一倍（即 更小的制造工艺，更多的晶体管 使其更快），它是一种以倍数增长的观测。虽然，近年来这种增长已经在放缓。

同时注意下图左上角 的图例 CPU MHz，展示了 CPU时钟频率提升曲线，但它主要得益于 CPU基础技术：pipelining，将一个 CPU instruction 分为越来越多的 stage，则每个 stage 的工作就很少，因此，CPU的时钟频率就可以提高，并通过多个 硬件处理单元 并行执行 来加速整体指令的 执行速度。

比如，2004年的 Pentinum4 已经有了 31 pipeline stages。

pipelining

开始前，结合上面的介绍，感性理解下 pipelining 技术：假设 CPUs 是一个工厂，有许多流水线 stage执行不同的任务（类似上图中的IF组成的斜线），各个硬件处理单元就是流水线旁的工人，每个指令就是流水线上的产品，工人会将产品加工后，往下一个pipeline stage传递。

官方说法：Pipelining is the foundational technique used to make CPUs fast wherein multiple instructions are overlapped during their execution。

通过pipelining技术，可以让多条指令 重叠执行。它灵感来源于，汽车装配流程线。CPU的指令会被划分为多个stages，不同指令的不同stage是可以并行操作，通过多个硬件处理单元 并行执行 来加快指令执行速度。

如下图，一条指令被分为5-stage：

• Instruction fetch (IF)
• Instruction decode (ID)
• Execute (EXE)
• Memory access (MEM)
• Write back (WB)

在cycle 1时，指令x的IF stage进入pipeline，在cycle 2时，指令x进入ID stage，指令x+1进入IF stage。按照这个模式，随着clock cycle依次下去。在cycle 5时，CPU上的所有pipeline stages都在忙着不同的指令（需要斜着看下图）。

pipelining 看起来很美好，但 存在几个会打破它的问题：

• Data hazards (指令间前后依赖)：

  一个instruction需要上一个instruction的结果，才能进入pipeline。比如：Read-after-write，instruction x+1 必须在 instruction x 写完后，才进行读，否则读到错误的值。相同情况还有，Write-after-read 和 Write-after-write。

• branch misprediction：

  从上面的pipeline得知，我们需要在第一条指令还未完成时，第二条指令就需要进入pipeline，来保证pipeline上有源源不断的指令来执行。因此，如果代码中出现了 分支情况 (if-then-else)，CPU会通过一些算法，预测下一阶段的指令，从而保证源源不断的指令进入pipeline，而不会出现卡壳。

  但是，CPU如果预测错了branch，则这个pipeline整个会被清空，从fetch到execute阶段，从头再来开始。直观看来，misprediction会浪费大量clock cycle。

  回到数据库领域中的misprediction，比如依赖于input data的filter条件，是无法做预测的，因此会大大降低查询的执行速度，下面会介绍。

superscalar

除了pipelining技术外，现代CPU架构还提供了superscalar能力。处理器内核中，存在多个执行单元，在一个clock cycle里，可以同时派发 不同的instruction 在不同的执行单元 中执行。

这也就是我们说的，指令级并行。回到最上面的figure1，hyper-pipeling代表superscalar，看出 超标量架构 带来的性能提示 大于 CPU频率的提升。

如下图，是一个superscalar CPU pipeline，每个pipeline stage可以同时处理2个instruction。

compiler

平时写程序时，编译器 已经帮我们 做好了相应 optimization，以便利用到 上面说到的现代CPU特点。其中最重要的技术是，loop pipelining。

比如一个数组A，其中每个元素相互独立，需要对A进行计算F()->G()，且F()需要2个CPU cycle，则程序表达的逻辑为

F(A[0]),G(A[0]), | F(A[1]),G(A[1]), | .. | F(A[n]), G(A[n])

通过compiler可以转换为

F(A[0]),F(A[1]),F(A[2]), | G(A[0]),G(A[1]),G(A[2]), | F(A[3]),..

这样，我们可以利用到CPU pipelining和superscalar 能力，提高计算性能。比如基于chunk-based列存的内存模型，就可以利用到loop pipelining能力。

它的本质：将原来需要 8 个clock cycles执行的计算，缩减到 4 个 cycle，

更多Loop Optimizations参考

database

分析现代CPU和数据库领域的关系，比如一条SQL：SELECT oid FROM table WHERE col < X; 其中X随机分布在[0,100]之间。不同计算逻辑对应的benchmark如下图，predicated的版本，比branch版本，它的执行效率更高，并且与selectivity无关。

还有一点影响CPU计算的因素是，CPU cache misses。因为，所有指令中，大约30%的instruction，是memory load/store，去访问DRAM，这会产生50ns的延迟，对3.6GHz的CPU来说，50ns可以执行180个cycles。

因此，只有当CPU访问的数据，都在CPU cache中时，CPU才能得到，最大化的计算吞吐。在数据库领域cache-conscious的优化，比如cache-aligned B-trees 和 radix-partitioned hash-join。

总结，现代CPU已经变得非常复杂，CPU cache，branch prediction，compiler的优化等，会让CPU执行效率 相差几个数量级。文章给出的方向是：尽可能将，OLAP的查询计算任务，交给 CPU和compiler，以提高查询性能。

Microbenchmark TPC-H Query 1

这一章主要关注在，基本的 表达式计算，不考虑复杂的关系操作(join)。 Query 1 的特点是：

• filter过滤的selectivity很高，对于6M的lineitem表，最终filter出5M的数据
• 分组聚合数据较少(4个聚合列)，因此只需要 较小的 hash-table，能够在CPU cache中完成高效计算

Query 1 on MySQL

我们知道传统的DBMS，在表达式计算时候，基于tuple-at-a-time的方式，这个过程除了计算本身，还有许多额外成本，尤其是当tuple非常多时，整体cost会非常大，造成了查询性能低。如下图中MySQL4.1的执行分析，可以看出几点：

(下图中各列说明：cum: 总累计时间 / excl: 总执行时间的占比 / calls: 方法被调用次数 / ins: 方法每次调用平均需要的指令数 / IPC: 方法达到的instruction per cycle数)

• 图中的加粗方法 为实际的real work，但只占 总执行时间的 10%
• 创建和查询hash-table，占据了总时间的 28% (ut_fold_ulint_pair和ut_fold_binary在计算字段hash值，hash_get_nth_cell在计算cell位置)
• 剩余 62% 的时间，花在了类似方法 rec_get_nth_field 上面，这些函数 在浏览MySQL record
• Item_func_plus::val这样的计算函数，每次加法 使用了 38个指令，38/0.8=49个cycle。原因是：缺失了loop pipelining优化，MySQL每次只对一个tuple执行加法计算，一个加包含了四个相互等待的指令(load src1, load src2, add, store)，平均每个指令延迟大概5个cpu cycle，因此一次加法操作，用掉了 20 个cpu cycles。49-20=29剩下的cycle用在了jumping, push/pop stack的调用上

总结，MySQL基于tuple-at-a-time模型，带来的问题：

• 由于一次计算只针对一个tuple，compiler无法用loop pipelining优化。同时计算指令间相互依赖，必须通过empty pipeline slots来等待上一个指令结果。因此，这些都加剧了指令的延迟
• 函数调用的指令成本，需要在每一次操作中，导致cost进一步加剧

Query 1 on MonetDB/MIL

首先MonetDB是列存格式，每个column存储在 Binary Association Table (BAT) 中，它使用一种 代数查询语言 MIL 进行查询。

不同于关系代数，MIL代数语言没有任何自由度。它的每个operator都必须有 固定格式输入格式 和 输出格式。

下图展示了TPC-H Query 1在MonetDB上的表现，可以看出：

• 20个MIL调用占据了 99% 的查询时间
• MIL操作的瓶颈在memory带宽，而不在CPU上了
  • 当查询数据量较小时候，SF=0.001(scaling factor控制数据量大小)，计算的中间数据完全可以放到CPU cache中，消除了DRAM访问cost。下图中看出，带宽大概在1.5GB/s
  • 当查询数据量较大时候，SF=1，必须要访问DRAM，带宽只能达到500MB/s

总结，MonetDB基于column-at-a-time模型，它的优缺点：

• pros：操作基于array，compiler能够利用到loop-pipelining
• cons：计算所需column的全量物化，并且在计算过程中产生了大量中间结果，造成了内存带宽压力

X100: A Vectorized Query Processor

结合上面Microbenchmark结果，X100需要实现一种 更高效的CPU查询效率，改进了如下几个可能产生的 bottleneck 部分：

• Disk：基于列存的存储结构，做了轻量级压缩，减少了带宽使用。同时利用了高效的顺序读(预读优化)

• RAM：基于列存的内存模型，节约内存空间和带宽使用。同时利用显示的基于平台的 memory<->cache 访问优化(SSE prefetching，参考Performance of SSE and AVX Instruction Sets搜索prefetch)

• Cache：采用类似volcano的向量化处理模型，vector是一个可以在CPU cache驻留的小块数据(如1000个tuple的列组成的chunk)，也是算子操作的基本单元。

• CPU：基于vectorized的primitives(翻译成原语，即由若干条指令组成的程序段，用于完成特点功能，中间不可被中断。它在操作系统中引入的概念，表示未经加工东西，在计算机中代表不可拆分的操作，必须当做一个整体对待，要么成功或失败，中间不能被打断，比如你在for里的计算。而不是翻译成原始数据类型)，可以让compiler利用到loop-pipelining，提高CPU吞吐(通过减少load/store指令数)

Query

X100采用基于volcano的iterator模型(也叫pipeline模型)，对于上面的TPC-H Query 1解析完的执行计划如下图，各个部分的算子作用：

• scan：扫描底层的DataSource，也接受projection下推
• selection：接收scan plan和filter expression，去决定哪些行数据最终被输出
• projection：接收selection plan和一系列expression(如ColumnExpr、MathExpr和CastExpr)，这些exprs会计算在selection plan上
• aggregate：接收input plan、group exprs 和 agg exprs。一般通过HashAggregate构造hashtable进行聚合计算

Vectorized Primitives

X100采用column-wise vector layout，主要原因是，执行 基于向量化的计算原语。由于它具有较低的灵活度，每个执行只对 特定类型的 定长数组 做计算。这种简单的形式，帮助compiler做出更加激进的loop-pipelining优化。如下的vectorized floating-point addition方法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

map_plus_double_col_double_col(int n,
double*__restrict__ res,
double*__restrict__ col1, double*__restrict__ col2,
int*__restrict__ sel)
{
  if (sel) {
    for(int j=0;j<n; j++) {
      int i = sel[j];
      res[i] = col1[i] + col2[i];
    }
  } else {
    for(int i=0;i<n; i++)
      res[i] = col1[i] + col2[i];
  }
}

上面是2个double column列数组相加操作，其中sel是selected行index，比如figure6中的selection vector，即满足条件的行index array。

X100中实现了几百个这样的vectorized primitives，为什么会有这么多，简单理解，double array + double，double array + double array等等，类似的不同类型的计算组合。通过这样的hardcode，帮助了更高效的优化。

TPC-H Experiments

最后惯例的benchmark，TPC-H来对比不同引擎的分析查询能力，如下图，X100相比MIL，在Query1(SF=1)上提升了7倍

如下图展示的trace信息，证明X100的优化点效果：

• all primitives 的执行都只要较低的CPU cycle per tuple，即使复杂的原语(aggregation)也很低。这受益于vectorized primitives带来的loop-pipelining
• chunk-based模型，大部分数据都放在CPU cache上，因此带来了很高的bandwidth(超过了7.5GB/s)

Vector Size Impact：

• X100当前采用的size=1024
• 如果size过大：无法放入到CPU cache中，退化到DRAM，带宽成为瓶颈
• 如果size过小：无法充分利用loop pipelining，极端一点就退化到tuple-at-a-time

总结

这篇是向量化执行引擎的经典论文。

通过介绍现代CPU的特性，到现有数据库tuple-at-a-time和column-at-a-time在分析型场景下 分别遇到的 指令延迟 和 内存带宽瓶颈 问题。

从而提出X100 的 chunk-based 向量化查询引擎，通过loop pipelining 和 chunk常驻cache，解决上面的问题。