探究 Presto SQL 引擎 (1)- 巧用 Antlr

关注

发布于: 3 小时前

一、背景

自 2014 年大数据首次写入政府工作报告，大数据已经发展 7 年。大数据的类型也从交易数据延伸到交互数据与传感数据。数据规模也到达了 PB 级别。

大数据的规模大到对数据的获取、存储、管理、分析超出了传统数据库软件工具能力范围。在这个背景下，各种大数据相关工具相继出现，用于应对各种业务场景需求。从 Hadoop 生态的 Hive, Spark, Presto, Kylin, Druid 到非 Hadoop 生态的 ClickHouse, Elasticsearch，不一而足...

这些大数据处理工具特性不同，应用场景不同，但是对外提供的接口或者说操作语言都是相似的，即各个组件都是支持 SQL 语言。只是基于不同的应用场景和特性，实现了各自的 SQL 方言。这就要求相关开源项目自行实现 SQL 解析。在这个背景下，诞生于 1989 年的语法解析器生成器 ANTLR 迎来了黄金时代。

二、简介

ANTLR 是开源的语法解析器生成器，距今已有 30 多年的历史。是一个经历了时间考验的开源项目。一个程序从源代码到机器可执行，基本需要 3 个阶段：编写、编译、执行。

在编译阶段，需要进行词法和语法的分析。ANTLR 聚焦的问题就是把源码进行词法和句法分析，产生一个树状的分析器。ANTLR 几乎支持对所有主流编程语言的解析。从antlr/grammars-v4可以看到，ANTLR 支持 Java,C, Python, SQL 等数十种编程语言。通常我们没有扩展编程语言的需求，所以大部分情况下这些语言编译支持更多是供学习研究使用，或者用在各种开发工具(NetBeans、Intellij)中用于校验语法正确性、和格式化代码。

对于 SQL 语言，ANTLR 的应用广度和深度会更大，这是由于 Hive, Presto, SparkSQL 等由于需要对 SQL 的执行进行定制化开发，比如实现分布式查询引擎、实现各种大数据场景下独有的特性等。

三、基于 ANTLR4 实现四则运算

当前我们主要使用的是 ANTLR4。在《The Definitive ANTLR4 Reference》一书中，介绍了基于 ANTLR4 的各种有趣的应用场景。比如：实现一个支持四则运算的计算器；实现 JSON 等格式化文本的解析和提取；

将 JSON 转换成 XML；从 Java 源码中提取接口等。本节以实现四则运算计算器为例，介绍 Antlr4 的简单应用，为后面实现基于 ANTLR4 解析 SQL 铺平道路。实际上，支持数字运算也是各个编程语言必须具备的基本能力。

3.1 自行编码实现

在没有 ANTLR4 时，我们想实现四则运算该怎么处理呢？有一种思路是基于栈实现。例如，在不考虑异常处理的情况下，自行实现简单的四则运算代码如下：

