自己实现一个SQL解析引擎 - 数据库编程

}

查询分析

查询分析需要对查询语句进行词法分析和语法分析，构建语法树。词法分析是指识别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 单表语法为例

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

这种方式下，物理计划一次返回一行，执行的顺序由运算符的函数

自己实现一个SQL解析引擎(三)