6.830 Lab 2: SimpleDB Operators6.830 Lab 2: SimpleDB OperatorsAssigned: September 30, 2010 Due: Friday, October 15, 2010 Version History: ● 9/30/10 : Initial version ● 10/5/10 : Updated due date In this lab assignment, you will write a set of operators for SimpleDB to implement table modifications (e.g., insert and delete records), selections, joins, and aggregates. These will build on top of the foundation that you wrote in Lab 1 to provide you with a database system that can perform simple queries over multiple tables. Additionally, we ignored the issue of buffer pool management in Lab 1; we have not dealt with the problem that arises when we reference more pages than we can fit in memory over the lifetime of the database. In Lab 2, you will design an eviction policy to flush stale pages from the buffer pool. You do not need to implement transactions or locking in this lab. The remainder of this document gives some suggestions about how to start coding, describes a set of exercises to help you work through the lab, and discusses how to hand in your code. This lab requires you to write a fair amount of code, so we encourage you to start early! 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 lab 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 (see Section 3.3)!1. Getting started You should begin with the code you submitted for Lab 1 (if you did not submit code for Lab 1, or your solution didn't work properly, contact us to discuss options.) We have provided you with extra test cases for this lab that are not in the original code distribution you received. We reiterate that the unit tests we provide are to help guide your implementation along, but they are not intended to be comprehensive or to establish correctness. You will need to add these new test cases to your release. The easiest way to do this is to untar the new code in the same directory as your top-level simpledb directory, as follows: ● Make a backup of your Lab 1 solution by typing : $ tar -cvzf 6.830-lab1-submitted.tar.gz 6.830-lab1● Change to the directory that contains your top-level simpledb code: $ cd 6.830-lab2● Download the new tests and skeleton code for Lab 2 from http://db.csail.mit.edu/6.830/6.830-lab2-supplement.6.830 Lab 2: SimpleDB Operatorstar.gz: $ wget http://db.csail.mit.edu/6.830/6.830-lab2-supplement.tar.gz● Extract the new files for Lab 2 by typing: tar -xvzf 6.830-lab2-supplement.tar.gz● Eclipse users will have to take one more step for their code to compile. (First, make sure the project is in your workspace in Eclipse following similar steps as done in lab1.) Under the package explorer, right click the project name (probably 6.830-lab1), and select Properties. Choose Java Build Path on the left-hand-side, and click on the Libraries tab on the right-hand-side. Push the Add JARs... button, select zql.jar and jline-0.9.94.jar, and push OK, followed by OK. Your code should now compile. 1.3. Implementation hints As before, we strongly encourage you to read through this entire document to get a feel for the high-level design of SimpleDB before you write code. We suggest exercises along this document to guide your implementation, but you may find that a different order makes more sense for you. As before, 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 Section 3.4 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. ● Implement the operators Filter and Join and verify that their corresponding tests work. The Javadoc comments for these operators contain details about how they should work. We have given you implementations of Project and OrderBy which may help you understand how other operators work. ● Implement IntAggregator and StringAggregator. Here, you will write the logic that actually computes an aggregate over a particular field across multiple groups in a sequence of input tuples. Use integer division for computing the average, since SimpleDB only supports integers. StringAggegator only needs to support the COUNT aggregate, since the other operations do not make sense for strings. ● Implement the Aggregate operator. As with other operators, aggregates implement the DbIterator interface so that they can be placed in SimpleDB query plans. Note that the output of an Aggregate operator is an aggregate value of an entire group for each call to next(), and that the aggregate constructor takes the aggregation and grouping fields. ● Implement the methods related to tuple insertion, deletion, and page eviction in BufferPool. You do not need to worry about transactions at this point. ● Implement the Insert and Delete operators. Like all operators, Insert and Delete implement DbIterator, accepting a stream of tuples to insert or delete and outputting a single tuple with an integer field that indicates the number of tuples inserted or deleted. These operators will need to call the appropriate methods in BufferPool that actually modify the pages on disk. Check that the tests for inserting and deleting tuples work properly. Note that SimpleDB does not implement any kind of consistency or integrity checking, so it is possible to insert duplicate records into a file and there is no way to enforce primary or foreign key constraints. 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. 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 of an optional contest to see who can write the fastest SimpleDB implementation. Finally, you might notice that the iterators in this lab extend the AbstractDbIterator class instead of implementing the DbIterator interface. Because the