自己实现一个SQL解析引擎

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 = $$;}

stmt_list: stmt ; { $$ = $1; result- result_tree = $$; }

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

调用yyparse时则为：
ParseResult p;
yyparse(

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;

 //其他结构体

}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;

 //其他类型节点 

}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;

 //其他类型的节点

}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语句中的有意义的逻辑单元，如关键字（SELECT，INSERT等），数字，函数名等。语法分析则是根据语法规则将识别出来的词组合成有意义的语句。 词法分析工具LEX，语法分析工具为Yacc，在GNU的开源软件中对应的是Flex和Bison，通常都是搭配使用。

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

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

参考文献： 《数据库系统实现》
《flex与bison》

欢迎光临我的网站----蝴蝶忽然的博客园----人既无名的专栏。
如果阅读本文过程中有任何问题，请联系作者，转载请注明出处！

mysql实现一次将多条不同sql查询结果并封装到一个结果集 最近遇到一个统计查询需求，要求一次性查询多个统计信息，其中两个查询信息不在一个表中，也没有业务关联，表中也没有做连接处理。不考虑产品设计是否合理，完全是实际需求如此，需要一次性查询出来返回给前端进行展示，对于这种“非常规”的统计查询平常肯定会遇见，感觉有点代表性，所以简单记录一下。希望对有相同需求的同学可以作为参考。
Mybatis中sql拦截增强-AOP+interceptor实现分页和排序 基于interceptor可以实现sql的完整打印，除了实现打印之外。其实还可以实现分页和排序，下面的分页和排序基于aop+mybatis的interceptor实现。其本质还是对mappedStament的boundSql进行增强。 下面的项目来源于github,通过这个我们可以很好的学习mybatis中插件interceptor的使用。
第十二届 BigData NoSQL Meetup — 基于hbase的New sql落地实践 立即下载