用 Rust 从零实现列式存储:编码比压缩算法更重要
"列式存储快",这句话的原因常被简单归结为"列压缩比高"。但压缩只解释了一半。
更本质的原因是:分析型查询通常只碰少部分列。 行存读一行要带出全部 50 列,列存只读需要的那 3 列——IO 量直接少了一个数量级。
而让列存真正强大的第二层,是编码:列内的数据高度同质(全是同一类型的值),所以有大量可以利用的规律。
先看清行存的问题
假设一张订单表,一行是:
pub struct Order {
pub id: u64,
pub user_id: u64,
pub amount: i64,
pub status: u8,
pub created_at: i64,
pub region: [u8; 8],
// ... 还有 40 个字段
}行存的存储方式:
[id1][user1][amount1][status1][ts1][region1][...]
[id2][user2][amount2][status2][ts2][region2][...]
[id3][user3][amount3][status3][ts3][region3][...]查询 SELECT sum(amount) WHERE region = 'x' 时:
- 只关心
amount和region两列 - 但每个磁盘块里混着全部字段
- 扫 1GB 数据,实际用到的可能只有 60MB
更糟的是 CPU 缓存: 每个 cache line(64 字节)里只有几个字节是需要的。
列存的布局:
id: [1][2][3][4]...[n]
user_id: [u1][u2][u3]...[un]
amount: [a1][a2][a3]...[an]
status: [s1][s2][s3]...[sn]同样的查询只需要读 amount 和 region 两段连续内存。 IO 量按列的比例下降。
编码才是重点
把同一列的值连续存放之后,会发现它们有很强的规律:
status 列: [1,1,1,1,1,1,2,2,2,2,1,1,1,1] -> 大量重复
region 列: ["cn-beijing","cn-beijing",...] -> 字典编码
id 列: [1001,1002,1003,1004,...] -> 等差!增量编码
amount 列: [100,200,300,400,...] -> 同上
timestamp: [1700000000,1700000001,...] -> 大数但增量小四种规律对应四种编码,这才是列存能压到 10:1 以上的原因——而通用压缩算法(gzip、zstd)在这些场景下反而效果一般,因为它们看到的是"字节流",不是"数值规律"。
列存的核心竞争力是"按列的语义做编码",不是"用更强的压缩算法"。 这也是为什么 Parquet 的 zstd 压缩率通常不如它自带的字典 + RLE 组合。
编码一:字典编码(Dictionary)
适合基数低(不同值少)的列,比如状态、地区、类别。
pub struct DictionaryEncoder {
/// 值 -> 编码后的整数
dict: std::collections::HashMap<Vec<u8>, u32>,
/// 反向表,解码时用
values: Vec<Vec<u8>>,
/// 编码后的整数序列
codes: Vec<u32>,
}impl DictionaryEncoder {
pub fn new() -> Self {
Self {
dict: std::collections::HashMap::new(),
values: Vec::new(),
codes: Vec::new(),
}
}
pub fn encode(&mut self, value: &[u8]) -> u32 {
if let Some(&code) = self.dict.get(value) {
self.codes.push(code);
return code;
}
let code = self.values.len() as u32;
self.dict.insert(value.to_vec(), code);
self.values.push(value.to_vec());
self.codes.push(code);
code
}
pub fn decode(&self, code: u32) -> Option<&[u8]> {
self.values.get(code as usize).map(|v| v.as_slice())
}
/// 压缩率:原始字节数 / 编码后字节数
pub fn compression_ratio(&self) -> f64 {
let raw: usize = self.codes.iter().map(|_| 8).sum(); // 假设原始是 8 字节
let encoded = self.codes.len() * self.code_width();
raw as f64 / encoded.max(1) as f64
}
/// 编码需要多少位:基数 <= 256 用 1 字节,<= 65536 用 2 字节
fn code_width(&self) -> usize {
match self.values.len() {
0..=256 => 1,
257..=65536 => 2,
_ => 4,
}
}
}两个关键优化:
1. 码宽按基数选。 只有 5 个不同的 status 值,每个码只需要 3 个 bit——而不是 4 字节。
2. 字典本身也要编码。 字典往往是字符串,可以用前缀共享(类似 Trie 的序列化)来压缩。
字典编码还有一个隐藏的好处:直接支持 GROUP BY 和等值比较。
WHERE status = 'paid'
-> 先在字典里查 'paid' 的码是 2
-> 然后只需要比较整数 2,而不是字符串比较字符串比较是全内存扫描里最慢的操作之一(要逐字节比)。转成整数比较之后,能快好几倍。
这也是为什么字典编码几乎所有列存格式都实现了。 它同时带来"压缩"和"查询加速"两个收益。
编码二:RLE(游程编码)
适合相邻值大量重复的列。比如排好序的时间戳、状态位。
#[derive(Debug, Clone, PartialEq)]
pub struct Run<T> {
pub value: T,
pub count: u32,
}
pub fn rle_encode(values: &[u32]) -> Vec<Run<u32>> {
let mut runs = Vec::new();
if values.is_empty() {
return runs;
}
let mut current = values[0];
let mut count = 1u32;
for &v in &values[1..] {
if v == current && count < u32::MAX {
count += 1;
} else {
runs.push(Run { value: current, count });
current = v;
count = 1;
}
}
runs.push(Run { value: current, count });
runs
}
pub fn rle_decode(runs: &[Run<u32>]) -> Vec<u32> {
let mut out = Vec::with_capacity(runs.iter().map(|r| r.count as usize).sum());
for run in runs {
out.extend(std::iter::repeat(run.value).take(run.count as usize));
}
out
}RLE 的关键在于"用 (值, 次数) 代替重复的值"。
不用 RLE: [1,1,1,1,1,1,1,1,1,1] = 40 字节(u32)
用 RLE: [(1, 10)] = 8 字节5 倍的压缩,而且解码是纯顺序的,非常快。
RLE 的天然搭档:位图(Bitmap)
布尔列(is_deleted、has_shipped)用位图最合适——1 个 bit 存一个值:
pub struct Bitmap {
bits: Vec<u64>,
len: usize,
}
impl Bitmap {
pub fn new(len: usize) -> Self {
Self {
bits: vec![0u64; len.div_ceil(64)],
len,
}
}
pub fn set(&mut self, i: usize) {
self.bits[i / 64] |= 1u64 << (i % 64);
}
pub fn get(&self, i: usize) -> bool {
(self.bits[i / 64] >> (i % 64)) & 1 == 1
}
/// 位图之间做 AND / OR,一次 64 位
pub fn and(&self, other: &Bitmap) -> Bitmap {
let bits = self.bits.iter().zip(&other.bits).map(|(a, b)| a & b).collect();
Bitmap { bits, len: self.len }
}
pub fn count_ones(&self) -> usize {
self.bits.iter().map(|b| b.count_ones() as usize).sum()
}
}位图不只是压缩手段,它还是"执行"的手段。
WHERE a > 10 AND b < 5 可以先用两个比较生成两个位图,然后一次 64 位的 AND 得到结果——这是向量化执行的基础(下一篇的主题)。
而且 RLE 和位图天然互补:位图只在"稀疏"时才值得(否则 1 bit/值 已经是最小单位),RLE 在"成段重复"时更优。很多格式会根据数据特征自动选。
编码三:增量编码(Delta)
适合单调递增或接近等差的列。典型是自增主键、时间戳。
pub fn delta_encode(values: &[i64]) -> Vec<i64> {
if values.is_empty() {
return Vec::new();
}
let mut out = Vec::with_capacity(values.len());
out.push(values[0]); // 第一个存原值
for i in 1..values.len() {
out.push(values[i] - values[i - 1]);
}
out
}
pub fn delta_decode(deltas: &[i64]) -> Vec<i64> {
let mut out = Vec::with_capacity(deltas.len());
let mut acc = 0i64;
for &d in deltas {
acc += d;
out.push(acc);
}
out
}为什么有效? 看时间戳:
原值: [1700000000, 1700000001, 1700000002, 1700000003]
增量: [1700000000, 1, 1, 1]大数变成了小数。 而小数意味着——可以用更少的字节存。
增量 + 变长整数 + 位打包
增量之后通常还有一个"大多数增量很小、偶尔很大"的分布。所以:
第一步:增量编码。 大数变小。
第二步:位打包(bit packing)。 如果所有值都小于 2^7,每个只用 7 bit:
pub fn bit_pack(values: &[u64], bit_width: u32) -> Vec<u8> {
let mut out = Vec::new();
let mut buffer = 0u64;
let mut bits_in_buffer = 0u32;
for &v in values {
buffer |= (v & ((1u64 << bit_width) - 1)) << bits_in_buffer;
bits_in_buffer += bit_width;
while bits_in_buffer >= 8 {
out.push((buffer & 0xFF) as u8);
buffer >>= 8;
bits_in_buffer -= 8;
}
}
// 收尾
if bits_in_buffer > 0 {
out.push((buffer & 0xFF) as u8);
}
out
}
pub fn bit_unpack(data: &[u8], bit_width: u32, count: usize) -> Vec<u64> {
let mut out = Vec::with_capacity(count);
let mut buffer = 0u64;
let mut bits_in_buffer = 0u32;
let mut byte_idx = 0;
for _ in 0..count {
while bits_in_buffer < bit_width {
let byte = data.get(byte_idx).copied().unwrap_or(0) as u64;
buffer |= byte << bits_in_buffer;
bits_in_buffer += 8;
byte_idx += 1;
}
out.push(buffer & ((1u64 << bit_width) - 1));
buffer >>= bit_width;
bits_in_buffer -= bit_width;
}
out
}位打包的压缩比非常实在:如果增量都是个位数(0-15),bit_width = 4,也就是每个值 4 bit——比 u64 省 16 倍。
这就是 Parquet 里 "delta binary packed" 编码的效果,它对时间戳列的压缩率通常能达到 20:1 以上。
注意位打包的边界处理。 上面用"累积到 8 位就吐一个字节"的写法,避免了跨字节边界的复杂处理。这是位操作里最容易出错的地方,一定要写单元测试。
编码四:FOR(Frame of Reference)
有时一列的值都在一个很小的范围内,但不是从 0 开始:
[1000000, 1000001, 1000002, 1000003]增量编码会把第一个值 1000000 原样存下来——这是个"大数尾巴"。
FOR 的做法是"先减去最小值,再位打包":
pub struct ForEncoded {
pub min: u64,
pub bit_width: u32,
pub packed: Vec<u8>,
pub count: usize,
}
pub fn for_encode(values: &[u64]) -> Option<ForEncoded> {
if values.is_empty() {
return None;
}
let min = *values.iter().min()?;
let max = *values.iter().max()?;
// 偏移后的最大值决定位宽
let range = max - min;
let bit_width = 64 - range.leading_zeros();
let offsets: Vec<u64> = values.iter().map(|v| v - min).collect();
Some(ForEncoded {
min,
bit_width,
packed: bit_pack(&offsets, bit_width),
count: values.len(),
})
}FOR + 位打包,效果往往比增量还稳:它不会因为"第一个值特别大"而浪费。
实际格式里通常是组合使用:先做增量,再对增量做 FOR(因为增量分布也有个最小正值),再位打包。这就是 Parquet 的 "DELTA_BINARY_PACKED" 的实际结构。
编码选择:怎么自动决定
一个可用的实现应该根据数据特征自动选编码:
pub fn choose_encoding(values: &[i64]) -> Encoding {
if values.is_empty() {
return Encoding::Plain;
}
// 1. 先看去重后的基数
let distinct: std::collections::HashSet<_> = values.iter().collect();
if distinct.len() < values.len() / 4 && distinct.len() < 1024 {
return Encoding::Dictionary; // 基数低,字典编码
}
// 2. 看是否有很多连续重复
let repeats = values.windows(2).filter(|w| w[0] == w[1]).count();
if repeats > values.len() / 2 {
return Encoding::Rle; // 大量相邻重复
}
// 3. 看是否单调(或者近似单调)
let monotonic = values.windows(2).all(|w| w[0] <= w[1]);
if monotonic {
// 看增量是否小
let max_delta = values
.windows(2)
.map(|w| (w[1] - w[0]) as u64)
.max()
.unwrap_or(0);
if max_delta < 1 << 16 {
return Encoding::DeltaBinaryPacked; // 单调且增量小
}
}
// 4. 看值域是否集中
let min = *values.iter().min().unwrap();
let max = *values.iter().max().unwrap();
let range = (max - min) as u64;
// 相对值域很小 -> FOR
if (range as f64) < (max.abs() as f64) * 0.5 {
return Encoding::For;
}
Encoding::Plain
}注意这里的顺序:从"压缩收益最大"的条件开始判断。 字典 > RLE > 增量 > FOR > 原样。
真实实现(Parquet)还会做一件事:按块(page)而不是按整列选编码。 一个 100 万行的列会被切成 64KB 左右的页,每页独立选编码——因为数据的特征在局部可能不同(比如时间戳列的前半段是密集的,后半段是稀疏的)。
查询下推:让统计信息帮你跳过大块数据
编码之外,列存还有一个杀手特性:每个数据块都带统计信息(min/max),可以跳过整个块。
pub struct ColumnChunkStats {
pub min: i64,
pub max: i64,
pub null_count: u64,
pub row_count: u64,
}
impl ColumnChunkStats {
/// 判断这个块是否可能包含满足条件的行
pub fn might_match(&self, range: &(i64, i64)) -> bool {
// 区间不相交 -> 整块跳过
!(self.max < range.0 || self.min > range.1)
}
}这就是 zone map / 谓词下推(predicate pushdown)。
效果非常直接:WHERE created_at > '2026-01-01' 时,如果数据按时间排序存储,前面 80% 的块可以直接跳过,一次 IO 都不做。
pub fn scan_with_filter(chunks: &[ColumnChunk], predicate: &(i64, i64), col: usize) -> Vec<i64> {
let mut results = Vec::new();
for chunk in chunks {
// 1. 先用统计信息跳过
if !chunk.stats[col].might_match(predicate) {
continue;
}
// 2. 真正解码并过滤
let values = chunk.decode_column(col);
for v in values {
if v >= predicate.0 && v <= predicate.1 {
results.push(v);
}
}
}
results
}统计信息跳过是"免费的过滤"——它不需要解码,只需要读几十字节的元信息,就能排除整个数据块。
排序对分析型数据库的性能影响巨大,根本原因就在这里:有序的数据让 min/max 区间不重叠,谓词下推才能跳过大量块。
结论
列式存储的能力来自两层:
第一层是布局:同列连续存放,只读需要的列。 第二层是编码:字典(基数低)、RLE(成段重复)、增量 + 位打包(单调小增量)、FOR(值域集中),按块自动选择。
再加上一层"元数据加速":
每个块的 min/max 统计,让"不匹配的块"完全不用解码。
理解了这三层,再看 Parquet 的 encoding、page_size、row_group_size、statistics 这些配置,你会清楚每个旋钮在控制什么。而且会明白为什么"把数据按常用的过滤字段排序"能带来数量级的性能提升——它让 zone map 真正起作用。
下一篇我们去看"解码之后怎么算"——向量化执行引擎。