乐趣区

关于sql语句:PisaProxy-之-SQL-解析实践

SQL 语句解析是一个重要且简单的技术,数据库流量相干的 SQL 审计、读写拆散、分片等性能都依赖于 SQL 解析,而 Pisa-Proxy 作为 Database Mesh 理念的一个实际,对数据库流量的治理是其外围,因而实现 SQL 解析是一项很重要的工作。 本文将以 Pisa-Proxy 实际为例,为大家展示 Pisa-Proxy 中的 SQL 解析实现,遇到的问题及优化。

一、背景

对于语法分析

语法分析个别通过词法分析器,如 Flex,生成相应的 token,语法分析器通过剖析 token,来判断是否满足定义的语法规定。

语法分析器个别会通过解析生成器生成。

语法分析算法罕用的有以下:

  • LL(自上而下)

与上下文无关文法,从左到右扫描,从最左推导语法树,相比 LR 更容易了解,错误处理更敌对。

  • LR(自下而上)

与上下文无关文法,从左到右扫描,从最右节点推导语法树,相比 LL 速度快。

  • LALR

与 LR 相似,在解析时比 LR 生成的状态更少,从而缩小 Shift/Reduce 或者 Reduce/Reduce 抵触,被业界宽泛应用的 bison/yacc 生成的就是基于 LALR 解析器。

对于调研

在开发 SQL 解析之初,咱们从性能、维护性、开发效率、完成度四方面别离调研了 antlr_rust,sqlparser-rs,nom-sql 我的项目,但都存在一些问题。

  • antlr_rust

ShardingSphere 实现了基于 Antlr 的不同的 SQL 方言解析,为了应用它的 Grammar,咱们调研了 antlr_rust 我的项目,此我的项目不够沉闷,成熟度不够高。

  • sqlparser-rs

在 Rust 社区里,sqlparser-rs 我的项目是一个较为成熟的库,兼容各种 SQL 方言,Pisa-Proxy 在将来也会反对多种数据源,然而因为其词法和语法解析都是纯手工打造的,对咱们来说会不易保护。

  • nom-sql

nom-sql 是基于 nom 库实现的 SQL 解析器,然而未实现残缺,性能测试不如预期。

  • grmtools

Grmtools 是在寻找 Rust 相干的 Yacc 实现时发现的库,该库实现了兼容绝大部分 Yacc 性能,这样就能够复用 MySQL 官网的语法文件,然而须要手写 Lex 词法解析,通过对开发效率及完成度衡量后,咱们决定做难且正确的事,实现本人的 SQL 解析器,疾速实现一个 Demo 进行测试。

编码实现后,测试成果还不错。

总结如下:

工具 antlr_rust sqlparser-rs nom-sql grmtools
完成度
性能
维护性
开发效率

最终咱们抉择了 Grmtools 来开发 Pisa-Proxy 中的 SQL 解析。

二、Grmtools 应用

应用 Grmtools 解析库大抵分为两个步骤,上面以实现计算器为例。

  1. 编写 Lex 和 Yacc 文件

Lex:创立 calc.l,内容如下:

/%%
[0-9]+ "INT"
\+ "+"
\* "*"
\( "("
\) ")"
[\t]+ ;

Grammar:创立 calc.y 内容如下:

%start Expr
%avoid_insert "INT"
%%
Expr -> Result<u64, ()>:
      Expr '+' Term {Ok($1? + $3?) }
    | Term {$1}
    ;

Term -> Result<u64, ()>:
      Term '*' Factor {Ok($1? * $3?) }
    | Factor {$1}
    ;

Factor -> Result<u64, ()>:
      '(' Expr ')' {$2}
    | 'INT'
      {let v = $1.map_err(|_| ())?;
          parse_int($lexer.span_str(v.span()))
      }
    ;
%%
  1. 结构词法和语法解析器

Grmtools 须要在编译时生成词法和语法解析器,因而须要创立 build.rs,其内容如下:

use cfgrammar::yacc::YaccKind;
use lrlex::CTLexerBuilder;
fn main() -> Result<(), Box<dyn std::error::Error>> {CTLexerBuilder::new()
        .lrpar_config(|ctp| {ctp.yacckind(YaccKind::Grmtools)
                .grammar_in_src_dir("calc.y")
                .unwrap()})
        .lexer_in_src_dir("calc.l")?
        .build()?;
    Ok(())
}
  1. 在利用中集成解析
use std::env;

use lrlex::lrlex_mod;
use lrpar::lrpar_mod;

// Using `lrlex_mod!` brings the lexer for `calc.l` into scope. By default the
// module name will be `calc_l` (i.e. the file name, minus any extensions,
// with a suffix of `_l`).
lrlex_mod!("calc.l");
// Using `lrpar_mod!` brings the parser for `calc.y` into scope. By default the
// module name will be `calc_y` (i.e. the file name, minus any extensions,
// with a suffix of `_y`).
lrpar_mod!("calc.y");

fn main() {
    // Get the `LexerDef` for the `calc` language.
    let lexerdef = calc_l::lexerdef();
    let args: Vec<String> = env::args().collect();
    // Now we create a lexer with the `lexer` method with which we can lex an
    // input.
    let lexer = lexerdef.lexer(&args[1]);
    // Pass the lexer to the parser and lex and parse the input.
    let (res, errs) = calc_y::parse(&lexer);
    for e in errs {println!("{}", e.pp(&lexer, &calc_y::token_epp));
    }
    match res {Some(r) => println!("Result: {:?}", r),
        _ => eprintln!("Unable to evaluate expression.")
    }
}

