erogov 22 сен 2021 в 14:52

Запросы в PostgreSQL: 5. Вложенный цикл

19 мин

26K

Блог компании Postgres ProfessionalPostgreSQL*SQL*

Я уже рассказал об этапах выполнения запросов и о статистике, и о двух основных видах доступа к данным: о последовательном сканировании и об индексном сканировании.

Настал черед способов соединения. В этой статье я кратко напомню, какие бывают логические типы соединений, и расскажу о первом из трех физических способов соединения — о вложенном цикле. Заодно посмотрим и на новую для 14-й версии мемоизацию строк.

Соединения

Соединения — ключевая возможность языка SQL, основа его гибкости и мощности. Наборы строк (полученные непосредственно из таблиц или как результат выполнения других операций) всегда соединяются попарно. Существует несколько типов соединений.

Внутренние соединения. Внутреннее соединение (INNER JOIN или просто JOIN) включает такие пары строк из двух наборов, для которых выполняется условие соединения. Условие соединения связывает некоторые столбцы одного набора строк с некоторыми столбцами другого; все участвующие столбцы составляют ключ соединения.
Если условие состоит из оператора равенства, соединение называют эквисоединением; это наиболее частый случай.
Декартово произведение (CROSS JOIN) двух наборов включает все возможные пары строк из обоих наборов — это частный случай внутреннего соединения с истинным условием.

Внешние соединения. Левое внешнее соединение (LEFT OUTER JOIN или просто LEFT JOIN) добавляет к внутреннему соединению строки из левого набора, для которых не нашлось соответствия в правом наборе (столбцы отсутствующего правого набора получают неопределенные значения).
То же верно и для правого внешнего соединения (RIGHT JOIN) с точностью до перестановки наборов.
Полное внешнее соединение (FULL JOIN) объединяет левое и правое внешние соединения, и содержит строки как из левого, так и из правого наборов, для которых не нашлось соответствия.
Полусоединения и антисоединения. Полусоединение похоже на внутреннее соединение, но включает строки только одного набора, для которых нашлось соответствие в другом наборе (строка будет включена в результат только один раз, даже если соответствий несколько).
Антисоединение включает строки одного набора, для которых не нашлось пары в другом наборе.
В языке SQL нет явных операций полу- и антисоединения, но к ним, например, приводят такие конструкции, как EXISTS и NOT EXISTS.

Все это — логические операции. Например, внутреннее соединение часто описывается как декартово произведение, в котором оставлены только строки, удовлетворяющие условию соединения. Но физически выполнить внутреннее соединение обычно можно другими, более экономными, способами.

PostgreSQL предоставляет несколько способов соединения:

соединение вложенным циклом (nested loop);
соединение хешированием (hash join);
соединение слиянием (merge join).

Способы соединения — алгоритмы, реализующие логические операции соединения SQL. Часто эти базовые алгоритмы имеют вариации, приспособленные для конкретных типов соединений. Например, внутреннее соединение с помощью вложенного цикла представляется в плане узлом Nested Loop, а тот же алгоритм для левого внешнего соединения — Nested Loop Left Join.

В разных ситуациях более эффективными оказываются разные способы; планировщик выбирает лучший по стоимости.

Соединение вложенным циклом

Базовый алгоритм соединения вложенным циклом таков. Во внешнем цикле перебираются строки первого набора данных (который называется внешним). Для каждой такой строки во вложенном цикле перебираются строки второго набора (который называется внутренним), удовлетворяющие условию соединения. Каждая найденная пара немедленно возвращается как часть результата.

Алгоритм обращается к внутреннему набору столько раз, сколько строк содержит внешний набор. Поэтому эффективность соединения вложенным циклом зависит от нескольких условий:

кардинальность внешнего набора строк;
наличие метода доступа ко внутреннему набору, позволяющего эффективно получить нужные строки;
повторные обращения к одним и тем же строкам внутреннего набора.

Рассмотрим несколько примеров.

Декартово произведение

Соединение вложенным циклом — наиболее эффективный способ выполнения декартова произведения, независимо от количества строк в обоих наборах.

