block
in this part refer to this second definition (a set of pages).hasNext()
will always be called before next()
.null
.null
objects, negative buffer sizes or buffers too small to perform a join, invalid queries, etc...). You can handle these inputs however you want, or not at all.SNLJOperator
. You should take a look at it to get a sense for how the pseudocode in lecture and section translate to code, but you should not copy it when writing your own join operators. Although each join algorithm should return the same data, the order differs between each join algorithm, as does the structure of the code. In particular, SNLJ does not need to explicitly manage pages of data (it only ever needs the next record of each table, and therefore can just use an iterator over all records in a table), whereas all the algorithms you will be implementing in this part must explicitly manage when pages of data are fetched from disk.TestNestedLoopJoin
depend on a properly implemented BNLJ.BNLJOperator
. The next
and hasNext
methods of the iterator have already been filled out for you, but you will need to implement the fetchNextRecord
method, which should do most of the heavy lifting of the BNLJ algorithm.fetchNextLeftBlock
, which should fetch the next non-empty block of left table pages from leftIterator
, and fetchNextRightPage
, which should fetch the next non-empty page of the right table (from rightIterator
).fetchNextRecord
method should, as its name suggests, fetches the next record of the join output. When implementing this method there are 4 important cases you should consider:BNLJOperator
, all the tests in TestNestedLoopJoin
should pass.SHJOperator.java
. Simple Hash Join performs a single pass of partitioning on only the left records before attempting to join. Read the code for SHJ carefully as it should give you a good idea of how to implement Grace Hash Join.GHJOperator.java
. You will need to implement the functions partition
, buildAndProbe
, and run
. Additionally, you will have to provide some inputs in getBreakSHJInputs
and getBreakGHJInputs
which will be used to test that Simple Hash Join fails but Grace Hash Join passes (tested in testBreakSHJButPassGHJ
) and that GHJ breaks (tested in testGHJBreak
) respectively.Partition.java
in the query/disk
directory will be useful when working with partitions. Read through the file and get a good idea what methods you can use.GHJOperator.java
, all tests in TestGraceHashJoin.java
will pass. There will be no hidden tests for Grace Hash Join. Your grade for Grace Hash Join will come solely from the released public tests.SortOperator
by the Run
class (located in query/disk/Run.java
). As runs in external mergesort can span many pages (and eventually span the entirety of the table), the Run
class does not keep all its data in memory. Rather, it creates a temporary table and writes all of its data to the temporary table (which is materialized to disk at the buffer manager's discretion).sortRun
, mergeSortedRuns
, mergePass
, and sort
methods of SortOperator
.sortRun(run)
should sort the passed in data using an in-memory sort (Pass 0 of external mergesort).mergeSortedRuns(runs)
should return a new run given a list of sorted runs.mergePass(runs)
should perform a single merge pass of external mergesort, given a list of all the sorted runs from the previous pass.sort()
should run external mergesort from start to finish, and return the final run with the sorted dataTestSortOperator
should pass.SortOperator
to sort during the sort phase of SMJ.SortMergeIterator
inner class of SortMergeOperator
.SortMergeOperator
and your implementation of SortOperator
may be tested independently. You must not use any method of SortOperator
in SortMergeOperator
, aside from the public methods given in the skeleton (in other words: don't add a new public method to SortOperator
and call it from SortMergeOperator
).SortMergeIterator
, all the tests in TestSortMergeJoin
should pass.database.query.TestNestedLoopJoin
database.query.TestGraceHashJoin
database.query.TestSortOperator
database.query.TestSortMergeJoin