21 Вложенный цикл

PostgreSQL 18 · Издание 2026 года · Китайский перевод доступен для PostgreSQL 18

简体中文 · PG14 English · PG14 简体中文 · PG18Русский · PG18

21.1. Виды и способы соединений

Соединения — ключевая возможность языка SQL, основа его гибкости и мощности. Наборы строк (полученные непосредственно из таблиц или как результат выполнения других операций) всегда соединяются попарно.

Существует несколько видов соединений.

Внутренние соединения. Внутреннее соединение (INNER JOIN, или просто JOIN) включает такие пары строк из двух наборов, для которых выполняется условие соединения. Условие соединения связывает некоторые столбцы одного набора строк с некоторыми столбцами другого; все участвующие столбцы составляют ключ соединения.

Если условие требует равенства значений в столбцах одного и другого наборов, соединение называют эквисоединением; это наиболее частый случай.

Декартово произведение (CROSS JOIN) двух наборов включает все возможные пары строк — это частный случай внутреннего соединения с истинным условием.

Внешние соединения. Левое внешнее соединение (LEFT OUTER JOIN, или просто LEFT JOIN) добавляет к внутреннему соединению строки из левого набора, для которых не нашлось соответствия в правом наборе (столбцы отсутствующего правого набора получают неопределенные значения).

То же верно и для правого внешнего соединения (RIGHT JOIN), с точностью до перестановки наборов.

Полное внешнее соединение (FULL JOIN) объединяет левое и правое внешние соединения, добавляя строки как из левого, так и из правого наборов, для которых не нашлось соответствия.

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

Антисоединение включает строки одного набора, для которых не нашлось пары в другом наборе.

В языке SQL нет явных операций полу- и антисоединения, но к ним, например, приводят такие конструкции, как EXISTS и NOT EXISTS.

Все это — логические операции. Например, внутреннее соединение часто описывается как декартово произведение, в котором оставлены только строки, удовлетворяющие условию соединения. Но физически выполнить внутреннее соединение обычно можно другими, более экономными средствами.

PostgreSQL предоставляет несколько способов соединения:

соединение вложенным циклом (nested loop);
соединение хешированием (hash join);
соединение слиянием (merge join).

Способы соединения — алгоритмы, реализующие логические операции соединения SQL. Эти базовые алгоритмы часто имеют вариации, приспособленные для конкретных видов соединений, хотя могут и не поддерживать все из них. Например, вложенный цикл может применяться и для внутреннего соединения (в этом случае он будет представлен узлом Nested Loop), и для левого внешнего соединения (что будет отражено в плане узлом Nested Loop Left Join), но не может использоваться для полного соединения.

Более того, варианты тех же алгоритмов используются и для выполнения других операций, например агрегации.

Как и методы доступа, способы соединения по-разному показывают себя в разных ситуациях; планировщик выбирает лучший по стоимости вариант.

21.2. Соединение вложенным циклом

Базовый алгоритм соединения вложенным циклом устроен следующим образом. Во внешнем цикле перебираются строки первого набора (который называется внешним). Для каждой такой строки во вложенном цикле перебираются строки второго набора (который называется внутренним), удовлетворяющие условию соединения. Каждая найденная пара немедленно возвращается как часть результата¹.

Алгоритм обращается к внутреннему набору столько раз, сколько строк содержит внешний набор. Поэтому на эффективность соединения вложенным циклом влияет несколько условий:

кардинальность внешнего набора строк;
наличие метода доступа ко внутреннему набору, позволяющего эффективно получить нужные строки;
повторные обращения к одним и тем же строкам внутреннего набора.

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

Соединение вложенным циклом — наиболее эффективный способ выполнения декартова произведения, независимо от количества строк в наборах:

=> EXPLAIN SELECT * FROM aircrafts_data a1
  CROSS JOIN aircrafts_data a2
WHERE a2.range > 5000;
                     QUERY PLAN
