Версия для печати
На
главную страницу
Использование хэш-ключей вместо строковых индексов
Arthur Fuller (оригинал:
Intelligent Database Design Using Hash Keys)
Перевод Моисеенко С.И.
Вашему приложению может потребоваться индекс на основе длинной строки символов или,
что еще хуже, конкатенации двух строк или строки и одного-двух целых чисел. Для
небольшой таблицы вы можете не заметить какого-либо отрицательного влияния
такого индекса. Но если предположить, что рассматриваемая таблица содержит 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
Заключение
Этот подход может дать значительный прирост производительности, и я настоятельно
советую вам протестировать этот метод на вашей собственной системе.
Представленный метод предполагает, что поиск ограничивается одной таблицей, что
может не всегда иметь место. Я пока еще экспериментирую со способами применения
этой техники для поиска в соединенных таблицах, и когда я найду лучший подход,
то дам вам знать.
См. комментарий к данной статье А.Г.Архангельского
На главную страницу
Версия для печати
|