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 | /// Encodes SQL keys, using an order-preserving encoding - see kv::encoding for details. Options can |
对应 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 应该不是一个合理的方案。
- Column 有基本的
Parsing
这里的 Lexer 不太教科书,而是手工编写的一个识别器,我感觉用 flex 写一个没准还舒服些。
语法分析则是一个递归下降的 Parsing,语法结构如下:
1 | /// Parses an SQL statement |
可以从这个来推断出它的结构,这段应该是按照 standard 写的,还算有参考价值。对外产生最终的结构在目录 ast
下头,具体是一个 ast::Statement
.
特殊的,如果是 SELECT *
Planner
Planner 负责将 ast::Statement
转为 Plan
. 这部分 Plan / PlanNode 本身就是可以运行的了,通过走一个可选的 Optimizer 来进行优化。
这个地方没有一个 (单独的)Binder 阶段来 resolve name,
Plan Select
Scope
1 | /// Manages names available to expressions and executors, and maps them onto columns/fields. |
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
- 搜了下,function 处理中,可以参考这两个。toydb 类型处理感觉是比较简单的,function 和 ast::function 一一对应
- Column: 这个比较重要,放后面说,这个在它的 SQL 语法不存在,属于内部生成的
- Operation: 从 AND OR 到加减法等等
总之,这里会构建一份 Expression
FromTable ( TableRef ) 构建
- 采用
1 | build_from_clause: |
这个地方用到了 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 | Aggregation aggregates |
Eg:
1 | └─Aggregation: sum |
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)
- 把 Selection 中的表达式替换为对 Aggregation 的 Column-Ref, 这里相当于从 Select 里面抽出 expr.
- 抽取 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 掉