Algoritmos para Operação de Junção

Loops Aninhados

AULA 17 Profa. Sandra de Amo

GBC053 – BCC

Operadores do SQLEMP(ENUM,ENOME,SAL,DNUM)

DEPT(DNUM,DNOME,ORC)

SELECT Sal. EMP

FROM EMP, DEPT

WHERE DEPT.DNUM = EMP.DNUM

AND DEPT.ORC > 40 mi

JUNÇÃO por DNUM

PROJEÇÃO EM Sal

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

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

Como otimizar o NLJ-tt ?

Custo = M + Pr.M. N

Reduzir o número de scans da tabela interna ? Reduzir o tamanho

tabela interna ?

NLJ- pag a pag Block Nested Loop Join (BNL)

Index Nested Loop Join

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

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