SQL引擎如何把语句转换为一个抽象语法树

DLab数据实验室 2021-07-19

521

导读："select * from tb_user where userid > 10;"这是再简单不过的一条sql语句，从表tb_user中筛选出userid大于10的所有记录。我们平时会写各种各样或简单或复杂的sql语句，然后不一会儿就会得到我们想要的结果集。但是你有没有想过从一条sql到一个结果集，这中间经历了多少坎坷呢？

作者：小舰学长中国人民大学计算机硕士

来源：DLab数据实验室（ID：rucdlab）

SQL引擎

小到传统的单机数据库，大到分布式数据库、大数据计算引擎，他们大都可以借助SQL引擎完成“接受一条sql语句然后返回查询结果”的功能。单机数据库可能处理的数据量有限，而大数据计算引擎补充了对海量数据的查询能力。但是他们核心的执行逻辑都是一样的，大致可以通过下面的流程来概括：

我们本次要讨论的就是前两个模块：词法分析和语法分析形成抽象语法树（AST）的内容。

抽象语法树

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

简单的描述了一下SQL引擎等执行流程，我们来着重分析一下前两个阶段吧：词法分析->语法分析->AST

很多的SQL引擎都是借助ANTLR工具来协助进行语法解析，查询引擎presto就是用的antlr做底层sql语法解析的，我们只需要定义好一个语法文件（一般以.g4后缀结束)，就可以利用ANTLR工具来进行词法语法解析代码的生成了。

简单示例

先举个简单的小例子：

首先定义一个简单的语法文件：Hello.g4

这个文件中，grammar Hello中的Hello就是一个语法文件，跟我们的Hello.g4的Hello是同一个名字。

在这里面，通过小写来定义规则，例如这里我其实定义了两个规则，一个是检测以“Hello”或者“hello”开头，紧跟一个由小写字母构成的词的规则“r“，另一个是匹配‘i love you'或者‘you love me’的短语的规则“love”。如果你用的是Intellij IDEA并且由ANLTR插件的话，通过右键然后选择Configure ANLTR就会生成词法语法解析的对应类（如下图），其中核心的几个类有HelloLexer、HelloParser、HelloVisitor和HelloListener。

其中，这几个重要的类的作用如下：

HelloLexer：词法解析，可以理解为将sql分割为token；

HelloParser：语法解析，将词法解析的结果进行语法解析，从而形成一棵抽象语法树（AST）；

HelloVisitor和HelloListener：进行抽象语法树的遍历，一般都会提供这两种模式，Visitor访问者模式和Listener监听器模式。如果想自己定义遍历的逻辑，可以继承这两个接口，实现对应的方法。

有了这几个类的保证，我们其实就可以简单使用一下我们定义好的规则了。

我们来看一段简单的代码：

这段代码就是使用我们的两个规则的实例：

对于读入的sql表达式先通过Lexer进行词法分析形成tokens，然后通过Parser创建parser对象，对parser对象应用我们的语法规则“r”或“love”后生成对应的抽象语法树。

例如我们先只应用规则“r“，也就是匹配”Hello/hello ***“，我们可以看到输入i love you会在应用规则的时候被检测出不匹配，而输入hello world则可以通过，从而形成一棵AST。

我们看到我们可以通过对AST应用Visit方法来进行遍历，上面展示的是最原始最简单的语法树遍历，只有两个节点，分别是hello和world的内容。

SQL引擎

有了上面的基础，我们就可以看一下SQL引擎是怎样实现的，其实跟上面的例子流程几乎一样，只是每个环节的内容都多了点而已，我们以Presto引擎的词法语法解析来看：

很显然，它也是需要有一个SqlBase.g4语法文件，然后里面会定义一些规则、变量等；

他也会生成这么几个重要的类：

然后它的调用也是如出一辙：

然后对生成的AST进行遍历

再往下就是各种visit的实现了，由于sql语法树节点类型众多，因此会有很多不同的visit实现，下面展示的也只是其中的一部分，每个visit方法会对sql语句中涉及到该部分的模块单独拿来进行遍历、分析。

例如下面这段，就是对于join算子的遍历解析，上来会先判断Join的类型是否是自然连接，如果是自然连接则直接抛出”不支持自然连接“的异常。

当一条sql语句的AST被遍历了个遍之后，该条语句的信息其实也已经被引擎掌握了，就会生成对应的逻辑计划，然后再进一步生成物理计划，最后真正的被引擎执行。

总结

以上就是一条sql语句进行sql引擎后进行词法语法解析形成AST的过程，其实无论是开始讲的简单例子也好，后面分析的Presto引擎也好，他们都是相同的道理。至于.g4中的语法规则，目前Presto支持ANSI SQL的词法和语义支持，不同的SQL引擎可能会支持不同的标准，例如Hive SQL是一种类SQL的查询表达，如果体现在这里的话，可能就是.g4文件的规则内容会有所不同了～～

数据库

文章转载自DLab数据实验室，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

SQL引擎如何把语句转换为一个抽象语法树

简单示例

评论