6.830 / 6.814: Syllabus 2021

6.830 / 6.814: Syllabus 2021

文章目录

• • • 1.参考链接：
    • 2.SimpleDB Architecture and Implementation Guide
    • • 2.2Fields and Tuples
      • 2.3Catalog
      • 2.4BufferPool
      • 2.5HeapFile access method
      • 2.6Operators

1.参考链接：

1.1 课程链接：.830/assign.php
1.2 lab1链接：.md
1.3 HearmingBear Lab1链接：
1.4 我的仓库地址：

2.SimpleDB Architecture and Implementation Guide

2.2Fields and Tuples

src/java/simpledb/storage/TupleDesc.java

package simpledb.storage;import simpledbmon.Type;import java.io.Serializable;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;/*** 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 herereturn (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 heretdItems = 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 heretdItems = 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 herereturn 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 hereif (i >= tdItems.length || i < 0) {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 hereif (i >= tdItems.length || i < 0) {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 herefor (int i = 0; i < tdItems.length; i++) {if (tdItems[i].fieldName.equals(name)){return i;}}throw new NoSuchElementException("not find filedName " + 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 hereint size = 0;for (int i = 0; i < tdItems.length; i++) {size += tdItems[i].Len();}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 hereint n = td1.numFields() + td2.numFields();Type[] type = new Type[n];String[] strings = new String[n];int index = 0;for (int i = 0; i < td1.numFields(); i++){type[index] = FieldType(i);strings[index] = FieldName(i);index++;}for (int i = 0; i < td2.numFields(); i++){type[index] = FieldType(i);strings[index] = FieldName(i);index++;}return new TupleDesc(type,strings);}/*** 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 hereif (Class().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
//        int h = 0;
//        for (int i = 0; i < tdItems.length; i++){
//            h = 31 * h + tdItems[i].toString().hashCode();
//        }
//        return h;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 hereStringBuilder stringBuilder = new StringBuilder();for (int i = 0; i < tdItems.length - 1; i++) {stringBuilder.append(tdItems[i].toString()+", ");}stringBuilder.append(tdItems[tdItems.length - 1].toString());String();}
}

变量定义：
private final TDItem[] tdItems;//描述元组的列字段
关键方法：
merge：合并两个元组

src/java/simpledb/storage/Tuple.java

package simpledb.storage;import java.io.Serializable;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Objects;/*** 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 heretupleDesc = td;fields = new Field[td.numFields()];}/*** @return The TupleDesc representing the schema of this tuple.*/public TupleDesc getTupleDesc() {// some code goes herereturn tupleDesc;}/*** @return The RecordId representing the location of this tuple on disk. May*         be null.*/public RecordId getRecordId() {// some code goes herereturn recordId;}/*** Set the RecordId information for this tuple.** @param rid*            the new RecordId for this tuple.*/public void setRecordId(RecordId rid) {// some code goes hererecordId = 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 herefields[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 herereturn 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:** column1tcolumn2\tcolumnN** where t is any whitespace (except a newline)*/public String toString() {// some code goes hereStringBuilder sb = new StringBuilder();for (int i = 0; i < tupleDesc.numFields() - 1; i++) {sb.append(fields[i].toString()+"t");}sb.append(fields[tupleDesc.numFields() - 1].toString() + "n");String();}/*** @return*        An iterator which iterates over all the fields of this tuple* */public Iterator<Field> fields(){// some code goes herereturn (Iterator<Field>) Arrays.asList(fields).iterator();}/*** reset the TupleDesc of this tuple (only affecting the TupleDesc)* */public void resetTupleDesc(TupleDesc td){// some code goes heretupleDesc = td;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Tuple tuple = (Tuple) o;return Objects.equals(tupleDesc, tuple.tupleDesc) && Objects.equals(recordId, dId) && Arrays.equals(fields, tuple.fields);}@Overridepublic int hashCode() {int result = Objects.hash(tupleDesc, recordId);result = 31 * result + Arrays.hashCode(fields);return result;}
}

变量定义：
private TupleDesc tupleDesc;//元组描述
private RecordId recordId;//记录id
private final Field[] fields;//字段值数组

ant runtest -Dtest=TupleDescTest
BUILD SUCCESSFUL
ant runtest -Dtest=TupleTest
BUILD FAILED

2.3Catalog

src/java/simpledb/common/Catalog.java

