Недавно, на хабре вышла статья про один нюанс в оптимизаторе PostgreSQL [1]. Будучи предельно технической и скучной по-определению, она триггернула интересную дискуссию в комментах и дала мне, как разработчику систем баз данных, возможность взглянуть на систему с точки зрения разработчика приложений. Это оказалось продуктивным для обеих сторон и привело к патчу и треду в сообществе. Данный пост - про ещё одну точку оптимизации - использование конструкции VALUES в выражениях SQL.

Здесь я также мимоходом хочу затронуть весьма глобальный вопрос: а должна ли open-source СУБД исправлять огрехи пользователя? Я имею в виду оптимизировать запрос ещё до начала поиска оптимального плана, устраняя само-соединения, подзапросы, упрощая выражения - всё то, чего можно добиться изменением приложения. Вопрос не праздный, поскольку в той же дискуссии [1] было указано, что стоимость планирования запроса в Oracle быстро растет при усложении текста запроса, что скорее всего вызвано, в том числе, большой номенклатурой правил оптимизации.

Итак, конструкция VALUES. Помимо команды INSERT, по не до конца понятной причине она часто встречается также в запросах на выборку в форме проверки на вхождение во множество:

SELECT * FROM a WHERE x IN (VALUES (1), (2),...);

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

CREATE EXTENSION tablefunc;

CREATE TABLE norm_test AS
  SELECT abs(r::integer) AS x, 'abc'||r AS payload
  FROM normal_rand(1000, 1., 10.) AS r;
CREATE INDEX ON norm_test (x);
ANALYZE norm_test;

здесь значение х в таблице norm_test имеет нормальное распределение с матожиданием 1 и стандартным отклонением 10 [2]. Значений не слишком много и все они попадут в MCV-статистику, так что для каждого отдельного значения можно будет точно рассчитать количество дубликатов, несмотря на неравномерность распределения. Также, чтобы упростить сканирование по таблице, мы естественным образом ввели индекс по данной колонке. А теперь выполним запрос:

EXPLAIN ANALYZE
SELECT * FROM norm_test WHERE x IN (VALUES (1), (29));

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

  Hash Semi Join  (cost=0.05..21.36 rows=62) (actual rows=85)
   Hash Cond: (norm_test.x = "*VALUES*".column1)
   ->  Seq Scan on norm_test  (rows=1000) (actual rows=1000)
   ->  Hash  (cost=0.03..0.03 rows=2) (actual rows=2)
         ->  Values Scan on "*VALUES*"  (rows=2) (actual rows=2)

Здесь и далее я слегка упрощаю эксплейн для наглядности.

Хм, последовательное сканирование всех туплов, когда нам было достаточно двух индексных сканирований? Давайте отключим HashJoin и посмотрим, что получиться:

SET enable_hashjoin = 'off';

 Nested Loop  (cost=4.43..25.25 rows=62) (actual rows=85)
   ->  Unique  (rows=2 width=4) (actual rows=2)
         ->  Sort  (rows=2) (actual rows=2)
               Sort Key: "*VALUES*".column1
               ->  Values Scan on "*VALUES*"  (rows=2) (actual rows=2)
   ->  Bitmap Heap Scan on norm_test  (rows=31) (actual rows=42)
         Recheck Cond: (x = "*VALUES*".column1)
         ->  Bitmap Index Scan on norm_test_x_idx  (rows=31) (actual rows=42)
               Index Cond: (x = "*VALUES*".column1)

Теперь видно, что Postgres выжал максимум: за один проход по множеству VALUES он для каждого значения выполняет сканирование индекса по таблице. Намного интересней предыдущего варианта. Однако не так просто, как при обычном сканировании индекса. К тому же, если посмотреть в эксплейн запроса внимательней, то можно заметить, что оптимизатор ошибается с предсказанием кардинальности джойна и сканирования по индексу. А что будет, если переписать запрос без VALUES:

EXPLAIN (ANALYZE, TIMING OFF)
SELECT * FROM norm_test WHERE x IN (1, 29);

/*
 Bitmap Heap Scan on norm_test  (cost=4.81..13.87 rows=85) (actual rows=85)
   Recheck Cond: (x = ANY ('{1,29}'::integer[]))
   Heap Blocks: exact=8
   ->  Bitmap Index Scan on norm_test_x_idx  (rows=85) (actual rows=85)
         Index Cond: (x = ANY ('{1,29}'::integer[]))
 */

Как можно увидеть, мы получили почти вдвое более дешевый план запроса, выполняемый сканированием индекса. При этом, имея возможность эстимировать каждое значение из множества и имея оба этих значения в MCV-статистике, Postgres точно предсказывает кардинальность результата этого сканирования.

Итак, не будучи большой проблемой сам по себе (всегда можно использовать HashJoin и захэшировать VALUES-значения в inner), использование VALUES-последовательностей таит в себе опасности:

• оптимизатор может использовать NestLoop и при большом размере списка VALUES может снизить производительность;

