# Hash join

Для большой выборки оптимизатор предпочитает соединение хешированием:

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

                    QUERY PLAN
    -------------------------------------------
     Hash Join
       Hash Cond: (tf.ticket_no = t.ticket_no)
       ->  Seq Scan on ticket_flights tf
       ->  Hash
             ->  Seq Scan on tickets t
    (5 rows)

Узел Hash Join начинает работу с того, что обращается к дочернему узлу Hash. Тот получает от своего дочернего узла (здесь - Seq Scan) весь набор строк и строит хеш-таблицу.

Затем Hash Join обращается ко второму дочернему узлу и соединяет строки, постепенно возвращая полученные результаты.

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

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

                                        QUERY PLAN
    -----------------------------------------------------------------------------------
     Hash Join  (cost=161241.33..494089.17 rows=8391906 width=136)
       Hash Cond: (tf.ticket_no = t.ticket_no)
       ->  Seq Scan on ticket_flights tf  (cost=0.00..149997.06 rows=8391906 width=32)
       ->  Hash  (cost=78283.70..78283.70 rows=2949570 width=104)
             ->  Seq Scan on tickets t  (cost=0.00..78283.70 rows=2949570 width=104)
    (5 rows)

Первая компонента стоимости узла Hash Join складывается из:

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

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

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

Главный вывод: стоимость хеш-соединения пропорциональна N + M, где N и M - число строк в соединяемых наборах данных. При больших N и M это значительно выгоднее, чем произведение в случае соединения внешним циклом.

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

Модификации Hash Join включают уже рассмотренные Left (Right), Semi и Anti, а также Full для полного соединения:

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

                                      QUERY PLAN
    ------------------------------------------------------------------------------
     Hash Full Join  (cost=3.47..30.04 rows=1339 width=67)
       Hash Cond: (s.aircraft_code = ml.aircraft_code)
       ->  Seq Scan on seats s  (cost=0.00..21.39 rows=1339 width=15)
       ->  Hash  (cost=3.36..3.36 rows=9 width=52)
             ->  Seq Scan on aircrafts_data ml  (cost=0.00..3.36 rows=9 width=52)
    (5 rows)

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

Для группировки (GROUP BY) и устранения дубликатов (DISTINCT и операции со множествами без слова ALL) используются методы, схожие с методами соединения. Один из способов выполнения состоит в том, чтобы построить хеш-таблицу по нужным полям и получить из нее уникальные значения.

    => EXPLAIN SELECT fare_conditions, count(*)
      FROM seats
      GROUP BY fare_conditions;

                              QUERY PLAN
    ---------------------------------------------------------------
     HashAggregate  (cost=28.09..28.12 rows=3 width=16)
       Group Key: fare_conditions
       ->  Seq Scan on seats  (cost=0.00..21.39 rows=1339 width=8)
    (3 rows)

То же самое и с DISTINCT:

    => EXPLAIN SELECT DISTINCT fare_conditions
      FROM seats;

                              QUERY PLAN
    ---------------------------------------------------------------
     HashAggregate  (cost=24.74..24.77 rows=3 width=8)
       Group Key: fare_conditions
       ->  Seq Scan on seats  (cost=0.00..21.39 rows=1339 width=8)
    (3 rows)

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

Значение work_mem по умолчанию:

    => SHOW work_mem;

     work_mem
    ----------
     4MB
    (1 row)

Увеличим размер:

    => SET work_mem = '128MB';

    SET

    => EXPLAIN (COSTS OFF, TIMING OFF, ANALYZE) SELECT *
      FROM bookings b JOIN tickets t ON b.book_ref = t.book_ref;

                                QUERY PLAN
    ------------------------------------------------------------------
     Hash Join (actual rows=2949857 loops=1)
       Hash Cond: (t.book_ref = b.book_ref)
       ->  Seq Scan on tickets t (actual rows=2949857 loops=1)
       ->  Hash (actual rows=2111110 loops=1)
             Buckets: 4194304  Batches: 1  Memory Usage: 104862kB
             ->  Seq Scan on bookings b (actual rows=2111110 loops=1)
     Planning time: 3.253 ms
     Execution time: 3630.731 ms
    (8 rows)

Хеш-таблица поместилась в память (Batches: 1). Параметр Buckets показывает число корзин в хеш-таблице, а Memory Usage - использованную оперативную память.

