近期研究了《数据库系统实现》这本书，了解了一条SQL是如何进行编译的，以下为自己从书中的总结。
首先先介绍概念，对于查询处理，一般分为三个步骤：
对SQL语句进行语法分析，即将查询语句转换成按照某种有用方式表示查询语句结构的语法树
把语法分析树转换成关系代数表达式树(或某种类似标记)，一般称之为逻辑查询计划
逻辑查询计划必须转换成物理查询计划，物理查询计划不仅指明了要执行的操作，而且也找出了这些操作执行的顺序、执行每步所用的算法，获得所存储数据的方式以及数据从一个操作传递给另一个操作的方式，除此之外，还必须估计每个可能选项的预计代价。
以下是详细的步骤。
查询的编译
1：语法分析与预处理
语法分析与语法分析树
原子
语法类
SQL简单子集的语法(语法分析)
查询
  ::= SELECT  FROM  WHERE 
选择列表
 ::=  , ::= 
from列表
  ::= , ::= 
条件
  ::=  AND  ::=  IN ()
举例说明：
query: select title from startsin WHERE name = "tao"
语法树
语法树
预处理器
主要用来检查关系的使用，检查与解析属性的使用以及检查类型
2：用于改进查询计划的代数定律
交换律与结合律
涉及选择的定律
下推选择(必须下推到包含涉及属性的关系中，下推选择较为复杂)
涉及投影的定律
有关连接和积的定律
有关消除重复的定律
涉及分组与聚集的定律
说明：
代数定律类似于数学里的各种定律，如(x+y)+z=x+(y+z)等。
了解下推选择，必须了解前置知识，即数据库的关系代数：投影、选择、并、差、积、交、自然连接等，在此不赘述了，有兴趣的可以了解一下。
3：从语法分析树到逻辑查询计划
概念：将语法树转换成所希望的逻辑查询计划
最终目标：将查询语句转化为关系代数
《数据库系统实现》这本书上，有详细的例子说明，辅以图说明，可以详细研究一下。
4：查询的优化
最后可以了解一下查询是以什么指标来衡量查询的优化的。
中间关系大小的估计
投影运算大小的估计
选择运算大小的估计
连接运算大小的估计
多连接属性的自然连接
多个关系的连接
其他运算大小的估计(并、交、差、消除重复、分组与聚集)
本次总结较为干货，如果没有数据库方面的知识储备可能很难看懂。建议做数据开发或者数据分析的同学有兴趣可以研究一下《数据库系统实现》这本书，从深层次帮我们理解一条SQL语句是如何从编译到执行的。我们平时使用例如hive等，进行SQL操作时，内部执行计划就是以上这样的。如果我们要进行SQL的血缘分析，那么代码就是按照以上步骤实现的，有兴趣可以研究类似HiveParser之类的SQL解析方式。

近期研究了《数据库系统实现》这本书，了解了一条SQL是如何进行编译的，以下为自己从书中的总结。
首先先介绍概念，对于查询处理，一般分为三个步骤：
对SQL语句进行语法分析，即将查询语句转换成按照某种有用方式表示查询语句结构的语法树
把语法分析树转换成关系代数表达式树(或某种类似标记)，一般称之为逻辑查询计划
逻辑查询计划必须转换成物理查询计划，物理查询计划不仅指明了要执行的操作，而且也找出了这些操作执行的顺序、执行每步所用的算法，获得所存储数据的方式以及数据从一个操作传递给另一个操作的方式，除此之外，还必须估计每个可能选项的预计代价。
以下是详细的步骤。
查询的编译
1：语法分析与预处理
语法分析与语法分析树
原子
语法类
SQL简单子集的语法(语法分析)
查询
  ::= SELECT  FROM  WHERE 
选择列表
 ::=  , ::= 
from列表
  ::= , ::= 
条件
  ::=  AND  ::=  IN ()
