6.830 Lab 1: SimpleDB
齐典
Intro
在6.830中，实现一个基础的数据管理系统SimpleDB。Lab1主要是实现对硬盘上存储数据的访问，之后的Lab会实现其他query processing operators，包括transactions，locking，concurrent queries。
1. Getting started
SimpleDB使用 Ant build tool 来编译代码和运行测试。Ant和make一样，只是编译文件被写成XML格式，更适合java 代码。
MAC下用http://blog.sina.com.cn/s/blog_877e9c3c0101qs87.html中的方法安装ant成功：
HemingbeardeMacBook-Pro:~ hemingbear$ ant -version
Apache Ant(TM) version 1.10.7 compiled on September 1 2019文档中提供了单元测试的方法，以及ant命令行指令。
To run the unit tests use the
testbuild target:$ cd [project-directory] $ # run all unit tests $ ant test $ # run a specific unit test $ ant runtest -Dtest=TupleTestYou should see output similar to:
build output... test: [junit] Running simpledb.CatalogTest [junit] Testsuite: simpledb.CatalogTest [junit] Tests run: 2, Failures: 0, Errors: 2, Time elapsed: 0.037 sec [junit] Tests run: 2, Failures: 0, Errors: 2, Time elapsed: 0.037 sec ... stack traces and error reports ...The output above indicates that two errors occurred during compilation; this is because the code we have given you doesn't yet work. As you complete parts of the lab, you will work towards passing additional unit tests.
Command Description ant Build the default target (for simpledb, this is dist). ant -projecthelp List all the targets in build.xmlwith descriptions.ant dist Compile the code in src and package it in dist/simpledb.jar.ant test Compile and run all the unit tests. ant runtest -Dtest=testname Run the unit test named testname.ant systemtest Compile and run all the system tests. ant runsystest -Dtest=testname Compile and run the system test named testname.
其中，ant systemtest是提供的end-to-end test，如果出现错误，可以通过检查出错位置的源代码来debug。
课程推荐的IDE是ECLIPSE，我这里使用IDEA。
Lab需要补充没有实现的代码，可能需要添加私有方法或者辅助类，可能要修改API，但要保证grading测试可以运行并通过。
2. SimpleDB Architecture and Implementation Guide
简单介绍SimpleDB的结构，SimpleDB包括了：
- Classes that represent fields, tuples, and tuple schemas;
- Classes that apply predicates and conditions to tuples;
- One or more access methods (e.g., heap files) that store relations on disk and provide a way to iterate through tuples of those relations;
- A collection of operator classes (e.g., select, join, insert, delete, etc.) that process tuples;
- A buffer pool that caches active tuples and pages in memory and handles concurrency control and transactions (neither of which you need to worry about for this lab); and,
- A catalog that stores information about available tables and their schemas.
SimpleDB不包括一些被认为应该被数据库包括的内容，SimpleDB不包括：
- (In this lab), a SQL front end or parser that allows you to type queries directly into SimpleDB. Instead, queries are built up by chaining a set of operators together into a hand-built query plan (see Section 2.7). We will provide a simple parser for use in later labs.
- Views.
- Data types except integers and fixed length strings.
- (In this lab) Query optimizer.
- (In this lab) Indices.
2.1. The Database Class
Database类提供了database中要用到的静态全局对象。其中，包括了访问catalog(database中所有表的集合)、buffer pool(现在驻留在内存中所有数据库文件页的集合)以及log file的方法。在这个lab中不需要关心log file。
2.2. Fields and Tuples
数据库中，行被称为记录(record)或元组(tuple),列称为字段(field)或属性(attribute)。tuples在SimpleDB中十分基础，是一组Field对象的集合，Field是不同数据类型(e.g.,integer,string)实现的接口，Tuple对象是由底层访问方法(e.g.,heap files,B trees)创建的，Tuple也有类型type（或称为组织结构schema），称为_tuple descriptor_，是TypleDesc对象，这个对象包括了Type对象的集合。
Exercise 1
Implement the skeleton methods in:
- src/simpledb/TupleDesc.java
- src/simpledb/Tuple.java
At this point, your code should pass the unit tests TupleTest and TupleDescTest. At this point, modifyRecordId() should fail because you havn't implemented it yet.
TupleDesc主要定义了Tuple结构，这里是一个TDItem类型的数组，一个TDItem对象包括fieldType和fieldName两个属性，通过这两个属性描述数据库的行。
src/simpledb/TupleDesc.java代码如下：
package simpledb;
import java.io.Serializable;
import java.util.*;
/**
* TupleDesc describes the schema of a tuple.
*/
public class TupleDesc implements Serializable {
/**
* the parameter used to hold tuple
*/
private final TDItem[] tdItems;
/**
* A help class to facilitate organizing the information of each field
* */
public static class TDItem implements Serializable {
private static final long serialVersionUID = 1L;
/**
* The type of the field
* */
public final Type fieldType;
/**
* The name of the field
* */
public final String fieldName;
public TDItem(Type t, String n) {
this.fieldName = n;
this.fieldType = t;
}
public String toString() {
return fieldName + "(" + fieldType + ")";
}
}
/**
* @return
* An iterator which iterates over all the field TDItems
* that are included in this TupleDesc
* */
public Iterator<TDItem> iterator() {
// some code goes here
return (Iterator<TDItem>) Arrays.asList(tdItems).iterator();
}
private static final long serialVersionUID = 1L;
/**
* Create a new TupleDesc with typeAr.length fields with fields of the
* specified types, with associated named fields.
*
* @param typeAr
* array specifying the number of and types of fields in this
* TupleDesc. It must contain at least one entry.
* @param fieldAr
* array specifying the names of the fields. Note that names may
* be null.
*/
public TupleDesc(Type[] typeAr, String[] fieldAr) {
// some code goes here
tdItems = new TDItem[typeAr.length];
for(int i=0;i<typeAr.length;++i){
tdItems[i] = new TDItem(typeAr[i],fieldAr[i]);
}
}
/**
* Constructor. Create a new tuple desc with typeAr.length fields with
* fields of the specified types, with anonymous (unnamed) fields.
*
* @param typeAr
* array specifying the number of and types of fields in this
* TupleDesc. It must contain at least one entry.
*/
public TupleDesc(Type[] typeAr) {
// some code goes here
tdItems = new TDItem[typeAr.length];
for(int i=0;i<typeAr.length;++i){
tdItems[i] = new TDItem(typeAr[i],"");
}
}
/**
* @return the number of fields in this TupleDesc
*/
public int numFields() {
// some code goes here
return tdItems.length;
}
/**
* Gets the (possibly null) field name of the ith field of this TupleDesc.
*
* @param i
* index of the field name to return. It must be a valid index.
* @return the name of the ith field
* @throws NoSuchElementException
* if i is not a valid field reference.
*/
public String getFieldName(int i) throws NoSuchElementException {
// some code goes here
if(i<0 || i>= tdItems.length){
throw new NoSuchElementException("pos " + i + " is not a valid index");
}
return tdItems[i].fieldName;
}
/**
* Gets the type of the ith field of this TupleDesc.
*
* @param i
* The index of the field to get the type of. It must be a valid
* index.
* @return the type of the ith field
* @throws NoSuchElementException
* if i is not a valid field reference.
*/
public Type getFieldType(int i) throws NoSuchElementException {
// some code goes here
if(i<0 || i>=tdItems.length){
throw new NoSuchElementException("pos " + i + " is not a valid index");
}
return tdItems[i].fieldType;
}
/**
* Find the index of the field with a given name.
*
* @param name
* name of the field.
* @return the index of the field that is first to have the given name.
* @throws NoSuchElementException
* if no field with a matching name is found.
*/
public int fieldNameToIndex(String name) throws NoSuchElementException {
// some code goes here
for(int i=0;i<tdItems.length;++i){
if(tdItems[i].fieldName.equals(name)){
return i;
}
}
throw new NoSuchElementException("not find fieldName " + name);
}
/**
* @return The size (in bytes) of tuples corresponding to this TupleDesc.
* Note that tuples from a given TupleDesc are of a fixed size.
*/
public int getSize() {
// some code goes here
int size = 0;
for(int i=0;i<tdItems.length;++i){
size += tdItems[i].fieldType.getLen();
}
return size;
}
/**
* Merge two TupleDescs into one, with td1.numFields + td2.numFields fields,
* with the first td1.numFields coming from td1 and the remaining from td2.
*
* @param td1
* The TupleDesc with the first fields of the new TupleDesc
* @param td2
* The TupleDesc with the last fields of the TupleDesc
* @return the new TupleDesc
*/
public static TupleDesc merge(TupleDesc td1, TupleDesc td2) {
// some code goes here
Type[] typeAr = new Type[td1.numFields() + td2.numFields()];
String[] fieldAr = new String[td1.numFields() + td2.numFields()];
for(int i=0;i<td1.numFields();++i){
typeAr[i] = td1.tdItems[i].fieldType;
fieldAr[i] = td1.tdItems[i].fieldName;
}
for(int i=0;i<td2.numFields();++i){
typeAr[i+td1.numFields()] = td2.tdItems[i].fieldType;
fieldAr[i+td1.numFields()] = td2.tdItems[i].fieldName;
}
return new TupleDesc(typeAr,fieldAr);
}
/**
* Compares the specified object with this TupleDesc for equality. Two
* TupleDescs are considered equal if they have the same number of items
* and if the i-th type in this TupleDesc is equal to the i-th type in o
* for every i.
*
* @param o
* the Object to be compared for equality with this TupleDesc.
* @return true if the object is equal to this TupleDesc.
*/
public boolean equals(Object o) {
// some code goes here
if(this.getClass().isInstance(o)) {
TupleDesc two = (TupleDesc) o;
if (numFields() == two.numFields()) {
for (int i = 0; i < numFields(); ++i) {
if (!tdItems[i].fieldType.equals(two.tdItems[i].fieldType)) {
return false;
}
}
return true;
}
}
return false;
}
public int hashCode() {
// If you want to use TupleDesc as keys for HashMap, implement this so
// that equal objects have equals hashCode() results
throw new UnsupportedOperationException("unimplemented");
}
/**
* Returns a String describing this descriptor. It should be of the form
* "fieldType[0](fieldName[0]), ..., fieldType[M](fieldName[M])", although
* the exact format does not matter.
*
* @return String describing this descriptor.
*/
public String toString() {
// some code goes here
StringBuilder sb = new StringBuilder();
for(int i=0;i<tdItems.length-1;++i){
sb.append(tdItems[i].fieldName + "(" + tdItems[i].fieldType + "), ");
}
sb.append(tdItems[tdItems.length-1].fieldName + "(" + tdItems[tdItems.length-1].fieldType + ")");
return sb.toString();
}
}
src/simpledb/Tuple代码如下：
package simpledb;
import java.io.Serializable;
import java.util.Arrays;
import java.util.Iterator;
/**
* Tuple maintains information about the contents of a tuple. Tuples have a
* specified schema specified by a TupleDesc object and contain Field objects
* with the data for each field.
*/
public class Tuple implements Serializable {
private static final long serialVersionUID = 1L;
private TupleDesc tupleDesc;
private RecordId recordId;
private final Field[] fields;
/**
* Create a new tuple with the specified schema (type).
*
* @param td
* the schema of this tuple. It must be a valid TupleDesc
* instance with at least one field.
*/
public Tuple(TupleDesc td) {
// some code goes here
tupleDesc = td;
fields = new Field[td.numFields()];
}
/**
* @return The TupleDesc representing the schema of this tuple.
*/
public TupleDesc getTupleDesc() {
// some code goes here
return tupleDesc;
}
/**
* @return The RecordId representing the location of this tuple on disk. May
* be null.
*/
public RecordId getRecordId() {
// some code goes here
return recordId;
}
/**
* Set the RecordId information for this tuple.
*
* @param rid
* the new RecordId for this tuple.
*/
public void setRecordId(RecordId rid) {
// some code goes here
recordId = rid;
}
/**
* Change the value of the ith field of this tuple.
*
* @param i
* index of the field to change. It must be a valid index.
* @param f
* new value for the field.
*/
public void setField(int i, Field f) {
// some code goes here
fields[i] = f;
}
/**
* @return the value of the ith field, or null if it has not been set.
*
* @param i
* field index to return. Must be a valid index.
*/
public Field getField(int i) {
// some code goes here
return fields[i];
}
/**
* Returns the contents of this Tuple as a string. Note that to pass the
* system tests, the format needs to be as follows:
*
* column1\tcolumn2\tcolumn3\t...\tcolumnN
*
* where \t is any whitespace (except a newline)
*/
public String toString() {
// some code goes here
StringBuilder sb = new StringBuilder();
for(int i=0;i<tupleDesc.numFields()-1;++i){
sb.append(fields[i].toString()+" ");
}
sb.append(fields[tupleDesc.numFields()-1].toString()+"\n");
return sb.toString();
}
/**
* @return
* An iterator which iterates over all the fields of this tuple
* */
public Iterator<Field> fields()
{
// some code goes here
return (Iterator<Field>) Arrays.asList(fields).iterator();
}
/**
* reset the TupleDesc of this tuple (only affecting the TupleDesc)
* */
public void resetTupleDesc(TupleDesc td)
{
// some code goes here
tupleDesc = td;
}
}
单元测试 ant runtest -Dtest=TupleDescTest 和 ant runtest -Dtest=TupleTest 的结果如下：
HemingbeardeMacBook-Pro:simple-db-hw hemingbear$ ant runtest -Dtest=TupleDescTest
Buildfile: /Users/hemingbear/Desktop/Code/6.830-Database/simple-db-hw/build.xml
compile:
testcompile:
runtest:
[junit] Running simpledb.TupleDescTest
[junit] Testsuite: simpledb.TupleDescTest
[junit] Tests run: 6, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.031 sec
[junit] Tests run: 6, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.031 sec
[junit]
[junit] Testcase: combine took 0.006 sec
[junit] Testcase: getType took 0.001 sec
[junit] Testcase: getSize took 0 sec
[junit] Testcase: nameToId took 0.01 sec
[junit] Testcase: numFields took 0 sec
[junit] Testcase: testEquals took 0 sec
BUILD SUCCESSFUL
Total time: 0 seconds
*******************************************************************************
HemingbeardeMacBook-Pro:simple-db-hw hemingbear$ ant runtest -Dtest=TupleTest
Buildfile: /Users/hemingbear/Desktop/Code/6.830-Database/simple-db-hw/build.xml
compile:
testcompile:
runtest:
[junit] Running simpledb.TupleTest
[junit] Testsuite: simpledb.TupleTest
[junit] Tests run: 3, Failures: 0, Errors: 1, Skipped: 0, Time elapsed: 0.026 sec
[junit] Tests run: 3, Failures: 0, Errors: 1, Skipped: 0, Time elapsed: 0.026 sec
[junit]
[junit] Testcase: modifyFields took 0.01 sec
[junit] Testcase: getTupleDesc took 0 sec
[junit] Testcase: modifyRecordId took 0.002 sec
[junit] Caused an ERROR
[junit] modifyRecordId() test failed due to RecordId.equals() not being implemented. This is not required for Lab 1, but should pass when you do implement the RecordId class.
[junit] java.lang.UnsupportedOperationException: modifyRecordId() test failed due to RecordId.equals() not being implemented. This is not required for Lab 1, but should pass when you do implement the RecordId class.
[junit] at simpledb.TupleTest.modifyRecordId(TupleTest.java:54)
[junit]
BUILD FAILED
2.3. Catalog
catalog类描述的是数据库实例。包含了数据库现有的表信息以及表的schema信息。现在需要实现添加新表的功能，以及从特定的表中提取信息。提取信息时通过表对应的TupleDesc对象决定操作的字段类型和数量。
全局catalog是分配给整个SimpleDB进程的Catalog类一个实例，可以通过方法Database.getCatalog()获得，global buffer pool可以通过方法Database.getBufferPool()获得。
Exercise 2
Implement the skeleton methods in:
- src/simpledb/Catalog.java
At this point, your code should pass the unit tests in CatalogTest.
src/simpledb/Catalog.java代码如下
package simpledb;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
/**
* The Catalog keeps track of all available tables in the database and their
* associated schemas.
* For now, this is a stub catalog that must be populated with tables by a
* user program before it can be used -- eventually, this should be converted
* to a catalog that reads a catalog table from disk.
*
* @Threadsafe
*/
public class Catalog {
private final ConcurrentHashMap<Integer,Table> hashTable;
private static class Table{
private static final long serialVersionUID = 1L;
public final DbFile dbFile;
public final String tableName;
public final String pk;
public Table(DbFile file,String name,String pkeyField){
dbFile = file;
tableName = name;
pk = pkeyField;
}
public String toString(){
return tableName + "(" + dbFile.getId() + ":" + pk +")";
}
}
/**
* Constructor.
* Creates a new, empty catalog.
*/
public Catalog() {
// some code goes here
hashTable = new ConcurrentHashMap<Integer,Table>();
}
/**
* Add a new table to the catalog.
* This table's contents are stored in the specified DbFile.
* @param file the contents of the table to add; file.getId() is the identfier of
* this file/tupledesc param for the calls getTupleDesc and getFile
* @param name the name of the table -- may be an empty string. May not be null. If a name
* conflict exists, use the last table to be added as the table for a given name.
* @param pkeyField the name of the primary key field
*/
public void addTable(DbFile file, String name, String pkeyField) {
// some code goes here
Table t = new Table(file,name,pkeyField);
hashTable.put(file.getId(),t);
}
public void addTable(DbFile file, String name) {
addTable(file, name, "");
}
/**
* Add a new table to the catalog.
* This table has tuples formatted using the specified TupleDesc and its
* contents are stored in the specified DbFile.
* @param file the contents of the table to add; file.getId() is the identfier of
* this file/tupledesc param for the calls getTupleDesc and getFile
*/
public void addTable(DbFile file) {
addTable(file, (UUID.randomUUID()).toString());
}
/**
* Return the id of the table with a specified name,
* @throws NoSuchElementException if the table doesn't exist
*/
public int getTableId(String name) throws NoSuchElementException {
// some code goes here
Integer res = hashTable.searchValues(1,value->{
if(value.tableName.equals(name)){
return value.dbFile.getId();
}
return null;
});
if(res != null){
return res.intValue();
}else{
throw new NoSuchElementException("not found id for table " + name);
}
}
/**
* Returns the tuple descriptor (schema) of the specified table
* @param tableid The id of the table, as specified by the DbFile.getId()
* function passed to addTable
* @throws NoSuchElementException if the table doesn't exist
*/
public TupleDesc getTupleDesc(int tableid) throws NoSuchElementException {
// some code goes here
Table t = hashTable.getOrDefault(tableid,null);
if(t != null){
return t.dbFile.getTupleDesc();
}else{
throw new NoSuchElementException("not found tuple desc for table " + tableid);
}
}
/**
* Returns the DbFile that can be used to read the contents of the
* specified table.
* @param tableid The id of the table, as specified by the DbFile.getId()
* function passed to addTable
*/
public DbFile getDatabaseFile(int tableid) throws NoSuchElementException {
// some code goes here
Table t = hashTable.getOrDefault(tableid,null);
if(t != null){
return t.dbFile;
}else{
throw new NoSuchElementException("not found db file for table " + tableid);
}
}
public String getPrimaryKey(int tableid) {
// some code goes here
Table t = hashTable.getOrDefault(tableid,null);
if(t != null){
return t.pk;
}else{
throw new NoSuchElementException("not found primary key for table " + tableid);
}
}
public Iterator<Integer> tableIdIterator() {
// some code goes here
return hashTable.keySet().iterator();
}
public String getTableName(int id) {
// some code goes here
Table t = hashTable.getOrDefault(id,null);
if(t != null){
return t.tableName;
}else{
throw new NoSuchElementException("not found name for table " + id);
}
}
/** Delete all tables from the catalog */
public void clear() {
// some code goes here
hashTable.clear();
}
/**
* Reads the schema from a file and creates the appropriate tables in the database.
* @param catalogFile
*/
public void loadSchema(String catalogFile) {
String line = "";
String baseFolder=new File(new File(catalogFile).getAbsolutePath()).getParent();
try {
BufferedReader br = new BufferedReader(new FileReader(new File(catalogFile)));
while ((line = br.readLine()) != null) {
//assume line is of the format name (field type, field type, ...)
String name = line.substring(0, line.indexOf("(")).trim();
//System.out.println("TABLE NAME: " + name);
String fields = line.substring(line.indexOf("(") + 1, line.indexOf(")")).trim();
String[] els = fields.split(",");
ArrayList<String> names = new ArrayList<String>();
ArrayList<Type> types = new ArrayList<Type>();
String primaryKey = "";
for (String e : els) {
String[] els2 = e.trim().split(" ");
names.add(els2[0].trim());
if (els2[1].trim().toLowerCase().equals("int"))
types.add(Type.INT_TYPE);
else if (els2[1].trim().toLowerCase().equals("string"))
types.add(Type.STRING_TYPE);
else {
System.out.println("Unknown type " + els2[1]);
System.exit(0);
}
if (els2.length == 3) {
if (els2[2].trim().equals("pk"))
primaryKey = els2[0].trim();
else {
System.out.println("Unknown annotation " + els2[2]);
System.exit(0);
}
}
}
Type[] typeAr = types.toArray(new Type[0]);
String[] namesAr = names.toArray(new String[0]);
TupleDesc t = new TupleDesc(typeAr, namesAr);
HeapFile tabHf = new HeapFile(new File(baseFolder+"/"+name + ".dat"), t);
addTable(tabHf,name,primaryKey);
System.out.println("Added table : " + name + " with schema " + t);
}
} catch (IOException e) {
e.printStackTrace();
System.exit(0);
} catch (IndexOutOfBoundsException e) {
System.out.println ("Invalid catalog entry : " + line);
System.exit(0);
}
}
}
单元测试 ant runtest -Dtest=CatalogTest结果：
HemingbeardeMacBook-Pro:simple-db-hw hemingbear$ ant runtest -Dtest=CatalogTest
Buildfile: /Users/hemingbear/Desktop/Code/6.830-Database/simple-db-hw/build.xml
compile:
[depend] Deleted 15 out of date files in 0 seconds
[javac] Compiling 14 source files to /Users/hemingbear/Desktop/Code/6.830-Database/simple-db-hw/bin/src
testcompile:
runtest:
[junit] Running simpledb.CatalogTest
[junit] Testsuite: simpledb.CatalogTest
[junit] Tests run: 5, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.025 sec
[junit] Tests run: 5, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.025 sec
[junit]
[junit] Testcase: handleDuplicateNames took 0.008 sec
[junit] Testcase: handleDuplicateIds took 0 sec
[junit] Testcase: getTableId took 0.001 sec
[junit] Testcase: getDatabaseFile took 0 sec
[junit] Testcase: getTupleDesc took 0.001 sec
BUILD SUCCESSFUL
Total time: 1 second
2.4. BufferPool
buffer pool（在SimpleDB中是BufferPool类）负责将内存最近读过的物理页缓存下来。所有的读写操作通过buffer pool读写硬盘上不同文件，BufferPool里的numPages参数确定了读取的固定页数，在之后的lab中，需要实现淘汰机制(eviction policy)。在这个lab中，只需要实现构造器和BufferPool.getPage()方法，BufferPool应该存取最多numPages个物理页，当前lab中如果页的数量超过numPages，先不实现eviction policy，先扔出一个DbException错误。
Database类提供了一个静态方法Database.getBufferPool()，返回整个SimpleDB进程的BufferPool实例引用。
Exercise 3
Implement the
getPage()method in:
- src/simpledb/BufferPool.java
We have not provided unit tests for BufferPool. The functionality you implemented will be tested in the implementation of HeapFile below. You should use the
DbFile.readPagemethod to access pages of a DbFile.
src/simpledb/BufferPool.java代码如下:
private static final int DEFAULT_PAGE_SIZE = 4096;
private static int pageSize = DEFAULT_PAGE_SIZE;
/** Default number of pages passed to the constructor. This is used by
other classes. BufferPool should use the numPages argument to the
constructor instead. */
public static final int DEFAULT_PAGES = 50;
private final int numPages;
private final ConcurrentHashMap<Integer,Page> pageStore;
/**
* Creates a BufferPool that caches up to numPages pages.
*
* @param numPages maximum number of pages in this buffer pool.
*/
public BufferPool(int numPages) {
// some code goes here
this.numPages = numPages;
pageStore = new ConcurrentHashMap<Integer,Page>();
}
/**
* Retrieve the specified page with the associated permissions.
* Will acquire a lock and may block if that lock is held by another
* transaction.
* <p>
* The retrieved page should be looked up in the buffer pool. If it
* is present, it should be returned. If it is not present, it should
* be added to the buffer pool and returned. If there is insufficient
* space in the buffer pool, a page should be evicted and the new page
* should be added in its place.
*
* @param tid the ID of the transaction requesting the page
* @param pid the ID of the requested page
* @param perm the requested permissions on the page
*/
public Page getPage(TransactionId tid, PageId pid, Permissions perm)
throws TransactionAbortedException, DbException {
// some code goes here
if(!pageStore.containsKey(pid.hashCode())){
DbFile dbfile = Database.getCatalog().getDatabaseFile(pid.getTableId());
Page page = dbfile.readPage(pid);
pageStore.put(pid.hashCode(),page);
}
return pageStore.get(pid.hashCode());
}2.5. HeapFile access method
访问方法提供了硬盘读写数据的方式。通常的访问方法包括heap files(没排序的行数据文件)和B-trees，在这里，只需要实现heap file访问方法。
HeapFile对象包含一组“物理页”，每一个页大小固定，大小由BufferPool.DEFAULT_PAGE_SIZE定义，页内存储行数据。在SimpleDB中，数据库中每一个表对应一个HeapFile对象，HeapFile中每一页包含很多个slot，每个slot是留给一行的位置。除了这些slots，每个物理页包含一个header，heade是每个tuple slot的bitmap。如果bitmap中对应的某个tuple的bit是1，则这个tuple是有效的，否则无效（被删除或者没被初始化）。HeapFile对象中的物理页的类型是HeapPage，这是一种Page的接口，物理页是存储在buffer pool中，通过HeapFile类读写。
SimpleDB数据库的每个tuple需要tuple size * 8 bits 的内容大小和1 bit的header大小。因此，在一页中可以包含的tuple数量计算公式是：_tuples per page_ = floor((_page size_ * 8) / (_tuple size_ * 8 + 1))。其中，tuple size是页中单个tuple 的bytes大小。
一旦知道了每页中能够保存的tuple数量，需要的header的物理大小是：headerBytes = ceiling(tupsPerPage/8)。
bitmap中，low bits代表了先填入的slots状态。因此，第一个headerByte的最小bit代表了第一个slot是否使用，第二小的bit代表了第二个slot是否使用。同样，最大headerByte的一些高位可能不与slot存在映射关系，只是满足headerBytes的ceiling。
提示：所有的java虚拟机都是big-endian。
- 大端模式是指数据的低位保存在内存的高地址中，而数据的高位保存在内存的低地址中.
- 小端模式是指数据的低位保存在内存的低地址中，而数据的高位保存在内存的高地址中。
Exercise 4
Implement the skeleton methods in:
- src/simpledb/HeapPageId.java
- src/simpledb/RecordID.java
- src/simpledb/HeapPage.java
Although you will not use them directly in Lab 1, we ask you to implement getNumEmptySlots() and isSlotUsed() in HeapPage. These require pushing around bits in the page header. You may find it helpful to look at the other methods that have been provided in HeapPage or in src/simpledb/HeapFileEncoder.java to understand the layout of pages.
You will also need to implement an Iterator over the tuples in the page, which may involve an auxiliary class or data structure.
At this point, your code should pass the unit tests in HeapPageIdTest, RecordIDTest, and HeapPageReadTest.
After you have implemented HeapPage, you will write methods for HeapFile in this lab to calculate the number of pages in a file and to read a page from the file. You will then be able to fetch tuples from a file stored on disk.
src/simpledb/HeapPageId.java代码如下：
package simpledb;
/** Unique identifier for HeapPage objects. */
public class HeapPageId implements PageId {
private final int tableId;
private final int pgNo;
/**
* Constructor. Create a page id structure for a specific page of a
* specific table.
*
* @param tableId The table that is being referenced
* @param pgNo The page number in that table.
*/
public HeapPageId(int tableId, int pgNo) {
// some code goes here
this.tableId = tableId;
this.pgNo = pgNo;
}
/** @return the table associated with this PageId */
public int getTableId() {
// some code goes here
return tableId;
}
/**
* @return the page number in the table getTableId() associated with
* this PageId
*/
public int getPageNumber() {
// some code goes here
return pgNo;
}
/**
* @return a hash code for this page, represented by the concatenation of
* the table number and the page number (needed if a PageId is used as a
* key in a hash table in the BufferPool, for example.)
* @see BufferPool
*/
public int hashCode() {
// some code goes here
String hash = "" + tableId +pgNo;
return hash.hashCode();
}
/**
* Compares one PageId to another.
*
* @param o The object to compare against (must be a PageId)
* @return true if the objects are equal (e.g., page numbers and table
* ids are the same)
*/
public boolean equals(Object o) {
// some code goes here
if(o instanceof PageId){
PageId pi = (PageId) o;
if(pi.getTableId() == tableId && pi.getPageNumber() == pgNo){
return true;
}
}
return false;
}
/**
* Return a representation of this object as an array of
* integers, for writing to disk. Size of returned array must contain
* number of integers that corresponds to number of args to one of the
* constructors.
*/
public int[] serialize() {
int data[] = new int[2];
data[0] = getTableId();
data[1] = getPageNumber();
return data;
}
}
src/simpledb/RecordID.java代码如下：
package simpledb;
import java.io.Serializable;
/**
* A RecordId is a reference to a specific tuple on a specific page of a
* specific table.
*/
public class RecordId implements Serializable {
private static final long serialVersionUID = 1L;
private final PageId pid;
private final int tupleno;
/**
* Creates a new RecordId referring to the specified PageId and tuple
* number.
*
* @param pid
* the pageid of the page on which the tuple resides
* @param tupleno
* the tuple number within the page.
*/
public RecordId(PageId pid, int tupleno) {
// some code goes here
this.pid = pid;
this.tupleno = tupleno;
}
/**
* @return the tuple number this RecordId references.
*/
public int getTupleNumber() {
// some code goes here
return tupleno;
}
/**
* @return the page id this RecordId references.
*/
public PageId getPageId() {
// some code goes here
return pid;
}
/**
* Two RecordId objects are considered equal if they represent the same
* tuple.
*
* @return True if this and o represent the same tuple
*/
@Override
public boolean equals(Object o) {
// some code goes here
if(o instanceof RecordId){
RecordId ro = (RecordId) o;
if(ro.getPageId().equals(pid) && ro.getTupleNumber() == tupleno){
return true;
}
}
return false;
}
/**
* You should implement the hashCode() so that two equal RecordId instances
* (with respect to equals()) have the same hashCode().
*
* @return An int that is the same for equal RecordId objects.
*/
@Override
public int hashCode() {
// some code goes here
String hash = "" + pid.getTableId()+pid.getPageNumber() + tupleno;
return hash.hashCode();
}
}
src/simpledb/HeapPage.java代码如下：
package simpledb;
import java.util.*;
import java.io.*;
/**
* Each instance of HeapPage stores data for one page of HeapFiles and
* implements the Page interface that is used by BufferPool.
*
* @see HeapFile
* @see BufferPool
*
*/
public class HeapPage implements Page {
final HeapPageId pid;
final TupleDesc td;
final byte header[];
final Tuple tuples[];
final int numSlots;
byte[] oldData;
private final Byte oldDataLock=new Byte((byte)0);
/**
* Create a HeapPage from a set of bytes of data read from disk.
* The format of a HeapPage is a set of header bytes indicating
* the slots of the page that are in use, some number of tuple slots.
* Specifically, the number of tuples is equal to: <p>
* floor((BufferPool.getPageSize()*8) / (tuple size * 8 + 1))
* <p> where tuple size is the size of tuples in this
* database table, which can be determined via {@link Catalog#getTupleDesc}.
* The number of 8-bit header words is equal to:
* <p>
* ceiling(no. tuple slots / 8)
* <p>
* @see Database#getCatalog
* @see Catalog#getTupleDesc
* @see BufferPool#getPageSize()
*/
public HeapPage(HeapPageId id, byte[] data) throws IOException {
this.pid = id;
this.td = Database.getCatalog().getTupleDesc(id.getTableId());
this.numSlots = getNumTuples();
DataInputStream dis = new DataInputStream(new ByteArrayInputStream(data));
// allocate and read the header slots of this page
header = new byte[getHeaderSize()];
for (int i=0; i<header.length; i++)
header[i] = dis.readByte();
tuples = new Tuple[numSlots];
try{
// allocate and read the actual records of this page
for (int i=0; i<tuples.length; i++)
tuples[i] = readNextTuple(dis,i);
}catch(NoSuchElementException e){
e.printStackTrace();
}
dis.close();
setBeforeImage();
}
/** Retrieve the number of tuples on this page.
@return the number of tuples on this page
*/
private int getNumTuples() {
// some code goes here
//_tuples per page_ = floor((_page size_ * 8) / (_tuple size_ * 8 + 1))
int num = (int)Math.floor((BufferPool.getPageSize()*8*1.0)/(td.getSize()*8+1));
return num;
}
/**
* Computes the number of bytes in the header of a page in a HeapFile with each tuple occupying tupleSize bytes
* @return the number of bytes in the header of a page in a HeapFile with each tuple occupying tupleSize bytes
*/
private int getHeaderSize() {
// some code goes here
// headerBytes = ceiling(tupsPerPage/8)
return (int)Math.ceil(getNumTuples()*1.0/8);
}
/** Return a view of this page before it was modified
-- used by recovery */
public HeapPage getBeforeImage(){
try {
byte[] oldDataRef = null;
synchronized(oldDataLock)
{
oldDataRef = oldData;
}
return new HeapPage(pid,oldDataRef);
} catch (IOException e) {
e.printStackTrace();
//should never happen -- we parsed it OK before!
System.exit(1);
}
return null;
}
public void setBeforeImage() {
synchronized(oldDataLock)
{
oldData = getPageData().clone();
}
}
/**
* @return the PageId associated with this page.
*/
public HeapPageId getId() {
// some code goes here
return pid;
}
/**
* Suck up tuples from the source file.
*/
private Tuple readNextTuple(DataInputStream dis, int slotId) throws NoSuchElementException {
// if associated bit is not set, read forward to the next tuple, and
// return null.
if (!isSlotUsed(slotId)) {
for (int i=0; i<td.getSize(); i++) {
try {
dis.readByte();
} catch (IOException e) {
throw new NoSuchElementException("error reading empty tuple");
}
}
return null;
}
// read fields in the tuple
Tuple t = new Tuple(td);
RecordId rid = new RecordId(pid, slotId);
t.setRecordId(rid);
try {
for (int j=0; j<td.numFields(); j++) {
Field f = td.getFieldType(j).parse(dis);
t.setField(j, f);
}
} catch (java.text.ParseException e) {
e.printStackTrace();
throw new NoSuchElementException("parsing error!");
}
return t;
}
/**
* Generates a byte array representing the contents of this page.
* Used to serialize this page to disk.
* <p>
* The invariant here is that it should be possible to pass the byte
* array generated by getPageData to the HeapPage constructor and
* have it produce an identical HeapPage object.
*
* @see #HeapPage
* @return A byte array correspond to the bytes of this page.
*/
public byte[] getPageData() {
int len = BufferPool.getPageSize();
ByteArrayOutputStream baos = new ByteArrayOutputStream(len);
DataOutputStream dos = new DataOutputStream(baos);
// create the header of the page
for (int i=0; i<header.length; i++) {
try {
dos.writeByte(header[i]);
} catch (IOException e) {
// this really shouldn't happen
e.printStackTrace();
}
}
// create the tuples
for (int i=0; i<tuples.length; i++) {
// empty slot
if (!isSlotUsed(i)) {
for (int j=0; j<td.getSize(); j++) {
try {
dos.writeByte(0);
} catch (IOException e) {
e.printStackTrace();
}
}
continue;
}
// non-empty slot
for (int j=0; j<td.numFields(); j++) {
Field f = tuples[i].getField(j);
try {
f.serialize(dos);
} catch (IOException e) {
e.printStackTrace();
}
}
}
// padding
int zerolen = BufferPool.getPageSize() - (header.length + td.getSize() * tuples.length); //- numSlots * td.getSize();
byte[] zeroes = new byte[zerolen];
try {
dos.write(zeroes, 0, zerolen);
} catch (IOException e) {
e.printStackTrace();
}
try {
dos.flush();
} catch (IOException e) {
e.printStackTrace();
}
return baos.toByteArray();
}
/**
* Static method to generate a byte array corresponding to an empty
* HeapPage.
* Used to add new, empty pages to the file. Passing the results of
* this method to the HeapPage constructor will create a HeapPage with
* no valid tuples in it.
*
* @return The returned ByteArray.
*/
public static byte[] createEmptyPageData() {
int len = BufferPool.getPageSize();
return new byte[len]; //all 0
}
/**
* Delete the specified tuple from the page; the corresponding header bit should be updated to reflect
* that it is no longer stored on any page.
* @throws DbException if this tuple is not on this page, or tuple slot is
* already empty.
* @param t The tuple to delete
*/
public void deleteTuple(Tuple t) throws DbException {
// some code goes here
// not necessary for lab1
}
/**
* Adds the specified tuple to the page; the tuple should be updated to reflect
* that it is now stored on this page.
* @throws DbException if the page is full (no empty slots) or tupledesc
* is mismatch.
* @param t The tuple to add.
*/
public void insertTuple(Tuple t) throws DbException {
// some code goes here
// not necessary for lab1
}
/**
* Marks this page as dirty/not dirty and record that transaction
* that did the dirtying
*/
public void markDirty(boolean dirty, TransactionId tid) {
// some code goes here
// not necessary for lab1
}
/**
* Returns the tid of the transaction that last dirtied this page, or null if the page is not dirty
*/
public TransactionId isDirty() {
// some code goes here
// Not necessary for lab1
return null;
}
/**
* Returns the number of empty slots on this page.
*/
public int getNumEmptySlots() {
// some code goes here
int cnt = 0;
for(int i=0;i<numSlots;++i){
if(!isSlotUsed(i)){
++cnt;
}
}
return cnt;
}
/**
* Returns true if associated slot on this page is filled.
*/
public boolean isSlotUsed(int i) {
// some code goes here
// use bitmap
int quot = i/8;
int remainder = i%8;
int bitidx = header[quot];
int bit = (bitidx>>remainder) & 1;
return bit == 1;
}
/**
* Abstraction to fill or clear a slot on this page.
*/
private void markSlotUsed(int i, boolean value) {
// some code goes here
// not necessary for lab1
}
/**
* @return an iterator over all tuples on this page (calling remove on this iterator throws an UnsupportedOperationException)
* (note that this iterator shouldn't return tuples in empty slots!)
*/
public Iterator<Tuple> iterator() {
// some code goes here
ArrayList<Tuple> filledTuples = new ArrayList<Tuple>();
for(int i=0;i<numSlots;++i){
if(isSlotUsed(i)){
filledTuples.add(tuples[i]);
}
}
return filledTuples.iterator();
}
}
ant runtest -Dtest=HeapPageIdTest 和ant runtest -Dtest=TupleDescTest以及ant runtest -Dtest=HeapPageReadTest都BUILD SUCCESSFUL。
Exercise 5
Implement the skeleton methods in:
- src/simpledb/HeapFile.java
To read a page from disk, you will first need to calculate the correct offset in the file. Hint: you will need random access to the file in order to read and write pages at arbitrary offsets. You should not call BufferPool methods when reading a page from disk.
You will also need to implement the `HeapFile.iterator()` method, which should iterate through through the tuples of each page in the HeapFile. The iterator must use the `BufferPool.getPage()` method to access pages in the `HeapFile`. This method loads the page into the buffer pool and will eventually be used (in a later lab) to implement locking-based concurrency control and recovery. Do not load the entire table into memory on the open() call -- this will cause an out of memory error for very large tables.
At this point, your code should pass the unit tests in HeapFileReadTest.
src/simpledb/HeapFile.java代码如下：
package simpledb;
import java.io.*;
import java.util.*;
/**
* HeapFile is an implementation of a DbFile that stores a collection of tuples
* in no particular order. Tuples are stored on pages, each of which is a fixed
* size, and the file is simply a collection of those pages. HeapFile works
* closely with HeapPage. The format of HeapPages is described in the HeapPage
* constructor.
*
* @see simpledb.HeapPage#HeapPage
* @author Sam Madden
*/
public class HeapFile implements DbFile {
private final File file;
private final TupleDesc td;
/**
* Constructs a heap file backed by the specified file.
*
* @param f
* the file that stores the on-disk backing store for this heap
* file.
*/
public HeapFile(File f, TupleDesc td) {
// some code goes here
this.file = f;
this.td = td;
}
/**
* Returns the File backing this HeapFile on disk.
*
* @return the File backing this HeapFile on disk.
*/
public File getFile() {
// some code goes here
return file;
}
/**
* Returns an ID uniquely identifying this HeapFile. Implementation note:
* you will need to generate this tableid somewhere to ensure that each
* HeapFile has a "unique id," and that you always return the same value for
* a particular HeapFile. We suggest hashing the absolute file name of the
* file underlying the heapfile, i.e. f.getAbsoluteFile().hashCode().
*
* @return an ID uniquely identifying this HeapFile.
*/
public int getId() {
// some code goes here
return file.getAbsoluteFile().hashCode();
}
/**
* Returns the TupleDesc of the table stored in this DbFile.
*
* @return TupleDesc of this DbFile.
*/
public TupleDesc getTupleDesc() {
// some code goes here
return td;
}
// see DbFile.java for javadocs
public Page readPage(PageId pid) {
// some code goes here
int tableId = pid.getTableId();
int pgNo = pid.getPageNumber();
RandomAccessFile f = null;
try{
f = new RandomAccessFile(file,"r");
if((pgNo+1)*BufferPool.getPageSize() > f.length()){
f.close();
throw new IllegalArgumentException(String.format("table %d page %d is invalid", tableId, pgNo));
}
byte[] bytes = new byte[BufferPool.getPageSize()];
f.seek(pgNo * BufferPool.getPageSize());
// big end
int read = f.read(bytes,0,BufferPool.getPageSize());
if(read != BufferPool.getPageSize()){
throw new IllegalArgumentException(String.format("table %d page %d read %d bytes", tableId, pgNo, read));
}
HeapPageId id = new HeapPageId(pid.getTableId(),pid.getPageNumber());
return new HeapPage(id,bytes);
}catch (IOException e){
e.printStackTrace();
}finally {
try{
f.close();
}catch (Exception e){
e.printStackTrace();
}
}
throw new IllegalArgumentException(String.format("table %d page %d is invalid", tableId, pgNo));
}
// see DbFile.java for javadocs
public void writePage(Page page) throws IOException {
// some code goes here
// not necessary for lab1
}
/**
* Returns the number of pages in this HeapFile.
*/
public int numPages() {
// some code goes here
int num = (int)Math.floor(file.length()*1.0/BufferPool.getPageSize());
return num;
}
// see DbFile.java for javadocs
public ArrayList<Page> insertTuple(TransactionId tid, Tuple t)
throws DbException, IOException, TransactionAbortedException {
// some code goes here
return null;
// not necessary for lab1
}
// see DbFile.java for javadocs
public ArrayList<Page> deleteTuple(TransactionId tid, Tuple t) throws DbException,
TransactionAbortedException {
// some code goes here
return null;
// not necessary for lab1
}
// see DbFile.java for javadocs
public DbFileIterator iterator(TransactionId tid) {
// some code goes here
return new HeapFileIterator(this,tid);
}
private static final class HeapFileIterator implements DbFileIterator{
private final HeapFile heapFile;
private final TransactionId tid;
private Iterator<Tuple> it;
private int whichPage;
public HeapFileIterator(HeapFile file,TransactionId tid){
this.heapFile = file;
this.tid = tid;
}
@Override
public void open() throws DbException, TransactionAbortedException {
// TODO Auto-generated method stub
whichPage = 0;
it = getPageTuples(whichPage);
}
private Iterator<Tuple> getPageTuples(int pageNumber) throws TransactionAbortedException, DbException{
if(pageNumber >= 0 && pageNumber < heapFile.numPages()){
HeapPageId pid = new HeapPageId(heapFile.getId(),pageNumber);
HeapPage page = (HeapPage)Database.getBufferPool().getPage(tid, pid, Permissions.READ_ONLY);
return page.iterator();
}else{
throw new DbException(String.format("heapfile %d does not contain page %d!", pageNumber,heapFile.getId()));
}
}
@Override
public boolean hasNext() throws DbException, TransactionAbortedException {
// TODO Auto-generated method stub
if(it == null){
return false;
}
if(!it.hasNext()){
if(whichPage < (heapFile.numPages()-1)){
whichPage++;
it = getPageTuples(whichPage);
return it.hasNext();
}else{
return false;
}
}else{
return true;
}
}
@Override
public Tuple next() throws DbException, TransactionAbortedException, NoSuchElementException {
// TODO Auto-generated method stub
if(it == null || !it.hasNext()){
throw new NoSuchElementException();
}
return it.next();
}
@Override
public void rewind() throws DbException, TransactionAbortedException {
// TODO Auto-generated method stub
close();
open();
}
@Override
public void close() {
// TODO Auto-generated method stub
it = null;
}
}
}
ant runtest -Dtest=HeapFileReadTest的结果：
HemingbeardeMacBook-Pro:simple-db-hw hemingbear$ ant runtest -Dtest=HeapFileReadTest
Buildfile: /Users/hemingbear/Desktop/Code/6.830-Database/simple-db-hw/build.xml
compile:
[depend] Deleted 5 out of date files in 0 seconds
[javac] Compiling 5 source files to /Users/hemingbear/Desktop/Code/6.830-Database/simple-db-hw/bin/src
testcompile:
runtest:
[junit] Running simpledb.HeapFileReadTest
[junit] Testsuite: simpledb.HeapFileReadTest
[junit] Tests run: 6, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.053 sec
[junit] Tests run: 6, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.053 sec
[junit]
[junit] Testcase: getId took 0.023 sec
[junit] Testcase: testIteratorClose took 0.009 sec
[junit] Testcase: getTupleDesc took 0.001 sec
[junit] Testcase: numPages took 0.001 sec
[junit] Testcase: readPage took 0.002 sec
[junit] Testcase: testIteratorBasic took 0.002 sec
BUILD SUCCESSFUL
Total time: 1 second2.6. Operators
数据库Operators(操作符)负责查询语句的实际执行。在SimpleDB中，Operators是基于迭代器实现的，每种iterator实现了一个DbIterator接口。
SimpleDP和程序交互的过程中，现在root operator上调用getNext，之后在子节点上继续调用getNext，一直下去，直到leaf operators 被调用。他们从硬盘上读取tuples，并在树结构上传递。
这个lab中，只需要实现一个SimpleDB operator。
Exercise 6.
Implement the skeleton methods in:
- src/simpledb/SeqScan.java
This operator sequentially scans all of the tuples from the pages of the table specified by the
tableidin the constructor. This operator should access tuples through theDbFile.iterator()method.At this point, you should be able to complete the ScanTest system test. Good work!
You will fill in other operators in subsequent labs.
src/simpledb/SeqScan.java代码如下：
package simpledb;
import java.util.*;
/**
* SeqScan is an implementation of a sequential scan access method that reads
* each tuple of a table in no particular order (e.g., as they are laid out on
* disk).
*/
public class SeqScan implements OpIterator {
private static final long serialVersionUID = 1L;
private final TransactionId tid;
private int tableId;
private String tableAlias;
private DbFileIterator it;
/**
* Creates a sequential scan over the specified table as a part of the
* specified transaction.
*
* @param tid
* The transaction this scan is running as a part of.
* @param tableid
* the table to scan.
* @param tableAlias
* the alias of this table (needed by the parser); the returned
* tupleDesc should have fields with name tableAlias.fieldName
* (note: this class is not responsible for handling a case where
* tableAlias or fieldName are null. It shouldn't crash if they
* are, but the resulting name can be null.fieldName,
* tableAlias.null, or null.null).
*/
public SeqScan(TransactionId tid, int tableid, String tableAlias) {
// some code goes here
this.tid = tid;
this.tableId = tableid;
this.tableAlias = tableAlias;
}
/**
* @return
* return the table name of the table the operator scans. This should
* be the actual name of the table in the catalog of the database
* */
public String getTableName() {
return Database.getCatalog().getTableName(tableId);
}
/**
* @return Return the alias of the table this operator scans.
* */
public String getAlias()
{
// some code goes here
return tableAlias;
}
/**
* Reset the tableid, and tableAlias of this operator.
* @param tableid
* the table to scan.
* @param tableAlias
* the alias of this table (needed by the parser); the returned
* tupleDesc should have fields with name tableAlias.fieldName
* (note: this class is not responsible for handling a case where
* tableAlias or fieldName are null. It shouldn't crash if they
* are, but the resulting name can be null.fieldName,
* tableAlias.null, or null.null).
*/
public void reset(int tableid, String tableAlias) {
// some code goes here
this.tableId = tableid;
this.tableAlias = tableAlias;
}
public SeqScan(TransactionId tid, int tableId) {
this(tid, tableId, Database.getCatalog().getTableName(tableId));
}
public void open() throws DbException, TransactionAbortedException {
// some code goes here
it = Database.getCatalog().getDatabaseFile(tableId).iterator(tid);
it.open();
}
/**
* Returns the TupleDesc with field names from the underlying HeapFile,
* prefixed with the tableAlias string from the constructor. This prefix
* becomes useful when joining tables containing a field(s) with the same
* name. The alias and name should be separated with a "." character
* (e.g., "alias.fieldName").
*
* @return the TupleDesc with field names from the underlying HeapFile,
* prefixed with the tableAlias string from the constructor.
*/
public TupleDesc getTupleDesc() {
// some code goes here
return Database.getCatalog().getTupleDesc(tableId);
}
public boolean hasNext() throws TransactionAbortedException, DbException {
// some code goes here
if(it == null){
return false;
}
return it.hasNext();
}
public Tuple next() throws NoSuchElementException,
TransactionAbortedException, DbException {
// some code goes here
if(it == null){
throw new NoSuchElementException("no next tuple");
}
Tuple t = it.next();
if(t == null){
throw new NoSuchElementException("no next tuple");
}
return t;
}
public void close() {
// some code goes here
it = null;
}
public void rewind() throws DbException, NoSuchElementException,
TransactionAbortedException {
// some code goes here
it.rewind();
}
}
ant runsystest -Dtest=ScanTest 的结果：
HemingbeardeMacBook-Pro:simple-db-hw hemingbear$ ant runsystest -Dtest=ScanTest
Buildfile: /Users/hemingbear/Desktop/Code/6.830-Database/simple-db-hw/build.xml
compile:
testcompile:
runsystest:
[junit] Running simpledb.systemtest.ScanTest
[junit] Testsuite: simpledb.systemtest.ScanTest
[junit] Tests run: 3, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.513 sec
[junit] Tests run: 3, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.513 sec
[junit]
[junit] Testcase: testSmall took 0.357 sec
[junit] Testcase: testRewind took 0.003 sec
[junit] Testcase: testCache took 0.14 sec
BUILD SUCCESSFUL
Total time: 1 second2.7. A simple query
这一小节是要说明怎么综合上面的部分，执行一次简单的查询。
假如有一个数据文件"some_data_file.txt"，内容如下：
1,1,1
2,2,2
3,4,4可以将它转换成SimpleDB可以查询的二进制文件，转换格式为```java -jar dist/simpledb.jar convert some_data_file.txt 3```。其中参数3是告诉转换器输入有3列。
下列代码实现了对文件的简单查询，效果等同于SQL语句的`SELECT * FROM some_data_file`。
package simpledb;
import java.io.*;
public class test {
public static void main(String[] argv) {
// construct a 3-column table schema
Type types[] = new Type[]{ Type.INT_TYPE, Type.INT_TYPE, Type.INT_TYPE };
String names[] = new String[]{ "field0", "field1", "field2" };
TupleDesc descriptor = new TupleDesc(types, names);
// create the table, associate it with some_data_file.dat
// and tell the catalog about the schema of this table.
HeapFile table1 = new HeapFile(new File("some_data_file.dat"), descriptor);
Database.getCatalog().addTable(table1, "test");
// construct the query: we use a simple SeqScan, which spoonfeeds
// tuples via its iterator.
TransactionId tid = new TransactionId();
SeqScan f = new SeqScan(tid, table1.getId());
try {
// and run it
f.open();
while (f.hasNext()) {
Tuple tup = f.next();
System.out.println(tup);
}
f.close();
Database.getBufferPool().transactionComplete(tid);
} catch (Exception e) {
System.out.println ("Exception : " + e);
}
}
}我们创建的表有三个整数类型的field。为了表现，创建一个TupleDesc对象，传入一个Type对象数组，以及一个随意的String类型field names数组，一旦创建好这个TupleDesc对象，初始化HeapFile对象指向some_data_file.dat存储的数据。一旦创建了表，添加到catalog中，如果有数据库服务器已经在运行，我们加载这部分catalog信息。
一旦我们已经初始化好数据库系统，创建一种查询策略(query plan)。我们的策略只包括SeqScan操作，也就是扫描硬盘上的tuples。测试程序不停在SeqScan operator上调用hasNext和next，直到从SeqScan输出结果打印在命令行上。
We strongly recommend you try this out as a fun end-to-end test that will help you get experience writing your own test programs for simpledb. You should create the file "test.java" in the src/simpledb directory with the code above, and place the
some_data_file.datfile in the top level directory. Then run:ant java -classpath dist/simpledb.jar simpledb.testNote that
antcompilestest.javaand generates a new jarfile that contains it.
类似资料：