在列式存储里,"枚举型"数据几乎无处不在:城市、性别、状态码、设备型号、错误类别……这类列的共同特征是取值集合很小、重复度极高。把每一行都原样存成 UTF-8 字符串,是对空间的巨大浪费。字典编码(Dictionary Encoding)把每个不同的值收进一张"字典表",列里只存每个值对应的一个较小的整数 ID——4 字节的状态码可以压到 1~2 字节,20 字节的城市名可以压到 1 字节。更妙的是,若让字典保序,范围查询、排序、分组乃至连接都能直接在整数 ID 上完成,把字符串比较变成整数比较。本文从最朴素的字符串列浪费讲起,逐层剖析字典的构建与保序性、位打包、与 RLE 的叠加、高基数退化处理、并发与共享,最后给出一份本地实跑验证过的 Python 教学实现。
一、为什么列式存储偏爱字典编码
先算一笔账。假设有一张 1 亿行的日志表,其中 city 列只会出现 200 个城市名,平均每个名字 12 字节。行存里这列要占 1e8 × 12 ≈ 1.2 GB;列存虽然把这一列单独连续存放、压缩更友好,但原始字节量仍是 1.2 GB。而字典编码后,列里只需存一个不超过 200 的 ID,用 1 字节就够(28=256 > 200),总共 100 MB,再加一张 200 × 12 ≈ 2.4 KB 的字典表——压缩比约 12 倍。
字典编码能吃香,本质 depends on 三个条件,缺一不可:
- 低基数(low cardinality):不同值的个数
D远小于行数N。ID 宽度是ceil(log2 D)位,D 越小省得越多。 - 值远大于 ID:单个值的字节数越大(长字符串),换成整数 ID 的收益越明显;对 8 字节整数列编码反而可能得不偿失。
- 重复访问同一批值:过滤、分组、排序反复用到这些值,字典只解一次码、之后都在 ID 上运算,复用收益高。
反过来,若一列几乎每行都是唯一值(如用户 ID、时间戳、UUID),字典会退化成"一个值一个 ID"的映射表,既不省空间,还多了一次查表开销——这正是 DuckDB、ClickHouse、Parquet 都要做"基数自适应"的原因,后文详述。
二、字典编码的本质:值域到稠密整数的双射
形式化地,字典编码就是在一个列 C = [c0, c1, …, cN-1] 的不同值集合 V = {v0, …, vD-1} 与整数区间 [0, D) 之间建立双射 encode: v → id 与 decode: id → v,然后列里存 [encode(c0), encode(c1), …]。实现就是两张表:
- 字典表 values:按下标可寻址,
values[id]给出原值,用于解码与结果还原。 - 反向索引 index:哈希表
value → id,用于编码时 O(1) 查到每个值的 ID。
关键在于是否保序(order-preserving)。若字典表按值的自然/字典序排列,则 v_i < v_j ⇔ i < j,ID 之间的大小关系与原值完全一致;若按首次出现顺序插入,则 ID 只是任意标签,无法比较大小。这个区别决定了范围查询能否下推,是"能用的字典"与"高效的字典"的分水岭。
三、核心操作一:建典与编码解码
建典就是收集不同值并分配 ID。保序版对去重结果排序,非保序版按插入顺序编号。下面这段是教学实现,本地已实跑验证:
class DictionaryEncoder:
"""保序字典编码:值按字典序排列,ID 保序,支持范围查询下推。"""
def __init__(self, ordered=True):
self.ordered = ordered
self.values = [] # id -> value
self.index = {} # value -> id
def build(self, column):
# 保序:对去重结果排序;非保序:按首次出现顺序
uniq = sorted(set(column)) if self.ordered else list(dict.fromkeys(column))
self.values = uniq
self.index = {v: i for i, v in enumerate(uniq)}
return self
def encode(self, column):
return [self.index[v] for v in column]
def decode(self, ids):
return [self.values[i] for i in ids]
# 实测:col = ["北京","上海","广州","北京","深圳","上海","北京"] * 3
# 基数 4, 保序字典值序 = ['上海','北京','广州','深圳'](按 Unicode 码点)
# 编码后每个值用 2 bit 的 ID 表示,解码往返完全一致注意这里的排序用的是 Python/Unicode 码点序("上海" U+4E0A < "北京" U+5317 < "广州" U+5E7F < "深圳" U+6DF1)。真实系统要对齐数据库排序规则(collation):大小写敏感、重音、中文拼音/笔画序等都会改变 ID 的顺序。若字典序与查询所用 collation 不一致,保序下推就会出错——这是工程上最隐蔽的坑之一。
四、核心操作二:保序性与范围查询下推
保序字典的价值在范围查询。要在字符串列上查 city >= '广州' AND city <= '深圳',朴素做法要逐行做 1 亿次字符串比较;有了保序字典,只需两步:
- 第一步在字典上二分:用
lower_bound/upper_bound把值区间 [广州,深圳] 折成 ID 区间 [2, 4),字典只有 D 个元素,二分 O(log D)。 - 第二步在 ID 数组上过滤:把每行 ID 与区间比大小,纯整数比较,还能配合 SIMD 与Zone Map 跳过整块。
def lower_bound(self, value):
"""第一个 >= value 的 id"""
lo, hi = 0, len(self.values)
while lo < hi:
mid = (lo + hi) // 2
if self.values[mid] < value:
lo = mid + 1
else:
hi = mid
return lo
def upper_bound(self, value):
"""第一个 > value 的 id"""
lo, hi = 0, len(self.values)
while lo < hi:
mid = (lo + hi) // 2
if self.values[mid] <= value:
lo = mid + 1
else:
hi = mid
return lo
def range_ids(self, lo_val, hi_val):
return range(self.lower_bound(lo_val), self.upper_bound(hi_val))
# 实测:lower_bound('广州') = 2;等值命中 3 行;
# 区间['北京','广州'] 命中 12 行,值序 = ['上海','北京','广州','深圳']对于高选择性的等值过滤(city = '广州'),一些引擎还会维护"每个 ID 对应的行号列表"(类似倒排/位图),直接定位行,连 ID 数组都不用扫。Parquet 的 dictionary page + 位图、ClickHouse 的 LowCardinality 类型,本质都是这套思路的不同工程取舍。
五、核心操作三:位打包(Bit-packing)压到理论下界
拿到 ID 后,若仍用 4 字节 int 存一个最大只到 199 的 ID,等于每个 ID 浪费 24 个比特。位打包按实际需要的位宽 w = ceil(log2(D-1)) = (D-1).bit_length(),把多个 ID 紧密拼进字节流:ID 1(2 bit)+ ID 3(2 bit)拼成一个字节 0b00001101。这样每个 ID 只占 w 位,逼近信息论下界 N · log2 D。
def bits_needed(max_id):
return max(1, max_id.bit_length())
def bit_pack(ids, width):
"""把整数数组按固定位宽打包成字节流(MSB first)"""
out = bytearray(); buf = 0; nbits = 0
for v in ids:
buf = (buf << width) | v
nbits += width
while nbits >= 8:
nbits -= 8
out.append((buf >> nbits) & 0xFF)
if nbits:
out.append((buf << (8 - nbits)) & 0xFF)
return bytes(out)
def bit_unpack(data, count, width):
ids = []; buf = 0; nbits = 0; pos = 0
mask = (1 << width) - 1
while len(ids) < count:
while nbits < width:
buf = (buf << 8) | data[pos]; pos += 1; nbits += 8
nbits -= width
ids.append((buf >> nbits) & mask)
return ids
# 实测:21 个 ID × 2 bit = 6 字节;原生 4 字节整数要 84 字节 —— 压缩 14 倍工程实现要考虑字节序、SIMD 并行解包(一次解 8/16 个 ID)与边界尾部处理。Arrow、Parquet、ORC 的 RLE/bit-packed hybrid 编码都基于这个原理,只是做了块对齐与批量解码优化。
六、与 RLE 叠加:先排序再游程
当列被按某个键排序后,同一值的行会连续出现,字典 ID 也成串重复。此时在 ID 数组上做游程编码(RLE),把连续的相同 ID 压成 (值, 重复次数) 二元组,压缩率会比单纯位打包更高。实测中 21 个排序后的 ID 压成 4 个游程:
def rle_encode(ids):
runs = []; i = 0
while i < len(ids):
val = ids[i]; j = i + 1
while j < len(ids) and ids[j] == val:
j += 1
runs.append((val, j - i))
i = j
return runs
def rle_decode(runs):
out = []
for val, length in runs:
out.extend([val] * length)
return out
# 实测:21 个排序 ID -> 4 个游程,84 字节 -> 32 字节
# 位打包 + RLE 的混合编码正是 Parquet/ORC 的默认选择排序是 RLE 生效的前提。所以列存常常让数据按"低基数列优先"排序,人为制造长游程;ClickHouse 的 LowCardinality 也类似地在内存里用 ID 字典、在排序后靠 RLE 收缩磁盘体积。位打包擅长"ID 分散",RLE 擅长"ID 连续",两者互补,混合编码取各自所长。
七、高基数退化:字典不是万能药
字典编码的死穴是高基数。当 D 接近 N(如主键、时间戳、浮点数),ID 宽度逼近甚至超过原值宽度,字典表本身膨胀成 N 条,反而更慢更占空间。工程上有三种应对:
| 策略 | 做法 | 适用场景 | 代价 |
|---|---|---|---|
| 基数阈值回退 | 建典时统计 D/N,超过阈值(如 0.8)就放弃字典、改用 plain 编码 | 通用兜底,Parquet/DuckDB 常用 | 需预扫描或采样估算基数 |
| 字典淘汰 / 溢出 | 字典满后新值写入溢出区(plain 段),ID 高位标记"溢出" | 数据倾斜、基数渐增 | 解码路径分叉,实现复杂 |
| 换专用编码 | 时间戳用 Delta+Gorilla,浮点用 XOR,长字符串用 FSST/ZSTD | 已知数据分布 | 编码种类多,选择成本高 |
这里的"换专用编码"里,Gorilla 压缩常与字典编码并列出现:Facebook 的 Gorilla 时序库对时间戳用"差值的差值(delta-of-delta)+ 可变长编码",对浮点值用"相邻 XOR + 前导/尾随零计数",把规律的时间序列压到接近零边际成本。它不是字典编码,但解决的是同一类问题——利用数据分布的重复性与规律性,用更少的位表达同样的信息。理解了字典编码的"值域映射 + 位打包"思想,再看 Gorilla、FSST、Frame-of-Reference 这些编码便一脉相承。
八、工程进阶:并发、共享与字典传递
把字典编码用到生产系统,还要处理几个工程问题:
- 并发建典:多线程同时编码时,反向索引
value → id要加锁或用无锁并发哈希;可以采用"线程本地字典 + 定期合并"降低竞争,代价是合并后要重写 ID。 - 字典共享:一个查询里多列可能共享同一张字典(如国家/城市),共享可省内存并让跨列比较直接做;DuckDB 的 dictionary vector 允许多个 Vector 引用同一个 dictionary 而不复制。
- 字典传递(dictionary passing):在向量化执行里,过滤/投影算子尽量保持Dictionary 表示不解码,让后续算子继续在 ID 上运算,直到最终输出才 decode——这是"全链路字典"的性能关键。
- 字典顺序与 collation 对齐:如前所述,保序下推要求字典序与查询排序规则一致,否则结果错误。多语言/多 collation 场景尤其要小心。
九、在真实系统里的位置
字典编码是现代分析引擎的公共底座,几乎无处不在:
| 系统 | 字典编码的角色 | 特色 |
|---|---|---|
| Parquet / ORC | 每个 row group 可带 dictionary page,存值时先尝试字典编码 | 基数过高自动回退 plain;写时采样估算 |
| ClickHouse | LowCardinality(T) 用 ID 字典表示,计算多在 ID 上进行 | 字典与 RLE、SIMD 结合,列式查询极快 |
| DuckDB | 向量执行引擎原生支持 dictionary vector | 算子间保持字典表示,减少解码 |
| Apache Arrow | DictionaryArray = indices + dictionary | 跨语言零拷贝共享,支持 chunk 间字典统一 |
| Apache Doris / StarRocks | 低基数列字典编码 + 倒排/位图索引 | 与 Bitmap 索引联动,加速等值/IN 查询 |
可以看到,越现代的引擎越强调"字典表示在全链路里保持不解码"——字典编码早已不只是一种压缩手段,而是贯穿存储、执行、索引的一套数据表示范式。
十、教学实现完整代码与实测结果
把前面的片段拼起来,就是一份可运行的字典编码器。以下是本地实跑(Python 3.13)通过的版本与输出:
col = ["北京","上海","广州","北京","深圳","上海","北京"] * 3
enc = DictionaryEncoder(ordered=True).build(col)
ids = enc.encode(col)
w = bits_needed(max(ids)) # = 2
assert enc.decode(ids) == col # ① 解码往返
assert bit_unpack(bit_pack(ids, w), len(ids), w) == ids # ② 位打包往返
assert enc.lower_bound("广州") == 2 # ③ 保序下推
assert rle_decode(rle_encode(sorted(ids))) == sorted(ids) # ④ RLE 往返
# 输出:
# [1] 字典编码往返 OK: 基数=4 位宽=2bit
# [2] 位打包往返 OK: 21 个 ID x 2bit = 6 字节 (原生 84 字节, 压缩 14.0x)
# [3] 保序下推 OK: 等值命中 3 行, 区间['北京','广州']命中 12 行
# [4] RLE 往返 OK: 21 个 ID -> 4 个游程 (84 字节 -> 32 字节)
# [5] 非保序字典往返 OK: 值序按插入顺序, 不支持范围下推
# ALL TESTS PASSED这段代码刻意保持了最小可理解的形态:没有 SIMD、没有溢出区、没有并发。但它完整覆盖了字典编码的三个核心操作(建典/编码/解码)、两个关键优化(位打包/RLE)与一个决定性的性质(保序下推)。读懂它,再去读 Parquet 的 RleBpkDictionaryEncoder 或 DuckDB 的 dictionary vector 源码,会发现问题域是熟悉的。
十一、结语:从"省空间"到"改范式"
字典编码表面上是一种压缩技巧——把长字符串换成短整数,省下 10 倍空间。但它的真正威力在于把问题域换了:一旦列变成稠密整数 ID,比较、排序、分组、连接这些算子都从昂贵的字符串操作降级为廉价的整数操作,还能叠加位打包、RLE、位图、SIMD 等一整套工具链。保序性让范围查询能下推到字典层面,全链路不解码让性能收益贯穿执行引擎。理解字典编码,就理解了现代列式存储"以空间换时间、再以编码消空间"的设计哲学——而这,正是从"能用"到"高效"的分水岭。

发表评论 取消回复