Consider a relation schema, R(A, B), with the following characteristics:

Question

a. Total number of tuples: 1,000,000
b. 10 tuples per page
c. Attribute A is a candidate key; range is 1 to 1,000,000
d. Clustered B+ tree index of depth 4 on A
e. Attribute B has 100,000 distinct values
f. Hash index on B

Estimate the number of page transfers needed to evaluate each of the following queries for each of the proposed methods:
1. ?A<3000: sequential scan; index on A
2. ?A>3000?A<3200?B=5: index on A; index on B
3. ?A=22 ? Bƒ=66: sequential scan; index on A; index on B

Answer 1

The relation has 100,000 pages.
1. ?A<3000
Sequential scan
Since the index is clustered, the relation is sorted, so to scan the tuples with
A < 3000 we need to fetch
100, 000 ? 3, 000/1, 000, 000 = 300 pages
Index on A
Use the index to ?nd the last page page where A < 3000 and then scan the relevant pages. The cost is 4 to search the
index plus the cost of the scan, which is the same as above:
4 + 300 = 304 pages

2. ?A>3000 ? A<3200 ? B=5
Index on A
Use the index to ?nd the ?rst page where A > 3000 then scan the pages until you ?nd the ?rst page where A ? 3200:
4 + 100, 000 ? 200/1, 000, 000 = 24 pages
Index on B
On the average there are 1,000,000/100,000 = 10 tuples per any given value of B. Use the hash index on B to ?nd the
tuples where B=5. Then we need one page transfer for each tuple in the bu?er. In total about 1.2 + 10 = 11.2 page
transfers.

3. ?Aƒ=22 ? Bƒ=66
Sequential scan
Need to scan the entire relation: 100,000 page transfers.
Index on A
Not helpful. For every value in the range of 1 to 1,000,000, except 22, use the index to get the page that holds that
tuple: 4(depth of B+ tree) 999, 999(tuples) = 3, 999, 996 page transfers.
Index on B
This index is also not of much use. For each value in the range of 1 to 100,000, except 66, ?nd the bucket that contains
pointers to the actual tuples: 1.2 x 99, 999. For each such tuple (there are about 999,990 of them) fetch the
corresponding page. The total cost is thus
1.2 × 99, 999 + 999, 990 = 1119989 pages