Хэш-соединение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Чтобы разделить оба отношения $R$ и $S$ и
Чтобы сохранить весь раздел из $R$ в памяти, известный как «раздел 0»

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

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

Хэш против присоединения

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

Хэш оставил запрет на присоединение

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

Это более эффективно, когда таблица NOT IN меньше таблицы FROM .

Хэширование правого анти-соединения

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

Это более эффективно, когда таблица NOT IN больше таблицы FROM .

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

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

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

Хэш левого полусоединения

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

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

Это более эффективно, когда таблица IN меньше таблицы FROM .

Хэширование правого полусоединения

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

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

Это более эффективно, когда таблица IN больше таблицы FROM .

См. также

Ссылки

^ ДеВитт, диджей; Кац, Р.; Олкен, Ф.; Шапиро, Л.; Стоунбрейкер, М.; Вуд, Д. (июнь 1984 г.). «Методы реализации систем баз данных основной памяти». Учеб. Конференция ACM SIGMOD . 14 (4): 1–8. дои : 10.1145/971697.602261 .

Внешние ссылки

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

[1] ДеВитт, диджей; Кац, Р.; Олкен, Ф.; Шапиро, Л.; Стоунбрейкер, М.; Вуд, Д. (июнь 1984 г.). «Методы реализации систем баз данных основной памяти». Учеб. Конференция ACM SIGMOD . 14 (4): 1–8. дои : 10.1145/971697.602261 .

[1]