Партиционированный Postgres: немного о проблемах с лимитами

В то время, как пользователи видят позитивные стороны технологий, мы, разработчики, обычно сталкиваемся с ограничениями/недоработками/багами и видим наш продукт с совсем другой стороны. Вот и в этот раз: после публикации результатов сравнительного тестирования где прогонялись запросы теста Join-Order-Benchmark на базе с партициями и без, меня не отпускало ощущение, что всё-таки что-то я не досмотрел и при наличии партиций постгрес должен строить план хуже, чем без них. И это должен быть не просто баг, а технологическое ограничение. И вот, методом разглядывания потолка удалось-таки найти тонкое место - запросы с лимитами.

В отличие от одиночной таблицы, при наличии ограничения на количество выдаваемых строк или fractional paths (к примеру, SQL-директива LIMIT может задавать такое ограничение), оптимизатор сталкивается со множеством вопросов: сколько строк будет извлечено из каждой партиции? А может будет задействована только первая? А какая будет первая? - это неочевидно в условиях потенциально возможного execution-time pruning'a партиций ...

А что, если сканирование партиций у нас будет происходить по индексу, а результат будет получен слиянием - то есть при наличии MergeAppend'a - здесь совсем непонятно как оценивать количество строк, которые должны будут быть извлечены из партиции и, следовательно, какой оператор сканирования применить. А что, если используя partitionwise join у нас под Append попадает целое поддерево - знание о лимитах в таком случае является важным - к примеру, при выборе типа JOIN, разве нет?

Проблема промежуточных планов запросов

Такое множество вопросов к партиционированию привело к компромиссному решению в при выборе плана запроса для поддерева, находящегося под Append'ом: для целей выбора оптимально fractional path рассматривается два варианта плана: с минимальным total cost и с минимальным startup cost. Грубо говоря, план будет оптимален, если у нас в запросе есть LIMIT 1 или какой-то очень большой LIMIT. А как быть с промежуточными вариантами? Давайте посмотрим в конкретные примеры (спасибо @apyhalov).

DROP TABLE IF EXISTS parted,plain CASCADE;
CREATE TEMP TABLE parted (x integer, y integer, payload text)
PARTITION BY HASH (payload);
CREATE TEMP TABLE parted_p1 PARTITION OF parted
  FOR VALUES WITH (MODULUS 2, REMAINDER 0);
CREATE TEMP TABLE parted_p2 PARTITION OF parted
  FOR VALUES WITH (MODULUS 2, REMAINDER 1);
INSERT INTO parted (x,y,payload)
  SELECT (random()*600)::integer, (random()*600)::integer, md5((gs%500)::text)
  FROM generate_series(1,1E5) AS gs;
CREATE TEMP TABLE plain (x numeric, y numeric, payload text);
INSERT INTO plain (x,y,payload) SELECT x,y,payload FROM parted;
CREATE INDEX ON parted(payload);
CREATE INDEX ON plain(payload);
VACUUM ANALYZE;
VACUUM ANALYZE parted;

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

EXPLAIN (COSTS OFF)
SELECT * FROM plain p1 JOIN plain p2 USING (payload) LIMIT 100;
EXPLAIN (COSTS OFF)
SELECT * FROM parted p1 JOIN parted p2 USING (payload) LIMIT 100;

/*
 Limit
   ->  Nested Loop
         ->  Seq Scan on plain p1
         ->  Memoize
               Cache Key: p1.payload
               Cache Mode: logical
               ->  Index Scan using plain_payload_idx on plain p2
                     Index Cond: (payload = p1.payload)

 Limit
   ->  Merge Join
         Merge Cond: (p1.payload = p2.payload)
         ->  Merge Append
               Sort Key: p1.payload
               ->  Index Scan using parted_p1_payload_idx on parted_p1 p1_1
               ->  Index Scan using parted_p2_payload_idx on parted_p2 p1_2
         ->  Materialize
               ->  Merge Append
                     Sort Key: p2.payload
                     ->  Index Scan using parted_p1_payload_idx on parted_p1 p2_1
                     ->  Index Scan using parted_p2_payload_idx on parted_p2 p2_2
*/

Планы запросов выглядят оптимально: в зависимости от лимита будет выбрано только минимально необходимое число строк, поскольку имея индекс по атрибуту соединения мы уже имеем упорядоченный доступ к данным. А теперь спровоцируем сложное поддерево под аппендом, путём включения Partitionwise Join:

SET enable_partitionwise_join = 'true';
EXPLAIN (COSTS OFF)
SELECT * FROM parted p1 JOIN parted p2 USING (payload) LIMIT 100;
/*
 Limit
   ->  Append
         ->  Nested Loop
               Join Filter: (p1_1.payload = p2_1.payload)
               ->  Seq Scan on parted_p1 p1_1
               ->  Materialize
                     ->  Seq Scan on parted_p1 p2_1
         ->  Nested Loop
               Join Filter: (p1_2.payload = p2_2.payload)
               ->  Seq Scan on parted_p2 p1_2
               ->  Materialize
                     ->  Seq Scan on parted_p2 p2_2
*/

