Декартово произведение и θ-соединения

Две предыдущие операции — σ и π — работают с одной таблицей. Но 99% реальных запросов соединяют несколько таблиц: «клиенты вместе с их заказами», «заказы вместе с позициями», «позиции вместе с товарами». Чтобы это сделать в реляционной алгебре, нужно сначала уметь склеивать два отношения. Эта склейка называется декартовым произведением — и оттуда выводятся все виды JOIN, которые есть в SQL.

Декартово произведение: ⨯

⨯ (произведение)

— это «комбинируй каждый с каждым». Если в первом отношении m кортежей, во втором n, в результате получится m·n кортежей. Схема результата — это все атрибуты обеих таблиц подряд (атрибуты с одинаковым именем приходится переименовывать).

$R_1 \times R_2 = \{ (t_1, t_2) \mid t_1 \in R_1, t_2 \in R_2 \}$

В SQL это CROSS JOIN. Посмотрим на маленьком примере:

Декартово произведение 3 клиентов на 3 категории — должно быть 9 кортежей:

PostgreSQL

Девять строк: каждый из трёх клиентов «встречается» с каждой из трёх категорий. На реальных таблицах декартово произведение взрывается катастрофически: 1000 заказов × 1000 товаров = миллион строк. Поэтому в чистом виде ⨯ используется редко — почти всегда сразу за ним идёт фильтр.

θ-соединение: ⨯ + σ

Теперь возьмём декартово произведение и тут же отфильтруем — оставим только «осмысленные» комбинации. Например, склеим клиентов с их заказами по условию customers.id = orders.customer_id.

θ-соединение

(theta join) — это и есть JOIN ... ON p в SQL. Формально:

$R_1 \bowtie_p R_2 = \sigma_p(R_1 \times R_2)$

Самая частая разновидность — когда предикат это равенство между атрибутами двух таблиц. Это называется

equi-join

(от англ. equality, равенство). Именно equi-join’ы СУБД умеют исполнять быстро — через hash join и merge join, о которых мы поговорим в модуле про индексы.

θ-соединение = ⨯ + σ

JOIN ON p — это просто sugar для двух операций алгебры подряд. PostgreSQL разворачивает его именно так.

customersm строк

ordersn строк

⨯m·n строк

σc.id = o.customer_id

результат≤ n строк

клиент + его заказы

Две одинаковые записи в SQL

Раз JOIN ON p ≡ σ_p(R₁ × R₂), значит, две следующие SQL-записи дают тот же результат:

Старый стиль: CROSS JOIN + WHERE — буквальный перевод алгебры

PostgreSQL

Современный стиль: явный INNER JOIN ... ON

PostgreSQL

Стандарт SQL рекомендует второй вариант — он явно выделяет соединение и его условие. Это лучше читается, и оптимизатору проще понять намерение. Старый стиль (FROM A, B WHERE ...) разрешён и сейчас, но в современном коде встречается редко.

Natural join: соединение по совпадающим именам

Если у двух таблиц есть атрибуты с одинаковыми именами, можно написать NATURAL JOIN — и СУБД автоматически возьмёт предикат равенства по всем общим атрибутам. Это очень красиво в учебниках, но опасно в проде: добавил кто-то одинаково названную колонку в обе таблицы — и логика твоего запроса молча поменялась.

В рамках курса мы знаем, что natural join существует, но никогда не пишем его — он не стоит риска.

Что становится «хвостом»

Inner join (INNER JOIN или просто JOIN) — это симметричная операция: если у клиента нет заказов, то клиент не появится в результате. Если у заказа нет клиента (что в принципе невозможно при правильной схеме, но допустим) — заказ тоже выпадет. Мы видим только пары, для которых предикат истинен.

Что делать, если нужно «всех клиентов и их заказы (если есть)»? Для этого существуют LEFT/RIGHT/FULL OUTER JOIN — но это уже не чистая реляционная алгебра, а её расширение. К ним мы вернёмся в модуле 5 («JOIN’ы во всех видах»), где разберём подробно. Сейчас важно одно: все JOIN’ы строятся над декартовым произведением, разница только в том, что делать с «остальными» строками.

Проверка знанийKnowledge check

У клиента есть таблица customers (12 строк) и таблица orders (20 строк). Сколько строк может максимально вернуть запрос FROM customers c, orders o (без WHERE)?

ОтветAnswer

240. Декартово произведение — это m·n. 12 клиентов на 20 заказов = 240 пар. Это худший случай, когда нет фильтра по customer_id. В реальной жизни мы почти всегда сразу добавляем WHERE c.id = o.customer_id, что превращает произведение в equi-join и даёт ≤ 20 строк (по одной на каждый заказ).

Hash Join: как equi-join работает внутри Postgres Nested Loop Join: двойной цикл и точки оптимума

Чек-лист

⨯ (декартово произведение) — комбинируй каждый с каждым. В SQL это CROSS JOIN.
θ-соединение — это ⨯ + σ_p. В SQL это JOIN ON p. Это правильная запись.
Equi-join — частный случай θ-соединения, где предикат — равенство. 99% реальных JOIN’ов.
Старая запись FROM A, B WHERE ... эквивалентна JOIN ... ON, но в современном коде пишут второй вариант.
NATURAL JOIN существует, но опасен — не используй без особой нужды.