-----------------------------------------------------
 Nested Loop  (cost=0.00..2.78 rows=45 width=144)
   -> Seq Scan on aircrafts_data a1                 ← внешний набор
       (cost=0.00..1.09 rows=9 width=72)
   -> Materialize  (cost=0.00..1.14 rows=5 width=72)
       -> Seq Scan on aircrafts_data a2             ← внутренний набор
           (cost=0.00..1.11 rows=5 width=72)
           Filter: (range > 5000)
(7 rows)

Узел Nested Loop выполняет соединение алгоритмом вложенного цикла. Он всегда имеет два дочерних узла. Тот, что находится выше в выводе плана, представляет внешний набор строк; тот, что ниже, — внутренний.

В данном случае внутренний набор представлен узлом Materialize ². Этот узел материализует строки, полученные от нижестоящего узла, что позволяет при повторном обращении не сканировать заново всю таблицу, а сразу прочитать сохраненные строки, удовлетворяющие условию. (с. 338)

К плану такого же вида может привести и запрос с обычным эквисоединением:

=> EXPLAIN SELECT *
FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
WHERE t.ticket_no = '0005432000284';
                           QUERY PLAN
----------------------------------------------------------------
 Nested Loop  (cost=0.99..25.05 rows=3 width=136)
   -> Index Scan using tickets_pkey on tickets t
       (cost=0.43..8.45 rows=1 width=104)
       Index Cond: (ticket_no = '0005432000284'::bpchar)
   -> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.57 rows=3 width=32)
       Index Cond: (ticket_no = '0005432000284'::bpchar)
(7 rows)

Здесь планировщик, понимая равенство двух значений, заменил условие соединения tf.ticket_no = t.ticket_no на условие tf.ticket_no = константа, фактически сведя эквисоединение к декартову произведению³.

Оценка кардинальности. Кардинальность декартова произведения равна произведению кардинальностей соединяемых наборов: 3 = 1 × 3.

Оценка стоимости. Начальная стоимость соединения равна сумме начальных стоимостей дочерних узлов.

Полная стоимость соединения в данном случае складывается:

из стоимости получения всех строк внешнего набора;
однократной стоимости получения всех строк внутреннего набора (поскольку оценка кардинальности внешнего набора равна единице);
стоимости обработки каждой строки результата.

Схема зависимостей при вычислении оценок выглядит так:

                           QUERY PLAN
----------------------------------------------------------------
 Nested Loop  (cost=0.99..25.05 rows=3 width=136)
   -> Index Scan using tickets_pkey on tickets t
       (cost=0.43..8.45 rows=1 width=104)

× 1

       Index Cond: (ticket_no = '0005432000284'::bpchar)
   -> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.57 rows=3 width=32)
       Index Cond: (ticket_no = '0005432000284'::bpchar)
(7 rows)

Вот как вычисляется стоимость соединения в этом случае:

=> SELECT 0.43 + 0.56 AS startup_cost,
  round((
    8.45 + 16.57 +
    3 * current_setting('cpu_tuple_cost')::real
  )::numeric, 2) AS total_cost;
 startup_cost | total_cost
--------------+------------
         0.99 |      25.05
(1 row)

Вернемся теперь к предыдущему примеру с узлом Materialize:

=> EXPLAIN SELECT *
FROM aircrafts_data a1
  CROSS JOIN aircrafts_data a2
WHERE a2.range > 5000;
                     QUERY PLAN
-----------------------------------------------------
 Nested Loop  (cost=0.00..2.78 rows=45 width=144)
   -> Seq Scan on aircrafts_data a1
       (cost=0.00..1.09 rows=9 width=72)
   -> Materialize  (cost=0.00..1.14 rows=5 width=72)
       -> Seq Scan on aircrafts_data a2
           (cost=0.00..1.11 rows=5 width=72)
           Filter: (range > 5000)
(7 rows)

В общем случае полная стоимость соединения складывается ⁴:

из стоимости получения всех строк внешнего набора;
однократной стоимости первоначального получения всех строк внутреннего набора (в ходе которого выполняется материализация);
(N−1)-кратной стоимости повторного получения строк внутреннего набора (где N — число строк во внешнем наборе);
стоимости обработки каждой строки результата.

Схема зависимостей здесь получается такая:

                    QUERY PLAN
