CMU15-445 Lab3 : 执行器实现

(Updated: )
数据库
, ,

Task1 - System Catalog

维护一个内部的目录来跟踪数据库内的元数据。

Catalog

Schema (class)

表的结构信息，不包含表的实际数据。

1
2
3
4
5
6
7
CREATE TABLE `t_user` (
  `id` int(11) NOT NULL,
  `name` VARCHAR(20) DEFAULT NULL,
  `phone` VARCHAR(20) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB DEFAULT CHARACTER SET = ascii ROW_FORMAT = COMPACT;

这些信息就由 Schema 来储存，真实数据数据会通过 Tuple 来储存。

TableHeap 与 Schema 结合才是完整的表。

Column (class)

表示列的信息。

1
2
3
4
5
// 例如： column_name_ = 'id' column_type_ = INTEGER ...
std::string column_name_;      // column 名字
TypeId column_type_;           // column 类型  INVALID, BOOLEAN, TINYINT, SMALLINT, INTEGER, BIGINT, DECIMAL, VARCHAR, TIMESTAMP 
uint32_t variable_length_{0};  // 变量长度
uint32_t column_offset_{0};    // 这一列在 `Tuple` 中的偏移量

TableHeap (class)

表示磁盘上的物理表。

由多个 TablePage 组成，插入时从第一张 TablePage 开始，不能插入就尝试下一张，或者新建一张（没有下一张时），只到由空余的位置插入 Tuple。

更新，删除，查找通过 Rid::GetPageId() 可以轻松在 BufferPoolManger 中找到对应的 TablePage，并且通过 Rid::GetSlotNum() 在 TablePage 中找到对应的 Tuple。

TablePage (class)

继承 Page

format

Header 的大小是 24 ，使用偏移量来获得 Page 中的每个值。

插入 Tuple

使用 memcpy 将 Tuple::Data 拷贝一份到TablePage::Data 对应的位置上。

同时会修改参数 Rid 做为这条 Tuple 的标志符，接下来更新、删除、查找这条 Tuple 都要依靠 Rid。

更新 Tuple

使用memmove 来将原来的 TablePage::Data 中要被更新的 Tuple::Data 移动到TablePage::Data后面。

重新设置TablePage::Data 中的 Tuple::Data的偏移量。

删除 Tuple

MarkDelete

只是标记为被删除，实际 TupleCount 和 free_space_pointer 都没有被改变，之后可以通过 TablePage::RollbackDelete(const RID &rid,...) 来恢复。

ApplyDelete

使用 memmove 将内容移除，不可恢复，删除后同样需要设置 TablePage::Data 中的 Tuple::Data的偏移量。

Tuple (class)
1
2
3
bool allocated_;  // 是否被分配了内存
uint32_t size_;   // 被分配内存的大小
char *data_;      // 被分配的内存（数据）

format

Rid (class)

通过 Rid 就能快速找到 TablePage 中的 Tuple 。

1
2
page_id_t page_id_{INVALID_PAGE_ID};  // 这个 `Tuple` 在哪页上
uint32_t slot_num_{0};                // `TablePage` 中的偏移量

TableIterator (class)

为 sequential scan TableHeap 提供的迭代器。

*TableIterator 会返回一个 Tuple

TableIterator 只会向前迭代，每次都是迭代一张表（而不是一张 Page，一张表可能有多个 Page 组成 ）。

TableMetadata (class)

1
2
3
4
Schema schema_;
std::string name_;
std::unique_ptr<TableHeap> table_;
table_oid_t oid_;

将 TableHeap 与 Schema 封装起来组成完整的表，同时加入表名称 name 和表的标示号 oid_ 来帮助 Catalog 管理多个表。

IndexInfo (class)

1
2
3
4
5
6
Schema key_schema_;
std::string name_;
std::unique_ptr<Index> index_;
index_oid_t index_oid_;
std::string table_name_;
const size_t key_size_;

观察上面的 TableMetadata 会发现少了索引，IndexInfo 就表示了这个索引，而 Catalog 的作用就是实现 TableMetadata 与 IndexInfo 关联起来，真正实现完整的表。

Catalog (class)

1
2
3
4
5
6
7
8
9
10
11
12
/** tables_ : table identifiers -> table metadata. Note that tables_ owns all table metadata. */
std::unordered_map<table_oid_t, std::unique_ptr<TableMetadata>> tables_;
/** names_ : table names -> table identifiers */
std::unordered_map<std::string, table_oid_t> names_;
/** The next table identifier to be used. */
std::atomic<table_oid_t> next_table_oid_{0};
/** indexes_: index identifiers -> index metadata. Note that indexes_ owns all index metadata */
std::unordered_map<index_oid_t, std::unique_ptr<IndexInfo>> indexes_;
/** index_names_: table name -> index names -> index identifiers */
std::unordered_map<std::string, std::unordered_map<std::string, index_oid_t>> index_names_;
/** The next index identifier to be used */
std::atomic<index_oid_t> next_index_oid_{0};

通过给定的类成员就能够推断出 Catalog 是如何关联 TableMetadata 和 IndexInfo 以及使用表名称/索引表名称关联 TableMetadata/IndexInfo。

CreateTable

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

创建一个新表（初始化一个 TableMetadata），创建完新表就要在哈希表中关联起来 table_oid_t => TableMetadata, table_name => table_oid_t

GetTable

TableMetadata *GetTable(const std::string &table_name)

TableMetadata *GetTable(table_oid_t table_oid)

通过创造表时做的哈希映射实现即可，要注意的是如何从 std::unique<TableMetadata> 获得裸指针。

CreateIndex

1
2
3
4
5
6
7
8
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)

