This problem will explore different join implementations and the associated IO costs for different models. Let R$($a$,$ b$),$ S$($b$,$ c$),$ and T$($c$,$ d$)$ be tables. For the purpose of this question, use the values provided below.

$$ P$($R$)=$ number of pages of R $=20$

$$ T$($R$)=$ number of tuples of R $=1600$

$$ P$($S$)=$ number of pages of S $=200$

$$ T$($S$)=$ number of tuples of S $=15000$

$$ P$($T$)=$ number of pages of T $=2000$

$$ P$($R$,$ S$)=$ number of pages in output RS $=100$

$$ P$($S$,$ T$)=$ number of pages in output ST $=1000$

$$ P$($R$,$ S$,$ T$)=$ number of pages in output RST $=500$

$$ B $=$ number of buffer pages $=32$

a$)[3$ point$]$

Let us start by considering a simple nested loop join. Compute the IO cost for a simple nested loop join if R is the $$outer loop$$ and S is the $$inner loop.$$

b$)[3$ point$]$

Compute the IO cost for a simple nested loop join if S is the $$outer loop$$ and R is the $$inner loop.$$

c$)[8$ points$]$

Now consider using a block nested loop join. Compute the IO cost for joining R$,$ S and then joining the result with T$.$ Then compute the IO cost for joining S$,$ T and then joining the result with R$.$

d$)[3$ points$]$

Now consider using a sort$-$merge join. Compute the IO cost for joining R$,$ S and then joining the result with T$.$ Assume that the tables are not sorted before starting. Also assume that we do not need to do any back up as described in lecture.

e$)[4$ points$]$

Again, using a sort$-$merge join, compute the IO cost for joining S$,$ T and then joining

the result with R$.$ Assume that the tables are not sorted before starting. Also assume

that we do not need to do any back up as described in lecture.

f$)[3$ points$]$

Now suppose we only want to join R and S $($with sort$-$merge join$)$ but this time all values for the join attribute are the same. What would be the IO cost now?

g$)[3$ points$]$

Now consider using a hash join. Compute the IO cost for joining R$,$ S and then joining the result with T$.$

h$)[3$ points$]$

Again, using a hash join, compute the IO cost for joining S$,$ T and then joining the result with R$.$