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