AOBD 07/08
Mini-Projecto 2
Soluções
1) Considere que existem três relações R1=(A,B,C), R2=(C,D) e
R3=(D,E) com chaves primárias A, C e D, respectivamente.
Considere ainda que estas relações têm as seguintes
propriedades:

A relação R1 contém 10,000 tuplos.

A relação R2 contém 30,000 tuplos.

A relação R3 contém 20,000 tuplos.

Na relação R1, cada página de dados pode armazenar um
máximo de 10 tuplos.

Na relação R2, cada página de dados pode armazenar um
máximo de 15 tuplos.

Na relação R3, cada página de dados pode armazenar um
máximo de 20 tuplos.
a) Estime o tamanho do resultado da junção
natural entre as três tabelas (R1 |x| R2 |x| R3) e
apresente uma estratégia eficiente para o seu
processamento, tendo em atenção o tamanho
das relações e indicando o custo em termos de
operações de I/O. Poderá assumir a existência
de índices sobre qualquer uma das 3 relações.

R1 - 10,000 tuplos/1000 páginas => 1 tuplo = 0.1 páginas

R2 - 30,000 tuplos/2000 páginas => 1 tuplo = 0.067 páginas

R3 - 20,000 tuplos/1000 páginas => 1 tuplo = 0.05 páginas

R2 |X| R1 = máx 10,000 tuplos (C é chave em R2)


R2 |X| R3 = máx 20,000 tuplos (D é chave em R3)


1 tuplo = máx 0.167 páginas => ~ 6 tuplos/página
1 tuplo = máx 0.117 páginas => ~ 9 tuplos/página
R3 |X| R1 |X| R2 = máx 10,000 tuplos (D é chave em R3)

1 tuplo = máx 0.217 páginas => ~ 5 tuplos/página
(nota: os valores apresentados acima são estimativas por excesso)

Uma estratégia eficiente seria:



Fazer primeiro R2 merge-join R1 (assumindo que existem índices sobre
os atríbutos C das duas tabelas)

Custo : R2p + R1p = 1000 + 2000 = 3000 IO

Tamanho da relação : approx. 1667 páginas
Fazer um hash-join do resultado anterior com R3

Custo: 3*((R2 |x| R1)p + R3p) = 5301 IO

Custo total: 11001 IO
Ou um merge join do resultado anterior com R3 se R3 se encontrar
ordenada por um índice no atríbuto D.

Custo: (R2 |x| R1)p + R3p = 2667 IO

Custo total: 5667 IO
b) Para uma junção natural entre as tabelas R1 e
R2, estime o número de acessos necessário à
execução de cada um dos seguintes
algoritmos, explicando sempre os cálculos
necessários:
i. Nested-loop join, podendo tanto R1 como R2
corresponder à inner table.
ii. Merge join, assumindo que as relações não se
encontram inicialmente ordenadas.
iii. Hash join, assumindo que não existem colisões na
função de hash.
Rb = nº de páginas, Rt = nº de tuplos

Nested Loop:

block nested-loop join
 R1b * R2b + R1b= 2 001 000 I/O
 R2b * R1b + R2b= 2 002 000 I/O
 nested-loop join
 R1t * R2b + R1b = 20 001 000 I/O
 R2t * R1b + R2b = 30 002 000 I/O
Merge Join

R1b + R2b + Sort(R1) + Sort(R2) = 28 204 I/O
 Sort(R) = Rb * (2 * log
M-1(Rb/M) + 1)
 M = 3
Hash Join



3 * (R1b + R2b) = 9000 I/O
2) Explique o conceito de “index intersection”
usado no SQL Server 2005, relacionando-o
com o facto de, em algumas situações, a
existência de índices secundários poder trazer
benefícios em termos de performance em
comparação com índices primários. Apresente
ainda um exemplo em que a utilização de index
intersection seja vantajosa.
SQL Server pode usar vários índices para fazer a selecção de
conjuntos de dados e depois fazer uma intersecção entre
estes. Por exemplo, para a consulta:
SELECT count (*) FROM orders WHERE o_orderdate
between '9/15/1992' and '10/15/1992' and
o_custkey between 100 and 200;
SQL Server pode usar o índices em “o_custkey” e “o_orderdate” e
aplicar um algoritmo de join para onter a intersecção dos dois
conjuntos de ponteiros retornados. Isto deverá ser mais rápido
visto que é mais eficiente ler apenas os índices de que as
páginas de dados.
3) Em cada uma das seguintes situações, indique qual o
algoritmo de junção que seria mais eficiente em termos de
número de operações de I/O. Justifique a sua resposta.
a) Junção natural entre duas tabelas a e b que sejam pequenas (i.e.
todos os tuplos de a e b podem ser armazenados em memória) e
para as quais não existam índices.
b) Junção natural entre duas tabelas a e b para as quais não
existam índices e em que o número de tuplos em a seja muito
maior que o número de tuplos em b.
c) Junção natural entre duas tabelas a e b, considerando que
ambas contêm aproximadamente o mesmo número de tuplos e
que existem índices sob o atributo sobre o qual se vai processar
a junção das tabelas.
d) Junção entre duas tabelas a e b, considerando que um operador
diferente da igualdade entre atributos é usado na condição de
junção das tabelas, e que existem índices sobre o atributo sobre
o qual se vai processar a junção das tabelas.
 Nested-loop join, visto as tabelas serem pequenas e
