Otimização de Consultas em Banco de Dados

Prévia do material em texto

Disciplina: Banco de Dados II
Prof: Aglaê Pereira Zaupa
Otimização de Consultas
Unoeste – Universidade do Oeste Paulista
FIPP – Faculdade do Oeste Paulista
Otimização de Consultas
Necessidade de Otimização
� Por que otimizar uma consulta?
� A mesma consulta a uma base de dados pode 
ser expressa por meio de muitas expressões de 
álgebra relacional diferentes
� O ideal é que o tempo de execução de 
diferentes expressões seja idêntico
� O programador não deve necessitar de 
conhecimentos acerca do funcionamento interno 
do SGBD
Otimização de Consultas
Necessidade de Otimização
� SQL – utilizada pela maioria dos SGBDR
� A consulta deve passar por uma análise léxica, 
sintática e ser validada. Depois uma 
representação interna da consulta é criada (p.e. 
árvore de consulta)
� O SGBD deve planejar uma estratégia de 
execução . O processo de escolha da estratégia 
adequada para o processamento da consulta é 
a otimização
Otimização de Consultas
Necessidade de Otimização
� Estratégias de otimização
� Otimização Heurística – ordenação das operações 
em uma estratégia de execução de consulta
� Estimativa sistemática de custo – envolve o custo das 
diferentes estratégias de execução e da escolha do 
plano de execução com o menor custo estimado
� Combinação das estratégias
utilizando
Otimização de Consultas
Necessidade de Otimização-Exemplo
� Exemplo de consulta sobre um BD acadêmico:
� Obter os nomes dos alunos que cursaram com conceito 
“A“ uma disciplina do curso de nome “Computação" que 
ofereça mais de 5 créditos
� Uma solução possível:
π NomeAl
(σ (NomeCurso = “Computação” and
Conceito = "A"and
CreditosDisc > 5)
(Aluno X
(Historico X
(Disciplina X
(Curric X Curso) )))
Otimização de Consultas
Necessidade de Otimização
Expressão Alternativa
π NomeAl
(Aluno
X
(σ (Conceito = "A") Historico
X
(σ (NomeCurso = “Computação”) Curso
X
(Curric X (σ CreditosDisc > 5) Disciplina ))))
Otimização de Consultas
Otimização Algébrica (heurística)
� Baseia-se em regras heurísticas (“achismo" ou 
“achamento”☺) de transformação de 
expressões relacionais
� Objetivo:
� obter expressões de álgebra relacional equivalentes 
à consulta original e cuja execução direta demande 
menos tempo e menos recursos de máquina
� Regra geral de otimização:
� diminuir os resultados intermediários
Highlight
Otimização de Consultas
Otimização Heurística – Como fazer
� Montar um plano de execução de consulta para executar 
grupos de operações com base nos caminhos de 
acesso disponíveis
� Executar seleções e projeções o mais cedo possível
� Essas operações geram resultados menores (menos linhas e/ou 
menos colunas) que seus operandos
� Executar operações binárias o mais tarde possível
� Operações binárias aumentam o volume de dados (efeito 
multiplicativo) e são onerosas em termos de tempo de execução
� Sempre que possível, transformar operações de produto 
cartesiano em operações de junção
Highlight
Otimização de Consultas
Árvore de Consulta 
Plano de execução
� Para visualizar a otimização algébrica, é conveniente 
representar as consultas em forma de árvore
π NomeAl
σ NomeCurso=“Computação” AND conceito=“A” AND CredDisc > 5
X
Aluno X
Historico
X
Disciplina X
Curriculo Curso
https://www.macoratti.net/13/06/sql_arcb.htm
Otimização de Consultas
Árvore de Consulta 
Segunda Expressão
� A segunda expressão de álgebra relacional para a mesma consulta 
é representada pela árvore abaixo
π NomeAl
X
Aluno
X
σ conceito=“A”
Historico Curriculo
X
σ Credito > 5
Disciplina
X
σ NomeCurso=“Computação”
Curso
Otimização de Consultas
Exemplo de Otimização
� Consulta sobre o BD acadêmico
� Obter os nomes dos alunos que obtiveram conceito “E" em 
disciplina denominada “Programação I"
� Expressão em álgebra:
π NomeAl
(σ NomeDisc = 'Programação I' and
Conceito='E' and
Aluno.CodAl = Historico.CodAl and
Historico.CodDisc = Disciplina.CodDisc)
(Aluno X (Historico X Disciplina) )
Otimização de Consultas
Árvores de consulta 
Expressão original
π NomeAl
σ NomeDisc=“ProgramaçãoI” AND conceito=“E” AND 
Aluno.codAl=Historico.CodAl AND
Historico.CodDisc = Disciplina.CodDisc
X
Aluno X
Historico Disciplina
Otimização de Consultas
Árvores de consulta 
1ª otimização
π NomeAl
σσσσ (Aluno.codAl=Historico.CodAl)
Aluno
HistoricoDisciplina
σσσσ (conceito=“E”)
σσσσ (Historico.CodDisc = Disciplina.CodDisc)
σσσσ (NomeDisc=“ProgramaçãoI”)
X
X
Otimização de Consultas
Árvores de consulta 
2ª otimização
π NomeAl
(Aluno.codAl=Historico.CodAl)
Aluno
HistoricoDisciplina
σ (conceito=“E”)
(Historico.CodDisc = 
Disciplina.CodDisc)
σ (NomeDisc=“ProgramaçãoI”)
Otimização de Consultas
Árvores de consulta 
3ª otimização
π NomeAl
(Aluno.codAl=Historico.CodAl)
Aluno
HistoricoDisciplina
σ (conceito=“E”)
(Historico.CodDisc = Disciplina.CodDisc)
σ (NomeDisc=“ProgramaçãoI”)
ππππ CodAl
ππππ CodDisc ππππ CodAl, CodDisc
Otimização de Consultas
Otimização com base em estimativas de 
custo
� A otimização heurística não leva em conta volumes de dados nem 
tempos de acesso 
� Com isso, pode gerar árvores de consulta menos eficientes
� Exemplo:
� Caso a tabela de alunos fosse consideravelmente menor que as 
demais, poderia ser mais eficiente incluí-la na primeira operação de 
junção
� Otimização baseada em estimativas de custo
� Para diferentes árvores de consulta, equivalentes do ponto de vista das 
regras heurísticas, é escolhida uma que se estima ter o menor custo de 
implementação
� Custo = volume de acesso a disco
� Como é oneroso verificar volumes de dados a cada transação, 
normalmente o SGBD coleta dados estatísticos sobre as tabelas 
(número de linhas, número de valores diferentes por coluna, ...)
Otimização de Consultas
Otimização em Produtos Comerciais
� Informix 5.0, Ingres 6.4, Oracle 7.0 e Sybase 4.9 usam otimização 
heurística
� Todos combinam otimização heurística com estimativas de custo baseadas 
em estatísticas coletadas pelo próprio SGBD
� Todos mantém estatísticas sobre as tabelas
� Ingres procura manter estatísticas sobre distribuição de valores em colunas 
(mínimo, média, máximo)
� Oracle e Ingres podem coletar estatísticas por amostragem em tabelas, 
evitando a varredura completa da tabela
� Nenhum otimizador usa custos de transmissão dos dados na rede nas 
estimativas de custo
� Oracle, Ingres e Informix são capazes de mover pequenas tabelas locais 
para estações remotas, onde ocorrerá a junção com grandes tabelas
� Oracle permite que o desenvolvedor defina dicas para o otimizador
Otimização de Consultas
Exercício
� Considerando a consulta abaixo desenhe a árvore de 
consulta inicial depois mostre como a árvore é otimizada 
por meio das regras heurísticas
SELECT EMP_CODIGO, EMP_NOME, EMP_ENDERECO
FROM EMPREGADO, DEPTO
WHERE DEPTO.DEP_NOME=“FIPP” AND
DEPTO.DEP_NUMERO=EMPREGADO.DEP_NUMERO