Assume that at most 5 tuples in s match each tuple in r.

Question

Compute the cost of using the following methods:

(a) Nested loops

(b) Block-nested loops

(c) Index-nested loops with a hash index on B in s. (Do the computation for both clustered and unclustered index.)



where r occupies 2,000 pages, 20 tuples per page, s occupies 5,000 pages, 5 tuples per page, and the amount of main memory available for block-nested loops join is 402 pages.

Answer 1

(a) Nested loops: scan r and for each of its 40,000 tuples scan s once. The result is

2,000 + 40,000 x 5,000 = 200,002,000 pages



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





(c) 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) x 40,000 = 90,000 pages



In case of an unclustered index, the matching tuples of s can be in different 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)x40,000 = 282,000 pages