Mr Dk.
## Integrating Compression and Execution 压缩能够通过减少磁盘寻找时间、减少数据移动时间、提升 buffer pool 命中率来提升 I/O 性能。带来的问题是如何选用压缩算法。如果选择不当，那么原先的 I/O 瓶颈可能会变成 CPU 瓶颈。 - NULL 值压缩：连续的 0 或空白被替换为有多少个连续空值的 **描述** - 字典编码：将值编码为键值对，存放在字典中，字典需要能够被装在缓存里 - Run-length 编码：对列中的连续相同值进行编码，存放为 `` 的三元组 - 对排序后的列效果最好...
DBMS 正在面临低缓存利用率和低处理单元利用率的问题。本文提出基于 block 的查询处理策略能够更好地利用处理器和缓存，从而获得更好的性能。 目前对于简单查询来说，CPI (Clock Per Instruction) 的值非常高，大约需要 1.2-1.8 个时钟周期才可以执行完一条指令。对现在的 RISC 处理器来说，每一个时钟周期可以同时执行多条指令，也就是说峰值 CPI 可以是一个很小的分数。目前的 DBMS 很难有效利用现代的超标量处理器。在科学型计算的工作负载下，将会在处理器中产生大量的 stall 和 cache miss。 本文在 DB2 上实现了一个基于 block 的执行引擎，主要特性是在执行器算子之间产生一个 block 的中间结果，以及一个 block 描述符用于描述...
## Motivation 传统 DBMS 的 demand-driven 流水线执行模型：一个进程或线程能够完成所有的执行： - 避免进程间通信 - 避免进程同步和调度 - 最小化数据拷贝 目前大部分的 DBMS 只有在涉及到 I/O 的时候才会以 block 为单位进行处理，其它操作都是以记录为单位进行处理。目前存在的问题： 1. 数据和指令的 cache 局部性非常差，因为计划树的算子流水线非常长，可能会导致反复 load 和 store 算子内的数据结构和指令 2. 条件分支开销大，每个算子都会进行一系列的检查操作，很可能会带来...
## Block Oriented Processing 向量风格的处理，能够分摊条件检查和分支的开销，从而有效利用 CPU 和内存。对于多处理器来说也是有效的，因为每个处理器可以处理自己的那一块数据。 每一个算子可以修改已有的列或产生新的列，新列的空间需要被预先分配。重用已有的块内空间可以降低或避免不需要的数据拷贝。 在行存中，如果一条记录比较大，那么一个 block 中无法容纳很多条记录；但对于列存来说，分配一个较大的向量化 block 依旧能够维持较好的缓存利用率。因为大部分的 block 操作都是在两个输入列上进行操作，并产生一个新的列。只有三个列向量需要被放在缓存中。 ### Block Descriptor 用于描述 block 内的模式： - 指向 block 的指针 - block 的大小 - 每一条记录的大小...
> Good paper, look forward to it. 靠大佬分享了 😅
遵循对一个东西开喷就要讲清楚理由的原则，Andy Pavlo 把他在网课里随口说的 _I hate mmap_ 变成了一篇完整的论文。甚至还在页眉上做了点文章： 🤣  Memory-mapped (mmap) 文件 I/O 是一个 OS 提供的特性，可以让用户空间的程序用指针像读写内存一样读写文件，即使文件无法在内存中装下。POSIX mmap 系统调用可以将一个文件映射到进程的虚拟地址空间中，并在进程读写文件时按需加载页面。由 OS 透明地管理页面的 load 和 evict，从进程的视角来看只有指针（内存）操作。 传统的 DBMS（这里特指 larger-than-memory 的 DBMS）使用 read/write 系统调用实现...
## Background ### MMAP Overview 使用 mmap 访问文件的步骤： 1. 程序调用 mmap，获得一个指向映射文件内容的指针 2. OS 在进程虚拟地址空间保留一部分用作映射，但不装载文件的任何部分进内存 3. 程序使用指针访问文件内容 4. OS 试图获取页面 5. 映射缺失引发 page fault，OS 将页面调入物理内存 6. OS 在页表中加入虚拟内存到物理内存的映射条目 7. CPU 将这个页表条目缓存在本地...
## Problems With MMAP 本章详细说明了 mmap 替换 DBMS buffer pool 之后会引发的问题，以及解决这些问题所需要付出的代价。 ### Problem 1: Transactional Safety 事务是 DBMS 对文件把控最重要最复杂的环节。由于 DBMS 通过 mmap 把页面在内存与磁盘间同步的权利下放给 OS，那么 OS 可以在任何时间将脏页刷进磁盘，而 DBMS 不会收到任何通知。那么 DBMS 就没法知道一个页面有没有真正进入磁盘。这对事务的回滚、提交来说是致命的。...
## Experimental Analysis 对比：使用 fio 存储跑分工具，运行几个常见的 I/O pattern - Direct I/O（模拟 buffer pool，不使用 OS 的 page cache） - mmap ### Random Reads Mmap 就算使用了符合 I/O pattern 的 hint，性能也较差。性能下降始于 page cache...
目前的 DB 在现代 CPU 上处理 **计算密集型** 应用时，IPC (Instructions-Per-Cycle) 指标非常低。本文分析了原因，并给出了一些设计查询执行器的意见。此外，本文提出了一个新的向量化查询执行引擎，CPU 效率较高。 现在 CPU 只有当能够找到足够多 **无关** 指令时，才能充分利用并行执行的能力。OLAP 负载就需要做大量的无关计算，理论上应该具有较高的 IPC 效率。然而，已有研究表明，DB 在现在 CPU 上运行这些负载时，取得了较低的 IPC 效率。所以需要深入分析一下关系型数据库是如何在现代超标量处理器上做查询执行的。 结论是，DBMS 普遍采用 **火山迭代器** 模型，一次处理一个元组，带来巨大的解释开销，同时使编译器无法使用一些性能攸关的优化技术。本文中实现了一个列式执行模型，使 DB 不再受火山模型的局限。