[mySQL] Effektiv auf viele Spalten sortieren

[AlecWhite]

Moin liebes Forum,

kennt jemand ein Möglichkeit eine Tabelle mit vielen VARCHAR Spalten (ca. 20) effizient zu sortieren (ca. 5-15 Mio Datensätze)? Könnte jetzt für jede Spalte einen Index anlegen, aber das ist....öh...sehr speicherintensiv (und afaik hat mySQL da so seine Grenzen, was die Anzahl der Indizes angeht).

Gibt es da bessere Möglichkeiten? Tabelle müsste sich auch effizient joinen lassen.

Bin echt für jede Idee dankbar, da ich langsam echt alles ausgetestet habe, aber die Performance ist doch arg mau.

[RMC]

effektiv oder effizient?

[AlecWhite]

Effizient..effektiv ja schon Order By :) - korrigiert :D

[DanMan]

Das kommt wie immer darauf an, nach welchen der Daten, die drinstehen du suchst, und welche du nur abrufst. Für die, die du suchst machst du einen Index. Du weißt, dass man Indizes über mehrere Spalten anlegen kann?

Was die Sortierung angeht: mehr wie ORDER BY gibts nicht, also auch kein verstecktes Leistungspotential. Da bringt dir auch ein Index nix. Evtl. könntest du die Daten auf mehrere Tabellen aufteilen, falls das bei dir Sinn macht.

[AlecWhite]

Klar kann ich ein Index über mehrere Spalten anlegen, aber: Das nützt mir nur etwas, wenn ich auch alle Spalten im Index durchsuche.

Beispiel: Index mit Spalten a, b und c

Suche nach a, b und c: Index kann verwendet werden
Suche nach a und b: Index kann verwendet werden
Suche nach a und c: Index kann nicht verwendet werden

Und was die Sortierung angeht: Ein Index bringt ordentlich was für die Sortierung. Hab die häufigsten Anfrage mal untersucht und die betreffende Tabelle mal danach indiziert - läuft wesentlich smoother. Im Execution Plan waren vorher viele temporäre Tabellen und "sort on disk" aufgelistet, jetzt kann die Sortierung über den Index realisiert werden.

Nur sind das über 20 Spalten und gesucht wird nach allen möglichen Kombinationen - für jede einen Index anlegen ist einfach nicht machbar.

[HonK_DD]

Versuch doch mal die Tabelle in mehrere einzelne zu zerlegen oder gehen die Abfragen größten Teils über alle Spalten?

[DanMan]

Und was die Sortierung angeht: Ein Index bringt ordentlich was für die Sortierung. Hab die häufigsten Anfrage mal untersucht und die betreffende Tabelle mal danach indiziert - läuft wesentlich smoother. Im Execution Plan waren vorher viele temporäre Tabellen und "sort on disk" aufgelistet, jetzt kann die Sortierung über den Index realisiert werden.
Der Schein trügt. Die Ergebnisse werden schneller gefunden, auf die Sortierung hat das keine direkten Auswirkungen. Zumindest wär mir das neu.
Nur sind das über 20 Spalten und gesucht wird nach allen möglichen Kombinationen - für jede einen Index anlegen ist einfach nicht machbar.
Das klingt nach unzureichender Normalisierung, wenn in einer Tabelle alle möglichen, verschiedenen Daten stehen.

Jedenfalls kenn ich keine pauschalen Wundertips. Man müsste mMn. schon dein komplettes Schema kennen um zu optimieren, weiß nicht wie die anderen das sehen.

[Gast]

Das klingt nach unzureichender Normalisierung, wenn in einer Tabelle alle möglichen, verschiedenen Daten stehen.


Normalisierung bringt aber auch nicht wirklich mehr Performance. Der Übergang von der 1. zur 2. Normalform bringt vielleicht mehr Performance, weil sich ggf. die Rows reduzieren. Ansonsten musst du mit Joins wieder alles zusammenführen und das kostet mehr. Bei reinen OLAP Anwendungsfällen sind eigentlich flache Tabellen besser geeignet, auch wenn man das vielleicht nicht pauschalisieren kann.

[Coda]

Der Schein trügt. Die Ergebnisse werden schneller gefunden, auf die Sortierung hat das keine direkten Auswirkungen. Zumindest wär mir das neu.
Der Index hilft in der Regel auch beim Sortieren. Das ist ja normalerweise ein B-Tree und den kann man natürlich auch in sortierter Reihenfolge durchlaufen in beide Richtungen.

