列式存储格式与压缩

数据仓库与事务型数据库的不同主要在于它们的存储引擎结构。操作型系统优化单个记录的写入，使用行式存储；而分析系统则需要以低延迟处理数十亿条记录的聚合。这一需求使得转向列式存储格式成为必需。

在行式系统（如PostgreSQL或MySQL）中，数据在磁盘上按行物理相邻存储。为了获取单个属性，例如从 sales 表中获取 total_amount，存储引擎必须将整个行块读入内存，并丢弃不相关的字段。

在列式格式中，单个列的值是连续存储的。这种物理组织方式显著减少了分析查询所需的输入/输出（I/O）带宽。如果一个表包含100列，而查询只选择5列，列式引擎将只获取与这5列对应的数据块。

假设一个表有 $N$ 行和 $k$ 列。令 $s(c_i)$ 为列 $i$ 的平均字节大小。表的总大小约为：

$S_{total} = N \sum_{i=1}^{k} s(c_i)$

在全表扫描操作中，当查询请求列的子集 $Q \subset \{c_1, ..., c_k\}$ 时，行式存储的I/O成本与 $S_{total}$ 成正比。对于列式存储，成本只与请求的数据成正比：

$Cost_{IO} \approx N \sum_{c_j \in Q} s(c_j)$

由于分析查询通常访问不到可用列的15%，I/O吞吐量的减少通常是一个数量级。

存储布局可视化

下图对比了行式存储和列式存储中数据块的填充方式。请注意列式布局如何将同构数据类型分组，这是对后面讨论的压缩技术来说一个主要因素。

物理块放置的对比。行式存储在一个块内交错放置混合数据类型。列式存储将数据类型分隔到不同的块中。

压缩算法

列式存储的第二个优点是可压缩性。由于单个物理块只包含一个列的值，数据是同构的。整数存储在整数旁边，字符串存储在字符串旁边。这种一致性使得压缩算法能够达到明显更高的比率（通常是3:1到10:1），相比行式块。

Snowflake和Redshift等现代数据仓库根据数据特性自动应用不同的编码算法。

游程编码 (RLE)

RLE对于基数低（少量唯一值）且已排序或已聚类的列非常有效。引擎不再存储重复值，而是存储值及其连续出现的次数。

考虑一个按状态排序的 status 列： 原始数据：['ACTIVE', 'ACTIVE', 'ACTIVE', 'INACTIVE', 'INACTIVE'] RLE：[('ACTIVE', 3), ('INACTIVE', 2)]

这减少了存储占用并加速处理。查询执行引擎可以直接在压缩数据上操作。例如，COUNT(*) 操作只需简单地将游程长度求和，而无需解压缩值。

字典编码

对于 Customer_City 或 Product_Category 等中等基数的列，字典编码用小整数替换长字符串。引擎维护一个将值映射到ID的字典。

原始数据：['笔记本电脑', '智能手机', '笔记本电脑', '平板电脑'] 字典：{0: '笔记本电脑', 1: '智能手机', 2: '平板电脑'} 编码数据：[0, 1, 0, 2]

这使得CPU在过滤时能够处理整数比较而非字符串比较，从而计算成本更低且更利于缓存。

增量编码

增量编码用于单调递增或变化小的数值数据或时间戳。引擎不再存储完整整数（可能需要4或8字节），而是存储相邻值之间的差异。

原始数据：[1638400100, 1638400105, 1638400110] 增量（基准：1638400100）：[0, 5, 5]

增量通常可以用更少的比特表示，从而实现“位打包”，即多个值被打包到一个标准的整数词中。

向量化处理与SIMD

列式格式使向量化查询执行成为可能。由于数据以单一类型数组的形式排列，现代CPU可以使用SIMD（单指令多数据）指令。

在标准的行式迭代中，CPU一次处理一个值：

# 标量处理逻辑（伪代码）
for row in rows:
    if row.quantity > 10:
        result.add(row)

在向量化处理中，CPU将一批列值加载到向量寄存器（例如AVX-512）中，并在一个时钟周期内同时对所有值应用比较。

$V_{result} = V_{quantity} > [10, 10, ..., 10]$

这种硬件层面的优化减少了每行的CPU周期并改善了L1/L2缓存局部性，因为CPU缓存填充的是相关列数据，而非行中不相关的字段。

对查询性能的影响

减少的I/O和高压缩的结合，带来查询性能的非线性改进。然而，这也伴随着昂贵的写入操作。修改列式数据库中的单个行通常需要重写磁盘上的多个数据块，这就是MPP系统更倾向于批量写入而非单行插入的原因。

下图显示了随着查询列数量的变化，行式和列式存储之间的性能差异。

存储引擎的性能特点。列式存储在获取少量列时保持低延迟，但当查询选择几乎所有列（重建完整元组）时，其性能会趋向于行式存储。

元数据和块头

为了管理这些压缩块，MPP系统使用大量的元数据头。每个文件或微分区都包含一个头部区域，详细说明该块内每个列的最小和最大值。

当查询包含一个过滤谓词（例如 WHERE order_date > '2023-01-01'）时，查询优化器会在解压缩块之前检查这些头部。如果该块的最大 order_date 是 '2022-12-31'，引擎就会跳过整个块。这个机制，称为块修剪或区域映射，允许系统完全绕过千兆字节的数据，进一步依赖列式结构以与访问模式对齐的方式物理组织数据。