Introdução a Algoritmos de Joins no SQL Server

Pessoal, o post de hoje foi feito para explicar de maneira bem rápida os operadores de joins existentes no SQL Server. Entender cada tipo de join é essencial para uma boa análise de performance, pois os tempos de execução podem variar bastante de acordo com cada cenário.
Muitas pessoas perguntam. Qual o melhor operador de join? Não há. Cada um tem características específicas e são utilizados em cenários distintos. Por isso a importância de conhecer cada um deles.
Existem 3 operadores de JOIN no SQL Server: Nested Loops, Hash Join e Merge Join.

NESTED LOOPS

Como o próprio nome sugere, utiliza a ideia de loop. Para cada valor de uma tabela (outer input), faz-se uma busca de igualdade na outra tabela (inner input). É muito efetivo quando utilizado em cenários onde um input possui poucos registros e o inner input possui índice para a condição de igualdade.
No exemplo abaixo o Query Optimizer resolveu utilizar o NESTED LOOPS como solução para o INNER JOIN.

select top 1000
  SalesOrderID   = sor.SalesOrderID
, LineTotal      = sor.LineTotal
, OrderDate      = soh.OrderDate
, ShipDate       = soh.ShipDate
, TrackingNumber = sor.CarrierTrackingNumber
from       Sales.SalesOrderDetail sor
inner join Sales.SalesOrderHeader soh 
           on sor.SalesOrderID = soh.SalesOrderID
where    sor.CarrierTrackingNumber = '6431-4D57-83'
order by sor.SalesOrderID

Perceba que o número de linhas estimadas é pequeno, porque nesse caso foi utilizado o filtro “where sor.CarrierTrackingNumber = ‘6431-4D57-83′”.

Nesse cenário o plano de execução se mostrar muito bom, uma vez que necessitou de apenas 9 Logical Reads pra retornar o result set em microssegundos.
Table ‘SalesOrderHeader’. Scan count 0, logical reads 6 Table ‘SalesOrderDetail’. Scan count 1, logical reads 3.
CPU time = 15 ms, elapsed time = 0 ms.

MERGE JOIN

O Merge Join geralmente é utilizado para grandes volumes de dados. Ele necessita de dois inputs ordenados pelo valor de comparação (ON clauses), onde é feito o teste de igualdade linha a linha de cada output. Sua condição de parada é ao término dos dados do menor input.
Retirando a condição de busca por TrackingNumber, verifica-se uma alteração no plano de execução, onde o Query Optimizer opta por utilizar o MERGE JOIN.

select top 1000
  SalesOrderID   = sor.SalesOrderID
, LineTotal      = sor.LineTotal
, OrderDate      = soh.OrderDate
, ShipDate       = soh.ShipDate
, TrackingNumber = sor.CarrierTrackingNumber
from       Sales.SalesOrderDetail sor
inner join Sales.SalesOrderHeader soh 
           on sor.SalesOrderID = soh.SalesOrderID
order by sor.SalesOrderID

Como mencionado acima, o Merge Join utiliza inputs ordenados. No exemplo utilizado as duas tabelas possuem índices ordenados pela coluna SalesOrderID.

HASH JOIN

O Hash Join é geralmente utilizado para grandes volumes de dados, condições não indexadas, entre outros. É composto por duas fases: Build e Probe. Na primeira fase (Build), o Query Engine escolhe o menor input e gera uma Hash Table baseado nas Hash Keys. Na segunda fase (Probe), toda linha do segundo input é transformado em hash e comparado com a Hash Table gerado na fase Build, retornando assim todas as igualdades. Importante lembrar que se o Memory Grant da consulta não for suficiente, o SQL Server irá utilizar a TEMPDB para armazenar a Hash Table.

No exemplo abaixo, retirando-se o TOP 1000 e alterando a ordenação para ShipDate, o Query Optimizer decidiu por utilizar o Hash Match.

select 		
  SalesOrderID   = sor.SalesOrderID
, LineTotal      = sor.LineTotal
, OrderDate      = soh.OrderDate
, ShipDate       = soh.ShipDate
, TrackingNumber = sor.CarrierTrackingNumber
from       Sales.SalesOrderDetail sor
inner join Sales.SalesOrderHeader soh 
           on sor.SalesOrderID = soh.SalesOrderID
order by soh.ShipDate

FORCE JOIN (CUIDADO!)

É possível forçar a utilização de um algoritmo de join no seu código T-SQL, mas cuidado! Isso pode gerar dor de cabeça se não for bem utilizado. Basta colocar o nome do algoritmo entre o INNER | LEFT | RIGTH | FULL e o JOIN.
Exemplo:

select top 1000
  SalesOrderID   = sor.SalesOrderID
, LineTotal      = sor.LineTotal
, OrderDate      = soh.OrderDate
, ShipDate       = soh.ShipDate
, TrackingNumber = sor.CarrierTrackingNumber
from             Sales.SalesOrderDetail sor
inner MERGE join Sales.SalesOrderHeader soh 
                 on sor.SalesOrderID = soh.SalesOrderID
where    sor.CarrierTrackingNumber = '6431-4D57-83'
order by sor.SalesOrderID

É isso aí pessoal, se tiverem alguma dúvida por favor deixar um comentário.
Obs: os exemplos foram feitos em cima da base AdventureWorks, disponível nesse link.

REFERÊNCIA

Tipo de Joins no SQL Server

https://docs.microsoft.com/en-us/sql/relational-databases/performance/joins?view=sql-server-2017

One thought on “Introdução a Algoritmos de Joins no SQL Server

  1. anderson May 23, 2019 / 9:05 am

    Explicação bem didática! Parabéns

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.