Речь здесь пойдёт о стабильности стандартной статистики Postgres и об идее очередного расширения - на этот раз альтернативы команде ANALYZE. Всё началось с того, что заканчивая работу над предыдущей статьёй я вдруг заметил, что результат выполнения одного и того же запроса теста Join Order Benchmark (JOB) в серии последовательных прогонов может отличаться в разы и даже на порядки - причем как по значению параметра execution-time, так и по pages-read. Это выглядело очень странно, поскольку и тест и ноутбук и все настройки оставались теми же - даже погода за окном. И я решил расследовать, что происходит …

Разрабатывая средства оптимизации планов запросов я часто использую JOB для оценки эффекта, который моя фича оказывает на планировщик. Как минимум, это позволяет выявить недочеты и определить, что не произошло деградации качества планов запросов, которые находит оптимизатор. Поэтому стабильность работы бенчмарка очень важна и затраты времени на анализ проблемы здесь оправданы. После недолгого исследования методики прогона бенчмарка обнаружился источник нестабильности - команда ANALYZE.

Построение статистики в PostgreSQL основано на базовых технологиях: Random Sampling with Reservoir, вычислении количества различных значений (ndistinct) и HyperLogLog для потоковой статистики - например, для вычисления distinct-значений в батчах при вычислении агрегатов или принятии решения об использовании оптимизации abbreviated keys. Поскольку природа расчёта статистики стохастическая, нет ничего странного в некоторых флуктуациях. Однако насколько больших, как их можно уменьшить и как это влияет на планы запросов? И самое главное - а как тогда сравнивать результаты бенчмарков при наличии таких значительных отклонений даже в базовом случае?

Можно ли добиться стабильности планов запросов?

Ок, подумал я, таблицы большие, строк много - давайте просто поднимем величину параметра default_statistics_target и это решит проблему, не так ли? Последовательно увеличиваю размер сэмпла для статистики со 100 до 10000, повторно выполняя прогон всех запросов бенчмарка и фиксирую как ведет себя критерий pages-read:

Имеем, что даже при максимальной детализации статистики планы запросов таки меняются после повторного выполнения ANALYZE. Если улучшение от увеличения выборки со 100 до 10000 и произошло, то это качественно не изменило ситуацию. В любом случае, такие большие нестабильности ставят под вопрос возможность независимого воспроизведения бенчмарка и сравнительного анализа результатов без сравнения планов запросов.

Теперь копнем поглубже: а что вообще флуктуирует? С помощью нехитрого скрипта проведём эксперимент и соберём скалярную статистику (stanullfrac, stawidth, stadistinct) перестроив статистики десять раз. Скрипт для такой операции может выглядеть следующим образом:

CREATE TABLE test_res(expnum integer, oid Oid, relname name, attname name,
                      stadistinct real, stanullfrac real, stawidth integer);
DO $$
DECLARE
    i integer;
BEGIN
  TRUNCATE test_res;
  FOR i IN 0..9 LOOP
    INSERT INTO test_res (expnum,oid,relname,attname,stadistinct,stanullfrac,stawidth)
      SELECT i, c.oid, c.relname, a.attname, s.stadistinct, s.stanullfrac, s.stawidth
      FROM pg_statistic s, pg_class c, pg_attribute a
      WHERE c.oid >= 16385 AND c.oid = a.attrelid AND
      s.starelid = c.oid AND a.attnum = s.staattnum;
    ANALYZE;
  END LOOP;
END; $$

А потом сравним результаты:

WITH changed AS (
  SELECT relname,attname,(abs(max - min) / avg * 100)::integer AS res, avg
  FROM (
    SELECT relname,attname, max(stadistinct) AS max, avg(stadistinct) AS min,
      avg(stadistinct) AS avg
    FROM test_res
    WHERE relname <> 'test_res'
    GROUP BY relname,attname
    )
  WHERE max - min > 0 AND abs(max - min) / avg > 0.01
) SELECT relname,attname, res AS "stadistinct dispersion", avg::integer
  FROM changed t
  ORDER BY relname,attname;

Здесь можно было бы использовать что-то более математически правильное, но для наших целей сойдет и такой простой критерий, чтобы посмотреть флуктуацию статистики. Используя вышеприведенные скрипты посмотрим, как флуктуирует ndistinct для 100, 1000 и 10000 элементов стат выборки:

Стохастичненько, правда? Здесь много странного, но мы не будем сильно копать, списав все на то, что определение значения ndistinct по небольшой выборке не сходится равномерно к истинному значению. Да, флуктуации затихают с размером выборки, но ведь 10000 это уже предел, а размеры таблиц в данном бенчмарке не такие уж и большие - в реальной жизни на много больших таблицах статистика может оставаться нестабильной.

Ещё одно наблюдение по результатам этого эксперимента: сильнее всего страдает статистика по полям с большим количеством дубликатов. На практике это означает, что группировка или соединение по какому-нибудь безобидному полю "Статус" может вызывать большие погрешности эстимации внутри оптимизатора, даже если выражение по этому полю только часть длинного списка выражений в запросе.

А в чём конкретно нестабильность?

