Просмотр кода страницы Продвинутые методы ускорения сортировки в ClickHouse

{{Карточка_командного_проекта
|name=Сервис по работе с геоданными
|company=Яндекс
|semester=Осень 2018
|course=3-4
|number_of_students=?
|categorize=yes
}}


Хорошим алгоритмом для сортировки массива чисел является radix sort. В ClickHouse есть реализация этого алгоритма. Алгоритм работает как для беззнаковых, так и для знаковых чисел, а также для чисел с плавающей запятой.

Но для сортировки данных в ClickHouse нужно учесть несколько особенностей:
- нужна не непосредственная сортировка, а получение перестановки индексов;
- часто данные нужно сортировать не по одному числу, а по кортежу;
- причём, компонетны кортежа расположены в отдельных массивах (т. н. structure of arrays);
- структура кортежа известна только в рантайме;
- часто нужна не полная, а частичная сортировка (получение в нужном порядке первых N элементов);
- есть сценарии, в которых требуется и в которых не требуется stable sort.

В таком виде оптимальный вариант на тему radix sort ещё никто не исследовал.