元数据卡
维度 值 难度 （黑魔法） 前置 第9章 查询编译、C/C++ 数组与循环基础知识 关键词 SIMD、AVX2、AVX-512、向量化执行、列存、ClickHouse、DuckDB、延迟物化 代码语言 C++（主）/ Pseudocode（算法原理）
你的进度
堡垒的仓库里有一条新流水线。不像人工一件件搬运货物，它一次抓起一整排——处理 4 个、8 个、16 个箱子。这就是 SIMD（单指令多数据）。在数据分析型仓库（OLAP）里，它特别有用，因为你经常需要给整列数据做同样的操作。
破局 · 溯源
1. SIMD 基础：一个指令，多个数据
普通工人一次只搬一个箱子：
// 标量（SISD）：一次处理一个
for (int i = 0; i < N; i++) {
C[i] = A[i] + B[i];
}一条 CPU 指令（比如 add）做两个整数加法，出一个结果。
SIMD 工人不一样——他一次处理多个：
标量（SISD）： 向量（SIMD）：
1 1 2 3 4 ← 操作数 A
+ + + + + ← 一条指令
5 5 6 7 8 ← 结果一次能搬多少，看 CPU 的 SIMD 寄存器的宽度：
指令集 | 寄存器宽度 | 一次可处理
MMX | 64-bit | 2 个 int32
SSE/SSE2 | 128-bit | 4 个 float / 2 个 double
AVX/AVX2 | 256-bit | 8 个 float / 4 个 double
AVX-512 | 512-bit | 16 个 float / 8 个 double
SVE (ARM) | 可变 | 128-2048-bit 可伸缩用 AVX2 做一次加法，C++ 里这么写：
#include <immintrin.h> // Intel Intrinsics
void vector_add_avx2(float* a float* b float* c int n) {
// 每次处理 8 个 float (256-bit / 32-bit = 8)
for (int i = 0; i < n; i += 8) {
__m256 va = _mm256_loadu_ps(&a[i]); // 加载 8 个 float
__m256 vb = _mm256_loadu_ps(&b[i]); // 加载 8 个 float
__m256 vc = _mm256_add_ps(va vb); // 一条指令完成 8 个加法
_mm256_storeu_ps(&c[i] vc); // 存回内存
}
// 处理剩余元素（不能整除 8 时）
for (int i = n - n % 8; i < n; i++) {
c[i] = a[i] + b[i];
}
}注意对齐： SIMD 加载/存储指令对地址对齐很敏感。_mm256_load_ps 要求 32 字节对齐，不对齐直接 SIGSEGV。_mm256_loadu_ps（带 u 表示 unaligned）允许不对齐但可能慢一点。堡垒里的数据库在分配缓冲池时通常会确保对齐。
2. 为什么 OLAP 查询适合 SIMD
堡垒门口的告示板查一个人的信息——一次取一行，条件窄，返回少。
-- OLTP：查一个冒险者的信息
SELECT * FROM adventurers WHERE adventurer_id = 42;
-- 返回：1 行这种查询总共就遍历那么几行，SIMD 没用——你都没有足够数据让它一次处理 8 个。
但账房先生要做年度统计——情况就反过来了：
-- OLAP：分析一年的宝物价值
SELECT
EXTRACT(MONTH FROM discovered_at) AS month
SUM(value)
COUNT(*)
AVG(value)
FROM vault_items
WHERE discovered_at >= '2024-01-01'
AND discovered_at < '2025-01-01'
AND item_type IN ('Gemstone' 'Artifact')
GROUP BY month;这个查询可能要处理 1 亿行的 vault_items 表，但只读 3 列（discovered_at、value、item_type）。当数据以列存格式存储时，这三列在内存里是三块连续的长条。
连续的内存 + 大规模数据 + 少量列 + 同样的计算逻辑反复执行 = SIMD 的盛宴。
列存布局（示意图，一列 8 个 int32）：
discovered_at: [2024-01-01 | 2024-01-01 | 2024-01-02 | ...] ← 连续内存
value: [ 120.50 | 230.00 | 45.00 | ...] ← 连续内存
item_type: [Gemstone | Artifact | Weapon | ...] ← 连续内存
一列 1 亿个 float = 400MB 连续内存
一次 _mm256_loadu_ps 加载 8 个 = 32 bytes 约 2ns
标量加载 8 个 float ≈ 8 × 0.5ns = 4ns（且多 7 次指令解码）保守估计 SIMD 版本比标量版本快 2-4 倍，理想情况下可达 8 倍（理论峰值取决于数据宽度）。
3. 向量化执行模型
在堡垒数据库引擎层面，向量化不直接调 _mm256_add_ps——它体现在更高层的架构：一次处理一批数据，不是一行。
向量大小：一批搬多少
经典的向量化引擎用 1024 作为默认向量大小——MonetDB/X100 的传统，ClickHouse 也沿用了。
// 火山模型：一次返回一行
class VolcanoExecutor {
Tuple* next(); // 一次一行
};
// 向量化模型：一次返回一批
class VectorizedExecutor {
// 一次返回一个向量（比如 1024 行）
// 用 Vector 对象包装批数据，而不是逐行 Tuple
Vector* next_vector();
};实际的向量结构（简化）：
// ClickHouse-style 向量（简化）
struct ColumnVector {
size_t size; // 当前向量中的行数（一般 ≤ 1024）
void* data; // 列数据的连续数组
uint8_t* null_map; // 空值位图（可选）
};
struct Vector { // 相当于一行
std::vector<ColumnVector*> columns; // 多列
};向量化执行的一个完整例子
账房先生要做的事：
SELECT SUM(value) FROM vault_items WHERE item_type = 'Gemstone';向量化执行的过程是这样的：
Step 1: 扫描 item_type 列，一次读 1024 个字符串/枚举值
→ 生成一个 mask：[1 0 1 1 0 ...] 满足条件的位置标记为 1
Step 2: 用 mask 从 value 列中过滤
→ 根据 mask 从 value 数组中收集符合条件的 value 值
→ 生成一个 "压缩" 后的连续数组 [value_1 value_3 value_4 ...]
Step 3: 对这个数组做向量化 SUM
→ 每 8 个一组用 AVX2 加法指令累加每个步骤里，数据都以 batch 流动，不是一行一行。好处有三：
- 分摊函数调用开销：1024 行只要一次
next_vector()调用 - 利用缓存局部性：一列数据在内存中连续，CPU 缓存友好
- 编译器自动向量化：很多情况下，简单的
for循环，加上-O2 -mavx2，编译器自己就生成 SIMD 指令了
4. ClickHouse 的向量化实践
ClickHouse 可能是向量化执行上走得最彻底的开源系统。它的口号：the fastest database for real-time analytics。
向量在哪里？
ClickHouse 几乎所有执行单元都在跟 Block 打交道——Block 就是一组 ColumnVector：
// ClickHouse 核心数据结构
// Block ≈ 一组同长度的列
// 每列用一个 IColumn 表示
class IColumn {
public:
virtual size_t size() const = 0;
virtual void insertFrom(const IColumn& src size_t n) = 0;
// ... 所有操作都是对"一批"数据
};
class ColumnVector : public IColumn {
PaddedPODArray<UInt64> data; // 连续对齐的数组
};所有算子都操作 Block，不碰 Tuple：
// FireFilterTransform（过滤操作）
Block FireFilterTransform::transform(const Block& block) {
// block 包含两列：item_type (ColumnString) value (ColumnUInt32)
ColumnPtr type_col = block.getByName("item_type").column;
ColumnPtr value_col = block.getByName("value").column;
// 生成 filter mask
IColumn::Filter mask(type_col->size() 0);
type_col->compareEqual("Gemstone" mask); // 向量化比较
// 按 mask 过滤 value 列
auto filtered = value_col->filter(mask -1);
return Block{{filtered}};
}延迟物化（Late Materialization）
ClickHouse 的一个核心理念：别急着把列拼成行。
早物化（不好的做法）：过滤前就把三列拼成行，白费了列存的带宽优势。
延迟物化（好的做法）：
1. 先只读过滤用的列（item_type）
2. 拿到过滤后的行号
3. 用行号去读其他需要的列（value name）
4. 最后才拼成完整行延迟物化的好处：
item_type value name
列 1 列 2 列 3
Filter ← 只需要这一列
mask
value name
过滤后子集 过滤后子集
物化成行 ← 最后一步才拼这一步在行存引擎里完全没机会——你得读完整的一行才能碰到某一列。列存 + 向量化 + 延迟物化，三件事必须一起做。
ClickHouse 的 SIMD 实战
ClickHouse 用了大量 SIMD，但大部分不是手写的——靠编译器自动生成：
// ClickHouse 中常见的模式（SUM 的实现核心）
// 它用循环展开 + 编译器 SIMD 自动矢量化
UInt64 accumulate(const UInt64* data size_t size) {
// 编译器带 -O2 -mavx2 会把这段自动向量化
UInt64 sum = 0;
for (size_t i = 0; i < size; i++) {
sum += data[i];
}
return sum;
}
// 部分热点路径也会手写 SIMD（如哈希计算）：
// 用 _mm_crc32_u64 硬件 CRC 加速哈希ClickHouse 的代码库中，很多地方并不直接用 Intel Intrinsics——而是依赖编译器（Clang）的自动向量化。代价是必须用 Clang 编译（GCC 的自动向量化能力弱一些）。
5. DuckDB 的向量化引擎
DuckDB 走了另一条路，但效果类似。它的核心是 DataChunk——相当于 ClickHouse 的 Block：
// DuckDB 的核心数据结构
struct DataChunk {
vector<Vector> data; // 向量数组
idx_t size; // chunk 当前大小（default: STANDARD_VECTOR_SIZE=2048）
void SetCardinality(idx_t size);
void Normalify(); // 确保数据连续
};
struct Vector {
VectorType type; // 存储格式：FLAT/DICTIONARY/CONSTANT/SEQUENCE
vector_buffer_t buffer; // 数据或引用
};注意 DuckDB 的 Vector 有多种类型：FLAT（常规扁平数组）、DICTIONARY（字典编码）、CONSTANT（所有值相同）、SEQUENCE（等差序列）。这些类型在某些阶段直接省掉了计算。
// DuckDB 的 Filter 执行（概念）
struct FilterState {
SelectionVector sel; // 满足条件的行索引
idx_t count;
};
void FilterExecute(Vector& input Vector& result FilterState& state) {
switch (input.type) {
case VectorType::CONSTANT:
// 所有值相同，只需判断一次
if (MatchesCondition(input.GetValue(0))) {
result.Reference(input); // 直接引用，不拷贝
state.count = 1;
}
break;
case VectorType::FLAT:
// 扁平数组，走向量化过滤
FilterFlat(input result state);
break;
// ...
}
}DuckDB 通过多态的向量类型偷了很多懒——如果一整列都是同一个值（GROUP BY 场景里的常数列很常见），它直接跳过逐行处理。
与 ClickHouse 的对比
| 维度 | ClickHouse | DuckDB |
|---|---|---|
| 向量大小 | 1024 | 2048 |
| SIMD 策略 | 主要靠编译器自动向量化 + 手写热点 | 也靠编译器，但更偏重在架构层面避免不必要的计算 |
| 延迟物化 | 非常激进（整卷都是延迟物化） | 有限度的延迟物化（更多靠向量类型优化） |
| 存储格式 | 自研列存（MergeTree） | 行存为主（可加载列存文件如 Parquet） |
| 运行时 | C++ 原生，OLAP 场景极致优化 | 嵌入式友好，OLAP 场景强但更通用 |
6. 常见 SIMD 操作
不管哪种引擎，向量化执行最终落到几个固定模式。
过滤 Mask
// 输入：一列 int32 value 值
// 输出：一个 mask 标记 value > 50000 的位置
// 标量版本：
for (int i = 0; i < N; i++) {
mask[i] = (value[i] > 50000);
}
// AVX2 向量化版本：
for (int i = 0; i < N; i += 8) {
__m256i v_value = _mm256_loadu_si256((__m256i*)&value[i]);
__m256i v_threshold = _mm256_set1_epi32(50000);
__m256i v_mask = _mm256_cmpgt_epi32(v_value v_threshold);
// v_mask 中每个元素是 0 或 0xFFFFFFFF
_mm256_storeu_si256((__m256i*)&mask[i] v_mask);
}得到 mask 后要"收集"（gather）符合条件的元素：
// gather：从连续数组中收集满足条件的元素
// 输入：data[N] mask[N]（0/1）
// 输出：compacted[M]（只包含 mask=1 的元素）
// 标量版本：
int j = 0;
for (int i = 0; i < N; i++) {
if (mask[i]) compacted[j++] = data[i];
}
// AVX2 compress store（AVX-512 中有直接的 VPCOMPRESS 指令）
// AVX2 需要用 permute 组合：
// 1. 用 mask 做 _mm256_maskload_ps 加载
// 2. 用 _mm256_permutevar8x32_ps 做压缩填充聚合（Sum / Avg / Min / Max）
SUM 是最简单的 SIMD 场景：
// 标量：
float sum = 0;
for (int i = 0; i < N; i++) sum += data[i];
// AVX2 向量化：
__m256 v_sum = _mm256_setzero_ps();
for (int i = 0; i < N; i += 8) {
__m256 v_data = _mm256_loadu_ps(&data[i]);
v_sum = _mm256_add_ps(v_sum v_data);
}
// 最后将 v_sum 中的 8 个 float 水平归约：
// 方法：把高 128 位和低 128 位相加，再用 extract/hadd 继续归约
float result[8];
_mm256_storeu_ps(result v_sum);
float total = result[0] + result[1] + result[2] + result[3]
+ result[4] + result[5] + result[6] + result[7];MIN/MAX 类似，用 _mm256_min_ps / _mm256_max_ps。
但 SIMD 做聚合有一个微妙的陷阱：
标量累加：浮点数加法顺序确定（从左到右）
SIMD 累加：8 条独立的累加链，最后水平归约
导致浮点加法的顺序与标量不同
→ 可能出现舍入误差差异对于要求确定性的应用，必须用标量加法或者保证最终的顺序一致性。
哈希
哈希在很多数据库的 GROUP BY、JOIN、DISTINCT 中高频出现，向量化哈希就是干这个的。
// 标量哈希：
for (int i = 0; i < N; i++) {
hashes[i] = hash_function(keys[i]);
}
// 向量化哈希：
// 用硬件 CRC 指令（SSE 4.2 的 _mm_crc32_u64）加速
for (int i = 0; i < N; i++) {
// 一条指令完成：数据加载 + 哈希累加
uint64_t h = _mm_crc32_u64(0 keys[i]);
hashes[i] = h;
}Intel 的哈希加速核心其实是 CRC 指令——不提供完整的加密级哈希，但对哈希表够用了。ClickHouse 和 DuckDB 都用这个套路加速 GROUP BY。
深入冒险
向量化哈希表的碰撞处理
哈希表在 SIMD 加速下遇到一个瓶颈：探测时一次加载一批哈希槽，比较 8 个槽的 key。
// 简化版的向量化哈希探针（线性探测）
// 假设每个 slot 是 (uint64_t hash uint64_t key Value value)
void probe(__m256i probe_hash HashTable& ht) {
int slot = probe_hash & ht.mask;
// 一次加载 8 个相邻 slot 的哈希值
__m256i v_slot_hashes = _mm256_loadu_si256(
(__m256i*)&ht.slots[slot].hash
);
// 与 probe_hash 比较（广播成 8 份）
__m256i v_result = _mm256_cmpeq_epi64(v_slot_hashes probe_hash);
int mask = _mm256_movemask_pd(_mm256_castsi256_pd(v_result));
// mask 的每个 bit 表示对应位置是否匹配
}如果匹配到了多个槽，再逐一确认精确 key（哈希可能冲突）。做得更极端的引擎比如 Umbra，会为哈希表设计 SIMD 友好的布局——slot 按 cache line 对齐，减少伪共享。
编译器自动向量化的局限
你其实不需要手写 _mm256_add_ps——现代编译器（Clang / GCC）可以自动把简单循环向量化。但有些情况编译器就没办法了：
// 编译器不能自动向量化：
for (int i = 0; i < N; i++) {
result[data[i].index] += data[i].value; // 间接访问（可能别名）
}
for (int i = 0; i < N; i++) {
if (data[i] < 0) { // 条件分支打断向量化
data[i] = 0;
}
}
// 编译器可以自动向量化：
for (int i = 0; i < N; i++) {
result[i] = data[i] + bias; // 连续、无分支、无间接
}
for (int i = 0; i < N; i++) {
// 三元表达式可能会被编译为 blendv 指令
data[i] = (data[i] < 0) ? 0 : data[i];
}DuckDB 和 ClickHouse 都把核心循环刻意简化，让编译器更容易自动向量化。手动 SIMD 只留给编译器搞不定的部分，比如哈希表的 gather 操作。
常见陷阱
陷阱 1：SIMD 不是万能的
SIMD 加速的前提是大量的同质数据。下面这些场景 SIMD 不好使：
- OLTP 短查询——数据太少
- 字符串操作——长度不固定，对不齐
- 递归计算——每个结果依赖前一个
陷阱 2：用 SIMD 一定比标量快
不一定。几个原因：
- 数据对齐：不对齐的加载可能比标量还慢（尤其旧 CPU 上）
- 数据搬运开销：把数据装进 SIMD 寄存器、取出来，都有成本
- 剩余元素处理：不能整除向量宽度时，尾循环需要额外处理
- 热身效应：第一次用 SIMD 指令，CPU 要打开向量单元的电源门控，额外耗几个微秒
// 对极短的数组（n < 8），SIMD 版本反而不如标量
// SIMD 版：load(8) + add(1) + store(8) = 赋存 17 个元素
// 标量版：load(4) + add(4) + store(4) = 也差不多，甚至因更少的指令解码而更快陷阱 3：浮点数聚合的舍入差异
如前面提到的，SIMD 的并行累加链和水平归约会让浮点结果跟标量顺序累加有差异。如果你的应用要求严格确定（比如金融计算），需要注意。
// 标量累加：
10.0 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 = 10.999999
// SIMD 累加（8 个并行链最后水平归约）：
// 链1: 10.0 + 0.1 + 0.1 = ...
// 结果可能略有不同陷阱 4：SSE vs AVX 的切换开销
在同一个函数中混合使用 SSE 和 AVX 指令会导致 CPU 的状态切换惩罚（称为"transition penalty"）。现代 Intel CPU 在 SSE 和 AVX 指令之间切换时，会等待所有正在执行的 AVX 指令退役，然后再启用 SSE 模式——代价可高达 50-70 个周期。
// 混合使用：
__m128 sse_val = _mm_load_ss(&a); // SSE 指令
__m256 avx_val = _mm256_loadu_ps(&b); // AVX 指令，第一次触发切换惩罚
// 全用 AVX（如果 CPU 支持）
__m256 avx_a = _mm256_broadcast_ss(&a); // 用 AVX 指令替代 SSE
__m256 avx_val = _mm256_loadu_ps(&b);通关挑战
- 热身：在一台 CPU 上检查它支持的 SIMD 指令集（Linux:
cat /proc/cpuinfo | grep flags找avx2/avx512f; macOS:sysctl -a | grep machdep.cpu.features） - 挑战：写一个 C++ 小程序，对比标量 vs AVX2 的数组求和性能（N=10^8 float 数组，分别计时标量循环和 SIMD 归约）
// 示例框架
#include <immintrin.h>
#include <chrono>
#include <iostream>
int main() {
const int N = 100000000;
float* data = (float*)aligned_alloc(32 N * sizeof(float));
// 初始化 data...
// 标量求和
auto t1 = std::chrono::steady_clock::now();
float sum_scalar = 0;
for (int i = 0; i < N; i++) sum_scalar += data[i];
auto t2 = std::chrono::steady_clock::now();
// SIMD 求和
auto t3 = std::chrono::steady_clock::now();
__m256 v_sum = _mm256_setzero_ps();
for (int i = 0; i < N; i += 8) {
v_sum = _mm256_add_ps(v_sum _mm256_load_ps(&data[i]));
}
float sum_simd[8];
_mm256_storeu_ps(sum_simd v_sum);
float simd_result = sum_simd[0]+sum_simd[1]+sum_simd[2]+sum_simd[3]
+ sum_simd[4]+sum_simd[5]+sum_simd[6]+sum_simd[7];
auto t4 = std::chrono::steady_clock::now();
std::cout << "标量: " << (t2-t1).count()/1e6 << "ms\n";
std::cout << "SIMD: " << (t4-t3).count()/1e6 << "ms\n";
free(data);
}- 观察：用 ClickHouse 跑一个 COUNT/SUM 查询，对比 DuckDB 或 PostgreSQL 的同一查询，观察延迟和吞吐差异
验收标准
- 能用自己的话解释 SIMD 的核心思想（一条指令处理多个数据元素）
- 能说明为什么 OLAP 查询比 OLTP 更适合向量化
- 理解向量化执行模型中的 "vector/batch" 概念（区别于火山模型的逐行处理）
- 知道 ClickHouse 和 DuckDB 向量化设计的异同
- 能解释延迟物化的概念及其与向量化的协同关系
常见卡点
| 卡点 | 原因 |
|---|---|
| 认为向量化等于手写 SIMD intrinsics | 大部分向量化执行引擎依赖编译器自动向量化，手写只用于特定热点 |
| 觉得向量化对任何查询都有用 | OLTP 场景没意义；字符串高比例查询也没意义 |
| 混淆向量化执行（batch 处理）和指令级 SIMD | 上层 batch 处理是架构设计，下层 SIMD 是 CPU 指令利用：两者独立但协同 |
| 认为延迟物化是向量化独有的 | 任何列存引擎都可以延迟物化，但向量化执行让它收益更明显 |
现在不需要理解
- 具体的 AVX-512 指令集细节（512-bit 宽度、mask register）
- ClickHouse MergeTree 引擎的粒度压缩细节
- 跨平台 SIMD 抽象层（Google Highway、SIMDe 等）
- GPU 加速的查询执行（与 CPU SIMD 是不同的优化路径）
旅人笔记
向量化执行的核心不是某条 CPU 指令，而是一种数据驱动的大局观：当你处理的是整列数据而不是单行时，把所有同质的计算挤进 CPU 的宽通道，一次做完。SIMD 是这条思路在指令级的落地，batch processing 和延迟物化是架构级的落地。