关于sql:如何实现一个SQL解析器

作者：vivo 互联网搜寻团队- Deng Jie

一、背景

随着技术的一直的倒退，在大数据畛域呈现了越来越多的技术框架。而为了升高大数据的学习老本和难度，越来越多的大数据技术和利用开始反对SQL进行数据查问。SQL作为一个学习老本很低的语言，反对SQL进行数据查问能够升高用户应用大数据的门槛，让更多的用户可能应用大数据。

本篇文章次要介绍如何实现一个SQL解析器来利用的业务当中，同时联合具体的案例来介绍SQL解析器的实际过程。

二、为什么须要SQL解析器？

在设计我的项目零碎架构时，咱们通常会做一些技术调研。咱们会去思考为什么须要SQL解析器？怎么判断抉择的 SQL 解析器能够满足以后的技术要求？

2.1 传统的SQL查问

传统的SQL查问，依赖残缺的数据库协定。比方数据存储在MySQL、Oracle等关系型数据库中，有规范的SQL语法。咱们能够通过不同的SQL语句来实现业务需要，如下图所示：

然而，在解决海量数据的时候，关系型数据库是难以满足理论的业务需要的，咱们须要借助大数据生态圈的技术组件来解决理论的业务需要。

2.2 理论利用场景

在应用大数据生态圈的技术组件时，有些技术组件是自带SQL的，比方Hive、Spark、Flink等；而有些技术组件自身是不带SQL的，比方Kafka、HBase。上面，咱们能够通过比照不带SQL和应用SQL解析器后的场景，如下图所示：

从上图中，咱们能够看到，图右边在咱们应用不带SQL的技术组件时，实现一个查问时，须要咱们编写不同的业务逻辑接口，来与Kafka、HBase这些技术组件来进行数据交互。如果随着这类组件的减少，查问性能复杂度的减少，那边每套接口的复杂度也会随之减少，对于后续的扩大和保护也是很不不便的。而图左边在咱们引入SQL解析器后，只须要一套接口来实现业务逻辑，对于不同的技术组件进行适配即可。

三、什么是SQL解析器？

在抉择SQL解析器利用到咱们理论的业务场景之前，咱们先来理解一下SQL解析器的外围知识点。

3.1 SQL解析器蕴含哪些内容？

在应用SQL解析器时，解析SQL的步骤与咱们解析Java/Python程序的步骤是十分的类似的，比方：

在C/C++中，咱们能够应用LEX和YACC来做词法剖析和语法分析
在Java中，咱们能够应用JavaCC或ANTLR

在咱们应用解析器的过程当中，通常解析器次要包含三局部，它们别离是：词法解析、语法解析、语义解析。

3.1.1 什么词法解析？

如何了解词法解析呢？词法解析咱们能够这么来进行了解，在启动词法解析工作时，它将从左到右把字符一个个的读取并加载到解析程序外面，而后对字节流进行扫描，接着依据构词规定辨认字符并切割成一个个的词条，切词的规定是遇到空格进行宰割，遇到分号时完结词法解析。比方一个简略的SQL如下所示：

SQL示例

SELECT name FROM tab;

通过词法解析后，后果如下所示：

3.1.2 什么是语法解析？

如何了解语法解析呢？语法解析咱们能够这么来进行了解，在启动语法解析工作时，语法分析的工作会在词法剖析的后果上将词条序列组合成不同语法短句，组成的语法短句将与相应的语法规定进行适配，若适配胜利则生成对应的形象语法树，否则报会抛出语法错误异样。比方如下SQL语句：

SQL示例

SELECT name FROM tab WHERE id=1001;

约定规定如下：

上表中，红色的内容通常示意终结符，它们个别是大写的关键字或者符号等，小写的内容是非终结符，个别用作规定的命名，比方字段、表名等。具体AST数据结构如下图所示：

3.1.3 什么是语义解析？

如何了解语义解析呢？语义解析咱们能够这么来进行了解，语义剖析的工作是对语法解析失去的形象语法树进行无效的校验，比方字段、字段类型、函数、表等进行查看。比方如下语句：

SQL示例

SELECT name FROM tab WHERE id=1001;

上述SQL语句，语义剖析工作会做如下查看：

SQL语句中表名是否存在；
字段name是否存在于表tab中；
WHERE条件中的id字段类型是否能够与1001进行比拟操作。

