Wie bekomme ich einen JOIN schnell?

[Andreas Korthaus]

Hallo!

Ist ne Prima Sache wenn man kurz vorm Abschicken mal aus Versehen auf "Refresh" kommt ;-)
Also nochmal:
Ich kann in der MySQL Doku leider nicht wirklich alle Informationen finden die ich gerne hätte. Aber erstmal zu meiner Abfrage:

Tabelle "a" enthält wenige Datensätze, und die wenigen Datensätze sollen noch mit in Tabelle "b"(viel mehr Datensätze) enthaltenen Daten gefiltert werden.

SELECT a.key
FROM a
LEFT JOIN b
ON a.key=b.key
WHERE(b.wert1 = 1234 AND b.wert2 < 4321)

So. Zunächst, die Richtung des Joins sollte ja so stimmen. Aber wie optimiere ich das jetzt? In der MySQL Doku steht im Kapitel zur Optimierung, dass man unbedingt einen Index über beide Tabellen anlegen soll, aber wie geht das? Das steht nirgends in der Doku! Und auch in PHPmyADmin finde ich keine Möglichkeit. Wie muß das heißen? Und wie sollte der Index idealerweise überhaupt aussehen, also über welche Spalten und in welcher Reihenfolge?

ich habe ja
a.key <= benötigt für den JOIN
b.key <= benötigt für den JOIN
b.wert1 <= benötigt für WHERE cond.
b.wert2 <= benötigt für WHERE cond.

Soweit ich das weiß sollten die Spalten in der Reihenfolge ihres "unique-Grades" im Index stehen.

a.key ist eine Teilmenge aus b.key, welches unique ist.

also vermutlich a.key,b.key

aber was ist mit den beiden anderen Spalten für die WHERE Bedingung? sollte ich die auch hinzufügen, oder lieber nicht? Was ist im allgemeinen wichtiger, ein Index über die JOIN-Spalten, oder über die WHERE-Bedingungen-Spalten?

Was würdet Ihr hier empfehlen?

Viele Grüße
Andreas

[Vinzenz]

Hallo Andreas

Tabelle "a" enthält wenige Datensätze, und die wenigen Datensätze sollen noch mit in Tabelle "b"(viel mehr Datensätze) enthaltenen Daten gefiltert werden.

SELECT a.key
FROM a
LEFT JOIN b
ON a.key=b.key
WHERE(b.wert1 = 1234 AND b.wert2 < 4321)

So. Zunächst, die Richtung des Joins sollte ja so stimmen. Aber wie optimiere ich das jetzt? In der MySQL Doku steht im Kapitel zur Optimierung, dass man unbedingt einen Index über beide Tabellen anlegen soll, aber wie geht das? Das steht nirgends in der Doku! Und auch in PHPmyADmin finde ich keine Möglichkeit. Wie muß das heißen? Und wie sollte der Index idealerweise überhaupt aussehen, also über welche Spalten und in welcher Reihenfolge?

Du hast es ja selbst gelesen: Den Index musst Du in den Tabellen anlegen. Geht sogar mit phpMyAdmin ...

ich habe ja
a.key <= benötigt für den JOIN
b.key <= benötigt für den JOIN

Also jeweils ein Index für das Feld key in Tabelle a und in Tabelle b

b.wert1 <= benötigt für WHERE cond.
b.wert2 <= benötigt für WHERE cond.

Greifst Du oft auf diese Spalten zu, dann lohnt sich auch ein Index dafür

Soweit ich das weiß sollten die Spalten in der Reihenfolge ihres "unique-Grades" im Index stehen.

a.key ist eine Teilmenge aus b.key, welches unique ist.

Wenn ich Dich richtig verstehe, hast Du ja schon einen UNIQUE-Index auf key in Tabelle b.

Was für einen Index Du in Tabelle a verwendest, hängt von der Beziehung zwischen den Tabellen ab.

Können einem Datensatz aus Tabelle b mehrere Datensätze aus Tabelle a zugeordnet sein (1:n)-Beziehung, dann ein einfacher Index auf key in Tabelle a

Ist jedem Datensatz aus Tabelle b maximal ein Datensatz aus Tabelle a zugeordnet (1:1)-Beziehung, dann ein UNIQUE-Index auf key in Tabelle a

Was für Indizes auf die Spalten b.wert1 und b.wert2, hängt von den möglichen Werten ab, wahrscheinlich also ein einfacher Index, da die Werte wohl mehrfach vorkommen können.

Denke daran, dass Indizes die Einfüge- und Löschoperationen auf den Tabellen verlangsamen.

aber was ist mit den beiden anderen Spalten für die WHERE Bedingung? sollte ich die auch hinzufügen, oder lieber nicht? Was ist im allgemeinen wichtiger, ein Index über die JOIN-Spalten, oder über die WHERE-Bedingungen-Spalten?

Ein Index über die JOIN-Spalten sollte _immer_ vorhanden sein, sonst darf das DBMS linear suchen *wart*

Gruss,

Vinzenz

[Andreas Korthaus]

Hallo!

SELECT a.key
FROM a
LEFT JOIN b
ON a.key=b.key
WHERE(b.wert1 = 1234 AND b.wert2 < 4321)

Du hast es ja selbst gelesen: Den Index musst Du in den Tabellen anlegen. Geht sogar mit phpMyAdmin ...

Ich finde es nicht mehr, aber ich könnte schwören das ich in der Doku irgendwo gelesen habe dass man auch indices über 2 Tabellen erstellen kann. Wobei - mysql erstellt pro Tabelle ein Verzeichis, wo sollte dann der Index gespeichert werden?

