Ускоряем запросы в PostgreSQL, оптимизируя оператор GROUP BY19.11.2024 17:01

Пользователи PostgreSQL нередко оперируют аналитическими запросами, которые предполагают сортировку и группировку данных по разным правилам. Время и стоимость выполнения таких запросов можно значительно сократить, если оптимизировать вычисление агрегатов и сортировок. Об одной из таких оптимизаций — выборе порядка колонок в выражении GROUP BY — расскажем в этой статье.

Postgres уже умеет перестраивать список группируемых выражений в соответствии с порядком колонок из условия ORDER BY, чтобы исключить дополнительную сортировку и сэкономить вычислительные ресурсы. Мы пошли дальше, реализовали свою идею в дистрибутивах Postgres Pro Standard и Enterprise и вынесли патчи на обсуждение сообщества Postgres (первое и второе) с расчётом, что они войдут в ближайшую версию ванильного PostgreSQL.

Для группировки таблиц СУБД по одной или нескольким колонкам обычно используют методы хэширования (HashAgg) или предварительной сортировки строк (кортежей) с последующим проходом по отсортированному множеству (SortAgg). В случае сортировки по множеству колонок Postgres должен вызывать оператор сравнения не однократно, а для каждой пары значений. Например, чтобы сравнить строку таблицы ('UserX1', 'Saturday', $100) со строкой ('UserX1', 'Monday', $10) и определить относительный порядок этих строк, мы должны сначала сравнить два первых значения и, если они совпали, перейти к следующей паре. Если вторая пара значений (в нашем примере 'Saturday' и 'Monday') отличается, то нет смысла вызывать оператор сравнения для третьего элемента.

Именно на этом приципе основан наш механизм оптимизации оператора SortAgg. Если при сравнении строк в начале сравнивать значения колонки с меньшим количеством дубликатов (например, сначала сравнивать номера СНИЛС, а затем дни недели), то вызывать оператор сравнения придётся значительно реже.

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

Пример 1

Отсортируем таблицу по одним и тем же полям, но в разном порядке: 

CREATE TABLE shopping (
  CustomerId bigint, CategoryId bigint, WeekDay text, Total money
);
INSERT INTO shopping (CustomerId, CategoryId, WeekDay, Total)
  SELECT random()*1E6, random()*100, 'Day ' || (random()*7)::integer,
    random()*1000::money
  FROM generate_series(1,1E6) AS gs;
VACUUM ANALYZE shopping;

SET max_parallel_workers_per_gather = 0;
SET work_mem = '256MB';

EXPLAIN (ANALYZE, TIMING OFF)
SELECT CustomerId, CategoryId, WeekDay, Total
FROM shopping
ORDER BY WeekDay,Total,CategoryId,CustomerId;

EXPLAIN (ANALYZE, TIMING OFF)
SELECT CustomerId, CategoryId, WeekDay, Total
FROM shopping
ORDER BY CustomerId,CategoryId,WeekDay,Total;

Результаты выполнения этих запросов будут такими: 

 Sort  (cost=117010.84..119510.84 rows=1000000 width=30)
       (actual rows=1000000 loops=1)
   Sort Key: weekday, total, categoryid, customerid
   Sort Method: quicksort  Memory: 71452kB
   ->  Seq Scan on shopping  (actual rows=1000000 loops=1)
 Execution Time: 2858.596 ms

 Sort  (cost=117010.84..119510.84 rows=1000000 width=30)
       (actual rows=1000000 loops=1)
   Sort Key: customerid, categoryid, weekday, total
   Sort Method: quicksort  Memory: 71452kB
   ->  Seq Scan on shopping  (actual rows=1000000 loops=1)
 Execution Time: 505.775 ms

Второй запрос выполняется почти в шесть раз быстрее первого, хотя данные в обоих запросах одни и те же. Всё потому, что оператор сравнения во втором случае вызывался реже. В сортируемом кортеже 4 колонки (CustomerId, CategoryId, WeekDay, Total), а Postgres вызывает оператор сравнения отдельно для каждой пары значений — максимум 4 раза. Но если первой колонкой в сравнении идёт CustomerId, то необходимость вызывать оператор сравнения для следующей колонки будет намного ниже, чем когда первой стоит колонка WeekDay.

Этот пример показывает, что вычислительные затраты в операции сортировки довольно весомы. С учётом того, что в аналитическом запросе может быть множество сортировок/досортировок (каждый агрегат может определить свой порядок входящих данных), такая дополнительная операция позволит сэкономить вычислительные ресурсы.

Заметим, что значения поля Сost оператора Sort в примере 1 одинаковы. Значит, для оптимизатора Postgres оба варианта сортировки идентичны (вариант сортировки определяется случайным образом).

Поскольку порядок сортировки при группировке (GROUP BY) или слиянии (Merge Join) не влияет на итоговый результат, то можно выбирать его так, чтобы минимизировать количество операций сравнения. А если в таблице множество индексов, то сканировать и досортировывать данные можно разными способами, и правильный выбор варианта инкрементальной сортировки (IncrementalSort) может дать позитивный эффект.

