Хеш-индексы SQL Server

Question

При использовании типа столбца CHECKSUM для искусственного создания хеш-индекса является ли поиск на самом деле O (1) или он все еще O (lg n), как для кластерного индекса? У меня есть таблица, из которой я буду выбирать, основываясь на столбце идентификатора, и мне нужно, чтобы поиск выполнялся как можно быстрее, поэтому является ли кластерный индекс самым быстрым из возможных вариантов? Я ищу что-то, что обеспечит производительность O (1).

Answer 1

Хорошо, 2 балла.
Функция SQL CHECKSUM не создает хеш-значения. Это фактически вычисляет значение CRC. Это не очень хороший кандидат, чтобы основывать проверку хэша, потому что будет относительно большое количество коллизий. Вы должны проверить функцию hash_bytes, если хотите использовать функцию хеширования.
Во-вторых, вы на самом деле не создаете хеш-индекс. Вы создаете обычное b-дерево для хеш-значения, поэтому время поиска будет точно таким же, как и для любого другого индекса b-дерева в типе данных аналогичного размера.
Существует вероятность того, что вы могли бы получить небольшую производительность, используя CRC или хеш с длинным значением varchar, чтобы можно было сравнивать меньшее количество байтов, но при сравнении строк проверяется только столько байтов, сколько необходимо, до первый символ, который не совпадает, и если вы совпадаете с хэшированным значением, вам все равно нужно дважды проверить фактическое значение. Таким образом, если у вас нет много очень похожих строк, вы, вероятно, в конечном итоге будете сравнивать БОЛЬШЕ байтов, используя хэш (или CRC).

Короче говоря, я не думаю, что это разумный план, но, как и в случае всех оптимизаций, вы должны проверить его в своем конкретном случае, а затем принять решение. Мне было бы интересно увидеть ваши результаты, если вы захотите опубликовать их. И я не верю, что есть более быстрый способ найти строку на сервере SQL, чем с помощью кластерного индекса.

Если вам не безразлично, Ingres (от CA) может создать хеш-индексы, которые затем достигнут O (1). могут быть и другие RDBM, которые также поддерживают истинные хеш-индексы.

Answer 2

Я не думаю, что SQL-сервер изначально имеет индекс на основе хеш-таблицы. В документации BOL говорится о построении стандартного (древовидного) индекса для вычисляемого значения. Это не то же самое, что Линейная хеш-таблица , которая является структурой индекса, доступной на некоторых платформах СУБД, но не SQL Server (AFAIK).

Вы можете получить некоторую выгоду от использования метода, описанного в этом сообщении в блоге , для хеширования больших строковых значений, таких как URL, для более быстрого поиска. Однако базовый индекс по-прежнему является древовидной структурой и имеет значение O (Log N).

Answer 3

Вы можете попытаться настроить использование хеш-соединения, вы можете посмотреть план выполнения, чтобы убедиться, что хеш-соединение действительно используется. Когда используются хеш-объединения, SQL Server все равно сначала создает хеш-таблицу как часть выполнения отдельного запроса. Я считаю, что индексы никогда не хранятся в виде хэша, только в виде деревьев.

В общем случае я бы не создавал искусственный столбец хэшей, если вы не выполняете точные сопоставления с потенциально большими строками или двоичными объектами (как упоминает pipTheGeek). Я просто хотел добавить, что иногда это необходимо, поскольку строки могут быть слишком большими, чтобы поместиться в ключ индекса. Существует ограничение на размер индексных ключей, я думаю, 2k для SQL Server.

Конечно, в ваше объединение необходимо включить столбец хеша и столбец источника, чтобы устранить любые неоднозначности, возникающие в результате хеширования.

Answer 4

Нет никакого преимущества в поиске индексированного CHECKSUM над кластеризованным индексом в поле ID, если поле идентификатора - int, поскольку оба будут выполнять поиск кластерного индекса. Кроме того, CHECKSUM столбца int всегда возвращает то же значение, что и столбец (то есть CHECKSUM (535) = 535). Однако поиск в CHECKSUM, как правило, будет работать лучше, если идентификатор представляет собой длинный символьный столбец.