# Nested loop

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

    => EXPLAIN (COSTS OFF) SELECT *
      FROM tickets t JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
      WHERE t.ticket_no IN ('0005432312163','0005432312164');

                                        QUERY PLAN
    -----------------------------------------------------------------------------------
     Nested Loop
       ->  Index Scan using tickets_pkey on tickets t
             Index Cond: (ticket_no = ANY ('{0005432312163,0005432312164}'::bpchar[]))
       ->  Index Scan using ticket_flights_pkey on ticket_flights tf
             Index Cond: (ticket_no = t.ticket_no)
    (5 rows)

- Узел Nested Loop обращается к первому (внешнему) набору за первой строкой. Здесь это - узел Index Scan по билетам.
- Затем Nested Loop обращается ко второму (внутреннему) набору и просит выдать все строки, соответствующие строке первого набора. Здесь это - узел Index Scan по перелетам.
- Процесс повторяется до тех пор, пока внешний набор не исчерпает все строки.

Посмотрим на оцененную стоимость.

    => EXPLAIN SELECT *
      FROM tickets t JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
      WHERE t.ticket_no IN ('0005432312163','0005432312164');

                                                 QUERY PLAN
    -----------------------------------------------------------------------------------------------------
     Nested Loop  (cost=0.99..46.09 rows=6 width=136)
       ->  Index Scan using tickets_pkey on tickets t  (cost=0.43..12.89 rows=2 width=104)
             Index Cond: (ticket_no = ANY ('{0005432312163,0005432312164}'::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)
    (5 rows)

Первая компонента стоимости Nested Loop - сумма первых компонент стоимости дочерних узлов (Index Scan).

Вторая компонента стоимости Nested Loop складывается из:

- стоимости получения данных от внешнего набора (вторая компонента Index Scan по билетам);
- стоимости получения данных от внутреннего набора (вторая компонента Index Scan по перелетам), умноженной на число строк внвнешнего набора (2);
- процессорного времени на обработку строк.

В общем случае формула более сложная, но основной вывод: стоимость пропорциональна N * M, где N и M - число строк в соединяемых наборах данных.

Команда EXPLAIN ANALYZE позволяет узнать, сколько раз на самом деле выполнялся вложенный цикл (loops) и сколько в среднем было выбрано строк (rows) и потрачено времени (time) за один раз. Видно, что планировщик немного ошибся - получилось 8 строк вместо 6.

    => EXPLAIN (COSTS OFF,ANALYZE) SELECT *
      FROM tickets t JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
      WHERE t.ticket_no IN ('0005432312163','0005432312164');

                                                    QUERY PLAN
    -----------------------------------------------------------------------------------------------------------
     Nested Loop (actual time=2.533..5.056 rows=8 loops=1)
       ->  Index Scan using tickets_pkey on tickets t (actual time=1.313..1.334 rows=2 loops=1)
             Index Cond: (ticket_no = ANY ('{0005432312163,0005432312164}'::bpchar[]))
       ->  Index Scan using ticket_flights_pkey on ticket_flights tf (actual time=0.786..1.848 rows=4 loops=2)
             Index Cond: (ticket_no = t.ticket_no)
     Planning time: 0.383 ms
     Execution time: 5.090 ms
    (7 rows)

Предупреждение: вывод времени выполнения каждого шага, как в этом примере, может существенно замедлять выполнение запроса на некоторых платформах. Если такая информация не нужна, лучше указывать фразу TIMING OFF.

# Модификации

Существует несколько модификаций алгоритма. Для левого соединения:

    => EXPLAIN (COSTS OFF) SELECT *
      FROM aircrafts a LEFT JOIN seats s ON (a.aircraft_code = s.aircraft_code)
      WHERE a.model LIKE 'Аэробус%';

                              QUERY PLAN
    --------------------------------------------------------------
     Nested Loop Left Join
       ->  Seq Scan on aircrafts_data ml
             Filter: ((model ->> lang()) ~~ 'Аэробус%'::text)
       ->  Bitmap Heap Scan on seats s
             Recheck Cond: (ml.aircraft_code = aircraft_code)
             ->  Bitmap Index Scan on seats_pkey
                   Index Cond: (ml.aircraft_code = aircraft_code)
    (7 rows)

Эта модификация возвращает строки, даже если для левого (a) набора строк не нашлось соответствия в правом (s) наборе.

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

Антисоединение возвращает строки одного набора, если только для них не нашлось соответствия в другом наборе. Такая модификация может использоваться для обработки предиката NOT EXISTS:

    => EXPLAIN (COSTS OFF) SELECT *
      FROM aircrafts a
      WHERE a.model LIKE 'Аэробус%'
      AND NOT EXISTS (SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code);

                            QUERY PLAN
    ----------------------------------------------------------
     Nested Loop Anti Join
       ->  Seq Scan on aircrafts_data ml
             Filter: ((model ->> lang()) ~~ 'Аэробус%'::text)
       ->  Index Only Scan using seats_pkey on seats s
             Index Cond: (aircraft_code = ml.aircraft_code)
    (5 rows)

Та же операция антисоединения используется и для аналогичного запроса, записанного иначе:

    => EXPLAIN (COSTS OFF) SELECT *
      FROM aircrafts a LEFT JOIN seats s ON (a.aircraft_code = s.aircraft_code)
      WHERE a.model LIKE 'Аэробус%'
      AND s.aircraft_code IS NULL;

                            QUERY PLAN
    ----------------------------------------------------------
     Nested Loop Anti Join
       ->  Seq Scan on aircrafts_data ml
             Filter: ((model ->> lang()) ~~ 'Аэробус%'::text)
       ->  Index Scan using seats_pkey on seats s
             Index Cond: (ml.aircraft_code = aircraft_code)
    (5 rows)

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

    => EXPLAIN SELECT *
      FROM aircrafts a
      WHERE a.model LIKE 'Аэробус%'
      AND EXISTS (SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code);

                                           QUERY PLAN
    ----------------------------------------------------------------------------------------
     Nested Loop Semi Join  (cost=0.28..4.24 rows=1 width=52)
       ->  Seq Scan on aircrafts_data ml  (cost=0.00..3.39 rows=1 width=52)
             Filter: ((model ->> lang()) ~~ 'Аэробус%'::text)
       ->  Index Only Scan using seats_pkey on seats s  (cost=0.28..23.20 rows=149 width=4)
             Index Cond: (aircraft_code = ml.aircraft_code)
    (5 rows)

Обратите внимание: хотя в плане для таблицы s указано rows=149, на самом деле достаточно получить всего одну строку, чтобы понять значение предиката EXISTS.

PostgreSQL так и делает (actual rows):

    => EXPLAIN (COSTS OFF, ANALYZE) SELECT *
      FROM aircrafts a
      WHERE a.model LIKE 'Аэробус%'
      AND EXISTS (SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code);

                                             QUERY PLAN
    ---------------------------------------------------------------------------------------------
     Nested Loop Semi Join (actual time=3.274..3.384 rows=3 loops=1)
       ->  Seq Scan on aircrafts_data ml (actual time=2.502..2.524 rows=3 loops=1)
             Filter: ((model ->> lang()) ~~ 'Аэробус%'::text)
             Rows Removed by Filter: 6
       ->  Index Only Scan using seats_pkey on seats s (actual time=0.270..0.270 rows=1 loops=3)
             Index Cond: (aircraft_code = ml.aircraft_code)
             Heap Fetches: 3
     Planning time: 0.167 ms
     Execution time: 3.418 ms
    (9 rows)

Модификации алгоритма вложенного цикла для полного соединения (FULL JOIN) не существует. Это связано с тем, что полный проход по второму набору строк может не выполняться.

Если пренебречь производительностью, полное соединение можно получить, объединив левое соединение и антисоединение. Такой способ может пригодиться, так как FULL JOIN (как мы увидим позже) работает только с эквисоединениями.

# Соединение нескольких таблиц

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

    => 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
    --------------------------------------------------------------
     Nested Loop
       ->  Index Only Scan using flights_pkey on flights f
             Index Cond: (flight_id = 12345)
       ->  Gather
             Workers Planned: 2
             ->  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)
    (10 rows)

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

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

Конец демонстрации.