Merge join

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

=> EXPLAIN (COSTS OFF) SELECT *
  FROM tickets t JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
  ORDER BY t.ticket_no;

                           QUERY PLAN                            
-----------------------------------------------------------------
 Merge Join
   Merge Cond: (t.ticket_no = tf.ticket_no)
   ->  Index Scan using tickets_pkey on tickets t
   ->  Index Scan using ticket_flights_pkey on ticket_flights tf
(4 rows)

Посмотрим на стоимость: 

=> EXPLAIN SELECT *
  FROM tickets t JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
  ORDER BY t.ticket_no;

                                                  QUERY PLAN                                                   
---------------------------------------------------------------------------------------------------------------
 Merge Join  (cost=38.10..787871.36 rows=8391906 width=150)
   Merge Cond: (t.ticket_no = tf.ticket_no)
   ->  Index Scan using tickets_pkey on tickets t  (cost=0.43..138478.98 rows=2949570 width=104)
   ->  Index Scan using ticket_flights_pkey on ticket_flights tf  (cost=0.56..537184.08 rows=8391906 width=32)
(4 rows)

Первая компонента включает:

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

Общий вывод: стоимость соединения слиянием пропорциональна N + M (где N и M - число соединяемых строк), если не требуется отдельная сортировка. Сортировка набора из K строк добавляет к оценке как минимум K * log(K).

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

=> EXPLAIN SELECT * 
  FROM tickets t JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
  ORDER BY t.ticket_no
  LIMIT 1000;

                                                     QUERY PLAN                                                      
---------------------------------------------------------------------------------------------------------------------
 Limit  (cost=38.10..131.98 rows=1000 width=150)
   ->  Merge Join  (cost=38.10..787871.36 rows=8391906 width=150)
         Merge Cond: (t.ticket_no = tf.ticket_no)
         ->  Index Scan using tickets_pkey on tickets t  (cost=0.43..138478.98 rows=2949570 width=104)
         ->  Index Scan using ticket_flights_pkey on ticket_flights tf  (cost=0.56..537184.08 rows=8391906 width=32)
(5 rows)

Обратите внимание и на то, как уменьшилась общая стоимость.

Если нужного индекса не окажется, придется выполнять сортировку в узле Sort. Тогда первая компонента стоимости будет не меньше стоимости сортировки, и первые строки запрос не сможет выдавать без задержки.

Вот пример такого плана (здесь явная сортировка выбрана из-за небольшого размера таблицы): 

=> EXPLAIN SELECT * 
  FROM aircrafts a JOIN seats s ON a.aircraft_code = s.aircraft_code
  ORDER BY a.aircraft_code;

                                     QUERY PLAN                                      
-------------------------------------------------------------------------------------
 Merge Join  (cost=1.51..420.71 rows=1339 width=83)
   Merge Cond: (s.aircraft_code = ml.aircraft_code)
   ->  Index Scan using seats_pkey on seats s  (cost=0.28..64.60 rows=1339 width=15)
   ->  Sort  (cost=1.23..1.26 rows=9 width=52)
         Sort Key: ml.aircraft_code
         ->  Seq Scan on aircrafts_data ml  (cost=0.00..1.09 rows=9 width=52)
(6 rows)

Группировка и уникальные значения

Как мы видели, для устранения дубликатов может использоваться хеширование. Другой способ - сортировка значений: 

=> EXPLAIN SELECT DISTINCT book_date
  FROM bookings
  ORDER BY book_date;

                                  QUERY PLAN                                  
------------------------------------------------------------------------------
 Unique  (cost=314054.67..324610.22 rows=441843 width=8)
   ->  Sort  (cost=314054.67..319332.45 rows=2111110 width=8)
         Sort Key: book_date
         ->  Seq Scan on bookings  (cost=0.00..34558.10 rows=2111110 width=8)
(4 rows)

Сортировка и устранение дубликатов происходит в узле Unique. Для группировки будет использоваться узел с другим названием - GroupAggregate.

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

Использование памяти при сортировке