详见: grmtools – grmtools

上文曾经提到,咱们须要手写词法解析,是因为在原生的 Grmtools 中,词法解析是用正则匹配的,对于灵便简单的 SQL 语句来说,不足以满足,因而须要手工打造词法解析,在 Grmtools 中实现自定义词法解析须要咱们实现以下 Trait:

lrpar::NonStreamingLexer

另外也提供了一个不便的办法去实例化:

lrlex::LRNonStreamingLexer::new()

三、遇到的问题

基于以上,咱们开发了 SQL 词法解析,复用了 MySQL 官网的 sql_yacc 文件,在开发过程中,也遇到了以下问题。

  1. Shift/Reduce 谬误
Shift/Reduce conflicts:
     State 619: Shift("TEXT_STRING") / Reduce(literal: "text_literal")

这是应用 LALR 算法经常出现的谬误,谬误成因个别通过剖析相干规定解决,例如常见的 If-Else 语句,规定如下:

%nonassoc LOWER_THEN_ELSE 
%nonassoc ELSE 
stmt: 
    IF expr stmt %prec LOWER_THEN_ELSE
  | IF expr stmt ELSE stmt

当 ELSE 被扫描入栈时,此时会有两种状况。

1)按第二条规定持续 Shift

2)按第一条规定进行 Reduce

这就是经典的 Shift/Reduce 谬误。

回到咱们的问题,有如以下规定:

literal -> String:
    text_literal 
    { }
  | NUM_literal  
    { }
 ...
 
 text_literal -> String:
    'TEXT_STRING' {}
  | 'NCHAR_STRING' {}
  | text_literal 'TEXT_STRING' {}
 ...

剖析:

stack Input token action
test Shift test
test $ Reduce: text_literal/Shift: TEXT_STRING

计划:

须要设置优先级解决,给 text_literal 设置更低的优先级,如以下:

%nonassoc 'LOWER_THEN_TEXT_STRING'
%nonassoc 'TEXT_STRING'


literal -> String:
    text_literal  %prec 'LOWER_THEN_TEXT_STRING' 
    { }
  | NUM_literal  
    { }
 ...
 
 text_literal -> String:
    'TEXT_STRING' {}
  | 'NCHAR_STRING' {}
  | text_literal 'TEXT_STRING' {}
 ...
  1. SQL 蕴含中文问题

在应用词法解析时,.chars() 生成字符串数组会呈现数组长度和字符长度不统一的状况,导致解析出错,要更改为 .as_bytes() 办法。

四、优化

  1. 在空跑解析(测试代码见附录),不执行 action 的状况下,性能如下:
[mworks@fedora examples]$ time ./parser

real        0m4.788s
user        0m4.781s
sys         0m0.002s

尝试优化,以下是火焰图:

通过火焰图发现,大部分 CPU 耗时在序列化和反序列化,以下是定位到的代码:

能够看出在每次解析的时候都须要反序列化数据,在编译完之后,__GRM_DATA__STABLE_DATA 是固定不变的, 因而 grmstable 这两个参数能够作为函数参数传递,更改为如下:

  1. 再剖析,每次解析的时候,都会初始化一个 actions 的数组,随着 grammar 中语法规定的增多,actions 的数组也会随之增大,且数组元素类型是 dyn trait 的援用,在运行时是有开销的。

再看代码,发现 actions 数组是有法则的,如以下:

::std::vec![&__gt_wrapper_0,
               &__gt_wrapper_1,
               &__gt_wrapper_2,
               ...
            ]

因而咱们能够手动构造函数,以下是伪代码:

match idx {0 => __gt_wrapper_0(),
    1 => __gt_wrapper_1(),
    2 => __gt_wrapper_2(),
    ....
}

通过 gobolt 查看汇编,发现差别还是很大,省去了数组的相干开销,也能极大地缩小内存应用。

详见:https://rust.godbolt.org/z/zTjW479f6

然而随着 actions 数组的一直增大,会有大量的 je,jmp 指令,不分明是否会影响 CPU 的分支预测,如影响是否能够通过 likely/unlikely 形式优化,目前还没有进行测试。

最终火焰图比照

最终测试后果

[mworks@fedora examples]$ time ./parser

real        0m2.677s
user        0m2.667s
sys         0m0.007s

五、总结

本文为 Pisa-Proxy SQL 解析解读系列第一篇,介绍了在 Pisa-Proxy 中开发 SQL 解析背地的故事,后续咱们会陆续为大家具体介绍 Yacc 语法规定的编写,Grmtools 中组件及实用工具等内容,敬请期待。

附录

Pisa-Proxy 的 SQL 解析代码:

pisanix/pisa-proxy/parser/mysql at master · database-mesh/pisan

测试代码

    let input = "select id, name from t where id = ?;"
    let p = parser::Parser::new();
    for _ in 0..1_000_000
    {let _ = p.parse(input);
    }

Pisanix

我的项目地址:https://github.com/database-mesh/pisanix

官网地址:https://www.pisanix.io/

Database Mesh:https://www.database-mesh.io/

退出移动版