Оптимизация CROSS JOIN — первые шаги
Различные СУБД предлагают широкий набор разновидностей операторов 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!
