|
|
|||||||||||||||||||||||||||||
|
Использование хэш-ключей вместо строковых индексов в MS SQL ServerИсточник: SQL exercises
Вашему приложению может потребоваться индекс на основе длинной строки символов или, что еще хуже, конкатенации двух строк или строки и одного-двух целых чисел. Для небольшой таблицы вы можете не заметить какого-либо отрицательного влияния такого индекса. Но если предположить, что рассматриваемая таблица содержит 50 миллионов записей? Теперь вы не сможете не заметить воздействия, которое скажется как на требованиях к хранению, так и к производительности поиска. Однако вам не обязательно так поступать. Есть очень простая альтернатива, использующая то, что еще известно под названием хэш-блоков или хэш-ключей. Что такое хэширование?Говоря коротко, хэширование - это целочисленный результат алгоритма (известного как хэш-функция), применяемого к заданной строке. Вы передаете в алгоритм строку, а на выходе получаете целое число. Если Вы используете эффективную хэш-функцию, то вероятность того, что две различных строки дадут одно и то же значение хэш-функции, будет невелика. Такой случай известен под названием коллизии хэширования. Предположим, что Вы применили к этой статье алгоритм хэширования, затем изменили один символ в статье и повторили алгоритм: он возвратил бы другое целое число. Хэш-ключи в проекте базы данныхКак бы теперь грамотно применить хэш-ключи в наших проектах баз данных? Предположим, что интересующая нас таблица имеет следующие столбцы:
Составной индекс на обоих столбцах потреблял бы 50 + 50 символов на строку. Учитывая, что у нас 50 миллионов строк, это - проблема. Хэш-ключ, построенный на тех же двух столбцах будет значительно меньше (4 байта на строку). Еще лучше, что мы не должны хранить сами хэш-ключи - или более точно, мы должны сохранить их только однажды. Мы создаем вычисляемый столбец, формула которого дает нам хэш-ключ этих двух столбцов. Теперь мы индексируем строку по хэш-ключу и обходимся без индекса на двух упомянутых выше столбцах. Основной процесс состоит в следующем:
В таблице с 50 миллионами строк, несомненно, будут возникать коллизии хэширования, но это не является проблемой. Возвращаемый набор строк будет значительно меньше, чем набор строк, которые пришлось бы запросить, чтобы найти точное совпадение с оригинальными поисковыми значениями. Вы локализуете небольшой набор строк, используя хэш-ключ, и затем выполняете сравнение на точное совпадение с каждой строкой из этого набора. Поиск, основанный на целочисленном столбце, может оказаться существенно быстрее, чем поиск на базе строкового ключа большой длины, и еще быстрее, чем для составного ключа. Алгоритмы хэширования, использующие функцию ChecksumЕсть несколько доступных алгоритмов, простейший из которых встроен в SQL Server в форме функции Checksum . Например, следующий запрос демонстрирует получение хэш-ключа для любого заданного значения или комбинации значений: USE AdventureWorks Этот код приводит к следующему результату (для краткости показаны только 10 строк):
Имеется множество вариантов того, как создавать хэш-ключ. Вы могли бы применить срабатывание триггера на вставку или использовать хранимую процедуру, чтобы создать хэш-ключ сразу, как только получены необходимые данные, или даже выполнить запрос UPDATE , который создаст хэш-ключи и заполнит хэш-столбец задним числом (чтобы Вы могли применить этот метод к таблицам, которые уже содержат миллионы строк). Как было показано выше, я предпочитаю решение, состоящее в том, чтобы "хранить" хэш-ключи в вычисляемом столбце, который потом индексируется. При этом индекс содержит хэш-ключи, но сама таблица - нет. Используя этот метод, Вы могли бы решить проблему следующим образом, предполагая, что целью поиска являются значения в Name и GroupName : CREATE PROCEDURE DemoHash ЗаключениеЭтот подход может дать значительный прирост производительности, и я настоятельно советую вам протестировать этот метод на вашей собственной системе. Представленный метод предполагает, что поиск ограничивается одной таблицей, что может не всегда иметь место. Я пока еще экспериментирую со способами применения этой техники для поиска в соединенных таблицах, и когда я найду лучший подход, то дам вам знать. Arthur Fuller (оригинал: Intelligent Database Design Using Hash Keys) Ссылки по теме
|
|