NESTED LOOP ou HASH JOIN? Qual a melhor opção para junção de tabelas?

Table Join

O NESTED LOOP e o HASH JOIN não são as únicas opções utilizadas pelo Otimizador do Oracle para fazer a junção de linhas de duas tabelas, mas são as opções mais utilizadas. Neste artigo vamos explorar um pouco como funcionam essas operações e verificar qual delas é a melhor opção para o Otimizador.

Vamos começar respondendo a questão que também é o titulo desse artigo, NESTED LOOP ou HASH JOIN? Qual a melhor opção para o Otimizador realizar uma operação de junção de duas tabelas? A resposta é: depende, sim depende do tamanho das tabelas envolvidas, se existem índices nas colunas utilizadas como chave da junção, da seletividade das colunas do filtro da cláusula WHERE, etc… Para facilitar o entendimento vamos começar com uma breve descrição das duas operações e em seguida vamos fazer simulações para consolidar essa teoria.

Definição NESTED LOOP

Operação utilizada para junção de duas tabelas, nessa operação as linhas da tabela externa (Condutora) são recuperados e para cada linha dessa tabela são recuperadas linhas da tabela interna (Conduzida). Essa operação é utilizada pelo Otimizador quando um pequeno conjunto de linhas de cada uma das tabela são utilizadas na junção das duas tabelas e o método de acesso normalmente utilizado para recuperar as linhas da tabela interna é um índice.

Definição HASH JOIN

Operação utilizada para junção de duas tabelas quando o conjunto de linhas a ser recuperado dessas tabelas é grande, o Otimizador utiliza a tabela que possui o menor conjunto de linhas (BUILD TABLE) para criar um “HASH TABLE” na memoria (in-memory hash) e busca na outra tabela (PROBE TABLE) as linhas que corresponde a função HASH da primeira tabela.

Descrição da simulação

Para compreender melhor essas definições vamos fazer três simulações utilizando o “SAMPLE SCHEMA SH“, na primeira simulação nossa consulta vai selecionar poucas linhas e o Otimizador vai escolher um plano de execução com NESTED LOOP, na segunda simulação vamos alterar o filtro da cláusula WHERE para selecionar uma grande quantidade de linhas e neste caso o Otimizador escolherá a operação HASH JOIN, na ultima simulação vamos utilizar um HINT para forçar o Otimizador utilizar NESTED LOOP para fazer o JOIN da mesma consulta utilizada na segunda simulação e vamos comparar os resultados em termos de desempenho.

Caso tenha alguma dúvida na leitura do plano de execução gerado pelo pacote DBMS_XPLAN consulte a série de artigos que vai ajuda-lo a interpretar essas informações:

1. Como verificar a ordem que as operações são realizadas
2. Como interpretar os valores estatísticos estimados
3. Como interpretar os valores estatísticos coletados durante a execução
4. Como interpretar as seções não estatísticas do plano de execução

 

Junção de tabelas com NESTED LOOP

Nesta simulação nossa consulta vai selecionar 75 linhas, o Otimizador decide que a melhor opção será um NESTED LOOP, pois o JOIN consistirá da leitura de 1 linha da tabela COUNTRIES e 75 linhas da tabela CUSTOMERS.

Title of the document

Ajudo DBAs e analistas de sistema a se destacarem em suas empresas

e obter um crescimento mais acelerado em suas carreiras, quer saber mais click no link abaixo:

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
sh@LAB11 > SELECT * FROM V$VERSION where rownum < 2;

BANNER
--------------------------------------------------------------------------------
Oracle Database 11g Enterprise Edition Release 11.2.0.4.0 - Production

sh@LAB11 > set tab off;
sh@LAB11 > set lines 300 pages 100;
sh@LAB11 >
sh@LAB11 > ALTER SESSION SET statistics_level=ALL;

Session altered.

sh@LAB11 > select /* tst001 */ co.COUNTRY_ID, cu.CUST_FIRST_NAME, cu.CUST_CITY
  2    from countries co,
  3         customers cu
  4   where co.COUNTRY_ID = cu.COUNTRY_ID
  5     and co.COUNTRY_ID = 52787;

COUNTRY_ID CUST_FIRST_NAME      CUST_CITY
---------- -------------------- ------------------------------
     52787 Arnold               Riyadh
     52787 Augustus             Riyadh
     52787 Bertilde             Riyadh
     52787 Bertram              Riyadh
     52787 Beulah               Riyadh
     52787 Byron                Riyadh
     52787 Bryant               Riyadh
     .....
     .....
     .....
     52787 Pavani               Riyadh
     52787 Sydney               Riyadh
     52787 Ramkumar             Riyadh
     52787 Pablo                Riyadh
     52787 Joshua               Riyadh