Обратите внимание, что хеш-таблица строилась по меньшему набору строк.

Сравним с таким же запросом, который выводит только одно поле:

    => EXPLAIN (COSTS OFF, TIMING OFF, ANALYZE) SELECT b.book_ref
      FROM bookings b JOIN tickets t ON b.book_ref = t.book_ref;

                                QUERY PLAN
    ------------------------------------------------------------------
     Hash Join (actual rows=2949857 loops=1)
       Hash Cond: (t.book_ref = b.book_ref)
       ->  Seq Scan on tickets t (actual rows=2949857 loops=1)
       ->  Hash (actual rows=2111110 loops=1)
             Buckets: 4194304  Batches: 1  Memory Usage: 72049kB
             ->  Seq Scan on bookings b (actual rows=2111110 loops=1)
     Planning time: 0.337 ms
     Execution time: 2575.033 ms
    (8 rows)

Расход памяти уменьшился, так как в хеш-таблице теперь только одно поле (вместо трех).

Обратите внимание на строку Hash Cond: она содержит предикаты, участвующие в соединении. Условие может включать и такие предикаты, которые не могут использоваться механизмом соединения, но должны учитываться. Они отображаются в отдельной строке Join Filter и тоже попадают в хеш-таблицу (сравните объем памяти):

    => EXPLAIN (COSTS OFF, ANALYZE, TIMING OFF) SELECT b.book_ref
      FROM bookings b JOIN tickets t ON b.book_ref = t.book_ref
                                    AND b.total_amount::text > t.passenger_id;

                                QUERY PLAN
    ------------------------------------------------------------------
     Hash Join (actual rows=1198320 loops=1)
       Hash Cond: (t.book_ref = b.book_ref)
       Join Filter: ((b.total_amount)::text > (t.passenger_id)::text)
       Rows Removed by Join Filter: 1751537
       ->  Seq Scan on tickets t (actual rows=2949857 loops=1)
       ->  Hash (actual rows=2111110 loops=1)
             Buckets: 4194304  Batches: 1  Memory Usage: 86308kB
             ->  Seq Scan on bookings b (actual rows=2111110 loops=1)
     Planning time: 1.268 ms
     Execution time: 3485.768 ms
    (10 rows)

Теперь уменьшим work_mem так, чтобы хеш-таблица не поместилась, и включим вывод сообщений о временных файлах:

    => SET work_mem = '32MB';

    SET

    => SET log_temp_files = 0;

    SET

    => EXPLAIN (COSTS OFF, ANALYZE, TIMING OFF) SELECT b.book_ref
      FROM bookings b JOIN tickets t ON b.book_ref = t.book_ref;

                                QUERY PLAN
    ------------------------------------------------------------------
     Hash Join (actual rows=2949857 loops=1)
       Hash Cond: (t.book_ref = b.book_ref)
       ->  Seq Scan on tickets t (actual rows=2949857 loops=1)
       ->  Hash (actual rows=2111110 loops=1)
             Buckets: 1048576  Batches: 4  Memory Usage: 18011kB
             ->  Seq Scan on bookings b (actual rows=2111110 loops=1)
     Planning time: 0.248 ms
     Execution time: 3388.761 ms
    (8 rows)

Потребовалось 4 пакета, и время выполнения запроса выросло.

