基础功能

Note

实验开始前请先更新实验框架

与上次实验类似，本次实验同样具有较为明确的目标，所有修改均在 optimizer/optimizer.cpp 和 optimizer/optimizer.h 中完成，你需要在优化器中修改查询计划树节点，得到更优的查询计划。

完成本实验时，你需要修改节点在查询计划树中的位置。熟悉 Operator 的成员变量及构造方式将会对完成本次实验有较大的帮助，在实验过程中可能需要阅读 operators 文件夹下的代码，了解不同 Operator 的构造方式。

任务 1：查询重写（8 分）

本任务中，你将实现课程讲述的查询重写算法，涉及 SplitPredicates, PushDownFilter, PushDownSeqScan 和 PushDownJoin 四个函数。

由于谓词的形式多种多样，为简化代码工作量，你只需对本次实验测例中出现过的谓词形式进行处理即可，具体而言：

复合谓词均由单一谓词的合取 (and) 组成，不包含析取 (or)。
单一谓词仅包括普通谓词和连接谓词两类。
普通谓词均为 <列> <比较操作符> <常数> 的形式，即列出现在谓词左侧，常数出现在谓词右侧，如 id < 1, a.id = 3 等。其中 <列> 和 <常数> 均为普通值，不会出现其他形式的表达式（如 a.id + 1 = 3 * 2 这样的复杂形式）。
每个表最多只有一个对应的普通谓词。
连接谓词均为列与列的等值连接（如 a.id = b.id）。
任意两个表之间最多只有一个连接谓词。
多表连接的 SQL 表示均为左深树。

我们首先来完成 SplitPredicates 函数，该函数将复合的选择谓词分解为多个选择节点。你需要遍历查询计划树，当遍历到选择（Filter）节点时，判断其是否由多个合取谓词组成，若满足条件，则将其分解为多个选择节点。

在 PushDown 函数中，优化器会再次自顶向下遍历查询计划树，并根据查询计划树节点调用对应的优化函数，本步骤中你需要完成 PushDownFilter 和 PushDownSeqScan 函数，完成后将通过 10-filter-pushdown.test 测例。

PushDownFilter 函数负责处理 Filter 节点，你需要判断谓词是普通谓词还是连接谓词，并记录必要的谓词信息。

PushDownSeqScan 函数负责处理查询计划树底层的扫描节点，该函数需要查找当前计划树的普通谓词是否使用了扫描节点中包含的列，若存在这样的普通谓词，则将相应的谓词下推到该扫描节点上方。

本次实验的测试使用了 explain 命令，该命令会输出查询计划树，测试程序会比对你优化后的查询计划树与期望结果是否相同。

你需要补充 PushDownJoin 的函数实现部分，完成后将通过 20-join-pushdown.test 测例。

PushDownSeqScan 函数处理连接节点，对于查询计划树中的笛卡尔积节点，即 join_condition 为 true 的节点，需要判断当前查询计划树是否存在连接谓词可以用于该节点，如果有则修改该节点的 join_condition，从而实现笛卡尔积到连接的转换。

在本任务中，你将使用贪心算法进行多表连接的连接顺序选择，你需要补充 optimizer/optimizer.cpp 中的 ReorderJoin 函数，完成后将通过最后一个测例 30-join-order.test。

贪心算法的实现流程在课程中已有详细的描述，文档中不再赘述，你可以参考课程 PPT 来熟悉连接顺序选择问题的贪心算法。

本任务的测例也与课程 PPT 中的例子相同，唯一的区别是在表 r3 中多插入了一条数据，这是为了避免贪心算法中将 r3 选为第一个表，从而产生不同的运行结果。你的算法运行流程应与课程 PPT 中的步骤相同，你可以对照课程 PPT 进行调试。

实验报告的通用要求请查看实验提交要求中的实验报告部分。

本次实验中，请在实验报告中描述你在每个函数中补充的代码所做的工作。此外，也欢迎在最后一次实验报告中谈一谈对这门课的体验感受以及课程建议等内容。