a.key <= benötigt für den JOIN
b.key <= benötigt für den JOIN

Also jeweils ein Index für das Feld key in Tabelle a und in Tabelle b

Aber es kann doch pro Abfrage nur _ein_ Index verwendet werden, oder?

b.wert1 <= benötigt für WHERE cond.
b.wert2 <= benötigt für WHERE cond.

Greifst Du oft auf diese Spalten zu, dann lohnt sich auch ein Index dafür

Jedesmal greife ich drauf zu. Ich will einen Index gerade für die obige Anfrage optimieren.

Soweit ich das weiß sollten die Spalten in der Reihenfolge ihres "unique-Grades" im Index stehen.

a.key ist eine Teilmenge aus b.key, welches unique ist.

Wenn ich Dich richtig verstehe, hast Du ja schon einen UNIQUE-Index auf key in Tabelle b.

nö, die Spalte "key" ist nur unique. Was bringt mir ein Primärschlüssel, wenn ich gerne einen Index mit allen 4 Spalten hätte,  oder brauche ich einen primär-Schlüssel über die Spalte a.key, und einen 2. Index über (b.key,b.wert1,b.wert2)? b.key ist ebenfalls unique, und somit sollte es auch an erster Stelle stehen.

Was für einen Index Du in Tabelle a verwendest, hängt von der Beziehung zwischen den Tabellen ab.

Wie beschrieben, in Tabelle "b" stehen alle verfügaren Werte für "key", und die Werte sind unique, es gibt keine Doppelten Werte. Spalte "a.key" enthält eine Teilmenge von "b.key".

Können einem Datensatz aus Tabelle b mehrere Datensätze aus Tabelle a zugeordnet sein (1:n)-Beziehung, dann ein einfacher Index auf key in Tabelle a

Oh, jetzt wo Du es sagst, sicher kann das sein ;-)

Also a.key ist also doch nicht unique, kann aber immer noch nur Wete aus b.key enthalten, welche aber auf alle Fälle unique ist.

|| Ist jedem Datensatz aus Tabelle b maximal ein Datensatz aus Tabelle a zugeordnet (1:1)-Beziehung, dann ein UNIQUE-Index auf key in Tabelle
ja, das also nicht, also ein non-unique Index.

Was für Indizes auf die Spalten b.wert1 und b.wert2, hängt von den möglichen Werten ab, wahrscheinlich also ein einfacher Index, da die Werte wohl mehrfach vorkommen können.

genau. Nur wie gesagt, es wird nur ein index pro SQL-Abfrage verwendet, der beste, da bringt es nichts wenn ich 4 für sich nette Indices habe, ich brauche _einen_ guten der auf obige Abfrage passt.

Denke daran, dass Indizes die Einfüge- und Löschoperationen auf den Tabellen verlangsamen.

Das ist egal.

Grüße
Andreas

[Vinzenz]

Hallo Andreas,

Ich finde es nicht mehr, aber ich könnte schwören das ich in der Doku irgendwo gelesen habe dass man auch indices über 2 Tabellen erstellen kann. Wobei - mysql erstellt pro Tabelle ein Verzeichis, wo sollte dann der Index gespeichert werden?

Wär' mir, ehrlich gesagt, neu - aber interessant. Ich frag' mich aber, was das nutzen soll? Seh' ich im Moment einfach nicht.

Eine gute Lektüre über MySQL und Indizes:
http://www.mysql.com/doc/en/MySQL_indexes.html

»

a.key <= benötigt für den JOIN
b.key <= benötigt für den JOIN

Also jeweils ein Index für das Feld key in Tabelle a und in Tabelle b
Aber es kann doch pro Abfrage nur _ein_ Index verwendet werden, oder?

Nein, MySQL nutzt soviele wie es für nötig hält.

1. Index auf a.key und b.key

Wird der Index auf b.key und a.key genutzt, um schnell die relevanten Zeilen zu finden, vermeidet eben die lineare Suche

2. Index auf b.wert1 und b.wert2

Wie Du dort nachlesen kannst, verwendet MySQL einen ggf. vorhandenen Index, wenn MySQL dadurch weniger als 30% der Datensätze lesen muss.

Jedesmal greife ich drauf zu. Ich will einen Index gerade für die obige Anfrage optimieren.

Wenn Du eine spezielle Abfrage optimieren willst, dann verwende EXPLAIN, um herauszufinden, wie MySQL an die Abfrage rangeht, anschließend kannst Du in der SELECT-Anweisung noch USE INDEX verwenden, um MySQL einen bestimmten Index anzuweisen, den es nutzen soll.

nö, die Spalte "key" ist nur unique. Was bringt mir ein Primärschlüssel, wenn ich gerne einen Index mit allen 4 Spalten hätte,  oder brauche ich einen primär-Schlüssel über die Spalte a.key, und einen 2. Index über (b.key,b.wert1,b.wert2)? b.key ist ebenfalls unique, und somit sollte es auch an erster Stelle stehen.

Indizes gehören zum allgemeinen Datenbankentwurf, und nicht unbedingt zur Optimierung einer Abfrage. Ist es allerdings _die_ Abfrage, die 90% Deiner Datenbankaktionen ausmacht, dann lohnt es sich, die Datenbank in Hinblick auf diese Abfrage zu optimieren.

MySQL verwendet drei Schlüsselwörter, um Indizes anzulegen:

PRIMARY KEY - Primärschlüssel, ist auf jeden Fall eindeutig
UNIQUE - ein eindeutiger Index, d.h. jeder Wert darf nur einmal vorkommen
INDEX - Ein nicht eindeutiger Index