Посмотрим сообщения о временных файлах в журнале - поскольку были использованы 4 пакета, то файлов будет (4-1)*2 = 6:

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

    2019-02-13 13:05:17.042 MSK [6714] postgres@demo LOG:  temporary file: path "base/pgsql_tmp/pgsql_tmp6714.2", size 12145518
    2019-02-13 13:05:17.042 MSK [6714] postgres@demo STATEMENT:  EXPLAIN (COSTS OFF, ANALYZE, TIMING OFF) SELECT b.book_ref
    	  FROM bookings b JOIN tickets t ON b.book_ref = t.book_ref;
    2019-02-13 13:05:17.344 MSK [6714] postgres@demo LOG:  temporary file: path "base/pgsql_tmp/pgsql_tmp6714.4", size 16973333
    2019-02-13 13:05:17.344 MSK [6714] postgres@demo STATEMENT:  EXPLAIN (COSTS OFF, ANALYZE, TIMING OFF) SELECT b.book_ref
    	  FROM bookings b JOIN tickets t ON b.book_ref = t.book_ref;
    2019-02-13 13:05:17.455 MSK [6714] postgres@demo LOG:  temporary file: path "base/pgsql_tmp/pgsql_tmp6714.1", size 12151958
    2019-02-13 13:05:17.455 MSK [6714] postgres@demo STATEMENT:  EXPLAIN (COSTS OFF, ANALYZE, TIMING OFF) SELECT b.book_ref
    	  FROM bookings b JOIN tickets t ON b.book_ref = t.book_ref;
    2019-02-13 13:05:17.751 MSK [6714] postgres@demo LOG:  temporary file: path "base/pgsql_tmp/pgsql_tmp6714.3", size 16984258
    2019-02-13 13:05:17.751 MSK [6714] postgres@demo STATEMENT:  EXPLAIN (COSTS OFF, ANALYZE, TIMING OFF) SELECT b.book_ref
    	  FROM bookings b JOIN tickets t ON b.book_ref = t.book_ref;
    2019-02-13 13:05:17.846 MSK [6714] postgres@demo LOG:  temporary file: path "base/pgsql_tmp/pgsql_tmp6714.0", size 12120655
    2019-02-13 13:05:17.846 MSK [6714] postgres@demo STATEMENT:  EXPLAIN (COSTS OFF, ANALYZE, TIMING OFF) SELECT b.book_ref
    	  FROM bookings b JOIN tickets t ON b.book_ref = t.book_ref;
    2019-02-13 13:05:18.151 MSK [6714] postgres@demo LOG:  temporary file: path "base/pgsql_tmp/pgsql_tmp6714.5", size 16942145
    2019-02-13 13:05:18.151 MSK [6714] postgres@demo STATEMENT:  EXPLAIN (COSTS OFF, ANALYZE, TIMING OFF) SELECT b.book_ref
    	  FROM bookings b JOIN tickets t ON b.book_ref = t.book_ref;

По размеру видно, что часть файлов относится к первой таблице (они меньше), а часть - ко второй (они больше).

Информацию об использовании временных файлов и вообще о вводе-выводе может показать и сама команда EXPLAIN с указанием BUFFERS:

    => EXPLAIN (COSTS OFF, ANALYZE, TIMING OFF, BUFFERS) SELECT b.book_ref
      FROM bookings b JOIN tickets t ON b.book_ref = t.book_ref;

                                 QUERY PLAN
    ---------------------------------------------------------------------
     Hash Join (actual rows=2949857 loops=1)
       Hash Cond: (t.book_ref = b.book_ref)
       Buffers: shared hit=260 read=61975, temp read=10668 written=10662
       ->  Seq Scan on tickets t (actual rows=2949857 loops=1)
             Buffers: shared hit=130 read=48658
       ->  Hash (actual rows=2111110 loops=1)
             Buckets: 1048576  Batches: 4  Memory Usage: 18011kB
             Buffers: shared hit=130 read=13317, temp written=4444
             ->  Seq Scan on bookings b (actual rows=2111110 loops=1)
                   Buffers: shared hit=130 read=13317
     Planning time: 0.325 ms
     Execution time: 3396.554 ms
    (12 rows)

- Hash: temp written - страницы пакетов, записанные при построении хеш-таблицы;
- Hash Join: temp read/written - чтение и запись временных файлов на этапе соединения.

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

Пример плана с двумя соединениями хешированием (имена пассажиров и рейсы):

    => EXPLAIN (COSTS OFF) SELECT t.passenger_name, f.flight_no
      FROM tickets t
        JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
        JOIN flights f ON f.flight_id = tf.flight_id;

                       QUERY PLAN
    -------------------------------------------------
     Hash Join
       Hash Cond: (tf.flight_id = f.flight_id)
       ->  Hash Join
             Hash Cond: (tf.ticket_no = t.ticket_no)
             ->  Seq Scan on ticket_flights tf
             ->  Hash
                   ->  Seq Scan on tickets t
       ->  Hash
             ->  Seq Scan on flights f
    (9 rows)

Сначала соединяются билеты (tickets) и перелеты (ticket_flights), причем хеш-таблица строится по таблице билетов. Затем получившийся набор строк соединяется с перелетами (flights), по которым строится другая хеш-таблица.

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