MIT 6.830 实现简易数据库 lab1

Posted by zsh on July 7, 2022

前言

最近在学习CMU-15-445数据库课程,想着能跟着课程实现一个简易数据库。但是CMU课程附带的Project是用c++写的,而我单纯只想学习数据库,不想为了写Project 去学c++。正好发现MIT-6.830内容跟CMU的课程内容很相近,同时附带的Project是用java实现的,于是就决定看CMU-15-445课程,同时实现MIT-6.830,同时 在这里记录一下MIT6.830的实现思路。

exercise 1

SimpleDB通过Tuple类表示数据,TupleDesc类表示数据的Schema,Field接口表示具体字段,SimpleDB目前只支持Int和String两种类型的字段,Type枚举表示 字段类型,实验1需要实现

  • src/java/simpledb/storage/TupleDesc.java
  • src/java/simpledb/storage/Tuple.java

两个类,同时通过TupleTest和TupleDescTest。第一个实验非常简单,只需要在TupleDesc里添加表示字段类型和字段名称的list,然后在Tuple类里添加List 就可以了。

exercise 2

Catalog可以看成MySQL里的具体数据库,在Catalog里有table集合,因此需要定义一个Table类,结构如下

1
2
3
4
5
6
7
8
9
10
11
12
13
public static class Table {
    int id;
    String name;
    DbFile file;
    String pkeyField;

    public Table(int id, String name, DbFile file, String pkeyField) {
        this.id = id;
        this.name = name;
        this.file = file;
        this.pkeyField = pkeyField;
    }
}

实验2需要实现

  • src/java/simpledb/common/Catalog.java

并通过CatalogTest

exercise 3

我们知道数据库的数据最终是存放在硬盘里的,而且跟操作系统管理内存一样都有分页机制。而一页数据通常都比较小(4kb-64kb不等)读取硬盘数据的延迟又很高, 因此就需要在内存中建立BufferPool,在读取一页数据时将临近几页数据一次性读取并放入,通过这种方式可以提升数据读取的性能。实验3需要实现

  • src/java/simpledb/storage/BufferPool.java

同时需要注意,BufferPool中大部分方法不需要在lab1中完成,同时也没有提供测试

exercise 4

实验3提到了Page,而实验4就需要实现Page的读取操作。我们知道Page是逻辑上的划分,真正存储在硬盘上的是一个个文件,就是HeapFile。一个HeapFile里有 HeapPage的集合, HeapPage的逻辑结构如下:

  • 开头有固定数量的bit,用来表示对应位置有无Tuple,此位置定义为Header
  • Header后面是一行行Tuple

实验4给了几个公式,我们需要实现这几个公式,用来计算一个HeapPage能容纳多少Tuple,以及Header大小

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 计算一个page里能放多少tuple, 单位是bit, page的bit / 单个tuple所需的bit + 1
 */
private int getNumTuples() {
    return (int) Math.floor((BufferPool.getPageSize() * 8.0) / (td.getSize() * 8 + 1.0));
}

/**
 * 计算page的header占用byte数,一个tuple占一位,因此 / 8 = byte数
 */
private int getHeaderSize() {
    return (int) Math.ceil(getNumTuples() / 8.0);
}

如果对于HeapPage的逻辑结构不太清楚,可以去看HeapFileEncoder类,该类提供了如何把Tuple转换成HeapPage的方法。实验4需要实现

  • src/java/simpledb/storage/HeapPageId.java
  • src/java/simpledb/storage/RecordId.java
  • src/java/simpledb/storage/HeapPage.java

并通过HeapPageIdTest, RecordIDTest, HeapPageReadTest测试

exercise 5

HeapPage是以逻辑结构的形式存储在HeapFile,因此要想读取Tuple,首先需要读取HeapPage,HeapPage有自己的编号,通过编号计算出在文件中的offset, 然后用RandomAccessFile读取数据,构建HeapPage。同时还需要实现一个迭代器,用来读取HeapFile中所有HeapPage的Tuple。这里要注意的是不能一次性把整个 HeapFile加载到内存中,不然会造成OOM。如果对于迭代器没有思路,可以参考已经给出的BTreeFileIterator。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 从file中读取指定page,需要计算offset,使用RandomAccessFile读取,offset=pageNumber * pageSize
 * */
public Page readPage(PageId pid) {
    int offset = pid.getPageNumber() * BufferPool.getPageSize();
    try (RandomAccessFile randomAccessFile = new RandomAccessFile(file, "r")) {
        randomAccessFile.seek(offset);
        byte[] bytes = new byte[BufferPool.getPageSize()];
        randomAccessFile.read(bytes);
        return new HeapPage((HeapPageId) pid, bytes);
    } catch (IOException e) {
        e.printStackTrace();
    }
    return null;
}

实验5需要实现

  • src/java/simpledb/storage/HeapFile.java

并通过HeapFileReadTest

exercise 6

实现SeqScan操作,其实就是遍历整个HeapFile的Tuple,都是包装前面实验写好的iterator。实验6需要实现

  • src/java/simpledb/execution/SeqScan.java

并通过systemtest/ScanTest