Третий и последний классический алгоритм — Merge Join. Его идея украдена у mergesort: если оба входа отсортированы по одному и тому же ключу, можно пройти их синхронно и склеить за O(N + M). Никакой хэш-таблицы, никакой памяти, никакого random access — только два sequential read’а и линейная склейка.

Merge Join — алгоритм, любимый OLAP-нагрузкой и хранилищами данных, и редкость в OLTP. Чтобы понять, когда он выгоден, надо посмотреть на его требования и стоимость в контексте Postgres.

Алгоритм: два указателя

В простейшем виде Merge Join выглядит как «зип» двух отсортированных списков:

i, j = 0, 0
while i < N and j < M:
    if left[i].key < right[j].key:
        i += 1
    elif left[i].key > right[j].key:
        j += 1
    else:  # equal — emit
        emit (left[i], right[j])
        # обработать дубликаты — все right с тем же ключом матчатся с left[i]
        # и все left с тем же ключом — с right[j]
        ...

Сложность — O(N + M), один линейный проход по каждому входу. На двух таблицах по миллиону строк это два миллиона сравнений, в разы меньше, чем NL без индекса, и сопоставимо с Hash Join.

Главное требование: оба входа должны быть отсортированы

Это требование делает Merge Join одновременно мощным и капризным. Если входы уже отсортированы (через Index Scan по B+tree на join-ключе) — Merge Join практически бесплатен. Если нет — придётся вставлять Sort-узел перед каждым входом, и стоимость сортировки O(N log N) часто перевешивает выигрыш от линейного merge.

Когда выбирает Postgres

Постгрес выбирает Merge Join, когда:

1. Обе таблицы упорядочены индексом по join-ключу. Тогда merge — это просто Index Scan обеих + проход по итераторам, минимальный CPU и нулевой memory overhead.
2. Результат всё равно нужно сортировать. Например, запрос с ORDER BY join_key или GROUP BY join_key. Тогда сортировка после Hash Join была бы избыточной — Merge даёт сортированный output бесплатно.
3. Огромные таблицы, work_mem мал. Hash Join при недостатке памяти переходит в batched (медленный диск); Merge тоже потребует external sort, но он более последовательный — может быть быстрее.
4. Join-условие — range или strict-equal. Merge Join поддерживает не только =, но и < / <= / >= (range join), что Hash Join не умеет.

Demo: смотрим, как Postgres его выбирает

В Postgres дефолтное поведение для маленьких таблиц — Nested Loop или Hash Join. Чтобы заставить Merge Join, нужно либо сделать таблицы достаточно большими и предоставить отсортированные индексы, либо принудительно выключить остальные алгоритмы.

Ожидаем в плане:

Merge Join
  Merge Cond: (c.id = o.customer_id)
  ->  Index Scan using customers_pkey on customers c
  ->  Sort  (Sort Key: o.customer_id)  <-- внешняя сортировка orders
        ->  Seq Scan on orders o

Index Scan на customers_pkey даёт уже отсортированные данные. На orders сортировки по customer_id нет, поэтому Postgres вставляет Sort-узел — и его стоимость может перевесить выигрыш merge. Смотри в EXPLAIN ANALYZE, использовалась ли quicksort или external sort, и какой Memory:/Disk: overhead.

Двусторонний Index Scan: best case Merge Join

Лучший сценарий — когда обе таблицы имеют индекс по join-ключу. Тогда Sort вообще не нужен.

Теперь под Merge Join’ом должно быть два Index Scan — никакого Sort. Это и есть идеальный Merge Join: ноль extra памяти, два sequential reads. Стоимость в разы ниже предыдущего варианта.

External sort: когда не помещается в work_mem

Если Sort требует больше памяти, чем work_mem, Postgres делает external sort (на диске):

В EXPLAIN ANALYZE это видно как:

Sort Method: external merge  Disk: 12000kB

Если видишь external merge в плане — это знак: либо подними work_mem, либо построй индекс по сорт-ключу, чтобы Sort не понадобился.

Range join: уникальное преимущество Merge

Hash Join не умеет range-условия (a.x BETWEEN b.lo AND b.hi). Merge Join — умеет, если обе стороны отсортированы по соответствующему ключу. Это редкий, но мощный паттерн, например, для джойнов с диапазонами времени или версий.

В таких запросах Hash Join невозможен (нет equality), Nested Loop работает плохо без индекса на range, а Merge Join может пройтись по отсортированным значениям и связать их. Постгрес может выбрать его сам, если статистика согласована.

Cost formula

Из costsize.c, упрощённо:

merge_cost = sort_cost(outer if not sorted) + sort_cost(inner if not sorted)
           + (outer.rows + inner.rows) × cpu_operator_cost
           + IF many duplicates: extra rescans on inner

Главные драйверы:

• Нужна ли сортировка на одной/обеих сторонах — если да, добавляется sort_cost = N × log N × cpu_operator_cost.
• Размер обеих таблиц.
• Дубликаты в join-ключе — если на одной стороне много строк с одинаковым ключом, Merge должен «rewind» (перематывать назад) и проходить их повторно. Это обрабатывается через Materialize под одной из сторон.

Edge case: дубликаты и Materialize

Когда на inner-стороне много строк с одинаковым ключом, классический merge должен возвращаться назад при следующем outer-ключе того же значения. Постгрес обходит это через Materialize на inner: кэширует «текущую группу» одинаковых ключей в памяти и переигрывает её, когда нужно.

В EXPLAIN это выглядит так:

Merge Join
  ->  Sort outer ...
  ->  Materialize
        ->  Sort inner ...

Materialize тут — индикатор: возможны дубликаты по join-ключу. Если дубликатов мало, расход небольшой; если много (n_distinct низкий) — Merge Join может стать медленнее Hash Join.

Чек-лист

• Merge Join = «зип» двух отсортированных потоков, O(N + M).
• Требует, чтобы обе стороны были отсортированы по join-ключу. Если нет — вставляется Sort-узел.
• Идеальный сценарий: обе таблицы имеют B+tree индекс по join-ключу → два Index Scan + merge → минимум CPU и I/O.
• Поддерживает range-conditions (<, <=, >=), что Hash Join не умеет.
• При недостатке work_mem Sort идёт в external (диск) — добавляет 2x I/O.
• Materialize под inner — знак дубликатов по join-ключу.
• На OLTP редок; на OLAP/DWH и больших отсортированных таблицах — главный конкурент Hash Join.
• В Postgres диагностируется через SET enable_hashjoin = off; SET enable_nestloop = off; — посмотри, что планер посчитал бы при отсутствии других вариантов.