--------------------------------------------------
 Nested Loop  (cost=0.00..2.78 rows=45 width=144)
   -> Seq Scan on aircrafts_data a1
       (cost=0.00..1.09 rows=9 width=72)

× 9

   -> Materialize
       (cost=0.00..1.14 rows=5 width=72)
       -> Seq Scan on aircrafts_data a2
           (cost=0.00..1.11 rows=5 width=72)
           Filter: (range > 5000)
(8 rows)

Благодаря материализации повторное получение данных обошлось дешевле. Стоимость первого обращения к узлу Materialize указана в плане, но стоимость повторного обращения не выводится. Я не буду разбирать, как вычисляется эта оценка⁵, но в данном случае она составляет 0,0125.

Таким образом, стоимость соединения для этого примера вычисляется так:

=> SELECT 0.00 + 0.00 AS startup_cost,
  round((
    1.09 + (1.14 + 8 * 0.0125) +
    45 * current_setting('cpu_tuple_cost')::real
  )::numeric, 2) AS total_cost;
 startup_cost | total_cost
--------------+------------
         0.00 |       2.78
(1 row)

Параметризованное соединение

Рассмотрим другой, более типичный пример, который не сводится к простому декартову произведению:

=> CREATE INDEX ON tickets(book_ref);
=> EXPLAIN SELECT *
FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
WHERE t.book_ref = '03A76D';
                           QUERY PLAN
----------------------------------------------------------------
 Nested Loop  (cost=0.99..45.67 rows=6 width=136)
   -> Index Scan using tickets_book_ref_idx on tickets t
       (cost=0.43..12.46 rows=2 width=104)
       Index Cond: (book_ref = '03A76D'::bpchar)
   -> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.57 rows=3 width=32)
       Index Cond: (ticket_no = t.ticket_no)
(7 rows)

Здесь узел Nested Loop перебирает строки внешнего набора (билеты) и для каждой такой строки обращается к строкам внутреннего набора (перелеты), передавая в условие доступа номер билета t.ticket_no как параметр. Когда вызывается внутренний узел Index Scan, он имеет дело с условием ticket_no = константа.

Оценка кардинальности. По оценке планировщика, условию на номер бронирования удовлетворяют две строки внешнего набора (rows=2), и для каждой во внутреннем наборе будет найдено в среднем три строки (rows=3).

Селективностью соединения называется доля строк от декартова произведения двух наборов, которая остается после соединения. Конечно, из учета надо сразу исключить строки обоих наборов, содержащие неопределенные значения в столбцах, по значениям которых происходит соединение (для таких строк условие равенства заведомо не будет выполняться).

Кардинальность оценивается как кардинальность декартова произведения (то есть произведение кардинальностей двух наборов), умноженная на селективность⁶.

В данном случае известна оценка кардинальности первого (внешнего) набора — две строки. Никаких условий на второй (внутренний) набор, кроме самого условия соединения, нет. Поэтому за кардинальность второго набора принимается кардинальность таблицы ticket_flights.

Поскольку соединяемые таблицы связаны внешним ключом, оценка селективности дается на основании того, что каждая строка дочерней таблицы имеет ровно одну пару в родительской таблице. За селективность в этом случае принимается величина, обратная размеру таблицы, на которую ссылается внешний ключ⁷.

Таким образом (учитывая, что столбцы ticket_no не имеют неопределенных значений), оценка составляет

=> SELECT round(2 * tf.reltuples * (1.0 / t.reltuples)) AS rows
FROM pg_class t, pg_class tf
WHERE t.relname = 'tickets'
  AND tf.relname = 'ticket_flights';
 rows
------
    6
(1 row)

Разумеется, таблицы можно соединять и без внешних ключей. Тогда в качестве селективности соединения будет использоваться оценка селективности конкретных условий соединения⁸.

Для нашего случая эквисоединения «базовая» формула расчета селективности, предполагающая равномерное распределение значений, выглядит как $\min\left(\frac{1}{nd_1},\frac{1}{nd_2}\right)$ , где nd₁ — число уникальных значений ключа соединения в первом наборе строк, а nd₂ — во втором⁹. (с. 351)

