Почему нельзя просто считать медиану на каждом воркере и потом объединять

Что проверяют

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

Как отвечать

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

Контрпример приводится в одну строку. Пусть на одном воркере [1, 2, 3], на другом [100, 200, 300]. Локальные медианы равны 2 и 200, их среднее 101, а настоящая медиана объединения 51.5. Размеры частей тут одинаковые, то есть взвешивание по размеру проблему не лечит.

Что делать вместо этого. Точно: полная сортировка с перемешиванием по ключу, либо многопроходный поиск по значению, когда бинарным поиском подбирается граница, а каждый проход считает, сколько элементов ниже неё. Приближённо: скетчи квантилей вроде t-digest, Q-digest или алгоритма Гринвальда и Ханны. Они сливаются ассоциативно и дают гарантию по ошибке, поэтому именно на них построены percentile_approx в Spark и quantileTDigest в ClickHouse.

Где спотыкаются

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

Вспоминают median of medians и предлагают его как способ слияния. Это алгоритм выбора опорного элемента в quickselect, он нужен, чтобы гарантировать линейное время поиска, и точной медианы сам по себе не даёт.

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