Nested-loop joins test the join predicate on each pair of tuples, so they work for any condition. Hash join relies on equal keys hashing to the same partition, so it supports only equality (equi-) joins. The standard sort-merge join is also designed for equality conditions.
Question 2 Multiple Choice
Relation r occupies 100 blocks and relation s occupies 1,000 blocks. Using block nested-loop join with r as the outer relation and, in the worst case, only one buffer block for each relation, how many block transfers are needed?
A1,100
B100,100
C101,000
D1,000,000
For each block of the outer relation r, the whole inner relation s is scanned: 100 x 1,000 = 100,000 transfers, plus 100 to read r once, for 100,100. With s as the outer relation it would be 1,000 x 100 + 1,000 = 101,000, which is why the smaller relation is usually chosen as outer.
Question 3 True / False
Hash join can be used only when the smaller of the two relations fits entirely in main memory.
TTrue
FFalse
Answer: False
When the build relation is too large, hash join first partitions both relations on disk using the same hash function on the join attribute. Matching tuples fall into matching partitions, and only one partition of the build relation must fit in memory at a time. If partitions are still too big, they can be partitioned again recursively.
Question 4 Short Answer
Name one situation in which sort-merge join is an especially good choice compared with hash join.
Think about your answer, then reveal below.
Model answer: When one or both inputs are already sorted on the join attribute, for example because they are read through a clustered B+-tree index or come from an earlier sort, so the sorting step is free or cheap; or when the query's output must be sorted on the join attribute anyway, such as with an ORDER BY on that column.
Sort-merge join's main cost is sorting. If sorting is already done or is needed for later steps, the merge pass costs only one read of each input, and the sorted output can be reused.