EXPLAIN SELECT * 
FROM aircrafts_data a1
  CROSS JOIN aircrafts_data a2 
WHERE a2.range > 5000;

                     QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Nested Loop  (cost=0.00..2.78 rows=45 width=144) 
   −> Seq Scan on aircrafts_data a1                      вешний набор
       (cost=0.00..1.09 rows=9 width=72)
   −> Materialize  (cost=0.00..1.14 rows=5 width=72)     внутренний набор
       −> Seq Scan on aircrafts_data a2 
           (cost=0.00..1.11 rows=5 width=72)
           Filter: (range > 5000)
(7 rows)

Узел Nested Loop выполняет соединение алгоритмом вложенного цикла. Он всегда имеет два дочерних узла. Тот, что находится выше в выводе плана, представляет внешний набор данных; тот, что ниже — внутренний.

В данном случае внутренний набор представлен узлом Materialize. Фактически этот узел возвращает полученные от нижестоящего узла строки, предварительно сохраняя их в памяти (пока размер не превышает work_mem; затем данные начинают сохраняться на диск во временный файл). При повторном обращении узел читает запомненные ранее строки, уже не обращаясь к дочернему узлу. Это позволяет не выполнять повторно сканирование всей таблицы, а прочитать только нужные строки, удовлетворяющие условию.

К плану такого же вида может привести и запрос с внутренним соединением:

EXPLAIN SELECT * 
FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no 
WHERE t.ticket_no = '0005432000284';

                           QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Nested Loop  (cost=0.99..25.05 rows=3 width=136) 
   −> Index Scan using tickets_pkey on tickets t
       (cost=0.43..8.45 rows=1 width=104)
       Index Cond: (ticket_no = '0005432000284'::bpchar)
   −> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.57 rows=3 width=32)
       Index Cond: (ticket_no = '0005432000284'::bpchar) 
(7 rows)

Здесь планировщик, понимая равенство двух значений, заменил условие соединения tf.ticket_no = t.ticket_no на условие tf.ticket_no = константа, фактически сведя внутреннее соединение к декартовому произведению.

Оценка кардинальности. Кардинальность декартового произведения равна произведению кардинальностей соединяемых наборов: 3 = 1 × 3.

Оценка стоимости. Начальная стоимость соединения равна сумме начальных стоимостей дочерних узлов.

Полная стоимость соединения в данном случае складывается из

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

SELECT 0.43 + 0.56 AS startup_cost, 
  round((
    8.45 + 16.58 +
    3 * current_setting('cpu_tuple_cost')::real 
  )::numeric, 2) AS total_cost;

 startup_cost | total_cost 
−−−−−−−−−−−−−−+−−−−−−−−−−−−
         0.99 |      25.06
(1 row)

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

Вернемся к предыдущему примеру:

EXPLAIN SELECT * 
FROM aircrafts_data a1
  CROSS JOIN aircrafts_data a2 
WHERE a2.range > 5000;

                     QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Nested Loop  (cost=0.00..2.78 rows=45 width=144) 
   −> Seq Scan on aircrafts_data a1
       (cost=0.00..1.09 rows=9 width=72)
   −> Materialize  (cost=0.00..1.14 rows=5 width=72)
       −> Seq Scan on aircrafts_data a2 
           (cost=0.00..1.11 rows=5 width=72)
           Filter: (range > 5000)
(7 rows)

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

В общем случае полная стоимость соединения складывается из

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

В этом примере при первоначальном получении строк выполняется материализация, поэтому повторное получение обходится дешевле. Стоимость первого обращения к узлу Materialize указана в плане, но стоимость повторного обращения не выводится. Я не буду разбирать, как вычисляется эта оценка, но в данном случае она составляет 0,0125.

Таким образом, стоимость соединения для этого примера вычисляется так:

SELECT 0.00 + 0.00 AS startup_cost, 
  round((
    1.09 +
    1.14 + 8 * 0.0125 +
    45 * current_setting('cpu_tuple_cost')::real
  )::numeric, 2) AS total_cost;

 startup_cost | total_cost 
