Внешняя сортировка

В памяти помещается тысяча строк, а в файле их девятнадцать тысяч — каталог всех землетрясений магнитудой от 5 за одиннадцать лет. Его нужно упорядочить по магнитуде. Так бывает всегда, когда данных больше, чем памяти: журнал за год, выгрузка из базы, индекс по таблице в сто гигабайт. Схему знает сортировка слиянием: нарезать файл на куски размером с память, каждый отсортировать и записать на диск — получатся отсортированные прогоны, — а потом прогоны слить. Но первый шаг можно сделать вдвое лучше, чем «кусками размером с память». Ниже прогоны режет снегоочиститель.

Кольцо — все значения ключа по порядку, от наименьшего к наибольшему. Снег — строки, которые лежат в памяти, плуг — последняя записанная строка. Плуг идёт по кругу и забирает ближайший снег впереди: следующую строку прогона. На её место из файла приходит новая и падает где попало. Если она упала впереди плуга, она успеет в этот же прогон; если позади — ждёт следующего круга. На случайных ключах каждый круг даёт прогон почти ровно в 2M строк, хотя в памяти никогда не больше M.

Идея

Внешняя сортировка работает в две фазы и всегда читает и пишет файлы подряд, а не вразнобой. Первая фаза делает отсортированные прогоны, каждый не длиннее того, что можно упорядочить в памяти, — или, при замещающем выборе, вдвое длиннее. Вторая сливает по k прогонов за раз, держа в куче по первой строке от каждого. Цена — число проходов по всем данным: один на прогоны и ⌈log_k R⌉ на слияние R прогонов.

Прогоны длиннее памяти

Обычный способ — прочитать M строк, отсортировать, записать — даёт прогоны ровно по M. Замещающий выбор делает то же самое по одной строке. В памяти куча из M строк. Из неё уходит в прогон наименьшая строка, которая не меньше последней записанной, а на её место сразу читается следующая строка файла. Если новая строка меньше только что записанной, в текущий прогон ей уже нельзя — прогон шёл бы назад, — и она помечается для следующего. Когда в куче не остаётся строк текущего прогона, начинается новый: все помеченные теперь его.

Переключите в сцене файл на «по возрастанию» — получится один прогон на весь файл, а на «по убыванию» — ровно по M. Замещающий выбор подстраивается под порядок, который в данных уже есть: почти отсортированный журнал выходит из первой фазы почти одним куском.

Почему 2M

Это прикидка, а не доказательство; её приводит Дональд Кнут. Представим, что снег, то есть новые строки, падает на кольцевую дорогу равномерно, а плуг ездит по кругу с постоянной скоростью. Через несколько кругов картина установится: за круг выпадает столько снега, сколько плуг за круг убирает, иначе снега становилось бы всё больше или всё меньше. Сразу позади плуга снега нет — он только что прошёл. Чем дальше от плуга назад, тем дольше это место не чистили, и снега там больше. Глубина растёт линейно, и самая глубокая — прямо перед плугом, где снег копился целый круг.

Весь снег на дороге — это память, M строк, и он лежит треугольником: от нуля позади плуга до снегопада за целый круг перед ним. Снегопад за круг — прямоугольник той же высоты на всю длину дороги, и треугольник — ровно его половина. Значит, за круг выпадает, а плуг убирает 2M строк — это и есть прогон. Строгий вывод в третьем томе «Искусства программирования» Кнута: на случайных данных средняя длина прогона стремится к 2M.

На настоящих данных так и выходит. Магнитуды землетрясений в порядке времени при M = 1000 дают 9 прогонов в среднем по 2119 строк, а кусками по тысяче — 20. Население городов в порядке файла GeoNames — прогоны около 1,9M. В сцене виден и сам треугольник: синий снег перед плугом глубже, оранжевый позади только начинает копиться.

Слияние: сколько проходов

Прогоны сливают так же, как в сортировке слиянием, только не по два, а по k сразу: в куче лежит первая строка каждого из k файлов, наименьшая уходит в результат, а на её место читается следующая строка из того же файла. Один такой проход читает и пишет каждую строку один раз.

