Due Monday December 6 at beginning of
class
In this part of the project, we will provide you with a fully functional Minirel system (including a heapfile implementation in case you don't want to use yours) with one exception: it will not have any join methods. You will implement a new join method called "Ripple Join". Your join method will use the heapfile layer to access tuples from its input relations. We expect the amount of code for this to be equivalent to the amount of code required for Part 1. The Ripple Join is a general join method that can be used to perform any join, but it is especially useful in the field of Online Analytical Processing (OLAP).
The Ripple Join algorithm is described in "Ripple Joins for Online Aggregation", P. Haas and J. Hellerstein, in Proc. 1999 ACM SIGMOD Int'l. Conf. on Management of Data, ACM Press, 1999. You should print and read this paper. Feel free to skip Section 5.2 and to just skim Sections 5.3 and 5.4.
You will implement this algorithm in the Minirel system. Specifically, you will implement a version of ripple join that is binary (exactly 2 relations are being joined), groups on a single field, and retrieves only that field plus a single aggregate, which is either COUNT, SUM, or AVG and is applied to exactly one field. In addition, your version of the algorithm does not need to be adaptive but must handle non-unitary aspect ratios. This will all make some sense once you've read the paper. This will give you some experience with DBMS internals and with some of the important issues in the emerging field of OLAP.
We suggest you go about this part of the project in two phases: Phase 1: get the Ripple Join method working as a "regular" join method, without regard to its uses in grouping, aggregates, and OLAP. You can do all the design and testing of Ripple Join in the context of Minirel. Only this first phase is actually required. But if you're adventurous, you can earn up to 25% extra credit on this (that's 25% of the total possible points for the Ripple Join -- the heapfile stuff isn't included here) by going on to Phase 2.
Phase 2: Once you have the algorithm working, you will want to test its ability to improve certain characteristics of online grouping and aggregation. Minirel doesn't support grouping and aggregation, so the general idea here will be to write a function that will execute OLAP queries by invoking the Ripple Join function (which now works superbly, of course!) and, at the proper times, printing out partial results of grouping and aggregation as the query executes. You can test and debug this portion by using a testfile that calls it with various inputs.
What follows is a syntax for Minirel's user interface and DML. After that we provide the details of the interfaces for the functions you must write and information about the files you need to copy to get started. Feel free to experiment with Minirel and its facilities, but much of what follows you can view as reference material.
The following database utilities can be run as a standalone UNIX program:
We have provided implementations of these routines in minirel.C, dbcreate.C, and dbdestroy.C respectively. Each of these executables can be created by giving appropriate arguments to make.
This is the main routine which is used to access and query the Minirel database dbname. When minirel is invoked with a dbname, the very first thing it does is to change its working UNIX directory (using chdir) to dbname. Each Minirel database corresponds to a UNIX directory and each relation within that database corresponds to a file within the directory. The minirel utility starts off by creating a buffer manager, opening the relation and attribute catalogs and then calling the function parse(). With the call to parse(), an infinite loop will start prompting the user for a new command, calling the appropriate routines of the lower layers to execute the command and then prompting the user again. After a command is parsed, it is transformed by the interp() function (in file parser/interp.C) into a sequence of operators (e.g. selects, joins, creates, destroys, prints, loads etc.), which are then executed one by one by the database back-end. Executing an operator involves calling some routine, one of which you will implement during Part 2 of the project. For example, when the front-end receives a select-project query, the parser will call a procedure named select() that will in turn call the methods of the HeapFileScan class to scan the appropriate heapfile.
This creates the database dbname.
This destroys the database dbname.
Once minirel has been invoked, it can be used to either answer queries (using SQL DML) or to perform various utility operations (via SQL DDL). The syntax of these commands is described using a pseudo context-free grammar. All commands to the Minirel front-end must end with a semi-colon.
<SQL_COMMAND> ::= <DDL_STATEMENT>;
| <DML_STATEMENT>;
<DDL_STATEMENT> ::= <CREATE>
| <DESTROY>
| <BUILD_INDEX>
| <DROP_INDEX>
| <LOAD>
| <PRINT>
| <HELP>
| <QUIT>
We now describe the semantics of each command in detail.
<CREATE>::= create relname(attr1=format1, ..., attrN=formatN)
The create command creates the relation relname with the given schema. Relation and attribute names can be at most MAXNAME = 12 characters long. Each format argument has a type specification ('i', 'f' or 's') followed by an integer. The only valid length for the 'i' format is sizeof(int) and for the 'f' format is sizeof(float). For the 's' format valid lengths are between 1 to 255 (both inclusive). This command results in a call to the RelCatalog::createRel function that updates the catalogs appropriately and then creates a HeapFile to store the tuples of the relation.
<DESTROY>::= destroy relname
The destroy command destroys any indices on the relation (this can be found by examining the catalogs) and then it destroys the HeapFile for that relation. Finally it removes all relevant catalog entries for that relation.
<BUILD_INDEX>::= buildindex relname(attrname)
The buildindex command creates an index on attribute attrname of relation relname. You should assume that all indices on a relation are created before any tuples are loaded into the relation. When an index is created, buildindex updates the catalogs and creates the index file.
<DROP_INDEX> ::= dropindex relname(attrname)
The dropindex command removes the index on attribute attrname of relation relname. In addition to updating the catalogs, it also removes the underlying index file.
<PRINT> ::= print relname
The print routine prints the contents of the specified relation in a reasonably tidy format.
<LOAD> ::= load relname(filename)
The load utility bulk loads tuples into a relation using data in a binary UNIX file. When the parser receives the load command, it begins by examining the catalogs to determine the types and lengths of all the attributes and the number of indices (if any). These must have been specified by previous create and buildindex commands. Then it opens the UNIX file filename containing the input data. Each tuple is in binary format (i.e. there is no space wasted for delimiters) and the length of each field can be determined from the catalog. The third step is to create an instance of the HeapFile class passing the relname as parameter. Since the relation must have already been created (by a previous create call), this will just open the corresponding DB file. The same thing needs to be done for all indices that have been defined on relname. Finally, the tuples are read from the UNIX file one at a time, using the type information given by the schema. After each tuple is read in from the UNIX file, it is inserted into the HeapFile using HeapFile::insertRec(). Then Index::insertEntry() is called on each index to create an index entry for the tuple. After loading all the tuples, the UNIX file is closed.
<HELP> ::= help [relname]
If relname is not specified, help lists the names of all the relations in the database. Otherwise, it lists the name, type, length and offset of the relation.
<QUIT> ::= quit
The quit command exits minirel, causing all buffers to be flushed to disk. Prior to quitting, the system closes down any open files (including catalogs).
One of the neat things about a relational database is that in addition to the data, even the metadata that describe what relations exist in the database, the types of their attributes and so on are also stored in relations, called catalogs. Minirel has two catalog relations : relcat and attrcat. The relcat relation contains one tuple for every relation in the database (including itself). The attrcat relation contains one tuple for every attribute of every relation (including the catalog relations) and this tuple contains information about the attribute. Both attrcat and relcat are created by the dbcreate utility and together they contain the schema of the database. Since each database has its own schema, relcat and attrcat must be placed in the UNIX directory corresponding to the database. relcat and attrcat are instances of the RelCatalog and AttrCatalog classes respectively; see the code for details if you like.
Minirel implements a simplified version of SQL DML. The syntax of this language is described below.
<DML_STATEMENT> ::= <QUERY>
| <UPDATE>
We now describe the format of a query.
<QUERY> ::= select [into relname] <TARGET_LIST> [where <QUAL>]
The result of a query is either printed on the screen or optionally stored in a relation with name relname. In practice, for the first case, the Minirel parser and query interpreter will always put the results into a temporary relation anyway. If no qualification is given in a query, then the query is equivalent to simply printing all columns requested in the target list.
<TARGET_LIST> ::= (relname1.attr1, relname2.attr2, ..., relnameN.attrN)
This is a list of attributes attr1, attr2, ..., attrN from relations relname1, relname2,... relnameN respectively that constitutes the target list of a query. All attributes in the target list should come from the same relation, except when the qualification is a join, in which case the attributes may come from any of the two relations that are joined. The projection on those attributes happens on the fly while the qualification is being evaluated, i.e. while the selection or join is being processed.
<QUAL> ::= <SELECTION>
|<JOIN>
Qualifications are very simple, either a selection clause or a join clause.
<SELECTION> ::= relname.attr <OP> value
A selection condition simply involves the comparison of an attribute value with a constant. If OP is =, and there is an index on attr, the index will be used to process the selection. The index class we provide uses hashing and so it cannot be used to evaluate non-equality predicates.
<JOIN> ::= relname1.attr1 <OP> relname2.attr2
A join condition involves the comparison of an attribute value of one tuple with an attribute value of another tuple. Your Ripple Join code will handle both equi-joins and non-equi-joins.
<UPDATE> ::= <DELETE>
| <INSERT>
An update is really either an insert or a delete; i.e., you cannot use Minirel to modify the value of an existing tuple in a user relation.
<DELETE> ::= delete relname [where <SELECTION>]
This specifies the deletion of tuples from relname satisfying the specified selection condition.
<INSERT> ::= insert relname(attr1=val1, attr2=val2,... attrN=valN)
This will insert the given values as a tuple into the relation relname. Note that the values of the attributes need not be given in the same order as the schema specification during the creation of relname.
For this part of the project you will implement the following routines according to the given specifications. The first one will be called by the parser with appropriate parameters in response to various SQL DML statements submitted by the user.
const Status QU_Join(const string & result, const int projCnt, const attrInfo projNames[], const attrInfo *attr1, const Operator op, const attrInfo *attr2)
All joins are implemented using the Ripple Join algorithm. The main job of QU_Join is to convert the attrInfo parameters into AttrDesc objects, compute the record length of the result tuples, and pass the relevant information on to the RipJoin constructor to set up the actual join. QU_Join will then repeatedly call RipJoin::getNext until the join is complete, printing each tuple as it is retrieved. The RipJoin destructor should be called at the end.
For the purposes of this project, we will ignore the "result" parameter. "projCnt" is the number of attributes being projected, and "projNames" contains their field and relation names. attr1 and attr2 are the two attributes whose values will be compared using "op". You should perform projection on the fly using information given in projCnt and projNames.
Your call to set up the RipJoin iterator might look something like this:
RJ = new RipJoin(projCnt, AttrDescArray, AttrDesc1, op, AttrDesc2,
recLen, 1, 1, RJ_status);
See below for more details.
RipJoin::RipJoin(const int projCnt, const AttrDesc AttrDescArray[], const AttrDesc *AttrDesc1, const Operator op, const AttrDesc *AttrDesc2, const int recLen, const int beta1, const int beta2, Status& returnStatus)
Initiates a Ripple Join iterator, which will in turn open two heap file scans. "beta1" and "beta2" represent the aspect ratio for the rectangles of the ripple join (see the paper for details). The other attributes are similar to those of QU_Join. See the pseudocode in the paper for some hints on how to set up the Ripple Join iterator.RipJoin::~RipJoin()
Cleans up after the iterator has completed.const Status RipJoin::getNext(Record & rec)
Returns (in "rec") the next record that is the result of the join. See the pseudocode in the paper for details. The return Status should be OK if another tuple is produced. If there are no more tuples, return JOINEOF (you should define this in error.C and error.h; but note that it doesn't necessarily indicate an error -- only if the higher level chooses to interpret it that way). Return reasonable error codes for other problems.Note that you can partially test last these three functions by simply running Minirel queries. Complete testing, though, will require you to write some testing code that will give different aspect ratios (i.e., values of "beta1" and "beta2" other than 1) to the Ripple Join constructor. Our testing of your code will also involve both running Minirel and called your RipJoin methods directly via a testing program.
That's all that's required (Phase 1). The following function, as mentioned above, is extra credit. Sure looks tempting, though, doesn't it?
const Status Ripple_OLAP(const attrInfo projNames[], const attrInfo *attr1, const Operator op, const attrInfo *attr2, const int beta1, const int beta2)
This is similar to QU_Join, except it will invoke the constructor for RipJoin with values for "beta1" and "beta2" that are not necessarily 1. We will assume the convention that the first attribute in projNames is the grouping attribute and the second one is the attribute on which the aggregate computation is being performed. There should be exactly two elements in projNames, then, hence the absence of a "projCnt" parameter. In addition, it will periodically print the running results of the AVG grouped aggregate. (The AVG aggregate applies only to numeric fields, so this is a good opportunity for an error message.) Here, "periodically" means after each step has completed. you should print to the screen each group value and running aggregate value along with the step number. For example, "After Step n:" followed by the result as computed so far. One suggestion for keeping track of the groups is to use a hash table; examples of their use are elsewhere in Minirel. How do you tell when a step is completed? The internal state of the RipJoin iterator has this information, so one way is to add a member function to retrieve the current step from the iterator. Other means are acceptable also.You should continue to use the same error handling mechanism that you used for the previous parts of the project. Feel free to augment this with new error codes and messages as needed, to use some, all, or none of those provided in error.[Ch], etc. The important thing is to flag the errors; naming them and deciding which error code to use, etc., is less important at this stage than simply recognizing that an error has occurred.
To get everything to work smoothly, we propose a few changes to the interface of the HeapFileScan class. These will already be available in the implementation of the HeapFileScan we will provide as a starting point to this part of the project. However if you are using your own implementation of HeapFileScan, you need to make note of the following :
Start by reading the Ripple Join paper (see link above). Then make a copy of the files and directories found in ~test594/project/part2 into your home directory. There are subdirectories here, so use the "-r" option of "cp" to make sure you copy everything recursively. You're already on friendly terms with some of these files; feel free to examine the others. You will create the files join.C and join.h. Join.c will contain your implementations of the functions above and join.h will contain the class definitions for the RipJoin class and any other declarations you decide you need. The "test" subdirectory contains some useful tests for the basic RippleJoin, but once you need to test non-unitary aspect ratios and Ripple_OLAP, you're on your own (i.e., write a simple test script, as we mentioned above). A more complete pseudocode for the Ripple Join iterator is now available in both postscript and pdf.
We hope you had fun and learned a lot building the heapfile and join methods!!