Consider a relation s over the attributes A and B with the following characteristics:

Question

 7,000 tuples with 70 tuples per page
 A hash index on attribute A
 The values that the attribute A takes in relation s are integers that are uniformly distributed
in the range 1 ? 200.
(a) Assuming that the aforesaid index on A is unclustered, estimate the number of disk accesses needed to compute the query A=18(s).
(b) What would be the cost estimate if the index were clustered?

Answer 1

It takes 1.2 I/Os to nd the right bucket. The number of tuples selected from s is expected to be 7000/200 = 35.
(a) If the index is unclustered, every tuple can potentially lead to a separate I/O. So, the cost will be ceiling(1.2 + 35) = 37.
(b) If the index is clustered, then 37 tuples can at most span 2 pages, so the I/O cost would be ceiling(1.2+2)=4.