Длинные строки в таблицах хэширования
Во многих реляционных СУБД поддерживаются так называемые хэш-кластерные индексы (clustered hashed index). Такие объекты правильнее называть таблицами хэширования, а не индексами. Таблица хэширования представляет собой таблицу реляционной базы данных, доступ к строкам которой осуществляется с помощью преобразования ключа. Значения колонок, которые объявлены ключевыми, преобразуются в позиции строк таблицы (и при их вставке там и размещаются) - хэшируются. Такую функцию называют хэш-функцией. Ключ таблицы, который подвергается преобразованию, называется хэш-ключом. Данные, которые обрабатываются таким образом, размещаются в специальных таблицах, называемых еще хэш-кластерами или просто хэш-таблицами. В настоящем курсе предполагается, что проектировщику известны общие методы организации физического доступа к данным, поэтому мы не будем детально обсуждать вопрос, как устроены такие таблицы.
Отметим только, что хэширование является очень эффективным методом доступа по первичному ключу к записи за один доступ. Если значения ключа равномерно распределены, то в среднем это будет так. В противном случае производительность доступа будет резко падать из-за коллизий, т.е. случая, когда для двух различных значений первичного ключа хэш-функция дает одинаковые числа, т.е. позиции записи. В худшем случае придется просканировать всю таблицу, чтобы получить одну запись!
Несмотря на то, что построены динамические таблицы хэширования (изменяющие свой размер во время существования), в большинстве СУБД поддерживаются статические таблицы хэширования, размер которых определяется при их создании. В большинстве случаев таблица хэширования формируется случайным образом по отношению к порядку следования значений ключа, хотя известны функции преобразования ключа, которые поддерживают лексикографический порядок на значении ключа таблицы.
Хэш-индекс обычно применяется, если ключ полностью представлен в предложении WHERE и используется операция равенства для колонок ключа. Нас интересует проблема увеличения производительности в хэш-таблицах, когда длина строки превышает размер физической страницы на жестком диске.
Чтобы лучше понять проблему, рассмотрим, как определяется хэш-таблица в SQL.
Такая таблица создается при помощи команды, например
CREATE CLUSTERED HASHES INDEX CHXNAME ON EMPLOYEE (EMPNO) SIZE 2000 ROWS;
Предложение SIZE задает вероятное количество строк в индексе, а ROWS определяет число строк для хранения индекса. Размер можно задавать в блоках (BUCKETS). Таким образом, по значению первичного ключа адресуется блок, содержащий целое число строк, или строка, если ее размер сопоставим с размером физического блока. В последнем случае считается, что блок содержит одну строку.
Для таблицы хэширования определяется параметр "число строк на странице" (rows per page) или "кластеризация страницы" (page clustering), или коэффициент блокировки, равный
Как видно из определения таблицы хэширования, размер строки и размер физического блока должны быть согласованы. Проблема длинной строки в таблице хэширования состоит в том, что если строка занимает несколько блоков, то возрастает частота коллизий и вместо одного физического доступа для получения строки требуется 4-6, что уже сопоставимо с использованием индексов другого типа.
Цель разбиения таблицы хэширования состоит в том, чтобы попытаться достигнуть такого значения параметра blocking factor (коэффициент блокировки), которое содержало бы по крайней мере как можно больше строк, которые будут выбираться вместе в большинстве транзакций к этой таблице в базе данных.
Поскольку в современных СУБД размер физического блока фиксирован для каждой операционной платформы, то единственным способом влияния на величину этого параметра является подгонка размера строки. Если нельзя пересмотреть спецификацию типов колонок таблицы и свести их размеры до минимума, то единственной возможностью выбрать подходящий коэффициент блокирования является разбиение таблицы хэширования.
