Использование хэш-ключей вместо строковых индексов в SQL Server
Однако вам не обязательно так поступать. Есть очень простая альтернатива, использующая то, что еще известно под названием хэш-блоков или хэш-ключей.
Что такое хэширование?
Говоря коротко, хэширование - это целочисленный результат алгоритма (известного как хэш-функция), применяемого к заданной строке. Вы передаете в алгоритм строку, а на выходе получаете целое число. Если Вы используете эффективную хэш-функцию, то вероятность того, что две различных строки дадут одно и то же значение хэш-функции, будет невелика. Такой случай известен под названием коллизии хэширования. Предположим, что Вы применили к этой статье алгоритм хэширования, затем изменили один символ в статье и повторили алгоритм: он возвратил бы другое целое число.
Хэш-ключи в проекте базы данных
Как бы теперь грамотно применить хэш-ключи в наших проектах баз данных? Предположим, что интересующая нас таблица имеет следующие столбцы:
Имя столбца | Тип Данных |
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