精华内容
下载资源
问答
  • 首先先介绍概念,对于查询处理,一般分为三个步骤:对SQL语句进行语法分析,即将查询语句转换成按照某种有用方式表示查询语句结构的语法树把语法分析树转换关系代数表达式树(或某种类似标记),一般称之逻辑查询...
    abea020e3f7abf5cab4cd376ec0c1baf.png

    近期研究了《数据库系统实现》这本书,了解了一条SQL是如何进行编译的,以下为自己从书中的总结。

    首先先介绍概念,对于查询处理,一般分为三个步骤:

    • 对SQL语句进行语法分析,即将查询语句转换成按照某种有用方式表示查询语句结构的语法树
    • 把语法分析树转换成关系代数表达式树(或某种类似标记),一般称之为逻辑查询计划
    • 逻辑查询计划必须转换成物理查询计划,物理查询计划不仅指明了要执行的操作,而且也找出了这些操作执行的顺序、执行每步所用的算法,获得所存储数据的方式以及数据从一个操作传递给另一个操作的方式,除此之外,还必须估计每个可能选项的预计代价。

    以下是详细的步骤。

    查询的编译

    1:语法分析与预处理

    • 语法分析与语法分析树
      • 原子
      • 语法类
    • SQL简单子集的语法(语法分析)
      • 查询
      ::= SELECT  FROM  WHERE 
      • 选择列表
     ::=  , ::= 
      • from列表
      ::= , ::= 
      • 条件
      ::=  AND  ::=  IN ()
    • 举例说明:
      • query: select title from startsin WHERE name = "tao"
      • 语法树
    cea19ee3bd68ef0bbe6830846e227454.png

    语法树

    • 预处理器
      • 主要用来检查关系的使用,检查与解析属性的使用以及检查类型

    2:用于改进查询计划的代数定律

    • 交换律与结合律
    • 涉及选择的定律
    • 下推选择(必须下推到包含涉及属性的关系中,下推选择较为复杂)
    • 涉及投影的定律
    • 有关连接和积的定律
    • 有关消除重复的定律
    • 涉及分组与聚集的定律

    说明:

    • 代数定律类似于数学里的各种定律,如(x+y)+z=x+(y+z)等。
    • 了解下推选择,必须了解前置知识,即数据库的关系代数:投影、选择、并、差、积、交、自然连接等,在此不赘述了,有兴趣的可以了解一下。

    3:从语法分析树到逻辑查询计划

    • 概念:将语法树转换成所希望的逻辑查询计划
    • 最终目标:将查询语句转化为关系代数
    • 《数据库系统实现》这本书上,有详细的例子说明,辅以图说明,可以详细研究一下。

    4:查询的优化

    最后可以了解一下查询是以什么指标来衡量查询的优化的。

    • 中间关系大小的估计
    • 投影运算大小的估计
    • 选择运算大小的估计
    • 连接运算大小的估计
    • 多连接属性的自然连接
    • 多个关系的连接
    • 其他运算大小的估计(并、交、差、消除重复、分组与聚集)

    本次总结较为干货,如果没有数据库方面的知识储备可能很难看懂。建议做数据开发或者数据分析的同学有兴趣可以研究一下《数据库系统实现》这本书,从深层次帮我们理解一条SQL语句是如何从编译到执行的。我们平时使用例如hive等,进行SQL操作时,内部执行计划就是以上这样的。如果我们要进行SQL的血缘分析,那么代码就是按照以上步骤实现的,有兴趣可以研究类似HiveParser之类的SQL解析方式。

    展开全文
  • 功能:将用户输入的SQL语句序列转换为一个可执行的操作序列,并返回查询的结果集。 SQL的解析引擎包括查询编译与查询优化和查询的运行,主要包括3个步骤: 查询分析:制定逻辑查询计划(优化相关)制定物理查询...

    自己实现一个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 ';'  { 
      =$1;result>resulttree=
      ; }  
    2. | stmt_list stmt ';' { 
      =(($2!=NULL)?$2:$1);result>resulttree=
      ;}  
    3. stmt_list: stmt ';'  { 
      =$1;result>resulttree=
      ; }  
    4. | stmt_list stmt ';' { 
      =(($2!=NULL)?$2:$1);result>resulttree=
      ;}  


    调用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,功能语句之分。

        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
    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的方式进行解析。

    参考文献:

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


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

    展开全文
  • 首先先介绍概念,对于查询处理,一般分为三个步骤:对SQL语句进行语法分析,即将查询语句转换成按照某种有用方式表示查询语句结构的语法树把语法分析树转换关系代数表达式树(或某种类似标记),一般称之逻辑查询...
    a0cd28aa33f0a01b743b80e05d8a03fc.png

    近期研究了《数据库系统实现》这本书,了解了一条SQL是如何进行编译的,以下为自己从书中的总结。

    首先先介绍概念,对于查询处理,一般分为三个步骤:

    • 对SQL语句进行语法分析,即将查询语句转换成按照某种有用方式表示查询语句结构的语法树
    • 把语法分析树转换成关系代数表达式树(或某种类似标记),一般称之为逻辑查询计划
    • 逻辑查询计划必须转换成物理查询计划,物理查询计划不仅指明了要执行的操作,而且也找出了这些操作执行的顺序、执行每步所用的算法,获得所存储数据的方式以及数据从一个操作传递给另一个操作的方式,除此之外,还必须估计每个可能选项的预计代价。

    以下是详细的步骤。

    查询的编译

    1:语法分析与预处理

    • 语法分析与语法分析树
      • 原子
      • 语法类
    • SQL简单子集的语法(语法分析)
      • 查询
      ::= SELECT  FROM  WHERE 
      • 选择列表
     ::=  , ::= 
      • from列表
      ::= , ::= 
      • 条件
      ::=  AND  ::=  IN ()
    • 举例说明:
      • query: select title from startsin WHERE name = "tao"
      • 语法树
    9bb7dadbc32d9f0c3d71ad4c45cb0e7e.png

    语法树

    • 预处理器
      • 主要用来检查关系的使用,检查与解析属性的使用以及检查类型

    2:用于改进查询计划的代数定律

    • 交换律与结合律
    • 涉及选择的定律
    • 下推选择(必须下推到包含涉及属性的关系中,下推选择较为复杂)
    • 涉及投影的定律
    • 有关连接和积的定律
    • 有关消除重复的定律
    • 涉及分组与聚集的定律

    说明:

    • 代数定律类似于数学里的各种定律,如(x+y)+z=x+(y+z)等。
    • 了解下推选择,必须了解前置知识,即数据库的关系代数:投影、选择、并、差、积、交、自然连接等,在此不赘述了,有兴趣的可以了解一下。

    3:从语法分析树到逻辑查询计划

    • 概念:将语法树转换成所希望的逻辑查询计划
    • 最终目标:将查询语句转化为关系代数
    • 《数据库系统实现》这本书上,有详细的例子说明,辅以图说明,可以详细研究一下。

    4:查询的优化

    最后可以了解一下查询是以什么指标来衡量查询的优化的。

    • 中间关系大小的估计
    • 投影运算大小的估计
    • 选择运算大小的估计
    • 连接运算大小的估计
    • 多连接属性的自然连接
    • 多个关系的连接
    • 其他运算大小的估计(并、交、差、消除重复、分组与聚集)

    本次总结较为干货,如果没有数据库方面的知识储备可能很难看懂。建议做数据开发或者数据分析的同学有兴趣可以研究一下《数据库系统实现》这本书,从深层次帮我们理解一条SQL语句是如何从编译到执行的。我们平时使用例如hive等,进行SQL操作时,内部执行计划就是以上这样的。如果我们要进行SQL的血缘分析,那么代码就是按照以上步骤实现的,有兴趣可以研究类似HiveParser之类的SQL解析方式。

    展开全文
  • sql基础2

    2019-09-26 11:04:47
    1.some和any连接分别表示一些...3.关系代数的除法求所有 转换为 sql语句可以用 not exist来实现 4.事务实现隔离性的原理,是讲数据存放在内存中,即使是同时发生,其实执行也是有顺序的 5.数据库设计理论:数据...

    1.some和any连接分别表示一些满足条件为真和所有满足条件才为真。去掉any连接,因为存在歧义,已经被some连接代替

    2.关联子查询:子查询中需要外面查询的变量。一般写的都是非关联子查询

    3.关系代数的除法求所有 转换为 sql语句可以用 not exist来实现

    4.事务实现隔离性的原理,是讲数据存放在内存中,即使是同时发生,其实执行也是有顺序的

    5.数据库设计理论:数据依赖理论;关系范式理论;模式分解理论

    6.数据库文件组织方式:

      1)无序记录文件(堆文件heap):

      2)有序记录文件

      3)散列记录文件

      4)聚簇记录文件

      长时候使用后如果发现数据库性能下降的话,就需要  数据库重组。数据的组织方式要配合数据操作的方法(算法)才能发挥特定的效率

    以下是学习过程的图片截图:

        

    转载于:https://www.cnblogs.com/wanjn/p/10802458.html

    展开全文
  • 数据库中的EXISTS语句

    2019-12-27 21:44:36
    EXISTS语句关系代数中表示存在。 什么时候使用EXISTS语句: 1、首先要明确在sql server中带有IN谓词,比较运算符的查询语句都可以转换成EXISTS语句。如果你EXISTS语句用的熟练的话可以首先使用它,如果不太熟的...
  • 自己实现一个SQL解析引擎

    千次阅读 2018-02-21 02:49:49
    自己实现一个SQL解析引擎功能:将用户输入的SQL语句序列转换为一个可执行的操作序列,并返回查询的结果集。 SQL的解析引擎包括查询编译与查询优化和查询的运行,主要包括3个步骤:查询分析:制定逻辑查询计划(优化...
  • SQL语法大全

    2014-03-30 11:00:11
    rs.open SQL语句,conn,3,2 3. SQL常用命令使用方法: (1) 数据记录筛选: sql="select * from 数据表 where 字段名=字段值 order by 字段名 [desc]" sql="select * from 数据表 where 字段名 like \'%字段值%\'...
  • 语言是一种介于关系代数与关系演算之间的语言,其功能主要包括数据定义、查询 操纵和控制四个方面,通过各种不同的语句米实现。按照所实现的功能, 语句以下几种 数据库、登录、用户、模式、基表、视图、索引...
  • 一、关系数据库系统的查询处理: ...检查通过后,把SQL查询语句转换为等价的关系代数表达式 这个过程把外部表示转为内部表示 查询优化:选择一个高效执行的查询处理策略 依据:基于规则、基于代价、基于语义 ...
  • 2009达内SQL学习笔记

    2010-02-10 19:46:58
    多数DBMS不需要在单条SQL语句后加分号,但特定的DBMS可能必须在单条SQL语句后加分号。 SQL语句的最后一句要以 “;”号结束 二、写子句顺序 Select column,group_function From table [Where condition] ...
  • SQLServer2008查询性能优化 2/2

    热门讨论 2012-03-02 16:26:55
    2.5.2 为SQL Server分配更多内存 27 2.5.3 增加系统内存 27 2.5.4 更换32位处理器为64位处理器 27 2.5.5 启用3GB进程空间 28 2.5.6 在32位SQL Server中使用4GB以上内存 28 2.6 磁盘瓶颈分析 29 2.6.1 磁盘...
  • 2.5.2 为SQL Server分配更多内存 27 2.5.3 增加系统内存 27 2.5.4 更换32位处理器为64位处理器 27 2.5.5 启用3GB进程空间 28 2.5.6 在32位SQL Server中使用4GB以上内存 28 2.6 磁盘瓶颈分析 29 2.6.1 磁盘...
  • 检查通过后把SQL查询语句转换成等价的关系代数表达式  RDBMS一般都用查询树(语法分析树)来表示扩展的关系代数表达式  把数据库对象的外部名称转换为内部表示 查询优化 查询优化:选择一个高效执行的查询处理...
  • 数据库系统基础

    2013-03-13 17:36:49
    一、关系处理查询和查询优化 1、查询优化——代数优化(指关系代数表达式的优化),物理优化(指存取路径和...此过程中要把数据库对象的外部名称转换为内部表示。 ~3、查询优化——可以是基于代价,基于规则,基于语义的。
  • 可以找学长学姐要理论题目背下,SQL语句要熟练,不止是SELECT,还有创建表,插入数据删除数据修改数据等一系列操作,关系代数表达式会考,要会但不需太大的经历投入其中,ER图以及ER图转换为关系模型一定会有一道大...
  • 2-3:查询处理

    2020-10-07 23:11:13
    查询系统内部表示建立在关系代数基础上 查询处理中系统首先必须把查询语句翻译成系统的内部表示形式 该翻译过程类似于编译器的语法分析器所作的工作 在产生查询语句的系统内部表示形式的过程中 语法分析器检查用户...
  • 书中涉及的内容非常广泛,包括DBMS的概念、术语和体系结构,ER模型和ER图,数据抽象和语义数据建模,UML类图表示法,基本关系模型,关系代数和关系演算,SQL,规范化,磁盘上组织记录文件的主要方法,文件的索引技术...
  • 第3部分数据库系统(第6~9章),介绍数据库系统的基本概念,关系数据库系统的定义,关系代数,关系数据库标准语言SQL,关系规范化理论以及数据库应用系统的设计方法和步骤,最后介绍了几种常用的数据库管理系统。...
  • 分布式数据库试题及答案.doc

    热门讨论 2010-12-29 16:46:29
    1.3.3. 假设要求查询系号1的所有学生的姓名和成绩,写出在全局模式上的SQL查询语句,并要求转换成相应的关系代数表示,画出全局查询树,请依次进行全局优化和分片优化,画出优化后的查询树。要求给出优化变换过程...
  • 4.3. 对题4.2所确定的分片模式,要求查询级别高于“6”的所有职员的姓名和工资,写出的在全局模式上的SQL查询语句,并要求转换成相应的关系代数表示,画出全局查询树。 26 4.3.1. 进行全局优化,画出各步优化后的...
  • 2.2.2 关系代数 15 2.2.3 关系演算 16 2.2.4 SQL 16 2.3 关系数据库的生命周期 17 2.3.1 需求收集和分析 17 2.3.2 逻辑数据库设计 18 2.3.3 物理数据库设计 25 2.3.4 实现物理设计 27 2.4 反向...
  • margin-right:0cm">掌握各类SQL语句的语法构成、语义与功能,特别是Select语句的不同应用方法。包括基本的定义及修改,索引的建立和删除;掌握SQL的数据操纵,连接查询,嵌套查询&#...
  • 6.1 SQL及其对象-关系特性概述 104 6.1.1 SQL标准及其组件 104 6.1.2 SQL-99中的对象-关系支持 105 6.1.3 SQL中一些新操作和特性 109 6.2 数据模型的演变和数据库技术的当前发展趋势 109 6.3 ...
  • (内有最新习题和ppt教程) ...(40) 将E-R图转换关系模式时,实体与联系都可以表示成______。(B) A. 属性 B. 关系 C. 键 D. 域 (41) 在下列选项中,哪个不是一个算法一般应该具有的基本特征______。(C)...
  • (49) 按条件f对关系R进行选择,其关系代数表达式(C) A. R|X|R B. R|X|Rf C. бf(R) D. ∏f(R) (50) 数据库概念设计的过程中,视图设计一般有三种设计次序,以下各项中不对的是(D) 注:P127,要牢记 A. 自顶向下 B....

空空如也

空空如也

1 2
收藏数 27
精华内容 10
关键字:

关系代数转换为sql语句