第4章：列式存储（Columnar Storage）

一、导读

1.1 本章学习目标

第4章讲解面向分析场景的列式存储引擎。与行式存储不同，列式存储将同一列的数据连续存放在一起，这种组织方式极大地提高了分析查询的效率和数据压缩率。

本章核心学习目标：

理解列式存储 vs 行式存储的本质区别：数据组织方式如何影响查询性能
掌握列式存储的编码方案：字典编码、游程编码、位打包、Delta 编码
理解列式存储的压缩技术：为什么列式存储的压缩率远高于行式存储
掌握典型列式格式：Parquet、ORC、ClickHouse 的存储结构
理解向量化执行引擎：列式存储如何与现代 CPU 的 SIMD 指令配合

1.2 为什么本章如此重要

现代数据分析场景（数据仓库、OLAP、BI 报表）几乎都采用列式存储。从 Parquet 到 ClickHouse，从 Snowflake 到 BigQuery，列式存储已经成为分析型数据库的事实标准。

理解列式存储的原理，能帮助你：

选择合适的列式格式和压缩算法
理解为什么某些查询快而某些查询慢
优化数据分区和排序策略

1.3 核心问题引导

为什么 SELECT AVG(salary) FROM employees 在列式存储上比行式存储快 10 倍以上？

列式存储的字典编码是什么？什么场景下效果最好？

Parquet 的 Row Group 和 Column Chunk 是什么关系？

为什么列式存储不适合点查询和频繁更新？

二、核心概念详解

2.1 行式存储 vs 列式存储

行式存储 (Row-Oriented):
┌────┬────────┬─────┬──────────┐
│ id │ name   │ age │ salary   │
├────┼────────┼─────┼──────────┤
│ 1  │ Alice  │ 30  │ 50000    │  ← 一行连续存储
│ 2  │ Bob    │ 25  │ 60000    │
│ 3  │ Carol  │ 35  │ 55000    │
│ 4  │ Dave   │ 28  │ 70000    │
└────┴────────┴─────┴──────────┘

列式存储 (Column-Oriented):
id:     [1, 2, 3, 4]          ← 同一列连续存储
name:   [Alice, Bob, Carol, Dave]
age:    [30, 25, 35, 28]
salary: [50000, 60000, 55000, 70000]

核心差异：

维度	行式存储	列式存储
查询 `SELECT *`	高效（一次读取整行）	低效（需要合并多列）
查询 `SELECT col`	低效（读取整行，丢弃不需要的列）	高效（只读取需要的列）
聚合查询	低效	高效（向量化处理）
压缩率	低（混合类型数据）	高（同类型数据）
更新操作	高效（原地修改）	低效（需要修改多个列文件）

2.2 列式存储的编码方案

2.2.1 字典编码（Dictionary Encoding）

将重复出现的值映射为整数索引：

原始数据: [Alice, Bob, Alice, Carol, Alice, Bob]
字典: {Alice: 0, Bob: 1, Carol: 2}
编码后: [0, 1, 0, 2, 0, 1]

优势:
- 原始: 6 × 5 bytes (字符串) = 30 bytes
- 编码: 6 × 1 byte (索引) + 字典 = 6 + 15 = 21 bytes
- 压缩率提升，且整数比较比字符串比较快得多

适用场景: 低基数列（如性别、状态、城市名）

2.2.2 游程编码（Run-Length Encoding, RLE）

将连续重复的值压缩为 (值, 计数) 对：

原始数据: [1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3]
RLE 编码: [(1, 4), (2, 2), (3, 5)]

优势:
- 原始: 11 × 4 bytes = 44 bytes
- 编码: 3 × (4 + 4) bytes = 24 bytes
- 对于排序后的数据，RLE 压缩率极高

适用场景: 排序后的数据、低基数列

2.2.3 Delta 编码

存储相邻值的差值而非原始值：

原始数据: [1000, 1001, 1003, 1006, 1010]
Delta 编码: [1000, 1, 2, 3, 4]

优势:
- 差值通常比原始值小，可以用更少的字节存储
- 对于时间戳、递增 ID 等单调递增数据效果极好

适用场景: 时间戳、自增 ID、排序后的数值列

2.2.4 位打包（Bit Packing）

根据实际值范围动态调整每个值占用的位数：

原始数据: [3, 7, 1, 5, 6, 2]  (范围 1-7, 需要 3 bits)
位打包: [011, 111, 001, 101, 110, 010]
总位数: 6 × 3 = 18 bits = 2.25 bytes

原始存储: 6 × 32 bits = 192 bits = 24 bytes
压缩比: 192 / 18 ≈ 10.7x

2.3 Parquet 文件格式

Parquet 是 Apache 基金会开发的列式存储格式，被 Spark、Hive、Presto 等广泛使用。

