Algoritmos de Processamento e Otimização de Consultas

Adriano Douglas GirardelloAna Paula Fredrich

Tiago Alexandre Schulz Sippert

1 Introdução

Este trabalho aborda as técnicas utilizadas por um Sistema Gerenciador de Banco de Dados para processar, otimizar e executar consultas

de alto nível

2 Passos do Processamento de uma Consulta

Análise Léxica Análise Sintática Validação das análises Otimizador de Consulta Gerador de código Processador em tempo de execução

Pode ser gerado erro nesta etapa

2 Passos do Processamento de uma Consulta: Quatro Estágios

Moldar a Consulta em Alguma Forma Interna Converter para a Forma Canônica Escolher Procedimentos Candidatos de Baixo

Nível Gerar Planos de Consultas e Escolher o mais Econômico

2.1 Moldar a Consulta em Alguma Forma Interna

Conversão da consulta original para manipulação pela máquina, eliminando peculiaridades

Podem ser escolhidas Árvore de Sintaxe Abstrata Árvore de Consulta

Em geral é escolhida álgebra relacional

2.2 Converter para a Forma Canônica

Otimizações não referentes aos valores dos dados ou aos acessos físicos

Regras de transformação Várias formas de escrita de uma consulta Converter a representação original para uma

mais eficiente

2.3 Escolher Procedimentos Candidatos de Baixo Nível

Como executar a consulta Levar em consideração

Existência de índices, caminhos de acesso Agrupamento físico, distribuição dos valores

Para cada operação de baixo nível existem vários procedimentos implementados

Cada procedimento tem a fórmula de custo O otimizador escolhe qual procedimento

implementar para cada operação de baixo nível

2.4 Gerar Planos de Consultas e Escolher o mais Econômico

Elaborado um conjunto de planos de consulta Escolhido o melhor desses planos Muitos planos candidatos Tarefa de escolha demorada Limite de planos gerados Atribuição de peso de execução (soma dos

custos individuais) Avaliação dos resultados individuais

3 Traduzindo Consultas SQL para Álgebra Relacional

Linguagem SQL utilizada na maioria dos bancos comerciais

Cada consulta SQL é composta de blocos de consultas, que formam as unidades básicas

Unidade básica é transformada e otimizada

4 Algoritmo para Ordenação Externa

Ordenação é um dos algoritmos principais Utilizado quando ocorre ORDER BY Também utilizado em:

JOIN UNION INTERSECTION PROJECT

Adequada para registros grandes que não cabem totalmente em memória

4 Algoritmo para Ordenação Externa

Utiliza ordenação sort-merge Ordena primeiramente sub-arquivos Após faz a fusão nos sub-arquivos Exige espaço de buffer na memória

5.1 Implementação da Operação SELECT

Várias opções de implementação Podem ser divididos em:

Métodos de busca para seleção simples Métodos de busca para seleções complexas

O otimizador deve escolher o método apropriado para cada operação SELECT

Escolha do método com o menor custo estimado

5.1.1 Métodos de Busca para Seleções Simples

S1 Busca Linear: Força Bruta S2 Busca Binária S3 Utilização de Índice Primário: Chave Hash S4 Utilização de Índice Primário para

Recuperar Registros Múltiplos S5 Utilização de um Índice Cluster para

Recuperação de Múltiplos Registros S6 Utilização de um Índice Secundário em uma

Comparação de Igualdade

5.1.2 Métodos de Busca para Seleções Complexas

S7 Seleção Conjuntiva Utilizando um Índice Individual

S8 Seleção Conjuntiva Utilizando um Índice Composto

S9 Seleção Conjuntiva por Meio da Integração de Registros

5.1 Implementação da Operação SELECT

Se existir caminho de acesso direto O método correspondente é utilizado

Se não existir caminho É utilizado força bruta para escolha

Otimizar consultas de seleção conjuntiva (AND) Otimizador sempre escolhe a consulta que

retorna o menor número de registros Seleção disjuntiva é muito mais difícil de

otimizar (OR)

5.2 Implementação da Operação JOIN

Uma das operações que mais consome tempo de consulta

Possibilidade de duas ou mais vias (dois ou mais arquivos)

O número de maneiras para executar as junções múltiplas aumenta rapidamente

5.2.1 Métodos para a Implementação de Junções

J1 Junção de Laços Aninhados J2 Junção de Laço Único J3 Junção Sort-Merge J4 Junção-Hash

5.2.2 Efeitos da Disponibilidade de Espaço de Buffer

Efeito importante sobre operações de junção Tamanho do buffer

