Note：执行完SQL语句后需要输出执行所用的时间，在项目验收中将会用于考察索引效果，另外对于查询语句，需要输出共查询到多少条记录，对于插入/删除/更新语句，需要输出影响了多少条记录（参考MySQL输出）。

更正：
源代码src/parser/syntax_tree.c中的 CreateSyntaxNode函数更正，详见PR。
image.png

#5.1 实验概述

Executor（执行器）的主要功能是根据解释器（Parser）生成的语法树，通过Catalog Manager 提供的信息生成执行计划，并调用 Record Manager、Index Manager 和 Catalog Manager 提供的相应接口进行执行，最后通过执行上下文ExecuteContext将执行结果返回给上层模块。
考虑到同学们尚未接触到编译原理的相关知识，在本实验中，我们已经为同学们设计好MiniSQL中的Parser模块，与Parser模块的相关代码如下：

  • src/include/parser/minisql.l：SQL的词法分析规则；
  • src/include/parser/minisql.y：SQL的文法分析规则；
  • src/include/parser/minisql_lex.h：flex(lex)根据词法规则自动生成的代码；
  • src/include/parser/minisql_yacc.h：bison(yacc)根据文法规则自动生成的代码；
  • src/include/parser/parser.h：Parser模块相关的函数定义，供词法分析器和语法分析器调用存储分析结果，同时可供执行器调用获取语法树根结点；

  • src/include/parser/syntax_tree.h：语法树相关定义，语法树各个结点的类型同样在SyntaxNodeType中被定义。

    #5.1.1 语法树数据结构

    以下是语法树（结点）的数据结构定义，每个结点都包含了一个唯一标识符id_，唯一标识符在调用CreateSyntaxNode函数时生成（框架中已经给出实现）。type_表示语法树结点的类型，line_no_和col_no_表示该语法树结点对应的是SQL语句的第几行第几列，child_和next_分别表示该结点的子结点和兄弟结点，val_用作一些额外信息的存储（如在kNodeString类型的结点中，val_将用于存储该字符串的字面量）。

    1. /**
    2. * Syntax node definition used in abstract syntax tree.
    3. */
    4. struct SyntaxNode {
    5. int id_;    /** node id for allocated syntax node, used for debug */
    6. SyntaxNodeType type_; /** syntax node type */
    7. int line_no_; /** line number of this syntax node appears in sql */
    8. int col_no_;  /** column number of this syntax node appears in sql */
    9. struct SyntaxNode *child_;  /** children of this syntax node */
    10. struct SyntaxNode *next_;   /** siblings of this syntax node, linked by a single linked list */
    11. char *val_; /** attribute value of this syntax node, use deep copy */
    12. };
    13. typedef struct SyntaxNode *pSyntaxNode;

    举一个简单的例子，select * from t1 where id = 1 and name = "str";这一条SQL语句生成的语法树如下。以根结点为例说明，kNodeSelect为结点的类型，(1,47)表示该结点在规约（reduce，编译原理中的术语）后位于行的第1行第47列（语句末），id(9)表示该结点的id_为9。
    image.png

    #5.2 解析语法树完成命令执行

    Parser模块中目前能够支持以下类型的SQL语句。其中包含了一些在语法定义上正确，但在语义上错误的SQL语句（如Line 8～10）需要同学们在执行器中对这些特殊情况进行处理。此外涉及到事务开启、提交和回滚相关的begin、commit和rollback命令可以不做实现。

    1. create database db0;
    2. drop database db0;
    3. show databases;
    4. use db0;
    5. show tables;
    6. create table t1(a int, b char(20) unique, c float, primary key(a, c));
    7. create table t1(a int, b char(0) unique, c float, primary key(a, c));
    8. create table t1(a int, b char(-5) unique, c float, primary key(a, c));
    9. create table t1(a int, b char(3.69) unique, c float, primary key(a, c));
    10. create table t1(a int, b char(-0.69) unique, c float, primary key(a, c));
    11. create table student(
    12. sno char(8),
    13. sage int,
    14. sab float unique,
    15. primary key (sno, sab)
    16. );
    17. drop table t1;
    18. create index idx1 on t1(a, b);
    19. -- "btree" can be replaced with other index types
    20. create index idx1 on t1(a, b) using btree;
    21. drop index idx1;
    22. show indexes;
    23. select * from t1;
    24. select id, name from t1;
    25. select * from t1 where id = 1;
    26. -- note: use left association
    27. select * from t1 where id = 1 and name = "str";
    28. select * from t1 where id = 1 and name = "str" or age is null and bb not null;
    29. insert into t1 values(1, "aaa", null, 2.33);
    30. delete from t1;
    31. delete from t1 where id = 1 and amount = 2.33;
    32. update t1 set c = 3;
    33. update t1 set a = 1, b = "ccc" where b = 2.33;
    34. begin;
    35. commit;
    36. rollback;
    37. quit;
    38. execfile "a.txt";

    在Parser模块调用yyparse()（一个示例在src/main.cpp中）完成SQL语句解析后，将会得到语法树的根结点pSyntaxNode，将语法树根结点传入执行器ExecuteEngine（定义于src/include/executor/execute_engine.h）后，ExecuteEngine将会根据语法树根结点的类型，分发到对应的执行函数中，以完成不同类型SQL语句的执行。
    在本节中，你需要实现ExecuteEngine中所有的执行函数，它们被声明为private类型的成员，即所有的执行过程对上层模块是隐藏的，上层模块只需要调用ExecuteEngine::execute()并传入语法树结点即可无感知地获取到执行结果。

  • ExecuteEngine::ExecuteCreateDatabase(*ast, *context)

  • ExecuteEngine::ExecuteDropDatabase(*ast, *context)
  • ExecuteEngine::ExecuteShowDatabases(*ast, *context)
  • ExecuteEngine::ExecuteUseDatabase(*ast, *context)
  • ExecuteEngine::ExecuteShowTables(*ast, *context)
  • ExecuteEngine::ExecuteCreateTable(*ast, *context)
  • ExecuteEngine::ExecuteDropTable(*ast, *context)
  • ExecuteEngine::ExecuteShowIndexes(*ast, *context)
  • ExecuteEngine::ExecuteCreateIndex(*ast, *context)
  • ExecuteEngine::ExecuteDropIndex(*ast, *context)
  • ExecuteEngine::ExecuteSelect(*ast, *context)
  • ExecuteEngine::ExecuteInsert(*ast, *context)
  • ExecuteEngine::ExecuteDelete(*ast, *context)
  • ExecuteEngine::ExecuteUpdate(*ast, *context)
  • ExecuteEngine::ExecuteExecfile(*ast, *context)
  • ExecuteEngine::ExecuteQuit(*ast, *context)
  • ExecuteEngine::ExecuteTrxBegin(*ast, *context)：事务相关，可不实现
  • ExecuteEngine::ExecuteTrxCommit(*ast, *context)：事务相关，可不实现
  • ExecuteEngine::ExecuteTrxRollback(*ast, *context)：事务相关，可不实现

