description |
---|
PROJECT #3 - QUERY EXECUTION |
这个 project 主要是实现增加对数据库系统的执行计划的支持。需要实现各种 executors,将 query plan 传入 executors 然后执行它们。需要实现下列的 executors:
- Access Methods: Sequential Scans, Index Scans
- Modifications: Inserts, Updates, Deletes
- Miscellaneous: Nested Loop Joins, Index Nested Loop Joins, Aggregation, Limit/Offset
我们需要实现迭代查询处理模型,每个查询计划执行器实现了一个 Init()
函数和 Next()
函数。当 DBMS 调用 executors 的 Next()
函数时,它会返回
- 一个
tuple
并返回true
- 没有
tuple
可以再返回时,返回false
这个 task 不难,主要是实现
src/include/catalog/catalog.h
文件(catalog 维护了数据库的 meta-data)中的要求实现的函数,这些函数与数据库的表和索引有关。
GetTable()
使用std::unordered_map
的at
函数,它会做下标检查,当key
不存在时会抛出异常- 在
CreateIndex
函数中,创建表的索引时,需要使用 table heap 的迭代器取出每个 tuple,然后使用 tuple 的KeyFromTuple
构造 key tuple 插入到 B+ Tree 中
在顺序执行器中,如何保存
table_heap_
的迭代器呢?一直没找到解决方案,因为我先选择在使用std::vector<Tuple>
先保存结果,然后在Next
中一个一个返回。在返回结果时,记得要根据OutputSchema
构造 tuple 返回
|
Tuple make_tuple(const Tuple &tuple, const Schema *output_schema) {
std::vector<Value> values;
for (const auto &col : output_schema->GetColumns()) {
values.push_back(tuple.GetValue(output_schema, output_schema->GetColIdx(col.GetName())));
}
return Tuple(values, output_schema);
}
INDEX SCANS
通过 B+ Tree 索引,先获得 RID
,然后根据 RID
在 table_heap_
中得到对应的 tuple
- 通过
dynamic_cast<BPlusTreeIndex<GenericKey<8>, RID, GenericComparator<8>> *>(indexInfo_->index_.get());
将 Index
转成 BPlusTreeIndex
类型
INSERT
- 插入执行器需要区分待插入的数据是
RawInsert
还是来自 child_executor_
- 如果待插入的表存在索引需要使用
KeyFromTuple
构造 index_key
,然后将它插入到 B+ Tree 索引中
- engine 在插入、更新、删除不需要将 tuple 添加到
result_set
中,否则在 test 中会报 result_set
不为空的错误
UPDATE
由 child_executor_
的 Next
提供 tuple,然后调用 GenerateUpdatedTuple
生成待更新的 tuple,最后使用 table_heap_->UpdateTuple
进行更新操作
DELETE
- 由
child_executor_
的 Next
提供 tuple
- 调用
table_heap_->MarkDelete
标记这个 tuple 需要删除
- 如果待插入的表存在索引需要使用
KeyFromTuple
构造 index_key
,然后在 B+ Tree 索引中将这个 Key 删除
NESTED LOOP JOIN
使用 left_executor
和 right_executor
提供的 tuple 进行 EvaluateJoin
构造符合条件的 tuple
INDEX NESTED LOOP JOIN
使用索引来进行 Join,这样就不需要扫描整个 inner table。因此我们需要将 outer tuple 转化为对应的 key
,然后在 inner table index 中进行查找。
测试/验证/打包
- 测试
cd build
make executor_test
- 格式验证
make format
make check-lint
make check-clang-tidy
- 打包
zip project3-submission.zip src/include/buffer/lru_replacer.h src/buffer/lru_replacer.cpp \
src/include/buffer/buffer_pool_manager.h src/buffer/buffer_pool_manager.cpp \
src/include/storage/page/b_plus_tree_page.h src/storage/page/b_plus_tree_page.cpp \
src/include/storage/page/b_plus_tree_internal_page.h src/storage/page/b_plus_tree_internal_page.cpp \
src/include/storage/page/b_plus_tree_leaf_page.h src/storage/page/b_plus_tree_leaf_page.cpp \
src/include/storage/index/b_plus_tree.h src/storage/index/b_plus_tree.cpp \
src/include/storage/index/index_iterator.h src/storage/index/index_iterator.cpp \
src/include/catalog/catalog.h src/include/execution/execution_engine.h src/include/storage/index/index.h \
src/include/execution/executor_factory.h src/execution/executor_factory.cpp \
src/include/execution/executors/seq_scan_executor.h src/execution/seq_scan_executor.cpp \
src/include/execution/executors/index_scan_executor.h src/execution/index_scan_executor.cpp \
src/include/execution/executors/insert_executor.h src/execution/insert_executor.cpp \
src/include/execution/executors/update_executor.h src/execution/update_executor.cpp \
src/include/execution/executors/delete_executor.h src/execution/delete_executor.cpp \
src/include/execution/executors/nested_loop_join_executor.h src/execution/nested_loop_join_executor.cpp \
src/include/execution/executors/nested_index_join_executor.h src/execution/nested_index_join_executor.cpp \
src/include/execution/executors/limit_executor.h src/execution/limit_executor.cpp \
src/include/execution/executors/aggregation_executor.h src/execution/aggregation_executor.cpp \
src/include/storage/index/b_plus_tree_index.h src/storage/index/b_plus_tree_index.cpp
然后前往 https://www.gradescope.com 提交代码