# 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).

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