Sorting data larger than memory

WHAT THIS TESTS The interviewer checks that you understand sorting cannot assume the data fits in memory and know the classic external algorithm.

A GOOD ANSWER COVERS The database uses external merge sort, designed for data larger than available memory. It has two phases. First, run generation: the engine reads the 100GB in chunks sized to fit the roughly 1GB of working memory, sorts each chunk in memory with an efficient in-memory sort, and writes each sorted chunk back to disk as a sorted run. With 1GB of memory this yields on the order of a hundred sorted runs. Second, merging: the engine performs a multi-way merge, opening many runs at once, holding a small input buffer for each plus an output buffer, repeatedly taking the smallest current key across the runs and writing it to the output, refilling buffers from disk as they drain. If the number of runs exceeds the number of buffers memory allows, it merges in multiple passes, each pass combining groups of runs into fewer, larger runs, until a single fully sorted run remains. Cost is dominated by reading and writing the data a few times, scaling with the number of merge passes, which the large fan-in keeps small. Memory limits the run size and the merge fan-in.

COMMON WRONG ANSWERS Claiming it just loads everything into RAM, impossible at 100GB with 1GB. Assuming a single pass regardless of size. Confusing this with quicksort alone. Forgetting that runs are written to and reread from disk, dominating cost.

LIKELY FOLLOW-UPS What determines the number of merge passes; how does memory affect fan-in; how is this related to external hashing; can an index avoid the sort entirely.

ONE CONCRETE EXAMPLE With 100GB and 1GB of memory, phase one produces about a hundred 1GB sorted runs. Phase two opens many of those runs at once and merges them by always emitting the smallest pending key, refilling each run's buffer from disk as needed, until all hundred runs are combined into one sorted 100GB output, having read and written the data only a couple of times.