罗罗编程学习记录
本页内容 展开查看

05.8.4 向量化执行与列存压缩

所属:全栈开发面试题库 / 05 数据库与存储 / 05.8 OLAP 与列存

覆盖范围

  • 行存与列存的物理差异
  • 列存编码:字典、RLE、delta、bitpacking
  • 通用压缩算法:LZ4、ZSTD
  • 向量化执行:按列批量处理与 SIMD
  • 谓词下推与延迟物化

高频题速览

编号 题目 难度 频率
05.8.4-001 列存为什么压缩率高 基础 ★★★★★
05.8.4-002 常见列存编码有哪些 进阶 ★★★★
05.8.4-003 向量化执行比火山模型快在哪 进阶 ★★★★
05.8.4-004 谓词下推和延迟物化 进阶 ★★★
05.8.4-005 LZ4 和 ZSTD 怎么选 进阶 ★★★

05.8.4-001 列存为什么压缩率高?

频率 ★★★★★ | 难度 基础

一句话结论

列存同一列连续存储相同类型数据,相邻值重复或单调变化多(同枚举、同时间),压缩算法易找到冗余;行存一行混类型,压缩比低。

概念解释

  • 同质性:一列同类型,字节分布有规律。
  • 重复值:字典编码、RLE 压缩。
  • 单调值:delta 编码。

常见误区

  • 误区:列存压缩靠 LZ4/ZSTD。正解:列存先做轻量编码(字典/RLE/delta),再叠通用压缩。

05.8.4-002 常见列存编码有哪些?

频率 ★★★★ | 难度 进阶

一句话结论

字典编码(低基数字符串映射整数)、RLE 游程编码(重复值 值+次数)、delta 编码(存差值)、bitpacking(小整数压缩位宽)、位图(布尔/枚举);ORC/Parquet 按列自适应选编码。

代码 / 示例

原始列(状态字符串):
active,active,active,active,inactive,inactive,active
字典编码:{active:0, inactive:1}
RLE:0->4, 1->2, 0->1
最终字节:4 0, 2 1, 1 0

常见误区

  • 误区:高基数列也能用字典。正解:字典大反而占空间,高基数列用 delta+bitpacking 或直接压缩。

05.8.4-003 向量化执行比火山模型快在哪?

频率 ★★★★ | 难度 进阶

一句话结论

传统火山模型(Volcano)逐行调用 next(),虚函数调用开销大;向量化执行按列批量加载一批行(如 1024 行),在批内循环处理,减少函数调用开销,利用 CPU SIMD 和缓存局部性。

概念解释

  • 火山模型:每次 next() 处理一行。
  • 向量化:每次处理一个 batch。
  • SIMD:一条指令处理多个数据。

常见误区

  • 误区:向量化就是 SIMD。正解:向量化是批处理模型,SIMD 是底层指令,两者配合。

05.8.4-004 谓词下推和延迟物化是什么?

频率 ★★★ | 难度 进阶

一句话结论

谓词下推把过滤条件推到扫描层,在读列阶段就过滤;延迟物化先在列存用过滤列(如 id 列)筛选,再回表读取大列,避免读取被过滤掉行的大字段。

代码 / 示例

SELECT id, name, big_text FROM events
WHERE event_type = 'click';
-- 延迟物化:先按 event_type 列筛出命中行的 id,再读这些行的 big_text
-- 而不是先读所有行的 big_text 再过滤

常见误区

  • 误区:谓词下推只在分布式执行中。正解:单机列存扫描也有谓词下推。

05.8.4-005 LZ4 和 ZSTD 怎么选?

频率 ★★★ | 难度 进阶

一句话结论

LZ4 压缩快、解压快、压缩比中等,适合热数据频繁解压;ZSTD 压缩比高、压缩略慢,适合冷数据存储;ClickHouse 默认 LZ4,ORC/Parquet 常用 ZSTD/Snappy。

常见误区

  • 误区:压缩率越高越好。正解:高压缩比压缩/解压 CPU 开销大,频繁扫描的查询用 LZ4 更平衡。

05.8.4-005 Parquet 嵌套结构怎么存?

频率 ★★ | 难度 进阶

一句话结论

Parquet 用 Dremel 编码存储嵌套结构(repetition/definition level),支持嵌套 JSON 展开为列;ORC 嵌套支持弱于 Parquet。


05.8.4-006 编码和压缩是什么关系?

频率 ★★ | 难度 进阶

一句话结论

先做轻量编码(字典/RLE/delta),再叠通用压缩(LZ4/ZSTD);编码是结构化压缩,通用压缩是字节压缩;两者叠加效果最好。


05.8.4-007 向量化对 JOIN 有什么帮助?

频率 ★★ | 难度 高级

一句话结论

向量化 Hash Join 按列批量构建 hash 表,probing 批量处理,利用 SIMD;比火山模型逐行 JOIN 快数倍。

典型场景与代码示例

列存编码对比

原始列(status 字符串):
  active, active, active, active, inactive, inactive, active

字典编码:
  {active: 0, inactive: 1}
  [0, 0, 0, 0, 1, 1, 0]

RLE(游程编码):
  0->4, 1->2, 0->1
  字节:[4, 0, 2, 1, 1, 0]

压缩效果:100 字节原始数据 -> 5 字节压缩后

向量化执行流程

火山模型(逐行):
  for each row:
    value = row.column
    result = compute(value)

向量化(批处理):
  for batch of 1024 rows:
    values = load_column_batch()  // 批量加载到 CPU 寄存器
    results = simd_compute(values)  // SIMD 批量计算
    store_column_batch(results)

压缩格式选择