Alle drei Anweisungen erzeugen einen Index, und ein eindeutiger Index muss nicht unbedingt ein Primärschlüssel sein (wenn er es auch meistens ist)

Können einem Datensatz aus Tabelle b mehrere Datensätze aus Tabelle a zugeordnet sein (1:n)-Beziehung, dann ein einfacher Index auf key in Tabelle a
Oh, jetzt wo Du es sagst, sicher kann das sein ;-)

Also a.key ist also doch nicht unique, kann aber immer noch nur Wete aus b.key enthalten, welche aber auf alle Fälle unique ist.

Wenn Du eine 1:n-Beziehung zwischen zwei Tabellen hast, und Du oft den JOIN nutzt, dann indiziere die Felder.

Wär' zu schön, wenn MySQL schon FOREIGN KEY in 3.x.x hätte.

beste, da bringt es nichts wenn ich 4 für sich nette Indices habe, ich brauche _einen_ guten der auf obige Abfrage passt.

Doch

Das ist egal.

Dann nimm so viele Indizes wie möglich!

Gruss,

Vinzenz

[Andreas Korthaus]

Hallo!

In einigen Fällen kann eine Anfrage so optimiert werden, dass Sie Werte abruft, ohne in der Daten-Datei nachzuschlagen. Wenn alle benutzten Spalten einer Tabelle numerisch sind und ein ganz links stehendes Präfix für einen Schlüssel ergeben, können die Werte mit größerer Geschwindigkeit aus dem Index-Baum abgerufen werden:

Ich finde es nicht mehr, aber ich könnte schwören das ich in der Doku irgendwo gelesen habe dass man auch indices über 2 Tabellen erstellen kann. Wobei - mysql erstellt pro Tabelle ein Verzeichis, wo sollte dann der Index gespeichert werden?

Wär' mir, ehrlich gesagt, neu - aber interessant. Ich frag' mich aber, was das nutzen soll? Seh' ich im Moment einfach nicht.

Hatte ich wohl was falsches im Kopf, naja.

Eine gute Lektüre über MySQL und Indizes:
http://www.mysql.com/doc/en/MySQL_indexes.html

Das habe ich schon mehrmals gelesen, aber so 100%ig schlau bin ich noch nicht.

Nein, MySQL nutzt soviele wie es für nötig hält.

Ich habe das zwar noch nie irgendwo wirklich eindeutig lesen können, aber Michael sagt da was anders.

1. Index auf a.key und b.key

zumindest ein Index auf a.key ist klar. Wenn das denn so ist das nur ein Index pro Abfrage pro Tabelle genutzt wird. In der Doku steht z.b:

"Wenn es separate einspaltige Indexe auf spalte1 und spalte2 gibt, versucht der Optimierer, den restriktivsten Index zu finden, indem er entscheidet, welcher Index weniger Zeilen finden wird, und diesen Index dann benutzen, um Zeilen abzurufen."
d.h. wenn ich alles eigene Indices erstelle, dann wird höchtens einer benutzt, und zwar der restriktivste, also der über b.key.

Wird der Index auf b.key und a.key genutzt, um schnell die relevanten Zeilen zu finden, vermeidet eben die lineare Suche

klar!

2. Index auf b.wert1 und b.wert2

Mir stellt sich eigentlich nur noch die Frage, ob ein Index auf Spalte b.key, oder (b.wert1,b.wert2) oder (b.key,b.wert1,b.wert2). Der zweite würde vermutlich auc nicht genutzt, ich würde mal auf den 3. Tippen.

Wie Du dort nachlesen kannst, verwendet MySQL einen ggf. vorhandenen Index, wenn MySQL dadurch weniger als 30% der Datensätze lesen muss.

ja, _einen_!

Wenn Du eine spezielle Abfrage optimieren willst, dann verwende EXPLAIN, um herauszufinden, wie MySQL an die Abfrage rangeht, anschließend kannst Du in der SELECT-Anweisung noch USE INDEX verwenden, um MySQL einen bestimmten Index anzuweisen, den es nutzen soll.

MySQL weiß besser als ich welcher Index der beste ist, also warum sollte ich das vorschreiben? Und wie verrät mir EXPLAIN wie MySQL da herangeht? Ich finde EXPLAIN bis auf die Information welcher Index tatsächlich verwendet wird wenig hilfreich.

Indizes gehören zum allgemeinen Datenbankentwurf, und nicht unbedingt zur Optimierung einer Abfrage.

Sehe ich anders. Der Index ist dazu da die Anfragen zu beschleunigen, sonst nichts. Der Datenbank-Entwurf hat mit den Indices erstmal nichts zu tun. Wenn ich meine Daten-Struktur habe kann ich Indices dazu einsetzen, die Anfragen zu beschleunigen, evtl sogar jede "teure" Abfrage einzelnd. Man kann ja in einer Tabelle mehrere Indices speziell für mehrere verschiedene Abfragen haben. Es wird halt bei jeder Abfrage dann immer der für die aktuelle Abfrage optimierte Index verwendet.

Ist es allerdings _die_ Abfrage, die 90% Deiner Datenbankaktionen ausmacht, dann lohnt es sich, die Datenbank in Hinblick auf diese Abfrage zu optimieren.

Das habe ich vor. Habe ich 3 verschiedene Abfragen die zusammen 90% der Abfragen ausmachen, dann kann ich auch 3 Verschiedene Indices erstrellen, für jedee der 3 den optimalen Index. Der Query-Optimizer sollte sich dann automatisch den jeweils günstigstens Index verwenden.

