列式压缩：RLE / Dictionary / FSST

列式存储的压缩率优势，本质上是数据局部性的胜利。当同一列的值被物理连续存放， 它们天然就具备高重复度、小值域、强有序性——而这恰恰是各类编码算法最喜欢的输入。

一、行存与列存：为什么列更好压

1.1 行存的内存布局

在行存（row-oriented）系统中，一行数据的所有字段被连续存放：

Row 0: | id(int32) | name(varchar) | city(varchar) | age(int32) |
Row 1: | id(int32) | name(varchar) | city(varchar) | age(int32) |

同一行的所有字段在物理地址上连续，适合 OLTP 场景中的整行读写。但从压缩角度看， 相邻字节属于不同类型、不同值域的字段，数据熵极高，通用压缩器压缩率有限。

1.2 列存的内存布局

列存（column-oriented）系统将同一列的所有值连续存放：

id column:   | 1 | 2 | 3 | 4 | 5 | 6 | ... |
name column: | Alice | Bob | Carol | Dave | Eve | Frank | ... |
city column: | Beijing | Beijing | Shanghai | Beijing | Shanghai | Beijing | ... |
age column:  | 28 | 35 | 28 | 42 | 31 | 28 | ... |

这种布局带来三大压缩友好特性：

类型均一性（Type Homogeneity）：同一列的值类型完全一致，编码器可以针对 int32、float64、varchar 分别选用最优编码方案。

值域集中（Value Locality）：以 city 列为例，全表可能只有几十个不同的城市 名。低基数（low cardinality）字段在列存中天然适合字典编码。

有序性（Sortedness）：如果表按某列排序，那么该列在磁盘上就是有序的。有序数据 可以直接用 RLE 或 Delta 编码，压缩率极高。

1.3 压缩率的量化对比

以 TPC-H lineitem 表（SF=10，约 6000 万行）为例：

关键观察：即便 Parquet 使用轻量级的 Snappy 压缩，也比 CSV+zstd 好得多。这说明 编码层（encoding）贡献了大部分压缩率，通用压缩器只是锦上添花。

1.4 编码 vs 压缩：两层流水线

列式存储的压缩通常分为两层：

原始列数据
    |
    v
[编码层] -- Dictionary / RLE / Delta / FSST / Bit-Packing
    |
    v
编码后的紧凑字节流
    |
    v
[压缩层] -- Zstd / Snappy / LZ4 / Gzip / 无压缩
    |
    v
最终存储的字节

编码层是语义感知的：它知道数据类型、值域分布、排序状态。压缩层是通用的： 它只看到字节流。两层的组合效果往往是乘法关系——字典编码将 city 列从平均 8 字节/值缩减为 1 bit/值（64 倍），再经 Zstd 可能再缩 1.5-2 倍，总压缩比可达 100 倍以上。

二、RLE：游程长度编码

2.1 基本原理

RLE（Run-Length Encoding）是最朴素的编码之一：将连续相同的值替换为 (值, 重复次数) 对。

输入: A A A A B B C C C C C A A
输出: (A,4) (B,2) (C,5) (A,2)

对于列式存储来说，RLE 在以下场景中效果极好：

• 表按该列排序（或近似排序），大量连续重复值。
• 布尔列、状态列等低基数字段。
• 时间戳列如果精度较低（如按天），排序后也会有大量重复。

2.2 编码格式设计

一个实际可用的 RLE 编码器需要考虑：

// RLE 编码单元
struct rle_run {
    uint32_t value;       // 值（或字典索引）
    uint32_t run_length;  // 重复次数
};

但直接存 (value, run_length) 对长度为 1 的 run 反而膨胀。因此实际系统中通常 采用混合方案：

• 当 run_length >= 阈值（如 8）时，使用 RLE 编码。
• 当 run_length < 阈值时，直接存储原始值（literal run）。

Parquet 的 RLE/Bit-Packing Hybrid Encoding 就是这样的设计：

每个"group"的头部有一个 varint：
  - 若最低位为 0：表示 RLE run
    header = (run_length << 1) | 0
    后接一个 bit-packed 的值
  - 若最低位为 1：表示 literal run
    header = (num_groups << 1) | 1
    后接 num_groups * 8 个 bit-packed 的值

2.3 RLE 的适用性分析

场景               | 压缩效果 | 说明
-------------------|----------|----------------------------------
排序后的低基数列    | 极好     | run_length 极长，接近最优
排序后的高基数列    | 好       | 有一定的连续重复
未排序的低基数列    | 一般     | 短 run 较多，overhead 抵消收益
未排序的高基数列    | 差       | 几乎无连续重复，反而膨胀
随机数据            | 极差     | 每个值都是长度 1 的 run

核心教训：RLE 对数据的排序状态极度敏感。在实际系统中，RLE 几乎总是用在 字典编码之后——即对字典索引序列做 RLE，而非对原始值做 RLE。

2.4 RLE 在排序键上的威力

假设一张用户行为日志表有 10 亿行，按 event_type 列排序，该列有 20 种事件类型， 均匀分布。那么：

