数据库中的压缩和编码技术

发表于 |

主要包含了数据库中的压缩和编码技术。

分离自《磁盘上的数据结构》。

常见的编码(encoding)方法

Dictionary Encoding

布隆过滤器(Bloomfilter)

功能性上，字典是布隆过滤器的超集，但 Bloomfilter 有如下优势：

  • 高基数场景下，字典本身会占用很多内存，因此只能 fallback 到普通存储，但是 Bloomfilter 仍然可以运行
  • 布隆过滤器是定长且紧凑，因此天生适合 OSS 场景

总的来说，对于低基数，确实可以只使用字典。但是对于中高技术，Bloomfilter 的优势会越来越明显。

关于全局字典

优势：

  1. 对 Late Materialization 友好
    因为全表或全文件的 ID 是完全一致的。在进行 GROUP BY、DISTINCT 或 JOIN 时，计算引擎完全不需要看原始字符串，直接对底层的整数 ID 进行哈希、比较和聚合。只有在最终向用户展示结果的那一刻，才查一次全局字典。
    而如果使用局部字典，则可能需要提前物化。或者引入一个字典对齐（Dictionary Unification）的转换步骤。
  2. 极致的全局压缩率
    消除了一切跨块的字典数据冗余。对于低基数但全局分布均匀的字段（如枚举值、性别、状态码），全局字典体积最小。
  3. 支持更快的谓词下推（Predicate Pushdown）
    查询 WHERE 城市 = '北京' 时，只需要在全局字典中查到 "北京" -> ID 5。然后所有数据块的过滤条件直接变成 WHERE ID = 5，匹配极快。

劣势：

  1. 构建成本极高（Two-Pass 限制）
    在写入数据前，必须先扫描全量数据以生成完整的全局字典。
  2. 字典体积爆炸风险（Global Dictionary Bloat）
    如果列的基数随着时间推移不断变大（例如：用户 ID、设备 UUID），全局字典会变得无比巨大。
  3. 破坏数据局部性优势
    如果某些值只在特定的时间段出现，全局字典依然要把它们塞进那张大表里，导致原本可以只用 1 字节（Local ID）表示的数据，被迫用 2 字节或 4 字节（Global ID）表示。
  4. 没法做 pruning
    因为如果每个 Page 有自己的字典，那么直接读取这个字典就能知道某个值是否存在了。

Run-Length Encoding, RLE

重复出现的数字用重复次数代替。

1
2
3
AAAAABB
==>
A5B2

Variable-length Encoding

优势：

  • 对非均匀分布极其友好：如果 Delta 结果中存在大量极小值（如 0, 1, -1），同时混有少量极大值（异常跳跃），变长编码能对小值实现极致压缩（只占 1 字节），且完美兼容大值。
  • 无需前瞻元数据：每个数字的长度信息都嵌入在其自身的字节中，属于流式编码，不需要提前计算整块数据的最大值，适合流式处理。

劣势：

  • CPU 分支预测失败率高：解码时必须逐个字节解析标志位，导致大量的 if-else 分支判断。在现代 CPU 上，这会引发严重的分支预测失败，导致流水线停顿。
  • 无法利用 SIMD 加速：由于每个数字的字节长度不固定，数据之间存在位置依赖。

Prefix Encoding / Huffman Encoding

Bitpacking

在现代时序数据库（如 InfluxDB、ClickHouse）和大数据列存（如 Parquet、ORC）中，Delta 编码后的首选通常是 Bit-packing。
为了解决 Bit-packing 害怕离群值的缺点，通常会搭配 FOR（Frame of Reference） 或 Patched Item 机制：将异常放大的差值单独剥离到另一个数组存储，而主体继续保持极低位宽的 Bit-packing。

以数据块（Block，如 32 或 64 个数字）为单位，找出该块内最大绝对值所需的固定位数 b（Bit-width），然后所有数字统一用 b 个 bit 紧凑存储。

优势：

  • 吞吐量吞吐量极高（CPU 极其友好）
    • 读性能是 O(1) 的
      解码时没有任何条件分支，只有固定的位移（Shift）和位与（And）操作。
      只要知道 index，就能推出 offset。
    • 所有数字在块内对齐且长度完全一致，完美支持 SIMD
  • 向量化：可以利用 SIMD 指令（如 AVX-512）一次性并行解码 16 或 32 个数字，解码速度通常比变长编码快一个数量级。

劣势：

  • 极易受到“离群值/异常值”的惩罚（Outlier Vulnerability）
    解决该痛点通常需引入 FOR/FastPFOR 框架
  • 块级延迟与元数据开销
    必须攒满一个 Block 才能计算最大位宽并写入，且每个块需要额外存储位宽 b 的元数据。

Bitmap Encoding

为列中的每一个唯一值（Category）都单独创建一个由 0 和 1 组成的位数组（Bitmap）。位数组的长度等于数据的总行数。如果第 i 行等于该值，则第 j 个 bit 置为 1，否则置为 0。

优势：

  1. 在布尔类型等 low cardinality 数据列中效率好。
  2. 对位操作很友好，因此适合处理很多 AND OR 的这种复杂条件。特别地，还能用上 SIMD 来加速。
  3. 对于等值查询比较友好。

劣势：

  1. 对基数很敏感，如果基数高，特别是还有很大的数字，那么开销就很大

对比字典，字典的优势在：

  1. 对聚合操作如 GROUP BY 等更友好。
  2. 对高基数的情况，效果没有 Bitmap 那么差。

Delta Encoding

计算连续值之间的差值。

1
2
3
9999 10000 9998
==>
9999 +1 -2

ZigZag Encoding

主要解决负数的补码前导零太多影响压缩的问题。

把负数最前面的符号位，移动到尾部。

常见的压缩算法

LZ4

LZMA(Lempel-Ziv-Markov Chain Algorithm)

Zstd

Snappy

Zlib

GZip