CS245 Winter 2000 Assignment 5 due in class on Thursday February 10 PROBLEM 1 Do Problem 6.1.4 from textbook. PROBLEM 2 Do Problem 6.1.6 part (a) and (b) only, from textbook. PROBLEM 3 Do Problem 7.2.6 part (b) from textbook. PROBLEM 4 Do Problem 7.4.1 parts (c), (d), (f), (h) from textbook. PROBLEM 5 Suppose you have 2 relations, R(A, B, C) and S(B, C, D, E). You have a clustered unique (no duplicate keys) B+-tree index on attribute A for relation R. Assume this index is kept entirely in memory (i.e., you do not need to read it from disk). For relation S, you have two indices: * a non-clustered non-unique B+-tree index for attribute B * a clustered non-unique B+-tree index for attribute C Furthermore, assume that these two indices are kept in memory (i.e. you do not need to read them from disk). Also, assume that all of the tuples of S that agree on attribute C are stored in sequentially adjacent blocks on disk (that is, if more than one block is needed to store all of the tuples with some value of C, then these blocks will be sequentially located on the disk). Other relevant data: * 500 tuples of R are stored per block on disk. * T(R) = 500,000 (number of tuples of R) * 100 tuples of S are stored per block on disk. * T(S) = 100,000 (number of tuples of S) * V(S,B)= 40,000 (image size of attribute B in S) * V(S,C)= 40 (image size of attribute C in S) You want to execute the following query: SELECT * FROM R, S WHERE (R.B=S.B) AND (R.C=S.C) We present you with two query plans: Plan 1: For every block B of R, retrieved using the clustered index on A for R For every tuple r of B Use the index on B for S to retrieve all of the tuples s of S such that s.B=r.B For each of these tuples s, if s.C=r.C, output r.A, r.B, r.C, s.B, s.C, s.D, s.E Plan 2: For every block B of R, retrieved using the clustered index on A for R For every tuple r of B Use the index on C for S to retrieve all of the tuples s of S such that s.C=r.C For each of these tuples s, if s.B=r.B, output r.A, r.B, r.C, s.B, s.C, s.D, s.E You should analyze each of these plans carefully in terms of their behavior regarding accesses to disk. Your analysis should consider the behavior both in terms of the number of I/Os, as well as the total access time. Explain which of the plans is therefore better under what circumstances. Be sure to include in your analysis what accesses to disk are sequential accesses and which ones are random accesses. * Now consider what happens if instead V(S,C) = 500. Will one plan perform better than the other? * Instead of using the V-function to do your estimate, assume that the number of tuples returned is proportional to the size of the domain of an attribute. Let DOM(S,B) = 1000, and DOM(S,C) = 100. Re-calculate your estimates. END OF HOMEWORK 5