VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > 数据库 > sql数据库 >
  • sql语句大全之自己实现一个SQL解析引擎

功能:将用户输入的SQL语句序列转换为一个可执行的操作序列,并返回查询的结果集。
SQL的解析引擎包括查询编译与查询优化和查询的运行,主要包括3个步骤:

  1. 查询分析:
  2. 制定逻辑查询计划(优化相关)
  3. 制定物理查询计划(优化相关)
  • 查询分析: 将SQL语句表示成某种有用的语法树.
  • 制定逻辑查询计划: 把语法树转换成一个关系代数表达式或者类似的结构,这个结构通常称作逻辑计划。
  • 制定物理查询计划:把逻辑计划转换成物理查询计划,要求指定操作执行的顺序,每一步使用的算法,操作之间的传递方式等。
    查询分析各模块主要函数间的调用关系: 

    图1.SQL引擎间模块的调用关系

FLEX简介

flex是一个词法分析工具,其输入为后缀为.l的文件,输出为.c的文件. 示例是一个类似Unix的单词统计程序wc

 

[cpp] view plain copy
 
 
 
  1. %option noyywrap  
  2. %{  
  3.     int chars = 0;  
  4.     int words = 0;  
  5.     int lines = 0;  
  6. %}  
  7.   
  8. %%  
  9.   
  10. [_a-zA-Z][_a-zA-Z0-9]+ { words++; chars += strlen(yytext); }  
  11. \n { chars++ ; lines++; }  
  12. .  { chars++; }  
  13.   
  14. %%  
  15.   
  16. int main()  
  17. {  
  18.        yylex();  
  19.        printf("%8d %8d %8d\n",lines,words,chars);  
  20.     return 0;  
  21. }  


 

.l文件通常分为3部分:

 

[cpp] view plain copy
 
 
 
  1. %{  
  2.     definition  
  3. %}  
  4.   
  5. %%  
  6.     rules  
  7. %%  
  8.     code  


 

definition部分为定义部分,包括引入头文件,变量声明,函数声明,注释等,这部分会被原样拷贝到输出的.c文件中。
rules部分定义词法规则,使用正则表达式定义词法,后面大括号内则是扫描到对应词法时的动作代码。
code部分为C语言的代码。yylex为flex的函数,使用yylex开始扫描。
%option 指定flex扫描时的一些特性。yywrap通常在多文件扫描时定义使用。常用的一些选项有
noyywrap 不使用yywrap函数
yylineno 使用行号
case-insensitive 正则表达式规则大小写无关

flex文件的编译

 

[cpp] view plain copy
 
 
 
  1. flex  –o wc.c wc.l  
  2.    cc wc.c –o wc  


 

Bison简介

Bison作为一个语法分析器,输入为一个.y的文件,输出为一个.h文件和一个.c文件。通常Bison需要使用Flex作为协同的词法分析器来获取记号流。Flex识别正则表达式来获取记号,Bison则分析这些记号基于逻辑规则进行组合
计算器的示例:calc.y

 

