首页 > 代码库 > 自己实现一个SQL解析引擎

自己实现一个SQL解析引擎

自己实现一个SQL解析引擎

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

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

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

FLEX简单介绍

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

%option noyywrap
%{
    int chars = 0;
    int words = 0;
    int lines = 0;
%}

%%

[_a-zA-Z][_a-zA-Z0-9]+ { words++; chars += strlen(yytext); }
\n { chars++ ; lines++; }
.  { chars++; }

%%

int main()
{
       yylex();
       printf("%8d %8d %8d\n",lines,words,chars);
    return 0;
}

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

%{
    definition
%}

%%
    rules
%%
    code

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

flex文件的编译

    flex  –o wc.c wc.l
    cc wc.c –o wc

Bison简单介绍

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

%{
#include <stdio.h>
%}

%token NUMBER
%token ADD SUB MUL DIV ABS
%token OP CP
%token EOL

%%

calclist:
    | calclist exp EOL {printf("=%d \n> ",$2);}
    | calclist EOL {printf("> ");}
    ;
exp: factor
    | exp ADD factor  {$$ = $1 + $3;}
    | exp SUB factor  {$$ = $1 - $3;}
    ;
factor:term
    | factor MUL term {$$ = $1 * $3;}
    | factor DIV term {$$ = $1 / $3;}
    ;
term:NUMBER
    | ABS term ABS { $$ = ($2 >= 0 ? $2 : -$2);}
    | OP exp CP    { $$ = $2;}
    ;
%%
int main(int argc,char *argv[])
{
    printf("> ");
    yyparse();

    return 0;
}
void yyerror(char *s)
{
    fprintf(stderr,"error:%s:\n",s);
}

Flex与Bison共享记号,值通过yylval在Flex与Bison间传递。相应的.l文件为

%option noyywrap
%{
#include "fb1-5.tab.h"
#include <string.h>
%}

%%
"+" { return ADD;}
"-" { return SUB;}
"*" { return MUL;}
"/" { return DIV;}
"|" { return ABS;}
"(" { return OP;}
")" { return CP;}
[0-9]+ { 
                 yylval = atoi(yytext);
                 return NUMBER;
           }

\n { return EOL; }
"//".*

[ \t] {}
"q" {exit(0);}
.   { yyerror("invalid char: %c\n;",*yytext); }
%%

Bision文件编译

    bison -d cacl.y
    flex cacl.l
    cc -o cacl cacl.tab.c lex.yy.c

通常,Bison默认是不可重入的,假设希望在yyparse结束后保留解析的语法树,能够採用两种方式,一种是添加一个全局变量,还有一种则是设置一个额外參数,当中ParseResult能够是用户自定义的结构体。
%parse-param {ParseResult *result}
在规则代码中能够引用该參数:

stmt_list: stmt ‘;‘  { $$ = $1; result->result_tree = $$; }
| stmt_list stmt ‘;‘ { $$ = (($2 != NULL)? $2 : $1); result->result_tree = $$;}

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

SQL解析引擎中的数据结构

语法树结构

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

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

typedef struct node{
   NODEKIND kind;

   union{
         //...
           /* query node */
         struct{
             int         distinct_opt;
              struct node *limit; 
              struct node *select_list;
              struct node *tbl_list;
              struct node *where_clause;
              struct node *group_clause;
              struct node *having_clause;
              struct node *order_clause;
         } SELECT;
         /* delete node */
        struct{
            struct node *limit;
            struct node *table;
            struct node *where_clause;
            struct node *group_clause;
         } DELETE;
/* relation node */
          struct{
                char * db_name;
                char * tbl_name;
                char * alias_name;
          } TABLE;
        //其它结构体
   }u;
}NODE ;

NODEKIND枚举了全部可能出现的节点类型.其定义为

typedef enum NODEKIND{
    N_MIN,
    /* const node*/
    N_INT,    //int or long
    N_FLOAT,  //float
    N_STRING, //string
    N_BOOL,   //true or false or unknown
    N_NULL,   //null
    /* var node*/
    N_COLUMN, // colunm name
    //其它类型
    /*stmt node*/    
    N_SELECT,
    N_INSERT,
    N_REPLACE,
    N_DELETE,
    N_UPDATE,
    //其它类型
    N_MAX
} NODEKIND;

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

typedef struct _ParseNode
{
  ObItemType   type_;//节点的类型,如T_STRING,T_SELECT等

  /* 终止符节点,具有实际的值 */
  int64_t      value_;
  const char*  str_value_;

  /* 非终止符节点,拥有多个孩子 */
  int32_t      num_child_;//子节点的个数
  struct _ParseNode** children_;//子节点指针链

} ParseNode;

逻辑计划结构

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

typedef struct plannode{

    PLANNODEKIND kind;

    union{
        /*stmt node*/
        struct {
            struct plannode *plan;
        }SELECT;

        /*op node*/
        struct {
            struct plannode *rel;
            struct plannode *filters; //list of filter
        }SCAN;
        struct {
            struct plannode *rel;
            NODE *expr_filter; //list of compare expr
        }FILTER;
        struct {
            struct plannode *rel;
            NODE *select_list;    
        }PROJECTION;
        struct {
            struct plannode *left;
            struct plannode *right;
        }JOIN;
        /*leaf node*/
        struct {
            NODE *table;
        }FILESCAN;
        //其它类型节点    
    }u;
}PLANNODE;

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

