技術貼 | SQL編譯與執行-parser

語言: CN / TW / HK

時間 2023-01-03 16:02:15 KaiwuDB

主題:

前言

SQL 編譯與執行系列技術博客將按照以下順序分別介紹整個 SQL 執行引擎。

圖一 SQL 編譯與執行研讀流程

parser 部分，包括詞法解析和語法解析。
compile 部分，包括語義解析以及計劃的構建。
optimize 部分，包括計劃的優化。
exec 部分，包括執行計劃的生成以及執行。

本文作為本系列第一篇文章，首先為大家介紹 parser 的核心設計，主要包括 SQL 詞法以及語法的解析。

一、SQL 執行流程

圖二所示為一條 SQL 語句的整體處理流程，總體來説，一條 SQL 語句需要經過下述步驟：parser—構建邏輯計劃—構建優化計劃—構建物理計劃—構建執行計劃。

圖二 SQL執行流程

parser 過程最主要的目的就是解析輸入的 SQL 語句，通過詞法解析器解析為 token，通過語法解析器生成抽象語法樹，而後即可傳入 SQL 執行引擎進行識別和處理。

接着進入下一步，首先要對輸入的數據進行有效性驗證，解析並轉換 AST 樹，構建邏輯計劃。接下來就是對生成的計劃進行優化以找到代價最小的執行方式，根據優化好的邏輯計劃構建可執行的物理計劃，最後下發到各個節點進行分佈式執行。

二、Lex & Yacc

Lex 代表 Lexical Analyzar（詞法分析器），Yacc 代表 Yet Another Compiler Compiler（編譯器代碼生成器）。它們分別是用來生成詞法分析器和語法分析器的工具，Lex 和 Yacc 在 UNIX 下分別叫 Flex 和 Bison。

詞法解析是編譯的第一步，將語句拆分為 token，移除空格和註釋，逐個讀入源碼中的 character，檢查是否有效並傳遞給語法分析器。語法分析器以 token-stream 的形式從詞法分析器獲取輸入；解析器根據規則文件生成的規則將 token 解析成一個抽象語法樹的結構，如圖三所示。

圖三 Lex & Yacc 執行流程

從上圖的執行流程可以看出，我們需要分別為 Lex 和 Yacc 提供對應的規則文件，Lex & Yacc 根據給定的規則，生成符合需求的詞法分析器和語法分析器。一般這兩種配置都是文本文件且結構相同：

... definitions ...%%... rules ...%%... subroutines …

文件通過 %% 分成三部分，最上面定義了各種名稱，例如各種表達式、token 等，中間則是重點的規則，首先看一下 Lex 的規則文件：

