Algoritmos para Operação
de Junção
AULA 14
SISTEMAS DE BANCO DE DADOS
Tabelas a serem juntadas

R : tabela externa



S : tabela interna




M páginas
Pr tuplas por página
N páginas
Ps tuplas por página
Condição de Junção: Ri = Sj
Custo de uma operação de I/O = 10ms
Nested Loops Join – tupla a tupla
Para cada tupla r ε R faça
Para cada tupla s ε S faça
se ri = sj então
insere <r,s> em
Result
Retorne Result
t
Página de R
Páginas de S
Custo do NLJ - t/t





S é escaneada Pr . M vezes
Cada scan em S equivale a N operações de
I/O (N = número de páginas de S)
R é escaneada uma vez
Custo total = Pr. M. N + M
Não se considera o custo de escrever o
resultado, pois é igual para todos os
métodos.
Exemplo




M = 1000 páginas
Pr = 100 registros por página
N = 500
Custo = 1000 + 100.1000.500 = 50.000.100 I/Os
~ 140 horas de processamento !!
Nested Loops Join – página a página
Para cada R-page de R faça
Para cada S-page de S faça
se ri = sj então
insere <r,s> em
Result
Retorne Result
Páginas de S
Página de R
Custo do NLJ- p/p





S é escaneada M vezes
Cada scan em S equivale a N operações de
I/O (N = número de páginas de S)
R é escaneada uma vez
Custo total = M. N + M
Não se considera o custo de escrever o
resultado, pois é igual para todos os
métodos.
Exemplo



M = 1000 páginas
N = 500
Custo = 1000 + 1000.500 = 501.000 I/Os
~ 1,4 horas de processamento
Block Nested Loops Join – uso do Buffer
Caso 1:
Tem-se espaço suficiente no buffer
para a relação S inteira + 2
páginas extras
Para cada R-page faça
Para cada S-page in memory faça
se ri = sj então insere <r,s> em
Result
Retorna Result
Relação S inteira
Página de R
Página de output
Buffer
Custo = M + N I/Os
No exemplo :
1500 I/Os = 15
segundos
Block Nested Loops Join – uso do Buffer
Caso 2:
Tem-se espaço suficiente no buffer
para B - 2 páginas da relação R
+ 2 páginas extras
Para cada bloco de (B-2) páginas in
memory de R-page faça
Para cada S-page faça
se ri = sj então insere <r,s> em
Result
Retorna Result
Bloco de B-2 páginas de R
Página de S
Página de output
Buffer tem capacidade para B páginas
Esquema Geral do BNL Join
Relação R
Relações R e S
Bloco de B-2 páginas de R
Página de S
Página de output
Buffer tem capacidade para B páginas
Disco
Disco
S
Custo do BNL Join

K = Número de blocos de B-2 páginas de M






K = [M/(B-2)]
Cada página de S é escaneada K vezes
Cada scan em S equivale a N operações de I/O (N =
número de páginas de S)
R é escaneada uma vez
Custo total = K.N + M = [M/(B-2)]N + M
Não se considera o custo de escrever o resultado,
pois é igual para todos os métodos.
Exemplo




M = 1000 páginas
N = 500
B = 102
Custo = (1000/100).500 + 1000 = 6000 I/Os
~ 1 minuto
Exercício

Calcular o custo do BNL Join, caso a relação
S (menor) seja escolhida como a relação
externa.
Otimizações do BNL Join
1. Diminuindo o custo de CPU para fazer as
junções.


Se houver espaço suficiente na memória,
construir uma tabela hash para cada R-block
carregado na memória, com chave = atributo da
junção.
Para cada tupla s ε S, para encontrar r ε R-block
tal que ri = sj, utiliza-se a tabela Hash construída.
Otimizações do BNL Join
2. Ao invés de utilizar B-2 páginas em memória para
alocar blocos da relação externa R, e uma só página
para a relação S, utilizar (B-2)/2 páginas para alocar
um bloco de R e (B-2)/2 páginas para alocar um
bloco da relação interna S.
Exercício: calcular o custo neste caso.
Onde há melhora de performance em relação ao método
anterior (onde 1 única página em memória é alocada
para a relação S) ?
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
Index Nested Loops Join
Se uma das relações (S)
possui um índice nos
atributos da junção
(chave = atributos da
junção)
Usa S como a relação
interna
Para cada tupla r ε R faça
Para cada tupla s ε S
tal que ri = sj
insere <r,s> em Result
Retorna Result
Usa o índice em S para
encontrar todas as
tuplas de S com sj = rj
Custo do INL Join

