EECS 484 F19 - Homework 4 University of Michigan EECS 484

EECS 484 F19 - Homework 4 Deadline -- 6:00 PM on Tuesday, Nov 26th, 2019 Deliverables: You need to submit all your solutions in a single PDF on Gradescope. Your solutions can be either handwritten or created electronically, as long as they are clear. This homework is to be done in teams of 2 students; individual work is permitted, but not recommended. Both members of each team will receive the same score; as such, it is not necessary for each team member to submit the assignment. Create a group of 2 under Homework 4 in Gradescope before you submit. No late days for homework! If you miss the due date, you get 0 points. No exceptions on this. By submitting this homework, you are agreeing to abide by the Honor Code: I have neither given nor received unauthorized aid on this assignment, nor have I concealed any violations of the Honor Code. Question 1 (12 points): Consider doing Grace Hash Join algorithm on a system with number of pages in memory equal to B, answer the following questions: 1. How many partitions do we end up having if we only do one round of hashing in the partition phase?(4 points) 2. How many partitions do we end up having if we do 2 rounds of hashing with 2 different hash function in the partitioning phase? (4 points) 3. Can we use the same hash function in partitioning phase and probing phase? Justify you answer with one or two sentences. (4 points) Question 2 (20 points): In class, we developed a cost model for various relational database operations, such as joins. We counted the total number of I/Os (i.e., writing or reading a page) required to perform each operation. From there, we could estimate the relative performance of two query plans. If we were to consider a nested-loop join vs. a hash join, for example, we might guess that using the hash join would be better because it would require fewer I/Os.