首页 > 数据库 >Apache顶级项目ShardingSphere — SQL Parser的设计与实现

Apache顶级项目ShardingSphere — SQL Parser的设计与实现

时间：2024-08-30 16:05:34浏览次数：11  
标签：SQL ShardingSphere Parser 语法 NUM expr 解析

导语：SQL作为现代计算机行业的数据处理事实标准，是目前最重要的数据处理接口之一，从传统的DBMS(如MySQL、Oracle)，到主流的计算框架（如spark，flink）都提供了SQL的解析引擎，因此想对sql进行精细化的操作，一定离不开SQL Parser。Apache ShardingSphere 是一套开源的分布式数据库中间件解决方案组成的生态圈，需要对SQL进行精细化的操作，如改写，加密等，因此也实现了SQL Parser，并提供独立的Parser引擎。

先来认识一下传统数据库中一条SQL处理流程是怎样的，接受网络包-》数据库协议解析网络包的到sql-》SQL语法解析为抽象语法树-》把语法树转换成关系代数表达式树（逻辑执行计划）-》再转换成物理算子树（物理执行计划）-》遍历物理算子树执行相应算子的实现获取数据并返回。

一、工作原理

SQL Parser 的功能是把一条SQL解析为抽象语法树（AST），SQL Parser需要编译原理相关的知识，简单介绍一下。

SQL Parser 包含词法解析（Lexer）和语法解析(Parser)，词法解析的作用是把一个sql 分割成一个一个不可分割的单元，例子：

原始sql: select id,name from table1 where name=“xxx”;

词法解析器输入是原始sql，并且暴露一个接口nextToken(),每次调用nextToken()都会返回一个Token(表示上面所说的不可分割的元素)，伪代码如下：



String originSql = "select id,name from table1 where name='xxx'";
Lexer lexer = new Lexer(originSql);
while(!lexer._hitEOF){// 判断是否结束
  System.out.printLn(lexer.nextToken())
}
// 输出如下：
select
id
,
name
from
table1
where
name
=
'xxx'



语法分析器的作用是使用Lexer的输出（调用nextToken()）,构造出AST,以上面的sql为例，解析器得出的语法树如下：


在这里插入图片描述


 


1、Lexer（词法分析）原理


Lexer 也称为分词，从左向右扫描SQL，将其分割成一个个的toke(不可分割的，具有独立意义的单元，类似英语中的单词)。


Lexer的实现一般都是构造DFA(确定性有限状态自动机)来实现的，以一个例子说明。


状态转移图如下，这是一个能够识别标识符，数字和一般运算符的词法解析器。


在这里插入图片描述


代码实现可以使用传统的while case的模板实现，伪代码如下：




Class Token{...}
Enum State {
    BEGIN,OPERATER,IDENTIFIER,NUMBER
}

Class Lexer{
    String input = "...";
    State state = BEGIN;
    int index = 0;
    Token nextToken() {
        while(index < input.length) {
            Char char = input.charAt(index);
            switch (state) {
                case BEGIN: 
                    switch (char){
                        case a-zA-Z_ :
                            index++;
                            state = IDENTIFIER;
                        case +-*/ :
                            state = BEGIN
                            return Token(OPERATER)
                        case 0-9:
                            state = NUMBER;
                            index++;
                        default:
                            return null;
                    }
                case IDENTIFIER:
                    switch (char){
                        case a-zA-Z_0-9 :
                            index++;
                            state = IDENTIFIER;
                        default :
                            state = BEGIN;
                            index--;
                            return Token(IDENTIFIER)
                    }
                case NUMBER:
                    switch (char){
                        case 0-9 :
                            index++;
                            state = NUMBER;
                        default :
                            state = BEGIN;
                            index--;
                            return Token(NUMBER)
                    }
                
                default:
                    return null;
            }
        }
    }
}



 


2、Parser（语法解析） 原理