• 每种类型平均有 5000 万行连续相同值。
• 使用 RLE 编码后，整个 event_type 列只需存储 20 个 (value, count) 对。
• 即使加上字典，总大小也不过几百字节——原始 10 亿个值被压缩了近 10 亿倍。

这也是为什么 ClickHouse 极度强调排序键（ORDER BY）的选择——它直接决定了主键列 的 RLE 压缩效率。

三、字典编码：低基数列的杀手锏

3.1 基本原理

字典编码（Dictionary Encoding）的思路非常直观：

1. 扫描列中所有不同的值，构建一个字典（去重后的值列表）。
2. 将原始值替换为字典中的整数索引。

原始值:  Beijing  Beijing  Shanghai  Beijing  Shenzhen  Shanghai
字典:    0=Beijing  1=Shanghai  2=Shenzhen
编码后:  0  0  1  0  2  1

字典编码的压缩效果取决于：

• 基数（cardinality）：不同值的数量越少，索引位宽越小。
• 原始值大小：原始值越大（如长字符串），压缩收益越高。

3.2 位宽选择与 Bit-Packing

字典索引的位宽应该根据字典大小选择最小值：

字典大小    | 索引位宽 | 每个值存储
------------|----------|----------
2           | 1 bit    | 0.125 字节
4           | 2 bits   | 0.25 字节
16          | 4 bits   | 0.5 字节
256         | 8 bits   | 1 字节
65536       | 16 bits  | 2 字节

Bit-Packing 是将这些窄位宽的索引紧密排列的过程：

// 将 8 个 3-bit 值打包到 3 个字节中
// values: [5, 3, 7, 1, 6, 2, 4, 0]
// 二进制: 101 011 111 001 110 010 100 000
// 字节:   [10101111] [10011100] [10000xxx]
void bitpack_3bit(const uint8_t *values, uint8_t *output, int count) {
    int bit_pos = 0;
    for (int i = 0; i < count; i++) {
        int byte_idx = bit_pos / 8;
        int bit_offset = bit_pos % 8;
        output[byte_idx] |= (values[i] & 0x07) << bit_offset;
        if (bit_offset > 5) {
            output[byte_idx + 1] |= (values[i] & 0x07) >> (8 - bit_offset);
        }
        bit_pos += 3;
    }
}

3.3 字典编码的局限

字典编码并非万能的。当基数很高时（如 UUID、用户 ID），字典本身可能比原始数据还大。 Parquet 默认字典页大小限制为 1 MB，超出则回退到 PLAIN 编码。各系统的策略：

Parquet: 字典页大小限制，超出则回退
ClickHouse: 自适应选择编码方案
DuckDB: 字典编码 + FSST 组合
ORC: 字典大小超过列总大小 N% 时回退

3.4 字典编码 + RLE 的黄金组合

在实际系统中，字典编码和 RLE 往往是组合使用的：

原始列（排序后）:
  Beijing Beijing Beijing Shanghai Shanghai Shenzhen Shenzhen Shenzhen

Step 1 - 字典编码:
  字典: {0: Beijing, 1: Shanghai, 2: Shenzhen}
  索引: 0 0 0 1 1 2 2 2

Step 2 - RLE 编码索引:
  (0, 3) (1, 2) (2, 3)

最终: 3 个 (index, count) 对 + 3 个字典条目
原始: 8 个变长字符串，总约 64 字节
编码后: 约 30 字节（字典） + 12 字节（RLE） = 42 字节

如果列未排序，则 RLE 效果差，此时字典索引直接用 Bit-Packing 存储：

原始列（未排序）:
  Beijing Shanghai Beijing Shenzhen Beijing Shanghai

Step 1 - 字典编码:
  字典: {0: Beijing, 1: Shanghai, 2: Shenzhen}
  索引: 0 1 0 2 0 1

Step 2 - Bit-Packing（2 bits per value）:
  6 个值 * 2 bits = 12 bits = 1.5 字节

最终: 约 30 字节（字典） + 2 字节（packed indices） = 32 字节
原始: 约 48 字节

四、FSST：短字符串的快速压缩

4.1 背景与动机

FSST（Fast Static Symbol Table）来自 2020 年 Peter Boncz 团队的 VLDB 论文， 已被 DuckDB 采用。传统字典编码对高基数字符串列（如 URL、地址）效果差，但这些 字符串往往有大量共同子串——比如 “http://www.”、“.com”、“/index”。 FSST 的核心思想：不做整串字典，而是做子串字典（Symbol Table）。

4.2 符号表构建

FSST 的符号表有以下约束：

• 最多 255 个符号（symbol），每个符号最长 8 字节。
• 符号编码为 1 字节的 escape code（0x00-0xFE），0xFF 保留作转义。
• 不在符号表中的字节直接输出（前缀 0xFF 表示 literal byte）。

构建算法（贪心迭代）：