Еще один случай, когда сортировка оказывается выгодней - ограниченная оперативная память: алгоритм внешней сортировки работает эффективней, чем хеш-соединение с использованием нескольких пакетов.

Включим сообщения о временных файлах и посмотрим, как выполняется сортировка. 

=> SET log_temp_files = 0;

SET

=> EXPLAIN (COSTS OFF, TIMING OFF, ANALYZE) SELECT DISTINCT book_date
  FROM bookings;

                           QUERY PLAN                           
----------------------------------------------------------------
 Unique (actual rows=540474 loops=1)
   ->  Sort (actual rows=2111110 loops=1)
         Sort Key: book_date
         Sort Method: external merge  Disk: 37248kB
         ->  Seq Scan on bookings (actual rows=2111110 loops=1)
 Planning time: 0.056 ms
 Execution time: 2397.735 ms
(7 rows)

Строки не помещаются в доступную память и используется внешняя сортировка (Sort Method: external merge).

Также в журнале сообщений мы видим запись о временном файле: 

postgres$ tail -n 4 /var/log/postgresql/postgresql-10-main.log

	  FROM bookings b JOIN tickets t ON b.book_ref = t.book_ref;
2019-02-13 13:05:45.184 MSK [7523] postgres@demo LOG:  temporary file: path "base/pgsql_tmp/pgsql_tmp7523.0", size 38141952
2019-02-13 13:05:45.184 MSK [7523] postgres@demo STATEMENT:  EXPLAIN (COSTS OFF, TIMING OFF, ANALYZE) SELECT DISTINCT book_date
	  FROM bookings;

Запись появляется, когда файл освобождается, поэтому его размер известен.

А теперь увеличим work_mem: 

=> SET work_mem = '32MB';

SET

=> EXPLAIN (COSTS OFF, TIMING OFF, ANALYZE) SELECT DISTINCT book_date
  FROM bookings;

                        QUERY PLAN                        
----------------------------------------------------------
 HashAggregate (actual rows=540474 loops=1)
   Group Key: book_date
   ->  Seq Scan on bookings (actual rows=2111110 loops=1)
 Planning time: 0.068 ms
 Execution time: 1190.318 ms
(5 rows)

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

Но если добавить предложение ORDER BY, планировщик возвращается к сортировке: 

=> EXPLAIN (COSTS OFF, TIMING OFF, ANALYZE) SELECT DISTINCT book_date
  FROM bookings
  ORDER BY book_date;

                           QUERY PLAN                           
----------------------------------------------------------------
 Sort (actual rows=540474 loops=1)
   Sort Key: book_date
   Sort Method: quicksort  Memory: 30475kB
   ->  HashAggregate (actual rows=540474 loops=1)
         Group Key: book_date
         ->  Seq Scan on bookings (actual rows=2111110 loops=1)
 Planning time: 0.064 ms
 Execution time: 1620.304 ms
(8 rows)

Теперь все строки поместились в память (Sort Method: quicksort).

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

Пример запроса с двумя соединениями слиянием (номера билетов и места в салоне): 

=> EXPLAIN (COSTS OFF) SELECT t.ticket_no, bp.flight_id, bp.seat_no
  FROM tickets t
    JOIN ticket_flights tf ON t.ticket_no = tf.ticket_no 
    JOIN boarding_passes bp ON bp.ticket_no = tf.ticket_no 
     AND bp.flight_id = tf.flight_id 
  ORDER BY t.ticket_no;

                                   QUERY PLAN                                   
--------------------------------------------------------------------------------
 Merge Join
   Merge Cond: ((t.ticket_no = tf.ticket_no) AND (bp.flight_id = tf.flight_id))
   ->  Merge Join
         Merge Cond: (bp.ticket_no = t.ticket_no)
         ->  Index Scan using boarding_passes_pkey on boarding_passes bp
         ->  Index Only Scan using tickets_pkey on tickets t
   ->  Index Only Scan using ticket_flights_pkey on ticket_flights tf
(7 rows)

Здесь соединяются билеты (tickets) и посадочные талоны (boarding_passes), и с этим, уже отсортированным по номерам билетов, набором строк соединяются перелеты (ticket_flights).

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