Question 3: Join Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . [10 points] Consider relations T1(X,Y) and T2(X,Z) to be joined on the common attribute X. Assume that there are no indexes for either relations. There are B=50 pages in the buffer. Table T1 spans M =1600 pages with 50 tuples per page. Table T2 spans N =500 pages with 100 tuples per page. What are the I/O costs for the following joins? Assume the simplest cost model, where pages are read and written one at a time. Assume that you will need one buffer block to hold the evolving output block and one input block to hold the current input block of the inner relation. Ignore the cost of the final writing of the results (a) [3 points] Block nested loop join with T1 as the outer relation and T2 as the inner rela- tion. 2 17,600 2 18,100 2 18,600 2 20,400 2 22,100 2 22,800 (b) [3 points] How many passes are necessary to build the hash table for T1 in a hash join operation? 2 1 2 2 2 3 2 4 (c) [4 points] What is the I/O cost for a hash join between T2 and T1 under the optimal arrangement (i.e., T2 as the outer relation)? 2 2,300 2 4,200 2 6,300 2 7,000 2 7,600 2 8,400

Uestion 3: Join Algorithms [10 points ] Consider relations T1(X,Y) and T2(X,Z) to be joined on the common attribute X. Assume that there are no indexes for either relations. - There are B=50 pages in the buffer. - Table T1 spans M=1600 pages with 50 tuples per page. - Table T2 spans N=500 pages with 100 tuples per page. What are the I/O costs for the following joins? - Assume the simplest cost model, where pages are read and written one at a time. - Assume that you will need one buffer block to hold the evolving output block and one input block to hold the current input block of the inner relation. - Ignore the cost of the final writing of the results (a) [3 points] Block nested loop join with T1 as the outer relation and T2 as the inner relation. 17,60018,10018,60020,40022,10022,800 (b) [3 points] How many passes are necessary to build the hash table for T1 in a hash join operation? 1234 (c) [4 points] What is the I/O cost for a hash join between T2 and T1 under the optimal arrangement (i.e., T2 as the outer relation)? 2,300 4,200 6,300 7,000 7,600 8,400