SimpleDB-Lab1

0.实验目标

完成本实验后，要能通过ScanTest系统测试

• 实现管理Tuple的类，即Tuple、TupleDesc。SimpleDB 中已经实现了Field、IntField、 StringField和Type，只需要支持整数和（固定长度的）字符串字段以及固定长度的 tuples。
• 实现 Catalog 。
• 实现BufferPool构造函数和getPage()方法。
• 实现访问方法、HeapPage和HeapFile以及相关的ID类。
• 实现操作符SeqScan。

1. 实现管理Tuple的类

a. 要修改的文件

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

b. 实现目标

• 通过单元测试TupleTest和TupleDescTest。
• 其中，modifyRecordId()方法应该失败（暂时不需要实现）。

c. 设计思路

• Tuple类

  • 构造函数Tuple(TupleDesc td)

  • TupleDesc getTupleDesc()

    • 增加私有变量TupleDesc td

  • RecordId getRecordId()

    • 增加私有变量RecordId rid

  • void setRecordId(RecordId rid)

  • void setField(int i, Field f)

    • 增加私有变量Field数组

  • Field getField(int i)

  • String toString()

  • Iterator<Field> fields()

  • void resetTupleDesc(TupleDesc td)

• TupleDesc类

  • Iterator<TDItem> iterator()

  • TupleDesc(Type[] typeAr, String[] fieldAr)

    • 增加私有变量TDItem数组

  • TupleDesc(Type[] typeAr)

  • int numFields()

  • String getFieldName(int i)

  • Type getFieldType(int i)

  • int fieldNameToIndex(String name)

  • int getSize()

    • 计算所占字节数

  • TupleDesc merge(TupleDesc td1, TupleDesc td2)

  • boolean equals(Object o)

  • int hashCode()

  • String toString()

2. 实现Catalog

a. 要修改的文件

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

b. 实现说明

需要在Catalog类中支持添加新表，以及获取特定表的信息的功能

c. 实现目标

• 通过单元测试CatalogTest

d. 设计思路

• 映射集合：将表名映射到表id、将表id映射到表名、将表id映射到表、将表id映射到表主键
• Catalog中存储当前数据库的表。对于SimpleDB，只有一个全局Catalog。
  • 构造函数Catalog()
  • void addTable(DbFile file, String name, String pkeyField)：在Catalog中插入一张新表，表内容为file，表名为name，主键名为pkeyfield（可为“”）。若表名已存在，则更新表内容。
  • int getTableId(String name)：返回指定表名的表的id。
  • TupleDesc getTupleDesc(int tableid)：通过表id获取表描述。
  • DbFile getDatabaseFile(int tableid)：通过表id获取表。
  • … …

3. 实现BufferPool的getPage()方法

a. 要修改的文件

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

b. 实现说明

• 没有单元测试，可以在HeapFile实现中测试。
• 能够使用DbFile.readPage方法来访问DbFile的页面。

c. 设计思路

• BufferPool是缓冲池，存储固定数量的Page。对于SimpleDB，只有一个全局BufferPool。

  • numPages：存储的Page的数量。
  • 构造函数BufferPool(int numPages)
  • Page getPage(TransactionId tid, PageId pid, Permissions perm)：获取指定的Page。若在缓冲池中，则直接返回；否则，从磁盘中读取并加入到BufferPool。若BufferPool空间不够，则淘汰掉Page，并将新读入的Page放在淘汰掉的Page的位置。
  • … …

• 映射集合：将PageId映射到BPageId，若对应的value为-1则说明BufferPool中没有该Page，需要先读取进BufferPool。

• Page的List集合：BufferPool中存储的Page，通过BPageId能够直接获取Page

• pageNum：当前BufferPool中的Page数量，若小于numPages则可以直接将Page加载到BufferPool中，否则需要淘汰Page。

• 需要读入Page时，应该调用BufferPool.getPage。BufferPool中存放着缓存的Page。若需要读取的Page在BufferPool中，就直接返回该页面；否则，通过Catalog.getDatabaseFile()获得DbFile表文件（例如HeapFile），再调用DbFile.readPage()从磁盘中加载需要读取的Page，之后更新BufferPool。

