¿Por qué la unión de bucles anidados solo admite combinaciones izquierdas?

En el blog de Craig Freedman, Nested Loops Join , explica por qué la unión de bucles anidados no puede admitir una unión externa derecha:

El problema es que escaneamos la tabla interna varias veces, una vez por cada fila de la unión externa. Podemos encontrar las mismas filas internas varias veces durante estos escaneos múltiples. ¿En qué punto podemos concluir que una fila interna particular no se ha unido o no se unirá?

¿Alguien puede explicar esto de una manera realmente simple y educativa?

¿Significa que el bucle comienza con la tabla externa ( R1) y escanea la interna ( R2)?

Entiendo que para un R1valor que no se une con R2, debe reemplazarse con un NULLpara que el conjunto de resultados se convierta en ( NULL, R2). Para mí, parece imposible devolver un R2valor cuando R1no se une, por la razón de que no puede saber qué R2valor devolver. Pero esa no es la forma en que se explica. ¿O es eso?

De hecho, SQL Server optimiza (y a menudo reemplaza) RIGHT JOINcon LEFT JOIN, pero la pregunta es explicar por qué es técnicamente imposible para una lógica de NESTED LOOPS JOINuso / soporte RIGHT JOIN.

El problema principal aquí es la implementación de una unión externa, usando bucles anidados, de una manera técnica que es opuesta a la lógica , donde se accede a la tabla interna a través del bucle externo y se accede a la tabla externa a través del bucle interno .

Dadas las tablas A y B, implementemos A LEFT JOIN B.

A
--
1
2

B
_
1
3

Primero, hagámoslo de manera " natural ".

Iteramos a través de A. Accedemos al
registro 1. I
iteramos a través de B.
Encontramos el registro 1 en B y la salida 1-1 .

Seguimos iterando a través de A. Accedemos al
registro 2.
iteramos a través de B.
No encontramos ninguna coincidencia en B.
Generamos 2 nulos .

Ahora, hagámoslo de la manera " opuesta ".

Iteramos a través de B. Accedemos al
registro 1.
Iteramos a través de A.
Encontramos el registro 1 en A y la salida 1-1 .

Seguimos iterando a través de B. Accedemos al
registro 3.
iteramos a través de A.
No encontramos ninguna coincidencia en A.

Ahora recuerde que sí A LEFT JOIN B, lo que significa que además de 1-1 deberíamos generar 2 nulos .
El problema es que, en ese momento, no tenemos idea de qué identificación de registros A ya tenemos una coincidencia (1) y para qué registros no tenemos (2).

En realidad, esto puede resolverse de varias maneras, por ejemplo, manteniendo una matriz de bits para la tabla A.
Cuando se encuentra un registro A como coincidente, lo marcamos en la matriz de bits.
Al final de los bucles anidados, revisamos la matriz de bits y enviamos y sacamos cualquier registro que no haya sido marcado.
Obviamente, esto es más complicado que el bucle anidado "natural".

Lo que no me gusta en el artículo vinculado es la afirmación de que "el algoritmo de unión de bucle anidado no admite el operador de unión lógica de la unión derecha" .

Si bien existe una limitación, la redacción en este punto es un poco confusa. Espero que lo siguiente explique mejor las cosas:

El algoritmo de unión lop anidada involucra dos tablas (si las tablas base o los conjuntos de resultados de operaciones anteriores son irrelevantes) que se denominan tabla externa e interna y el algoritmo las trata de manera diferente (la tabla "externa" se recorre en la parte externa bucle y la tabla "interna" en los bucles internos).

Entonces, digamos que tenemos una unión:

A (some_type) JOIN B

El algoritmo se puede ejecutar como:

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

o:

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

Ahora, si ( some_type) es INNERo CROSSunirse, entonces no hay limitación, el planificador puede elegir entre cualquiera de las dos formas (con diferentes características de rendimiento, dependiendo del tamaño de los conjuntos, distribución de valores de las columnas unidas, índices, etc. Por lo general, se elegirá la tabla más pequeña para que sea la tabla "externa" en el algoritmo).

Pero cuando some_typese LEFTune, solo puede usar:

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

y no

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

Y dado que a RIGHTsiempre se puede reescribir como una LEFTcombinación, tiene la misma limitación, a la inversa. Para A RIGHT JOIN B(que puede reescribirse a B LEFT JOIN A) solo puede usar:

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

y no al revés ^* .

La misma limitación se aplica para left-semijoin, left-anti-semijoin, right-semijoin y right-semi-semijoin.

La FULLunión, por otro lado, no se puede manejar directamente con un algoritmo de unión de bucle anidado. El artículo explica muy bien (está cerca del final) cómo se puede reescribir una unión completa (y es por el optimizador) a una unión de una unión izquierda y una anti-semi-unión izquierda que luego podrían planificarse como dos bucles anidados (y un Unión).

^* _{Como Dudu Markovitz explica en su respuesta, la forma inversa podría usarse, pero solo si modificamos el algoritmo de unión de bucle anidado para tener una estructura adicional y un paso adicional al final.}