Wenn es allerdings ein Hash-Index ist, dann nicht.

Edit: Kann man bei MySQL sogar spezifizieren beim Erzeugen des Index. "USING HASH" oder "USING BTREE". MyISAM und InnoDB können beide aber nur BTREE.

[AlecWhite]

@DanMan:
[...] MySQL can use an index to satisfy an ORDER BY clause without doing any extra sorting.

http://dev.mysql.com/doc/refman/5.0/en/order-by-optimization.html

Die Tabelle ist bereits in 3ter Normalform (und auf 4te und 5te will ich eigentlich nich gehen (zumal dazu einige Applikationen umgeschrieben werden müssten und das ist nicht drin))

Für das Problem ist es egal, ob ich 2 oder 20 Spalten habe. Mal als Beispiel:

Tabelle mit Kundennummer, Vorname, Nachname, Geburtsdatum

Das typische Anwendungsfall ist, dass die Daten entweder nach

Vorname, Nachname, Geburtsdatum
Nachname, Vorname, Geburtsdatum
Geburtsdatum, Nachname, Vorname
Geburtsdatum, Vorname, Nachname

aus der DB kommen müssen. Bereits bei 3 Spalten habe ich also 4 mögliche Sortierungen. Bei nur ein paar tausend Datensätzen ist das alles kein Problem, aber mit ein paar Millionen wird das nix mit schnellen auslesen. Kann jetzt 4 Indizes anlegen, dann geht alles fix, aber was mache ich bei,,,hmm...7 Spalten da bräuchte ich ja 64 Indizes....das geht unter mysql nicht und der Speicherplatz...hmm (na ja, da könnte ich ein Auge zudrücken)...und die Insert Performance kann ich dann auch in die Tonne treten.

[DanMan]

Normalisierung bringt aber auch nicht wirklich mehr Performance. Der Übergang von der 1. zur 2. Normalform bringt vielleicht mehr Performance, weil sich ggf. die Rows reduzieren. Ansonsten musst du mit Joins wieder alles zusammenführen und das kostet mehr. Bei reinen OLAP Anwendungsfällen sind eigentlich flache Tabellen besser geeignet, auch wenn man das vielleicht nicht pauschalisieren kann.
Stimmt natürlich. Bringt nur dann Geschwindigkeit, wenn durch das Aufteilen auf mehrere Tabellen Abfragen gezielter auf einzelne Tabellen erstellt werden können. Joins fressen das wieder auf, ja. Ansonsten bringt die Normalisierung an sich keine Geschwindigkeitsvorteile.
Der Index hilft in der Regel auch beim Sortieren. Das ist ja normalerweise ein B-Tree und den kann man natürlich auch in sortierter Reihenfolge durchlaufen in beide Richtungen.

Wenn es allerdings ein Hash-Index ist, dann nicht.

Edit: Kann man bei MySQL sogar spezifizieren beim Erzeugen des Index. "USING HASH" oder "USING BTREE". MyISAM und InnoDB können beide aber nur BTREE.
@DanMan:
http://dev.mysql.com/doc/refman/5.0/en/order-by-optimization.html

Ok, wieder was gelernt.

Die Tabelle ist bereits in 3ter Normalform (und auf 4te und 5te will ich eigentlich nich gehen (zumal dazu einige Applikationen umgeschrieben werden müssten und das ist nicht drin))

Für das Problem ist es egal, ob ich 2 oder 20 Spalten habe. Mal als Beispiel:

Tabelle mit Kundennummer, Vorname, Nachname, Geburtsdatum

Das typische Anwendungsfall ist, dass die Daten entweder nach

Vorname, Nachname, Geburtsdatum
Nachname, Vorname, Geburtsdatum
Geburtsdatum, Nachname, Vorname
Geburtsdatum, Vorname, Nachname

aus der DB kommen müssen. Bereits bei 3 Spalten habe ich also 4 mögliche Sortierungen. Bei nur ein paar tausend Datensätzen ist das alles kein Problem, aber mit ein paar Millionen wird das nix mit schnellen auslesen. Kann jetzt 4 Indizes anlegen, dann geht alles fix, aber was mache ich bei,,,hmm...7 Spalten da bräuchte ich ja 64 Indizes....das geht unter mysql nicht und der Speicherplatz...hmm (na ja, da könnte ich ein Auge zudrücken)...und die Insert Performance kann ich dann auch in die Tonne treten.
Richtig. Wäre das InnoDB Tabellenformat eine Option? Das sperrt nur die betroffene Zeile bei Updates/Inserts statt die ganze Tabelle wie bei MyIsam. Allerdings brauchen die Indizes da noch mehr Speicherplatz. :)

