Dlaczego zagnieżdżone pętle łączą tylko lewe połączenia?

W blogu Craig Freedman, w zagnieżdżonych pętli Dołącz wyjaśnia dlaczego zagnieżdżone pętle przystąpić nie może poprzeć prawo sprzężenia zewnętrznego:

Problem polega na tym, że skanujemy wewnętrzną tabelę wiele razy - raz dla każdego rzędu sprzężenia zewnętrznego. Podczas tych wielu skanów możemy napotkać te same wewnętrzne rzędy wiele razy. W którym momencie możemy dojść do wniosku, że określony rząd wewnętrzny nie dołączył lub nie będzie się łączyć?

Czy ktoś może wyjaśnić to w naprawdę prosty i edukacyjny sposób?

Czy to oznacza, że ​​pętla zaczyna się od zewnętrznej tabeli ( R1), a skanuje wewnętrzną ( R2)?

Rozumiem, że dla R1wartości, która się nie łączy R2, należy ją zastąpić, NULLaby zestaw wyników stał się ( NULL, R2). Dla mnie wydaje się niemożliwe zwrócenie R2wartości, gdy R1się nie łączy, z tego powodu, że nie może wiedzieć, któraR2 wartość zwrócić. Ale nie tak to wyjaśnia. Albo to jest?

SQL Server działa w rzeczywistości Optimize (i często zastępuje) RIGHT JOINz LEFT JOIN, ale chodzi o to, aby wyjaśnić, dlaczego jest to technicznie niemożliwe, aby NESTED LOOPS JOINużyć / support RIGHT JOINlogika.

Głównym problemem jest tutaj implementacja złączenia zewnętrznego, wykorzystującego zagnieżdżone pętle, w sposób techniczny przeciwny do logicznego , w którym dostęp do wewnętrznego stołu jest uzyskiwany przez zewnętrzną pętlę, a dostęp do zewnętrznego stołu przez wewnętrzną pętlę .

Biorąc pod uwagę tabele A i B, zastosujmy A LEFT JOIN B.

A
--
1
2

B
_
1
3

Po pierwsze, zróbmy to w „ naturalny ” sposób.

Iterujemy przez A.
Mamy dostęp do rekordu 1.
Iterujemy przez B.
Znajdujemy rekord 1 w B i wyprowadzamy 1-1 .

Kontynuujemy iterację przez A.
Mamy dostęp do rekordu 2.
Iterujemy przez B.
Nie znajdujemy żadnego dopasowania w B.
Wyprowadzamy 2-null .

Zróbmy to teraz w „ przeciwny ” sposób.

Iterujemy przez B.
Mamy dostęp do rekordu 1.
Iterujemy przez A.
Znajdujemy rekord 1 w A i wyprowadzamy 1-1 .

Kontynuujemy iterację przez B.
Mamy dostęp do rekordu 3.
Iterujemy przez A.
Nie znajdujemy żadnego dopasowania w A.

Teraz pamiętaj, że tak było A LEFT JOIN B, co oznacza, że ​​oprócz 1-1 powinniśmy wypisać 2-null .
Problem polega na tym, że w tym momencie nie mamy pojęcia, dla których rekordów o identyfikatorze A mamy już dopasowanie (1), a dla których rekordów nie (2).

Można to faktycznie rozwiązać na różne sposoby, np. Trzymając tablicę bitów dla tabeli A.
Gdy rekord A zostanie znaleziony jako dopasowanie, zaznaczamy go w tablicy bitów.
Na końcu zagnieżdżonych pętli przechodzimy przez tablicę bitów i wypisujemy i wypisujemy każdy rekord, który nie został zaznaczony.
Jest to oczywiście bardziej skomplikowane niż „naturalna” pętla zagnieżdżona.

W linkowanym artykule nie podoba mi się stwierdzenie, że „algorytm łączenia w pętli zagnieżdżonej nie obsługuje logicznego operatora łączenia w prawym złączu” .

Chociaż istnieją ograniczenia, sformułowania w tym miejscu są nieco mylące. Mam nadzieję, że poniższe informacje wyjaśniają lepiej:

Algorytm zagnieżdżonego łączenia LOP obejmuje dwie tabele (niezależnie od tego, czy tabele podstawowe lub zestawy wyników poprzednich operacji są nieistotne), które są nazywane zewnętrznymi i wewnętrznymi tabelą i są traktowane przez algorytm w inny sposób (tabela „zewnętrzna” jest przeglądana na zewnętrznej pętla i „wewnętrzny” stół w wewnętrznych pętlach).

Powiedzmy, że mamy połączenie:

A (some_type) JOIN B

Algorytm można wykonać jako:

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

lub:

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

Teraz, jeśli ( some_type) jest INNERlub CROSSłączy, to nie ma żadnych ograniczeń, planista może wybrać jeden z dwóch sposobów (z różnymi charakterystykami wydajności, w zależności od wielkości zestawów, rozkładu wartości połączonych kolumn, indeksów itp. Zwykle najmniejszą tabelę wybiera się jako tabelę „zewnętrzną” w algorytmie).

Ale gdy some_typesię LEFTprzyłączyć, to może korzystać tylko z:

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

i nie

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

A ponieważ a RIGHTzawsze można przepisać jako LEFTłączenie, ma to samo ograniczenie, odwrotnie. Do A RIGHT JOIN B(który można przepisać a B LEFT JOIN A) można użyć tylko:

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

a nie na odwrót ^* .

To samo ograniczenie dotyczy lewostronnego półjoina, lewego anty-semijoina, prawego półjoina i prawego anty-semijoina.

Z FULLdrugiej strony złączenie nie może być obsługiwane bezpośrednio za pomocą algorytmu łączenia zagnieżdżonego. Artykuł wyjaśnia bardzo dobrze (jest na końcu), w jaki sposób można przepisać pełne sprzężenie (i jest to przez optymalizator) do połączenia lewego sprzężenia i lewego anty-półjoina, które następnie można zaplanować jako dwie zagnieżdżone pętle (i unia).

^* _{Jak wyjaśnia Dudu Markovitz w swojej odpowiedzi, można by zastosować odwrotny sposób, ale tylko jeśli zmodyfikujemy algorytm łączenia w pętli zagnieżdżonej, aby mieć dodatkową strukturę i dodatkowy krok na końcu.}