MIT 6.5830(6.830) Lab1

简介

MIT 6.580也就是之前的6.830，课程名称为Database System，可以访问[课程主页](6.5830/6.5831: Database Systems (formerly 6.814/6.830) (mit.edu))和[Lab首页](MIT-DB-Class/simple-db-hw-2022 (github.com))查看更多信息。这门课的Lab的主要任务就是实现一个简单的DBMS，这里称为SimpleDB，整体代码框架已经给出了，我们只需要补充其中缺失的部分即可，其中需要我们补写的函数也用TODO注释给出// TODO: some code goes here。整个项目使用Java编写，而与之相比CMU 15-445/645使用C++实现，所以我感觉Java的这个对我来说更简单一些。

整个实验具有5个Lab，它们分别需要完成以下的任务

Lab 1: SimpleDB 整体基础架构的实现， 包括从磁盘读取表到内存、实现缓冲池等。

Lab 2: SimpleDB Operators 实现SQL语句中的具体操作，比如连接、聚合函数、插入删除等

Lab 3: Query Optimization 实现查询优化

Lab 4: SimpleDB Transactions 实现事务

Lab 5: B+ Tree Index B+树索引

Lab 6: Rollback and Recovery 回滚与恢复

从整个lab来看，它实现了一个最小的却又基本具有完备功能的DBMS，对于我个人来说，之前接触过实现DBMS的项目就是OceanBase举办的数据库比赛，当时开发的是他们的miniob，也算是具有一定的经验，但这两个数据库的结构还是不同的，也算是一个新的挑战。

Get Start

关于如何拉取与进行开发，在Lab官网中已经有了非常详细的介绍。项目需要使用Java实现，推荐使用JDK 11。这个实验提供了非常详尽的单元测试，每一个模块完成之后都可以进行测试，这是我认为非常好的一点。

Lab1分析

Lab1整体的代码实现其实非常简单，这个实验的目的也就是为了能够让人弄清该DBMS的整体架构，它包括了以下的过程。数据库从磁盘中读取文件到HeapFile并对其进行分页产生HeapPage，在这个过程中，还会页载入缓冲池BufferPool。在分页之后。需要在每一页之中填充数据，即每一行的元组数据Tuple和元组描述也就是表头TupleDesc 。同时，对于加载进来的表，还需要将他和schema信息保存在Catalog之中。除了这些类之外，还需要实现一些表示唯一ID的类，比如RecordId和PageId等。整体的结构可以用下图表示

img

Exercises

Lab1之中共分出了6个小的实现练习，这里只放部分重要代码。

Exercise 1 Fields and Tuples

这个就是主要实现元组与表头的定义，TupleDesc中包含了对列名和类型的定义，而Tuple之中则包含了Field记录。这个练习非常简单，只需实现其构造函数和一些get(),set(),toString(),equals()方法即可，这里就不贴代码了。

Exercise 2 Catalog

在Catalog目录类之中，需要存储当前加载的所有表的信息，用于查询。这里会根据表明和表的ID进行频繁的数据查询，所以为了效率问题，在存储时选择了两个哈希Map进行存储，可以分别使用Name和Id进行检索，同时使用一个内部类储存信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static class TableItem implements Serializable {
    private static final long serialVersionUID = 1L;
    private final String tableName;
    private final DbFile file;
    private final String pkeyField;

    public TableItem(String tableName, DbFile file, String pkeyField) {
        this.tableName = tableName;
        this.file = file;
        this.pkeyField = pkeyField;
    }
}
private Map<Integer, TableItem> catalog;
private Map<String, Integer> nameMapId;

在添加表时，根据实验指引，当名字相同是需要覆盖旧的， 这一点使用HashMap可以自然实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void addTable(DbFile file, String name, String pkeyField) {
       if (name == null || name.length() == 0) {
           String randName = (UUID.randomUUID()).toString();
           this.nameMapId.put(randName, file.getId());
           this.catalog.put(file.getId(), new TableItem(randName, file, pkeyField));
       }
       else {
           if (this.nameMapId.containsKey(name)) {
               this.catalog.remove(this.nameMapId.get(name));
           }
           this.nameMapId.put(name, file.getId());
           this.catalog.put(file.getId(), new TableItem(name, file, pkeyField));
       }
       // TODO: some code goes here
   }

Exercise 3 BufferPool

