Кейс

Недавно я изучал вопрос, насколько распространены полиморфные ссылки в реляционных базах — болезненном для производительности паттерне с дискриминированным внешним ключом, который автоматически генерируют ORM-фреймворки (Rails, Django, Hibernate), CRM-платформы (Salesforce) и многие 1С-конфигурации. Главная страница типичного интернет-магазина или activity-лента CRM-системы строится именно таким запросом: базовая таблица соединяется LEFT JOIN-ами со всеми возможными подтипами через пару столбцов (type, id).

Та статья отвечала на вопрос «насколько распространён подобный паттерн». Ведь если заниматься улучшением, то неплохо понимать, насколько оно полезно, не так ли? Здесь я пытаюсь дать представление о том, каким образом данный шаблон приводит к регрессии производительности и показать направления улучшения оптимизатора PostgreSQL, позволяющие облегчить ситуацию.

Спойлер: пока немного — но кое-что движется на pgsql-hackers. Три патча, обсуждавшихся в 2024–2026 годах, нацелены на три разных источника регрессии. Ниже о каждом.

SELECT
    ol.id,
    COALESCE(p.name, g.name, s.name) AS item_name
FROM order_lines ol
  LEFT JOIN products p
    ON ol.dtype = 'A' AND ol.item_id = p.id
  LEFT JOIN gift_cards g
    ON ol.dtype = 'B' AND ol.item_id = g.id
  LEFT JOIN subscriptions s
    ON ol.dtype = 'C' AND ol.item_id = s.id
WHERE EXISTS (
  SELECT 1 FROM orders o
  WHERE o.id = ol.order_id AND o.placed_at >= 2024/01/01)
ORDER BY ol.popularity
LIMIT 100

Источники проблем

В настоящий момент оптимизатор Postgres реализует весьма примитивную логику . На примере таблицы order_lines из предыдущей статьи для каждой строки базовой таблицы запрос обращается к каждой из N таблиц-подтипов через LEFT JOIN. Только одно из этих соединений возвращает совпадение — то, чей дискриминатор соответствует значению item_type в данной строке. Остальные N−1 соединений гарантированно безрезультатны: их ON-предикат содержит другое значение дискриминатора (см схему ниже).

Планировщик выбирает один порядок сканирования inner side LEFT JOIN’a и применяет его ко всем строкам — он не умеет маршрутизировать каждую outer-строку к соответствующей inner-таблице на основе значения дискриминатора. Базовая стоимость паттерна — O(M × N) проб, из которых только O(M) полезны. Более того, это и в принципе невозможно: нет такого constraint, который бы гарантировал непересекающиеся значения ключа в inner-таблицах.

После некоторого размышления, я вывел для себя следующие основные причины деградации производительности запросов:

1. Размер базовой таблицы. Удвоение количества строк в базовой таблице удваивает число безрезультатных проб inner-side JOIN'a.

2. Агрегация (обычно ORDER BY + LIMIT) результата запроса. Сортировка часто блокирует пайплайн, и оператор LIMIT не может ограничить выборку и сократить сканирование join tree.

3. EXISTS-подзапрос, который планировщик трансформирует (pull-up) в джойн. При превышении количества таблиц в join tree величины join_collapse_limit полученный SEMI JOIN выпадает из задачи поиска порядка соединения и перемещается в другую задачу. Это приводит к тому, что изначально служащий как фильтр строк сканирования базовой таблицы, данный EXISTS уходит наверх и будет фильтровать строки базовой таблицы сильно позже.

4. Накопление погрешности оценки кардинальности. С увеличением количества джойнов эстимация быстро уходит в минимальное значение и не меняется выше по дереву плана. Для нашего каскада LEFT JOINs это не очень актуально, но всё же.

Разберём пути решения проблемы.

1. Result Filter и одностороннее ограничение

Необходимость посмотреть в в inner каждого джойна для каждой строки из outer-таблицы остаётся - нет пока такого constraint в базе, который бы гарантировал, что если нашлась строка для данного item_id в таблице gift_cards, то такой записи точно не будет в таблице subscriptions. Однако, если join clause имеет вид:

ON ol.item_type = ‘subscription’ AND ol.item_id = s.id

то можно ограничить накладые расходы на сканирование inner'a, выполняя проверку условия на ol.item_type: если оно даёт false, то обращаться в inner нет смысла, поскольку строка inner'a всё-равно будет заменена на набор NULL-значений. Получаем что-то вроде следующей схемы плана запроса:

И тогда join tree плана нашего запроса будет выглядеть как-то так:

В декабре 2024 года на pgsql-hackers возникло обсуждение под заголовком «Do not scan index in right table if condition for left join evaluates to false using columns in left table». Том Лейн предложил разделить условия JOIN ... ON ... на две группы — зависящие только от внешней (левой) стороны и зависящие от внутренней (правой). Условия первой группы можно оценить ДО запуска сканирования внутренней стороны NestLoop-а: если они уже ложны, сканирование можно пропустить целиком.

Для нашего паттерна это попадает в самое больное место:

LEFT JOIN gift_cards g
  ON ol.item_type = 'gift_card'
 AND ol.item_id   = g.id

Первое условие — ol.item_type = 'gift_card' — зависит только от ol. Если для текущей строки ol.item_type = 'product', то весь JOIN заведомо вернёт NULL, и сканирование gift_cards бессмысленно.

Андрес Фрейнд предложил элегантную реализацию: не нужна новая машинерия в исполнителе. Существующий Result-узел плана уже умеет оценивать one-time qual — условие, оцениваемое один раз на каждый верхний кортеж. Условие на внешнюю сторону переносится в Result над сканированием внутренней:

В обычном случае внутреннее сканирование запускается, как и раньше. Но когда ol.item_type для текущей строки не соответствует дискриминатору данного JOIN-а, Result возвращает пустое множество, и сканирование не выполняется.

Эффект для полиморфного паттерна: число проб внутренней стороны падает с M × N до M (одна на строку — той, у которой дискриминатор совпадает). Безрезультатные пробы исчезают.

Что не покрыто:

• Условие должно быть полностью на внешней стороне. Условия, ссылающиеся на колонки внутренней таблицы помимо ключа JOIN, не могут быть проверены до сканирования.

• Для случая, когда внутренняя сторона не индексирована (например, Seq Scan), выигрыш ещё больше — но и потенциальная сложность реализации тоже.

Статус: обсуждение продолжается; патч в коммитфесте пока не зарегистрирован (на момент написания этой статьи).