Привет, Хабр! Делимся переводом статьи о патче, сделанном разработчиком «Тантор Лабс» для 19 версии PostgreSQL — по сути, частичкой вклада нашей компании.

Скрытая стоимость избыточной осведомленности. Так можно сказать о ситуации, когда данные распределены неравномерно, целевые значения статистики Postgres установлены высоко, и планировщик пытается оценить стоимость операции JOIN.

Более 20 лет Postgres использовал простой цикл со сложностью O(N²) для сравнения списков наиболее частых значений (Most Common Values, MCV) во время оценки join. Это работало нормально, когда целевые значения статистики малы (по умолчанию default_statistics_target равен 100). Но сегодня опыт PostgreSQL рекомендует увеличивать это значение. Известно, что пользователи используют высокие значения (1000, а иногда и выше), чтобы справиться со сложным распределением данных, и если добавить к этому запрос с 10 соединениями — этот «простой цикл» легко может стать тихим убийцей производительности на этапе планирования.

В Postgres 19 это меняется.

Проблема: Квадратичная сложность!

Когда вы соединяете две таблицы, планировщику нужно оценить, сколько строк совпадет. Если в обоих столбцах есть списки MCV, функция eqjoinsel() пытается сопоставить их, чтобы получить точную оценку.

Исторически это делалось путем сравнения каждого элемента из списка A с каждым элементом из списка B.

• Если у вас 100 MCV — это 10 000 сравнений. Быстро.

• Если у вас 10 000 MCV (максимальный целевой показатель статистики) — это 100 000 000 сравнений. Уже не так быстро.

Это означало, что само планирование запроса могло занимать значительно больше времени, чем его выполнение, особенно для простых OLTP-запросов.

Решение: Использовать хеширование

Выход из ситуации – элегантен и эффективен. Вместо вложенного цикла планировщик теперь делает следующее:

1. Проверяет, превышает ли общее количество MCV 200 (по 100 с каждой стороны).

2. Если да, он строит хеш-таблицу для MCV с одной (меньшей) стороны.

3. Затем проходит по MCV с другой стороны, проверяя их по этой хеш-таблице.

Порог 200 был выбран потому, что хеширование имеет начальную стоимость (выделение памяти, вычисление хешей). Для небольших списков простой цикл на самом деле быстрее. Но как только вы пересекаете этот порог, хеш-таблица оказывается эффективнее.

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

Давайте-ка сравним

Я хотел проверить все самостоятельно, поэтому создал наихудший сценарий: две таблицы с 100 000 строк, но только 10 000 уникальных значений, и я установил целевой показатель статистики на максимум (10 000), чтобы получить огромный список MCV.

Настройка

CREATE TABLE t1 (x int);
CREATE TABLE t2 (x int);

-- Сценарий A: 3 млн строк, статистика 10000
INSERT INTO t1 SELECT x % 10000 FROM generate_series(1, 3000000) x;
INSERT INTO t2 SELECT x % 10000 FROM generate_series(1, 3000000) x;

-- Максимизируем целевой показатель статистики
ALTER TABLE t1 ALTER COLUMN x SET STATISTICS 10000;
ALTER TABLE t2 ALTER COLUMN x SET STATISTICS 10000;

ANALYZE t1;
ANALYZE t2;

Результаты

Я выполнил следующий запрос 10 раз в обеих версиях, чередуя их для справедливости, и использовал медиану для результатов:

EXPLAIN (ANALYZE, TIMING OFF) SELECT count(*) FROM t1 JOIN t2 ON t1.x = t2.x;

Сценарий A: Высокая статистика (10k MCV)

• Строк: 3 миллиона

• Целевой показатель статистики: 10 000

• Количество MCV: 10 000

• До (Postgres 18): ~27,8 мс

• После (Postgres 19): ~1,75 мс

• Ускорение: ~16x

Сценарий B: Средняя статистика (1k MCV)

• Строк: 300 000

• Целевой показатель статистики: 1 000

• Количество MCV: 1 000

• До (Postgres 18): ~0,85 мс

• После (Postgres 19): ~0,60 мс

• Ускорение: ~1,4x (ускорение на 40%)

Сценарий C: Статистика по умолчанию (100 MCV)

• Строк: 30 000

• Целевой показатель статистики: 100 (по умолчанию)

• Количество MCV: 100

• До (Postgres 18): ~0,40 мс

• После (Postgres 19): ~0,43 мс

• Ускорение: Отсутствует (оптимизация правильно пропущена)

Поскольку общее количество MCV в Сценарии C (100 + 100 = 200) не превысило порог в 200, Postgres 19 правильно выбрал простой цикл, избегая накладных расходов на построение хеш-таблицы. Это подтверждает, что исправление достаточно умное, чтобы применяться только тогда, когда это важно.

«Квадратичная кривая» в действии

Чтобы визуализировать разницу между O(N²) и O(N), я провел тестирование в широком диапазоне целевых значений статистики (от 10 до 10 000). В каждом тесте количество строк было установлено в 300 раз больше целевого значения статистики, чтобы гарантировать, что список MCV полностью заполнен и релевантен.

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

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

Спасибо Илье Евдокимову за разработку, Давиду Гейеру за соавторство и Тому Лейну за рецензирование.

Примечание: Эта функция сейчас находится в основной ветке (master) разработки Postgres 19. Как и все функции в разработке, она может быть изменена до окончательного выпуска.