Однако, что всё-таки конкретно приводит к флуктуации планов запросов в данном бенчмарке? Для этого нужно посмотреть в планы запросов. Один запрос у нас стабильно меняет план от итерации к итерации - 30с.sql из-за чего его удобно анализировать. сравнивая планы запросов можно заметить, что соперничают HashJoin и парметризованый NestLoop с очень близкими оценками (см здесь и здесь). При помощи метода пристального взгляда можно заметить, что расхождения в эстимациях начинаются уже на стадии SeqScan’a, расходясь потом по всему плану:

->  Parallel Seq Scan on public.cast_info
    (cost=0.00..498779.41 rows=518229 width=42)
    Output: id, person_id, movie_id, person_role_id, note, nr_order, role_id
    Filter: (cast_info.note = ANY ('{(writer),
          "(head writer)","(written by)",(story),"(story editor)"}'))

->  Parallel Seq Scan on public.cast_info
    (cost=0.00..498779.41 rows=520388 width=42)
    Output: id, person_id, movie_id, person_role_id, note, nr_order, role_id
    Filter: (ci.note = ANY ('{(writer),
          "(head writer)","(written by)",(story),"(story editor)"}'))

Видно небольшое различие в оценке количества выбираемых из таблицы строк. Копнем дальше и посмотрим в причину.

Сравнить гистограммы или MCV уже не так просто, поэтому просто изучим наш конкретный запрос, а точнее, проблемный оператор сканирования. Эстимация x = ANY (...) происходит путем эстимации каждого отдельного выражения x = Ni с последующим сложением вероятностей. В нашем случае, все пять констант Ni попадают в MCV-статистику - значит даже значение ndistinct не будет использовано Postgres. Таким образом, оценка должна быть максимально точна и стабильна. Однако если копнуть цифры, то можно увидеть, что после ANALYZE частотность каждого из элементов выборки меняется. Например для default_statistics_target=10000:

Итоговая оценка здесь изменяется примерно на процент, что в принципе не так много. Однако, кто знает, может быть мы не попали в плохую вероятность? К тому же, ошибка накапливается в процессе планирования вышестоящих операторов дерева запроса, что в итоге вызывает изменение плана этого запроса. 

В общем, это соответствует теории, что вычисление количества distinct в наборе значений c хорошей точностью можно получить только проанализировав практически все строки таблицы. Более того, в сообществе уже были как репорты проблем со статистикой [вот и вот для примера], так и  попытки решить проблему. Однако, это в любом случае упирается в дорогостоящее расширение объёма статистической выборки и не является универсально применимым - а значит не применимым в ядре PostgreSQL. Однако для аналитических задач, где размеры и денормализация схемы предъявляют повышенные требования к качеству статистики это имеет смысл. К тому же данные загружаются большими блоками и сбор статистики не требуется слишком часто. Так может быть мы можем это сделать через механизм расширений?

Схема расширения для стандартной статистики

Вспомним статью  DeWitt1998 -  там автор предложил строить статистику, цепляясь к SeqScan нодам запросов. В Postgres имеется механизм CustomScan нод, которую можно вставлять в произвольную часть плана запроса и реализовать произвольной сложности операции. Поэтому такую идею несложно реализовать. Также, никто не мешает с помощью расширения добавить в UI новую функцию, которая будет проходить всю таблицу и подсчитывать как минимум ndistinct и MCV максимально точно. Имея стандартную "легковесную" статистику на количество ndistinct можно еще перед запуском такой процедуры анализа прикинуть, насколько дорогостоящей и выполнимой она будет с точки зрения вычислительных ресурсов.

Подавать такую уточненную статистику в оптимизатор можно при помощи двух хуков: get_relation_stats_hook и get_index_stats_hook. Они позволяют подменить стандартную статистику, получаемую из  pg_statistic на любую другую, если только она соответствует внутреннему формату Postgres. Второй хук особенно интересен тем, что с его помощью можно реализовать статистику не полную, а предикатную - то есть статистику по данным, выбранным из таблицы с некоторым фильтром - аналог SQL Server’ного CREATE STATISTICS … WHERE … .

Как хранить статистику? Чтобы оптимизатор смог ее корректно использовать, очевидно, что формат ее хранения должен соответствовать формату хранения стандартной статистики. В этом нет ничего сложного, поскольку расширение может создавать собственные таблицы - так почему бы не создать pg_statistic_extra?

Дополнительные бонусы из создания такого расширения могут всплыть совершенно неожиданно. Например, в процессе написания данного поста я осознал для себя, что это может помочь решить диллему статистик по партиционированной таблице: никто не любит тратить на неё ресурсы, поскольку она фактически дублирует работу вычисления статистики по каждой отдельной партиции. При этом она не сильно-то и меняется со временем: партиций много и если данные хорошо размазаны, то и статистика по всем данным меняется несущественно (за исключением, возможно, ключа партиционирования). К тому же таблица может быть очень большой и такие штуки, как ndistinct в стандартной статистике могут быть далеки от реальности. А при помощи расширения можно реализовать создание детальной статистики по событию: attach/detach partition, в моменты обновлений и т.д., что может позволить более осознанно запускать вычислительно дорогую операцию.

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

Вот собственно и весь roadmap. Осталось найти активного студента и можно подаваться с проектом на GSoC ;). А что вы думаете об этой проблеме? Напишите в комментариях.

THE END.

2 февраля 2025 г., Паттайя, Тайланд.