Mengapa loop bersarang bergabung hanya mendukung gabungan kiri?

Dalam blog Craig Freedman, Nested Loops Join , ia menjelaskan mengapa loop nested bergabung tidak dapat mendukung join luar kanan:

Masalahnya adalah kita memindai tabel bagian dalam beberapa kali - satu kali untuk setiap baris gabungan luar. Kami mungkin menemukan baris dalam yang sama beberapa kali selama beberapa pemindaian ini. Pada titik mana kita dapat menyimpulkan bahwa barisan dalam tertentu belum atau tidak mau bergabung?

Dapatkah seseorang tolong jelaskan ini dengan cara yang sangat sederhana dan mendidik?

Apakah ini berarti bahwa loop dimulai dengan tabel luar ( R1) dan memindai bagian dalam ( R2)?

Saya mengerti bahwa untuk R1nilai yang tidak bergabung R2, itu harus diganti dengan NULLsehingga set hasil menjadi ( NULL, R2). Bagi saya tampaknya tidak mungkin untuk mengembalikan R2nilai ketika R1tidak bergabung, karena alasan itu tidak dapat mengetahui R2nilai yang akan dikembalikan. Tapi bukan itu yang dijelaskan. Atau itu?

SQL Server sebenarnya tidak mengoptimalkan (dan sering menggantikan) RIGHT JOINdengan LEFT JOIN, tapi pertanyaannya adalah untuk menjelaskan mengapa hal itu secara teknis tidak mungkin untuk NESTED LOOPS JOINmenggunakan / dukungan RIGHT JOINlogika.

Masalah utama di sini adalah implementasi gabungan luar, menggunakan loop bersarang, dengan cara teknis yang berlawanan dengan cara logis , di mana tabel bagian dalam diakses melalui loop luar dan tabel luar diakses melalui loop dalam .

Diberikan tabel A dan B, mari kita implementasikan A LEFT JOIN B.

A
--
1
2

B
_
1
3

Pertama, mari kita lakukan dengan cara " alami ".

Kami beralih melalui A.
Kami mengakses catatan 1.
Kami beralih melalui B.
Kami menemukan catatan 1 dalam B dan output 1-1 .

Kami terus mengulangi melalui A.
Kami mengakses catatan 2.
Kami beralih melalui B.
Kami tidak menemukan kecocokan dalam B.
Kami menampilkan 2-null .

Sekarang, mari kita lakukan dengan cara yang " berlawanan ".

Kami beralih melalui B.
Kami mengakses catatan 1.
Kami beralih melalui A.
Kami menemukan catatan 1 di A dan output 1-1 .

Kami terus mengulangi melalui B.
Kami mengakses catatan 3.
Kami beralih melalui A.
Kami tidak menemukan kecocokan di A.

Sekarang ingat bahwa itu adalah A LEFT JOIN B, yang berarti bahwa selain 1-1 kita harus menghasilkan 2-null .
Masalahnya adalah bahwa pada saat itu, kita tidak tahu untuk yang mana merekam id A kita sudah memiliki kecocokan (1) dan untuk catatan mana kita tidak (2).

Ini sebenarnya dapat diselesaikan dengan berbagai cara misalnya dengan memegang array bit untuk tabel A.
Ketika sebuah record A ditemukan sebagai kecocokan, kita menandainya dalam array bit.
Pada akhir loop bersarang kita akan melalui bit array dan output dan output setiap record yang tidak ditandai.
Ini jelas lebih rumit daripada loop bersarang "alami".

Apa yang saya tidak suka dalam artikel tertaut adalah pernyataan bahwa "algoritma join loop bersarang tidak mendukung operator join logis dari join kanan" .

Meskipun ada batasan, kata-kata pada saat ini agak membingungkan. Saya harap yang berikut ini menjelaskan hal-hal yang lebih baik:

Algoritma lop join bersarang melibatkan dua tabel (apakah tabel dasar atau set hasil dari operasi sebelumnya tidak relevan) yang diberi nama tabel luar dan dalam dan mereka diperlakukan dengan cara yang berbeda oleh algoritma (tabel "luar" dilintasi di luar loop dan tabel "inner" di loop dalam).

Jadi, katakanlah kita telah bergabung:

A (some_type) JOIN B

Algoritme dapat dijalankan sebagai:

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

atau:

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

Sekarang, jika ( some_type) adalah INNERatau CROSSbergabung, maka tidak ada batasan, perencana dapat memilih antara salah satu dari dua cara (dengan karakteristik kinerja yang berbeda, tergantung pada ukuran set, distribusi nilai dari kolom yang bergabung, indeks, dll. Biasanya tabel terkecil akan dipilih sebagai tabel "luar" dalam algoritma).

Tapi ketika some_typeyang LEFTbergabung, hanya dapat menggunakan:

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

dan tidak

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

Dan karena a RIGHTdapat selalu ditulis ulang sebagai LEFTgabungan, ia memiliki batasan yang sama, secara terbalik. Untuk A RIGHT JOIN B(yang dapat ditulis ulang a B LEFT JOIN A) hanya dapat menggunakan:

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

dan bukan sebaliknya ^* .

Batasan yang sama berlaku untuk kiri-semijoin, kiri-anti-semijoin, kanan-semijoin dan kanan-anti-semijoin.

The FULLbergabung di sisi lain tidak bisa langsung ditangani dengan loop bersarang bergabung algoritma. Artikel ini menjelaskan dengan sangat baik (sudah mendekati akhir) bagaimana gabungan penuh dapat ditulis ulang (dan oleh optimizer) ke gabungan kiri bergabung dan anti-semijoin kiri yang kemudian dapat direncanakan sebagai dua loop bersarang (dan Persatuan).

^* _{Sebagai Dudu Markovitz menjelaskan dalam jawabannya, cara sebaliknya akan dapat digunakan tetapi hanya jika kita memodifikasi bersarang loop bergabung algoritma untuk memiliki struktur tambahan dan langkah tambahan pada akhirnya.}