Project #3 - Query Execution 项目要求

Project #1 中我们实现了一个 buffer pool manager。Project #2 中我们实现了一个 B+Tree 索引。在此次 Project，你将实现一个让 BusTub 执行 query 的组件。你要创建 operator executors 来执行 SQL queries，实现 optimizer rules 来 transform query plans。

• Task #1: Access Method Executors
• Task #2: Aggregation and Join Executors
• Task #3: Sort + Limit Executors and Top-N Optimization
• Leaderboard Task (Optional)

BACKGROUND

我们首先讨论 query process 的基本知识。请仔细阅读这部分，因为在本项目中，需要你们自己构建 sql queries，以测试 executor 的实现。

BusTub 架构：

我们已经提供了一个完成的 query processing layer，你可以使用 BusTub shell 来执行 SQL queries，就像 homework 1 中的一样。使用如下命令可以编译并构建 BusTub shell。也可以使用 BusTub Web Shell 在线运行 sql queries。

cd build && make -j$(nproc) shell
./bin/bustub-shell

在 shell 中可使用 \dt 获取所有表。默认情况下，BusTub shell 会自动创建三个预先填充了数据的表格。这是为你提供的便利，这样你就不必在每次重建你的代码时加载假数据。当你重新启动 DBMS 时，对这些表的任何改变都不会被保存。

bustub> \dt
+-----+----------------+------------------------------+
| oid | name           | cols                         |
+-----+----------------+------------------------------+
| 0   | __mock_table_1 | (colA:INTEGER, colB:INTEGER) |
| 1   | __mock_table_2 | (colC:VARCHAR, colD:VARCHAR) |
| 2   | __mock_table_3 | (colE:INTEGER, colF:VARCHAR) |
| ... | ...            | ...                          |
+-----+----------------+------------------------------+

你可以通过 SELECT 语句来获取表中的数据。

bustub> SELECT * FROM __mock_table_1;
+---------------------+---------------------+
| __mock_table_1.colA | __mock_table_1.colB |
+---------------------+---------------------+
| 0                   | 0                   |
| 1                   | 100                 |
| 2                   | 200                 |
| 3                   | 300                 |
| 4                   | 400                 |
| 5                   | 500                 |
| ...                 | ...                 |
+---------------------+---------------------+

注意：

• BusTub只支持一小部分的 SQL 语法。如果它对某些 SQL 查询不起作用，请不要感到惊讶。关于BusTub支持的所有 SQL 查询，请参考 tests/sql 中的SQLLogicTest 文件。
• 如果你使用 CLion 来运行 BusTub 的 shell，请在 shell 中添加一个 --disable-tty 参数，这样它就能在 CLion 终端中正确工作。
• 语句的结尾一定要用;（内部命令除外）。
• BusTub只支持 INT和 VARCHAR(n) 类型。另外，你应该对字符串使用单引号，例如：INSERT INTO table VALUES ('a')。

Explain SQL Queries

我们接下来讨论 BusTub shell 怎样知道给出输入 SELECT * FROM __mock_table_1; 时，应该从 __mock_table_1 中读取所有数据。BusTub 也支持 EXPLAIN 语句 print query 的 execution plan。你可以添加 EXPLAIN 在 query 开头，来查看到这些信息：