75 rows selected.

sh@LAB11 > column sql_id new_value m_sql_id
sh@LAB11 > column child_number new_value m_child_no
sh@LAB11 >
sh@LAB11 > SELECT sql_id, child_number
  2    FROM v$sql
  3   WHERE sql_text LIKE '%tst001%'
  4     AND sql_text NOT LIKE '%v$sql%';

SQL_ID        CHILD_NUMBER
------------- ------------
cc7vkhbu2thgt            0

sh@LAB11 >
sh@LAB11 > SELECT *
  2    FROM TABLE (dbms_xplan.display_cursor ('&m_sql_id',&m_child_no,'basic iostats last'));
old   2:   FROM TABLE (dbms_xplan.display_cursor ('&m_sql_id',&m_child_no,'basic iostats last'))
new   2:   FROM TABLE (dbms_xplan.display_cursor ('cc7vkhbu2thgt',         0,'basic iostats last'))

PLAN_TABLE_OUTPUT
-------------------------------------------------------------------------------------------------------------
EXPLAINED SQL STATEMENT:
------------------------
select /* tst001 */ co.COUNTRY_ID, cu.CUST_FIRST_NAME, cu.CUST_CITY
from countries co,        customers cu  where co.COUNTRY_ID =
cu.COUNTRY_ID    and co.COUNTRY_ID = :"SYS_B_0"

Plan hash value: 763797669

---------------------------------------------------------------------------------------------
| Id  | Operation          | Name         | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
---------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |              |      1 |        |     75 |00:00:00.01 |    1462 |
|   1 |  NESTED LOOPS      |              |      1 |     75 |     75 |00:00:00.01 |    1462 |
|*  2 |   INDEX UNIQUE SCAN| COUNTRIES_PK |      1 |      1 |      1 |00:00:00.01 |       1 |
|*  3 |   TABLE ACCESS FULL| CUSTOMERS    |      1 |     75 |     75 |00:00:00.01 |    1461 |
---------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("CO"."COUNTRY_ID"=:SYS_B_0)
   3 - filter("CU"."COUNTRY_ID"=:SYS_B_0)


23 rows selected.

sh@LAB11 >

 

Junção de tabelas com HASH JOIN

Nesta segunda simulação vamos filtrar três países no campo COUNTRY_ID da cláusula WHERE o que vai aumentar nossa seleção de linhas para aproximadamente 34 mil linhas, com essa estimativa o Otimizador decide que a melhor opção para realizar esta junção é a operação HASH JOIN.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
sh@LAB11 > select /* tst002 */ co.COUNTRY_ID, cu.CUST_FIRST_NAME, cu.CUST_CITY
  2    from countries co,
  3         customers cu
  4   where co.COUNTRY_ID = cu.COUNTRY_ID
  5     and co.COUNTRY_ID in (52770,52776,52790);

COUNTRY_ID CUST_FIRST_NAME      CUST_CITY
---------- -------------------- ------------------------------
     52770 Abigail              Ede
     52770 Abigail              Hoofddorp
     52770 Abigail              Schimmert
     52770 Abigail              Scheveningen
     52770 Abigail              Haarlem
     52770 Abigail              Lelystad
     52776 Abner                Murnau
     52790 Abner                Los Angeles
     52776 Abner                Stuttgart
     52790 Abner                Montara
     .....
     .....
     .....
     52790 Jordan               Molino
     52790 Sydney               Evinston
     52790 Boriana              Orlinda
     52790 Jade                 Norman
     52790 Joshua               Cleveland
     52790 Andrew               Duncan

34473 rows selected.

sh@LAB11 >
sh@LAB11 > column sql_id new_value m_sql_id
sh@LAB11 > column child_number new_value m_child_no
sh@LAB11 >
sh@LAB11 > SELECT sql_id, child_number
  2    FROM v$sql
  3   WHERE sql_text LIKE '%tst002%'
  4     AND sql_text NOT LIKE '%v$sql%';

SQL_ID        CHILD_NUMBER
------------- ------------
9z5f0k26an9vy            0

sh@LAB11 >
sh@LAB11 > SELECT *
  2    FROM TABLE (dbms_xplan.display_cursor ('&m_sql_id',&m_child_no,'basic iostats last'));
old   2:   FROM TABLE (dbms_xplan.display_cursor ('&m_sql_id',&m_child_no,'basic iostats last'))
new   2:   FROM TABLE (dbms_xplan.display_cursor ('9z5f0k26an9vy',         0,'basic iostats last'))

