Warum unterstützen verschachtelte Schleifen nur Linksverknüpfungen?

In Craig Freedmans Blog " Nested Loops Join" erklärt er, warum der Join "Nested Loops Join" keinen rechten äußeren Join unterstützen kann:

Das Problem ist, dass wir die innere Tabelle mehrmals scannen - einmal für jede Zeile des äußeren Joins. Während dieser mehreren Scans können dieselben inneren Zeilen mehrmals auftreten. An welchem ​​Punkt können wir schließen, dass eine bestimmte innere Reihe nicht beigetreten ist oder nicht beitreten wird?

Kann jemand dies bitte auf wirklich einfache und lehrreiche Weise erklären?

Bedeutet das, dass die Schleife mit der äußeren Tabelle ( R1) beginnt und die innere ( R2) scannt ?

Ich verstehe, dass für einen R1Wert, der nicht mit verknüpft ist, dieser durch einen Wert R2ersetzt werden sollte, NULLdamit die Ergebnismenge ( NULL, R2) wird. Für mich scheint es unmöglich, einen R2Wert zurückzugeben, wenn er R1nicht verbunden ist, da er nicht wissen kann, welcher R2Wert zurückgegeben werden soll. Aber so wird es nicht erklärt. Oder ist es?

SQL Server optimiert zwar (und ersetzt es häufig) RIGHT JOINdurch LEFT JOIN, aber die Frage ist, warum es technisch unmöglich ist, eine Logik NESTED LOOPS JOINzu verwenden / zu unterstützen RIGHT JOIN.

Das Hauptproblem hierbei ist die Implementierung eines äußeren Joins unter Verwendung verschachtelter Schleifen auf eine technische Weise, die der logischen Weise entgegengesetzt ist , bei der auf die innere Tabelle über die äußere Schleife und auf die äußere Tabelle über die innere Schleife zugegriffen wird .

Lassen Sie uns anhand der Tabellen A und B implementieren A LEFT JOIN B.

A
--
1
2

B
_
1
3

Lassen Sie es uns zuerst auf " natürliche " Weise tun .

Wir iterieren durch A.
Wir greifen auf Datensatz 1 zu.
Wir iterieren durch B.
Wir finden Datensatz 1 in B und geben 1-1 aus .

Wir iterieren weiter durch A.
Wir greifen auf Datensatz 2 zu.
Wir iterieren durch B.
Wir finden keine Übereinstimmung in B.
Wir geben 2-null aus .

Jetzt machen wir es auf die " entgegengesetzte " Weise.

Wir iterieren durch B.
Wir greifen auf Datensatz 1 zu.
Wir iterieren durch A.
Wir finden Datensatz 1 in A und geben 1-1 aus .

Wir iterieren weiter durch B.
Wir greifen auf Datensatz 3 zu.
Wir iterieren durch A.
Wir finden keine Übereinstimmung in A.

Denken Sie jetzt daran, dass dies A LEFT JOIN Bder Fall war , was bedeutet, dass wir zusätzlich zu 1-1 2-null ausgeben sollten .
Das Problem ist, dass wir zu diesem Zeitpunkt keine Ahnung haben, für welche Datensätze ID A wir bereits eine Übereinstimmung haben (1) und für welche Datensätze wir keine haben (2).

Dies kann tatsächlich auf verschiedene Arten gelöst werden, z. B. indem ein Bit-Array für Tabelle A gehalten wird.
Wenn ein A-Datensatz als Übereinstimmung gefunden wird, markieren wir ihn im Bit-Array.
Am Ende der verschachtelten Schleifen durchlaufen wir das Bit-Array und geben alle nicht markierten Datensätze aus und geben sie aus.
Dies ist offensichtlich komplizierter als die "natürliche" verschachtelte Schleife.

Was mir im verlinkten Artikel nicht gefällt, ist die Aussage, dass "der Nested-Loop-Join-Algorithmus den logischen Join-Operator von Right Join nicht unterstützt" .

Obwohl es eine Einschränkung gibt, ist der Wortlaut an dieser Stelle etwas verwirrend. Ich hoffe, das Folgende erklärt die Dinge besser:

Der verschachtelte Lop-Join-Algorithmus umfasst zwei Tabellen (unabhängig davon, ob Basistabellen oder Ergebnismengen früherer Operationen irrelevant sind), die als äußere und innere Tabelle bezeichnet werden und vom Algorithmus unterschiedlich behandelt werden (die "äußere" Tabelle wird am äußeren durchlaufen Schleife und die "innere" Tabelle an den inneren Schleifen).

Nehmen wir also an, wir haben einen Join:

A (some_type) JOIN B

Der Algorithmus kann wie folgt ausgeführt werden:

outer-loop-A  nested-loop  inner-loop-B

oder:

outer-loop-B  nested-loop  inner-loop-A

Wenn ( some_type) nun INNERoder CROSSverknüpft ist, gibt es keine Einschränkung. Der Planer kann zwischen zwei Möglichkeiten wählen (mit unterschiedlichen Leistungsmerkmalen, abhängig von der Größe der Sätze, der Verteilung der Werte der verknüpften Spalten, Indizes usw. Normalerweise wird die kleinste Tabelle als "äußere" Tabelle im Algorithmus ausgewählt.

Aber wenn some_typesich LEFTanschließen, kann es nur verwenden:

outer-loop-A  nested-loop  inner-loop-B

und nicht

outer-loop-B  nested-loop  inner-loop-A

Und da a RIGHTimmer als LEFTJoin umgeschrieben werden kann , hat es umgekehrt die gleiche Einschränkung. Für A RIGHT JOIN B(was a umgeschrieben werden kann B LEFT JOIN A) kann nur verwendet werden:

outer-loop-B  nested-loop  inner-loop-A

und nicht umgekehrt ^* .

Die gleiche Einschränkung gilt für Links-Semijoin, Links-Anti-Semijoin, Rechts-Semijoin und Rechts-Anti-Semijoin.

Der FULLJoin hingegen kann nicht direkt mit einem Nested-Loop-Join-Algorithmus behandelt werden. Der Artikel erklärt sehr gut (es ist fast zu Ende), wie ein vollständiger Join in eine Vereinigung aus einem linken Join und einem linken Antisemijoin umgeschrieben werden kann (und vom Optimierer durchgeführt wird), die dann als zwei verschachtelte Schleifen (und a) geplant werden können Union).

^* _{Wie Dudu Markovitz in seiner Antwort erklärt, könnte der umgekehrte Weg verwendet werden, aber nur, wenn wir den Nested-Loop-Join-Algorithmus so modifizieren, dass er am Ende eine zusätzliche Struktur und einen zusätzlichen Schritt aufweist.}