Snappy:
  压缩速度:快
  解压速度:快
  压缩比:中等
  适用:热数据频繁查询

ZSTD:
  压缩速度:中
  解压速度:中
  压缩比:高(比 Snappy 高 30%)
  适用:温数据、存储成本敏感

LZ4:
  压缩速度:最快
  解压速度:最快
  压缩比:低
  适用:实时热数据

面试高频追问

问:列存为什么压缩率高?

答:同一列连续存相同类型数据,相邻值重复或单调变化多,编码(字典/RLE/delta)易找冗余;行存混类型,压缩比低。

问:向量化比火山模型快在哪?

答:火山模型逐行调用 next(),虚函数开销大;向量化按列批量处理,减少函数调用,利用 SIMD 和缓存局部性。

问:LZ4 和 ZSTD 怎么选?

答:热数据频繁解压用 LZ4(解压快);冷数据存储用 ZSTD(压缩比高);不是越高压缩比越好。

问:谓词下推怎么工作?

答:引擎先读 footer 的 min/max 统计,跳过不匹配的行组,只读涉及列;避免全文件扫描。

核心要点速记

编码 原理 适用
字典 字符串映射整数 低基数字符串
RLE 重复值+次数 重复值多
delta 存差值 单调递增
bitpacking 小整数压缩位宽 小整数

向量化 vs 火山:批处理 vs 逐行;SIMD 加速。

一句话记忆:列存先编码再压缩;向量化是批处理模型。

相关概念辨析

行存 vs 列存

维度 行存 列存
存储 一行数据连续存储 一列数据连续存储
点查 快 慢
聚合扫描 慢 快
压缩 差 好
适合 OLTP OLAP

LZ4 vs ZSTD

  • LZ4:压缩比低,速度快,解压快。
  • ZSTD:压缩比高,速度中等,解压快。
  • 选择:热数据用 LZ4;冷数据用 ZSTD。

05.8.4-009 字典编码的原理和适用条件?

频率 ★★★ | 难度 进阶

一句话结论

字典编码把低基数字段的重复值映射为整数 ID,存储时只存 ID 数组;适用于基数低(如省份、状态、枚举)的字符串列。

概念解释

  • 字典编码:distinct value -> integer ID,存储 ID 数组。
  • 适用条件:基数低(< 100000),重复值多。
  • 不适用:高基数字段(如 user_id、URL),字典膨胀反而慢。

原理流程

  1. 写入时收集 distinct value,建字典表。
  2. 数据存储为 ID 数组,字典表单独存。
  3. 查询时先查字典表得到值,再做过滤。

代码 / 示例

-- ClickHouse 低基数字段用 LowCardinality
CREATE TABLE t (
  province LowCardinality(String),
  status LowCardinality(String),
  user_id UInt64
) ENGINE = MergeTree ORDER BY (province, status);

常见误区

  • 误区:所有字符串都用 LowCardinality。正解:高基数字典大,查询要反查字典,反而慢。

追问延伸

  • 查看基数:SELECT uniqExact(col) FROM t。
  • 字典膨胀:字典超过内存阈值时自动降级为普通编码。

05.8.4-010 谓词下推在列存中怎么实现?

频率 ★★★ | 难度 进阶

一句话结论

谓词下推把过滤条件下推到存储层,在读取数据时就过滤,减少扫描量;列存中按 Row Group 级别统计信息(min/max)跳过不满足条件的 Row Group。

概念解释

  • 谓词下推:过滤条件不在计算层执行,下推到存储层。
  • Row Group:列存文件按 Row Group 分块,每块有 min/max 统计信息。
  • 跳过不满足条件的 Row Group:WHERE date > '2026-01-01' 时,min/max 显示该 Row Group 全在 2025 年,直接跳过。

原理流程

  1. 查询 WHERE date > '2026-01-01' AND province = '广东'。
  2. 列存文件每个 Row Group 记录 date 列的 min/max。
  3. min/max < '2026-01-01' 的 Row Group 直接跳过,不读取。
  4. 读取的 Row Group 再按 province 过滤。

常见误区

  • 误区:谓词下推只在分布式执行中有。正解:单机列存扫描也有 Row Group 级裁剪。

追问延伸

  • 统计信息:写入时自动收集 min/max/null count。
  • 跳过率:EXPLAIN 看 skipped rows。

05.8.4-011 SIMD 和向量化执行的关系?

频率 ★★ | 难度 高级

一句话结论

向量化执行是按批处理数据的模型(减少函数调用开销),SIMD 是底层 CPU 指令(一条指令处理多个数据);向量化让 SIMD 能发挥作用。

概念解释

  • 向量化:一次处理一批行(如 1024 行),减少循环开销和函数调用。
  • SIMD:CPU 单指令多数据,一条指令处理 8 个 int 或 16 个 float。
  • 关系:向量化提供批处理数据,SIMD 加速批内计算。

原理流程

  1. 传统火山模型:逐行调用 next(),每行一次函数调用。
  2. 向量化:一次返回一批行(如 1024 行),批量计算。
  3. 批内计算用 SIMD:一条指令处理 8 个整数加法。

常见误区

  • 误区:向量化就是 SIMD。正解:向量化是执行模型,SIMD 是硬件指令;向量化不一定要 SIMD。

追问延伸

  • 向量化执行引擎:ClickHouse、Doris、Velox。
  • CPU 缓存:批处理数据在 L1/L2 缓存中,减少内存访问。

待整理清单

  • [ ] Parquet 与 ORC 编码细节对比
  • [ ] Bit slicing 与 SIMD 友好编码
  • [ ] ClickHouse/Doris 列存编码实现差异