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)

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

=> 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 складывается из:

В общем случае формула более сложная, но основной вывод: стоимость пропорциональна 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) с помощью другого вложенного цикла.

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