Статистика по количеству уникальных значений показывает, что в таблице tickets номера билетов уникальны (что естественно, поскольку столбец ticket_no является первичным ключом), а в таблице ticket_flights на каждый билет в среднем приходится примерно три строки:

=> SELECT t.n_distinct, tf.n_distinct
FROM pg_stats t, pg_stats tf
WHERE t.tablename = 'tickets' AND t.attname = 'ticket_no'
  AND tf.tablename = 'ticket_flights' AND tf.attname = 'ticket_no';
 n_distinct | n_distinct
------------+-------------
         -1 | -0.30457819
(1 row)

В итоге оценка совпала бы с оценкой на основе внешнего ключа:

=> SELECT round(2 * tf.reltuples *
  least(1.0/t.reltuples, 1.0/tf.reltuples/0.30457819)
) AS rows
FROM pg_class t, pg_class tf
WHERE t.relname = 'tickets' AND tf.relname = 'ticket_flights';
 rows
------
    6
(1 row)

Планировщик старается по возможности уточнить базовую оценку. В настоящее время он не использует гистограммы, но учитывает списки наиболее частых значений, если такая статистика собрана по ключу соединения для обеих таблиц¹⁰. В этом случае можно относительно точно рассчитать селективность соединения той части строк, которая попадает в списки, и только оставшуюся часть оценивать исходя из равномерного распределения. (с. 353)

Тем не менее в общем случае оценка селективности соединения в отсутствие внешнего ключа может оказаться хуже оценки при его наличии. Особенно велик риск получить сильно заниженную оценку для составных ключей соединения.

С помощью команды EXPLAIN ANALYZE можно посмотреть не только реальное число строк, но и количество обращений к внутреннему циклу:

=> EXPLAIN (analyze, timing off, summary off, buffers off) SELECT *
FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
WHERE t.book_ref = '03A76D';
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop  (cost=0.99..45.67 rows=6 width=136)
   (actual rows=8.00 loops=1)
   -> Index Scan using tickets_book_ref_idx on tickets t
       (cost=0.43..12.46 rows=2 width=104) (actual rows=2.00 loop...
       Index Cond: (book_ref = '03A76D'::bpchar)
       Index Searches: 1
   -> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.57 rows=3 width=32) (actual rows=4.00 loops=2)
       Index Cond: (ticket_no = t.ticket_no)
       Index Searches: 2
(10 rows)

Оценка подтвердилась: во внешнем наборе оказалось две строки (actual rows=2). Внутренний узел Index Scan выполнялся поэтому два раза (loops=2) и каждый раз выбирал в среднем четыре строки (actual rows=4). Отсюда общее количество найденных строк: actual rows=8. (с. 166)

Примечание

Я выключаю вывод времени выполнения каждого шага плана (timing off), чтобы не увеличивать ширину вывода, сильно ограниченную размером книжной страницы; к тому же на некоторых платформах такой вывод может существенно замедлять выполнение запроса. Но если время все-таки оставить, выведенное значение тоже будет усредненным, как и количество строк. Чтобы получить полное время, среднее надо умножить на число итераций (loops).

Оценка стоимости. Стоимость рассчитывается так же, как в уже рассмотренных примерах. Повторное сканирование внутреннего набора строк в данном случае не отличается по стоимости от первого.

В итоге получаем:

=> SELECT 0.43 + 0.56 AS startup_cost,
  round((
    12.46 + 2 * 16.58 +
    6 * current_setting('cpu_tuple_cost')::real
  )::numeric, 2) AS total_cost;
 startup_cost | total_cost
--------------+------------
         0.99 |      45.68
(1 row)

Кеширование (мемоизация) строк

Если повторное сканирование внутреннего набора строк часто выполняется с одними и теми же значениями параметра и, соответственно, приводит к одним и тем же результатам, может оказаться выгодным закешировать строки внутреннего набора. (v. 14)

Такую функцию выполняет узел Memoize¹¹. Он схож с узлом материализации Materialize, но рассчитан на параметризованное соединение и устроен значительно сложнее:

узел Materialize просто материализует все строки дочернего узла, а Memoize отдельно запоминает строки для каждого значения параметра;
при переполнении хранилище строк узла Materialize начинает сбрасывать данные на диск, а хранилище узла Memoize — нет (это лишило бы кеширование всякого смысла).

Вот пример плана запроса, который использует узел Memoize:

=> EXPLAIN SELECT *
FROM flights f
  JOIN aircrafts_data a ON f.aircraft_code = a.aircraft_code
WHERE f.flight_no = 'PG0003';
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop  (cost=5.44..387.10 rows=113 width=135)
   -> Bitmap Heap Scan on flights f
       (cost=5.30..382.22 rows=113 width=63)
       Recheck Cond: (flight_no = 'PG0003'::bpchar)
       -> Bitmap Index Scan on flights_flight_no_scheduled_depart...
           (cost=0.00..5.27 rows=113 width=0)
           Index Cond: (flight_no = 'PG0003'::bpchar)
   -> Memoize  (cost=0.15..0.27 rows=1 width=72)
       Cache Key: f.aircraft_code
       Cache Mode: logical
       -> Index Scan using aircrafts_pkey on aircrafts_data a
           (cost=0.14..0.26 rows=1 width=72)
           Index Cond: (aircraft_code = f.aircraft_code)
(13 rows)

Для кеширования строк выделяется память процесса размером work_mem × × hash_mem_multiplier. Как следует из названия второго параметра, внутри для поиска строк используется хеш-таблица (вариант с открытой адресацией ¹²). Ключом хеширования (Cache Key) служит значение параметра (или набор значений параметров, если их несколько). В логическом режиме (Cache Mode: logical) ключи сравниваются по значению (обычным оператором равенства), а в двоичном — побитово. (по умолчанию: 4MB) (по умолчанию: 2.0) (с. 520)

Кроме того, все ключи хеширования связаны в список, один конец которого считается «холодным» (давно не использовавшиеся ключи), а другой — «горячим» (ключи, использованные недавно).

Если при обращении к узлу Memoize оказывается, что строки, соответствующие переданным значениям параметров, находятся в кеше, они возвращаются родительскому узлу (Nested Loop) без обращения к дочернему узлу. Использованный ключ хеширования передвигается в горячий конец списка.

Если же в кеше нет нужных строк, узел Memoize получает строки от дочернего узла, сохраняет их в кеше и возвращает узлу выше. Новый ключ хеширования также становится горячим.

Пока кеш заполняется новыми данными, доступная память может исчерпаться. Чтобы освободить ее, из кеша удаляются строки, соответствующие холодным ключам. Этот алгоритм вытеснения отличается от того, что используется в буферном кеше, но выполняет ту же задачу. (с. 196)

Может оказаться, что каким-то значениям параметров соответствует так много строк, что они не помещаются полностью в кеш, даже если все остальные строки уже вытеснены. Тогда такие параметры пропускаются — нет смысла запоминать лишь часть строк, поскольку в следующий раз все равно придется обращаться к дочернему узлу за полной выборкой.

Оценки кардинальности и стоимости. Вычисление оценок ничем радикально не отличается от того, что мы уже видели выше. Однако следует учесть, что стоимость узла Memoize, показанная в плане, не имеет ничего общего с реальностью: это просто стоимость дочернего узла, увеличенная на значение cpu_tuple_cost ¹³. (по умолчанию: 0.01)

Но чтобы узел Memoize имел смысл, его стоимость должна быть не больше, а наоборот, меньше стоимости дочернего узла. С похожей ситуацией мы уже сталкивались на примере узла Materialize: «настоящая» стоимость вычисляется для повторного сканирования узла ¹⁴ и в плане не отображается.

Стоимость повторного сканирования узла Memoize учитывает размер памяти, доступной для кеширования, и предполагаемый характер обращений к кешу. Расчет очень сильно зависит от точности оценки количества различных значений параметров, с которыми будет сканироваться внутренний набор строк¹⁵. Получив ее, можно прикинуть вероятность обнаружения строки в кеше и вероятность вытеснения строк из кеша. Ожидаемые попадания в кеш уменьшают оценку стоимости, а потенциальные вытеснения — наоборот, увеличивают. В детали вычисления стоимости я вдаваться не буду.