não estarem ordenadas pelo atríbuto pelo qual se vai
fazer a junçao.
 Hash-join, visto uma das tabelas ser muito mais
pequena do que a outra e nenhuma das tabelas estar
ordenada pelo atríbuto pelo qual se vai fazer a junçao.
 Merge-join, visto existirem indices que levem a que
as tabelas se encontrem ordenadas pelo atríbuto pelo
qual se vai fazer a junção.
 Nested-loop join, visto não estarmos na presença de
um equi-join.
4) Explique a diferença entre cost based
optimization e heuristic optimization, indicando
situações em que um tipo de estratégia de
optimização possa ser preferível ao outro.
“Cost base optimization” requer um modelo de custos, i.e.,
estatísticas que suportem a estimativa de custos, e
algoritmos de procura eficientes sobre o espaço dos
planos de execução. “Heuristic optimization” é rápida e
intuitiva, mas não garante a melhor solução.
Um optimizador baseado em custos pode ter problemas com
consultas complexas (e.g., consultas aninhadas). Para
consultas com muitos joins, o próprio processo de procura
do plano pode ser demasiado caro. Por outro lado, usando
só heurísticas, seria difícil escolher entre um “full-table
scan” ou um “index-scan”, visto que a sua eficiência
depende da selectividade da consulta.
5) Considere que existe uma relação R=(a,b,c) contendo 5
milhões de tuplos, e que cada página de dados armazena
um máximo de 10 tuplos. Assuma ainda que o atributo a é
uma chave candidata, podendo tomar valores entre 1 e
5,000,000. Considede ainda que o optimizador de
interrogações pode escolher entre as seguintes
estratégias para aceder aos tuplos de R:

Aceder à tabela directamente.

Usar um indice clustered do tipo B+Tree sobre o
atríbuto a.

Usar um índice hash no atributo a.
a) Para cada uma das seguintes interrogações,
indique qual a aproximação mais eficiente em
termos de I/O, justificando a sua resposta.
i. σa<5,000 (R)
ii. σa>5,000 (R)
iii. σa=5,000 (R)
iv. σa>5,000 ∧ a<5,010 (R)
v. σ¬(a=5,000) (R)
vi. σa>4,900,000 (R)
i. σa<5,000 (R)
Querie muito selectiva, usar o índice B+Tree no atríbuto a.
ii. σa>5,000 (R)
Query pouco selectiva, fazer um full-table scan.
iii. σa=5,000 (R)
Querie por igualdade, utlizar o indice hash.
iv. σa>5,000 ∧ a<5,010 (R)
Querie muito selectiva, usar o indice B+Tree (clustered index) em a.
v. σ¬(a=5,000) (R)
Querie pouco selectiva, full table scan.
vi. σa>4,900,000 (R)
Querie muito selectiva, utilizar o indice B+Tree no atríbuto a.
b) Para cada uma das seguintes interrogações envolvendo uma
negação, indique qual a aproximação mais eficiente em
termos de I/O. Indique claramente os passos envolvidos no
processamento das interrogações justificando se iria recorrer
a índices para o seu processamento e/ou se iria substituir as
expressões em álgebra relacional por outras que lhes sejam
equivalentes.
i. σ¬(a<2,500,000)(R)
ii. σ¬(a=2,500,000)(R)
iii. σ¬(a<2,500,000 ∨ b<5000)(R)
i. σ¬(a<2,500,000)(R)
Equivalente a select(a>=2500000)(R) – a consulta iria retornar
approx. metade dos tuplos. Como o índice é clustered, deveria
ser usado para retornar todos os tuplos satisfazendo a condição.
ii. σ¬(a=2,500,000)(R)
Querie pouco selectiva, full table scan.
iii. σ¬(a<2,500,000 ∨ b<5000)(R)
Equivalente a select(a>=2500000 AND b>=5000)(R). Usar o
índice B+Tree sobre a para a primeira condição de selecção
(index scan). Nos resultados deste primeiro passo, seleccionar
apenas os tuplos que satisfaçam a segunda condição.