ToyDB Query Parsing

mwish

2023-06-07

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 的事务引擎上，存储内容如下：

/// 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，语法结构如下：

/// 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

/// 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
- 搜了下，function 处理中，可以参考这两个。toydb 类型处理感觉是比较简单的，function 和 ast::function 一一对应
  - https://www.postgresql.org/docs/current/sql-expressions.html
  - https://duckdb.org/docs/sql/functions/date
Column: 这个比较重要，放后面说，这个在它的 SQL 语法不存在，属于内部生成的
Operation: 从 AND OR 到加减法等等

总之，这里会构建一份 Expression

FromTable ( TableRef ) 构建

采用

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 掉