mySQL: Wieviele Indizes verwendet mySQL pro Tabelle und Abfrage

[fredy]

Hi!

Kann es sein, dass mySQL pro Abfrage und Tabelle nur einen Index benutzt ?

Danke und liebe Grüße
fredy

[Cheatah]

Hi,

Kann es sein, dass mySQL pro Abfrage und Tabelle nur einen Index benutzt ?

ja. In wievielen Indizes mit widersprüchlichen Ergebnissen sollte es denn Deiner Meinung nach sonst arbeiten? Würden mehrere Indizes verwendet werden, könnte es im Grunde auch gleich einen Full Table Scan machen - der Organisationsaufwand, mehrere Indizes zu verknüpfen, würde den Geschwindigkeitsvorteil wieder wett machen.

Wenn Du mehrere Indizes für sinnvoll hälst, hast Du den Fehler gemacht, sie nur einspaltig anzulegen.

Cheatah

[Michael Schröpl]

Hi Cheatah,

Kann es sein, dass mySQL pro Abfrage und Tabelle nur einen Index
benutzt ?
ja. In wievielen Indizes mit widersprüchlichen Ergebnissen sollte
es denn Deiner Meinung nach sonst arbeiten? Würden mehrere Indizes
verwendet werden, könnte es im Grunde auch gleich einen Full Table
Scan machen - der Organisationsaufwand, mehrere Indizes zu verknüp-
fen, würde den Geschwindigkeitsvorteil wieder wett machen.

Das ist eine Frage der Projektivität der Indexe.

Wenn ich mit zwei Indexzugriffen jeweils 0.0001% der Datensatzmenge
isolieren und dies dann mit sich selbst JOINen könnte, dann wäre das
rasend schnell, verglichen mit einem full table scan.

Wenn Du mehrere Indizes für sinnvoll hälst, hast Du den Fehler
gemacht, sie nur einspaltig anzulegen.

Vielleicht. Meistens sogar. Aber nicht immer.

Stell Dir vor, Du willst einen Präfix-Match gegen mehrere Indexe fahren:

SELECT <fields> FROM <tablename>
 WHERE <field1> LIKE 'x%'
   AND <field2> LIKE 'y%';

Bilde das mal mit einem einzigen Index über beiden Spalten nach ...

Viele Grüße
      Michael

[Cheatah]

Hi,

Wenn ich mit zwei Indexzugriffen jeweils 0.0001% der Datensatzmenge
isolieren und dies dann mit sich selbst JOINen könnte, dann wäre das
rasend schnell, verglichen mit einem full table scan.

das ist richtig, nur sprechen zwei Gründe dagegen:

1.) ist es (bei "handelsüblicher" Datenmenge einer privaten Website) sehr unwahrscheinlich, eine solche Erfolgsquote zu haben; trotz günstigster Indizes. In der Regel wird ein _guter_ Index rund 10% der Daten zurückliefern - unterschiedliche Indizes bringen sich kaum überschneidende Mengen, die zu JOINen nicht mehr effizient über eine Bitmap lösbar ist. Der Organisationsaufwand hierzu, verbunden mit dem Organisationsaufwand der Suche nach dem passenden Index, ist hoch.

2.) weiß die Datenbank normalerweise nicht, ob ein Index (und wenn ja, welcher) derartige Erfolge liefern kann; denn wenn er bei der einen Abfrage 1% der Daten liefert, liefert er bei einer anderen vielleich 99%. Zwar kann man dazu statistische Analysen durchführen; aber selbst Oracle, bei dem sowas gang und gäbe ist und das mit Datenmassen immenser Größe vertraut ist, erlaubt pro Tabellenabfrage nur einen Index.

Ich würde von keinem DBMS erwarten, dass es, nur weil es "bei dieser Abfrage zufällig sinnvoll ist", Dinge tut, von denen selbst die mächtigsten Systeme Abstand nehmen.

Wenn Du mehrere Indizes für sinnvoll hälst, hast Du den Fehler
gemacht, sie nur einspaltig anzulegen.

Vielleicht. Meistens sogar. Aber nicht immer.