这里的 Index 是指的 BPlusTreeIndex（基类指针可以指向派生类）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class BPlusTreeIndex : public Index {
 public:
  BPlusTreeIndex(IndexMetadata *metadata, BufferPoolManager *buffer_pool_manager);

  void InsertEntry(const Tuple &key, RID rid, Transaction *transaction) override;

  void DeleteEntry(const Tuple &key, RID rid, Transaction *transaction) override;

  void ScanKey(const Tuple &key, std::vector<RID> *result, Transaction *transaction) override;

  INDEXITERATOR_TYPE GetBeginIterator();

  INDEXITERATOR_TYPE GetBeginIterator(const KeyType &key);

  INDEXITERATOR_TYPE GetEndIterator();

 protected:
  // comparator for key
  KeyComparator comparator_;
  // container
  BPlusTree<KeyType, ValueType, KeyComparator> container_;
};

可以看到 BPlusTreeIndex 是包含了一个 BPlusTree 。

GetIndex

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

IndexInfo *GetIndex(index_oid_t index_oid)

与 TableMetaData 的取法相同。

Task2 - Executors

SQL 语句在 Bustub 中的执行过程

Parser

SQL 语句通过 Parser 生成抽象语法树 AST (编译原理中的 AST)。

Binder

1
SELECT id FROM table1;

需要被绑定的是 id 与 table1 ，这两个会被绑定到对应的实体上（各种 C++ 中的类），这用 Bustub 就能理解这些标记了。

Planner

Binder 结束后，Planner 根据 Binder 生成的树生成一颗初步的查询计划树。

1
SELECT R.id, S.cdate From R JOIN S ON R.id = S.id WHERE S.value > 100;

生产的查询计划树为 ：

查询计划

叶子节点的结果会返回给他的父节点，最后由根结点得到最终结果。

Optimizer

对 Planner 生成的查询计划进行修改优化，生成最终的查询计划。

  • Rule-based ，根据已有的规则进行修改优化，不需要知道实际的数据。

  • Cost-based ，先读取数据并通过统计学模型来计算不同形式但等价的查询计划的 cost，选取 cost 最小的作为最终的查询计划。

Bustub 采用了第一种。

关于 Rule-based 的一些例子：

Predicate Pushdown

谓词下放

尽可能早的进行过滤操作，这样想上层节点返回的行会更少。

Projection Pushdown

向上层节点返回尽可能少的列，减少无效数据的开销。

Unnecessary Predicate

1
SELECT * FROM A WHERE 1 = 0;

删除不必要的谓词，

1
SELECT * FROM A;

Join Elimination

1
SELECT A1.* FROM A AS A1 JOIN A AS A2 ON A1.id = A2.id;

删除不必要的连表，

1
SELECT * FROM A;

Ignoring Projection

1
SELECT * FROM A AS A1 WHERE EXISTS(SELECT val FROM A AS A2 WHERE A1.id = A2.id);

删除不必要的投影，

1
SELECT * FROM A;

Merging Predicate

1
SELECT * FROM A WHERE val BETWEEN 1 AND 100 OR val BETWEEN 50 AND 150;

合并谓词，

1
SELECT * FROM A WHERE val BETWEEN 1 AND 150;

Executor

在生成最终的查询计划后，就可以生成真正的可执行的算子了，要实现的就是这部分的内容。

算子的执行模型分为三类：Iterator、Materialization、Vectorization Model。

Bustub 使用 Iterator Model。

火山模型/迭代器模型 (Iterator/Volcano/Pipeline Model)

火山模型/迭代器模型

每次执行 Next() 都会返回一个元组或空标记。父节点的 Next() 通过调用子节点的 Next() 来获取子节点的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 父节点的 Next
bool Next(Tuple *tuple) {
  if(child.Next(tuple)) {
    
    ...
      
    return true;
  }
  return false; // 算子不能在返回值，算子执行结束了。
}

// 叶子节点 例如：全表扫描
bool Next(Tuple *tuple) {
  if(TableIterator != TableEnd) {
    Predicate(tuple); // 谓词
    return true;
  }
  return false; // 表遍历完了
}

从跟节点开始执行循环，每次都从叶子节点开始一层一层向上返回数据，直到跟节点，然后进行下一次循环。

这样做一次只调用一行数据，内存占用较小，但是函数的开销就会大一些，Bustub 中的 Next() 是虚函数。

物化模型 (Materialization Model)

物化模型

每次执行 Next() 会返回全部数据，算子会将要处理的数据全部处理后一起返回。

1
2
3
4
5
6
7
8
vector<Tuple> Next() {
  vector<Tuple> res;
  vector<Tuple> child_res = child.Next();
  for (auto tuple : child_res) {
    ...
  }
  return res;
}

这种模型消耗的内存会更大，适合处理要返回的数据很少的情景。

向量模型 (Vectorization Model)

向量模型

是上面两种模型的中和，调用一次 Next() 返回一批数据，可以使用 SIMD 进行优化。