[cpp] view plain copy
 
 
 
  1. %{  
  2. #include <stdio.h>  
  3. %}  
  4.   
  5. %token NUMBER  
  6. %token ADD SUB MUL DIV ABS  
  7. %token OP CP  
  8. %token EOL  
  9.   
  10. %%  
  11.   
  12. calclist:  
  13.     | calclist exp EOL {printf("=%d \n> ",$2);}  
  14.     | calclist EOL {printf("> ");}  
  15.     ;  
  16. exp: factor  
  17.     | exp ADD factor  {$$ = $1 + $3;}  
  18.     | exp SUB factor  {$$ = $1 - $3;}  
  19.     ;  
  20. factor:term  
  21.     | factor MUL term {$$ = $1 * $3;}  
  22.     | factor DIV term {$$ = $1 / $3;}  
  23.     ;  
  24. term:NUMBER  
  25.     | ABS term ABS { $$ = ($2 >= 0 ? $2 : -$2);}  
  26.     | OP exp CP    { $$ = $2;}  
  27.     ;  
  28. %%  
  29. int main(int argc,char *argv[])  
  30. {  
  31.     printf("> ");  
  32.     yyparse();  
  33.   
  34.     return 0;  
  35. }  
  36. void yyerror(char *s)  
  37. {  
  38.     fprintf(stderr,"error:%s:\n",s);  
  39. }  
  40.   
  41. Flex与Bison共享记号,值通过yylval在Flex与Bison间传递。对应的.l文件为  
  42.   
  43. %option noyywrap  
  44. %{  
  45. #include "fb1-5.tab.h"  
  46. #include <string.h>  
  47. %}  
  48.   
  49. %%  
  50. "+" { return ADD;}  
  51. "-" { return SUB;}  
  52. "*" { return MUL;}  
  53. "/" { return DIV;}  
  54. "|" { return ABS;}  
  55. "(" { return OP;}  
  56. ")" { return CP;}  
  57. [0-9]+ {   
  58.                  yylval = atoi(yytext);  
  59.                  return NUMBER;  
  60.            }  
  61.   
  62. \n { return EOL; }  
  63. "//".*  
  64.   
  65. [ \t] {}  
  66. "q" {exit(0);}  
  67. .   { yyerror("invalid char: %c\n;",*yytext); }  
  68. %%  


 

Bision文件编译

 

[cpp] view plain copy
 
 
 
  1. bison -d cacl.y  
  2.   flex cacl.l  
  3.   cc -o cacl cacl.tab.c lex.yy.c  


 

通常,Bison默认是不可重入的,如果希望在yyparse结束后保留解析的语法树,可以采用两种方式,一种是增加一个全局变量,另一种则是设置一个额外参数,其中ParseResult可以是用户自己定义的结构体。
%parse-param {ParseResult *result}
在规则代码中可以引用该参数:

 

[cpp] view plain copy
 
 
 
  1. stmt_list: stmt ';'  { 
     
    ; }  
  2. | stmt_list stmt ';' { 
     
    ;}  
  3. stmt_list: stmt ';'  { 
     
    ; }  
  4. | stmt_list stmt ';' { 
     
    ;}  


 

调用yyparse时则为:
ParseResult p;
yyparse(&p);

SQL解析引擎中的数据结构

语法树结构

在实现的时候可以把语法树和逻辑计划都看成是树结构和列表结构,而物理计划更像像是链式结构。树结构要注意区分叶子节点(也叫终止符节点)和非叶子节点(非终止符节点)。同时叶子节点和非叶子节点都可能有多种类型。

语法树的节点:包含两个部分,节点的类型的枚举值kind,表示节点值的联合体u,联合体中包含了各个节点所需的字段。

 

[cpp] view plain copy
 
 
 
  1. typedef struct node{  
  2.    NODEKIND kind;  
  3.   
  4.    union{  
  5.          //...  
  6.            /* query node */  
  7.          struct{  
  8.              int         distinct_opt;  
  9.               struct node *limit;   
  10.               struct node *select_list;  
  11.               struct node *tbl_list;  
  12.               struct node *where_clause;  
  13.               struct node *group_clause;  
  14.               struct node *having_clause;  
  15.               struct node *order_clause;  
  16.          } SELECT;  
  17.          /* delete node */  
  18.         struct{  
  19.             struct node *limit;  
  20.             struct node *table;  
  21.             struct node *where_clause;  
  22.             struct node *group_clause;  
  23.          } DELETE;  
  24. /* relation node */  
  25.           struct{  
  26.                 char * db_name;  
  27.                 char * tbl_name;  
  28.                 char * alias_name;  
  29.           } TABLE;  
  30.         //其他结构体  
  31.    }u;  
  32. }NODE ;  
  33. NODEKIND枚举了所有可能出现的节点类型.其定义为  
  34.   
  35. typedef enum NODEKIND{  
  36.     N_MIN,  
  37.     /* const node*/  
  38.     N_INT,    //int or long  
  39.     N_FLOAT,  //float  
  40.     N_STRING, //string  
  41.     N_BOOL,   //true or false or unknown  
  42.     N_NULL,   //null  
  43.     /* var node*/  
  44.     N_COLUMN, // colunm name  
  45.     //其他类型  
  46.     /*stmt node*/      
  47.     N_SELECT,  
  48.     N_INSERT,  
  49.     N_REPLACE,  
  50.     N_DELETE,  
  51.     N_UPDATE,  
  52.     //其他类型  
  53.     N_MAX  
  54. } NODEKIND;  


 

