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

Компания	Яндекс
Учебный семестр	Осень 2018
Учебный курс	3-4-й курс
Максимальное количество студентов, выбравших проект: ?

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

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

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