Краткий ответ

Инкрементальная сортировка использует частичный порядок входных данных: если строки уже сгруппированы по префиксу требуемого порядка, оптимизатор сортирует каждую такую группу отдельно, а не весь набор целиком. Это обычно уменьшает потребление памяти и объём работы, особенно когда группы небольшие.

Исторический контекст

Обычная сортировка требует собрать весь входной набор и упорядочить его перед передачей результата дальше. Для больших выборок это приводит к значительному потреблению памяти, а при её нехватке — к записи промежуточных данных во временное хранилище.

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

Постановка проблемы

Предположим, запрос требует порядок по customer_id, created_at, а индекс обеспечивает только порядок по customer_id. Полная сортировка всех строк может оказаться дорогой, хотя строки одного клиента уже идут подряд.

Неверная оценка числа строк или размера групп влияет на выбор плана. Оптимизатор может выбрать инкрементальную сортировку, рассчитывая на небольшие группы, но при фактическом распределении данных отдельные группы окажутся большими и начнут использовать временное хранилище.

Подробное решение

Инкрементальная сортировка работает в несколько этапов:

Оператор получает поток, упорядоченный по известной части ключа, например по customer_id.
Он выделяет последовательные группы с одинаковым значением этого ключа.
Внутри каждой группы сортирует строки по недостающей части, например по created_at.
Передаёт группы дальше в требуемом общем порядке.

Минимальный пример идеи:

CREATE INDEX ix_orders_customer
    ON orders (customer_id);

SELECT order_id, customer_id, created_at
FROM orders
WHERE status = 'paid'
ORDER BY customer_id, created_at;

Такой индекс не задаёт порядок по created_at, но может предоставить строки, сгруппированные по customer_id. В поддерживающей эту возможность СУБД план может использовать инкрементальную сортировку: каждая группа клиента сортируется отдельно. Само наличие индекса не гарантирует такой план — оптимизатор сравнивает его стоимость с полным сканированием и полной сортировкой.

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

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

Инкрементальная сортировка отличается от полного устранения сортировки. Если индекс полностью соответствует требуемому порядку, дополнительный оператор сортировки не нужен. Если соответствует только префиксу, сортировка всё ещё выполняется, но меньшими независимыми порциями.

Ситуация из практики

В отчётной системе запрос выбирал оплаченные заказы и сортировал их по клиенту и времени создания. Индекс по клиенту обеспечивал группировку заказов, однако фильтр по статусу удалял часть строк. Наивным вариантом был полный скан таблицы с полной сортировкой: он имел предсказуемый план, но при больших объёмах создавал значительные временные файлы.

Второй вариант — индекс по клиенту и времени создания. Он мог полностью устранить сортировку, но делал индекс шире и не решал проблему эффективного отбора по статусу. Стоимость дополнительных записей и обслуживания индекса была существенной для часто изменяемой таблицы.

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

Что кандидаты часто упускают

1. Может ли инкрементальная сортировка полностью устранить чтение данных?

Нет. Она влияет на порядок обработки уже полученных строк, но не заменяет фильтрацию и не делает индекс автоматически селективным. Если индекс не позволяет быстро найти нужные строки, основная стоимость может оставаться на этапе чтения и проверки предиката.

2. Почему свежая статистика всё равно важна для выбора этого плана?

Оптимизатору нужно оценить количество групп и размер каждой группы. От этого зависят ожидаемая память, стоимость сортировки и вероятность обращения к временному хранилищу. Статистика может быть актуальной по общему числу строк, но недостаточно точно отражать неравномерное распределение: несколько крупных групп способны сделать инкрементальную сортировку невыгодной.

3. Всегда ли более узкий индекс предпочтительнее индекса, полностью соответствующего сортировке?

Нет. Узкий индекс дешевле поддерживать и обычно занимает меньше места, но может оставить дополнительную сортировку. Широкий индекс способен полностью задать порядок и сократить вычисления при чтении, однако увеличивает стоимость вставок, изменений, обслуживания и объём дискового ввода-вывода. Выбор зависит от частоты запроса, размера таблицы, изменяемости данных и фактической стоимости обоих планов.