举例说明：
query: select title from startsin WHERE name = "tao"
语法树
语法树
预处理器
主要用来检查关系的使用，检查与解析属性的使用以及检查类型
2：用于改进查询计划的代数定律
交换律与结合律
涉及选择的定律
下推选择(必须下推到包含涉及属性的关系中，下推选择较为复杂)
涉及投影的定律
有关连接和积的定律
有关消除重复的定律
涉及分组与聚集的定律
说明：
代数定律类似于数学里的各种定律，如(x+y)+z=x+(y+z)等。
了解下推选择，必须了解前置知识，即数据库的关系代数：投影、选择、并、差、积、交、自然连接等，在此不赘述了，有兴趣的可以了解一下。
3：从语法分析树到逻辑查询计划
概念：将语法树转换成所希望的逻辑查询计划
最终目标：将查询语句转化为关系代数
《数据库系统实现》这本书上，有详细的例子说明，辅以图说明，可以详细研究一下。
4：查询的优化
最后可以了解一下查询是以什么指标来衡量查询的优化的。
中间关系大小的估计
投影运算大小的估计
选择运算大小的估计
连接运算大小的估计
多连接属性的自然连接
多个关系的连接
其他运算大小的估计(并、交、差、消除重复、分组与聚集)
本次总结较为干货，如果没有数据库方面的知识储备可能很难看懂。建议做数据开发或者数据分析的同学有兴趣可以研究一下《数据库系统实现》这本书，从深层次帮我们理解一条SQL语句是如何从编译到执行的。我们平时使用例如hive等，进行SQL操作时，内部执行计划就是以上这样的。如果我们要进行SQL的血缘分析，那么代码就是按照以上步骤实现的，有兴趣可以研究类似HiveParser之类的SQL解析方式。

自己实现一个SQL解析引擎

功能：将用户输入的SQL语句序列转换为一个可执行的操作序列，并返回查询的结果集。 

SQL的解析引擎包括查询编译与查询优化和查询的运行，主要包括3个步骤：

查询分析：
制定逻辑查询计划（优化相关）
制定物理查询计划（优化相关）

查询分析： 将SQL语句表示成某种有用的语法树.
制定逻辑查询计划： 把语法树转换成一个关系代数表达式或者类似的结构，这个结构通常称作逻辑计划。
制定物理查询计划：把逻辑计划转换成物理查询计划，要求指定操作执行的顺序，每一步使用的算法，操作之间的传递方式等。

查询分析各模块主要函数间的调用关系: 



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

FLEX简介

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





[cpp] view
 plain copy






%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部分：





[cpp] view
 plain copy






%{  

    definition  

%}  

  

%%  

    rules  

%%  

    code  








definition部分为定义部分，包括引入头文件，变量声明，函数声明，注释等，这部分会被原样拷贝到输出的.c文件中。

rules部分定义词法规则，使用正则表达式定义词法，后面大括号内则是扫描到对应词法时的动作代码。

code部分为C语言的代码。yylex为flex的函数，使用yylex开始扫描。

%option 指定flex扫描时的一些特性。yywrap通常在多文件扫描时定义使用。常用的一些选项有

noyywrap 不使用yywrap函数

yylineno 使用行号

case-insensitive 正则表达式规则大小写无关

flex文件的编译





[cpp] view
 plain copy






flex  –o wc.c wc.l  

   cc wc.c –o wc  








Bison简介

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

计算器的示例：calc.y





[cpp] view
 plain copy






