返回文章列表

用 Rust 从零实现内存 SQL 引擎:把前面二十个轮子串起来

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

前面写的二十个轮子各自独立。但真正有意思的问题不是"每个怎么实现",而是"它们怎么组合成一个系统"。

这篇做一个内存 SQL 引擎。它不引入新算法,而是把前面写过的东西拼起来:

SQL 文本
  │ ① 词法 + 语法分析(← 引用 0910 的思路)
  v
逻辑计划(AST)
  │ ② 绑定 + 类型检查
  v
物理计划(算子树)
  │ ③ 列式存储(← 引用 0927)
  │ ④ 向量化执行(← 引用 0928)
  v
结果集

这一篇的重点是"接口怎么定义"和"算子怎么串",而不是单个算法。


第一步:解析 SQL

先定一个足够用的 SQL 子集:

SELECT region, sum(amount) AS total
FROM orders
WHERE amount > 100
GROUP BY region
HAVING sum(amount) > 1000
ORDER BY total DESC
LIMIT 10;

AST 设计:

#[derive(Debug, Clone)]
pub enum Statement {
    Select(SelectStmt),
    CreateTable(CreateTableStmt),
    Insert(InsertStmt),
}
 
#[derive(Debug, Clone)]
pub struct SelectStmt {
    pub projections: Vec<SelectItem>,
    pub from: String,
    pub filter: Option<Expr>,
    pub group_by: Vec<String>,
    pub having: Option<Expr>,
    pub order_by: Vec<OrderItem>,
    pub limit: Option<u64>,
}
 
#[derive(Debug, Clone)]
pub enum SelectItem {
    /// 普通列引用
    Column(String),
    /// 聚合函数
    Aggregate { func: AggFunc, arg: String, alias: Option<String> },
    /// 通配
    Wildcard,
}
 
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum AggFunc {
    Sum,
    Count,
    Min,
    Max,
    Avg,
}

解析部分直接复用前面写过的"词法 + 递归下降"。 这里不重复实现,只强调 SQL 解析相比 JSON 多出来的两个难点:

1. SELECT 子句里的聚合和普通列混在一起。 解析时要区分"这是列引用还是聚合函数调用",需要向前看一个 token。

2. 关键字大小写不敏感,但标识符大小写敏感。 SELECT 和 select 等价,但 "Region" 和 "region" 不是同一列(取决于方言)。

处理方式:词法分析时把关键字统一转大写,标识符保留原样,然后比较时统一小写。

第二步:逻辑计划——先想清楚"做什么"

解析出来的 AST 是"SQL 原样的结构"。逻辑计划要把它变成"算子树"。

#[derive(Debug)]
pub enum LogicalPlan {
    Scan {
        table: String,
        /// 列裁剪:只读这些列
        columns: Vec<String>,
    },
    Filter {
        input: Box<LogicalPlan>,
        predicate: Expr,
    },
    Aggregate {
        input: Box<LogicalPlan>,
        group_by: Vec<Expr>,
        aggregates: Vec<(AggFunc, Expr, String)>,
    },
    Project {
        input: Box<LogicalPlan>,
        exprs: Vec<(Expr, String)>,
    },
    Sort {
        input: Box<LogicalPlan>,
        keys: Vec<(Expr, bool)>, // (表达式, 是否降序)
    },
    Limit {
        input: Box<LogicalPlan>,
        n: u64,
    },
}

从 SQL 到逻辑计划,最关键的是"算子顺序"。 SQL 子句的书写顺序和实际执行顺序不同:

书写顺序:  SELECT  FROM  WHERE  GROUP BY  HAVING  ORDER BY  LIMIT
执行顺序:  FROM  WHERE  GROUP BY  HAVING  SELECT  ORDER BY  LIMIT
                                ↑                    ↑
                          这里还看不到 SELECT 的别名

这解释了一个经典的 SQL 疑问:为什么 WHERE 里不能用 SELECT 的别名?

因为 WHERE 在 SELECT 之前执行——别名还不存在。而 ORDER BY 在 SELECT 之后,所以能用别名。