Ler para a memória a quantia máxima de blocos do arquivo Reduz o número de acessos ao disco

Quando o buffer está cheio ele é escrito no disco

6 Combinação de Operações Usando Pipelines

Cada SQL é traduzida em uma expressão composta de várias operações

Cada operação gera arquivos temporários gerando sobrecarga excessiva

Utilizar códigos de execução correspondentes que realizem uma só consulta

Criar dinamicamente código de execução Conforme resultado é produzido pode ser

utilizado para as próximas operações

7 Utilização de Heurísticas na Otimização de Consultas

Regras heurísticas para muda representação interna

Otimizado a partir da análise sintática Uma das principais heurísticas é utilizar

SELECT e PROJECT antes de aplicar o JOIN As operações SELECT e PROJECT reduzem o

tamanho do arquivo de entrada para o JOIN

7.1 Notações de Árvores de Consulta e de Grafos de Consultas

Árvore de consulta: Estrutura de dados de árvore correspondente a

uma expressão algébrica relacional Representa relações de entrada como nós folhas e

operações como nós internos Execução dos nós internos até chegar à raiz No final produz a relação de resultados da

consulta

7.2 Conversões de Árvores de Consulta em Planos de Execução

de Consultas O plano de execução inclui informações sobre

os métodos de acesso disponíveis para cada relação

Inclui algoritmos a serem utilizados na computação dos operadores

8 Utilização de Seletividade e Estimativa de Custo na Otimização

de Consultas Otimizador não deve depender somente de

heurísticas Estimar e comparar custos usando diferentes

estratégias Escolher a estratégia com menor custo Estimativas precisas são necessárias Comparação de maneira correta e realista Limitar número de estratégias

8.1 Componentes do Custo para a Execução de uma Consulta

1. Custo de Acesso ao Armazenamento Secundário

2. Custo de Armazenamento 3. Custo de Computação 4. Custo de Uso de Memória 5. Custo de Comunicação

9 Otimização Semântica de Consultas

Utilização de restrições no banco de dados para tornar uma consulta mais eficiente

Pode ser utilizada em conjunto com as outras técnicas

Otimizador semântico verifica a existência de restrições. Dependendo das restrições ele modifica a consulta

ou nem a executa Economiza tempo considerável de

processamento

9 Otimização Semântica de Consultas

Número de restrições X Tempo de execução Pesquisar muitas restrições para ver quais são

aplicadas realmente Bancos de Dados Futuros:

Técnicas de otimização semântica podem ser incorporadas totalmente ao SGBD

10 Otimização Física

Pode ser dividido em dois discos Permite acessos paralelos Escolha de boa distribuição dos dados Fatiamento de disco:

Divide as tuplas de relações individuais entre os diversos discos

Ligação física ótima difere entre consultas Administrador do BD escolhe melhor ligação

11 Estatísticas de Bancos de Dados

Utilizado na seleção de caminhos de acesso Uso das chamadas estatísticas no catálogo Listamos estatísticas em dois exemplos:

DB2 Ingres

Tais estatísticas são usadas para entender como o banco é usado e como otimizá-lo

11.1 Estatísticas do BD2

Para cada tabela básica: Cardinalidade Número de páginas ocupadas por esta tabela Fração de "espaço de tabela" ocupado

Para cada coluna de cada tabela básica: Número de valores distintos nesta coluna Segundo valor mais alto nesta coluna Segundo valor mais baixo nesta coluna Somente para colunas indexadas, os dez valores

que ocorrem com maior freqüência nesta coluna

11.1 Estatísticas do BD2

Para cada índice: Uma indicação quanto a ser este um "índice de

agrupamento" (isto é, um índice usado para agrupar dados logicamente relacionados em posições fisicamente contíguas no disco).

Se for o caso, a fração da tabela indexada ainda em seqüência de agrupamento em cluster.

Número de páginas por folhas neste índice. Número de níveis neste índice.

11.2 Estatísticas do Ingres

Para cada tabela básica: Cardinalidade Número de páginas primárias para esta tabela Número de páginas de overflow para esta tabela

Para cada coluna de cada tabela básica: Número de valores distintos nesta coluna Valores máximo, mínimo e médio para esta coluna Valores efetivos nesta coluna e o número de vezes

em que eles ocorrem.

Conclusões

Existem muitos métodos de otimização Métodos de otimização são importantes:

Reduzem tempo de execução Reduzem custos de processamento Melhoram o desempenho em geral

Existem muitos inibidores ao tentar realizar otimizações no processamento de consultas

Inibidores impedem que o otimizador faça uma consulta tão boa quanto poderia