Способы соединения
Соединение слиянием
16
Авторские права
© Postgres Professional, 2019–2024
Авторы: Егор Рогов, Павел Лузанов, Павел Толмачев, Илья Баштанов
Фото: Олег Бартунов (монастырь Пху и пик Бхрикути, Непал)
Использование материалов курса
Некоммерческое использование материалов курса (презентации,
демонстрации) разрешается без ограничений. Коммерческое
использование возможно только с письменного разрешения компании
Postgres Professional. Запрещается внесение изменений в материалы
курса.
Обратная связь
Отзывы, замечания и предложения направляйте по адресу:
Отказ от ответственности
Компания Postgres Professional не несет никакой ответственности за
любые повреждения и убытки, включая потерю дохода, нанесенные
прямым или непрямым, специальным или случайным использованием
материалов курса. Компания Postgres Professional не предоставляет
каких-либо гарантий на материалы курса. Материалы курса
предоставляются на основе принципа «как есть» и компания Postgres
Professional не обязана предоставлять сопровождение, поддержку,
обновления, расширения и изменения.
2
Темы
Алгоритм соединения слиянием
Вычислительная сложность
Соединение слиянием в параллельных планах
3
Слияние двух отсортированных наборов строк
Результат соединения автоматически отсортирован
Соединение слиянием
Merge Join
Sort
Seq Scan
Index Scan
либо
сортировка
либо
упорядоченные
данные
Третий, и последний, способ соединения — соединение слиянием.
Идея этого способа состоит в том, что два предварительно
отсортированных набора данных нетрудно объединить в один общий —
и точно так же отсортированный — набор. Похожим образом работает
узел Gather Merge.
Подготовительным этапом для соединения слиянием служит
сортировка обоих наборов строк. Сортировка — дорогая операция,
она имеет сложность O(N log N).
Но иногда этого этапа удается избежать, если можно сразу получить
отсортированные по нужным столбцам наборы строк, например, за счет
индексного доступа к таблице.
4
Слияние
namealbum_idid title year
6
4
5
2
1
2Abbey Road
The Beatles
A Day in the Life
Another Girl
All You Need Is Love
Act Naturally1969
1968
3 Across the Universe
3 Let It Be 1970
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
1 1Yellow Submarine All Together Now1969
Само слияние устроено просто. Сначала берем первые строки обоих
наборов и сравниваем их между собой. В данном случае мы сразу
нашли соответствие и можем вернуть первую строку результата:
(«Yellow Submarine», «All Together Now»).
Общий алгоритм таков: читаем следующую строку того набора, для
которого значение поля, по которому происходит соединение, меньше
(один набор «догоняет» другой). Если же значения одинаковы, как
в нашем примере, то читаем следующую строку второго (внутреннего)
набора.
5
Слияние
namealbum_idid title year
6
4
5
2
2Abbey Road
The Beatles
A Day in the Life
Another Girl
Act Naturally1969
1968
3 Across the Universe
3 Let It Be 1970
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
1 1Yellow Submarine All Together Now1969
1 All You Need Is Love
Вновь соответствие: («Yellow Submarine», «All You Need Is Love»).
Снова читаем следующую строку второго набора.
6
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
Слияние
namealbum_idid title year
6
4
5
2
2Abbey Road
The Beatles
A Day in the Life
Another Girl
Act Naturally1969
1968
3 Across the Universe
3 Let It Be 1970
1 1Yellow Submarine All Together Now1969
1 All You Need Is Love
В данном случае соответствия нет.
Поскольку 1 < 2, читаем следующую строку первого набора.
7
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
Слияние
namealbum_idid title year
6
4
5
2
2Abbey Road
The Beatles
A Day in the Life
Another Girl
Act Naturally1969
1968
3 Across the Universe
3 Let It Be 1970
1 1Yellow Submarine All Together Now1969
1 All You Need Is Love
Соответствия нет.
3 > 2, поэтому читаем следующую строку второго набора.
8
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
Слияние
namealbum_idid title year
6
4
5
2
2Abbey Road
The Beatles
A Day in the Life
Another Girl
Act Naturally1969
1968
3 Across the Universe
3 Let It Be 1970
1 1Yellow Submarine All Together Now1969
1 All You Need Is Love
Снова нет соответствия, снова 3 > 2, снова читаем строку второго
набора.
9
Слияние
namealbum_idid title year
6
4
5
2
2Abbey Road
The Beatles
A Day in the Life
Another Girl
Act Naturally1969
1968
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
1 1Yellow Submarine All Together Now1969
1 All You Need Is Love3 Let It Be 1970
3 Across the Universe
Есть соответствие: («Let It Be», «Across the Universe»).
3 = 3, читаем следующую строку второго набора.
10
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
Слияние
namealbum_idid title year
6
4
5
2
2Abbey Road
The Beatles
A Day in the Life
Another Girl
Act Naturally1969
1968
3 Across the Universe
3 Let It Be 1970
1 1Yellow Submarine All Together Now1969
1 All You Need Is Love
Соответствия нет.
3 < 5, читаем строку первого набора.
11
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
Слияние
namealbum_idid title year
6
4
5
2
2Abbey Road
The Beatles
A Day in the Life
Another Girl
Act Naturally1969
1968
3 Across the Universe
3 Let It Be 1970
1 1Yellow Submarine All Together Now1969
1 All You Need Is Love
Соответствия нет.
4 < 5, читаем строку первого набора.
12
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
Слияние
namealbum_idid title year
6
4
5
2
2Abbey Road
The Beatles
A Day in the Life
Another Girl
Act Naturally1969
1968
3 Across the Universe
3 Let It Be 1970
1 1Yellow Submarine All Together Now1969
1 All You Need Is Love
И последний шаг: снова нет соответствия.
На этом соединение слиянием окончено.
На самом деле алгоритм сложнее — если в первом (внешнем) наборе
строк встречается несколько одинаковых значений, нужно иметь
возможность перечитать строки второго (внутреннего) набора
с тем же ключом соединения.
Псевдокод алгоритма можно посмотреть в файле
src/backend/executor/nodeMergejoin.c.
Важно, что алгоритм слияния возвращает результат соединения
в отсортированном виде. В частности, полученный набор строк
можно использовать для следующего соединения слиянием без
дополнительной сортировки.
14
Вычислительная сложность
~ N+M, где
N и M — число строк в первом и втором наборах данных,
если не требуется сортировка
~ NlogN+Mlog M,
если сортировка нужна
Возможные начальные затраты на сортировку
Эффективно для большого числа строк
В случае, когда не требуется сортировать данные, общая сложность
соединения слиянием пропорциональна сумме числа строк в обоих
наборах данных. Но, в отличие от соединения хешированием, здесь
не требуются накладные расходы на построение хеш-таблицы.
Поэтому соединение слиянием может успешно применяться как
в OLTP-, так и в OLAP-запросах.
Однако если сортировка требуется, то стоимость становится
пропорциональной произведению количества строк на логарифм этого
количества, и на больших объемах такой способ скорее всего
проиграет соединению хешированием.
16
Внешний набор строк сканируется параллельно,
внутренний — последовательно каждым процессом
В параллельных планах
Merge Join
Parallel
Index Scan
Gather
Merge Join
Parallel
Index Scan
Merge Join
Parallel
Index Scan
Sort
Seq Scan
Sort
Seq Scan
Sort
Seq Scan
Соединение слиянием может использоваться в параллельных планах.
Так же, как и при соединении вложенным циклом, сканирование одного
набора строк выполняется рабочими процессами параллельно,
но другой набор строк каждый рабочий процесс читает полностью
самостоятельно. Поэтому при соединении больших объемов строк
в параллельных планах гораздо чаще используется соединение
хешированием, имеющее эффективный параллельный алгоритм.
17
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
В параллельных планах
namealbum_id
id title year
1 Yellow Submarine
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
6 Abbey Road 1969
4 The Beatles
1968
3 Let It Be 1970
Parallel Index Scan
Внутренний набор данных будет просканирован каждым из рабочих
процессов от начала и до того момента, как станет понятно, что больше
нет соответствий.
На этом слайде показаны строки, перебираемые первым процессом.
18
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
В параллельных планах
namealbum_id
id title year
1 Yellow Submarine
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
6 Abbey Road 1969
4 The Beatles
1968
3 Let It Be 1970
Второй процесс просканирует весь набор и найдет одно соответствие.
19
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
В параллельных планах
namealbum_id
id title year
1 Yellow Submarine
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
6 Abbey Road 1969
4 The Beatles
1968
3 Let It Be 1970
А третий процесс не обнаружит ни одного соответствия.
Конечно, все три процесса сканируют внутренний набор одновременно,
а не по очереди.
21
Итоги
Соединение слиянием может потребовать подготовки
надо отсортировать наборы строк
или получить их заранее отсортированными
Эффективно для больших выборок
хорошо, если наборы уже отсортированы
хорошо, если нужен отсортированный результат
Не зависит от порядка соединения
Поддерживает только эквисоединения
другие не реализованы, но принципиальных ограничений нет
Чтобы начать соединение слиянием, оба набора строк должны быть
отсортированы. Хорошо, если удается получить данные уже в нужном
порядке; если нет — требуется выполнить сортировку.
Само слияние выполняется очень эффективно даже для больших
наборов строк. В качестве приятного бонуса результирующая выборка
тоже упорядочена, поэтому такой способ соединения привлекателен,
если вышестоящим узлам плана также требуется сортировка
(например, запрос с фразой ORDER BY или еще одна сортировка
слиянием).
Итак, в распоряжении планировщика есть три способа соединения:
вложенный цикл, хеширование и слияние (не считая различных
модификаций). Для каждого способа есть ситуации, в которых он
оказывается более эффективным, чем остальные. Это позволяет
планировщику выбрать именно тот способ, который — как
предполагается — лучше подойдет в каждом конкретном случае.
А точность предположений напрямую зависит от имеющейся
статистики.
22
Практика
1. Проверьте план выполнения запроса, показывающего все
места в салонах в порядке кодов самолетов:
SELECT * FROM aircrafts a
JOIN seats s ON a.aircraft_code = s.aircraft_code
ORDER BY a.aircraft_code;
Но оформите его в виде курсора.
Уменьшите значение параметра cursor_tuple_fraction
в десять раз. Как при этом изменился план выполнения?
2. Самолет можно заменить другим, если его вместимость
отличается не более, чем на 20%. Получите таблицу замен
между моделями Боинг и Аэробус, выполнив полное
соединение. Как выполняется запрос?
2. Запрос, который нужно выполнить:
WITH cap AS (
SELECT a.model, count(*)::numeric capacity
FROM aircrafts a
JOIN seats s ON a.aircraft_code = s.aircraft_code
GROUP BY a.model
), a AS (
SELECT * FROM cap WHERE model LIKE 'Аэробус%'
), b AS (
SELECT * FROM cap WHERE model LIKE 'Боинг%'
)
SELECT a.model AS airbus, b.model AS boeing
FROM a FULL JOIN b
ON b.capacity::numeric/a.capacity BETWEEN 0.8 AND 1.2
ORDER BY 1,2;