%{  

#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文件编译





[cpp] view
 plain copy






bison -d cacl.y  

  flex cacl.l  

  cc -o cacl cacl.tab.c lex.yy.c  








通常，Bison默认是不可重入的，如果希望在yyparse结束后保留解析的语法树，可以采用两种方式，一种是增加一个全局变量，另一种则是设置一个额外参数，其中ParseResult可以是用户自己定义的结构体。

%parse-param {ParseResult *result}

在规则代码中可以引用该参数：





[cpp] view
 plain copy






stmt_list: stmt ';'  { 

=$1;result−>resulttree=
; }  

| stmt_list stmt ';' { 

=(($2!=NULL)?$2:$1);result−>resulttree=
;}  

stmt_list: stmt ';'  { 

=$1;result−>resulttree=
; }  

| stmt_list stmt ';' { 

=(($2!=NULL)?$2:$1);result−>resulttree=
;}  








调用yyparse时则为： 

ParseResult p;

yyparse(&p);

SQL解析引擎中的数据结构

语法树结构

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

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





[cpp] view
 plain copy






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结构。





[cpp] view
 plain copy






typedef struct _ParseNode  

{  

  ObItemType   type_;//节点的类型，如T_STRING,T_SELECT等  

  

  /* 终止符节点，具有实际的值 */  

  int64_t      value_;  

  const char*  str_value_;  

  

  /* 非终止符节点，拥有多个孩子 */  

  int32_t      num_child_;//子节点的个数  

  struct _ParseNode** children_;//子节点指针链  

  

} ParseNode;  








逻辑计划结构

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





[cpp] view
 plain copy






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的枚举值如下：





[cpp] view
 plain copy






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。其定义如下：





[cpp] view
 plain copy






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枚举如下：





[cpp] view
 plain copy






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函数即可。程序结束时再释放内存池即可。





[cpp] view
 plain copy






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完成。源文件可以这样表示




文件

意义





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 单表语法为例





[sql] view
 plain copy






DELETE  [IGNORE] [FIRST|LAST row_count]   

FROM tbl_name   

[WHERE where_definition]    

[ORDER BY ...]  








用Bison可以表示为:





[plain] view
 plain copy






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的情况下，原子表达式实际上就是一个比较关系表达式，其节点为列名，数字，字符串，可以将原子表达式定义为





[cpp] view
 plain copy






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





[cpp] view
 plain copy






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’))));

执行物理计划时：





