文档章节

自己实现一个SQL解析引擎

黑客画家
 黑客画家
发布于 2018/03/20 14:25
字数 3298
阅读 168
收藏 0

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

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

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

SQL解析引擎中的数据结构    

语法树结构

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

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

typedef struct node{
   NODEKIND kind;

  union{
      /* SM component nodes */
      /* create table node */
      struct{
         char *relname;
         struct node *attrlist;
      } CREATETABLE;

      /* create index node */
      struct{
         char *relname;
         char *attrname;
      } CREATEINDEX;

      /* drop index node */
      struct{
         char *relname;
         char *attrname;
      } DROPINDEX;

      /* drop table node */
      struct{
         char *relname;
      } DROPTABLE;

      /* load node */
      struct{
         char *relname;
         char *filename;
      } LOAD;

      /* set node */
      struct{
         char *paramName;
         char *string;
      } SET;

      /* help node */
      struct{
         char *relname;
      } HELP;

      /* print node */
      struct{
         char *relname;
      } PRINT;

      /* QL component nodes */
      /* query node */
      struct{
         struct node *relattrlist;
         struct node *rellist;
         struct node *conditionlist;
         struct node *orderrelattr; 
         struct node *grouprelattr; 
      } QUERY;

      /* insert node */
      struct{
         char *relname;
         struct node *valuelist;
      } INSERT;

      /* delete node */
      struct{
         char *relname;
         struct node *conditionlist;
      } DELETE;

      /* update node */
      struct{
         char *relname;
         struct node *relattr;
         struct node *relorvalue;
         struct node *conditionlist;
      } UPDATE;

      /* command support nodes */
      /* relation attribute node */
      struct{
         char *relname;
         char *attrname;
      } RELATTR;

      /* order + relation attribute node */
      struct{
         int order;
         struct node *relattr;
      } ORDERATTR;

      /* agg func + relation attribute node */
      struct{
         AggFun func;
         char *relname;
         char *attrname;
      } AGGRELATTR;

      /* condition node */
      struct{
         struct node *lhsRelattr;
         CompOp op;
         struct node *rhsRelattr;
         struct node *rhsValue;
      } CONDITION;

      /* relation-attribute or value */
      struct{
         struct node *relattr;
         struct node *value;
      } RELATTR_OR_VALUE;

      /* <attribute, type> pair */
      struct{
         char *attrname;
         char *type;
      } ATTRTYPE;

      /* <value, type> pair */
      struct{
         AttrType type;
         int  ival;
         real rval;
         char *sval;
      } VALUE;

      /* relation node */
      struct{
         char *relname;
      } RELATION;

      /* list node */
      struct{
         struct node *curr;
         struct node *next;
      } LIST;
   } u;
}NODE ;

//NODEKIND枚举了所有可能出现的节点类型.其定义为
/*
 * all the available kinds of nodes
 */
typedef enum{
    N_CREATETABLE,
    N_CREATEINDEX,
    N_DROPTABLE,
    N_DROPINDEX,
    N_LOAD,
    N_SET,
    N_HELP,
    N_PRINT,
    N_QUERY,
    N_INSERT,
    N_DELETE,
    N_UPDATE,
    N_RELATTR,
    N_ORDERATTR,
    N_AGGRELATTR,
    N_CONDITION,
    N_RELATTR_OR_VALUE,
    N_ATTRTYPE,
    N_VALUE,
    N_RELATION,
    N_STATISTICS,
    N_LIST
} 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语句中的有意义的逻辑单元,如关键字(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,功能语句之分。

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

本文转载自:http://blog.csdn.net/qq910894904/article/details/34861173

共有 人打赏支持
黑客画家
粉丝 144
博文 203
码字总数 533724
作品 0
杭州
高级程序员
私信 提问
认识MySQL---JC MySQL系列(一)

(一)认识MySQL MySQL数据库是开放源代码的关系型数据库。目前,它可以提供的功能有:支持sql语言、子查询、存储过程、触发器、视图、索引、事务、锁、外键约束和影像复制等。 同Oracle和S...

jk88
2013/05/24
0
0
sharding-sphere之SQL路由

在sql路由过程中,是通过sql路由引擎ShardingRouter完成的,定义如下: 可以看到,sql路由解析分为两块,一块做解析,一块做路由。实现类有两个,一个是指定数据库路由DatabaseHintSQLRouter...

一滴水的坚持
2018/06/19
0
0
巨杉数据库 MySQL兼容项目正式开源

9月7日、8日,2018 ODF 开源数据库论坛,在北京盛大开幕。在大会上,巨杉数据库正式发布了巨杉全新的MySQL/MariaDB兼容架构,并将项目正式开源。 开源数据库论坛(ODF)是中国开源数据库垂直...

巨杉数据库
2018/09/16
0
0
数据库中间件 Sharding-JDBC 源码分析 —— SQL 解析(一)之语法解析【推荐收藏】

🙂🙂🙂关注微信公众号:【芋艿的后端小屋】有福利: RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表 RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址 您对于源码...

芋道源码掘金Java群217878901
2017/07/24
0
0
数据库中间件 Sharding-JDBC 源码分析 —— SQL 解析(一)之语法解析

关注微信公众号:【芋艿的后端小屋】有福利: RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表 RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址 您对于源码的疑问每条留...

芋艿V
2017/07/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

组合问题(先提取数字+全组合)

今天在网上看到一个问题:想从A,B,C,D,E字母中选取3个A,B,C;并做出全组合ABC,ACB,BAC,BCA,CBA,CAB。这样的结果会有多少? 想法也是和问题一致: 1. 先从数列中选取所需要的值: A,B,C,D,E中选取...

tedzheng
19分钟前
0
0
vi常用命令

记录存档用,如下: 1、打开命令: vi+filename 2、退出命令: :q 退出而且不保存修改的内容 :q! 强制退出不保存修改的内容 :wq 退出并且保存修改的内容 :wq! 强制保存修改的内容然后退出...

ZICK_ZEON
20分钟前
1
0
查看Mysql正在执行的事务、锁、等待

一、关于锁的三张表(MEMORY引擎) ## 当前运行的所有事务mysql> select * from information_schema.innodb_trx\G;*************************** 1. row *************************** ......

吴伟祥
20分钟前
2
0
判断ifream 是否加载完成

$(function(){var iframe = document.getElementById("mainFrames"); if (iframe.attachEvent){ iframe.attachEvent("onload", function(){ //你要做的事}); }els......

卖星星的小矮人
23分钟前
1
0
11 Git —— 自定义Git

11 Git —— 自定义Git 忽略特殊文件 有些时候,你必须把某些文件放到Git工作目录中,但又不能提交它们,比如保存了数据库密码的配置文件啦,等等,每次git status都会显示Untracked files ....

lwenhao
30分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部