Введение
Эта статья появилась как ответ на предложение Артура Фуллера (Arthur Fuller) использовать хэш-функции в базах данных.
Что предлагает А.Фуллер?
"Вашему приложению может потребоваться индекс на основе длинной строки символов или, что еще хуже, конкатенации двух строк или строки и одного-двух целых чисел. Для небольшой таблицы вы можете не заметить какого-либо отрицательного влияния такого индекса. Но если предположить, что рассматриваемая таблица содержит 50 миллионов записей? Теперь вы не сможете не заметить воздействия, которое скажется как на требованиях к хранению, так и к производительности поиска.
Однако вам не обязательно так поступать. Есть очень простая альтернатива, использующая то, что еще известно под названием хэш-блоков или хэш-ключей."
Рассмотрим это предложение:
Что такое хэш-функция ?
Хэш-функцией называется односторонняя функция, предназначенная для получения дайджеста или "отпечатков пальцев" файла, сообщения или некоторого блока данных.
Хэш-код создается функцией Н:
h = H (M)
Где М является сообщением произвольной длины и h является хэш-кодом фиксированной длины.
Хэш-функция Н, которая используется для аутентификации сообщений, должна обладать следующими свойствами:
- Хэш-функция Н должна применяться к блоку данных любой длины.
- Хэш-функция Н создает выход фиксированной длины.
- Н(М) относительно легко (за полиномиальное время) вычисляется для любого значения М.
- Для любого данного значения хэш-кода h вычислительно невозможно найти M такое, что Н(M) = h.
- Для любого данного х вычислительно невозможно найти y<>x, что H(y) = H(x).
- Вычислительно невозможно найти произвольную пару (х,y) такую, что H(y) = H(x).
Первые три свойства требуют, чтобы хэш-функция создавала хэш-код для любого сообщения.
Четвертое свойство определяет требование односторонности хэш-функции: легко создать хэш-код по данному сообщению, но невозможно восстановить сообщение по данному хэш-коду. Это свойство важно, если аутентификация с использованием хэш-функции включает секретное значение.
Пятое свойство гарантирует, что невозможно найти другое сообщение, чье значение хэш-функции совпадало бы со значением хэш-функции данного сообщения. Это предотвращает подделку аутентификатора при использовании зашифрованного хэш-кода.
Хэш-функция, которая удовлетворяет первым пяти свойствам, называется простой или слабой хэш-функцией. Если кроме того выполняется шестое свойство, то такая функция называется сильной хэш-функцией. Однако, так как исходное сообщение имеет любую, а выходное фиксированную длину, то ВСЕГДА будут возникать коллизии.
Как предлагается использовать ?
"Пользователь (либо человек, либо приложение) запрашивает некоторые значения.
Эти значения теперь преобразовываются в хэш-ключ.
Механизм базы данных выполняет поиск в индексе, построенном на хэш-столбце, возвращая требуемую строку, или небольшой набор соответствующих строк.
В таблице с 50 миллионами строк, несомненно, будут возникать коллизии хэширования, но это не является проблемой. Возвращаемый набор строк будет значительно меньше, чем набор строк, которые пришлось бы запросить, чтобы найти точное совпадение с оригинальными поисковыми значениями. Вы локализуете небольшой набор строк, используя хэш-ключ, и затем выполняете сравнение на точное совпадение с каждой строкой из этого набора. Поиск, основанный на целочисленном столбце, может оказаться существенно быстрее, чем поиск на базе строкового ключа большой длины, и еще быстрее, чем для составного ключа."
Вроде все получается красиво. Но!
Если приложение запрашивает одно точное значение, то таких значений немного и результатом поиска будет 1 строка. И тогда, возможно, это будет работать.
Если значений много, то сначала нужно найти это "одно точное значение". Если точное значение неизвестно, то пользователь осуществляет частичный поиск, типа "найди то, не знаю что". Это либо часть строки, либо одно из текстовых полей индекса. В этом случае хэш-индекс работать не будет, потому что хэш-функция части не соответствует хэш-функции целого. Значит необходимо оставить и стандартный способ индексирования таблицы. И тем самым затраты как времени, так и размера ключей удваиваются.
Но даже если имеется точное значение, которое нужно найти, как избежать ошибок в самой БД. В качестве примера - результаты анализа БД "ГИБДД 2002 Автотранспорт Москвы февраль 2002 г". При таком количестве ошибок найти точное значение не удается. Если слово "Александр" записано 153 разными способами, то какое значение нужно искать?
Предложенный Фуллером запрос работает только в MSSQL и даже в этом случае зависит от реализации оптимизатора запросов.
SELECT * FROM Adventureworks.HumanResources.Department
WHERE HashKey = @id
AND Name = @Name AND GroupName = @GroupName
Оптимизатор может сначала взять поля Name и GroupName, построить по ним индекс, а затем использовать HashKey. Таким образом никакой экономии не происходит.
Для того чтобы запрос работал в любом случае он должен быть преобразован следующим образом:
Select * from (Select * from Adventureworks.HumanResources.Department where HAshKey=@ID)
where Name = @Name AND GroupName = @GroupName;
Конечно, если построить индекс, который бы обеспечивал уникальность значений из нескольких строковых полей... Но, хэш-функция гарантировать уникальность не может, особенно при больших размерах таблицы.
И в этом случае вместо правильного результата получим пустой ответ.
А как в этом случае (допустим что в хэш-функцию входят Имя, Отчество и Фамилия) получить список уникальных Фамилий? Этот простой запрос ставит в тупик самые мощные компьютеры и здесь хотелось бы получить ускорение. Но хэш-функция и здесь не спасает.
Как решать подобную задачу на очень больших таблицах?
Как ни странно нужно учится у классиков. Если встречается очень большая таблица с текстовыми полями - это означает, что таблица ненормализована. Например, таблица содержащая сведения о 25 миллионах людей, в которой нужно искать данные по именам, отчествам и фамилиям, обладает громадной избыточностью и требует нормализации. Это реальная таблица - БД "Прописка Москвы и Московской области 2005 г".
Даже с учетом того, что в таблице немерянное количество ошибок, количество уникальных фамилий составляет 669500. После исправления ошибок останется около 10000. Количество уникальных имен составляет 84500. После исправления ошибок останется около 3000. Таким образом, за счет того, что Имена, Отчества и Фамилии выносятся в отдельные таблицы, поиск осуществляется в очень маленьких таблицах, для которых по утверждениям А.Фуллера "... вы можете не заметить какого-либо отрицательного влияния такого индекса". А выборка из большой таблицы осуществляется с помощью целочисленного индекса, и совершенно безразлично каким образом это число получено. При этом остается возможность поиска по части имени или фамилии, а также последовательный поиск.
Как ни странно, нормализация одновременно устраняет ошибки в БД, подобные вышеописанным. А также существенно уменьшается размер БД.
Вообще, наличие в очень больших таблицах текстовых полей означает, что эти поля не являются определяющими, т.е. по ним не производится поиск. Они как правило большие и по ним невозможно построить индекс. В остальных случаях за счет избыточности текста практически всегда их можно разделить на термины и нормализовать всю таблицу.
А для чего хотелось бы использовать Хэш-функции ?
Сразу скажу - именно "хотелось бы" - так как коллизии - это основная проблема, которая мешает использовать эти приемы на практике.
1) Хотелось бы построить уникальный (primary) индекс по правилам с условиями.
Например, нужно внести запись о человеке. Уникальный индекс построен по правилу: Фамилия, Имя, Отчество, Дата_Рождения. Но в момент внесения записи дата рождения и/или отчество неизвестно. А известно, например, место работы или другая информация.
Тогда можно написать следующий триггер для вставки:
CREATE TRIGGER VIPerson_INSERT FOR VIPerson
ACTIVE BEFORE INSERT POSITION 1 AS
DECLARE VARIABLE USR SmallInt;
DECLARE VARIABLE Grp CHAR(1) character set win1251;
DECLARE VARIABLE Lev SmallInt;
DECLARE VARIABLE VipF Char(126) character set win1251;
DECLARE VARIABLE VipM Char(126) character set win1251;
DECLARE VARIABLE VipL Char(126) character set win1251;
DECLARE VARIABLE VipS Char(126) character set win1251;
DECLARE VARIABLE VIPX Char(16) character set win1251;
DECLARE VARIABLE VIPY Char(16) character set win1251;
DECLARE VARIABLE VIPZ Char(630) character set win1251;
BEGIN
VipF = '';
VipM = '';
VipL = '';
VipS = '';
VipX = '';
VipY = '';
VipZ = '';
new.VIPersnID = 0;
If (new.VIPFNAME is not null) then VipF = new.VIPFNAME;
If (new.VIPMNAME is not null) then VipM = new.VIPMNAME;
If (new.VIPLNAME is not null) then VipL = new.VIPLNAME;
If (new.VIPSURNM is not null) then VipS = new.VIPSURNM;
If (new.VIPBRDAY is not null) then VIPX = CAST(new.VIPBRDAY as CHAR(10));
else VIPX = new.VIPDataX;
If ((new.VIPMRDAY is not null) and (f_Year(new.VIPMRDAY) < 2000)) then
VIPY = CAST(new.VIPMRDAY as CHAR(10));
VIPZ = VipF//VipM//VipL//VipS//VipX//VipY;
new.VIPersnID = f_CRC32(VIPZ);
END;
Такой триггер позволял бы получать уникальный индекс даже в том случае, когда одно или несколько полей имеют значение null, недопустимое для обычного индекса. Кроме того, если поле VIPBrDay имеет значение Null, то вместо него подставляется другое поле VIPDataX с тем чтобы отличить одну запись от другой. При этом неважно нормализована таблица или нет. Принцип работает и в том и в другом случае.
Все бы было хорошо, но коллизии начались при размере таблицы около 300000 записей.
2) При использовании генераторов для получения ID записи, связи между таблицами обеспечивают только декларативную целостность.
Это означает, что запись одной таблицы указывает на запись в другой таблице игнорируя содержимое этих записей. И при изменении значений в справочнике таблица, которая использует это значение никогда не узнает об этом.
Если бы ID записи вычислялся как функция от содержимого одного или нескольких полей, то при их изменении событие передавалось бы по всей цепочке связей и позволяло бы на каждом этапе запустить проверку допустимости этих изменений или произвести какие-либо другие действия.
Проблема опять таки в коллизиях.
Частичное решение проблемы в увеличении размера результата хэш-функции.
Заключение
Предложенный метод повышения производительности не учитывает реальные данные. Даже предложенный А.Фуллером запрос неявно создает обычные строковые индексы, что делает бесполезным использование хэш-функции.
При правильной нормализации данных эффективность хэш-функции для поиска данных не лучше, чем поиск по словарям.
И, наконец, хэш-функция не позволяет производит частичный или последовательный поиск, что существенно органичивает возможности самой БД.
Хэш-функции могут использоваться в небольших таблицах для получения уникального ключа в случае если эта таблица является справочником и до промышленного использования есть возможно проверить, что ВСЕ введенные значения дают уникальные хэш-значения и коллизии отсутствуют.
Полезная литература:
- Иванов М.А., Чугунков И.В. "Теория, применение и оценка качества генераторов псевдослучайных последовательностей", изд. "Кудиц-Образ", М., 2003г
- ТИИЭР т.64, No.12 декабрь 1976г Ф.Дж.Макульямс, Н.Дж.Слоан, "Псевдослучайные последовательности и таблицы".
- Д.Кнут "Искусство программирования для ЭВМ" т.3 "Сортировка и поиск" глава 6.4 "Хэширование" изд."Мир", М., 1978г.