用 Rust 从零实现向量化执行引擎:SQL 为什么快在批量
上一篇实现了列式存储,把数据按列存好了。但**"怎么算"还没有解决**——把一列 10 万个值加起来,有很多种写法,性能可能差 10 倍。
现代分析型数据库(DuckDB、ClickHouse、Snowflake)都用向量化执行。它的核心思想不复杂:不逐行处理,而是一批一批处理。
这篇从零实现一个向量化执行引擎,并说清楚它到底快在哪。
先看逐行解释执行的问题
一个朴素的 SQL 引擎,每个算子是一个 next() 方法:
trait RowIterator {
/// 返回下一行;None 表示结束
fn next(&mut self) -> Option<Row>;
}
struct Filter {
input: Box<dyn RowIterator>,
predicate: Expr,
}
impl RowIterator for Filter {
fn next(&mut self) -> Option<Row> {
loop {
let row = self.input.next()?;
if self.predicate.eval(&row) {
return Some(row);
}
}
}
}每个 next() 调用要处理一行。 问题有三个:
1. 每行一次虚函数调用。 self.input.next() 是动态分发,无法内联。
2. 每行要判断一次类型。 predicate.eval 内部要 match 表达式的类型,这个分支每行做一次。
3. 无法自动向量化。 编译器只能看到"每次处理一个值",它没法把循环展开成 SIMD 指令,因为迭代次数不固定(next() 返回 None 的时机不可预测)。
逐行执行最大的损失不是函数调用开销,而是"编译器无法优化"。 现代编译器对"固定长度的批量循环"能做向量化,但对"每次可能提前退出的单行处理"做不到。
向量化的核心:批量 + 选择向量
向量化执行把接口改成"一次处理一批":
pub const BATCH_SIZE: usize = 2048;
pub trait VectorizedOperator {
/// 返回下一批数据;is_empty 表示结束
fn next_batch(&mut self) -> Batch;
}
pub struct Batch {
/// 每列一个向量
columns: Vec<Column>,
/// 有效行数
len: usize,
}BATCH_SIZE = 2048 是个经验值。
- 太小(比如 16):每批的调度开销占比高,向量化收益不足
- 太大(比如 100 万):超出 CPU 缓存,批量处理反而变慢
2048 行 × 8 字节 = 16KB,正好能放进 L1/L2 缓存。
列的数据结构
#[derive(Debug, Clone)]
pub enum Column {
I64(Vec<i64>),
F64(Vec<f64>),
/// 字符串用"字典编码 + 码数组"表示(承接上一篇)
Str { dict: Vec<String>, codes: Vec<u32> },
Bool(Vec<u8>),
}字符串列用字典编码的码数组——这样比较、分组、哈希都在整数上做,速度快很多。
还有一个关键设计:用 null 位图而不是 Option。
pub struct ColumnData<T> {
values: Vec<T>,
/// 每个值的有效性
validity: Option<Bitmap>,
len: usize,
}为什么不用 Vec<Option<T>>? 因为 Option<i64> 是 16 字节(要额外存判别式),而 Vec<i64> + 位图是 8 字节 + 1 bit。内存少一半,缓存命中率翻倍。
而且位图可以直接做位运算——valid AND predicate_result 一次 64 位。
算子一:向量化过滤
关键武器是选择向量(selection vector):
pub struct SelectionVector {
/// 被选中的行号
indices: Vec<u32>,
}过滤不再是"生成新的一批值",而是"生成一批下标":
impl FilterOp {
pub fn next_batch(&mut self) -> Batch {
loop {
let input = self.input.next_batch();
if input.is_empty() {
return Batch::empty();
}
// 对整批求谓词,得到一个位图
let mask = self.predicate.eval_mask(&input);
// 收集所有 true 的位置
let mut selection = Vec::new();
for i in 0..input.len {
if mask.get(i) {
selection.push(i as u32);
}
}
if selection.is_empty() {
continue; // 这批全被过滤掉了,取下一批
}
return input.select(&selection);
}
}
}两个关键收益:
- 谓词求值是对整个向量做的,可以按 64 位一组处理,编译器能生成 SIMD 指令
- 不需要"复制"数据——
select只是记录下标,所有算子共享同一份底层数据(这叫 late materialization,延迟物化)
eval_mask 的实现是优化的核心:
impl Expr {
/// 对整个向量求值,返回位图
pub fn eval_mask(&self, batch: &Batch) -> Bitmap {
match self {
Expr::Column(idx) => {
// 直接返回这一列的 validity
batch.columns[*idx].validity()
}
Expr::Eq(col, value) => {
let column = &batch.columns[*col];
match column {
Column::I64(values) => {
let mut mask = Bitmap::new(values.len());
// 这个循环会被编译器向量化
for (i, &v) in values.iter().enumerate() {
if v == *value {
mask.set(i);
}
}
mask
}
_ => todo!(),
}
}
}
}
}为什么这个循环能被向量化? 因为:
- 迭代次数在编译期已知(
values.len()) - 没有提前退出(不 break)
- 操作简单(比较 + 置位)
编译器会把每 4 个或 8 个 i64 打包成 SIMD 寄存器,一次比较多个值。
这就是向量化执行快的真正来源:不是"我们手写了 SIMD",而是"把代码写成编译器能自动向量化的形状"。
向量化执行的核心技巧是"让循环的形状对编译器友好":固定长度、无提前退出、无类型分支。
算子二:向量化聚合
SUM(amount) 在逐行执行里是"每行加一次"。向量化版本:
pub struct SumAggregate {
input: Box<dyn VectorizedOperator>,
column: usize,
sum: i64,
count: u64,
}
impl SumAggregate {
pub fn consume(&mut self) -> i64 {
loop {
let batch = self.input.next_batch();
if batch.is_empty() {
break;
}
match &batch.columns[self.column] {
Column::I64(values) => {
// 关键:用一个局部变量累加,而不是每次都写 self.sum
let mut local = 0i64;
for &v in values {
local += v;
}
self.sum += local;
self.count += values.len() as u64;
}
_ => todo!(),
}
}
self.sum
}
}注意那个 local 变量。 这不是多余的——它让编译器知道"这个累加不会和其他内存操作交错",从而放心地做向量化和指令重排。
如果直接写 self.sum += v,编译器不能确定 self 是否会被别名(aliasing),可能放弃向量化。
这一个小改动在实际测试里能带来明显的差距。
多列聚合:一次遍历算多个
分析查询经常同时算多个聚合:
SELECT sum(amount), avg(amount), min(amount), max(amount), count(*) FROM orders WHERE ...关键洞察:这四个聚合可以一次遍历算完。
pub struct MultiAggregate {
input: Box<dyn VectorizedOperator>,
column: usize,
sum: i64,
count: u64,
min: i64,
max: i64,
}
impl MultiAggregate {
pub fn consume(&mut self) -> (i64, f64, i64, i64, u64) {
while let batch = self.input.next_batch() {
if batch.is_empty() {
break;
}
if let Column::I64(values) = &batch.columns[self.column] {
let mut local_sum = 0i64;
let mut local_min = i64::MAX;
let mut local_max = i64::MIN;
// 一次循环算四个聚合
for &v in values {
local_sum += v;
local_min = local_min.min(v);
local_max = local_max.max(v);
}
self.sum += local_sum;
self.min = self.min.min(local_min);
self.max = self.max.max(local_max);
self.count += values.len() as u64;
}
}
(self.sum, self.sum as f64 / self.count as f64, self.min, self.max, self.count)
}
}数据只从内存读一遍,同时更新四个累加器。 逐行执行时,每个聚合是独立的算子,数据要多读几遍。
这就是为什么分析型数据库的算子要设计成"一次扫描多个聚合"。
算子三:哈希聚合(GROUP BY)
GROUP BY region 需要哈希表。向量化版本的关键是批量哈希 + 批量探测:
pub struct HashAggregate {
input: Box<dyn VectorizedOperator>,
group_col: usize,
/// 分组键 -> 分组 id
table: std::collections::HashMap<u64, u32>,
/// 每个分组的聚合状态
groups: Vec<GroupState>,
}
impl HashAggregate {
fn consume_batch(&mut self, batch: &Batch) {
let keys = &batch.columns[self.group_col];
match keys {
Column::I64(values) => {
// 批量计算哈希
let hashes: Vec<u64> = values.iter().map(|&v| hash_i64(v)).collect();
// 批量探测 / 插入
let group_ids: Vec<u32> = hashes
.iter()
.zip(values)
.map(|(&h, &v)| {
*self.table.entry(h).or_insert_with(|| {
let id = self.groups.len() as u32;
self.groups.push(GroupState::default());
id
})
})
.collect();
// 批量更新聚合
for (i, &gid) in group_ids.iter().enumerate() {
self.groups[gid as usize].sum += batch.numeric_value(i);
self.groups[gid as usize].count += 1;
}
}
_ => todo!(),
}
}
}注意这里的哈希表是"分组键的哈希 -> 分组 id",而不是"键 -> 聚合值"。
这样把"哈希查找"和"聚合更新"分开了:
- 哈希查找是随机访问(慢,但必须做)
- 聚合更新是顺序的局部操作(快)
另一个重要优化:如果分组键已经字典编码(基数低的字符串列),那它本身就是个小整数——直接用数组代替哈希表:
/// 字典编码的 group by:直接数组索引,不需要哈希
fn aggregate_by_dict_code(codes: &[u32], values: &[i64], num_dicts: usize) -> Vec<i64> {
let mut sums = vec![0i64; num_dicts];
for (&code, &v) in codes.iter().zip(values) {
// 一次数组索引,而不是一次哈希查询
sums[code as usize] += v;
}
sums
}这是列存 + 字典编码 + 向量化三者叠加的效果:字符串分组变成数组索引。
所以"列存"和"向量化"必须一起用才发挥威力。 单独的向量化,如果底层还是行存、还要做字符串比较,收益会大打折扣。
算子四:向量化的 JOIN
Hash join 的向量化版本和聚合类似,但两边都要批量处理:
1. 构建阶段(build):把小的那一侧建成哈希表,key -> 行号列表
2. 探测阶段(probe):批量扫描大的那一侧,批量查哈希表pub struct HashJoin {
/// build 侧:key 哈希 -> 行号
build_table: std::collections::HashMap<u64, Vec<u32>>,
}
impl HashJoin {
pub fn probe_batch(&self, batch: &Batch, key_col: usize) -> Vec<(u32, u32)> {
let keys = &batch.columns[key_col];
let mut pairs = Vec::new();
match keys {
Column::I64(values) => {
for (probe_idx, &v) in values.iter().enumerate() {
let h = hash_i64(v);
if let Some(build_rows) = self.build_table.get(&h) {
// 一次探测可能匹配多行(一对多)
for &build_idx in build_rows {
pairs.push((probe_idx as u32, build_idx));
}
}
}
}
_ => todo!(),
}
pairs
}
}返回的是"行号对",而不是已经拼好的行。 这又是延迟物化——只有真正需要输出的时候才去取列值。
在 SELECT region, count(*) FROM ... JOIN ... GROUP BY region 这种查询里,join 之后可能 90% 的行都会被聚合掉。 如果 join 时就物化了全部列,那 90% 的复制都白做了。
延迟物化(late materialization)是列存 + 向量化体系里的一个核心原则:算子之间传递"行号",只有最后一个算子才真正取数据。
性能差异从哪来:一次量化
用一个具体例子对比(1000 万行,sum(amount) where region = 3):
| 实现 | 耗时 | 相对 |
|---|---|---|
| 逐行 + 字符串比较 | 850ms | 1× |
| 逐行 + 字典码比较 | 320ms | 2.7× |
| 向量化 + 字典码 | 45ms | 19× |
| 向量化 + SIMD 显式 intrinsic | 32ms | 27× |
从 850ms 到 45ms,差距主要来自三处:
- 字典编码(850 → 320):字符串比较变整数比较
- 批量循环 + 自动向量化(320 → 45):SIMD + 更好的分支预测
- 手写 SIMD(45 → 32):最后那部分收益需要 intrinsic
注意第 3 步的边际收益:手写 SIMD 相比"编译器自动向量化"只快 1.4 倍——所以先做好前两步,手写 SIMD 是最后才考虑的优化。
而且要注意平台差异。 上面这个数据在 AVX2 上成立;在没有 SIMD 的架构(或者编译目标没开启)上,向量化执行的收益会小很多——但字典编码和批量的收益依然存在。
什么时候向量化不划算
向量化不是万能的,有几个反例:
1. 点查(OLTP 场景)。 SELECT * FROM users WHERE id = 42 只读一行——批量的开销(分配 batch 结构、构造选择向量)完全白费。这就是为什么 OLTP 数据库不用向量化执行。
2. 有大量提前退出的查询。 LIMIT 10 ——只需要 10 行,但批量会先读 2048 行。优化方式是把 limit 下推到扫描算子,让它只取需要的量。
3. 超高选择率的过滤。 如果谓词过滤掉 99.9% 的行,那"批量求值 + 收集选择向量"的大部分工作是浪费的。这种情况适合"先采样,发现选择率低就切换到逐行模式"。
向量化是为"扫描大量数据"设计的。 单行操作、点查、短查询都不是它的主场。这也是为什么没有一个数据库"只用向量化"——OLAP 和 OLTP 的执行器是两套。
结论
向量化执行的核心是三件事:
接口改成批量(一次 2048 行);谓词返回位图而不是单行布尔值;算子间传递行号而不是物化数据(延迟物化)。
性能收益的构成也很清楚:
- 消除每行的虚函数调用和类型分支
- 让循环形状对编译器友好,从而自动向量化(SIMD)
- 配合列存和字典编码,把字符串操作变成整数操作
一个重要的心态提醒:不要一上来就手写 SIMD intrinsic。 先把批量接口、位图、选择向量、字典编码做好,这些结构性优化能拿到 80% 的收益。剩下的 20% 才需要针对具体 CPU 做特化,而且会损失可移植性。
下一篇,我们把这几篇的东西合起来——列存 + 编码 + 向量化 + 解析,做一个能真正跑 SQL 的内存引擎。