MIT 6.830 数据库实验 Lab 2 实验报告

发表于 2022-11-20 更新于 2022-11-29 分类于后端，数据库阅读次数：本文字数： 3.2k 阅读时长 ≈ 6 分钟

摘要

书接上回，本次 lab 的实验目标是实现数据库的各种操作符，包含 filter、join、aggregate、insert、delete 等。此外，还需要实现第一节没有实现的页面调度算法，处理 BufferPool 满时的页面调度，此外还有脏页面写回等操作。

下面将按 Exercise 的顺序一个个进行介绍。

Exercise

OpIterator & Operator

在实现之前，先介绍下操作符的规范接口。基础接口是 OpIterator，它定义了以下方法，本质上是保存了一张临时的表，可以通过 getTupleDesc() 获取表的描述符，通过反复调用 next() 遍历表的每一行。SeqScan 操作符直接实现了 OpIteraotr 接口，根据表的 id 创建这样的迭代器，作为后续操作符的参数。

void open(); // 开启迭代器
boolean hasNext(); // 是否有下一个元素
Tuple next(); // 获取下一个元组
void rewind(); // 迭代器指针重置
TupleDesc getTupleDesc(); // 获取表的描述符
void close(); // 关闭迭代器

操作符规范是一个抽象类 Operator，实现了 OpIterator 的 open、close、hasnext、next 方法，避免逻辑冗余。抽象类中包含以下为实现的方法：

abstract Tuple fetchNext() // 获取下一个元组，不存在则返回null
TupleDesc getTupleDesc(); // 获取表的描述符
OpIterator[] getChildren(); // 获取操作符的参数
void setChildren(OpIterator[] children); // 设置操作符的参数

可以看出，一个操作符持有一个或多个的临时表 OpIterator 参数，本身的 fetchNext 则是用于迭代该操作符的结果。换而言之，Operator 是持有 OpIteraotr[] 的 OpIterator，进而实现了操作符的嵌套，操作符一般只接收一个表参数，除了 join。

Filter & Join

首先要实现的是 filter 和 join 操作，均继承实现了 Operator 的抽象类，分别对应 SQL 语法中的 where 从句和 join 从句。filter 操作通过 Predicate 对象去判断每行是否存在于最终的结果中，内部持有一个 OpIteraotr 参数代表要遍历的表。要做的事情也很简单，fetchNext 的时候一直迭代表直到找到一条满足条件的记录，返回即可。

Join 操作与之类似，需要先实现 JoinPredicate 用于匹配一对记录是否存在于最终的结果中，fetchNext 操作则相对复杂。join 遍历的实际是两张表的笛卡尔积，需要内部去维护更新这个笛卡尔积的索引，找到符合条件的一对记录后，还要将它们拼接返回。

Aggregate

在 SimpleDB 中，仅考虑对单个字段分组、聚合。根据聚合字段在类型，可以分为整形聚合和字符串型聚合两类。整形聚合支持 max、min、avg 等数值操作，而字符串型聚合只支持 count 操作。两种聚合分别定义在 IntegerAggregator 和 StringAggregator 操作符中，实现了抽象的 Aggregator 接口（而不是 OpIteraotr），包含以下方法：

1 2	void mergeTupleIntoGroup(Tuple tup); // 将新的元组加入到分组结果中 OpIterator iterator(); // 返回聚合结果的迭代器

可以看到，聚合类是通过 mergeTupleIntoGroup 方法逐条记录地去进行分组，再通过 iterator() 返回结果迭代器，而不是像其他的操作符那样，初始化时就具有表作为输入。我的理解是，由于聚合操作的特点，本身就是要先读取完整个表才能得到分组和聚合结果。如果聚合操作实现操作符接口，也只能是内部再维护一个 OpIterator 结果，所以不如直接解耦这部分逻辑。

两个聚合类的内部实现其实很简单，依赖一个 <GroupValue, AggregateValue> 的 HashMap，对于新的元组，如果不存在分组值，就新建这个分组。这个 HashMap 可以转换成一个 Iterator<Tuple>，核心问题是怎么把这个转成 OpIterator。因为 Java 自带的 Iterator 和 Stream 均不支持重用，我个人构建了一个 Supplier<Stream<Tuple>>，在每次 rewind 的时候获取一个新的 Iterator<Tuple>，这个 Supplier 再通过一个适配器转换成 OpIterator。

HeapFile

这里需要支持 HeapFile 的修改表操作，即增删元组，需要从 HeapPage, HeapFile, BufferPool 三层由底向上地支持增删功能。之前说过，HeapFile 由很多个 HeapPage 组成，通过 BufferPool 统一读取页面进行缓存。在增删元组的时候，HeapFile 需要找到最后一个有空 slot 的页面，插入元组并更新其 RecordId，还需要将页面标记为 “脏” 的，因为页面发生了改变，丢弃前必须写回磁盘。删除元组时，HeapFile 根据其 RecordId 直接定位页面，将对应 slot 标记为空，将页面标记为脏即可。而 HeapPage 则负责在当前页面完成增删。BufferPool 的插入和删除元组操作，则要先通过 Catalog 定位到 HeapFile，在获得修改后脏页面后需要更新缓存中的页面，如果之前没有标记脏位，这里也需要标记。

上面是简单的逻辑介绍，在实现的时候还有些细节可以处理。在插入页面时，找到有空 slot 的页面后，需要具体找到 slot 的位置。由于 bitmap 是以 byte[] 存储的，可以先找到不为 - 1 的 byte，再在 byte 内找到标识位不为 1 的索引。-1 代表着一个全为 1 的有符号数，对于任意长度的有符号数均是如此。因为在负数的补码实现下，最高位的权重是负的，其余位的权重是正的，\(-2^n+\sum_{i=0}^{n-1}2^i=-1\)。在插入页面时，若不存在有空 slot 的页面，需要新建页面，完成插入后最好将页面写回文件，不然 numPages() 方法的返回结果会错误。

Insert & delete

在实现了 HeapFile 的插入删除操作后，这两个操作符也不难了。值得注意的是，这两个操作只需要返回一个整数元组，代表受影响的元组数量。因此 fetchNext 方法只应该返回一个 tuple，之后就返回 null。

Page eviction

最后，需要完成 BufferPool 的页面调度算法，也就是页面逐出的逻辑。操作系统上的页面调度算法有很多，先进先出，时钟算法，LRU（最近未使用）等。最常用的算法就是 LRU，因为它的性能是最好的。LRU 主要包含两个操作，获取页面和逐出页面。在获取页面时，先判断页面是否在缓存区中，命中则直接返回，未命中则加载至缓存区中。逐出页面时，删除最近最少使用的页面。为了达到 \(O(1)\) 的获取页面和逐出页面的复杂度，需要使用一个 HashMap 和一个链表，HashMap 存储链表中的指针，用于查询是否在缓存区中。链表按最近使用的顺序存储页面，在页面使用后或者需要删除时完成高效地移动和删除。具体可以参考 146. LRU 缓存 - 力扣（LeetCode）。

除了页面逐出操作外，还需要实现 flushPage 方法将脏页面写回磁盘，但不逐出，以及 discardPage 将页面丢弃，不将页面写回磁盘。通过调用 HeapFile.writePage 以及直接操作 BufferPool 即可实现这两种操作。