4. 实现HeapPage的方法

a. 要修改的文件

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

b. 实现说明

在HeapPage中实现getNumEmptySlots()和isSlotUsed()方法，这些方法需要在页面头部移动位。可以查看HeapPage或src/simpledb/HeapFileEncoder.java中提供的其他方法，来了解页面的布局。

实现页面中Tuple的迭代器，这可能涉及辅助类或数据结构。

在实现了HeapPage之后，还要为HeapFile编写方法，用于计算文件中的页面数量并从文件中读取页面。然后就能够从存储在磁盘上的文件中获取元组。

c. 实现目标

• 通过单元测试HeapPageIdTest、RecordIDTest和HeapPageReadTest。

d. 设计思路

• HeapPage实现了接口Page，是用堆文件的方式存储Tuple。包括PageId pid，Tuple描述td、指明当前位置是否为空的header（类似位图）、Tuple集合tuples、槽位数量numSlots，还有用于恢复数据的oldData和oldDataLock。

  • 构造函数HeapPage(HeapPageId id, byte[] data)：给变量pid、td、numSlots赋值。data通过流解析：前header.length位是header，指明该Page中的header.length条记录（元组）是否有效；之后是Tuples，每个Tuple占td.getSize()位。读取完数据后关闭流dis。最后调用setBeforeImage()，将Page中的数据存档在oldData中，用于数据恢复。

  • HeapPage getBeforeImage()：返回一个新的HeapPage对象，其中的内容是oldData中的存档信息，用于数据恢复。

  • void setBeforeImage()：将Page中的数据备份到oldData中，作为一个存档，用于数据恢复。

  • Tuple readNextTuple(DataInputStream dis, int slotId)：通过流dis读取Page中第slotId个元组的数据，返回读取到的元组以Tuple形式返回。若第slotId位为空，则从dis中读td.getSize()位（该表中单个元组的大小），然后返回null；否则创建新的Tuple，并设置RecordId，之后调用Type.parse方法得到Field，并通过Tuple.setFiled设置元组的数值，最后返回该Tuple。

  • byte[] getPageData()：生成一个byte数组来表示Page中的所有数据，用于序列化这个Page存放到磁盘上。

    • 创建一个ByteArrayOutputStream名为baos，长度为PageSize。再创建一个DataOutputStream向baos写入Bytes。首先写入header，之后对于每个元组，若元组为空则写入td.getSize()（一个元组的长度）个0；否则遍历元组内的Field，调用Field.serialize()写入输出流。将除了header、元组外的剩余位置都补0，最后刷新到输出流，返回baos.toByteArray()，也就是最后的字节数组。

  • byte[] createEmptyPageData()：静态方法，生成一个空的PageData的字节数组。

• HeapPage的header是byte[]类型，因此大小为ceil(numSlots/8)。isSlotUsed()方法需要进行位运算。

• HeapPage的迭代器需要自定义，因为中间可能有空位，需要跳过null获得下一个元组。

5. 实现HeapFile的方法

a. 要修改的文件

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

b. 实现说明

从磁盘读取页面，首先需要计算文件中的正确偏移量。（提示：为了在任意偏移量处读取和写入页面，你需要对文件进行随机访问。在从磁盘读取页面时，不应调用BufferPool的方法。）

还需要实现HeapFile.iterator()方法，该方法应遍历HeapFile中每个页面的元组。迭代器必须使用BufferPool.getPage()方法来访问HeapFile中的页面。该方法将页面加载到缓冲池中，并最终用于实现基于锁的并发控制和恢复（在后续的实验中）。不要在open()调用时将整个表加载到内存中，若表非常大会导致内存错误。

c. 实现目标

• 通过单元测试HeapFileReadTest。

d. 设计思路