在语法树中,分析树的叶子节点为数字,字符串,属性等,其他为内部节点。因此有些数据库的实现中将语法树的节点定义为如下的ParseNode结构。

 

[cpp] view plain copy
 
 
 
  1. typedef struct _ParseNode  
  2. {  
  3.   ObItemType   type_;//节点的类型,如T_STRING,T_SELECT等  
  4.   
  5.   /* 终止符节点,具有实际的值 */  
  6.   int64_t      value_;  
  7.   const char*  str_value_;  
  8.   
  9.   /* 非终止符节点,拥有多个孩子 */  
  10.   int32_t      num_child_;//子节点的个数  
  11.   struct _ParseNode** children_;//子节点指针链  
  12.   
  13. } ParseNode;  


 

逻辑计划结构

逻辑计划的内部节点是算子,叶子节点是关系.

 

[cpp] view plain copy
 
 
 
  1. typedef struct plannode{  
  2.   
  3.     PLANNODEKIND kind;  
  4.   
  5.     union{  
  6.         /*stmt node*/  
  7.         struct {  
  8.             struct plannode *plan;  
  9.         }SELECT;  
  10.   
  11.         /*op node*/  
  12.         struct {  
  13.             struct plannode *rel;  
  14.             struct plannode *filters; //list of filter  
  15.         }SCAN;  
  16.         struct {  
  17.             struct plannode *rel;  
  18.             NODE *expr_filter; //list of compare expr  
  19.         }FILTER;  
  20.         struct {  
  21.             struct plannode *rel;  
  22.             NODE *select_list;      
  23.         }PROJECTION;  
  24.         struct {  
  25.             struct plannode *left;  
  26.             struct plannode *right;  
  27.         }JOIN;  
  28.         /*leaf node*/  
  29.         struct {  
  30.             NODE *table;  
  31.         }FILESCAN;  
  32.         //其他类型节点      
  33.     }u;  
  34. }PLANNODE;  


 

逻辑计划节点的类型PLANNODEKIND的枚举值如下:

 

[cpp] view plain copy
 
 
 
  1. typedef enum PLANNODEKIND{  
  2.     /*stmt node tags*/  
  3.     PLAN_SELECT,  
  4.     PLAN_INSERT,  
  5.     PLAN_DELETE,  
  6.     PLAN_UPDATE,  
  7.     PLAN_REPLACE,  
  8.     /*op node tags*/  
  9.     PLAN_FILESCAN, /* Relation     关系,叶子节点 */  
  10.     PLAN_SCAN,         
  11.     PLAN_FILTER,   /* Selection  选择   */  
  12.     PLAN_PROJ,     /* Projection 投影*/  
  13.     PLAN_JOIN,     /* Join       连接 ,指等值连接*/  
  14.     PLAN_DIST,     /* Duplicate elimination( Distinct) 消除重复*/  
  15.     PLAN_GROUP,    /* Grouping   分组(包含了聚集)*/  
  16.     PLAN_SORT,     /* Sorting    排序*/  
  17.     PLAN_LIMIT,  
  18.     /*support node tags*/  
  19.     PLAN_LIST      
  20. }PLANNODEKIND;  


 

物理计划结构

物理逻辑计划中关系扫描运算符为叶子节点,其他运算符为内部节点。拥有3个迭代器函数open,close,get_next_row。其定义如下:

 

