MIT6.830 Database Systems 2021 Lab2

前情提要

放寒假之前，决心寒假通关所有lab，没想到回家以后直接开摆，现在坐在学校的图书馆里写下这份实验报告，一个lab写了一个假期，真有你的，下次再也不拖了…

Lab Overview

在lab2里，我们主要完成数据库里常见运算符的底层算子的实现，例如Filter,Join,insert,delete,group等操作。对于insert和delete操作，我们将在HeapFile, HeapPage和BufferPool三个层面完成对数据的更新，保证数据库的一致性。最后，我们还会完成对缓冲池的管理，将脏页刷新到磁盘里，淘汰多余的数据页。

实验开始

Exercise 1

• Filter:筛选并返回符合条件的元组。其实就是过滤操作。
• Join：将两个数据表里符合条件的元组连接成新的元组。

1.1 Predicate

SimpleDB里将判断元组满足某一条件的过程封装为Predicate类，其中通过枚举类定义了一系列操作，例如EQUALS，GREATER_THAN，LESS_THAN等等。构造方法里，我们需要初始化与传入元组比较的下标值，具体的运算操作，元组与之比较的值。filter方法判断是否满足某一条件，根据文档注释可以通过Field的compare方法实现。

1.2 JoinPredicate

JoinPredicate在join的过程中提供判断，所以在构造方法里和Predicate不同的是，我们需要初始化join过程中两个元组构成判断条件的field的索引，以及具体的运算操作。

1.3 Filter

filter类相当于SQL里的select语句的具体实现。在这里，其实是对上面Predicate的简单封装，通过构造方法里传入的具体的predicate和对应元组的迭代器，过滤不符合条件的元组。具体实现通过fetchNext方法，遍历所有元组，筛选符合条件的元组。

1.4 Join

这一部分的难点在于fetchNext方法的实现，最简单的方式是两重循环(nested loops join)，外层循环遍历child1的所有元组，内层循环遍历child的所有元组，判断是否满足条件，如果满足条件就将二者merge，返回merge后的元组。需要注意的是，每次merge成功后，我们要标记child1迭代器的状态，只有不符合判定条件时，才会执行child1.next()操作。另外，当child2遍历结束，但child1还没有结束时，我们需要rewind``child2,同时标记child1的迭代器。

protected Tuple fetchNext() throws TransactionAbortedException, DbException {
        // some code goes here
        while (child1.hasNext() || child2.hasNext()) {
            if (isUpdate) tuple1 = child1.next();
            while (child2.hasNext()) {
                Tuple tuple2 = child2.next();
                if (p.filter(tuple1, tuple2)) {
                    Tuple tuple = new Tuple(TupleDesc.merge(tuple1.getTupleDesc(), tuple2.getTupleDesc()));
                    tuple.setRecordId(tuple1.getRecordId());
                    int len1 = tuple1.getTupleDesc().numFields(), len2 = tuple2.getTupleDesc().numFields();
                    int idx =0;
                    for (int i = 0; i < len1; i++, idx++) tuple.setField(idx, tuple1.getField(i));
                    for (int i = 0; i < len2; i++, idx++) tuple.setField(idx, tuple2.getField(i));
                    isUpdate = false;
                    return tuple;
                }
                isUpdate = true;
            }
            if (!child2.hasNext() && child1.hasNext()) {
                isUpdate = true;
                child2.rewind();
            }
        }
        return null;
    }
复制代码

Exercise 2

这一部分我们需要实现分组函数(Group by),以及支持一些基本的SQL算术运算-聚合函数(COUNT, SUM, AVG, MIN, MAX)。我们以(groupValue, aggregateValue)的形式返回聚合运算的结果，如果非分组，只用返回(aggregateValue)。

2.1 IntegerAggregator

IntegerAggregator类封装了对数据类型为INT_TYPE的数据的分组聚合运算操作。构造方法中，我们需要初始化以下参数：

• gbField:分组列的索引值，如果是非分组(NO_GROUPING)的话，则为-1
• fbFieldType:分组列的数据类型，如果为非分组，则为null
• aField:聚合列的索引值
• what：具体的算术运算操作

我们考虑用Map去维护分组聚合运算的结果，键为分组列对应的field,值为运算结果，如果是非分组运算，我们就将键置为null进行存储。这里值得一提的是，一开始我使用ConcurrentHashMap存储结果，后来过系统测试的时候抛空指针异常，debug后发现ConcurrentHashMap不支持key为null的存储，否则会抛出空指针异常，之后换成HashMap顺利通过测试。具体实现的时候，首先根据是否分组进行分类，然后进行简单的算术运算，更新维护Map的状态。最后的迭代器，我们可以简单维护一个数据类型为Tuple的list，之后遍历Map,获取键值对，将结果添加到list中，最后调用lab1中实现的TupleIterator并返回就可以。

2.2 StringAggregator

StringAggregator类封装了对数据类型为STRING_TYPE的数据的分组聚合运算操作。具体实现过程和上面类似，由于只支持COUNT操作，所以比较容易实现。

2.3 Aggregate

Aggregate类可以通过对上述IntegerAggregator和StringAggregator的简单调用实现。这里简单提一下自己当时无意间写下的几个bug，首先，获取分组列的数据类型时，要先考虑是否分组，否则如果不分组，则会抛出数组索引越界异常

gbFieldType = (gField == Aggregator.NO_GROUPING ? null : child.getTupleDesc().getFieldType(gfield));
复制代码

