Способы соединения
Соединение вложенным циклом
16
Авторские права
© Postgres Professional, 2019–2024
Авторы: Егор Рогов, Павел Лузанов, Павел Толмачев, Илья Баштанов
Фото: Олег Бартунов (монастырь Пху и пик Бхрикути, Непал)
Использование материалов курса
Некоммерческое использование материалов курса (презентации,
демонстрации) разрешается без ограничений. Коммерческое
использование возможно только с письменного разрешения компании
Postgres Professional. Запрещается внесение изменений в материалы
курса.
Обратная связь
Отзывы, замечания и предложения направляйте по адресу:
Отказ от ответственности
Компания Postgres Professional не несет никакой ответственности за
любые повреждения и убытки, включая потерю дохода, нанесенные
прямым или непрямым, специальным или случайным использованием
материалов курса. Компания Postgres Professional не предоставляет
каких-либо гарантий на материалы курса. Материалы курса
предоставляются на основе принципа «как есть» и компания Postgres
Professional не обязана предоставлять сопровождение, поддержку,
обновления, расширения и изменения.
2
Темы
Общие соображения о соединениях
Соединение вложенным циклом
Модификации: левые, полу- и анти- соединения
Вычислительная сложность
Вложенный цикл в параллельных планах
3
Соединения
Способы соединения — не соединения SQL
inner/left/right/full/cross join, in, exists — логические операции
способы соединения — механизм реализации
Соединяются не таблицы, а наборы строк
могут быть получены от любого узла дерева плана
Наборы строк соединяются попарно
порядок соединений важен с точки зрения производительности
обычно важен и порядок внутри пары
Мало получать данные с помощью рассмотренных методов доступа,
надо еще и уметь соединять их. Для этого PostgreSQL предоставляет
несколько способов.
Способы соединения представляют собой алгоритмы для соединения
двух наборов строк. С их помощью реализуются и другие конструкции
языка SQL, например, EXISTS. Не стоит путать одно с другим: SQL-
соединения — это логические операции над двумя множествами;
способы соединения PostgreSQL — это возможные реализации таких
соединений, учитывающие производительность.
Часто можно услышать, что соединяются таблицы. Это удобное
упрощение, но на самом деле в общем случае соединяются наборы
строк. Эти наборы действительно могут быть получены
непосредственно из таблицы (с помощью одного из методов доступа),
но с тем же успехом могут, например, являться результатом соединения
других наборов строк.
Наконец, наборы строк всегда соединяются попарно. Порядок,
в котором соединяются таблицы, не важен с точки зрения логики
запроса (например, (a join b) join c или (b join c) join a),
но очень важен с точки зрения производительности. Как мы увидим
дальше, важен и порядок, в котором соединяются два набора строк
(a join b или b join a).
4
Для каждой строки одного набора
перебираем подходящие строки другого набора
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
Nested Loop
Nested Loop
Index Scan
on songs
Seq Scan
on albums
внешний
набор
внутренний
набор
Начнем с соединения вложенными циклами (nested loop), как с самого
простого. Его алгоритм таков: для каждой строки одного из наборов
перебираем и возвращаем соответствующие ему строки второго
набора. По сути, это два вложенных цикла, отсюда и название способа.
Заметим, что ко второму (внутреннему) набору мы будем обращаться
столько раз, сколько строк в первом (внешнем) наборе. Если нет
эффективного метода доступа для поиска соответствующих строк
во втором наборе (то есть, попросту говоря, индекса на таблице),
придется неоднократно перебирать большое количество строк, не
относящихся к делу. Очевидно, это будет не лучший выбор, хотя для
небольших наборов алгоритм и в этом случае может оказаться
достаточно эффективным.
В плане запроса мы будем видеть узел Nested Loop с двумя дочерними
узлами (которые могут представлять не только методы доступа,
но и другие операции, например, соединения или агрегации).
5
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
nameid title year
Nested Loop
1
6
4
5
1
2
1
2
Yellow Submarine
Abbey Road
The Beatles
A Day in the Life
All Together Now
Another Girl
All You Need Is Love
Act Naturally
1969
1969
1968
3 Across the Universe
3 Let It Be
1970
album_id
Рисунки иллюстрируют этот способ соединения. На них:
•
строки, к которым ранее уже был доступ, показаны серым;
•
строки, доступ к которым выполняется на текущем шаге, выделены
цветом;
•
оранжевым контуром выделены строки, составляющие пару,
подходящую по условию соединения (в данном примере —
по равенству числовых идентификаторов).
Сначала мы читаем первую строку первого набора и находим ее пару
во втором наборе. Соответствие нашлось, и у нас уже есть первая
строка результата, которую можно вернуть вышестоящему узлу плана:
(«Let It Be», «Across the Universe»).
6
namealbum_idid title year
Nested Loop
6
4
5
2
2
Abbey Road
The Beatles
A Day in the Life
Another Girl
Act Naturally
3 Let It Be
3 Across the Universe
1969
1968
1970
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
1 Yellow Submarine 1 All Together Now1969
1 All You Need Is Love
Читаем вторую строку первого набора.
Для нее тоже перебираем пары из второго набора. Сначала
возвращаем («Yellow Submarine», «All Together Now»)...
7
namealbum_idid title year
Nested Loop
6
4
5
2
2
Abbey Road
The Beatles
A Day in the Life
Another Girl
Act Naturally
3 Let It Be
3 Across the Universe
1969
1968
1970
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
1 Yellow Submarine 1 All Together Now1969
1 All You Need Is Love
...затем вторую пару («Yellow Submarine», «All You Need Is Love»).
8
namealbum_idid title year
Nested Loop
3
1
4
Let It Be
Yellow Submarine
The Beatles
5
2
2
A Day in the Life
Another Girl
Act Naturally
1 All Together Now
3
1
Across the Universe
All You Need Is Love
6 Abbey Road
1969
1969
1968
1970
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
Переходим к третьей строке первого набора. Для нее соответствий нет.
9
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
namealbum_idid title year
Nested Loop
3
1
6
4
Let It Be
Yellow Submarine
Abbey Road
The Beatles
5
2
2
A Day in the Life
Another Girl
Act Naturally
1 All Together Now
3
1
Across the Universe
All You Need Is Love
не все строки
внутреннего набора
были прочитаны
1969
1969
1968
1970
Для четвертой строки тоже нет соответствий. На этом работа
соединения заканчивается.
Часть строк второго набора мы вообще не рассматривали — на рисунке
они остались белыми.
(С исходным кодом алгоритма можно ознакомиться в файле
src/backend/executor/nodeNestloop.c.)
11
Кеширование повторяющихся данных внутреннего набора
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
Мемоизация
Nested Loop
Memoize
Seq Scan
on songs
кеширование
Index Scan
on albums
Если внутренний набор сканируется много раз с повторяющимися
значениями параметров, иногда имеет смысл закешировать результат,
чтобы не читать много раз одни и те же данные. Эта операция
называется мемоизацией. Она выполняется в узле Memoize, который
встраивается между Nested Loop и узлом, поставляющим данные.
(Если планировщик ошибается в своих расчетах, мемоизацию можно
отключить, установив параметр enable_memoize в значение off.)
Для кеширования используется хеш-таблица. Ключом хеширования
служит параметр или несколько параметров, с которыми выполняется
обращение к внутреннему набору.
12
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
name id title year
Мемоизация
1
1
3
It’s All Too Much
All Together Now
Across the Universe
1 All You Need Is Love
album_id
1
6
4
Yellow Submarine
Abbey Road
The Beatles
3 Let It Be
1969
1969
1968
1970
2
8
5
Help!
Revolver
A Hard Day’s Night
7 Please Please Me
1965
1966
1964
1963
1 Yellow Submarine
2 Another Girl
значения
повторяются
work_mem ×
hash_mem_multiplier
в общем случае –
несколько строк
Рассмотрим пример. В отличие от предыдущего, здесь песен меньше,
чем альбомов; к тому же, почти все они относятся к одному и тому же
альбому.
Если необходимой строки нет в хеш-таблице, узел Memoize читает ее
из внутреннего набора, сохраняет в кеше и возвращает родительскому
узлу Nested Loop.
В общем случае значению параметра могут соответствовать несколько
строк из внутреннего набора — будут закешированы все эти строки.
Если все они не помещаются в память (которая ограничена размером
work_mem × hash_mem_multiplier), значение параметра игнорируется,
поскольку кешировать только часть строк нет смысла. В плане запроса
количество таких ситуаций будет показано как overflow.
13
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
name id title year
Мемоизация
1
1
3
It’s All Too Much
All Together Now
Across the Universe
1 All You Need Is Love
album_id
1
6
4
Yellow Submarine
Abbey Road
The Beatles
3 Let It Be
1969
1969
1968
1970
2
8
5
Help!
Revolver
A Hard Day’s Night
7 Please Please Me
1965
1966
1964
1963
1 Yellow Submarine
2 Another Girl
work_mem ×
hash_mem_multiplier
Если необходимая строка уже есть в кеше, узел Memoize сразу
возвращает ее узлу Nested Loop. Обращения к внутреннему набору не
происходит.
14
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
name id title year
Мемоизация
1
1
3
It’s All Too Much
All Together Now
Across the Universe
1 All You Need Is Love
album_id
1
6
4
Yellow Submarine
Abbey Road
The Beatles
3 Let It Be
1969
1969
1968
1970
2
8
5
Help!
Revolver
A Hard Day’s Night
7 Please Please Me
1965
1966
1964
1963
3 Let It Be
2 Another Girl
1 All You Need Is Love
1 Yellow Submarine
добавляется
в начало
work_mem ×
hash_mem_multiplier
Пока в кеше хватает места, новые значения продолжают кешироваться.
При этом новое значение добавляется в начало кеша.
15
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
name id title year
Мемоизация
1
1
3
It’s All Too Much
All Together Now
Across the Universe
1 All You Need Is Love
album_id
1
6
4
Yellow Submarine
Abbey Road
The Beatles
3 Let It Be
1969
1969
1968
1970
2
8
5
Help!
Revolver
A Hard Day’s Night
7 Please Please Me
1965
1966
1964
1963
1 Yellow Submarine
2 Another Girl
1 All You Need Is Love
3 Let it Be
work_mem ×
hash_mem_multiplier
свежее
всплывает
Уже закешированное значение «всплывает наверх», когда к нему
обращаются, а остальные, соответственно, опускаются вниз.
16
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
name id title year
Мемоизация
1
1
3
It’s All Too Much
All Together Now
Across the Universe
1 All You Need Is Love
album_id
1
6
4
Yellow Submarine
Abbey Road
The Beatles
3 Let It Be
1969
1969
1968
1970
2
8
5
Help!
Revolver
A Hard Day’s Night
7 Please Please Me
1965
1966
1964
1963
2 Help!
2 Another Girl
1 All You Need Is Love
1 Yellow Submarine
старое
отбрасывается
Если память заканчивается, из кеша удаляются «нижние» строки,
к которым дольше всего не было обращений. Таким образом
реализуется алгоритм вытеснения LRU.
18
Вычислительная сложность
~ N ×M, где
N — число строк во внешнем наборе данных,
M — среднее число строк внутреннего набора,
приходящееся на одну итерацию
Соединение эффективно только для небольшого числа строк
Если принять за N число строк во внешнем наборе данных, а за M —
среднее число строк внутреннего набора, приходящееся на одну
итерацию, то общая сложность соединения будет пропорциональна
произведению N × M.
Для непараметризованного соединения M будет в точности равно числу
строк внутреннего набора; для параметризованного — M может быть
значительно меньше.
Метод соединения вложенным циклом эффективен только для
небольшого числа строк. В частности, такой метод (в сочетании
с индексным доступом) характерен для OLTP-запросов, в которых надо
очень быстро вернуть мало строк.
20
В параллельных планах
Внешний набор строк сканируется параллельно,
внутренний — последовательно каждым процессом
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
Nested Loop
Index Scan
on songs
Parallel Seq Scan
on albums
Nested Loop
Index Scan
on songs
Parallel Seq Scan
on albums
Nested Loop
Index Scan
on songs
Parallel Seq Scan
on albums
Gather
Соединение вложенным циклом может использоваться в параллельных
планах.
Внешний набор строк сканируется несколькими рабочими процессами
параллельно. Получив строку из внешнего набора, процесс затем
перебирает соответствующие ему строки внутреннего набора
последовательно.
21
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
В параллельных планах
namealbum_id
id title year
3 Let It Be
5
2
2
A Day in the Life
Another Girl
Act Naturally
1 All Together Now
3
1
Across the Universe
All You Need Is Love
1970
4 The Beatles 1968
6
2
Abbey Road
Help!
1969
1965
8 Revolver 1966
1 Yellow Submarine 1969
Parallel Seq Scan
Чтобы получить очередную страницу из внешнего набора, процессы
синхронизируются. К внутреннему набору данных каждый процесс
обращается независимо от остальных.
23
Итоги
Вложенный цикл не требует подготовительных действий
может отдавать результат соединения без задержек
Эффективен для небольших выборок
внешний набор строк не очень велик
к внутреннему есть эффективный доступ (обычно по индексу)
Зависит от порядка соединения
обычно лучше, если внешний набор меньше внутреннего
Поддерживает соединение по любому условию
как эквисоединения, так и любые другие
Сильной стороной способа соединения вложенными циклами является
его простота: не требуется никаких подготовительных действий, мы
можем начать возвращать результат практически моментально.
Обратная сторона состоит в том, что этот способ крайне неэффективен
для больших объемов данных. Ситуация та же, что и с индексами: чем
больше выборка, тем больше накладных расходов.
Таким образом, соединение вложенными циклами имеет смысл
применять, если:
●
один из наборов строк небольшой;
●
к другому набору есть эффективный доступ по условию соединения;
●
общее количество строк результата невелико.
Это обычная ситуация для OLTP-запросов (например, запросов от
пользовательского интерфейса, где веб-страница или экранная форма
должны открыться быстро и не выводят большой объем информации).
Еще одна особенность, которую стоит отметить: соединение
вложенными циклами может работать для любого условия соединения.
Подходит как эквисоединение (по условию равенства, как в примере),
так и любое другое.
24
Практика
1. Создайте индекс на таблице рейсов (flights) по аэропортам
отправления (departure_airport).
Найдите все рейсы из Ульяновска и проверьте план
выполнения запроса.
2. Постройте таблицу расстояний между всеми аэропортами
(так, чтобы каждая пара встречалась только один раз).
Какой способ соединения используется в таком запросе?
2. Используйте оператор <@> из расширения earthdistance.