上述查看完结后，语义解析会生成对应的表达式供优化器去应用。

四、如何抉择SQL解析器？

在理解了解析器的外围知识点后，如何抉择适合的SQL解析器来利用到咱们的理论业务当中呢？上面，咱们来比照一下支流的两种SQL解析器。它们别离是ANTLR和Calcite。

4.1 ANTLR

ANTLR是一款功能强大的语法分析器生成器，能够用来读取、解决、执行和转换结构化文本或者二进制文件。在大数据的一些SQL框架外面有有宽泛的利用，比方Hive的词法文件是ANTLR3写的，Presto词法文件也是ANTLR4实现的，SparkSQLambda词法文件也是用Presto的词法文件改写的，另外还有HBase的SQL工具Phoenix也是用ANTLR工具进行SQL解析的。

应用ANTLR来实现一条SQL，执行或者实现的过程大抵是这样的，实现词法文件（.g4），生成词法分析器和语法分析器，生成形象语法树（也就是我常说的AST），而后再遍历形象语法树，生成语义树，拜访统计信息，优化器生成逻辑执行打算，再生成物理执行打算去执行。

官网示例：

ANTLR表达式

assign : ID '=' expr ';' ;

解析器的代码相似于上面这样：

ANTLR解析器代码

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

4.1.1 Parser

Parser是用来辨认语言的程序，其自身蕴含两个局部：词法分析器和语法分析器。词法分析阶段次要解决的问题是关键字以及各种标识符，比方INT（类型关键字）和ID（变量标识符）。语法分析次要是基于词法剖析的后果，结构一颗语法分析数，流程大抵如下：

因而，为了让词法剖析和语法分析可能失常工作，在应用ANTLR4的时候，须要定义语法（Grammar）。

咱们能够把字符流（CharStream），转换成一棵语法分析树，字符流通过词法剖析会变成Token流。Token流再最终组装成一棵语法分析树，其中蕴含叶子节点（TerminalNode）和非叶子节点（RuleNode）。具体语法分析树如下图所示：

4.1.2 Grammar

ANTLR官网提供了很多罕用的语言的语法文件，能够进行批改后间接进行复用：https://github.com/antlr/grammars-v4

在应用语法的时候，须要留神以下事项：

语法名称和文件名要统一；
语法分析器规定以小写字母开始；
词法分析器规定以大写字母开始；
用'string'单引号引出字符串；
不须要指定开始符号；
规定以分号完结；
...

4.1.3 ANTLR4实现简略计算性能

上面通过简略示例，阐明ANTLR4的用法，须要实现的性能成果如下：

ANTLR示例

1+2 => 1+2=31+2*4 => 1+2*4=91+2*4-5 => 1+2*4-5=41+2*4-5+20/5 => 1+2*4-5+20/5=8(1+2)*4 => (1+2)*4=12

通过ANTLR解决流程如下图所示：

整体来说一个准则，递归降落。即定义一个表达式(如expr)，能够循环调用间接也能够调用其余表达式，然而最终必定会有一个最外围的表达式不能再持续往下调用了。

步骤一：定义词法规定文件（CommonLexerRules.g4）

CommonLexerRules.g4

// 定义词法规定lexer grammar CommonLexerRules; //////// 定义词法// 匹配IDID     : [a-zA-Z]+ ;// 匹配INTINT    : [0-9]+    ;// 匹配换行符NEWLINE: '\n'('\r'?);// 跳过空格、跳格、换行符WS     : [ \t\n\r]+ -> skip; //////// 运算符DIV:'/';MUL:'*';ADD:'+';SUB:'-';EQU:'=';

步骤二：定义语法规定文件（LibExpr.g4）

LibExpr.g4

// 定于语法规定grammar LibExpr; // 导入词法规定import CommonLexerRules; // 词法根prog:stat+ EOF?; // 定义申明stat:expr (NEWLINE)?         # printExpr    | ID '=' expr (NEWLINE)? # assign    | NEWLINE                # blank    ; // 定义表达式expr:expr op=('*'|'/') expr # MulDiv    |expr op=('+'|'-') expr # AddSub    |'(' expr ')'           # Parens    |ID                     # Id    |INT                    # Int    ;

步骤三：编译生成文件

如果是Maven工程，这里在pom文件中增加如下依赖：

ANTLR依赖JAR

