The assignment is due by 11:59pm (right before midnight) on February 14th. Please submit the assignment here.

Acknowledgement

This assignment comes from Prof. Sam Madden's 6.830 class at MIT and from Prof. Magda Balazinksa's CSE544-Autumn 2009 class at University of Washington.

Clarifications

Turn-in Instructions

Please submit your code (see below) and a short (2 pages, maximum) writeup describing your approach. The writeup should:

We will use the latest version you submit that arrives before the deadline. Please indicate your assignment partner if you have one. Please also attach your writeup (one writeup for each team) as a PDF or a text file.

Grading

50% of your grade will be based on whether or not your code passes the system test suite we will run over it. These tests will be a superset of the tests we have provided. Before handing in your code, you should make sure it produces no errors (passes all of the tests) from both ant test and ant systemtest.

Important: before testing, we will replace your build.xml, HeapFileEncoder.java (you need not worry about this for this particular assignment), and the entire contents of the test/ directory with our version of these files! This means you cannot change the format of .dat files! You should therefore be careful changing our APIs. This also means you need to test whether your code compiles with our test programs. In other words, we will untar your tarball, replace the files mentioned above, compile it, and then grade it. It will look roughly like this:

$ tar zxvf 544-hw2.tar
$ cd ./544-hw2
[replace build.xml, HeapFileEncoder.java, and test]
$ ant test
$ ant systemtest
[additional tests]

An additional 50% of your grade will be based on the quality of your writeup and our subjective evaluation of your code.

Assignment goal

In this assignment, you will write parts of a basic database management system called SimpleDB. In this lab assignment, you will write a set of operators for SimpleDB to implement selections, joins, and aggregates. Additionally, the system, as provided to you has a very simple buffer pool management policy that does not deal with the problem that arises when we reference more pages than we can fit in memory over the lifetime of the database. In this assignment, you will also design an eviction policy to flush stale pages from the buffer pool. We will not ask you to add transactions, locking, and concurrent queries because quarters are so short. However, we invite you to think how you would add such functionality into the system.

SimpleDB is written in Java. We have provided you with a set of mostly unimplemented classes and interfaces. You will need to write the code for these classes. We will grade your code by running a set of system tests written using JUnit. We have also provided a number of unit tests, which we will not use for grading but that you may find useful in verifying that your code works.

The extra credit questions ask you to implement table modifications (e.g., insert and delete records).

The remainder of this document describes the basic architecture of SimpleDB, gives some suggestions about how to start coding, and discusses how to hand in your assignment.

We strongly recommend that you start as early as possible on this assignment. It requires you to write a fair amount of code!

Extra Credit

The parts labeled Extra credit will count for an additional 5%. Please work on them only if you have spare time!

Important: The extra credit questions appear in the middle of the assignment instructions. Make sure to read past these questions even if you don't do the extra credit!!

0. Find bugs, be patient, earn candy bars

SimpleDB is a relatively complex piece of code. It is very possible you are going to find bugs, inconsistencies, and bad, outdated, or incorrect documentation, etc.

We ask you, therefore, to do this assignment with an adventurous mindset. Don't get mad if something is not clear, or even wrong; rather, try to figure it out yourself or send us a friendly email. We promise to help out by posting bug fixes, new tarballs, etc., as bugs and issues are reported.

And if you find a bug in our code, we'll give you a candy bar from the Benson store (see “submitting a bug” at the end of the instructions)!

1. Getting started

These instructions are written for any Unix-based platform (e.g., Linux, MacOS, etc.). Because the code is written in Java, it should work under Windows as well, though the directions in this document may not apply.

$ wget http://www.cs.washington.edu/education/courses/544/11wi/assign2/hw2.tgz
$ tar zxvf hw2.tgz
$ cd 544-hw2

SimpleDB uses the Ant build tool to compile the code and run tests. Ant is similar to make, but the build file is written in XML and is somewhat better suited to Java code. Most modern Linux distributions include Ant.

To help you during development, we have provided a set of unit tests in addition to the end-to-end tests that we use for grading. These are by no means comprehensive, and you should not rely on them exclusively to verify the correctness of your project.

$ cd 544-hw2
$ # run all unit tests
$ ant test
$ # run a specific unit test
$ ant runtest -Dtest=TupleTest

# build output...
test:
 [junit] Running simpledb.TupleTest
 [junit] Testsuite: simpledb.TupleTest
 [junit] Tests run: 3, Failures: 0, Errors: 3, Time elapsed: 0.036 sec
 [junit] Tests run: 3, Failures: 0, Errors: 3, Time elapsed: 0.036 sec
# ... stack traces and error reports ...

