Оптимизация запросов

Соединение хешированием

Авторские права

Авторы: Егор Рогов, Павел Лузанов, Павел Толмачев, Илья Баштанов

Использование материалов курса

Некоммерческое использование материалов курса (презентации,

демонстрации) разрешается без ограничений. Коммерческое

использование возможно только с письменного разрешения компании

Postgres Professional. Запрещается внесение изменений в материалы

курса.

Обратная связь

Отзывы, замечания и предложения направляйте по адресу:

edu@postgrespro.ru

Отказ от ответственности

Компания Postgres Professional не несет никакой ответственности за

любые повреждения и убытки, включая потерю дохода, нанесенные

прямым или непрямым, специальным или случайным использованием

материалов курса. Компания Postgres Professional не предоставляет

каких-либо гарантий на материалы курса. Материалы курса

предоставляются на основе принципа «как есть» и компания Postgres

Professional не обязана предоставлять сопровождение, поддержку,

обновления, расширения и изменения.

Темы

Последовательное соединение хешированием:

одно- и двухпроходное

Группировка с помощью хеширования

Вычислительная сложность

Параллельное соединение хешированием:

одно- и двухпроходное

Однопроходное соединение

Применяется, когда для хеш-таблицы достаточно

оперативной памяти

SELECT a.title, s.name

FROM albums a JOIN songs s ON a.id = s.album_id;

Построение хеш-таблицы

Yellow Submarine

Abbey Road

The Beatles

3 Let It Be

1969

1968

1970

Let It Be

Abbey Road

4 The Beatles

10100001

10001001

01000100

1 Yellow Submarine11000111

id title year

номер

корзины

work_mem × hash_mem_multiplier

id titleхеш-код

участвует

в условии

соединения

используется

в запросе

внутренний набор

Первым этапом в памяти строится хеш-таблица.

Идея хеширования состоит в том, что функция хеширования

равномерно распределяет значения по ограниченному числу корзин

хеш-таблицы. В таком случае разные значения как правило будут

попадать в разные корзины. Если равномерности не будет, в одну

корзину может попасть много значений. В таком случае они

выстраиваются в список, и по мере увеличения длины списка

эффективность поиска по хеш-таблице будет падать.

Итак, строки первого набора читаются последовательно, и для каждой

из них вычисляется хеш-функция от значения полей, входящих

в условие соединения (в нашем примере — числовые

идентификаторы).

По значению хеш-функции определяется номер корзины. Например,

если используется 4 корзины, то в качестве номера корзины можно

взять два младших бита.

В корзину хеш-таблицы помещаются вычисленный хеш-код и все поля,

которые входят в условие соединения или используются в запросе.

Размер хеш-таблицы в памяти ограничен значением work_mem ×

× hash_mem_multiplier. Наилучшая эффективность достигается, если

вся хеш-таблица помещается в этот объем памяти целиком. (Это еще

одна причина не использовать в запросе лишние поля, в том числе,

«звездочку».)

Исходный код алгоритма можно найти в файле

src/backend/executor/nodeHashjoin.c.

Сопоставление

SELECT a.title, s.name

FROM albums a JOIN songs s ON a.id = s.album_id;

A Day in the Life

Another Girl

All You Need Is Love

Act Naturally

1 All Together Now

3 Across the Universe

11000100

namealbum_id

Let It Be

Abbey Road

4 The Beatles

10100001

10001001

01000100

1 Yellow Submarine11000111

id titleхеш-код

внешний набор

work_mem × hash_mem_multiplier

На втором этапе мы последовательно читаем второй набор строк.

По мере чтения мы вычисляем хеш-функцию от значения полей,

участвующих в условии соединения. Если в соответствующей корзине

хеш-таблицы обнаруживается строка

- с таким же хеш-кодом,

- и со значениями полей, подходящими под условие соединения,

то мы нашли пару.

Проверки одного только хеш-кода недостаточно. Во-первых, не все

условия соединения, перечисленные в запросе, могут быть учтены при

выполнении соединения хешированием (поддерживаются только

эквисоединения). Во-вторых, возможны коллизии, при которых разные