Natürlich nicht immer. Meistens eben.

SELECT <fields> FROM <tablename>
WHERE <field1> LIKE 'x%'
   AND <field2> LIKE 'y%';

Bilde das mal mit einem einzigen Index über beiden Spalten nach ...

Oracle:

SQL> create index testindex on bak_category (name, normalized_name);
Index wurde angelegt.
SQL> set autotrace traceonly explain
SQL> select * from bak_category where name like 'x%' and normalized_name like 'y%';

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE
   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'BAK_CATEGORY'
   2    1     INDEX (RANGE SCAN) OF 'TESTINDEX' (NON-UNIQUE)

Also, der Index wird verwendet. Ich kann natürlich nicht dafür sprechen, dass MySQL das auch tut :-)

Cheatah

[Michael Schröpl]

Hallo Cheatah,

Wenn ich mit zwei Indexzugriffen jeweils 0.0001%
der Datensatzmenge isolieren und dies dann mit
sich selbst JOINen könnte, dann wäre das
rasend schnell, verglichen mit einem full table
scan.
das ist richtig, nur sprechen zwei Gründe dagegen:
1.) ist es (bei "handelsüblicher" Datenmenge einer
privaten Website) sehr unwahrscheinlich, eine solche
Erfolgsquote zu haben; trotz günstigster Indizes.

Bei einer Tabelle mit 10000 Einträgen wäre der Primärschlüsselindex ein solcher. Und der ist auch der wahrscheinlichste Kandidat, überhaupt zu existieren.

In der Regel wird ein _guter_ Index rund 10% der
Daten zurückliefern

Himmel, nein!

10% ist schon fast zu schlecht, um den Index überhaupt erst anzulegen. Unter 10-15% (d. h. 7-10 verschiedene Werte) brauchst Du gar nicht erst anzufangen - da ist der full table scan wirklich besser.

Sämtliche Indexe meiner aktuellen Suchmaschinen-Implementierung projezieren um zwischen 2 und 6 Zehnerpotenzen! _Das_ sind "gute" Indexe. :-)

Der Organisationsaufwand hierzu, verbunden mit dem
Organisationsaufwand der Suche nach dem passenden
Index, ist hoch.

Das ist wahr.
Aber ein guter query optimizer wird auch einen hohen Aufwand betreiben wollen, wenn er eine oder mehrere Zehnerpotenzen gewinnen kann - vor allem, wenn dasselbe Statement immer wieder ausgeführt werden muß!
"analyze table" ist der Weg dorthin - die Frage ist lediglich, welche Informationen gespeichert werden und wer die sich zunutze macht.

2.) weiß die Datenbank normalerweise nicht, ob ein
Index (und wenn ja, welcher) derartige Erfolge
liefern kann; denn wenn er bei der einen Abfrage 1%
der Daten liefert, liefert er bei einer anderen
vielleicht 99%.

Doch - das weiß sie sehr genau, wenn sie die Tabelle per "analyze" untersucht hat.

Würde ich "analyze" implementieren, dann würde ich auf jeden Fall speichern:

• die Anzahl der verschiedenen Werte (und damit die mittlere Projektivität des Index) sowie
• eine Liste aller Werte, die mehr als 10% der Treffer liefern würden. (Das können höchstens 10 Stück sein - und die kann ich auch noch in einem Baum der Tiefe 4 speichern, wenn es denn sein muß ... ;-)

Und bei einem Indexzugriff würde ich diese Liste prüfen, um einen Indexzugriff für diese "pathologisch schlechten" Werte zu verhindern.
Je höher die Summe der Verwendungen von Werten in dieser Liste sind (also je wahrscheinlicher ich bei dieser Zusatzprüfung einen Wert finde), desto sicherer optimiere ich den Ausführungsplan dadurch, daß ich mich gegen den Indexzugriff und für den full table scan entscheide.
Ich kann also sehr wohl zwischen "guten" und "schlechten" Indexen unterscheiden - beispielsweise schon dadurch, daß bei "guten" Indexen die Stopwortliste leer ist. Außerdem kann ich auch noch die Wahrscheinlichkeit für das Auftreten eines Wertes außerhalb der Stopwortliste speichern ...

