|
Chris Pollett >Old Classes
> |
HW3 Solutions Page12.5 The goal in this problem is for each situation to estimate the number of pages retrieved. (I will assume including intermediate pages to get the final result.)1. In this problem we assume we have a B+-tree index on sid. 1.a \sigma_{Sailors.sid<50000}(Sailors). We are given that the low value of sid in the B+-index is 1 and the high value is 100,000. Assuming that the Sailors table is ordered on sid and the data is uniformly distributed we will need to retrieve roughly half of Sailors' 500 pages. i.e., 250 pages In addition, to find the first page to retrieve will require a search down the B+-tree. So 5 more pages are needed, yielding a total of 255 pages. If Sailors were not sorted we could estimate that we'd need to retrieve half the leaf pages of the index (25 pages) plus the 5 pages (height 4 means 4 edges from root to leaf, so 5 nodes) to search down the tree. At this point though, we would be unable to determine how many pages of Sailors we would need to retrieve. In the worst case, it could be all the number of records many pages 80*500 giving a total of 40030 page accesses if the index were used. 1.b \sigma_{Sailors.sid=50000}(Sailors). We are given that sid is a key so this will retrieve 1 row. So the number of pages retrieved will be the search down the tree together with the page containing that row: 5+1 =6 pages. 2. In this problem we assume we have a hash index on sid. 2.a \sigma_{Sailors.sid<50000}(Sailors). Since the index is a hash index we can't use it to return the desired results. So we'd probably end up doing a file scan and retrieving 500 pages. If Sailors is sorted we could binary search for the place to retrieve the expected 250 satisfying pages. This gives [log_2 500] = 9 pages accesses + 250 page accesses = 259 pages. 2.b \sigma_{Sailors.sid=50000}(Sailors). To search down the index will take 3 pages in this case. (The IHeight is 2). From that we need one more page access to get the correct page with the row we want. 13.3 We are given a file with 4500 records of 48 bytes each. We are told that pages are 512 bytes long of which 500 bytes is usable. So 10 records can be stored in a page and the file is 450 pages long. We are also given that we have 4 buffer pages.1. How many sorted subfiles will there be after the initial pages of the sort, and how long will each subfile be? Since we have 4 buffer pages and need to reserve one for output, we will create 4-1 =3 files after the first pass. Each will be roughly 450/3 = 150 pages long. In actuality, since 4 does not evenly divide 450 and we are splitting into runs of length 4, we get the first file has 152 pages, the second 150, and the third one has 148 pages. Note: what the book calls a subfile I call a run. The total number of runs one get is [450/4] = 113. these are stored in 3 files using the scheme from class. 2. How many passes (including the initial pass just considered) are required to sort this file? After the first pass the runs have length 4, after the second pass they have length 12, then 36, then 108, then 324, then one more sorts the file. So 6 passes are needed. 3. What is the total I/O cost for sorting this file? 2 x number pages x number of passes = 5400 I/Os. 4. What is the largest file, in terms of the number of records you can sort with four buffer pages in two passes? How would your answer change if you had 257 buffer pages? The run length after the second pass is 12 pages. So the largest file that can be sorted must have 12 pages. Since each page can store 10 records, this gives 120 records. If we had 257 buffers pages, then after two passes we have runs of length 257*256=65792 pages. This would allow us to store 657920 tuples. Find the cost of using the index to retrieve the records in sorted order (basically treesort algorithm ignoring the insert step) for each of the following cases: Note: In my answers I an assuming the tree index is completely filled. (Not likely in practice.) It might be reasonable to modify my estimates by assuming some fill fixed factor such .66 . This fill factor can also be estimated from the fact the number of leaf index pages is 50. (1) The records themselves are stored in the index. In this case, we first need to estimate the size of the index. An index entry is a record of 48 bytes followed by a 4 byte page pointer. The available space in a page is 512-12 -4) =496 bytes. (4 bytes are for the first page pointer.) So we can store 9 records in an index node. As 9^4 > 4500. The index will have 4 levels. Since the records themselves are stored in the index after scanning down the leftmost branch of the index, we can read the leaf pages in order to output in sorted order. The number of leaf pages will be 4500/9 =500 pages. So the total cost will be 504 pages I/Os. (2) The data entries at the leaf of the index are (k, rid) pairs. Such pairs would be 4+8=12 bytes long. Higher levels of the tree have entries consisting of the key k and a data page, so 4+4=8 bytes. So for non leaf pages we can store 496/8 = 62 entries and leaf nodes can contain 496/12 = 42 entries. As (62^2)*42 > 4500, the index will have height 3. To then look up a record will take one more page access. So to retrieve all the records in order, we need 3 accesses to scan down leftmost path, then we need to scan the leaves of the index as well as retrieve a page (in worst case) for each tuple at a given leaf. The number of leaf pages will be 4500/42 = 108 pages. This gives a total of 4500+108+3 =4608 page I/Os. (3) How would the costs of using the index change if the file is the largest that you can sort in two passes with 257 buffer pages? So now we are answering the previous two questions where the file has 657920 many tuples in 65792 pages. In the first case the index would now have height 7 as 9^7 > 657920. The number of leaf pages in the index becomes 657920/9= 73103. So the cost would be 7+73103=73110 I/O accesses. In the unclustered case, the index would have height 4 as 62^3*42 > 657920. The number of leaf pages will be 657920/42 = 15665 pages. So the total cost (worst case) will be 657920+15665+4= 81589 pages I/Os.
//HeapMockDisk.java
import java.nio.*;
import java.util.*;
/**
This class adds support for adding and deleting records from files
to the MockDisk class. (addRecord, deleteRecord).
It also has methods to get a string with the records contents of a file
(toStringFile) as well as a method to delete files. (deleteFile).
@author Chris Pollett
@version 2003/11/6
*/
public class HeapMockDisk extends MockDisk
{
/**
Just call the MockDisk constructor.
does the same as the default contructor but allows one
to specify a BufferManager to use. Useful if want to
subclass BufferManager to do a customized page replacement policy.
@param buffer - buffer manager to use in creating this instance
of the drive
*/
public HeapMockDisk(BufferManager buffer)
{
super(buffer);
}
/**
this deletes a file from the directory and deallocates its blocks
from the PAM.
@throws MissingResourceException - if the filename is not
found in the directory.
*/
public void deleteFile(String fileName)
throws MissingResourceException
{
int headerIndex = findFileHeader(fileName);
Page p = driveBuffer.readPage(headerIndex);
int availableIndex = p.getByte(HEADER_AVAILABLE_INDEX);
int fullIndex = p.getByte(HEADER_FULL_INDEX);
p.setByte(HEADER_FULL_INDEX, (byte)NULL_PAGE);
driveBuffer.setDirty(headerIndex);
driveBuffer.releasePage(headerIndex);
deallocateList(availableIndex);
deallocateList(fullIndex);
}
/**
Adds the given record to the given heap file
Should use the available pages linked list as described in the book.
If the page becomes full after the addition, page should be moved
to the full pages linked list.
@throws MissingResourceException - if the filename is not
found in the directory.
@throws IllegalArgumentException - if the record contains
more bytes then the record size of the given heap file.
*/
public void addRecord(String fileName, byte[] record)
throws MissingResourceException, IllegalArgumentException
{
int current;
int headerIndex = findFileHeader(fileName);
Page p = driveBuffer.readPage(headerIndex);
int size = p.getRecordSize();
int maxNumRecords = DATA_SIZE/size;
if(size != record.length)
throw new IllegalArgumentException();
int availableIndex = p.getByte(HEADER_AVAILABLE_INDEX);
int fullIndex = p.getByte(HEADER_FULL_INDEX);
driveBuffer.releasePage(headerIndex);
if(isNullPage(availableIndex))
{
availableIndex=firstFreePage();
allocatePage(availableIndex);
p=driveBuffer.readPage(availableIndex);
p.setNumberOfRecords(0);
driveBuffer.releasePage(availableIndex);
prependHeaderList(HEADER_AVAILABLE_INDEX, headerIndex, availableIndex);
}
p = driveBuffer.readPage(availableIndex);
addRecordPage(record, p);
int numRecords = p.getNumberOfRecords()+1;
if(numRecords < maxNumRecords || numRecords == 1)
p.setNumberOfRecords(numRecords);
driveBuffer.setDirty(availableIndex);
driveBuffer.releasePage(availableIndex);
if(numRecords == maxNumRecords)
{
removePageFromList(HEADER_AVAILABLE_INDEX, headerIndex, availableIndex);
prependHeaderList(HEADER_FULL_INDEX, headerIndex, availableIndex);
}
}
/**
Delete the given record from the given heap file
Checks both the available pages linked list
and the full pages linked list for the record.
If a full page becomes un-full after the deletion, page
is moved to available pages linked list. If a page
becomes empty it should removed from the file.
@throws MissingResourceException - if the filename is not
found in the directory or the record is not found in the file.
@throws IllegalArgumentException - if the record contains
more bytes then the record size of the given heap file.
*/
public void deleteRecord(String fileName, byte[] record)
throws MissingResourceException, IllegalArgumentException
{
int headerIndex = findFileHeader(fileName);
int numRecords;
boolean fromFull=false;
Page p = driveBuffer.readPage(headerIndex);
int size = p.getRecordSize();
if(size != record.length)
throw new IllegalArgumentException();
int availableIndex = p.getByte(HEADER_AVAILABLE_INDEX);
int fullIndex = p.getByte(HEADER_FULL_INDEX);
driveBuffer.releasePage(headerIndex);
int index = deleteRecordFromList(HEADER_AVAILABLE_INDEX, record,
availableIndex);
if(isNullPage(index) || isEmptyPage(index))
{
index = deleteRecordFromList(HEADER_FULL_INDEX, record, fullIndex);
if(!(isNullPage(index) || isEmptyPage(index)))
{
removePageFromList(HEADER_FULL_INDEX, headerIndex, index);
prependHeaderList(HEADER_AVAILABLE_INDEX, headerIndex, index);
fromFull = true;
}
else
{
throw new MissingResourceException("Record to delete not in file",
"HeapMockDisk","");
}
}
p = driveBuffer.readPage(index);
numRecords = p.getNumberOfRecords();
driveBuffer.releasePage(index);
if(numRecords == 0)
{
removePageFromList(HEADER_AVAILABLE_INDEX, headerIndex, index);
deallocatePage(index);
}
}
/**
This returns a string containing each record in a file,
one newline after each record. To draw a record it prints
the bytes in the record separated by spaces. For example,
suppose the file had record size of 3 byte and two records in it.
a possible string returned might be:
"255 0 148\n192 16 12"
@throws a MissingResourceException - if the filename is not
found in the directory.
@param filename - name of file to make into a string
@return - string with file info
*/
public String toStringFile(String fileName)
throws MissingResourceException
{
int headerIndex = findFileHeader(fileName);
Page p = driveBuffer.readPage(headerIndex);
int availableIndex = p.getByte(HEADER_AVAILABLE_INDEX);
int fullIndex = p.getByte(HEADER_FULL_INDEX);
int size = p.getRecordSize();
driveBuffer.releasePage(headerIndex);
String recordString = toStringList(availableIndex, size, true);
recordString += toStringList(fullIndex, size, false);
return recordString;
}
/*
Traverses the directory to find the index of the header
page of the file with the given filename
@param fileName - name of file to search for
@return - index of header page for file
@throws MissingResourceException - if the filename is not
found in the directory or the record is not found in the file.
*/
int findFileHeader(String fileName)
throws MissingResourceException
{
int dirIndex = DIR_START;
int tmpIndex = dirIndex;
int nameStart = DATA_START;
int nameLength = HEADER_AVAILABLE_INDEX - nameStart;
isValidNumber(fileName.length(), nameLength, nameLength);
Page p;
boolean notFound = true;
boolean areEqual;
do
{
p = driveBuffer.readPage(dirIndex);
areEqual =true;
for(int i = 0; i < nameLength ; i++)
{
if(((int)p.getByte(nameStart + i)) != ((int)fileName.charAt(i)))
areEqual = false;
}
tmpIndex = p.getNextPage();
driveBuffer.releasePage(dirIndex);
if(areEqual) notFound = false;
else dirIndex= tmpIndex;
} while(dirIndex != DIR_START && notFound);
if(notFound)
throw new MissingResourceException("File not in directory",
"HeapMockDisk","");
return dirIndex;
}
/*
Removes the page with the given page ID from the file whose
directory header page has the passed ID.
@param byteIndex - says whether the page is in the available list
or full list
@param headerIndex - page ID of header page for this file
@param pageIndex - page ID of page to remove
*/
void removePageFromList(int byteIndex, int headerIndex, int pageIndex)
{
Page p = driveBuffer.readPage(pageIndex);
int previous = p.getPreviousPage();
int next = p.getNextPage();
driveBuffer.releasePage(pageIndex);
if(previous == headerIndex)
{
p=driveBuffer.readPage(previous);
p.setByte(byteIndex, (byte)next);
driveBuffer.setDirty(previous);
driveBuffer.releasePage(previous);
}
else
{
p=driveBuffer.readPage(previous);
p.setNextPage(next);
driveBuffer.setDirty(previous);
driveBuffer.releasePage(previous);
}
p=driveBuffer.readPage(next);
p.setPreviousPage(previous);
driveBuffer.setDirty(next);
driveBuffer.releasePage(next);
}
/*
Add the page with page ID pageIndex to the front of the list
that starts with page ID headerIndex. byteindex says if this is
the available or full list.
@param byteIndex - says whether the page is in the available list
or full list
@param headerIndex - page ID of header page for this file
@param pageIndex - page ID of page to prepend
*/
void prependHeaderList(int byteIndex, int headerIndex, int pageIndex)
{
Page p=driveBuffer.readPage(headerIndex);
int next = p.getByte(byteIndex) & 255;
if(next == EMPTY_PAGE) next = NULL_PAGE;
p.setByte(byteIndex, (byte)pageIndex);
driveBuffer.setDirty(headerIndex);
driveBuffer.releasePage(headerIndex);
p=driveBuffer.readPage(pageIndex);
p.setPreviousPage(headerIndex);
p.setNextPage(next);
driveBuffer.setDirty(pageIndex);
driveBuffer.releasePage(pageIndex);
if(next != NULL_PAGE)
{
p=driveBuffer.readPage(next);
p.setPreviousPage(pageIndex);
driveBuffer.setDirty(next);
driveBuffer.releasePage(next);
}
}
/*
Adds a record to the passed page
@param record - array of bytes representing record
@param p - page to add record to
*/
void addRecordPage(byte[] record, Page p)
{
int slot=p.getNumberOfRecords()*record.length;
isValidNumber(slot, 0, Page.DATA_SIZE-1);
for(int i=0; i < record.length; i++)
{
p.setByte(DATA_START+slot+i, record[i]);
}
}
/*
Deletes a record from a list of pages, return the page ID
of the page the record was first found in. Does not delete
page from list
@param byteIndex - says whether the list is in the available list
or full list
@param record - array of bytes representing record
@param pageIndex - page ID of start of list to delete record from
@return - page ID of page record deleted from
*/
int deleteRecordFromList(int byteIndex, byte[] record, int pageIndex)
{
int next;
Page p;
while(!(isNullPage(pageIndex) || isEmptyPage(pageIndex) ))
{
p = driveBuffer.readPage(pageIndex);
next = p.getNextPage();
driveBuffer.releasePage(pageIndex);
if(removeRecordFromPage(byteIndex, record, pageIndex))
{
p = driveBuffer.readPage(pageIndex);
driveBuffer.setDirty(pageIndex);
driveBuffer.releasePage(pageIndex);
return pageIndex;
}
pageIndex = next;
}
return NULL_PAGE;
}
/*
Deletes a record from a page, return true if record was found and deleted.
If not found does nothing and returns false
@param byteIndex - says whether the list is in the available list
or full list
@param record - array of bytes representing record
@param pageIndex - page ID of start of list to delete record from
@return - whether record was found
*/
boolean removeRecordFromPage(int byteIndex, byte[] record, int pageIndex)
{
Page p = driveBuffer.readPage(pageIndex);
int length = record.length;
int numRecords = p.getNumberOfRecords();
if( byteIndex == HEADER_FULL_INDEX ) numRecords = DATA_SIZE/length;
boolean areEqual;
for(int i=0; i < numRecords; i++)
{
areEqual = true;
for(int j = 0; j < length; j++)
{
if( p.getByte(DATA_START+i*length+j) != record[j])
{
areEqual = false;
}
}
if(areEqual)
{
for(int k=(i+1)*length+DATA_START; k < PAGE_SIZE; k++)
{
p.setByte(k-length, p.getByte(k));
}
p.setNumberOfRecords(numRecords-1);
driveBuffer.releasePage(pageIndex);
return true;
}
}
driveBuffer.releasePage(pageIndex);
return false;
}
/*
Deallocates the records in a list
@param index - page ID of start of list to deallocate
*/
void deallocateList(int index)
{
int next;
Page p;
while(!(isNullPage(index) || isEmptyPage(index) ))
{
p = driveBuffer.readPage(index);
next = p.getNextPage();
driveBuffer.releasePage(index);
deallocatePage(index);
index=next;
}
}
/*
Use to output the records in a list of pages
@param index - page ID of start of list
@param size - record size in bytes
@param whether to use number of records information from a given page
or to just assume all slots are filled.
@return - whether record was found
*/
String toStringList(int index, int size, boolean useNumRecords)
{
if (isNullPage(index) || isEmptyPage(index)) return "";
Page p;
int next;
int lastByte = DATA_SIZE;
if(size > DATA_SIZE/2)
{
lastByte = size;
}
String out = "";
do
{
p = driveBuffer.readPage(index);
next = p.getNextPage();
if(useNumRecords && size <= DATA_SIZE/2)
{
lastByte = size*p.getNumberOfRecords();
}
int cnt = 1;
for(int i=DATA_START; i < DATA_START + lastByte; i++)
{
int b = p.getByte(i) & 255;
out += ""+b;
if(cnt == size)
{
out +="\n";
cnt=1;
}
else
{
out +=" ";
cnt++;
}
}
driveBuffer.releasePage(index);
index=next;
}while(!(isNullPage(index) || isEmptyPage(index) ));
return out;
}
/*
Some simple tests to illustrate how the new methods of this drive works.
*/
public static void main(String args[])
{
HeapMockDisk m = new HeapMockDisk(new LRUBufferManager());
/* addRecord, record size 1 tests */
m.createFile("h1",1);
byte[] b1 = new byte[1];
for(byte i = 20; i < 29; i++)
{
b1[0]=i;
m.addRecord("h1",b1);
}
System.out.println(m.toStringFile("h1")); //tests toStringFile
/* addRecord, record size 2 tests */
m.createFile("h2",2);
byte[] b2 = new byte[2];
for(byte i = 30; i < 35; i++)
{
b2[0]=i;
b2[1]= (byte)(i + 1);
m.addRecord("h2",b2);
}
System.out.println(m.toStringFile("h2")); //tests toStringFile
/* addRecord, record size 3 tests */
m.createFile("h3",3);
byte[] b3 = {7,8,9};
m.addRecord("h3", b3);
byte[] b4 = {10,11,12};
m.addRecord("h3", b4);
System.out.println(m.toStringFile("h3")); //tests toStringFile
/* addRecord, record size 4 tests */
m.createFile("h4",4);
byte[] b5 = {12,14,15,16};
m.addRecord("h4", b5);
System.out.println(m.toStringFile("h4")); //tests toStringFile
/* check delete record size =1 */
b1[0]=28;
m.deleteRecord("h1",b1);
b1[0]=25;
m.deleteRecord("h1",b1);
/* check delete record size =2 */
b2[0]=30;
b2[1]=31;
m.deleteRecord("h2",b2);
System.out.println(m.toStringFile("h2")); //tests toStringFile
/* check delete record size = 3 */
m.deleteRecord("h3",b3);
/* check file deletion */
m.deleteFile("h2");
System.out.println(m.toStringDrive());
for(int i=0; i < BUFFER_SIZE; i++)
{
System.out.println(m.driveBuffer.toStringBufferPoolPage(i));
}
}
}
// LRUBufferManager.java
import java.nio.*;
import java.util.*;
/**
This class is a subclass of @see BufferManager
used to manage reading and writing pages on a
MockDisk object.
It uses the Least Recently Used page policy
as it its page replacement policy to determine
which page should be flushed from the buffer
if the need arises.
@author Chris Pollett
@version 2003/10/6
*/
public class LRUBufferManager extends BufferManager
{
/**
Sets up the LRUBufferManager.
By calling the parent method it creates the bufferPool,
and arrays to keep track pin count, dirtiness and which
pages are in the pool. Sets the passed drive full of free
pages to be the pages managed by this BufferManager.
In addition, it sets up two arrays which are used to
determine which is the least recently used unpinned
page.
@param size - how many pages the buffer pool will be
@param drive - pages used to represent the disk drive
*/
public void create(int size, Page[] drive)
{
super.create(size, drive);
timeStamp = new int[size];
clockIndex = new int[size];
for(int i=0; i < size; i++)
{
timeStamp[i]=i;
clockIndex[i]=i;
}
}
/**
Gets a page that is not currently in the buffer pool.
If the page that is replaced has its dirty bit
set then it is written back to the disk. This
method uses the LRU replacement policy to determine
which should be the next buffer page to be used
to read disk page into.
@param pageNumber - page to retrieve.
@throws BufferOverflowException - if page is not in buffer and
all buffer pages are currently pinned.
*/
int getPage(int pageNumber)
throws BufferOverflowException
{
isValidNumber(pageNumber, 0, driveSize);
int index;
int tmpClock = clock;
boolean notFound = true;
/*here is where we find the least recently used page */
do
{
index = clockIndex[tmpClock];
if(timeStamp[index]==tmpClock && pinCount[index]==0)
{
notFound=false;
}
else
{
tmpClock++;
tmpClock = (tmpClock < bufferSize) ? tmpClock : 0;
}
} while( tmpClock != clock && notFound);
/* now we do essentially what we had before */
if( pinCount[index] > 0)
throw new BufferOverflowException();
if(dirty[index])
{
drive[pageNumbers[index]].copy(bufferPool[index]);
dirty[index] = false;
}
storedPages.remove(new Integer(pageNumbers[index]));
bufferPool[index].copy(drive[pageNumber]);
pageNumbers[index] = pageNumber;
storedPages.put(new Integer(pageNumber), new Integer(index));
pinCount[index] = 1;
return index;
}
/**
Releases one pin on the given page in the buffer pool.
If the pin count goes to zero we update the timeStamp
on the item. We also update the entry in clockIndex
for the timeStamp to the current item.
@param pageNumber - page to release a pin of.
@throws IllegalStateException - if pin count on a page goes negative.
*/
public void releasePage(int pageNumber)
throws IllegalStateException
{
/* start of code in method same as before */
isValidNumber(pageNumber, 0, driveSize);
Object indexObj = storedPages.get(new Integer(pageNumber));
if(indexObj == null)
throw new MissingResourceException("Page not in buffer pool.",
"BufferManager", ""+pageNumber);
int index =((Integer)indexObj).intValue();
if(pinCount[index] <= 0)
throw new IllegalStateException("Page "+pageNumber
+ "released too many times");
pinCount[index]--;
/* new code */
if(pinCount[index] == 0)
{
clockIndex[clock] = index;
timeStamp[index] = clock;
clock++;
clock = (clock < bufferSize) ? clock : 0;
}
}
int[] timeStamp; // used to keep track of when buffer page last used
int[] clockIndex; // last page used at given timestamp
}
|