Использование хэш-ключей в базах данных первоисточник Рассмотрим это предложение: Что такое хэш-функция ?Хэш-функцией называется односторонняя функция, предназначенная для получения дайджеста или "отпечатков пальцев" файла, сообщения или некоторого блока данных. Хэш-код создается функцией Н: h = H (M) Где М является сообщением произвольной длины и h является хэш-кодом фиксированной длины. Хэш-функция Н, которая используется для аутентификации сообщений, должна обладать следующими свойствами:
Первые три свойства требуют, чтобы хэш-функция создавала хэш-код для любого сообщения. Хэш-функция, которая удовлетворяет первым пяти свойствам, называется простой или слабой хэш-функцией. Если кроме того выполняется шестое свойство, то такая функция называется сильной хэш-функцией. Однако, так как исходное сообщение имеет любую, а выходное фиксированную длину, то ВСЕГДА будут возникать коллизии. Как предлагается использовать ? "Пользователь (либо человек, либо приложение) запрашивает некоторые значения. Вроде все получается красиво. Но! Если приложение запрашивает одно точное значение, то таких значений немного и результатом поиска будет 1 строка. И тогда, возможно, это будет работать. Если значений много, то сначала нужно найти это "одно точное значение". Если точное значение неизвестно, то пользователь осуществляет частичный поиск, типа "найди то, не знаю что". Это либо часть строки, либо одно из текстовых полей индекса. В этом случае хэш-индекс работать не будет, потому что хэш-функция части не соответствует хэш-функции целого. Значит необходимо оставить и стандартный способ индексирования таблицы. И тем самым затраты как времени, так и размера ключей удваиваются. Но даже если имеется точное значение, которое нужно найти, как избежать ошибок в самой БД. В качестве примера — результаты анализа БД "ГИБДД 2002 Автотранспорт Москвы февраль 2002 г". При таком количестве ошибок найти точное значение не удается. Если слово "Александр" записано 153 разными способами, то какое значение нужно искать? Предложенный Фуллером запрос работает только в MSSQL и даже в этом случае зависит от реализации оптимизатора запросов. SELECT * FROM Adventureworks.HumanResources.Department Оптимизатор может сначала взять поля Name и GroupName, построить по ним индекс, а затем использовать HashKey. Таким образом никакой экономии не происходит. Для того чтобы запрос работал в любом случае он должен быть преобразован следующим образом: Select * from (Select * from Adventureworks.HumanResources.Department where HAshKey=@ID) Конечно, если построить индекс, который бы обеспечивал уникальность значений из нескольких строковых полей... Но, хэш-функция гарантировать уникальность не может, особенно при больших размерах таблицы. А как в этом случае (допустим что в хэш-функцию входят Имя, Отчество и Фамилия) получить список уникальных Фамилий? Этот простой запрос ставит в тупик самые мощные компьютеры и здесь хотелось бы получить ускорение. Но хэш-функция и здесь не спасает. Как решать подобную задачу на очень больших таблицах? Как ни странно нужно учится у классиков. Если встречается очень большая таблица с текстовыми полями — это означает, что таблица ненормализована. Например, таблица содержащая сведения о 25 миллионах людей, в которой нужно искать данные по именам, отчествам и фамилиям, обладает громадной избыточностью и требует нормализации. Это реальная таблица — БД "Прописка Москвы и Московской области 2005 г". Даже с учетом того, что в таблице немерянное количество ошибок, количество уникальных фамилий составляет 669500. После исправления ошибок останется около 10000. Количество уникальных имен составляет 84500. После исправления ошибок останется около 3000. Таким образом, за счет того, что Имена, Отчества и Фамилии выносятся в отдельные таблицы, поиск осуществляется в очень маленьких таблицах, для которых по утверждениям А.Фуллера "... вы можете не заметить какого-либо отрицательного влияния такого индекса". А выборка из большой таблицы осуществляется с помощью целочисленного индекса, и совершенно безразлично каким образом это число получено. При этом остается возможность поиска по части имени или фамилии, а также последовательный поиск. Как ни странно, нормализация одновременно устраняет ошибки в БД, подобные вышеописанным. А также существенно уменьшается размер БД. Вообще, наличие в очень больших таблицах текстовых полей означает, что эти поля не являются определяющими, т.е. по ним не производится поиск. Они как правило большие и по ним невозможно построить индекс. В остальных случаях за счет избыточности текста практически всегда их можно разделить на термины и нормализовать всю таблицу. А для чего хотелось бы использовать Хэш-функции ?Сразу скажу — именно "хотелось бы" — так как коллизии - это основная проблема, которая мешает использовать эти приемы на практике. 1) Хотелось бы построить уникальный (primary) индекс по правилам с условиями. Например, нужно внести запись о человеке. Уникальный индекс построен по правилу: Фамилия, Имя, Отчество, Дата_Рождения. Но в момент внесения записи дата рождения и/или отчество неизвестно. А известно, например, место работы или другая информация. Тогда можно написать следующий триггер для вставки: CREATE TRIGGER VIPerson_INSERT FOR VIPerson Такой триггер позволял бы получать уникальный индекс даже в том случае, когда одно или несколько полей имеют значение null, недопустимое для обычного индекса. Кроме того, если поле VIPBrDay имеет значение Null, то вместо него подставляется другое поле VIPDataX с тем чтобы отличить одну запись от другой. При этом неважно нормализована таблица или нет. Принцип работает и в том и в другом случае. Все бы было хорошо, но коллизии начались при размере таблицы около 300000 записей. 2) При использовании генераторов для получения ID записи, связи между таблицами обеспечивают только декларативную целостность. Это означает, что запись одной таблицы указывает на запись в другой таблице игнорируя содержимое этих записей. И при изменении значений в справочнике таблица, которая использует это значение никогда не узнает об этом. ЗаключениеПредложенный метод повышения производительности не учитывает реальные данные. Даже предложенный А.Фуллером запрос неявно создает обычные строковые индексы, что делает бесполезным использование хэш-функции. При правильной нормализации данных эффективность хэш-функции для поиска данных не лучше, чем поиск по словарям. И, наконец, хэш-функция не позволяет производит частичный или последовательный поиск, что существенно органичивает возможности самой БД. Хэш-функции могут использоваться в небольших таблицах для получения уникального ключа в случае если эта таблица является справочником и до промышленного использования есть возможно проверить, что ВСЕ введенные значения дают уникальные хэш-значения и коллизии отсутствуют. Полезная литература:
11.06.2007 |
 faq(c) |
