Query Execution in Column-Oriented Database Systems

[mrdrivingduck]

主讲列式存储中的查询执行。Daniel J. Abadi 同学的博士论文，好长一篇。每一个 chapter 都是一篇独立的论文了。还是读这篇更详细点的吧。

[mrdrivingduck]

Abstract

在一维的存储世界中模拟二维关系表的两种方式：

• 按行存储：适合事务数据处理，因为业务通常只访问某几行
• 按列存储：适合分析型处理

本文经过分析得出，一个特别为列式存储设计的查询执行器对于获取性能来说至关重要。本文提出了 C-Store，分为存储层 + 执行层。提升性能的三个要点：

1. 执行层能够直接操作压缩后的列数据，提升 I/O 和 CPU 的效率；解决执行器扩展性的问题
2. 尽可能推迟各列被 join 成行的时机
3. invisible join

[mrdrivingduck]

Introduction

分析型应用的特点：

• 不可预测：在事务型业务中，查询的模式基本是固定的（比如编码在应用程序中的 prepared statement）；而分析型业务比较自由
• 持续时间长：读取和计算的数据量大
• 面向读多于面向写：以只读查询为主，写入性能较差
• 聚焦于属性，而不是聚焦于实体：查询基本只会聚焦在某几个列上

几种构建列式存储的方法：

• 对行存进行垂直分区，无需修改 DBMS 代码
• 修改物理存储层为列存，数据在进入执行层之前恢复为行存，无需修改执行器代码
• 修改物理存储层和执行层，充分针对列存场景进行优化：不同列的数据组成行元组的时机尽可能延迟，减少元组的构建开销

优化列式存储性能的更深层方法：

• 压缩：列存有着更低的信息熵，压缩后可以节省 I/O；有些数据类型可以直接在压缩后的数据上操作；但执行器必须知道某一列是怎么压缩的，这可能会为执行器带来可扩展性的问题（一堆 if 语句）——本文试图解决这个问题，使得添加新的压缩算法不需要修改执行引擎代码
• 元组构造：大部分查询访问多于一个列，且大部分输出标准（ODBC / JDBC）都是面向行的，因此多个列的数据必须要被重组为行元组，那么两个因素很重要：怎么 重组和 何时重组；重组越晚，就可以避免越多最终会被过滤掉的行元组生成
• Invisible Join

[mrdrivingduck]

Column-Store Architecture Approaches and Challenges

三个等级的实现方式：

• 行存模拟列存
• 列存 + 行存执行器
• 列存 + 列存执行器

使用行存来模拟列存的几种方案（性能都不好）：

• 使用行存表来单独存储表的每一列，每个表包含两列：<ctid, value>
  • ctid 用于把属于同一个行的各列数据串联起来
  • 查询重写，使各个列表通过 ctid join
  • 列表中每个元组的开销过大
• 为表中的每一个列建索引
  • 如果在一个列上没有过滤条件，那么 index only scan 比 heap scan 慢得多
• 物化视图（理想情况，结果已提前生成）

列存 + 行存执行器：

• 在物理上每个列单独存放，保证所有列的存放顺序一致（每列的第 i 个数据都是第 i 个行元组的数据），这样隐含了 join key，不再有行存上 join 的问题
• 必须在查询开始执行前重建行元组（因为执行器还是基于行存的）

列存 + 列存执行器：

• 行元组重建可以被延迟
• 或许可以不需要读取不被输出的列，更少的数据将会被搬运到内存中

三种实现方式，实现难度逐渐增大，但优化空间和性能也在逐步提升。

[mrdrivingduck]

C-Store Architecture

每个表被表示为 投影 的集合，每个投影是一个表的子集，包含了表的所有行以及 某几列。每个投影中的各个列单独存放，但行顺序相同。表中的每个列至少会出现在一个投影中，一个列可以被存储在多个投影中（以不同的顺序）。

C-Store 中包含：

• RS (Read-optimized Store)
• WS (Write-optimized Store)：包含最近的写入和更新

由 Tuple Mover 周期性地把 WS 中的内容转移到 RS 中。

存储层上，投影中的每个列被存放在一个单独的文件中，被分为 64KB 大小的 block，每一个 block 可以使用最适合这个 block 的压缩算法。

C-Store 的算子与其它关系型数据库相比：

• 表达式计算产生的是 bit-column，可被用于高效的与或运算
• 投影没有开销
• Join 产生的是 position 而不是值

向量化执行：一次性获取多个属性值，从而有效利用 loop pipelining，提升 CPU 使用效率。

[mrdrivingduck]

Integrating Compression and Execution

压缩能够通过减少磁盘寻找时间、减少数据移动时间、提升 buffer pool 命中率来提升 I/O 性能。带来的问题是如何选用压缩算法。如果选择不当，那么原先的 I/O 瓶颈可能会变成 CPU 瓶颈。

• NULL 值压缩：连续的 0 或空白被替换为有多少个连续空值的 描述
• 字典编码：将值编码为键值对，存放在字典中，字典需要能够被装在缓存里
• Run-length 编码：对列中的连续相同值进行编码，存放为 <value, start_position, run_length> 的三元组 - 对排序后的列效果最好
• Bit-Vector 编码：即所谓 bitmap 编码，适合表示布尔值（比如是否存在）
• 重量级压缩：Lempel-Ziv 编码（gzip 的实现）