External sorting

Memory holds a thousand lines, and the file has nineteen thousand: the catalogue of all earthquakes of magnitude 5 and above over eleven years. It has to be ordered by magnitude. This is always the case when there is more data than memory: a log for a year, a database dump, an index over a hundred-gigabyte table. Merge sort knows the scheme: cut the file into memory-sized chunks, sort each and write it to disk, which gives sorted runs, and then merge the runs. But the first step can be done twice as well as “memory-sized chunks”. Below, the runs are cut by a snowplow.

The ring is all the values of the key in order, from smallest to largest. The snow is the lines lying in memory, the plough is the last line written. The plough goes round and takes the nearest snow ahead: the next line of the run. In its place a new line comes from the file and falls anywhere. If it falls ahead of the plough, it makes it into this same run; if behind, it waits for the next lap. On random keys each lap gives a run of almost exactly 2M lines, although memory never holds more than M.

The idea

External sorting works in two phases and always reads and writes files in order, never at random. The first phase makes sorted runs, each no longer than what can be ordered in memory, or, with replacement selection, twice as long. The second merges k runs at a time, keeping the first line of each in a heap. The price is the number of passes over all the data: one for the runs and ⌈log_k R⌉ to merge R runs.

Runs longer than memory

The usual way, read M lines, sort, write, gives runs of exactly M. Replacement selection does the same one line at a time. Memory holds a heap of M lines. The smallest line that is not less than the last one written leaves it for the run, and the next line of the file is read in its place at once. If the new line is smaller than the one just written, it can no longer join the current run, which would then go backwards, and it is marked for the next one. When the heap has no lines of the current run left, a new run begins: all the marked lines now belong to it.

Switch the file in the scene to “ascending” and you get one run for the whole file; switch it to “descending” and you get runs of exactly M. Replacement selection adapts to whatever order the data already has: a nearly sorted log leaves the first phase almost in one piece.

Why 2M

This is an estimate, not a proof; it is given by Donald Knuth. Imagine that the snow, that is, the new lines, falls evenly on a ring road, and the plough drives round at a constant speed. After a few laps the picture settles: as much snow falls in a lap as the plough clears in a lap, otherwise there would be more and more snow or less and less. Right behind the plough there is no snow, since it has just passed. The further back from the plough, the longer that spot has gone uncleared and the more snow lies there. The depth grows linearly, and it is deepest right in front of the plough, where snow has been piling up for a whole lap.

All the snow on the road is memory, M lines, and it lies in a triangle: from zero behind the plough to a whole lap’s snowfall in front of it. A lap’s snowfall is a rectangle of the same height over the whole length of the road, and the triangle is exactly half of it. So in a lap 2M lines fall and the plough clears 2M lines, and that is a run. The rigorous derivation is in the third volume of Knuth’s “The Art of Computer Programming”: on random data the mean length of a run tends to 2M.

On real data this is just what happens. Earthquake magnitudes in time order with M = 1000 give 9 runs of 2119 lines on average, while chunks of a thousand give 20. City populations in the order of the GeoNames file give runs of about 1.9M. The scene also shows the triangle itself: the blue snow ahead of the plough is deeper, the orange snow behind is only beginning to pile up.

Merging: how many passes

Runs are merged just as in merge sort, only not two at a time but k at once: the heap holds the first line of each of the k files, the smallest goes to the output, and the next line of the same file is read in its place. One such pass reads and writes each line once.

The larger k, the fewer the passes, but each of the k files needs its own read buffer: memory is split into k + 1 parts, counting the write buffer. On old disks too small a buffer meant an extra movement of the head for every read, and k was chosen with care. GNU sort merges 16 files at a time by default. And here long runs pay off a second time: 20 runs merged 16 at a time need two passes, while the 9 runs of replacement selection need one.

Code

The listing really sorts the earthquake catalogue by magnitude as if memory held a thousand lines: the runs are written to temporary files, and the merge reads them line by line. It makes the runs both ways, merges them 2 at a time, 16 at a time and all at once, counts the passes and the lines the merge read and wrote, and checks the result against an ordinary sort.

19073 earthquakes, memory for 1000 lines, sorted by magnitude
runs                       files  fan-in  passes  lines moved
memory-sized chunks           20       2       5       190730
memory-sized chunks           20      16       2        76292
memory-sized chunks           20      20       1        38146
                          runs of 73..1000 lines, mean 954
replacement selection          9       2       4       152584
replacement selection          9      16       1        38146
replacement selection          9       9       1        38146
                          runs of 966..2404 lines, mean 2119

In both cases the first phase reads and writes all 19,073 lines once, and the merge adds the “lines moved” column to that. Merging in pairs takes 5 passes against 4: there are half as many runs, and log₂ goes down by one. Merging 16 at a time, the difference is two passes against one, that is, half the disk work. The shortest run of replacement selection, 966 lines, is the last one: the claim above allows it to be shorter than M.

What it costs

For external data the main measure is not comparisons but exchanges with the disk: in the time of one disk read the processor manages millions of comparisons (latency numbers). In 1988 Alok Aggarwal and Jeffrey Vitter introduced the external memory model for this: memory holds M lines, the disk reads in blocks of B, and only block reads and writes are counted. They proved that sorting needs on the order of (n/B) log_M/B (n/B) block transfers, and a multiway merge with k about M/B reaches this bound. With gigabytes of memory and large blocks this logarithm is usually no more than two: one or two merge passes are enough.

How it is done in practice

• GNU sort. It sorts buffer-sized chunks in memory (--buffer-size), writes them to temporary files and merges them 16 at a time (--batch-size); if there are more files, it merges them in groups into new temporary files until a single group is left.
• PostgreSQL. When a sort runs out of work_mem, EXPLAIN ANALYZE shows “Sort Method: external merge”. Before version 9.6 the runs were made by replacement selection. In 9.6 they began to be made by quicksort: it makes better use of the processor cache, while a heap jumps around memory. Version 11 removed the last setting under which replacement selection was still switched on: such sorts, in the words of the release notes, were no longer useful.
• Why it turned out this way. Memory has become plentiful, runs are few, and the merge almost always fits into one pass, which runs twice as long can no longer shorten. And in memory the winner is whoever reads in order: sorting a chunk in memory is work for the cache, a heap of millions of lines is not. Replacement selection still wins on nearly sorted data: there the run comes out as one.
• LSM trees. Databases that write to disk in sorted files later merge them in the background: this is the same multiway merge, only continuous (LSM tree).

History

External sorting is older than disks: in the 1950s files were kept on magnetic tape, and tape can only be read in order. Merge sort suited it perfectly, and many ways of distributing runs over tapes were invented: polyphase merge, cascade merge, oscillating merge. In the third volume of Donald Knuth’s “The Art of Computer Programming”, published in 1973, a whole section is given to external sorting, and the analysis of replacement selection and the snowplow is there too. Tapes went away, but the model, data read in order and in large pieces, stayed: in 1988 Aggarwal and Vitter described it for disks, and the same model describes the processor cache, where nearby data is cheaper than distant data.

Problems

In the problem one has to count the runs of replacement selection on real data, earthquake magnitudes and city populations, and find the longest. The catch is in equal keys.