Introduction

In this assignment, you will implement the index nested loops join algorithm.

Available Documentation

You should begin by reading the chapter on Implementation of Relational Operations, in particular, the section on Index Nested Loops Join.

What You Have to Implement

class index_nested_loop {
  public:
    index_nested_loop(
      char     *filename1,    // Name of heapfile for relation R.

      int       len_in1,      // # of columns in R.

      AttrType  in1[],        // Array containing field types of R.

      short     t1_str_sizes[], // Array containing size of columns in R.

      int       join_col_in1,   // The join column number of R.

      char     *filename2,    // Name of heapfile for relation S

      int       len_in2,      // # of columns in S.

      AttrType  in2[],        // Array containing field types of S.

      short     t2_str_sizes[], // Array containing size of columns in S.

      int       join_col_in2, // The join column number of S.

      char     *filename3,    // Name of heapfile for joined results

      IndexType in_type,       // Index type for inner relation

      Status&   s             // Status of constructor

    );
   ~index_nested_loop();
};

The index_nested_loop constructor joins two relations R and S, represented by the heapfiles filename1 and filename2, respectively, using the index nested loops join algorithm. Note that the columns for relation R (S) are numbered from 0 to len_in1 - 1 (len_in2 - 1). You are to concatenate each matching pair of records and write it into the heapfile filename3. The error layer for the index_nested_loop class is JOINS.

You will need to use the following classes which are given: HeapFile, Scan, BTreeFile and BTreeFileScan. You will call BTreeFile methods to build up a btree index for the inner heapfile S. Then you scan the outer heapfile R, for each tuple in the outer heapfile R, retrieve the matching S tuples by scaning the Btree index on the inner heapfile S.

Where to Find Makefiles, Code, etc.

Information on setting up the code and the error protocol to follow.

What to Turn In, and When

You should turn in hardcopies of your code together with hardcopies of the output produced by running the tests provided by me. A solution will be made public after the due date, and solutions turned in after that time will not receive any credit. So be sure to turn in whatever you have, even if it is not working fully, at that time.