Пример 2

Допустим, нужно сгруппировать данные, чтобы вычислить средние затраты каждого покупателя в заданной категории товаров в зависимости от дня недели: 

SET enable_hashagg = 'off';
EXPLAIN (ANALYZE, TIMING OFF)
SELECT CustomerId, CategoryId, WeekDay, avg(Total::numeric)
FROM shopping
GROUP BY WeekDay,CategoryId,CustomerId;

/*
GroupAggregate (actual rows=999370 loops=1)
   Group Key: weekday, categoryid, customerid
   ->  Sort (actual rows=1000000 loops=1)
         Sort Key: weekday, categoryid, customerid
         Sort Method: quicksort  Memory: 71452kB
         ->  Seq Scan on shopping (actual rows=1000000 loops=1)
  Execution Time: 2742.777 ms
 */

Чтобы явно продемонстрировать концепцию, мы отключили агрегацию методом хэширования. С точки зрения запроса порядок колонок в выражении GROUP BY совершенно не важен. Изменим этот порядок и посмотрим результат: 

EXPLAIN (ANALYZE, TIMING OFF, COSTS OFF)
SELECT CustomerId, CategoryId, WeekDay, avg(Total::numeric)
FROM shopping
GROUP BY CustomerId,CategoryId,WeekDay;

/*
 GroupAggregate (actual rows=999370 loops=1)
   Group Key: customerid, categoryid, weekday
   ->  Sort (actual rows=1000000 loops=1)
         Sort Key: customerid, categoryid, weekday
         Sort Method: quicksort  Memory: 71452kB
         ->  Seq Scan on shopping (actual rows=1000000 loops=1)
  Execution Time: 1840.517 ms
 */

Что ж, ускорение не столь впечатляющее, как в примере 1, но достаточно заметное и, что важно, бесплатное: нам не потребовался новый индекс или сложная трансформация запроса. Такое изменение можно сделать автоматически, главное научить оптимизатор Postgres различать стоимости разных комбинаций grouping clause и рассматривать дополнительную стратегию группировки.

Немного истории

В 2023 году Postgres научился исключать избыточные колонки из операции группировки. Избыточность может возникать, например, когда в дереве запроса имеется выражение равенства: 

EXPLAIN (COSTS OFF)
SELECT sum(total) FROM shopping WHERE CustomerId=CategoryId
GROUP BY CustomerId,CategoryId;

/*
 HashAggregate
   Group Key: customerid
   ->  Seq Scan on shopping
         Filter: (customerid = categoryid)
 */

В примере выше значения в колонках CustomerId и CategoryId принадлежат одному классу эквивалентности (абстракция EquivalenceClass в коде Postgres), и любую из этих колонок можно исключить из выражения группировки.

В PostgreSQL 17 появилась ещё одна дополнительная стратегия: оптимизатор научился подстраивать порядок группируемых колонок для сортировки входных данных. Таким образом, во время планирования Postgres рассматривает уже две альтернативных стратегии:

  1. Сгруппировать уже отсортированные данные, а затем пересортировать по требованиям ORDER BY.

  2. Сортировать входящие данные по правилам, заданным ORDER BY, а затем выполнить группировку.

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

CREATE INDEX ON shopping(CustomerId, weekday);

EXPLAIN (COSTS OFF)
SELECT count(*) FROM shopping WHERE CustomerId < 5000
GROUP BY WeekDay,CustomerId ORDER BY WeekDay,CustomerId;

EXPLAIN (COSTS OFF)
SELECT count(*) FROM shopping WHERE CustomerId < 50000
GROUP BY WeekDay,CustomerId ORDER BY WeekDay,CustomerId;

/*
 GroupAggregate
   Group Key: weekday, customerid
   ->  Sort
         Sort Key: weekday, customerid
         ->  Index Only Scan using shopping_customerid_weekday_idx on shopping
               Index Cond: (customerid < 5000)

Sort
   Sort Key: weekday, customerid
   ->  GroupAggregate
         Group Key: customerid, weekday
         ->  Index Only Scan using shopping_customerid_weekday_idx on shopping
               Index Cond: (customerid < 50000)
 */

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

Не правда ли, дополнительная стратегия Postgres позволяет находить весьма интересные варианты планов запросов? Минус в том, что для оптимизации кейсов из примеров 1 и 2 она не задействует статистику распределения данных.

Что мы предлагаем

Наша стратегия переупорядочения колонок основана на знании статистики распределения значений в колонках таблицы. Это cost-based-стратегия, она предлагает оптимизатору альтернативный вариант выполнения оператора, который минимизирует количество операций сравнения при сортировке.

Чтобы пояснить основную идею, рассмотрим запрос с группировкой из примера выше: 

SELECT avg(Total::numeric) FROM shopping GROUP BY CustomerId,CategoryId,WeekDay;

Случай, когда в первой позиции сортировки находится CustomerId, является более эффективным, поскольку содержит наибольшее (примерно половину из 1 млн) количество distinct-значений. А значит, для каждого кортежа есть 2 других кортежа, где операция сравнения значений колонки CustomerId не определит порядок этих кортежей, и придётся сравнивать значения из последующих колонок.