1. 初始化空符号表
2. 重复以下过程，直到收敛或达到 255 个符号：
   a. 用当前符号表对样本数据进行"试编码"
   b. 统计所有可能的 1-8 字节子串的"压缩收益"
      收益 = (子串长度 - 1) * 出现次数
   c. 选择收益最高的子串加入符号表
   d. 如果没有正收益的候选，停止
3. 输出最终符号表

4.3 编码与解码

编码过程是简单的贪心最长匹配：

输入: "http://www.github.com/duck"
符号表:
  s0 = "http://"  -> 0x00
  s1 = "www."     -> 0x01
  s2 = ".com"     -> 0x02
  s3 = "hub"      -> 0x03
  s4 = "git"      -> 0x04
  s5 = "/duck"    -> 0x05

编码: 0x00 0x01 0x04 0x03 0x02 0x05
输出: 6 字节（原始 26 字节，压缩比 4.3x）

解码则是简单的查表替换，非常快：

// FSST 解码核心循环（伪代码）
void fsst_decode(const uint8_t *in, size_t in_len,
                 const char *symbols[256], const uint8_t sym_lens[256],
                 char *out, size_t *out_len) {
    size_t o = 0;
    for (size_t i = 0; i < in_len; i++) {
        if (in[i] == 0xFF) {
            // literal byte
            out[o++] = in[++i];
        } else {
            uint8_t sym = in[i];
            memcpy(out + o, symbols[sym], sym_lens[sym]);
            o += sym_lens[sym];
        }
    }
    *out_len = o;
}

4.4 FSST 的性能特征

FSST 的杀手级优势在于随机访问：编码后的每个字符串可以独立解码，不需要 像 LZ4/Zstd 那样解压整个块。这对列式存储中的谓词下推（predicate pushdown） 非常重要——筛选时只需解码被选中的行。

4.5 DuckDB 中的 FSST 实践

DuckDB 在其存储格式中将 FSST 作为字符串列的默认编码方案之一：

DuckDB 字符串列编码选择逻辑（简化）:

if cardinality < threshold:
    use Dictionary Encoding
elif fsst_compression_ratio > 1.2:
    use FSST
else:
    use Uncompressed + general compression (Zstd/LZ4)

在实际测试中，FSST 对 URL、文件路径、日志消息等列的压缩率通常在 2-4 倍， 而编码/解码速度远快于通用压缩器。

五、Delta 与 Frame-of-Reference：数值列的利器

5.1 Delta Encoding

对于单调递增或近似递增的数值列（如时间戳、自增 ID），Delta Encoding 将原始值 转换为相邻值的差值：

原始值:   1000  1002  1005  1007  1010  1012  1018  1020
Delta:    1000  2     3     2     3     2     6     2

第一个值存储原始值（base value），后续值存储差值。差值通常远小于原始值，因此 可以用更少的 bit 来存储。

5.2 Frame-of-Reference (FOR)

FOR 是 Delta 的一个变体：选择一个”参考帧”（通常是块内最小值），然后存储每个值 与参考帧的偏移量。

原始值:     10045  10052  10048  10061  10050  10047  10055  10059
最小值:     10045
偏移量:     0      7      3      16     5      2      10     14
最大偏移:   16 -> 需要 5 bits

存储: base=10045, bit_width=5, packed_offsets=[0,7,3,16,5,2,10,14]
原始: 8 * 32 bits = 256 bits
编码: 32 bits (base) + 3 bits (width) + 8 * 5 bits = 75 bits
压缩比: 3.4x

5.3 Delta + FOR 的组合

在实际系统中，Delta 和 FOR 经常组合使用：先按块（如 128 个值）分组，每块内 做 FOR，然后用 Bit-Packing 存储偏移量。第一个值或块的 base 值单独存储。

5.4 DELTA_BINARY_PACKED（Parquet 实现）

Parquet 对整数列使用 DELTA_BINARY_PACKED 编码：

Block = 128 values（可配置）
Mini-block = 32 values

每个 block:
  - min_delta: 块内最小差值（zigzag varint 编码）
  - bit_widths: 每个 mini-block 的位宽（1 字节/mini-block）
  - mini-block data: bit-packed 的 (delta - min_delta) 值

整体结构:
  [block_size] [num_mini_blocks] [total_values] [first_value]
  [block_0_header] [block_0_data]
  [block_1_header] [block_1_data]
  ...

这种分层结构允许每个 mini-block 使用不同的位宽，适应局部数据分布的变化。

5.5 ZigZag 编码：处理有符号差值

当差值可能为负数时（如非单调序列），需要 ZigZag 编码将有符号整数映射到无符号整数：

// ZigZag 编码
static inline uint32_t zigzag_encode(int32_t n) {
    return (uint32_t)((n << 1) ^ (n >> 31));
}

// ZigZag 解码
static inline int32_t zigzag_decode(uint32_t n) {
    return (int32_t)((n >> 1) ^ -(n & 1));
}

// 映射关系:
//  0 -> 0
// -1 -> 1
//  1 -> 2
// -2 -> 3
//  2 -> 4
// ...

ZigZag 编码保证绝对值小的数映射到小的无符号数，从而让后续的 varint 或 bit-packing 编码更高效。