Parquet 文件结构:
┌─────────────────────────────────────┐
│         4 bytes: Magic "PAR1"       │
├─────────────────────────────────────┤
│        Row Group 0                  │
│  ┌─────────────────────────────┐    │
│  │ Column Chunk 0 (id)         │    │
│  │  - Page 0 (Data Page)       │    │
│  │  - Page 1 (Data Page)       │    │
│  │  - Page 2 (Dictionary Page) │    │
│  ├─────────────────────────────┤    │
│  │ Column Chunk 1 (name)       │    │
│  │  - Page 0 (Data Page)       │    │
│  │  ...                        │    │
│  ├─────────────────────────────┤    │
│  │ Column Chunk N (...)        │    │
│  └─────────────────────────────┘    │
├─────────────────────────────────────┤
│        Row Group 1                  │
│        ...                          │
├─────────────────────────────────────┤
│        Footer                       │
│  - Schema                           │
│  - Row Group 元数据                  │
│  - Column Chunk 统计信息             │
│  - Key-Value 元数据                  │
├─────────────────────────────────────┤
│        4 bytes: Footer Length       │
├─────────────────────────────────────┤
│        4 bytes: Magic "PAR1"        │
└─────────────────────────────────────┘

Row Group 是 Parquet 的基本读写单位，典型大小为 128MB-1GB。每个 Row Group 包含一批行的所有列数据。

Column Chunk 是一个 Row Group 中某一列的所有数据。它由多个 Page 组成：

Data Page：包含实际的数据值（经过编码和压缩）
Dictionary Page：字典编码的字典数据
Statistics：每页的最小值、最大值、空值计数（用于查询跳过）

2.4 向量化执行

列式存储天然适合向量化执行——一次处理一批数据（而非一次处理一行），充分利用现代 CPU 的 SIMD 指令和缓存局部性。

标量执行 (一次一行):
for row in table:
    if row.age > 30:
        result.append(row.salary)

向量化执行 (一次一批):
batch_size = 1024
for batch in column_batches:
    mask = batch.age > 30        # SIMD 比较
    result.extend(batch.salary[mask])  # SIMD 过滤

向量化执行的优势：

CPU 缓存友好：连续处理同一列的数据，缓存命中率高
SIMD 指令：一条指令处理多个数据（如 AVX-512 一次处理 16 个 int32）
分支预测友好：减少条件分支，使用位掩码替代

三、实战案例

3.1 案例一：Parquet vs CSV 性能对比

python

import pandas as pd
import time
import os

# 生成测试数据
n = 10_000_000
df = pd.DataFrame({
    'id': range(n),
    'name': [f'user_{i}' for i in range(n)],
    'age': [20 + i % 50 for i in range(n)],
    'salary': [50000 + i * 10 for i in range(n)],
    'department': ['Engineering', 'Sales', 'Marketing', 'HR'][i % 4] for i in range(n)
})

# CSV 写入和读取
start = time.time()
df.to_csv('/tmp/test.csv', index=False)
csv_write_time = time.time() - start

start = time.time()
df_csv = pd.read_csv('/tmp/test.csv')
csv_read_time = time.time() - start

# Parquet 写入和读取
start = time.time()
df.to_parquet('/tmp/test.parquet', engine='pyarrow', compression='snappy')
pq_write_time = time.time() - start

start = time.time()
df_pq = pd.read_parquet('/tmp/test.parquet', columns=['department', 'salary'])
pq_read_time = time.time() - start

# 结果
csv_size = os.path.getsize('/tmp/test.csv') / 1024 / 1024
pq_size = os.path.getsize('/tmp/test.parquet') / 1024 / 1024

print(f"CSV:  {csv_size:.1f} MB, write={csv_write_time:.2f}s, read={csv_read_time:.2f}s")
print(f"Parquet: {pq_size:.1f} MB, write={pq_write_time:.2f}s, read={pq_read_time:.2f}s")
print(f"压缩率: {csv_size/pq_size:.1f}x")
print(f"读取加速: {csv_read_time/pq_read_time:.1f}x")

# 典型输出:
# CSV:     420.3 MB, write=8.5s, read=6.2s
# Parquet:  85.7 MB, write=3.1s, read=0.8s
# 压缩率: 4.9x
# 读取加速: 7.8x

四、本章小结

列式存储将同列数据连续存放，适合分析型查询（只读少数列、大量聚合）

编码方案（字典编码、RLE、Delta 编码、位打包）大幅降低存储空间

Parquet 是最流行的列式格式，通过 Row Group、Column Chunk、Page 三级结构组织数据

向量化执行利用列式数据的连续性，充分发挥 CPU 的 SIMD 和缓存优势

五、思考与练习

思考题

为什么列式存储不适合 SELECT * 查询和频繁更新？

字典编码在什么场景下会适得其反？

Parquet 的 Statistics 信息如何帮助查询优化？

编程练习

实现一个简单的列式存储引擎，支持写入、按列读取和基本聚合。

实现字典编码和 RLE 编码，对比不同数据特征下的压缩率。