刚做的网站怎么收录,营销型网站和普通网站,龙岗网络公司,公司网站开发怎么做简介#xff1a; SQL作为一种领域语言#xff0c;最早用于关系型数据库#xff0c;方便管理结构化数据#xff1b;SQL由多种不同的类型的语言组成#xff0c;包括数据定义语言#xff0c;数据控制语言、数据操作语言#xff1b;各数据库产品都有不同的声明和实现#x…简介 SQL作为一种领域语言最早用于关系型数据库方便管理结构化数据SQL由多种不同的类型的语言组成包括数据定义语言数据控制语言、数据操作语言各数据库产品都有不同的声明和实现用户可以很方便的使用SQL操作数据数据库系统中的词法语法分析器负责分析和理解SQL文本的含义包括词法分析、语法分析、语义分析3部分。 作者 | 林夕 来源 | 阿里技术公众号
SQLStructured Query Language作为一种领域语言编程语言最早用于关系型数据库方便管理结构化数据SQL由多种不同的类型的语言组成包括数据定义语言数据控制语言、数据操作语言各数据库产品都有不同的声明和实现用户可以很方便的使用SQL操作数据数据库系统中的词法语法分析器负责分析和理解SQL文本的含义包括词法分析、语法分析、语义分析3部分。经过词法语法分析器生成ASTAbstract Syntax Tree会被优化器处理生成生成执行计划再由执行引擎执行下图以MySQL架构为例展示词法语法分析器所处的位置。 本文通过介绍词法语法分析器技术和业界的做法以及过去使用自动生成的词法语法分析器遇到的问题分享自研SQL Parser的设计与实践以及其带来的性能和功能的提升。
一 业界产品如何开发SQL Parser
按照解析器代码开发方式可分为以下两种
1 自动生成
为方便开发词法、语法分析的过程业界有许多词法、语法分析工具例如Flex、Lex、Bison工具常用于生成以C、C作为目标语言的词法、语法代码如果以Java作为目标语言可以使用比较流行的ANTLR和JavaCC等工具ANTLR、JavaCC工具都以用户编写的词法语法规则文件作为输入其中语法文件需要满足EBNFextended Backus–Naur form[1]语法规则 这2个工具使用LL(k) (Left-to-right, Leftmost derivation)[2] 算法“自顶向下[3]”解析SQL文本并构建SQL AST PrestoSpark、Hive等数据库和大数据系统多采用该方式生成。生成的代码包含词法和语法解析部分语义分析还需要结合Meta数据各数据库内核自己处理更多自动生成工具的功能和算法对比[4]在参考文献中。
2 手工编写
与自动生成工具不同InfluxDB、H2、Clickhouse等流行的数据库的SQL Parser组件均是手工编写而成。
优点
代码逻辑清晰方便开发人员调试和排错性能更好有更多代码优化的空间交给开发人员可以使用更优秀的算法和数据结构提升性能自主可控无licence约束可读性和可维护性更高不需要额外依赖第三方词法语法代码生成工具。
不足
对开发人员的技术要求较高需了解编译原理技术开发工作量较大实现MySQL常用语法的各类分支需要投入很多时间和精力需要长时间、大规模测试才会趋于稳定。
二 问题与挑战
1 复杂查询的性能问题
在实时分析型数据库的实际生产环境中经常需要处理数以千行的复杂查询请求或者深层嵌套的查询请求自动生成的解析器由于状态机管理复杂线程堆栈太深导致个别查询请求在词法语法解析阶段性能下降严重。
2 大批量写入吞吐问题
分析型数据库要稳定处理大批量、高并发写入的场景要求SQL Parser组件有很好的性能和稳定性我们尝试使用过ANTLRJavaCC等工具生成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、等号操作符、数值常量尤其在识别标识符变量表名列名等和保留字TABLEFROMSELECT等需要对字符串进行反复对比。自动生成工具在这一阶段使用DFADeterministic 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在具备更好的执行性能例如AB两张表的大小相差悬殊而且错误的Join顺序对数据库系统不友好通过更改AB表的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;Overridepublic int hashCode(){...}Overridepublic boolean equals(Object obj) {...}Overridepublic 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;Overridepublic List Node getChildren() {return Arrays. NodeasList(beginExpr, this.endExpr);}Overridepublic 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会经过使用“等价关系代数”编写的RBORule-Based Optimization规则处理达到优化器的目的。
-- 常量折叠示例
SELECT * FROM T1
WHERE c_weekBETWEEN CAST(date_format(date_add(day, -day_of_week(20180605),date(20180605)), %Y%md) as bigint)AND CAST(date_format(date_add(day, -day_of_week(20180606),date(20180606)), %Y%md) as bigint)------------折叠后-----------
SELECT * from T1
WHERE c_week BETWEEN 20180602 and 20180603
-- 函数转换示例
SELECT * FROM T1
WHERE DATE_FORMAT(t1.pay_time, %Y%m%d) 20180529AND DATE_FORMAT(t1.pay_time, %Y%m%d) 20180529-----------转化后, 更好利用索引------------
SELECT * FROM T1
WHERE t1.pay_time 2018-05-29 00:00:00AND 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统计和特征分析方面更轻量化、便捷。
原文链接 本文为阿里云原创内容未经允许不得转载。