−−−−−−−−−−−−−−+−−−−−−−−−−−−
         0.00 |       2.78
(1 row)

Параметризованное соединение

Рассмотрим другой, более типичный, пример, который не сводится к простому декартовому произведению:

CREATE INDEX ON tickets(book_ref);
EXPLAIN SELECT * 
FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no 
WHERE t.book_ref = '03A76D';

                           QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Nested Loop  (cost=0.99..45.67 rows=6 width=136)
   −> Index Scan using tickets_book_ref_idx on tickets t
       (cost=0.43..12.46 rows=2 width=104)
       Index Cond: (book_ref = '03A76D'::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) 
(7 rows)

Здесь узел Nested Loop перебирает строки внешнего набора (билеты), и для каждой такой строки обращается к строкам внутреннего набора (перелеты), передавая в условие доступа номер билета t.ticket_no как параметр. Когда вызывается внутренний узел Index Scan, он имеет дело с условием ticket_no = константа.

Оценка кардинальности. По оценке планировщика, условие на номер бронирования оставит во внешнем наборе две строки (rows=2), и для каждой из этих строк во внутреннем наборе в среднем будет найдено три строки (rows=3).

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

Кардинальность оценивается как кардинальность декартова произведения (то есть произведение кардинальностей двух наборов), умноженная на селективность.

В данном случае имеем оценку кардинальности первого (внешнего) набора — две строки. Никаких условий на второй (внутренний) набор, кроме самого условия соединения, нет. Поэтому за кардинальность второго набора принимается кардинальность таблицы ticket_flights.

Поскольку соединяемые таблицы связаны внешним ключом, оценка селективности дается на основании того, что каждая строка дочерней таблицы имеет ровно одну пару в родительской таблице. За селективность в этом случае принимается величина, обратная размеру таблицы, на которую ссылается внешний ключ.

Таким образом, оценка составляет (учитывая, что столбцы ticket_no не имеют неопределенных значений):

SELECT round(2 * tf.reltuples * (1.0 / t.reltuples)) AS rows 
FROM pg_class t, pg_class tf
WHERE t.relname = 'tickets'
AND tf.relname = 'ticket_flights';

 rows 
−−−−−−
    6 
(1 row)

Разумеется, таблицы можно соединять, не определяя внешних ключей. Тогда в качестве селективности соединения будет использоваться оценка селективности конкретных условий соединения.

Для нашего случая эквисоединения «базовая» формула для расчета селективности, предполагающая равномерное распределение значений, выглядит как

$min \big( \frac{1}{nd_1},\frac{1}{nd_2} \big),$

где nd₁ — число уникальных значений ключа соединения в первом наборе строк, а nd₂ — во втором.

Статистика по количеству уникальных значений показывает, что в таблице tickets номера билетов уникальны (что естественно, поскольку столбец ticket_no является первичным ключом), а в таблице ticket_flights на каждый билет в среднем приходится примерно четыре строки:

SELECT t.n_distinct, tf.n_distinct
FROM pg_stats t, pg_stats tf
WHERE t.tablename = 'tickets' AND t.attname = 'ticket_no'
AND tf.tablename = 'ticket_flights' AND tf.attname = 'ticket_no';

 n_distinct | n_distinct 
−−−−−−−−−−−−+−−−−−−−−−−−−
         −1 | −0.3054527
(1 row)

В итоге оценка совпала бы с оценкой, данной на основе наличия внешнего ключа:

SELECT round(2 * tf.reltuples * 
  least(1.0/t.reltuples, 1.0/tf.reltuples/0.3054527)
) AS rows
FROM pg_class t, pg_class tf
WHERE t.relname = 'tickets' AND tf.relname = 'ticket_flights';

 rows 
−−−−−−
    6 
(1 row)

