Part 1: Join Algorithms
In this part, you will implement some join algorithms: block nested loop join, sort merge, and
grace hash join. You can complete Task 1, Task 2 and Task 3 in any order you want. Task 4 is
dependent on the completion of Task 3.
Aside from when the comments tell you that you can do something in memory, everything else
should be streamed. You should not hold more pages in memory at once than the given
algorithm says you are allowed to. Doing otherwise may result in no credit.
Note on terminology: in lecture, we sometimes use both block and page describe the unit of
transfer between memory and disk. In the context of join algorithms, however, page refers to the
unit of transfer between memory and disk, and block refers to a set of one or more pages. All
uses of the word block in this part refer to this second definition (a set of pages).
Convenient assumptions:
For all iterators that will be implemented in this project you can assume hasNext() will
always be called before next() .
Any Record object provided through an argument or as an element of a list or iterator will
never be null .
For testing purposes, we will not be testing behavior on invalid inputs ( 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.
Your join operators, sort operator, and query plans do not need to account for underlying
relations being mutated during their execution.
CS186 Projects
Cookies
This site uses cookies to deliver its service and to analyse traffic. By browsing this site, you accept
our cookie policy.
Reject all
https://cs186.gitbook.io/project/
https://policies.gitbook.com/privacy/cookies