Из всех алгоритмов соединения Nested Loop Join — самый простой и старый. Его описывает один цикл с другим внутри. На бумаге выглядит примитивно: «для каждой строки внешней таблицы найди подходящие строки во внутренней». Этот же алгоритм пишет джуниор на собеседовании, когда спрашивают «реализуйте JOIN на Python». И, парадоксально, именно его выбирает Postgres-оптимизатор чаще, чем кажется — в десятках реальных продакшен-сценариев.

Чтобы понимать, почему оптимизатор иногда выбирает Nested Loop, а иногда — нет, нужно знать его стоимость как функцию размеров таблиц и наличия индекса. Этим и займёмся.

Алгоритм: два цикла

В простейшем (naive) виде Nested Loop выглядит так:

for outer_row in outer_table:
    for inner_row in inner_table:
        if join_condition(outer_row, inner_row):
            emit (outer_row, inner_row)

Это O(N × M), где N — число строк во внешней таблице, M — во внутренней. На двух таблицах по миллиону строк это триллион сравнений — заведомо неприемлемо. Поэтому naive-вариант оптимизатор использует только когда обе таблицы очень малы (десятки строк).

Index Nested Loop: магия превращения O(N×M) в O(N×log M)

Настоящая сила Nested Loop проявляется, когда на внутренней таблице есть индекс по join-ключу. Тогда внутренний «полный проход» превращается в Index Scan или Index Only Scan — log M вместо M.

for outer_row in outer_table:        # N итераций
    for inner_row in index_scan(inner_table, key = outer_row.key):  # log M
        emit (outer_row, inner_row)

Стоимость: N × log M. На outer = 10 строк и inner = 10M строк это 10 × ~23 = ~230 операций. Для сравнения, Hash Join потребует пробежать inner целиком, построить хэш-таблицу на 10M записей, выделить ~гигабайт памяти. Nested Loop здесь — выигрывает безоговорочно.

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

Оптимизатор оценивает стоимость в disk pages × cost-per-page + cpu_tuple_cost × rows. Nested Loop с индексом обыгрывает Hash Join и Merge Join, когда:

1. Outer-таблица маленькая: после фильтров на ней остаётся 1-100 строк. Накладные расходы N × log M ничтожны.
2. На inner-таблице есть индекс по join-ключу. Без индекса каждый внутренний проход — полный Seq Scan, стоимость взрывается.
3. LIMIT и ORDER BY на outer: если запрос требует первые 10 строк отсортированных по чему-то, удобно сначала отсортировать outer, потом для каждой первой строки сходить по индексу.
4. Cross-join маленьких таблиц: для двух таблиц по 10-100 строк все три алгоритма одинаково дёшевы, и Nested Loop выбирается из-за простейшего setup.

Когда не стоит ждать Nested Loop:

• Обе таблицы большие, индекса на inner нет — оптимизатор пойдёт в Hash Join.
• Outer-таблица большая. Даже с индексом N × log M быстро становится дороже, чем «один Seq Scan каждой таблицы для Hash Join».

Демо: считаем стоимость на реальных таблицах

В плане ожидаем Nested Loop сверху, под ним Index Scan по orders_pkey (одна строка из orders) и Index Scan по customers_pkey (одна строка из customers по customer_id). Total Buffers: shared hit будет крошечный — 4-6 страниц.

Теперь принудительно заставим Hash Join — чтобы сравнить стоимости:

Видим, что Hash Join вынужден прочитать всю таблицу customers целиком (10K строк, ~100 страниц), чтобы построить хэш-таблицу — ради одного матча. На таком маленьком outer Nested Loop был бы в десятки раз дешевле. Это хороший пример выбора в зависимости от размера outer.

Materialize: кэшируем inner для повторных проходов

Иногда внутренний цикл хочется пройти много раз без повторного выполнения. Например, если inner — это результат фильтра по другой таблице или подзапрос. Тогда Postgres вставляет узел Materialize — мини-кэш в памяти, который запоминает результат inner и отдаёт его N раз без повторного вычисления.

Materialize появляется в плане только если он реально окупается: если outer пройдёт inner пару раз, кэшировать невыгодно. Постгрес считает breakeven по rows × cost.

Если outer имеет 5 строк, а inner — таблица без подходящего индекса, Postgres почти наверняка вставит Materialize. С индексом по customers(id) он есть, поэтому здесь увидим обычный Index Nested Loop.

Cost formula: что считает оптимизатор

Точная формула из исходников costsize.c для Nested Loop:

cost = startup_cost(outer) + startup_cost(inner)
     + outer.rows × (run_cost(inner_per_row) + cpu_tuple_cost)
     + run_cost(outer)

Главная зависимость — линейная по outer.rows. Если на outer есть фильтр, который сильно его сокращает, NL становится сильно выгоднее. Это объясняет один из самых частых паттернов:

«Запрос медленный, я добавил индекс, стал быстрый. Через месяц данных стало 100x больше — и теперь снова медленный.»

Что произошло: оптимизатор выбирал NL, потому что после фильтра outer был маленький. С ростом данных фильтр пропускает 100x больше строк — N в формуле взлетает, NL перестаёт быть дешевым, и планер должен бы переключиться на Hash Join, но если статистика устарела или join_collapse_limit мешает — он этого не делает.

Параметры, которые на это влияют

• enable_nestloop — глобальное вкл/выкл (on по умолчанию). Только для диагностики.
• enable_material — управляет вставкой Materialize-узла.
• random_page_cost и seq_page_cost — управляют относительной стоимостью Index Scan vs Seq Scan внутри inner.
• cpu_tuple_cost — добавляется на каждый emit; на NL с большим outer ощутимо.

Чек-лист

• Nested Loop = два вложенных цикла. Naive O(N×M), с индексом на inner — O(N × log M).
• Идеальный сценарий: маленький outer (после фильтров) + индекс на inner по join-ключу.
• Index Scan под Nested Loop — самый частый паттерн на OLTP-нагрузке.
• Materialize появляется, когда inner вычислять заново дороже, чем закэшировать в work_mem.
• Не работает хорошо, когда outer становится большим; тогда оптимизатор сам переключится на Hash Join.
• SET enable_nestloop = off — диагностика, не лекарство.
• При неверной статистике (ANALYZE устарел) можно получить кошмарный NL на больших outer-таблицах — следи за n_distinct и pg_stats.