You are given the following information about two tables, r and s.

Question

• Table r occupies 800 pages, 20 rows per page, one of its attributes is A
• Table s occupies 200 pages, 10 rows per page, one of its attributes is B
• Main memory has 52 buffers
• _ Table r occupies 800 pages, 20 rows per page, one of its attributes is A
• _ Table s occupies 200 pages, 10 rows per page, one of its attributes is B
• _ Main memory has 52 bu_ers

(a) Compute the minimum cost (measured as the number of I/O operations) of a blocknested
• loops join r ZA=B s. Specify how the bu_ers are used and explain your reasoning
• carefully. An answer that is just a number gets no credit.

(b) Assume there is an unclustered, 3-level, B+ tree index on r with search key A and that
each row of s joins with 5 rows of r. Compute the cost of an index-nested loops join.
Explain your reasoning carefully. An answer that is just a number gets no credit.

Answer 1

Solution:
(a) 50 input buffers for s, one input buffer for r, one output buffer s is broken into 4 segments, one pass over r for each segment
total cost = 4 passes over r (= 3200 I/O ops) + 1 pass over s (= 200 I/O ops) = 3400 I/O
operations

(b) 200 I/O ops to scan S
num. rows in s = 2000
for each row of s it takes 3 + 5 I/O ops to get the 5 matching rows of r
total cost = 2000  8 + 200 = 16,200 I/O ops.