MySQL verwendet drei Schlüsselwörter, um Indizes anzulegen:

PRIMARY KEY - Primärschlüssel, ist auf jeden Fall eindeutig
UNIQUE - ein eindeutiger Index, d.h. jeder Wert darf nur einmal vorkommen
INDEX - Ein nicht eindeutiger Index

Ist mir bekannt ;-)

Dann nimm so viele Indizes wie möglich!

Was habe ich von vielen Indices wenn am Ende nur einer verwendet wird?  Bei Mehrspaltigen wird es nur kritisch ob der Index überhaupt verwendet wird, aber das muß ich nochmal nachlesen, da kommt es näämlich auf die Reihenfolge der indizierten Spalten an!

Viele Grüße
Andreas

[Michael Schröpl]

Hi Andreas,

"Wenn es separate einspaltige Indexe auf spalte1 und spalte2 gibt, versucht der Optimierer, den restriktivsten Index zu finden, indem er entscheidet, welcher Index weniger Zeilen finden wird, und diesen Index dann benutzen, um Zeilen abzurufen."
d.h. wenn ich alles eigene Indices erstelle, dann wird höchtens einer benutzt, und zwar der restriktivste, also der über b.key.

Für dieses "also" hast Du ein bißchen wenig Kontext angeboten.

Cheatahs Posting geht davon aus, daß  der Index über b.wert1 und b.wert2 der restriktivste ist (und zwar von allen in Frage kommenden Indexen aller beteiligten Tabellen!), und daß deshalb von der hier berechneten kleinsten Trefferzahl ausgehend weitere Zugriffspfade auf andere Tabellen aufgebaut werden - beispielsweise über deren Index zur JOIN-Spalte, vielleicht aber auch über andere Indexe, falls entsprechende zusätzliche WHERE-Klauseln auch dort eine frühzeitige scharfe Filterung erlauben.

2. Index auf b.wert1 und b.wert2
   Mir stellt sich eigentlich nur noch die Frage, ob ein Index auf Spalte b.key, oder (b.wert1,b.wert2) oder (b.key,b.wert1,b.wert2). Der zweite würde vermutlich auc nicht genutzt, ich würde mal auf den 3. Tippen.

Cheatah hat ausgeführt, weshalb der zweite Index, erweitert um b.key, in diesem Fall am besten hilft - die ersten beiden Felder helfen bei der Adressierung der gesuchten Teilmenge, das dritte Feld erspart die Adressierung des Datensatzes der entsprechenden Zeile. Derselbe Index kann also innerhalb derselben Query unterschiedliche Funktionen haben.

MySQL weiß besser als ich welcher Index der beste ist, also warum sollte ich das vorschreiben?

Ob mySQL das wirklich am besten weiß, hängt davon ab, welche Informationen es auswerten darf. So detailliert habe ich keine Vorstellung vom Query Optimizer, daß ich diesem blind vertrauen würde ... aber zum Thema "regelbasierter vs. kostenbasierter Optimierer" solltest Du vermutlich mal einen Grundlagenartikel lesen, das wäre in Deinem aktuellen Stadium vermutlich hilfreich (die erforderlichen Grundbegriffe beherrschst Du inzwischen).
Ich kann Dir nur sagen, daß ich die Oracle-Möglichkeit, per "hints" die Verwendung bestimmter Indexe "nahezulegen", schon mal dringend benötigt habe, weil meine Tabelle "degenerierte" Daten enthielt (sehr viele UNIQUE-Datensätze plus einen einzigen Sonderwert, der dann aber irre oft vorkam, jedoch nie in einer WHERE-Klausel verwendet wurde), und Oracle mit seiner Anschauung des wahrscheinlichen Nutzwertes dieses Indexes total daneben lag: Die mittlere Projektivität des Index war ihm nicht gut genug, die tatsächliche (aufgrund der mir bekannten WHERE-Klauseln) war jedoch optimal. Also mußte ich Oracle zu seinem Glück zwingen ...

Und wie verrät mir EXPLAIN wie MySQL da herangeht? Ich finde EXPLAIN bis auf die Information welcher Index tatsächlich verwendet wird wenig hilfreich.

Das ist doch schon eine ganze Menge. ;-)
Außerdem zeigt Dir mySQL, wie viele Operationen es beim Zugriff auf den Index gemacht hat - es sagt Dir also seine "Kostenfunktion" in der Einheit "Indexzugriffe". Mach mal mehrere Zugriffe mit verschiedenen Suchbegriffen und laß sie Dir jeweils EXPLAINen ...

Indizes gehören zum allgemeinen Datenbankentwurf, und nicht unbedingt zur Optimierung einer Abfrage.
Sehe ich anders. Der Index ist dazu da die Anfragen zu beschleunigen, sonst nichts.

Beide Aussagen finde ich zu radikal - aber an beiden ist durchaus etwas dran.

Wird ein Index als Mittel zur Durchsetzung von Datenkonsistenz eingesetzt (also ein UNIQUE INDEX, um Duplikate innerhalb einer Spalte zu verhindern), dann gehört er in den Datenbankentwurf (letzten Endes implementiert er dabei eine CONSTRAINT, welche das RDMBS nicht mit anderen Mitteln beherrscht).
Aus diesem Blickwinkel heraus macht auch das gewohnheitsmäßige Anlegen von Primärschlüsseln Sinn - es erspart einem die in diesem Forum immer wiederkehrende Frage, wie man nachträglich Duplikate aus einer Tabelle löscht. ;-)

Zusätzliche Performance-steigernde Indizes, wie Du sie hier suchst, gehören jedoch in der Tat zur Query-Optimierung.