При том, что ничего не изменилось в данных, мы видим, что выбран неудачный план. Причина такой деградации в том, что при планировании Append'a, оптимизатор выбирает самый дешёвый по критерию startup_cost план. А им является тот, который содержит NestLoop + SeqScan - с точки зрения скорости запуска такого плана, при отсутствии необходимости сканировать таблицы совсем, такой план немного выигрывает даже у очевидного NestLoop + IndexScan.

Так работает текущий Postgres, включая dev-ветку. Однако эта проблема исправляется достаточно просто, путём добавления соответствующей логики в код оптимизатора. Совместными с @billexpи @apyhalov усилиями мы подготовили патч, который можно найти на текущем коммитфесте , и который фиксит данную проблему. А в треде с его обсуждением можно найти ещё одно интересное наблюдение по поводу коррекции startup_cost оператора последовательного сканирования, имплементация которого также может облегчить ситуацию с выбором неоптимальных fractional paths для случая с LIMIT 1.

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

 Limit
   ->  Append
         ->  Nested Loop
               ->  Seq Scan on parted_p1 p1_1
               ->  Memoize
                     Cache Key: p1_1.payload
                     Cache Mode: logical
                     ->  Index Scan using parted_p1_payload_idx on parted_p1 p2_1
                           Index Cond: (payload = p1_1.payload)
         ->  Nested Loop
               ->  Seq Scan on parted_p2 p1_2
               ->  Memoize
                     Cache Key: p1_2.payload
                     Cache Mode: logical
                     ->  Index Scan using parted_p2_payload_idx on parted_p2 p2_2
                           Index Cond: (payload = p1_2.payload)

А вот следующая проблема уже не имеет простого решения в настоящий момент.

Проблема вычисляемого лимита

Рассмотрим следующий запрос:

EXPLAIN (COSTS OFF)
SELECT * FROM parted p1 JOIN parted p2 USING (payload,y)
ORDER BY payload,y LIMIT 100;

Запустив его с нашим патчем вы получите хороший план - будет использован NestLoop с параметризованным сканированием по индексу, который вернет только минимально необходимое количество строк. Однако путем простого уменьшения лимита мы получим изначальную унылую картину:

EXPLAIN (COSTS OFF)
SELECT * FROM parted p1 JOIN parted p2 USING (payload,y)
ORDER BY payload,y LIMIT 1;

/*
Limit
   ->  Merge Append
         Sort Key: p1.payload, p1.y
         ->  Merge Join
               Merge Cond: ((p1_1.payload = p2_1.payload) AND (p1_1.y = p2_1.y))
               ->  Sort
                     Sort Key: p1_1.payload, p1_1.y
                     ->  Seq Scan on parted_p1 p1_1
               ->  Sort
                     Sort Key: p2_1.payload, p2_1.y
                     ->  Seq Scan on parted_p1 p2_1
         ->  Merge Join
               Merge Cond: ((p1_2.payload = p2_2.payload) AND (p1_2.y = p2_2.y))
               ->  Sort
                     Sort Key: p1_2.payload, p1_2.y
                     ->  Seq Scan on parted_p2 p1_2
               ->  Sort
                     Sort Key: p2_2.payload, p2_2.y
                     ->  Seq Scan on parted_p2 p2_2
*/

Снова SeqScan, чтение всех строк из таблиц и запрос становится в десятки раз медлительнее, хотя мы только уменьшили лимит! При этом, отключив SeqScan мы снова можем увидеть быстрый план и использование инкрементальной сортировки.

Фундаментальная проблема здесь в том, что оптимизатор знает только цифру итогового лимита на количество строк в запросе/подзапросе. В нашем случае, когда IncrementalSort должен будет досортировать поступающие данные, при планировании оператора Append оптимизатор не может предположить, сколько данных потребуется: в результате может потребоваться только одна строка, так и все строки из каждой партиции - в зависимости от распределения данных в столбце у.

Даже представив теоретически, что мы научим IncrementalSort вычислять количество групп по столбцу payload и, на основании этого оценивать максимально потребное количество строк в каждой партиции, мы не можем улучшить план, поскольку планирование оператора Append уже завершено, возможные варианты его исполнения уже зафиксированы - мы ведь планируем запрос снизу-вверх!

Подводя итог. Партиционированные таблицы таки сильно усложняют задачу для текущей версии Postgres, ограничивая пространство поиска оптимальных планов запросов и процесс перехода на них следует тщательно тестировать, делая упор на кейсы, где требуется некоторая лимитированная выборка данных из таблиц и нет очевидного прунинга партиций на этапе планирования. И хотя направление активно развивается, можно ожидать улучшений ситуации в ближайшем будущем (особенно, если пользователи будут активнее репортить возникающие проблемы), но существуют кейсы, где решение в рамках существующей архитектуры не очевидно и требует дополнительного R&D.

Согласны вы с моими выводами, или я только что ерунду написал? Пожалуйста, оставьте ваше мнение в комментариях.

THE END.

9 Декабря 2024, Паттайя, Тайланд.