SQL 的"声明式"只体现在写起来可以随意,执行顺序是完全固定的。 理解这个顺序,才能正确构造计划树。

构造顺序:

pub fn build_plan(stmt: &SelectStmt, catalog: &Catalog) -> Result<LogicalPlan, PlanError> {
    // 1. FROM:扫描(同时做列裁剪)
    let mut plan = LogicalPlan::Scan {
        table: stmt.from.clone(),
        columns: collect_required_columns(stmt),  // 关键优化:只扫需要的列
    };
 
    // 2. WHERE
    if let Some(pred) = &stmt.filter {
        plan = LogicalPlan::Filter {
            input: Box::new(plan),
            predicate: pred.clone(),
        };
    }
 
    // 3. GROUP BY + 聚合
    let aggregates = collect_aggregates(&stmt.projections);
    if !stmt.group_by.is_empty() || !aggregates.is_empty() {
        plan = LogicalPlan::Aggregate {
            input: Box::new(plan),
            group_by: stmt.group_by.iter().map(|c| Expr::Column(c.clone())).collect(),
            aggregates,
        };
    }
 
    // 4. HAVING(作用在聚合结果上)
    if let Some(having) = &stmt.having {
        plan = LogicalPlan::Filter {
            input: Box::new(plan),
            predicate: having.clone(),
        };
    }
 
    // 5. SELECT:投影
    plan = LogicalPlan::Project {
        input: Box::new(plan),
        exprs: stmt.projections.iter().map(to_projection).collect(),
    };
 
    // 6. ORDER BY
    if !stmt.order_by.is_empty() {
        plan = LogicalPlan::Sort {
            input: Box::new(plan),
            keys: stmt.order_by.iter().map(to_sort_key).collect(),
        };
    }
 
    // 7. LIMIT
    if let Some(n) = stmt.limit {
        plan = LogicalPlan::Limit {
            input: Box::new(plan),
            n,
        };
    }
 
    Ok(plan)
}

这七步的顺序和 SQL 的逻辑执行顺序一一对应。 函数读起来就像一个"从下往上包"的过程。

列裁剪:一个高收益的优化

collect_required_columns 是个简单但收益巨大的优化:

fn collect_required_columns(stmt: &SelectStmt) -> Vec<String> {
    let mut cols = std::collections::HashSet::new();
 
    // SELECT 里用到的列
    for item in &stmt.projections {
        collect_expr_columns(item, &mut cols);
    }
    // WHERE / GROUP BY / HAVING / ORDER BY 里用到的列
    if let Some(f) = &stmt.filter {
        collect_expr_columns_expr(f, &mut cols);
    }
    for g in &stmt.group_by {
        cols.insert(g.clone());
    }
    if let Some(h) = &stmt.having {
        collect_expr_columns_expr(h, &mut cols);
    }
 
    cols.into_iter().collect()
}

为什么这个优化收益巨大? 因为列存的核心优势就是"不读不需要的列"。

SELECT sum(amount) FROM orders WHERE region = 'cn'

如果表有 50 列,列裁剪让 IO 从"全表 50 列"降到"2 列"——25 倍的 IO 减少,这是所有优化里最立竿见影的一个。

在列存系统里,"列裁剪"不是优化技巧,而是必须做的基础能力。 不做它,列存就退化成了行存。

第三步:物理计划——"怎么做"

逻辑计划说"要过滤",物理计划说"用向量化的 FilterOp 来过滤"。

pub enum PhysicalPlan {
    Scan(ScanExec),
    Filter(FilterExec),
    HashAggregate(HashAggExec),
    Project(ProjectExec),
    Sort(SortExec),
    Limit(LimitExec),
}

转换的关键决策是"用哪种算法":