В колонке WeekDay не более 7 различных значений, и если она сортируется первой, то для определения порядка с большой долей вероятности придется сравнивать значения последующих колонок.

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

Первый патч вводит кэширование distinct-статистики по столбцам, которые упоминаются в выражениях запроса. Например, если в запросе имеется условие A.CustomerId=B.PersonId, то кэшируется число различных значений в колонках A.CustomerId и B.PersonId.

Второй патч касается формулы подсчёта стоимости сортировки. В текущей версии Postgres сортировка оценивается по формуле:

cost = C * N * log_2(N),

где
N — количество кортежей для сортировки,
C = 2.0*cpu_operator_cost — параметр, регулируемый пользователем.

Этот патч вводит количество колонок таблицы в оценку стоимости:

cost = (1.0 + ncols) * N * log_2(N).

Подход очень простой и весьма топорный, однако даже с такой простой формулой Postgres может оценивать различные варианты сортировки.

Эта модель меняет баланс некоторых операторов внутри Postgres. Например, модель стоимости операции агрегации методом хэширования (HashAgg) учитывает количество колонок в агрегируемом кортеже. В то же время агрегация с предварительной сортировкой оценивалась излишне позитивно в случае длинного списка сортируемых значений. Таким образом, этот патч усиливает крен оптимизатора в сторону хэширования в операциях группировки особенно на небольших объёмах данных.

Третий патч переосмысляет формулу из второго патча. Здесь кэш distinct-статистики, добавленный первым патчем, помогает оценить количество distinct-значений в первой сортируемой колонке и формула становится такой:

cost = [1.0 + 1.0+(\frac{N-ndistinct}{N-1})*(ncols-1) ]* N * log_2(N).

Этот подход можно расширить при наличии достоверной статистики по совместному распределению колонок, но мы ограничимся только первой колонкой (этого достаточно в большинстве случаев). Как видим, оптимизатор способен различать стоимость сортировки различных комбинаций колонок, а это позволяет выбрать оптимальный вариант сортировки.

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

Посмотрим теперь на то, как повлияет такое изменение на запросы, приведённые в примерах 1 и 2. Начнём с сортировки: 

EXPLAIN (ANALYZE, TIMING ON)
SELECT CustomerId, CategoryId, WeekDay, Total
FROM shopping
ORDER BY CustomerId,CategoryId,WeekDay,Total;

EXPLAIN (ANALYZE, TIMING ON)
SELECT CustomerId, CategoryId, WeekDay, Total
FROM shopping
ORDER BY CategoryId,CustomerId,WeekDay,Total;

/*
Sort  (cost=191291.64..193791.64) (actual time=350.819..395.024)
   Sort Key: customerid, categoryid, weekday, total
   ->  Seq Scan on shopping  (cost=0.00..17353.00) (actual time=0.031..60.262)
 Execution Time: 423.583 ms

Sort  (cost=266482.66..268982.66)
       (actual time=653.143..694.736)
   Sort Key: categoryid, customerid, weekday, total
   ->  Seq Scan on shopping  (cost=0.00..17353.00) (actual time=0.012..55.073)
 Execution Time: 723.005 ms
 */

Можно заметить два заметных улучшения:

  1. Изменился уровень величины cost-запроса в целом, и соотношение стоимости сортировки к стоимости сканирования стало точнее отражать реальность.

  2. Отличие в стоимости плана отражает различие времени выполнения запроса.

А теперь — результат выполнения запроса с группировкой: 

SET enable_hashagg = 'off';
EXPLAIN (COSTS OFF)
SELECT CustomerId, CategoryId, WeekDay, avg(Total::numeric)
FROM shopping
GROUP BY WeekDay,CategoryId,CustomerId;

/*
 GroupAggregate
   Group Key: customerid, weekday, categoryid
   ->  Sort
         Sort Key: customerid, weekday, categoryid
         ->  Seq Scan on shopping
 */

Оптимизатор изменил порядок следования колонок и переставил колонку CustomerId в начало списка группировки. Учитывая реальное распределение значений по остальным колонкам, можно было дополнительно переставить колонки CategoryId и WeekDay. Но такая тонкая настройка имеет мало практического смысла и с достаточной достоверностью может быть сделана при наличии расширенной статистики по всем трем полям.

Безусловно, предлагаемое решение неидеально: математическую модель можно корректировать и делать как более практичной (случай, когда во всех колонках содержатся дубликаты крайне редкий), так и более детализированной. Также мы не учитывали относительную стоимость оператора сравнения: для сравнения строковых типов потребуется больше ресурсов, чем для целочисленных, не так ли? Однако основную задачу — создать дополнительную стратегию группировки, которая качественно отличается от уже имеющихся в оптимизаторе Postgres, — она выполняет.

Замечания, дополнения или идеи альтернативного решения проблемы прошу оставлять в комментариях или в community mailing list.

© Habrahabr.ru