exercise 1
实现对某一字段直方图的构建。估计查询计划的代价首先要获得数据的统计数据，本lab采用直方图对数据进行统计。一个直方图代表着一个字段的统计信息， 直方图将字段的值分为多个相同的区间，并统计落于每个区间的记录数。每个区间的记录数是一个bucket，bucket的宽度是区间的大小，bucket的高度是落于该区间的记录的数量。 然后根据构造的直方图，计算某一谓词下某一字段的选择率。 选择率的计算过程如下：
- 对于等值运算value = const，首先需要找到包含该const值的桶，然后进行计算：选择率 = （value = const 的记录数）/ 记录总数，假设数值在桶中是均匀分布的，value = const的记录数为 桶宽 / 桶高，故选择率可以表示为 （桶高 / 桶宽）/ 记录总数。
- 对于非等值运算，我们采用的也是同样的思想，value > const的选择率 = （value > const的记录数）/ 记录总数，value > const的记录数的记录数在直方图中由两部分构成。（const，b.right]部分的记录数 和 [b.right，max]部分的记录数。（const，b.right]部分的记录数 = （h_b / w_b）* （b_right - const）, [b.right，max]部分的记录数 = 后面桶高的加和。
实验1需要实现
- src/java/simpledb/optimizer/IntHistogram.java
同时需要通过IntHistogramTest
exercise 2
TableStats类的作用是构建表中所有字段的直方图，然后估算某个字段的选择性以及全表扫描的花费。实现步骤如下
- 在构造器方法里创建每个字段的直方图
- 实现
estimateSelectivity(int field, Predicate.Op op, Field constant)方法，获取某个字段的估算选择性 - 实现
estimateScanCost，获取全表扫描的估算花费 - 实现
estimateTableCardinality(double selectivityFactor)根据给定的选择因子返回基数 实验2需要实现- src/java/simpledb/execution/IntegerAggregator.java
- src/java/simpledb/execution/StringAggregator.java
- src/java/simpledb/execution/Aggregate.java
并通过IntegerAggregatorTest，StringAggregatorTest，AggregateTest
exercise 3
计算Join操作的开销，估计Join之后的基数。循环嵌套的连接成本如下： joincost(t1 join t2) = scancost(t1) + ntups(t1) x scancost(t2) //IO cost
- ntups(t1) x ntups(t2) //CPU cost
t1的扫描成本：cost1 t2的扫描成本：t1中的每一条记录都要与t2中的所有数据进行连接，每从t1中取出一条数据都要对它 进行全表扫描，故其扫描成本是 card1 * cost2 t1与t2的连接成本：card1 * card2
实验3需要实现
- src/java/simpledb/optimizer/JoinOptimizer.java
并通过TableStatsTest
exercise 4
实现Insert和Delete类，作为insert和delete的SQL语句具体执行类，底层还是调用的实验3写的insertTuple和deleteTuple，这里需要实现writePage方法， 在insert或者delete之后调用，把操作结果落盘 实现2需要实现
- src/java/simpledb/execution/Insert.java
- src/java/simpledb/execution/Delete.java
并通过InsertTest, DeleteTest, HeapFileWriteTest，HeapPageWriteTest，systemtest/InsertTest，systemtest/DeleteTest
exercise 5
实现页置换算法，当BufferPool的pages满了后，需要挑选一页置换，可以选择LRU，LFU，Clock等 实验5需要实现
- src/java/simpledb/storage/BufferPool.java
并通过systemtest/EvictionTest
