CS3223: Database Systems Implementation

Project Assignment 2: Index Structures

In this assignment, you will extend SimpleDB to support btree and hash indexes. Fortunately, you do not need to implement the code for btree and hash indexes – they have already been implemented. The code that you need to study in this assignment can be found in the following subdirectories:

· index

· index/btree

· index/hash

· index/planner

· index/query

You will also need to make changes to the file SimpleDB.java in the subdirectory server.

1. Create an index on studentdb tables

· Figure out the SQL command to do so, i.e., create index … [Hint: Look at how the command is being parsed. You can find this in the file Parser.java in the subdirectory parse. Or simply look at the grammar.]

· Add the commands to create indexes to the CreateStudentDB program. You can create as many indexes as you would like to. You should create at least one to try out; in particular, the index on student. Rerun CreateStudentDB to create the tables and the indexes. Note that you should delete the database (i.e., the studentdb folder) under the OS before running (or use a different database name).

2. Use the appropriate pair of (QueryPlanner, UpdatePlanner)

See SimpleDB.java (in subdirectory server). You will find in the code two (QueryPlanner, UpdatePlanner) pairs, one of which has been commented out. Comment out the first pair, and uncomment the second pair. The second pair uses HeuristicQueryPlanner and IndexUpdatePlanner which support indexing. This will be clear if you look at these codes (but not necessary at this point).

3. Run some test programs

· Run the programs IndexRetrievalTest.java and IndexUpdateTest.java in subdirectory index. You need to make sure you have created an index on MajorId of the Student table (and make sure you are using the right database if you have renamed it).

· Run the program IndexSelectTest.java in subdirectory index/query. You need to make sure the necessary indexes have been created (if you have not already done so).

4. Support for multiple index structures

· The basic code (as you have run above) has a default setting for the index structure used. Figure out which is that – hash or btree?

· Repeat the experiments in Step 3 above by setting the default to the other structure.

· Modify SimpleDB so that it supports both indexes. In other words, it is possible to create a hash index on attribute A, and a btree index on attribute B. Note that you will need to change the parser to accept SQL commands like create index … using hash.

5. Submit a report

Submit a report that describes the changes made to support multiple indexes. It is sufficient to create a table as follows:

File to change	Changes
simpledb/parse/Lexer.java	Added keywords “using” and “hash” and “btree” to keywords (in routine initKeywords())
Simpledb/parse/Parser.java	In routine CreateIndex(), added some code to handle “using hash” and “using btree”
….	….