Nested loops, Hash join e Sort Merge joins

Traduzi um ótimo post explicando os tipos operações que um join pode ter no Oracle. Assim podemos ter uma notação de quando devemos mudar os planos do Oracle para agir da forma que queremos, mas claro, sabendo o que está fazendo!

Nested loop (loop over loop)

Neste algoritmo, um loop externo é formado que consiste de poucas entradas e então para cada entrada, um loop interno é processado.

Ex:

SELECT tab1.*, tab2.* FROM tabl, tab2 WHERE tabl.col1 = tab2.col2;

É processado como:

For i in (select * from tab1) loop
  For j in (select * from tab2 where col2=i.col1) loop
    Display results;
  End loop;
End loop;

Os passos involvidos em fazer nested loop são:

a) Identificar a tabela (condutora) externa

b) Designar a tabela (conduzida) interna para a tabela externa.

c) Para cada linha da tabela externa, acessar linhas da tabela interna.

No plano de execução ele é visto como isto:

NESTED LOOPS
outer_loop
inner_loop

Quando o otimizador usa nested loops?

O otimizador usa nested loop quando nós estamos fazendo join de tabelas contendo pequeno número de linhas com uma condição que conduza eficientemente. É importante ter um índice na coluna da tabela de inner join como esta tabela é verificada várias vezes por um novo valor da tabela externa.

O otimizador pode não usar nested loop no caso:
1. Nenhuma das linhas de ambas as tabelas é bastante grande
2. A query interna sempre resulta no mesmo conjunto de registros
3. O caminho de acesso da tabela interna é independente dos dados vindo da tabela externa.

Note: Você verá mais uso de nested loop quando usando o modo de otimização FIRST_ROWS, como ele é feito para mostrar resultados instantâneamente para o usuário assim que é obtido. Não há necessidade de pegar qualquer dado antes dele ser retornado para o usuário. No caso do hash join, é necessário e é explicado abaixo.

Hash join

Hash joins são usados quando fazendo join de tabelas grandes. O otimizador usa a menor das duas tabelas para criar um hash table na memória e scaneia a maior tabela e compara o valor de hash (das linhas da tabela maior) com esta hash table para encontrar as linhas do join.

O algoritmo do hash join é dividido em duas partes
1. Construir um hash table em memória da menor das duas tabelas.
2. Verifica este hash table com o valor de hash de cada linha da segunda tabela.

Em poucas palavras, ele funciona como

Fase de construção

For each row RW1 in small (left/build) table loop
  Calculate hash value on RW1 join key
  Insert RW1 in appropriate hash bucket.
End loop;

Fase da verificação

For each row RW2 in big (right/probe) table loop
  Calculate the hash value on RW2 join key
  For each row RW1 in hash table loop
    If RW1 joins with RW2
      Return RW1, RW2
  End loop;
End loop;

Quando o otimizador usa hash join?

O otimizador usa hash join quando estamos fazendo join de grandes tabelas ou grandes frações de pequenas tabelas.

Diferente de nested loop, o resultado do hash join não é instântaneo como a junção feita com hash é bloqueada na fase da construção da hash table.

Note: Você pode ver mais hash joins usados com o otimizador no modo ALL_ROWS, porque ele funciona mostrando resultados depois que todas as linhas de no mínimo uma das tabelas tenha todo o hash na hash table.

Sort merge join

Sort merge join é usado para juntar duas fontes de dados independentes. Eles executam melhor que nested loop quando o volume de dados é grande nas duas tabelas, mas não é bom como hash joins em geral.

Eles trabalham melhor que hash join quando a condição do join das colunas estão já ordenadas ou quando ordenação não é requerida.

A operação completa é feita em duas partes:

Sort join operation

get first row RW1 from input1
get first row RW2 from input2.

Merge join operation

while not at the end of either input loop
  if RW1 joins with RW2
    get next row R2 from input 2
    return (RW1, RW2)
  else if RW1 < style="">
    get next row RW1 from input 1
  else
    get next row RW2 from input 2
end loop

Note: Se os dados já estão ordenados, o primeiro passo é evitado.

Um importante ponto para entender é, diferente de nested loop onde a tabela (interna) conduzida é lida muitas vezes como a tabela externa, no sort merge join cada uma das tabelas envolvidas são acessadas no máximo uma vez. Então elas conseguem ser melhor que nested loop quando o conjunto de dados é grande.

Quando o otimizador usa Sort merge join?

a) Quando a condição do join não é uma igualdade (como <, <=, >=). Isto é porque hah join não pode ser usado para condições de não-igualdade e se o conjunto de dados é grande, nested loop definitivamente não é uma opção.

b) Se a ordenação é de qualquer forma requerida devido algum outro atributo (além de join) como "order by", o otimizador prefere sort merge join a hash join como ele é barato.

Note: Sort merge join pode ser visto com ambos hints do otimizador ALL_ROWS e FIRST_ROWS porque ele funciona primeiramente ordenando ambas as fontes de dados e então começa a retornar resultados. Então se o conjunto de dados é grande e você tem FIRST_ROWS como um hint, o otimizador pode preferir sort merge join a nested loop, por causa da massa de dados. E se você tem ALL_ROWS como hint e se qualquer condição não-igual é usada na query, o otimizador pode usar sort-merge join a hash join.

Fonte: http://oracle-online-help.blogspot.com/2007/03/nested-loops-hash-join-an...

Há outros posts fera no link do blog acima, vale a pena conferir. ;)

muito bom , nunca vi nada do

muito bom , nunca vi nada do tipo ;-)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Post new comment

The content of this field is kept private and will not be shown publicly.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.

More information about formatting options