返回文章列表

用 Rust 从零实现向量化执行引擎:SQL 为什么快在批量

660 字·5 分钟阅读
Rust从零造轮子查询引擎

上一篇实现了列式存储,把数据按列存好了。但**"怎么算"还没有解决**——把一列 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);
        }
    }
}

两个关键收益:

  1. 谓词求值是对整个向量做的,可以按 64 位一组处理,编译器能生成 SIMD 指令
  2. 不需要"复制"数据——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,差距主要来自三处:

  1. 字典编码(850 → 320):字符串比较变整数比较
  2. 批量循环 + 自动向量化(320 → 45):SIMD + 更好的分支预测
  3. 手写 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 行);谓词返回位图而不是单行布尔值;算子间传递行号而不是物化数据(延迟物化)。

性能收益的构成也很清楚:

  1. 消除每行的虚函数调用和类型分支
  2. 让循环形状对编译器友好,从而自动向量化(SIMD)
  3. 配合列存和字典编码,把字符串操作变成整数操作

一个重要的心态提醒:不要一上来就手写 SIMD intrinsic。 先把批量接口、位图、选择向量、字典编码做好,这些结构性优化能拿到 80% 的收益。剩下的 20% 才需要针对具体 CPU 做特化,而且会损失可移植性。

下一篇,我们把这几篇的东西合起来——列存 + 编码 + 向量化 + 解析,做一个能真正跑 SQL 的内存引擎。