The output above indicates that three errors occurred during compilation; this is because the code we have given you doesn't yet work. As you complete parts of the assignment, you will work towards passing additional unit tests. If you wish to write new unit tests as you code, they should be added to the test/simpledb directory.

For more details about how to use Ant, see the manual. The Running Ant section provides details about using the ant command. However, the quick reference table below should be sufficient for working on the assignments.

1.1. Running end-to-end tests

We have also provided a set of end-to-end tests that will eventually be used for grading. These tests are structured as JUnit tests that live in the test/simpledb/systemtest directory. To run all the system tests, use the systemtest build target:

$ ant systemtest

# ... build output ...

systemtest:

[junit] Running simpledb.systemtest.ScanTest
[junit] Testsuite: simpledb.systemtest.ScanTest
[junit] Tests run: 3, Failures: 0, Errors: 3, Time elapsed: 0.237 sec
[junit] Tests run: 3, Failures: 0, Errors: 3, Time elapsed: 0.237 sec
[junit]
[junit] Testcase: testSmall took 0.017 sec
[junit] 	Caused an ERROR
[junit] implement this
[junit] java.lang.UnsupportedOperationException: implement this
[junit] 	at simpledb.HeapFile.id(HeapFile.java:46)
[junit] 	at simpledb.systemtest.SystemTestUtil.matchTuples(SystemTestUtil.java:90)
[junit] 	at simpledb.systemtest.SystemTestUtil.matchTuples(SystemTestUtil.java:83)
[junit] 	at simpledb.systemtest.ScanTest.validateScan(ScanTest.java:30)
[junit] 	at simpledb.systemtest.ScanTest.testSmall(ScanTest.java:41)
# ... more error messages ...

This indicates that this test failed, showing the stack trace where the error was detected. To debug, start by reading the source code where the error occurred. When the tests pass, you will see something like the following:

$ ant systemtest

# ... build output ...

[junit] Testsuite: simpledb.systemtest.ScanTest
[junit] Tests run: 3, Failures: 0, Errors: 0, Time elapsed: 7.278 sec
[junit] Tests run: 3, Failures: 0, Errors: 0, Time elapsed: 7.278 sec
[junit]
[junit] Testcase: testSmall took 0.937 sec
[junit] Testcase: testLarge took 5.276 sec
[junit] Testcase: testRandom took 1.049 sec

BUILD SUCCESSFUL
Total time: 52 seconds

1.1.1 Creating dummy tables

It is likely you'll want to create your own tests and your own data tables to test your own implementation of SimpleDB. You can create any .txt file and convert it to a .dat file in SimpleDB's HeapFile format using the command:

$ ant dist

$ java -jar dist/simpledb.jar convert file.txt N

where file.txt is the name of the file and N is the number of columns in the file. Notice that file.txt has to be in the following format:

int1,int2,...,intN
int1,int2,...,intN
int1,int2,...,intN
int1,int2,...,intN

$ java -jar dist/simpledb.jar print file.dat N

where file.dat is the name of a table created with the convert command, and N is the number of columns in the file.

1.2. Working in Eclipse

Eclipse is a graphical software development environment that you might be more comfortable with working in. The instructions we provide were generated by using Eclipse 3.4.0 (Ganymede) for Java Developers (not the enterprise edition) with Java 1.5.0_13 on Ubuntu 7.10. They should also work under Windows or on MacOS.

Setting the Assignment Up in Eclipse

