PBD - 07 - Otimização de consultas

Prévia do material em texto

Práticas em Práticas em 
Banco de Dados Banco de Dados 
Práticas em Práticas em 
Banco de Dados Banco de Dados 
Parte 7 – Otimização de Consultas
Professor Eduardo Xavier
Parte 7 – Otimização de Consultas
Professor Eduardo Xavier
Módulo Processador de Módulo Processador de 
ConsultasConsultas
• Objetivo: Otimização do processamento de uma consulta.
• Tradução, transformação e geração de uma estratégia (plano) de execução
• Estratégia de acesso:
• Leva em conta algoritmos predefinidos para implementação de passos do 
processamento e estimativas sobre os dados
• Vale a pena todo este esforço? Sim!
• Tx = tempo para definir e executar uma estratégia otimizada de processamento
• Ty = tempo para executar uma estratégia não-otimizada de 
processamento
• Quase sempre: Tx < Ty
Processamento de ConsultasProcessamento de Consultas
• Consulta SQL
• É adequada para uso humano, porém não é adequada para processamento pelo 
SGBD, porque:
• Não descreve uma sequência de passos (procedimento) a ser seguida
• Não descreve uma estratégia eficiente para a implementação de cada passo no 
que diz respeito ao acesso a nível físico (arquivos do BD)
• O SGBD deve se preocupar com este processamento!
• Quem faz isso? O módulo Processador de Consultas
Etapas do ProcessamentoEtapas do Processamento
Tradução
Transformação
Definição do 
Plano de Execução
Consulta em linguagem de alto nível
(Exemplo: consulta SQL)
Representação interna
(árvore algébrica da consulta)
Representação transformada
(árvore otimizada algebricamente)
Plano de Execução
(árvore com indicação de estratégias de acesso)
Processador Run-timeGerador de Código Código de 
Execução
Resultado da Consulta
Etapas do ProcessamentoEtapas do Processamento
Tradução
Transformação
Definição do 
Plano de Execução
Consulta em linguagem de alto nível
(Exemplo: consulta SQL)
Representação interna
(árvore algébrica da consulta)
Representação transformada
(árvore otimizada algebricamente)
Plano de Execução
(árvore com indicação de estratégias de acesso)
Processador Run-timeGerador de Código Código de 
Execução
Resultado da Consulta
• Análise léxica
• Cláusulas SQL e nomes válidos
• Análise sintática 
• Validação da gramática
• Análise semântica 
• Nomes usados de acordo com a 
estrutura do esquema
• Conversão para uma árvore 
algébrica da consulta
Processamento de ConsultasProcessamento de Consultas
• O que é uma árvore algébrica de consulta?
• É uma estrutura que representa o mapeamento da consulta para a álgebra 
relacional (uma expressão da álgebra relacional “estendida”)
• Pode indicar alguma computação (função agregação, atributo calculado, ...)
• Nodos folha: relações (do BD ou resultados intermediários)
• Nodos internos: operações da álgebra
• Processamento da árvore
• Nodos internos são executados quando seus operandos estão disponíveis
• São substituídos pela relação resultante
• A execução termina quando o nodo raiz é executado
Processamento de ConsultasProcessamento de Consultas
• Exemplo de árvore algébrica 
de consulta
select m.CRM, m.nome, a.número, a.andar
from Médicos m, Ambulatórios a
where m.especialidade = ‘ortopedia’
and a.andar = 2
and m.número = a.número
Etapas do ProcessamentoEtapas do Processamento
Tradução
Transformação
Definição do 
Plano de Execução
Consulta em linguagem de alto nível
(Exemplo: consulta SQL)
Representação interna
(árvore algébrica da consulta)
Representação transformada
(árvore otimizada algebricamente)
Plano de Execução
(árvore com indicação de estratégias de acesso)
Processador Run-timeGerador de Código Código de 
Execução
Resultado da Consulta
• Definição de uma árvore de consulta 
equivalente
• Chega ao mesmo resultado, porém 
processa de forma mais eficiente
• Este processo também é conhecido 
como Otimização Algébrica
Processamento de ConsultasProcessamento de Consultas
• Exemplo de árvore equivalente
Etapas do ProcessamentoEtapas do Processamento
Tradução
Transformação
Definição do 
Plano de Execução
Consulta em linguagem de alto nível
(Exemplo: consulta SQL)
Representação interna
(árvore algébrica da consulta)
Representação transformada
(árvore otimizada algebricamente)
Plano de Execução
(árvore com indicação de estratégias de acesso)
Processador Run-timeGerador de Código Código de 
Execução
Resultado da Consulta
• Análise de alternativas de definição de 
estratégias de acesso
• Escolha de algoritmos para 
implementação de operações
• Existência de índices
• Estimativas sobre os dados (tamanho 
de tabelas, seletividade, ...)
Processamento de ConsultasProcessamento de Consultas
• Exemplo de Plano de Execução
Etapas do ProcessamentoEtapas do Processamento
Tradução
Transformação
Definição do 
Plano de Execução
Consulta em linguagem de alto nível
(Exemplo: consulta SQL)
Representação interna
(árvore algébrica da consulta)
Representação transformada
(árvore otimizada algebricamente)
Plano de Execução
(árvore com indicação de estratégias de acesso)
Processador Run-timeGerador de Código Código de 
Execução
Resultado da Consulta
FOCO:
OTIMIZADOR DE 
CONSULTA
Otimização HeurísticaOtimização Heurística
• “A arte ou a ciência do descobrimento”
• As regras de heurística para otimização de consulta utilizam 
expressões equivalentes para transformar a árvore inicial na 
árvore de consulta otimizada final.
• Vamos tomar como exemplo a transformação da seguinte 
consulta:
SELECT E.UNOME 
FROM EMPREGADO E, TRABALHA_EM T, PROJETO P
WHERE P.PNOME=“AQUARIUS” AND P.PNUMERO=T.NRP 
 AND T.ESSN=E.SSN AND E.DATANASC > “31-12-1957”;
