Introduction

In this assignment, you will implement the index nested loops join algorithm for equijoins. You should begin by reading the textbook chapter on Implementation of Relational Operators, particularly the section on Index Nested Loops Join.

You will carry out this assignment in teams of two (with the same partner as for the previous assignments).

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 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 of S
      char     *filename3,      // Name of heapfile for merged results
      IndexType in_type,        // the 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.

You should use the standard Minibase error protocol. 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 B+-Tree index for the inner heapfile S. Then you scan the outer heapfile R; for each tuple in the outer heapfile R, retrieve the matching tuples in S by scanning the B+-Tree on the inner heapfile S.

A couple of notes on the interfaces:

HeapFile::insertRecord(char* recPtr, int recLen, RID& outRid) inserts the record of length recLen pointed to by recPtr into the heap and passes back the newly allocated RID of the record in outrid.

HeapFile::getRecord(const RID& rid, char* const recPtr, int recLen) takes in an RID rid and passes back the record associated with rid in the character array pointed to by recPtr. It passes back the length of the record in recLen.

Scan::getNext(RID& rid, char* recPtr, int& recLen) passes back the RID of the next record in rid, copies the actual record into the array pointed to by recPtr, and passes back the length of the record in recLen.

You are expected to handle variable length keys in this assignment. You do not need to worry about alignment (if you don't understand what alignment is, you can safely ignore the rest of this paragraph; it won't be an issue in the data we use for testing). You may assume that the length of all columns will be a multiple of four. This implies that all columns are aligned on a four-byte boundary.

Getting Started

Please copy or download the Makefile from ~cs186/minibase/hwk/assign/IndexNL_au96/src into your own local directory. Then run gmake setup to copy the necessary files into that directory. The files you have in your local directory are

• Makefile: A sample Makefile for you to compile your project.
• index_nl.h: Specifications for the class index_nested_loop. You have to implement these specifications as part of the assignment. You can not modify the public members, but you can add private members.
• index_nl.C: This is an incomplete file - your task is to complete it. Make sure to read the comments in here!
• index_nl_driver.C: index nested loop join test driver program.

You can find other useful include files (scan.h, heapfile.h, index.h, btfile.h) in ~cs186/minibase/hwk/assign/IndexNL_au96/include.

When you ran gmake in the instructions above, you linked the code in your directory with a library called libwith.a. This library contains a compiled version of a solution to the assignment, which you can produce by running gmake solution. Your challenge will be to make the code in your directory work with a library called libwithout.a .

Another Note: This assignment only works under HP-UX. Our libraries do not work under Ultrix.

How to Turn In Homework 4

For each team, choose one member to be responsible for turning in the assignment.  That member of the team should create a directory named hwk4 at the top level of their account. Into that directory he/she should copy the files index_nl.C and index_nl.h. She/he should then create a file called README formatted as follows:

Name and login of Team Member 1
Name and login of Team Member 2

An example file might look like:

Paul Aoki, cs186tb
Marcel Kornacker, cs186tc

Any other notes in the README file will be ignored.

At this point, the person turning in the assignment can turn it in via the turnin command. To use this, he/she simply types turnin cs186 hwk4. This will only work if he/she has got the hwk4 directory set up as above. The turnin command should produce output like the following:

franklin% turnin cs186 hwk4
Checking authorization for user:cs186te
Creating turnin directory: cs186te.24Sep16:52:44
8 blocks