Du siehst, ein Schlüsselwort INDEX sagt allein noch nichts darüber aus, was man damit letzten Endes erreichen will ...

Was habe ich von vielen Indices wenn am Ende nur einer verwendet wird?

Du hast die Chance, daß in mehreren verschiedenen Situationen der Query Optimizer unterschiedliche Ausführungspläne für geeignet hält, wobei Du jeden dieser Ausführungspläne durch einen _passenden_ Index unterstützen kannst.

Bei Mehrspaltigen wird es nur kritisch ob der Index überhaupt verwendet wird, aber das muß ich nochmal nachlesen, da kommt es näämlich auf die Reihenfolge der indizierten Spalten an!

Richtig.

Viele Grüße
      Michael

[Robert]

Schön, daß ich Dir auch mal was zeigen kann ;)

Wenn die Tabelle schon existiert, dann

ALTER TABLE Tb_A ADD INDEX ( key_a )

oder beim erstellen

CREATE TABLE Tb_A(
  key_a MEDIUMINT NOT NULL ,
  INDEX ( key_a )
 ) TYPE = MyISAM

Gruß Robert

[Andreas Korthaus]

Schön, daß ich Dir auch mal was zeigen kann ;)

Wie man einen Index anlegt ist mir bekannt, mir geht es darum einen möglichst optimalen Index für eine möglichst schnelle Abfrage zu erstellen.

Grüße
Andreas

[Michael Schröpl]

Hi Andreas,

Wobei - mysql erstellt pro Tabelle ein Verzeichis, wo sollte dann der Index gespeichert werden?

weder glaube ich diese Behauptung, noch macht sie überhaupt Sinn: Nicht mySQL erstellt diese Dateien, sondern der jeweilige Tabellentreiber. Und da kann jeder machen, was er will.

Aber es kann doch pro Abfrage nur _ein_ Index verwendet werden, oder?

Pro Abfrage auf _eine_ Tabelle, ja. Aber ein JOIN enthält Abfragen auf mehrere Tabellen.

Wenn ein JOIN versuchen soll, die zueinander passenden Werte aus (mindestens) zwei Tabellen zu finden, dann hat er verschiedene Möglichkeiten. Zwei fallen mir spontan ein:

1. In beiden Tabellen ist das Berechnen der Werte "schwierig". Dann ist es sinnvoll, beides separat zu berechnen, beide Ergebnismengen zwischenzuspeichern und sie anschließend zu kombinieren. Dies impliziert, beide Mengen nach dem JOIN-Kriterium zu sortieren - und das ist bekanntlich teuer (n * log(n)). Läge bereits ein Index, also ein nach dem Auslese-Kriterium sortierter Baum vor, dann könnte man diesen eventuell nutzen - selbst wenn das JOIN-Kriterium selbst gar nicht Bestandteil der WHERE-Klausel dieses Tabellenzugriffs ist: Es könnte trotzdem die beste verfügbare Methode sein, die Tabelle in dieser Reihenfolge zu traversieren.

2. Das Finden eines zugehörigen Wertes ist in einer der beiden Tabellen sehr viel einfacher als in der anderen (beispielsweise weil in der einen Tabelle ein UNIQUE INDEX darauf existiert). In diesem Falle weiß der Query Optimizer, daß die Anzahl der Treffer im Wesentlichen durch die Treffer aus der anderen Tabelle bestimmt wird, und er weiß, daß er zu jedem dieser Treffer sehr schnell über den Indexzugriff das passende Gegenstück finden kann. In diesem Fall kann der Query Optimizer sich dafür entscheiden, nicht die beiden Mengen getrennt zu berechnen, sondern nur die zweite und über diese eine Schleife laufen zu lassen, in der jeweils das passende Gegenstück geholt wird. Dies ist insbesondere dann sinnvoll, wenn die Ergebnismenge dann später _nicht_ nach dem JOIN-Kriterium sortiert ausgegeben werden soll - wäre dies der Fall, dann hätten wir nicht viel gewonnen, wenn wir die zunächst nicht notwendige Sortierung später dann doch noch durchführen müßten (mit einer anderen Anzahl von Datensätzen - meistens kleiner, in manchen JOIN-Fällen aber sogar größer).

Viele Grüße
      Michael

P.S.: Indexe über Spalten aus mehreren Tabellen sind in SQL so ohne weiteres nicht darstellbar, fürchte ich.
Andererseits habe ich in Oracle 7 Mitte der 90er mal ein Konstrukt verwendet, welches sich "Cluster" schimpfte und einen gemeinsamen Cluster-Index definierte - in ein solches Cluster konnte man dann mehrere Tabellen so legen (d. h. darin erzeugen und definieren, welche Spalte[n] für den Cluster-Index verwendet werden sollten), daß die Datensätze in bereits nach dem Cluster-Index geJOINter Form physikalisch abgespeichert wurden. Das war natürlich für das Auslesen in der geJOINten Form sehr angenehm, weil es die Anzahl der Festplattenzugriffe erheblich reduzierte.

[Andreas Korthaus]

Hallo!

weder glaube ich diese Behauptung,

Das ist keine Glaubesnfrage ;-)

noch macht sie überhaupt Sinn: Nicht mySQL erstellt diese Dateien, sondern der jeweilige Tabellentreiber. Und da kann jeder machen, was er will.

ok ;-)

Pro Abfrage auf _eine_ Tabelle, ja. Aber ein JOIN enthält Abfragen auf mehrere Tabellen.