typedef enum PLANNODEKIND{
    /*stmt node tags*/
    PLAN_SELECT,
    PLAN_INSERT,
    PLAN_DELETE,
    PLAN_UPDATE,
    PLAN_REPLACE,
    /*op node tags*/
    PLAN_FILESCAN, /* Relation     关系,叶子节点 */
    PLAN_SCAN,       
    PLAN_FILTER,   /* Selection  选择   */
    PLAN_PROJ,     /* Projection 投影*/
    PLAN_JOIN,     /* Join       连接 ,指等值连接*/
    PLAN_DIST,     /* Duplicate elimination( Distinct) 消除反复*/
    PLAN_GROUP,    /* Grouping   分组(包括了聚集)*/
    PLAN_SORT,     /* Sorting    排序*/
    PLAN_LIMIT,
    /*support node tags*/
    PLAN_LIST    
}PLANNODEKIND;

物理计划结构

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

typedef int (*IntFun)(PhyOperator *);
typedef int (*RowFun)(Row &row,PhyOperator *);
struct phyoperator{
    PHYOPNODEKIND kind;

    IntFun open;
    IntFun close;
    RowFun get_next_row;//迭代函数

    union{
        struct {
            struct phyoperator *inner;
            struct phyoperator *outter;
            Row one_row;
        }NESTLOOPJOIN;
        struct {
            struct phyoperator *inner;
            struct phyoperator *outter;
        }HASHJOIN;
        struct {
            struct phyoperator *inner;
        }TABLESCAN;
        struct {
            struct phyoperator *inner;
            NODE * expr_filters;
        }INDEXSCAN;
        //其它类型的节点
    }u;
}PhyOperator;

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

typedef enum PHYOPNODEKIND{
    /*stmt node tags*/
    PHY_SELECT,
    PHY_INSERT,
    PHY_DELETE,
    PHY_UPDATE,
    PHY_REPLACE,
    /*phyoperator node tags*/
    PHY_TABLESCAN,
    PHY_INDEXSCAN,
    PHY_FILESCAN,
    PHY_NESTLOOPJOIN,
    PHY_HASHJOIN,
    PHY_FILTER,
    PHY_SORT,
    PHY_DIST,
    PHY_GROUP,
    PHY_PROJECTION,
    PHY_LIMIT
}PHYOPNODEKIND;

节点内存池

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

static NODE *nodepool = NULL;
static int MAXNODE = 256;
static int nodeptr = 0;

NODE *newnode(NODEKIND kind)
{
    //首次使用时申请MAXNODE个节点
    if(nodepool == NULL){
        nodepool = (NODE *)malloc(sizeof(NODE)*MAXNODE);
        assert(nodepool);
    }

    assert(nodeptr <= MAXNODE);
    //当节点个数等于MAXNODE时realloc扩展为原来的两倍节点
    if (nodeptr == MAXNODE){
        MAXNODE *= 2;
        NODE *newpool = 
(NODE *)realloc(nodepool,sizeof(NODE)*MAXNODE) ; 
        assert(newpool);
        nodepool = newpool;
    }

    NODE *n = nodepool + nodeptr;
    n->kind = kind ;
    ++nodeptr;

    return n;
}

查询分析

查询分析须要对查询语句进行词法分析和语法分析,构建语法树。词法分析是指识别SQL语句中的有意义的逻辑单元,如keyword(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,功能语句之分。

    stmt_list : stmt ‘;’
    | stmt_list stmt ‘;’
    ;
    stmt: ddl
    | dml    
    | unility
    | nothing
    ;
    dml: select_stmt   
    | insert_stmt   
    | delete_stmt   
    | update_stmt   
    | replace_stmt  
    ;

以DELETE 单表语法为例

DELETE  [IGNORE] [FIRST|LAST row_count] 
FROM tbl_name 
[WHERE where_definition]  
[ORDER BY ...]

用Bison能够表示为:

delete_stmt:DELETE opt_ignore opt_first FROM table_ident opt_where opt_groupby 
{
           $$ = delete_node(N_DELETE,$3,$5,$6,$7);
}  
;
opt_ignore:/*empty*/
            | IGNORE
;

opt_first: /* empty */{ $$ = NULL;}
| FIRST INTNUM { $$ = limit_node(N_LIMIT,0,$2);}
| LAST INTNUM { $$ = limit_node(N_LIMIT,1,$2);}
;

然后在把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的情况下,原子表达式实际上就是一个比較关系表达式,其节点为列名,数字,字符串,能够将原子表达式定义为

struct CompExpr
{
    NODE * attr_or_value;
    NODE * attr_or_value;
    CompOpType kind;
};

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的迭代器函数例如以下:

void NestLoopJoin::Open()
{
    R.Open();
    S.Open();
    r =R.GetNext();
}
void NestLoopJoin::GetNext(tuple &t)
{
    Row r,s;
    S.GetNext(s);
    if(s.empty()){
        S.Close();
        R.GetNext(r);
        if(r.empty())
            return;
        S.Open();
        S.GetNext(s);
    }
    t = join(r,s)
}
void NestLoopJoin::Close()
{
        R.Close();
        S.Close();
}

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

运行物理计划时:

    phy.Open();
    while(!tuple.empty()){
        phy.GetNext(tuple);
    }
    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的方式进行解析。

參考文献:

《数据库系统实现》
《flex与bison》


欢迎光临我的站点----蝴蝶忽然的博客园----人既无名的专栏。
假设阅读本文过程中有不论什么问题,请联系作者,转载请注明出处!

自己实现一个SQL解析引擎