Оптимизация запросов
Соединение хешированием
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;
Построение хеш-таблицы
1
6
4
Yellow Submarine
Abbey Road
The Beatles
3 Let It Be
1969
1969
1968
1970
3
6
Let It Be
Abbey Road
4 The Beatles
10100001
10001001
01000100
1 Yellow Submarine11000111
id title year
01
10
00
11
номер
корзины
work_mem × hash_mem_multiplier
id titleхеш-код
участвует
в условии
соединения
используется
в запросе
внутренний набор
Первым этапом в памяти строится хеш-таблица.
Идея хеширования состоит в том, что функция хеширования
равномерно распределяет значения по ограниченному числу корзин
хеш-таблицы. В таком случае разные значения как правило будут
попадать в разные корзины. Если равномерности не будет, в одну
корзину может попасть много значений. В таком случае они
выстраиваются в список, и по мере увеличения длины списка
эффективность поиска по хеш-таблице будет падать.
Итак, строки первого набора читаются последовательно, и для каждой
из них вычисляется хеш-функция от значения полей, входящих
в условие соединения (в нашем примере — числовые
идентификаторы).
По значению хеш-функции определяется номер корзины. Например,
если используется 4 корзины, то в качестве номера корзины можно
взять два младших бита.
В корзину хеш-таблицы помещаются вычисленный хеш-код и все поля,
которые входят в условие соединения или используются в запросе.
Размер хеш-таблицы в памяти ограничен значением work_mem ×
× hash_mem_multiplier. Наилучшая эффективность достигается, если
вся хеш-таблица помещается в этот объем памяти целиком. (Это еще
одна причина не использовать в запросе лишние поля, в том числе,
«звездочку».)
Исходный код алгоритма можно найти в файле
src/backend/executor/nodeHashjoin.c.
5
Сопоставление
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
5
2
1
2
A Day in the Life
Another Girl
All You Need Is Love
Act Naturally
1 All Together Now
3 Across the Universe
11000100
01
10
00
11
namealbum_id
3
6
Let It Be
Abbey Road
4 The Beatles
10100001
10001001
01000100
1 Yellow Submarine11000111
id titleхеш-код
внешний набор
work_mem × hash_mem_multiplier
На втором этапе мы последовательно читаем второй набор строк.
По мере чтения мы вычисляем хеш-функцию от значения полей,
участвующих в условии соединения. Если в соответствующей корзине
хеш-таблицы обнаруживается строка
- с таким же хеш-кодом,
- и со значениями полей, подходящими под условие соединения,
то мы нашли пару.
Проверки одного только хеш-кода недостаточно. Во-первых, не все
условия соединения, перечисленные в запросе, могут быть учтены при
выполнении соединения хешированием (поддерживаются только
эквисоединения). Во-вторых, возможны коллизии, при которых разные
значения получат одинаковые хеш-коды (вероятность этого мала, но
тем не менее она есть).
В нашем примере для первой строки соответствия нет.
6
Сопоставление
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
5
2
1
2
A Day in the Life
Another Girl
All You Need Is Love
Act Naturally
3 Across the Universe
11000111
01
10
00
11
namealbum_id
1 All Together Now
3
6
Let It Be
Abbey Road
4 The Beatles
10100001
10001001
01000100
1 Yellow Submarine11000111
id titleхеш-код
Вторая строка второго набора дает соответствие, которое уже можно
вернуть вышестоящему узлу плана: («Yellow Submarine», «All Together
Now»).
7
Сопоставление
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
5
2
1
2
A Day in the Life
Another Girl
All You Need Is Love
Act Naturally
1 All Together Now
3 Across the Universe
11110110
01
10
00
11
namealbum_id
3
6
Let It Be
Abbey Road
4 The Beatles
10100001
10001001
01000100
1 Yellow Submarine11000111
id titleхеш-код
Для третьей строки соответствия нет оответствующая корзина хеш-
таблицы пуста).
8
Сопоставление
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
5
2
1
2
A Day in the Life
Another Girl
All You Need Is Love
Act Naturally
10100001
01
10
00
11
namealbum_id
1 All Together Now
6 Abbey Road
4 The Beatles
10001001
01000100
1 Yellow Submarine11000111
3 Across the Universe
3 Let It Be10100001
id titleхеш-код
Для четвертой получаем соответствие («Let It Be», «Across the
Universe»).
Заметим, что в корзине хеш-таблицы оказалось две строки первого
набора, и в общем случае их придется просмотреть обе.
9
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
Сопоставление
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
5
2
2
A Day in the Life
Another Girl
Act Naturally
3 Across the Universe
11000111
01
10
00
11
namealbum_id
1 All Together Now
3
6
Let It Be
Abbey Road
4 The Beatles
10100001
10001001
01000100
1 Yellow Submarine11000111
1 All You Need Is Love
id titleхеш-код
Для пятой строки получаем соответствие («Yellow Submarine», «All You
Need Is Love»).
10
SELECT a.title, s.name
FROM albums a JOIN songs s ON a.id = s.album_id;
Сопоставление
5
2
1
2
A Day in the Life
Another Girl
All You Need Is Love
Act Naturally
1 All Together Now
3 Across the Universe
11110110
01
10
00
11
namealbum_id
3
6
Let It Be
Abbey Road
4 The Beatles
10100001
10001001
01000100
1 Yellow Submarine11000111
id titleхеш-код
Для шестой строки соответствия нет. На этом работа соединения
завершена.
12
Двухпроходное соединение
Применяется, когда хешаблица не помещается
в оперативную память: наборы данных разбиваются
на пакеты и последовательно соединяются
13
id title year
Построение хеш-таблицы
work_mem × hash_mem_multiplier
временные
файлы для
внутреннего
набора
пакет
2
пакет
3
пакет
4
хеш-таблица
(пакет 1)
Если хеш-таблица не помещается в объем памяти, ограниченный
work_mem × hash_mem_multiplier, первый (внутренний) набор строк
разбивается на отдельные пакеты. Для распределения по пакетам
используется некоторое количество битов хеш-кода, поэтому число
пакетов всегда кратно двум. В идеале в каждый пакет попадает
примерно одинаковое количество строк, но, если значения в строках
повторяются, возможен перекос.
При планировании запроса заранее вычисляется минимально
необходимое число пакетов так, чтобы хеш-таблица для каждого пакета
помещалась в памяти. Это число не уменьшается, даже если
оптимизатор ошибся с оценками, но при необходимости может
динамически увеличиваться.
Хеш-таблица для первого пакета остается в памяти, а строки,
принадлежащие другим пакетам, сбрасываются на диск во временные
файлы — каждый пакет в свой файл.
На рисунке показано четыре пакета.
14
пакет
2
пакет
3
пакет
4
namealbum_id
Сопоставление – пакет 1
хеш-таблица
(пакет 1)
пакет
2
пакет
3
пакет
4
временные
файлы для
внешнего
набора
temp_file_limit
Далее читается второй (внешний) набор строк. Если строка
принадлежит первому пакету, она сопоставляется с хеш-таблицей,
которая как раз содержит первый пакет. С другими пакетами строку
сопоставлять не надо — в них не может найтись соответствие,
поскольку хеш-коды заведомо будут отличаться.
Если строка принадлежит другому пакету, она сбрасывается на диск —
опять же, каждый пакет в свой временный файл.
Таким образом, при N пакетах используются 2(N–1) файлов.
Следует учитывать, что использование временных файлов на диске
ограничивается параметром temp_file_limit, который определяет общий
предел дисковой памяти для сеанса. уферы временных таблиц
в это ограничение не входят.)
15
Сопоставление – пакет 2
namealbum_id
хеш-таблица
(пакет 2)
пакет
2
пакет
3
пакет
4
пакет
2
пакет
3
пакет
4
Далее по очереди обрабатываются все пакеты, начиная со второго.
Из временного файла в хеш-таблицу считываются строки внутреннего
набора, затем из другого временного файла считываются строки
внешнего набора и сопоставляются с хеш-таблицей.
Процедура повторяется для всех оставшихся N–1 пакетов. На рисунке
показано соединение для второго пакета.