Кроме базовой формулы планировщик учитывает и списки наиболее частых значений, если такая статистика собрана по ключу соединения для обоих таблиц. В этом случае можно относительно точно рассчитать селективность соединения той части строк, которая попадает в списки, и оценивать исходя из равномерного распределения только селективность соединения оставшихся строк. Гистограммы в настоящее время не используются для уточнения оценки.

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

С помощью команды EXPLAIN ANALYZE можно посмотреть не только реальное число строк, но и количество обращений к внутреннему циклу:

EXPLAIN (analyze, timing off, summary off) SELECT * 
FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no 
WHERE t.book_ref = '03A76D';

                            QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Nested Loop  (cost=0.99..45.67 rows=6 width=136) 
   (actual rows=8 loops=1)
   −> Index Scan using tickets_book_ref_idx on tickets t
       (cost=0.43..12.46 rows=2 width=104) (actual rows=2 loops=1)
       Index Cond: (book_ref = '03A76D'::bpchar)
   −> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.57 rows=3 width=32) (actual rows=4 loops=2)
       Index Cond: (ticket_no = t.ticket_no)
(8 rows)

Во внешнем наборе оказалось две строки (actual rows=2), что совпадает с оценкой. Внутренний узел Index Scan поэтому выполнялся два раза (loops=2), и каждый раз выбирал в среднем четыре строки (actual rows=4). Отсюда общее количество найденных строк (actual rows=8).

Я выключаю вывод времени выполнения каждого шага плана (timing off) в основном чтобы не увеличивать ширину вывода; к тому же на некоторых платформах такой вывод может существенно замедлять выполнение запроса. Но если время все-таки вывести, это тоже будет среднее значение, как и количество строк. Чтобы получить полное значение, его надо умножать на количество итераций (loops).

Оценка стоимости. Стоимость рассчитывается так же, как в уже рассмотренных примерах. Напомню план запроса:

EXPLAIN SELECT * 
FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no 
WHERE t.book_ref = '03A76D';

                           QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Nested Loop  (cost=0.99..45.67 rows=6 width=136)
   −> Index Scan using tickets_book_ref_idx on tickets t
       (cost=0.43..12.46 rows=2 width=104)
       Index Cond: (book_ref = '03A76D'::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)
(7 rows)

Стоимость повторного сканирования внутреннего набора строк в данном случае не отличается от стоимости первого сканирования. В итоге получаем:

SELECT 0.43 + 0.56 AS startup_cost, 
  round((
    12.46 + 2 * 16.58 +
    6 * current_setting('cpu_tuple_cost')::real 
  )::numeric, 2) AS total_cost;

 startup_cost | total_cost 
−−−−−−−−−−−−−−+−−−−−−−−−−−−
         0.99 |      45.68
(1 row)

Кеширование (мемоизация) строк

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

Это стало возможным в версии PostgreSQL 14 с появлением узла Memoize. Он схож с узлом материализации Materialize, но рассчитан на параметризованное соединение и устроен значительно сложнее:

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

Вот пример плана запроса, который использует узел Memoize:

EXPLAIN SELECT * 
FROM flights f
  JOIN aircrafts_data a ON f.aircraft_code = a.aircraft_code 
WHERE f.flight_no = 'PG0003';

                             QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Nested Loop  (cost=5.44..387.10 rows=113 width=135) 
   −> Bitmap Heap Scan on flights f
      (cost=5.30..382.22 rows=113 width=63)
      Recheck Cond: (flight_no = 'PG0003'::bpchar)
      −> Bitmap Index Scan on flights_flight_no_scheduled_depart...
          (cost=0.00..5.27 rows=113 width=0)
          Index Cond: (flight_no = 'PG0003'::bpchar) 
   −> Memoize  (cost=0.15..0.27 rows=1 width=72)
       Cache Key: f.aircraft_code
       −> Index Scan using aircrafts_pkey on aircrafts_data a
           (cost=0.14..0.26 rows=1 width=72)
           Index Cond: (aircraft_code = f.aircraft_code)
(12 rows)