Ansonsten bleibt dir wirklich nur übrig alle Abfragen durchzugehen, und die Reihenfolge möglichst einheitlich zu halten, um damit hoffentlich die nötige Anzahl Indizes gering zu halten.

edit:
http://dev.mysql.com/doc/refman/5.0/en/internal-temporary-tables.html
http://docs.cellblue.nl/2007/03/17/easy-mysql-performance-tweaks/

[daflow]

Wie verhalten sich die Abfragen in MySql, wenn du 7 einzelne Indexe anlegst?
Jede denkbare Kombi ist wie du selber schon sagtest Murks, weil natürlich jede Änderung ewig dauert und auch dein Bufferpool dauernd geflusht wird und nie das drin ist, was gerade ebraucht wird. Apropos... liese sich die das Problem evtl. ein weng mit Hardware/DB-Konfig ein weng lindern? (Physiche Verteilung der Daten/Indizes auf viele Platten, Bufferpool/Sortpools etc. anpassen...)
Nachtrag: Wenn ichs richtig lese hättetst du gern für alle 20 Spalten indizierte Zugriffe? Kannst du den Spalten ausschliessn für die ein Index kaum Sinn macht wegen geringer Selektivität (-> nur wenig unterschiedliche Werte vorhanden)?

[AlecWhite]

Wie verhalten sich die Abfragen in MySql, wenn du 7 einzelne Indexe anlegst?
Nicht viel anders. Für das erste Sortierkriterium kann der Index verwendet werden. Für die anderen heißt es -> ab auf die Platte, dort sortieren, das Ergebnisse auf die Platte -> Ausgabe

Dieses genau diese temporären Tabellen brauchen den ganzen Aufwand - das sortieren an sich, ist prinzipiell nicht so fordernen, aber da werden wirklich viele Daten hin und her kopiert.

Das bringt mich allerdings auf eine Idee: Unter *nix kann ich doch bestimmte Teile des Dateisystems in den Arbeitsspeicher mounten? Wenn ja, müsste es doch möglich sein, mysql dazu zu überreden, die temporären Tabellen in eben jenes Verzeichnis zu platzieren. Da würde die Sortierung quasi im Arbeitspeicher vorgenommen werden. An Arbeitspeicher mangelt es dem System wirklich nicht. Mal testen.

[Gast_samm]

Richtig. Wäre das InnoDB Tabellenformat eine Option? Das sperrt nur die betroffene Zeile bei Updates/Inserts statt die ganze Tabelle wie bei MyIsam. Allerdings brauchen die Indizes da noch mehr Speicherplatz. :)
Das Indizieren ist wohl ein ebenso grosses Problem wie die Sperre in diesem Fall :)

AlecWhite: Bei beliebig viel Speicher: Es gibt doch die Memory Engine :) Kannst bis zu 64 Indexe machen, und zwar b-trees oder hashes. Problem: Die Daten werden nicht auf die Platte zurückgeschrieben. Das müsstest du selbst machen, quasi die Tabelle doppelt führen, aber alle SELECT-queries auf der Memory-Version ausführen.

[Gast_samm]

Oh, und ausserdem hab ich noch das gefunden: http://www.clusterdb.com/mysql-cluster/replacing-memory-storage-engine-with-mysql-cluster-2/

[DanMan]

Bei beliebig viel Speicher: Es gibt doch die Memory Engine :)
Hatte ich auch schon überlegt, aber bei 15Mio Zeilen á 20 Spalten, mit jeweils 100B/Zelle, da sind wir ganz schnell im zweistelligen Gigabytebereich von grob geschätzt 30GB.

[daflow]

[...]
Das bringt mich allerdings auf eine Idee: Unter *nix kann ich doch bestimmte Teile des Dateisystems in den Arbeitsspeicher mounten? Wenn ja, müsste es doch möglich sein, mysql dazu zu überreden, die temporären Tabellen in eben jenes Verzeichnis zu platzieren. Da würde die Sortierung quasi im Arbeitspeicher vorgenommen werden. An Arbeitspeicher mangelt es dem System wirklich nicht. Mal testen.