在这个系统中，缓冲池主要用来缓存从磁盘中读出来的最近使用的页，这里同样使用一个Map来作为存储结构，在Lab1中，仅需要实现它的getPage()方法。具体的话，当缓冲池中有这一页时直接返回，没有这一页时需要从磁盘进行加载，可以使用表ID和页ID从目录中进行查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public Page getPage(TransactionId tid, PageId pid, Permissions perm)
        throws TransactionAbortedException, DbException {
    // TODO: some code goes here
    if (pages.containsKey(pid.hashCode())) {
        return pages.get(pid.hashCode());
    }
    if (pages.size() == this.maxSize) {
        throw new DbException("");
    }
    Catalog catalog = Database.getCatalog();

    Page page = catalog.getDatabaseFile(pid.getTableId()).readPage(pid);
    if (page != null) {
        pages.put(pid.hashCode(), page);
        return page;
    }

    throw new DbException("");
}

Exercise 4 HeapFile access method

一个HeapFile对象由一组HeapPage组成，其中每一页的页大小由BufferPool.getPageSize()获得，而每一页由一系列的Tuple和表示是否有效的bitmapHeader组成，其中每一页有多少个Tuple和需要几个字节的Header可由如下公式计算出。其中注意每一字节的的顺序Header由最低位开始，如Header中第一个字节为00000010则表示第二个Tuple是有效的。一共需要实现HeapPageId,RecordId,HeapFile三个类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//HeapFile.java
	private int getNumTuples() {
        // TODO: some code goes here
        return (int) Math.floor((BufferPool.getPageSize() * 8) / (this.td.getSize() * 8 + 1.0));
    }
    private int getHeaderSize() {
        // TODO: some code goes here
        return (int) Math.ceil(getNumTuples() / 8.0);
    }
    public int getNumUnusedSlots() {
        // TODO: some code goes here
        int cnt = 0;
        for (int i = 0; i < getNumTuples(); i++) {
            if (!isSlotUsed(i)) cnt ++;
        }
        return cnt;
    }
    public boolean isSlotUsed(int i) {
        // TODO: some code goes here
        int index = i / 8;
        int offset = i % 8;
        return ((this.header[index] >> offset) & 1) == 1;
    }
    public Iterator<Tuple> iterator() {
        // TODO: some code goes here
        List<Tuple> list = new ArrayList<>();
        for (int i = 0; i < getNumTuples(); i++) {
            if (isSlotUsed(i)) list.add(tuples[i]);
        }
        return list.iterator();
    }

Exercise 5 HeapFile

这个练习依旧是补全HeapFile，这里需要实现从磁盘文件中加载并填充页，然后还需返回所有Tuple的迭代器。同时在迭代器之中对BufferPool进行查询和填充。其中需要实现readPage()函数，在实现时需要根据给定的PageId进行从指定位置开始的随机读取，而在实现迭代器时，我这里使用了一个内部类实现DbFileIterator接口来帮助实现。其中numPages()方法用于返回当前HeapFile中的页数，这里牵扯到是使用ceil还是floor，我看网上使用的都是floor,但我感觉应该使用ceil，在Lab1中无论使用哪一个都能通过测试，等之后的实验用到时再来填坑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
   public int numPages() {
       // TODO: some code goes here
       return (int) Math.ceil(this.file.length() * 1.0 / BufferPool.getPageSize());
   }
   public Page readPage(PageId pid) {
       // TODO: some code goes here
       int tableId = pid.getTableId();
       int pageNumber = pid.getPageNumber();
       RandomAccessFile f = null;
       try {
           f = new RandomAccessFile(this.file, "r");
           if ((pageNumber + 1) * BufferPool.getPageSize() > f.length()) {
               f.close();
               throw new IllegalArgumentException("");
           }
           byte [] data = new byte[BufferPool.getPageSize()];
           f.seek(pageNumber * BufferPool.getPageSize());
           int read = f.read(data, 0, BufferPool.getPageSize());
           if (read != BufferPool.getPageSize()) {
               f.close();
               throw new IllegalArgumentException("");
           }
           return new HeapPage(new HeapPageId(tableId, pageNumber), data);
       } catch (IOException e) {
           e.printStackTrace();
       } finally {
           try {
               f.close();
           } catch (IOException e) {
               e.printStackTrace();
           }
       }
       return null;
   }
