SQL解析器详解

1.概述

最近,有同学留言关于SQL解析器方面的问题,今天笔者就为大家分享一下SQL解析器方便的一些内容。

2.内容

2.1 SQL解析器是什么?

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

SQL解析器详解

 

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

1.词法分析

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

SELECT age FROM user

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

key 非key key 非key
SELECT age FROM user

通常情况下,词法分析可以使用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时会生成如下语法数:

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,执行或者实现的过程大致如下:

  1. 实现词法文件(g4);
  2. 生成词法分析器和语法分析器;
  3. 生成抽象语法数(AST);
  4. 遍历AST;
  5. 生成语义树;
  6. 优化生成逻辑执行计划;
  7. 生成物理执行计划再执行。

实例代码如下所示:

assign : ID '=' expr ';' ;

解析器的代码类似如下:

void assign(){
  match(ID);
  match('=');
  expr();
  match();        
}

 

1.Parser

Parser是用来识别语言的程序,其本身包含两个部分:词法分析器和语法分析器。词法分析阶段主要解决的问题是key以及各种symbols,比如INT或者ID。语法分析主要是基于词法分析的结果构造一颗语法分析树,如下图所示:

SQL解析器详解

 

 因此,为了让词法分析和语法能够正常工作,在使用ANTLR4的时候,需要定义Grammar。

我们可以把CharStream转换成一颗AST,CharStream经过词法分析后会变成Token,TokenStream再最终组成一颗AST,其中包含TerminalNode和RuleNode,具体如下所示:

SQL解析器详解

 

 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如下图所示:

SQL解析器详解

 

 整个语法文件的目的是为了让ANTLR生成相关的JAVA代码,我们设置生成visitor,然后,它们会生成如下文件:

  • ExprParser;
  • ExprLexer;
  • ExprBaseVisitor;
  • ExprVisitor。

ExprLexer是词法分析器,ExprParser是语法分析器。一个语言的解析过程一般是从词法分析到语法分析。这是ANTLR4为我们生成的框架代码,而我们需要做的事情就是实现一个Visitor,一般从ExprBaseVisitor来继承即可。生成的文件如下所示:

SQL解析器详解

 

 然后,我编写一个自定义的实现计算类,代码如下所示:

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方案。

SQL解析器详解

 

 上面的图是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 SQL HBase
Apache Kylin SQL HBase
... ... ... ... ...

 

上面列举的这些大数据常用的组件中Calcite均有集成,可以看到Hive就是自己做了SQL解析,只使用了Calcite的查询优化功能,而像Flink则是从解析到优化都直接使用了Calcite。

上面介绍的Calcite集成方法,都是把Calcite的模块当作库来使用,如果觉得太重量级,可以选择更简单的适配器功能。通过类似Spark这些框架来自定义的Source或Sink方式,来实现和外部系统的数据交互操作。

Adapter Target Language
Cassandra CQL
Pig Pig Latin
Spark RDD
Kafka Java 
... ...

上图就是比较典型的适配器用法,比如通过Kafka的适配器就能直接在应用层通过SQL,而底层自动转换成Java和Kafka进行数据交互。

1.pom依赖

<dependency>
    <groupId>org.smartloli</groupId>
    <artifactId>jsql-client</artifactId>
    <version>1.0.2</version>
</dependency>

2.实例

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语句,截图如下所示:

SQL解析器详解

 

感兴趣的同学,可以关注Kafka Eagle官网,或者源代码

4.结束语

这篇博客就和大家分享到这里,如果大家在研究学习的过程当中有什么问题,可以加群进行讨论或发送邮件给我,我会尽我所能为您解答,与君共勉!

另外,博主出书了《Kafka并不难学》和《Hadoop大数据挖掘从入门到进阶实战》,喜欢的朋友或同学, 可以在公告栏那里点击购买链接购买博主的书进行学习,在此感谢大家的支持。关注下面公众号,根据提示,可免费获取书籍的教学视频。

上一篇:04-PG数据库的语法解析


下一篇:[ pikachu ] 靶场通关之 XSS (六) --- 什么是 Xss 之盲打 ?