package simpledbmon;import simpledb.storage.DbFile;
import simpledb.storage.HeapFile;
import simpledb.storage.TupleDesc;import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.UUID;
import urrent.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 + "(" + Id() + ":" + pk + ")";}}/*** Constructor.* Creates a new, empty catalog.*/public Catalog() {// some code goes herehashTable = new ConcurrentHashMap<>();}/*** 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;  Id() 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 hereTable t = new Table(file,name,pkeyField);hashTable.Id(),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;  Id() 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 hereInteger res = hashTable.searchValues(1,value->{if(value.tableName.equals(name)){return Id();}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 Id()*     function passed to addTable* @throws NoSuchElementException if the table doesn't exist*/public TupleDesc getTupleDesc(int tableid) throws NoSuchElementException {// some code goes hereTable t = OrDefault(tableid,null);if (t != null){return TupleDesc();} 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 Id()*     function passed to addTable*/public DbFile getDatabaseFile(int tableid) throws NoSuchElementException {// some code goes hereTable t = OrDefault(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 hereTable t = OrDefault(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 herereturn hashTable.keySet().iterator();}public String getTableName(int id) {// some code goes hereTable t = OrDefault(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 herehashTable.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(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<>();ArrayList<Type> types = new ArrayList<>();String primaryKey = "";for (String e : els) {String[] els2 = e.trim().split(" ");names.add(els2[0].trim());if (els2[1].trim().equalsIgnoreCase("int"))types.add(Type.INT_TYPE);else if (els2[1].trim().equalsIgnoreCase("string"))types.add(Type.STRING_TYPE);else {System.out.println("Unknown type " + els2[1]);it(0);}if (els2.length == 3) {if (els2[2].trim().equals("pk"))primaryKey = els2[0].trim();else {System.out.println("Unknown annotation " + els2[2]);it(0);}}}Type[] typeAr = Array(new Type[0]);String[] namesAr = Array(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();it(0);} catch (IndexOutOfBoundsException e) {System.out.println ("Invalid catalog entry : " + line);it(0);}}
}

变量定义：
private final ConcurrentHashMap<Integer,Table> hashTable;//定义目录表
方法定义：
loadSchema：从文件中读取schema并创建相关表到数据库。

ant runtest -Dtest=CatalogTest
BUILD SUCCESSFUL

2.4BufferPool

src/java/simpledb/storage/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 byother classes. BufferPool should use the numPages argument to theconstructor 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 herethis.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 hereif(!ainsKey(pid.hashCode())){DbFile dbfile = Catalog().TableId());Page page = adPage(pid);pageStore.put(pid.hashCode(),page);}(pid.hashCode());}

2.5HeapFile access method

src/java/simpledb/storage/HeapPageId.java

