Оптимизация запросов
Соединение слиянием
13
Авторские права
© Postgres Professional, 2019–2022
Авторы: Егор Рогов, Павел Лузанов, Павел Толмачев, Илья Баштанов
Использование материалов курса
Некоммерческое использование материалов курса (презентации,
демонстрации) разрешается без ограничений. Коммерческое
использование возможно только с письменного разрешения компании
Postgres Professional. Запрещается внесение изменений в материалы
курса.
Обратная связь
Отзывы, замечания и предложения направляйте по адресу:
Отказ от ответственности
Компания Postgres Professional не несет никакой ответственности за
любые повреждения и убытки, включая потерю дохода, нанесенные
прямым или непрямым, специальным или случайным использованием
материалов курса. Компания Postgres Professional не предоставляет
каких-либо гарантий на материалы курса. Материалы курса
предоставляются на основе принципа «как есть» и компания Postgres
Professional не обязана предоставлять сопровождение, поддержку,
обновления, расширения и изменения.
2
Темы
Соединение слиянием
Сортировка
3
Соединение слиянием
Алгоритм соединения слиянием
Вычислительная сложность
Соединение слиянием в параллельных планах
4
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_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.album_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.album_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.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, читаем следующую строку первого набора.
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
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, снова читаем строку второго
набора.
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.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, читаем следующую строку второго набора.
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
Соответствия нет.
3 < 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
Соответствия нет.
4 < 5, читаем строку первого набора.
13
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
И последний шаг: снова нет соответствия.
На этом соединение слиянием окончено.
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
Соединение слиянием может использоваться в параллельных планах.
Так же, как и при соединении вложенным циклом, сканирование одного
набора строк выполняется рабочими процессами параллельно,
но другой набор строк каждый рабочий процесс читает полностью
самостоятельно. Поэтому при соединении больших объемов строк
в параллельных планах гораздо чаще используется соединение
хешированием, имеющее эффективный параллельный алгоритм.
18
Сортировка
Сортировка в памяти
Внешняя сортировка
Группировка с помощью сортировки
Сортировка в параллельных планах
19
Быстрая сортировка (quick sort)
Частичная пирамидальная сортировка (top-N heapsort)
когда нужна только часть значений
Инкрементальная сортировка
когда данные уже отсортированы, но не по всем ключам
Сортировка в памяти
В идеальном случае набор строк, подлежащий сортировке, целиком
помещается в память, ограниченную параметром work_mem. В этом
случае все строки просто сортируются алгоритмом быстрой
сортировки (quick sort) и результат возвращается вышестоящему узлу.
Если нужно отсортировать не весь набор данных, а только его часть
(при использовании предложения LIMIT), может применяться
частичная пирамидальная сортировка (top-N heapsort).
Если набор данных требуется отсортировать по ключам K1 ... Km ... Kn
и при этом известно, что набор уже отсортирован по первым m ключам,
можно не пересортировывать все данные заново. Достаточно разбить
набор данных на группы, имеющие одинаковые значения начальных
ключей K1 ... Km (значения таких групп следуют друг за другом), и затем
отсортировать отдельно каждую из групп по оставшимся ключам
Km+1 ... Kn. Такой способ называется инкрементальной сортировкой.
Поскольку сортируемые наборы данных уменьшаются, уменьшается и
требование к доступному объему памяти.
21
work_mem
Внешняя сортировка
namealbum_id
5
1
2
1
2
A Day in the Life
All Together Now
Another Girl
All You Need Is Love
Act Naturally
3 Across the Universe
5
1
A Day in the Life
All Together Now
quicksort
2 Another Girl
5
1
A Day in the Life
All Together Now
2 Another Girl
В идеальном случае набор строк, подлежащий сортировке, целиком
помещается в память, ограниченную параметром work_mem. В этом
случае все строки просто сортируются (используется алгоритм быстрой
сортировки qsort) и возвращается результат.
Если набор строк велик, он не поместится в память целиком. В таком
случае используется алгоритм внешней сортировки.
Набор строк читается в память, пока есть возможность, затем
сортируется и записывается во временный файл.
22
work_mem
Внешняя сортировка
namealbum_id
5
1
2
1
2
A Day in the Life
All Together Now
Another Girl
All You Need Is Love
Act Naturally
3 Across the Universe
quicksort
1
2
All You Need Is Love
Act Naturally
3 Across the Universe
1
2
All You Need Is Love
Act Naturally
3 Across the Universe5
1
A Day in the Life
All Together Now
2 Another Girl
temp_file_limit
Эта процедура повторяется столько раз, сколько необходимо, чтобы
записать все данные в файлы, каждый из которых по отдельности
отсортирован.
Напомним, что общий размер временных файлов сеанса (не включая
временные таблицы) ограничен значением параметра temp_file_limit.
23
work_mem
Внешняя сортировка
1 All You Need Is Love
1 All Together Now
слияние
1
2
All You Need Is Love
Act Naturally
3 Across the Universe5
1
A Day in the Life
All Together Now
2 Another Girl
Далее несколько файлов сливаются аналогично тому, как работает
соединение слиянием. Основное отличие состоит в том, что сливаться
могут более двух файлов одновременно.
Для слияния не требуется много места в памяти. Достаточно
разместить по одной строке из каждого файла (как в примере на
слайде). Среди этих строк выбирается минимальная (максимальная)
и возвращается как часть результата, а на ее место читается новая
строка из того же файла.
На практике строки читаются не по одной, а порциями, чтобы
оптимизировать ввод-вывод.
Если оперативной памяти недостаточно, чтобы слить сразу все файлы,
процесс повторяется многократно: сливаются по несколько файлов за
раз и результаты записываются в новые временные файлы, затем
происходит слияние этих новых файлов и так далее.
На самом деле, конечно, сортировка устроена сложней. С деталями
реализации можно познакомиться в файле
src/backend/utils/sort/tuplesort.c.
История развития способов сортировки в PostgreSQL хорошо описана
в презентации Грегори Старка «Sorting Through The Ages»:
25
Узел Gather Merge сохраняет порядок сортировки
выполняет слияние данных, поступающих от нижестоящих узлов
Параллельная сортировка
Gather Merge
Sort
Sort Sort
Сортировка может участвовать в параллельных планах. Каждый
рабочий процесс сортирует свою часть данных и передает результат
вышестоящему узлу, который собирает данные в единый набор.
Но узел Gather для этого не годится, поскольку он выдает результат
в том порядке, в котором строки поступают от рабочих процессов.
Поэтому в таких планах используется узел Gather Merge, сохраняющий
порядок сортировки поступающих строк. Для этого он реализует
алгоритм слияния, объединяя несколько отсортированных наборов
в один.
27
Создание индекса
Используется сортировка
сначала все строки сортируются
затем строки собираются в листовые индексные страницы
ссылки на них собираются в страницы следующего уровня
и так далее, пока не дойдем до корня
Может выполняться параллельно
max_parallel_maintenance_workers
Ограничение
maintenance_work_mem, так как операция не частая
Индекс (речь идет про B-дерево) можно строить, добавляя
последовательно в пустой индекс по одной строке из таблицы. Но такой
способ крайне неэффективен.
Поэтому при создании индекса используется сортировка: все строки
таблицы сортируются и раскладываются по листовым индексным
страницам. Затем достраиваются верхние уровни дерева, состоящие из
ссылок на элементы страниц нижележащего уровня, до тех пор, пока на
очередном уровне не получится одна страница — она и будет корнем
дерева.
Сортировка устроена точно так же, как рассматривалось выше. Однако
размер памяти ограничен не work_mem, а maintenance_work_mem,
поскольку операция создания индекса не слишком частая и имеет
смысл выделить для нее больше памяти.
Построение индекса может выполняться параллельно. Ограничение
на количество процессов накладывается значением параметра
max_parallel_maintenance_workers, хотя реальное количество может
выбрано и меньше. Ограничение на память действует для всех
запущенных процессов, а не для каждого из них по отдельности.
28
Итоги
Соединение слиянием может потребовать подготовки
надо отсортировать наборы строк
или получить их заранее отсортированными
Эффективно для больших выборок
хорошо, если наборы уже отсортированы
хорошо, если нужен отсортированный результат
Не зависит от порядка соединения
Поддерживает только эквисоединения
другие не реализованы, но принципиальных ограничений нет
Чтобы начать соединение слиянием, оба набора строк должны быть
отсортированы. Хорошо, если удается получить данные уже в нужном
порядке; если нет — требуется выполнить сортировку.
Само слияние выполняется очень эффективно даже для больших
наборов строк. В качестве приятного бонуса результирующая выборка
тоже упорядочена, поэтому такой способ соединения привлекателен,
если вышестоящим узлам плана также требуется сортировка
(например, запрос с фразой ORDER BY или еще одна сортировка
слиянием).
В настоящее время соединение слиянием поддерживает только
эквисоединения, соединения по операциям «больше» или «меньше»
не реализованы.
Итак, в распоряжении планировщика есть три способа соединения:
вложенный цикл, хеширование и слияние (не считая различных
модификаций). Есть ситуации, в которых каждый из способов
оказывается более эффективным, чем остальные. Это позволяет
планировщику выбрать именно тот способ, который — как
предполагается — лучше подойдет в каждом конкретном случае.
А точность предположений напрямую зависит от имеющейся
статистики.
29
Практика
1. Создайте индекс по столбцам passenger_name и passenger_id
таблицы билетов (tickets).
Потребовался ли временный файл для выполнения этой
операции?
2. Проверьте план выполнения запроса из демонстрации,
показывающего все места в салонах в порядке кодов
самолетов, но оформленного в виде курсора.
Уменьшите значение параметра cursor_tuple_fraction
в десять раз. Как при этом изменился план выполнения?
1. Включите журналирование использования временных файлов,
установив значение параметра log_temp_files в ноль.
2. Речь идет о запросе
SELECT *
FROM aircrafts a
JOIN seats s ON a.aircraft_code = s.aircraft_code
ORDER BY a.aircraft_code;
