ToyDB Query Parsing

ToyDB 提供了手动解析的 Parser 和自己写的 Catalog 和 Planner,Catalog. 它有一个很奇怪的特点就是,大家都叫一个名字,然后从 modules 来区分。我不知道这算不算好的实践,反正给我整的有点麻。

这里我折腾了一个简单的可以玩 query 的场景:https://github.com/mapleFU/toydb ,见这个项目里的 test_basic_sql

Catalog

ToyDB 的 Catalog 和 Transaction 是半绑定的,Catalog 和 Transaction 都以一个 Trait 的形式提供。ToyDB 的 Catalog 只支持单个 database,不支持 DDL。系统会存储在一个 Raft Key-Value 的事务引擎上,存储内容如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/// Encodes SQL keys, using an order-preserving encoding - see kv::encoding for details. Options can
/// be None to get a keyspace prefix. We use table and column names directly as identifiers, to
/// avoid additional indirection and associated overhead. It is not possible to change names, so
/// this is ok. Uses Cows since we want to borrow when encoding but return owned when decoding.
///
/// 最后一项可能由 Option 构成, Option 为空的时候, 可以拿到这个 key
/// 编码: 这里会把对应的对象整理成一个 Key, Table / Index / Row 存放在不同的 keyspace (类似 ns).
///
/// 这个基本上套了一层 foundation db 的编码系统。
enum Key<'a> {
/// A table schema key for the given table name
/// tableName.
/// 这个的 prefix 为 0x01
Table(Option<Cow<'a, str>>),
/// A key for an index entry
///
/// (tableName, columnName, value).
Index(Cow<'a, str>, Cow<'a, str>, Option<Cow<'a, Value>>),
/// A key for a row identified by table name and row primary key
///
/// (tableName, value)
Row(Cow<'a, str>, Option<Cow<'a, Value>>),
}

对应 Trait 如下:

  • Catalog, Schema, Column, Table: https://github.com/erikgrinaker/toydb/blob/master/src/sql/schema.rs
    • Column 有基本的 (name, type) 支持 default, pk, nullable, unique, foreign key 甚至 index,支持上层去 validate 对应的 value,这个检查。(虽然有的地方我感觉不应该在 Column 里面支持)
    • Table 即 <name: String, columns: [Column]>,在单个 Table 内,只有单个 key 是主键,不支持联合主键。Index 也只支持单值的 Index,不支持联合索引
    • Schema 这里会访问物理层,来拿到对应的内容。
    • 它的 Catalog 这个地方支持的是访问 Table 的接口
    • 讨论:在 Column 支持 pk, default, unique, fk 应该不是一个合理的方案。

Parsing

这里的 Lexer 不太教科书,而是手工编写的一个识别器,我感觉用 flex 写一个没准还舒服些。

语法分析则是一个递归下降的 Parsing,语法结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/// Parses an SQL statement
fn parse_statement(&mut self) -> Result<ast::Statement> {
match self.peek()? {
Some(Token::Keyword(Keyword::Begin)) => self.parse_transaction(),
Some(Token::Keyword(Keyword::Commit)) => self.parse_transaction(),
Some(Token::Keyword(Keyword::Rollback)) => self.parse_transaction(),

Some(Token::Keyword(Keyword::Create)) => self.parse_ddl(),
Some(Token::Keyword(Keyword::Drop)) => self.parse_ddl(),

Some(Token::Keyword(Keyword::Delete)) => self.parse_statement_delete(),
Some(Token::Keyword(Keyword::Insert)) => self.parse_statement_insert(),
Some(Token::Keyword(Keyword::Select)) => self.parse_statement_select(),
Some(Token::Keyword(Keyword::Update)) => self.parse_statement_update(),

Some(Token::Keyword(Keyword::Explain)) => self.parse_statement_explain(),

Some(token) => Err(Error::Parse(format!("Unexpected token {}", token))),
None => Err(Error::Parse("Unexpected end of input".into())),
}
}

可以从这个来推断出它的结构,这段应该是按照 standard 写的,还算有参考价值。对外产生最终的结构在目录 ast 下头,具体是一个 ast::Statement.

特殊的,如果是 SELECT *

Planner

Planner 负责将 ast::Statement 转为 Plan. 这部分 Plan / PlanNode 本身就是可以运行的了,通过走一个可选的 Optimizer 来进行优化。

这个地方没有一个 (单独的)Binder 阶段来 resolve name,

Plan Select

Scope

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/// Manages names available to expressions and executors, and maps them onto columns/fields.
///
/// Scope 包含一组有序的 columns. 同时包含限定符, 表示这些东西的归属.
#[derive(Clone, Debug)]
pub struct Scope {
// If true, the scope is constant and cannot contain any variables.
constant: bool,
// Currently visible tables, by query name (i.e. alias or actual name).
//
// Table 的名称集合, 构建了 alias / table_name -> Table 的映射
// TODO(maple): 这个 Table 是怎么构建出来的? 具体 binding 吗?
tables: HashMap<String, Table>,
// Column labels, if any (qualified by table name when available)
//
// columns 是表的 source-of-truth, 下面三个 hash 都是根据这玩意造出来的.
columns: Vec<(Option<String>, Option<String>)>,
// Qualified names to column indexes.
//
// qualified: 有 table-name 和 field-name 的, 这个地方 field-name 可能是一个 label.
qualified: HashMap<(String, String), usize>,
// Unqualified names to column indexes, if unique.
unqualified: HashMap<String, usize>,
// Unqualified ambiguous names.
// TODO(maple): ambiguous 的 name 是怎么 solving 的?
ambiguous: HashSet<String>,
}

Expression

Expression 的 solving 通常不需要变更类型,字面量是什么类型使用的就是什么类型,这里支持的类型有:

  • INTEGER: 1, 2, 3
  • FLOAT: 1.2
  • NULL
  • Boolean: true, false
  • String: ''

常量解析的时候,一般就用上面这些类型,然后在表达式 eval 阶段判断类型。

表达式会从 Scope 中捞到名字,从 ast::Expression 构建一个 Expression 它会构建:

  • Literal: 返回 Constant
  • Field: 带有来源的 fieldId 和 table.name 的名字,返回 Field
  • Function:很遗憾,它没有实现任何 function
  • Column: 这个比较重要,放后面说,这个在它的 SQL 语法不存在,属于内部生成的
  • Operation: 从 AND OR 到加减法等等

总之,这里会构建一份 Expression

FromTable ( TableRef ) 构建

  • 采用
1
2
3
4
5
6
7
8
build_from_clause:
- copy 一份 root Scope
- (对每个子成员) (使用 root Scope) build_from_item
- (递归基) 去 catalog 查询有没有这个名字的表, 然后走 `scope::add_table`, 返回一个 Node::Scan
- (Join) 去 build_from_item 左表, 然后用同一个 scope 去 build_from_item 右表
再用这个 scope 去 `build_expression`, 构建出 `ON ..` 的条件
构成一个 Node::NextLoopJoin 节点. (这里有一些关于 right join 的 hack 操作,暂不讨论)
- 对上述的成员,构成一个 Node::NestLoopJoin 的左深树, 并递归的去 merge 这些 scope

这个地方用到了 build_expression 来处理 ON 的情况,对外返回了一个新的 Scope.

Where 构建

用到了 build_expression 来处理 WHERE 子表达式。同 Expression 一节

注意这里没有 subquery,所以内容应该很简单

Selection-List 处理

select-list 如果是 empty,作者认为是全部输出(即 SELECT *),不懂 SQL 语法,这是真的吗?

inject_hidden

这里会先尝试给 select 去 inject_hidden,插入一些需要结果的 ast::Expr 或者 ast::Field,最后再通过 Projection 把这些字段给 Prune 掉。这个时候会利用之前说的 Column 字段。

这里会尝试:

  • 插入 HAVING 的内容
  • 插入 ORDER BY 的内容

inject_hidden 插入的时候,会有两个 ast::Expr:

  • Selection 的 expr 组
  • 需要插入的 expr

这个时候,大致逻辑如下:

  • 扫描 selection ,和需要插入的 expr 对比
    • 如果某项成员正好相等 (SELECT x .. ORDER BY x),那么就标记为 ast::expr::Column
    • 否则,访问 expr 树,找到对应的 Column Ref,然后替换成对应的上下文,比如 SELECT a .. HAVING a = 10 , a 替换为 Column(0)
  • 对于没有找到相似的,全部加入 selection, 然后表达式替换为 Column( 在 selection 中的位置)

Plan Agg

Plan Agg 是代码里面我看的最蛋疼的一部分,这个部分结果大概是:

1
2
Aggregation aggregates
- Projection aggregators, group-bys

Eg:

1
2
3
└─Aggregation: sum
└─ Projection: a, b + 2
└─ Filter: a > 0

Aggregation 前 aggregates 项是对应的,后面来自 GROUP-BY 子句

Group-BY 表达式的处理分成好几个阶段:

  • 从 Selection-List 中抽取 Aggregation
    • 把 Selection 中的表达式替换为对 Aggregation 的 Column-Ref, 这里相当于从 Select 里面抽出 expr. exprs 都是裸的 ast::expr. SELECT max(a) ... 抽成 ColumnRef(0) + MAX
    • 能抽成 Field-Ref 的尽量抽取成 Field-Ref,表达形式为 Column(idx)
  • 抽取 GROUP BY
    • 把 Selection 中的表达式替换为对 Group By 的 Column-Ref
  • 构建 Aggregator
    • 插入上面的表达式。这里会对 Scope 做一个 Projection,有点 hack,我还得消化一下
  • 再构建一个 Projection,拿到 Selection-List

剩余

  • Build Having
  • Build Order
  • Build Offset
  • Build Limit
  • inject_hidden 插入的隐藏列 Projection 掉