Block Oriented Processing of Relational Database Operations in Modern Computer Architectures

[mrdrivingduck]

10.1.1.137.6207.pdf

[mrdrivingduck]

DBMS 正在面临低缓存利用率和低处理单元利用率的问题。本文提出基于 block 的查询处理策略能够更好地利用处理器和缓存，从而获得更好的性能。

目前对于简单查询来说，CPI (Clock Per Instruction) 的值非常高，大约需要 1.2-1.8 个时钟周期才可以执行完一条指令。对现在的 RISC 处理器来说，每一个时钟周期可以同时执行多条指令，也就是说峰值 CPI 可以是一个很小的分数。目前的 DBMS 很难有效利用现代的超标量处理器。在科学型计算的工作负载下，将会在处理器中产生大量的 stall 和 cache miss。

本文在 DB2 上实现了一个基于 block 的执行引擎，主要特性是在执行器算子之间产生一个 block 的中间结果，以及一个 block 描述符用于描述 block 中的内容。同时引入面向 block 的执行算法。实验结果表明，这个引擎在处理器和内存资源的利用率上更好：

1. 更好的指令流水线和避免分支预测失败
2. 最小化数据 cache miss
3. 减少指令跳转长度和函数调用的开销
4. 提升指令 cache 的利用率

[mrdrivingduck]

Motivation

传统 DBMS 的 demand-driven 流水线执行模型：一个进程或线程能够完成所有的执行：

• 避免进程间通信
• 避免进程同步和调度
• 最小化数据拷贝

目前大部分的 DBMS 只有在涉及到 I/O 的时候才会以 block 为单位进行处理，其它操作都是以记录为单位进行处理。目前存在的问题：

1. 数据和指令的 cache 局部性非常差，因为计划树的算子流水线非常长，可能会导致反复 load 和 store 算子内的数据结构和指令
2. 条件分支开销大，每个算子都会进行一系列的检查操作，很可能会带来 CPU 内的 stall
3. 指令数量较大，因为每条记录都会执行一次相同的指令处理流程

迭代器模型在解决这些局限上有很大的空间。

[mrdrivingduck]

Block Oriented Processing

向量风格的处理，能够分摊条件检查和分支的开销，从而有效利用 CPU 和内存。对于多处理器来说也是有效的，因为每个处理器可以处理自己的那一块数据。

每一个算子可以修改已有的列或产生新的列，新列的空间需要被预先分配。重用已有的块内空间可以降低或避免不需要的数据拷贝。

在行存中，如果一条记录比较大，那么一个 block 中无法容纳很多条记录；但对于列存来说，分配一个较大的向量化 block 依旧能够维持较好的缓存利用率。因为大部分的 block 操作都是在两个输入列上进行操作，并产生一个新的列。只有三个列向量需要被放在缓存中。

Block Descriptor

用于描述 block 内的模式：

• 指向 block 的指针
• block 的大小
• 每一条记录的大小
• block 中记录的数量
• 每条记录中的 field 以及 offset

Block Oriented Operators

以一个或多个向量作为输入，产生一个向量或数值作为输出。对运算前的空值检查全都以 block 为单位进行；具体的运算也以向量为单位来进行循环，循环非常紧凑。

Performance Discussion

• 通过仔细选择 block size，最大化数据缓存的利用；在多个算子之间复用 block 空间；对同一个 block 中的数据循环调用操作函数可以保证指令缓存的局部性
• 只对 block 进行一次条件检查，最小化循环内的分支条件，得到更好的指令流水效果
• 最小化函数调用的次数和指令数量