Hex-Zeichen performant in Datenbank

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Hex-Zeichen performant in Datenbank

    Hi,
    ich würde meine DB gerne optimieren. Ich nutze sha1 Datensätze als Primary Key. Die Zeichenlänge ist immer gleich, deswegen nutze ich CHAR(40) als Spaltentyp. Datenbanken sind bei fixen Zeilen- und Indexlängen deutlich performanter.

    Als Zeichensatz hatte ich global UTF8 genutzt. Nach RFC 3629 ist spezifiziert, dass UTF8 ein bis vier Bytes je Zeichen belegt.
    MySQL unterstützt drei Bytes, siehe dazu dev.mysql.com/doc/refman/5.0/en/charset-unicode.html.
    Für mein CHAR(40) werden also 120 Bytes (40*3) reserviert.

    Nun ärgere ich mich, dass meine Dateien immer größer und größer werden, dabei nutzt mein "Alphabet" gerademal 16 Zeichen von 128 möglichen (2^7) Alphabetzeichen, die sowieso reserviert sind.

    Schritt 1 war erstmal mich von UTF8 zu verabschieden und aufs kleinere ASCII zu wechseln.

    Quellcode

    1. ALTER TABLE `tabelle` CHANGE `spalte` `spalte` CHAR( 40 ) CHARACTER SET ASCII COLLATE ascii_general_ci NOT NULL;


    Dadurch ist der Datensatz in der Tat auf etwa ein drittel reduziert worden:

    Quellcode

    1. utf8_general_ci
    2. Daten 16,550,8 KiB
    3. Index 8,566,0 KiB
    4. Insgesamt 25,116,8 KiB
    6. ascii_general_ci
    7. Daten 6,286,7 KiB
    8. Index 8,566,0 KiB
    9. Insgesamt 14,852,7 KiB


    Leider habe ich festgestellt, dass der Index gleich blieb. Das der Index optimiert ist, liegt am Binary Tree wie er eben bei MyISAM und InnoDB immer genutzt wird.
    Man sollte sich also eher freuen, dass utf8 die Sache nicht viel langsamer macht ;) Problem für mich, ist dass der Index irgendwann nicht mehr in den Arbeitspeicher passt.

    Hierfür gibt es zwei Lösungen.

    sha1 ist ein guter Hashing Algorithmus und damit schließen wir bei einer Index Länger von ~6 Zeichen schon ziemlich viele Datensätze aus, die wir uns vom Filesystem laden können.
    Lösung "eins" wäre also ein partieller Index auf der sha1 Spalte. Nachteil am partiellen Index ist, dass wir mit der Festplatte (oder dem Festplattencache) in Kontakt kommen.
    Für eine andere Optimierung habe ich nämlich "spalte 2" als Covering Index schon hinzugefügt, damit beide Spalten aus dem Arbeitsspeicher geladen werden.

    Lösung "zwei" ist es die Daten stattdessen weiter zu komprimieren.
    Man könnte den Zeichenraum also von 2^4 Hexzeichen also auf 2^7 ASCII Zeichen umzurechnen und die Zeichenlänge damit von 40 Byte auf xx Byte zu reduzieren.
    Dafür würde man wieder CPU Zeit verschwenden. Haltet ihr das für eine gute Lösung? Ich muss mal ausrechnen wieviel Platz ich tatsächlich sparen würde.

  • Ganz brachial gefragt, wieso SHA1 primary key? Könntest du nicht durchnummerieren (int, auto_increment) und die SHA1 in eine andere Spalte legen als PK (ind die indizieren). Ändert erstmal nichts am Problem, aber MySQL legt doch sowieso einen Index für den PK an, der wäre dann ja schonmal kleiner. Ich nehme an, dass du das gemacht hast, weil deine häufigste Zugriffsart über den SHA kommt. Aber bei einem partiellen Index fängst du dir doch mit Sicherheit Kollisionen ein, sodass du danach möglicherweise aus mehrern Spalten auswählen musst.
    ~ mfg SeBa

    Ich beantworte keine PMs zu Computer-/Programmierproblemen. Bitte wendet euch an das entsprechende Forum.

    [Blockierte Grafik: http://i.creativecommons.org/l/by-sa/3.0/80x15.png]

  • d0nut schrieb:

    Leider habe ich festgestellt, dass der Index gleich blieb. Das der Index optimiert ist, liegt am Binary Tree wie er eben bei MyISAM und InnoDB immer genutzt wird.
    Man sollte sich also eher freuen, dass utf8 die Sache nicht viel langsamer macht ;) Problem für mich, ist dass der Index irgendwann nicht mehr in den Arbeitspeicher passt.

    Ich denke eher, dass es damit zusammenhängt, dass alle ASCII Zeichen in UTF8 und ASCII genau die selbe größe haben, nämlich 1 Byte und somit für Hexzahlen das Encoding keine allzugroße Rolle spielt.


    Müssen es denn unbedingt Hashes als Primary Key sein? Mal abgesehen davon, dass ich davon ausgehe, dass Ganzzahl-Indexe generell perfomanter sind als Char-Indexe hast du da ja unfassbar viel Overhead drin. Selbst wenn du nur 160bit für jeden Key bräuchtest is das noch mindestens das 5fache von dem was du bräuchtest um jedem Datensatz nen eindeutigen Key geben zu können.

  • Hi,

    du schreibst ja selber, dass die Mysql Engines mit dem Binary Tree arbeiten. Dann dürfte doch die Performance total in den Keller gehen, wenn du den PK hasht.
    Die DB ist ja überhaupt nichtmehr in der Lage die Indizies intern richtig sortieren zu können, was ja fast immer auf einen Tablescan hinausläuft, wenn man nach dem PK sucht.

    Das würde mich mal interessieren. Was spuckt denn Explain aus ? :)


    Man könnte den Zeichenraum also von 2^4 Hexzeichen also auf 2^7 ASCII Zeichen umzurechnen und die Zeichenlänge damit von 40 Byte auf xx Byte zu reduzieren.

    Das versteh ich nicht. Char bleibt ja Char, egal ob du nur Hexzahlen oder auch ASCII abspeicherst, es werden bei UTF8 ja immer 3byte reserviert und einen HEX Datentyp hab ich bei MySql nicht gesehen. Inwiefern möchtest du das denn umrechnen ?


    Ich hab grad gesehen, dass es bei MySQL BIT als Datentyp gibt.
    Ein sha1 ist ja eine 40 Zeichen lange Hexzahl, was 160 Bit (20Byte) entspricht.

    Für das Char(40) werden 120 Bytes reserviert, was 100Byte pro Spalte Mehrverbrauch im Gegensatz zu Bit(160) wäre.
    Ich weiss nicht, wie es mit der Performance und der Umrechnung aussieht, das müsstest du testen, was im Endeffekt besser ist, aber es spart bei den gehashten Werten eine Menge Speicherplatz. (Falls es denn überhaupt so funktioniert)

  • Genau durchschaut :)
    Der tatsächliche PK ist in der Tat ein auto increment integer, aber ich brauche eine persistene und eindeutige Session ID um auf die UserID zu gelangen. Das jeder Benutzer die Session ID mitbringt, macht es den Hauptteil der Requests aus.

    @Rondrer.. um die Authentifizierung sicher zu halten benötige ich auch Hashing, damit nicht jeder eine beliebige Identität annehmen kann.
    Aber guter Einwand... wenn man stattdessen ein Verschlüsselung nutzen könnte, würde ich natürlich meinen Integer Lookup machen müssen. Verschlüsselung heißt für mich aber immer, dass ich auch entschlüsseln kann.. hm..

    Der partielle Index hilft mir nur zu vermeiden, dass mein Index nicht mehr in den Arbeitsspeicher passt. Um so mehr Stellen ich aus dem Index eliminiere, um so langsamer wird die Anwendung natürlich, weil für die letzten Zeichen ein Tablescan gemacht wird :(

    @vince.. ich hashe nicht live, sondern speichere den gehashten Wert als Index. Damit sind weder Tablescans noch Festplattenzugriffe nötig (noch passt der Index in den RAM).

    Zur Umrechnung habe ich mir noch keine groooßen Gedanken gemacht.. das Verfahren klingt mir noch zu befremdlich ;)
    Ein ASCII "G" wäre nach meiner Definition ein hexadezimales "1"+"F", ein ASCII "H" ein hexadezimales "2F".
    Somit brauche ich statt 2 Hex-Zeichen nur ein ASCII-Zeichen speichern.

    Deine Rechnung gefällt mit den Bits gefällt mir auch:)