7. Hashing

Question 1

Why do we need hashing in addition to sorting in databases?

Answer 1

Sometimes, sorting is a bit overkill for the problem. In a lot of cases, all we want is to group the same value together, but we do not actually care about the order the values appear in (think GROUP BY or de-duplication).

Question 2

Why do we need special hashing algorithms for databases?

Answer 2

same as for sorting: we cannot fit all of our data in memory

Question 3

External hashing algorithm - describe

Answer 3

In-memory buffer has B pages

1. “divide” - use some hash function to put all records into B-1 partitions. We do this by using B-1 output buffers. When an output buffer fills up we flush the page to disk.
2. If some partitions do not fit in memory (have >B-1 pages), partition them once more with another hash function. Repeat until all pages fit in memory.
3. “conquer” - build a hash table for each partition with a common in-memory algorithm, concatenate all the tables together.