Und Oracle macht das auch intern so ähnlich - um sich beispielsweise zwischen zwei möglichen Indexzugriffen für den besseren zu entscheiden. Wahrscheinlich kennt Oracle nur die mittlere Projektivität der Tabellen - was im Schnitt auch schon zu sehr guten Ergebnissen führt (wenn Index A 10 verschiedene Werte liefert und Index B 10000 ...).

Die von mir beschriebene Zusatzprüfung der "worst case list" würde die Effektivität m. E. noch etwas erhöhen. Jedenfalls in Fällen einer entsprechenden Ungleichverteilung.
Ob eine solche tatsächlich vorliegt, weiß einerseits der Admin und andererseits die Datenbank aufgrund des "analyze"-Ergebnisses. Es wäre also genauso gut denkbar, ein solches Feature einfach immer einzuschalten, wie es über einen Konfigurationsschalter zur Verfügung zu stellen.

Zwar kann man dazu statistische Analysen
durchführen; aber selbst Oracle, bei dem sowas
gang und gäbe ist und das mit Datenmassen immenser
Größe vertraut ist, erlaubt pro Tabellenabfrage nur
einen Index.

Ich weiß. Der vor mir beschriebene Fall war auch "konstruiert".

Ich würde von keinem DBMS erwarten, dass es, nur
weil es "bei dieser Abfrage zufällig sinnvoll ist",
Dinge tut, von denen selbst die mächtigsten Systeme
Abstand nehmen.

Ich hinterfrage eben gerade dieses "Abstand nehmen".
Und es kann gut sein, daß es sich wirklich nicht lohnt, bestimmte Dinge zu implementieren.

Aber ein execution plan optimizer ist KI - da ist es sehr schwer, irgend einen Alternativplan von vorn herein als untauglich auszuschließen. Es gibt immer Anwendungsfälle, in denen genau er die Rettung wäre.

SELECT <fields> FROM <tablename>
WHERE <field1> LIKE 'x%'
   AND <field2> LIKE 'y%';
Bilde das mal mit einem einzigen Index über
beiden Spalten nach ...

Execution Plan

0      SELECT STATEMENT Optimizer=CHOOSE
   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'BAK_CATEGORY'
   2    1     INDEX (RANGE SCAN) OF 'TESTINDEX' (NON-UNIQUE)

Also, der Index wird verwendet.

Ja - für die erste der beiden WHERE-Klauseln. Aber nicht für die zweite. (Wie denn auch? ;-)

Klar erkennt Oracle, daß es mit dem zweispaltigen Index wenigstens die erste der beiden Spalten adressieren kann - aber die zweite nicht, weil es dafür einen String-Match über ein concat beider Spaltenwerte machen müßte, und das geht nicht wegen der wildcard am Ende der ersten WHERE-Klausel.

Wäre die Abfrage

SELECT <fields> FROM <tablename>
 WHERE <field1> = 'x'
   AND <field2> LIKE 'y%';

gewesen, dann hätte die Datenbank den kombinierten Index für _beide_ WHERE-Klauseln nutzen können.
(Und dann wäre die Reihenfolge der beiden Spalten im Indexbaum entscheidend gewesen.)

Ich kann natürlich nicht dafür sprechen, dass
MySQL das auch tut :-)

In diesem eingeschränkten Sinne - bestimmt. Es muß ja nur erkennen, daß es nur den ersten Teil des Indexbaums nutzen darf, den zweiten also praktisch als "%"-wildcard ansehen. Also:

SELECT <fields> FROM <tablename>
 WHERE <field1> LIKE 'x%'
   AND <field2> =    'y';

und

SELECT <fields> FROM <tablename>
 WHERE <field1> LIKE 'x%'
   AND <field2> LIKE '%';

müßten intern dieselben Indexzugriffe verursachen, falls ein gemeinsamer Index über (<field1>,<field2>) existiert - und auch dieselben, wie wenn der Index nur über <field1> gelegt worden wäre. Beide execution plans müssen sich genau durch den zusätzlichen Vergleich der Ergebniswerte mit 'y' unterscheiden, denke ich.

