Algoritmos para Operação de Junção

AULA 14

SISTEMAS DE BANCO DE DADOS

Tabelas a serem juntadas R : tabela externa

M páginas Pr tuplas por página

S : tabela interna 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 tuplaPara 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áginas de S

Página de R

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áginaPara 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

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-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

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.

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 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-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 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 = 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 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, ordena RSe S não está ordenada, ordena STr = 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

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(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 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 = Pr . N

Otimização do Sort Merge JoinRealizar 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 Geral2a iteração da ordenação

Buffer

Subarquivos da Relação R em discoCada página estáordenada

Subarquivos da Relação S em disco

R S

Página de

em disco

Página ordenadade R

Página ordenadade S

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

Buffer tem capacidade para B páginas,onde B – 1 = número k de partições

Página de R

Relações R e S

DiscoDisco

Relação R particionada

Pt 1 Pt 2 Pt 3 Pt 6Pt 5Pt 4

DistribuiUsando hash h

Fase da Junção de R e S

Buffer tem capacidade para B páginas,onde B – 2 = tamanho da partição da relação menor

Página da partição n de R

Relações R e Sparticionadas

DiscoDisco

SRelação R

Partição n de S (inteira)

SPágina de R

Algoritmo Hash JoinRotina 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 JoinRotina 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

ExemploM = 500N = 1000B > 500 ~ 25 páginasCusto Hash = 3(1500) = 4500Custo de Sort-Merge = 3(1500) caso B > 2 + 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).

1000

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