Чем больше k, тем меньше проходов, но у каждого из k файлов должен быть свой буфер чтения: память делится на k + 1 частей, считая буфер записи. На старых дисках слишком маленький буфер означал лишнее движение головки на каждое чтение, и k выбирали осторожно. GNU sort по умолчанию сливает по 16 файлов. И здесь длинные прогоны окупаются второй раз: 20 прогонов при слиянии по 16 требуют двух проходов, а 9 прогонов замещающего выбора — одного.

Код

Листинг по-настоящему сортирует каталог землетрясений по магнитуде так, будто в памяти помещается тысяча строк: прогоны пишутся во временные файлы, слияние читает их строку за строкой. Он делает прогоны обоими способами, сливает их по 2, по 16 и все сразу, считает проходы и строки, которые слияние прочитало и записало, и сверяет результат с обычной сортировкой.

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

Первая фаза в обоих случаях читает и пишет все 19 073 строки один раз, слияние добавляет к этому столбец «lines moved». Слияние попарно делает 5 проходов против 4: прогонов вдвое меньше, и log₂ уменьшается на единицу. При слиянии по 16 разница — два прохода против одного, то есть вдвое меньше работы с диском. Самый короткий прогон замещающего выбора, 966 строк, — последний: утверждение выше разрешает ему быть короче M.

Сколько это стоит

Для внешних данных главная мера — не сравнения, а обмены с диском: за время одного чтения с диска процессор успевает сделать миллионы сравнений (порядки задержек). Алок Аггарвал и Джеффри Виттер в 1988 году ввели для этого модель внешней памяти: в памяти M строк, диск читает блоками по B, и считаются только чтения и записи блоков. Они доказали, что сортировке нужно порядка (n/B) log_M/B (n/B) обменов блоками, и многопутевое слияние с k около M/B эту границу достигает. При памяти в гигабайты и больших блоках этот логарифм обычно не больше двух: хватает одного-двух проходов слияния.

Как это делают на практике

• GNU sort. Сортирует в памяти куски размером с буфер (--buffer-size), пишет их во временные файлы и сливает по 16 за раз (--batch-size); если файлов больше, сливает группами в новые временные файлы, пока не останется одна группа.
• PostgreSQL. Когда сортировке не хватает work_mem, EXPLAIN ANALYZE показывает «Sort Method: external merge». До версии 9.6 прогоны делались замещающим выбором. В 9.6 их стали делать быстрой сортировкой: она лучше использует кеш процессора, а куча прыгает по памяти. В версии 11 убрали и последний параметр, при котором замещающий выбор ещё включался: такие сортировки, по словам примечаний к выпуску, перестали быть полезны.
• Почему так вышло. Памяти стало много, прогонов мало, и слияние почти всегда укладывается в один проход — вдвое более длинные прогоны его уже не сокращают. А в памяти выигрывает тот, кто читает подряд: сортировка куска в памяти — работа для кеша, куча из миллионов строк — нет. Замещающий выбор по-прежнему выигрывает на почти отсортированных данных: там прогон выходит один.
• LSM-деревья. Базы, которые пишут на диск отсортированными файлами, потом сливают их в фоне — это то же многопутевое слияние, только непрерывное (LSM-дерево).

История

Внешняя сортировка старше дисков: в 1950-х файлы хранились на магнитных лентах, а лента читается только подряд. Сортировка слиянием подходила к ней идеально, и способов раскладывать прогоны по лентам придумали множество — многофазное слияние, каскадное, осциллирующее. В третьем томе «Искусства программирования» Дональда Кнута, вышедшем в 1973 году, внешней сортировке отдан целый раздел, и там же — анализ замещающего выбора и снегоочиститель. Ленты ушли, а модель — данные читаются подряд и большими кусками — осталась: в 1988 году Аггарвал и Виттер описали её для дисков, и та же модель описывает кеш процессора, где близкие данные дешевле далёких.

Задачи

В задаче нужно сосчитать прогоны замещающего выбора на настоящих данных — магнитудах землетрясений и населении городов — и найти самый длинный. Подвох — в одинаковых ключах.