View
222
Download
1
Category
Preview:
Citation preview
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
ResultRetorna Result
Relação S inteira
Buffer
Página de R Página de output
Custo = M + N I/OsNo 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
ResultRetorna Result
Bloco de B-2 páginas de R
Buffer tem capacidade para B páginas
Página de S Página de output
Esquema Geral do BNL Join
Bloco de B-2 páginas de R
Buffer tem capacidade para B páginas
Página de S Página de output
Relações R e S
DiscoDisco
Relação R 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.
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 ResultRetorna Result
Otimizações do BNL Join1. 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 Join2. 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 JoinSe 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 ResultRetorna 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 + (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 S = M = 1000 páginas (INTERNA)Tamanho de R = N = 500 páginas (EXTERNA)80 tuplas por página na relação externa R100 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çãonã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.000CUSTO = 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
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. Varre ambas as páginas simultaneamente para
encontrar as tuplas que casam. À medida que se encontram as tuplas que casam vai-
se construindo páginas da relação de output.
Sort Merge Join: Esquema Geral
Página de S
Página de output
Relações R e S
DiscoDisco
Relação R S
Página de R
4, 5, 2
4, 5, 2, 1, 3
4, 7, 26, 7, 36, 1, 9
2, 5, 23, 5, 24, 1, 34, 7, 15, 8, 06, 8, 46, 7, 5
4, 5, 2, 7, 1
6, 7, 3, 8, 4
4, 7, 2, 1, 3
Relação R SRelação R
Algoritmo Sort Merge JoinSe R não está ordenada pelo atributo
i, ordena R pelo atributo iSe S não está ordenada pelo atributo
j, ordena S pelo atributo jTr = 1a tupla de RTs = 1a tupla de SGs = 1a tupla de SWhile 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; endwhileGs = Ts;endwhile
Exercício
Execute o algoritmo SortMerge em R e S especificando os valores assumidos pelas Variáveis Tr, Gs e Ts.
Custo do Sort-Merge Join Número de páginas no buffer = B Custo de ordenar a relação R
2M(logB-1M1 + 1) onde M1 = M/B Custo de ordenar a relação S
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 1M = 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
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 2M = 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 3M = 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 = M + Pr . M. N
Recommended