技術文章 » Pisa-Proxy 之 SQL 解析實踐

Pisa-Proxy 之 SQL 解析實踐

2022-06-27 15:00:39

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 專案，但都存在一些問題。

ShardingSphere 實現了基於 Antlr 的不同的 SQL 方言解析，為了使用它的 Grammar，我們調研了 antlr_rust 專案，此專案不夠活躍，成熟度不夠高。

在 Rust 社群裡，sqlparser-rs 專案是一個較為成熟的庫，相容各種 SQL 方言，Pisa-Proxy 在未來也會支援多種資料來源，但是由於其詞法和語法解析都是純手工打造的，對我們來說會不易維護。

nom-sql 是基於 nom 庫實現的 SQL 解析器，但是未實現完整，效能測試不如預期。

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 是固定不變的, 因此 grm，stable 這兩個引數可以作為函數引數傳遞，更改為如下：

  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/

SphereEx 官網：https://www.sphere-ex.com