<dependencies>    <dependency>        <groupId>org.antlr</groupId>        <artifactId>antlr4</artifactId>        <version>4.9.3</version>    </dependency>    <dependency>        <groupId>org.antlr</groupId>        <artifactId>antlr4-runtime</artifactId>        <version>4.9.3</version>    </dependency></dependencies>

而后，执行Maven编译命令即可：

Maven编译命令

mvn generate-sources

步骤四：编写简略的示例代码

待估算的示例文本：

示例文本

1+21+2*41+2*4-51+2*4-5+20/5(1+2)*4

加减乘除逻辑类：

逻辑实现类

package com.vivo.learn.sql; import java.util.HashMap;import java.util.Map; /** * 重写拜访器规定，实现数据计算性能 * 指标： *     1+2 => 1+2=3 *     1+2*4 => 1+2*4=9 *     1+2*4-5 => 1+2*4-5=4 *     1+2*4-5+20/5 => 1+2*4-5+20/5=8 *     (1+2)*4 => (1+2)*4=12 */public class LibExprVisitorImpl extends LibExprBaseVisitor<Integer> {    // 定义数据    Map<String,Integer> data = new HashMap<String,Integer>();     // expr (NEWLINE)?         # printExpr    @Override    public Integer visitPrintExpr(LibExprParser.PrintExprContext ctx) {        System.out.println(ctx.expr().getText()+"="+visit(ctx.expr()));        return visit(ctx.expr());    }     // ID '=' expr (NEWLINE)? # assign    @Override    public Integer visitAssign(LibExprParser.AssignContext ctx) {        // 获取id        String id = ctx.ID().getText();        // // 获取value        int value = Integer.valueOf(visit(ctx.expr()));         // 缓存ID数据        data.put(id,value);         // 打印日志        System.out.println(id+"="+value);         return value;    }     // NEWLINE                # blank    @Override    public Integer visitBlank(LibExprParser.BlankContext ctx) {        return 0;    }     // expr op=('*'|'/') expr # MulDiv    @Override    public Integer visitMulDiv(LibExprParser.MulDivContext ctx) {        // 左侧数字        int left = Integer.valueOf(visit(ctx.expr(0)));        // 右侧数字        int right = Integer.valueOf(visit(ctx.expr(1)));        // 操作符号        int opType = ctx.op.getType();         // 调试        // System.out.println("visitMulDiv>>>>> left:"+left+",opType:"+opType+",right:"+right);         // 判断是否为乘法        if(LibExprParser.MUL==opType){            return left*right;        }         // 判断是否为除法        return left/right;     }     // expr op=('+'|'-') expr # AddSub    @Override    public Integer visitAddSub(LibExprParser.AddSubContext ctx) {        // 获取值和符号         // 左侧数字        int left = Integer.valueOf(visit(ctx.expr(0)));        // 右侧数字        int right = Integer.valueOf(visit(ctx.expr(1)));        // 操作符号        int opType = ctx.op.getType();         // 调试        // System.out.println("visitAddSub>>>>> left:"+left+",opType:"+opType+",right:"+right);         // 判断是否为加法        if(LibExprParser.ADD==opType){            return left+right;        }         // 判断是否为减法        return left-right;     }     // '(' expr ')'           # Parens    @Override    public Integer visitParens(LibExprParser.ParensContext ctx) {        // 递归下调        return visit(ctx.expr());    }     // ID                     # Id    @Override    public Integer visitId(LibExprParser.IdContext ctx) {        // 获取id        String id = ctx.ID().getText();        // 判断ID是否被定义        if(data.containsKey(id)){            // System.out.println("visitId>>>>> id:"+id+",value:"+data.get(id));            return data.get(id);        }        return 0;    }     // INT                    # Int    @Override    public Integer visitInt(LibExprParser.IntContext ctx) {        // System.out.println("visitInt>>>>> int:"+ctx.INT().getText());        return Integer.valueOf(ctx.INT().getText());    } }

Main函数打印输出后果类：

package com.vivo.learn.sql; import org.antlr.v4.runtime.tree.ParseTree; import java.io.FileNotFoundException;import java.io.IOException;import org.antlr.v4.runtime.*; /** * 打印语法树 */public class TestLibExprPrint {     // 打印语法树 input -> lexer -> tokens -> parser -> tree -> print    public static void main(String args[]){        printTree("E:\\smartloli\\hadoop\\sql-parser-example\\src\\main\\resources\\testCase.txt");    }      /**     * 打印语法树 input -> lexer -> token -> parser -> tree     * @param fileName     */    private static void printTree(String fileName){        // 定义输出流        ANTLRInputStream input = null;         // 判断文件名是否为空,若不为空，则读取文件内容，若为空，则读取输出流        if(fileName!=null){            try{                input = new ANTLRFileStream(fileName);            }catch(FileNotFoundException fnfe){                System.out.println("文件不存在，请查看后重试！");            }catch(IOException ioe){                System.out.println("文件读取异样，请查看后重试！");            }        }else{            try{                input = new ANTLRInputStream(System.in);            }catch(FileNotFoundException fnfe){                System.out.println("文件不存在，请查看后重试！");             }catch(IOException ioe){                System.out.println("文件读取异样，请查看后重试！");            }        }         // 定义词法规定分析器        LibExprLexer lexer = new LibExprLexer(input);         // 生成通用字符流        CommonTokenStream tokens = new CommonTokenStream(lexer);         // 语法解析        LibExprParser parser = new LibExprParser(tokens);         // 生成语法树        ParseTree tree = parser.prog();         // 打印语法树        // System.out.println(tree.toStringTree(parser));         // 生命拜访器        LibExprVisitorImpl visitor = new LibExprVisitorImpl();        visitor.visit(tree);     } }

执行代码，最终输入后果如下图所示：

4.2 Calcite

上述ANTLR内容演示了词法剖析和语法分析的简略流程，然而因为ANTLR要实现SQL查问，须要本人定义词法和语法相干文件，而后再应用ANTLR的插件对文件进行编译，而后再生成代码（与Thrift的应用相似，也是先定义接口，而后编译成对应的语言文件，最初再继承或者实现这些生成好的类或者接口）。

4.2.1 原理及劣势

而Apache Calcite的呈现，大大简化了这些简单的工程。Calcite能够让用户很不便的给本人的零碎套上一个SQL的外壳，并且提供足够高效的查问性能优化。

query language；
query optimization；
query execution；
data management；
data storage；

上述这五个性能，通常是数据库系统蕴含的罕用性能。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】：最外围的模块，专一于查问优化。

功能模块的划分足够正当，也足够独立，使得不必残缺集成，而是能够只抉择其中的一部分应用，而基本上每个模块都反对自定义，也使得用户可能更多的定制零碎。

下面列举的这些大数据罕用的组件都Calcite均有集成，能够看到Hive就是本人做了SQL解析，只应用了Calcite的查问优化性能。而像Flink则是从解析到优化都间接应用了Calcite。

下面介绍的Calcite集成办法，都是把Calcite的模块当做库来应用。如果感觉太重量级，能够抉择更简略的适配器性能。通过相似Spark这些框架里自定义的Source或Sink的形式，来实现和内部零碎的数据交互操作。

上图就是比拟典型的适配器用法，比方通过Kafka的适配器就能间接在应用层通过SQL，而底层主动转换成Java和Kafka进行数据交互（前面局部有个案例操作）。

4.2.2 Calcite实现KSQL查问Kafk

参考了EFAK（原Kafka Eagle开源我的项目）的SQL实现，来查问Kafka中Topic外面的数据。

1.惯例SQL查问

SQL查问

select * from video_search_query where partition in (0) limit 10

预览截图：

2.UDF查问

SQL查问

select JSON(msg,'query') as query,JSON(msg,'pv') as pv from video_search_query where `partition` in (0) limit 10

预览截图：

4.3 ANTLR4 和 Calcite SQL解析比照

4.3.1 ANTLR4解析SQL

ANTLR4解析SQL的次要流程蕴含：定义词法和语法文件、编写SQL解析逻辑类、主服务调用SQL逻辑类。

1.定义词法和语法文件

可参考官网提供的开源地址：详情

2.编写SQL解析逻辑类

这里，咱们编写一个实现解析SQL表名的类，具体实现代码如下所示：

解析表名

public class TableListener extends antlr4.sql.MySqlParserBaseListener {    private String tableName = null;    public void enterQueryCreateTable(antlr4.sql.MySqlParser.QueryCreateTableContext ctx) {        List<MySqlParser.TableNameContext> tableSourceContexts = ctx.getRuleContexts(antlr4.sql.MySqlParser.TableNameContext.class);        for (antlr4.sql.MySqlParser.TableNameContext tableSource : tableSourceContexts) {            // 获取表名            tableName = tableSource.getText();        }    }    public String getTableName() {        return tableName;    }}

3.主服务调用SQL逻辑类

对实现SQL解析的逻辑类进行调用，具体代码如下所示：

主服务

public class AntlrClient {    public static void main(String[] args) {        // antlr4 格式化SQL        antlr4.sql.MySqlLexer lexer = new antlr4.sql.MySqlLexer(CharStreams.fromString("create table table2 select tid from table1;"));        antlr4.sql.MySqlParser parser = new antlr4.sql.MySqlParser(new CommonTokenStream(lexer));        // 定义TableListener        TableListener listener = new TableListener();        ParseTreeWalker.DEFAULT.walk(listener, parser.sqlStatements());        // 获取表名        String tableName= listener.getTableName();        // 输出表名        System.out.println(tableName);    }}

4.3.2 Calcite解析SQL

Calcite解析SQL的流程相比拟ANTLR是比较简单的，开发中无需关注词法和语法文件的定义和编写，只需关注具体的业务逻辑实现。比方实现一个SQL的COUNT操作，Calcite实现步骤如下所示。

1.pom依赖

Calcite依赖JAR

<dependencies>  <!-- 这里对Calcite适配依赖进行封装，引入下列包即可 -->  <dependency>    <groupId>org.smartloli</groupId>    <artifactId>jsql-client</artifactId>    <version>1.0.0</version>  </dependency></dependencies>

2.实现代码

Calcite示例代码

package com.vivo.learn.sql.calcite;import com.alibaba.fastjson.JSON;import com.alibaba.fastjson.JSONArray;import com.alibaba.fastjson.JSONObject;import org.smartloli.util.JSqlUtils;public class JSqlClient {    public static void main(String[] args) {        JSONObject tabSchema = new JSONObject();        tabSchema.put("id","integer");        tabSchema.put("name","varchar");        JSONArray datasets = JSON.parseArray("[{\"id\":1,\"name\":\"aaa\",\"age\":20},{\"id\":2,\"name\":\"bbb\",\"age\":21},{\"id\":3,\"name\":\"ccc\",\"age\":22}]");        String tabName = "userinfo";        String sql = "select count(*) as cnt from \"userinfo\"";        try{           String result = JSqlUtils.query(tabSchema,tabName,datasets,sql);            System.out.println("result: "+result);        }catch (Exception e){            e.printStackTrace();        }    }}

3.预览截图

4.3.3 比照后果

综合比照，咱们从对两种技术的学习老本、应用复杂度、以及灵便度来比照，能够优先选择Calcite来作为SQL解析器来解决理论的业务需要。

五、总结

另外，在单机模式的状况下，执行打算能够较为简单的翻译成执行代码，然而在分布式畛域中，因为计算引擎多种多样，因而，还须要一个更加贴近具体计算引擎的形容，也就是物理打算。换言之，逻辑打算只是形象的一层形容，而物理打算则和具体的计算引擎间接挂钩。

满足上述场景，通常都能够引入SQL解析器：

给关系型数据库（比方MySQL、Oracle）这类提供定制化的SQL来作为交互查问；
给开发人员提供了JDBC、ODBC之类和各种数据库的标准接口；
对数据分析师等不太会编程语言的但又须要应用数据的人；
大数据技术组件不自带SQL的；

参考资料：

https://github.com/smartloli/EFAK
https://github.com/antlr/antlr4
https://github.com/antlr/grammars-v4
https://github.com/apache/calcite

一、背景

二、为什么须要SQL解析器？

2.1 传统的SQL查问

2.2 理论利用场景

三、什么是SQL解析器？

3.1 SQL解析器蕴含哪些内容？

3.1.1 什么词法解析？

3.1.2 什么是语法解析？

3.1.3 什么是语义解析？

四、 如何抉择SQL解析器？

4.1 ANTLR

4.1.1 Parser

4.1.2 Grammar

4.1.3 ANTLR4实现简略计算性能

4.2 Calcite

4.2.1 原理及劣势

4.2.2 Calcite实现KSQL查问Kafk

4.3 ANTLR4 和 Calcite SQL解析比照

4.3.1 ANTLR4解析SQL

4.3.2 Calcite解析SQL

4.3.3 比照后果

五、总结

四、如何抉择SQL解析器？