Как работают hash join и merge join

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

Умеете ли вы читать план запроса и понимаете ли, почему PostgreSQL выбрал тот или иной способ соединения. Следом обычно спрашивают про третий способ, nested loop, и почему запрос, который летал, вдруг стал медленным.

Как отвечать

• Hash join: работает в две фазы. На фазе построения по меньшему, по оценке планировщика, набору строится хеш-таблица по ключу соединения. На фазе проверки второй набор читается один раз, и каждая строка ищется в таблице. Сортировка не нужна, стоимость близка к линейной. Ограничения: только условие равенства и память. Бюджет задаёт work_mem, умноженный на hash_mem_multiplier; если таблица не помещается, она делится на пакеты и уходит на диск, в EXPLAIN ANALYZE это видно по Batches больше единицы;
• Merge join: оба входа отсортированы по ключу, и два курсора идут по ним параллельно, как при слиянии двух отсортированных списков. Сортировку дают B-tree индекс или явный узел Sort. В PostgreSQL тоже работает только на равенстве. Выход уже упорядочен, и ORDER BY по тому же ключу бывает бесплатным;
• Nested loop: для каждой строки внешнего набора ищет пару во внутреннем. Выгоден, когда внешних строк мало, а на внутренней таблице есть индекс, и это единственный вариант для условий вроде a.x < b.y.

Выбор делает планировщик по оценке количества строк, поэтому от точной статистики зависит больше, чем от формы запроса.

В Python-проекте join обычно рождает ORM, select_related в Django или joinedload в SQLAlchemy. План смотрите прямо из кода: queryset.explain(analyze=True) в Django или EXPLAIN ANALYZE на SQL, который печатает движок SQLAlchemy с echo=True.

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

Говорят, что хеш строится по меньшей таблице. На деле по меньшему набору после фильтров, и по оценке. Если оценка ошиблась в сто раз, хеш строится по большому набору и уходит на диск.

Считают, что merge join требует заранее отсортированных таблиц. Сортировку планировщик добавит сам, вопрос только в её цене.

Лечат плохой план через SET enable_hashjoin = off в проде. Это отладочный переключатель, а настоящее лечение это ANALYZE, расширенная статистика, work_mem или подходящий индекс.