Cobar源码分析之AST

Cobar源码分析之AST

背景

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也经历了三个版本的迭代，本质是性能考虑：

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

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

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

本文不对SQL Parser做过多的介绍，这篇文章我也仔细阅读了几遍，附上总结的脑图：

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等语句，体现在上图的DMLSelectStatementExpression：表达式，比如and、or、比较等语句，体现在InExpression、ComparisionEqualsExpression、LiteralNumber、IdentifierTableReference：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方法实现如下：

@Override public 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项目中的单元测试进行实际的演示感受。