[cpp] view plain copy
 
 
 
  1. typedef int (*IntFun)(PhyOperator *);  
  2. typedef int (*RowFun)(Row &row,PhyOperator *);  
  3. struct phyoperator{  
  4.     PHYOPNODEKIND kind;  
  5.   
  6.     IntFun open;  
  7.     IntFun close;  
  8.     RowFun get_next_row;//迭代函数  
  9.   
  10.     union{  
  11.         struct {  
  12.             struct phyoperator *inner;  
  13.             struct phyoperator *outter;  
  14.             Row one_row;  
  15.         }NESTLOOPJOIN;  
  16.         struct {  
  17.             struct phyoperator *inner;  
  18.             struct phyoperator *outter;  
  19.         }HASHJOIN;  
  20.         struct {  
  21.             struct phyoperator *inner;  
  22.         }TABLESCAN;  
  23.         struct {  
  24.             struct phyoperator *inner;  
  25.             NODE * expr_filters;  
  26.         }INDEXSCAN;  
  27.         //其他类型的节点  
  28.     }u;  
  29. }PhyOperator;  


 

物理查询计划的节点类型PHYOPNODEKIND枚举如下:

 

[cpp] view plain copy
 
 
 
  1. typedef enum PHYOPNODEKIND{  
  2.     /*stmt node tags*/  
  3.     PHY_SELECT,  
  4.     PHY_INSERT,  
  5.     PHY_DELETE,  
  6.     PHY_UPDATE,  
  7.     PHY_REPLACE,  
  8.     /*phyoperator node tags*/  
  9.     PHY_TABLESCAN,  
  10.     PHY_INDEXSCAN,  
  11.     PHY_FILESCAN,  
  12.     PHY_NESTLOOPJOIN,  
  13.     PHY_HASHJOIN,  
  14.     PHY_FILTER,  
  15.     PHY_SORT,  
  16.     PHY_DIST,  
  17.     PHY_GROUP,  
  18.     PHY_PROJECTION,  
  19.     PHY_LIMIT  
  20. }PHYOPNODEKIND;  


 

节点内存池

可以看到分析树,逻辑计划树和物理查询树都是以指针为主的结构体,如果每次都动态从申请的话,会比较耗时。需要使用内存池的方式,一次性申请多个节点内存,供以后调用。下面是一种简单的方式,每次创建节点时都使用newnode函数即可。程序结束时再释放内存池即可。

 

[cpp] view plain copy
 
 
 
  1. static NODE *nodepool = NULL;  
  2. static int MAXNODE = 256;  
  3. static int nodeptr = 0;  
  4.   
  5. NODE *newnode(NODEKIND kind)  
  6. {  
  7.     //首次使用时申请MAXNODE个节点  
  8.     if(nodepool == NULL){  
  9.         nodepool = (NODE *)malloc(sizeof(NODE)*MAXNODE);  
  10.         assert(nodepool);  
  11.     }  
  12.   
  13.     assert(nodeptr <= MAXNODE);  
  14.     //当节点个数等于MAXNODE时realloc扩展为原来的两倍节点  
  15.     if (nodeptr == MAXNODE){  
  16.         MAXNODE *= 2;  
  17.         NODE *newpool =   
  18. (NODE *)realloc(nodepool,sizeof(NODE)*MAXNODE) ;   
  19.         assert(newpool);  
  20.         nodepool = newpool;  
  21.     }  
  22.   
  23.     NODE *n = nodepool + nodeptr;  
  24.     n->kind = kind ;  
  25.     ++nodeptr;  
  26.   
  27.     return n;  
  28. }  


 

查询分析

查询分析需要对查询语句进行词法分析和语法分析,构建语法树。词法分析是指识别SQL语句中的有意义的逻辑单元,如关键字(SELECT,INSERT等),数字,函数名等。语法分析则是根据语法规则将识别出来的词组合成有意义的语句。 词法分析工具LEX,语法分析工具为Yacc,在GNU的开源软件中对应的是Flex和Bison,通常都是搭配使用。

词法和语法分析

SQL引擎的词法分析和语法分析采用Flex和Bison生成,parse_sql为生成语法树的入口,调用bison的yyparse完成。源文件可以这样表示

文件 意义
parse_node.h parse_node.cpp 定义语法树节点结构和方法,入口函数为parse_sql
print_node.cpp 打印节点信息
psql.y 定义语法结构,由Bison语法书写
psql.l 定义词法结构,由Flex语法书写

SQL查询语句语法规则

