Команда Pivot описала оптимизацию аналитических запросов, которые группируют строки, сортируют группы по агрегату и оставляют только первые K результатов. Типичный пример — найти десять товаров с наибольшим числом заказов через GROUP BY, ORDER BY COUNT(*) DESC и LIMIT 10.
При высокой кардинальности ключей аналитические базы обычно распределяют входные данные между потоками CPU. Каждый поток разбивает свой фрагмент на партиции по хешу ключа и ведёт для каждой отдельную хеш-таблицу. Это позволяет агрегировать данные без блокировок и конкуренции за кеш. Затем потоки объединяют частичные результаты по диапазонам партиций и соединяют их в полный результат GROUP BY.
Для Top-K большая часть этой работы не нужна. Если данные разделены на 4096 партиций, десять итоговых групп могут находиться максимум в десяти из них. Остальные партиции всё равно приходится объединять при стандартном алгоритме, хотя их результаты не попадут в ответ.
Простейший фильтр — общий счётчик агрегата на партицию. Если суммарное число заказов в партиции меньше значения у десятого места текущего Top-K, ни одна её группа не сможет войти в результат. Но такой критерий слишком грубый: сто товаров по 15 заказов дают общую сумму 1500 и не позволяют отбросить партицию при пороге 1000, хотя каждый товар заведомо ниже порога. При этом одинаковая сумма может скрывать одну группу с 1401 заказом, которую пропускать нельзя.
В Pivot добавили фиксированное число слотов внутри каждой партиции. Группа попадает в слот по дополнительным битам того же хеша, а слот хранит суммарный агрегат своих групп. Поскольку значение отдельной группы не превышает сумму слота, партицию можно пропустить, если все её слоты ниже текущего порога Top-K. Чем больше слотов, тем точнее оценка, без роста числа основных партиций. При равномерном распределении значений выгоды может не быть, поэтому движок должен отключать оптимизацию для таких данных.
По данным авторов, 63% запросов ClickBench используют подходящий шаблон. В Q16 время выполнения снизилось с 35,6 до 22,2 мс, ускорение составило 1,6 раза, а более 70% партиций не потребовали слияния. Команда также ожидает большего эффекта после появления в Pivot MPP и сброса данных на диск, поскольку пропуск партиций сократит обмен данными и дисковый ввод-вывод.