Viele Grüße
      Michael

[Cheatah]

Hi Michael,

Bei einer Tabelle mit 10000 Einträgen wäre der Primärschlüsselindex ein solcher. Und der ist auch der wahrscheinlichste Kandidat, überhaupt zu existieren.

natürlich, natürlich, natürlich. Wenn man allerdings auf einen Primary Key geht, wird man kaum noch weitere Einschränkungen brauchen, oder? Es purzelt maximal ein Ergebnis raus - ob man dieses verwirft, ist ohne Index sicherlich nicht langsamer als mit einem zweiten, sondern eher sogar schneller. Bei einem zweispaltigen Index entfällt der Table Access By Rowid; aber so ein Index ist in der Praxis eher die Ausnahme.

10% ist schon fast zu schlecht, um den Index überhaupt erst anzulegen.

Kommt auf die Daten an. Gerade wenn Du eine Handvoll verschiedener Typen hast, sind i.d.R. einige dabei, die mehr als 10% beanspruchen.

Unter 10-15% (d. h. 7-10 verschiedene Werte) brauchst Du gar nicht erst anzufangen - da ist der full table scan wirklich besser.

Sag mir das ruhig - ich weiß das ;-) Allerdings rechnen wir zwei beide auch mit etwas größeren Daten- und Abfragemengen, als es bei privaten Sites zu erwarten ist. In dem Bereich habe ich bisher kein DB-Layout gesehen, in dem ein zwei- bis dreispaltiger Index nicht auch dann sinnvoll war, wenn die erste Spalte vielleicht auf 1-20% einschränkte (je nach Wert).

Sämtliche Indexe meiner aktuellen Suchmaschinen-Implementierung projezieren um zwischen 2 und 6 Zehnerpotenzen! _Das_ sind "gute" Indexe. :-)

Ja, stimmt :-)

Aber ein guter query optimizer

Hat das im Subject gennante DBMS einen solchen? MySQL ist rasend schnell, obwohl (bzw. weil) es äußerst simpel aufgebaut ist. Und wie gesagt: Selbst Oracle lässt sich nicht dazu bewegen, mehrere Indizes bei der selben Tabellenabfrage zu verwenden.

vor allem, wenn dasselbe Statement immer wieder ausgeführt werden muß!

Ja. Hierbei treten aber auch Stichworte wie Caching und Precompiling in den Vordergrund; und zu einem guten DB-Layout gehört auch, dass sich der Layouter über die Optimierung Gedanken macht, um dem DBMS Arbeit zu sparen. Schließlich muss dies _jedes_ Statement schnell bearbeiten, nicht nur _dieses_, weil es zufällig gerade öfter aufgerufen wird, da sollte es nicht unter der eigenen Last zusammenbrechen ;-)

"analyze table" ist der Weg dorthin

Bisweilen ist das aber auch hinderlich. Besonders bei stetigen Änderungen kostet dies regelmäßig viel Zeit; und ob, gerade bei der Verwendung von Bind-Variablen, das Ergebnis der Analyse bei unterschiedlichen Aufrufen auch tatsächlich sinnvoll ist, steht ebenfalls in den Sternen. Wir haben übrigens schon bewusst auf Bind-Variablen verzichtet, weil dann der Execution Plan jedes Mal neu berechnet wird... wegen der unterschiedlichen Ergebnisse war das performanter :-)

Würde ich "analyze" implementieren, dann würde ich auf jeden Fall speichern:

Wie oft würdest Du diese Werte aktualisieren? Schon einen Index aktuell zu halten kostet Rechenzeit (und einiges an Speichermanagement). Eine Analyse kann jedoch nur schwerlich inkrementell gemacht werden, da sie auch darauf beruht, gerade detaillierte Daten _nicht_ zu speichern - im (dumm implementierten) Extremfall müsste jeder INSERT und jedes UPDATE zu einer neuen Analyse führen.

Und bei einem Indexzugriff würde ich diese Liste prüfen, um einen Indexzugriff für diese "pathologisch schlechten" Werte zu verhindern.

