15.5

Let \(r\) and \(s\) be relations with no indices, and assume that the relations are not sorted. Assuming infinite memory, what is the lowest-cost way (in terms of I/O operations) to compute \(r \bowtie s\)? What is the amount of memory required for this algorithm.

---

We can store the entire smaller relation in memory, read the larger relation block by block, and perform nested-loop join using the larger one as the outer relation. The number of I/O operations is equal to \(b_r + b_s\), and the memory requirement is \(\min(b_r, b_s) + 2\) pages.