Сортировка и группировка

Группировка

Авторские права

Авторы: Егор Рогов, Павел Лузанов, Павел Толмачев, Илья Баштанов

Фото: Олег Бартунов (монастырь Пху и пик Бхрикути, Непал)

Использование материалов курса

Некоммерческое использование материалов курса (презентации,

демонстрации) разрешается без ограничений. Коммерческое

использование возможно только с письменного разрешения компании

Postgres Professional. Запрещается внесение изменений в материалы

курса.

Обратная связь

Отзывы, замечания и предложения направляйте по адресу:

edu@postgrespro.ru

Отказ от ответственности

Компания Postgres Professional не несет никакой ответственности за

любые повреждения и убытки, включая потерю дохода, нанесенные

прямым или непрямым, специальным или случайным использованием

материалов курса. Компания Postgres Professional не предоставляет

каких-либо гарантий на материалы курса. Материалы курса

предоставляются на основе принципа «как есть» и компания Postgres

Professional не обязана предоставлять сопровождение, поддержку,

обновления, расширения и изменения.

Темы

Применение группировки

Группировка хешированием

Группировка сортировкой

Комбинированная группировка

Группировка в параллельных планах

Оконные функции

Применение группировки

Явное указание

GROUP BY

Исключение дубликатов

DISTINCT

UNION, INTERSECT, EXCEPT

В SQL-запросе набор строк можно сгруппировать с помощью

предложения GROUP BY, в сочетании с которым обычно используются

агрегатные функции, обрабатывающие все строки группы. Похожую

возможность для оконных функций дает предложение PARTITION BY.

Группировка может выполняться и неявно при устранении дубликатов

в запросе со словом DISTINCT или с командами обработки двух

наборов строк (UNION, INTERSECT, EXCEPT без слова ALL), которые

удаляют дубликаты.

Сервер выбирает один из доступных способов группировки, учитывая

имеющиеся ресурсы, возможность получить отсортированные данные

для ключа группировки и другие факторы.

Группировка хешированием

Yellow Submarine

Abbey Road

The Beatles

3 Let It Be

1969

1968

1970

id title year

корзина 00

010001 00

корзина 11

SELECT year, count(*) cnt

FROM t

GROUP BY year;

корзина 10

корзина 01

1970

счетчик

Про идею хеширования было рассказано в теме «Типы индексов».

При группировке значений может использоваться похожий принцип.

В примере на слайде показано, как вычисляется значение агрегатной

функции count при группировке по полю year. Сервер получает и по

очереди обрабатывает строки таблицы.

Предварительно рассчитывается количество корзин — степень числа 2,

и определяется число разрядов хеш-кода, содержащих номер корзины.

В примере на слайде это два последних разряда.

Для строки вычисляется хеш-функция от значения year. По хеш-коду

определяется номер корзины и в хеш-таблицу добавляется запись

с хеш-кодом, если его еще нет в таблице.

Поскольку в нашем примере вычисляется значение агрегатной функции

count, в каждой записи хеш-таблицы дополнительно хранится счетчик,

который увеличивается при обработке очередной строки.

В нашем примере первая строка порождает новую запись в корзине 00.

SELECT year, count(*) cnt

FROM t

GROUP BY year;

корзина 00

корзина 11

корзина 10

корзина 01

Группировка хешированием

Yellow Submarine

Abbey Road

The Beatles

3 Let It Be

1969

1968

1970

id title year

100010 01 1

1970

1969

010001 00

Вторая строка попадает в корзину 01 и порождает в ней новую запись.

корзина 00

корзина 11

корзина 10

корзина 01

Группировка хешированием

Yellow Submarine

Abbey Road

The Beatles

3 Let It Be

1969

1968

1970

id title year

010001 00 1

100010 01 1

110001 11 1

1970

1969

1968

SELECT year, count(*) cnt

FROM t

GROUP BY year;

Третья строка порождает новую запись в корзине 11.

корзина 00

корзина 11

корзина 10

корзина 01

Группировка хешированием

Yellow Submarine

Abbey Road

The Beatles

3 Let It Be

1969

1968

1970

id title year

110001 11 1

1970

1969

1968

010001 00

100010 01

SELECT year, count(*) cnt

FROM t

GROUP BY year;

Хеш-код последней строки попадает в корзину с номером 01. В корзине

уже есть запись с таким значением ключа, поэтому сервер увеличивает

значение ее счетчика на единицу. На этом обработка таблицы

завершается: в хеш-таблице собрались все уникальные значения.

Алгоритм возвращает сами значения и их количество.

Такой же алгоритм (с незначительными модификациями) используется

и для получения уникальных записей без вычисления агрегатной

функции, и при вычислении других агрегатных функций.

корзина 00

корзина 11

корзина 10

корзина 01

Хеш-группировка и пакеты

Yellow Submarine

Abbey Road

The Beatles

3 Let It Be

1969

1968

1970

id title year

01011 0 11 1

work_mem × hash_mem_multiplier =

= 4MB × 2

1965

1969

1966

01010 0 00

10001 0 01

Help!

Revolver

A Hard Day’s Night

2 Please Please Me

1965

1966

1964

1963

00110 1 10

01000 1 00

1964

1970

11000 1 11 1968

пакет 1

11010 0 10 11963

Если выделенной памяти не хватает, исходный набор разбивается на

части (пакеты), так чтобы хеш-таблица для каждого пакета умещалась

в оперативной памяти. Расчетное количество пакетов — степень