逻辑算子 可选物理算子 选择依据
Aggregate HashAgg / SortedAgg 数据是否已排序
Sort 内存排序 / 外部排序 数据量是否超过内存
Join HashJoin / NestedLoop 是否有等值条件
pub fn physicalize(logical: LogicalPlan, catalog: &Catalog) -> Result<PhysicalPlan, PlanError> {
    match logical {
        LogicalPlan::Scan { table, columns } => {
            let table = catalog.get(&table)?;
            Ok(PhysicalPlan::Scan(ScanExec::new(table, columns)))
        }
 
        LogicalPlan::Aggregate { input, group_by, aggregates } => {
            let child = physicalize(*input, catalog)?;
 
            // 决策:数据已按 group key 排序 -> 用 SortedAgg 省一次哈希
            if is_sorted_by(&child, &group_by) {
                Ok(PhysicalPlan::SortedAggregate(SortedAggExec::new(child, group_by, aggregates)))
            } else {
                Ok(PhysicalPlan::HashAggregate(HashAggExec::new(child, group_by, aggregates)))
            }
        }
 
        // ...
        _ => todo!(),
    }
}

第四步:执行器接口

这是全文最重要的一段代码——它定义了所有算子之间的契约:

pub trait Executor {
    /// 返回下一批数据
    fn next_batch(&mut self) -> Result<Batch, ExecError>;
 
    /// 输出 schema(列名和类型)
    fn schema(&self) -> &Schema;
 
    /// 重置,用于重新执行(比如 nested loop join 的内侧)
    fn reset(&mut self) -> Result<(), ExecError>;
}

三个方法各有用途:

  • next_batch:拉取数据(火山模型的批量版本)
  • schema:让上层知道列的顺序和类型
  • reset:嵌套循环连接需要重复扫描内侧

reset 这个方法很容易被忽略,但它是"算子可重入"的保证。 有它,同一个算子可以被执行多次;没有它,嵌套循环 join 就无法实现。

第五步:把算子串起来

pub fn build_executor(plan: PhysicalPlan) -> Box<dyn Executor> {
    match plan {
        PhysicalPlan::Scan(exec) => Box::new(exec),
        PhysicalPlan::Filter(exec) => Box::new(exec),
        PhysicalPlan::HashAggregate(exec) => Box::new(exec),
        PhysicalPlan::Project(exec) => Box::new(exec),
        PhysicalPlan::Sort(exec) => Box::new(exec),
        PhysicalPlan::Limit(exec) => Box::new(exec),
    }
}

每个算子内部持有一个 Box<dyn Executor> 作为输入。 这样构建出来就是一棵算子树。

驱动执行:

pub fn execute(mut root: Box<dyn Executor>) -> Result<(), ExecError> {
    loop {
        let batch = root.next_batch()?;
        if batch.is_empty() {
            break;
        }
        // 输出这批(真实场景是发给客户端)
        print_batch(&batch);
    }
    Ok(())
}

第六步:几个算子的具体实现

Scan:从表里读列

pub struct ScanExec {
    table: std::sync::Arc<TableData>,
    columns: Vec<usize>,
    /// 当前读到第几批
    batch_idx: usize,
    schema: Schema,
}
 
impl ScanExec {
    pub fn new(table: &std::sync::Arc<TableData>, columns: Vec<String>) -> Self {
        let col_indices: Vec<usize> = columns
            .iter()
            .filter_map(|c| table.column_index(c))
            .collect();
 
        let schema = Schema::from_columns(&table, &col_indices);
 
        Self {
            table: table.clone(),
            columns: col_indices,
            batch_idx: 0,
            schema,
        }
    }
}
 
impl Executor for ScanExec {
    fn next_batch(&mut self) -> Result<Batch, ExecError> {
        let start = self.batch_idx * BATCH_SIZE;
        let end = (start + BATCH_SIZE).min(self.table.row_count());
        self.batch_idx += 1;
 
        if start >= end {
            return Ok(Batch::empty());
        }
 
        // 只取需要的列——列存的核心优势
        let columns: Vec<Column> = self
            .columns
            .iter()
            .map(|&ci| self.table.column_slice(ci, start, end))
            .collect();
 
        Ok(Batch {
            columns,
            len: end - start,
        })
    }
 
    fn schema(&self) -> &Schema {
        &self.schema
    }
 
    fn reset(&mut self) -> Result<(), ExecError> {
        self.batch_idx = 0;
        Ok(())
    }
}

Limit:提前停止

pub struct LimitExec {
    input: Box<dyn Executor>,
    remaining: u64,
}
 
