Algoritmos Aleatórios Para
Optimização de consultas
Artigo apresentado por:
Daniel Martins 110370082
David Martins 080316033
Introdução
• Optimização de Queries é um processo
dispendioso.
• Algoritmos Aleatórios aplicados problemas de
optimização combinatória:
– Simulated Annealing
– Iterative Improvement
Algoritmos Aleatórios
• Cada solução para um problema de
optimização pode ser pensado como um
estado
• Cada estado tem um custo associado
• O seu objectivo é encontrar o estado com
minímo custo global
• Existem 2 tipos de movimentos associado ao
estado :
– DownHill
– UpHill
• Minímo Local
• Minímo Global
Algoritmo Iterative Improvement
• Uma optimização começa num estado
aleatório
• Implementa a solução através de sucessivos
movimentos downHill até encontrar o minímo
local
• Repete-se indefinidamente até encontrar uma
condição de paragem
Algoritmo Simulated Annealing
• Aceita movimentos upHill
• O loop interior do algoritmo é chamado
estado
• Cada estado é executado através do
parâmetro temperatura
• Temperatura controla movimentos upHill
• Cada estado termina quando atinge o
equilibrio
Algoritmo Two Phase Optimization
• É uma combinação dos 2 algoritmos
anteriores
• Fase 1:
– O II corre durante um pequeno período de tempo
• Fase 2:
– O SA corre com uma temperatura baixa inicial
Estado de Espaço
• Corresponde a uma estratégia de acessos para
uma consulta ser optimizada
• Join Processing Tree
– Folhas são as relações base
– Nós internos são operadores join
– Arestas indicam o fluxo da informação
Função Vizinho
Função Custo
• É utilizada apenas para a entrada e saída de
cada estratégia de dados.
• É baseada nas seguintes suposições:
– Sem pipelining
– Buffering minímo para todas as operações
– Execução on-the-fly nas projecções
Comportamento como uma função do
tempo
Qualidade do Output
Tempo de optimização da Query
• Tamanho da query
• Variância nos parâmetros do catálogo
• Tipo de Query
Análise Estado de Espaço
• Um custo escalonado é o rácio de um custo de
uma estratégia sobre o custo minímo local.
• A média do rácio específico VS o menor custo
minímo local é afectada pela variância e pela
consulta.
• Podemos concluir que o maior minímo local
não de todo melhor que a média do estado
aleatório mas está relacionado com o custo de
pequenas variâncias
• Na experiência foram contados o número de
minímo locais visitados com custo distintos
• Para cada consulta mediu-se a distância a
distância média entre 2 minímos locais
visitados
Explicação do comportamento como
uma função do tempo
• SA começa com um estado aleatório que
tende para um custo de área elevado
– Temperatura mantém-se elevada
– Grande número de movimentos upHill
– Grande probabilidade de aceitar movimentos
upHill
• II consegue descobrir o minímo local apenas
com algumas optimizações locais
• Consegue atingir rapidamente o fundo através
de movimentos downHill
• 2PO atinge rapidamente o fundo (fase II)
• 2PO melhora rapidamente procurando na área
(fase SA)
• Termina em menor tempo em relação aos
outros 2 algoritmos
Conclusões
• Foram utilizados 2 algoritmos SA e II para
optimização de grandes join queries
• II é melhor que o SA inicialmente, ao longo do
tempo SA consegue superar o II
• Foi realizado o estudo da função custo sobre o
espaço de estado da query
• Através disto explicou-se o comportamento do
2 algoritmos
• Conclui-se que o 2PO tem performance
superior aos outros 2 algoritmos