public DbFileIterator iterator(TransactionId tid) {
       // TODO: some code goes here
       return new HeapFileIterator(this, tid);
   }
   private static class HeapFileIterator implements DbFileIterator {
       private HeapFile heapFile;
       private Iterator<Tuple> iterator;
       private int curPage;
       private TransactionId tid;

       public HeapFileIterator(HeapFile heapFile, TransactionId tid) {
           this.heapFile = heapFile;
           this.tid = tid;
       }

       @Override
       public void open() throws DbException, TransactionAbortedException {
           this.curPage = 0;
           this.iterator = getPageIter();
       }
       public Iterator<Tuple> getPageIter() throws TransactionAbortedException, DbException {
           if (this.curPage >= 0 && this.curPage < heapFile.numPages()) {
               HeapPage page = (HeapPage) Database.getBufferPool().getPage
                       (this.tid, new HeapPageId(heapFile.getId(), this.curPage), Permissions.READ_ONLY);
               return page.iterator();
           }
           return null;
       }
       @Override
       public boolean hasNext() throws DbException, TransactionAbortedException {
           if (iterator == null) return false;
           if (!iterator.hasNext()) {
               if (this.curPage == heapFile.numPages() - 1) return false;
               this.curPage ++;
               iterator = getPageIter();
               if (iterator == null) return false;
               return iterator.hasNext();
           }
           return true;
       }

       @Override
       public Tuple next() throws DbException, TransactionAbortedException, NoSuchElementException {
           if (iterator == null || !iterator.hasNext()) {
               throw new NoSuchElementException();
           }
           return iterator.next();
       }

       @Override
       public void rewind() throws DbException, TransactionAbortedException {
           this.close();
           this.open();
       }

       @Override
       public void close() {
           this.iterator = null;
       }
   }

Exercise 6 Operators

在SimpleDB中所有的操作operators对象都需要实现DbIterator，它整个将会以一个树形的模式运作，通过将较低级别的运算符传递到较高级别的运算符的构造函数中，将运算符连接到一个执行计划中。在计划的顶部，与SimpleDB交互的程序只需在根运算符上调用getNext（）；然后，该运算符对其子级调用getNext（），依此类推，直到调用调用到叶运算符。它们从磁盘获取元组并将其传递到树（作为getNext（）的返回参数）；元组以这种方式向上传播计划，直到它们在根处被输出，或者被计划中的另一个运算符组合或拒绝。在Lab1中，只需实现一个简单的操作SeqScan，即按顺序的将元组打印出来，这里还会有一个别名选项，需要将它加到输出的TupleDesc中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public TupleDesc getTupleDesc() {
    // TODO: some code goes here
    TupleDesc tupleDesc = Database.getCatalog().getTupleDesc(this.tableId);
    if (tableAlias == null || tableAlias.length() == 0) return tupleDesc;
    Iterator<TupleDesc.TDItem> it = tupleDesc.iterator();
    Type[] typeAr = new Type[tupleDesc.numFields()];
    String[] fieldAr = new String[tupleDesc.numFields()];
    int i = 0;
    while (it.hasNext()) {
        TupleDesc.TDItem next = it.next();
        typeAr[i] = next.fieldType;
        fieldAr[i] = this.tableAlias + "." + next.fieldName;
        i ++;
    }
    return new TupleDesc(typeAr, fieldAr);
}
public void open() throws DbException, TransactionAbortedException {
    // TODO: some code goes here
    this.iterator = Database.getCatalog().getDatabaseFile(this.tableId).iterator(tid);
    this.iterator.open();
}
public boolean hasNext() throws TransactionAbortedException, DbException {
    // TODO: some code goes here
    return iterator.hasNext();
}

public Tuple next() throws NoSuchElementException,
        TransactionAbortedException, DbException {
    // TODO: some code goes here
    if (!hasNext()) throw new NoSuchElementException();
    return iterator.next();
}

public void close() {
    // TODO: some code goes here
    this.iterator = null;
}

public void rewind() throws DbException, NoSuchElementException,
        TransactionAbortedException {
    // TODO: some code goes here
    this.iterator.rewind();
}

测试

在每一个Exercise做完之后，实验都提供有测试文件，可以使用ant进行测试，我这里也是通过了所有测试，按照顺序分别为

1
2
3
4
5
6
7
ant runtest -Dtest=TupleTest
				   TupleDescTest
				   CatalogTest
				   HeapPageIdTest
				   RecordIdTest
				   HeapPageReadTest
ant runsystest -Dtest=ScanTest

时间记录

开始：2022.11.25

结束：2022.11.25

耗费：1天