投影

投影节点可以表示对其输入的各种计算。它总是恰好有一个子节点。在 BusTub shell 中，检查以下查询的查询计划：

EXPLAIN SELECT 1 + 2;
EXPLAIN SELECT colA FROM __mock_table_1;
EXPLAIN SELECT colA + colB AS a, 1 + 2 AS b FROM __mock_table_1;

投影计划节点由一个或多个表示计算的表达式组成：

• ColumnValueExpression：直接将子执行器的一列放入输出。语法 #0.0 表示第一个子节点中的第一列。在连接计划中，你会看到类似 #0.0 = #1.0 的内容。
• ConstantExpression：表示一个常量值（例如 1）。
• ArithmeticExpression：表示算术计算的树。例如，1 + 2 将由一个 ArithmeticExpression 表示，其两个子节点为 ConstantExpression（1 和 2）。

过滤

过滤计划节点用于根据谓词过滤子节点的输出。例如：

EXPLAIN SELECT * FROM __mock_table_1 WHERE colA > 1;

过滤节点恰好有一个子节点并包含一个谓词。

值

值计划节点用于直接生成值：

EXPLAIN values (1, 2, 'a'), (3, 4, 'b');
CREATE TABLE table1(v1 INT, v2 INT, v3 VARCHAR(128));
EXPLAIN INSERT INTO table1 VALUES (1, 2, 'a'), (3, 4, 'b');

值计划节点在将用户提供的值插入表时很有用。

SeqScan

SeqScanPlanNode 可以通过 SELECT * FROM table 语句来规划。

bustub> CREATE TABLE t1(v1 INT, v2 VARCHAR(100));
Table created with id = 15
bustub> EXPLAIN (o,s) SELECT * FROM t1;
=== OPTIMIZER ===
SeqScan { table=t1 } | (t1.v1:INTEGER, t1.v2:VARCHAR)

SeqScanExecutor 遍历一个表并逐个返回其元组。

提示：确保你在使用 TableIterator 对象时理解前置递增和后置递增运算符之间的区别。（查看这里快速复习。）

提示：不要发出在 TableHeap 中已删除的元组。 检查每个元组对应的 TupleMeta 的 is_deleted_ 字段。

提示：顺序扫描的输出是每个匹配元组及其原始记录标识符（RID）的副本。

注意：BusTub 不支持 DROP TABLE 或 DROP INDEX。你可以通过重新启动 shell 来重置数据库。

Insert

InsertPlanNode 可以通过 INSERT 语句来规划。注意，你需要使用单引号来指定 VARCHAR 值。

