MIT 6.830 实现简易数据库 lab

Posted by zsh on August 7, 2022

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类的作用是构建表中所有字段的直方图,然后估算某个字段的选择性以及全表扫描的花费。实现步骤如下

  1. 在构造器方法里创建每个字段的直方图
  2. 实现estimateSelectivity(int field, Predicate.Op op, Field constant)方法,获取某个字段的估算选择性
  3. 实现estimateScanCost,获取全表扫描的估算花费
  4. 实现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