15
Algoritmos de Junção – Sort-Merge Join Otimizado Hash Join AULA 19 Profa. Sandra de Amo GBC053 – BCC

Algoritmos de Junção – Sort-Merge Join Otimizado Hash Join AULA 19 Profa. Sandra de Amo GBC053 – BCC

Embed Size (px)

Citation preview

Page 1: Algoritmos de Junção – Sort-Merge Join Otimizado Hash Join AULA 19 Profa. Sandra de Amo GBC053 – BCC

Algoritmos de Junção – Sort-Merge Join Otimizado

Hash Join

AULA 19 Profa. Sandra de Amo

GBC053 – BCC

Page 2: Algoritmos de Junção – Sort-Merge Join Otimizado Hash Join AULA 19 Profa. Sandra de Amo GBC053 – BCC

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

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

Page 3: Algoritmos de Junção – Sort-Merge Join Otimizado Hash Join AULA 19 Profa. Sandra de Amo GBC053 – BCC

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

Page 4: Algoritmos de Junção – Sort-Merge Join Otimizado Hash Join AULA 19 Profa. Sandra de Amo GBC053 – BCC

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)

Page 5: Algoritmos de Junção – Sort-Merge Join Otimizado Hash Join AULA 19 Profa. Sandra de Amo GBC053 – BCC

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

Page 6: Algoritmos de Junção – Sort-Merge Join Otimizado Hash Join AULA 19 Profa. Sandra de Amo GBC053 – BCC

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

Page 7: Algoritmos de Junção – Sort-Merge Join Otimizado Hash Join AULA 19 Profa. Sandra de Amo GBC053 – BCC

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.

Page 8: Algoritmos de Junção – Sort-Merge Join Otimizado Hash Join AULA 19 Profa. Sandra de Amo GBC053 – BCC

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

Page 9: Algoritmos de Junção – Sort-Merge Join Otimizado Hash Join AULA 19 Profa. Sandra de Amo GBC053 – BCC

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

Page 10: Algoritmos de Junção – Sort-Merge Join Otimizado Hash Join AULA 19 Profa. Sandra de Amo GBC053 – BCC

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

Page 11: Algoritmos de Junção – Sort-Merge Join Otimizado Hash Join AULA 19 Profa. Sandra de Amo GBC053 – BCC

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

Page 12: Algoritmos de Junção – Sort-Merge Join Otimizado Hash Join AULA 19 Profa. Sandra de Amo GBC053 – BCC

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)

Page 13: Algoritmos de Junção – Sort-Merge Join Otimizado Hash Join AULA 19 Profa. Sandra de Amo GBC053 – BCC

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

Page 14: Algoritmos de Junção – Sort-Merge Join Otimizado Hash Join AULA 19 Profa. Sandra de Amo GBC053 – BCC

ExemploM = 500N = 1000B > 500 ~ 25 páginasCusto Hash = 3(1500) = 4500Custo de Sort-Merge = 3(1500) caso B > 2 + 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 Sort-Merge, pois necessita de menos espaço no buffer para ter o custo mínimo de 3(M+N).

1000

Page 15: Algoritmos de Junção – Sort-Merge Join Otimizado Hash Join AULA 19 Profa. Sandra de Amo GBC053 – BCC

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