bustub> EXPLAIN SELECT * FROM __mock_table_1;
=== BINDER ===
BoundSelect {
  table=BoundBaseTableRef { table=__mock_table_1, oid=0 },
  columns=[__mock_table_1.colA, __mock_table_1.colB],
  groupBy=[],
  having=,
  where=,
  limit=,
  offset=,
  order_by=[],
  is_distinct=false,
}
=== PLANNER ===
Projection { exprs=[#0.0, #0.1] } | (__mock_table_1.colA:INTEGER, __mock_table_1.colB:INTEGER)
MockScan { table=__mock_table_1 } | (__mock_table_1.colA:INTEGER, __mock_table_1.colB:INTEGER)
=== OPTIMIZER ===
MockScan { table=__mock_table_1 } | (__mock_table_1.colA:INTEGER, __mock_table_1.colB:INTEGER)

EXPLAIN 的结果提供了 query processing layer 内 transformation process 的概况。

语句首先会进入 parser 和 binder，产生 AST 抽象语法树。这让 BusTub 理解 query 想要做什么。在这个例子中，query 希望对 __mock_table_1 执行 BoundSelect，并检索两列 (即 colA 和 colB)。注意 binder 会自动将原始 SQL query 中的 * 字符扩展为表中的实际列。

然后 binder AST 会进入 planner，planner 会产生 query 的 query plan。query 被 plan 为一棵有两个节点的树，数据从树的叶子流向根。

最后 optimizer 将优化这个 query plan。在这个例子中，他将删除 projection plan node 因为它是冗余的。

下面，来看另一个更复杂的例子：

bustub> EXPLAIN (o) SELECT colA, MAX(colB) FROM
  (SELECT * FROM __mock_table_1, __mock_table_3 WHERE colA = colE) GROUP BY colA;
=== OPTIMIZER ===
Agg { types=[max], aggregates=[#0.1], group_by=[#0.0] }
  NestedLoopJoin { type=Inner, predicate=(#0.0=#1.0) }
    MockScan { table=__mock_table_1 }
    MockScan { table=__mock_table_3 }

在 BusTub 中 optimizer 的输出总是一棵树，对于?这个例子，这棵树长这样：

如果你在 BusTub Web Shell 中运行这个用例，你会发现使用了 HashJoin 而不是 NestedLoopJoin。

在本学期的项目中，你无需实现 HashJoin。

此次 Project 中，你需要构造 SQL queries 来测试你实现的 executors。EXPLAIN 对于你了解一个 SQL query 是否使用了一个特定的 executor 是非常重要的。

Sample Executors

我们已经实现了几个 executor。下面我们看下 planner 何时会将 SQL queries 计划 (plan) 为这些 plan nodes。

Projection

一个 projection plan node 用于对一个输入进行计算。它总是正好有一个 child 结点。?

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;

一个 projection plan node 包含几个计算的表达式，它可以是 ColumnValueExpression(此处 colA 在 explain 的时候会被展示为 #0.0)，表示直接将 child executor 的第一列放到这个输出列；或者是 ConstantExpression，表示一个常量值 (如 1)。表达式也可以用树形表示，如 1+2 是一个有两个 ConstantExpression (1 和 2) 作为孩子结点的 ArithmeticExpression。

注意，语法 #0.0 意味着第一个 child 的第一个列， #0.1 意味着第一个 child 的第二个列。在 plan join 的时候，你会看到类似 #0.0 = #1.0 的情况。

Filter

一个 filter plan node 用于使用一个给定的 predicate 过滤 child 的输出。?

EXPLAIN SELECT * FROM __mock_table_1 WHERE colA > 1;

一个 filter plan node 正好有一个 child 结点，并包含一个谓词。

Values

一个 values plan node 用于直接产生一个值。?

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');

value plan node 在往 table 中插入用户提供的 value 时非常有用。

Schema

你可能注意到了，在 explain 的时候，每个 plan node 后面都跟着一长串的列表述。这是 plan node 的 expected output schema。

Projection { exprs=[#0.0, #0.1] } | (__mock_table_1.colA:INTEGER, __mock_table_1.colB:INTEGER)

这表明这个 plan node 的 executor 将产生两个列。它们都是整数类型。output schema 是在 planner 上推断出来的。此次 Project 中，你实现的 executor 必须产生与 plan node 中指定的 schema 完全一致的 tuple，否则将无法通过检查输出的测试。

PROJECT SPECIFICATION

对于这个 Project，您需要在 BusTub 中实现额外的 operator executor。我们将使用 iterator query processing model (即 the Volcano model)。在这个模型中，每个 query plan executor 都实现 Next 函数。当 DBMS 调用 executor 的 Next 函数时，executor 返回 (1) a single tuple (2) 一个 no more tuple 的指示符。使用这种方法，每个 executor 实现一个循环，该循环继续对其 children 调用 Next 以检索元组并逐个处理它们。

在 BusTub 的 iterator model 实现中，每个执行器的 Next 函数除了返回一个 tuple 外还返回一个 record 标识符 (RID)。record 标识符用作 tuple 的唯一标识符。

executor 是根据 executor_factory.cpp 中的 execution plan 创建的。

这个 Project 中的所有测试用例都是以一种称为 SQLLogicTest (源自 SQLite) 的特殊文件格式编写的。您可以在本页末尾找到如何使用它。

Task #1 - Access Method Executors

在 background 章节，我们可以看到 BusTub 已经能够在 SELECT 查询中从模拟表中检索数据。这是因为这些是特殊的表，实际上并不存储真正的 tuples。它们是“虚拟”表，是 MockScan Executor 使用预定义的算法生成的始终相同的 tuples。这也是不能更新这些表的原因。

本任务中，你要实现 Executor 来对存储中的表进行读取和写入。

涉及文件：

src/include/execution/seq_scan_executor.h
src/execution/seq_scan_executor.cpp
src/include/execution/insert_executor.h
src/execution/insert_executor.cpp
src/include/execution/delete_executor.h
src/execution/delete_executor.cpp
src/include/execution/index_scan_executor.h
src/execution/index_scan_executor.cpp

SeqScan

The SeqScanPlanNode can be planned with a SELECT * from table statement.

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 遍历一个表并返回它的 tuples，一次一个。

提示：使用 TableIterator 对象时要小心。确保您了解预增量运算符和后增量运算符之间的区别。如果在 ++iter 和 iter++ 之间切换，可能会发现得到了奇怪的输出。

提示：sequential scan 的输出是每个匹配的 tuple 以及它的 record 标识符 (RID)。

注意：BusTub 目前不支持 DROP TABLE 或 DROP INDEX。若要重置数据库则需重新启动 shell。

Insert

The InsertPlanNode can be planned with a INSERT statement.

注意：需要使用单引号来指定 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 将 tuples 插入表并更新索引。它正好有一个 child 来生成要插入到表中的值。planner 将确保该值与表具有相同的 schema。executor 将生成一个整数 tuple 作为输出，表示在插入完成后，表中插入的行数。如果表有相关联的索引，请在插入表时更新索引。

提示：在 executor 初始化期间，你需要查找要插入表的表信息。See "System Catalog"。

提示：你需要更新与插入表相关的所有索引。See "Index Updates"。

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

Delete

The DeletePlanNode can be planned with a DELETE statement.

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 删除表的 tuples 并更新索引。它只有一个 child，其中包含了要从表中删除的记录。executor 将生成一个整数输出，表示它从表中删除的行数。还需更新表相关联的索引。

你可以假设 DeleteExecutor 始终位于 query plan 的 root 位置。DeleteExecutor 不应该修改它的结果集。

提示：你需要从 child executor 中获取 RID，并调用 TableHeap::MarkDelete() 来删除 tuple。所有删除都将在事务提交时应用。

提示：你需要更新与删除表相关的所有索引。See "Index Updates"。

IndexScan

IndexScanExecutor 遍历索引来检索 tuple 的 RID，然后 operator 使用这些 RID 在相应的表中检索其 tuple。一次给一个 tuple。

你可通过 SELECT FROM <table> ORDER BY <index column> 来测试你的 index scan executor。下面解释下为什么 ORDER BY 会在 Task #3 中转为 IndexScan。

bustub> CREATE TABLE t2(v3 int, v4 int);
Table created with id = 16

bustub> CREATE INDEX t2v3 ON t2(v3);
Index created with id = 0

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

本次 Project 中，plan 中的索引对象将始终是 BPlusTreeIndexForOneIntegerColumn。你可以安全地将其强制转换并存储在 executor 对象中：

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

然后你可以从索引对象构造索引迭代器，扫描所有 key 和 tuple IDs，从 table heap 中查找元组。并按索引 key 的顺序发出所有 tuple 作为 executor 的输出。BusTub 仅支持具有单个唯一整数列的索引。测试用例中不会有重复的 key。

提示：现在你已经实现了所有与存储相关的 executor。在下面的任务中，你可以自己创建表并插入一些值来测试你的 executor 执行是否正确。此外还应该通过本地测试 SQLLogicTests #1 to #5。

Task #2 - Aggregation & Join Executors

涉及文件：

src/include/execution/aggregation_executor.h
src/execution/aggregation_executor.cpp
src/include/execution/nested_loop_join_executor.h
src/execution/nested_loop_join_executor.cpp
src/include/execution/nested_index_join_executor.h
src/execution/nested_index_join_executor.cpp

Aggregation

NestedLoopJoin

NestedIndexJoin

Task #3 - Sort + Limit Executors and Top-N Optimization

涉及文件：

src/include/execution/sort_executor.h
src/execution/sort_executor.cpp
src/include/execution/limit_executor.h
src/execution/limit_executor.cpp
src/include/execution/topn_executor.h
src/execution/topn_executor.cpp
src/optimizer/sort_limit_as_topn.cpp

Sort

Limit

Top-N Optimization Rule

Leaderboard Task (Optional)

ADDITIONAL INFORMATION

本节提供了一些关于 BusTub 中其他系统组件的额外信息，为了完成本 Project 你需要和它们交互。

System Catalog

数据库维护一个内部 catalog，以跟踪关于数据库的 meta-data 信息。在这个 Project 中，你将与 system catalog 交互，以查询有关 tables、indexes 及其 schemas 的信息。

catalog 的实现全部都在 src/include/catalog/catalog.h 中。你应该特别注意成员函数 Catalog::GetTable() 和 Catalog::GetIndex()。你将在 executor 的实现中使用这些函数来查询 catalog 中的表和索引。

Index Updates

对于会更改表的executors (InsertExecutor and DeleteExecutor)，你必须修改操作所针对的表的所有索引。你会发现 Catalog::GetTableIndexes() 函数对于查询为某个特定表定义的所有索引很有用。一旦你拥有表的每个索引的 IndexInfo 实例，你就可以在底层索引结构上调用索引修改操作。

在这个 Project 中，我们使用你在 Project 2 中对 B+Tree 索引的实现作为所有索引操作的底层数据结构。因此，本 Project 的成功完成依赖于 B+Tree 索引的工作实现。

INSTRUCTIONS

本地测试

$ cd build
$ make -j$(nproc) sqllogictest
$ ./bin/bustub-sqllogictest ../test/sql/p3.00-primer.slt --verbose

SUBMISSION

make format
make check-lint
make check-clang-tidy-p3

本栏目推荐文章
• 基于VueCli自定义创建项目
• IDEA项目名称后面出现中括号，模块Modules的名子和文件夹名称不同，可以右键修改名称也可以在File->Project Structure 修改Modules的Name(快捷键ctrl+Shift+Alt+s)
• 去年最火的 JS 开源项目「GitHub 热点速览」
• 用jacoco统计JAVA项目测试代码覆盖率
• 分享uniapp移动端和h5项目如何使用谷歌地图
• Pycharm项目文件变黄
• java项目(jar包)配置为开机自启 jar包bat脚本启动和配置为开机自启
• web项目启动时dubbo报错： No provider available for the service com.davidhu.shopguide.api.service.UserEventService from the url zookeeper ://localhost:2181/org.apache.du
• 蚂蚁爱购--靠谱的SpringBoot项目
• 人人都是项目经理

Execution Project 项目 Queryexecution project项目query execution project3心得project execution project数据库 数据 project fields return query project项目adding module 工程项目 插件project manager intellij project项目idea reference packages project项目 项目管理 多功能project工具 flutter project项目type