Algoritmos para Operação de Junção
Loops Aninhados
AULA 17
Profa. Sandra de Amo
GBC053 – BCC
Operadores do SQL
EMP(ENUM,ENOME,SAL,DNUM)
DEPT(DNUM,DNOME,ORC)
SELECT Sal. EMP
FROM EMP, DEPT
WHERE DEPT.DNUM = EMP.DNUM
AND DEPT.ORC > 40 mi
PROJEÇÃO EM Sal
JUNÇÃO por DNUM
SELEÇÃO ORC > 40mi
Quais os salários dos empregados que trabalham em departamentos com orçamento acima
de 40 milhões de reais ?
Nesta aula

Vamos estudar 3 algoritmos que
implementam a operação de Junção (JOIN)

Vamos calcular seus respectivos custos
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 !!
Como otimizar o NLJ-tt ?
Custo = M + Pr.M. N
Reduzir o número
de scans da tabela interna ?
NLJ- pag a pag
Block Nested Loop Join (BNL)
Reduzir o tamanho
tabela interna ?
Index Nested Loop Join
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 + M. N
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 na memória 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 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 = M + K.N = M + [M/(B-2)]N
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.

Calcular o custo do BNL Join no Caso 1, caso só se tenha
espaço suficiente no buffer para B - 2 páginas da relação S +
2 páginas extras
Para cada R-page faça
Para cada bloco de B-2 páginas de S faça
se ri = sj então insere <r,s> em Result
Retorna Result
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-1)/2 páginas para alocar
um bloco de R e (B-1)/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 = ri
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 K I/O,
onde K = número de tuplas de S com si= rj.
Custo do INL Join

Custo Total em caso de índice hash agrupado:


M + Pr.M . (2 + 1)
Custo Total em caso de índice B-tree
agrupado

M + Pr.M. (4 + 1)
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 S = M = 1000 páginas (INTERNA)
Tamanho de R = N = 500 páginas (EXTERNA)
80 tuplas por página na relação externa R
100 tuplas por página na relação interna S
S tem indice hash no atributo de junção
Atributo de junção não é chave da relação S
CASO 1: Indice é agrupado
CUSTO = 500 + 80 . 500 (1,2 + 1) = 500 + 40000(2,2) = 88500 I/Os = 15 min
CASO 2 : Indice é não é agrupado

Supondo que há distribuição uniforme dos valores do atributo A em S: cada tupla de R
‘casa’ com 2,5 tuplas de S.

Total de tuplas de S = 100*1000= 100.000

Total de tuplas de R = 500* 80 = 40.000
CUSTO = 500 + 80 . 500 (1,2 + 2,5) = 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