Otimização HeurísticaOtimização Heurística
Transformação de Uma ConsultaTransformação de Uma Consulta
Otimização HeurísticaOtimização Heurística
Transformação de Uma ConsultaTransformação de Uma Consulta
Otimização HeurísticaOtimização Heurística
Transformação de Uma ConsultaTransformação de Uma Consulta
Otimização HeurísticaOtimização Heurística
Transformação de Uma ConsultaTransformação de Uma Consulta
Otimização HeurísticaOtimização Heurística
Transformação de Uma ConsultaTransformação de Uma Consulta
Otimização AlgébricaOtimização Algébrica
• Também acontece durante a etapa de Transformação
• Entrada: árvore de consulta inicial
• Saída: árvore de consulta otimizada
• Importante: pode acontecer das árvores de entrada e saída serem idênticas
• Base:
• Regras de equivalência algébrica
• Devem ser conhecidas pelo otimizador para que possam ser geradas 
transformações válidas
• Algoritmo de otimização algébrica
• Indica a ordem de aplicação das regras e de outros processamentos de 
otimização
Referências BibliográficasReferências Bibliográficas
ELSMARI, Ramez & NAVATHE, Shamkant B. Sistema de Banco de Dados. 
Rio de Janeiro: Editora Addison-Wesley. 4ª. edição, 2005, 744p.
	Slide 1
	Módulo Processador de Consultas
	Processamento de Consultas_clipboard0
	Etapas do Processamento_clipboard1
	Etapas do Processamento_clipboard2
	Processamento de Consultas_clipboard3
	Processamento de Consultas_clipboard4
	Etapas do Processamento_clipboard5
	Processamento de Consultas_clipboard6
	Etapas do Processamento_clipboard7
	Processamento de Consultas
	Etapas do Processamento
	Otimização Heurística
	Otimização Heurística Transformação de Uma Consulta_clipboard8
	Otimização Heurística Transformação de Uma Consulta_clipboard9
	Otimização Heurística Transformação de Uma Consulta_clipboard10
	Otimização Heurística Transformação de Uma Consulta
	Slide 18
	Otimização Algébrica
	Referencias Bibliográficas