Parser阶段有两种类型方法来实现，一种是自顶向下分析法，另一种是自底向上分析法，简单介绍一下两种类型分析法的处理思路。


首先给出上下文无关语法和相关术语的定义：


    

  • 终结符集合 T （terminal set）
    • 



一个有限集合，其元素称为 终结符（terminal）


    

  • 非终结符集合 N （non-terminal set)
    • 



一个有限集合，与 T 无公共元素，其元素称为 非终结符（non-terminal）


    

  • 符号集合 V （alphabet）
    • 



T 和 N 的并集，其元素称为符号（symbol） 。因此终结符和非终结符都是符号。符号可用字母：A, B, C, X, Y, Z, a, b, c 等表示。


    

  • 符号串（a string of symbols）
    • 



一串符号，如 X1 X2 … Xn 。只有终结符的符号串称为 句子（sentence）。空串 （不含任何符号）也是一个符号串，用 ε 表示。符号串一般用小写字母 u, v, w 表示。


    

  • 产生式（production）
    • 



一个描述符号串如何转换的规则。对于上下文本无关语法，其固定形式为：A -> u ，其中 A 为非终结符， u 为一个符号串。


    

  • 产生式集合 P （production set）
    • 



一个由有限个产生式组成的集合


    

  • 展开（expand）
    • 



一个动作：将一个产生式 A -> u 应用到一个含有 A 的符号串 vAw 上，用 u 代替该符号串中的 A ，得到一个新的符号串 vuw。


    

  • 折叠（reduce）
    • 



一个动作：将一个产生式 A -> u 应用到一个含有 u 的符号串 vuw 上，用 A 代替该符号串中的 u ，得到一个新的符号串 vAw。


    

  • 起始符号 S （start symbol）
    • 



N 中的一个特定的元素


    

  • 推导（derivate）
    • 



一个过程：从一个符号串 u 开始，应用一系列的产生式，展开到另一个的符号串 v。若 v 可以由 u 推导得到，则可写成：u => v 。


    

  • 上下文本无关语法 G （context-free grammar, CFG）
    • 



一个 4 元组：(T, N, P, S) ，其中 T 为终结符集合， N 为非终结符集合， P 为产生式集合， S 为起始符号。一个句子如果能从语法 G 的 S 推导得到，可以直接称此句子由语法 G 推导得到，也可称此句子符合这个语法，或者说此句子属于 G 语言。G 语言（ G language） 就是语法 G 推导出来的所有句子的集合，有时也用 G 代表这个集合。


    

  • 解析（parse）
    • 



也称为分析，是一个过程：给定一个句子 s 和语法 G ，判断 s 是否属于 G ，如果是，则找出从起始符号推导得到 s 的全过程。推导过程中的任何符号串（包括起始符号和最终的句子）都称为 中间句子（working string）。


 


2.1 自顶向下分析法 LL(1)


LL(1) 是自顶向下分析法的一种，第一个L代表从左向右扫描待解析文本，第二个L代表从左向右展开，(1)代表每次读取一个Token。


以简单表达式为例子：




// 语法规则， 整个是一个产生式，左边expr为非终结符，NUM是一
//个Token，为终结符
expr: NUM | NUM expr
// 待解析文本 
1 2 23 45
1
2
3
4
5



解析过程如下：


在这里插入图片描述


我们的目标是将起始符号expr展开成句子 1 2 23 45


    

  1. 

    对比expr和NUM(1),只能选择expr -> NUM expr，才可以和NUM(1)匹配，展开后得NUM expr
    

    2. 

  2. 

    忽略已匹配的NUM(1), 再次读入NUM(2),只能选择expr -> NUM expr，展开后得NUM expr
    

    3. 

  3. 

    忽略已匹配的NUM(2),再次读入NUM(23),只能选择expr -> NUM expr，展开后得NUM expr
    

    4. 

  4. 

    忽略已匹配的NUM(23),再次读入NUM(45),只能选择expr -> NUM，展开后得NUM
    

    5. 

  5. 

    得到最终句子 NUM(1)NUM(2) NUM(23) NUM(45) 可接受，解析完成
    

    6. 