六、Parquet 编码：定义层级与重复层级

6.1 嵌套数据的挑战

Parquet 支持嵌套数据结构（如 JSON、Protobuf 中的 repeated/optional 字段）。 要将嵌套结构平铺到列存中，需要额外的元数据来描述层级关系。

以下面的 schema 为例：

message Document {
  required int64 doc_id;
  optional group links {
    repeated int64 forward;
    repeated int64 backward;
  }
  repeated group name {
    repeated group language {
      required string code;
      optional string country;
    }
    optional string url;
  }
}

6.2 Definition Level（定义层级）

Definition Level 记录一个字段在哪个嵌套层级上有定义（非 NULL）。

对于 links.forward 字段:
  - 如果 links 为 NULL:         def_level = 0
  - 如果 links 存在但 forward 为空: def_level = 1
  - 如果 forward 有值:           def_level = 2

示例数据:
  doc_id=1, links={forward=[20,40,60]}
  doc_id=2, links=NULL
  doc_id=3, links={forward=[80]}

forward 列存储:
  values:     20   40   60   NULL  80
  def_levels:  2    2    2    0     2

6.3 Repetition Level（重复层级）

Repetition Level 记录当前值在哪个嵌套层级上是新的重复元素。

rep_level = 0: 新的顶层记录
rep_level = 1: 同一记录内的新 repeated group
rep_level = 2: 同一 group 内的新 repeated 值

forward 列存储:
  values:     20   40   60   NULL  80
  def_levels:  2    2    2    0     2
  rep_levels:  0    2    2    0     0
              ^新记录     ^新记录  ^新记录
                   ^同组重复
                        ^同组重复

6.4 Definition/Repetition Level 的编码

这两个 level 序列本身也需要编码。由于它们的值域很小（通常 0-7），Parquet 使用 前面提到的 RLE/Bit-Packing Hybrid 编码：

def_levels = [2, 2, 2, 0, 2, 2, 2, 2, 0, 2]

字典大小 = 3 (0, 1, 2)，需要 2 bits

如果有长 run:
  RLE: (2, 3) (0, 1) (2, 4) (0, 1) (2, 1)
如果 run 很短:
  Bit-packed: 每 8 个值 pack 到 2 字节

在实际数据中，def_level 和 rep_level 经常有长 run（如大量非 NULL 值的 def_level 都相同），因此 RLE 编码效率很高。

七、页级编码选择与 Parquet 文件结构

7.1 Parquet 文件的物理结构

+---------------------------+
| Magic: "PAR1" (4 bytes)   |
+---------------------------+
| Row Group 0               |
|   +---------------------+ |
|   | Column Chunk: col_0  | |
|   |   [Dict Page]        | |
|   |   [Data Page 0]      | |
|   |   [Data Page 1]      | |
|   +---------------------+ |
|   | Column Chunk: col_1  | |
|   |   [Data Page 0]      | |
|   |   [Data Page 1]      | |
|   +---------------------+ |
+---------------------------+
| Row Group 1               |
|   ...                     |
+---------------------------+
| Footer                    |
|   [File Metadata]         |
|   [Footer Length] (4B)    |
|   Magic: "PAR1" (4B)     |
+---------------------------+

7.2 数据页结构

每个数据页（Data Page V2）的结构：

+-----------------------------------+
| Page Header (Thrift encoded)      |
|   - page type                     |
|   - uncompressed size             |
|   - compressed size               |
|   - num values                    |
|   - encoding                      |
|   - def level byte length         |
|   - rep level byte length         |
+-----------------------------------+
| Repetition Levels (uncompressed)  |
| [RLE/BP encoded]                  |
+-----------------------------------+
| Definition Levels (uncompressed)  |
| [RLE/BP encoded]                  |
+-----------------------------------+
| Values (may be compressed)        |
| [encoding-specific format]        |
+-----------------------------------+

7.3 编码选择策略

Parquet 支持多种编码方式，写入器需要根据数据特征选择最优编码：

BYTE_STREAM_SPLIT 是一个巧妙的编码：将浮点数的字节按位置分组。例如 4 字节 float 的第 0 个字节放一起，第 1 个字节放一起，以此类推。同一位置的字节 往往具有相似性，有利于后续的通用压缩。

原始 float32 序列（hex）:
  3F800000  3F800000  3F000000  3F000000

按字节位置分组:
  byte 0: 3F 3F 3F 3F  -> 高重复
  byte 1: 80 80 00 00  -> 中等重复
  byte 2: 00 00 00 00  -> 完全相同
  byte 3: 00 00 00 00  -> 完全相同

7.4 页大小的权衡

页大小    | 压缩率     | 随机访问粒度 | 内存使用    | I/O 效率
----------|-----------|-------------|------------|----------
小（8 KB）| 较差      | 细粒度      | 低         | 多次小 I/O
中（1 MB）| 较好      | 中等        | 中等       | 平衡
大（8 MB）| 最好      | 粗粒度      | 高         | 少次大 I/O

