Algoritmos de junção: loop aninhado, hash e mesclagem

Você já conhece INNER JOIN como sintaxe. Em entrevistas para cargos seniores, os entrevistadores perguntam como o banco de dados executa fisicamente uma junção. Existem três algoritmos:

• Laço aninhado
• Junção por dispersão
• Junção por mesclagem (mesclagem por ordenação)

O tipo lógico de junção (INNER, LEFT) é independente do algoritmo. O planejador escolhe o algoritmo com base no tamanho das tabelas, nos índices e na ordem de ordenação. Saber quando cada um é mais vantajoso é o cerne desta lição.

O laço aninhado é o mais simples: para cada linha da tabela externa, percorra a tabela interna em busca de correspondências. Em pseudocódigo, são dois laços, um dentro do outro.

De forma ingênua, isso é O(externa * interna), o que é péssimo para tabelas grandes. Mas ele se torna excelente quando o lado interno tem um índice na chave de junção: cada linha externa aciona uma busca barata no índice, em vez de uma varredura completa da tabela interna.

É o método preferido do planejador quando a tabela externa é pequena e a coluna de junção interna possui um índice.

O indício de um laço aninhado é loops no nó interno. O exemplo mostra loops=3 porque o lado externo produziu 3 linhas; portanto, a varredura do índice interno foi executada 3 vezes.

O perigo aparece quando o lado externo é grande. Se ele produzir 2 milhões de linhas, o lado interno será executado 2 milhões de vezes. Até mesmo uma busca rápida de 0,01 ms se transforma em 20 segundos.

Em entrevistas, sinalize qualquer laço aninhado em que loops seja grande sobre uma tabela interna sem um bom índice: essa é a consulta lenta.

A junção por dispersão lida bem com tabelas grandes e não ordenadas. Ela é executada em duas fases:

• Construção: leia a tabela menor e carregue-a em uma tabela de dispersão na memória, indexada pela coluna de junção.
• Sondagem: percorra a tabela maior; para cada linha, calcule a dispersão da chave de junção e procure-a na tabela de dispersão.

Cada tabela é lida apenas uma vez, resultando aproximadamente em O(externa + interna). Não são necessários índices nem entradas ordenadas, e é por isso que ela predomina em junções analíticas grandes baseadas em condições de igualdade.

Há dois pontos que você precisa mencionar sobre as junções por dispersão:

• Elas funcionam apenas para condições de junção por igualdade (a.id = b.id). Uma condição de intervalo, como a.x < b.y, não pode usar uma junção por dispersão.
• O lado de construção precisa caber na memória de trabalho. Se não couber, o Postgres grava lotes no disco (você verá Batches: > 1 e uso de disco), o que torna a junção muito mais lenta.

Portanto, uma junção por dispersão com um lado de construção enorme e pouca memória de trabalho é um erro real de desempenho que deve ser apontado.

A junção por mesclagem (mesclagem por ordenação) exige que ambas as entradas estejam ordenadas pela chave de junção. Em seguida, percorre as duas em paralelo, como na mesclagem de duas listas ordenadas, avançando o ponteiro que estiver atrás.

Ela é eficiente quando as entradas já estão ordenadas, por exemplo, quando vêm diretamente de um índice na ordem da chave, pois nesse caso não é necessária uma etapa de ordenação. Ela também oferece suporte a junções por intervalo e por desigualdade, ao contrário da junção por dispersão.

Se as entradas não estiverem pré-ordenadas, o planejador adicionará nós Sort explícitos, e o custo dessa ordenação poderá tornar a junção por dispersão mais barata.

Memorize quando cada algoritmo é mais vantajoso:

• Laço aninhado: tabela externa pequena e chave de junção interna indexada; também é a única opção para junções por desigualdade sem entrada ordenada.
• Junção por dispersão: tabelas grandes e não ordenadas unidas por igualdade; não são necessários índices.
• Junção por mesclagem: ambas as entradas já estão ordenadas pela chave, geralmente por meio de índices, ou para junções por intervalo; é excelente para conjuntos muito grandes e pré-ordenados.

O planejador estima o custo de cada opção e escolhe a mais barata com base em suas estimativas de linhas.

O uso de recursos varia muito, e os entrevistadores exploram esse ponto:

• Laço aninhado: usa pouca memória; o custo é dominado pelas buscas internas repetidas.
• Junção por dispersão: precisa de memória para a tabela de dispersão; transborda para o disco se ficar grande demais.
• Junção por mesclagem: é barata para mesclar, mas cara se precisar ordenar primeiro; as ordenações também usam work_mem e podem transbordar para o disco.

Assim, aumentar work_mem pode transformar uma dispersão ou ordenação lenta, que transborda para o disco, em uma operação executada na memória: uma resposta concreta de otimização.

Um cenário clássico: uma consulta era rápida no desenvolvimento e lenta na produção. O plano mostra um laço aninhado com loops=3000000.

O planejador subestimou a quantidade de linhas externas (as estatísticas desatualizadas indicavam 3 linhas, mas a realidade era de 3 milhões), por isso escolheu um laço aninhado. Com estatísticas precisas, teria escolhido uma junção por dispersão.

Sua resposta na entrevista: execute ANALYZE para que a estimativa fique correta; então o planejador mudará para uma junção por dispersão, e a consulta ficará muito mais rápida.

Normalmente, você não deve forçar algoritmos, mas pode fazer isso em testes para compará-los. O Postgres oferece opções de ativação e desativação para cada método:

SET enable_nestloop = off; e opções semelhantes para enable_hashjoin e enable_mergejoin. Desative uma delas, execute novamente EXPLAIN ANALYZE e observe se a alternativa é realmente mais rápida.

As correções adequadas continuam sendo: estatísticas atualizadas, os índices corretos, work_mem suficiente e predicados seletivos. Forçar algoritmos serve apenas para diagnóstico.

Considere uma carga de trabalho analítica que une duas grandes tabelas de fatos e dimensões por um identificador:

• Se a dimensão couber na memória, espere uma junção por dispersão, geralmente a melhor opção.
• Se ambas chegarem ordenadas por meio de índices, uma junção por mesclagem poderá evitar a construção da tabela de dispersão.
• Um laço aninhado nesse caso seria um sinal de alerta, geralmente causado por uma estimativa incorreta.

Ler qual opção o planejador escolheu e avaliar se deveria tê-la escolhido é exatamente o sinal de experiência sênior que essas perguntas procuram testar.

Você une duas tabelas grandes e não ordenadas por uma condição de igualdade a.id = b.id; nenhuma delas tem um índice útil, e as estatísticas estão corretas. Qual algoritmo de junção o planejador provavelmente escolherá?

Os três algoritmos de junção:

• Laço aninhado: cada linha externa multiplica uma busca interna; é excelente com uma tabela externa pequena e uma chave interna indexada, mas perigoso quando loops é enorme.
• Junção por dispersão: construção e sondagem; é melhor para junções grandes, não ordenadas e por igualdade, mas se limita à igualdade e é restringida por work_mem.
• Junção por mesclagem: percorre entradas ordenadas em paralelo; é ideal quando os dados já estão ordenados ou para junções por intervalo.

O planejador escolhe com base no custo e nas estatísticas. Um laço aninhado surpreendente com uma quantidade enorme de laços quase sempre indica uma estimativa incorreta de linhas; corrija as estatísticas.