在数据量爆炸式增长的时代，数据库存储成本与查询性能之间的权衡成为系统设计者的核心挑战。压缩技术是平衡这一矛盾的关键杠杆，但盲目应用压缩算法往往事倍功半，甚至可能因额外的 CPU 开销拖垮查询性能。本文旨在穿透具体实现的迷雾，回归信息论与数学模型的本源，为数据库压缩的工程实践提供一套可量化、可推演的决策框架。我们将从香农熵出发，解析主流压缩算法的数学本质，揭示列存布局与压缩的协同效应，并最终落脚于一套可操作的参数化启发式指南。
一、理论基础：香农熵与无损压缩的绝对极限
任何关于数据压缩的讨论，都必须始于克劳德・香农的信息论。对于一个离散随机变量 (X)，其取值为 (x_i)，对应的概率为 (p_i)，则其香农熵定义为：
[H (X) = -\sum_i p_i \log_2 p_i \quad \text {(比特 / 符号)} ]
这个公式揭示了数据中固有的、不可压缩的 “信息量”。香农源编码定理指出：任何无损压缩编码的平均码长 (L) 必须满足 (L \ge H (X))。如果使用最优的前缀码（如算术编码），可以达到 (H (X) \le L < H (X)+1) 的逼近。
对于数据库的一列（Column）数据，若包含 (n) 个值，则其理论上的最佳压缩后尺寸约为 (n \cdot H (X)) 比特，再加上模型本身（如字典、块索引）的元数据开销。这为评估任何实际压缩算法的效率提供了一个黄金标准：我们距离熵极限还有多远？
当面对多列关系时，若将各列 (C_1, \dots, C_k) 联合建模，压缩极限是联合熵 (H (C_1,\dots,C_k))。如果各列独立编码，则总下限为 (\sum_j H (C_j))。然而，现实中列之间常存在强相关性（例如 “城市” 与 “邮政编码”），此时条件熵 (\sum_j H (C_j \mid C_{<j})) 可能远小于独立熵之和。这正是语义压缩或预测性压缩（如使用机器学习模型预测一列值并存储残差）的数学基础，旨在逼近更紧致的条件熵下限。
二、主流压缩算法的数学模型解析
实际数据库系统不会对每列运行算术编码器，而是采用结构化的编码方案，其效率依然可以用熵的视角来审视。
1. 字典编码 (Dictionary Encoding)
字典编码将每个不同的值映射为一个整数 ID，并存储一个反向查找字典。假设一列有 (k) 个不同值，朴素情况下每个 ID 需要 (\lceil \log_2 k \rceil) 比特。若值的分布倾斜，并对 ID 采用变长编码，则其下限仍是该列值的熵 (H (X))。
总存储成本可分解为：
- 数据部分：(n \cdot b) 比特，其中 (b) 是每个 ID 的比特数（通常经位打包优化）。
- 字典部分：(k \cdot s) 字节，(s) 取决于原始值的类型和编码。
工程权衡：字典编码在基数（(k)）较低或分布高度倾斜时效益最大。当基数接近行数（(k \approx n)）时，(b) 变大，字典开销占主导，收益甚微。其优势在于解码速度快，且 ID 的比较、范围过滤可直接在整数上进行，CPU 和缓存友好。
2. 游程编码 (Run-Length Encoding, RLE)
RLE 将连续重复的值序列压缩为（值， 长度）对。设一列长度为 (n)，共有 (r) 个游程。编码成本约为：
- 值部分：(r \cdot b_v) 比特（每个游程的值 ID）
- 长度部分：(r \cdot b_\ell) 比特（表示游程长度的比特数）
平均每值比特数为 ((r \cdot (b_v + b_\ell))/n)。显然，当 (r \ll n)（即游程长、数据高度聚集）时，RLE 效率极高。
与熵的关系：如果数据已排序或与排序键高度相关，其 “游程过程” 的熵很低，RLE 可以逼近该熵下限。若数据为独立同分布且基数高，则期望游程长度接近 1，RLE 会退化为存储原始数据并附加额外开销。
3. 增量编码与帧间参考 (Delta & Frame-of-Reference)
对于数值列，尤其是单调或接近单调的序列（如时间戳、自增 ID），更高效的编码是存储差值。
- 增量编码：存储连续值之间的差值 (\Delta)。若序列缓慢变化，(\Delta) 的熵远低于原始值的熵。
- 帧间参考：对于一个数据块，找出最小值作为 “基准”，存储每个值与该基准的偏移量。当块内数值范围较小时，偏移量的熵显著降低。
这些编码本质上是为数据寻找一个 “预测器”，并存储预测误差，其压缩效率取决于预测的准确性，数学上对应的是条件熵 (H (X \mid \text {predictor}))。
三、列存布局：压缩的天然放大器
列式存储将同一列的值连续存放，这一简单的布局改变，从数学上深刻影响了局部熵的分布，从而使上述简单编码的效率倍增。
在行存中，不同类型的数据交错排列，局部序列的统计特性混乱，熵值较高。而在列存中，连续存储的是同类型、同语义的值，它们天然具有更低的信息熵：大量重复的状态码、聚集的日期范围、相近的数值。此外，通过对表按某一常用过滤列（如时间）进行排序或分区，可以人为地在每个存储单元（块或行组）内创造极低的局部熵环境 —— 例如，长串相同的客户 ID 或地区代码。
正如 MotherDuck 列存指南中指出的，列存布局使得高级压缩技术成为可能，并常能实现相比行存数量级提升的压缩比。这不仅降低了存储成本，更重要的是，减少了解析查询所需读取的物理 I/O 数据量，而 I/O 往往是分析型工作负载的首要瓶颈。
然而，这种优化并非没有代价。列存对写操作不友好：单行更新需要修改多个列文件，导致写放大。此外，需要重构完整行的查询（如 SELECT *）可能比行存更慢。这是一个典型的工程权衡：为优化的读取模式牺牲了写入和全行扫描的效率。
四、量化权衡：一个工程成本模型
要做出明智的压缩决策，我们需要一个量化的成本模型。一个实用的抽象是将总成本视为加权和：
[\text {总成本} = w_s \cdot \text {存储字节} + w_i \cdot \text {扫描 I/O 字节} + w_c \cdot \text {CPU 周期数} ]
其中权重 (w_s, w_i, w_c) 由具体的业务场景和硬件成本决定。例如，在云存储按量付费且查询不频繁的场景，(w_s) 较高；在需要实时交互分析的场景，(w_i) 和 (w_c) 则更为关键。
基于此模型，我们可以理解核心的权衡维度：
- 压缩率 vs. CPU 开销：更复杂的算法（如算术编码）更接近熵极限，但编解码的 CPU 成本高昂。简单的字典 + 位打包或 RLE 通常是 “足够好” 且解码极快的选择。
- 读性能 vs. 写性能：列存系统为读而优化，通常将写入缓冲为大段不可变数据块，一次性压缩后写入。需要频繁重优化编码字典的算法会被避免。
- 元数据开销 vs. 适应性：为每个数据块定制字典和编码可以更好地匹配局部统计特性，降低熵，但增加了元数据管理和复杂度。
五、可落地参数与启发式指南
基于熵感知，我们可以为常见数据类型制定编码选择清单：
| 数据类型 | 特征 | 推荐编码 | 关键参数与说明 |
|---|---|---|---|
| 低基数分类数据 | 国家、状态枚举，基数 k < 1000 | 字典编码 + 位打包 ID | 计算 (b = \lceil \log_2 k \rceil)，若分布倾斜可评估变长编码收益。考虑与 RLE 联用（如果数据已排序）。 |
| 中基数偏态分类数据 | 产品 ID、用户 ID，基数中等，但少数值高频出现 | 字典编码 | 评估字典大小 (k \cdot s) 与数据部分 (n \cdot b) 的比例。可尝试按频率排序字典，并对高频 ID 使用更短的变长码。 |
| 高基数近唯一数据 | 哈希值、UUID，(k \approx n) | 通用压缩（如 ZSTD）在块级别应用 | 字典编码收益低。关注块大小（如 128KB-1MB）以平衡压缩率与随机访问粒度。 |
| 单调 / 近单调数值 | 时间戳、自增主键 | 增量编码 + 位打包 或 帧间参考 | 计算块内最大值与最小值的差 (R)，所需比特数 (b = \lceil \log_2 R \rceil)。增量编码下，计算差值序列的熵。 |
| 文本数据 | 日志、描述字段 | 块级字典（如 FSST） + 通用压缩 | FSST 等算法为常见子串构建静态字典，在高基数字符串上能提供接近 LZ4 的压缩比与更快的解压速度。 |
实施要点：
- 数据排序：按常用过滤列排序是提升压缩效率最有效的单一手段，它能极大增加 RLE 的有效性并优化区域地图跳过。
- 批量加载：始终以大批量（数十万行以上）写入数据，以便形成优化、压缩良好的列存段。
- 监控与适配：建立监控，追踪不同编码方案的实际压缩率、查询延迟和 CPU 利用率。对于动态变化的数据分布，可考虑采用两级机器学习模型进行在线编码方案选择。
六、风险与局限
尽管数学模型提供了清晰的优化方向，但工程实践必须警惕以下陷阱：
- CPU 开销不可忽视：在高速 OLTP 场景或低延迟查询要求下，复杂的解码流程可能成为新的瓶颈。压缩的收益必须用查询延迟的潜在增加来兑换。
- 预测性压缩的隐藏成本：基于机器学习的预测性压缩虽然能逼近条件熵，但引入了模型训练、存储和推理开销。其净收益需仔细评估，可能仅在数据规模极大、模式稳定时为正。
- 写放大与更新代价：列存压缩块通常不可变，更新需要重写整个块，带来写放大。需要设计合理的增量存储（Delta Store）和合并（Merge）策略来缓解。
结语
数据库压缩远非选择一种压缩算法那么简单。它是一场基于信息论、以香农熵为终极标尺，在存储成本、I/O 带宽和 CPU 周期之间进行的精密权衡。通过建立数学模型，我们将工程决策从 “经验直觉” 提升到 “量化分析” 的层面。列存布局通过降低局部熵，为简单高效的编码创造了舞台。而最终的落地，则需要我们将熵的理论值，转化为针对具体数据特征的编码选择清单与可调参数。记住，最优的压缩策略永远是相对于特定工作负载和成本模型而言的。理解其背后的数学，方能驾驭其工程的复杂。
资料来源：
- CMU 15-445/645 数据库系统课程笔记《存储模型与压缩》。
- MotherDuck《数据工程师的列式存储指南》中关于压缩技术与工程权衡的论述。