get ready

MIT6.830這個課程主要內容是資料庫基礎，會有很多reading和lab。主要內容：

focusing on basics such as the relational algebra and data model, schema normalization, query optimization, and transactions.

lab是分幾步實現一個簡單的simple-db，主要的框架代碼已經給好了，而且也很貼心的給了test。

課程地址：

6.830/6.814 Schedule and Readings?

db.lcs.mit.edu

labs github:

MIT-DB-Class/course-info-2018?

github.com圖標https://github.com/MIT-DB-Class/simple-db-hw?

github.com圖標

lab1實現資料庫基本的存儲邏輯結構，具體包括：Tuple,TupleDesc,HeapPage,HeapFile,SeqScan, BufferPool等。

  • Tuple和TupleDesc是資料庫表的最基本元素了。Tuple就是一個若干個Field的數組，TupleDesc則是一個表的meta-data，包括每列的field name和type。

  • HeapPage和HeapFile都分別是Page和DbFile interface的實現，畢竟HeapPage和HeapFile組織還是太簡單了，後面lab會用B+樹來替代之。
  • BufferPool是用來做緩存的，getPage會優先從這裡拿，如果沒有，才會調用File的readPage去從文件中讀取對應page，disk中讀入的page會緩存在其中。
  • SeqScan用來遍歷一個table的所有tuple，包裝了HeapFile的iterator。

畫了個大概的關係圖：

SimpleDB architecture

  • 用於存儲的tuple, files, tuple schema等
  • 應用predicated和conditions到tuples
  • access methods，用來存儲關係，提供關係的遍歷方式
  • select, join, delete等
  • buffer pool，用來做緩存
  • catalog保存表和其schema的信息

暫時沒有SQL front end，這個可以考慮後面自己手寫一個。沒視圖，數據類型小等。而且也沒有優化器、沒有索引。

labs

exercise 1

實現這兩個骨架：

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

Tuple就是filed objects的集合，然後filed類型可以不同。TupleDesc則是Tuple的schema，也就是其元信息。

先看下代碼/src/java/simpledb/TupleDesc.java，裡面有個TDItem，表示filed，包含其類型和名字：

所以，TupleDesc就是tuple的schema，比如對於表student

id(int) name(string) sex(string)
1 xxx m
2 yyy f

那麼(1, xxx, m)就是一個Tuple，然後TupleDesc是(id(int) name(string) sex(string))。

具體看下Type的實現(src/java/simpledb/Type.java)：

public enum Type implements Serializable {
INT_TYPE() {
/*...*/
}, STRING_TYPE() {
/*...*/
};

public static final int STRING_LEN = 128;
public abstract int getLen();
public abstract Field parse(DataInputStream dis) throws ParseException;
}

是個枚舉類型，目前只有string和int兩種類型，然後支持從DataInputStream解析出Field，而Field是一個interface，有IntField和StringField實現。

至此思路很清晰，只需要給Tuple加個TupleDesc和ArrayList<Field>成員，並實現相關函數。

exercise 2

Catelog是Table的集合，然後每個Table有DbFile, PrimaryKeyField, Name，所以：

後面增刪查改就很容易了。

exercise 3

BufferPool是用來在內存中緩存從disk讀入的pages的。有固定的pages大小，所以需要有置換策略，這個在後面的lab會實現。

exercise 4

DbFil是用來read/write數據的interface，有HeapFile和BTreeFile兩個實現。

每個HeapFile表示一個表，包含了多個page，然後每個page的size都是固定的。所以，每個page可以分配若干個Tuple，計算方式是：

_tuples per page_ = floor((_page size_ * 8) / (_tuple size_ * 8 + 1))

之所以需要+1，是因為每個page都會有一個header，這個header裡面有個bitmap來表示對應Tuple是否已經in use了。

exercise 5

HeapFile是DbFile interface的實現，包含有一系列HeapPage，是沒有順序的。然後HeapFile剛開始是不會將數據讀入內存的，只保存了其handler，只有在readPage的時候，才會根據元信息計算出offset，然後在文件中讀取對應的page。

然後還需要給實現Iterator，我們在open的時候不要將整個文件都讀入內存，而是遍歷的時候，根據position來計算offset，只讀入對應的Tuple。所以，需要維護幾個變數:currPageId, currPage,tupleIter,open等來維護現在查詢的狀態。然後，我們的page都是從BufferPool中讀取的，而不是直接去disk讀。

在寫這個的時候，嘗試用RandomAccessFile去讀文件，然後採用的是read(buf, offset, len)函數，offset設置的是在文件中的offset。後來發現，對於這個函數的offset有點誤解，應該是在buf中的offset。正確的用法應該是，先seek(offset)，然後read(buf)。

所以，BufferPool和HeapFile是互相調用的。如果我想要readPage，會去BufferPool裡面取，如果內存中沒有緩存這個page，BufferPool會調用HeapFile的readPage，然後從disk中，根據計算出來的offset，讀取page。

exercise 6

很容易，包裝一下HeapFile的iterator就好。

https://github.com/xiebei1108/MIT6.830/blob/master/note/lab1.pdf?

github.com


推薦閱讀：
相關文章