注意点：为什么1,2,3只能选择expr -> NUM expr， Lexer中会有接口判断是否得到末尾，ShardingSphere中接口是lexer._hitEOF。


 


2.1 自底向上分析法 LR(1)


自底向上分析的顺序和自顶向下分析的顺序相反，从给定的句子开始，不断的挑选出合适的产生式，将中间句子中的子串折叠为非终结符，最终折叠到起始符号。


LR(1) 是自底向上分析法的一种，第一个L代表从左向右扫描待解析文本，第二个R代表从右向坐折叠，(1)代表每次读取一个Token。


以简单表达式为例：




// 语法规则， 整个是一个产生式，左边expr为非终结符，NUM是一
//个Token，为终结符
expr: NUM | expr NUM
// 待解析文本 
1 2 23 45



解析过程是如下：


在这里插入图片描述


我们的目标是把 1 2 23 45 折叠为expr


    

  1. 

    读入NUM(1),发现只能选择expr -> NUM, 折叠得expr
    

    2. 

  2. 

    读入NUM(2),只能选择expr -> expr NUM,折叠得expr
    

    3. 

  3. 

    读入NUM(23),只能选择expr -> expr NUM, 折叠得expr
    

    4. 

  4. 

    读入NUM(45),只能选择expr-> expr NUM, 折叠得expr 可接受，解析完成
    

    5. 



二、ShardingSphere Parser 实现


实现Parser的方式一般分为两种，一种是写代码实现状态机来进行解析，另一种是通过解析器生成器根据定义的语法规则生成解析器，ShardingSphere使用第二种方式，这是由于衡量了性能，扩展性和容易维护因素最终决定的。


以ShardingSphere中的MySQL 解析引擎为例，模块shardingsphere-sql-parser-mysql，语法定义路径src/main/antlr。


在这里插入图片描述


功能点：


    

  • 

    提供独立的SQL解析引擎
    

    • 

  • 

    可以方便的对语法规则进行扩充和修改
    

    • 

  • 

    提供SQL 变量参数化功能
    

    • 

  • 

    提供SQL 格式化功能
    

    • 

  • 

    支持多种方言
    

    • 



数据库支持状态MySQL支持，完善PostgreSQL支持，完善SQLServer支持Oracle支持SQL92支持


使用方法：




//maven 依赖
<dependency>
    <groupId>org.apache.shardingsphere</groupId>
    <artifactId>shardingsphere-sql-parser-engine</artifactId>
    <version>${project.version}</version>
</dependency>
// 根据需要引入指定方言的解析模块（以MySQL为例）,可以添加所有支持的方言，也可以只添加使用到的
<dependency>
    <groupId>org.apache.shardingsphere</groupId>
    <artifactId>shardingsphere-sql-parser-mysql</artifactId>
    <version>${project.version}</version>
</dependency>
//获取语法树
/**
 * databaseType type:String 可能值 MySQL,Oracle，PostgreSQL，SQL92，SQLServer
 * sql type:String 解析的SQL
 * useCache type:boolean 是否使用缓存
 * @return parse tree
 */
ParseTree tree = new SQLParserEngine(databaseType).parse(sql, useCache); 
// 获取SQLStatement
/**
 * databaseType type:String 可能值 MySQL,Oracle，PostgreSQL，SQL92，SQLServer
 * useCache type:boolean 是否使用缓存
 * @return SQLStatement
 */
ParseTree tree = new SQLParserEngine(databaseType).parse(sql, useCache); 
SQLVisitorEngine sqlVisitorEngine = new SQLVisitorEngine(databaseType, "STATEMENT");
SQLStatement sqlStatement = sqlVisitorEngine.visit(tree);



 