• может быть выбран SeqScan в случае, когда более оптимальным было бы сканирование по индексу;

• оптимизатор даёт большие погрешности при оценке кардинальности операции JOIN и нижележащих операций.

А зачем вообще кому то требуется использовать такие выражения?

Моя догадка - здесь имеет место частный случай, когда система автоматизации - ORM или Rest API проверяет вхождение объекта в некое множество объектов. Поскольку VALUES описывает реляционную таблицу, а значение этого списка - это строка таблицы, то скорее всего мы имеем дело со случаем, когда каждая строка описывает экземпляр объекта в приложении, а наш случай - частная история, когда объект характеризуется только одним свойством. Если моя догадка неверна, прошу поправить в комментах - может кто-то знает иные причины?

Итак, конструкция 'x IN VALUES' - это опасно. Так почему бы не исправить ситуацию, преобразовав VALUES в массив? Тогда получим конструкцию вида 'x = ANY [...]', являющуюся в коде Postgres'a частным случаем операции ScalarArrayOpExpr. Она упростит дерево запроса, исключив появление ненужного джойн. Также, механизм оценки кардинальности Postgres умеет работать с операцией проверки вхождения в массив, и если массив достаточно небольшой (< 100 элементов), то выполнит статистическую оценку поэлементно. В дополнение, постгрес умеет оптимизировать поиск по массиву, хэшируя значения (если потребная для этого память попадёт в величину work_mem) - то есть всем хорошо, не так ли?

Что ж мы в лаборатории оптимизации Postgres Professional решили попробовать сделать это - и на удивление, оказалось достаточно тривиально.

Первая особенность с которой мы столкнулись - преобразование возможно только для операции над скалярной величиной: то есть нельзя в общем случае преобразовать выражение вида '(x,y) IN (VALUES (1,1), (2,2), ...)' так, чтобы результат в точности соответствовал состоянию до преобразования. Почему? Объяснить не очень просто - дело в особенности оператора сравнения для типа записи - чтобы научить постгрес работать с таким оператором полностью аналогично скалярным типам, нужно сильно переделать кэш типов.

Второе - нужно не забыть проверить данный подзапрос (да, VALUES представлен в query tree как подзапрос) на наличие volatile-функций - и всё! Любопытно, что преобразование возможно даже в случае, если внутри VALUES присутствуют параметры, вызовы функций и сложные выражения. Пример:

CREATE TEMP TABLE onek (ten int, two real, four real);
PREPARE test (int,numeric, text) AS
  SELECT ten FROM onek
  WHERE sin(two)*four/($3::real) IN (VALUES (sin($2)), (2), ($1));
EXPLAIN (COSTS OFF) EXECUTE test(1, 2, '3');

/*
                                                       QUERY PLAN                                                       
------------------------------------------------------------------------------------------------------------------------
 Seq Scan on onek
   Filter: (((sin((two)::double precision) * four) / '3'::real) = ANY ('{0.9092974268256817,2,1}'::double precision[]))
(2 rows)
*/

Сейчас фича проходит испытания. Учитывая, что зависимости от версии ядра минимальны - структура query tree достаточно стабильна, и нет причин модифицировать код, то она может использоваться в Postgres версии 10, а может быть даже и ранее.

А теперь собственно холивар, который я упоминал выше. Поскольку мы сделали это в виде внешней библиотеки, то потребовалось перехватить хук планнера (чтобы упростить query tree до начала оптимизации) и стоило нам дополнительного прохода по дереву запроса. Очевидно, что большинство запросов в системе не будут иметь необходимости в этом преобразовании, и данная операция будет попросту добавлять оверхед. Однако там, где она-таки сработает, она может дать (и по моим наблюдениям даёт) заметный эффект.

В сообществе PostgreSQL до недавнего времени существовало консенсусное решение: если проблему можно устранить путём изменения самого запроса, то не стоит усложнять код ядра, поскольку это неминуемо приведёт к повышению затрат на сопровождение и (помятуя об опыте Oracle) будет влиять на производительность самого оптимизатора.

Однако, наблюдая за коммитами ядра я замечаю, что кажется мнение сообщества потихоньку дрейфует. Например в этом году усложнили технологию разворачивания (pull-up) подзапросов в SEMI JOIN, добавив коррелированные подзапросы [3]. А чуть позднее - разрешили вышестоящему запросу получать сведения о порядке сортировки результата подзапроса [4], хотя ранее, в целях упрощения планирования, запрос и его подзапросы планировались независимо. Так мы и до перепланирования подзапросов дойдём, нет?

А что вы думаете: способен ли open-source проект поддерживать множество правил преобразования, которые бы позволяли устранять избыточность и сложность, которую пользователь привносит, стремясь сделать запрос читабельнее и понятнее. И самое главное - а стоит ли?

1. Странное поведение планировщика запросов PostgreSQL

2. F.41. tablefunc — functions that return tables

3. Commit 9f13376. pull-up correlated subqueries

4. Commit a65724d. Propagate pathkeys from CTEs up to the outer query