SQL parsing practice of Pisa proxy

SQL  Statement parsing is an important and complex technology , Database traffic related  SQL  Audit 、 Read / write separation 、 Slicing and other functions depend on  SQL  analysis , and  Pisa-Proxy  As  Database Mesh  A practice of the idea , The management of database traffic is its core , So realize  SQL  Parsing is a very important job .

This article will be  Pisa-Proxy  Practice as an example , Show you  Pisa-Proxy  Medium  SQL  Parsing implementation , Problems encountered and optimization .

One 、 background

About parsing

Parsing is usually done through a lexical analyzer , Such as  Flex, Generate corresponding  token, The parser parses  token, To determine whether the defined syntax rules are met .

Parsers are usually generated by parsing generators .

Syntax analysis algorithms are commonly used as follows ：

• LL（ From top to bottom ）

Context free grammar , Scan from left to right , Derive the syntax tree from the leftmost , comparison  LR  Easier to understand , Error handling is more friendly .

• LR（ Bottom up ）

Context free grammar , Scan from left to right , Derive the syntax tree from the rightmost node , comparison  LL  Fast .

• LALR

And  LR  similar , When parsing, the  LR  Fewer states are generated , Thereby reducing  Shift/Reduce  perhaps  Reduce/Reduce  Conflict , Widely used in the industry  bison/yacc  What is generated is based on  LALR  Parser .

About research

Developing  SQL  At the beginning of analysis , From performance 、 Maintenance 、 Development efficiency 、 The degree of completion has been investigated in four aspects  antlr_rust,sqlparser-rs,nom-sql  project , But there are some problems .

• antlr_rust

ShardingSphere  Based on  Antlr  Different  SQL  Dialect analysis , In order to use its  Grammar, We investigated  antlr_rust  project , This project is not active enough , Not mature enough .

• sqlparser-rs

stay  Rust  In the community ,sqlparser-rs  The project is a relatively mature library , Compatible with all kinds of  SQL  dialect ,Pisa-Proxy  It will also support multiple data sources in the future , However, its lexical and grammatical analysis are all made by hand , It will be difficult for us to maintain .

• nom-sql

nom-sql  Is based on  nom  Library implementation of  SQL  Parser , But not complete , The performance test is not as good as expected .

• grmtools

Grmtools  Is looking for  Rust  dependent  Yacc  Libraries discovered during implementation , The library is compatible with most  Yacc  function , So you can reuse  MySQL  Official grammar file , But you need to write by hand  Lex  lexing , After weighing the development efficiency and completion , We decided to do something difficult and right , Realize one's own  SQL  Parser , Quickly implement a  Demo  To test .

After coding , The test results are good .

Summarized below ：

In the end, we chose  Grmtools  To develop  Pisa-Proxy  Medium  SQL  analysis .

Two 、Grmtools  Use

Use  Grmtools  The parsing library is roughly divided into two steps , Let's take the implementation of calculator as an example .

• To write  Lex  and  Yacc  file

Lex： establish  calc.l, The contents are as follows ：

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


Grammar： establish  calc.y  The contents are as follows ：

%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()))
 }
 ;
%%


• Construct lexical and grammatical parsers

Grmtools  You need to generate lexical and grammatical parsers at compile time , So you need to create  build.rs, It reads as follows ：

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(&quot;calc.y&quot;)
 .unwrap()
 })
 .lexer_in_src_dir(&quot;calc.l&quot;)?
 .build()?;
 Ok(())
}


• Integrate parsing in the application

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!(&quot;{}&quot;, e.pp(&lexer, &calc_y::token_epp));
 }
 match res {
 Some(r) => println!(&quot;Result: {:?}&quot;, r),
 _ => eprintln!(&quot;Unable to evaluate expression.&quot;)
 }
}


See : 

grmtools - grmtools

As mentioned above , We need handwriting lexical analysis , Because in the original  Grmtools  in , Lexical parsing uses regular matching , For flexible and complex  SQL  The statement is , Not enough to satisfy , Therefore, it is necessary to create lexical analysis by hand , stay  Grmtools  To implement custom lexical parsing in, we need to implement the following  Trait：

lrpar::NonStreamingLexer


It also provides a convenient way to instantiate ：

lrlex::LRNonStreamingLexer::new()


3、 ... and 、 Problems encountered

Based on the above , We developed  SQL  lexing , Reuse the  MySQL  Official  sql_yacc  file , In the development process , Also encountered the following problems .

• Shift/Reduce  error

Shift/Reduce conflicts:
 State 619: Shift("TEXT_STRING") / Reduce(literal: "text_literal")


This is the use of  LALR  Common mistakes in algorithms , The causes of errors are generally solved by analyzing relevant rules , For example, common  If-Else  sentence , The following rules ：

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


When  ELSE  When being scanned into the stack , There are two situations .

1） Continue according to the second rule  Shift

2） Follow the first rule  Reduce

This is the classic  Shift/Reduce  error .

Back to our question , The following rules apply ：

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


analysis ：

programme ：

Priority needs to be set to solve , to  text_literal  Set a lower priority , As below ：

%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' {}
 ...


• SQL  Contains Chinese questions

When using lexical parsing ,.chars()  When a string array is generated, the length of the array is inconsistent with that of the character , Cause parsing error , To change to  .as_bytes()  Method .

Four 、 Optimize

• Analyze in the air （ See Appendix for test code ）, Don't execute  action  Under the circumstances , The performance is as follows ：

[[email protected] examples]$ time ./parser

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


Try to optimize , Here is the flame diagram ：

Find out from the flame diagram , Most of the  CPU  Time consuming in serialization and deserialization , Here is the code to navigate to ：

It can be seen that the data needs to be deserialized every time it is parsed , After compiling ,

__GRM_DATA

  and  

__STABLE_DATA

  It's fixed ,  therefore  

grm

,

stable

  These two parameters can be passed as function parameters , Change to the following ：

• reanalysis , Every time you parse , Will initialize a  actions  Array of , With  grammar  The increase of grammatical rules in ,actions  The array of will also grow , And the array element type is  dyn trait  References to , There is overhead at runtime .

Look at the code , Find out  actions  Arrays are regular , As below ：

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


So we can manually construct , Here is the pseudo code ：

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


adopt  gobolt  Check the assembly , The difference is still very big , This saves the array overhead , It can also greatly reduce memory usage .

See ：

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

But as the  actions  The array keeps growing , There will be a lot of  je,jmp  Instructions , It is not clear whether it will affect  CPU  Branch prediction of , Such as whether the influence can be passed  likely/unlikely  Way optimization , There is no test yet .

Final flame diagram comparison

Final test results

[[email protected] examples]$ time ./parser

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


5、 ... and 、 summary

This paper is about  Pisa-Proxy SQL  The first in the series of analysis and interpretation , This paper introduces the in  Pisa-Proxy  In the development  SQL  Analyze the story behind , In the future, we will give you a detailed introduction  Yacc  Writing grammar rules ,Grmtools  Components and utilities in , Coming soon .

appendix

Pisa-Proxy  Of  SQL  Parsing code ：

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

Test code

 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

Project address ：

https://github.com/database-mesh/pisanix

Official website address ：

https://www.pisanix.io/

Database Mesh：

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

SphereEx  Official website ：

https://www.sphere-ex.com