Parquet 默认页大小为 1 MB，行组大小为 128 MB。

八、Arrow IPC 格式

8.1 Arrow 的设计哲学

Apache Arrow 是内存中的列式数据格式标准，其 IPC（Inter-Process Communication） 格式是它的序列化形式。与 Parquet 的”压缩存储”定位不同，Arrow IPC 追求 零拷贝反序列化。

Parquet 的目标: 最小化存储大小 -> 编码 + 压缩
Arrow IPC 的目标: 最小化序列化/反序列化开销 -> 对齐 + 零拷贝

8.2 Arrow IPC 的消息格式

Arrow IPC Stream Format:
  [Schema Message]
  [RecordBatch Message 0]
  [RecordBatch Message 1]
  ...
  [End of Stream marker]

每个 RecordBatch Message:
  +---------------------------+
  | Metadata (flatbuffers)    |
  |   - schema                |
  |   - buffer layouts        |
  |   - null counts           |
  +---------------------------+
  | Body (raw buffers)        |
  |   - validity bitmaps      |
  |   - offsets (for strings) |
  |   - data buffers          |
  +---------------------------+

8.3 Arrow IPC 中的压缩

Arrow IPC 从 1.0 版本开始支持可选的 buffer 级压缩：

支持的压缩算法:
  - LZ4_FRAME: 默认推荐，解压极快
  - ZSTD: 更高压缩率

压缩粒度: 每个 buffer 独立压缩
  - 对于 Dictionary-encoded 列: 字典 buffer 和索引 buffer 分别压缩
  - 对于 String 列: offset buffer 和 data buffer 分别压缩

8.4 Arrow 的字典编码

Arrow 原生支持字典编码（DictionaryType），这是一种逻辑类型而非物理编码：

// Arrow Dictionary-encoded Array 的内存布局
// 以 string 列为例:

// Dictionary (共享):
//   offset buffer: [0, 7, 15, 23]
//   data buffer:   "BeijingShanghaiShenzhen"

// Indices Array:
//   type: int32
//   values: [0, 0, 1, 0, 2, 1, 0, 0]

// 逻辑值: Beijing, Beijing, Shanghai, Beijing, Shenzhen, Shanghai, Beijing, Beijing

在 Arrow IPC 中，字典可以在消息间共享（Delta Dictionary），避免重复传输：

Message 0: DictionaryBatch (id=0, data=["Beijing","Shanghai","Shenzhen"])
Message 1: RecordBatch (col_0 uses dict id=0, indices=[0,1,2,0])
Message 2: RecordBatch (col_0 uses dict id=0, indices=[1,0,2,1])
// 字典只传输一次

8.5 Arrow vs Parquet：互补而非竞争

维度        | Parquet              | Arrow IPC
------------|---------------------|-------------------
定位        | 持久存储（磁盘）     | 内存交换（IPC/网络）
编码复杂度  | 高（多种编码组合）   | 低（接近原始布局）
压缩率      | 极高（10-20x）       | 中等（2-5x with LZ4）
随机访问    | 行组/页级别           | RecordBatch 级别
写入速度    | 较慢（编码开销）     | 极快（接近 memcpy）
读取速度    | 需要解码             | 零拷贝
典型用途    | 数据湖、离线分析     | Spark shuffle、跨进程传递

九、完整 C 实现：字典编码器（含 RLE 回退）

下面给出一个完整的 C 语言实现，包含字典构建、Bit-Packing 编码、RLE 回退逻辑， 以及解码验证。编译：gcc -O2 -Wall -o dict_encoder dict_encoder.c

/* dict_encoder.c -- dictionary encoder with RLE fallback */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <assert.h>

#define MAX_DICT   4096
#define MAX_STRLEN 128

/* ---- Dictionary ---- */
typedef struct { char entries[MAX_DICT][MAX_STRLEN]; int size; } Dict;

static int dict_find(const Dict *d, const char *v) {
    for (int i = 0; i < d->size; i++)
        if (strcmp(d->entries[i], v) == 0) return i;
    return -1;
}
static int dict_add(Dict *d, const char *v) {
    int i = dict_find(d, v);
    if (i >= 0) return i;
    assert(d->size < MAX_DICT);
    strncpy(d->entries[d->size], v, MAX_STRLEN - 1);
    return d->size++;
}

/* ---- Bit-width ---- */
static int bit_width(int max_val) {
    int w = 0; unsigned v = (unsigned)max_val;
    while (v) { w++; v >>= 1; }
    return w ? w : 1;
}

/* ---- Bit-Packing ---- */
typedef struct { uint8_t *data; int bytes, count, bw; } BPBuf;

