关于数据库:深入浅出-MatrixOne-Parser

作者：林俊洪  MO 研发工程师

▌Part 1 – 概述

数据库内核博大精深，但执行 SQL 的流程大同小异。

数据库内核能够拆分为:

• 接管 client 发送过去的网络包
• 解决网络包，将 SQL 解析成形象语法树
• 将语法树转换和优化成查问打算
• 通过查问打算生成执行打算，并执行返回后果

为什么说是博大精深呢？因为每个局部都有拿进去探讨和钻研的价值，各个厂家的数据库实现形式和细节也是花样百出。本文将次要探讨 SQL 是如果被解析成形象语法树的。简略来说，就是如何将 SQL 字符串如果解析成相应数据库语言的构造体。

▌Part 2 – 词法剖析

将 SQL 解析成语法树，首先须要进行词法剖析。词法剖析的过程简而言之是将 SQL 字符串拆解成若干个 token。例如，select a from t 咱们能够将其拆解成 select、a、from、t 这几个 token。而这些 token 能够作为语法分析的输出。

>>> DFA

MatrixOne 的 Lexer (词法分析器) 是手动编写的，相比于通过工具，比方 Lex，生成 Lexer，更加灵便，不便 MatrixOne parser 兼容 MySQL 语法。对于手动编写 Lexer，能够从有穷自动机说起。

有穷自动机（Finite Automata, FA）由两位神经物理学家 MeCuloch 和 Pitts 在 1948 年首先提出，是对一类解决零碎建设的数学模型。简略的定义是：给定输出串 x，如果存在一个对应于 x 的从初始状态到某个终止状态的转换序列，则称 x 被改 FA 接管。

首先，要辨认一个 token，能够通过正则匹配，例如整数的正则定义：

digit : 0|1|2|...|9 
integer : digit digit

实现正则匹配，能够通过 FA，举个例子，比方咱们要辨认正则文法 r = (a | b) * abb，状态转换图如下：

如此，当状态达到终止状态 3 时，辨认胜利。仔细观察能够发现一个问题，在 0 状态时，接管 a，能够从 0 到 0 或者从 0 到 1，这种不确定性无奈编程。称之为非确定的有穷状态机（NFA）。

给出一个论断，对任何 NFA，存在定义同一语言的确定的有穷自动机（DFA）。能够通过子集结构法将 NFA 转换成 DFA。

对于上述的例子，将 NFA 转换成 DFA 后的状态图如下：

从上图能够看出无论在哪一个状态接管 a 或 b，达到的下一个状态时确定的。
这样，通过对不同类型的 token 作出状态图，再将其整合，一个简略辨认 token DFA 如下：

对于 MySQL 的不同 token，比方 数字, 字符串，标识符，数学符号，正文等等，能够参照其定义，写出相应的 DFA，最终造成 Lexer。感兴趣的同学能够看看 MatrixOne 的 Lexer，实现在 scanner.go 中，在 mysql_lexer.go 中将其封装了起来。

▌Part 3 – 语法分析

词法剖析后 tokens 将作为语法分析的输出。SQL 的语法解析的实现常见有两种形式：
一种是采纳 LL 文法 ，自顶向下的剖析。手动编写的 parser 个别会采取这种形式，比方 clickhouse 的 parser、sqlparser-rs。
另一种是采纳 LR 文法，自底向上剖析。一些工具 bison、goyacc 能够通过事后定义好的 BNF 文件生成语法解析器。

这两种形式有各自的优缺点，实践上性能相差不大。手动编写的语法分析易于调试，代码直观不言而喻，但也因其手动编写，开发工夫会较长。MatrixOne 的语法分析器应用 goyacc 生成的，目前次要兼容 MySQL 语法。能够通过 MySQL 给出的相干文档，定义出 BNF 文件（.y 文件），生成解析器。当然生成的解析器代码难以浏览调试。

>>> 工作过程

goyacc 生成的语法分析器，承受 LALR(1)（lookahead-LR）文法。与 LL 文法不同，承受 LALR(1) 文法的分析器，其语法分析是从分析树的底部向顶部方向结构分析树，对于 LARL(1)

• L：对输出进行从左到右的扫描
• R：反向结构出一个最右推导序列
• 1 则是须要向前查看 1 个 token

自底向上的语法分析采纳最左规约的形式，通用框架是移入 - 规约剖析（Shift-Reduce Parsing）。

移入 - 规约分析器可采取的 4 种动作：

• 移入：将下一个 token 移到栈的顶端
• 归约：如果栈中的符号串是某个产生式的左端，则归约成右端，被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串
• 接管：胜利实现语法分析过程
• 谬误：发现一个语法错误

移入 - 规约剖析的工作过程：

• 语法分析器将 0 个或多个输出 token 移入栈的顶端，直到能够对栈顶的一个文法符号串 β 进行归约为止。
• 而后，β 归约为某个产生式的左部
• 语法分析器一直地反复这个循环，直到检测到一个语法错误，或者栈中蕴含了开始符号且输出缓冲区为空（语法分析胜利）为止。

举个例子，剖析如下表达式 E 语法时：

id + (id + id)

能够定义出如下产生式，其中表达式 E 是非终结符，id、+、-、(,) 是终结符：

E : E + E
E : E * E
E : (E)
E : id

通过移入 - 规约剖析，能够得出表达式语法正确：

>>> 抵触