значения получат одинаковые хеш-коды (вероятность этого мала, но

тем не менее она есть).

В нашем примере для первой строки соответствия нет.

Сопоставление

SELECT a.title, s.name

FROM albums a JOIN songs s ON a.id = s.album_id;

A Day in the Life

Another Girl

All You Need Is Love

Act Naturally

3 Across the Universe

11000111

namealbum_id

1 All Together Now

Let It Be

Abbey Road

4 The Beatles

10100001

10001001

01000100

1 Yellow Submarine11000111

id titleхеш-код

Вторая строка второго набора дает соответствие, которое уже можно

вернуть вышестоящему узлу плана: («Yellow Submarine», «All Together

Now»).

Сопоставление

SELECT a.title, s.name

FROM albums a JOIN songs s ON a.id = s.album_id;

A Day in the Life

Another Girl

All You Need Is Love

Act Naturally

1 All Together Now

3 Across the Universe

11110110

namealbum_id

Let It Be

Abbey Road

4 The Beatles

10100001

10001001

01000100

1 Yellow Submarine11000111

id titleхеш-код

Для третьей строки соответствия нет (соответствующая корзина хеш-

таблицы пуста).

Сопоставление

SELECT a.title, s.name

FROM albums a JOIN songs s ON a.id = s.album_id;

A Day in the Life

Another Girl

All You Need Is Love

Act Naturally

10100001

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»).

Заметим, что в корзине хеш-таблицы оказалось две строки первого

набора, и в общем случае их придется просмотреть обе.

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;

A Day in the Life

Another Girl

Act Naturally

3 Across the Universe

11000111

namealbum_id

1 All Together Now

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»).

SELECT a.title, s.name

FROM albums a JOIN songs s ON a.id = s.album_id;

Сопоставление

A Day in the Life

Another Girl

All You Need Is Love

Act Naturally

1 All Together Now

3 Across the Universe

11110110

namealbum_id

Let It Be

Abbey Road

4 The Beatles

10100001

10001001

01000100

1 Yellow Submarine11000111

id titleхеш-код

Для шестой строки соответствия нет. На этом работа соединения

завершена.

Двухпроходное соединение

Применяется, когда хеш-таблица не помещается

в оперативную память: наборы данных разбиваются

на пакеты и последовательно соединяются

id title year

Построение хеш-таблицы

work_mem × hash_mem_multiplier

временные

файлы для

внутреннего

набора

пакет

хеш-таблица

(пакет 1)

Если хеш-таблица не помещается в объем памяти, ограниченный

work_mem × hash_mem_multiplier, первый (внутренний) набор строк

разбивается на отдельные пакеты. Для распределения по пакетам

используется некоторое количество битов хеш-кода, поэтому число

пакетов всегда кратно двум. В идеале в каждый пакет попадает

примерно одинаковое количество строк, но, если значения в строках

повторяются, возможен перекос.

При планировании запроса заранее вычисляется минимально

необходимое число пакетов так, чтобы хеш-таблица для каждого пакета

помещалась в памяти. Это число не уменьшается, даже если

оптимизатор ошибся с оценками, но при необходимости может

динамически увеличиваться.

Хеш-таблица для первого пакета остается в памяти, а строки,

принадлежащие другим пакетам, сбрасываются на диск во временные

файлы — каждый пакет в свой файл.

На рисунке показано четыре пакета.

пакет

namealbum_id

Сопоставление – пакет 1

хеш-таблица

(пакет 1)

пакет

временные

файлы для

внешнего

набора

temp_file_limit

Далее читается второй (внешний) набор строк. Если строка

принадлежит первому пакету, она сопоставляется с хеш-таблицей,

которая как раз содержит первый пакет. С другими пакетами строку

сопоставлять не надо — в них не может найтись соответствие,

поскольку хеш-коды заведомо будут отличаться.

Если строка принадлежит другому пакету, она сбрасывается на диск —

опять же, каждый пакет в свой временный файл.

Таким образом, при N пакетах используются 2(N–1) файлов.