三、常见解析器


 


1、MySQL Parser


词法解析通过手写代码的方式实现，语法解析通过定义语法规则，使用bison生成语法解析代码。


 


2、PostgreSQL Parser


通过定义语法规则，使用flex/bison生成词法，语法解析代码。


 


3、TIDB Parser（能够单独使用, golang）


词法解析通过手写代码的方式实现，语法解析通过定义语法规则，使用goyacc生成语法解析代码。


 


4、ShardingSphere Parser(能够单独使用, 多种目标语言c,c++,java, golang,python）


    

  • 通过定义语法规则，使用ANTLR生成词法，语法解析代码
    • 

  • 可以方便自定义语法
    • 

  • 提供缓存机制
    • 

  • SQL 格式化，SQL参数化
    • 

  • 支持多种DB: Mysql, PostgreSQL, SQLServer, Oracle, SQL92
    • 

  • 支持自定义visitor
    • 



 


5、alibaba druid（能够单独使用，java）


    

  • 通过代码的方式实现词法解析器和语法解析器
    • 

  • 支持多种DB: Mysql, PostgreSQL, SQLServer, Oracle, odps, db2, hive, SQL92
    • 

  • SQL 格式化，SQL参数化
    • 

  • 支持自定义visitor
    • 



 


6、Jsqlparser（能够单独使用, java）


    

  • 

    通过javacc定义语法解析规则实现
    

    • 

  • 

    不局限于某一个DB
    

    • 



注意：


    

  1. 

    基本都是通过定义语法来实现的，词法解析都是通过定义正则语言，构造有限状态自动机实现，区别是LL(自顶向下)语法和LR(自底向上)语法。
    

    2. 

  2. 

    antlr使用的是LL(自顶向下)的语法规则 改进的LL(*)算法，Bison和goyacc使用LR(自底向上)的语法规则，LALR算法，Jsqlparser是LL(k), druid目测类似LL(k)。
    

    3. 

  3. 

    LR相比LL表达能力更强，典型的例子是antlr不支持相互左递归，bison支持。
    

    4. 



四、AST(语法树)应用


    

  • 转化为逻辑执行计划，逻辑执行计划再转换为物理执行计划，物理执行计划用于存储引擎具体执行。
    • 



eg: select * from table1, table2 where table1.id=1 转化为逻辑执行计划为：


在这里插入图片描述


    

  • 通过遍历语法树，对SQL进行格式化，参数化等
    • 



参考文献


[1] LL(*)：https://www.antlr.org/papers/LL-star-PLDI11.pdf


[2] LALR：https://suif.stanford.edu/dragonbook/lecture-notes/Stanford-CS143/11-LALR-Parsing.pdf；http://www.cs.ecu.edu/karl/5220/spr16/Notes/Bottom-up/lalr.html


[3] TiDB优化器设计：https://pingcap.com/blog-cn/tidb-cascades-planner


[4] MySQL优化器设计：https://dev.mysql.com/doc/refman/8.0/en/cost-model.html



标签：SQL,ShardingSphere,Parser,语法,NUM,expr,解析	

From： https://www.cnblogs.com/Jcloud/p/18388914
      

      




      

      

        
相关文章

        

          
    
 
  • 对比 Vitess，ShardingSphere 有哪些不同
    本篇为InfoQ中文站供稿原文链接：https://www.infoq.cn/article/NHSAAmN*MfpLiTiTTEu5?from=timeline&isappinstalled=0ShardingSphere是什么？ShardingSphere是一套开源的分布式数据库中间件解决方案组成的生态圈，它由Sharding-JDBC、Sharding-Proxy和Sharding-Sidecar（规......
     
  • mysql参数和配置文件优先级
    mysqld-auto.cnf，持久化配置参数文件（位于DATA目录）（mysqld-auto.cnf中的变量如果和my.cnf相同则使用mysqld-auto.conf中的）命令行输入的配置参数代码中指定配置文件my.cnf中的配置参数命令行输入配置文件my.cnf中的配置参数/etc目录中的配置文件my.cnf中的配置参数/etc/mysql目录中......
     
  • Apache顶级项目ShardingSphere — SQL Parser的设计与实现
    导语：SQL作为现代计算机行业的数据处理事实标准，是目前最重要的数据处理接口之一，从传统的DBMS(如MySQL、Oracle)，到主流的计算框架（如spark，flink）都提供了SQL的解析引擎，因此想对sql进行精细化的操作，一定离不开SQLParser。ApacheShardingSphere是一套开源的分布式数据库中间件解决方案......
     
  • 对比 Vitess，ShardingSphere 有哪些不同
    本篇为InfoQ中文站供稿原文链接：https://www.infoq.cn/article/NHSAAmN*MfpLiTiTTEu5?from=timeline&isappinstalled=0ShardingSphere是什么？ShardingSphere是一套开源的分布式数据库中间件解决方案组成的生态圈，它由Sharding-JDBC、Sharding-Proxy和Sharding-Sidecar（规划中）这3......
     
  • 【Mysql】mysql count主键字段很慢超时 执行计划Select tables optimized away ，最终调
     背景： mysql表 主键字段count，速度很慢，耗时将近30s   从执行计划可以看出：explainSELECTCOUNT(rule_id)ASdataCountFROM`sku_safe_stock_rule`;   原理分析：SelecttablesoptimizedawaySELECT操作已经优化到不能再优化了(MySQL根本没有遍历......
     
  • MYSQL实现Oracle中decode函数
    背景：写oracle脚本迁移mysql时，mysql不支持decode函数思路：理解decode函数使用方法及参数含义1、decode(expression,value,result1,result2)     理解：如果expression=value，则输出result1，否则输出result22、decode(expression,value1,result1,value2,result2,value3,res......
     
  • SQL server 数据文件物理层面迁移
    背景当前有一套SQLserver数据库（Primary+Mirror）主备环境数据盘大小不一致，且灾备环境无法对磁盘进行扩容，需要对灾备环境进行整体数据文件迁移，满足当前数据库运行。停止数据库mirro同步select'use[master]ALTERDATABASE['+db_name(database_id)+']SETPARTNERSUSPEND'froms......
     
  • Mysql基础练习题 595.大的国家 （力扣）
            如果一个国家满足下述两个条件之一，则认为该国是大国：面积至少为300万平方公里（即，3000000km2），或者人口至少为2500万（即25000000）编写解决方案找出大国的国家名称、人口和面积，以任意顺序返回结果表。建表插入数据：CreatetableIfNotExistsWorld......
     
  • MySQL-进阶篇-SQL优化（插入数据优化、主键优化、order by优化、group by优化、limit优
    文章目录1.插入数据优化1.1使用批量插入1.2批量插入数据时手动提交事务1.3按主键的顺序插入1.4大批量插入数据时使用load指令2.主键优化2.1数据组织方式2.2页分裂2.3页合并2.4主键的设计原则2.4.1降低主键的长度2.4.2使用AUTO_INCREMENT自增主键2.4.3......
     
  • SQL语言简介
    一、SQL定义SQL：一门操作关系型数据库的编程语言，定义操作所有关系型数据库的统一标准。二、通用语法1、SQL语句可以单行或多行书写，以分号结尾，不加分号，程序会一直运行。2、SQL语句可以使用空格或缩进来增强语句的可读性。3、MySQL数据库的SQL语句不区分大小写。例：showdata......
     
    •            
          

        

      

    

    

      
赞助商

      




      

      
阅读排行

      

        
      

    

  





  
 
    
网站主页关于我们联系我们网站地图 

    
本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。 

    
Copyright © 2020-2023  IPS99  版权所有 IPS99