Note: 执行结果上下文ExecuteContext中提供了部分可能需要用到的数据，同学们在实际编程的时候根据需要自行定义ExecuteContext即可。

  1. /**
  2.  * ExecuteContext stores all the context necessary to run in the execute engine
  3.  * This struct is implemented by student self for necessary.
  4.  *
  5.  * eg: transaction info, execute result...
  6.  */
  7. struct ExecuteContext {
  8.   bool flag_quit_{false};
  9.   Transaction *txn_{nullptr};
  10. };

#5.3 模块相关代码

  • src/main.cpp
  • src/include/executor/execute_engine.h
  • src/executor/execute_engine.cpp

#5.4 开发提示

  1. 整个MiniSQL项目推荐在夏学期第7周前完成；
  2. 框架中已经给出了语法树的PrintTree()方法，它能够打印语法树中的每一个结点（输出DOT格式），具体用法和之前的B+树打印类似，输出的结果放在可视化界面中可以用作调试。此外也可以使用GDB或IDE自带的调试工具在完成SQL语法分析后得到语法树的语句打上断点以进行调试。
  3. 如果需要更改语法和文法以支持新的SQL命令，可以在学习LEX和YACC的相关知识后，修改src/include/parser/minisql.l和src/include/parser/minisql.y文件，然后执行src/include/parser/compile.sh脚本（它会自动生成对应的lex和yacc代码并移动到工程的指定目录下），最后需要重新执行cmake ..完成更新；
  4. 本模块可以不设计相关的测试代码，以手动执行SQL命令观察结果来代替测试。

#5.5 诚信守则

  1. 请勿从其它组或在网络上找到的其它来源中复制源代码，一经发现抄袭，成绩为0；
  2. 请勿将代码发布到公共Github存储库上。