Wenn Sie den CHECKSUM-Spaltentyp verwenden, um künstlich einen Hash-Index zu erstellen, ist das Nachschlagen tatsächlich O (1) oder ist es immer noch O (lg n) wie für einen gruppierten Index? Ich habe eine Tabelle, aus der ich basierend auf ihrer ID-Spalte auswählen werde und ich brauche die Suche so schnell wie möglich, also ist der Clustered Index die schnellste mögliche Option? Ich suche nach etwas, das O (1) Leistung bietet.SQL Server-Hash-Indizes
Okay, 2 Punkte.
Die SQL CHECKSUM-Funktion erzeugt keinen Hash-Wert. Es berechnet tatsächlich einen CRC-Wert. Es ist kein sehr guter Kandidat, um eine Hash-Prüfung zu begründen, da es eine relativ große Anzahl von Kollisionen geben wird. Sie sollten die Funktion hash_bytes überprüfen, wenn Sie eine Hash-Funktion wünschen.
Zweitens erstellen Sie nicht wirklich einen Hash-Index. Sie erstellen einen normalen B-Baum auf einem Hash-Wert, so dass die Nachschlagezeit genau so ist wie bei jedem anderen B-Baum-Index bei einem ähnlich großen Datentyp.
Es besteht die Möglichkeit, dass Sie etwas Leistung erzielen, indem Sie einen CRC oder Hash eines langen Varchar-Werts verwenden, um Vergleiche einer kleineren Anzahl von Bytes zu ermöglichen. Der Zeichenfolgenvergleich prüft jedoch nur so viele Bytes wie nötig bis zum ersten Zeichen, das nicht übereinstimmt, und wenn Sie den Hashwert vergleichen, müssen Sie den tatsächlichen Wert trotzdem noch einmal überprüfen. Wenn Sie also nicht viele sehr ähnliche Strings haben, werden Sie wahrscheinlich MEHR Bytes mit dem Hash (oder CRC) vergleichen.
Kurz gesagt, ich denke nicht, dass dies ein vernünftiger Plan ist, aber wie bei allen Optimierungen sollten Sie es in Ihrem speziellen Fall testen und dann entscheiden. Ich wäre daran interessiert, Ihre Ergebnisse zu sehen, wenn Sie sie veröffentlichen möchten. Und ich glaube nicht, dass es einen schnelleren Weg gibt, eine Zeile im SQL-Server zu lokalisieren, als mit einem gruppierten Index.
Falls Sie sich interessieren, kann Ingres (von CA) Hash-Indizes erstellen, die dann O (1) erreichen würden. Es kann andere RDBMs geben, die auch echte Hash-Indizes unterstützen.
Es gibt keinen Vorteil, eine indexierte CHECKSUM über einen gruppierten Index im ID-Feld zu durchsuchen, wenn das ID-Feld ein int ist, da beide eine gruppierte Indexsuche durchführen. Außerdem gibt eine CHECKSUM einer Int-Spalte immer denselben Wert wie die Spalte zurück (d. H. CHECKSUM (535) = 535). Eine CHECKSUM-Suche funktioniert jedoch im Allgemeinen besser, wenn die ID eine lange Zeichenspalte ist.
Gibt es also eine bessere Leistung als ein gruppierter Index? Der Clustered Index ist immer noch O (lg n) und ich habe nach O (1) gesucht. – eulerfx
Sie können versuchen, einen Hash-Join einzurichten, Sie können jedoch den Ausführungsplan überprüfen, um zu überprüfen, ob tatsächlich ein Hash-Join verwendet wird. Wenn Hash-Joins verwendet werden, erstellt SQL Server die Hash-Tabelle immer noch als Teil der Ausführung der einzelnen Abfrage. Ich glaube, Indizes werden niemals als Hash gespeichert, sondern nur als Bäume.
Im Allgemeinen würde ich keine künstliche Hash-Spalte erstellen, es sei denn, Sie tun exakte Übereinstimmungen mit möglicherweise großen Zeichenfolgen oder binären Blobs (wie PipTheGeek erwähnt). Ich wollte nur hinzufügen, dass dies manchmal notwendig ist, da Strings möglicherweise zu groß sind, um in einen Indexschlüssel zu passen. Es gibt ein Limit für die Größe der Indexschlüssel von 2k für SQL Server.
Natürlich müssen Sie in Ihrem Join die Hash-Spalte und die Quellspalte einschließen, um alle Mehrdeutigkeiten zu beheben, die sich aus dem Hash ergeben.
SQL Server hat eine [900-Byte-Grenze] (http://stackoverflow.com/a/12717441/880904) für die maximale Gesamtgröße aller Indexschlüsselspalten. –
Ich glaube nicht, dass SQL Server nativ einen Hash-Tabelle basierten Index hat. Die BOL documentation spricht über die Erstellung eines Standard (Baum) Index für einen berechneten Wert. Dies ist nicht dasselbe wie eine Linear Hash Table, die eine Indexstruktur ist, die auf einigen DBMS-Plattformen verfügbar ist, aber nicht SQL Server (AFAIK).
Sie können von der Verwendung der in this blog post beschriebenen Technik profitieren, um große Zeichenfolgenwerte wie URLs für schnellere Suche zu hashen. Der zugrunde liegende Index ist jedoch immer noch eine Baumstruktur und ist O (Log N).
UPDATE: In-Memory SQL Server-Tabellen verfügen über Hash-Tabellen-basierte Indexfunktionen. –
stimme ich nicht zu. Die CRCs sollten ziemlich zufällig sein, nachdem Sie einen Teil davon durch die Anzahl der Buckets modifiziert haben. Ich sehe nicht, warum Sie denken, dass es "eine relativ große Anzahl von Kollisionen" geben würde. – lkessler
Für einen Test habe ich nur auf Kollisionen auf einer Spalte von 11k Strings (meist URLs, also viele gleiche Anfangssegmente) überprüft. Mit BINARY_CHECKSUM habe ich 3 3-Wege-Kollisionen und 5 2-Wege-Kollisionen bekommen. Mit HASHBYTES habe ich keine, wie man es erwarten würde, sogar mit MD2. –