简介：SQL 作为一种畛域语言，最早用于关系型数据库，方便管理结构化数据；SQL 由多种不同的类型的语言组成，包含数据定义语言，数据管制语言、数据操作语言；各数据库产品都有不同的申明和实现；用户能够很不便的应用 SQL 操作数据，数据库系统中的词法语法分析器负责剖析和了解 SQL 文本的含意，包含词法剖析、语法分析、语义剖析 3 局部。
作者 | 林夕
起源 | 阿里技术公众号
SQL（Structured Query Language）作为一种畛域语言（编程语言），最早用于关系型数据库，方便管理结构化数据；SQL 由多种不同的类型的语言组成，包含数据定义语言，数据管制语言、数据操作语言；各数据库产品都有不同的申明和实现；用户能够很不便的应用 SQL 操作数据，数据库系统中的词法语法分析器负责剖析和了解 SQL 文本的含意，包含词法剖析、语法分析、语义剖析 3 局部。通过词法语法分析器生成 AST（Abstract Syntax Tree），会被优化器解决生成生成执行打算，再由执行引擎执行，下图以 MySQL 架构为例展现词法语法分析器所处的地位。
本文通过介绍词法语法分析器技术和业界的做法，以及过来应用主动生成的词法语法分析器遇到的问题，分享自研 SQL Parser 的设计与实际，以及其带来的性能和性能的晋升。
一 业界产品如何开发 SQL Parser？
依照解析器代码开发方式，可分为以下两种：
1 主动生成
为不便开发词法、语法分析的过程，业界有许多词法、语法分析工具，例如：Flex、Lex、Bison 工具罕用于生成以 C、C++ 作为目标语言的词法、语法代码；如果以 Java 作为目标语言，能够应用比拟风行的 ANTLR 和 JavaCC 等工具，ANTLR、JavaCC 工具都以用户编写的词法语法规定文件作为输出，其中语法文件须要满足 EBNF（extended Backus–Naur form）[1]语法规定，这 2 个工具应用 LL(k) (Left-to-right, Leftmost derivation)[2] 算法“自顶向下 [3]”解析 SQL 文本并构建 SQL AST，Presto，Spark、Hive 等数据库和大数据系统多采纳该形式生成。生成的代码蕴含词法和语法解析局部，语义剖析还须要联合 Meta 数据，各数据库内核本人解决；更多主动生成工具的性能和算法比照[4] 在参考文献中。
2 手工编写
与主动生成工具不同，InfluxDB、H2、Clickhouse 等风行的数据库的 SQL Parser 组件均是手工编写而成。
长处：
- 代码逻辑清晰，不便开发人员调试和排错；
- 性能更好：有更多代码优化的空间交给开发人员，能够应用更优良的算法和数据结构晋升性能；
- 自主可控：无 licence 束缚，可读性和可维护性更高；
- 不须要额定依赖第三方词法语法代码生成工具。
有余：
- 对开发人员的技术要求较高，需理解编译原理技术；
- 开发工作量较大，实现 MySQL 罕用语法的各类分支，须要投入很多工夫和精力；
- 须要长时间、大规模测试才会趋于稳定。
二 问题与挑战
1 简单查问的性能问题
在实时剖析型数据库的理论生产环境中，常常须要解决数以千行的简单查问申请或者深层嵌套的查问申请，主动生成的解析器，因为状态机治理简单，线程堆栈太深，导致个别查问申请在词法语法解析阶段性能降落重大。
2 大批量写入吞吐问题
剖析型数据库要稳固解决大批量、高并发写入的场景，要求 SQL Parser 组件有很好的性能和稳定性，咱们尝试应用过 ANTLR，JavaCC 等工具生成 SQL 的词法语法解析器，大批量写入时，values 子句在解析过程会产生太多 AST 长期对象，导致垃圾回收耗时的问题。
3 Query Rewriting 的灵活性问题
须要疾速不便的遍历 AST 树，找到合乎某种规定的叶子节点，批改改节点，主动生成的解析器并不能很灵便的反对。
主动生成的代码可读性差，排查问题老本高，简单查问场景下，性能有余，影响零碎稳定性和版本迭代速度；在设计之初，咱们放弃了主动生成的技术计划，齐全手工编写词法语法解析器。
三 自研词法语法分析器的技术要点
主动生成工具次要解决生成下图中左侧的 SQL Parser Core 和 SQL Tree Nodes 的局部，右侧 featrues 的局部须要开发同学解决，当右侧性能（例如：SQL rewriting）对左侧有的 Tree nodes 的更改性能有更多的需要时，想批改主动生成的代码，则无从下手。
主动生成工具是面向生成通用语法解析器而设计的，针对 SQL 这一特定畛域语言，有特定的优化技术晋升稳定性和性能，从设计之初，咱们抉择 LL(k)作为语法分析的算法，其自顶向下的个性，在手工编写分析器时，逻辑清晰，代码易读，不便开发和保护，LL(k)的“左递归”问题，可通过手工断定循环编程的形式防止。
1 词法和语法分析
词法剖析中，Lexer 继续读取间断 SQL 文本，将具备某特色的一段间断文本标识为 Token，并标识 Token 的类别，比方赋值语句 x = 30，通过词法剖析后 x, = , 30 别离被标识为 ID、等号操作符、数值常量；尤其在辨认标识符（变量，表名，列名等）和保留字（TABLE，FROM，SELECT 等）须要对字符串进行重复比照。主动生成工具在这一阶段应用 DFA（Deterministic Finite Automaton）和事后定义的词法文件，确定每个 Token 的值和类型，手工编写解析器不须要额定保护一个状态机，应用分支预测，缩小计算量和调用堆栈的深度。
语法分析器会应用词法剖析中的 Token 作为输出，以 SQL 语法形容作为规定，自顶向下，顺次将非叶子节点开展，构建语法树，整个过程就像是走迷宫，只有一个正确入口和进口，走完迷宫后，会生成一个正确的 AST。
疾速 Token 比拟
selECT c1 From T1;
因为大部分数据库系统对大小写不敏感，上述 query 中 selECT 和 From 会被辨认为保留字，c1 和 T1 会被辨认为标识符。辨认 2 者的类型不同，字符串匹配操作是必不可少的，通常将字符对立转为大写或者小写，再比拟字面值，是一个可行的计划。首先把数据库保留字依照 Map< String, Token > 初始化在内存里，key 是保留字的大写字符串，value 是 Token 类型；其中 key 在作大写转化时，可应用 ASCII 值 +32 的办法取代 toUpperCase()办法，在不影响正确性的前提下，取得数倍性能晋升。
疾速数值剖析
在解析常量值时，通常的做法是读取 SQL 中的字符串，把字符串作为参数，调用 Java 自带的 Integer.parseInt() / Float.parseFloat() / Long.parseLong()，能够间接在原文本上边读取边计算数值，该过程只应用根底类型，防止结构字符串，能够节俭内存，又晋升了解析速度，该优化对大批量写入数值的场景优化非常明显。
防止回溯[5]
SQL 语法解析过程中，通常只须要预读一个 Token，就能够决定如何构建语法节点的关系，或者构建哪种语法节点，有些语法分支较多，须要预读 2 个及以上的 Token 才能够做出判断，预读多个 Token 能够升高回溯带来的性能耗费，极少状况下，2 个以上的 Token 预读都也没有匹配到正确的语法分支，须要撤销预读，走其余分支；为了进步撤销的速度，能够在预读前保留 Token 位点，撤销时，能够疾速回到保留点。
在 insert into values 语句中，呈现常量字面值的概率比呈现其余的 token 要高，通过分支预测能够缩小判断逻辑，防止回溯，晋升性能。
表达式替换
Query rewriting[6]技术基于“关系代数”批改 AST，保障正确性的前提下，使新的 AST 在具备更好的执行性能，例如：A，B 两张表的大小相差悬殊，而且谬误的 Join 程序对数据库系统不敌对，通过更改 A，B 表的 Join 程序能够取得更高的执行性能。应用工具生成的解析器，通常不容许间接更改 AST 的节点，每次更改 AST 某个节点都须要从新构建整个 AST，性能并不好。自研的 Parser 中，每个 AST 节点类实现都 replace 接口，只须要批改 AST 中的子树就能够达到改写的目标。
public interface Replaceable {boolean replace(Node expr, Node target);
}
public class BetweenNode implements Replaceable {
public Node beginExpr;
public Node endExpr;
@Override
public int hashCode(){...}
@Override
public boolean equals(Object obj) {...}
@Override
public boolean replace(SQLExpr expr, SQLExpr target) {if (expr == beginExpr) {setBeginExpr(target);
return true;
}
if (expr == endExpr) {setEndExpr(target);
return true;
}
return false;
}
}其余优化
反对 AST Clone：如果放弃原 AST 构造不变，克隆出一个新的 AST，在新的 AST 批改节点构造，比方：减少 Hint，删减 where 条件，减少 limit 限度等。
保护 AST 父子关系：主动生成的解析器保护了父到子节点的关系，是单向的援用关系。手写代码能够减少子节点对父节点的援用，构建 AST 节点的双向援用关系，实现节点的疾速“回跳”，使得 AST 的遍历效率更高。
public abstract class Node {public abstract List< Node> getChildren()
}
public class BetweenNode extends Node {
public Node beginExpr;
public Node endExpr;
@Override
public List< Node> getChildren() {return Arrays.< Node>asList(beginExpr, this.endExpr);
}
@Override
public BetweenNode clone() {BetweenNode x = new BetweenNode();
if (beginExpr != null) {x.setBeginExpr(beginExpr.clone());
}
if (endExpr != null) {x.setEndExpr(endExpr.clone());
}
return x;
}
public void setBeginExpr(Node beginExpr) {if (beginExpr != null) {beginExpr.setParent(this);
}
this.beginExpr = beginExpr;
}
public void setEndExpr(Node endExpr) {if (endExpr != null) {endExpr.setParent(this);
}
this.endExpr = endExpr;
}
}2 语义剖析
写入事件回调
后面提到大批量导入数据时，词法语法分析阶段会产生很多 AST 小对象，给垃圾回收带来压力，解决这个问题的外围是要尽量应用根底数据类型，尽量不要产生 AST 节点对象。须要从词法分析阶段动手，防止进入语法分析阶段。在词法分析阶段，容许内部注册实现了写入接口的类，每当词法分析器解析出 values 中的每个具体值，或者残缺解析出 values 中的一行，同时回调写入接口，实现数据库写入逻辑。
public interface InsertValueHandler {Object newRow() throws SQLException;
void processInteger(Object row, int index, Number value);
void processString(Object row, int index, String value);
void processDate(Object row, int index, String value);
void processDate(Object row, int index, java.util.Date value);
void processTimestamp(Object row, int index, String value);
void processTimestamp(Object row, int index, java.util.Date value);
void processTime(Object row, int index, String value);
void processDecimal(Object row, int index, BigDecimal value);
void processBoolean(Object row, int index, boolean value);
void processNull(Object row, int index);
void processFunction(Object row, int index, String funcName, Object... values);
void processRow(Object row);
void processComplete();}
public class BatchInsertHandler implements InsertValueHandler {...}
public class Application {BatchInsertHandler handler = new BatchInsertHandler();
parser.parseInsertHeader(); // 头部：解析 insert into xxx values 局部
parser.parseValues(handler); // 批量值：values (xxx), (xxx), (xxx) 局部
}
Query Rewriting
手动编写的 SQL Parser 能够更灵便的与优化器配合，将 Query rewriting 的局部优化能力前置化到 SQL Parser 中实现，使得优化器能更加专一于基于代价和老本的优化上。Parser 能够联合 Meta 信息，利用“等价关系代数”，在 AST 上低成本实现 Query Rewriting 性能，以晋升查问性能，例如：常量折叠、函数变换、条件下推或上提、类型推导、隐式转化、语义去重等。
首先，须要设计一个构造存储 catalog 和 table 构造信息，包含库名，表名，列名，列类型等。
而后，应用“访问者模式”编写 Visitor 程序，通过“深度优先”遍历 AST，对字段、函数、表达式、操作符进行剖析，联合表构造和类型信息，推断表达式类型，留神，嵌套的查问语句中，雷同的表达式呈现的地位不同，所属的作用域也不同。
最初，AST 会通过应用“等价关系代数”编写的 RBO（Rule-Based Optimization）规定解决，达到优化器的目标。
-- 常量折叠示例
SELECT * FROM T1
WHERE c_week
BETWEEN CAST(date_format(date_add('day', -day_of_week('20180605'),
date('20180605')), '%Y%m&d') as bigint)
AND CAST(date_format(date_add('day', -day_of_week('20180606'),
date('20180606')), '%Y%m&d') as bigint)
------------ 折叠后 -----------
SELECT * from T1
WHERE c_week BETWEEN 20180602 and 20180603-- 函数转换示例
SELECT * FROM T1
WHERE DATE_FORMAT(t1."pay_time", '%Y%m%d') >= '20180529'
AND DATE_FORMAT(t1."pay_time", '%Y%m%d') <= '20180529'
----------- 转化后, 更好利用索引 ------------
SELECT * FROM T1
WHERE t1."pay_time" >= '2018-05-29 00:00:00'
AND t1."pay_time" < '2018-05-30 00:00:00'四 最初
优化后的 SQL Parser 的性能和稳定性晋升显著，以 TPC-DS[7] 99 个 Query 比照来看，手工编写的 SQL Parser 比 ANTLR Parser（应用 ANTLR 生成）速度快 20 倍，比 JSQLParser（应用 JavaCC 生成）速度快 30 倍，在批量 Insert 场景下，速度晋升 30~50 倍。
本文通过介绍主动生成工具生成的词法语法分析器和自研分析器的利弊衡量和思考，联合 OLAP 的大吞吐，解决简单 SQL 的业务个性，抉择手工编写解析器。性能优化伎俩贴近 SQL 解析的特点；在语义剖析层面，联合 Schema 信息积淀了很多语义剖析工具，在离线或在线 SQL 统计和特征分析方面更轻量化、便捷。
原文链接
本文为阿里云原创内容，未经容许不得转载。