Para cada r = <r1,...,ri,...,rn>

Custo para encontrar todas as tuplas de S com sj = ri




Se o índice é B-Tree: custo para encontrar a folha apropriada é 2
a 4 I/Os = profundidade da árvore
Se o índice é Hash : custo para encontrar o bucket apropriado é
1 a 2 I/Os (2 I/Os caso for extensível com diretório de ponteiros
em disco).
Se o índice é agrupado: custo de encontrar as tuplas
correspondendo ao ponteiro indicado pelo índice é 1 I/O.
Se o índice não é agrupado: custo de encontrar as tuplas
correspondendo ao ponteiro indicado pelo índice pode ser N I/O,
onde N = número de tuplas de S com si= rj.
Custo do INL Join

Custo Total em caso de índice hash agrupado:


M + (2 + 1).Pr.M
Custo Total em caso de índice B-tree
agrupado

M + (4 + 1).Pr.M
Exemplo 1






Tamanho de R = M = 1000 páginas
Tamanho de S = N = 500
Pr = 100 tuplas por página
S tem indice hash no atributo de junção
Atributo de junção é chave da relação S
Custo =

1000 + 100.000 (1 + 1,2 ) = 221.000 I/0s = 37 min
Exemplo 2







Tamanho de R = M = 1000 páginas
Tamanho de S = N = 500
Ps = 80 tuplas por página
R tem indice hash no atributo de junção
Atributo de junção não é chave da relação R
Custo p/ encontrar a pág. do indice correspondendo a ri = sj

500 + 80 . 500 (1,2) = 500 + 40000(1,2) = 48500 I/Os
Custo p/ encontrar as tuplas em R indicadas pelo ponteiro da entrada <ri,*>

Total de tuplas de R = 100.000

Total de tuplas de S = 40.000

Se há distribuição uniforme, cada tupla de S ‘casa’ com 2,5 tuplas de R.

Se o indice de R é agrupado: as tuplas de R que casam com sj estão em uma
página:


Custo total = 48.500 + 40000 = 88.500 I/Os = 15 min
Se o indice de R não é agrupado:

Custo total = 48.500 + 2,5. 40000 = 148.500 I/Os = 25 min
Conclusão


INL Join vale mais a pena quando o índice
está na relação maior e é agrupado.
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 rel. maior = 15 min
INL Join com índice ñ agrupado na rel. maior = 25 min
Sort Merge Join





Ordena relação R pelo atributo de junção
Ordena relação S pelo atributo de junção
Carrega página de R e página de S na memória.
Escaneia ambas as páginas simultaneamente para
encontrar as tuplas que casam.
À medida que se encontram as tuplas que casam vaise construindo páginas da relação de output.
Sort Merge Join: Esquema Geral
Relação R
Relações R e S
4, 5, 2
4, 7, 2
6, 7, 3
6, 1, 9
Página de R
Disco
2, 5, 2
3, 5, 2
4, 1, 3
4, 7, 1
5, 8, 0
6, 8, 4
6, 7, 5
Página de S
4, 5, 2, 1, 3
4, 5, 2, 7, 1
4, 7, 2, 1, 3
Página de output
6, 7, 3, 8, 4
Disco
S
Algoritmo Sort Merge Join
Se R não está ordenada, ordena R
Se S não está ordenada, ordena S
Tr = 1a tupla de R
Ts = 1a tupla de S
Gs = 1a tupla de S
While Tr ≠ eof e Gs ≠ eof do
While Tri < Gsj do
Tr = next tuple em R depois de Tr;
endwhile
While Tri > Gsj do
Gs = next tuple em S depois de
Gs;
endwhile
While Tri = Gsj do
Ts = Gs
While Tsj = Tri do
insere <Tr, Ts> em Result
Ts = next tuple em S depois
de Ts;
endwhile
Tr = next tuple em R depois de Tr;
endwhile
Gs = Ts;
endwhile
Custo do Sort-Merge Join