Wie wäre es mit ANALYZE INDEX? ;-)

Um das ganze nicht zu sehr ausweiten zu lassen: Es gibt viele Möglichkeiten, viele davon hier und dort implementiert, viele nicht. Eine gute Optimierung ist immer hochgradig individuell - besonders hier gilt das (selbstbezügliche) Prinzip "Pauschalisierungen sind falsch und dumm". Was in dem einen Fall ein hervorragender Gedanke ist, kann einem im anderen Fall das System zusammenbrechen lassen, oder zumindest bringt es längst nicht die gleiche Erfolgsrate und ist vermutlich durch ein anderes Vorgehen zu toppen.

Und trotz alledem kenne ich kein DBMS, welches mehrere Indexzugriffe bei einer einzelnen Tabellenabfrage machen würde - meiner Ansicht nach ist das ein recht sicheres Zeichen dafür, dass eine solche Methode doch eher problematisch als hilfreich ist.

Der vor mir beschriebene Fall war auch "konstruiert".

Ja, und im Einzelfall hast Du zweifellos auch recht :-)

Aber ein execution plan optimizer ist KI

Manchmal aber mehr "K" als "I" ;-)

Execution Plan

0      SELECT STATEMENT Optimizer=CHOOSE
   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'BAK_CATEGORY'
   2    1     INDEX (RANGE SCAN) OF 'TESTINDEX' (NON-UNIQUE)
Also, der Index wird verwendet.
Ja - für die erste der beiden WHERE-Klauseln. Aber nicht für die zweite. (Wie denn auch? ;-)

Ganz einfach: Die zweite Spalte befindet sich im Range der ersten. "x%" ist ein vollständiger Bereich des Index von A bis B, und darin wird nach allen "y%" der zweiten Spalte gesucht. Anders wäre es natürlich, wenn Du "%y" suchen würdest - soweit ich weiß kann man aber in manchen Systemen (htdig fällt mir spontan ein) auch umgekehrte Indizes einsetzen, die eben exakt dieses erlauben. In Oracle habe ich es noch nie gebraucht; keine Ahnung, ob es das dort gibt.

Klar erkennt Oracle, daß es mit dem zweispaltigen Index wenigstens die erste der beiden Spalten adressieren kann - aber die zweite nicht, weil es dafür einen String-Match über ein concat beider Spaltenwerte machen müßte, und das geht nicht wegen der wildcard am Ende der ersten WHERE-Klausel.

Soweit ich informiert bin, können die Spalten im Index klar voneinander getrennt werden, und zwar ohne Performanceverlust. Zumindest wenn ich nur die beiden indizierten Spalten selektiere, wird der Table Access By Rowid auch weggelassen. Ergo scheint die Prüfung nichts weiter als den Index zu brauchen.

Cheatah

[MIchael Schröpl]

Hi Cheatah,

10% ist schon fast zu schlecht, um den Index überhaupt
erst anzulegen.
Kommt auf die Daten an. Gerade wenn Du eine Handvoll
verschiedener Typen hast, sind i.d.R. einige dabei, die
mehr als 10% beanspruchen.

Yep. Aber wenn es _im Mittel_ 10% der Treffer sind, dann nützt
der Index weniger, als er kostet.

Würde ich "analyze" implementieren, dann würde ich auf
jeden Fall speichern:
Wie oft würdest Du diese Werte aktualisieren?

Ich - gar nicht. "analyze" ist ein Kommando, welches der
Betreiber des RDBMS ausführt oder auch nicht.
Diese Entscheidung kann ich ihm nicht abnehmen, weil ich sein
Betriebskonzept nicht kenne.

Wenn Du nicht gerade 24/7 denken mußt (der Dir wenigstens in
bestimmten low-traffic-Zeiten etwas mehr CPU-Last zumuten
kannst), dann sind die housekeeping-Phasen genau dazu nützlich,
um Berechnungen durchzuführen, die besser dort als während der
online-Wartezeit des Benutzers stattfinden sollten.
Und in solchen Phasen ist ein "analyze" gut platziert.

