Оптимизация запросов
Соединение вложенным циклом
13
Авторские права
© Postgres Professional, 2019–2022
Авторы: Егор Рогов, Павел Лузанов, Павел Толмачев, Илья Баштанов
Использование материалов курса
Некоммерческое использование материалов курса (презентации,
демонстрации) разрешается без ограничений. Коммерческое
использование возможно только с письменного разрешения компании
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
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
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.a_id;
3 Across the Universe
3 Let It Be
1970
album_id
Начнем с соединения вложенными циклами (nested loop), как с самого
простого. Его алгоритм таков: для каждой строки одного из наборов
перебираем и возвращаем соответствующие ему строки второго
набора. По сути, это два вложенных цикла, отсюда и название способа.
Заметим, что ко второму (внутреннему) набору мы будем обращаться
столько раз, сколько строк в первом (внешнем) наборе. Если нет
эффективного метода доступа для поиска соответствующих строк
во втором наборе (то есть, попросту говоря, индекса на таблице),
придется неоднократно перебирать большое количество строк, не
относящихся к делу. Очевидно, это будет не лучший выбор, хотя для
небольших наборов алгоритм и в этом случае может оказаться
достаточно эффективным.
Рисунки иллюстрируют этот способ соединения. На них:
- серым показаны строки, к которым ранее уже был доступ;
- строки, доступ к которым выполняется на текущем шаге, выделены
цветом;
- оранжевым контуром выделены строки, составляющие пару,
подходящую по условию соединения (в данном примере — по
равенству числовых идентификаторов).
Сначала мы читаем первую строку первого набора и находим ее пару
во втором наборе. Соответствие нашлось, и у нас уже есть первая
строка результата, которую можно вернуть вышестоящему узлу плана:
(«Let It Be», «Across the Universe»).
5
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.a_id;
1 Yellow Submarine 1 All Together Now1969
1 All You Need Is Love
Читаем вторую строку первого набора.
Для нее тоже перебираем пары из второго набора. Сначала
возвращаем («Yellow Submarine», «All Together Now»)...
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.a_id;
1 Yellow Submarine 1 All Together Now1969
1 All You Need Is Love
...затем вторую пару («Yellow Submarine», «All You Need Is Love»).
7
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.a_id;
Переходим к третьей строке первого набора. Для нее соответствий нет.
8
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
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.a_id;
Для четвертой строки тоже нет соответствий. На этом работа
соединения заканчивается.
Часть строк второго набора мы вообще не рассматривали — на рисунке
они остались белыми.
(С исходным кодом алгоритма можно познакомиться в файле
src/backend/executor/nodeNestloop.c.)
10
Вычислительная сложность
~ N ×M, где
N — число строк во внешнем наборе данных,
M — среднее число строк внутреннего набора,
приходящееся на одну итерацию
Соединение эффективно только для небольшого числа строк
Если принять за N число строк во внешнем наборе данных, а за M
среднее число строк внутреннего набора, приходящееся на одну
итерацию, то общая сложность соединения будет пропорциональна
произведению N × M.
Из-за этого метод соединения вложенным циклом эффективен только
для небольшого числа строк.
В частности, такой метод (в сочетании с индексным доступом)
характерен для OLTP-запросов, в которых надо очень быстро вернуть
очень небольшое число строк.
12
внешний набор строк
сканируется параллельно,
внутренний — последовательно
каждым рабочим процессом
5
2
2
A Day in the Life
Another Girl
Act Naturally
3 Across the Universe
1
1
All Together Now
All You Need Is Love
5
2
2
A Day in the Life
Another Girl
Act Naturally
3 Across the Universe
1
1
All Together Now
All You Need Is Love
id title year
namealbum_id
В параллельных планах
1
6
4
5
2
2
Yellow Submarine
Abbey Road
The Beatles
A Day in the Life
Another Girl
Act Naturally
3 Let It Be
3 Across the Universe
1
1
All Together Now
All You Need Is Love
1969
1969
1968
1970
album_id
Соединение вложенным циклом может использоваться в параллельных
планах.
Внешний набор строк сканируется несколькими рабочими процессами
параллельно. Получив строку из внешнего набора, процесс затем
перебирает соответствующие ему строки внутреннего набора
последовательно.
14
Итоги
Вложенный цикл не требует подготовительных действий
может отдавать результат соединения без задержек
Эффективен для небольших выборок
внешний набор строк не очень велик
к внутреннему есть эффективный доступ (обычно по индексу)
Зависит от порядка соединения
обычно лучше, если внешний набор меньше внутреннего
Поддерживает соединение по любому условию
как эквисоединения, так и любые другие
Сильной стороной способа соединения вложенными циклами является
его простота: не требуется никаких подготовительных действий, мы
можем начать возвращать результат практически моментально.
Обратная сторона состоит в том, что этот способ крайне неэффективен
для больших объемов данных. Ситуация та же, что и с индексами: чем
больше выборка, тем больше накладных расходов.
Таким образом, соединение вложенными циклами имеет смысл
применять, если:
- один из наборов строк небольшой;
- к другому набору есть эффективный доступ по условию соединения;
- общее количество строк результата невелико.
Это обычная ситуация для OLTP-запросов (например, запросов от
пользовательского интерфейса, где веб-страница или экранная форма
должны открыться быстро и не выводят большой объем информации).
Еще одна особенность, которую стоит отметить: соединение
вложенными циклами может работать для любого условия соединения.
Подходит как эквисоединение (по условию равенства, как в примере),
так и любое другое.
15
Практика
1. Создайте индекс на таблице рейсов (flights) по аэропортам
отправления (departure_airport).
Найдите все рейсы из Ульяновска и проверьте план
выполнения запроса.
2. Соедините любые две таблицы без указания условий
соединения (иными словами, выполните декартово
произведение таблиц).
Какой способ соединения будет выбран планировщиком?
3. Постройте таблицу расстояний между всеми аэропортами
(так, чтобы каждая пара встречалась только один раз).
Какой способ соединения используется в таком запросе?
3. Используйте оператор <@> из расширения earthdistance.