Número de páginas no buffer = B
Custo de ordenar a relação R


Custo de ordenar a relação S


2M(logB-1M1 + 1) onde M1 = M/B
2N(logB-1N1 + 1) onde N1 = N/B
Custo de juntar as duas relações = M + N
(supondo que cada partição de R e cada partição de S cabe
numa página)
Observação : uma partição corresponde ao conjunto de
tuplas com o mesmo valor do atributo de junção
Exemplo 1
M = 1000, N = 500, B = 102
 Custo de ordenar a relação R
 2M(logB-1M/B + 1) = 2. 1000 (log101 1000/102 + 1) =
= 2. 1000 (0,5 + 1) = 3000 I/Os
(101)1/2 = 9,80
 Custo de ordenar a relação S = 2. 500 (0,3+1) = 1300 I/Os
 Custo de juntar as duas relações = 1500 I/Os
 Custo total = 5800 I/Os
 Custo do BNL Join = 6000 I/Os
 Custos não muito diferentes
Exemplo 2
M = 1000, N = 500, B = 35
 Custo de ordenar a relação R
 2M(logB-1M/35 + 1) = 2. 1000 (log34 1000/35 + 1) =
= 2. 1000 (1 + 1) = 4000 I/Os
(34)1 = 34 1000/35 = 28,57
 Custo de ordenar a relação S = 2. 500 (1 + 1) = 2000 I/Os
 Custo de juntar as duas relações = 1500 I/Os
 Custo total = 7500 I/Os = 3 min e 7 seg
 Custo do BNL Join = [M/(B-2)]N + M = 31 . 500 + 1000 =
16500 I/Os = 7 min
 Sort Merge bem mais rápido
Exemplo 3
M = 1000, N = 500, B = 300
 Custo de ordenar a relação R
 2M(logB-1M/300 + 1) = 2. 1000 (log299 3,33 + 1) =
= 2. 1000 (0,2 + 1) = 2400 I/Os
(299)0.2 = 3,12
 Custo de ordenar a relação S = 2. 500 (0,2 + 1) = 1200 I/O
 Custo de juntar as duas relações = 1500 I/Os
 Custo total = 5100 I/Os = 2min e 7 segundos
 Custo do BNL Join = 4 . 500 + 1000 = 3000 I/Os = 75 seg
 BNL mais rápido
Discussão: Sort Merge Join

Piores casos:

Se o número de tuplas numa partição da segunda
relação (S) é muito grande e não cabe no buffer
pool


Partição de S deverá ser varrida tantas vezes quanto
for o número de tuplas na correspondente partição de
R.
Pior caso: todas as tuplas de R e S contém o
mesmo valor no atributo de junção:

Custo = Pr . N
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

Suponha que:

B > M1/2, onde M é a relação maior

número de subarquivos de R = M/B < M1/2

número de subarquivos de S = N/B < M/B < M1/2

Idéia: Se tivermos B > 2 M1/2 + 3, 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

Custo Total = 3(M+N)
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
Exemplo

M = 1000, N = 500, B = 102

102 > 2.1000 ½ + 3 = 64 + 3 = 67

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: 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 + 3
~ 67 páginas
 25 ≤ B ≤ 67: Hash Join é melhor
 B ≥ 67 : 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 Sort-Merge, pois
necessita de menos memória interna 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
Algoritmos de “Join” nos SGBDs comerciais






Sybase ASE: INJ e Sort-Merge
Sybase ASIQ: NLJ p/p, INJ, Sort-Merge, Hash Join
simples
Oracle 8: NLJ p/p, Sort-Merge, Hash Join híbrido
IBM DB2: BNL, Sort-Merge, Hash Join híbrido
MS SQL Server: BNL, INL, Sort-Merge, Hash Join
simples, Hash teams (técnica própria da MS)
Informix: BNL, INL, Hash Join híbrido