本文已收录 https://github.com/lkxiaolou/lkxiaolou 欢迎 star。

背景

Cobar

Cobar是阿里开源的数据库中间件，关于它的介绍这里不再赘述，可以参考之前的文章《Cobar SQL审计的设计与实现》

SQL

SQL是一种领域语言（编程语言），常用于关系型数据库，方便管理结构化数据。数据库执行 SQL 时先对 SQL 进行词法分析、语法分析、语义分析生成抽象语法树（Abstract Syntax Tree，简称AST），再被优化器处理生成执行计划，由执行引擎执行。

SQL Parser

将 SQL 解析为 AST 的解析器叫SQL Parser，开发这个解析器通常有两种方式：

• 通过工具自动生成

• 优点：简单易于实现

• 缺点：性能不佳，二次开发困难

• 手工编写

• 优点：性能好，代码清晰易于扩展

• 缺点：对开发人员要求高，需要了解编译原理

Cobar 中也实现了 SQL Parser，它在 Cobar 中的位置可以从它的架构图中看到

SQL Parser 之后是 SQL Router，可以推断出 SQL Parser 解析出 AST 的目的是为了分库分表的路由功能。

Cobar 的 SQL Parser 也经历了三个版本的迭代，本质是性能考虑：

1. 第一版：基于 JavaCC 生成 SQL parser，性能较差，优化不方便

2. 第二版：仿照 ANTLR 生成的 parser 结构手写，中间对象过多

3. 第三版：基于 LL(2)识别器手写

本文不对 SQL Parser 做过多的介绍，有兴趣可以参考这篇文章《比开源快30倍的自研SQL Parser设计与实践》，这篇文章我也仔细阅读了几遍，附上总结的脑图：

https://github.com/lkxiaolou/reading/tree/main/xmind

Cobar AST

Cobar 中的 SQL Parser 将 SQL 解析为 AST，为了直观感受，先举个例子：

select id,type from goods as g where type in (select type from type_config where status = 0)

经过 Cobar SQL Parser 后，生成了如下 AST 对象：

这个 AST 的根节点就是 select 语句，然后每个属性都是叶子节点，叶子节点的属性再分出叶子节点。可能有点绕，需要从代码层面感受。

AST 的 Node 定义如下，这里只有个 accept 方法，是为了遍历这棵树，暂时不管，后面会说到：

public interface ASTNode {    void accept(SQLASTVisitor visitor);}

实现这个 ASTNode 主要有这几个：

• SQLStatement：SQL 语句，比如 select、update、insert 等语句，体现在上图的 DMLSelectStatement

• Expression：表达式，比如 and、or、比较等语句，体现在 InExpression、ComparisionEqualsExpression、LiteralNumber、Identifier

• TableReference：table 相关语句，体现在 TableReferences、TableRefFactor

以 ComparisionEqualsExpression 的实现为例

其中 1 是比较的左右表达式，2 是判断符，这里是“=”，3 是计算该表达式。

evaluationInternal 如何实现？其实表达式被结构化和穷举之后这个问题变得简单，比如这里只需要取左右的数值，进行是否相等的比较即可。

AST 操作

有了如上对 AST 的了解，接下来看对 AST 的操作，最基本的是遍历，利用 ASTNode 的 accept，需要实现SQLASTVisitor接口，这个 SQLASTVisitor 定义如下：

其实是利用了 java 的多态，对每种 ASTNode 都定义了 visit 方法，遍历时不同对象对应到不同方法上。

比如MySQLOutputASTVisitor可以遍历 AST，将 AST 还原为 SQL 输出，只需要这样：

SQLStatement stmt = SQLParserDelegate.parse(sql);StringBuilder s = new StringBuilder();stmt.accept(new MySQLOutputASTVisitor(s));System.out.println(s.toString());

这样执行会输出

SELECT id, type FROM goods AS G WHERE type IN (SELECT type FROM type_config WHERE status = 0)

SQLParserDelegate.parse(sql)解析出来为 DMLSelectStatement 对象，它的 visit 方法实现如下：

@Overridepublic void accept(SQLASTVisitor visitor) {    visitor.visit(this);}

再看 MySQLOutputASTVisitor 的 visit(DMLSelectStatement node)实现：代码比较长，这里就不贴了，总体思路是遇到叶子节点就直接按格式存入 StringBuilder 中，否则继续调用相应节点的 accept 继续遍历，是一种深度遍历的思想。

我们可以参考 MySQLOutputASTVisitor 编写符合自己需求的遍历器。

AST 的应用

分库分表

Cobar 中利用 AST 可以获取 table 名、列名、比较的值进行分库分表，这也是 Cobar 最重要的功能。

SQL 特征生成

除此之外，我了解的 AST 还可以对原始 SQL 生成 SQL 特征，比如原始 SQL 是这样：

select id, name, age from user as u where age >= 20

或者是

select id, name, age from user as u where age >= 30

都可以被归一化为

select id, name, age from user as u where age >= ?

在进行 SQL 慢查询或其他的统计、针对 SQL 进行限流时非常有用。

危险 SQL 拦截

线上写了一条没有 where 条件的 update 或 delete，这时可以利用 AST 进行表达式计算，对没有 where 条件和 where 条件恒为 true 的 SQL 进行拦截。

最后

本文从 SQL AST 的来源、结构、遍历原理、应用等方面进行介绍，相信看完文章会对 SQL AST 有了初步的了解，如果想进一步了解可以参考 Cobar 项目中的单元测试进行实际的演示感受。

搜索关注微信公众号"捉虫大师"，后端技术分享，架构设计、性能优化、源码阅读、问题排查、踩坑实践。