simpledb-lab1

2022秋MIT6.830lab1实验报告

在该实验中我们可以实现一个基础的database

• what we will do in this lab? Tuple、TupleDesc、Catalog and so on
• Remember what we dont do - transaction, locking, and recovery

exercise1

在exercise1中我们需要实现Tuple和TupleDesc

Tuple: 指的是表中的一行数据，在实验中是由fields组成的，field指的是元数据？大概这么理解，实验中包括了int和string两种类型
TupleDesc: 指的是一个表的行描述符，包括了字段名字和类型

可以看到Tuple类中有对TupleDesc类的引用，因此我们先实现TupleDesc

在TupleDesc中已经帮我们实现了hepler class，我们使用一个collection操作TDItem即可

在Tuple这个类中，我们只需要使用Colletion操作Field即可

Test Pass:

总体而言比较easy

exercise2

exercise2要求我们实现catalog

catalog就是数据库中用于索引一个表的目录，主要包括了该表的dbfile即磁盘存储，name即表名，pk即主键值。这里需要注意的是dbfile中的几个方法，getId()获取该表的唯一标识，getTd()获取该表描述符，这些方法在本次实验中会实现。

我们可以用一个map结构存储表，这里可以建立一个静态内部类帮我我们存储表相关信息

private static class Table {
    public DbFile file;
    public String pkeyField;

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

}

Map<String, Table> tables;

其余方法按照hint实现即可

exercise3

要求我们实现BufferPool的getPage方法

首先我们需要理解BufferPool，在数据库中所有对数据的操作是基于BufferPool的，BufferPool是存放在内存中的，如果直接对磁盘中的数据进行操作IO消耗太大，因此我们可以理解为BufferPool提供了一个全局访问点，而在BufferPool中数据是以页的形式存储的，因此我们需要实现getPage方法提供获取数据页的接口

final Map<PageId, Page> pages;

public Page getPage(TransactionId tid, PageId pid, Permissions perm)
        throws TransactionAbortedException, DbException {
    // hint: use DbFile.readPage() to access Page of a DbFile
   if (!pages.containsKey(pid)) {
        if (pages.size() == numPages) throw new DbException("Buffer Pool has not space!");
        DbFile file = Database.getCatalog().getDatabaseFile(pid.getTableId());
        pages.put(pid, file.readPage(pid));
   }
   return pages.get(pid);
}

在该实验中不要求实现BufferPool满后的缺页替换，只需要抛错即可。

PageId: 是一个page的唯一标识，可以通过PageId getTableId、getPageNumber

exercise4

需要我们实现HeapPage HeapPageId RecordId

首先我们可以梳理一下数据库中数据的存储结构了

• Field - 包括val和type，是最小的单元
• Tuple - 是Collection of Field，代表一行数据 Tuple通过RecordId唯一标识，RecordId包括了getPageId() 和 getTupeNo()两方法
• Page - 是Tuple的集合，同样的通过PageId唯一标识，包括了getTableId() 和 getPageNo() 两个方法
• DbFile - 是Page的集合，DbFile代表了一张表在磁盘上的存储，通过getId()唯一标识一张表，同时还存储了表的描述符Td

Page Dbfile都是以接口抽象，因为存在多种存储形式，但是Tuple、RecordId是这些不同存储形式相同的底层行数据，行标识因此不用接口抽象

依照上述整理我们一次实现RecordId

RecordId 内包含 PageId 和 tupleNo两个成员变量
HeapPageId 内包含 tableId 和 pageNo 两个成员变量

最后再实现HeapPage，这里HeapPage略微有点难度，这里给出我的实现

private int getNumTuples() {
    return (BufferPool.getPageSize() * 8) / (td.getSize() * 8 + 1);

}

private int getHeaderSize() {
    return (int)Math.ceil(getNumTuples() * 1.0 / 8);

}

// 这两个方法按照hint中的公式计算即可，注意getNumTuples这里需要化为double再除，否则会缺失
public boolean isSlotUsed(int i) {
    // byte数组八个tuple一组，每个tuple在它所在的byte下标位标记
    return ((header[i / 8] >> (i % 8)) & 1) == 1;
}

public Iterator<Tuple> iterator() {
    return new Iterator<Tuple>() {

        private int index = -1;

        @Override
        public boolean hasNext() {
            if (index + 1 < numSlots && isSlotUsed(index + 1)) {
                return true;
            }
            return false;
        }

        @Override
        public Tuple next() {
            return hasNext() ? tuples[++index] : null;
        }

        @Override
        public void remove() throws UnsupportedOperationException{
            throw new UnsupportedOperationException("no impletion of this method");
        }
    };
}

exercise5

要求实现HeapFile

HeapFile 即 DbFile的一种实现，对应一个数据表，那么包含File(磁盘上的File)、Td(磁盘描述符)

该实验的难点在于实现Iterator和ReadPage, 这里给出我的代码

 public Page readPage(PageId pid){
    // 偏移量
    long offset = pid.getPageNumber() * BufferPool.getPageSize();
    byte[] data = new byte[BufferPool.getPageSize()];
    Page page = null;
    // Raf 随机访问文件
    // Raf seek 跳过 offset字节数
    // Raf read 读满 data数组
    try (RandomAccessFile raf = new RandomAccessFile(f, "r")){
        raf.seek(offset);
        raf.read(data);
        page = new HeapPage((HeapPageId)pid, data);
    } catch(IOException e) {
        
    }
    return page;
}

private class HeapFileIterator implements DbFileIterator {

    private final TransactionId tid;
    private int pgNo = 0;
    private HeapPageId pid = new HeapPageId(getId(), pgNo);
    private Iterator<Tuple> iterator;
    private boolean flag = false;

    public HeapFileIterator(TransactionId tid) {
        this.tid = tid;
    }
    
    @Override
    public boolean hasNext() throws DbException, TransactionAbortedException {
        if (!flag) return false;
        if (iterator.hasNext()) return true;
        if (pgNo < numPages() - 1) {
            pid = new HeapPageId(getId(), ++pgNo);
            iterator = ((HeapPage)Database.getBufferPool().getPage(tid, pid, Permissions.READ_ONLY)).iterator();
        }
        return iterator.hasNext();
    }

    @Override
    public Tuple next() throws DbException, TransactionAbortedException,
            NoSuchElementException {
        if (hasNext()) {
            return iterator.next();
        }
        throw new NoSuchElementException("no valid element!");
    }

    @Override
    public void open() throws DbException, TransactionAbortedException {
        flag = true;
        iterator = ((HeapPage)Database.getBufferPool().getPage(tid, pid, Permissions.READ_ONLY)).iterator();
    }

    @Override
    public void rewind() throws DbException, TransactionAbortedException {
        pgNo = 0;
        pid = new HeapPageId(getId(), pgNo);
        iterator = ((HeapPage)Database.getBufferPool().getPage(tid, pid, Permissions.READ_ONLY)).iterator();
    }

    @Override
    public void close() {
        flag = false;
    }
}

这里读取Tuple中需要读取对应的Page，其思想还是从BufferPool中读取，我们在前面已经实现了BufferPool的getPage，缺页时从DbFile的readPage获取

exercise6

实现SeqScan

该实验要求我们从数据库层面实现一种opt，即全表顺序扫描，我们已经层层封装了tuple的Iterator，在这里使用即可，比较easy

All Tests Pass