Статьи:: Базы данных :: MS SQL Server :: Использование хэш-ключей вместо строковых индексов

   Обсудить на форуме

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

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

Что такое хэширование?

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

Хэш-ключи в проекте базы данных

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

 

Имя столбца	Тип Данных
Name	Varchar(50)
GroupName	Varchar(50)

 

Составной индекс на обоих столбцах потреблял бы 50 + 50 символов на строку. Учитывая, что у нас 50 миллионов строк, это - проблема. Хэш-ключ, построенный на тех же двух столбцах будет значительно меньше (4 байта на строку). Еще лучше, что мы не должны хранить сами хэш-ключи - или более точно, мы должны сохранить их только однажды. Мы создаем вычисляемый столбец, формула которого дает нам хэш-ключ этих двух столбцов. Теперь мы индексируем строку по хэш-ключу и обходимся без индекса на двух упомянутых выше столбцах.

Основной процесс состоит в следующем:

Пользователь (либо человек, либо приложение) запрашивает некоторые значения.

Эти значения теперь преобразовываются в хэш-ключ.

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

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

Алгоритмы хэширования, использующие функцию Checksum

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

USE AdventureWorks
SELECT Name, GroupName, Checksum(Name,GroupName) AS HashKey
FROM Adventureworks.HumanResources.Department
ORDER BY HashKey

Этот код приводит к следующему результату (для краткости показаны только 10 строк):

 

Name	GroupName	Hashkey
Tool Design	Research and Development	-2142514043
Production	Manufacturing	-2110292704
Shipping and Receiving	Inventory Management	-1405505115
Purchasing	Inventory Management	-1264922199
Document Control	Quality Assurance	-922796840
Information Services	Executive General and Administration	-904518583
Quality Assurance	Quality Assurance	-846578145
Sales	Sales and Marketing	-493399545
Production Control	Manufacturing	-216183716
Marketing	Sales and Marketing	-150901473

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

Используя этот метод, Вы могли бы решить проблему следующим образом, предполагая, что целью поиска являются значения в Name и GroupName :

CREATE PROCEDURE DemoHash
(
@Name Varchar(50),
@GroupName Varchar(50)
)
AS
-- USE AdventureWorks
DECLARE @id as int
SET @id = Checksum(@Name,@GroupName)
SELECT * FROM Adventureworks.HumanResources.Department
WHERE HashKey = @id
AND Name = @Name AND GroupName = @GroupName

Заключение

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

Arthur Fuller (оригинал: Intelligent Database Design Using Hash Keys)
Перевод Моисеенко С.И.
http://sqlbooks.ru/