关于数据库:技术贴-SQL编译与执行

6次阅读

共计 4552 个字符，预计需要花费 12 分钟才能阅读完成。

SQL 编译与执行系列技术博客将依照以下程序别离介绍整个 SQL 执行引擎。

图一 SQL 编译与执行研读流程

parser 局部，包含词法解析和语法解析。
compile 局部，包含语义解析以及打算的构建。
optimize 局部，包含打算的优化。
exec 局部，包含执行打算的生成以及执行。

本文作为本系列第一篇文章，首先为大家介绍 parser 的外围设计，次要包含 SQL 词法以及语法的解析。

图二所示为一条 SQL 语句的整体解决流程，总体来说，一条 SQL 语句须要通过下述步骤：parser—构建逻辑打算—构建优化打算—构建物理打算—构建执行打算。

图二 SQL 执行流程 parser

过程最次要的目标就是解析输出的 SQL 语句，通过词法解析器解析为 token，通过语法解析器生成形象语法树，而后即可传入 SQL 执行引擎进行辨认和解决。

接着进入下一步，首先要对输出的数据进行有效性验证，解析并转换 AST 树，构建逻辑打算。接下来就是对生成的打算进行优化以找到代价最小的执行形式，依据优化好的逻辑打算构建可执行的物理打算，最初下发到各个节点进行分布式执行。

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 FromTable
SelectFiled:
           // FieldList 代表着一个字段列表“Select”FieldList
          |“Select”“*”FromTable:
             // 从一个表列表中获取“From”TableList
FieldList:
           // 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 解析。上述所示仅为一个简略的例子，实在应用的构造则会简单的多。

开务数据库应用了 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 解析成制订好的树结构。具备这些根底后，咱们就能够进行语法的增加以及批改，减少更多的解析规定，为后续操作做好筹备。

正文完