O SQL Server suporte 4 tipos de junção: nested loops join, merge join, hash join e remote join.

Nested loops join
Percorre a tabela interna, será percorrida linha a linha para cada linha encontrada na tabela externa; é muito eficiente quando a tabela externa é pequena. Para ficar mais claro observe o pseudocódigo:

for each row R1 in the outer table
for each row R2 in the inner table
if R1 joins with R2
return (R1, R2)

O custo deste algoritmo é proporcional ao tamanho da tabela externa multiplicada pelo tamanho da tabela interna. Execute o script t-sql abaixo e veja o plano de execução (Ctrl + L) como segue:

CREATE TABLE #Cliente (Id INT PRIMARY KEY IDENTITY(1, 1), Nome VARCHAR(100));
CREATE TABLE #Pedido (Id INT PRIMARY KEY IDENTITY(1, 1), Cliente_id INT);
INSERT INTO #Cliente (Nome) VALUES ('Maria');
INSERT INTO #Cliente (Nome) VALUES ('José');
INSERT INTO #Cliente (Nome) VALUES ('Pedro');
INSERT INTO #Cliente (Nome) VALUES ('João');

INSERT INTO #Pedido (Cliente_id) VALUES(1);
INSERT INTO #Pedido (Cliente_id) VALUES(1);
INSERT INTO #Pedido (Cliente_id) VALUES(1);
INSERT INTO #Pedido (Cliente_id) VALUES(1);
INSERT INTO #Pedido (Cliente_id) VALUES(2);
INSERT INTO #Pedido (Cliente_id) VALUES(2);
INSERT INTO #Pedido (Cliente_id) VALUES(2);
INSERT INTO #Pedido (Cliente_id) VALUES(2);
INSERT INTO #Pedido (Cliente_id) VALUES(3);
INSERT INTO #Pedido (Cliente_id) VALUES(3);
INSERT INTO #Pedido (Cliente_id) VALUES(3);
INSERT INTO #Pedido (Cliente_id) VALUES(3);
INSERT INTO #Pedido (Cliente_id) VALUES(4);
INSERT INTO #Pedido (Cliente_id) VALUES(4);
INSERT INTO #Pedido (Cliente_id) VALUES(4);
INSERT INTO #Pedido (Cliente_id) VALUES(4);

SELECT *
FROM #Cliente AS cliente
INNER JOIN #Pedido AS Pedido ON(Pedido.Cliente_id = cliente.Id)

Plano de execução
nestedLoops

Hash Loop join
Tem duas entradas, a tabela interna (probe input) e a externa (build input), a menor das duas tabelas será a tabela externa. Este join vasculha toda a tabela externa e cria uma estrutura em memória organizadas por chaves (hash keys), ou seja, este processo utiliza mais memória. A seguir a tabela interna é scaneada e suas linhas são comparadas uma a uma com a estrutura criada. Se a estrutura de hash não couber na memória, ela será fragmentada e executada em partes. É muito utilizado para grandes tabelas, pois a busca é relativamente rápida. O SQL Server irá decidir ao gerar o plano de execução, mas podemos dar algumas dicas para ele?
Sim podemos, isso é chamado de table hint, eu posso “forçar” meu join a utilizar um hash loop join acrescentando a palavra chave “HASH” entre “INNER” e “JOIN”.

SELECT *
FROM #Cliente AS cliente
INNER HASH JOIN #Pedido AS Pedido ON(Pedido.Cliente_id = cliente.Id)

O plano de execução ficaria assim:

hashLoopJoin

Bom, agora vamos comparar o plano de execução gerado pelo SQL Server, com e sem o table hint; Adicionei uma query hint (uma dica de consulta): RECOMPILE, assim não seremos “enganados” pelo plano de execução cacheado do SQL Server:

SELECT *
FROM #Cliente AS cliente
INNER HASH JOIN #Pedido AS Pedido ON(Pedido.Cliente_id = cliente.Id)
OPTION(RECOMPILE)

SELECT *
FROM #Cliente AS cliente
INNER JOIN #Pedido AS Pedido ON(Pedido.Cliente_id = cliente.Id)
OPTION(RECOMPILE)

Comparação
comparacaoPlanoExecucao

Aqui fica claro que a decisão do SQL Server em usar o nested loop join é melhor, afinal, a segunda consulta foi bem superior. Quer dizer que nunca devo utilizar essa table hint?!
Não é bem assim, vai de caso a caso, as vezes detectamos que o SQL Server está gerando um plano de execução não tão bom (quanto poderia), e não podemos simplesmente forçar um recompile na consulta, no banco de produção. Mas repito, vai do caso em particular.

Merge join
É a estrutura que melhor se beneficia de índices, sejam eles clusterizados ou não clusterizados. Se beneficiando muito quando os dados estão ordenados. Cada entrada é scaneada apenas uma vez, por isso a eficácia deste tipo de join. Múltiplas tabelas podem ser unidas por vez, mas nestes casos uma tabela temporária será utilizada.

merge

Remote join
Esse tipo de join é útil quando a tabela externa é uma tabela remota (chamada por linked server por exemplo), esse tipo deve ser usando quando a tabela interna conter menor número de linhas que a tabela externa.

Até a próxima pessoal!