Due Wednesday November 10 at beginning of
class
In this part of the project, you will implement a File Manager
for Heap Files that also provides a scan mechanism that will allow you to search a heap
file for records that satisfy a search predicate called a filter. How are heap
files different from the files that the DB layer of Minirel provides ? The main difference
is that the files at the DB layer are physical (a bunch of pages) and not logical. The
HeapFile layer imposes a logical ordering on the pages (via a linked list). In addition,
while both the DB and Buffer Manager layers consider pages to be simply a chunk of bytes,
the Heap File layer imposes a slotted-page structure on top of each page. This is
necessary for accommodating variable length records.
The Heap File layer contains three main classes: a Page class
for describing the structure and the operations that can be performed on a slotted page, a
HeapFile class for inserting and deleting records from a heap file, and a HeapFileScan
class (derived from the HeapFile class) for scanning a heap file (with an optional
predicate). You will implement the HeapFile and HeapFileScan classes.
The detailed description of each of these classes follows.
The following is the definition of the Page class (given in page.h).
If you like, you may read Section 7.6 of the text for a little background,
but it's not necessary since you will only be using, not implementing,
the slotted page structures.
const unsigned PAGESIZE = 1024;
const unsigned DPFIXED= sizeof(slot_t)+4*sizeof(short)+3*sizeof(int);
private:
char data[PAGESIZE - DPFIXED];
slot_t slot[1]; // first element of slot array - grows
backwards!
short slotCnt; // number of slots in use;
short freePtr; // offset of first free byte in data[]
short freeSpace; // number of bytes free in data[]
short dummy; // for alignment purposes
int prevPage; // backwards pointer
int nextPage; // forwards pointer
int curPage; // page number of current pointer
public:
void init(const int pageNo); // initialize a new page
void dumpPage() const; // dump
contents of a page
const int getNextPage() const; // returns value of nextPage
const int getPrevPage() const; // returns value of prevPage
// sets value of nextPage to pageNo
void setNextPage(const int pageNo);
// sets value of prevPage to pageNo
void setPrevPage(const int pageNo);
// inserts a new record (rec) into the page, returns RID of
record
const Status insertRecord(const Record & rec, RID& rid);
// delete the record with the specified rid
const Status deleteRecord(const RID & rid);
// returns RID of first record on page
const Status firstRecord(RID& firstRid) const;
// returns RID of next record on the page
const Status nextRecord (const RID & curRid, RID& nextRid)
const;
// returns reference to record with RID rid
const Status getRecord(const RID & rid, Record & rec);
};
The Page class uses a slotted page approach for organizing variable length records. When a record is in memory, it is convenient for the higher layers to deal with a record in the following form.
struct Record
{
void* data;
int length;
};
However on a page, records are stored differently. Only the data parts of records are stored one after another starting from byte 0 of a page while the slot array (which contains pointers to the start of records) grows from the bottom of the page towards the top. There are several important things to notice. First the data[] area in a page is used to hold both records and all but the 0th element of the slot array! Secondly, since the slot array grows towards the "top", it is indexed with the values 0, -1, -2, -3, ... and not 0, 1, 2, 3 ... This is very important ! Each element of the slot array has the structure:
struct slot_t {
short offset;
short length; // equals -1 if slot is
not in use
};
The offset records the start of the record from the beginning of data[] and the length equals its length. The slotCnt attribute is used to indicate the current end of the slot array. It is initialized to 0 (by the init() member function) and everytime a record is added to the page, its value is decremented by 1. freePtr is the first free byte in data[]. freeSpace keeps track of how much free space is available in data[]. dummy is there for alignment purposes only. The nextPage and prevPage members are used to for a doubly linked list of the pages in the file. Finally curPage is the page number of the current page. As records are deleted, the resulting hole should be compacted. However, since records are addressed via a (pageNo, slotNo) pair called RID, we cannot compact the slot array (except in one case). RIDs have the following structure:
struct RID{
int pageNo;
int slotNo;
};
The pageNo identifies a physical page number (something that the buffer manager and the DB
layers understand) in the file. The slotNo specifies a slot in the slot array on the page.
The only tricky thing is that the slotNo field of an RID is always positive while the slot
array is itself indexed using a negative number, so the sign has to be flipped when
converting from one form to another. As an aside, in a real DBMS, RIDS usually have a
third component that indicates the storage volume or file.
The Page class has no constructor or destructor. Why is this ? Well recall that in the BufMgr class, the bufPool is defined to be an array of Pages. Whe the bufPool is first created, the Page class constructor would get called on each Page instance in bufPool. This is not when we want the "constructor" to be called. Instead we want it to be called when first allocate an empty page in the file (usually in the HeapFile::insertRecord method). To get around this problem, the Page class has no constructor. Rather an init() method is provided.
void init(const int pageNo)
Initializes the structure of a page. The pageNo parameter is used to set the curPage attribute.
void dumpPage()
Prints the contents of the data structures of the page (but not the contents of the records on the page). This might be useful for debugging.
const int getNextPage() const
Returns the value of the nextPage attribute. Note that the pageNo of the next page need not be consecutive to the curPage number. This is because the order of pages in the heap file is determined by the linked list of pages and not by the page numbers. The File class in the I/O layer might come up with any pageNo when allocating a new page. The page numbers are used merely as pointers.
const int getPrevPage() const
Returns the value of the prevPage attribute.
void setNextPage(const int pageNo)
Sets value of nextPage to pageNo.
void setPrevPage(const int pageNo)
Sets value of prevPage to pageNo.
const Status insertRecord(const Record & rec, RID & rid)
Inserts the record rec in the page. The data and length
portions of the record are copied into appropriate postions in the page. Returns the RID
of the record via the rid parameter. Returns OK if no errors occurred, NOSPACE if there is
not sufficient room on the page to hold the record.
const Status deleteRecord(const RID & rid)
Deletes record with RID rid, compacting the hole created.
Compacting the hole , in turn, requires that all the offsets (in the slot array) of all
records after the hole be adjusted by the size of the hole. The slot array can be
compacted only if the record corresponding to the last slot is being deleted.
Returns OK if no errors occurred, INVALIDSLOTNO if the rid is invalid
(i.e. there is no such record in the page), NORECORDS if no more records are left in the
page (this is not really an error condition).
const Status firstRecord(RID& firstRid) const
Returns the RID of the first record of the page (via the
firstRid parameter). Remember that slot[0] (and possibly slot[-1], ...) might be empty due
to deletions. Scans the slot array backward starting at 0,
looking for a non-empty slot (an empty slot is indicated by a length field of -1).
Returns OK if no errors occurred, NORECORDS if the page was empty.
const Status nextRecord (const RID & curRid, RID& nextRid) const
Returns (via the nextRid parameter) the RID of the next record on the page after curRid. Returns OK if no errors occurred, ENDOFPAGE if curRid was the last record on the page.
const Status getRecord(const RID & rid, Record & rec)
Returns the length and a pointer to the record with RID rid.
You can get recLen from the proper entry in the slot array. However recPtr needs to be an address
and not just the offset from the beginning of data[]. This means that the
upper layers can directly
modify part of the page frame that contains the record. Returns OK if
no errors occurred, INVALIDSLOTNO if the rid is invalid (i.e. if there is no such record
on the page).
The HeapFile class is used to implement heap files on top of the physical files provided by the DB class. Each heap file consists of a special header page plus one or more data pages. This header page is different from the DB header page for the file (you should not even be aware of the DB header page) and its contents are decided and manipulated by the HeapFile class. The HeapFile level header page has the following structure :
struct HeaderPage
{
char fileName[MAXNAMESIZE]; // name of file
int
firstPage;
// pageNo of first data page in file
int
lastPage;
// pageNo of last data page in file
int
pageCnt;
// number of pages
int
recCnt;
// record count
};
The meaning of most of the fields in this structure should be obvious from their names. lastPage is used to keep track of the last page in the file. When someone tries to add a record to the file, this is the place likely to have space. When a HeapFile is instantiated, you should read the header page for the file into the buffer pool and keep it pinned until the file is closed. Rather than keeping track of whether it got updated while it was pinned, always unpin it with dirty = true. It is possible that the same file may be opened more than once at the same time. The HeapFile class need not be aware of this since this will simply result in the header page being pinned in the buffer pool multiple times and will not be flushed out until the last instance of the HeapFile has been closed. All this logic is handled by the BufMgr class. The firstPage attribute of the header page points to the first data page. The data pages are instances of the Page class and they are linked together using a doubly linked list (via the prevPage and nextPage members).
// class definition of HeapFile
class HeapFile {
protected:
File*
file; // pointer to
underlying DB File object
HeaderPage* headerPage; // pointer to header page
in buffer pool
int
headerPageNo; // page number of header page
public:
// initialize
HeapFile(const string & name, Status& returnStatus);
// destructor
~HeapFile();
// return number of records in file
const int getRecCnt() const;
// insert record into file
const Status insertRecord(const Record & rec, RID& outRid);
// delete record from file
const Status deleteRecord(const RID & rid);
};
The private data members of the HeapFile class include file: a pointer to the
File object that results from a call to DB::openFile(), headerPage: a
pointer to the pinned header page of the file in the buffer pool, and headerPageNo:
the page number of the header page of the HeapFile. The following are the descriptions of
the public member functions.
HeapFile(const string & name, Status& returnStatus)
The actions performed by the constructor depend on whether or not the file already exists. If the file does not exist, the constructor first creates a file instance by invoking DB.createfile(name). Next the file is opened and the HeaderPage for the file created and initialized. To get space to hold the header page, do the following:
Page* tmpPage;
status = bufMgr->allocPage(file, headerPageNo, tmpPage)
// allocate a page to hold the header page
// check status for errors
headerPage = (HeaderPage *) tmpPage; // cast Page* to HeaderPage*
If the file already exists, the constructor simply reads the header page for the file into the buffer pool by executing the following:
// File already exists, get header page into buffer pool
Page* tmpPage;
status = file->getFirstPage(headerPageNo); // check status for errors
status = buf->readPage(file, headerPageNo, tmpPage);
// check status for errors
headerPage = (HeaderPage *)tmpPage;
You can distinguish between the two cases by simply trying to open the file. If the open fails, then the file does not exist and must be created ! Note that the constructor returns status information through the returnStatus parameter.
~HeapFile()
The destructor unpins the header page and calls DB::closeFile().
const int getRecCnt() const
Returns the number of records currently in the file.
const Status insertRecord(const Record & rec, RID& outRid)
Appends Record rec to the file. Uses the HeaderPage to locate the last page in the file which is then read into the buffer pool and pinned. Then the Page::insertRecord() method is invoked on the last page. In case the last page is full, allocates a new Page (and inserts it at the end of the doubly linked list of pages) before calling Page::insertRecord. You also need to handle the case when the file is empty. Be careful not to leave anything pinned when this function returns (except the header page). The RID of the record inserted is returned via the outRid parameter. Returns OK if no errors occurred or the error code of the first error that occurred.
const Status deleteRecord(const RID & rid)
Deletes the record with RID rid from the file by calling
Page::deleteRecord on the appropriate page. The page must of course be first read in and
pinned in the buffer pool. In addition if the deletion of the records results in an empty
page, the page must be deallocated and removed from the doubly linked list of pages.
Returns OK if no errors occurred or the error code of the first error that occurred.
The HeapFile class defined above is used for basic operations like insertion and deletion of records. For retrieving records from the file we must use the HeapFileScan class (which also represents a HeapFile since it is derived from the HeapFile class). The HeapFileScan class can be used in three ways :
Several HeapFileScans may be instantiated on the same file, and this is ok. Each HeapFileScan will cause a separate pin on the header page in the buffer pool, but the Buffer Manager layer should be able to handle this transparently as long as all HeapFileScan objects are deleted properly.
class HeapFileScan : public HeapFile
{
public:
// initiate a filtered scan
HeapFileScan(const string & name,
const int offset,
const int length,
const Datatype type,
const char* filter,
const Operator op,
Status & status);
// end filtered scan
~HeapFileScan();
// read record from file, returning pointer and length
const Status getRecord(const RID & rid, Record & rec);
// marks current page of scan dirty
const Status markDirty(const RID & rid);
// return next record
const Status scanNext(RID& outRid);
// read record from file, returning pointer and length
const Status getRandomRecord(const RID &rid, Record & rec);
private:
RID
curRec; // rid of last
record returned
Page* curPage; //
pointer to pinned page in buffer pool
int curPageNo; //
page number of pinned page
bool dirtyFlag; // true
if page has been updated
int
offset; // byte offset
of filter attribute
int
length; // length of
filter attribute
Datatype type; //
datatype of filter attribute
const char* filter; // comparison value of filter
Operator
op; // comparison
operator of filter
const bool matchRec(const Record & rec) const;
};
Private Data Members of HeapFileScan
curRec is the RID of the last record returned by the scan. curPage is a pointer to the buffer pool page containing record curRec and curPageNo is its page number. To make scans fast, we keep the current page pinned until we have processed all the records on the page. Then the page is unpinned and the next page is read into the buffer pool and pinned. dirtyFlag represents the update status of the page which must be supplied to the Buffer Manager when the page is unpinned.
The other fields have to do with conditional or filtered scans. length is the size of the field on which predicate is applied and offset is its position within the record (we consider fixed length attributes only). The type of the attribute can be STRING, INTEGER or FLOAT and is defined in heapFile.h Similarly all ordinary comparison operators (as defined in heapFile.h) have to be supported. The value to be compared against is stored in binary form in filter. For example, if we want to evaluate salary < 20,000 then 20,000 will be stored as a 4 byte array in filter.
HeapFileScan(const string & name, const int offset, const int length, const Datatype type, const char* filter, const Operator op, Status & status)
This method initiates both unconditional and filtered scans. If filter == NULL, an unconditional scan is performed. Otherwise, the data members of the object are initialized with the parameters to the constructor. In either case, the HeapFile with the appropriate name is opened by giving a call to the HeapFile constructor. The status of all these operations is indicated via the status parameter.
~HeapFileScan()
Shuts down the scan and unpins curPage.
const Status scanNext(RID& outRid)
Returns (via the outRid parameter) the RID of the next record that satisfies the scan predicate. The basic idea is to scan the file one page at a time. For each page, use the firstRecord() and nextRecord() methods of the Page class to get the rids of all the records on the page. Convert the rid to a pointer to the record data and invoke matchRec() to determine if record satisfies the filter associated with the scan. If so, return rid. To make things fast, keep the current page pinned until all the records on the page have been processed. Then continue with the next page in the file. Returns OK if no errors occurred. Otherwise, return the error code of the first error that occurred.
const Status getRecord(const RID & rid, Record & rec)
Returns (via the rec parameter) the record identified by rid. The page containing the record should already be pinned in the buffer pool (by a preceding scanNext() call). If not, return BADPAGENO. A pointer to the pinned page can be found in curPage. Just invoke Page::getRecord() on this page and return its status value.
const bool matchRec(const Record & rec) const
This private method determines whether the record rec satisfies the predicate associated with the scan. It takes care of attributes not being aligned properly. Returns true if the record satisfies the predicate, false otherwise. We will provide this method for you.
const Status markDirty(const RID & rid)
Marks the current page of the scan dirty by setting the dirtyFlag. The dirtyFlag should be reset every time a page is pinned. Make sure that when you unpin a page in the buffer pool, that you pass dirtyFlag as a parameter to the unpin call. Returns OK if no errors. The page containing the record should already be pinned in the buffer pool.
const Status getRandomRecord(const RID &rid, Record & rec)
Retrieves an arbitrary record from a file. If the specified record is not on the currently pinned page, the current page is unpinned and the required page is read into the buffer pool and pinned. The difference between this method and the getRecord() method above is that getRandomRecord() does not assume that the requested record is on the page currently pinned by the scan. Returns OK if no errors. Otherwise, the first error occurred.
Start by making a copy of the directory ~test594/project/part1 in your home directory. In it you will find the following files :
Each function that you implement must do some error checking on its input parameters to make sure that they are valid. If they are not, then the function should return an appropriate error code. Each function should also check the return status of every function it calls. If an error occurred, you should just return this code to the higher level calling function. Remember to do any necessary cleanup while doing a premature exit from a function. Usually, you should not print out error messages in any of the functions you implement. These should only be printed by the top level calling function in testfile.C for example. The intermediate functions in the HeapFile layer should just relay the error codes to the higher layers.
Testing for correctness involves more than just seeing if a few test cases produce the correct output. There are certain types of errors (memory errors and memory leaks) that usually surface after the system has been running for a longer period of time, so you should run a few fairly robust tests. If you have programmed in Java you should keep in mind that C++ does not have automatic garbage collection, so each new must ultimately be matched by a corresponding delete. Otherwise all the memory in the system might be used up.