熟悉Bison和Flex的用法之后,我们就可以利用Flex获取记号,Bison设计SQL查询语法规则。一个SQL查询的语句序列由多个语句组成,以分号隔开,单条的语句又有DML,DDL,功能语句之分。


  1.  
    stmt_list : stmt ‘;’
  2.  
    | stmt_list stmt ‘;’
  3.  
    ;
  4.  
    stmt: ddl
  5.  
    | dml
  6.  
    | unility
  7.  
    | nothing
  8.  
    ;
  9.  
    dml: select_stmt
  10.  
    | insert_stmt
  11.  
    | delete_stmt
  12.  
    | update_stmt
  13.  
    | replace_stmt
  14.  
    ;

以DELETE 单表语法为例

 

[sql] view plain copy
 
 
 
  1. DELETE  [IGNORE] [FIRST|LAST row_count]   
  2. FROM tbl_name   
  3. [WHERE where_definition]    
  4. [ORDER BY ...]  

 

用Bison可以表示为:

 

[plain] view plain copy
 
 
 
  1. delete_stmt:DELETE opt_ignore opt_first FROM table_ident opt_where opt_groupby   
  2. {  
  3.            $$ = delete_node(N_DELETE,$3,$5,$6,$7);  
  4. }    
  5. ;  
  6. opt_ignore:/*empty*/  
  7.             | IGNORE  
  8. ;  
  9.   
  10. opt_first: /* empty */{ $$ = NULL;}  
  11. | FIRST INTNUM { $$ = limit_node(N_LIMIT,0,$2);}  
  12. | LAST INTNUM { $$ = limit_node(N_LIMIT,1,$2);}  
  13. ;  

 

然后在把opt_where,opt_groupbytable_ident等一直递归下去,直到不能在细分为止。 SQL语句分为DDL语句和DML语句和utility语句,其中只有DML语句需要制定执行计划,其他的语句转入功能模块执行。

制定逻辑计划

执行顺序

语法树转为逻辑计划时各算子存在先后顺序。以select语句为例,执行的顺序为: FROM > WHERE > GROUP BY> HAVING > SELECT > DISTINCT > UNION > ORDER BY > LIMIT。 没有优化的逻辑计划应按照上述顺序逐步生成或者逆向生成。转为逻辑计划算子则对应为: JOIN –> FILTER -> GROUP -> FILTER(HAVING) -> PROJECTION -> DIST -> UNION -> SORT -> LIMIT

逻辑计划的优化

逻辑计划的优化需要更细一步的粒度,将FILTER对应的表达式拆分成多个原子表达式。如WHERE t1.a = t2.a AND t2.b = '1990'可以拆分成两个表达式: 1)t1.a = t2.a 2)t2.b = '1990' 不考虑谓词LIKE,IN的情况下,原子表达式实际上就是一个比较关系表达式,其节点为列名,数字,字符串,可以将原子表达式定义为

 

[cpp] view plain copy
 
 
 
  1. struct CompExpr  
  2. {  
  3.     NODE * attr_or_value;  
  4.     NODE * attr_or_value;  
  5.     CompOpType kind;  
  6. };  

 

CompOpType为“>”, ”<” ,”=”等各种比较操作符的枚举值。

如果表达式符合 attr comp value 或者 value comp attr,则可以将该原子表达式下推到对应的叶子节点之上,增加一个Filter。 如果是attr = value类型,且attr是关系的索引的话,则可以采用索引扫描IndexScan。 当计算三个或多个关系的并交时,先对最小的关系进行组合。

还有其他的优化方法可以进一步发掘。内存数据库与存储在磁盘上的数据库的代价估计不一样。根据处理查询时CPU和内存占用的代价,主要考虑以下一些因素:

  • 查询读取的记录数;
  • 结果是否排序(这可能会导致使用临时表);
  • 是否需要访问索引和原表。

制定物理计划

物理查询计划主要是完成一些算法选择的工作。如关系扫描运算符包括: TableScan(R):按任意顺序读入所以存放在R中的元组。 SortScan(R,L):按顺序读入R的元组,并以列L的属性进行排列 IndexScan(R,C): 按照索引C读入R的元组。

根据不同的情况会选择不同的扫描方式。其他运算符包括投影运算Projection,选择运算Filter,连接运算包括嵌套连接运算NestLoopJoin,散列连接HashJoin,排序运算Sort等。 算法的一般策略包括基于排序的,基于散列的,或者基于索引的。