• DbFile是表述单张表的数据结构，能够获取到表在磁盘上存储的具体Pages，并且遍历表的元组。每个DbFild都是通过缓存池来获取的。

  • Page readPage(PageId id)：从磁盘中读取指定的Page。
  • void writePage(Page p)：将指定的Page写入磁盘。
  • List<Page> insertTuple(TransactionId tid, Tuple t)：将指定的tuple插入表中，返回被修改的Page的List。
  • List<Page> deleteTuple(TransactionId tid, Tuple t)：从表中移除指定的tuple，返回被修改的Page的List。
  • DbFileIterator iterator(TransactionId tid)：返回一个能够遍历所有元组的迭代器（通过BufferPool的getPage实现）。
  • int getId()：返回这个DbFile在Catalog中的ID。
  • TupleDesc getTupleDesc()：返回这个表的TupleDesc。

• int numPages()：HeapFile中包含的Page数量，为文件大小除PageSize向上取整。

• Page readPage(PageId pid)：主要参考TestUtil中的readFileBytes(String path)方法，从文件中读取data。之后调用构造函数HeapPage(pid, data)创建HeapPage对象并返回。

• DbFileIterator iterator(TransactionId tid)：对HeapFile中的所有元组进行遍历。

  • DbFileIterator是一个接口，可以看作一个扩展的迭代器。

    • void open()：打开迭代器，打开之前无法获取迭代器中的内容。
    • boolean hasNext()：是否有下一项。
    • Tuple next()：返回下一个元组并使迭代器向后移一位。
    • void rewind()：重设迭代器，使其返回开头。
    • void close()：关闭迭代器，关闭后无法获取下一项内容。

  • 这里对DbFileIterator的实现类之一AbstractDbFileIterator进行实现。由于AbstractDbFileIterator是抽象类，因此需要实现抽象方法readNext()以及没有实现的父类方法open()和rewind()。

    • 在AbstractDbFileIterator实现类中，新增两个变量tupleIterator和currentPage，分别是Page内的迭代器以及当前的Page。这是由于HeapPage中实现了对元组的迭代器，因此可以直接通过迭代器遍历Page内元组。
    • 若迭代器遍历到该Page最后一项，则需要查看是否还有下一页。若有，则更新currentPage和迭代器tupleIterator；否则返回null。

6. 实现Operator

a. 要修改的文件

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

b. 实现说明

该操作符按顺序扫描由构造函数中的tableid指定的表的所有页面中的元组。该操作符应通过DbFile.iterator()方法访问元组。

c. 实现目标

• 通过系统测试ScanTest

d. 设计思路

• 从实现角度来说不难，创建变量tid、tableId、tableAlias分别为事务编号、表号和表的别名。
• TupleDesc getTupleDesc()：返回带有别名的表描述。创建新的Type[]和String[]，用原本的表描述（通过表号查询得到）来给变量赋值。
• hasNext()、next()等一系列Iterator相关方法：通过获取HeapFile的iterator实现。本质上是检测之前的Iterator的正确性。

小结

• 实现不难，但是Iterator相关测试一直报错。一路查上去发现是之前的一些文件没写正确，但是当时的Test过于简单因此没查出问题。

• 由于SeqScan的Iterator就是调用HeapFile的iterator实现，因此重新查看HeapFileReadTest。与Iterator相关的测试为testIteratorBasic()，但是只测了三个元组，测试过于简单。用该测试测试505条元组后开始报错。一个Page中最多存放504个元组，这说明对于多个Page的HeapFile读取有误。

• 重新查看对HeapPageReadTest，发现不论怎么修改测试数据结果均正确，说明对Page内的元组的读写无误。那么问题应该出在HeapFile与HeapPage的数据传输上。

  • HeapFile是整个表的抽象，有file变量指向数据在磁盘具体位置，但是并不会保存具体的Page。当用户需要查询Page时，首先通过BufferPool的readPage查看Page是否在缓冲池中，若在则直接返回该Page；否则调用表文件HeapFile的readPage，从磁盘中读入Page，并更新缓冲池信息。
  • 因此问题出在HeapFile的readPage()方法中。经查看，原本的方法一次性读入了全部文件并直接传入HeapPage的构造方法，返回新创建的HeapPage。进行更正后，输入流首先根据PageId，跳过之前的Page，读取PageSize个字节存入data，再将data传入HeapPage的构造方法创建新的HeapPage。

• 更正完成后，测试通过。