Algoritmos de Processamento e
Otimização de Consultas
Adriano Douglas Girardello
Ana 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


Se não existir caminho




O método correspondente é utilizado
É 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


Ler para a memória a quantia máxima de
blocos do arquivo


Tamanho do buffer
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