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)


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

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

=> 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), по которым строится другая хеш-таблица.


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