...%%/* 變量 */[a-z]    {            yylval = *yytext - 'a';            return VARIABLE;         }  /* 整數 */[0-9]+   {            yylval = atoi(yytext);            return INTEGER;         }/* 操作符 */[-+()=/*\n] { return *yytext; }/* 跳過空格 */[ \t]    ;/* 其他格式報錯 */.        yyerror("invalid character");%%…

對於詞法解析對應的規則，可以看出，左邊是掃出來的字符內容，通過正則表達式進行匹配，如果匹配到即返回右邊大括號中運行的結果。再看看 Yacc 對應的規則文件：

%token INTEGER VARIABLE%left '+' '-'%left '*' '/'...%%program:        program statement '\n'        |        ;

statement:        expr                    { printf("%d\n", $1); }        | VARIABLE '=' expr     { sym[$1] = $3; }        ;       expr:        INTEGER        | VARIABLE              { $$ = sym[$1]; }        | expr '+' expr         { $$ = $1 + $3; }        | expr '-' expr         { $$ = $1 - $3; }        | expr '*' expr         { $$ = $1 * $3; }        | expr '/' expr         { $$ = $1 / $3; }        | '(' expr ')'          { $$ = $2; }        ;%%…

首先是定義了 token 以及一些運算符。%left 代表左結合，同一行的運算符優先級是一樣的，不同行的越靠下優先級就越高。

語法規則使用了巴科斯範式（BNF）定義，它不僅能嚴格地表示語法規則，而且所描述的語法是與上下文無關的。它具有語法簡單，表示明確，便於語法分析和編譯的特點。每條規則的左部是一個非終結符，右部是由非終結符和終結符組成的一個符號串。具有相同左部的規則可以共用一個左部，各右部之間以直豎“|”隔開。

解析表達式是生成表達式的逆向操作，我們需要歸宿表達式到一個非終結符。Yacc 生成的語法分析器使用自底向上的歸約（shift-reduce）方式進行語法解析，同時使用堆棧保存中間狀態。簡單的以一條 select 為例：

// 有引號的代表終結符，沒有的代表非終結符。SelectStmt:             // 代表從哪些表裏獲取到哪些字段         SelectFiled FromTableSelectFiled:           // FieldList 代表着一個字段列表           “Select” FieldList          | “Select” “*”FromTable:             // 從一個表列表中獲取            “From” TableListFieldList:           // FieldList 可以是某個字段，也可以是多個字段，利用遞歸可以擴展到無數字段          “Field”         | FieldList “,” “Field”TableList:          // TableList同理           “Table”         | TableList “,” “Table”

當語法分析器進行語法分析的時候，用 . 代表當前讀取到的位置，以 SELECT * FROM test 為例：

     SELECT . * FROM test// 匹配到終結符SELECT，繼續執行→   SELECT * . FROM test// 此時堆棧裏的內容匹配到 SelectFiled，將 SELECT *彈出，SelectFiled 壓入到堆棧→   SelectFiled . FROM test→   SelectFiled FROM . test→   SelectFiled FROM test .→   SelectFiled FROM TableList .→   SelectFiled FromTable .→   SelectStmt

通過一系列的轉換，我們就獲得了一個 SelectStmt，而整個過程就可以構造一棵樹，用於 SQL 解析。上述所示僅為一個簡單的例子，真實使用的結構則會複雜的多。

三、SQL parser

開務數據庫使用了 Goyacc 生成語法分析器，而 Lex 則是手寫出來的，實現了 Goyacc 中要求的接口，對應 sql/pkg/sql/parser/scan.go pkg/sql/parser/lexer.go，實現了詞法分析的功能。

語法分析器所對應的功能在 sql.y 文件下。該文件仍符合上文所述 Yacc 規則文件格式，但沒有第三部分 subroutines，第一部分主要就是對一些 token、表達式、優先級、結合性的定義，其中有一個 union 結構體。

%union {  id    int32  pos   int32  str   string  union sqlSymUnion}

該結構體會在 sql.go 生成文件裏面生成一個對應的結構體，主要用來定義表達式和 token 的類型，存放解析過程中 token 的相關變量信息以及最後生成的 AST 信息。此外，還有一些對 token（終結符）和表達式（非終結符）的定義。

%token <str> IDENT SCONST BCONST BITCONST…%type <tree.Statement> stmt_block%type <tree.Statement> stmt…%left      AND%right     NOT%left      AND_AND%nonassoc  IS ISNULL NOTNULL %nonassoc  '<' '>' '=' LESS_EQUALS GREATER_EQUALS NOT_EQUALS…%%

下面是關於 rule 的定義，以 create table 為例：

create_table_stmt:  CREATE opt_temp_create_table TABLE table_name '(' opt_table_elem_list ')' opt_interleave opt_partition_by opt_table_with opt_create_table_on_commit  {    name := $4.unresolvedObjectName().ToTableName()    $$.val = &tree.CreateTable{      Table: name,      IfNotExists: false,      Interleave: $8.interleave(),      Defs: $6.tblDefs(),      AsSource: nil,      PartitionBy: $9.partitionBy(),      Temporary: $2.persistenceType(),      StorageParams: $10.storageParams(),      OnCommit: $11.createTableOnCommitSetting(),    }  }| CREATE opt_temp_create_table TABLE IF NOT EXISTS table_name '(' opt_table_elem_list ')' opt_interleave opt_partition_by opt_table_with opt_create_table_on_commit  {    name := $7.unresolvedObjectName().ToTableName()    $$.val = &tree.CreateTable{      Table: name,      IfNotExists: true,      Interleave: $11.interleave(),      Defs: $9.tblDefs(),      AsSource: nil,      PartitionBy: $12.partitionBy(),      Temporary: $2.persistenceType(),      StorageParams: $13.storageParams(),      OnCommit: $14.createTableOnCommitSetting(),    }  }

可以看出，除了上述所説的一些終結符和非終結符外，還有一個大括號，大括號裏面的內容就是當匹配時進行的一些操作，主要就是構建出所需要的 AST。

其中 $1 對應的就是匹配到的第一個字符，$4 就是 table_name 這一部分，最後產生的 CreateTable 這個結構體就對應着 tree 包下的結構體。

type CreateTable struct {   IfNotExists   bool   Table         TableName   Interleave    *InterleaveDef   PartitionBy   *PartitionBy   Temporary     bool   StorageParams StorageParams   OnCommit      CreateTableOnCommitSetting   Defs     TableDefs   AsSource *Select}

通過生成的 sql.go 中的 parse 就可以將 token-stream 生成一個 AST 對應的結構。

總結

以上就是開務數據庫的 SQL parser 詞法解析和語法解析部分，主要是語法解析部分使用 Goyacc 工具將 sql.y 中的規則生成對應的語法分析器，將詞法分析器生成的 token-stream 解析成制定好的樹結構。具備這些基礎後，我們就可以進行語法的添加以及修改，增加更多的解析規則，為後續操作做好準備。

「其他文章」