流水化操作与物化

由于查询的结果集可能会很大,超出缓冲区,同时为了能够提高查询的速度,各运算符都会支持流水化操作。流水化操作要求各运算符都有支持迭代操作,它们之间通过GetNext调用来节点执行的实际顺序。迭代器函数包括open,getnext,close3个函数。 设NestLoopJoin的两个运算符参数为R,S,NestLoopJoin的迭代器函数如下:

 

[cpp] view plain copy
 
 
 
  1. void NestLoopJoin::Open()  
  2. {  
  3.     R.Open();  
  4.     S.Open();  
  5.     r =R.GetNext();  
  6. }  
  7. void NestLoopJoin::GetNext(tuple &t)  
  8. {  
  9.     Row r,s;  
  10.     S.GetNext(s);  
  11.     if(s.empty()){  
  12.         S.Close();  
  13.         R.GetNext(r);  
  14.         if(r.empty())  
  15.             return;  
  16.         S.Open();  
  17.         S.GetNext(s);  
  18.     }  
  19.     t = join(r,s)  
  20. }  
  21. void NestLoopJoin::Close()  
  22. {  
  23.         R.Close();  
  24.         S.Close();  
  25. }  

 

如果TableScan,IndexScan,NestLoopJoin 3个运算符都支持迭代器函数。则图5中的连接NestLoopJoin(t1,t2’)可表示为: phy = Projection(Filter(NestLoopJoin(TableScan(t1),IndexScan(t2’))));

执行物理计划时:

 

[cpp] view plain copy
 
 
 
  1. phy.Open();  
  2.     while(!tuple.empty()){  
  3.         phy.GetNext(tuple);  
  4.     }  
  5.     phy.Close();  

 

这种方式下,物理计划一次返回一行,执行的顺序由运算符的函数调用序列来确定。程序只需要1个缓冲区就可以向用户返回结果集。 也有些情况需要等待所有结果返回才进行下一步运算的,比如Sort , Dist运算,需要将整个结果集排好序后才能返回,这种情况称作物化,物化操作通常是在open函数中完成的。

一个完整的例子

接下来以一个例子为例表示各部分的结构,SQL命令: SELECT t1.a,t2.b FROM t1,t2 WHERE t1.a = t2.a AND t2.b = '1990'; 其对应的分析树为: 图2. SQL例句对应的分析树

分析树的叶子节点为数字,字符串,属性等,其他为内部节点。 将图2的分析树转化为逻辑计划树,如图3所示。 图3. 图2分析树对应的逻辑计划

逻辑计划是关系代数的一种体现,关系代数拥有种基本运算符:投影 (π),选择 (σ),自然连接 (⋈),聚集运算(G)等算子。因此逻辑计划也拥有这些类型的节点。 逻辑计划的内部节点是算子,叶子节点是关系,子树是子表达式。各算子中最耗时的为连接运算,因此SQL查询优化的很大一部分工作是减小连接的大小。如图3对应的逻辑计划可优化为图4所示的逻辑计划。 图4. 图3优化后的逻辑计划

完成逻辑计划的优化后,在将逻辑计划转化为物理查询计划。图4的逻辑计划对应的物理查询计划如下: 图5. 图4对应的物理查询计划

物理查询计划针对逻辑计划中的每一个算子拥有对应的1个或多个运算符,生成物理查询计划是基于不同的策略选择合适的运算符进行运算。其中,关系扫描运算符为叶子节点,其他运算符为内部节点。

后记

开源的数据库代码中可以下载OceanBase或者RedBaseOceanBase 是淘宝的开源数据库,RedBase是斯坦福大学数据库系统实现课程的一个开源项目。后面这两个项目都是较近开始的项目,代码量较少,结构较清晰,相对简单易读,在github上都能找到。但是OceanBase目前SQL解析部分也没有全部完成,只有DML部分完成;RedBase设计更简单,不过没有设计逻辑计划。 本文中就是参考了RedBase的方式进行解析。

参考文献:

《数据库系统实现》


相关教程