impl Executor for LimitExec {
    fn next_batch(&mut self) -> Result<Batch, ExecError> {
        if self.remaining == 0 {
            return Ok(Batch::empty());
        }
 
        let batch = self.input.next_batch()?;
        if batch.is_empty() {
            return Ok(batch);
        }
 
        let take = (batch.len as u64).min(self.remaining) as usize;
        self.remaining -= take as u64;
 
        // 截断这一批
        Ok(batch.truncate(take))
    }
 
    // ...
}

Limit 的价值在于它让上层"提前退出"。

但这里有个重要细节:如果 Limit 上面还有 Sort,那"提前退出"没有意义——排序必须读完所有数据。只有 Limit 直接作用在 Scan 上时,才能真的少读数据。

这就是"优化器要做谓词/limit 下推"的原因:

不好: Limit -> Sort -> Scan        (必须读完)
更好: Limit -> Scan + TopN 堆      (只维护 N 个)

TopN 优化是:排序时只维护大小为 N 的最大堆,而不是全排序再取前 N。这在 ORDER BY ... LIMIT 10 时能把 O(n log n) 降到 O(n log k)。

Project:计算表达式

pub struct ProjectExec {
    input: Box<dyn Executor>,
    exprs: Vec<Expr>,
    schema: Schema,
}
 
impl Executor for ProjectExec {
    fn next_batch(&mut self) -> Result<Batch, ExecError> {
        let input = self.input.next_batch()?;
        if input.is_empty() {
            return Ok(input);
        }
 
        // 对每批逐表达式求值
        let columns: Vec<Column> = self
            .exprs
            .iter()
            .map(|e| e.eval(&input))
            .collect::<Result<_, _>>()?;
 
        Ok(Batch {
            columns,
            len: input.len,
        })
    }
    // ...
}

Sort:一个失败的教训

排序是最不"向量化友好"的算子。 因为:

  1. 它必须读完全部数据才能输出(阻塞算子)
  2. 输出是随机的行序,破坏了批量的顺序性
  3. 比较函数是动态的(按哪几列、升序还是降序)

常见的做法是"物化 + 索引排序":

pub struct SortExec {
    input: Box<dyn Executor>,
    keys: Vec<(usize, bool)>,
    /// 全部物化下来的数据
    materialized: Option<MaterializedData>,
    cursor: usize,
}
 
impl SortExec {
    fn materialize(&mut self) -> Result<(), ExecError> {
        if self.materialized.is_some() {
            return Ok(());
        }
 
        // 1. 读完全部输入,拼成完整列
        let mut columns: Vec<Column> = Vec::new();
        loop {
            let batch = self.input.next_batch()?;
            if batch.is_empty() {
                break;
            }
            // 追加到 columns
        }
 
        // 2. 生成排序索引(不移动数据!)
        let n = columns[0].len();
        let mut indices: Vec<u32> = (0..n as u32).collect();
 
        indices.sort_by(|&a, &b| {
            for (col, desc) in &self.keys {
                let ord = columns[*col].compare(a as usize, b as usize);
                let ord = if *desc { ord.reverse() } else { ord };
                if ord != std::cmp::Ordering::Equal {
                    return ord;
                }
            }
            std::cmp::Ordering::Equal
        });
 
        self.materialized = Some(MaterializedData { columns, indices });
        Ok(())
    }
}

关键点是"排序索引,而不是排序数据"。

  • 排序 Vec<u32> 索引:4 字节一个元素,交换成本低
  • 排序实际数据:每行可能是几百字节,交换成本高得多

这就是数据库里的"间接排序(indirect sort)"。

排序的核心优化是"移动指针而不是移动数据"。 这个思路在数据库里到处都是——延迟物化、间接排序、B 树存指针,本质都是同一件事。

第七步:一个完整的执行例子

以开头的 SQL 为例:

SELECT region, sum(amount) AS total FROM orders
WHERE amount > 100
GROUP BY region
HAVING sum(amount) > 1000
ORDER BY total DESC
LIMIT 10;

生成的算子树(从下往上读):