Для кеширования строк выделяется память процесса размером work_mem × hash_mem_multiplier. Как следует из названия второго параметра (по умолчанию равного 1.0), внутри для поиска строк используется хеш-таблица (вариант с открытой адресацией). Ключом хеширования (Cache Key) служит значение параметра (или набор значений параметров, если их несколько).

Кроме того, все ключи хеширования связаны в список, один конец которого считается «холодным» (ключи, давно не использованные), а другой — «горячим» (ключи, использованные недавно).

Если при обращении к узлу Memoize оказывается, что строки, соответствующие переданным значениям параметров, находятся в кеше, они возвращаются родительскому узлу (Nested Loop) без обращения к дочернему узлу. А использованный ключ хеширования передвигается в «горячий» конец списка.

Если же в кеше нет нужных строк, узел Memoize получает строки от дочернего узла, сохраняет их в кеше и возвращает узлу выше. Новый ключ хеширования также помещается в «горячий» конец списка.

Пока кеш заполняется новыми данными, доступная память может исчерпаться. Чтобы освободить ее, из кеша удаляются строки, соответствующие ключу с «холодного» конца списка, то есть наиболее давно не использованному. Этот алгоритм вытеснения устроен иначе, чем алгоритм, используемый в буферном кеше, но выполняет ту же задачу.

Может оказаться, что каким-то значениям параметров соответствует так много строк, что они не помещаются полностью в кеш, даже если все остальные строки уже вытеснены. Тогда такие параметры пропускается — нет смысла запоминать лишь часть строк, поскольку при следующем обращении невозможно будет вернуть полную выборку, не обращаясь к дочернему узлу.

Оценки кардинальности и стоимости соединения ничем радикально не отличаются от того, что мы уже видели выше.

Однако следует учесть, что стоимость узла Memoize, показанная в плане, не имеет ничего общего с реальностью: это просто стоимость дочернего узла, увеличенная на значение cpu_tuple_cost.

На самом же деле стоимость должна быть меньше, чтобы этот узел имел смысл. С похожей ситуацией мы уже сталкивались на примере узла Materialize: «настоящая» стоимость вычисляется для повторного сканирования узла и не отображается в плане.

Стоимость повторного сканирования узла Memoize учитывает размер памяти, доступный для кеширования, и предполагаемый характер обращений к кешу. Расчет существенным образом опирается на оценку количества различных значений параметров, с которыми будет сканироваться внутренний набор строк. Получив такую оценку, можно прикинуть вероятность обнаружить строки в кеше и вероятность вытеснения строк из кеша. Доля попаданий в кеш уменьшают оценку стоимости, а потенциальные вытеснения — наоборот, увеличивают.

В детали вычисления этой оценки я вдаваться не буду.

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

В нашем примере выбираются рейсы по одному маршруту, который обслуживается одним типом самолета; поэтому ключ хеширования совпадает для всех обращений к узлу Memoize. Первый раз нужной строки не оказывается в кеше (Misses: 1), но все повторные обращения обслуживаются кешем (Hits: 112). На все про все хватило одного килобайта памяти.

EXPLAIN (analyze, costs off, timing off, summary off) 
SELECT *
FROM flights f
  JOIN aircrafts_data a ON f.aircraft_code = a.aircraft_code 
WHERE f.flight_no = 'PG0003';

                             QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Nested Loop (actual rows=113 loops=1) 
   −> Bitmap Heap Scan on flights f
       (actual rows=113 loops=1)
       Recheck Cond: (flight_no = 'PG0003'::bpchar)
       Heap Blocks: exact=2
       −> Bitmap Index Scan on flights_flight_no_scheduled_depart...
           (actual rows=113 loops=1)
           Index Cond: (flight_no = 'PG0003'::bpchar) 
   −> Memoize (actual rows=1 loops=113)
       Cache Key: f.aircraft_code
       Hits: 112 Misses: 1 Evictions: 0 Overflows: 0 Memory 
       Usage: 1kB
       −> Index Scan using aircrafts_pkey on aircrafts_data a
           (actual rows=1 loops=1)
           Index Cond: (aircraft_code = f.aircraft_code)
(15 rows)

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