package org.example.calc; import java.util.*; public class CalcByHand {    // 定义操作符并区分优先级，*/ 优先级较高    public static Set<String> opSet1 = new HashSet<>();    public static Set<String> opSet2 = new HashSet<>();    static{        opSet1.add("+");        opSet1.add("-");        opSet2.add("*");        opSet2.add("/");    }    public static void main(String[] args) {        String exp="1+3*4";        //将表达式拆分成token        String[] tokens = exp.split("((?<=[\\+|\\-|\\*|\\/])|(?=[\\+|\\-|\\*|\\/]))");         Stack<String> opStack = new Stack<>();        Stack<String> numStack = new Stack<>();        int proi=1;        // 基于类型放到不同的栈中        for(String token: tokens){            token = token.trim();             if(opSet1.contains(token)){                opStack.push(token);                proi=1;            }else if(opSet2.contains(token)){                proi=2;                opStack.push(token);            }else{                numStack.push(token);                // 如果操作数前面的运算符是高优先级运算符，计算后结果入栈                if(proi==2){                    calcExp(opStack,numStack);                }            }        }         while (!opStack.isEmpty()){            calcExp(opStack,numStack);        }        String finalVal = numStack.pop();        System.out.println(finalVal);    }         private static void calcExp(Stack<String> opStack, Stack<String> numStack) {        double right=Double.valueOf(numStack.pop());        double left = Double.valueOf(numStack.pop());        String op = opStack.pop();        String val;        switch (op){            case "+":                 val =String.valueOf(left+right);                break;            case "-":                 val =String.valueOf(left-right);                break;            case "*":                val =String.valueOf(left*right);                break;            case "/":                val =String.valueOf(left/right);                break;            default:                throw new UnsupportedOperationException("unsupported");        }        numStack.push(val);    }}

复制代码

代码量不大，用到了数据结构-栈的特性，需要自行控制运算符优先级，特性上没有支持括号表达式，也没有支持表达式赋值。接下来看看使用 ANTLR4 实现。

3.2 基于 ANTLR4 实现

使用 ANTLR4 编程的基本流程是固定的，通常分为如下三步：

基于需求按照 ANTLR4 的规则编写自定义语法的语义规则, 保存成以 g4 为后缀的文件。
使用 ANTLR4 工具处理 g4 文件，生成词法分析器、句法分析器代码、词典文件。
编写代码继承 Visitor 类或实现 Listener 接口，开发自己的业务逻辑代码。

基于上面的流程，我们借助现有案例剖析一下细节。

第一步：基于 ANTLR4 的规则定义语法文件，文件名以 g4 为后缀。例如实现计算器的语法规则文件命名为 LabeledExpr.g4。其内容如下：

grammar LabeledExpr; // rename to distinguish from Expr.g4 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 :   '*' ; // assigns token name to '*' used above in grammarDIV :   '/' ;ADD :   '+' ;SUB :   '-' ;ID  :   [a-zA-Z]+ ;      // match identifiersINT :   [0-9]+ ;         // match integersNEWLINE:'\r'? '\n' ;     // return newlines to parser (is end-statement signal)WS  :   [ \t]+ -> skip ; // toss out whitespace

复制代码

(注：此文件案例来源于《The Definitive ANTLR4 Reference》)

简单解读一下 LabeledExpr.g4 文件。ANTLR4 规则是基于正则表达式定义定义。规则的理解是自顶向下的，每个分号结束的语句表示一个规则。例如第一行：grammar LabeledExpr; 表示我们的语法名称是 LabeledExpr, 这个名字需要跟文件名需要保持一致。Java 编码也有相似的规则：类名跟类文件一致。

规则 prog 表示 prog 是一个或多个 stat。

规则 stat 适配三种子规则：空行、表达式 expr、赋值表达式 ID’=’expr。

表达式 expr 适配五种子规则：乘除法、加减法、整型、ID、括号表达式。很显然，这是一个递归的定义。

最后定义的是组成复合规则的基础元素，比如：规则 ID: [a-zA-Z]+表示 ID 限于大小写英文字符串；INT: [0-9]+; 表示 INT 这个规则是 0-9 之间的一个或多个数字，当然这个定义其实并不严格。再严格一点，应该限制其长度。

在理解正则表达式的基础上，ANTLR4 的 g4 语法规则还是比较好理解的。

定义 ANTLR4 规则需要注意一种情况，即可能出现一个字符串同时支持多种规则，如以下的两个规则：

ID: [a-zA-Z]+;

FROM: ‘from’;

很明显，字符串” from”同时满足上述两个规则，ANTLR4 处理的方式是按照定义的顺序决定。这里 ID 定义在 FROM 前面，所以字符串 from 会优先匹配到 ID 这个规则上。

其实在定义好与法规中，编写完成 g4 文件后，ANTLR4 已经为我们完成了 50%的工作：帮我们实现了整个架构及接口了，剩下的开发工作就是基于接口或抽象类进行具体的实现。实现上有两种方式来处理生成的语法树，其一 Visitor 模式，另一种方式是 Listener(监听器模式)。

3.2.1 使用 Visitor 模式

第二步：使用 ANTLR4 工具解析 g4 文件，生成代码。即 ANTLR 工具解析 g4 文件，为我们自动生成基础代码。流程图示如下：

命令行如下：

antlr4 -package org.example.calc -no-listener -visitor .\LabeledExpr.g4

复制代码

命令执行完成后，生成的文件如下：

$ tree ..├── LabeledExpr.g4├── LabeledExpr.tokens├── LabeledExprBaseVisitor.java├── LabeledExprLexer.java├── LabeledExprLexer.tokens├── LabeledExprParser.java└── LabeledExprVisitor.java

复制代码

首先开发入口类 Calc.java。Calc 类是整个程序的入口，调用 ANTLR4 的 lexer 和 parser 类核心代码如下：

ANTLRInputStream input = new ANTLRInputStream(is);LabeledExprLexer lexer = new LabeledExprLexer(input);CommonTokenStream tokens = new CommonTokenStream(lexer);LabeledExprParser parser = new LabeledExprParser(tokens);ParseTree tree = parser.prog(); // parse EvalVisitor eval = new EvalVisitor();eval.visit(tree);

复制代码

接下来定义类继承 LabeledExprBaseVisitor 类，覆写的方法如下：

从图中可以看出，生成的代码和规则定义是对应起来的。例如 visitAddSub 对应 AddSub 规则，visitId 对应 id 规则。以此类推…实现加减法的代码如下：

/** expr op=('+'|'-') expr */@Overridepublic Integer visitAddSub(LabeledExprParser.AddSubContext ctx) {    int left = visit(ctx.expr(0));  // get value of left subexpression    int right = visit(ctx.expr(1)); // get value of right subexpression    if ( ctx.op.getType() == LabeledExprParser.ADD ) return left + right;    return left - right; // must be SUB}

复制代码

相当直观。代码编写完成后，就是运行 Calc。运行 Calc 的 main 函数，在交互命令行输入相应的运算表达式，换行 Ctrl+D 即可看到运算结果。例如 1+3*4=13。

3.2.2 使用 Listener 模式

类似的，我们也可以使用 Listener 模式实现四则运算。命令行如下：

antlr4 -package org.example.calc -listener .\LabeledExpr.g4

复制代码

该命令的执行同样会为我们生产框架代码。在框架代码的基础上，我们开发入口类和接口实现类即可。首先开发入口类 Calc.java。Calc 类是整个程序的入口，调用 ANTLR4 的 lexer 和 parser 类代码如下：

ANTLRInputStream input = new ANTLRInputStream(is);LabeledExprLexer lexer = new LabeledExprLexer(input);CommonTokenStream tokens = new CommonTokenStream(lexer);LabeledExprParser parser = new LabeledExprParser(tokens);ParseTree tree = parser.prog(); // parse ParseTreeWalker walker = new ParseTreeWalker();walker.walk(new EvalListener(), tree);

复制代码

可以看出生成 ParseTree 的调用逻辑一模一样。实现 Listener 的代码略微复杂一些，也需要用到栈这种数据结构，但是只需要一个操作数栈就可以了，也无需自行控制优先级。以 AddSub 为例：

@Overridepublic void exitAddSub(LabeledExprParser.AddSubContext ctx) {    Double left = numStack.pop();    Double right= numStack.pop();    Double result;    if (ctx.op.getType() == LabeledExprParser.ADD) {        result = left + right;    } else {        result = left - right;    }    numStack.push(result);}

复制代码

直接从栈中取出操作数，进行运算即可。

3.2.3 小结

关于 Listener 模式和 Visitor 模式的区别，《The Definitive ANTLR 4 Reference》一书中有清晰的解释：

Listener 模式：

Visitor 模式：

Listener 模式通过 walker 对象自行遍历，不用考虑其语法树上下级关系。Vistor 需要自行控制访问的子节点，如果遗漏了某个子节点，那么整个子节点都访问不到了。

Listener 模式的方法没有返回值，Vistor 模式可以设定任意返回值。

Listener 模式的访问栈清晰明确，Vistor 模式是方法调用栈，如果实现出错有可能导致 StackOverFlow。

通过这个简单的例子，我们驱动 Antlr4 实现了一个简单的计算器。学习了 ANTLR4 的应用流程。了解了 g4 语法文件的定义方式、Visitor 模式和 Listener 模式。通过 ANTLR4，我们生成了 ParseTree,并基于 Visitor 模式和 Listener 模式访问了这个 ParseTree，实现了四则运算。

综合上述的例子可以发现，如果没有 ANTLR4，我们自行编写算法也能实现同样的功能。但是使用 ANTLR 不用关心表达式串的解析流程，只关注具体的业务实现即可，非常省心和省事。

更重要的是，ANTLR4 相比自行实现提供了更具想象空间的抽象逻辑，上升到了方法论的高度，因为它已经不局限于解决某个问题，而是解决一类问题。可以说 ANTLR 相比于自行硬编码解决问题的思路有如数学领域普通的面积公式和微积分的差距。

四、参考 Presto 源码开发 SQL 解析器

前面介绍了使用 ANTLR4 实现四则运算，其目的在于理解 ANTLR4 的应用方式。接下来图穷匕首见，展示出我们的真正目的：研究 ANTLR4 在 Presto 中如何实现 SQL 语句的解析。

支持完整的 SQL 语法是一个庞大的工程。在 presto 中有完整的 SqlBase.g4 文件，定义了 presto 支持的所有 SQL 语法，涵盖了 DDL 语法和 DML 语法。该文件体系较为庞大，并不适合学习探究某个具体的细节点。

为了探究 SQL 解析的过程，理解 SQL 执行背后的逻辑，在简单地阅读相关资料文档的基础上，我选择自己动手编码实验。为此，定义一个小目标：实现一个 SQL 解析器。用该解析器实现 select field from table 语法，从本地的 csv 数据源中查询指定的字段。

4.1 裁剪 SelectBase.g4 文件

基于同实现四则运算器同样的流程，首先定义 SelectBase.g4 文件。由于有了 Presto 源码作为参照系，我们的 SelectBase.g4 并不需要自己开发，只需要基于 Presto 的 g4 文件裁剪即可。裁剪后的内容如下：

grammar SqlBase; tokens {    DELIMITER} singleStatement    : statement EOF    ; statement    : query                                                            #statementDefault    ; query    :  queryNoWith    ; queryNoWith:      queryTerm    ; queryTerm    : queryPrimary                                                             #queryTermDefault    ; queryPrimary    : querySpecification                   #queryPrimaryDefault    ; querySpecification    : SELECT  selectItem (',' selectItem)*      (FROM relation (',' relation)*)?    ; selectItem    : expression  #selectSingle    ; relation    :  sampledRelation                             #relationDefault    ; expression    : booleanExpression    ; booleanExpression    : valueExpression             #predicated    ; valueExpression    : primaryExpression                                                                 #valueExpressionDefault    ; primaryExpression    : identifier                                                                          #columnReference    ; sampledRelation    : aliasedRelation    ; aliasedRelation    : relationPrimary    ; relationPrimary    : qualifiedName                                                   #tableName    ; qualifiedName    : identifier ('.' identifier)*    ; identifier    : IDENTIFIER             #unquotedIdentifier    ; SELECT: 'SELECT';FROM: 'FROM'; fragment DIGIT    : [0-9]    ; fragment LETTER    : [A-Z]    ; IDENTIFIER    : (LETTER | '_') (LETTER | DIGIT | '_' | '@' | ':')*    ; WS    : [ \r\n\t]+ -> channel(HIDDEN)    ; // Catch-all for anything we can't recognize.// We use this to be able to ignore and recover all the text// when splitting statements with DelimiterLexerUNRECOGNIZED    : .    ;

复制代码

相比 presto 源码中 700 多行的规则，我们裁剪到了其 1/10 的大小。该文件的核心规则为: SELECT selectItem (',' selectItem)* (FROM relation (',' relation)*)

通过理解 g4 文件，也可以更清楚地理解我们查询语句的构成。例如通常我们最常见的查询数据源是数据表。但是在 SQL 语法中，我们查询数据表被抽象成了 relation。

这个 relation 有可能来自于具体的数据表，或者是子查询，或者是 JOIN，或者是数据的抽样，或者是表达式的 unnest。在大数据领域，这样的扩展会极大方便数据的处理。

例如，使用 unnest 语法解析复杂类型的数据，SQL 如下：

尽管 SQL 较为复杂，但是通过理解 g4 文件，也能清晰理解其结构划分。回到 SelectBase.g4 文件，同样我们使用 Antlr4 命令处理 g4 文件，生成代码：

antlr4 -package org.example.antlr -no-listener -visitor .\SqlBase.g4

复制代码

这样就生成了基础的框架代码。接下来就是自行处理业务逻辑的工作了。

4.2 遍历语法树封装 SQL 结构信息

接下来基于 SQL 语法定义语法树的节点类型，如下图所示。

通过这个类图，可以清晰明了看清楚 SQL 语法中的各个基本元素。

然后基于 visitor 模式实现自己的解析类 AstBuilder (这里为了简化问题，依然从 presto 源码中进行裁剪)。以处理 querySpecification 规则代码为例：

@Overridepublic Node visitQuerySpecification(SqlBaseParser.QuerySpecificationContext context){    Optional<Relation> from = Optional.empty();    List<SelectItem> selectItems = visit(context.selectItem(), SelectItem.class);     List<Relation> relations = visit(context.relation(), Relation.class);    if (!relations.isEmpty()) {        // synthesize implicit join nodes        Iterator<Relation> iterator = relations.iterator();        Relation relation = iterator.next();         from = Optional.of(relation);    }     return new QuerySpecification(            getLocation(context),            new Select(getLocation(context.SELECT()), false, selectItems),            from);}

复制代码

通过代码，我们已经解析出了查询的数据源和具体的字段，封装到了 QuerySpecification 对象中。

4.3 应用 Statement 对象实现数据查询

通过前面实现四则运算器的例子，我们知道 ANTLR 把用户输入的语句解析成 ParseTree。业务开发人员自行实现相关接口解析 ParseTree。Presto 通过对输入 sql 语句的解析，生成 ParseTree, 对 ParseTree 进行遍历，最终生成了 Statement 对象。核心代码如下：

SqlParser sqlParser = new SqlParser();Statement statement = sqlParser.createStatement(sql);

复制代码

有了 Statement 对象我们如何使用呢？结合前面的类图，我们可以发现：

Query 类型的 Statement 有 QueryBody 属性。
QuerySpecification 类型的 QueryBody 有 select 属性和 from 属性。

通过这个结构，我们可以清晰地获取到实现 select 查询的必备元素：

从 from 属性中获取待查询的目标表 Table。这里约定表名和 csv 文件名一致。
从 select 属性中获取待查询的目标字段 SelectItem。这里约定 csv 首行为 title 行。

整个业务流程就清晰了，在解析 sql 语句生成 statement 对象后，按如下的步骤：

s1: 获取查询的数据表以及字段。
s2: 通过数据表名称定为到数据文件，并读取数据文件数据。
s3: 格式化输出字段名称到命令行。
s4: 格式化输出字段内容到命令行。

为了简化逻辑，代码只处理主线，不做异常处理。

/** * 获取待查询的表名和字段名称 */QuerySpecification specification = (QuerySpecification) query.getQueryBody();Table table= (Table) specification.getFrom().get();List<SelectItem> selectItems = specification.getSelect().getSelectItems();List<String> fieldNames = Lists.newArrayList();for(SelectItem item:selectItems){    SingleColumn column = (SingleColumn) item;    fieldNames.add(((Identifier)column.getExpression()).getValue());} /** * 基于表名确定查询的数据源文件 */String fileLoc = String.format("./data/%s.csv",table.getName()); /** * 从csv文件中读取指定的字段 */Reader in = new FileReader(fileLoc);Iterable<CSVRecord> records = CSVFormat.RFC4180.withFirstRecordAsHeader().parse(in);List<Row> rowList = Lists.newArrayList();for(CSVRecord record:records){    Row row = new Row();    for(String field:fieldNames){        row.addColumn(record.get(field));    }    rowList.add(row);} /** * 格式化输出到控制台 */int width=30;String format = fieldNames.stream().map(s-> "%-"+width+"s").collect(Collectors.joining("|"));System.out.println( "|"+String.format(format, fieldNames.toArray())+"|"); int flagCnt = width*fieldNames.size()+fieldNames.size();String rowDelimiter = String.join("", Collections.nCopies(flagCnt, "-"));System.out.println(rowDelimiter);for(Row row:rowList){    System.out.println( "|"+String.format(format, row.getColumnList().toArray())+"|");}

复制代码

代码仅供演示功能，暂不考虑异常逻辑，比如查询字段不存在、csv 文件定义字段名称不符合要求等问题。

4.4 实现效果展示

在我们项目 data 目录，存储如下的 csv 文件：

cities.csv 文件样例数据如下：

"LatD","LatM","LatS","NS","LonD","LonM","LonS","EW","City","State"   41,    5,   59, "N",     80,   39,    0, "W", "Youngstown", OH   42,   52,   48, "N",     97,   23,   23, "W", "Yankton", SD   46,   35,   59, "N",    120,   30,   36, "W", "Yakima", WA   42,   16,   12, "N",     71,   48,    0, "W", "Worcester", MA

复制代码

运行代码查询数据。使用 SQL 语句指定字段从 csv 文件中查询。最终实现类似 SQL 查询的效果如下：

SQL 样例 1：select City, City from cities

SQL 样例 2：select name, age from employee

本节讲述了如何基于 Presto 源码，裁剪 g4 规则文件，然后基于 Antlr4 实现用 sql 语句从 csv 文件查询数据。依托于对 Presto 源码的裁剪进行编码实验，对于研究 SQL 引擎实现，理解 Presto 源码能起到一定的作用。

五、总结

本文基于四则运算器和使用 SQL 查询 csv 数据两个案例阐述了 ANTLR4 在项目开发中的应用思路和过程，相关的代码可以在github上看到。理解 ANTLR4 的用法能够帮助理解 SQL 的定义规则及执行过程，辅助业务开发中编写出高效的 SQL 语句。同时对于理解编译原理，定义自己的 DSL，抽象业务逻辑也大有裨益。纸上得来终觉浅，绝知此事要躬行。通过本文描述的方式研究源码实现，也不失为一种乐趣。