Limit 10
  └─ Sort (total DESC)
      └─ Project [region, sum(amount) AS total]
          └─ Filter (sum(amount) > 1000)        ← HAVING
              └─ HashAggregate (group: region, aggs: sum(amount))
                  └─ Filter (amount > 100)      ← WHERE
                      └─ Scan orders [region, amount]   ← 列裁剪:只读 2 列

两个值得注意的点:

1. WHERE 和 HAVING 是两个不同的 Filter 算子。 它们在不同位置——一个在聚合前,一个在聚合后。类型也不同:前者的输入是原始列,后者的输入是聚合结果。

2. Scan 只读两列。 尽管查询里提到 orders 表,但实际只用了 region 和 amount。

如果 orders 表有 50 列、1 亿行,这个列裁剪直接把 IO 从几十 GB 降到 1GB 左右。

执行计划的可视化

一个实用的功能是打印计划树:

pub fn explain(plan: &PhysicalPlan, indent: usize) -> String {
    let pad = " ".repeat(indent);
    let line = match plan {
        PhysicalPlan::Scan(e) => format!("{pad}Scan {} [{}]", e.table_name, e.columns.join(", ")),
        PhysicalPlan::Filter(e) => format!("{pad}Filter {}", e.predicate),
        PhysicalPlan::HashAggregate(e) => {
            format!("{pad}HashAggregate group=[{}] aggs=[{}]",
                e.group_by.join(","), e.aggs.join(","))
        }
        PhysicalPlan::Sort(e) => format!("{pad}Sort by {:?}", e.keys),
        PhysicalPlan::Limit(e) => format!("{pad}Limit {}", e.n),
        PhysicalPlan::Project(e) => format!("{pad}Project {:?}", e.exprs),
    };
 
    let mut out = line + "\n";
    if let Some(child) = plan.child() {
        out.push_str(&explain(child, indent + 2));
    }
    out
}

输出:

Limit 10
  Sort by [(1, true)]
    Project [Column(0), Aggregate(Sum, 1)]
      Filter sum(amount) > 1000
        HashAggregate group=[region] aggs=[sum(amount)]
          Filter amount > 100
            Scan orders [region, amount]

EXPLAIN 是所有数据库最重要的调试工具。 有了它,你能一眼看出"列裁剪有没有生效""谓词有没有下推"——这两个问题的答案,决定了查询是快还是慢。

结论

这个引擎不包含任何新算法,但它是整个系列里最有价值的一篇:

解析产出的 AST 是"SQL 的结构";逻辑计划是"要做什么";物理计划是"用什么算法做";执行器树是"一次一批地拉数据"。

贯穿其中的三个原则(它们在前面的轮子里都出现过):

  1. 列裁剪 + 延迟物化(来自列存和向量化)——把 IO 和内存拷贝降到最低
  2. 批量接口 + 位图(来自向量化执行)——让编译器能优化内层循环
  3. 移动索引而不是移动数据(来自排序)——在数据库里无处不在

这三条合起来,就是"分析型数据库为什么快"的完整答案。 而它们的共同前提是:数据按列存储——没有列存,前两条都无从谈起。


写完这一篇,这个「用 Rust 从零造轮子」系列就完整了。回头看,四十多个轮子可以分成几类:

类别 轮子
数据结构 哈希表、跳表、布隆过滤器、缓存、Trie、倒排索引、HNSW
内存与 IO 分配器、对象池、mmap、零拷贝
并发 线程池、无锁队列、定时器、工作窃取、协程、异步运行时
协议与框架 JSON、序列化、CLI、配置、HTTP、RESP、WebSocket、反向代理、RPC、S3
存储 WAL、Bitcask、LSM-Tree、列存
分布式 一致性哈希、分布式锁、Merkle Tree、CRDT、Raft、Saga
容错与执行 限流、熔断、连接池、消息队列、向量化执行、SQL 引擎

它们看起来分散,但反复出现的只有那么几个思路:用顺序换随机、用空间换时间、用批量换单行、用概率换确定性、用补偿换原子性。 这些思路的组合,构成了整个后端技术栈的面貌——这也是我写这个系列的初衷:不是记住每个轮子怎么造,而是认出每个设计背后在做什么交换。