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的类,比如RecordIdPageId等。整体的结构可以用下图表示

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天