MySQL: Sortierung einer Stringliste optimieren

Hallo.

Ich habe eine Liste mit mehr als 100.000 Namen und möchte die Sortierung gern optimieren. Also anstatt "SELECT .. ORDER BY username ASC" möchte ich einen numerischen Wert als Index setzen können, um das Ganze zu beschleunigen.

Meine erste Idee war die Liste zu sortieren und dann eine Index-Variable einzuführen. Also sowas zu machen:

UPDATE table SET idx = @rownum:=IFNULL(@rownum, 0)+1 ORDER BY username ASC

und dann kann ich "SELECT .. ORDER BY idx ASC" verwenden, was wesentlich schneller ist. Mein Problem bei dieser Methode ist, dass ich ständig neue Namen einfüge und somit die komplette Liste ständig aktualisiert müsste, was enorm viel Zeit kostet und damit unbrauchbar ist. Ich benötige es immer aktuell.

Ich suche eine Methode die aus einem maximal 255 langen STRING einen ganzahligen Wert macht, welchen man als Index für die Sortierung verwenden kann. Eine Überlegung war etwas mit FLOAT zu verwenden, aber Performance-Test gegenüber INTEGER bescheinigen dem kein gutes Ergebnis.

Optimal wäre das man einfach den STRING nimmt und daraus einen Wert macht und in die Liste einfügt ohne diese weiter bearbeiten zu müssen. Kennt da eventuell irgendjemand was passendes?

hustbaer

Erm...
Für sowas haben Datenbanken Indexe. Setze einen Index auf das Stringfeld und fertig. Dann ist das Sortieren quasi gratis. Wenn du die Zeilen quasi immer nur in dieser Reihenfolge sortiert brauchst dann setz einen Clustered-Index - dann ist nicht nur die Sortierung gratis, sondern die Zeilen stehen dann auch wirklich sortiert in der Tabelle.

Ansonsten kannst du noch die Integer-Werte mit grösseren Sprüngen verteilen - bei 100.000 Zeilen z.B. 4 Mrd / 100.000 = 40.000er Sprünge.
Also die erste Zeile bekommt 0 die zweite 40.000 die dritte 80.000 usw.
Beim Einfügen dann einfach (a+b)/2 rechnen. Und bei a + 1 == b musst du alles neu indizieren.

hustbaer schrieb:

Erm...
Für sowas haben Datenbanken Indexe. Setze einen Index auf das Stringfeld und fertig. Dann ist das Sortieren quasi gratis. Wenn du die Zeilen quasi immer nur in dieser Reihenfolge sortiert brauchst dann setz einen Clustered-Index - dann ist nicht nur die Sortierung gratis, sondern die Zeilen stehen dann auch wirklich sortiert in der Tabelle.

Von Cluster-Index habe ich noch nichts gehört.
Deine Annahme das ein Index auf VARCHAR das selbe wäre wie auf ein INTEGER ist jedoch falsch. Falls ich das so richtig verstanden habe.

Ein Beispiel:

SELECT SQL_NO_CACHE Title FROM `table` ORDER BY idx LIMIT 5000,50

SELECT SQL_NO_CACHE Title FROM `table` ORDER BY Title LIMIT 5000,50

Das erste mit dem INTEGER ist doppelt so schnell wie ein INDEX auf Title. Der Performance Unterschied macht sich erst mit LIMIT (Seitenauswahl) bemerkbar. Ohne Limit, also nur die ersten Ergebnisse, sind beide gleich schnell. Es lohnt sich also scheinbar doch dies anders zu lösen.

hustbaer schrieb:

Ansonsten kannst du noch die Integer-Werte mit grösseren Sprüngen verteilen - bei 100.000 Zeilen z.B. 4 Mrd / 100.000 = 40.000er Sprünge.
Also die erste Zeile bekommt 0 die zweite 40.000 die dritte 80.000 usw.
Beim Einfügen dann einfach (a+b)/2 rechnen. Und bei a + 1 == b musst du alles neu indizieren.

Ja, das wäre eine komplizierte Möglichkeit, die mir auch schon in Sinn kam. Ist ja dann ähnlich dem FLOAT. Gibt es keine Möglichkeit aus einem String eine Art Summe zu bilden wobei jede Position im String eine "Gewichtung" erhält? So das der erste Buchstabe eine höhe Gewichtung hat und dann weiter nach rechts immer niedriger wird? Jedenfalls soetwas in der Art wäre glaube ich eher sinnvoll. Wenn es so etwas gibt.

hustbaer

Es heisst ja auch nicht Cluster Index es heisst Clustered Index. Und wenn du davon noch nix gehört hast dann tu es googeln. Ob MySQL das kann weiss ich nicht, MSSQL kann es, und Oracle auch wenn ich mich richtig erinnere.
Der Vorteil von Clustered Indexen ist allerdings vor allem dass der Bookmark-Lookup entfällt - d.h. es geht schneller wenn du z.B. die ersten 1000 Zeilen haben willst. Wenn du dagegen erstmal 5000 Zeilen überspringen willst, aber dann nur 50 mickrige Zeilen selecten, dann könnte sein dass es mit Clustered Index sogar langsamer wird.

Und ja natürlich macht es einen Unterschied ob du nen Index auf VARCHAR oder INT hast wenn du gleich mal ein paar tausend Datensätze überspringen willst.
Weil halt der VARCHAR Index natürlich grösser ist als der INT Index. Nur ist der Unterschied oft verschmerzbar. Wo es dagegen wieder wurscht ist, ist wenn du den Startwert über WHERE indexedString >= 'blah' angeben kannst. Was beim "paginieren" natürlich i.A. nicht geht.

Was deine "gewichtete Summe" angeht... ein INT hat 4 Byte, und in 4 Byte bekommst du halt nicht viel mehr als 4 Zeichen an Information unter - und selbst das nur wenn du ohne Unicode auskommst. Und du wirst es vor allen nicht Kollisionsfrei hinbekommen. So lange du keinen Plan hast wie du mit Kollisionen umgehst brauchst du dir also mMn. keine Gedanken über die beste String -> INT Abbilsund zu machen.
Und Plan wie man da mit Kollisionen umgehen könnte fällt mir kein sinnvoller ein.

Dein Wunsch alle für die Sortierung nötigen Informationen in einen INT zu packen, ohne dass du die Werte dynamisch anpassen musst, und im Worst-Case einen riesen Haufen Keys updaten, ist mMn. auch von vorn herein zum Scheitern verurteilt. Das kann mMn. gar nicht gehen.