Wie bekomme ich einen JOIN schnell?

[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