Почему COALESCE ломает план PostgreSQL и как научить планировщик считать его селективность?

melisssha39 минут назадОбъяснить с

Почему COALESCE ломает план PostgreSQL и как научить планировщик считать его селективность?

Уровень сложностиСреднийВремя на прочтение6 минОхват и читатели1.1KБлог компании Тантор ЛабсPostgreSQL*Системное администрирование*Базы данных*Один COALESCE в условии способен превратить быстрый Hash Join в мучительно долгий Nested Loop. Убрать оператор COALESCE — и оценка стоимости плана упадёт в десятки раз, а запрос отработает мнгновенно. В данных при этом не меняется ничего: та же колонка, та же статистика, та же селективность, просто без COALESCE планировщик её видит, а с ним – перестаёт видеть.

В этой статье обсудим, как один COALESCE в JOIN роняет план, почему PostgreSQL теряет на нём оценку, а также посмотрим на патч, который учит планировщик считать селективность COALESCE из имеющейся статистики.

Предыстория

Клиент жаловался на долгое закрытие месяца в 1С. По логам почти всё время съедали запросы. Планировщик упорно выбирал Nested Loop там, где напрашивался Hash Join. Идти через hash join получалось только с помощью SET enable_nestloop = off - но это временная затычка, так как глобально ломать nested loop на боевой базе нельзя.

Дело было в условии соединения. Ключи сравнивались через COALESCE(..., '\xff') – типичный для 1С приём "NULL-безопасного" сравнения:

... AND COALESCE(t.col, '\xff') = COALESCE(r.col, '\xff')Одна из таких колонок - высокоселективная (n_distinct ≈ -0.59, то есть около 60% значений уникальны), но её нет в индексе, по которому идёт nested loop. Из-за этого NL перебирал кучу строк и отбрасывал их фильтром. А hash join, который тут был бы дешёвым, планировщик оценивал абсурдно дорого: cost 21766 против cost 1330 у nested loop - и, естественно, выбирал nested loop.

Ключевой момент: стоит убрать COALESCE с этой одной колонки...

... AND t.col = r.col...и стоимость hash join падает с 21766 до 765. Планировщик тут же выбирает его сам, и запрос отрабатывает быстро. Данные, селективность, распределение – всё то же самое; изменилось лишь то, что теперь планировщик их видит, а сквозь COALESCE – нет.

Данных планировщику хватает — статистика по обеим колонкам собрана; вот только привязана она к колонкам, а не к выражению COALESCE(...). Не найдя статистики, планировщик берёт дефолт и промахивается.

Полминуты матчасти: eqsel и eqjoinsel

Прежде чем выбрать план, планировщик оценивает селективность каждого условия, т.е. какую долю строк оно пропустит. Ошибка в оценке – и выбирается заведомо плохой план: не тот порядок соединений, nested loop там, где напрашивается hash join, и запрос становится медленнее. Для равенства есть два штатных оценщика в src/backend/utils/adt/selfuncs.c:

• eqsel – restriction-селективность, условие вида expr = const или expr = expr в пределах одной таблицы;
• eqjoinsel – join-селективность, условие соединения двух отношений.Оба опираются на статистику из pg_statistic: список наиболее частых значений (MCV), гистограмму, stanullfrac (доля NULL), оценку числа уникальных значений (ndistinct). Когда статистика есть – оценки хорошие. Когда её нет – начинается самое интересное.

Слепое пятно: COALESCE

COALESCE(a, b, c) возвращает первый не-NULL аргумент. Планировщик не знает об этом выражении: examine_variable() не находит по нему статистики, get_variable_numdistinct() возвращает флаг isdefault, и оценщик сваливается в дефолт.

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

CREATE TABLE a (x1 int, x2 int, y int);CREATE TABLE b (w int);
INSERT INTO a (x1, x2, y)SELECT     CASE WHEN i % 3 = 0 THEN NULL ELSE i % 1000 END,
CASE WHEN i % 3 = 0
THEN i % 500
ELSE NULL END,
i % 200 FROM generate_series(1, 100000) i;
INSERT INTO b (w) SELECT i % 1000 FROM generate_series(1, 100000) i;

CREATE INDEX a_coalesce_x1x2_idx ON a (COALESCE(x1, x2));ANALYZE a, b;
EXPLAIN ANALYZESELECT * FROM a JOIN b ON COALESCE(COALESCE(a.x1, a.x2), a.y) = b.w;На неизменённом планировщике:

Hash Join (cost=... rows=66488333 ...) (actual ... rows=10000000 ...)
Hash Cond: (COALESCE(COALESCE(a.x1, a.x2), a.y) = b.w)Оценка – 66 млнстрок против фактических 10 млн. Ошибка более чем в шесть раз, и это на ровном месте: все нужные распределения у планировщика есть, он просто не умеет их сложить для COALESCE.

Идея: разложить COALESCE по веткам

COALESCE(l₁, …, l_M) возвращает первую ветку, которая не NULL. Значит, до ветки с номером i дело доходит только тогда, когда все ветки перед ней оказались NULL. Вероятность этого – просто произведение долей NULL у всех предыдущих:

P(дойти до i) = stanullfrac(l₁) · stanullfrac(l₂) · … · stanullfrac(l_{i-1})Теперь – равенство двух COALESCE. Левый оператор в итоге равен какому-то значению l_i, правый – какому-то r_j. Равенство распадается на сумму по всем парам: для каждой берём вероятность, что левое значение равено l_i, правое - r_j, и l_i = r_j:

sel(COALESCE(l₁..l_M) = COALESCE(r₁..r_N))
= Σ_{i,j} P(дойти до i) · P(дойти до j) · sel(l_i = r_j)Внутренняя sel(l_i = r_j) - это обычное равенство двух простых выражений, для которого у планировщика есть статистика. Дальше просто рекурсивно вызываем тот же eqsel/eqjoinsel.

Про допущение: мы считаем, что «дотянуться до i слева» и «дотянуться до j справа» — независимые события, и что распределение значений не зависит от того, что предыдущие значения оказались NULL. Это приближение. Но оно заметно лучше дефолта, а на простых случаях, когда значения вообще без NULL или это константа, даёт точный ответ.

Реализация

Весь код находится в selfuncs.c и подключается к штатным оценщикам одной точкой: в начале eqsel (restriction) и eqjoinsel (join) добавлен ранний вызов. Если хотя бы одна сторона равенства обёрнута в COALESCE, управление уходит в общую функцию разбора; если COALESCE в условии нет – всё идёт по-старому, накладных расходов ноль.

Дальше эта функция делает ровно то, что описано в идее выше:

• разбираетCOALESCEна ветки – снимает служебные обёртки приведения типов, выбрасывает заведомо-NULL константы и обрывает список на первой не-NULL константе (всё, что стоит после неё, недостижимо);
• взвешивает каждую ветку - вероятностью до неё «дотянуться», то есть произведением долей NULL у всех предыдущих веток; эти доли берутся прямо из stanullfrac в статистике колонок;
• суммирует по парам веток - для каждой пары спрашивает у обычного eqsel/eqjoinsel селективность простого равенства и умножает на веса обеих веток. Пару «константа = константа» считает сразу, вызвав оператор.Ключевой принцип – не гадать: если хотя бы у одной ветки нет статистики, функция выходит, и оценка остаётся ровно такой, какой была без патча. Патч либо уточняет оценку, либо не вмешивается вовсе.

Почему <> считается через =

Для <> PostgreSQL считает не "напрямую", а через равенство: sel(<>) = 1 − sel(=) − nullfrac. Здесь nullfrac - доля строк, на которых всё условие даёт NULL: оператор строгий, если хотя бы один операнд NULL, результат тоже NULL:

clause_nullfrac = 1 − (1 − left_nullfrac) · (1 − right_nullfrac)Пример: слева 20% NULL, справа 30% NULL. Обе стороны одновременно не NULL только на 0.8 · 0.7 = 56% строк. Значит, хотя бы одна сторона NULL на 1 − 0.56 = 44%. Это и есть clause_nullfrac.

Дальше все строки делятся на три исхода: равенство истинно (sel), равенство ложно, либо всё NULL. Отсюда:

clause_nullfrac = 1.0 - (1.0 - left_nullfrac) * (1.0 - right_nullfrac);
acc_selec = 1.0 - acc_selec - clause_nullfrac;Если колонка a без NULL, то COALESCE(a, 1) тождественно a, и оценки a <> 5 и COALESCE(a, 1) <> 5 обязаны совпадать. На ревью они расходились почти в 9 раз. Причина — ветка <> уходила в разложение COALESCE, но нигде не переводилась в оператор-негатор. Отсюда и появились параметр negate, get_negator и подсчёт side_nullfrac.

Хеш-джойн: размер бакета

Оценки селективности мало — для hash join планировщику нужна ещё оценка размера бакета (estimate_hash_bucket_stats). Если ключ хеширования — COALESCE, то ndistinct снова приходит дефолтным, и оценка бакета уезжает.

Здесь патч делает две вещи. Во-первых, выносит подсчёт частоты самого частого значения в отдельную функцию get_variable_mcv_freq. Во-вторых, добавляет hash_bucket_stats_coalesce_dispatch: когда ndistinct дефолтный, а ключ — COALESCE, оценка ndistinct и частоты MCV собирается из per-branch статистик, взвешенных теми же префиксными вероятностями, и масштабируется через rows/tuples.

Было и стало

Несколько условий с COALESCE под EXPLAIN ANALYZE — оценка планировщика без патча и с патчем против фактического числа строк:

УсловиеБылоСталоФактджойн по вложенному COALESCE66 586 6677 771 66310 000 000джойн, COALESCE(col, 0) с обеих сторон500 00055 635 71255 601 040фильтр COALESCE(col, 0) = 0, fallback совпадает507 4587 456фильтр COALESCE(col, 1) = 0, fallback не совпадает5020<> по колонке без NULL10 20089 97390 000Как видно из таблицы, без патча оценка ошибочна в разы, а с патчем почти совпадает с фактической.

Статус и ссылки

Патч проходит ревью в pgsql-hackers и заведён в коммитфест:

• обсуждение: [https://www.postgresql.org/message-id/flat/CAF=hKRBhFDzdSomCM5XGFzRBpEAmh-fQyt-6vb4Ji0pZs=--7A@mail.gmail.com]Если у вас так же есть боевые запросы, где COALESCE в условии соединения ломает план, - интересно увидеть их в комментариях

Егор Савельев, «Тантор Лабс»Теги:• тантор лабс
• postgresql
• coalesce
• планировщикХабы:• Блог компании Тантор Лабс
• PostgreSQL
• Системное администрирование
• Базы данных