Вспомним главную страницу типичного интернет-магазина, например WB. Лично у меня на этой странице отображена реклама нескольких товаров:
Аэрогриль
Магний Цитрат + Б6
Протеиновые брауни
и т.д.
Думая как разработчик баз данных, я примерно представляю себе, что эта страница построена по результатам выполнения запроса вида:
SELECT name, description FROM products p LEFT JOIN kitchen_appliances ka ON (p.id = ka.id) LEFT JOIN pharmacy f ON (p.id = f.id) LEFT JOIN sportish_food sf ON (p.id = f.id) ... ORDER BY p.popularity DESC LIMIT N
Эффективно спланировать такой запрос непросто, что (по моему опыту) подтверждают репорты пользователей из мира 1С - ведь Postgres небогат сейчас на оптимизации LEFT JOIN. В то же время особенности паттерна позволяют придумать различные методики, повышающие эффективность его выполнения. Несколько очевидных приёмов оптимизации этого шаблона удалось реализовать и, спасибо ТанторЛабс, опробовать на реалистичных тестовых нагрузках. Однако для начала я хочу разобраться с вопросом, что такое есть полиморфные ссылки, откуда они берутся и насколько общим местом являются. Именно этот пробел я и постараюсь закрыть данной публикацией.
Паттерн
Строка заказа может ссылаться на физический товар, цифровую загрузку, подарочный сертификат или подписку. Запись о действии в CRM-системе может быть связана с контактом, компанией или сделкой. Запись журнала аудита может относиться к любой сущности в системе.
В реляционных схемах нет встроенного механизма для подобных ссылок. Наиболее распространённый способ кодирования использует дискриминированный внешний ключ — пару столбцов, которые совместно идентифицируют вспомогательную таблицу и строку в ней:
CREATE TABLE order_lines ( id SERIAL PRIMARY KEY, order_id INTEGER NOT NULL REFERENCES orders(id), item_type VARCHAR(20) NOT NULL, -- discriminator item_id INTEGER NOT NULL, -- polymorphic FK quantity INTEGER NOT NULL );
Здесь item_type может содержать значения 'product', 'gift_card' или 'subscription', а item_id хранит первичный ключ соответствующей таблицы. Внешний ключ не обеспечивает ссылочную целостность сразу для всех трёх вспомогательных таблиц, поэтому ядро СУБД трактует item_id как обычный целочисленный столбец.
Для разрешения ссылки — например, для получения читаемого имени того элемента, который был заказан, — запрос должен выполнить соединение базовой таблицы (здесь - order_lines) с каждой из возможных вспомогательных таблиц, ограниченное дискриминатором:
SELECT ol.id, COALESCE(p.name, g.name, s.name) AS item_name FROM order_lines ol LEFT JOIN products p ON ol.item_type = 'product' AND ol.item_id = p.id LEFT JOIN gift_cards g ON ol.item_type = 'gift_card' AND ol.item_id = g.id LEFT JOIN subscriptions s ON ol.item_type = 'subscription' AND ol.item_id = s.id;
Для каждой строки order_lines не более чем одно из трёх левых внешних соединений находит совпадение; остальные два возвращают NULL. По мере роста числа типов вспомогательных таблиц растёт и дерево LEFT JOIN-ов. Данная форма запроса далее именуется паттерном разрешения полиморфных ссылок.
Структурные инварианты
Рассматриваемый паттерн обладает жёсткой структурой, отличающей его от произвольного набора OUTER JOIN'ов:
Взаимное исключение. Предикаты дискриминатора в JOIN clause попарно дизъюнктны: для любой строки базовой таблицы предикат дискриминатора не более чем одного оператора JOIN принимает значение «истина». В приведённом примере предикаты
item_type = 'product',item_type = 'gift_card'иitem_type = 'subscription'не могут одновременно быть истинными для одной строки. Это гарантирует, что для каждой строки базовой таблицы совпадение даёт не более чем один LEFT JOIN. Следует отметить, что если значение дискриминатора строки не сопоставляется никакой из таблиц (например,item_type = 'coupon') или дискриминатор равен NULL, то ни один LEFT JOIN заведомо не сматчит строки. Инвариант формулируется как «не более одного», а не «ровно одно».Уникальность ключа внутренней стороны. Ключ соединения на стороне каждой вспомогательной таблицы является её первичным ключом. В сочетании со взаимным исключением данное свойство гарантирует, что каждое левое внешнее соединение порождает не более одного совпадения на строку базовой таблицы, и, следовательно, ни одно соединение не дублирует строки.
Ограничение на использование столбцов. Каждое обращение к столбцу вспомогательной таблицы T_i — в списке SELECT находится внутри выражения COALESCE или CASE, которое принимает значение NULL, если дискриминатор не соответствует T_i. Ни один столбец вспомогательной таблицы не используется вне такой обёртки. Более того, такое выражение должно содержать столбцы от каждой вспомогательной таблицы, участвующей в левом внешнем соединении в данном запросе: если COALESCE включает
p.nameиg.name, он должен включать иs.name— за исключением случая, когда соединение с подписками вообще не вносит столбца в данное свёртывающее выражение. Это требование полноты обеспечивает, что удаление несовпадающего соединения не изменяет результат свёртывающего выражения ни для одной строки базовой таблицы.
Таким образом, при выполнении инвариантов 1–3 для подмножества строк базовой таблицы, отфильтрованного условием discriminator = c_k (соответствующего таблице T_k), LEFT JOIN со всеми прочими вспомогательными таблицами могут быть безопасно удалены из плана.
Данное утверждение относится к случаю простого SELECT. Когда запрос полиморфного разрешения встроен в более крупный запрос с GROUP BY или агрегатными функциями, взаимодействие между устранением соединений и семантикой агрегатов требует дополнительного анализа.
Области применения паттерна
Рассматриваемый паттерн широко распространён в различных прикладных областях и фреймворках. Он встречается в двух различных формах, которые совпадают по структуре на уровне запроса, но различаются на уровне свойств схемы.
Полиморфные ассоциации (без ссылочной целостности). Фреймворк Ruby on Rails популяризировал термин «полиморфная ассоциация», реализуемую как пара столбцов type / id в ссылающейся таблице Ruby on Rails Guides. Объявление внешнего ключа невозможно, поскольку вспомогательная таблица различается для каждой строки. Когда запросу необходимо разрешить ссылку, ORM генерирует LEFT JOIN-ы, ограниченные дискриминатором, ко всем таблицам-кандидатам. Библиотека Django django-polymorphic использует тот же подход и документирует порождаемые им накладные расходы на количество запросов. Документация GitLab не рекомендует эту форму, ссылаясь на потерю ссылочной целостности и деградацию производительности запросов, наблюдаемую в промышленной среде.
Наследование таблиц через соединение (со ссылочной целостностью). Стратегия @Inheritance(strategy = JOINED) в Hibernate размещает каждый подкласс в отдельной таблице, первичный ключ которой является одновременно внешним ключом к родительской таблице. Дискриминатор хранится в родительской таблице. При загрузке базовой сущности Hibernate генерирует LEFT OUTER JOIN-ы ко всем таблицам подклассов в иерархии. В обсуждениях на форуме сообщества Hibernate документируются случаи генерации запросов с 30–40 LEFT OUTER JOIN-ами для иерархий умеренной глубины. Подробный анализ стратегий наследования Hibernate, включая JOINED-стратегию и порождаемую ею проблему множественных соединений, приведён также здесь. Мультитабличное наследование Django вероятно порождает аналогичную структуру. В отличие от формы с полиморфными ассоциациями, наследование через соединение предусматривает ограничения ссылочной целостности между родительской и дочерними таблицами, однако форма запроса разрешения остаётся идентичной.
Механизм наследования таблиц PostgreSQL (INHERITS) представляет собой частичное решение той же проблемы на уровне схемы: запросы к родительской таблице автоматически включают строки из дочерних таблиц без необходимости явных соединений. Однако INHERITS имеет существенные ограничения — механизм не обеспечивает ограничения внешнего ключа на дочерних таблицах, не распространяет уникальные ограничения на всю иерархию и плохо взаимодействует с некоторыми оптимизациями планировщика, — что ограничивает его применимость для данного сценария.
CRM-платформы. Salesforce предоставляет полиморфные поля поиска (WhoId, WhatId) для объекта Activity. Одно поле WhatId может ссылаться на Account, Opportunity, Campaign или любой из десятков пользовательских объектов. Salesforce предлагает оператор TYPEOF в SOQL специально для обработки полиморфного разрешения без необходимости явных соединений для каждого целевого типа.
Свидетельства проблем эффективности в промышленных системах
Количественные эталонные тесты, изолирующие накладные расходы паттерна полиморфного разрешения, в рецензируемой литературе встречаются редко. Вместе с тем сообщества разработчиков и документация фреймворков предоставляют косвенные свидетельства того, что проблема реальна.
Тому свидетельство обсуждения на форуме сообщества Hibernate, где разработчики сообщают, что загрузка одной сущности из иерархии с JOINED-наследованием порождает запросы с десятками LEFT OUTER JOIN-ов и что эти запросы доминируют во времени отклика при нагрузках с преобладанием чтения. Документация django-polymorphic посвящает отдельный раздел вопросам производительности, рекомендуя разработчикам использовать .non_polymorphic(), когда конкретный тип не требуется. Запрет GitLab на полиморфные ассоциации прямо мотивирован деградацией производительности запросов, наблюдаемой в промышленной среде.
Смежный корпус работ устанавливает, что запросы с множественными соединениями по своей природе подвержены деградации качества планов. Лейс и др. показали, что ошибки оценки кардинальности накапливаются мультипликативно при прохождении через цепочку соединений, нередко достигая нескольких порядков величины даже на хорошо проанализированных таблицах. Паттерн полиморфного разрешения с его N внешними соединениями очевидно подвержен такому накоплению ошибок.
Исходя из простой логики, влияние полиморфного паттерна на производительность должно быть наиболее выражено при одновременном выполнении трёх условий: число целевых типов N велико (более 8–10, а в реалиях PostgreSQL — более join_collapse_limit), базовая таблица велика (миллионы строк), и запрос является интенсивно читающим с требованиями к времени отклика. В таких случаях даже параметризованные Nested Loop генерируют значительный объём ввода-вывода: каждая безрезультатная проба обходит дерево соединений до листовой страницы, выполняет сравнение, завершающееся неудачей, и возвращается. Умножая на N−1 безрезультатных проб на строку и миллионы строк, совокупные затраты доминируют во времени выполнения запроса.
Альтернативы на уровне схемы
В литературе по базам данных предложен ряд стратегий моделирования иерархий типов, позволяющих избежать дискриминированного внешнего ключа. Фаулер каталогизировал три практически ориентированных паттерна: Class Table Inheritance (общая родительская таблица с таблицами подтипов, первичные ключи которых являются внешними ключами к родительской), Single Table Inheritance (все подтипы свёрнуты в одну широкую таблицу) и Concrete Table Inheritance (полностью независимые таблицы для каждого подтипа, требующие UNION ALL для полиморфных запросов).
Карвин посвятил отдельную главу книги SQL Antipatterns дискриминированному внешнему ключу под названием «Polymorphic Associations», утверждая, что данный подход жертвует ссылочной целостностью и производительностью запросов ради простоты схемы. В качестве предпочтительной альтернативы он рекомендует подход Class Table Inheritance, который называет «Common Super-Table».
Несмотря на существование альтернатив, дискриминированный внешний ключ вероятно остаётся доминирующим на практике (оставьте коммент ниже, если у вас иной опыт). ORM-фреймворки генерируют его по умолчанию, а ретроактивные изменения схемы в крупных промышленных системах непомерно дороги.
Взаимодействие с подзапросами EXISTS
На практике запрос часто включает подзапрос EXISTS или IN, фильтрующий базовую таблицу, — например, ограничивающий строки заказа заказами, размещёнными в определённом диапазоне дат или принадлежащими конкретному клиенту:
SELECT ol.id, COALESCE(p.name, g.name, s.name) AS item_name FROM order_lines ol LEFT JOIN products p ON ol.item_type = 'product' AND ol.item_id = p.id LEFT JOIN gift_cards g ON ol.item_type = 'gift_card' AND ol.item_id = g.id LEFT JOIN subscriptions s ON ol.item_type = 'subscription' 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' );
Подзапрос EXISTS в этом примере ссылается только на столбцы базовой таблицы — распространённый на практике случай, удобный для приёма оптимизации под названием "pull-up". Подзапрос, ссылающийся на столбцы вспомогательных таблиц, подчинялся бы иным, гораздо более сложным, правилам pull-up и здесь не рассматривается. Способ обработки планировщиком подзапроса EXISTS, относящегося только к базовой таблице, существенно влияет на производительность, причём результат зависит от того, преобразуется ли подзапрос в полусоединение, а также от настроек join_collapse_limit и from_collapse_limit.
Случай 1: EXISTS сохраняется в дереве плана как SubPlan. Когда планировщик не преобразует EXISTS в SEMI JOIN — например, потому что подзапрос содержит конструкции, препятствующие pull-up, — подзапрос обычно используется в качестве фильтра на уровне сканирования базовой таблицы, поскольку обязательное правило оптимизатора — проталкивать фильтр на минимальный уровень, где он может быть вычислен и применён. Каждая строка order_lines проверяется на соответствие SubPlan до попадания в дерево соединений. Строки, не прошедшие проверку EXISTS, отбрасываются немедленно, так что до N LEFT JOIN-ов доходят только прошедшие фильтрацию строки. Здесь имеет место баланс: фильтр базовой таблицы сокращает выборку на ранней стадии, но вычисляется на каждую строку.
Случай 2: EXISTS преобразуется в полусоединение. Оптимизатор PostgreSQL умеет преобразовывать простой подзапрос EXISTS в SEMI JOIN - см. нехитрую картинку ниже для иллюстрации.
После преобразования дерева запроса с помощью pull-up, отношение orders становится одним из базовых отношений, которые планировщик рассматривает при переборе порядков соединения . Планировщик вправе рассматривать все допустимые порядки соединений с учётом ограничений порядка, записанных в структурах SpecialJoinInfo для каждого внешнего и полусоединения. Поскольку предложение полусоединения ссылается только на столбцы order_lines, а LEFT JOIN-ы также требуют order_lines на внешней стороне, планировщик в принципе может разместить полусоединение рано — выполнив соединение orders с order_lines до любого из LEFT JOIN-ов. При точных оценках селективности планировщик, как правило, выбирает именно такое раннее размещение, и эффект фильтрации сохраняется. Риск в данном случае состоит не в структурной невозможности переупорядочения, а в том, что неточные оценки кардинальности (накапливающиеся по цепочке N соединений, как обсуждалось ранее) могут привести планировщик к выбору неоптимального порядка, при котором полусоединение размещается позднее оптимального.
Случай 3: превышение join_collapse_limit. Запрос содержит N отношений. Добавление таблицы orders увеличивает это число. Если оно превышает join_collapse_limit (по умолчанию 8 в PostgreSQL), планировщик делит задачу поиска оптимального порядка JOIN'ов на непересекающиеся подзадачи. Практически это означает, что он сохраняет синтаксическую вложенность JOIN из парсера. Ограничение существует потому, что количество порядков соединения растёт сверхэкспоненциально с числом отношений, что делает исчерпывающий поиск непрактичным при умеренно большом числе таблиц. LEFT JOIN-ы формируют левоглубокое дерево JoinExpr, которое планировщик обрабатывает как единый блок, выполняя соединения в их синтаксическом порядке. SEMI JOIN, добавленный pull-up'ом на верхний уровень такого дерева, оказывается вне задачи поиска, включающей базовую таблицу и возможность непосредственного джойна подзапроса с базовой таблицей не будет рассматриваться в принципе. Для больших базовых таблиц с селективным предикатом EXISTS и трудоёмкими LEFT JOIN это может ухудшить производительность на порядки по сравнению со случаем 1.
Особенно сильно это можно почувствовать при апгрейде, когда новый вид pull-up'а блокирует возможность быстро фильтровать строки базовой таблицы и приводит к заметной деградации запроса, которую можно преодолеть только его переписыванием.
Итого
Как оказалось, паттерн запроса чертовски распространённый. И нет смысла блеймить 1С за чрезмерную сложность - таковы предметная область и возможности реляционной модели. С точки зрения производительности, он будет более-менее эффективно выполняться при наличии правильно подобранных индексов (особенно на базовой таблице) и станет немедленно тормозить, если фильтр запроса по базовой таблице не покрывается одним из индексов. Так что придётся работать над оптимизацией и, в дальнейшем я постараюсь описать набор хаков для постгрессового оптимизатора, адресованные этому паттерну.
А что вы думаете об этом шаблоне? Согласны ли с данным анализом?
THE END.
18 мая 2026, Мадрид, Испания.
