Використання хеш-ключів замість строкових індексів в SQL Server, Інші СУБД, Бази даних, статті

Arthur Fuller (Оригінал: Intelligent Database Design Using Hash Keys)
Переклад Моісеєнко С.І.


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

Висновок


Цей підхід може дати значний приріст продуктивності, і я настійно раджу вам протестувати цей метод на вашій власній системі. Представлений метод передбачає, що пошук обмежується однією таблицею, що може не завжди мати місце. Я поки ще експериментую зі способами застосування цієї техніки для пошуку в з’єднаних таблицях, і коли я знайду кращий підхід, то дам вам знати.

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*