Algoritmos de Junção –
Sort-Merge Join Otimizado
Hash Join
AULA 19
Profa. Sandra de Amo
GBC053 – BCC
Otimização do Sort Merge Join
Realizar a junção durante a ordenação das relações
 Tamanho do buffer = B páginas
 Primeira iteração da ordenação: ordena-se cada página de R e
cada página de S e obtém-se M/B subarquivos ordenados de R e
N/B subarquivos ordenados de S
 Custo: 2M + 2N

Segunda iteração da ordenação: finaliza a ordenação
dos arquivos e ao mesmo tempo constrói a junção das
2 tabelas

Para finalizar a ordenação na 2a iteração:


Número de etapas = logB-1 (M/B) + 1 ≤ 2  logB-1 (M/B) ≤ 1
B ≥ M/B + 1  B2 – B ≥ M  B(B-1) ≥ M  B > M
Esquema Geral
2a iteração da ordenação
Subarquivos da Relação R
em disco
Cada página está
ordenada
Página ordenada
de R
Página de
R
Buffer
S
em disco
Página ordenada
de S
Subarquivos da
Relação S
em disco
Custo do Sort Merge Join Otimizado
Otimização



Primeira iteração da ordenação: ordena-se cada página de R e cada
página de S e obtém-se M/B subarquivos ordenados de R e N/B
subarquivos ordenados de S

Custo: 2M + 2N
Suponha que:

Temos no buffer 2X + 1 páginas, onde X > M1/2
M = tamanho da relação maior

número de subarquivos de R = M/X < M1/2

número de subarquivos de S = N/X < M/X < M1/2

Idéia: Se tivermos B > 2 M1/2 + 1, teremos espaço suficiente para
fazer o “merge” dos subarquivos de R e dos subarquivos de S na
segunda iteração, além de construir a resposta da junção
simultaneamente.

Custo = M + N (Não levo em consideração o tempo para gravar
a resposta)
Custo Total = 3(M+N)
Exemplo

M = 1000, N = 500, B = 102

102 > 2.1000 ½ + 1 = 64 + 1 = 65

Custo da 1a iteração da ordenação = 2M + 2N
= 2000 + 1000 = 3000 I/Os
Custo da 2a iteração (junção) =
M + N = 1500 I/Os
Custo total = 4500 I/Os = 45 segundos


Conclusão

Até o momento:







NLJ - t/t = 140 horas
NLJ - p/p = 1 hora e 24 min
BNL Join com B = 102 páginas no buffer = 1 min
INL Join com índice agrupado na relação maior = 15 min
INL Join com índice ñ agrupado na rel. maior = 25 min
Sort Merge Join, B = 102 páginas no buffer = 1 min 30 s
Sort Merge Join otimizado, B = 102 páginas no buffer
 Custo = 45 segundos
Hash Join

Fase do particionamento


Utiliza função hash para particionar R e S em k partições
Fase de junção




Supondo que cada partição i da relação menor S cabe na
memória
Carrega-se cada partição i de S na memória
Reserva-se uma página para a partição i da relação R
Para cada tupla t da partição i de R varre-se toda a
partição correspondente de S. Sabe-se que as tuplas que
casam com t só podem estar nesta partição i de S.
Fase do Particionamento de R e S
Relação R
particionada
Relações R e S
Pt 1 Pt 2 Pt 3 Pt 4 Pt 5 Pt 6
Distribui
Usando hash h
Página de R
Disco
Buffer tem capacidade para B páginas,
onde B – 1 = número k de partições
Disco
Fase da Junção de R e S
Relações R e S
particionadas
Relação R
Partição n de S (inteira)
Página da partição
n de R
Disco
Página de
R S
Buffer tem capacidade para B páginas,
onde B – 2 = tamanho da partição da
relação menor
Disco
S
Algoritmo Hash Join
Rotina Particiona(R,k)
% R = tabela, k = número de partições
Para cada página P da tabela R faça
begin
Leia P;
Para cada tupla r em P faça
begin
i : = h(r(A));
insere r na página Ki do buffer pool;
Se página Ki está cheia então grava Ki em disco e libera espaço no
buffer correspondente a Ki;
end
end
Para cada i=1,2,...,k faça
begin
Partição Pi = conjunto das páginas (em sequência) gravadas em
disco correspondentes ao espaço Ki do buffer pool
end
Algoritmo Hash Join
Rotina Junta(P1,…Pk,P’1,…,P’k)
% (P1,...,Pk = partições de R; P’1, ..., P’k = partições de S)
Para cada i = 1, ...,k faça
begin
carrega partição Pi de R no buffer pool (supomos que cada partição da
relação menor (R) caiba no buffer pool);
Para cada página P da partição P'i de S faça
begin
Para cada tupla s de P faça
begin
Para cada r na partição Pi de R tal que r(A) = s(A) faça
insere <r,s> em Result
end
end
end
Custo do Hash Join





R=M
S=N
Fase do Particionamento = 2(M + N)
Fase da Junção = M + N
Custo Total = 3(M+N)
Requisitos de memória








K = número de partições
M = tamanho da relação menor
N = tamanho da relação maior
B = número de páginas no buffer
Fase de particionamento: n. de partições = K = B - 1
Tamanho de cada partição da relação menor =
M/K = M/(B-1)
Fase da Junção : B ≥ M/(B-1) + 2
B> M
Exemplo
M = 500
N = 1000
B > 500 ~ 25 páginas
Custo Hash = 3(1500) = 4500
Custo de Sort-Merge = 3(1500) caso B > 2 1000 + 1
~ 65 páginas
 25 ≤ B ≤ 65: Hash Join é melhor
 B ≥ 65 : Hash e Sort-Merge têm os mesmos custos
 Quanto maior for a diferença entre o tamanho das
relações, maior a vantagem do Hash Join sobre o SortMerge, pois necessita de menos espaço no buffer para ter o
custo mínimo de 3(M+N).
Conclusão








NLJ - t/t = 140 horas
NLJ - p/p = 1 hora e 24 min
BNL Join com B = 102 páginas no buffer = 1 min
INL Join com índice agrupado na relação maior = 15 min
INL Join com índice ñ agrupado na rel. maior = 25 min
Sort Merge Join, B = 102 páginas no buffer = 1 min 30 s
Sort Merge Join otimizado, B = 102 páginas no buffer
= 45 segundos
Hash Join, B = 102 páginas no buffer = 45 segundos