Du kannst theoretisch jedes Filesystem in den Speicher mounten (also auch die Datenfiles) nur ist Arbeitsspeicher halt eher flüchtiger Natur beim Crash, von daher würd ich davon abraten dort selbst zu brasteln sondern eher Memory-Lösungen des Herstellers verwenden.
MySql ist leider nicht grade mein Steckenpferd, aber gibt es da keine Möglichkeiten Speichergrößen eben für Sortierungen, Temptables etc. festzulegen? Wäre natürlich noch die Frage wieviel Ram du zur Verfügung hast und ob sichs's lohnt hier anzusetzen. Ansonsten ist der billigste Weg natürlich immer die Optimierung der Zugriffe über Einschränkung der Sqls, legen von Indizes sowei testen verschiedener Statistikoptionen (kann man verschiedene Tabellen/indexstatistiken unter MySql ziehen?). Wenn da nichts machbar ist und sich das Problem nicht über Memory erschlagen lässt, sehe ich eigentlich fast nur noch die Möglichkeit der Parallelisierung auf möglichst viele Platten.

[Berni]

sort_buffer und tmp_table_size wären die Variablen, die man erhöhen könnte um das Sortieren in den RAM zu verlagern und zu beschleunigen. Siehe dazu auch die Laufzeitinformationen in phpmyadmin. Du musst aber natürlich schauen, dass dein RAM ausreicht...

Wenn ein Index auf der ersten Spalte einer Abfrage liegt und diese Spalte recht selektiv ist (und der Index auch benutzt werden kann => Explain) dann reduziert sich der Sortieraufwand schon erheblich (ansonsten auf die nächsten Spalten erweitern bis es einigermaßen selektiv ist). Daher würde ich ebenfalls für jede Abfrage zumindest einen Index auf die erste(n) Spalte(n) erstellen.

Ich frage mich aber auch wie einige Vorredner, ob du wirklich sämtliche Ergebnisse sortieren musst. Die Clients werden doch nicht ernsthaft auch 15 Mio. Datensätze als Ergebnis geliefert kriegen?

[CrazyIvan]

Naja, da das Stichwort OLAP vorhin erwähnt wurde, kann das schon sein. Wird sich wohl um eine ROLAP-Lösung handeln.
Vielleicht wäre es bei der Datenmenge mal eine Überlegung wert, sich nach HOLAP/MOLAP-Lösungen umzuschauen.

[AlecWhite]

Hallo an alle!

Hab heute mal an meiner Testmaschine einige Settings geändert (u.a die tmp_table_size etc.) Das brachte leider nix - die temporären Tabellen werden weiterhin auf die Festplatte geschrieben.

Also ein Verzeichnis /mysqltmp angelegt und in den RAM gemountet, den mysql server dazu überredet dort die temporären Tabellen anzulegen (gibt tatsächlich 'ne Option dafür, ich bin begeistert) und dann gemessen: Das brauchte ordentlich was. Bei 'nem Servercrash sind die Daten natürlich weg, aber das sind 1.) ja nur temporäre Tabelle, der Verlust ist verkraftbar :) und 2.) der Crash ist ohnehin Worst-Case. Da habe ich keine Bauchschmerzen bei.

Das war also schonmal eine gute Idee. Als nächstes habe ich mal getestet, ob eine Partitionierung der Daten etwas bringt. Seit Oracle ihre Hände in mySQL drin haben, kommen scheinbar einige gute Dinge bei rum. Die Daten geschickt indiziert: Das brauchte nochmal etwas. Logisch, 3, 4 sortierte Datenmengen zu mergen geht halt wesentlich effizienter als eine große Menge zu sortieren.

Mit den Ergebnissen bin soweit ganz zufrieden.

Kleine Hintergrund info: Derjenige welche bislang diese ganzen Datenbank-Geschichte gemacht hat (also dessen auswüchse - nicht nur die DB, sondern auch was da alles hinten dran hängt - ich jetzt bändigen muss) durfte endlich seinen Hut nehmen und jetzt hat mir das erstmal Zeitweise übertragen bis jemand neues gefunden wird. Bin aber eigentlich ganz scharf auf den Posten, da besser bezahlt und weniger Stress. Mit einer Performanzspritze am System kann ich natürlich erstmal eine bessere Position beziehen.