Part 2 of 5 · 1 min read
Sorting in memory versus external sort
Data that fits in memory sorts directly; data that does not must be sorted in chunks and merged.
Think of sorting a small stack of index cards right on a desk, compared to sorting a warehouse full of boxes that cannot all fit on any one desk at once.
In plain words: when the data to be sorted fits entirely in memory, typically inside the buffer pool covered in Level 4, sorting happens directly in memory, using a standard in-memory sorting algorithm, and is relatively cheap. When the data does not fit in memory, the database uses an external sort: it sorts chunks of the data in memory one at a time, writes each sorted chunk to disk, and then merges the sorted chunks together into one final sorted result. External sort is noticeably more expensive, since it involves real disk reads and writes, not just in-memory comparisons.
A worked example. Sorting a thousand rows that fit comfortably in memory is cheap and direct; sorting a hundred million rows that exceed available memory requires an external sort, with chunks written to and merged from disk.
The key lines.
SELECT * FROM orders ORDER BY placed_on;
-- sorted in memory if the result fits; external sort otherwise
External sort
An external sort sorts data too large to fit in memory by sorting smaller chunks individually, writing each sorted chunk to disk, and merging the sorted chunks together into one final result.
Example: sorting a warehouse full of boxes in smaller batches and then combining the sorted batches, since they cannot all fit on one desk at once, mirrors an external sort.