Mysql PHP Index-Optimierung: Index-Werte optimieren mittels CRC32-MD5-Hash

Im Artikel „Mysql PHP Index-Optimierung: Lange Index-Werte kürzen“ haben die Möglichkeit aufgezeigt, lange Datenbank-Varchar-Felder mittels MD5-Hash merklich zu verkürzen, um Plattenplatz zu sparen und die Performance deutlich zu erhöhen. Doch ganz so optimal ist der MD5-Hash nicht. Hier untersuchen wir nun eine andere Lösung:

Eigener Hash in MySQL aufbauen
Die Storage-Engines in MySQL bieten leider meistens keine Möglichkeit, Indizes per Hash aufzubauen (aktuell nur die Memory-Engine). Also müssen wir uns selbst darum kümmern. Vergleichbar ist das folgende Vorgehen mit der Speicherung von IP-Adressen (siehe „MySQL: IP-Adressen optimal speichern„), die ebenfalls nicht per varchar(15), sondern per Integer (nur vier Bytes!) erfolgen sollte.

MySQL bietet die mathematische Funktion „CRC32“. Diese MySQL-Funktion liefert uns mittels Umrechnung einen Integer zurück. Diese Umrechnung ist auf jedem Fall der oben beschrieben MD5-Lösung vorzuziehen, da der Speicherplatz deutlich kleiner und die Performance deutlich erhöht wird.

Feldanlage in MySQL + Index
url_crc int unsigned NOT NULL DEFAULT 0

Zugriff
SELECT * FROM meine_tabelle WHERE url_crc=CRC32(“http://sirmark.de”);

Mit der CRC-Methode erschlagen wir den Nachteil 1 (Zeichenkette immer 32-Zeichen lang) der MD5-Methode, minimieren den Speicherplatz und erhöhen die Performance noch einmal deutlich. Doch der Nachteil 2 bleibt: Auch diese Methode eignet sich nicht zur Rückrechnung des Feldinhaltes und kann bei völlig unterschiedlichen URLs (Strings) gleiche Werte zurückliefern.

Hash-Kollision ausschließen
Die Problematik, dass unterschiedliche String den gleichen Hash zurückliefern, kann je nach Anwendung zu einem Problem werden. Gerade mit der CRC32-Methode ist die Wahrscheinlichkeit von gleichen Hashs (Hash-Kollision) ein Vielfaches größer, als bei der MD5-Methode. Gehen Sie davon aus, dass Sie bei 100.000 Datensätzen mit mindestens einer Kollision rechnen müssen. Wenn Sie wie in unserem Beispiel eine URL per CRC32 optimieren und zusätzlich die URL im Klartext hinterlegen, benötigen Sie bei der Anfrage beide Werte.
Wenn wir in unserer Tabelle („meine_tabelle“) die Index-Spalte „url_crc“ und eine Textspalte „url“ (ohne Index) haben, dann genügt folgende Anfrage zur Eindeutigkeit:

SELECT * FROM meine_tabelle WHERE url_crc=CRC32(“http://sirmark.de”) AND url=’http://sirmark.de’;

Wichtig ist, dass die indexierte Spalte (“url_crc”) als erstes im SELECT abgefragt wird, da sonst der Index nicht greift!

Die 64bit-Hash-Abfrage in MySQL
MySQL liefert keine 64bit-CRC-Funktion. Wenn Sie jedoch mehr als 100.000 Datensätze in einer mittels CRC32-kodierten Funktion speichern, müssen Sie mit mindestens einer Hash-Kollision rechnen. Wenn Sie den eigentlichen Wert (in unserem Beispiel die URL im Klartext) nicht speichern möchten (da Sie den Wert nicht benötigen oder aus Sicherheitsgründen nicht speichern dürfen), dann können Sie den Hash erweitern. Wenn Sie einen zweiten eindeutigen Wert haben, hashen Sie diesen ebenfalls. Zusammen minimieren Sie die Möglichkeit einer Hash-Kollision deutlich.
In unserem Fall haben wir die Möglichkeit nicht. Also versuchen wir einen 64-Bit-Hash selbst zu generieren. Wir nutzen folgenden Trick: Aus unserer URL erzeugen wir noch zusätzlich einen MD5-Hash, nutzen jedoch nur einen Teil der 32 durch MD5 erzeugten Hash-Zeichenfolge, nämlich nur die letzten 16 Stellen:

SELECT MD5(‚http://sirmark.de‘) as MD5, RIGHT(MD5(‚http://sirmark.de‘),16) AS MyHash64

Zusammen mit der MySQL-Funktion CONV() erhalten wir nun eine Vergleichszahl, die die Möglichkeit einer Hash-Kollision deutlich minimiert. Conv arbeitet mit einer Genauigkeit von 64 Bit.

SELECT CONV(RIGHT(MD5(‚http://sirmark.de‘),16),16,10) AS MyHash64
Ergebnis: 18254737050769978686

GD Star Rating
loading...

Schreibe einen Kommentar