SQL 抽象语法树及改写场景应用

1 背景

我们平时会写各种各样或简单或复杂的 sql 语句，提交后就会得到我们想要的结果集。比如 sql 语句，”select * from t_user where user_id > 10;”，意在从表 t_user 中筛选出 user_id 大于 10 的所有记录。你有没有想过从一条 sql 到一个结果集，这中间经历了多少坎坷呢？

2 SQL 引擎

从 MySQL、Oracle、TiDB、CK，到 Hive、HBase、Spark，从关系型数据库到大数据计算引擎，他们大都可以借助 SQL 引擎，实现 “接受一条 sql 语句然后返回查询结果” 的功能。

他们核心的执行逻辑都是一样的，大致可以通过下面的流程来概括：

中间蓝色部分则代表了 SQL 引擎的基本工作流程，其中的词法分析和语法分析，则可以引申出 “抽象语法树” 的概念。

3 抽象语法树

3.1 概念

高级语言的解析过程都依赖于解析树（Parse Tree），抽象语法树（AST，Abstract Syntax Tree）是忽略了一些解析树包含的一些语法信息，剥离掉一些不重要的细节，它是源代码语法结构的一种抽象表示。以树状的形式表现编程语言的结构，树的每个节点 ASTNode 都表示源码中的一个结构；AST 在不同语言中都有各自的实现。

解析的实现过程这里不去深入剖析，重点在于当 SQL 提交给 SQL 引擎后，首先会经过词法分析进行 “分词” 操作，然后利用语法解析器进行语法分析并形成 AST。

下图对应的 SQL 则是 “select username,ismale from userInfo where age>20 and level>5 and 1=1”;

这棵抽象语法树其实就简单的可以理解为逻辑执行计划了，它会经过查询优化器利用一些规则进行逻辑计划的优化，得到一棵优化后的逻辑计划树，我们所熟知的 “谓词下推”、“剪枝” 等操作其实就是在这个过程中实现的。得到逻辑计划后，会进一步转换成能够真正进行执行的物理计划，例如怎么扫描数据，怎么聚合各个节点的数据等。最后就是按照物理计划来一步一步的执行了。

3.2 ANTLR4

解析（词法和语法）这一步，很多 SQL 引擎采用的是 ANTLR4 工具实现的。ANTLR4 采用的是构建 G4 文件，里面通过正则表达式、特定语法结构，来描述目标语法，进而在使用时，依赖语法字典一样的结构，将 SQL 进行拆解、封装，进而提取需要的内容。下图是一个描述 SQL 结构的 G4 文件。

3.3 示例

3.2.1 SQL 解析

博主的环境都是部署在cnaaa服务器上的，在 java 中的实现一次 SQL 解析，获取 AST 并从中提取出表名。

首先引入依赖：

<dependency>
    <groupId>org.antlr</groupId>
    <artifactId>antlr4-runtime</artifactId>
    <version>4.7</version>
</dependency>

在 IDEA 中安装 ANTLR4 插件；

示例 1，解析 SQL 表名。

使用插件将描述 MySQL 语法的 G4 文件，转换为 java 类（G4 文件忽略）。

类的结构如下：

其中 SqlBase 是 G4 文件名转换而来，SqlBaseLexer 的作用是词法解析，SqlBaseParser 是语法解析，由它生成 AST 对象。HelloVisitor 和 HelloListener：进行抽象语法树的遍历，一般都会提供这两种模式，Visitor 访问者模式和 Listener 监听器模式。如果想自己定义遍历的逻辑，可以继承这两个接口，实现对应的方法。

读取表名过程，是重写 SqlBaseBaseVisitor 的几个关键方法，其中 TableIdentifierContext 是表定义的内容；

SqlBaseParser 下还有 SQL 其他 “词语” 的定义，对应的就是 G4 文件中的各类描述。比如 TableIdentifierContext 对应的是 G4 中 TableIdentifier 的描述。

3.2.2 字符串解析

上面的 SQL 解析过程比较复杂，以一个简单字符串的解析为例，了解一下 ANTLR4 的逻辑。

1）定义一个字符串的语法：Hello.g4

2）使用 IDEA 插件，将 G4 文件解析为 java 类

3）语法解析类 HelloParser，内容就是我们定义的 h 和 world 两个语法规则，里面详细转义了 G4 文件的内容。

4）HelloBaseVisitor 是采用访问者模式，开放出来的接口，需要自行实现，可以获取 xxxParser 中的规则信息。

5）编写测试类，使用解析器，识别字符串 “hi abc”：

6）调试后发现命中规则 h，解析为 Hi 和 abc 两部分。

7）如果是 SQL 的解析，则会一层层的获取到 SQL 中的各类关键 key。

4 SqlParser

利用 ANTLR4 进行语法解析，是比较底层的实现，因为 Antlr4 的结果，只是简单的文法解析，如果要进行更加深入的处理，就需要对 Antlr4 的结果进行更进一步的处理，以更符合我们的使用习惯。

利用 ANTLR4 去生成并解析 AST 的过程，相当于我们在写 rpc 框架前，先去实现一个 netty。因此在工业生产中，会直接采用已有工具来实现解析。

Java 生态中较为流行的 SQL Parser 有以下几种（此处摘自网络）：

fdb-sql-parser 是 FoundationDB 在被 Apple 收购前开源的 SQL Parser，目前已无人维护。
jsqlparser 是基于 JavaCC 的开源 SQL Parser，是 General SQL Parser 的 Java 实现版本。
Apache calcite 是一款开源的动态数据管理框架，它具备 SQL 解析、SQL 校验、查询优化、SQL 生成以及数据连接查询等功能，常用于为大数据工具提供 SQL 能力，例如 Hive、Flink 等。calcite 对标准 SQL 支持良好，但是对传统的关系型数据方言支持度较差。
alibaba druid 是阿里巴巴开源的一款 JDBC 数据库连接池，但其为监控而生的理念让其天然具有了 SQL Parser 的能力。其自带的 Wall Filer、StatFiler 等都是基于 SQL Parser 解析的 AST。并且支持多种数据库方言。

Apache Sharding Sphere (原当当 Sharding-JDBC，在 1.5.x 版本后自行实现)、Mycat 都是国内目前大量使用的开源数据库中间件，这两者都使用了 alibaba druid 的 SQL Parser 模块，并且 Mycat 还开源了他们在选型时的对比分析 Mycat 路由新解析器选型分析与结果.