MIT 6.830 Lab2

Project Intro

Lab 2需要实现SQL中常见的几种算子逻辑：

  • Filter，条件查询过滤器
  • Join，两表连接查询（本Lab只实现内连接）
  • Aggregate，聚合运算（求平均值/最值等等）
  • Insert/Delete，增删元组

另外，对于需要修改文件内容的操作，需要在Buffer/File/Page这三个层面同时实现对应的修改，保证数据库的一致性。最后，由于Buffer Pool的容量是有限的，因此还需要实现一个页置换算法。

基本算子的实现

这一小节的内容对应Lab 2的Exercise 1-4。

Filter

Filter的判读过滤操作被抽象成了Predicate类，这个类在实现的时候，需要对三个对象进行初始化：

  • 需要判断的属性值的列号field
  • 判断的类型（大于/小于/等于/不等于），用一个枚举类型op表示
  • 判断的基准值，用Field类型的值operand表示
1
2
3
4
5
6
public Predicate(int field, Op op, Field operand) {
    // some code goes here
    this.field = field;
    this.op = op;
    this.operand = operand;
}

Predicate类会通过filter(Tuple t)方法判断给定的属性值是否满足判断条件，然后在Filter类中调用即可。

1
2
3
4
5
public boolean filter(Tuple t) {
    // some code goes here
    Field field = t.getField(this.field);
    return field.compare(op, operand);
}

Filter类中继承了Operator并需要实现一个fetchNext()方法，该方法遍历child中的tuple，直到找到一个满足条件的元组，否则就在遍历结束后返回null。

1
2
3
4
5
public Filter(Predicate p, OpIterator child) {
    // some code goes here
    this.p = p;
    this.child = child;
}

Join

这里实现的Join是内连接，就是将分别来自于两个表的，满足一定条件的元组a和b合成一个新的元组c，并且c的所有属性是a和b汇总得到的；例如：元组a是$(a_1,\ a_2,\ a_3)$，元组b是$(b_1,\ b_2)$，且a和b满足Join的判断条件，则生成的c是$(a_1,\ a_2,\ a_3,\ b_1,\ b_2)$。

与Filter类似地，Join的条件判断也通过一个类JoinPredicate来实现，只不过参数变成了两个元组。

1
2
3
4
5
6
7
8
9
10
11
public JoinPredicate(int field1, Predicate.Op op, int field2) {
    // some code goes here
    this.field1 = field1;
    this.op = op;
    this.field2 = field2;
}

public boolean filter(Tuple t1, Tuple t2) {
    // some code goes here
    return t1.getField(field1).compare(op, t2.getField(field2));
}

Aggregate

Aggregate操作是对数据表中的元组按照一定规则进行聚合运算，常见的Aggregate操作包括：

  • 计数类Count
  • 求和类Sum / Avg
  • 最值类Max / Min

Aggregate通常会和group by搭配使用，group by提供聚合的参照和依据，当它指定了某个属性后，该属性相同的元组会被聚合成一个结果，这时候Aggregate操作返回的结果就是类似(groupValue, aggregateValue)的元组。

在这个Lab中，需要实现两种不同数据类型（Int和String）的聚合运算。

Insert/Delete

增删元组这两种操作与前面的区别在于，Insert和Delete会改变数据表的Page中存储的元组信息，例如Insert会找到一个空的slot插入元组，Delete会把对应slot的元组标记为invalid（Lab 1提到的标记位）。

为此要先实现每个Heap Page中的插入删除操作，然后实现每个Heap File中的插入删除，然后再实现BufferPool中的插入删除。

  • 在一个Page发生了修改之后，这个Page就变成了脏页，需要标记为dirty，并让BufferPool在适当的时机写回到磁盘存储的文件中
  • 之后所有涉及到页修改的操作都需要通过BufferPool对外提供的方法进行，这其中执行的逻辑是BufferPool先判断要操作的页在不在Buffer中，如果不在就先去磁盘中把对应的Page读进来，然后在这个页上进行相关操作

页置换算法的实现

这一小节实现Lab 2的Exercise 5。

由于BufferPool容量有限，当读入的页超过容量后，需要将一部分页置换出去。常用的页置换算法有LRU、LFU等。这里实现了LRU的页置换算法。

LRU页置换

定义一个LRU类，数据结构设计为一个双向链表+哈希表。

  • 双向链表DLinkedNode按照被访问的顺序存储这些键值对，靠近链表头的键值对是最近访问的，靠近链表尾的键值对是最久未访问的
  • 哈希表cache通过缓存数据的键映射到其在双向链表中的位置

首先使用哈希表进行定位，找到缓存页在双向链表中的位置，随后将其移动到链表头，并完成相应的put或者add操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LRUCache<K, V> {
    class DLinkedNode{
        K key;
        V value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode(){}
        public DLinkedNode(K _key, V _value){
            key = _key;
            value = _value;
        }
    }
    private Map<K, DLinkedNode> cache = new ConcurrentHashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;
}