SQL解析器详解 - 哥不是小萝莉

2.1 SQL解析器是什么？

SQL解析与优化是属于编辑器方面的知识，与C语言这类编程语言的解析上是类似的。SQL解析主要包含：词法分析、语义语法分析、优化和执行代码生成、例如，我们非常熟悉的MySQL的一个SQL解析部分流程，如下图所以：

这里给大家介绍一下关于MySQL Lex和Bison生成的相关含义和具体负责的内容。

1.词法分析

SQL解析由词法分析和语法、语义分析两个部分组成。词法分析主要是把输入转化成若干个Token，其中Token包含key和非key。比如，一个简单的SQL如下所示：

SELECT age FROM user

在分析之后，会得到4个Token，其中有2个key，它们分别是SELECT、FROM。

SELECT

通常情况下，词法分析可以使用Flex来生成，但是我们熟悉的MySQL里面并没有使用该工具，而是手写了词法分析的部分（具体原因据说是为了效率和灵活性）。

MySQL在lex.h文件中对key进行了定义，下面是部分的key：

{"&&",         SYM(AND_AND_SYM)},
{"<",           SYM(LT)},
{"<=",         SYM(LE)},
{"<>",         SYM(NE)},
{"!=",          SYM(NE)},
{"=",           SYM(EQ)},
{">",           SYM(GE_SYM},
{">=",         SYM(GE)},
{"<<",         SYM(SHIFT_LEFT)},
{">>",         SYM(SHIFT_RIGHT)},
{"<=>",       SYM(EQUAL_SYM)},
{"ADD",        SYM(ADD)},
{"AFTER",     SYM(AFTER_SYM)},
{"AGGREGATE",       SYM(AGGREGATE_SYM)},
{"ALL",         SYM(ALL_SYM)},

2.语法分析

语法分析是生成语法树的过程，这是整个解析过程中最核心、最复杂的环节。不过，这部分MySQL使用了Bison来实现，即使如此，如何设计合适的数据结构和相关算法，以及存储和遍历所有的信息，也是值得我们去研究的。

例如，如下SQL语句：

SELECT name,age from user where age > 20 and age < 25 and gender = 'F'

解析上述SQL时会生成如下语法数：

2.2 ANTLR VS Calcite ?

2.2.1 ANTLR

ANTLR 是一个功能强大的语法分析生成器，可以用来读取、处理、执行和转换结构化文本或者二进制文件。在大数据的一些SQL框架里面有广泛的应用，比如Hive的词法文件是ANTLR3写的，Presto词法文件也是ANTLR4实现的，SparkSQL Lambda词法文件也是用Presto的词法文件改写的，另外还有HBase的SQL工具Phoenix也是用ANTLR工具进行SQL解析的。

使用ANTLR来实现一条SQL，执行或者实现的过程大致如下：

实现词法文件（g4）；

生成词法分析器和语法分析器；

生成抽象语法数（AST）；

遍历AST；

生成语义树；

优化生成逻辑执行计划；

生成物理执行计划再执行。

实例代码如下所示：

assign : ID '=' expr ';' ;

解析器的代码类似如下：

void assign(){
  match(ID);
  match('=');
  expr();
  match();        
1.Parser
Parser是用来识别语言的程序，其本身包含两个部分：词法分析器和语法分析器。词法分析阶段主要解决的问题是key以及各种symbols，比如INT或者ID。语法分析主要是基于词法分析的结果构造一颗语法分析树，如下图所示：
 因此，为了让词法分析和语法能够正常工作，在使用ANTLR4的时候，需要定义Grammar。
我们可以把CharStream转换成一颗AST，CharStream经过词法分析后会变成Token，TokenStream再最终组成一颗AST，其中包含TerminalNode和RuleNode，具体如下所示：
 2.Grammar
ANTLR官方提供了很多常用的语言的语法文件，可以进行膝盖后直接进行使用：
https://github.com/antlr/grammars-v4
在使用语法的时候，需要注意以下事项：
语法名称和文件名要一致；
语法分析器规则以小写字母开始；
词法分析器规则以大写字母开始；
用'string'单引号引出字符串；
不需要指定开始字符；
规则以分号结束；
 3.实例分析
这里我们使用IDEA来进行编写，使用IDEA中的ANTLR4相关插件来实现。然后创建一个Maven工程，在pom.xml文件中添加如下依赖：
<dependency>
    <groupId>org.antlr</groupId>
    <artifactId>antlr4</artifactId>
    <version>4.9.3</version>
</dependency>
然后，创建一个语法文件，内容如下所示：
grammar Expr;
prog : stat+;
stat: expr NEWLINE          # printExpr
    | ID '=' expr NEWLINE   # assign
    | NEWLINE               # blank
expr: expr op=('*'|'/') expr    # MulDiv
| expr op=('+'|'-') expr        # AddSub
| INT                           # int
| ID                            # id
| '(' expr ')'                  # parens
MUL : '*' ;
DIV : '/' ;
ADD : '+' ;
SUB : '-' ;
ID : [a-zA-Z]+ ;
INT : [0-9]+ ;
NEWLINE:'\r'? '\n' ;
WS : [ \t]+ -> skip;
上述语法文件很简单，本质含义就是一个递归下降，即定义一个表达式（expr），可以循环调用，也可以直接调用其他表达式，但是最终肯定会有一个最核心的表达式不能再继续往下调用了。以上语法文件在真正执行的时候会生成一颗AST，然后在IDEA中执行“Test Rule ...”，并在执行后的测试框中输入表达式“((1 + 2 ) + 3 - 4 * 5 ) / 6”，就会生成一颗AST了。AST如下图所示：
 整个语法文件的目的是为了让ANTLR生成相关的JAVA代码，我们设置生成visitor，然后，它们会生成如下文件：
ExprParser；
ExprLexer；
ExprBaseVisitor；
ExprVisitor。
ExprLexer是词法分析器，ExprParser是语法分析器。一个语言的解析过程一般是从词法分析到语法分析。这是ANTLR4为我们生成的框架代码，而我们需要做的事情就是实现一个Visitor，一般从ExprBaseVisitor来继承即可。生成的文件如下所示：
 然后，我编写一个自定义的实现计算类，代码如下所示：
public class ExprCalcVistor extends ExprBaseVisitor{
    public Integer visitAssign(ExprParser.AssignContext ctx) {
        String id = ctx.ID().getText();
        Integer value = (Integer) visit(ctx.expr());
        return value;
    @Override
    public Integer visitInt(ExprParser.IntContext ctx) {
        return Integer.valueOf(ctx.INT().getText());
    @Override
    public Integer visitMulDiv(ExprParser.MulDivContext ctx) {
        Integer left = (Integer) visit(ctx.expr(0));
        Integer right = (Integer) visit(ctx.expr(1));
        if (ctx.op.getType() == ExprParser.MUL){
            return left * right;
        }else{
            return left / right;
最后，执行主函数，代码如下所示：
public class ExprMain {
    public static void main(String[] args) throws IOException {
        ANTLRInputStream inputStream = new ANTLRInputStream("1 + 2 * 3");
        ExprLexer lexer = new ExprLexer(inputStream);
        CommonTokenStream tokenStream = new CommonTokenStream(lexer);
        ExprParser parser = new ExprParser(tokenStream);
        ParseTree parseTree = parser.prog();
        ExprCalcVistor visitor = new ExprCalcVistor();
        Integer rtn = (Integer) visitor.visit(parseTree);
        System.out.println("result: " + rtn);
2.2.2 Calcite
上述ANTLR内容演示了词法分析和语法分析的简单流程，但是由于ANTLR要实现SQL查询，需要自己定义词法和语法相关文件，然后再使用ANTLR的插件对文件进行编译，然后再生成代码。
而Apache Calcite的出现，大大简化了这些复杂工程，Calcite可以让用户很方便的给自己的系统套上一个SQL的外壳，并且提供足够高效的查询性能优化。
query language
query optimization
query execution
data management
data storage
上述这五个功能，通常是数据库系统包含的常用功能。Calcite在设计的时候就确定了自己只关注绿色的三个部分，而把下面数据管理和数据存储留给了外部的存储或者计算引擎。
数据管理和数据存储，尤其是数据存储是很复杂的，也会由于数据本身的特性导致实现上的多样性。Calcite弃用这2部分的设计，而是专注于上层更加通用的模块，使得自己能够足够的轻量化，系统复杂性得到控制，开发人员的专注点不会耗费太多时间。
同时，Calcite也没有去重复造轮子，能复用的东西，Calcite都会直接拿来复用。这也是让开发者能够去接受使用Calcite的原因之一，比如，如下例子：
示例1：作为一个SQL解析器，关键的SQL解析，Calcite没有重复造轮子，而是直接使用了开源的JavaCC，来将SQL语句转化为Java代码，然后进一步转成AST以供下一阶段使用；
示例2：为了支持后面会提到的灵活的元数据功能，Calcite需要支持运行时编译Java代码，默认的JavaC太重了，需要一个更加轻量级的编译器，Calcite同样没有选择造轮子，而是使用了开源的Janino方案。
 上面的图是Calcite官网给出的架构图，从图中我们可以知道，一方面印证了我们上面提到的，Calcite足够的简单，没有做自己不改做的事情；另一方面，也是更重要的，Calcite被设计的足够模块化和可插拔。
JDBC Client：这个模块用来支持使用JDBC Client的应用
SQL Parser and Validator：该模块用来做SQL解析和校验
Expressions Builder：用来支持自己做SQL解析和校验的框架对接
Operator Expressions：该模块用来处理关系表达式
Metadata Provider：该模块用来支持外部自定义元数据
Pluggable Rules：该模块用来定义优化规则
Query Optimizer：最核心的模块，专注于查询优化
功能模块的规划足够合理，也足够独立，使得不用完整的集成，而是可以只选择其中的一部分使用，而基本上每个模块都支持自定义，也使得用户能够更多的定制系统，如下表所示：
System
Query Language
JDBC Driver
SQL Parser and Validator
Execution Engine
Apache Flink
Streaming SQL
Native
Apache Hive
SQL+extensions
Tez, Spark
Apache Drill
SQL+extensions
Native
Apache Phoenix
HBase
Apache Kylin
HBase
上面列举的这些大数据常用的组件中Calcite均有集成，可以看到Hive就是自己做了SQL解析，只使用了Calcite的查询优化功能，而像Flink则是从解析到优化都直接使用了Calcite。
上面介绍的Calcite集成方法，都是把Calcite的模块当作库来使用，如果觉得太重量级，可以选择更简单的适配器功能。通过类似Spark这些框架来自定义的Source或Sink方式，来实现和外部系统的数据交互操作。
Adapter
Target Language
Cassandra
Pig Latin
Spark
Kafka
上图就是比较典型的适配器用法，比如通过Kafka的适配器就能直接在应用层通过SQL，而底层自动转换成Java和Kafka进行数据交互。
1.pom依赖
<dependency>
    <groupId>org.smartloli</groupId>
    <artifactId>jsql-client</artifactId>
    <version>1.0.2</version>
</dependency>
public static void main(String[] args) throws Exception {
        JSONObject tabSchema = new JSONObject();
        tabSchema.put("id", "integer");
        tabSchema.put("name", "varchar");
        tabSchema.put("age", "integer");
        String tableName = "stu";
        List<JSONArray> preRusult = new ArrayList<>();
        JSONArray dataSets = new JSONArray();
        for (int i = 0; i < 5000; i++) {
            JSONObject object = new JSONObject();
            object.put("id", i);
            object.put("name", "aa" + i);
            object.put("age", 10 + i);
            dataSets.add(object);
        preRusult.add(dataSets);
        String sql = "select count(*) as cnt from stu";
        JSONObject result = JSqlUtils.query(tabSchema, tableName, preRusult, sql);
        System.out.println(result);
3.Calcite实现KSQL查询Kafka
Kafka Eagle实现了SQL查询Kafka Topic中的数据，SQL操作Topic如下所示：
select * from efak_cluster_006 where `partition` in (0) limit 10
执行上图SQL语句，截图如下所示：
感兴趣的同学，可以关注Kafka Eagle官网，或者源代码。
4.结束语
这篇博客就和大家分享到这里，如果大家在研究学习的过程当中有什么问题，可以加群进行讨论或发送邮件给我，我会尽我所能为您解答，与君共勉！
另外，博主出书了《Kafka并不难学》和《Hadoop大数据挖掘从入门到进阶实战》，喜欢的朋友或同学， 可以在公告栏那里点击购买链接购买博主的书进行学习，在此感谢大家的支持。关注下面公众号，根据提示，可免费获取书籍的教学视频。