static BPBuf bp_encode(const int *vals, int n, int bw) {
    BPBuf b = { .bw = bw, .count = n, .bytes = (n * bw + 7) / 8 };
    b.data = calloc(b.bytes + 4, 1);
    uint32_t mask = (1U << bw) - 1;
    int pos = 0;
    for (int i = 0; i < n; i++) {
        int bi = pos >> 3, bo = pos & 7;
        uint32_t v = (uint32_t)vals[i] & mask;
        b.data[bi] |= (uint8_t)(v << bo);
        if (bo + bw > 8)  b.data[bi+1] |= (uint8_t)(v >> (8 - bo));
        if (bo + bw > 16) b.data[bi+2] |= (uint8_t)(v >> (16 - bo));
        pos += bw;
    }
    return b;
}
static void bp_decode(const BPBuf *b, int *out) {
    uint32_t mask = (1U << b->bw) - 1;
    int pos = 0;
    for (int i = 0; i < b->count; i++) {
        int bi = pos >> 3, bo = pos & 7;
        uint32_t r = (uint32_t)b->data[bi] >> bo;
        if (bo + b->bw > 8)  r |= (uint32_t)b->data[bi+1] << (8 - bo);
        if (bo + b->bw > 16) r |= (uint32_t)b->data[bi+2] << (16 - bo);
        out[i] = (int)(r & mask);
        pos += b->bw;
    }
}

/* ---- RLE ---- */
typedef struct { int val, cnt; } Run;
typedef struct { Run *runs; int nruns, total; } RLEBuf;

static RLEBuf rle_encode(const int *v, int n) {
    RLEBuf b = { .runs = malloc(sizeof(Run) * n), .total = n };
    int cv = v[0], cc = 1;
    for (int i = 1; i < n; i++) {
        if (v[i] == cv) { cc++; continue; }
        b.runs[b.nruns++] = (Run){ cv, cc };
        cv = v[i]; cc = 1;
    }
    b.runs[b.nruns++] = (Run){ cv, cc };
    return b;
}
static void rle_decode(const RLEBuf *b, int *out) {
    int p = 0;
    for (int i = 0; i < b->nruns; i++)
        for (int j = 0; j < b->runs[i].cnt; j++)
            out[p++] = b->runs[i].val;
}

/* ---- Encoded Column ---- */
typedef enum { ENC_BP, ENC_RLE } EncMode;
typedef struct {
    Dict d; EncMode mode; BPBuf bp; RLEBuf rle; int nvals;
} EncCol;

static EncCol encode_column(const char **strs, int n) {
    EncCol c = { .nvals = n };
    int *idx = malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) idx[i] = dict_add(&c.d, strs[i]);

    RLEBuf rle = rle_encode(idx, n);
    double ratio = (double)rle.nruns / n;
    int bw = bit_width(c.d.size - 1);

    if (ratio < 0.5) {
        c.mode = ENC_RLE; c.rle = rle;
        printf("[enc] RLE: %d runs / %d vals (ratio=%.3f)\n", rle.nruns, n, ratio);
    } else {
        c.mode = ENC_BP; c.bp = bp_encode(idx, n, bw);
        free(rle.runs);
        printf("[enc] BitPack: bw=%d, ratio=%.3f\n", bw, ratio);
    }
    free(idx);
    return c;
}

static char **decode_column(const EncCol *c) {
    int *idx = malloc(sizeof(int) * c->nvals);
    if (c->mode == ENC_RLE) rle_decode(&c->rle, idx);
    else                    bp_decode(&c->bp, idx);

    char **out = malloc(sizeof(char*) * c->nvals);
    for (int i = 0; i < c->nvals; i++)
        out[i] = strdup(c->d.entries[idx[i]]);
    free(idx);
    return out;
}

static void free_enc(EncCol *c) {
    if (c->mode == ENC_BP) free(c->bp.data); else free(c->rle.runs);
}

/* ---- Size estimation ---- */
static size_t raw_size(const char **s, int n) {
    size_t t = 0;
    for (int i = 0; i < n; i++) t += strlen(s[i]) + 1;
    return t;
}
static size_t enc_size(const EncCol *c) {
    size_t ds = 0;
    for (int i = 0; i < c->d.size; i++) ds += strlen(c->d.entries[i]) + 1;
    size_t is = (c->mode == ENC_RLE)
        ? (size_t)c->rle.nruns * 8 : (size_t)c->bp.bytes;
    return ds + is;
}

/* ---- Tests ---- */
static void test_sorted(void) {
    printf("\n--- Sorted Data (expect RLE) ---\n");
    const char *v[] = {
        "Beijing","Beijing","Beijing","Beijing","Beijing",
        "Beijing","Beijing","Beijing","Beijing","Beijing",
        "Shanghai","Shanghai","Shanghai","Shanghai","Shanghai",
        "Shenzhen","Shenzhen","Shenzhen","Shenzhen","Shenzhen",
    };
    int n = 20;
    EncCol c = encode_column(v, n);
    char **d = decode_column(&c);
    for (int i = 0; i < n; i++) assert(strcmp(v[i], d[i]) == 0);
    printf("raw=%zu enc=%zu ratio=%.1fx  OK\n", raw_size(v,n), enc_size(&c),
           (double)raw_size(v,n) / enc_size(&c));
    for (int i = 0; i < n; i++) free(d[i]);
    free(d); free_enc(&c);
}

