Приблизительные процентили
Вычисление точных процентилей над крупными наборами данных может требовать слишком больших затрат, и поэтому мы использовали инфраструктуру SQL/MR для реализации вычисления приблизительных процентилей. Это позволяет распараллелить вычисление процентилей, если допустить наличие некоторой ошибки. В этой реализации также используется динамический полиморфизм SQL/MR, позволяющий вычислять приблизительные процентили над данными разных типов.
Рис. 8. Вычисление приблизительных процентилей с использованием SQL/MR.
Мы реализовали распределенный алгоритм вычисления приблизительных процентилей, описанный в [9], в виде пары SQL/MR-функций. Для применения этого средства требуется указать значения требуемых процентилей и максимальную относительную ошибку e (рис. 8). Относительная ошибка определяется следующим образом: для каждого значения v, которое алгоритм оценивает как относящееся к n-ой процентили, реальная процентиль v находится в интервале между n-e и n+e. Если не вдаваться в детали, алгоритм сначала вычисляет сводные данные в каждом узле, а потом склеивает в некотором одном узле эти сводные данные для получения приблизительных процентилей. Мы реализовали этот алгоритм с использованием функции approximate_percentile_summary, которая вызывается надо всеми уместными данными в заданном узле и выдает в качестве результата сводные данные. Затем все сводные данные переносятся в один узел с использованием конструкции PARTITION BY 1, где они склеиваются для получения окончательного результата функцией approximate_percentile_merge. Результирующая схема approximate_percentile_merge состоит из схемы входной таблицы, к которой добавлен столбец percentile.