Следует учитывать, что использование временных файлов на диске

ограничивается параметром temp_file_limit, который определяет общий

предел дисковой памяти для сеанса. (Буферы временных таблиц

в это ограничение не входят.)

Сопоставление – пакет 2

namealbum_id

хеш-таблица

(пакет 2)

пакет

Далее по очереди обрабатываются все пакеты, начиная со второго.

Из временного файла в хеш-таблицу считываются строки внутреннего

набора, затем из другого временного файла считываются строки

внешнего набора и сопоставляются с хеш-таблицей.

Процедура повторяется для всех оставшихся N–1 пакетов. На рисунке

показано соединение для второго пакета.

Сопоставление – пакет 3

namealbum_id

хеш-таблица

(пакет 3)

пакет

На рисунке показано соединение для третьего пакета.

Сопоставление – пакет 4

namealbum_id

хеш-таблица

(пакет 4)

пакет

После обработки последнего пакета соединение завершено и

временные файлы освобождены.

Таким образом, при нехватке оперативной памяти алгоритм соединения

становится двухпроходным: каждый пакет (кроме первого) требуется

записать на диск и затем прочитать повторно. Разумеется, это

сказывается на эффективности соединения. Поэтому важно, чтобы:

- в хеш-таблицу попадали только действительно нужные поля

(обязанность автора запроса),

- хеш-таблица строилась по меньшему набору строк (обязанность

планировщика).

Вычислительная сложность

~ N + M, где

N и M — число строк в первом и втором наборах данных

Начальные затраты на построение хеш-таблицы

Эффективно для большого числа строк

Общая сложность соединения хешированием пропорциональна сумме

числа строк в одном и другом наборах данных. Поэтому метод

соединения хешированием гораздо эффективнее вложенного цикла при

большом числе строк.

Однако, чтобы начать соединение, требуется заплатить накладные

расходы на построение хеш-таблицы: из-за этого при небольшом числе

строк вложенный цикл более эффективен.

Соединение хешированием (в сочетании с полным сканированием

таблиц) характерно для OLAP-запросов, в которых надо обработать

большое число строк, причем общая пропускная способность важнее

времени отклика.

Параллельно, один проход

Процессы используют общую хеш-таблицу

Параллельный алгоритм

Gather

Parallel Hash Join

Parallel Hash

Parallel

Seq Scan

Parallel

Seq Scan

Parallel Hash Join

Parallel Hash

Parallel

Seq Scan

Parallel

Seq Scan

Parallel Hash Join

Parallel Hash

Parallel

Seq Scan

Parallel

Seq Scan

В отличие от других способов соединения, хеш-соединение не только

может участвовать в параллельных планах, но и имеет отдельный

эффективный алгоритм работы. Этот алгоритм позволяет параллельно

выполнять оба этапа соединения: и построение хеш-таблицы по

первому (внутреннему) набору строк, и сопоставление с ней строк

второго (внешнего) набора.

Возможность параллельного хеш-соединения управляется параметром

enable_parallel_hash; по умолчанию параметр включен.

Как и у последовательного алгоритма, у параллельного есть два

варианта: однопроходный при достаточном количестве оперативной

памяти и двухпроходный.

Начнем с однопроходного варианта.

id title year

Построение хеш-таблицы

work_mem × hash_mem_multiplier ×

× количество процессов

хеш-таблица

Parallel

Hash

Однопроходный алгоритм используется, если хеш-таблица помещается

в суммарный объем памяти, выделенный всем участвующим

в соединении процессам, то есть размер хеш-таблицы ограничен

значением work_mem × hash_mem_multiplier × количество процессов.

Процессы параллельно читают первый набор строк (например,

используя узел Parallel Seq Scan) и строят общую хеш-таблицу

в разделяемой памяти, где каждый из них имеет к ней доступ.

namealbum_id

Сопоставление

хеш-таблица

Parallel

Hash Join

После того, как хеш-таблица полностью построена, рабочие процессы

приступают к параллельному чтению второго набора и сопоставляют

прочитанные ими строки с общей-хеш-таблицей. Таким образом,