[cpp] view
 plain copy






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表示的查询进行语法分析，生成查询语法分析树。
语义检查：检查sql中所涉及的对象以及是否在数据库中存在，用户是否具有操作权限等
视图转换：将语法分析树转换成关系代数表达式，称为逻辑查询计划；
查询优化：在选择逻辑查询计划时，会有多个不同的表达式，选择最佳的逻辑查询计划；
代码生成：必须将逻辑查询计划转换成物理查询计划，物理查询计划不仅能指明要执行的操作，也给出了这些操作的执行顺序，每步所用的算法，存储数据的方式以及从一个操作传递给另一个操作的方式。
将DML转换成一串可执行的存取操作的过程称为束缚过程。
Mysql查询语句执行过程
这里简单介绍一下mysql数据库，mysql数据库是一款关系型数据库，所谓关系型数据库就是以二维表的形式存储数据，使用行和列方便我们对数据的增删改查。
这篇博客，我们以mysql数据库为例，对一条sql语句的执行流程进行分析。(本篇博客不涉及到表连接)
首先，创建一张student表，字段有自增主键id，学生姓名name，学科subject，成绩grade
建表语句：
DROP TABLE IF EXISTS student;
CREATE TABLE `student` (
`id` int(5) NOT NULL AUTO_INCREMENT,
`name` varchar(10) DEFAULT NULL,
`subject` varchar(10) DEFAULT NULL,
`grade` double(4,1) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=40 DEFAULT CHARSET=utf8;
初始化数据：
INSERT INTO student(`name`,`subject`,grade)VALUES('aom','语文',88);
INSERT INTO student(`name`,`subject`,grade)VALUES('aom','数学',99);
INSERT INTO student(`name`,`subject`,grade)VALUES('aom','外语',55);
INSERT INTO student(`name`,`subject`,grade)VALUES('jack','语文',67);
INSERT INTO student(`name`,`subject`,grade)VALUES('jack','数学',44);
INSERT INTO student(`name`,`subject`,grade)VALUES('jack','外语',55);
INSERT INTO student(`name`,`subject`,grade)VALUES('susan','语文',56);
INSERT INTO student(`name`,`subject`,grade)VALUES('susan','数学',35);
INSERT INTO student(`name`,`subject`,grade)VALUES('susan','外语',77);
INSERT INTO student(`name`,`subject`,grade)VALUES('alice','语文',88);
INSERT INTO student(`name`,`subject`,grade)VALUES('alice','数学',77);
INSERT INTO student(`name`,`subject`,grade)VALUES('alice','外语',100);
INSERT INTO student(`name`,`subject`,grade)VALUES('rajo','语文',33);
INSERT INTO student(`name`,`subject`,grade)VALUES('rajo','数学',55);
INSERT INTO student(`name`,`subject`,grade)VALUES('rajo','外语',55);
下面我们来看一下，数据在数据库中的存储形式。
(图1.0)
现在针对这张student表中的数据提出一个问题：要求查询出挂科数目多于两门(包含两门)的前两名学生的姓名，如果挂科数目相同按学生姓名升序排列。
下面是这条查询的sql语句
SELECT `name`,COUNT(`name`) AS num FROM student WHERE grade < 60 GROUP BY `name` HAVING num >= 2 ORDER BY num DESC,`name` ASC LIMIT 0,2;
执行结果：
以上这条sql语句基本上概括了单表查询中所有要注意的点，那么我们就以这条sql为例来分析一下一条语句的执行流程。
1，一条查询的sql语句先执行的是 FROM student 负责把数据库的表文件加载到内存中去，如上图所示。(mysql数据库在计算机上也是一个进程，cpu会给该进程分配一块内存空间，在计算机‘服务’中可以看到，该进程的状态)
2，WHERE grade 
图(1.3)
3，GROUP BY `name`会把图(1.3)的临时表切分成若干临时表，我们用下图来表示内存中这个切分的过程。
4，SELECT 的执行读取规则分为sql语句中有无GROUP BY两种情况。
(1)当没有GROUP BY时，SELECT 会根据后面的字段名称对内存中的一张临时表整列读取。
(2)当查询sql中有GROUP BY时，会对内存中的若干临时表分别执行SELECT，而且只取各临时表中的第一条记录，然后再形成新的临时表。这就决定了查询sql使用GROUP BY的场景下，SELECT后面跟的一般是参与分组的字段和聚合函数，否则查询出的数据要是情况而定。另外聚合函数中的字段可以是表中的任意字段，需要注意的是聚合函数会自动忽略空值。
我们还是以本例中的查询sql来分析，现在内存中有四张被GROUP BY `name`切分成的临时表，我们分别取名为 tempTable1,tempTable2,tempTable3,tempTable4分别对应上图，下面写四条"伪SQL"来说明这个查询过程。
SELECT `name`,COUNT(`name`) AS num FROM tempTable1;
SELECT `name`,COUNT(`name`) AS num FROM tempTable2;
SELECT `name`,COUNT(`name`) AS num FROM tempTable3;
SELECT `name`,COUNT(`name`) AS num FROM tempTable4;
最后再次成新的临时表，如下图：
5，HAVING num >= 2对上图所示临时表中的数据再次过滤，与WHERE语句不同的是HAVING 用在GROUP BY之后，WHERE是对FROM student从数据库表文件加载到内存中的原生数据过滤，而HAVING 是对SELECT 语句执行之后的临时表中的数据过滤，所以说column AS otherName ,otherName这样的字段在WHERE后不能使用，但在HAVING 后可以使用。但HAVING的后使用的字段只能是SELECT 后的字段，SELECT后没有的字段HAVING之后不能使用。HAVING num >= 2语句执行之后生成一张临时表，如下：
6，ORDER BY num DESC,`name` ASC对以上的临时表按照num，name进行排序。
7，LIMIT 0,2取排序后的前两个。