Also im KLartext, wenn ich eine Join über 2 Tabellen mache kann ich maximal 2 Indices verwenden, maximal einen pro Tabelle, richtig?

1. In beiden Tabellen ist das Berechnen der Werte "schwierig". Dann ist es sinnvoll, beides separat zu berechnen, beide Ergebnismengen zwischenzuspeichern und sie anschließend zu kombinieren. Dies impliziert, beide Mengen nach dem JOIN-Kriterium zu sortieren - und das ist bekanntlich teuer (n * log(n)). Läge bereits ein Index, also ein nach dem Auslese-Kriterium sortierter Baum vor, dann könnte man diesen eventuell nutzen - selbst wenn das JOIN-Kriterium selbst gar nicht Bestandteil der WHERE-Klausel dieses Tabellenzugriffs ist: Es könnte trotzdem die beste verfügbare Methode sein, die Tabelle in dieser Reihenfolge zu traversieren.

Was bedeutet "traversieren"?
Den 1, Satz verstehe ich nicht. Wie will man(mysql) für Werte "berechnen"? Die Tabellen sollen doch verknüptft ewerden, wawum soll man dann in beiden Tabellen alle Werte Sortieren? Ich würde die erste Tabelle durchgehen und gleichzeitig in der 2. Tabelle nach übereinstimmungen Suchen. Aus der Ergebnismenge würde ich dann mit der WHERE-Bedingung filtern. Die erste Tabelle enthält ja erheblich weniger Datensätze, also ist die Schleife in der das geschieht nichtmal so auffwenig.
Weil Du das schreibst, in der Doku steht der Otimizer würde die Verknüpfungsbedingung in die WHERE Bedingung "verschieben", wieso?

2. Das Finden eines zugehörigen Wertes ist in einer der beiden Tabellen sehr viel einfacher als in der anderen (beispielsweise weil in der einen Tabelle ein UNIQUE INDEX darauf existiert).

Die 2. Tabelle hat einen non_unique Index, aber dafür erheblich weniger Datensätze, die 2. hat einen unique Index, aber nur solange ich die Where-Bedingung außen vorlasse. Dann kann ich über die "join-Spalte" der 2. Tabelle einen Primär-Schlüssel legen. Aber wie gesagt hätte ich dann die Wehre-Bedingung nicht optimiert. Aber da ich ja in der Tabelle nur einne Index verwenden kann, müßte ich auf den unique Primär-Schlüssel verzichten, und einen 3-spaltigen Index über die Spalten b.key(Join-Spalte) b.wert1 und b.wert2 legen(beides WHERE-Bedingung), aber da der Index dann nicht merh Unique ist, wird das Joinen vermutlich langsamer. Außerdem mache ich mir hier ein 2. Problem - wird der Index dann überhaupt verwendet? Ein Index (b.key,b.wert1,b.wert2), in der Doku habe ich dazu nur BEispiele zu WHERE-Bedingungen gelesen, halt das der Index nur verwendet wird, wenn auch in Reihenfolge der Spalten im Index die einzelnen durch AND verknüpften WHERE-Bedingungen stehen. Wie ist das wenn ich 1 Spalte für den JOIN verwende, und 2 für die WHERE-Bedingung?
Nochmal die Abfrage:

SELECT a.key
FROM a
LEFT JOIN b
ON a.key=b.key
WHERE(b.wert1 = $variable1 AND b.wert2 < $variable2)

Beziehung zw. a.key : b.key => n:1

2 Indices:
1.: (a.key) <- non unique
2.: (b.key,b.wert1,b.wert2)

Wäre das so das Optimum?

In diesem Falle weiß der Query Optimizer, daß die Anzahl der Treffer im Wesentlichen durch die Treffer aus der anderen Tabelle bestimmt wird, und er weiß, daß er zu jedem dieser Treffer sehr schnell über den Indexzugriff das passende Gegenstück finden kann. In diesem Fall kann der Query Optimizer sich dafür entscheiden, nicht die beiden Mengen getrennt zu berechnen, sondern nur die zweite und über diese eine Schleife laufen zu lassen, in der jeweils das passende Gegenstück geholt wird. Dies ist insbesondere dann sinnvoll, wenn die Ergebnismenge dann später _nicht_ nach dem JOIN-Kriterium sortiert ausgegeben werden soll - wäre dies der Fall, dann hätten wir nicht viel gewonnen, wenn wir die zunächst nicht notwendige Sortierung später dann doch noch durchführen müßten (mit einer anderen Anzahl von Datensätzen - meistens kleiner, in manchen JOIN-Fällen aber sogar größer).

Sortieren muß ich nicht. Aber das hast Du Dir jetzt überlegt, wie aber ist das in der Praxis? Sind die Indices wie ich oben geschrieben habe das was zu empfehlen ist, oder habe ich noch was falsch verstanden?

Viele Grüße
Andreas

PS: Folgendes Zitat aus der MySQL Doku ist leidr im falschen Posting gelandet ;-)

"In einigen Fällen kann eine Anfrage so optimiert werden, dass Sie Werte abruft, ohne in der Daten-Datei nachzuschlagen. Wenn alle benutzten Spalten einer Tabelle numerisch sind und ein ganz links stehendes Präfix für einen Schlüssel ergeben, können die Werte mit größerer Geschwindigkeit aus dem Index-Baum abgerufen werden:"

das nur mal so zur Diskussion unten ob man besser Strings oder INTEGER einsetzt, wobei das natürlich nur für MySQL so gilt.

[Michael Schröpl]

Hi Andreas,

