A query performs a hash-join on relations R (2 M pages) and S (3 M pages) with a 40 % selective predicate on S. Memory is 102 pages. Using the hybrid grace-hash algorithm, what is the minimum number of passes required to complete the join and how many partitions are created in the first pass?
Correct: N/A
One page is reserved for input buffer, leaving 101 for partitions. Smaller relation R needs ⌈2 M / 101⌉ = 19802 partitions, but we can stop recursive partitioning when partition size ≤ memory. After first pass we get 30 partitions (102-1). Largest partition of R is 2 M / 30 ≈ 66 k pages ≤ 102, so only 2 passes total are required.