CS3223: Database Systems Implementation

Project Assignment 4: Join algorithms

SimpleDB currently supports cross product. It can also work with index-based join. In this assignment, you will extend SimpleDB to support the following join algorithms:

a) Sort-merge join. The code for sort-merge join is available - see MergeJoinPlan and MergeJoinScan in simpledb/materialize subdirectory. You need to figure out how to integrate them - see TablePlanner in simpledb.opt subdirectory.

b) Index-based join (this is already available, just need to understand and get it to work). Look at TablePlanner in simpledb.opt; in particular, focus on the routines related to selecting indexes for join queries. It suffices to restrict to just equality predicates for index joins (afterall, hash index only supports equality predicates).

c) Nested-loops join. See makeProductJoin (in TablePlanner) which is essentially doing a cross product plus a selection. However, for nested-loops join, there should be no additional selection operation. You should be able to adapt the code for ProductPlan and ProductScan for this. You can design your own solution too.

You should be using the (HeuristicQueryPlanner, IndexUpdatePlanner) pair in this assignment.

Run your test programs in the student database. [Note that you may need to rename your database (or delete the old one before you rerun).

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
…	…
…	….
….	….