Click here to view and discuss this page in DocCommentXchange. In the future, you will be sent there automatically.

SQL Anywhere 11.0.1 (Deutsch) » SQL Anywhere Server - SQL-Benutzerhandbuch » Abfrageverarbeitung » Abfragen optimieren und ausführen » Algorithmen zur Abfrageausführung » Typen von Algorithmen

 

Join-Algorithmen

SQL Anywhere unterstützt eine Vielzahl unterschiedlicher Join-Implementierungen, die der Abfrageoptimierer verwenden kann. Jeder Join-Algorithmus hat spezifische Eigenschaften, die ihn für eine bestimmte Abfrage und eine bestimmte Ausführungsumgebung mehr oder weniger geeignet machen.

Die Reihenfolge der Joins in einem Zugriffsplan stimmt nicht notwendigerweise mit der Reihenfolge der Joins in der Original-SQL-Anweisung überein. Der Abfrageoptimierer ist dafür verantwortlich, aufgrund der niedrigsten Ausführungskosten die beste Join-Strategie für jede Abfrage zu wählen. In manchen Situationen können Neuschreibungsoptimierungen einer Abfrage für komplexe Anweisungen benutzt werden, welche die Anzahl der Joins, die für eine bestimmte Anweisung berechnet werden, erhöhen oder reduzieren.

SQL Anywhere unterstützt drei Klassen von Join-Algorithmen, in denen es zusätzliche Varianten gibt:

  • Nested-Loops-Join   Der einfachste Algorithmus ist der Nested-Loops-Join. Für jede Zeile auf der linken Seite wird auf der rechten Seite nach einer Übereinstimmung aufgrund der Join-Bedingung gesucht. Normalerweise wird über einen Index auf die Zeilen auf der rechten Seite zugegriffen, um die Gesamtkosten für die Ausführung zu senken. Dieses Szenario wird häufig als Index-Nested-Loops-Join bezeichnet.

    Für den Nested-Loops-Join gibt es Varianten, welche die Joins LEFT OUTER und FULL OUTER unterstützen. Eine Nested-Loops-Implementierung kann auch für Semijoins verwendet werden (meistens für die Verarbeitung von EXISTS-Unterabfragen).

    Ein Nested-Loops-Join kann unabhängig von den Merkmalen der Join-Bedingung benutzt werden, obwohl die Berechnung eines Joins mit Ungleich-Bedingungen sehr ineffizient sein kann.

    Ein Nested-Loops-Full-Outer-Join ist in der Ausführung sehr teuer, egal wie groß die Eingaben sind. Er wird vom Optimierer nur als letzte Möglichkeit gewählt, wenn kein anderer Join-Algorithmus möglich ist.

  • Merge-Join   Ein Merge-Join geht davon aus, dass die beiden Eingaben nach den Join-Attributen sortiert sind. Die Join-Bedingung muss mindestens ein Gleichheits-Prädikat enthalten, damit diese Methode vom Optimierer gewählt wird. Der Basisalgorithmus führt die beiden Eingaben einfach zusammen: Wenn sich die Werte der beiden Join-Attribute unterscheiden, springt der Algorithmus zur nächsten Zeile auf der linken oder rechten Seite, je nachdem, auf welcher Seite der niedrigere der beiden Werte steht. Wenn es mehr als eine Übereinstimmung gibt, ist möglicherweise eine Rückverfolgung erforderlich.

    Für den Merge-Join gibt es Varianten, welche die Left-Outer- und Full-Outer-Joins unterstützen. Der Merge-Join für Fill-Outer-Joins ist erheblich effizienter als sein Gegenstück mit Nested-Loops.

    Der Basisalgorithmus für Merge-Join wird auch benutzt, um die SQL Mengenoperatoren EXCEPT und INTERSECT zu unterstützen, obwohl diese Varianten ausdrücklich als EXCEPT- oder INTERSECT-Algorithmen innerhalb eines Zugriffsplans bezeichnet werden.

  • Hash-Join   Ein Hash-Join ist die vielseitigste Join-Methode, die vom SQL Anywhere-Datenbankserver unterstützt wird. Kurz gesagt erstellt der Hash-Join-Algorithmus eine speicherresidente Hash-Tabelle der kleineren der beiden Eingaben. Dann liest er die größere Eingabe und untersucht die Hash-Tabelle im Speicher auf Übereinstimmungen.

    Hash-Join-Varianten dienen der Unterstützung von Left-Outer-Joins, Full-Outer-Joins, Semijoins und Anti-Semijoins. Weiterhin unterstützt SQL Anywhere Hash-Join-Varianten für rekursive Inner- und Left-Outer-Joins, wenn ein rekursiver UNION-Abfrageausdruck benutzt wird.

    Die Algorithmen für Hash-Inner-Join, Left-Outer-Join, Semijoin und Anti-Semijoin können parallel ausgeführt werden.

    Falls die speicherresidente Hash-Tabelle, die vom Algorithmus erstellt wurde, nicht in den verfügbaren Arbeitsspeicher passt, teilt der Hash-Join-Algorithmus die Eingaben in Partitionen auf (eventuell rekursiv bei sehr großen Eingaben) und führt den Join für jede Partition einzeln aus. Falls nicht genug Cache-Speicher vorhanden ist, um alle Zeilen zu laden, die einen bestimmten Wert der Join-Attribute aufweisen, wechselt jeder Hash-Join, falls möglich, dynamisch zu einer indexbasierten Strategie mit verschachtelten Schleifen (bzw. Nested-Loops-Strategie). Zuerst werden jedoch die Zwischenergebnisse gelöscht, um ein Erschöpfen der Speicherbelegungsquote der Anweisung zu vermeiden.

    Varianten des Hash-Joins werden auch verwendet, um die SQL-Abfrageausdrücke EXCEPT und INTERSECT zu unterstützen, obwohl diese Varianten ausdrücklich als EXCEPT- oder INTERSECT-Algorithmen innerhalb eines Zugriffsplans bezeichnet werden.


HashJoin-Algorithmen (JH, JHSP, JHFO, JHAP, JHO, JHPO)
RecursiveHashJoin-Algorithmus (JHR)
RecursiveLeftOuterHashJoin-Algorithmus (JHRO)
HashSemijoin-Algorithmus (JHS)
HashAntisemijoin-Algorithmus (JHA)
MergeJoin-Algorithmen (JM, JMFO, JMO)
NestedLoopsJoin-Algorithmen (JNL, JNLFO, JNLO)
NestedLoopsSemijoin-Algorithmus (JNLS)
NestedLoopsAntisemijoin-Algorithmus (JNLA)