Propose an algorithm for finding an intersection of two large relations (i.e., ones that do not fit in main memory) using hashing.

What will be an ideal response?

Solution:
Hash each relation on all attributes using the same hash function. Keep the distinction between the two parts of the bucket, which came from different relations. Tuples that fall into the intersection must fall into the same bucket. If the bucket is small enough, do the intersection in main memory. Else hash the tuples in the bucket again using a different hash function. It is reasonable to expect that the second-level buckets will fit into the main memory and then intersection within each bucket can be done in main memory.