PLAN_TABLE_OUTPUT
-------------------------------------------------------------------------------------------------------------------------------------
EXPLAINED SQL STATEMENT:
------------------------
select /* tst002 */ co.COUNTRY_ID, cu.CUST_FIRST_NAME, cu.CUST_CITY
from countries co,        customers cu  where co.COUNTRY_ID =
cu.COUNTRY_ID    and co.COUNTRY_ID in (:"SYS_B_0",:"SYS_B_1",:"SYS_B_2")

Plan hash value: 1865765122

----------------------------------------------------------------------------------------------
| Id  | Operation           | Name         | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
----------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |              |      1 |        |  34473 |00:00:00.08 |    3697 |
|*  1 |  HASH JOIN          |              |      1 |   5443 |  34473 |00:00:00.08 |    3697 |
|   2 |   INLIST ITERATOR   |              |      1 |        |      3 |00:00:00.01 |       2 |
|*  3 |    INDEX UNIQUE SCAN| COUNTRIES_PK |      3 |      3 |      3 |00:00:00.01 |       2 |
|*  4 |   TABLE ACCESS FULL | CUSTOMERS    |      1 |  34473 |  34473 |00:00:00.05 |    3695 |
----------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - access("CO"."COUNTRY_ID"="CU"."COUNTRY_ID")
   3 - access(("CO"."COUNTRY_ID"=:SYS_B_0 OR "CO"."COUNTRY_ID"=:SYS_B_1 OR
              "CO"."COUNTRY_ID"=:SYS_B_2))
   4 - filter(("CU"."COUNTRY_ID"=:SYS_B_0 OR "CU"."COUNTRY_ID"=:SYS_B_1 OR
              "CU"."COUNTRY_ID"=:SYS_B_2))


27 rows selected.

sh@LAB11 >

 

Junção de tabelas usando HINT

Nas duas primeiras simulações observamos que o Otimizador escolheu o tipo de operação JOIN baseado nas definições de cada uma delas, mas será que essas escolhas foram realmente as melhores em termos de desempenho? Vamos fazer uma terceira simulação utilizando a segunda consulta, mas desta vez vamos utilizar um HINT para forçar a utilização de uma operação de JOIN diferente da escolhida pelo Otimizando na segunda simulação e comparar o desempenho dessa consulta com sua antecessora.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
sh@LAB11 > select /*+ USE_NL(co cu) */ co.COUNTRY_ID, cu.CUST_FIRST_NAME, cu.CUST_CITY
  2    from countries co,
  3         customers cu
  4   where co.COUNTRY_ID = cu.COUNTRY_ID
  5     and co.COUNTRY_ID in (52770,52776,52790);

COUNTRY_ID CUST_FIRST_NAME      CUST_CITY
---------- -------------------- ------------------------------
     52770 Abigail              Ede
     52770 Abigail              Hoofddorp
     52770 Abigail              Schimmert
     52770 Abigail              Scheveningen
     52770 Abigail              Haarlem
     52770 Abigail              Lelystad
     52776 Abner                Murnau
     52790 Abner                Los Angeles
     52776 Abner                Stuttgart
     52790 Abner                Montara
     52776 Abner                Neuss
     52776 Abner                Schwaebisch Gmuend
     ...
     ...
     ...
     52790 Boriana              Orlinda
     52790 Jade                 Norman
     52790 Joshua               Cleveland
     52790 Andrew               Duncan

34473 rows selected.

sh@LAB11 >
sh@LAB11 > column sql_id new_value m_sql_id
sh@LAB11 > column child_number new_value m_child_no
sh@LAB11 >
sh@LAB11 > SELECT sql_id, child_number
  2    FROM v$sql
  3   WHERE sql_text LIKE '%USE_NL(co cu)%'
  4     AND sql_text NOT LIKE '%v$sql%';

SQL_ID        CHILD_NUMBER
------------- ------------
69sh8pmxx610j            0

sh@LAB11 >
sh@LAB11 > SELECT *
  2    FROM TABLE (dbms_xplan.display_cursor ('&m_sql_id',&m_child_no,'basic iostats last'));
old   2:   FROM TABLE (dbms_xplan.display_cursor ('&m_sql_id',&m_child_no,'basic iostats last'))
new   2:   FROM TABLE (dbms_xplan.display_cursor ('69sh8pmxx610j',         0,'basic iostats last'))

PLAN_TABLE_OUTPUT
-----------------------------------------------------------------------------------------------------------------------------
EXPLAINED SQL STATEMENT:
------------------------
select /*+ USE_NL(co cu) */ co.COUNTRY_ID, cu.CUST_FIRST_NAME,
cu.CUST_CITY   from countries co,        customers cu  where
co.COUNTRY_ID = cu.COUNTRY_ID    and co.COUNTRY_ID in
(:"SYS_B_0",:"SYS_B_1",:"SYS_B_2")

Plan hash value: 1539906852