另外，对于OpIterator的实例，一定要先open再使用。其实，这两个bug在实验文档注释里都有提及，所以一定要认真阅读文档，理清思路之后，再动手写代码，避免这些低级的错误。

Exercise 3

• Removing tuples：根据tuple的RecordId,我们可以很容易地定位tuple所在的数据页，删除tuple的同时修改page header的状态。
• Adding tuples：首先，我们需要找到空页插入元组，如果没有足够的数据页，那么我们创建新的数据页，并把它追加到磁盘中。

3.1 HeapPage

将指定的tuple插入到数据页中或者从中删除，这一部分的代码实现起来比较直接，记得更新page header的状态，位运算的简单运用。

    private void markSlotUsed(int i, boolean value) {
        // some code goes here
        // not necessary for lab1
        int byteIndex = i / 8;
        int bitIndex = i % 8;
        if (value) {
            this.header[byteIndex] |= (1 << bitIndex);
        } else {
            this.header[byteIndex] ^= (1 << bitIndex);
        }
    }
复制代码

3.2 HeapFile

将指定的tuple插入HeapFile中，遍历每一页heappage,这里需要通过BufferPool去获取，如果存在空的槽，直接插入，并将被修改的页返回。如果没有空页，那么创建一个空页，将tuple插入，然后记得将page写入磁盘并返回。删除操作类似。

3.3 BufferPool

缓冲池里添加和删除tuple的操作可以基于上述两个类的简单封装完成，当添加或删除tuple后，对应的page就变成脏页，需要对其进行标记，同时将脏页刷新到缓存中，之后在适当的时机将脏页写入磁盘。

    public void insertTuple(TransactionId tid, int tableId, Tuple t)
        throws DbException, IOException, TransactionAbortedException {
        // some code goes here
        // not necessary for lab1
        DbFile dbFile = Database.getCatalog().getDatabaseFile(tableId);
        List<Page> dirtyPages = dbFile.insertTuple(tid, t);
        PageId pid = t.getRecordId().getPageId();
        for (Page dirtyPage : dirtyPages) {
            if (pageBuffer.containsKey(dirtyPage.getId())) {
                dirtyPage.markDirty(true, tid);
                lruNode dirtyNode = bufferPoolManager.pageIdlruNodeMap.get(dirtyPage.getId());
                bufferPoolManager.moveToHead(dirtyNode);
            } else {
                dirtyPage.markDirty(true, tid);
                if (bufferPoolManager.getSize() == numPages) { evictPage(); }
                bufferPoolManager.put(new lruNode(dirtyPage));
            }
        }
    }
复制代码

Exercise 4

Insert和Delete类统计插入和删除的记录的数量，如果被调用多次的话，则返回null，我们可以通过维护一个布尔类型的变量done进行检验。

Exercise 5

本实验的最后，我们要实现页面替换算法管理缓冲区内存，同时完成将脏页刷入磁盘的操作。这里我选择使用LRU算法完成页面管理，最简单的实现方式是为缓冲池里每个页面维护一个时间戳，每次对页面进行读写时，更新时间戳，当缓冲区容量达到上限时，淘汰时间戳最小的页面，即最久没有被访问的页面。另外一种比较常见的实现方式是通过链表和哈希表完成对缓冲区管理，我通过手写双链表和HashMap的方式实现，同时我定义了一个lruManager类，封装添加删除更新节点的操作。具体定义和接口如下：

    private final class lruNode {
        Page page;
        lruNode prev;
        lruNode next;
​
        public lruNode(Page page) {
            this.page = page;
        }
    }
    private final class lruManager {
        lruNode dummyHead;
        lruNode dummyTail;
        int capacity;
        int size;
        Map<PageId, lruNode> pageIdlruNodeMap;
​
        public lruManager(int capacity) {
            this.capacity = capacity;
            this.size = 0;
            pageIdlruNodeMap = new ConcurrentHashMap<>();
            dummyHead = new lruNode(null);
            dummyTail = new lruNode(null);
            dummyHead.next = dummyTail;
            dummyTail.prev = dummyHead;
        }
        
        public void put(lruNode node) {...}
​
        public void delete(lruNode node) {...}
​
        public lruNode getTail() {...}
        
​
        public void addToHead(lruNode node) {...}
​
        public int getSize() {...}
​
        public void moveToHead(lruNode node) {
            removeNode(node);
            addToHead(node);
        }
​
        public void removeNode(lruNode node) {...}
    }
复制代码

之后，discardPage和evictPage方法通过对上述lruManager进行调用即可完成，flushPage注意将数据页刷盘并且更改Dirty状态，并不会从缓冲区内淘汰。另外一个需要注意的地方是evictPage时，需要将脏页先刷新到磁盘里，然后再将脏页从缓冲区中淘汰，避免出现数据不一致的问题。

总结

Lab2整体来说还是比较有难度，整个实验写下来，加深了对数据库常见操作的理解，尤其是分组聚合运算。实验配套的系统测试还是非常强劲的，发现了不少平时没有考虑到的问题(corner case)，debug的过程非常酸爽，但我还是比较享受发现问题，定位问题，解决问题，最后pass test的过程(其实就是面向测试用例编程嘛，有被自己菜到)。最后，希望自己坚持到底，尝试去把推荐的paper都读一读，学习到更多有关DB的知识，早日通关，有所收获。