Разобраться в том, что на самом деле происходит при выполнении запроса, как обычно, помогает команда EXPLAIN ANALYZE.

В нашем примере выбираются рейсы по одному маршруту, который обслуживается одним типом самолета; поэтому ключ хеширования совпадает для всех обращений к узлу Memoize. Первый раз за нужной строкой приходится сходить в таблицу (Misses: 1), но все повторные обращения обслуживаются кешем (Hits: 112). На все про все хватило одного килобайта памяти.

Еще два выведенных значения равны нулю: количество вытеснений из кеша (Evictions) и количество переполнений памяти с невозможностью сохранить все строки, относящиеся к одному набору параметров (Overflows). Большие цифры говорили бы о том, что выделенной под кеш памяти оказалось недостаточно, скорее всего, из-за некорректной оценки количества разных значений параметров. В таких условиях применение узла Memoize может оказаться весьма затратным. В крайнем случае можно запретить планировщику использовать кеш, отключив параметр enable_memoize. (по умолчанию: on)

=> EXPLAIN (analyze, costs off, timing off, summary off, buffers off)
SELECT * FROM flights f
  JOIN aircrafts_data a ON f.aircraft_code = a.aircraft_code
WHERE f.flight_no = 'PG0003';
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop (actual rows=113.00 loops=1)
   -> Bitmap Heap Scan on flights f
       (actual rows=113.00 loops=1)
       Recheck Cond: (flight_no = 'PG0003'::bpchar)
       Heap Blocks: exact=2
       -> Bitmap Index Scan on flights_flight_no_scheduled_depart...
           (actual rows=113.00 loops=1)
           Index Cond: (flight_no = 'PG0003'::bpchar)
           Index Searches: 1
   -> Memoize (actual rows=1.00 loops=113)
       Cache Key: f.aircraft_code
       Cache Mode: logical
       Hits: 112  Misses: 1  Evictions: 0  Overflows: 0  Memory
       Usage: 1kB
       -> Index Scan using aircrafts_pkey on aircrafts_data a
           (actual rows=1.00 loops=1)
           Index Cond: (aircraft_code = f.aircraft_code)
           Index Searches: 1
(18 rows)

Внешние соединения

Соединение вложенным циклом может применяться для левого внешнего соединения (узел Nested Loop Left Join). В этом примере планировщик выбрал непараметризованное соединение:

=> EXPLAIN SELECT * FROM ticket_flights tf
  LEFT JOIN boarding_passes bp ON bp.ticket_no = tf.ticket_no
                              AND bp.flight_id = tf.flight_id
