数据库查询优化中的列存储压缩与向量化过滤（Columnar Storage Compression and Vectorized Filtering）技术
字数 3365 2025-12-12 19:52:31
数据库查询优化中的列存储压缩与向量化过滤（Columnar Storage Compression and Vectorized Filtering）技术
描述
列存储压缩与向量化过滤是现代分析型数据库（如ClickHouse、Snowflake、Amazon Redshift等）的核心优化技术，用于高效处理大规模数据分析查询。与传统的行式存储（Row-Based Storage， OLTP场景优化）不同，列式存储（Columnar Storage）将同一列的数据连续存储在磁盘上。这种存储方式天然适合压缩，并为向量化处理（一次处理一批数据，而不是一行）创造了条件。两者的结合，能极大减少I/O，提升CPU缓存利用率，并利用现代CPU的SIMD指令进行高效计算，从而在数据仓库和OLAP场景中获得几个数量级的性能提升。
解题过程/技术详解
我们将循序渐进地理解“列式存储为何高效压缩”、“如何压缩”以及“压缩后如何支持快速的向量化过滤”。
第一步：理解行式存储与列式存储的根本差异
假设我们有一个简单的订单表，结构如下：
| OrderID (int) |
CustomerID (int) |
ProductID (int) |
Quantity (int) |
OrderDate (date) |
| 1 |
101 |
1001 |
2 |
2023-10-01 |
| 2 |
102 |
1002 |
1 |
2023-10-01 |
| 3 |
101 |
1003 |
5 |
2023-10-02 |
| ... |
... |
... |
... |
... |
-
行式存储：在磁盘上，数据按行连续存放。即顺序存储：1, 101, 1001, 2, 2023-10-01, 2, 102, 1002, 1, 2023-10-01, 3, 101, 1003, 5, 2023-10-02, ...。
- 优点：插入/更新单行、点查询（通过主键查整行）效率高。
- 缺点：分析查询（如
SELECT SUM(Quantity) FROM orders WHERE OrderDate = ‘2023-10-01’）需要从磁盘读取整行数据（包括不需要的CustomerID, ProductID等），I/O效率低。同时，同一列的数据不连续，压缩效果差。
-
列式存储：在磁盘上，数据按列连续存放。即分别存储：
- OrderID列：
1, 2, 3, ...
- CustomerID列：
101, 102, 101, ...
- Quantity列：
2, 1, 5, ...
- OrderDate列：
2023-10-01, 2023-10-01, 2023-10-02, ...
- 优点：分析查询只需读取涉及的列（如Quantity和OrderDate），I/O量大幅减少。更重要的是，同一列的数据类型相同、值域相似，具有极高的数据局部性和重复性，这为高效压缩奠定了基础。
第二步：列式存储如何实现高效压缩
由于列中数据的同质性和局部性，可以采用针对性的压缩算法，大幅减少存储空间和处理时的内存带宽占用。常见压缩方法：
-
字典编码：
- 过程：扫描列中所有不同的值，为每个唯一值分配一个数字ID（通常是紧凑的整数，如0,1,2,...），形成“字典”。然后用这个紧凑的ID序列替换原始数据列。
- 例子：CustomerID列有
101, 102, 101, ...。字典：{101:0, 102:1}。编码后列变为0, 1, 0, ...。存储空间从多个int变为多个tinyint或smallint。
- 优势：重复值越多，压缩比越高。且过滤、分组、聚合操作可以直接在编码后的ID上进行，速度更快。
-
行程长度编码：
- 过程：将连续重复的值压缩为
(值, 连续出现次数)对。
- 例子：OrderDate列经过排序后可能是
2023-10-01, 2023-10-01, 2023-10-01, 2023-10-02, ...。编码为(2023-10-01, 3), (2023-10-02, 1), ...。
- 优势：对排序列或低基数列（如状态、类型）压缩效果极好，并能加速范围查询。
-
位图编码：
- 过程：针对低基数列（如性别、布尔值），为每个可能的值创建一个位图（bitmap）。位图的每一位对应一行，如果该行是这个值，则位为1，否则为0。
- 例子：
ProductID值不多时，可以为每个ProductID建立一个位图。过滤ProductID=1001时，直接读取1001对应的位图即可。
- 优势：非常适合多条件过滤（通过位图AND/OR操作）和基数计算。
-
增量编码/帧间压缩：
- 过程：存储相邻数据的差值，而不是原始值。对有序的数值列（如自增ID、时间戳）特别有效。
- 例子：
OrderID: 1, 2, 3, 5, 8 ... 编码为 1, 1, 1, 2, 3, ...（差值）。
- 优势：差值通常更小，可以用更少的比特存储。
第三步：向量化过滤——如何高效处理压缩后的列数据
传统的“火山模型”（一次处理一行）在列存储中效率低下，因为每处理一行都要调用大量虚函数，CPU分支预测开销大。向量化执行模型解决了这个问题。
- 核心思想：以列为单位，一次处理一批数据（例如1024行），这批数据称为一个“向量”（Vector）或“批次”（Batch）。
- 工作流程（以查询
SELECT SUM(Quantity) FROM orders WHERE OrderDate = ‘2023-10-01’ 为例）：
a. 向量化读取：从磁盘读取OrderDate列的一个数据块（通常是压缩的），在内存中解压成一个OrderDate向量（包含连续的多行日期值）。
b. 向量化过滤：CPU将OrderDate向量中的每个元素与常量‘2023-10-01’进行比较。这个比较操作是在一个紧密循环中对整个向量进行的，没有每行的函数调用开销。比较结果生成一个“选择向量”（Selection Vector）或位图（Bitmap），标记哪些行的条件为真。
c. 向量化聚合：根据上一步生成的选择向量，去Quantity列对应的向量中，只选取那些满足条件的行对应的Quantity值，加载到CPU寄存器。然后，使用SIMD指令（如AVX2, AVX-512），一次性对多个值（如8个32位整数）执行加法，从而加速SUM计算。
d. 循环处理：处理完一个批次后，移动到下一个批次的数据，重复上述过程，直到所有数据处理完毕。
第四步：技术协同与优势总结
-
压缩 + 向量化 = 极致性能：
- 减少I/O：压缩使从磁盘读取的数据量减少。
- 减少内存带宽：在内存中传递的数据也是压缩的，直到需要计算时才解压。
- 提升CPU缓存效率：列式数据和向量化处理让CPU一次加载和处理的是连续的同类型数据，非常适合CPU的缓存行和预取器，缓存命中率极高。
- 利用SIMD：向量化的连续数据布局是使用SIMD指令集进行并行计算的前提。一条SIMD指令可以同时完成多个数据的比较或算术运算，将性能提升数倍。
-
适用场景：
- 最适合：数据仓库、大数据分析、OLAP场景，查询涉及大量数据的扫描、过滤、聚合，但只访问部分列。
- 不适用：频繁单行插入/更新、点查询为主的OLTP场景，因为列修改会涉及多个文件，写入开销大。
总结
列存储压缩与向量化过滤是一个“组合拳”。列式存储改变了数据的物理布局，使其具备高压缩潜力；针对性的列压缩算法大幅降低了存储和I/O开销；向量化处理改变了数据的计算模型，使其能够充分利用现代CPU的缓存、流水线和SIMD并行能力。这三者环环相扣，共同构成了现代分析型数据库查询性能飞跃的核心基石。
数据库查询优化中的列存储压缩与向量化过滤（Columnar Storage Compression and Vectorized Filtering）技术 描述 列存储压缩与向量化过滤是现代分析型数据库（如ClickHouse、Snowflake、Amazon Redshift等）的核心优化技术，用于高效处理大规模数据分析查询。与传统的行式存储（Row-Based Storage， OLTP场景优化）不同，列式存储（Columnar Storage）将同一列的数据连续存储在磁盘上。这种存储方式天然适合压缩，并为向量化处理（一次处理一批数据，而不是一行）创造了条件。两者的结合，能极大减少I/O，提升CPU缓存利用率，并利用现代CPU的SIMD指令进行高效计算，从而在数据仓库和OLAP场景中获得几个数量级的性能提升。 解题过程/技术详解 我们将循序渐进地理解“列式存储为何高效压缩”、“如何压缩”以及“压缩后如何支持快速的向量化过滤”。 第一步：理解行式存储与列式存储的根本差异 假设我们有一个简单的订单表，结构如下： | OrderID (int) | CustomerID (int) | ProductID (int) | Quantity (int) | OrderDate (date) | |----------------|-------------------|-----------------|----------------|------------------| | 1 | 101 | 1001 | 2 | 2023-10-01 | | 2 | 102 | 1002 | 1 | 2023-10-01 | | 3 | 101 | 1003 | 5 | 2023-10-02 | | ... | ... | ... | ... | ... | 行式存储 ：在磁盘上，数据按 行 连续存放。即顺序存储： 1, 101, 1001, 2, 2023-10-01, 2, 102, 1002, 1, 2023-10-01, 3, 101, 1003, 5, 2023-10-02, ... 。 优点 ：插入/更新单行、点查询（通过主键查整行）效率高。 缺点 ：分析查询（如 SELECT SUM(Quantity) FROM orders WHERE OrderDate = ‘2023-10-01’ ）需要从磁盘读取 整行数据 （包括不需要的CustomerID, ProductID等），I/O效率低。同时，同一列的数据不连续，压缩效果差。 列式存储 ：在磁盘上，数据按 列 连续存放。即分别存储： OrderID列： 1, 2, 3, ... CustomerID列： 101, 102, 101, ... Quantity列： 2, 1, 5, ... OrderDate列： 2023-10-01, 2023-10-01, 2023-10-02, ... 优点 ：分析查询只需读取涉及的列（如Quantity和OrderDate），I/O量大幅减少。更重要的是， 同一列的数据类型相同、值域相似，具有极高的数据局部性和重复性 ，这为高效压缩奠定了基础。 第二步：列式存储如何实现高效压缩 由于列中数据的同质性和局部性，可以采用针对性的压缩算法，大幅减少存储空间和处理时的内存带宽占用。常见压缩方法： 字典编码 ： 过程 ：扫描列中所有不同的值，为每个唯一值分配一个数字ID（通常是紧凑的整数，如0,1,2,...），形成“字典”。然后用这个紧凑的ID序列替换原始数据列。 例子 ：CustomerID列有 101, 102, 101, ... 。字典： {101:0, 102:1} 。编码后列变为 0, 1, 0, ... 。存储空间从多个int变为多个tinyint或smallint。 优势 ：重复值越多，压缩比越高。且过滤、分组、聚合操作可以直接在编码后的ID上进行，速度更快。 行程长度编码 ： 过程 ：将连续重复的值压缩为 (值, 连续出现次数) 对。 例子 ：OrderDate列经过排序后可能是 2023-10-01, 2023-10-01, 2023-10-01, 2023-10-02, ... 。编码为 (2023-10-01, 3), (2023-10-02, 1), ... 。 优势 ：对排序列或低基数列（如状态、类型）压缩效果极好，并能加速范围查询。 位图编码 ： 过程 ：针对低基数列（如性别、布尔值），为每个可能的值创建一个位图（bitmap）。位图的每一位对应一行，如果该行是这个值，则位为1，否则为0。 例子 ： ProductID 值不多时，可以为每个ProductID建立一个位图。过滤 ProductID=1001 时，直接读取1001对应的位图即可。 优势 ：非常适合多条件过滤（通过位图AND/OR操作）和基数计算。 增量编码/帧间压缩 ： 过程 ：存储相邻数据的差值，而不是原始值。对有序的数值列（如自增ID、时间戳）特别有效。 例子 ： OrderID: 1, 2, 3, 5, 8 ... 编码为 1, 1, 1, 2, 3, ... （差值）。 优势 ：差值通常更小，可以用更少的比特存储。 第三步：向量化过滤——如何高效处理压缩后的列数据 传统的“火山模型”（一次处理一行）在列存储中效率低下，因为每处理一行都要调用大量虚函数，CPU分支预测开销大。向量化执行模型解决了这个问题。 核心思想 ： 以列为单位，一次处理一批数据 （例如1024行），这批数据称为一个“向量”（Vector）或“批次”（Batch）。 工作流程 （以查询 SELECT SUM(Quantity) FROM orders WHERE OrderDate = ‘2023-10-01’ 为例）： a. 向量化读取 ：从磁盘读取 OrderDate 列的一个数据块（通常是压缩的），在内存中 解压 成一个 OrderDate向量 （包含连续的多行日期值）。 b. 向量化过滤 ：CPU将 OrderDate向量 中的每个元素与常量 ‘2023-10-01’ 进行比较。这个比较操作是 在一个紧密循环中对整个向量进行的 ，没有每行的函数调用开销。比较结果生成一个“选择向量”（Selection Vector）或位图（Bitmap），标记哪些行的条件为真。 c. 向量化聚合 ：根据上一步生成的选择向量，去 Quantity 列对应的向量中， 只选取 那些满足条件的行对应的 Quantity 值，加载到CPU寄存器。然后， 使用SIMD指令 （如AVX2, AVX-512），一次性对多个值（如8个32位整数）执行加法，从而加速SUM计算。 d. 循环处理 ：处理完一个批次后，移动到下一个批次的数据，重复上述过程，直到所有数据处理完毕。 第四步：技术协同与优势总结 压缩 + 向量化 = 极致性能 ： 减少I/O ：压缩使从磁盘读取的数据量减少。 减少内存带宽 ：在内存中传递的数据也是压缩的，直到需要计算时才解压。 提升CPU缓存效率 ：列式数据和向量化处理让CPU一次加载和处理的是连续的同类型数据，非常适合CPU的缓存行和预取器，缓存命中率极高。 利用SIMD ：向量化的连续数据布局是使用SIMD指令集进行并行计算的前提。一条SIMD指令可以同时完成多个数据的比较或算术运算，将性能提升数倍。 适用场景 ： 最适合 ：数据仓库、大数据分析、OLAP场景，查询涉及大量数据的扫描、过滤、聚合，但只访问部分列。 不适用 ：频繁单行插入/更新、点查询为主的OLTP场景，因为列修改会涉及多个文件，写入开销大。 总结 列存储压缩与向量化过滤是一个“组合拳”。 列式存储 改变了数据的物理布局，使其具备 高压缩潜力 ；针对性的 列压缩算法 大幅降低了存储和I/O开销； 向量化处理 改变了数据的计算模型，使其能够充分利用现代CPU的 缓存、流水线和SIMD并行能力 。这三者环环相扣，共同构成了现代分析型数据库查询性能飞跃的核心基石。