---------------------------------------------------------------------------------------------
| Id  | Operation          | Name         | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
---------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |              |      1 |        |  34473 |00:00:00.13 |    5998 |
|   1 |  NESTED LOOPS      |              |      1 |   5443 |  34473 |00:00:00.13 |    5998 |
|*  2 |   TABLE ACCESS FULL| CUSTOMERS    |      1 |  34473 |  34473 |00:00:00.06 |    3696 |
|*  3 |   INDEX UNIQUE SCAN| COUNTRIES_PK |  34473 |      1 |  34473 |00:00:00.04 |    2302 |
---------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - filter(("CU"."COUNTRY_ID"=:SYS_B_0 OR "CU"."COUNTRY_ID"=:SYS_B_1 OR
              "CU"."COUNTRY_ID"=:SYS_B_2))
   3 - access("CO"."COUNTRY_ID"="CU"."COUNTRY_ID")
       filter(("CO"."COUNTRY_ID"=:SYS_B_0 OR "CO"."COUNTRY_ID"=:SYS_B_1 OR
              "CO"."COUNTRY_ID"=:SYS_B_2))


27 rows selected.

sh@LAB11 >

 

Comparando os planos de execução da segunda e terceira simulação podemos observar que a terceira simulação teve um desempenho inferior a segunda, o tempo de resposta aumentou de 8 para 13 centésimos de segundos e o número de buffers lidos aumento de 3697 para 5998, parece pouco mas se essa consulta fizer parte de uma aplicação que precisa executá-la milhões de vezes durante o dia a diferença passa ser significativa. O plano de execução da segunda simulação teve um desempenho melhor e a operação de junção foi uma escolha acertada do Otimizador.

Conclusão

Como pudemos observar em nossas simulações o Otimizador é muito competente na escolha do tipo de operação JOIN a ser utilizada na junção de duas tabelas, mas a escolha dele é feita baseada em objetos existentes no banco de dados naquele momento, em determinadas situações a escolha feita pelo Otimizador pode não ser a melhor devido a falta de um índice, estatísticas insuficientes ou desatualizadas, incompatibilidade de tipos de coluna de dados, etc… Nesse momento podemos aplicar os conceitos abordados neste artigo para analisar o plano de execução, identificar as causas que levaram o Otimizador a tomar uma decisão incorreta e corrigir este problema para melhorar o desempenho da instrução SQL.

Referências

http://docs.oracle.com/cd/E11882_01/server.112/e41573/optimops.htm#PFGRF94639

 
 
Promo-D75L

video-02
 
 
 
 
 
 
 
 
 
 
 
 
 
 

4 comments

  • Vinicius Calixto

    ótimo artigo

  • Jorge Luiz Vaz

    A forma como o otimizador escolhe o caminho depende do tipo de geração de estatística que fazemos ? Exemplificando !
    Seria interessante rodarmos uma estatística geral periodicamente com Histogramas para toda uma base de dados ?
    Digo isso, pois o Oracle roda estatísticas de forma frequente sem que haja qualquer interferência, e acredito que a utilização de Histogramas para análise de determinadas tabelas é um caso muito particular.
    O exemplo é muito interessante e sempre gosto de suas colocações, apesar de “eu” estar fugindo ao assunto.
    O fato que me deixa até certo ponto em dúvidas é dizer que uma tabela é grande, o que para mim é um situação complicada e relativa.
    Como mensurar uma tabela grande ? Seria o fato de ela ter “X” blocos, ou por exemplo “X” linhas ?
    Eu poderia ter uma tabela de milhões de registros com uma quantidade de blocos infinitamente inferior a uma outra que tivesse uma quantidade de linhas menor, pela definição de quantidade de campos.
    Quero chegar na sua análise de NESTED LOOPS e HASH JOIN, que utiliza uma tabela menor para ser a BUILD TABLE. Na prática nunca observei esse detalhe, mas já li artigos sobe o fato. A escolha do otimizador parece ser sempre uma escolha “sensata”, e o HINT, pode ser uma alternativa, que em alguns casos influencia e melhora a performance, mas, eu acho que em um projeto bem ajustado e customizado, diminuiria um pouco a preocupação de ajustes de SQLs.
    Acredito que isso não acontece na grande maioria das Empresas, principalmente na que eu trabalho, em que os SQLs, são escritos de maneira a atender a “situação momento”, e fica difícil uma análise melhor, pois as coisas são atendidas por “demanda” . Nada foi customizado e a bomba explode no Banco.

    • Olá Jorge,

      Muito boas as suas observações, concordo plenamente que se houvesse um melhor planejamento no modelo de dados das aplicações dificilmente teriamos problemas de performance nas instruções SQL, mas sabemos que na prática isso é muito raro.

      Um forte abraço,
      Valter Aquino

Deixe um comentário

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *