View
109
Download
4
Category
Preview:
Citation preview
Algoritmos Aleatórios Para Optimização de consultas
Artigo apresentado por:Daniel Martins 110370082David 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
Recommended