SimpleDB-Lab2
0.实验目标
实验二需要为SimpleDB编写一组操作符，用于实现表的修改（例如，插入和删除记录），选择操作，连接操作和聚合操作。这些操作将在Lab 1中所编写的基础上构建。此外，需要设计页面淘汰策略，完善缓冲池。仍不需要实现事务和锁。
可以使用提供的SQL解析器对数据库运行SQL查询。
- 实现Filter和Join操作符。这些操作符的Javadoc注释中包含了其工作细节。Project和OrderBy已实现，这可能有助于您理解其他操作符的工作方式。
- 实现IntegerAggregator和StringAggregator。需要编写逻辑来计算在一系列输入元组中，跨多个分组计算特定字段的聚合结果。由于SimpleDB仅支持整数，所以在计算平均值时请使用整数除法。StringAggregator仅需要支持COUNT聚合操作，因为其他操作对于字符串没有意义。
- 实现Aggregate操作符。和其他运算符一样，聚合运算符实现了 OpIterator 接口，这样它们就可以放在 SimpleDB 查询计划中。注意Aggregate运算符的输出是每次调用next()时整个组的聚合值，并且聚合构造器需要聚合和分组字段。
- 在 BufferPool 中实现与元组插入、删除和页面驱逐有关的方法。在这一点上，你不需要担心 transactions 的问题。
- 实现插入和删除操作符。像所有的操作符一样，Insert和Delete实现了OpIterator，接受一个要插入或删除的 tuple 流，并输出一个带有整数字段的单一 tuple ，表示插入或删除的 tuple 数量。这些操作者将需要调用BufferPool中的适当方法，这些方法实际上是修改磁盘上的页面。检查插入和删除 tuple 的测试是否正常工作。
P.S. 请注意，SimpleDB没有实现任何类型的一致性或完整性检查，所以有可能在文件中插入重复的记录，也没有办法强制执行主键或外键约束。
1. Filter and Join
a. 要修改的文件
- src/java/simpledb/execution/Predicate.java
- src/java/simpledb/execution/JoinPredicate.java
- src/java/simpledb/execution/Filter.java
- src/java/simpledb/execution/Join.java
b. 实现说明
SimpleDB OpIterator类实现了关系代数的操作，现在需要实现两个运算符，使你能够执行比表扫描更有趣的查询。
Filter: 这个操作符只返回满足 “谓词 “的 tuple ，”谓词 “是作为其构造函数的一部分指定的。因此，它过滤掉任何不符合谓词的 tuple 。
Join: 这个操作符根据作为其构造函数一部分传入的 “JoinPredicate “来连接其两个子代的 tuple 。我们只需要一个简单的嵌套循环连接，但你可以探索更有趣的连接实现。在你的实验报告中描述你的实现。
c. 实现目标
- 通过单元测试 PredicateTest、JoinPredicateTest、FilterTest 和 JoinTest
- 通过系统测试 FilterTest 和 JoinTest
d. 设计思路
Predicate类，即“谓词”，是用来辅助实现Filter操作的。构造函数中需要三个参数：需要进行比较tuple中的field的编号field、比较的操作符op（等于、大于等）、进行比较的值operand。
举个例子，当需要过滤出第2列大于200的tuple时，可以创建Predicate(field=2, op=GREATER_THAN, operand=200)
Predicate类的filter方法，传入一个tuple，返回该tuple是否满足“谓词条件”。
Filter类，继承了抽象类Operator。用来过滤出符合“谓词条件”的tuple，”谓词 “是作为其构造函数的一部分指定的。
可以看做一个自定义的迭代器，通过调用fetchNext()来获取符合要求的下一个tuple。
JoinPredicate类，与Predicate类类似，用来辅助Join操作。
JoinPredicate类的filter方法，传入两个tuple，返回这两个tuple是否满足“谓词条件”。
Join类，继承了抽象类Operator。用来将两张表进行连接。当且仅当表A与表B中的指定列的field的值相同时才连接。并且返回的tuple不去除重复的field值。
可以看做一个自定义的迭代器，通过调用fetchNext()来获取符合要求的下一个tuple。
e. 实现说明
- 参考OrderBy和Project类进行实现。
- 通过所有单元测试和系统测试。
2. Aggregates
a. 要修改的文件
- src/java/simpledb/execution/IntegerAggregator.java
- src/java/simpledb/execution/StringAggregator.java
- src/java/simpledb/execution/Aggregate.java
b. 实现说明
- 一个额外的SimpleDB操作符用GROUP BY子句实现了基本的SQL聚合。你应该实现五个SQL聚合（COUNT, SUM, AVG, MIN, MAX）并支持分组。你只需要支持单个字段的聚合，以及单个字段的分组。
- 为了计算聚合，我们使用一个Aggregator接口，将一个新元组合并到现有的聚合计算中。在构建过程中，Aggregator被告知它应该使用什么操作来进行聚合。随后，客户端代码应该为子迭代器中的每个元组调用Aggregator.mergeTupleIntoGroup()。在所有 tuple 被合并后，客户端可以检索到一个聚合结果的OpIterator。结果中的每个元组都是一对形式为(groupValue, aggregateValue)的元组，除非group by字段的值是Aggregator.NO_GROUPING，在这种情况下，结果是一个形式为(aggregateValue)的单一元组。
- 请注意，这个实现需要的空间与不同组的数量成线性关系。在本实验中，你不需要担心组的数量超过可用内存的情况。
c. 实现目标
- 通过单元测试IntegerAggregatorTest、StringAggregatorTest和AggregateTest
- 通过系统测试AggregateTest
d. 设计思路
Aggregate用来实现聚合操作（COUNT, SUM, AVG, MIN, MAX）的，并支持分组。
构造函数中需要传入参数：tuple迭代器child（遍历表中的每个元组）、进行聚合的列号afield、需要分组的列号gfield和聚合的符号aop。
Aggregator是一个接口，有IntegerAggregator和StringAggregator两个实现
void mergeTupleIntoGroup(Tuple)将传入的tuple加入到当前的聚合中。
OpIterator iterator()返回聚合结果的迭代器
主要是通过Map<Field, Tuple>将group field值映射到tuple，也就是分组的每个值对应一个tuple。若没有进行分组，则将field值置为null，放入map中。
目前是在每次调用mergeTupleIntoGroup()时更新map。
也可以保存max、min、sum、count等中间结果，等到OpIterator的open()时再统一添加tuple。
IntegerAggregator的实现有点粗糙：为了实时更新AVG的结果，需要知道sum和count的结果，每次重新计算平均值，因此另外设计了两个Map，来存放每个分组的sum和count。
通过所有单元测试和系统测试。
3. HeapFile Mutability
a. 要修改的文件
- src/java/simpledb/storage/HeapPage.java
- src/java/simpledb/storage/HeapFile.java
(Note that you do not necessarily need to implement writePage at this point).
b. 实现说明
现在将开始实现支持修改表格的方法。我们从单个页面和文件的层面开始。有两组主要的操作：添加 tuple 和删除 tuple 。
删除 tuple：要删除一个 tuple ，你需要实现deleteTuple。元组包含记录ID，允许你找到它们所在的页面，所以这应该很简单，只要找到元组所属的页面并适当地修改页面的标题。
添加 tuple：HeapFile.java中的insertTuple方法负责向一个堆文件添加元组。要向HeapFile添加一个新元组，你必须找到一个有空槽的页面。如果HeapFile中没有这样的页面存在，你需要创建一个新的页面并将其追加到磁盘上的物理文件中。你将需要确保元组中的RecordID被正确地更新。
为了实现HeapPage，你需要为insertTuple()和deleteTuple()等方法修改标题位图。你可能会发现，我们在实验1中要求你实现的getNumEmptySlots()和isSlotUsed()方法可以作为有用的抽象方法。请注意，有一个markSlotUsed方法作为抽象，用来修改页眉中元组的填充或清除状态。
注意，重要的是，HeapFile.insertTuple()和HeapFile.deleteTuple()方法要使用BufferPool.getPage()方法访问页面；否则，你在下一个实验的事务实现将不能正常工作。
在src/simpledb/BufferPool.java中实现insertTuple()和deleteTuple()。
这些方法应该调用HeapFile中属于被修改的表的适当方法（这个额外的间接层次是需要的，以便在未来支持其他类型的文件（例如索引））。
c. 实现目标
- 通过单元测试HeapPageWriteTest、HeapFileWriteTest和BufferPoolWriteTest
d. 实现说明
HeapPage中的插入与删除tuple
insertTuple：寻找空闲的槽位，插入新的tuple，并更新这个tuple的recoedId，调用markSlotUsed更新Page信息。
deleteTuple：调用markSlotUsed更新Page信息。
HeapFile中的插入与删除tuple
insertTuple：若有空闲的Page，则调用该Page的insertTuple插入；否则创建新的Page，再调用Page的insertTuple插入。返回更新过的Page（此处只修改了一个Page）。
deleteTuple：根据tuple的recordId信息找到对应的Page，调用Page的deleteTuple删除，并返回返回更新过的Page（此处只修改了一个Page）。
BufferPool中的插入与删除tuple
insertTuple：调用HeapFile中的insertTuple，并调用updateBufferPool()对BufferPool进行更新。
deleteTuple：调用HeapFile中的deleteTuple，并调用updateBufferPool()对BufferPool进行更新。
updateBufferPool：自己写的私有函数，用于更新BufferPool中指定的Page信息。对传入的List
，调用markDirty标记为脏页（之后需要写回磁盘）。若BufferPool中没有该页，则加入BufferPool。更新BufferPool中该页为最新传入的Page。 参考BTreeFile，实现了writePage()
测试BufferPoolWriteTest的handleManyDirtyPages中，首先创建了一个有一页的空Page的HeapFile，之后再加入10页，每页插入一条数据。然后测试文件中是否能读出十条数据。问题在于，HeapFileDuplicates的insertTuple()中是每次在文件中写入一个空页，然后创建一个新的HeapPage，再往HeapPage中插入数据，也就是数据没有写回文件中，仅仅保存在返回值List
中。 因此在BufferPool的insertTuple和deleteTuple里加一步更新BufferPool的操作，也就是将修改后发生变化的Page重新更新到BufferPool（但是可以不写回磁盘）
但是有个新的问题是，如果更新操作在BufferPool中执行，那么单独调用HeapFile的insertTuple就无法读到最新的Page信息。测试BufferPool的insertTuple中，是先在file中写入新的一页，再插入tuple，因此在HeapFile的insertTuple中对文件进行读写是可行的。因此直接在HeapFile的insertTuple操作中，若之前的Page都满了，则写入新的Page，并直接将新的Page写入磁盘。
发现之前的BufferPool有误，更正插入的第一页PageNo为0.
通过单元测试HeapPageWriteTest、HeapFileWriteTest和BufferPoolWriteTest
4. Insertion and deletion
a. 要修改的文件
- src/java/simpledb/execution/Insert.java
- src/java/simpledb/execution/Delete.java
b. 实现说明
现在你已经写好了所有用于添加和删除 tuple 的HeapFile机器，你将实现Insert和Delete操作。对于实现 “插入 “和 “删除 “查询的计划，最上面的运算符是一个特殊的 “插入 “或 “删除 “运算符，它修改了磁盘上的页面。这些操作符返回受影响 tuple 的数量。这是通过返回一个带有一个整数字段的单一元组来实现的，其中包含计数。
Insert：这个操作符将它从其子操作符中读取的 tuple 添加到其构造函数中指定的tableid’。它应该使用BufferPool.insertTuple()`方法来做这件事。
Delete: 这个操作符从其构造函数中指定的tableid中删除它从其子操作符中读取的 tuple。它应该使用BufferPool.deleteTuple()`方法来做这件事。
c. 实现目标
- 通过单元测试 InsertTest
- 通过系统测试 InsertTest 和 DeleteTest
d. 设计思路
- 操作符Insert和Delete的fetchNext()通过调用BufferPool中的insertTuple()和deleteTuple()实现。返回值为单个Tuple，TD为INT_TYPE，值为修改的tuple的数量。
- fetchNext()只能调用一次，第二次便返回null。因此设置一个私有变量，标记是否已经完成操作。
5. Page eviction
a. 要修改的文件
- src/java/simpledb/storage/BufferPool.java
b. 实现说明
在实验1中，我们没有正确观察到由构造参数numPages定义的缓冲池中最大页数的限制。现在，你将选择一个页面淘汰策略，并对以前任何读取或创建页面的代码进行编程，以实现你的策略。
当缓冲池中的页面超过numPages时，在加载下一个页面之前，应该将一个页面从缓冲池中淘汰。淘汰策略的选择由你决定；没有必要做一些复杂的事情。
注意BufferPool要求你实现flushAllPages()方法。这不是你在真正实现缓冲池时需要的东西。然而，我们需要这个方法用于测试。你不应该在任何真正的代码中调用这个方法。
由于我们实现ScanTest.cacheTest的方式，你需要确保你的flushPage和flushAllPages方法不从缓冲池中淘汰页面，以正确通过这个测试。
flushAllPages应该在BufferPool中的所有页面上调用flushPage，flushPage应该将任何脏页写入磁盘并标记为不脏，同时将其留在BufferPool中。
唯一应该从缓冲池中删除页面的方法是evictPage，它应该对它所淘汰的任何脏页面调用flushPage。
如果你没有在上面的HeapFile.java中实现writePage()，你也需要在这里实现它。最后，你还应该实现discardPage()，以便从缓冲池中删除一个页面而不写入磁盘。我们不会在本实验中测试discardPage()，但它在未来的实验中是必要的。
c. 实现目标
- 通过系统测试 EvictionTest
- 由于我们不会检查任何特定的驱逐策略，这个测试通过创建一个有16页的BufferPool（注意：虽然DEFAULT_PAGES是50，但我们初始化的BufferPool更少！），扫描一个超过16页的文件，看看JVM的内存使用率是否增加了5MB以上。如果你没有正确地实施淘汰策略，你将无法淘汰足够多的页面，并将超过大小限制，从而导致测试失败。
d. 设计思路
- flushPage()：将脏页写入磁盘，并标记为不脏。（不需要从BufferPool中淘汰该页）
- flushAllPages()：对BufferPool中的所有页面调用flushPage()。
- discardPage()：从BufferPool中删除一个页面，并且不写入磁盘。
- evictPage()：从BufferPool中淘汰一个页面。若为脏页，调用flushPage()将脏页写入磁盘；否则调用discardPage()直接删除页面。
e. 实现说明
- 更新了BufferPool，将把PageId映射到BufferPageId的Map更改为LinkedHashMap实现，这样就可以直接按照访存顺序获取到最近最久未访问的页面，便于页面淘汰。
- 相应地，将空页面的获取方式更改为了Queue实现。初始时，在队列中加载全部页面，之后每次需要时取出队列的第一个元素，将页面写入该位置的缓存。淘汰页面时，需要更新Queue，将淘汰页面的bpid重新加入Queue。
6. 小结
- 由于打包前要通过测试，所以一些各个Lab中通过打包实现的一些测试就先略过，最后再统一测试。
SimpleDB-Lab2