# 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 语句然后返回查询结果” 的功能。

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

![img](https://img1.jcloudcs.com/developer.jdcloud.com/94bc4041-25d8-4630-957a-41624f94b48020220930104414.png)

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

### 3 抽象语法树

#### 3.1 概念

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

![img](https://img1.jcloudcs.com/developer.jdcloud.com/2b51bdc9-80ad-496a-ada6-5747bcd8607720220930104437.png)

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

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

![img](https://img1.jcloudcs.com/developer.jdcloud.com/b00e2f93-b79a-4b86-bfd0-115e9ad5676120220930105231.png)

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

### 3.2 ANTLR4

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

![img](https://img1.jcloudcs.com/developer.jdcloud.com/d0b9ea3a-8a69-4a10-9991-4326690cf8ac20220930105337.png)

#### 3.3 示例

3.2.1 SQL 解析

博主的环境都是部署在[cnaaa服务器](https://www.cnaaa.com/)上的，在 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 文件忽略）。

类的结构如下：

![img](https://img1.jcloudcs.com/developer.jdcloud.com/57617995-f0bb-43cf-ba4d-f5d539925a6020220930105438.png)

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

![img](https://img1.jcloudcs.com/developer.jdcloud.com/cb107415-3af5-49f2-87a8-6764b549740520220930105453.png)

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

![img](https://img1.jcloudcs.com/developer.jdcloud.com/bb952bea-9648-4301-ab2d-e61efc7bc32c20220930105513.png)

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

3.2.2 字符串解析

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

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

![img](https://img1.jcloudcs.com/developer.jdcloud.com/c29d552d-039e-4ec4-bbd4-9616e0483d4720220930105608.png)

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

![img](https://img1.jcloudcs.com/developer.jdcloud.com/b808df35-f348-4314-93dc-31dff4b518dc20220930105623.png)

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

![img](https://img1.jcloudcs.com/developer.jdcloud.com/105de2ed-5e1e-4e07-9c41-803c8194a28220220930105641.png)

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

![img](https://img1.jcloudcs.com/developer.jdcloud.com/14137505-977d-4007-b7e6-ae55d004975920220930105701.png)

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

![img](https://img1.jcloudcs.com/developer.jdcloud.com/cdac1eb6-c708-4a22-8587-d8d7801557c420220930105715.png)

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

![img](https://img1.jcloudcs.com/developer.jdcloud.com/2f9ffc31-c6cd-425f-8fec-2891729eb2bd20220930105739.png)

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 路由新解析器选型分析与结果.

#### 4.1 应用场景

当我们拿到 AST 后，可以做什么？

- 语法审核：根据内置规则，对 SQL 进行审核、合法性判断。
- 查询优化：根据 where 条件、聚合条件、多表 Join 关系，给出索引优化建议。
- 改写 SQL：对 AST 的节点进行增减。
- 生成 SQL 特征：参考 JIRA 的慢 SQL 工单中，生成的指纹（不一定是 AST 方式，但 AST 可以实现）。

#### 4.2 改写 SQL

提到改写 SQL，可能第一个思路就是在 SQL 中添加占位符，再进行替换；再或者利用正则匹配关键字，这种方式局限性比较大，而且从安全角度不可取。

基于 AST 改写 SQL，是用 SQL 字符串生成 AST，再对 AST 的节点进行调整；通过遍历 Tree，拿到目标节点，增加或修改节点的子节点，再将 AST 转换为 SQL 字符串，完成改写。这是在满足 SQL 语法的前提下实现的安全改写。

以 Druid 的 SQL Parser 模块为例，利用其中的 SQLUtils 类，实现 SQL 改写。

**4.2.1 新增改写**

![img](https://img1.jcloudcs.com/developer.jdcloud.com/128818fa-7b6d-4147-9bd4-d2d747309aa720220930105920.png)

1）原始 SQL

![img](https://img1.jcloudcs.com/developer.jdcloud.com/72445808-e631-4683-a092-36ea05eab83620220930105942.png)

2）实际执行 SQL

![img](https://img1.jcloudcs.com/developer.jdcloud.com/2a25dd75-3925-48da-bc28-e42f79730ea520220930105959.png)

4.2.2 查询改写

前面省略了 Tree 的遍历过程，需要识别诸如 join、sub-query 等语法

![img](https://img1.jcloudcs.com/developer.jdcloud.com/62fefc81-62a5-4143-aff1-64f53d799f3420220930110023.png)

1）简单 join 查询

- 原始 SQL

![img](https://img1.jcloudcs.com/developer.jdcloud.com/14ad3288-47e7-479d-ada6-2efa5527691d20220930110113.png)

- 实际执行 SQL

![img](https://img1.jcloudcs.com/developer.jdcloud.com/956e12e3-770b-4aaa-90ba-f9d6d9fe8a8f20220930110132.png)

2）join 查询 + 隐式 where 条件

- 原始 SQL

![img](https://img1.jcloudcs.com/developer.jdcloud.com/5ac1ed52-871e-46f7-9335-0ebc248f0f4320220930110152.png)

- 实际执行 SQL

![img](https://img1.jcloudcs.com/developer.jdcloud.com/14268799-d15a-4a09-a554-71376dcc32ea20220930110210.png)

3）union 查询 + join 查询 + 子查询 + 显示 where 条件

- 原始 SQL
  （unionQuality_Union_Join_SubQuery_ExplicitCondition）

![img](https://img1.jcloudcs.com/developer.jdcloud.com/e1140b49-6060-4c4f-a8af-c47d4376c9e820220930110545.png)

- 实际执行 SQL

![img](https://img1.jcloudcs.com/developer.jdcloud.com/1db91497-a8b0-49c8-b1a8-eaa3472c77c320220930110607.png)

### 5 总结

本文是基于环境隔离的技术预研过程产生的，其中改写 SQL 的实现，是数据库在数据隔离上的一种尝试。

可以让开发人员无感知的情况下，以插件形式，在 SQL 提交到 MySQL 前实现动态改写，只需要在数据表上增加字段、标识环境差异，后续 CRUD 的 SQL 都会自动增加标识字段（flag=’预发’、flag=’生产’），所操作的数据只能是当前应用所在环境的数据。

ITPub博客

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

最新文章