Pro Abfrage auf _eine_ Tabelle, ja. Aber ein JOIN enthält Abfragen auf mehrere Tabellen.
Also im KLartext, wenn ich eine Join über 2 Tabellen mache kann ich maximal 2 Indices verwenden, maximal einen pro Tabelle, richtig?

Yep. Beide Datenstrukturen sind ja separat gespeichert (abgesehen von dem von mir an anderer Stelle erwähnten Cluster-Mechanismus ...), und für jede dieser Datenstrukturen sucht sich das RDMBS einen geeigneten Zugriffspfad.

Was bedeutet "traversieren"?

"Durchlaufen." (Ist Dein Google kaputt? ;-)

1. In beiden Tabellen ist das Berechnen der Werte "schwierig".
   Den 1, Satz verstehe ich nicht. Wie will man(mysql) für Werte "berechnen"? Die Tabellen sollen doch verknüpft ewerden, warum soll man dann in beiden Tabellen alle Werte Sortieren?

Nicht in den Tabellen - nur in den Treffermengen nach dem WHERE-Filter auf die jeweilige Tabelle.
Wie sonst möchtest Du denn zwei Mengen miteinander schneiden? Bedenke, daß Du _nach_ dem Berechnen der jeweiligen Treffer aus beiden Tabellen keinerlei Indexstrukturen für den gegenseitigen Abgleich mehr nutzen kannst.

Stell Dir vor, jede der beiden Tabellen produziert 100 Treffer in unsortierter Reihenfolge. Paarweiser Abgleich beim JOIN kostet 10000 Vergleiche.

Beide Mengen sortieren kostet jeweils n * log(n), also zusammen ca. 1400 Vergleiche, danach kannst Du beide nun sortierte Listen paarweise "aneinander vorbei ziehen", brauchst dafür noch mal ein paar hundert Vergleiche (je nach Duplikat-Quote im JOIN).

Was ist schneller?

Ich würde die erste Tabelle durchgehen und gleichzeitig in der 2. Tabelle nach übereinstimmungen Suchen.

Und wie machst Du das? Indem Du zu jedem Treffer aus der ersten Tabelle einen full table scan über die zweite Tabelle machst?

Die erste Tabelle enthält ja erheblich weniger Datensätze,

Und woher weiß das RDBMS das? Vor allem: Ist das überhaupt wichtig? Ist nicht noch wichtiger, wieviele Datensätze von Deiner Query _ausgewählt_ werden, als wie viele in der Tabelle _enthalten_ sind?
Ein Indexzugriff auf eine Million Datensätze über einen UNIQUE INDEX ist schneller als ein Indexzugriff auf 1000 Zeilen mit lediglich drei verschiedenen Werten ... das ist Dein Problem beim Suchen nach "javascript".

Weil Du das schreibst, in der Doku steht der Otimizer würde die Verknüpfungsbedingung in die WHERE Bedingung "verschieben", wieso?

Dazu habe ich nicht genug Kontext. (Und nein, ich äußere mich nicht zu den verschiedenen Arten von JOINs, die von neumodischen SQL-Dialekten unterstützt werden - ich bin bisher immer ohne das Wort "JOIN" ausgekommen.)

Die 2. Tabelle hat einen non_unique Index, aber dafür erheblich weniger Datensätze, die 2. hat einen unique Index, aber nur solange ich die Where-Bedingung außen vorlasse.

Huch ... was hat die uniqueness eines Index mit einem Zugriff auf diese Daten zu tun?

Dann kann ich über die "join-Spalte" der 2. Tabelle einen Primär-Schlüssel legen. Aber wie gesagt hätte ich dann die Wehre-Bedingung nicht optimiert.

Tja, einen Tod mußt Du sterben.

Wenn schon die Projektion _vor_ dem Verknüpfen gut ist, also pro Tabelle nur noch eine Handvoll Treffer erzeugt, dann ist anschließendes Sortieren und Kombinieren beider Treffermengen auch gut ... wenn nicht, dann gibt es bessere Ausführungspläne, nämlich in der Tat von der Tabelle mit den wenigen Treffern aus eine Schleife zu steuern, die jeweils die passenden Treffer aus der anderen Tabelle fischt (voraugesetzt, das geht ebenfalls hinreichend schnell, d. h. über einen guten Zugriffspfad).
EXPLAIN wird Dir jeweils sagen, welche Vorgehensweise es gewählt hat ... und da Du in SQL schlecht ausdrücken kannst, einen von beiden Wegen zu bevorzugen, mußt Du dem Optimizer vertrauen, daß er die richtige Entscheidung trifft. (Das _kann_ mit bestimmten Anordnungen innerhalb Deiner Query zusammenhängen ... deshalb hatte ich neulich gefragt, ob die Reihenfolge der MATCH()-Aufrufe etwas an der Geschwindigkeit ändert.)

Aber da ich ja in der Tabelle nur einne Index verwenden kann, müßte ich auf den unique Primär-Schlüssel verzichten, und einen 3-spaltigen Index über die Spalten b.key(Join-Spalte) b.wert1 und b.wert2 legen(beides WHERE-Bedingung), aber da der Index dann nicht merh Unique ist, wird das Joinen vermutlich langsamer.

Die letzte Bemerkung kann ich nicht nachvollziehen. Das JOIN besteht aus dem gesamten Ablauf - ob beim Zugriff auf eine der beteiligten Tabellen tatsächlich ein Index genutzt wird, und sogar welcher, kann eine Entscheidung des Query Optimizers sein (und die kann im Extremfall bei identischer SQL-Query modulo Host-Variablen sogar jedesmal anders ausfallen, falls das RDMBS "javascript" als böse[tm] erkennen kann, mit Hilfe von ANALYZE TABLE etc.).

