数据库内核开发-基础原理篇

项目框架

sql执行流程代码

YY_BUFFER_STATE buf = yy_scan_string(data_recv);
if (yyparse() == 0) {
 if (ast::parse_tree != nullptr) {
  try {
                    // analyze and rewrite
    std::shared_ptr<Query> query = analyze->do_analyze(ast::parse_tree);
             yy_delete_buffer(buf);
             finish_analyze = true;
             pthread_mutex_unlock(buffer_mutex);
                    // 优化器
    std::shared_ptr<Plan> plan = optimizer->plan_query(query, context);
                    
                    // portal
    std::shared_ptr<PortalStmt> portalStmt = portal->start(plan, context);


    portal->run(portalStmt, ql_manager.get(), &txn_id, context);
                    
              portal->drop();
      }

一条sql语句从输入到数据库系统，再到执行一般需要经历四个阶段

语法解析阶段（parser）

在这一阶段，程序会利用flex（语法分析生成器）和bison（语法分析生成器）对我们输入的sql语句进行解析，解释一下flex和bison

Flex和Bison是两个用于处理语言解析的工具，常常被用于编译器和解释器的开发中。

Flex：Flex是一个词法分析器生成器，也就是说，它可以根据用户定义的模式生成一个词法分析器（或者叫做扫描器）。这个词法分析器可以将输入的字符流转换为一系列的词法单元（tokens）。例如，对于一条SQL语句，词法分析器可以将其分解为一系列的关键字、标识符、运算符等。

Bison：Bison是一个语法分析器生成器，它可以根据用户定义的语法规则生成一个语法分析器。这个语法分析器可以将由词法分析器生成的词法单元序列转换为一个语法结构，通常是一个抽象语法树（AST）。例如，对于一条SQL语句，语法分析器可以将其转换为一个描述了这条SQL语句结构的AST。

在流程代码中，

YY_BUFFER_STATE buf = yy_scan_string(data_recv);

这行代码将接收到的SQL语句字符串转换为一个缓冲区，然后

if (yyparse() == 0)

这行代码调用解析器对SQL语句进行语法解析。如果解析成功，ast::parse_tree 将包含解析生成的抽象语法树（AST）。

抽象语法树（AST）是源代码的抽象语法结构的树状表现形式，它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构。在数据库中，当我们输入一条SQL语句时，数据库首先需要解析这条语句，解析的结果就是一个抽象语法树。例如，对于SQL语句 SELECT * FROM table WHERE id = 1，其对应的抽象语法树可能如下：

  SELECT
   /   |   \
 *   FROM  WHERE
     /     /   \
table   id   =   1

在这个树中，每个节点都代表一个操作或者一个值，例如 “SELECT”、”FROM”、”WHERE”、”=” 等等。这个树形结构清晰地表示了SQL语句的结构，使得数据库可以更容易地理解和执行这条SQL语句。

同时在parser能进行基本的sql语法检查。

语义分析（analyze）

std::shared_ptr query = analyze->do_analyze(ast::parse_tree);

这行代码进行语义分析，将AST转换为一个查询对象。这个查询对象包含了执行查询所需的所有信息。

传入analyze的parse_tree会在里面进行分类，通过

auto x = std::dynamic_pointer_cast<ast::SelectStmt>(parse)

↑

SelectStmt，UpdateStmt，DeleteStmt，InsertStmt分别代表增删改查几种sql语句

在analyze阶段，可以对解析出来的parse进行进一步检查，比如目标表（列）是否存在，以及左操作数和右操作数种类是否匹配等，然后把经过检查后的parse中的信息，封装成query查询对象，里面包含了查询所需的所有信息。

查询优化（optimizer）:

对应执行流程里的

std::shared_ptr plan = optimizer->plan_query(query, context);

将查询对象传递给优化器，优化器会生成一个执行计划。执行计划是一个树形结构，经过优化器后的执行计划要做出一定程度的优化，最终生成计划树，举个例子：

1	SELECT col1, col2 FROM table1, table2 WHERE table1.id = table2.id AND table1.id > 5 ORDER BY col2 DESC

这条sql对应的查询计划树可能是下面：

SortPlan (col2 DESC)
|
ProjectionPlan (col1, col2)
|
JoinPlan (table1.id = table2.id)
|   |
|   ScanPlan (table2)
|
ScanPlan (table1, id > 5)

最底层的 ScanPlan 是扫描操作，它们分别扫描 table1 和 table2。对于 table1，还有一个过滤条件 id > 5。
JoinPlan 是连接操作，它将 table1 和 table2 连接在一起，连接条件是 table1.id = table2.id。
ProjectionPlan 是投影操作，它从连接结果中选择 col1 和 col2 两列。
最顶层的 SortPlan 是排序操作，它按照 col2 列的值进行降序排序。

这个查询计划树表示了如何执行这条SQL查询语句。数据库会从最底层的扫描操作开始，逐步向上执行，最后得到排序后的结果。

执行计划（run）

portal->run(portalStmt, ql_manager.get(), &txn_id, context);

执行计划也有了，下一步就是按照计划调用执行方法，操作数据库了

run的代码：

// 遍历算子树并执行算子生成执行结果
void run(std::shared_ptr<PortalStmt> portal, QlManager* ql, txn_id_t *txn_id, Context *context){
    switch(portal->tag) {
        case PORTAL_ONE_SELECT:
        {
            ql->select_from(std::move(portal->root), std::move(portal->sel_cols), context);
            break;
        }

        case PORTAL_DML_WITHOUT_SELECT:
        {
            ql->run_dml(std::move(portal->root));
            break;
        }
        case PORTAL_MULTI_QUERY:
        {
            ql->run_mutli_query(portal->plan, context);
            break;
        }
        case PORTAL_CMD_UTILITY:
        {
            ql->run_cmd_utility(portal->plan, txn_id, context);
            break;
        }
        default:
        {
            throw InternalError("Unexpected field type");
        }
    }
}