Высокие значения в этих полях говорили бы о том, что выделенной под кеш памяти оказалось недостаточно, скорее всего из-за некорректной оценки количества разных значений параметров. В таких условиях применение узла Memoize может оказаться весьма затратным. В крайнем случае можно запретить планировщику использовать кеш с помощью параметра on enable_memoize.

Внешние соединения

Соединение вложенным циклом может применяться для левого внешнего соединения:

EXPLAIN SELECT * 
FROM ticket_flights tf
  LEFT JOIN boarding_passes bp ON bp.ticket_no = tf.ticket_no 
                              AND bp.flight_id = tf.flight_id
WHERE tf.ticket_no = '0005434026720';

                             QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Nested Loop Left Join  (cost=1.12..33.35 rows=3 width=57)
   Join Filter: ((bp.ticket_no = tf.ticket_no) AND (bp.flight_id = 
   tf.flight_id))
   −> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.57 rows=3 width=32)
       Index Cond: (ticket_no = '0005434026720'::bpchar) 
   −> Materialize  (cost=0.56..16.62 rows=3 width=25)
       −> Index Scan using boarding_passes_pkey on boarding_passe... 
           (cost=0.56..16.61 rows=3 width=25)
           Index Cond: (ticket_no = '0005434026720'::bpchar)
(10 rows)

Узел соединения вложенным циклом отображается здесь как Nested Loop Left Join. В этом примере планировщик выбрал непараметризованное соединение с фильтрацией: внутренний набор строк каждый раз сканируется одинаково (и поэтому «спрятан» за узлом материализации), а в качестве результата возвращаются строки, удовлетворяющие условию фильтрации (Join Filter).

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

Оценка стоимости не отличается от оценки для внутреннего соединения.

Надо, конечно, учитывать, что для внутреннего и внешнего соединений планировщик может выбрать разные планы. Даже для этого простого примера, если убедить планировщик использовать соединение вложенным циклом, можно увидеть разницу в фильтре Join Filter: для внешнего соединения нужно дополнительно проверять совпадение номеров билетов, чтобы получить корректный результат при отсутствии пары во внешнем наборе строк. Отсюда и небольшая разница в итоговой стоимости:

SET enable_mergejoin = off;
EXPLAIN SELECT * 
FROM ticket_flights tf
  JOIN boarding_passes bp ON bp.ticket_no = tf.ticket_no 
                         AND bp.flight_id = tf.flight_id
WHERE tf.ticket_no = '0005434026720';

                             QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Nested Loop  (cost=1.12..33.33 rows=3 width=57)
   Join Filter: (tf.flight_id = bp.flight_id)
   −> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.57 rows=3 width=32)
       Index Cond: (ticket_no = '0005434026720'::bpchar) 
   −> Materialize  (cost=0.56..16.62 rows=3 width=25)
       −> Index Scan using boarding_passes_pkey on boarding_passe... 
           (cost=0.56..16.61 rows=3 width=25)
           Index Cond: (ticket_no = '0005434026720'::bpchar)
(9 rows)

RESET enable_mergejoin;

Правое соединение не поддерживается, поскольку для алгоритма вложенного цикла внешний и внутренний наборы строк неравнозначны. Внешний набор строк просматривается полностью, но из внутреннего при индексном доступе читаются только строки, удовлетворяющие условию соединения. При этом часть строк может остаться непросмотренной.

Полное соединение также не поддерживается по тем же соображениям.

Анти- и полусоединения

Антисоединения и полусоединения похожи тем, что для каждой строки первого (внешнего) набора во втором (внутреннем) наборе достаточно искать лишь одну подходящую строку.

Антисоединение возвращает строки первого набора, если только для них не нашлось соответствия в другом наборе. Иными словами: если во втором наборе нашлась одна подходящая строка — строка из первого набора уже не попадет в результат, и дальше можно не проверять.

Антисоединение может использоваться для вычисления предиката NOT EXISTS. Модели самолетов, для которых не задана конфигурация салона:

EXPLAIN SELECT * 
FROM aircrafts a 
WHERE NOT EXISTS (
  SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code 
);

                             QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Nested Loop Anti Join  (cost=0.28..4.65 rows=1 width=40)
   −> Seq Scan on aircrafts_data ml  (cost=0.00..1.09 rows=9 widt... 
       −> Index Only Scan using seats_pkey on seats s
           (cost=0.28..5.55 rows=149 width=4)
           Index Cond: (aircraft_code = ml.aircraft_code) 
(5 rows)

Здесь антисоединение вложенным циклом отображается как узел Nested Loop Anti Join.

Но, конечно, это не единственный случай. Например, тот же план будет построен и для эквивалентного запроса, записанного иначе:

EXPLAIN SELECT a.* 
FROM aircrafts a
  LEFT JOIN seats s ON a.aircraft_code = s.aircraft_code 
WHERE s.aircraft_code IS NULL;

Полусоединение возвращает строки первого набора, если для них нашлось хотя бы одно соответствие во втором наборе (и снова, последующие совпадения можно не проверять — результат уже известен).

Полусоединение может использоваться для вычисления предиката EXISTS. Найдем теперь модели самолетов, в салоне которых есть места:

EXPLAIN SELECT * 
FROM aircrafts a 
WHERE EXISTS (
  SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code 
)

                             QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Nested Loop Semi Join  (cost=0.28..6.67 rows=9 width=40)
   −> Seq Scan on aircrafts_data ml  (cost=0.00..1.09 rows=9 widt... 
   −> Index Only Scan using seats_pkey on seats s
       (cost=0.28..5.55 rows=149 width=4)
       Index Cond: (aircraft_code = ml.aircraft_code) 
(5 rows)

Полусоединение вложенным циклом представлено узлом Nested Loop Semi Join.

В этом плане (и в планах выше для антисоединения) для таблицы seats указана обычная оценка строк (rows=149), хотя на самом деле достаточно получить всего одну. При выполнении запроса, конечно, цикл останавливается после первой строки (actual rows):

EXPLAIN (analyze, costs off, timing off, summary off) SELECT * 
FROM aircrafts a
WHERE EXISTS (
  SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code 
);

                         QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Nested Loop Semi Join (actual rows=9 loops=1)
   −> Seq Scan on aircrafts_data ml (actual rows=9 loops=1) 
   −> Index Only Scan using seats_pkey on seats s
       (actual rows=1 loops=9)
       Index Cond: (aircraft_code = ml.aircraft_code) 
       Heap Fetches: 0
(6 rows)

Оценка кардинальности полусоединения дается обычным образом, но кардинальность внутреннего набора строк считается равной единице. А для антисоединения рассчитанная селективность вычитается из единицы, как для отрицания.

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

Не эквисоединения

Алгоритм вложенного цикла позволяет соединять наборы строк по любому условию соединения.

Конечно, если внутренний набор строк является базовой таблицей, на этой таблице создан индекс, и оператор условия соединения входит в класс операторов этого индекса, то к внутреннему набору строк возможен эффективный доступ.

Но в любом случае остается вариант декартова произведения строк с фильтрацией по условию — и в этом случае условие может быть совершенно произвольным. Как, например, в этом запросе, выбирающем пары аэропортов, расположенных недалеко друг от друга:

CREATE EXTENSION earthdistance CASCADE;
EXPLAIN (costs off) SELECT * 
FROM airports a1
  JOIN airports a2 ON a1.airport_code != a2.airport_code
                  AND a1.coordinates <@> a2.coordinates < 100;

                             QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 Nested Loop
   Join Filter: ((ml.airport_code <> ml_1.airport_code) AND 
   ((ml.coordinates <@> ml_1.coordinates) < '100'::double precisi... 
   −> Seq Scan on airports_data ml
   −> Materialize
       −> Seq Scan on airports_data ml_1
(6 rows)

Параллельный режим

Соединение вложенным циклом может использоваться в параллельном режиме.

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

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

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_flight_id_status_idx on fligh...
       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.

Продолжение.

Теги:

Хабы: