Page 2 Q1. b, c, e Q2.
Sample Solutions to Midterm #3
Sort phase: We have sorted runs of 35 pages each.
Merge phase #1: The maximum number of SRs that can be merged is 34. Thus, we can handle up to 35(34) = 1190 pages, so far.
Merge phase #2: The maximum number of SRs that can be merged is 34. Thus, we can sort a maximum of 1190(34) = 40,460 pages in this instance of 3PMMS.
Page 3 Q3.
Level = 0
000 (0,16,32)¡ú(64,-,-)
001 (1, 17, – )
010 (2, 10, 18)
Next = 3
11 (3, 7, – )
100 (4, 12, – )
101 (5,-,-)
110 (6,-,-)
Page 4
Q4a.
floor((4096bytes/leafpage)/ (4+5+4+10)bytes/DE)=178DE/leafpage
ceiling( 105,000 DE / (178 DE / leaf page) ) = 590 leaf pages ceiling ( 590 / (178 + 1) ) = 4 level-l pages
ceiling ( 4 / (178 + 1) ) = 1 root page
Q4b.
1 + 1 + 590 = 592 page I/Os
Page 5 Q5.
Only the hash index on P.patID is useful here. There is no other way to solve the problem with INL.
Therefore, the outer table must be Admissions.
We will read all of Admissions, and join each tuple with the Patient table. Once we find the data entry in the hash index, we need to fetch the data row to get the fields called P.patName and P.patCity.
Cost=#ofpageI/Os =(#ofpagesofA)+(#oftuplesofA)*(1.2+1) = 1500 + 105,000 *(1.2 + 1)
= 232,500
… where the # of pages of A is: ceiling( 105,000 rows / 70 rows/page) = 1500.
Page 6 Q6.
Admissions: ceiling(105,000 records / 70 records/page) = 1500 pages Patient: ceiling( 50,000 records / 50 records/page) = 1000 pages
BNL join page I/Os = 1000 + ceiling(1000 / (17-2) ) * 1500 = 1000 + 67 * 1500
= 101,500
Note: Switching the outer and the inner table gives the same # of page I/Os, in this case; therefore, we¡¯ll award full marks for either.
Page 7
Q7a.
Read in 10 cylinders at a time, and write out 10 cylinders at a time. We¡¯ll do this once per sorted run. There will be 8 SRs in all.
Reads =(1LS+9SS)*8=8LS+72SS Writes =(1LS+9SS)*8=8LS+72SS
Q7b.
Reads: In this case, every read is an LS. Therefore, we get 0 SS + 80 LS.
Writes: How many writes do we do? ceiling(80 / 2) = 40 Each write involves 1 LS and 1 SS.
40 * (1 LS + 1 SS) = 40 LS + 40 SS.