SQL（StructuredQueryLanguage），作为一种领域语言（编程语言），最早用于关系型数据库，方便管理结构化数据；各种类型的语言组成，包括数据定义语言、数据控制语言、数据操作语言；每个数据库产品都有不同的声明和实现；用户可以方便地使用SQL来操作数据，数据库系统中的词法语法分析器负责分析和理解SQL文本的含义，包括词法分析、句法分析、语义分析3部分。词法解析器生成的AST（AbstractSyntaxTree）会被优化器处理生成执行计划，然后被执行引擎执行。下图以MySQL架构为例展示了词法解析器的位置。本文介绍了词法解析器技术和行业实践，以及以往使用自动生成词法解析器遇到的问题，分享了自研SQLParser的设计与实践，以及性能和功能的改进带来。1、行业产品如何开发SQLParser？根据解析器代码开发方式，可以分为以下两种：1.自动生成为了方便开发词法语法分析的过程，业界有很多词法语法分析工具，例如：Flex，Lex、Bison工具常用于生成、C++作为目标语言的词法代码；如果使用Java作为目标语言，可以使用流行的工具，如ANTLR和JavaCC。ANTLR和JavaCC工具都使用用户编写的词法文法规则文件作为输入，文法文件需要满足EBNF（扩展巴科斯-瑙尔形式）[1]文法规则，这两个工具使用LL(k)(Left-to-right,Leftmostderivation)[2]算法“自上而下[3]”解析SQL文本并构造SQLAST、Presto、Spark、Hive等数据库和大数据系统大多是通过这种方式生成的。生成的代码包括词法和语法分析部分。语义分析还需要结合Meta数据，由各个数据库的核心进行处理；自动生成工具[4]的更多功能和算法比较见参考资料。2、手工编写不同于自动生成工具。InfluxDB、H2、Clickhouse等流行数据库的SQLParser组件都是手工编写的。优点：代码逻辑清晰，方便开发者调试排查问题；更好的性能：给开发者更多的代码优化空间，可以使用更好的算法和数据结构来提升性能；独立控制：无许可限制，可读性和可维护性更高；无需依赖第三方词法语法代码生成工具。缺点：对开发者的技术要求比较高，需要了解编译的原理和技术；开发工作量比较大，需要花费大量的时间和精力去实现MySQL通用语法的各个分支；需要长时间和大规模的测试才能趋于稳定。二、问题与挑战1、复杂查询的性能问题在实时分析型数据库的实际生产环境中，往往需要处理上千行的复杂查询请求或深度嵌套的查询请求。自动生成的解析器，由于状态机管理复杂，线程栈太深，导致词法语法分析阶段个别查询请求性能下降严重。2.大规模写入吞吐量问题分析型数据库要稳定应对大容量、高并发的写入场景，要求SQLParser组件具有良好的性能和稳定性。我们尝试过使用ANTLR、JavaCC等工具生成SQL词法的语法解析器，在大批量写入时，values子句在解析过程中会生成过多的AST临时对象，导致耗时问题的垃圾收集。3.QueryRewriting的灵活性需要快速方便的遍历AST树，找到满足一定规则的叶子节点，修改节点。自动生成的解析器无法灵活支持。自动生成的代码可读性差，排错成本高，复杂查询场景性能不足，影响系统稳定性和版本迭代速度；在设计之初，我们就放弃了自动生成的技术方案，完全手工编写了词法句法分析器。3、自研词法分析器的技术要点。自动生成工具主要处理下图左侧SQLParserCore和SQLTreeNodes的生成。右边的features部分需要开发者处理。当右边的功能（例如：SQL重写）对左边的Tree节点的修改功能有更多的要求，无法修改自动生成的代码。自动生成工具是为生成通用语法分析器而设计的。对于SQL这种特定的领域语言，有特定的优化技术来提高稳定性和性能。从设计之初，我们就选择LL(k)作为文法分析的算法。其自上而下的特点，在手动编写分析器时，逻辑清晰，代码易读，便于开发和维护。LL(k)的“左递归”问题可以通过手动决策循环编程来避免。1.词法和语法分析在词法分析中，Lexer不断地读取连续的SQL文本，将一段具有一定特征的连续文本识别为Token，并识别出Token的类别，比如赋值语句x=30，经过词法分析x,=,30分别标识为ID、等号运算符、数值常量；特别是在识别标识符（变量、表名、列名等）和保留字（TABLE、FROM、SELECT等）时，需要反复比较字符串。自动生成工具在这个阶段使用DFA（DeterministicFiniteAutomaton）和预定义的词法文件来确定每个Token的值和类型。手动编写解析器不需要维护额外的状态机，并使用分支预测来减少计算量和调用堆栈的深度。语法分析器将词法分析中的Token作为输入，以SQL语法描述为规则，从上到下展开非叶子节点，构建语法树。整个过程就像走迷宫一样，只有一个正确的入口和出口，完成迷宫后，会生成一个正确的AST。快速令牌比较selECTc1FromT1;由于大多数数据库系统是不区分大小写的，所以上面查询中的selECT和From会被识别为保留字，c1和T1会被识别为标识符。要识别两者的不同类型，字符串匹配操作必不可少。通常，将字符统一转换为大写或小写，然后比较字面值是一种可行的解决方案。首先根据Map初始化内存中的数据库保留字，key为保留字的大写字符串，value为Token类型；当key转为大写时，可以使用ASCII值+32的方法代替toUpperCase()方法，在不影响正确性的前提下，性能可以提高数倍。快速数值分析在解析常量值时，通常的做法是读取SQL中的字符串，将字符串作为参数，调用Java自带的Integer.parseInt()/Float.parseFloat()/Long.parseLong()，即可直接在原文上读取并计算数值。这个过程只使用基本类型，避免构造字符串，节省内存，提高解析速度。对于大批量写入值的场景，这种优化非常明显。避免回溯[5]在SQL语法解析的过程中，通常只需要预读一个Token就可以决定如何建立语法节点之间的关系，或者说建立哪个语法节点。有的语法分支分支比较多，需要预读两个以上。只有令牌才能做出判断。预读多个Token可以减少回溯带来的性能消耗。在极少数情况下，超过2个Token预读不匹配正确的语法分支。需要取消预读，去其他分院；为了提高撤销速度，可以在预读前保存Token位置，撤销时可以快速回到保存点。在insertintovalues语句中，常量字面值出现的概率高于其他token。分支预测可以减少判断逻辑，避免回溯，提高性能。表达式替换查询重写[6]技术基于“关系代数”修改AST。在保证正确性的前提下，新的AST具有更好的执行性能。例如A、B两张表的大小相差很大，错误的Join顺序对数据库系统不友好，通过改变A、B表的Join顺序可以获得更高的执行性能。该工具生成的解析器通常不允许直接更改AST的节点。AST的每一个节点变化，都需要重新构建整个AST，性能不好。在自研的Parser中，每个AST节点类都实现了replace接口，只需要修改AST中的子树即可达到重写的目的。publicinterfaceReplaceable{booleanreplace(Nodeexpr,Nodetarget);}publicclassBetweenNodeimplementsReplaceable{publicNodebeginExpr;publicNodeendExpr;@OverridepublicinthashCode(){...}@Overridepublicbooleanequals(Objectobj){...}@Overridepublicbooleanreplace(SQLExprexpr==exprexpr){{setBeginExpr(target);returntrue;}if(expr==endExpr){setEndExpr(target);returntrue;}returnfalse;}}其他优化支持ASTClone：如果原AST结构不变，则克隆一个新的AST，修改节点结构中的新的AST，比如：增加Hint，删除where条件，增加limit限制等。维护AST父子关系：自动生成的解析器维护父子节点的关系，这是一种单向引用关系。手写代码可以增加子节点对父节点的引用，构建AST节点的双向引用关系，实现节点的快速“跳转”，让AST遍历更加高效。publicabstractclassNode{publicabstractListgetChildren()}publicclassBetweenNodetendsNode{publicNodebeginExpr;publicNodeendExpr;@OverridepublicListgetChildren(){returnArrays.asList(beginExpr,this.endExpr);}@OverridepublicBetweenNodeclone(){BetweenNodex=;if(beginExpr!=null){x.setBeginExpr(beginExpr.clone());}if(endExpr!=null){x.setEndExpr(endExpr.clone());}returnx;}publicvoidsetBeginExpr(NodebeginExpr){if(beginExpr!=null){beginExpr.setParent(this);}this.beginExpr=beginExpr;}publicvoidsetEndExpr(NodeendExpr){if(endExpr!=null){endExpr.setParent(this);}this.endExpr=endExpr;}}2.语义分析写事件回调前面提到，在大量导入数据时，词法语法分析阶段会产生很多小的AST对象，给垃圾回收带来压力。解决这个问题的核心是尽量使用基本数据类型，尽量不要生成AST节点对象。要从词法分析阶段入手，避免进入句法分析阶段。在词法分析阶段，实现write接口的类允许外部注册。每当词法分析器解析出values中的每一个具体值，或者完全解析出values中的一行时，它同时回调write接口，实现写数据库。逻辑。publicinterfaceInsertValueHandler{ObjectnewRow()throwsSQLException;voidprocessInteger(Objectrow,intindex,Numbervalue);voidprocessString(Objectrow,intindex,Stringvalue);voidprocessDate(Objectrow,intindex,Stringvalue);voidprocessDate(Objectrow,intindex,java.util.Datevalue);voidprocessTimestamp(Objectrow,intindex,Stringvalue);voidprocessTimestamp(Objectrow,intindex,java.util.Datevalue);voidprocessTime(Objectrow,intindex,Stringvalue);voidprocessDecimal(Objectrow,intindex,BigDecimalvalue);voidprocessBoolean(Objectrow,intindex,booleanvalue);voidprocessNull(Objectrow,intindex);voidprocessFunction(Objectrow,intindex,StringfuncName,Object...values);voidprocessRow(Objectrow);voidprocessComplete();}publicclassBatchInsertHandlerimplementsInsertValueHandler{...}publicclassApplication{BatchInsertHandlerhandler=newBatchInsertHandler();parser.parseInsertHeader();//头部：解析insertintoxxxvalues部分parser.parseValues(handler);//批量值：values(xxx),(xxx),(xxx)部分}查询重写ng手工编写的SQLParser可以更灵活地与优化器配合，将查询重写的部分优化能力预加载到SQLParser中，使优化器可以更专注于基于成本和成本的优化。Parser可以结合Meta信息，使用“等价关系代数”在AST上实现QueryRewriting功能，以低成本提高查询性能，例如：常量折叠、函数变换、条件下推或提升、类型推导、隐式转换、语义去重等。首先需要设计一个结构体来存储目录和表结构信息，包括库名、表名、列名、列类型等。然后，使用“访问者模式”编写Visitor程序，通过“遍历AST”depthfirst”，分析字段、函数、表达式、运算符，结合表结构和类型信息推断表达式类型。注意，在嵌套的查询语句中，同一个表达式出现在不同的位置，属于不同的范围。最后，AST会通过《等价关系代数》中写的RBO（Rule-BasedOptimization）规则进行处理，从而达到优化器的目的。--常量折叠示例SELECT*FROMT1WHEREc_weekBETWEENCAST(date_format(date_add('day',-day_of_week('20180605'),date('20180605')),'%Y%m&d')asbigint)ANDCAST(date_format(date_add('day',-day_of_week('20180606'),date('20180606')),'%Y%m&d')asbigint)------------折叠后----------SELECT*fromT1WHEREc_weekBETWEEN20180602and20180603--函数转换示例SELECT*FROMT1WHEREDATE_FORMAT(t1."pay_time",'%Y%m%d')>='20180529'ANDDATE_FORMAT(t1."pay_time",'%Y%m%d')<='20180529'------------转换后，更好地利用索引------------SELECT*FROMT1WHEREt1."pay_time">='2018-05-2900:00:00'ANDt1."pay_time"<'2018-05-3000:00:00'4.优化后的SQLParser性能和稳定性相比TPC-DS的99查询有明显提升[7]可以看到手写SQLParser比ANTLRParser（使用ANTLR生成）快20倍，比JSQLParser（使用JavaCC生成）快30倍，批量Insert场景下，速度提升30到50倍次。本文介绍了自动生成工具生成的词法解析器和自研分析器的优劣权衡和考虑，结合OLAP吞吐量大和SQL复杂的业务特点，选择手动编写解析器。性能优化方式贴近SQL解析特性；在语义分析层面，结合Schema信息积累了很多语义分析工具，在离线或在线SQL统计和特征分析方面更加轻量和方便。
