ibd-parte7

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

1
Introdução a Banco de Dados – DCC 011
Processamento e Otimização de 
Consultas
Introdução a Banco de Dados – DCC 011
Processo de Execução de uma Consulta
2
Introdução a Banco de Dados – DCC 011
Otimização de Consultas SQL
� Em algumas linguagens de consulta, a estratégia 
de execução é definida pela maneira como o 
usuário (ou programador) expressa a consulta
� Em SQL, que é uma linguagem declarativa, 
apenas os resultados desejados são 
especificados
� Portanto, a otimização de consultas é necessária 
em SGBDs relacionais baseados em SQL 
Introdução a Banco de Dados – DCC 011
Otimização de Consultas SQL
� Passos principais
� Tradução da consulta SQL para a álgebra 
relacional
� Otimização do resultado
� Estratégias de otimização
� Otimização baseada em heurísticas
� Otimização baseada na estimativa de custo da 
consulta
� Otimização semântica 
3
Introdução a Banco de Dados – DCC 011
Tradução de Consultas SQL para 
Expressões da AR
� Consultas SQL são decompostas em blocos
� Cada bloco é transformado em uma expressão 
da álgebra relacional
� Os blocos são otimizados internamente, levando-
se em consideração a ordem de execução entre 
eles
� Um bloco contém um único comando SELECT-
FROM-WHERE, incluindo cláusulas GROUP BY e 
HAVING, se houver
Introdução a Banco de Dados – DCC 011
Exemplo de Tradução de uma
Consulta SQL
SELECT LNAME, FNAME
FROM EMPLOYEE
WHERE SALARY > ( SELECT MAX (SALARY)
FROM EMPLOYEE
WHERE DNO = 5); 
SELECT MAX (SALARY)
FROM EMPLOYEE
WHERE DNO = 5
SELECT LNAME, FNAME
FROM EMPLOYEE
WHERE SALARY > C
piLNAME, FNAME (σSALARY>C(EMPLOYEE)) �MAX SALARY (σDNO=5 (EMPLOYEE))
4
Introdução a Banco de Dados – DCC 011
Otimização Baseada em Heurísticas
� Consultas são representadas internamente na forma de 
uma árvore ou grafo
� Árvores de consulta são preferidas para a otimização pois 
determinam a ordem de execução das operações
� Grafos de consulta indicam apenas as operações e os respectivos 
operandos envolvidos � portanto, existe apenas um grafo 
correspondente a cada consulta
� Regras heurísticas são usadas para alterar a representação 
interna (árvore ou grafo) de uma consulta de modo a 
otimizar a sua execução 
� Por exemplo: operações de projeção e seleção são aplicadas antes 
de uma junção 
� O plano de execução gerado determina a ordem em que 
as operações serão executadas e os recursos a serem 
utilizados (por ex., índices)
Introdução a Banco de Dados – DCC 011
Exemplo Preliminar
Consulta Q2 (Cap. 5 e 8):
Para cada projeto localizado em ‘Stafford’, recupere o número do 
projeto, o número do departamento responsável e o último nome, o 
endereço e a data de nascimento do gerente do departamento. 
Consulta SQL:
SELECT P.PNUMBER, P.DNUM, E.LNAME, E.ADDRESS, E.BDATE
FROM PROJECT AS P, DEPARTMENT AS D, EMPLOYEE AS E
WHERE P.DNUM=D.DNUMBER AND D.MGRSSN=E.SSN AND
P.PLOCATION=‘STAFFORD’;
Álgebra Relacional:
pipipipiPNUMBER, DNUM, LNAME, ADDRESS, BDATE (((σσσσPLOCATION=‘STAFFORD’(PROJECT))
DNUM=DNUMBER (DEPARTMENT)) MGRSSN=SSN (EMPLOYEE))
5
Introdução a Banco de Dados – DCC 011
Árvore de Consulta
pipipipiPNUMBER, DNUM, LNAME, ADDRESS, BDATE (((σσσσPLOCATION=‘STAFFORD’(PROJECT))
DNUM=DNUMBER (DEPARTMENT)) MGRSSN=SSN (EMPLOYEE))
Introdução a Banco de Dados – DCC 011
Árvore Canônica
SELECT P.PNUMBER, P.DNUM, E.LNAME, E.ADDRESS, E.BDATE
FROM PROJECT AS P, DEPARTMENT AS D, EMPLOYEE AS E
WHERE P.DNUM=D.DNUMBER AND D.MGRSSN=E.SSN AND
P.PLOCATION=‘STAFFORD’;
6
Introdução a Banco de Dados – DCC 011
Otimização Heurística
� Parte de uma árvore “canônica”, obviamente 
ineficiente, mas fácil de ser construída
� No exemplo anterior, considerando-se que
� P tem 100 tuplas de 100 bytes
� D tem 20 tuplas de 50 bytes
� E tem 5000 tuplas de 150 bytes
os produtos cartesianos resultariam em 10 milhões 
de tuplas de 300 bytes cada
� Transformações a partir da árvore canônica usam 
regras de equivalência entre expressões da álgebra 
relacional para melhorar progressivamente o plano 
de execução da consulta
Introdução a Banco de Dados – DCC 011
Exemplo
Consulta SQL:
SELECT LNAME
FROM EMPLOYEE, WORKS_ON, PROJECT
WHERE PNAME = ‘AQUARIUS’ AND PNUMBER=PNO AND
ESSN=SSN AND BDATE > ‘DEC-31-1957’;
Álgebra Relacional (Expressão Canônica):
pipipipiLNAME (σσσσPNAME=‘AQUARIUS’ AND PNUMBER=PNO AND ESSN=SSN AND BDATE>‘DEC-31-1957’
(EMPLOYEE × WORKS_ON × PROJECT))
7
Introdução a Banco de Dados – DCC 011
Exemplo: etapa 1
A árvore canônica 
é construída 
diretamente a 
partir da consulta 
SQL
Introdução a Banco de Dados – DCC 011
Exemplo: etapa 2
A condição de seleção é
desmembrada e as duas 
operações de seleção 
(sobre BDATE e PNAME) 
são aplicadas antes dos 
produtos cartesianos, 
para reduzir o número 
de tuplas resultantes
8
Introdução a Banco de Dados – DCC 011
Exemplo: etapa 3
As posições das relações 
EMPLOYEE e PROJECT 
são trocadas para que a 
condição de seleção 
mais restritiva 
(PNAME=‘Aquarius’) 
seja executada primeiro
Introdução a Banco de Dados – DCC 011
Exemplo: etapa 4
Produtos cartesianos 
seguidos de seleção 
são substituídos por 
junções
9
Introdução a Banco de Dados – DCC 011
Exemplo: etapa 5
A cada passo, são 
mantidas apenas os 
atributos necessários 
(operações de projeção 
são deslocadas para 
baixo)
Introdução a Banco de Dados – DCC 011
Regras de Transformação
� R1. Cascata de seleções: 
σ<cond1 E cond2 E ... E condn>(R) = 
σ<cond1>(σ<cond2>(... σ<condn>(R)) 
� R2. Comutatividade de seleções:
σ<cond1>(σ<cond2>(R)) = σ<cond2>(σ<cond1>(R))
� R3. Cascata de projeções:
pi<lista1>(pi<lista2>(R)) = pi<lista1>(R)
� R4. Comutatividade da seleção e projeção
pi<lista>(σ<cond>(R)) = σ<cond>(pi<lista>(R)) 
10
Introdução a Banco de Dados – DCC 011
Regras de Transformação (cont.)
� R5. Comutatividade da junção e do produto 
cartesiano
R × S = S × R R S = S R
� R6. Comutatividade da seleção e junção ou 
produto cartesiano (θ = { , ×})
σ<cond>(R θ S) = (σ<cond>(R)) θ S 
� R7. Comutatividade da projeção e junção ou 
produto cartesiano (θ = { , ×}) 
pi<lista>(R θ S) = (pi<listaR>(R)) θ (pi<listaS>(S))
� R8. Comutatividade da união e da interseção 
R ∪ S = S ∪ R R ∩ S = S ∩ R
Introdução a Banco de Dados – DCC 011
Regras de Transformação (cont.)
� R9. Associatividade da junção, produto cartesiano, 
união e interseção (θ = { , × , ∪ , ∩})
(R θ S) θ T = R θ (S θ T)
� R10. Comutatividade da seleção e das operações 
de conjunto (união, interseção e diferença) 
σ<cond>(R θ S) = σ<cond>(R) θ σ<cond>(S)
� R11. Comutatividade da projeção e união
pi<lista>(R ∪ S) = pi<lista>(R) ∪ pi<lista>(S)
� R12. Conversão da sequência seleção/produto 
cartesiano em junção 
σc(R × S) = R c A
11
Introdução a Banco de Dados – DCC 011
Passos para Otimização de uma 
Árvore Canônica do Tipo SPJ
1. Usando a regra R1, desmembre a condição (conjuntiva) 
da operação de seleção.
2. Usando as regras R2 e R6, reposicione as condições de 
seleção e junção de forma que elas possam ser aplicadas 
o mais cedo possível.
3. Usando as regras R5 e R9, reposicione as relações de 
forma que condições de seleção mais restritivas possam 
ser aplicadas mais cedo.
4. Usando a regra R12, converta as sequências de 
operações de seleção e produto cartesiano em junções.
5. Usando as regras R3, R4 e R7, desmembre a lista de 
atributos da operação de projeção de forma que 
operações de projeção específicas possam ser 
executadas mais cedo.
Introdução a Banco de Dados – DCC 011
Exercício
Seja o banco
de dados de uma livraria representado pelo seguinte esquema relacional:
Editora(CodEditora,NomeEditora)
Livro(CodLivro,Titulo,Autor,Assunto,AnoPub,CodEditora)
Instituicao(CodInst,NomeInst,Sigla,Local)
Adotado-por(CodLivro,CodInst,AnoAdocao)
Dada a consulta SQL
SELECT NomeInst FROM Instituicao
WHERE CodInst IN
(SELECT CodInst FROM Adotado-por
WHERE AnoAdocao = ‘2007’ AND CodLivro IN
(SELECT CodLivro FROM Livro
WHERE Assunto = ‘Portugues’ AND CodEditora IN
(SELECT CodEditora FROM Editora
WHERE NomeEditora = ‘Editora Campus’)))
reescreva-a de forma não-aninhada, gere a sua árvore canônica e, usando as regras de 
transformação, derive a árvore de consulta que corresponda à sequência de operações 
da álgebra relacional mais eficiente para a sua execução.