Por que a junção de loops aninhados suporta apenas junções à esquerda?

O que eu não gosto no artigo vinculado é a declaração de que "algoritmo de junção de loop aninhado não suporta o operador de junção lógica da junção à direita" .

Embora haja uma limitação, a redação neste momento é um pouco confusa. Espero que o seguinte explique melhor as coisas:

O algoritmo de lop join aninhado envolve duas tabelas (se tabelas base ou conjuntos de resultados de operações anteriores são irrelevantes) que são nomeadas de tabela externa e interna e são tratadas de maneira diferente pelo algoritmo (a tabela "externa" é atravessada na parte externa loop e a tabela "interna" nos loops internos).

Então, digamos que temos uma junção:

A (some_type) JOIN B

O algoritmo pode ser executado como:

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

ou:

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

Agora, se ( some_type) for INNERou CROSSjoin, então não há limitação, o planejador pode escolher entre uma das duas formas (com diferentes características de desempenho, dependendo do tamanho dos conjuntos, distribuição de valores das colunas unidas, índices, etc.) . Normalmente, a menor tabela será escolhida para ser a tabela "externa" do algoritmo).

Mas quando some_typeé LEFTjoin, só pode usar:

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

e não

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

E como a RIGHTsempre pode ser reescrito como uma LEFTjunção, ele tem a mesma limitação, ao contrário. For A RIGHT JOIN B(que pode ser reescrito a B LEFT JOIN A) só pode usar:

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

e não o contrário ^* .

A mesma limitação se aplica para semijoin esquerda, anti semijoin esquerda, semijoin direita e anti semijoin direita.

A FULLjunção, por outro lado, não pode ser tratada diretamente com um algoritmo de junção de loop aninhado. O artigo explica muito bem (está perto do fim) como uma junção completa pode ser reescrita (e é feita pelo otimizador) para uma união de uma junção esquerda e uma anti-semijoin esquerda que então pode ser planejada como dois loops aninhados (e um União).

^* _{Como Dudu Markovitz explica em sua resposta, o caminho inverso poderia ser usado, mas apenas se modificássemos o algoritmo de junção de loop aninhado para ter uma estrutura extra e um passo extra no final.}

A questão principal aqui é a implementação de uma junção externa, usando laços aninhados, de forma técnica oposta à forma lógica , onde a tabela interna é acessada pelo laço externo e a tabela externa é acessada pelo laço interno .

Dadas as tabelas A e B, vamos implementar A LEFT JOIN B.

A
--
1
2

B
_
1
3

Primeiro, vamos fazê-lo da maneira " natural ".

Nós iteramos através de A.
Nós acessamos o registro 1.
Nós iteramos através de B.
Nós encontramos o registro 1 em B e produzimos 1-1 .

Continuamos iterando através de A. Acessamos o
registro 2.
Nós iteramos através de B.
Não encontramos nenhuma correspondência em B.
Produzimos 2-null .

Agora, vamos fazer da maneira " oposta ".

Iteramos por B. Acessamos o
registro 1.
Iteramos por A.
Encontramos o registro 1 em A e produzimos 1-1 .

Continuamos iterando por B. Acessamos o
registro 3.
Iteramos por A.
Não encontramos nenhuma correspondência em A.

Agora lembre-se que era A LEFT JOIN B, o que significa que além de 1-1 devemos produzir 2-null .
O problema é que, nesse ponto, não temos ideia para quais registros id A já temos uma correspondência (1) e para quais registros não temos (2).

Isso pode ser resolvido de várias maneiras, por exemplo, mantendo uma matriz de bits para a tabela A.
Quando um registro A é encontrado como uma correspondência, nós o marcamos na matriz de bits.
No final dos loops aninhados, estamos passando pela matriz de bits e produzimos e produzimos qualquer registro que não tenha sido marcado.
Isso é obviamente mais complicado do que o loop aninhado "natural".