Продвинутые методы ускорения сортировки в ClickHouse
Компания | Яндекс |
Учебный семестр | Осень 2018 |
Учебный курс | 3-4-й курс |
Максимальное количество студентов, выбравших проект: ? | |
Хорошим алгоритмом для сортировки массива чисел является radix sort. В ClickHouse есть реализация этого алгоритма. Алгоритм работает как для беззнаковых, так и для знаковых чисел, а также для чисел с плавающей запятой.
Но для сортировки данных в ClickHouse нужно учесть несколько особенностей: - нужна не непосредственная сортировка, а получение перестановки индексов; - часто данные нужно сортировать не по одному числу, а по кортежу; - причём, компонетны кортежа расположены в отдельных массивах (т. н. structure of arrays); - структура кортежа известна только в рантайме; - часто нужна не полная, а частичная сортировка (получение в нужном порядке первых N элементов); - есть сценарии, в которых требуется и в которых не требуется stable sort.
В таком виде оптимальный вариант на тему radix sort ещё никто не исследовал.