Compute the cost of r  A=B s using the following methods:

Question

1. Nested loops
2. Block-nested loops
3. Index-nested loops with a hash index on B in s (consider both clustered and unclustered index)

where r occupies 2000 pages, 20 tuples per page; s occupies 5000 pages, 5 tuples per page; and the amount of main memory available for a block-nested loops join is 402 pages. Assume that at most 5 tuples of s match each tuple in r.

Answer 1

1. Nested loops: scan r and for each of its 40,000 tuples scan s once. The result is
2, 000+ 40, 000× 5, 000= 200, 002, 000 pages

2. Block-nested loops: Scan s once per each 400-page block of r, i.e., 5 times. The result therefore is:

3. Index-nested loops: The result depends on whether the index on B in s is clustered or not. For the clustered case, all tuples of s that match a tuple of r are in the same disk block and require 1 page transfer (since we assumed that at most 5 tuples of s match, they all ?t in one disk block). We also need to search the index once per each tuple of r. Suppose the later takes 1 disk access. Thus, the total is
2, 000+ (1 + 1 ? 1.2) × 40, 000 = 90, 000 pages
In case of an unclustered index, the matching tuples of s can be in di?erent blocks. As before, assume that s has at most 5 matching tuples per tuple in r. Thus, the cost would be
2, 000 + (1 + 5 ? 1.2) × 40, 000= 282, 000 pages