Какие физические типы соединений (джойнов) существуют на физическом уровне

Что проверяют

Различаете ли вы логический тип соединения (что вернуть) и физический алгоритм (как база это сделает) и умеете ли читать план запроса. Для инженера данных следом почти всегда спрашивают, какие джойны выбирает Spark и почему джойн с маленькой таблицей бывает медленным.

Как отвечать

INNER, LEFT, FULL, CROSS это логические типы. Физических алгоритмов в классической СУБД три, оптимизатор выбирает их по статистике:

• Nested Loop: для каждой строки внешнего набора ищет пары во внутреннем. Хорош, когда снаружи мало строк, а внутри есть индекс по ключу. Единственный вариант для условий без равенства вроде a.ts BETWEEN b.start AND b.end;
• Hash Join: строит хеш-таблицу по меньшему набору и прогоняет через неё второй. Только равенство; в PostgreSQL ограничен work_mem и при нехватке памяти дробится на пакеты с записью на диск;
• Merge Join: сливает два набора, отсортированных по ключу. Выгоден, когда сортировку даёт индекс или она всё равно нужна дальше.

В Spark то же в распределённом виде:

• Broadcast Hash Join: маленькая таблица рассылается на все экзекьюторы, шаффла нет. Порог задаёт spark.sql.autoBroadcastJoinThreshold, по умолчанию 10 МБ, вручную включается хинтом broadcast();
• Sort Merge Join: выбор по умолчанию для двух больших таблиц, обе стороны шаффлятся и сортируются;
• Shuffle Hash Join: шаффл без сортировки, когда одна сторона партиции помещается в память;
• Broadcast Nested Loop и Cartesian: для условий без равенства и CROSS JOIN, самые дорогие.

Адаптивное выполнение (AQE, по умолчанию включено с Spark 3.2) меняет план на лету: превращает sort merge в broadcast, если фактический размер оказался маленьким, и дробит перекошенные партиции.

Где спотыкаются

Называют LEFT JOIN и CROSS JOIN физическими типами. Это логика запроса, любой из них выполняется разными алгоритмами.

Говорят, что Nested Loop всегда плохой. С индексом и десятком строк снаружи он быстрее остальных.

Не знают про перекос ключей: одно значение вроде NULL собирает миллионы строк в одну партицию, и один таск работает часами.