Consider the join R S where the join predicate is R.a = S.b, given the following metadata about R and S:

Relation R contains 20,000 tuples and has 10 tuples per page (block)

Relation S contains 5,000 tuples and has 10 tuples per page (block)

Attribute b of relation S is the primary key for S, and every tuple in S matches 3 tuples in R

There exists a unclustered B+-tree index on R.a with height 3

There exists a clustered B+-tree index on S.b with height 2

The main memory buffer can hold 5 blocks

Answer the following questions:

1. If R S is evaluated with a block nested loop join, which relation should be the outer relation? Justify your answer. What is the cost of the join in number of I/Os?

2. If R S is evaluated with an index nested loop join, what will be the cost of the join in number of I/Os? Which index you will use? Show your cost analysis.

3. What is the cost of a plan that evaluates this query using sort-merge join. Show the details of your cost analysis.

4. Evaluate the cost of computing the R S using hash join assuming: i) The main memory buffer can hold 202 blocks, ii) The main memory buffer can hold 4 blocks.