Außerdem mache ich mir hier ein 2. Problem - wird der Index dann überhaupt verwendet?

Frag Dein RDBMS - dazu ist EXPLAIN da.

Ein Index (b.key,b.wert1,b.wert2), in der Doku habe ich dazu nur BEispiele zu WHERE-Bedingungen gelesen, halt das der Index nur verwendet wird, wenn auch in Reihenfolge der Spalten im Index die einzelnen durch AND verknüpften WHERE-Bedingungen stehen. Wie ist das wenn ich 1 Spalte für den JOIN verwende, und 2 für die WHERE-Bedingung?

Dann würde ich über die beiden WHERE-Spalten einen Index legen. Denn diese willst Du sicherlich über einen Index adressieren, um eine möglichst kleine Treffermenge vor dem Abgleich mit anderen Tabellen zu bekommen ... Du möchtest die Chance nutzen, von dieser Tabelle aus die anderen Tabellen anzusteuern, falls sie zufällig die "beste" während dieses JOINs ist.
Ist diese nicht der Fall, dann würde eine von einer anderen Tabelle "getrieben" Schleife nach der JOIN-Spalte dieser Tabelle suchen - dabei könnte ein zweiter Index über nur diese JOIN-Spalte helfen. Ob und in welchem Fall ein Index über alle drei Spalten helfen könnte, da bin ich mir im Moment reichlich unsicher.

Ein Index ist letzten Endes immer als sortierter Baum vorstellbar. Ein Index über mehrere Felder ist ein Index über Tupel, die sich aus diesen Feldern zusammensetzen; dieser Index ist nach dem ersten Feld sortiert, bei Gleichstand nach dem zweiten, bei erneutem Gleichstand nach dem dritten. Mit einem solchen Index kannst Du Such-Operationen nach jedem Präfix dieser Feldermenge unterstützen, nicht aber Such-Operationen nach anderen Felderfolgen (also auch nicht nach der Kombination aus dem zweiten und dritten Feld - danach ist das Ding nun mal nicht sortiert).

"In einigen Fällen kann eine Anfrage so optimiert werden, dass Sie Werte abruft, ohne in der Daten-Datei nachzuschlagen. Wenn alle benutzten Spalten einer Tabelle numerisch sind und ein ganz links stehendes Präfix für einen Schlüssel ergeben, können die Werte mit größerer Geschwindigkeit aus dem Index-Baum abgerufen werden:"
das nur mal so zur Diskussion unten ob man besser Strings oder INTEGER einsetzt, wobei das natürlich nur für MySQL so gilt.

Daß eine Abfrage schneller ist, muß noch kein Grund dafür sein, Strings nach Integer zu konvertieren: Falls Du extern dann doch Strings brauchst, mußt Du in beiden Richtungen konvertieren (zuerst bei der WHERE-Bedingung, dann nochmal beim Auslesen der Treffer). Das kostet auch etwas ... es kommt also darauf an, ob Du genug einsparst, um diese beiden Konvertierungen zu "verdienen".

Viele Grüße
      Michael

[Cheatah]

Hi,

ich gestehe, ich habe nicht alles gelesen; aber da in Deiner Antwort auf Michaels Posting noch keine Klarheit herrscht, dürfte das Problem noch nicht gelöst sein ;-)

SELECT a.key
FROM a
LEFT JOIN b
ON a.key=b.key
WHERE(b.wert1 = 1234 AND b.wert2 < 4321)

Überlege Dir, wie Du gerne hättest, dass die Datenbank vorgeht. In diesem Fall willst Du alle Datensätze aus a, für die in den zugehörigen Datensätzen aus b etwas zutrifft - also musst Du zunächst die Ergebnisse aus b geschickt einschränken, bevor Du a involvieren lassen darfst.

Ich unterstelle mal, dass "b.wert1=1234" prozentual sehr selten in b ist; wenn ein gewisser Grenzwert überschritten ist, wäre ein Index darüber ansonsten sogar kontraproduktiv. Läuft der Index in b nun über wert1 und wert2 (in dieser Reihenfolge), wird die Ergebnismenge sehr schnell eingeschränkt und mit einem Range Scan für wert2 auf die Schnelle noch etwas reduziert. Anschließend würde MySQL die gefundenen Zeilen von b "besuchen" und ihren b.key auslesen. Wenn ich nicht irre, reagiert MySQL ähnlich wie Oracle, wenn Du dem Index noch key hinzufügst: dieser letzte Schritt entfällt. Ergo: Index in b über wert1, wert2, key.

Nachdem MySQL nun viele b.key ermittelt hat, muss es a nach dem jeweiligen key durchsuchen. Dazu bietet sich zwangsläufig ein Index in a über key an. Viel mehr bietet dieses Statement nicht, was optimiert werden könnte - überprüfe mit EXPLAIN SELECT ..., ob die DB so vorgeht, wie es gewünscht war.

Soweit ich das weiß sollten die Spalten in der Reihenfolge ihres "unique-Grades" im Index stehen.

Ja, es sollte so schnell wie möglich so viel wie möglich eingeschränkt werden. Ein mit key beginnender Index in b würde aber nichts bringen, weil key ja _vor_ dem Durchsuchen des Index noch nicht bekannt ist.

Wenn Du Dir einen mehrspaltigen Index als sortierten Baum vorstellst, wirst Du recht schnell dahinter kommen, wie die Datenbank vorgehen muss, um ihn zu durchsuchen. Mit dieser Erkenntnis ist die Findung des richtigen Index gar nicht mehr so schwer.

Cheatah