Различные СУБД предлагают широкий набор разновидностей операторов JOIN для таблиц. Если Вам встретилась проблема с производительностью CROSS JOIN, - например, декартово произведение таблицы с миллионом записей самой на себя, - добро пожаловать, в этой статье перечислены простейшие способы избавиться от CROSS JOIN.
Конечно, можно пересмотреть и упростить саму бизнес-логику или способы расчетов, в данной статье рассмотрены некоторые базовые случаи, про которые не стоит забывать и имеет смысл проверять первыми. Надеюсь, они окажутся релевантными или смогут помочь найти другие SQL оптимизации.
Примеры в статье рассматриваются на основе CROSS JOIN из ClickHouse. Текущая версия ClickHouse не оптимизирует CROSS JOIN автоматически. Также стоит отметить, что поскольку часто SQL запросы не пишутся вручную, а, например, собираются по частям программно, то перечисленные далее случаи вполне реальны.
CROSS JOIN с таблицей, все поля которой далее не используются
Этот случай состоит в том, что одна из таблиц из CROSS JOIN далее не используется. Пример SQL для данного случая с объединением таблицы самой на себя следующий:
SELECT T_1.a1, T_1.a1 FROM T AS T_1 CROSS JOIN T AS T_2;
ClickHouse не оптимизирует этот CROSS JOIN, поэтому могут быть проблемы с производительностью "на ровном месте". Все SQL примеры доступны в playground.
Таким образом, прежде, чем рассматривать сложные оптимизации SQL для CROSS JOIN, имеет смысл сделать простейшую проверку, что поля обеих таблиц из CROSS JOIN выбираются и далее используются, в противном случае, если поля T_2 не используются, то можно избавиться от T_2 и CROSS JOIN соответственно:
SELECT a1, a1 FROM T;
Нужно учесть, что CROSS JOIN добавляет дубликаты (этим и отличается SQL от реляционой алгебры, т.е. SQL осонван на мультимножествах, а не на множествах), т.е. два перечиленные выше SQL запроса возвращают одинаковые результаты с точностью до дубликатов (которые можно удалить с помощью GROUP BY).
Всё может показаться достаточно очевидным, тем не менее, можно привести доказательство на основе реляционной алгебры, что проекция декартового произведения
PROJECT (T TIMES T`) { A1, A2,..., Am }
равна T. Декартово произведение T c атрибутами A1, A2, ..., Am на то же отношение T` с теми же атрибутами A`1, A`2, ..., A`m:
T TIMES T`
представляет собой все кортежи (a1, a2, …, am, a`1, a`2, …, a`m), такие, что
(a1, a2, …, am) ∈ T,
(a`1, a`2, …, a`m) ∈ T`.
Берем проекцию:
PROJECT (T TIMES T`) { A1, A2, ..., Am }
представляет собой все кортежи (a1, a2, …, am), такие, что
(a1, a2, …, am) ∈ T,
(a`1, a`2, …, a`m) ∈ T`,
или, избавляясь от (a`1, a`2, …, a`m) ∈ T`, поскольку кортежи (a`1, a`2, …, a`m) не используются в условиях, получаем:
все кортежи (a1, a2, …, am), такие, что
(a1, a2, …, am) ∈ T.
Видно, что это соответствует T, что и требовалось доказать.
CROSS JOIN с дополнительными условиями в ON других JOIN
Рассмотрим пример SQL для трех объединений таблицы самой на себя, причем в последнем объединении LEFT SEMI JOIN используется условие, по сути, объединяющее все три таблицы:
SELECT T_1.a1, T_2.a1 FROM T AS T_1 CROSS JOIN T AS T_2 LEFT SEMI JOIN T AS T_3 ON T_1.a1 = T_3.a1 AND T_2.a1 = T_3.a1;
Эквивалентно:
SELECT T_1.a1, T_2.a1 FROM T AS T_1 INNER JOIN T AS T_2 ON T_1.a1 = T_2.a1;
Или
SELECT a1, a1 FROM T;
Этот случай также достаточно очевиден, тем не менее, с точки зрения реляционной алгебры можно привести следующее доказательство. Будем условно использовать LEFT SEMI JOIN далее в реляционной записи и считаем, что Ak, A`k, A``k - ключевые (уникальные) атрибуты и T, T` и T`` - одно и то же отношение T:
PROJECT (T TIMES T` LEFT SEMI JOIN T`` WHERE ak = a`k = a``k) { A1, A`1 },
запишем это в кортежах в виде:
(a1, a`1), таких, что
(a1, a2, …, am) ∈ T,
(a`1, a`2, …, a`m) ∈ T`,
(a``1, a``2, …, a``m) ∈ T``,
ak = a`k = a``k (условие ON по ключевому уникальному полю).
Из равенства ключевых полей и того, что T, T` и T`` - это одно и то же отношение T, следует и равенство соответствующих кортежей:
ak = a`k = a``k => (a1, a2, …, am) = (a`1, a`2, …, a`m) = (a``1, a``2, …, a``m).
В связи с этим, упрощаем условие для T`` и получаем, что проеция PROJECT (T TIMES T` LEFT SEMI JOIN T`` WHERE ak = a`k = a``k) { A1, A`1 } представляет собой кортежи:
(a1, a`1), такие, что
(a1, a2, …, am) ∈ T,
(a`1, a`2, …, a`m ) ∈ T`,
ak = a`k.
Или, упрощая для T`, получаем, что это будут кортежи
(a1, a1), такие, что
(a1, a2, …, am) ∈ T,
Как видно, это эквивалентно PROJECT T { A1, A`1 }, или, в терминах SQL, это SELECT a1, a1 FROM T;, что и требовалось доказать.
CROSS JOIN с дополнительными условиями в WHERE
Аналогичен предыдущему случаю, только дополнительные условия, объединяющие все 3 таблицы, помещаются в WHERE:
SELECT T_1.a1, T_2.a1 FROM T AS T_1 CROSS JOIN T AS T_2 LEFT SEMI JOIN T AS T_3 ON T_1.a1 = T_3.a1 WHERE T_1.a1 = T_2.a1;
Упрощая, получим:
SELECT T_1.a1, T_2.a1 FROM T AS T_1 INNER JOIN T AS T_2 ON T_1.a1 = T_2.a1;
и далее
SELECT a1, a1 FROM T;
Надеюсь, перечисленные способы оптимизации CROSS JOIN, несмотря на свою очевидность, могут быть полезны сами по себе, или как пища для размышлений и более сложных оптимизаций. Успехов в работе с SQL!
Если у Вас есть интересные кейсы SQL оптимизаций, было бы здорово обсудить их в комментариях.
Комментарии (13)
Tzimie
09.05.2024 05:14+4Однако приведенные примеры это какая то оптимизация сферического запроса в вакууме. То есть вы консультант, смотрите чужой продукт и видите такой запрос из трёх cross join таблицы самой с собой. Но в моем опыте только один раз я видел столь безумный ляп, и он не был связан с cross join
Если же внутри одной фирмы вы видите такой запрос, то просто ищите автора, и если он не на колесах то просто говорите: дружище, без обид, но SQL - это не твое
koanse Автор
09.05.2024 05:14Согласен, но и на практике при ручном написании запросов такие случаи тоже встречаются (хоть и в виде диких ляпов).
Эти случаи могут быть актуальными, когда SQL генерируется кодом (.NET, Java, Go и т.д.) для конкретного UI или отчета, т.е. не вручную. Во всех трех случаях для таблицы с 1 млн записей условно UI корректный (например, сводная таблица), или отчет условно корректный, т.е. их можно получить не за 1 млн × 1 млн операций, а за разумное число операций, условно 1 млн, но из-за CROSS JOIN получить отчет невозможно. Т.е. это больше для случаев, когда SQL генерируется не вручную и чинится тоже не вручную.
Рассмотренные случаи помогают что-то исправить в CROSS JOIN (удалить его) без значительного вмешательства в проект, такого, как:
ограничить число записей в запросе для одной или обеих таблиц в CROSS JOIN (например, LIMIT, LIMIT BY, topK в ClickHouse, или обычный GROUP BY - если возможно)
добавление паджинации для одной или обеих таблиц из запроса (если возможно)
условное упрощение сводной таблицы до таблицы размером 4 × 4 и выполнение 16 отдельных запросов для каждой ячейки (может быть актуально, например, для таблиц по кварталам или месяцам, при возможности можно выполнять запросы параллельно)
добавление или изменение фильтров для сводной таблицы
отказ от сводной таблицы как условно последнее средство, замена одного отчета несколькими и т.д., т.е. пересмотр бизнес-логики
Akina
09.05.2024 05:14+4SELECT T_1.a1, T_1.a1 FROM T AS T_1 CROSS JOIN T AS T_2;... если поля T_2 не используются, то можно избавиться от T_2 и CROSS JOIN соответственно
SELECT a1, a1 FROM T;В общем случае - НЕЛЬЗЯ. Первый запрос возвращает несколько копий каждой записи. А второй - только одну копию. То есть запросы неэквивалентны. Более того, из результата первого запроса можно воспроизвести результат второго, но не наоборот. То есть предлагаемое преобразование приводит к необратимому повреждению результата и безвозвратной утрате части содержащихся в нём (мета)данных.
два перечисленные выше SQL запроса возвращают одинаковые результаты с точностью до дубликатов (которые можно удалить с помощью GROUP BY).
Да нельзя их удалять, эти дубликаты! НЕЛЬЗЯ! Ничто не гарантирует, что само количество дубликатов в наборе записей на самом деле не является важной и значимой характеристикой результата. Которая будет использоваться в дальнейшем.
PS. И как по мне, вообще всё написанное - это совершенно не оптимизация. В случае алгебраических выражений это бы называли приведением, упрощением, или ещё каким термином, но уж точно не оптимизацией. Какой термин применять в случае СУБД правильно - как-то не припоминается.
koanse Автор
09.05.2024 05:14Согласен, что разные результаты для
SELECT T_1.a1, T_1.a1 FROM T AS T_1 CROSS JOIN T AS T_2;иSELECT a1, a1 FROM T;, пояснение "возвращают одинаковые результаты с точностью до дубликатов (которые можно удалить с помощью GROUP BY)" может выглядеть неоднозначно, в playground приведён примерSELECT T_1.a1, T_1.a1 FROM T AS T_1 CROSS JOIN T AS T_2 GROUP BY T_1.a1, T_1.a1;SELECT a1, a1 FROM T;Он корректен, если a1 - это ключевое уникальное поле, для произвольного a1 корректно только такое:
SELECT T_1.a1, T_1.a1 FROM T AS T_1 CROSS JOIN T AS T_2 GROUP BY T_1.a1, T_1.a1;SELECT a1, a1 FROM T GROUP BY a1, a1;Согласен, что с точки зрения SQL это можно назвать иначе, "оптимизация CROSS JOIN" - для упрощения, чтобы не писать условно "оптимизация производительности SQL запроса путём удаления CROSS JOIN и замены на эквивалентный SQL запрос с другими типами JOIN (или без них) и дополнительными ограничениями, который возвращает те же результаты запроса"
miksoft
09.05.2024 05:14+1"возвращают одинаковые результаты с точностью до дубликатов (которые можно удалить с помощью GROUP BY)"
Все случаи применения CROSS JOIN, которые я встречал, именно для того и нужны, чтобы произвести дубликаты. А в статье предлагается их просто выкинуть, потеряв их основной функционал. Это не оптимизация, это ерунда какая-то.
Я бы понял, если бы предложили замену без потери функционала. LATERAL VIEW хотя бы...
koanse Автор
09.05.2024 05:14Согласен, что для произвольного запроса убрать CROSS JOIN невозможно, но в статье рассматриваются три частных случая и есть условия их применимости, не предлагается выкинуть любой CROSS JOIN. Такое впечатление, что в комментарии не дубликаты имеются в виду, а декартово произведение, полный перебор. Три случая в статье относятся к особым видам запросов, где действительно можно убрать CROSS JOIN. Здесь я проиллюстрировал два запроса: первый попадает под один из описанных случаев, второй нет, и так и остаётся CROSS JOIN.
Кроме того, в реляционной алгебре нет дубликатов (т.к. идёт работа со множествами), но декартово произведение всё равно используется, т.е. декартово произведение без дубликатов (другого декартового произведения условно и нет в реляционной алгебре) и CROSS JOIN без дубликатов как минимум не лишены смысла, поэтому с учетом того, что проектов и кейсов много, и здесь наверно тоже какие-то частные случаи имеются в виду, и этот кейс не противоречит кейсам из статьи
CROSS JOIN, которые я встречал, именно для того и нужны, чтобы произвести дубликаты
mentin
А вот нет, этот переход уже не работает (практически во всех SQL диалектах, с реляционной алгеброй зависит от определений). Для LEFT работал бы, а для INNER не годится без дополнительного условия, оставлю вопрос - какого?
Tzimie
Проверка на NULL
mentin
Да!
koanse Автор
Согласен, забыл в том случае дополнить, что a1 в T даже должно быть уникальным, ненулевым, в общем, ключом, иначе совсем не получится JOIN по
ON T_1.a1 = T_2.a1;dyadyaSerezha
Ничего себе забыл, это в корне меняет все дело.