static void test_unsorted(void) {
    printf("\n--- Unsorted Data (expect BitPack) ---\n");
    const char *v[] = {
        "Beijing","Shanghai","Shenzhen","Guangzhou",
        "Shanghai","Beijing","Guangzhou","Shenzhen",
        "Shenzhen","Beijing","Shanghai","Guangzhou",
        "Guangzhou","Shenzhen","Beijing","Shanghai",
    };
    int n = 16;
    EncCol c = encode_column(v, n);
    char **d = decode_column(&c);
    for (int i = 0; i < n; i++) assert(strcmp(v[i], d[i]) == 0);
    printf("raw=%zu enc=%zu ratio=%.1fx  OK\n", raw_size(v,n), enc_size(&c),
           (double)raw_size(v,n) / enc_size(&c));
    for (int i = 0; i < n; i++) free(d[i]);
    free(d); free_enc(&c);
}

int main(void) {
    printf("Dictionary Encoder with RLE Fallback\n");
    test_sorted();
    test_unsorted();
    printf("\nAll tests passed.\n");
    return 0;
}

编码选择的核心逻辑在 encode_column 中——先构建字典，将字符串转为整数索引， 然后对索引序列尝试 RLE。如果 num_runs / total_values < 0.5（数据有序，run 少）， 选择 RLE；否则选择 Bit-Packing。这个启发式简单但在实践中效果不错。

十、基准测试：Parquet vs ORC vs CSV

10.1 测试环境与方法

硬件: AMD EPYC 7R13 (64 cores), 256 GB DDR4, NVMe SSD (3 GB/s)
软件: Spark 3.5.0, Parquet 1.13, ORC 1.9, Zstd 1.5.5
数据集: TPC-H SF=100（约 6 亿行 lineitem）

10.2 文件大小对比

10.3 查询性能对比

测试查询：TPC-H Q6（简单扫描 + 过滤 + 聚合）

SELECT sum(l_extendedprice * l_discount) as revenue
FROM lineitem
WHERE l_shipdate >= '1994-01-01'
  AND l_shipdate < '1995-01-01'
  AND l_discount BETWEEN 0.05 AND 0.07
  AND l_quantity < 24;

关键观察：Parquet/ORC 的查询速度是 CSV 的 20 倍以上，主要得益于列裁剪和谓词下推。 压缩率更高意味着磁盘 I/O 更少，在大多数场景下减少 I/O 的收益远大于解码的 CPU 开销。

10.4 逐列编码效果分析

以 lineitem 表的几个典型列为例：

列名             | 类型     | 基数       | Parquet 编码       | 压缩比
-----------------|----------|-----------|-------------------|--------
l_orderkey       | INT64    | 1.5 亿    | DELTA_BINARY_PACKED| 3.2x
l_partkey        | INT64    | 2000 万   | DELTA_BINARY_PACKED| 2.8x
l_suppkey        | INT64    | 100 万    | DELTA_BINARY_PACKED| 2.5x
l_linenumber     | INT32    | 7         | RLE_DICTIONARY     | 32x
l_quantity       | DECIMAL  | 50        | RLE_DICTIONARY     | 18x
l_shipmode       | STRING   | 7         | RLE_DICTIONARY     | 45x
l_returnflag     | STRING   | 3         | RLE_DICTIONARY     | 64x
l_linestatus     | STRING   | 2         | RLE_DICTIONARY     | 72x
l_comment        | STRING   | 极高      | PLAIN + ZSTD       | 4.5x
l_shipdate       | DATE     | ~2500     | DELTA_BINARY_PACKED| 8.2x

可以看到：

• 低基数的字符串/枚举列（如 l_returnflag、l_shipmode）压缩率极高， 字典 + RLE 组合可达 40-70 倍。
• 高基数的数值列使用 Delta 编码也有 2-3 倍的压缩。
• 自由文本列（如 l_comment）只能依赖通用压缩，压缩率相对有限。

十一、工业实践：ClickHouse、DuckDB、Databricks、Snowflake

11.1 ClickHouse

ClickHouse 是列式数据库的典型代表，其压缩策略极具参考价值：

MergeTree 引擎的编码层:
  1. 列数据按 granule（8192 行）分块
  2. 每个块可选择不同的编码:
     - DoubleDelta: 时间戳列的差值的差值
     - Gorilla: 浮点数 XOR 编码（来自 Facebook Gorilla 论文）
     - T64: 64-bit 整数的转置位编码
     - LowCardinality: 内建字典编码类型
  3. 编码后再应用通用压缩（默认 LZ4）

ClickHouse 的一个独特设计是 LowCardinality 类型——这不是一种编码，而是 一种数据类型。声明 LowCardinality(String) 后，列在存储和查询执行中都使用 字典编码，避免了编解码的开销。

11.2 DuckDB

DuckDB 作为嵌入式 OLAP 数据库，其压缩策略更加自动化：

