Problem 5: Query Evaluation

Consider the join between relations R and S, where the join condition is R.a = S.b. We are given the following information about the two relations. The cost metric is the number of page I/Os, and the cost of writing out the result should be uniformly ignored.

Relation R contains 10,000 tuples and has 10 tuples per page.

Relation S contains 2,000 tuples and also has 10 tuples per page.

Attribute b of relation S is the primary key for S.

Both relations are stored as simple heap files.

Neither relation has any indexes built on it.

52 buffer pages are available.

Questions:

What is the cost of joining R and S using a simple nested loops join?

What is the cost of joining R and S using a block nested loops join?

What is the cost of joining R and S using a sort-merge join?

What is the cost of joining R and S using a hash join?

How many tuples will the join of R and S produce, at most, and how many pages would be required to store the result of the join back on disk?

If secondary B+ indexes existed on R.a and S.b, would either provide a cheaper alternative for performing the join (using an index nested loops join) than a block nested loops join? Explain.

If primary B+ indexes existed on R.a and S.b, would either provide a cheaper alternative for performing the join (using the index nested loops algorithm) than a block nested loops join? Explain.