To run a unit test or system test (both are JUnit tests, and can be initialized the same way), go to the Package Explorer tab on the left side of your screen. Under the “544-hw2” project, open the “test” directory. Unit tests are found in the “simpledb” package, and system tests are found in the “simpledb.systemtests” package. To run one of these tests, select the test (they are all called *Test.java - don't select TestUtil.java or SystemTestUtil.java), right click on it, select “Run As,” and select “JUnit Test.” This will bring up a JUnit tab, which will tell you the status of the individual tests within the JUnit test suite, and will show you exceptions and other errors that will help you debug problems.

Running Ant Build Targets

If you want to run commands such as “ant test” or “ant systemtest,” right click on build.xml in the Package Explorer. Select “Run As” and then “Ant Build…” (note: select the option with the ellipsis (…), otherwise you won't be presented with a set of build targets to run). Then, in the “Targets” tab of the next screen, check off the targets you want to run (probably “dist” and one of “test” or “systemtest”). This should run the build targets and show you the results in Eclipse's console window.

Adding External Libraries to the Build Path

Eclipse users will have to take a few more steps for their code to compile. First, in the package explorer, right click the project name (probably 544-hw2) and select Refresh. Then right click the project name again (under package explorer), and select Properties. In the dialog that appears, choose Java Build Path on the left-hand-side, then click on the Libraries tab on the right-hand-side. Push the Add External JARs… button, navigate to the lib directory of your project and select zql.jar and jline-0.9.94.jar, and push OK, followed by OK. Your code should now compile.

1.3. Implementation hints

Before beginning to write code, we strongly encourage you to read through this entire document to get a feel for the high-level design of SimpleDB.

You will need to fill in any piece of code that is not implemented. It will be obvious where we think you should write code. You may need to add private methods and/or helper classes. You may change APIs, but make sure our grading tests still run and make sure to mention, explain, and defend your decisions in your writeup.

In addition to the methods that you need to fill out for this assignment, the class interfaces contain numerous methods that you need not implement in this assignment. These will either be indicated per class:

 // Not necessary for assignment 1.
 public class Insert implements DbIterator {

 public boolean deleteTuple(Tuple t) throws DbException {

 // Some code goes here
 // Not necessary for assignment 1
 return false;
 }

We suggest exercises along this document to guide your implementation, but you may find that a different order makes more sense for you. We will grade your assignment by looking at your code and verifying that you have passed the test for the ant targets test and systemtest. See the “Grading” section at the end of this document for a complete discussion of grading and list of the tests you will need to pass.

Here's a rough outline of one way you might proceed with your SimpleDB implementation; more details on the steps in this outline, including exercises, are given in Section 2 below.

At this point you should be able to pass all of the tests in the ant systemtest target, which is the goal of this lab. Note: if you are not doing the extra credit questions, tests related to inserting and deleting tuples will not work for you.

You'll also be able to use the provided SQL parser to run SQL queries against your database! See Section 2.7 for a brief tutorial and a description.

Finally, you might notice that the iterators in this lab extend the AbstractDbIterator class instead of implementing the DbIterator interface. Because the implementation of next/hasNext is often repetitive, annoying, and error-prone, AbstractDbIterator implements this logic generically, and only requires that you implement a simpler readNext. Feel free to use this style of implementation, or just implement the DbIterator interface if you prefer. To implement the DbIterator interface, remove extends AbstractDbIterator from iterator classes, and in its place put implements DbIterator.

1.4. Transactions, locking, and recovery

As you look through the interfaces that we have provided you, you will see a number of references to locking, transactions, and recovery. You do not need to support these features. We will not be implementing this part of SimpleDB this quarter. It is there because we may use it in subsequent quarters.The test code we have provided you with generates a fake transaction ID that is passed into the operators of the query it runs; you should pass this transaction ID into other operators and the buffer pool.

2. SimpleDB Architecture and Implementation Guide

2.1. Filter and Join

Recall that SimpleDB DbIterator classes implement the operations of the relational algebra. You will now implement two operators that will enable you to perform queries that are slightly more interesting than a table scan.

Exercise 1. Implement the skeleton methods in:

src/simpledb/Predicate.java
src/simpledb/JoinPredicate.java
src/simpledb/Filter.java
src/simpledb/Join.java

At this point, your code should pass the unit tests in PredicateTest, JoinPredicateTest, FilterTest, and JoinTest. Furthermore, you should be able to pass the system tests FilterTest and JoinTest.

2.2. Aggregates

An additional SimpleDB operator implements basic SQL aggregates with a GROUP BY clause. You should implement the five SQL aggregates (COUNT, SUM, AVG, MIN, MAX) and support grouping. You only need to support aggregates over a single field, and grouping by a single field. In order to calculate aggregates, we use an Aggregator interface which merges a new tuple into the existing calculation of an aggregate. The Aggregator is told during construction what operation it should use for aggregation. Subsequently, the client code should call Aggregator.merge() for every tuple in the child iterator. After all tuples have been merged, the client can retrieve a DbIterator of aggregation results. Each tuple in the result is a pair of the form (groupValue, aggregateValue), unless the value of the group by field was Aggregator.NO_GROUPING, in which case the result is a single tuple of the form (aggregateValue).

Note that this implementation requires space linear in the number of distinct groups. For the purposes of this lab, you do not need to worry about the situation where the number of groups exceeds available memory.

Exercise 2. Implement the skeleton methods in:

src/simpledb/IntAggregator.java
src/simpledb/StringAggregator.java
src/simpledb/Aggregate.java

At this point, your code should pass the unit tests IntAggregatorTest, StringAggregatorTest, and AggregateTest. Furthermore, you should be able to pass the AggregateTest system test.

2.3. HeapFile Mutability [Extra credit – If you skip Extra Credit go to 2.5]

Now, we will begin to implement methods to support modifying tables. We begin at the level of individual pages and files. There are two main sets of operations: adding tuples and removing tuples.

Removing tuples: To remove a tuple, you will need to implement deleteTuple. Tuples contain RecordIDs which allow you to find the page they reside on, so this should be as simple as locating the page a tuple belongs to and modifying the headers of the page appropriately.

Adding tuples: The addTuple method in HeapFile.java is responsible for adding a tuple to a heap file. To add a new tuple to a HeapFile, you will have to find a page with an empty slot. If no such pages exist in the HeapFile, you need to create a new page and append it to the physical file on disk. You will need to ensure that the RecordID in the tuple is updated correctly.

Exercise 3. Implement the remaining skeleton methods in:

src/simpledb/HeapPage.java
src/simpledb/HeapFile.java (note that you do not necessarily need to implement writePage at this point.)

To implement HeapPage, you will need to modify the header bitmap for methods such as addTuple() and deleteTuple(). You may find that the getNumEmptySlots() and getSlot() methods serve as useful abstractions. Note that there is a setSlot() method provided as an abstraction to modify the filled or cleared status of a tuple in the page header.

Note that it is important that the HeapFile.addTuple() and HeapFile.deleteTuple() methods access pages using the BufferPool.getPage() method; otherwise, your implementation of transactions in the next lab will not work properly [Note: we will not do the next lab this quarter but still make sure to go through the BufferPool].

Exercise 3 (cont.) Implement the following skeleton methods:

insertTuple()
deleteTuple()

These methods should call the appropriate methods in the HeapFile that belong to the table being modified (this extra level of indirection is needed to support other types of files — like indices — in the future).

At this point, your code should pass the unit tests in HeapPageWriteTest and HeapFileWriteTest. We have not provided additional unit tests for HeapFile.deleteTuple() or BufferPool.

2.4. Insertion and deletion [Extra credit – If you skip Extra Credit go to 2.5]

Now that you have written all of the HeapFile machinery to add and remove tuples, you will implement the Insert and Delete operators.

For plans that implement insert and delete queries, the top-most operator is a special Insert or Delete operator that modifies the pages on disk. These operators return the number of affected tuples. This is implemented by returning a single tuple with one integer field, containing the count.

Exercise 4. Implement the skeleton methods in:

src/simpledb/Insert.java
src/simpledb/Delete.java

At this point, your code should pass the unit tests in InsertTest. We have not provided unit tests for Delete. Furthermore, you should be able to pass the InsertTest and DeleteTest system tests.

2.5. Page eviction

The existing implementation of SimpleDB provided to you does not correctly observe the limit on the maximum number of pages in the buffer pool defined by the constructor argument numPages. Now, you will choose a page eviction policy and instrument any previous code that reads or creates pages to implement your policy.

When more than numPages pages are in the buffer pool, one page should be evicted from the pool before the next is loaded. The choice of eviction policy is up to you; it is not necessary to do something sophisticated. Describe your policy in the lab writeup.

Important: If you are not doing the extra credit and thus are not implementing inserting/deleting tuples, you don't need to worry about writing dirty pages back to disk! All you have to do for this question is to implement the evictPage() method. You may also need to modify your getPage() method. You do NOT need to implement flushAllPages() nor flushPage().

If you are doing the extra credit, notice that BufferPool asks you to implement a flushAllPages() method. This is not something you would ever need in a real implementation of a buffer pool. However, we need this method for testing purposes. You should never call this method from any real code. Because of the way we have implemented ScanTest.testCache, you will need to ensure that your flushPage() and flushAllPages() methods do not evict pages from the buffer pool to properly pass this test. flushAllPages() should call flushPage() on all pages in the BufferPool, and flushPage() should write any dirty page to disk and mark it as not dirty, while leaving it in the BufferPool. The only method which should remove a page from the buffer pool is evictPage(), which should call flushPage() on any dirty page it evicts.

Note that we also use flushAllPages() in the query parser. Since we do not implement transactions in this assignment, there is no guarantee that any changes have been made durable when SimpleDB exits. Since it is fun to see changes actually appear on disk, we force all dirty pages to disk before quitting.

Exercise 5.

Fill in the evictPage() method and update your getPage() method in the file:

src/simpledb/BufferPool.java

Since we will not be checking for any particular eviction policy, this test works by creating a BufferPool with 16 pages (NOTE: while DEFAULT_PAGES is 100, we are initializing the BufferPool with less!), scanning a file with many more than 16 pages, and seeing if the memory usage of the JVM increases by more than 2MB. If you do not implement an eviction policy correctly, you will not evict enough pages, and will go over the size limitation, thus failing the test.

For those doing the extra credit, also fill in the flushPage() and flushAllPages() methods and appropriately fill in or modify any additional helper methods.

If you did not implement writePage() in HeapFile.java above, you will also need to do that here.

CSE 544: Assignment 2