External sort: k-way merge sort, переписанный в 1.4

ORDER BY кажется простой операцией, но сортировка — одна из самых требовательных к памяти задач СУБД. Чтобы отсортировать данные, в общем случае нужно видеть их все сразу: последний элемент потока может оказаться первым в результате. External sort — механизм, позволяющий ORDER BY отработать, когда данные не помещаются в RAM. В DuckDB 1.4 движок сортировки был полностью переписан как k-way merge sort, и этот урок разбирает, как он устроен.

Это третий и последний из «больших» out-of-core механизмов модуля. Логика спилла та же, что у агрегации и join, но алгоритмически сортировка устроена иначе: вместо партиционирования по хешу — слияние отсортированных кусков.

Почему сортировка требовательна к памяти

Агрегацию и join спасало партиционирование по хешу: строки разбивались на независимые группы, каждая обрабатывалась отдельно. С сортировкой так не получается — у сортировки нет «групп», которые можно обработать изолированно. Любой элемент может встать на любую позицию в финальном порядке, и определить его место нельзя, не сравнив с другими.

Наивная сортировка требует все данные в RAM: загрузить весь датасет, применить алгоритм сортировки, выдать результат. Для данных больше памяти это невозможно напрямую. Нужен алгоритм, который сортирует по частям и затем эти части объединяет, — и это external merge sort.

Идея external merge sort: run-ы и слияние

External merge sort работает в две фазы.

Фаза 1 — формирование run-ов (sorted runs). Данные читаются кусками такого размера, чтобы кусок поместился в memory_limit. Каждый кусок сортируется в памяти обычным быстрым in-memory алгоритмом и записывается на диск как отсортированный run. Run — это фрагмент данных, внутри себя полностью упорядоченный. После этой фазы на диске лежит несколько отсортированных run-ов; весь датасет не упорядочен, но каждый run — да.

Фаза 2 — слияние (merge). Отсортированные run-ы сливаются в один полностью отсортированный результат. Слияние не требует держать run-ы в памяти целиком: достаточно читать их потоково.

K-way merge: слияние сразу многих run-ов

Сердце алгоритма — фаза слияния. Как слить несколько отсортированных run-ов в один отсортированный поток?

Базовая идея слияния двух отсортированных списков знакома: смотрим на первые элементы обоих, берём меньший, продвигаемся в том списке, повторяем. K-way merge обобщает это на k run-ов сразу: смотрим на «головные» (наименьшие ещё не выданные) элементы всех k run-ов, выбираем глобально наименьший, выдаём его, продвигаемся в его run-е, повторяем.

Чтобы быстро находить наименьший из k голов, используется структура min-heap (куча минимумов) размера k: в ней лежат текущие головы всех run-ов, и извлечь минимум из неё дёшево. Каждый шаг: извлечь минимум из кучи (это очередной элемент результата), взять следующий элемент из того run-а, откуда был минимум, положить его в кучу. Так результат собирается по одному элементу, строго в порядке.

Почему k-way, а не сливать парами? Можно было бы сливать run-ы попарно: 0+1, 2+3, потом результаты, и так далее. Но это многопроходный merge — данные перечитываются с диска несколько раз. K-way merge сливает много run-ов за один проход, минимизируя число чтений с диска. Меньше проходов по диску — быстрее сортировка, ведь диск медленный.

Что нового в переписанном движке 1.4

В DuckDB 1.4 движок сортировки был полностью переписан. Новая реализация — это как раз чистый k-way merge sort, и она принесла несколько улучшений.

Адаптивность к уже упорядоченным данным. Если входные данные уже отсортированы или почти отсортированы, движок это распознаёт и не делает лишней работы. Сортировка по колонке, по которой данные уже упорядочены физически (например, таблица создавалась последовательно по этой колонке), обходится почти даром. Это важная оптимизация: на практике данные часто частично упорядочены.

Лучшая параллельность. Переписанный движок эффективнее задействует несколько потоков и на фазе формирования run-ов, и на фазе слияния.

Предсказуемое поведение под нехватку памяти. Сортировка плавно переходит в external-режим, когда run не помещается в память, без резких скачков.

Практический вывод для пользователя простой: ORDER BY в DuckDB 1.4 и новее быстрее и устойчивее, особенно на больших и на частично упорядоченных данных. Специально настраивать ничего не нужно — переписанный движок работает по умолчанию.

Видим внешнюю сортировку в работе

Воспроизведём ORDER BY на датасете, не влезающем в маленький лимит.

-- 60 млн строк со случайным ключом сортировки
CREATE TABLE big AS
SELECT range AS id,
       random() AS sort_key,
       ('payload_' || range) AS payload
FROM range(60000000);

SET memory_limit = '400MB';
SET temp_directory = '/tmp/sort-spill';

-- сортировка 60 млн строк по случайному ключу при лимите 400 МБ
SELECT id, sort_key
FROM big
ORDER BY sort_key
LIMIT 10;
-- запрос ОТРАБОТАЕТ: данные не влезли в 400 МБ,
-- отсортированы по run-ам и слиты k-way merge

SET memory_limit = '400MB';
EXPLAIN ANALYZE
SELECT id FROM big ORDER BY sort_key;

В выводе оператор ORDER_BY будет помечен как работающий в external-режиме. Во время выполнения в /tmp/sort-spill появятся файлы отсортированных run-ов, исчезающие по завершении.

Теперь — демонстрация адаптивности. Сравним сортировку по случайному ключу и по уже упорядоченной колонке:

-- по случайному ключу: полноценная сортировка
SELECT id FROM big ORDER BY sort_key LIMIT 10;

-- по id: данные УЖЕ упорядочены по id (таблица создана range)
SELECT id FROM big ORDER BY id LIMIT 10;
-- второй запрос заметно быстрее: движок 1.4 распознаёт
-- уже упорядоченные данные и не делает лишней работы

Сортировка в ряду out-of-core механизмов

Подведём общую черту под тремя механизмами модуля. Все три позволяют операции отработать при нехватке памяти, спиллив на диск, но устроены по-разному.

Агрегация и join опираются на хеш-партиционирование: задача распадается на независимые куски. Сортировка опирается на merge: куски не независимы, их нужно слить с учётом порядка. Но принцип один — свести задачу, не влезающую в память, к серии операций, каждая из которых в память помещается.

Попробуй сам

1. Создай большую таблицу: CREATE TABLE t AS SELECT range AS id, random() AS rk, ('s' || range) AS s FROM range(50000000);
2. Задай SET temp_directory = '/tmp/sort-demo'; и SET memory_limit = '350MB'; Выполни SELECT id, rk FROM t ORDER BY rk LIMIT 10; — запрос должен отработать.
3. Во время выполнения посмотри /tmp/sort-demo из другого терминала — есть ли файлы отсортированных run-ов? Что с ними после завершения?
4. Сделай EXPLAIN ANALYZE для SELECT id FROM t ORDER BY rk; при 350MB и при большом лимите. Сравни метку режима у оператора ORDER_BY.
5. Сравни время двух запросов при 350MB: ... ORDER BY rk (случайный ключ) и ... ORDER BY id (колонка, по которой данные уже упорядочены, ведь таблица создана через range). Какой быстрее и почему? Свяжи ответ с адаптивностью переписанного в 1.4 движка.