What is the general idea behind how the SortMerge class we are building works?

This is an implementation of the pull idea for operators as discussed in Chapter 12 of the textbook. This fits quite well with the idea behind iterators as in Java.

First, the query plan generator will set up the query plan (tree). For any join operator in the query tree that has been designated as a merge join, it will make a new SortMerge object to handle the join. Consider one of these SortMerge objects. Call it SM. SM will read records from two iterators, an "outer" and an "inner" representing the two tables (streams) it is joining. These are the operators immediately below SM in the query tree and are of type (Minibase's) Iterator. There will be some operator immediately above SM in the query tree (refer to this operator as the caller) that is pulling results from SM; in other words, the caller is iterating over the Iterator SM.

Second, at query execution time, the caller operator calls our SM object, each time asking SM for another join record. It will use SM.get_next() for this. Thus, the caller is using SM as an iterator to walk the join results one at a time.

Third, the query plan generator will initialize shutting the query process down. It does this by calling close on the object at the root of the query tree (an Iterator, of course). The root object calls close on any iterators it has been reading. Thus, the caller will call SM.close(); and SM should, in turn, call close on the two iterators it is reading, "inner" and "outer".

The SortMerge class just needs three things implemented, corresponding to the three steps above, respectively:

1. the constructor
2. get_next()
3. close()

First, the constructor is called when the query tree is being set up. Second, get_next is called repeatedly during query execution. Third, close() is called when the query process is being shut down.

This way of doing things seems to be quite reasonable, but it may seem quite odd when you go about coding. In SortMerge's constructor, you just set up the join, but you do not actually do any of the join processing. The set up includes determining whether either of your input iterators need sorting (and, if so, calling Sort to accomplish this), and preparing the variables / objects you will be using during the join processing.

The real work is done effectively in get_next. Each time SM.get_next() is called, it returns a Tuple that represents the next join result; or it returns null if there are no more join results. So get_next does not compute the entire join result when called. Rather, successive calls to get_next are iteratively computing the join. Essentially, we are implementing pipelining!

This way of doing things may be a bit mind-bending at first, if you have not programmed anything like it before. It is like event-driven programming. However, it is not so bad once you understand what is going on.

The close method is quite simple, but important. One simply needs to close SM's two input iterators. This is important since we need to free up those resources. For instance, if you forget this, your implementation will crash after a couple of the test queries because there will not be enough buffer pool available. The old queries's resources were not properly released. (If we were programming in C++, we would also need to free any objects we had made for use during the join processing. However, we are programming in Java, so we do not have to worry with this. Java's garbage collector takes care of it.)

I called Sort on am1, representing the outer stream's Iterator, because it needed sorting. Then when I tried to read a Tuple from am1, I got back null, meaning there was nothing on the stream! What's wrong?

The call to Sort invokes an external sort routine. That routine reads all the records from am1, sorts them into a temporary file, and then returns to you a new Iterator to walk over these sorted tuples. (Okay, actually it returns to you a Sort object. However, Sort is a subclass of Iterator in Minibase.)

So yes, am1 is "empty" after the call. All of its records have been consumed. You need to use the Sort to iterate.

For sanity, what I do is have two private Iterator variables, outerS and innerS ("S" for stream). If am1 (the outer) does not need sorting, I set outerS = am1. Otherwise, I set outerS = new Sort(..., am1, ...). Likewise for innerS with am2.

When do we throw the exceptions JoinNewFailed and JoinLowMemory?

The exception JoinNewFailed is meant for when SortMerge could not set up properly. This happens when it cannot successfully allocate the objects it needs to perform, such as an IoBuf and Tuple's to hold an outer and an inner tuple. Check after you have new'ed these that none is null. If any is null, the allocation was unsuccessful; punt by throwing JoinNewFailed.

The exception JoinLowMemory is meant for when there is not enough memory page-wise, amt_of_mem, to run the join. Here, we only need that amt_of_mem >= 2, since we are merging just two sorted streams.

I see that one of the parameters of SortMerge is int join_col_in1. Are the two relations joined on just a single column?

Yes. This only accommodates equi-joins with a single-column join condition. So the project is limited to this too.

What do boolean in1_sorted and boolean in2_sorted tell us? Does it mean whether am1 and am2, respectively, are sorted already for the join? And what are int sortFld1Len and int sortFld2Len?

Yes, the booleans are telling you whether the outer stream ("am1") and the inner stream ("am2") are sorted, respectively, already with respect to the join criterion.

If either is not already sorted, your code in SortMerge will need to call the external sort routine of Minibase, Sort, to do the job. If either is already sorted, you are lucky, and can skip that step in that case.

Just as the join here accommodates only a single join column, the sort is only with respect to a single column. The parameters int sortFld1Len and int sortFld2Len report the length of the column (field) for the outer table (R) and the inner table (S). That is, sortFld1Len is the length of field in R to sort on, and sortFld2Len is the length of field in S to sort on. This information is needed to call Sort.

Why do I have to initialize a Tuple object before I can use it?

Yes, you have to "format" it. A tuple is for a given schema; that is, it has certain columns, each of certain types (e.g., string, integer, & real). The system has to know the schema for this tuple to be able to allocate the proper amount of space for the tuple, and to store and retrieve the values for the tuple correctly.

Do I need to format a tuple object, say joinTuple, every time before I use it (say store new values in it)?

No, not if you are using joinTuple each time to collect another tuple value of the same schema, say a join result. You only need to format it once. However, if you wanted to reuse that tuple object to collect the results of another schema type, then you would need to format it again for the new schema.

That said, a good place to format the tuple objects you are going to use (e.g., joinTuple) would be in the SortMerge constructor. You should not need to initialize anything in get_next.

How do I actually format a Tuple object for use? How do I prepare, say, joinTuple for collecting the join result in get_next?

There is a class in Minibase called TupleUtils that provides what is needed. It contains useful utilities for dealing with Minibase tuples. For formatting joinTuple, call setup_op_tuple. In its parameters, you pass it information about two input tuple "schemas" (inner and outer), and the projection wanted for the output tuple's schema (for joinTuple). It passes back information via some of the parameters, and a return argument.

    // A container to hold the joined tuple.
    joinTuple = new Tuple();

    AttrType[] joinTypes = new AttrType[n_out_flds];
    short[]    ts_size   = null;

    ts_size =
        TupleUtils.setup_op_tuple(
            joinTuple,  // Output: Gets initialized by the call.
            joinTypes,  // Output: Gets initialized by the call.
            in1,        // Input: Attr-Type array for outer.
            len_in1,    // Input: #columns of outer schema
            in2,        // Input: Attr-Type array for inner.
            len_in2,    // Input: #columns of inner schema
            s1_sizes,   // Input: Array w/ sizes of string columns for outer.
            s2_sizes,   // Input: Array w/ sizes of string columns for inner.
            proj_list,  // Input: Says what columns to keep for joinTuple.
            n_out_flds  // Input: #columns in joinTuple's schema.
        );
	

All the parameters marked as "Input" above, you have available because they are parameters that SortMerge is called with. You have to provide a tuple object, e.g., joinTuple, and an array of AttrType (of length n_out_flds). These objects will be altered by the call. Lastly, the call returns an array of short, called ts_size above. This is as long as the number of columns of type "string" in joinTuple's schema. Each string can be of a different max-length, so Minibase has to track this information.

So we are keeping around four pieces of information to keep track of joinTuple and its schema:

1. joinTuple: A container for holding a join tuple's values.
2. joinTypes: An array that specifies the column type for each column in joinTuple.
3. ts_size: An array matching up with joinTuple's string columns, telling us how long each is.
4. n_out_flds: The number of columns in "joinTuple".

Okay. Not so object-oriented. We should have that all encoded in the obect joinTuple, no? Ideally, for sure. I did not write Minibase, however, so I disavow responsibility. :-)

Okay, that explains how to set up joinTuple. How do I "format" the tuple objects that I want to use to read the outer and the inner streams?

See the method in Tuple called setHdr. Say you have a Tuple called tupleOuter. You might make the call

tupleOuter.setHdr((short)inOuterLen, inOuter, s1_sizes);

passing in the requisite three pieces of information, as explained above. Here, inOuter is an array of AttrType, describing the column types, and s1_sizes is an array of short, describing the lengths of the string columns.

We need to temporarily store tuples from the inner stream ("table") that have the same join column value. The IoBuf class has been advertised for this. How do we use it?

Yes. You need space to put the equivalent tuples temporarily, so you can read them again, if needed.

This is done outside of the buffer pool here. So the temps are being kept in another part of main memory that you have allocated for the IoBuf. IoBuf is quite general (for handling such temporary storage) and also takes the name of a temporary heap file. It will store the temporary tuples on disk in the heapfile if the "buffer" runs out of room.

The good news is that IoBuf takes care of this for you, so you do not have to. The bad news is that you have to set it up correctly for it to work, and this is not so straightforward.

On new IoBuf, a new object has been allocated, but it has not been initialized yet. Say we have said

matchBuf = new IoBuf();

To set it up, we call IoBuf's init(...).

public void init(byte[][] bufs,
                 int      n_pages,
                 int      tSize,
                 Heapfile temp_fd)

The first argument, bufs, is for the temporary, main-memory space that the IoBuf object is going to use. It does not allocate this itself! So, you need to pass it a reference to space that you have allocated for this purpose.

The second argument, n_pages, is the number of pages bufs is space-wise. One page of space is sufficient here for this project.

With the third argument, tSize, we are telling it how big a tuple is in bytes.

The fourth argument, temp_fd, is for the heapfile that the IoBuf object uses, if needed.

We have to provide all this! For making some space, we could do something like

matchSpace = new byte [1][MINIBASE_PAGESIZE];

Of course, matchSpace should be declared somewhere, and be the right type. E.g.,

private byte matchSpace[][];

Say we have set up a Tuple object innerTuple for holding onto a tuple from the inner-stream, and matchBuf will be holding these.

For the heapfile, say we have

private Heapfile innerHeap;

In the code, we can set it up. E.g.,

innerHeap = null;
try {
    innerHeap = new Heapfile(null);
}
catch(Exception e) {
    throw new SortException (e, "Creating heapfile for IoBuf use failed.");
}

Finally, we can initialize our matchBuf.

matchBuf.init(matchSpace, 1, innerTuple.size(), innerHeap);

There. Not so bad really, eh?

How do I "flush" my IoBuf, call it matchBuf, when I want to write a new group to it?

How do I read through matchBuf a second time? (That is, how do I reset this "iterator"?)

To reuse matchBuf, call matchBuf.init(...) again. You can pass it the same arguments as before, as in the example above:

matchBuf.init(matchSpace, 1, innerTuple.size(), innerHeap);

You do not have to allocate matchSpace again or any of that. This has the effect of clearing out matchBuf.

To "reset" the "iterator" matchBuf so that you can iterate through its contents again, call

matchBuf.reread();

That is what that method is for. The javadoc is not so clear on this. Apologies. But that is what this FAQ is for!

What is IoBuf's Get(Tuple T) doing? How do I use it?

Its return value is of type Tuple and you pass it a Tuple as an argument. What is the deal here?

To use Get(T), one must pass it a Tuple object (here, T). This must exist, and not just be a reference. So you need to have said T = new Tuple(); at some point. Get does not create a Tuple object to return. It loads the appropriate information into the Tuple object, T, that you pass it.

Fair enough, you say. But why does it also have a return value? And of type Tuple too?

Well, it is using the return value to indicate whether it was successful in getting another tuple. If it is at the end of the stream, the Get will be unsuccessful. In the case of success, it returns a reference to your T! (Okay. So a bit redundant.) In the case of no tuples remaining to be gotten, it returns null.

So this is how you can tell whether you are at the end of the stream or not. You'll get back a null at the end.

Now a proper Iterator in Java protocol has a getNext and a hasNext. One uses the hasNext, which returns a boolean, to ask whether there is another item before calling getNext. That is cleaner. One day when we rewrite Java Minibase, that is probably what we should do.

In the least, I think that this would be cleaner if Get returned a boolean indicating success or not rather than Tuple. Oh well. C'est la vie.

Does IoBuf remove the tuple from its buffer storage when you call Get? Or does the tuple remain there?

It remains. So you can read the IoBuf a second time (and a third time, etc.) and see it again.

May I use Vector or ArrayList instead of IoBuf to store my group temporarily? I do not like IoBuf. No, not all all.

Not for full credit, you don't. Vector or the like could be made to work, but it is a kludge here. It is growable, and we have no control over how much main memory our SortMerge might be making off with.

IoBuf is well behaved for this, and offers a correct, relationally-sound implementation.

Do use Vector (etc.) if you must, or cannot get IoBuf to working. It will be two points off from the 15 point maximum for the project.

Deleting redundant result tuples isn't our job, right? Is it okay for a query to return duplicate tuples when distinct was not specified in the SLQ?

Right. Whether duplicates are to be eliminated or not is specified in the query, in the SQL. In either case, this is not handled within SortMerge, but elsewhere.

Of course an SQL query must return duplicates if distinct is not specified. That is part of SQL.

Are we responsible to take care of the other conditions in the query's where clause? And projecting to just the columns that the query asks for?

Yes and no. You are not responsible for writing code for this. However, the SortMerge routine is to check the conditions and to apply the projects.

You can handle it something like this in get_next().

    // Finally!  Join the OUTER tuple and the INNER.
    // That is, if the predicates of the query are true.
    if (PredEval.Eval(outputFilter, // The query's CondExpr
                      tupleOuter,   // The current tuple from Outer
                      tupleInner,   // The current tuple from Inner
                      inOuter,      // The AttrType of Outer tuples
                      inInner       // The AttrType of Inner tuples
        ) == true) {

        Projection.Join(tupleOuter,
                        inOuter,
                        tupleInner,
                        inInner,
                        joinTuple,    // The Joined-Tuple
                        permMat,      // The projection list
                        numOfOutFlds  // # fields in joined-tuple
                       );
        goodTuple = true;
    } else {
        goodTuple = false;
    }
    

If goodTuple, get_next() will return joinTuple in the end. Otherwise, get_next() keeps looking for a join-tuple that also satisfies the conditions (outputFilter) that it can return.