CMU数据库（15-445）Lab3- QUERY EXECUTION

Lab3 - QUERY EXECUTION

实验三是添加对在数据库系统中执行查询的支持。您将实现负责获取查询计划节点并执行它们的executor。您将创建执行下列操作的executor

Access Methods: Sequential Scans, Index Scans (with your B+Tree from Project #2)

Modifications: Inserts, Updates, Deletes

Miscellaneous: Nested Loop Joins, Index Nested Loop Joins, Aggregation, Limit/Offset

拓展阅读following a select statement through the PostgreSQL internals

Task1 - 热身任务

数据库维护一个内部目录来跟踪关于数据库的元数据。例如，目录用于回答存在哪些表以及表的位置。更多细节请参见.

你需要修改src/include/catalog/catalog.h允许DBMS添加新表到数据库中，并使用名称或内部对象标识符(table_oid_t)检索它们。你将实现以下方法

CreateTable(Transaction *txn, const std::string &table_name, const Schema &schema)

GetTable(const std::string &table_name)

GetTable(table_oid_t table_oid)

您还需要支持向目录添加索引(基于项目#2 Project #2))。与table_oid_t类似，索引oid t是索引的唯一对象标识符。您将实现以下方法

CreateIndex(txn, index_name, table_name, schema, key_schema key_attrs, keysize)

GetIndex(const std::string &index_name, const std::string &table_name)

GetIndex(index_oid_t index_oid),

GetTableIndexes(const std::string &table_name)

第一个任务官网给的评价是简单。

1.1 添加新表

其实就围绕这table的构造函数和源代码给的数据结构设计就好了

这里要维护好两个hash表

table_name --- table_id

Table_id --- unique_ptr

TableMetadata *CreateTable(Transaction *txn, const std::string &table_name, const Schema &schema) { BUSTUB_ASSERT(names_.count(table_name) == 0, "Table names should be unique!"); auto table_id = next_table_oid_++; TableHeap *_table = new TableHeap(bpm_, lock_manager_, log_manager_, txn); names_[table_name] = table_id; auto new_table = new TableMetadata(schema, table_name, static_cast<std::unique_ptr<TableHeap>>(_table),table_id); tables_[table_id] = static_cast<std::unique_ptr<TableMetadata>>(new_table); return new_table; }

剩下的两个get函数就是简单的hash表操作。由于Andy教授不提倡share代码。这里就简单附上一个实现，剩下的另一个基本没差

TableMetadata *GetTable(const std::string &table_name) { if (names_.count(table_name) == 0) { throw std::out_of_range(table_name); } table_oid_t id = names_[table_name]; if (tables_[id] != 0) { return tables_[id].get(); } return 0; } 1.2 添加索引

这里要注意一点我们添加的索引。是基于我们lab2实现过的b+树索引。

这里注意我们的index_Info函数需要一个Index的unique_ptr这里我们需要new一个BPlusTreeIndex传入。

我们要对当前表中所有tuple加上index

这里也需要维护好两个hash表

template <class KeyType, class ValueType, class KeyComparator> IndexInfo *CreateIndex(Transaction *txn, const std::string &index_name, const std::string &table_name, const Schema &schema, const Schema &key_schema, const std::vector<uint32_t> &key_attrs, size_t keysize) { auto index_id = next_index_oid_++; auto index_me = new IndexMetadata(index_name, table_name, &schema, key_attrs); std::unique_ptr<Index> BPlusTree_Index(new BPlusTreeIndex<KeyType, ValueType, KeyComparator>(index_me, bpm_)); IndexInfo *new_index = new IndexInfo(key_schema, index_name, std::move(BPlusTree_Index), index_id, table_name, keysize); indexes_[index_id] = static_cast<std::unique_ptr<IndexInfo>>(new_index); index_names_[table_name].insert(std::unordered_map<std::string, index_oid_t>::value_type (index_name, index_id)); auto table = GetTable(table_name)->table_.get(); // add index for every tuple for (auto it = table->Begin(txn); it != table->End(); ++it) { new_index->index_->InsertEntry(it->KeyFromTuple(schema, key_schema, key_attrs), it->GetRid(), txn); } return new_index; }

最后的get操作还是一样的。附上一个实现

IndexInfo *GetIndex(const std::string &index_name, const std::string &table_name) { if (index_names_.count(table_name) == 0) { throw std::out_of_range(table_name); } index_oid_t index_id = index_names_[table_name][index_name]; return indexes_[index_id].get(); }

可以通过cmu给出的对于catalog的test。这个测试文件就是线上评测用的测试文件。

Task2 - EXECUTORS

在第二个任务中，您将实现执行程序以进行顺序扫描，插入，哈希联接和聚合。 对于每种查询计划运算符类型，都有一个相应的executor对象，该对象实现Init和Next方法。 Init方法用于设置有关操作调用的内部状态（例如，检索要扫描的对应表）。 Next方法提供了迭代器接口，该接口在每次调用时返回一个元组（如果没有更多的元组，则返回null）。

你需要修改下面的文件来完成这一任务。

src/include/execution/executors/seq_scan_executor.h

src/include/execution/executors/index_scan_executor.h

src/include/execution/executors/insert_executor.h

src/include/execution/executors/update_executor.h

src/include/execution/executors/delete_executor.h

src/include/execution/executors/nested_loop_join_executor.h

src/include/execution/executors/nested_index_join_executor.h

src/include/execution/executors/aggregation_executor.h

src/include/execution/executors/limit_executor.h

我们假设执行器在整个项目中都是单线程的。您还可以根据需要随意添加私有函数和类成员。