каждый из процессов проверяет по хеш-таблице только часть данных.

Параллельно, два прохода

Наборы строк разбиваются на пакеты, которые затем

параллельно обрабатываются рабочими процессами

id title year

Разбиение на пакеты

пакет

namealbum_id

пакет

Хеш-таблица может не поместиться в объем памяти, ограниченный

work_mem × hash_mem_multiplier × количество процессов, причем это

может выясниться и на этапе выполнения соединения. В этом случае

используется двухпроходный алгоритм, который существенно

отличается и от двухпроходного последовательного, и от

однопроходного параллельного.

Сначала рабочие процессы параллельно читают первый набор данных,

разбивают его на пакеты и записывают пакеты во временные файлы.

Первый пакет тоже попадает в файл; хеш-таблица в памяти не

строится.

Обратите внимание, что каждый процесс записывает строки в каждый

временный файл; запись синхронизируется.

Затем рабочие процессы параллельно читают второй набор данных и

также разбивают его на пакеты и записывают во временные файлы.

Таким образом, при N пакетах на диск записываются 2N файлов.

Сопоставление

namealbum_id

хеш-таблица

(пакет 1)

пакет

work_mem × hash_mem_multiplier

хеш-таблица

(пакет 2)

хеш-таблица

(пакет 3)

Затем каждый рабочий процесс выбирает себе по одному пакету.

Процесс загружает первый набор выбранного пакета в хеш-таблицу

в памяти. В этом алгоритме у каждого процесса своя хеш-таблица

размером work_mem × hash_mem_multiplier, но располагаются они

в общей памяти, то есть доступ к каждой таблице есть у всех рабочих

процессов.

После заполнения хеш-таблицы процесс читает второй набор

выбранного пакета и сопоставляет строки.

Когда процесс завершает обработку одного пакета, он выбирает

следующий, еще не обработанный.

Сопоставление

work_mem × hash_mem_multiplier

namealbum_id

хеш-таблица

(пакет 4)

общими

усилиями

Когда необработанные пакеты заканчиваются, освободившийся

процесс подключается к обработке одного из еще не завершенных

пакетов, пользуясь тем, что все хеш-таблицы находятся в разделяемой

памяти.

Несколько хеш-таблиц работают лучше, чем одна большая: в этом

случае проще организовать совместную работу и меньше ресурсов

тратится на синхронизацию.

Итоги

Соединение хешированием требует подготовки

надо построить хеш-таблицу

Эффективно для больших выборок

в том числе есть возможность параллельного соединения

Зависит от порядка соединения

внутренний набор должен быть меньше внешнего,

чтобы минимизировать хеш-таблицу

Поддерживает только эквисоединения

для хеш-кодов операторы «больше» и «меньше» не имеют смысла

В отличие от соединения вложенным циклом, хеш-соединение требует

подготовки: построения хеш-таблицы. Пока таблица не построена, ни

одна результирующая строка не может быть получена.

Зато соединение хешированием эффективно работает на больших

объемах данных. Оба набора строк читаются последовательно и только

один раз (два раза в случае нехватки оперативной памяти).

Ограничением соединения хеширования является поддержка только

эквисоединений. Дело в том, что хеш-значения можно сравнивать

только на равенство, операции «больше» и «меньше» просто не имеют

смысла.

Практика

1. Напишите запрос, показывающий занятые места в салоне

для всех рейсов.

Какой способ соединения выбрал планировщик? Проверьте,

хватило ли оперативной памяти для размещения хеш-таблиц.

2. Измените запрос, чтобы он выводил только общее

количество занятых мест.

Как изменился план запроса? Почему планировщик не

использовал аналогичный план для предыдущего запроса?

3. Напишите запрос, показывающий имена пассажиров и

номера рейсов, которыми они следуют.

Разберитесь по плану запроса, в какой последовательности

выполняются операции.

1. Для этого достаточно соединить рейсы (flights) с посадочными

талонами (boarding_passes).

3. Такой запрос должен соединять три таблицы: билеты (tickets),

перелеты (ticket_flights) и рейсы (flights).