Правильная ссылка на эту страницу
http://az-design.ru/Support/DataBase/Hash-Index.shtml

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

Arthur Fuller (оригинал: Intelligent database design using hash-keys)
Перевод Моисеенко С.И.
http://www.sqlbooks.ru/readarticle.aspx?part=02&file=tsql09

       Вашему приложению может потребоваться индекс на основе длинной строки символов или, что еще хуже, конкатенации двух строк или строки и одного-двух целых чисел. Для небольшой таблицы вы можете не заметить какого-либо отрицательного влияния такого индекса. Но если предположить, что рассматриваемая таблица содержит 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 

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

Оглавление
Главная страница




Дата последнего изменения:
Thursday, 21-Aug-2014 09:10:44 MSK


Постоянный адрес статьи:
http://az-design.ru/Support/DataBase/Hash-Index.shtml