Хеш-соединение - Hash join

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

Хэш-соединения обычно более эффективны, чем соединения с вложенными циклами, за исключением случаев, когда сторона проверки соединения очень мала. Они требуют Equijoin предикат (а предикат сравнение записей из одной таблицы с записями из другой таблицы с использованием объединения операторов равенства '=' в одном или нескольких столбцах).

Классическое хеш-соединение

Классический алгоритм хеш-соединения для внутреннее соединение двух отношений протекает следующим образом:

Сначала подготовьте хеш-таблица с использованием содержимого одного отношения, в идеале того, которое меньше после применения локальных предикатов. Это отношение называется стороной сборки соединения. В хеш-таблица Записи - это сопоставления значения (составного) атрибута соединения с остальными атрибутами этой строки (в зависимости от того, какие из них необходимы).
Однажды хеш-таблица построена, просканируйте другую связь (сторону датчика). Для каждой строки отношения проверки найдите соответствующие строки отношения сборки, просмотрев хеш-таблица.

Первую фазу обычно называют этап "сборки", а второй называется фаза "зондирования". Точно так же отношение соединения, на котором построена хеш-таблица, называется входом «build», тогда как другой вход называется входом «probe».

Этот алгоритм прост, но он требует, чтобы меньшее отношение соединения помещалось в память, что иногда бывает не так. Простой подход к решению этой ситуации заключается в следующем:

Для каждого кортежа ${ displaystyle r}$ $р$ во вводе сборки ${ displaystyle R}$ $р$
1. Добавлять ${ displaystyle r}$ в хеш-таблицу в памяти
2. Если размер хеш-таблицы равен максимальному размеру в памяти:
  1. Сканируйте вход датчика ${ displaystyle S}$ , и добавить соответствующие кортежи соединения к выходному отношению
  2. Сбросьте хэш-таблицу и продолжите сканирование ввода сборки ${ displaystyle R}$
Сделайте окончательное сканирование входа датчика ${ displaystyle S}$ и добавьте полученные кортежи соединения к выходному отношению

По сути, это то же самое, что и блокировать вложенный цикл алгоритм присоединения. Этот алгоритм сканирует ${ displaystyle S}$ в итоге больше раз, чем необходимо.

Грейс хеш-соединение

Более удачный подход известен как «льготное хеш-соединение» по имени компьютера базы данных GRACE, для которого он был впервые реализован.

Этот алгоритм позволяет избежать повторного сканирования всего ${ displaystyle S}$ отношение, сначала разделив оба ${ displaystyle R}$ и ${ displaystyle S}$ с помощью хеш-функции и записи этих разделов на диск. Затем алгоритм загружает пары разделов в память, строит хэш-таблицу для меньшего разделенного отношения и исследует другое отношение на предмет совпадений с текущей хеш-таблицей. Поскольку разделы были сформированы путем хеширования по ключу соединения, любые выходные кортежи соединения должны принадлежать одному и тому же разделу.

Возможно, что один или несколько разделов все еще не помещаются в доступную память, и в этом случае алгоритм применяется рекурсивно: выбирается дополнительная ортогональная хэш-функция для хеширования большого раздела на подразделы, которые затем обрабатываются как перед. Поскольку это дорого, алгоритм пытается снизить вероятность того, что это произойдет, путем формирования наименьших возможных разделов на начальном этапе разделения.

Гибридное хеш-соединение

Алгоритм гибридного хеш-соединения^[1] - это усовершенствованное соединение с постепенным хешированием, которое использует больше доступной памяти. На этапе разделения гибридное хеш-соединение использует доступную память для двух целей:

Чтобы удерживать текущую страницу буфера вывода для каждого из ${ displaystyle k}$ перегородки
Для хранения всего раздела в памяти, известного как «раздел 0»

Поскольку раздел 0 никогда не записывается и не читается с диска, гибридное хеш-соединение обычно выполняет меньше операций ввода-вывода, чем льготное хеш-соединение. Обратите внимание, что этот алгоритм чувствителен к памяти, потому что есть два конкурирующих требования к памяти (хеш-таблица для раздела 0 и выходные буферы для оставшихся разделов). Выбор слишком большой хэш-таблицы может привести к рекурсии алгоритма, потому что один из ненулевых разделов слишком велик для размещения в памяти.

Хеш-анти-присоединение

Хеш-соединения также могут быть оценены для предиката антисоединения (предикат, выбирающий значения из одной таблицы, когда в другой не найдено связанных значений). В зависимости от размеров таблиц могут применяться разные алгоритмы:

Хэш слева от антисоединения

Подготовить хеш-таблица для НЕ В сторона соединения.
Сканируйте другую таблицу, выбирая любые строки, в которых атрибут соединения хешируется, до пустой записи в хеш-таблице.

Это более эффективно, когда НЕ В таблица меньше, чем ИЗ стол

Хеш-правый анти-присоединение

Подготовьте хеш-таблицу для ИЗ сторона соединения.
Сканируйте НЕ В table, удаляя соответствующие записи из хеш-таблицы при каждом попадании в хеш
Вернуть все, что осталось в хеш-таблице

Это более эффективно, когда НЕ В таблица больше, чем ИЗ стол

Полусоединение хэша

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

Как и в случае с антисоединением, полусоединение также может быть левым и правым:

Хеш-левое полусоединение

Подготовьте хеш-таблицу для В сторона соединения.
Сканируйте другую таблицу, возвращая все строки, которые производят хеш-попадание.

Записи возвращаются сразу после того, как они произвели хит. Фактические записи из хеш-таблицы игнорируются.

Это более эффективно, когда В таблица меньше, чем ИЗ стол

Хеш-правое полусоединение

Подготовьте хеш-таблицу для ИЗ сторона соединения.
Сканируйте В table, возвращая соответствующие записи из хеш-таблицы и удаляя их

При использовании этого алгоритма каждая запись из хеш-таблицы (то есть ИЗ table) можно вернуть только один раз, так как он удаляется после возврата.

Это более эффективно, когда В таблица больше, чем ИЗ стол

Смотрите также

внешняя ссылка

Хансйорг Целлер; Джим Грей (1990). «Адаптивный алгоритм хеш-соединения для многопользовательских сред» (PDF). Материалы 16-й конференции VLDB. Брисбен: 186–197. Архивировано из оригинал (PDF) на 2012-03-11. Получено 2008-09-21.

[1] DeWitt, D.J .; Katz, R .; Olken, F .; Шапиро, Л .; Stonebraker, M .; Вуд, Д. (июнь 1984 г.). «Методы реализации для систем баз данных с основной памятью». Proc. ACM SIGMOD Conf. 14 (4): 1–8. Дои:10.1145/971697.602261.

[1]