(495) 925-0049, ITShop интернет-магазин 229-0436, Учебный Центр 925-0049
  Главная страница Карта сайта Контакты
Поиск
Вход
Регистрация
Рассылки сайта
 
 
 
 
 

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

Источник: cyberguru

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

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

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

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

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

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

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

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

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

  1. Пользователь (либо человек, либо приложение) запрашивает некоторые значения.
  2. Эти значения теперь преобразовываются в хэш-ключ.
  3. Механизм базы данных выполняет поиск в индексе, построенном на хэш-столбце, возвращая требуемую строку, или небольшой набор соответствующих строк.

В таблице с 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

Заключение

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

Ссылки по теме


 Распечатать »
 Правила публикации »
  Обсудить материал в конференции Microsoft »
Обсудить материал в конференции Дизайн, графика, обработка изображений »
Написать редактору 
 Рекомендовать » Дата публикации: 06.09.2012 
 

Магазин программного обеспечения   WWW.ITSHOP.RU
Microsoft Office 365 Бизнес. Подписка на 1 рабочее место на 1 год
Microsoft System Center Standard Core Sngl License/Software Assurance Pack OLP 2Licenses NoLevel CoreLic Qualified
Microsoft SQL CAL 2017 Sngl OLP 1License NoLevel UsrCAL
Microsoft Visual Studio Professional w/MSDN AllLng License/Software Assurance Pack OLP 1 License No Level Qualified
Microsoft Visual Studio Professional 2017 Sngl OLP 1License NoLevel
 
Другие предложения...
 
Курсы обучения   WWW.ITSHOP.RU
 
Другие предложения...
 
Магазин сертификационных экзаменов   WWW.ITSHOP.RU
 
Другие предложения...
 
3D Принтеры | 3D Печать   WWW.ITSHOP.RU
 
Другие предложения...
 
Новости по теме
 
Рассылки Subscribe.ru
Информационные технологии: CASE, RAD, ERP, OLAP
Безопасность компьютерных сетей и защита информации
Новости ITShop.ru - ПО, книги, документация, курсы обучения
Программирование на Microsoft Access
CASE-технологии
Все о PHP и даже больше
Новые программы для Windows
 
Статьи по теме
 
Новинки каталога Download
 
Исходники
 
Документация
 
Обсуждения в форумах
Кто, что знает за карту рассрочки Совесть? (1)
Иногда требуется купить что-то очень нужное, но выделить средства нет возможности. В этом случае...
 
Access, Ключевое поле, Счетчик (10)
Подскажите пожалуйста, как изменить в Access в ключевом поле (счетчик последовательно),...
 
Решение задач на оптимизацию с помощью MS Excel (4)
Zdravstvuyte, ya pro4itala danniy material, no ne smogla ponat kakie formuli ispolzovalis v...
 
Отличается ли ДрифтКазино от беттинга? (4)
Друзья, давно заметил, что на Дрифте уже несколько месяцев во всю рекламируется и предлагается...
 
Как извлечь рисунки из файла Word (45)
Вообще-то есть еще способ - сделать в Word-е Copy рисунка, открыть Microsoft Photo Editor и там:...
 
 
 



    
rambler's top100 Rambler's Top100