Быстрее ли искать большую строку в БД по ее хэш-коду?

Question

Если мне нужно извлечь большую строку из БД, быстрее ли искать ее, используя саму строку, или получу ли я ее путем хеширования строки и сохранения хеша в БД, а затем поиска на основе этого?

Если да, какой алгоритм хеширования следует использовать (безопасность не является проблемой, я ищу производительность)

Если это имеет значение: я использую C # и MSSQL2005

Answer 1

В целом: вероятно, нет, при условии, что столбец проиндексирован. Серверы баз данных предназначены для быстрого и эффективного поиска. Некоторые базы данных (например, Oracle) предоставляют параметры для построения индексов на основе хеширования.

Однако, в конце концов, на это может ответить только тестирование производительности с репрезентативными (вашими требованиями) данными и схемами использования.

Answer 2

Я был бы удивлен, если бы это дало огромное улучшение, и я бы рекомендовал не использовать ваши собственные оптимизации производительности для поиска в БД.

Если вы используете индекс базы данных, администратор базы данных может настраивать производительность с помощью проверенных и надежных методов. Жесткое программирование собственной оптимизации индекса предотвратит это и может помешать вам повысить производительность индексирования в будущих версиях БД.

Answer 3

Хотя я никогда не делал этого, звучит так, будто это будет работать в принципе. Есть вероятность, что вы можете получить ложные срабатывания, но это, вероятно, довольно тонкий.

Я бы пошел с быстрым алгоритмом, таким как MD5, так как вы не хотите тратить больше времени на хеширование строки, чем потребовалось бы вам для ее поиска.

Последнее, что я могу сказать, это то, что вы узнаете, будет ли лучше, если вы попробуете это и измерите производительность.

Answer 4

Первый - ИЗМЕРЯЙТЕ. Это единственный способ сказать наверняка.
Второе - если у вас нет проблем со скоростью поиска строки, то сделайте это просто и не используйте хэш.

Тем не менее, для вашего актуального вопроса (и просто потому, что это интересная мысль). Это зависит от того, насколько похожи строки. Помните, что движку БД не нужно сравнивать все символы в строке, достаточно только найти разницу. Если вы просматриваете 10 миллионов строк, которые начинаются с одинаковых 300 символов, то хеш почти наверняка будет быстрее. Однако, если вы ищете единственную строку, которая начинается с x, тогда сравнение строк может быть быстрее. Хотя я думаю, что SQL все равно придется получать всю строку с диска, даже если он тогда использует только первый байт (или первые несколько байтов для многобайтовых символов), поэтому общая длина строки все равно будет влиять.

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

Вы также можете рассмотреть возможность использования функции CRC в SQL. Он выдает int, который будет еще быстрее интерпретироваться и быстрее вычисляться. Но вам придется дважды проверить результаты этого запроса, фактически протестировав строковые значения, потому что функция CRC не предназначена для такого рода использования и намного проще возвращать дублирующиеся значения. Вам нужно будет выполнить проверку CRC или Hash в одном запросе, а затем получить внешний запрос, который сравнивает строки. Вы также захотите просмотреть сгенерированный QEP, чтобы убедиться, что оптимизатор обрабатывает запрос в том порядке, который вы намеревались. Возможно, сначала будет решено выполнить сравнение строк, а затем - проверки CRC или Hash.

Как заметил кто-то другой, это только хорошо, если вы делаете точное совпадение. Хеш не может помочь, если вы пытаетесь выполнить какой-либо диапазон или частичное совпадение.

Answer 5

«Идеальный» ответ - безусловно, да. Сопоставление строк с индексированным столбцом всегда будет медленнее, чем сопоставление хеш-значения, хранящегося в столбце индекса. Это то, для чего предназначены хэш-значения, потому что они берут большой набор данных (например, 3000 точек сравнения, по одной на символ) и объединяют его в меньший набор данных (например, 16 точек сравнения, по одной на байт).

Таким образом, наиболее оптимизированный инструмент сравнения строк будет медленнее, чем оптимизированное сравнение хеш-значений.

Однако, как уже отмечалось, реализация собственной оптимизированной хэш-функции опасна и, вероятно, не будет успешной. (Я пытался и с треском провалился) Хеш-коллизии не представляют особой проблемы, потому что тогда вам просто придется прибегнуть к алгоритму сопоставления строк, что означает, что он будет (в худшем случае) точно таким же быстрым, как и метод сравнения строк.

Но это все при условии, что ваше хеширование выполнено оптимальным образом (что, вероятно, не будет) и что не будет никаких ошибок в вашем компоненте хеширования (что будет), и что производительность увеличение будет стоить усилий (вероятно, нет). Алгоритмы сравнения строк, особенно в индексированных столбцах, уже довольно быстрые, и усилие хеширования (время программиста), вероятно, будет намного выше, чем ваш возможный выигрыш.

А если вы хотите узнать о производительности, просто измерьте ее.

Answer 6

СОВЕТ: если вы собираетесь хранить хеш в базе данных, хеш MD5 всегда составляет 16 байтов, поэтому его можно сохранить в столбце uniqueidentifier (и System.Guid в .NET)

Это может дать некоторый выигрыш в производительности по сравнению с сохранением хэшей другим способом (я использую этот метод для проверки изменений полей двоичного файла / ntext, но не для строк / nvarchars).

Answer 7

Вы проводите матч равенство или матч ? Для совпадения равенства вы должны позволить БД обработать это (но добавить некластеризованный индекс) и просто проверить с помощью WHERE table.Foo = @foo. Для соответствия соответствия вам, возможно, следует взглянуть на полнотекстовый индекс .

Answer 8

Если ваши строки короткие (в целом менее 100 символов), строки будут быстрее.

Если строки большие, HASH поиск может и, скорее всего, будет быстрее.

HashBytes(MD4) кажется самым быстрым на DML.

Answer 9

Если вы используете поле фиксированной длины и индекс, он, вероятно, будет быстрее ...

Answer 10

Я запутался и, возможно, неправильно понял ваш вопрос.

Если у вас уже есть строка (таким образом, вы можете вычислить хеш), зачем вам ее извлекать?

Возможно, вы используете большую строку в качестве ключа для чего-то?