WHERE tf.ticket_no = '0005434026720' and tf.flight_id = 82977;
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop Left Join  (cost=1.12..17.17 rows=1 width=57)
   -> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..8.58 rows=1 width=32)
       Index Cond: ((ticket_no = '0005434026720'::bpchar) AND (fl...
   -> Index Scan using boarding_passes_pkey on boarding_passes bp
       (cost=0.56..8.58 rows=1 width=25)
       Index Cond: ((ticket_no = '0005434026720'::bpchar) AND (fl...
(7 rows)

Кардинальность внешнего соединения оценивается так же, как и кардинальность внутреннего, но в качестве результата берется максимум из полученной оценки и кардинальности внешнего набора строк¹⁶. Иными словами, внешнее соединение никогда не уменьшает количество строк (но увеличить может).

Стоимость оценивается аналогично внутреннему соединению.

Правое соединение не поддерживается¹⁷, поскольку для алгоритма вложенного цикла внешний и внутренний наборы строк неравнозначны. Внешний набор строк просматривается полностью, а из внутреннего при индексном доступе читаются только строки, удовлетворяющие условию соединения. При этом часть строк может остаться непросмотренной.

Полное соединение не поддерживается по тем же соображениям.

Анти- и полусоединения

Антисоединения и полусоединения похожи тем, что для каждой строки первого (внешнего) набора во втором (внутреннем) наборе достаточно найти лишь одну подходящую строку.

Антисоединение возвращает строки первого набора, если только для них не нашлось соответствия в другом наборе. Иными словами, если во втором наборе нашлась одна подходящая строка, строка из первого набора уже не попадет в результат, и дальше можно не проверять.

Антисоединение может использоваться для вычисления предиката NOT EXISTS. Найдем, например, модели самолетов, для которых не задана конфигурация салона. Антисоединение вложенным циклом отображается в плане как узел Nested Loop Anti Join:

=> EXPLAIN SELECT *
FROM aircrafts a
WHERE NOT EXISTS (
  SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code
);
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop Anti Join  (cost=0.28..5.26 rows=1 width=40)
   -> Seq Scan on aircrafts_data ml  (cost=0.00..1.09 rows=9 widt...
   -> Index Only Scan using seats_pkey on seats s
       (cost=0.28..10.64 rows=149 width=4)
       Index Cond: (aircraft_code = ml.aircraft_code)
(5 rows)

Тот же план будет построен и для эквивалентного запроса без NOT EXISTS:

=> EXPLAIN SELECT a.*
FROM aircrafts a
  LEFT JOIN seats s ON a.aircraft_code = s.aircraft_code
WHERE s.aircraft_code IS NULL;
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop Anti Join  (cost=0.28..5.26 rows=1 width=40)
   -> Seq Scan on aircrafts_data ml  (cost=0.00..1.09 rows=9 widt...
   -> Index Only Scan using seats_pkey on seats s
       (cost=0.28..10.64 rows=149 width=4)
       Index Cond: (aircraft_code = ml.aircraft_code)
(5 rows)

Полусоединение возвращает те строки первого набора, для которых нашлось хотя бы одно соответствие во втором наборе (и снова последующие совпадения можно не проверять — результат уже известен).

Полусоединение может использоваться для вычисления предиката EXISTS. Найдем теперь модели самолетов, в салоне которых установлены кресла:

=> EXPLAIN SELECT *
FROM aircrafts a
WHERE EXISTS (
  SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code
);
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop Semi Join  (cost=0.28..7.28 rows=9 width=40)
   -> Seq Scan on aircrafts_data ml  (cost=0.00..1.09 rows=9 widt...
   -> Index Only Scan using seats_pkey on seats s
       (cost=0.28..10.64 rows=149 width=4)
       Index Cond: (aircraft_code = ml.aircraft_code)
(5 rows)

Полусоединение вложенным циклом представлено узлом Nested Loop Semi Join. В этом плане (и в планах выше для антисоединения) для таблицы seats указана обычная оценка строк (rows=149), хотя на самом деле достаточно получить всего одну. При выполнении запроса цикл, конечно, останавливается после первой строки:

=> EXPLAIN (analyze, costs off, timing off, summary off, buffers off)
SELECT * FROM aircrafts a
WHERE EXISTS (
  SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code
);
                          QUERY PLAN
---------------------------------------------------------------
 Nested Loop Semi Join (actual rows=9.00 loops=1)
   -> Seq Scan on aircrafts_data ml (actual rows=9.00 loops=1)
   -> Index Only Scan using seats_pkey on seats s
       (actual rows=1.00 loops=9)
       Index Cond: (aircraft_code = ml.aircraft_code)
       Heap Fetches: 9
       Index Searches: 9
(7 rows)

Оценка кардинальности. Для полусоединения дается обычным образом, но кардинальность внутреннего набора строк считается равной единице. А для антисоединения рассчитанная селективность вычитается из единицы, как для отрицания¹⁸.

Оценка стоимости. Для анти- и полусоединений оценка стоимости учитывает, что второй набор читается не полностью, а только пока не будет найдена пара к строке первого набора¹⁹.

Неэквисоединения

Алгоритм вложенного цикла позволяет соединять наборы строк по любому условию соединения.

Конечно, если внутренний набор строк является базовой таблицей, на этой таблице создан индекс и оператор условия соединения входит в класс операторов этого индекса, то к внутреннему набору строк возможен эффективный доступ. Но всегда остается вариант декартова произведения строк с фильтрацией по условию — и в этом случае условие может быть совершенно произвольным. Как, например, в этом запросе, выбирающем пары аэропортов, расположенных недалеко друг от друга: (с. 397)

=> CREATE EXTENSION earthdistance CASCADE;
=> EXPLAIN (costs off) SELECT *
FROM airports a1
  JOIN airports a2 ON a1.airport_code != a2.airport_code
                  AND a1.coordinates <@> a2.coordinates < 100;
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop
   Join Filter: ((ml.airport_code <> ml_1.airport_code) AND
   ((ml.coordinates <@> ml_1.coordinates) < '100'::double precisi...
   -> Seq Scan on airports_data ml
   -> Materialize
       -> Seq Scan on airports_data ml_1
(6 rows)

Параллельный режим

Соединение вложенным циклом может использоваться в параллельном режиме²⁰. (с. 379)

Распараллеливание происходит только на уровне внешнего набора строк, который может одновременно читаться несколькими рабочими процессами. Получив очередную строку внешнего набора, каждый процесс затем сам перебирает соответствующие ей строки внутреннего набора — уже последовательно.

Ниже приведен пример запроса с несколькими соединениями, который находит пассажиров, купивших билеты на определенный рейс:

=> EXPLAIN (costs off) SELECT t.passenger_name
FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
  JOIN flights f ON f.flight_id = tf.flight_id
WHERE f.flight_id = 12345;
                             QUERY PLAN
---------------------------------------------------------------------
 Gather
   Workers Planned: 2
   -> Nested Loop
       -> Nested Loop
           -> Parallel Seq Scan on ticket_flights tf
               Filter: (flight_id = 12345)
           -> Index Scan using tickets_pkey on tickets t
               Index Cond: (ticket_no = tf.ticket_no)
       -> Materialize
           -> Index Only Scan using flights_flight_id_status_idx ...
               Index Cond: (flight_id = 12345)
(11 rows)

Для получения внутреннего набора используется параллельный план. Каждый из процессов читает свои строки таблицы перелетов ticket_flights и соединяет их вложенным циклом с билетами tickets. (с. 380)

Затем каждый процесс соединяет полученный набор строк c одной строкой таблицы рейсов flights, полученной по уникальному ключу и материализованной в узле Materialize, поэтому вложенный цикл оправдан даже для большого внутреннего набора строк. (v. 18)

backend/executor/nodeNestloop.c. ↩︎
backend/executor/nodeMaterial.c. ↩︎
backend/optimizer/path/equivclass.c. ↩︎
backend/optimizer/path/costsize.c, функции initial_cost_nestloop и final_cost_nestloop. ↩︎
backend/optimizer/path/costsize.c, функция cost_rescan. ↩︎
backend/optimizer/path/costsize.c, функция calc_joinrel_size_estimate. ↩︎
backend/optimizer/path/costsize.c, функция get_foreign_key_join_selectivity. ↩︎
backend/optimizer/path/clausesel.c, функция clauselist_selectivity. ↩︎
backend/utils/adt/selfuncs.c, функция eqjoinsel. ↩︎
backend/utils/adt/selfuncs.c, функция eqjoinsel. ↩︎
backend/executor/nodeMemoize.c. ↩︎
include/lib/simplehash.h. ↩︎
backend/optimizer/util/pathnode.c, функция create_memoize_path. ↩︎
backend/optimizer/path/costsize.c, функция cost_memoize_rescan. ↩︎
backend/utils/adt/selfuncs.c, функция estimate_num_groups. ↩︎
backend/optimizer/path/costsize.c, функция calc_joinrel_size_estimate. ↩︎
backend/optimizer/path/joinpath.c, функция match_unsorted_outer. ↩︎
backend/optimizer/path/costsize.c, функция calc_joinrel_size_estimate. ↩︎
backend/optimizer/path/costsize.c, функция final_cost_nestloop. ↩︎
backend/optimizer/path/joinpath.c, функция consider_parallel_nestloop. ↩︎