如果某些输出字符串能够按两种或以上的形式来结构，那么能够说这组文法存在二义性。还是看上文所说到的一个例子，对于产生式

E : E + E

是表白算数表达式的一种天然的形式。但这种递归定义的形式并没有齐全规定所有简单输出的状况，比方，输出是：

a + b + c

如果是左联合，则被结构为：

(a + b) + c

如果是右联合，则被结构为：

a + (b + c)

语法分析器遇到这种状况是能检测到歧义的，当语法分析器读到 b 时，栈中可见的输出是：

a + b

匹配上述文法规定的右端，进行归约操作。在利用则个规定后，栈中输出被规约成 E，语法分析器接着能够读取后续局部:

+ c

并再次归约，产生左联合。但语法分析器能够抉择 lookahead 1，直到读完：

a + b + c

而后对 b + c 进行归约，变成

a + E

最初再次归约，产生右联合。实际上，语法分析器在遇到 b 时，能够抉择移进或者归约，无奈抉择时，产生移进 / 归约抵触。而右联合时，语法分析器抉择两个归约动作，产生归约 / 归约抵触。

实际上，咱们能够在 BNF 文件中补充规定。算术表达式中，罕用优先级，左或右联合来补充规定，以此来打消掉一些歧义，比方，能够定义：

%left '+' '-'
%left '*' '/'

将加减乘除都定义成左联合，其次在 BNF 文件中，越晚（靠下）定义的 token，优先级越高。显然，乘除的优先级高于加减。

▌Part 4 – MatrixOne Parser

MO Parser 的词法剖析是手动编写的，次要的作用就是分词，为语法分析器提供 token。数据库语法分析其实就是生成语法树的过程，也是整个 SQL 解析的重点。在 mysql_sql.y 中定义了 MatrixOne 的语法规定，规定文件的构造如下：

%{// 在这里能够引入包名，在解析的过程中就能够调用到相应的函数}%

%struct {
    id int // token id
    str string // token 字符串
    item interface{} // 将 token 转化为理论的类型，比方 1 会转化成 int64 类型}

%union {
// 在这里定义 mo 设计好的语法树结构，比方
    selectStatement tree.SelectStatement
}

// 这里定义一系列的终结符，即 token。goyacc 会生成对应的 token id，比方
%token<str> SELECT

// 接着定义一系列非终结符。能够用 %union 中的字段来定义，goyacc 会做相应的映射，比方
%type <selectStatement> simple_select_clause

%%
// 在这编写 BNF，为了兼容 MySQL 语法，语法规定会参考 MySQL，当然，也会有 MatrixOne 本人的一些语法
// 比方 simple_select_clause 的一部分定义

simple_select_clause:
    SELECT distinct_opt select_expression_list from_opt where_expression_opt group_by_opt having_opt
    {
        $$ = &tree.SelectClause{
            Distinct: $2,
            Exprs: $3,
            From: $4,
            Where: $5,
            GroupBy: $6,
            Having: $7,
        }
    }
%%

在 select.go 中能够看到简略的 select 的局部定义 SelectClause

type SelectClause struct {
    SelectStatement
    Distinct bool
    Exprs    SelectExprs
    From     *From
    Where    *Where
    GroupBy  GroupBy
    Having   *Where
    Option   string
}

当胜利解析完 SQL，MO 定义的构造体里的字段都会被相应赋值。比方，解析 SQL：

select a, b from t1 where a > 3 and b = 4;

会生成如下语法树：

接着，就能够将语法树转化和优化成逻辑打算。

相熟了 MO 的语法树后，欢送大家为 MO Parser 兼容更多的 MySQL 语法。批改了 mysql_sql.y 后，进入到 parsers 目录下执行 make，就会生成新的语法分析器，该文件是 mysql_sql.go。

最初，一个简略的例子，应用 MO Parser 进行 SQL 解析：

package main

import (
    "fmt"

    "github.com/matrixorigin/matrixone/pkg/sql/parsers"
    "github.com/matrixorigin/matrixone/pkg/sql/parsers/dialect"
    "github.com/matrixorigin/matrixone/pkg/sql/parsers/tree"
)

func main() {sql := `select u.a, (select t.a from sa.t, u) from u, (select t.a, u.a from sa.t, u where t.a = u.a) as t where (u.a, u.b, u.c) in (select t.a, u.a, t.b * u.b as tubb from t)`
    // 也能够调用 parsers.Parse(dialect.MySQL, sqls), 进行多条 sql 解析
    ast, err := parsers.ParseOne(dialect.MYSQL, sql)
    if err != nil {fmt.Println(err)
    }
    fmt.Println(tree.String(ast, dialect.MYSQL))
}

能够留神到，Parse 须要传入 dialect.MySQL 参数，这是因为 MO Parser 在开始设计时，就有反对多方言的想法，目前实现了多方言的框架。

矩阵起源全面拥抱开源生态，以开源凋谢的形式摸索数字化路线。欢送扫码退出 MatrixOne 社群参加探讨：

MO 社群 ：增加 MO 小助手微信 → ID：MatrixOrigin001，退出 MatrixOne 社群
官网 ：matrixorigin.cn
源码 ：github.com/matrixorigin/matrixone
Slack：matrixoneworkspace.slack.com
知乎 | CSDN | 墨天轮 | OSCHINA | InfoQ：MatrixOrigin