Project #3 - Query Execution
项目准备
项目地址：Project #3 - Query Execution。
准备工作：阅读 Chapter 15 16 22，学习 Lecture #10 #11 #12 #13 #14，以及阅读课堂笔记。
项目结构
通过查看 sqllogictest.cpp，可以知道 SQL 语句的整个执行流程。首先调用 SQLLogicTestParser::Parse 将测试文件解析为多个测试记录，然后根据记录的类型分别处理。目前我们主要关注查询语句，只需查看 BustubInstance::ExecuteSqlTxn 函数的代码。如项目介绍描述的那样，代码分别执行 Binder,Planner,Optimize,ExecutionEngine。然后，本来想详细分析一下整个流程，但是由于时间原因，以及项目确实比较复杂，所以暂时搁置。
Task #1 - Access Method Executors
实现
① 遇到第一个问题，如何在 SeqScanExecutor 中遍历表，可以发现 exec_ctx 成员所属的类 ExecutorContext 中有一个 GetCatalog 方法，只要拿到 Catalog 就可以根据 plan_ 中的信息拿到 TableHeap 的迭代器 TableIterator。然后第二个问题就是如何存储迭代器，TableIterator 是不可复制的，我们可以使用 unique_ptr 来存储迭代器，并使用 make_unique 初始化。（注意，不能在构造函数初始化，一定要在 Init 函数中初始化，不然多次全表扫描会出问题！）
② 实现 Insert 时报错 “The executor will produce a single tuple of integer type as the output, indicating how many rows have been inserted into the table”，并且可以看到 Next 函数的注释中表示 “tuple The integer tuple indicating the number of rows inserted into the table”。说实话有点难以理解，我一开始以为每次调用 Next 会像迭代器模式一样，只执行一次插入，但是这样实现就会报上面的错误。然后通过查看 Discord 的讨论，发现是一次性插入所有记录，因为只要返回 true 就会打印插入的行数，返回 false 就不会打印。当插入零行时，还必须打印一个零，这说明，Next 必定要先返回 true，再返回 false。并且在构造 tuple 时需要使用 BIGINT 类型，不然会报其他错误（明明注释说的是 INTEGER 额）。
③ 在 Insert 的同时需要更新索引，一开始我是直接用普通的 tuple 作为 InsertEntry 的参数，结果在测试 p3.05-index-scan.slt 时报 stack buffer overflow 错误。通过 Debug 发现，在 InsertEntry 时会调用 GenericKey 类的 SetFromKey 函数，该函数会将 tuple 的数据拷贝到该类的 data_ 成员中，作为索引的 key 使用。所以传入的 tuple 必须只包含 key，那么如何确定 tuple 中的哪个数据是 key 呢。可以发现 Tuple 类中有 KeyFromTuple 函数，它的会生成只包含 key 的 tuple，因为需要的索引的 key，那么该函数必定需要传入和索引相关的模式，以及 key 所在列的下标，这些信息可以在 IndexInfo 中找到。（之前我有点迷糊，当成 MySQL 默认使用主键索引了，BusTub 使用的是 TableHeap，也就是说表默认是没有索引的）
④ 实现时不要使用 GetTableOid 函数，因为线上测试的函数名是 TableOid，可能是因为我 fork 的版本太新了，仓库的代码和测试代码不一样，所以只能直接使用 table_oid_ 成员。
⑤ 实现 update 时要注意，在创建新 tuple 时，使用的是 child_executor_->GetOutputSchema()，而不是 GetOutputSchema()。
⑥ 实现 index_scan 时，会使用到 b_plus_tree_index.h 中定义的别名，如 BPlusTreeIndexIteratorForTwoIntegerColumn。
⑧ 在 IndexScan 的提示中有这么一句话，“do not emit tuples that are deleted”，但是当从表中删除 tuple 时，也会从索引中删除对应的 key，所以应该不会遍历到已经删除的 key 才对，也就是说此时应该不用特判 TupleMeta 中的 is_deleted_ 成员。
⑨ 测试 p3.06-empty-table.slt 时，遇到 B+Tree 迭代器实现问题。当 B+Tree 的为 empty 时，获取迭代器我原来是抛出异常，现在改为返回一个默认构造的迭代器。
补充
① 当没有显示声明复制/移动构造函数或复制/移动运算符，以及析构函数时，编译器才会隐式生成这些函数（其他更复杂的情况可以查看 cppreference.com）。
② 创建 TupleMeta 时，会将 insertion_txn 和 deletion_txn_ 都初始化为 INVALID_TXN_ID，提示表示这些成员会在以后切换到 MVCC 存储时使用，有点遗憾没能体验一下。
③ vector 的 reserve 只会影响 capacity 的大小，而不会影响 size，讨论在此。
④ 重载前置和后置 ++ 的区别，前置 ++ 的重载声明为 operator++()，后置 ++ 的重载声明为 operator++(int)。
⑤ 为什么应该将移动构造声明为 noexcept，可以阅读 Friendly reminder to mark your move constructors noexcept。
Task #2 - Aggregation & Join Executors
实现
① 一开始实现真摸不着头脑，AggregationPlanNode 里面怎么这么多东西。group_bys 是指 GROUP BY 时对列的求值表达式，aggregates 是指使用聚合函数时对列的求值表达式，agg_types 是指聚合函数的类型。例如：GROUP BY DAY(col)、MIN(col1 + col2)。我们使用 InsertCombine 函数向哈希表插入值，参数可以使用 MakeAggregateKey 和 MakeAggregateValue 函数获得。
② 根据项目介绍，AggregationExecutor::Next 返回的 tuple 应该包含 key 和 value（我没看到，找错好难）。特别需要注意，当哈希表为空时，应该返回什么：如果是对某列进行 GROUP BY 操作，那么就返回 false，因为有个测试用例有注释 no groups, no output；否则，返回 true，并且 tuple 存储聚合函数的默认值。（可以通过判断 key 模式的列数是否为零，或者 value 模式的列数是否等于 plan_ 输出模式的列数，来判断当前是否对某列进行 GROUP BY 操作）
③ 实现 NestedLoopJoinExecutor：外层循环遍历左表，内层循环遍历右表，只有当右表遍历完，才会获取下一个左表中的元组。但是，因为每找到一个匹配就会返回，所以我们应该将左表的元组作为数据成员，并且添加一个标志表示右表是否遍历完。每当右表遍历完成，都需要重置标志，获取左表中的下一个元组，并且重新 Init 右表。我们调用 EvaluateJoin 判断元组是否匹配，如果匹配，就将两个元组合并为一个元组。特别注意，如果当前是左连接，并且左元组没有匹配任何右元组，仍然需要返回一个为右元组填充 null 值的合并元组。比较迷惑的是怎么表示 null，我的想法是根据列类型获取对应的 null 值，但是找不到这样的函数，所以我就直接返回 。突然看到聚合执行器里用到 BUSTUB_INT32_NULL 了ValueFactory::GetNullValueByType 函数，太久没写项目给忘了。我还遇到一个 BUG，调试半天，发现我没有在 Init 函数中初始化 SeqScanExecutor 的迭代器，导致重复调用 Init 时不会重置迭代器。
④ 实现 HashJoin：根据提示我们可以参考 SimpleAggregationHashTable 的实现建立一个哈希表，我们创建一个 JoinKey 类作为键，然后创建一个 hash<bustub::JoinKey> 类，直接复制 aggregation_plan.h 中的代码改个名字就行（不然 C++ 真不熟，又要搞半天）。在哈希表中，将 vector<Tuple> 作为值以处理哈希冲突。搞定哈希的方式之后，我们可以像 aggregation_executor.h 一样添加两个辅助函数 MakeLeftJoinKey 和 MakeRightJoinKey。然后直接在 Init 中对左表建立哈希表，在 Next 中遍历右表，类似 NestedLoopJoinExecutor 的实现，只不过此时需要维护更多的数据成员。特别需要注意如何处理左连接，因为我们是将左表建为哈希表，那么在遍历完右表后，还需要处理没有任何匹配的左表中的元组。这可以在匹配时将元组的地址存储在 unordered_set 中，然后在遍历完右表后再遍历一次左表，并检查 unordered_set 来判断是否输出。（之前我是将元组的 RID 存储到集合中作为标识，但是这是错误的，因为左表可能是临时表，其中元组的 RID 是无效的内容；我们也可以为右表建立哈希表而不是左表，这样对于左连接来说，更好处理）
⑤ 实现 Optimizing NestedLoopJoin to HashJoin：非常的神奇，参考 nlj_as_index_join.cpp 瞎改，感觉代码是一坨，但是竟然没有任何错误，直接通过测试（激动半天）。具体实现的话，一开始我以为传入的参数就是 NestedLoopJoin 计划节点，但是似乎不是，所以我们需要遍历当前计划的子节点，递归的进行优化。之前比较令我迷惑的一点，怎么判断表达式是否是某个类型，我查找很久 API 都没有找到类似的函数，然后想到 Project #0 中好像是直接做 dynamic_cast 转换，如果返回值为 nullptr 就表示类型不匹配，查看 nlj_as_index_join.cpp 发现果然是这样。搞定表达式类型判断之后，就可以根据 ColumnValueExpression::GetTupleIdx 值来交换左右表达式，并返回转换后的节点。
Task #3 - Sort + Limit Executors and Top-N Optimization
Easy！只有两点需要注意：一个是每次调用 Init 时都要初始化所有数据成员，不然下次调用会包含上次调用的数据；第二个是 C++ 的 priority_queue 默认是大顶堆，并且比较器和 Java 中的用法完全相反。
Optional Leaderboard Tasks
① 初次提交。
② 之后优化。
| Rank | Submission Name | Q1 | Q2 | Q3 | Time |
|---|---|---|---|---|---|
| 123 | ALEX | 740 | 30000 | 4839 | 4754 |
测试结果
1 | !/bin/bash |
项目小结
项目难度主要在项目理解上，常常是不理解某些变量的实际含义，或者知道该怎么做，却找不到对应的 API，或者对返回值理解有错误，而函数文档也不清晰。最后，看到实现的代码能够执行各种 SQL 语句，感觉还是很不错的。
Project #3 - Query Execution
https://ligh0x74.github.io/2023/11/03/Project 3 - Query Execution/