DuckDB 的压缩选择算法:
  1. 采样列数据（通常取前 N 行）
  2. 依次尝试以下编码（按预期压缩率从高到低）:
     a. Constant: 如果所有值相同
     b. Dictionary + BitPacking: 如果基数低
     c. FSST: 如果是字符串列且 FSST 有效
     d. CHIMP / Patas: 如果是浮点数列
     e. ALP: Adaptive Lossless floating-Point compression
     f. RLE: 如果数据排序良好
     g. BitPacking / FOR: 如果数值范围小
     h. Uncompressed: 回退方案
  3. 选择压缩率最高的方案

DuckDB 的 ALP（Adaptive Lossless floating-Point compression）是一项创新： 它检测浮点数是否可以无损地表示为整数（如 3.14 -> 314 / 100），如果可以， 则转为整数编码，压缩率大幅提升。

11.3 Databricks 与 Delta Lake

Databricks 在 Delta Lake 之上的优化主要体现在：

1. Z-ORDER 聚簇:
   - 将多列的值通过 Z-curve 映射到一维，使相关数据物理相邻
   - 提升多列谓词下推的效率
   - 增强列内数据局部性，间接提升压缩率

2. OPTIMIZE 与 COMPACT:
   - 合并小文件为大文件
   - 重新排序数据以提升压缩率
   - 生成统计信息（min/max）用于数据跳过

3. Photon 引擎:
   - C++ 向量化执行引擎
   - 延迟解码: 尽可能在编码态下完成过滤
   - 字典编码列的谓词可直接在字典索引上执行

11.4 Snowflake

Snowflake 使用自研的列式存储格式（Micro-Partition）：

Micro-Partition 特点:
  - 每个分区 50-500 MB（压缩后）
  - 不可变（immutable），类似 Parquet 文件
  - 自动收集每列的 min/max/distinct count 等统计信息
  - 支持的编码: RLE、Dictionary、Delta、Truncation 等

Snowflake 的独特优化:
  - 自动聚簇（Auto-Clustering）: 根据查询模式自动重排数据
  - 结果缓存: 相同查询的中间/最终结果缓存在 SSD 上
  - 编码态计算: 尽量在编码/压缩态下完成 filter/project

11.5 各系统对比

十二、工程陷阱与个人观点

12.1 常见工程陷阱

12.2 我的个人观点

关于编码 vs 通用压缩的优先级

很多团队在数据湖项目中花大量精力对比 Snappy、LZ4、Zstd 的压缩率和速度，却忽略了 编码层才是压缩率的主要来源。在我的经验中，一个好的编码选择（字典 + RLE/BitPacking + Delta）通常贡献了 80% 的压缩率，通用压缩器只贡献 20%。

关于排序键的重要性

如果让我给数据工程师一条建议，那就是：花 80% 的时间思考表的排序键，而不是压缩 算法。一个正确的排序键可以让 RLE 压缩率提升 100 倍，而在错误的排序键上，再好 的压缩算法也回天无力。

ClickHouse 的文档中有一句话说得好：“排序键的选择是 ClickHouse 表设计中最重要的 决策。”这句话对所有列式存储系统都适用。

关于 FSST 的前景

FSST 目前只在 DuckDB 中被广泛使用，但我认为它会被更多系统采纳——它填补了 “高基数字符串列”这个编码空白，且随机访问特性对向量化执行引擎非常友好。

关于编码态计算的趋势

最值得关注的趋势是”编码态计算”——在不解码的情况下直接在编码数据上执行查询。 例如对字典编码列做 WHERE city = 'Beijing'，先在字典查索引 0，再在索引数组中 扫描，完全不需要解码字符串。对 RLE 列做 COUNT 则直接对 run_length 求和。

关于未来方向

1. 自适应编码：根据运行时统计信息动态切换编码方案。
2. 硬件加速：利用 SIMD 加速 Bit-Packing、FSST 的解码，Arrow 和 DuckDB 已在这方面做了大量工作。
3. Learned Encoding：用机器学习预测最优编码方案。
4. 端到端压缩：将编码、压缩、索引、查询优化统一考虑。

列式存储的压缩率优势，本质上是数据局部性的胜利。理解这个本质，比记住任何具体的 编码算法都更重要。

参考资料

1. Apache Parquet Format Specification. https://parquet.apache.org/documentation/latest/
2. Apache Arrow Columnar Format. https://arrow.apache.org/docs/format/Columnar.html
3. P. Boncz et al. “FSST: Fast Random Access String Compression.” VLDB 2020.
4. D. Abadi et al. “Integrating Compression and Execution in Column-Oriented Database Systems.” SIGMOD 2006.
5. ClickHouse Docs: Compression Codecs. https://clickhouse.com/docs/en/sql-reference/statements/create/table
6. DuckDB Docs: Storage. https://duckdb.org/docs/internals/storage
7. D. Lemire, L. Boytsov. “Decoding Billions of Integers Through Vectorized Bit Packing.” SPE 2015.
8. Apache ORC Specification. https://orc.apache.org/specification/

上一篇: 时序数据压缩 下一篇: 凸包算法 相关阅读: - 整数压缩 - zstd 深度解剖