用 Rust 从零实现内存 SQL 引擎:把前面二十个轮子串起来
前面写的二十个轮子各自独立。但真正有意思的问题不是"每个怎么实现",而是"它们怎么组合成一个系统"。
这篇做一个内存 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:一个失败的教训
排序是最不"向量化友好"的算子。 因为:
- 它必须读完全部数据才能输出(阻塞算子)
- 输出是随机的行序,破坏了批量的顺序性
- 比较函数是动态的(按哪几列、升序还是降序)
常见的做法是"物化 + 索引排序":
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 的结构";逻辑计划是"要做什么";物理计划是"用什么算法做";执行器树是"一次一批地拉数据"。
贯穿其中的三个原则(它们在前面的轮子里都出现过):
- 列裁剪 + 延迟物化(来自列存和向量化)——把 IO 和内存拷贝降到最低
- 批量接口 + 位图(来自向量化执行)——让编译器能优化内层循环
- 移动索引而不是移动数据(来自排序)——在数据库里无处不在
这三条合起来,就是"分析型数据库为什么快"的完整答案。 而它们的共同前提是:数据按列存储——没有列存,前两条都无从谈起。
写完这一篇,这个「用 Rust 从零造轮子」系列就完整了。回头看,四十多个轮子可以分成几类:
| 类别 | 轮子 |
|---|---|
| 数据结构 | 哈希表、跳表、布隆过滤器、缓存、Trie、倒排索引、HNSW |
| 内存与 IO | 分配器、对象池、mmap、零拷贝 |
| 并发 | 线程池、无锁队列、定时器、工作窃取、协程、异步运行时 |
| 协议与框架 | JSON、序列化、CLI、配置、HTTP、RESP、WebSocket、反向代理、RPC、S3 |
| 存储 | WAL、Bitcask、LSM-Tree、列存 |
| 分布式 | 一致性哈希、分布式锁、Merkle Tree、CRDT、Raft、Saga |
| 容错与执行 | 限流、熔断、连接池、消息队列、向量化执行、SQL 引擎 |
它们看起来分散,但反复出现的只有那么几个思路:用顺序换随机、用空间换时间、用批量换单行、用概率换确定性、用补偿换原子性。 这些思路的组合,构成了整个后端技术栈的面貌——这也是我写这个系列的初衷:不是记住每个轮子怎么造,而是认出每个设计背后在做什么交换。