bustub> EXPLAIN (o,s) INSERT INTO t1 VALUES (1, 'a'), (2, 'b');
=== OPTIMIZER ===
Insert { table_oid=15 } | (__bustub_internal.insert_rows:INTEGER)
  Values { rows=2 } | (__values#0.0:INTEGER, __values#0.1:VARCHAR)

InsertExecutor 将元组插入表中并更新所有受影响的索引。它恰好有一个子节点生成要插入表中的值。计划器将确保值与表具有相同的模式。执行器将生成一个整数类型的单个元组作为输出，表示已插入表中的行数。如果表有关联的索引，请记住在插入表时更新索引。

提示：请参阅下面的系统目录部分了解有关系统目录的信息。要初始化此执行器，你需要查找有关要插入的表的信息。

提示：请参阅下面的索引更新部分了解有关更新表索引的更多详细信息。

提示：你需要使用 TableHeap 类来执行表修改。

Update

UpdatePlanNode 可以通过 UPDATE 语句来规划。它恰好有一个子节点包含表中要更新的记录。

bustub> explain (o,s) update test_1 set colB = 15445;
=== OPTIMIZER ===
Update { table_oid=20, target_exprs=[#0.0, 15445, #0.2, #0.3] } | (__bustub_internal.update_rows:INTEGER)
  SeqScan { table=test_1 } | (test_1.colA:INTEGER, test_1.colB:INTEGER, test_1.colC:INTEGER, test_1.colD:INTEGER)

UpdateExecutor 修改指定表中的现有元组。执行器将生成一个整数类型的单个元组作为输出，表示已更新的行数。请记住更新受更新影响的任何索引。

提示：要实现更新，首先删除受影响的元组，然后插入新的元组。

Delete

DeletePlanNode 可以通过 DELETE 语句来规划。它恰好有一个子节点包含表中要删除的记录。你的删除执行器应生成一个整数输出，表示它从表中删除的行数。它还需要更新所有受影响的索引。

bustub> EXPLAIN (o,s) DELETE FROM t1;
=== OPTIMIZER ===
Delete { table_oid=15 } | (__bustub_internal.delete_rows:INTEGER)
  Filter { predicate=true } | (t1.v1:INTEGER, t1.v2:VARCHAR)
    SeqScan { table=t1 } | (t1.v1:INTEGER, t1.v2:VARCHAR)

bustub> EXPLAIN (o,s) DELETE FROM t1 where v1 = 1;
=== OPTIMIZER ===
Delete { table_oid=15 } | (__bustub_internal.delete_rows:INTEGER)
  Filter { predicate=#0.0=1 } | (t1.v1:INTEGER, t1.v2:VARCHAR)
    SeqScan { table=t1 } | (t1.v1:INTEGER, t1.v2:VARCHAR)

你可以假设 DeleteExecutor 始终位于其出现的查询计划的根节点。DeleteExecutor 不应修改其结果集。

提示：要删除一个元组，你需要从子执行器获取 RID 并更新该元组对应的 TupleMeta 的 is_deleted_ 字段。

IndexScan

IndexScanExecutor 使用 B+ 树索引执行点查找和有序扫描来检索表中的元组。该执行器应能够支持在同一索引上的多次点查找。

你需要通过支持以下两种类型的查询来实现索引扫描：

1. 点查找：SELECT FROM <table> WHERE <index column> = <val>。你将在下一节中实现优化器规则，将 SeqScan 转换为 IndexScan。
2. 有序扫描：SELECT FROM <table> ORDER BY <index column>。为在索引列上使用 ORDER BY 的查询生成 IndexScan 的优化器规则已为你实现。你的任务是仅在 IndexScan 中处理 ASC（或默认）排序。

bustub> CREATE TABLE t1(v1 int, v2 int);
Table created with id = 22

bustub> CREATE INDEX t1v1 ON t1(v1);
Index created with id = 0

bustub> EXPLAIN (o,s) SELECT * FROM t1 WHERE v1 = 1;
=== OPTIMIZER ===
IndexScan { index_oid=0, filter=(#0.0=1) } | (t1.v1:INTEGER, t1.v2:INTEGER)

bustub> EXPLAIN (o,s) SELECT * FROM t1 ORDER BY v1;
=== OPTIMIZER ===
IndexScan { index_oid=0 } | (t1.v1:INTEGER, t1.v2:INTEGER)

在本项目中，计划中索引对象的类型将始终为 BPlusTreeIndexForTwoIntegerColumn。你可以安全地将对象转换为此类型并将其存储在需要时的执行器中：

tree_ = dynamic_cast<BPlusTreeIndexForTwoIntegerColumn *>(index_info_->index_.get())

然后你可以使用 B+ 树索引进行点查找或有序扫描，并发出满足条件的元组。在本学期中，你只需支持单个唯一整数列上的索引。我们的测试用例不会包含重复键。因此，此执行器每次点查找返回一个元组（如果存在的话）。

你需要在下一节中完成优化器规则，将 SeqScan 转换为 IndexScan。在实现 IndexScan 之前先实现优化器规则可能更有意义，这样可以了解 IndexScanExecutor 需要支持的查询类型。

提示：我们永远不会向带有索引的表插入重复行。

提示：如上所述，不要发出已删除的元组。

提示：请使用 ScanKey 进行点查找，使用 Index Iterator 进行有序扫描。

将 SeqScan 优化为 IndexScan

正如我们在课堂上学到的，当在索引列上查询时，使用 IndexScan 将显著提高查找性能。为此，我们需要将过滤条件下推到扫描器中，以便知道在索引中查找的键。然后我们可以直接通过索引检索值，而不是进行全表扫描。

你需要修改优化器，在可能的情况下将 SeqScanPlanNode 转换为 IndexScanPlanNode。

考虑以下示例：

bustub> EXPLAIN (o) SELECT * FROM t1 WHERE v1 = 1;

在不应用 MergeFilterScan 和 SeqScan as IndexScan 优化器规则的情况下，计划可能如下所示：

 Filter { predicate=(#0.0=1) } | (t1.v1:INTEGER, t1.v2:INTEGER, t1.v3:INTEGER)
   SeqScan { table=t1 } | (t1.v1:INTEGER, t1.v2:INTEGER, t1.v3:INTEGER)                              

在应用 MergeFilterScan 和 SeqScan as IndexScan 优化器规则之后，我们可以直接进行快速索引查找，而无需遍历整个表。结果计划将如下所示：

 IndexScan { index_oid=0, filter=(#0.0=1) } | (t1.v1:INTEGER, t1.v2:INTEGER, t1.v3:INTEGER)

以下是实现此优化器规则的简要步骤：

1. 启用谓词下推到 SeqScan： 我们可以在 SeqScanExecutor 中实现谓词过滤，以便后续索引扫描节点拥有该谓词。我们已经在入门优化器规则中为你启用了 MergeFilterScan 优化器规则 src/optimizer/merge_filter_scan.cpp 。

2. 使用索引： 你可以检查谓词中的过滤列。如果该列上恰好存在索引，则创建一个 IndexScanPlanNode。注意，要获得满分，你需要在几种不同情况下支持此优化器规则：(1) 当谓词中索引列上有一个等值测试时（即 WHERE v1 = 1）(2) 当索引列的顺序反转时（即 WHERE 1 = v1）(3) 当同一索引上有多个点查找时（即 WHERE v1 = 1 or v1 = 4）。注意，SELECT * FROM t1 WHERE v1 = 1 AND v2 = 2 形式的查询仍应使用顺序扫描，因此你不需要拆分谓词。

请查看优化器规则实现指南部分了解实现优化器规则的详细信息。

现在你已经实现了所有与存储相关的执行器。在接下来的任务中，你可以自己创建表并插入一些值来测试你的执行器实现！此时，你还应该已经通过了 SQLLogicTests #1 到 #6。

提示：你可能会发现工具函数 BPlusTreeIndex::ScanKey 很有帮助。

提示：思考如何处理 WHERE v1 = 1 OR v1 = 1 形式的查询。查看 /src/include/execution/plans/aggregation_plan.h 中的 AggregateKey 可能会有所帮助。

提示：请仅在上面提到的两种场景中将 SeqScan 优化为 IndexScan（即点查找和有序扫描）。

聚合

AggregationPlanNode 用于支持如下查询：

EXPLAIN SELECT colA, MIN(colB) FROM __mock_table_1 GROUP BY colA;
EXPLAIN SELECT COUNT(colA), min(colB) FROM __mock_table_1;
EXPLAIN SELECT colA, MIN(colB) FROM __mock_table_1 GROUP BY colA HAVING MAX(colB) > 10;
EXPLAIN SELECT DISTINCT colA, colB FROM __mock_table_1;

聚合执行器为每组输入计算一个聚合函数。它恰好有一个子节点。 输出模式由分组列后跟聚合列组成。

正如课堂上讨论的，实现聚合的常见策略是使用哈希表，以分组列作为键。在本项目中，你可以假设聚合哈希表适合内存。这意味着你不需要实现多阶段的基于分区的策略，哈希表也不需要由缓冲池页面支持。

我们提供了一个 SimpleAggregationHashTable 数据结构，它公开了一个内存哈希表（std::unordered_map），但具有专为计算聚合设计的接口。此类还公开了一个 SimpleAggregationHashTable::Iterator 类型，可用于遍历哈希表。你需要完成此类的 CombineAggregateValues 函数。

聚合执行器本身不需要处理 HAVING 谓词。计划器将带有 HAVING 子句的聚合规划为 AggregationPlanNode 后跟一个 FilterPlanNode。

提示：在查询计划的上下文中，聚合是流水线阻断器。这可能会影响你在实现中使用 AggregationExecutor::Init() 和 AggregationExecutor::Next() 函数的方式。仔细决定聚合的构建阶段应在 AggregationExecutor::Init() 还是 AggregationExecutor::Next() 中执行。

提示：你必须处理聚合函数输入中的 NULL 值（即元组可能在聚合函数使用的属性上具有 NULL 值）。请参阅测试用例了解预期行为。分组列永远不会为 NULL。

提示：在空表上执行聚合时，CountStarAggregate 应返回零，所有其他聚合类型应返回 integer_null。这就是 GenerateInitialAggregateValue 将大多数聚合值初始化为 NULL 的原因。

NestedLoopJoin

默认情况下，DBMS 将对所有连接操作使用 NestedLoopJoinPlanNode。考虑以下示例查询：

EXPLAIN SELECT * FROM __mock_table_1, __mock_table_3 WHERE colA = colE;
EXPLAIN SELECT * FROM __mock_table_1 INNER JOIN __mock_table_3 ON colA = colE;
EXPLAIN SELECT * FROM __mock_table_1 LEFT OUTER JOIN __mock_table_3 ON colA = colE;

你需要使用课堂上的简单嵌套循环连接算法为 NestedLoopJoinExecutor 实现内连接和左连接。此算子的输出模式是左表的所有列后跟右表的所有列。 对于外表中的每个元组，考虑内表中的每个元组，如果连接谓词满足则发出一个输出元组。

提示：你应该使用 NestedLoopJoinPlanNode 中的谓词。请参阅 AbstractExpression::EvaluateJoin，它处理左元组和右元组及其各自的模式。注意，这返回一个 Value，可能是 false、true 或 NULL。请参阅 FilterExecutor 了解如何在元组上应用谓词。

HashJoin

如果查询包含两个列之间多个等值条件的合取（等值条件由 AND 分隔），DBMS 可以使用 HashJoinPlanNode。考虑以下示例查询：

EXPLAIN SELECT * FROM __mock_table_1, __mock_table_3 WHERE colA = colE;
EXPLAIN SELECT * FROM __mock_table_1 INNER JOIN __mock_table_3 ON colA = colE;
EXPLAIN SELECT * FROM __mock_table_1 LEFT OUTER JOIN __mock_table_3 ON colA = colE;
EXPLAIN SELECT * FROM test_1 t1, test_2 t2 WHERE t1.colA = t2.colA AND t1.colB = t2.colC;
EXPLAIN SELECT * FROM test_1 t1 INNER JOIN test_2 t2 on t1.colA = t2.colA AND t2.colC = t1.colB;
EXPLAIN SELECT * FROM test_1 t1 LEFT OUTER JOIN test_2 t2 on t2.colA = t1.colA AND t2.colC = t1.colB;

你需要使用课堂上的哈希连接算法为 HashJoinExecutor 实现内连接和左连接。此算子的输出模式是左表的所有列后跟右表的所有列。与聚合一样，你可以假设连接使用的哈希表完全适合内存。

你的实现应正确处理多个元组发生哈希冲突的情况（在连接的任一侧）。你将需要使用 HashJoinPlanNode 中的连接键访问器函数 GetLeftJoinKey() 和 GetRightJoinKey() 来分别构造连接的左侧和右侧的连接键。

提示：你需要一种方法来对具有多个属性的元组进行哈希处理，以构造唯一的键。作为起点，请查看 AggregationExecutor 中的 SimpleAggregationHashTable 如何实现此功能。

提示：与聚合一样，哈希连接的构建侧是流水线阻断器。你应该再次考虑哈希连接的构建阶段应在 HashJoinExecutor::Init() 还是 HashJoinExecutor::Next() 中执行。

将 NestedLoopJoin 优化为 HashJoin

哈希连接通常比嵌套循环连接产生更好的性能。 你应该修改优化器，在可以使用哈希连接时将 NestedLoopJoinPlanNode 转换为 HashJoinPlanNode。具体来说，当连接谓词是两个列之间多个等值条件的合取时，可以使用哈希连接算法。在本项目中，你应该能够处理由 AND 连接的不同数量的等值条件。

考虑以下示例：

bustub> EXPLAIN (o) SELECT * FROM test_1 t1, test_2 t2 WHERE t1.colA = t2.colA AND t1.colB = t2.colC;

在不应用 NLJAsHashJoin 优化器规则的情况下，计划可能如下所示：

 NestedLoopJoin { type=Inner, predicate=((#0.0=#1.0)and(#0.1=#1.2)) } 
   SeqScan { table=test_1 }                                           
   SeqScan { table=test_2 }

在应用 NLJAsHashJoin 优化器规则之后，将从 NestedLoopJoinPlanNode 的单个连接谓词中提取左右连接键表达式。结果计划将如下所示：

 HashJoin { type=Inner, left_key=[#0.0, #0.1], right_key=[#0.0, #0.2] } 
   SeqScan { table=test_1 }                                             
   SeqScan { table=test_2 } 

请查看优化器规则实现指南部分了解实现优化器规则的详细信息。此时，你应该通过 SQLLogicTests - #14 到 #15。

提示：确保检查等值条件每一侧的列属于哪个表。外表的列可能位于等值条件的右侧。你可能会发现 ColumnValueExpression::GetTupleIdx 很有帮助。

提示：应用优化器规则的顺序很重要。例如，你应该在过滤器和 NestedLoopJoin 合并之后再优化 NestedLoopJoin 为 HashJoin。

提示 在处理多个等值条件时，尝试递归地提取键，而不是用多层 if 子句来匹配连接条件。

外部归并排序

除非 ORDER BY 属性与索引的键匹配，否则 BusTub 将对所有 ORDER BY 算子使用 SortPlanNode。

EXPLAIN SELECT * FROM __mock_table_1 ORDER BY colA ASC, colB DESC;

此计划节点不改变模式（即输出模式与输入模式相同）。你可以从 order_bys 中提取排序键。如果查询在 ORDER BY 子句中未包含排序方向（即 ASC、DESC），则排序模式将为 default（即 ASC）。

关于外部归并排序的一个重要假设是表中的条目无法全部放入内存。因此，你需要按照课堂上学到的内容：将中间排序结果存储在临时页面中，并基于上一轮的排序结果递归地进行归并排序。

你可能已经意识到，中间排序结果需要特定的页面格式。在本项目中，你将负责设计页面格式。查看 external_merge_sort_executor.h，你会发现 SortPage，它专门用于存储中间排序结果，但只包含最少的预定义成员/方法。你应该设计页面布局并实现页面的读/写方法。

然后你将实现归并排序算法。进行内存归并排序并不难。但当涉及磁盘时，你应该仔细思考如何通过页面接口和缓冲池操作排序后的元组。值得注意的是，不再使用的页面（即来自上一轮归并排序的页面）应该被删除，否则你将有一堆永远不会被引用但仍然存在于缓冲池中的"僵尸"页面。

为了简化你的 SortPage 实现，本学期我们只测试定长元组的排序。也就是说，我们不会排序包含 VARCHAR 属性的元组。此外，本学期我们只测试两路外部归并排序，即使 ExternalMergeSortExecutor 是模板化的。因此，你可以自由地实现两路归并排序算法，而不是 k 路归并。

但是，重要的是你确实在进行外部归并排序（不是将所有数据纯粹存储在内存中）。你可以使用 std::sort 对适合一个排序页面的元组进行排序，但不能对所有元组使用。此外，你的 SortPage 布局应该是紧凑的，即尽可能少的碎片。你还应该确保在归并排序完成后页面确实被删除了。

提示：对于基于排序键的元组比较，我们在 execution_common.h 中提供了一个辅助类 TupleComparator。我们还提供了一个辅助函数 GenerateSortKey，在排序元组时你可能会发现它很有帮助。

提示：为了更好地理解 SortPage 应该做什么以及从哪里开始，你可以查看你在项目 2 中使用的索引页面布局（例如，char 数组可以用作页面数据的起始）。鉴于我们只测试定长数据的假设，你可能会发现 Schema::GetInlinedStorageSize 很有帮助。此外，思考你的执行器将如何调用读/写方法也会很有帮助。

提示：在进行外部归并排序时，你实际上不需要手动操作"写入磁盘"的部分。缓冲池管理器会为你处理这些。记住你在 P1 中实现的内容：页面守卫会自动固定和取消固定页面，以及设置可驱逐性。只要正确使用页面守卫，你就不必在这个项目中过多担心页面操作。

Limit

LimitPlanNode 指定查询将生成的元组数量。考虑以下示例：

EXPLAIN SELECT * FROM __mock_table_1 LIMIT 10;

LimitExecutor 限制其子执行器输出的元组数量。如果其子执行器生成的元组数量少于计划节点中指定的限制，则此执行器无效，并产生它接收到的所有元组。

此计划节点不改变模式（即输出模式与输入模式相同）。你不需要支持偏移量。

查询 1：太多连接了！

考虑以下示例数据库：

CREATE TABLE t4(x int, y int);
CREATE TABLE t5(x int, y int);
CREATE TABLE t6(x int, y int);

用户不是来自 CMU，他们写出了糟糕的 SQL。他们忘记了如何编写带连接的查询，所以把所有谓词都放在了 WHERE 子句中。

SELECT * FROM t4, t5, t6
  WHERE (t4.x = t5.x) AND (t5.y = t6.y) AND (t4.y >= 1000000)
    AND (t4.y < 1500000) AND (t6.x >= 100000) AND (t6.x < 150000);

推荐优化： 分解过滤条件以提取哈希连接键，并将剩余的过滤条件下推到哈希连接之下。

查询 2：疯狂的数据科学家

有一位数据科学家把所有的钱都投资了 NFT。在意识到他们可怕的错误之后，他们发疯了，开始写一些奇怪的 SQL 查询。考虑以下示例：

SELECT v, d1, d2 FROM (
  SELECT v,
         MAX(v1) AS d1, MIN(v1), MAX(v2), MIN(v2),
         MAX(v1) + MIN(v1), MAX(v2) + MIN(v2),
         MAX(v1) + MAX(v1) + MAX(v2) AS d2
    FROM t7 LEFT JOIN (SELECT v4 FROM t8 WHERE 1 == 2) ON v < v4
    GROUP BY v
)

（这与实际的排行榜查询不同；请参阅测试文件。）

推荐优化：

• 列裁剪 —— 你只需要从聚合中的左表计算 v、d1、d2。我们提供了一个骨架文件 column_pruning.cpp。
• 公共表达式消除，将永远为假的过滤器转换为虚拟扫描（零行的值计划节点）
• 如果你能想到更多的话 :)

提示：你不需要实现完整的规则来优化这些查询。(1) 完整的谓词下推需要你处理所有计划节点 —— limit、order by 等。但要优化 Q2，你只需要实现对哈希连接/嵌套循环连接的谓词下推。(2) 完整的连接重排序需要你正确处理谓词（并且可能需要将中间的过滤器吸收回连接谓词），你不需要这样做。只需让你的优化器能处理这些查询就够了。

查询 3：白忙一场？

在完成了 Q1 和 Q2 的辛苦工作之后，这里有一个简短而有趣的题目。假设你有以下两个表，分别表示 1950 年代在世的每个人和 1600 年代出生的每个人。一个不了解人类寿命概念（或坚信吸血鬼存在）的人试图构造一个查询来输出这两个表的交集。你知道结果将为空，但你的连接执行器不知道，你能做什么来帮助加速这个过程？

SELECT * FROM alive_in_1950s a INNER JOIN born_in_1600s b ON a.birthday = b.birthday

（这与实际的排行榜查询不同；请参阅测试文件。）

推荐优化： 为哈希连接构建阶段使用的哈希表添加布隆过滤器。