числа 2; в хеш-коде выделяется нужное количество битов, которые

определяют принадлежность записи пакету (на слайде два пакета,

поэтому достаточно одного бита). Хеш-таблица для пакета 0

располагается в оперативной памяти, строки остальных пакетов

помещаются во временные файлы — каждый пакет в свой файл.

Использование временных файлов значительно снижает

производительность, и при хешировании этот эффект проявляется

сильнее, чем для других алгоритмов. Поэтому при группировке

хешированием выделяется work_mem × hash_mem_multiplier

оперативной памяти — по умолчанию вдвое больше, чем обычно.

Хеш-группировка и пакеты

work_mem × hash_mem_multiplier

00110 1 10

01000 1 00

1964

1970

11000 1 11 1968

пакет 1

корзина 00

корзина 11

корзина 10

корзина 01

11000 1 11 1

1970

1968

01000 1 00

00110 1 10 11964

Затем каждый из пакетов, записанных во временные файлы, читается в

память и формирует новую хеш-таблицу.

После обработки всех исходных строк, а также каждого из

дополнительных пакетов сервер может возвращать частичные

результаты (строки для каждой группы всегда находятся в одном

пакете).

Группировка сортировкой

1968

1969

1970

SELECT DISTINCT year

FROM t;

Yellow Submarine

Abbey Road

The Beatles

3 Let It Be

1969

1968

1970

id title year

1969

1968

1970

количество

SELECT year, count(year)

FROM t

GROUP BY year;

3 Let It Be 1970

набор

отсортирован

Исключение дубликатов и группировка могут выполняться не только

путем хеширования, но и с помощью сортировки. В этом случае

требуется набор данных, предварительно отсортированный по полям

группировки.

Узел Unique устраняет дубликаты, добавляя к результату очередное

значение, если оно не совпадает с предыдущим.

Узел GroupAggregate возвращает агрегированные данные. В примере

на слайде узел строит список различных значений поля year,

подсчитывая, сколько раз встретилось каждое из них в наборе данных.

Как было рассмотрено в предыдущей теме, упорядоченный набор строк

может быть получен с помощью индексного доступа или в результате

сортировки в узле Sort. В первом случае узлы Unique и GroupAggregate

обычно более выгодны, чем HashAggregate, поскольку выполняются

быстро и не требуют много памяти. Однако во втором случае

построение хеш-таблицы, как правило, эффективнее сортировки.

В отличие от HashAggregate, оба узла: Unique и GroupAggregate –

возвращают упорядоченные данные.

В параллельных планах

Gather

Partial

HashAggregate

Parallel

SeqScan

Finalize

HashAggregate

Partial

HashAggregate

Parallel

SeqScan

Gather

Merge

Finalize

GroupAggregate

Partial

HashAggregate

Parallel

SeqScan

Sort

Partial

HashAggregate

Parallel

SeqScan

Sort

Агрегация не имеет специальной параллельной реализации, но может

выполняться в параллельных планах. В этом случае каждый рабочий

процесс агрегирует свою часть данных и передает результат узлу

Gather, который собирает данные в единый набор. Следующий узел

выполняет агрегацию объединенного набора и вычисляет значение

агрегатной функции.

Пример такого плана показан на слайде слева. Обычно такой вариант

выигрывает, если количество групп достаточно велико.

Если же групп немного, может оказаться выгодным отсортировать

сгруппированные строки в каждом процессе. А дальше воспользоваться

тем, что наборы упорядочены, и на последнем этапе выполнить более

быструю группировку сортировкой.

Пример такого плана показан на слайде справа.

Оконные функции

Группировка всегда использует сортировку

1 2 3 4 5 1 2 3 4 5

OVER (PARTITION BY) OVER (PARTITION BY ORDER BY)

Группировка используется и в оконных функциях.

Если определение окна включает конструкцию PARTITION BY, оконная

функция вычисляется на основе групп строк (аналогично группировке

GROUP BY).

Для каждой группы строк границы рамки меняются в своих пределах.

Если при этом нет других указаний, для всех строк одной группы будет

получено одинаковое значение функции.

Как и в примере из темы «Сортировка», указание ORDER BY

упорядочивает строки в каждой группе; в этом случае предполагается,

что рамка охватывает строки от первой до текущей.

В отличие от обычной группировки GROUP BY, группировка

в определении окна всегда реализуется с помощью сортировки: план

строится так, чтобы на вход узлу WindowAgg пришел набор строк,

отсортированный сначала по ключам группировки PARTITION BY,

а затем — по ключам сортировки ORDER BY. Хеширование не

применяется даже в отсутствие конструкции ORDER BY.

Итоги

Группировка происходит не только при агрегации,

но и при устранении дубликатов

Выполняется с помощью хеширования или сортировки

Практика

1. Как выполняется запрос, вычисляющий количество мест

каждой категории в таблице seats?

Попробуйте со значениями параметров по умолчанию,

а затем запретите группировку хешированием.

2. Изучите запрос с оконной функцией и предложением

PARTITION BY:

SELECT status, count(*) OVER (PARTITION BY status)

FROM flights

WHERE flight_no = 'PG0007'

AND departure_airport = 'VKO'

AND flight_id BETWEEN 24104 AND 24115;

Добавьте вызов функции row_number с тем же окном

и сравните результаты и планы выполнения.

1. Запрос:

SELECT fare_conditions, count(*)

FROM seats

GROUP BY fare_conditions;

Для запрета группировки хешированием установите параметр

enable_hashagg в off.