PostgreSQL 'VALUES -> ANY' transformation: должна ли СУБД делать работу за пользователя?
Недавно, на хабре вышла статья про один нюанс в оптимизаторе 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 проект поддерживать множество правил преобразования, которые бы позволяли устранять избыточность и сложность, которую пользователь привносит, стремясь сделать запрос читабельнее и понятнее. И самое главное -, а стоит ли?
Странное поведение планировщика запросов PostgreSQL
F.41. tablefunc — functions that return tables
Commit 9f13376. pull-up correlated subqueries
Commit a65724d. Propagate pathkeys from CTEs up to the outer query