Schon einen Index aktuell zu halten kostet Rechenzeit (und
einiges an Speichermanagement). Eine Analyse kann jedoch nur
schwerlich inkrementell gemacht werden, da sie auch darauf
beruht, gerade detaillierte Daten _nicht_ zu speichern - im
(dumm implementierten) Extremfall müsste jeder INSERT und
jedes UPDATE zu einer neuen Analyse führen.

Yep. Aber die Aussage darüber, wie gut ein Index projeziert
und welche drei Werte die Super-GAUs sind, ändert sich nicht
innerhalb weniger Stunden.
Natürlich veralten die Werte von "analyze" ständig - aber eben
nur langsam. Wie oft man sie refreshen möchte, das hängt von
der Änderungsfrequenz des Tabellen-Inhalts ab ... das können
Stunden sein, aber auch Tage oder Wochen.

Und bei einem Indexzugriff würde ich diese Liste prüfen,
um einen Indexzugriff für diese "pathologisch
schlechten" Werte zu verhindern.
Wie wäre es mit ANALYZE INDEX? ;-)

Ich habe jetzt überhaupt nicht an real existierende Imple-
mentierungen gedacht, sondern an das Prinzip als solches.
Mich interessieren in diesem Kontext keine Produkte, sondern
Algorithmen ...

Execution Plan

0      SELECT STATEMENT Optimizer=CHOOSE
   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'BAK_CATEGORY'
   2    1     INDEX (RANGE SCAN) OF 'TESTINDEX' (NON-UNIQUE)
Also, der Index wird verwendet.
Ja - für die erste der beiden WHERE-Klauseln. Aber nicht für die zweite. (Wie denn auch? ;-)
Ganz einfach: Die zweite Spalte befindet sich im Range der
ersten. "x%" ist ein vollständiger Bereich des Index von A
bis B, und darin wird nach allen "y%" der zweiten Spalte
gesucht.

Und zwar wie?

Einen separat nach der zweiten Spalte sortierten Indexbaum nur
genau für diesen Treffer-Range des ersten kann es nicht geben
(wer sollte den wann angelegt haben?) - und wenn es den nicht
gibt, dann kann ich nur noch sämtliche gefundenen Indexwerte
mit einem "full indexrange scan" abfragen.

Das bedeutet für mich aber nicht, diesen Index "zu benutzen",
d. h. seine eigene Projektivität zu verwenden.
Ob ich jetzt innerhalb des Indexbaums einen Vergleich mit dem
Inhalt des zweiten Indexfeldes habe oder ob ich dafür auf die
row-Daten zugreifen muß, daß ist nur ein konstanter Faktor
mehr. Aber von konstanten Faktoren rede ich im Zusammenhang
mit Indexen normalerweise gar nicht ...

Klar erkennt Oracle, daß es mit dem zweispaltigen Index
wenigstens die erste der beiden Spalten adressieren kann

• aber die zweite nicht, weil es dafür einen String-Match
  über ein concat beider Spaltenwerte machen müßte, und das
  geht nicht wegen der wildcard am Ende der ersten WHERE-
  Klausel.
  Soweit ich informiert bin, können die Spalten im Index klar
  voneinander getrennt werden, und zwar ohne Performance-
  verlust.

Ich kann mir die erforderliche Datenstruktur nicht vorstellen.
Das Wissen, um sie zu berechnen, kann nicht existiert haben.

Zumindest wenn ich nur die beiden indizierten Spalten
selektiere, wird der Table Access By Rowid auch weggelassen.
Ergo scheint die Prüfung nichts weiter als den Index zu
brauchen.

Das ist wahr - das meinte ich aber nicht.

Sicher sparst Du den Zugriff auf die row-Daten - aber innerhalb
des Teilbaums der Treffer des ersten WHEREs macht das RDBMS
eine (langsame) Variante eines full table scans (weil es
zusätzlich auch noch in der Baumstruktur herum turnen muß) -
und keinen Baum-Abstieg zur gezielten _weiteren_ Reduzierung
der Treffermenge (weil eben kein Baum existiert, der nach
dem entsprechenden Kriterium sortiert sein könnte).

Viele Grüße
      Michael