Sorting data larger than memory
external sorting.
external merge sort reads memory-sized chunks, sorts each in RAM and writes them as sorted runs to disk, then merges many runs together in passes until one sorted output remains.
What's really being asked
The interviewer checks that you understand sorting cannot assume the data fits in memory and know the classic external algorithm.
The full answer
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.
The mistakes people make
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.
What usually comes next
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.
A 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.
Interview question
Why must a database use external merge sort rather than a normal in-memory sort for a 100GB ORDER BY with 1GB of RAM?
- a.ORDER BY is not allowed on large tables without an index
- b.The optimizer always sorts on disk regardless of size
- c.The data far exceeds RAM, so it is sorted as memory-sized runs on disk and then mergedCorrect
- d.In-memory sorts cannot handle more than a million rows
Why? this is the answer
Because the dataset dwarfs available memory, the engine sorts memory-sized chunks into runs on disk and merges them in passes. In-memory sorts have no fixed row cap, and the engine uses memory when data does fit.
Just read this? Test yourself on what you have been reading.
Read the original → cs186berkeley.net
- #databases
- #external-sort
- #order-by
- #merge-sort
- #query-execution
Put your scrolling time to good use
Learn one idea, try a quiz and save useful cards for revision. Tezvyn makes it easy to learn and stay current in your tech field, a few minutes at a time.
The iPhone app is on the way
We are building it. Until it lands, nothing here is held back from you: every interview card, your saved cards, streaks and the job board all work in Safari, plus hundreds of free practice quizzes of thirty questions each. Sign in and it all carries over to the app the day it arrives.
Want it as an icon? Tap Share at the bottom of Safari, then Add to Home Screen. It opens full screen and the cards you have read stay available offline.
We are hiring for this. Open roles that interview on databases — each one lists the topics its interview covers.
See open roles