package simpledb.storage;/** 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 herethis.tableId = tableId;this.pgNo = pgNo;}/** @return the table associated with this PageId */public int getTableId() {// some code goes herereturn tableId;}/*** @return the page number in the table getTableId() associated with*   this PageId*/public int getPageNumber() {// some code goes herereturn pgNo;}/*** @return a hash code for this page, represented by a combination 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 hereString 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 hereif (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;}}

变量定义：
private final int tableId;//表id
private final int pgNo;//页面号

src/java/simpledb/storage/RecordId.java

package simpledb.storage;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 herethis.pid = pid;this.tupleno = tupleno;}/*** @return the tuple number this RecordId references.*/public int getTupleNumber() {// some code goes herereturn tupleno;}/*** @return the page id this RecordId references.*/public PageId getPageId() {// some code goes herereturn pid;}/*** Two RecordId objects are considered equal if they represent the same* tuple.* * @return True if this and o represent the same tuple*/@Overridepublic boolean equals(Object o) {// some code goes hereif (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.*/@Overridepublic int hashCode() {// some code goes hereString hash = "" + TableId() + PageNumber() + tupleno;return hash.hashCode();}}

变量定义：
private final PageId pid;//页id
private final int tupleno;//tuple号

src/java/simpledb/storage/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((PageSize()*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 = Catalog().TableId());this.numSlots = getNumTuples();DataInputStream dis = new DataInputStream(new ByteArrayInputStream(data));// allocate and read the header slots of this pageheader = new byte[getHeaderSize()];for (int i=0; i<header.length; i++)header[i] = adByte();tuples = new Tuple[numSlots];try{// allocate and read the actual records of this pagefor (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((PageSize()*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 (il(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 it(1);}return null;}public void setBeforeImage() {synchronized(oldDataLock){oldData = getPageData().clone();}}/*** @return the PageId associated with this page.*/public HeapPageId getId() {// some code goes herereturn 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&Size(); i++) {try {adByte();} catch (IOException e) {throw new NoSuchElementException("error reading empty tuple");}}return null;}// read fields in the tupleTuple 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 (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 = PageSize();ByteArrayOutputStream baos = new ByteArrayOutputStream(len);DataOutputStream dos = new DataOutputStream(baos);// create the header of the pagefor (int i=0; i<header.length; i++) {try {dos.writeByte(header[i]);} catch (IOException e) {// this really shouldn't happene.printStackTrace();}}// create the tuplesfor (int i=0; i<tuples.length; i++) {// empty slotif (!isSlotUsed(i)) {for (int j=0; j&Size(); j++) {try {dos.writeByte(0);} catch (IOException e) {e.printStackTrace();}}continue;}// non-empty slotfor (int j=0; j<td.numFields(); j++) {Field f = tuples[i].getField(j);try {f.serialize(dos);} catch (IOException e) {e.printStackTrace();}}}// paddingint zerolen = PageSize() - (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();}ByteArray();}/*** 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 = PageSize();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 lab1return null;      }/*** Returns the number of empty slots on this page.*/public int getNumEmptySlots() {// some code goes hereint 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 bitmapint 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 hereArrayList<Tuple> filledTuples = new ArrayList<Tuple>();for(int i=0;i<numSlots;++i){if(isSlotUsed(i)){filledTuples.add(tuples[i]);}}return filledTuples.iterator();}}

src/java/simpledb/storage/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 herethis.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 herereturn 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 AbsoluteFile().hashCode();}/*** Returns the TupleDesc of the table stored in this DbFile.* * @return TupleDesc of this DbFile.*/public TupleDesc getTupleDesc() {// some code goes herereturn td;}// see DbFile.java for javadocspublic Page readPage(PageId pid) {// some code goes hereint tableId = TableId();int pgNo = PageNumber();RandomAccessFile f = null;try{f = new RandomAccessFile(file,"r");if((pgNo+1)*PageSize() > f.length()){f.close();throw new IllegalArgumentException(String.format("table %d page %d is invalid", tableId, pgNo));}byte[] bytes = new PageSize()];f.seek(pgNo * PageSize());// big endint read = f.read(bytes,PageSize());if(read != PageSize()){throw new IllegalArgumentException(String.format("table %d page %d read %d bytes", tableId, pgNo, read));}HeapPageId id = new TableId(),PageNumber());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 javadocspublic 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 hereint num = (int)Math.floor(file.length()*1.PageSize());return num;}// see DbFile.java for javadocspublic ArrayList<Page> insertTuple(TransactionId tid, Tuple t)throws DbException, IOException, TransactionAbortedException {// some code goes herereturn null;// not necessary for lab1}// see DbFile.java for javadocspublic ArrayList<Page> deleteTuple(TransactionId tid, Tuple t) throws DbException,TransactionAbortedException {// some code goes herereturn null;// not necessary for lab1}// see DbFile.java for javadocspublic DbFileIterator iterator(TransactionId tid) {// some code goes herereturn 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;}@Overridepublic void open() throws DbException, TransactionAbortedException {// TODO Auto-generated method stubwhichPage = 0;it = getPageTuples(whichPage);}private Iterator<Tuple> getPageTuples(int pageNumber) throws TransactionAbortedException, DbException{if(pageNumber >= 0 && pageNumber < heapFile.numPages()){HeapPageId pid = new Id(),pageNumber);HeapPage page = (BufferPool().getPage(tid, pid, Permissions.READ_ONLY);return page.iterator();}else{throw new DbException(String.format("heapfile %d does not contain page %d!", Id()));}}@Overridepublic boolean hasNext() throws DbException, TransactionAbortedException {// TODO Auto-generated method stubif(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;}}@Overridepublic Tuple next() throws DbException, TransactionAbortedException, NoSuchElementException {// TODO Auto-generated method stubif(it == null || !it.hasNext()){throw new NoSuchElementException();}();}@Overridepublic void rewind() throws DbException, TransactionAbortedException {// TODO Auto-generated method stubclose();open();}@Overridepublic void close() {// TODO Auto-generated method stubit = null;}}}

ant runtest -Dtest=HeapPageIdTest
ant runtest -Dtest=TupleDescTest
ant runtest -Dtest=HeapPageReadTest
ant runtest -Dtest=HeapFileReadTest
BUILD SUCCESSFUL。

2.6Operators

src/java/simpledb/execution/SeqScan.java

ution;import simpledbmon.Database;
import simpledbmon.DbException;
import simpledb.storage.DbFileIterator;
import simpledb.storage.Tuple;
import simpledb.storage.TupleDesc;
ansaction.TransactionAbortedException;
ansaction.TransactionId;import java.util.NoSuchElementException;/*** 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 herethis.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() {Catalog().getTableName(tableId);}/*** @return Return the alias of the table this operator scans.* */public String getAlias(){// some code goes herereturn 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 herethis.tableId = tableid;this.tableAlias = tableAlias;}public SeqScan(TransactionId tid, int tableId) {this(tid, tableId, Catalog().getTableName(tableId));}public void open() throws DbException, TransactionAbortedException {// some code goes hereit = Catalog().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 Catalog().getTupleDesc(tableId);}public boolean hasNext() throws TransactionAbortedException, DbException {// some code goes hereif (it == null){return false;}return it.hasNext();}public Tuple next() throws NoSuchElementException,TransactionAbortedException, DbException {// some code goes hereif (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 hereit = null;}public void rewind() throws DbException, NoSuchElementException,TransactionAbortedException {// some code wind();}
}

变量定义：
private final TransactionId tid;
private int tableId;
private String tableAlias;
private DbFileIterator it;

ant runsystest -Dtest=ScanTest
BUILD SUCCESSFUL