Banco de Dados I
2007
Módulo VI: Processamento e
Otimização de Consultas
(Aulas 1-5)
Clodis Boscarioli
Agenda:
O Processador de Consultas:
Conceitos Principais.
Algoritmos usados para implementar operações
algébricas;
Otimização Baseada em Custo;
Otimização Heurística;
Comentários sobre otimização no PostgreSQL.
Visão Geral
de um SGBD
Processador
de consultas
Usuários
navegantes
Programadores Usuários
Administrade aplicações sofisticados dores de BD
Interface com Programas de
aplicações
aplicações
Consultas
(queries)
Pré-compilador
de comandos
DML
Programas de
aplicações em
código objeto
Usuários
Esquema de
Banco de Dados
Compilador
DML
Interpretador
DDL
Componentes de execução
de consultas
SGBD
Gerenciador
de memória
Gerenciador
de transações
Gerenciador
de buffer
Gerenciador
de arquivos
Armazenamento
em disco
Índices
Arquivos de
dados
Dados
estatísticos
Dicionário
de dados
BD
Processamento de Consultas
Processar consultas envolve:
Traduzir consultas expressas em linguagens
de alto nível (como SQL) em expressões que
podem ser implementadas no nível físico do
sistema de banco de dados (nível de tabelas);
Otimizar a expressão destas consultas;
Avaliar a base de dados de acordo com as
diretrizes da consulta, para fornecer o
resultado.
Processamento de Consultas
Consulta SQL
É adequada para uso humano;
Não adequada ao processamento pelo SGBD:
Não descreve uma seqüência de passos
(procedimento) a ser seguida;
Não descreve uma estratégia eficiente para a
implementação de cada passo no que tange o
acesso em nível físico (arquivos do BD).
Cabe ao SGBD deve se preocupar com este
processamento módulo Processador de Consultas.
Módulo Processador de Consultas
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:
Considera algoritmos predefinidos para implementação de
passos do processamento e estimativas sobre os dados.
O esforço é valido, pois quase sempre
Tx << Ty
Tx = Tempo para definir e executar uma estratégia
otimizada de processamento;
Ty = Tempo para executar uma estratégia nãootimizada de processamento.
Passos no Processamento de Consultas
Consulta
Analisador
sintático
e tradutor
Expressão
algébrica
relacional
Otimizador
Saída da
Avaliador
consulta
Dados
Plano de
execução
Metadados
Passos no Processamento de Consultas
Consulta
Analisador
sintático
e tradutor
Expressão
algébrica
relacional
Otimizador
• Análise léxica
- cláusulasSaída
SQL
da e nomes válidos.
Avaliador
consulta
• Análise sintática
- validação da gramática.
• Análise semântica
- nomes usados de acordo com a estrutura
do esquema.
Dados
• Conversão para uma árvore algébrica
da consulta
Plano de
execução
Metadados
Passos no Processamento de Consultas
Consulta
Analisador
sintático
e tradutor
Expressão
algébrica
relacional
Otimizador
• Definição de uma árvore de
consulta equivalente
Saída da
Avaliador
- chega ao mesmo
resultado
consulta
- processa de forma mais
eficiente
• Fase chamada de
Otimização Algébrica
Dados
Plano de
execução
Metadados
Passos no Processamento de Consultas
Análise de alternativas de definição de
Analisador
estratégias de acesso
sintático
- escolha de Consulta
algoritmos para
e tradutor
implementação de operações
- existência de índices
- estimativas sobre os dados
(tamanho de tabelas, seletividade, ...)
Saída da
Avaliador
consulta
Dados
Expressão
algébrica
relacional
Otimizador
Plano de
execução
Metadados
Passos no Processamento de Consultas
Consulta
Analisador
sintático
e tradutor
FOCO:
OTIMIZADOR DE
CONSULTA
Saída da
Expressão
algébrica
relacional
Otimizador
Avaliador
consulta
Dados
Plano de
execução
Metadados
Exemplo Introdutório
Suponha a consulta:
select saldo
from conta
where saldo < 2500;
Esta pode ser traduzida nas duas expressões algébricas
relacionais diferentes:
σ
saldo < 2500 (π saldo (conta))
π saldo (σ saldo < 2500(conta))
Exemplo Introdutório
Além desta variação, é possível executar cada operação
algébrica relacional usando um entre diversos
algoritmos diferentes. Por exemplo:
Para executar a seleção, podemos procurar em todas
as tuplas de conta a fim de encontrar as tuplas com
saldo menor 2.500.
Se um índice árvore-B+ estiver disponível no atributo
saldo, podemos usar o índice em vez de localizar as
tuplas.
É necessário prover as expressões algébricas de
anotações que permitam especificar como serão
avaliadas.
Exemplo Introdutório
Uma operação algébrica relacional anotada com
instruções sobre como ser avaliada é chamada
de avaliação primitiva.
Vária avaliações primitivas podem ser
agrupadas em pipeline, e executadas em
paralelo.
Uma seqüência de operações primitivas é um
plano de execução de consulta ou plano de
avaliação de consulta.
Exemplo Introdutório
πsaldo
σsaldo < 2500 (use índice 1)
conta
Uma vez escolhido o plano de consulta, a consulta é
avaliada com aquele plano e o resultado da consulta é
produzido
Otimização de Consultas
Existem 2 técnicas básicas para otimização de
consultas:
As baseadas em heurísticas para a ordenação de
acesso ao banco de dados, que participarão da
estratégia de acesso;
e as que estimam sistematicamente o custo de
estratégias de execução diferentes e escolhem o
plano de execução com o menor custo estimado.
Catálogo de Informações para Estimativa de
Custo
nr: é o número de tuplas na relação r;
br: é o número de blocos que contêm tuplas da relação r;
sr: é o tamanho em bytes de uma tupla da relação r;
fr: é o fator de bloco da relação r, ou seja, o número de
tuplas da relação r que cabe em um bloco;
V(A,r): é o número de valores distintos que aparecem na
relação r para o atributo A. Esse valor é igual ao
tamanho (em número de tuplas) de πA(r). Se A é uma
chave para a relação r, V(A,r) é nr.
Catálogo de Informações para Estimativa de
Custo
SC(A,r): é a cardinalidade de seleção (seletividade) do atributo A da
relação r.
Dados uma relação r e um atributo A da relação, SC(A,r) é o
número médio de registros que satisfazem uma condição de
igualdade no atributo A, dado que pelo menos um registro
satisfaz a condição de igualdade.
Exemplo:
SC(A,r) = 1 se A é um atributo-chave de r;
Para um atributo que não é chave, estimamos que os
valores distintos de V(A,r) são distribuídos uniformemente
entre as tuplas, produzindo SC(A,r) = (nr / V(A,r))
Catálogo de Informações para Estimativa de
Custo
As duas últimas estatísticas podem ser
estendidas de forma a valer para um conjunto
de atributos, ao invés de valer para apenas um
atributo.
Se as tuplas da relação r estiverem
armazenadas fisicamente juntas em um arquivo,
a seguinte equação é válida:
Br = [nr, fr]
Catálogo de Informações para Estimativa de
Custo
Informações sobre índices:
fi: é o fan-out (número de ponteiros) médio dos nós
internos do índice i para índices estruturados em
árvore, como árvores B+;
HTi: é o número de níveis no índice i, ou seja, a altura
do índice i.
LBi: é o número de blocos de índice de nível mais
baixo no índice i, ou seja, o número de blocos no
nível de folha do índice (o número de blocos que
contém os registros folha de um índice).
Catálogo de Informações para Estimativa de
Custo
As variáveis estatísticas são usadas para estimar o tamanho
do resultado e o custo para várias operações e algoritmos.
A estimativa de custo do algoritmo A é EA.
Para manter as estatísticas precisas, toda vez que uma
relação for modificada tem-se que atualizar as estatísticas.
Contudo, a maioria do sistema não atualiza as estatísticas em
todas as modificações. Atualiza-as periodicamente.
Quanto mais informações forem utilizadas para estimar o
custo da consulta e quanto mais precisas forem essas
informações, melhores serão as estimativas de custo.
Medidas do Custo de uma Consulta
O custo de uma consulta pode ser estimado de diversas formas:
Por acessos a disco;
Por tempo de uso da CPU;
Pelo tempo de comunicação nos BD paralelos
e/ou distribuídos;
O tempo de execução de um plano poderia ser usado para
estimar o custo da consulta, contudo em grandes sistemas de
BD, utiliza-se o número de acessos a disco, porque estes
estabelecem o tempo crítico de execução do plano (já que são
lentos quando comparados às operações realizadas em
memória).
Medidas do Custo de uma Consulta
Para simplificar nossos cálculos assumiremos que todas as
transferências de blocos (do disco para memória) têm o
mesmo custo. Desconsideraremos o tempo de latência e o
tempo de busca. Também desconsideramos o custo de
escrever o resultado final de uma operação de volta para o
disco.
Os custos dos algoritmos dependem significativamente do
tamanho do buffer na memória principal. No melhor caso,
todos os dados podem ser lidos para o buffer e o disco não
precisa ser acessado novamente. No pior caso, supomos
que o buffer pode manter apenas alguns blocos de dados
– aproximadamente um bloco por relação. Geralmente
faremos a suposição do pior caso.
Operação de Seleção
É a varredura de arquivos: o operador de mais baixo
nível para se ter acesso aos dados.
São algoritmos de procura que localizam e recuperam
os registros que estão de acordo com uma condição de
seleção.
Tem-se vários algoritmos diferentes, que variam de
acordo com a complexidade da seleção e o uso ou não
de índices.
Operação de Seleção
Exemplo de algoritmos usados na implementação do
operador select:
Busca Linear (ou força bruta);
Busca Binária;
Utilização de índice primário (atributo chave);
Utilização de índice primário para recuperar múltiplos
registros (atributo chave);
Utilização de um índice cluster para recuperar
múltiplos registros (atributo não chave);
Utilização de um índice secundário (Árvore B+) em
uma comparação de igualdade;
Busca para seleções complexas
Operação de Seleção
Busca para seleções complexas:
Se uma condição de uma instrução select é uma
condição conjuntiva – ou seja, é formada por diversas
condições simples conectadas pelo conectivo lógico
AND, o SGBD pode usar os seguintes métodos:
Seleção conjuntiva utilizando um índice individual;
Seleção conjuntiva utilizando um índice composto;
Seleção conjuntiva por meio da interseção de registros.
Operação de Seleção
Busca para seleções complexas:
Se uma condição de uma instrução select é uma
condição disjuntiva – ou seja, é formada por diversas
condições simples conectadas pelo conectivo lógico
OR, a otimização é mais simples.
Pouca otimização pode ser feita, pois os registros
que satisfazem a condição disjuntiva são a união dos
registros que satisfazem as condições individuais.
Operação de Seleção
Veremos dois deles (os básicos):
Aquele que envolve uma Busca Linear;
Aquele que envolve uma Busca Binária.
Considere uma operação de seleção em uma
relação cujas tuplas são armazenadas juntas
em um único arquivo.
Seleção por Busca Linear – A1
Em uma busca linear, cada bloco de arquivo é varrido e
todos os registros são testados para verificar se
satisfazem a condição de seleção.
Como todos os blocos precisam ser lidos, EA1 = br.
No caso da seleção ser aplicada em um atributo-chave,
podemos supor que a metade dos blocos é varrida antes
de o registro ser encontrado, ponto no qual a varredura
termina. A estimativa então será EA1 = (br/2).
Seleção por Busca Binária – A2
Se o arquivo é ordenado em um atributo e a condição de seleção é
uma comparação de igualdade neste atributo, podemos usar uma
busca binária para localizar os registros que satisfazem a seleção.
Neste caso, a estimativa é:
EA2 = [log2(br)] + [SC(A,r)/fr] -1
O primeiro termo [log2(br)] contabiliza o custo para localizar a
primeira tupla por meio da busca binária nos blocos;
O número total de registros que satisfarão a seleção é SC(A,r), e
esses registros ocuparão [SC(A,r)/fr] blocos, dos quais um já
havia sido recuperado (por isso o -1).
Se a condição de igualdade estiver em um atributo-chave, então
SC(A,r) = 1, e a estimativa se reduz a EA2 = [log(br)].
Cálculo do Custo da Busca Binária
Acesso aos blocos:
Primeiro acesso (ao bloco central) não encontro o registro
procurado;
Segundo acesso (ao bloco central do lado esquerdo ou direito)
....
Até o pior caso (nono acesso), o registro é encontrando na
última divisão disponível (ou não é encontrado).
Para 500 blocos:
500 250 125 62,5 31,25 15,62 7,8 3,9 1,9 (nove divisões)
Cálculo: log2(500) = 9 29 = 516 (=~ 500)
Exemplo de Seleção por Busca Binária
Suponha as seguintes informações estatísticas para uma relação
conta:
fconta = 20 (ou seja, 20 tuplas de conta cabem em um único
bloco);
V(nome_agência, conta) = 50 (ou seja, existem 50 agências
com nomes diferentes);
V(saldo, conta) = 500 (ou seja, existe 500 valores diferentes de
saldos nesta relação);
nconta = 10.000 (ou seja, a relação conta possui 10.000 tuplas).
Considere a consulta:
σ nome_agência = Perryridge (conta)
Exemplo de Seleção por Busca Binária
Como a relação tem 10.000 tuplas, e cada bloco mantém 20 tuplas, o
número de blocos é bconta = 500 (10.000/20);
Uma varredura de arquivo simples faria 500 acessos a blocos, supondo
que o atributo da condição não fosse atributo-chave. Senão, seriam em
média 250 acessos;
Suponha que conta esteja ordenado por nome_agência.
Como V(nome_agência, conta) = 50, esperamos que 10.000/50=200
tuplas da relação conta pertençam à agência Perryridge;
Essas tuplas caberiam em 200/20 = 10 blocos;
Uma busca binária para encontra o primeiro registro [log2(500)] = 9;
Assim o custo total seria: 9 + 10 – 1 = 18 acessos a bloco.
Operação de Seleção
A otimização de consulta para uma operação SELECT é
necessária principalmente em condições de seleção
conjuntiva, sempre que mais de um dos atributos
envolvidos nas condições possuírem um caminho de
acesso.
O otimizador deve escolher o caminho de acesso que
recupera o menor número de registros (gera blocos de
respostas menores), de maneira mais eficiente.
As seleções que separam o menor número de tuplas
devem ser realizadas primeiro.
Na escolha entre múltiplas opções o otimizador
considera também a seletividade de cada condição.
Classificação
A ordenação é bastante importante, uma vez que o
algoritmo é utilizado:
Na implementação do order by.
Como um componente-chave nos algoritmos de sortmerge usado no join, union e intersection e em
algoritmos de eliminação de duplicatas para a
operação project.
A ordenação pode ser evitada se um índice apropriado
existir de forma a permitir o acesso ordenado aos
registros.
Classificação
Formas de ordenação:
Lógica: construção de um índice na chave de
classificação, o qual será usado para ler a
relação na ordem de classificação.
A leitura de tuplas na ordem de classificação pode
conduzir a um acesso de disco para cada tupla.
Física: as tuplas são gravadas de forma
ordenada no disco.
Classificação
O problema de classificação pode ser tratado sob duas
condições:
Quando
a relação cabe completamente na memória
principal:
Técnicas padrões de classificação (quicksort entre outras)
podem ser usadas.
Quando
a relação é maior que a memória principal classificação externa:
Algoritmo comum: sort-merge externo
Para entendê-lo, considere M o número de frames de páginas
no buffer da memória principal ( o número de blocos de disco
cujos conteúdos podem ser colocados no buffer da memória
principal).
Ordenação Externa
A ordenação externa é adequada para manipular
arquivos de registros grandes, que são armazenados
em disco e que não cabem inteiramente na memória
principal.
A ordenação nesse algoritmo é feita por partes –
estratégia merge-sort.
Fases:
Fase de ordenação;
Fase de fusão.
Inicialização:
i  1;
j  b; (tamanho do arquivo em blocos)
k  n0; (tamanho do buffer em blocos)
m   (j/k)  (maior inteiro)
Fase de ordenação
Se no buffer cabem 3 blocos,
e o arquivo possui 11 blocos,
será preciso 4 iterações da
fase de ordenação. As 3
primeiras ordenarão 9 blocos
e a última ordenará 2 blocos.
Enquanto (i <= m) faça
{
leia os próximos k blocos do arquivo para o buffer ou se houver
menos do que k blocos restantes, leia todos os blocos restantes;
ordene os registros no buffer e grave-os como um sub-arquivo
temporário (utilize um algoritmo de ordenação interna, como o
bubble ou quicksort, por exemplo);
i  i + 1;
}
Fase de fusão: fundir os subarquivos até que reste apenas 1
Inicialização
Temos 4 subarquivos ordenados (m = 4 e k = 3).
i  1;
p   logk-1m ; (p é o número de passagens da fase de fusão)
j  m;
p=2
enquanto (i <= p) faça
{
n  1;
q = 2 e depois 1
q   (j/(k-1)) ; (número de subarquivos a gravar nesta passagem)
enquanto (n <= q) faça
{
ler os próximos k-1 subarquivos ou os subarquivos
restantes (da passagem anterior), um bloco de cada arquivo por vez;
fundir e gravar no novo subarquivo um bloco por vez
n  n + 1;
}
j  q;
i  i + 1;
}
Exemplo no Navathe
Se o número de blocos do arquivo = 1024
Se o tamanho do buffer = 5 blocos
Na fase de ordenação serão criados 205 subarquivos
204 com 5 blocos e 1 com 4 blocos
Na fase de fusão, em cada uma das 4 passagens, serão gravados,
respectivamente:
52 subarquivos
13 subarquivos
04 arquivos
01 arquivo
Número de subarquivos / tamanho do buffer -1 bloco
Por que -1?
Porque um bloco de buffer fica reservado
para armazenar um bloco resultado da fusão.
Sort-merge Externo (Korth)
1.
Várias classificações temporárias são executadas:
i = 0;
repeat
leia M blocos da relação, ou o resto da relação,
aquilo que for menor;
ordene a parte da relação que está na memória;
escreva os dados ordenados no arquivo temporário
Ri;
i = i + 1;
until o fim da relação
Sort-merge Externo
2.
Faz-se o merge nos arquivos temporários. Suponha, por enquanto, que
o número total de temporários, N, seja menor do que M, de forma que se
consiga alocar um frame de página para um bloco de cada arquivo
temporário e há espaço para manter uma página de resultado.
leia um bloco de cada um dos N arquivos Ri, para uma página de buffer
na memória;
repeat
escolha a primeira tupla (na ordem de classificação) entre todas as
páginas do buffer;
escreva a tupla no resultado e apague-a da página de buffer;
if a página de buffer de qualquer temporário Ri está vazia and not fim
de arquivo (Ri) then leia o próximo bloco de Ri na página de buffer;
until todas as páginas de buffer estarem vazias;
Considerações
Geralmente, se a relação é muito maior que a memória, pode haver
M ou mais temporários gerados na primeira fase, e não será
possível alocar um frame de página para cada temporário durante a
fase de merge.
Neste caso, faz-se a operação de merge em múltiplos passos.
Como há memória suficiente para M-1 páginas de buffer de entrada,
cada merge terá M-1 temporários como entrada.
Funcionamento próximo slide.
Exemplo: Suponha agora que apenas um tupla caiba em um bloco
(f = 1), e suponha que a memória mantém três frames de página no
máximo. Durante os estágios de merge, dois frames de página são
usados para entrada e um para o resultado.
Funcionamento
Faz-se o merge sobre os primeiros M-1 temporários (conforme descrito
anteriormente) para obter um único temporário para o próximo passo;
Faz-se o merge dos próximos M-1 temporários de forma semelhante, e
assim por diante, até que todos os temporários iniciais tenham sido
processados;
Nesse ponto, o número de temporários foi reduzido a um fator de M–1;
Se esse número reduzido de temporários ainda é maior ou igual a M, outro
passo é dado, usando os temporários criados pelo passo anterior;
Esses passos são repetidos tantas vezes quantas forem necessárias, até
que o número de temporários seja menor que M;
Então, um passo final gera o resultado classificado.
Exemplo
g
a
d
c
b
24
19
31
33
14
e
16
r
16
d
m
p
d
a
19
a
19
d
31
b
14
g
24
c
33
d
31
e
16
g
24
21
a
14
3
d
7
16
d
21
m
3
b
14
c
33
e
16
d
21
3
m
2
r
7
a
14
Relação
inicial
a
14
p
2
d
7
r
16
p
2
Temporários
Criar
temporários
Temporários
Passo 1:
de merge
a
14
a
19
b
14
c
33
d
7
d
21
d
31
e
16
g
24
m
3
p
2
r
16
Resultado
classificado
Passo 2:
de merge
Número de Acessos a Disco
Fase de ordenação:
2 * b, onde b é o número de blocos do arquivo que está sendo
ordenado
Cada bloco b será acessado duas vezes, uma vez para leitura e
outra vez para escrita
Fase de fusão:
2 * (b * log Dm nr), onde Dm é o número de subarquivos fundidos
em cada fusão e nr é número de subarquivos.
O 2 se dá por conta da leitura e escrita de cada bloco
O termo interno ao parênteses conta quantas vezes cada bloco
será analisado (lido e escrito)
Operação de Junção
equi_join: designação para uma junção da forma r |X|r.A=s.B s, em que A e B
são atributos ou conjuntos de atributos das relações r e s, respectivamente.
O exemplo usado será:
depositante |X| cliente
Suponha as seguintes informações de catálogo:
ncliente = 10.000
fcliente = 25, o que implica bcliente = 10.000/25 = 400
ndepositante = 5.000
fdepositante = 50, o que implica bdepositante = 5.000/50 = 100
V(nome_cliente, depositante) = 2.500, o que implica que, em média,
cada cliente tem duas contas
Suponha ainda que nome-cliente em depositante seja uma chave
estrangeira vinda de cliente
Estimativa do Tamanho das Junções
O produto cartesiano r X s contém nr * ns tuplas.
Cada tupla deste produto cartesiano ocupa sr + ss bytes.
Assim podemos calcular o tamanho do produto
cartesiano.
Para junção natural ... Sejam r(R) e s(S) duas relações:
Se R ∩ S = ∅, então r |X| s é igual a r X s;
Se R ∩ S é uma chave para R, então sabemos que
uma tupla de s irá juntar-se com no máximo uma
tupla de r. Assim, o número de tuplas na junção não
é maior que o número de tuplas de s.
Se R ∩ S é uma chave estrangeira para S – vinda de
R – , então o número de tuplas em r |X| s é
exatamente igual ao número de tuplas em s.
Estimativa do Tamanho das Junções
No exemplo: depositante |x| cliente,
nome_cliente em depositante é uma chave
estrangeira vinda de cliente.
O tamanho do resultado é exatamente
ndepositante, que é 5.000;
Com calcular o tamanho da junção quando R ∩
S não é uma chave para R ou para S?
Estimativa do Tamanho das Junções
Suponha que cada valor aparece com probabilidade igual.
Considere uma tupla t de r e suponha R ∩ S = {A}.
Estima-se que a tupla t produz
ns / V(A,s)
tuplas em r |X| s, uma vez que esse é o número médio de tuplas em s
com um determinado valor para os atributos A.
Considerando todas as tuplas em r, estima-se que há
nr * ns / V(A, s)
tuplas em r |X| s.
Estimativa do Tamanho das Junções
Observe que se invertermos os papéis de r e s, as estimativas
resultariam em valores diferentes se V(A,r) ≠ V(A,s).
Se isso acontece, há a probabilidade de haver tuplas pendentes
que não participam da junção . A estimativa mais baixa será,
provavelmente, a mais precisa.
Técnicas mais sofisticadas para a estimativa do tamanho da junção
devem ser usadas se a hipótese de distribuição uniforme não puder
ser considerada.
Estimativa do Tamanho das Junções
Calculando a estimativa do tamanho para depositante
|X| clientes, sem utilizar informações sobre chaves
entrangeiras.
Como V(nome_cliente, depositante) = 2.500 e
V(nome_cliente, cliente) = 10.000, as duas estimativas
que obtemos são:
(10.000 * 5.000) / 2.500 = 20.000
(5.000 * 10.000)/10.000 = 5.000
Junção de Laço Aninhado
for each tupla tr in r do
begin
for each tupla ts in s do
begin
teste o par (tr, ts) para ver se
satisfazem a condição de junção;
se satisfizerem, adicione tr.ts ao
resultado
end
end
r: relação externa
s: relação interna
tr.ts : tupla obtida concatenando os valores dos atributos das tuplas tr e
ts
Junção de Laço Aninhado
Este algoritmo não requer índices e pode ser usado seja qual for a
condição de junção.
É um algoritmo caro já que examina todos os pares de tuplas nas duas
relações. O número de pares de tuplas a ser considerado é nr * ns (para
cada registro r tem-se que executar uma varredura completa em s).
No pior caso o buffer pode manter apenas um bloco de cada relação, e um
total de nr * bs + br acessos à blocos serão necessários (ou seja, os blocos
da relação r (br) são lidos uma vez por ocasião do laço mais externo e, os
blocos da relação s (bs) são lidos para cada vez que uma tupla de r precisa
ser comparada com todas as tuplas de s por ocasião do laço mais interno)
No melhor caso, há espaço suficiente para que ambas as relações caibam
na memória, assim cada bloco terá de ser lido somente uma vez,
conseqüentemente, apenas br + bs acessos à blocos serão necessários.
Note que, se a relação menor couber completamente na memória, é melhor
usar essa relação como a mais interna.
Exemplo
Considere a junção natural de depositante e cliente.
Suponha que não existem índices para estas relações.
Suponha que depositante é a relação mais externa e
cliente é a relação mais interna.
5.000 * 10.000 tuplas serão examinadas.
Pior caso: 5.000 * 400 + 100 = 2.000.100 acessos à
disco.
Melhor caso: 400 + 100 = 500 acessos à disco.
Trocando as relações dos laços internos e externos:
10.000 * 100 + 400: 1.000.400 acessos à disco.
Merge-junção (Korth)
Sejam r(R) e s(S) relações cuja junção natural
será calculada, e seja R ∩ S a notação para
seus atributos em comum.
Suponha que ambas as relações estejam
classificadas nos atributos R ∩ S.
A junção destas relações pode ser feita por
meio de um merge.
pr := endereço da primeira tupla de r;
ps := endereço da primeira tupla de s;
while (ps <> nulo and pr <> nulo) do
begin
ts := tupla para qual ps aponta;
Ss := {ts};
configure ps para apontar para a próxima tupla de s;
acabou := false;
while (not acabou and ps <> nulo) do
begin
ts’ := tupla para qual ps aponta;
if (ts’[AtribJunção] = ts[AtribJunção])
then begin
Ss = Ss ∪ {ts’};
configure ps para apontar para
a próxima tupla de s;
end
else acabou := verdadeiro;
end;
// permanece varrendo s enquanto as tuplas contiverem valores iguais para o
atributo de junção, e as coloca em uma relação auxiliar.
tr := tupla para a qual pr aponta;
while ( pr <> nulo and tr[AtribJunção] < ts[AtribJunção]) do
begin
configure pr para apontar para a próxima tupla
de r;
tr := tupla para qual pr aponta;
end
// percorre r enquanto não encontrar uma tupla com um valor no atributo de
junção igual ou maior ao valor no atributo de junção das tuplas de s que estão
na relação auxiliar
while (pr <> nulo and tr[AtribJunção] = ts[AtribJunção]) do
begin
for each rs in Ss do
begin
adicione ts.tr ao resultado;
end
configure pr para apontar para a próxima tupla
de r;
tr := tupla para a qual pr aponta;
end;
// encontrando a tupla de r que deve ser juntar às tuplas de Ss, realiza a
concatenação das tuplas, percorrendo r para ver se existem outras a serem
concatenadas.
End;
Merge-junção
Suponha depositante |x| cliente. Com o atributo de
junção sendo o nome do cliente. As relações já estão
ordenadas neste atributo.
O custo da junção é 400 + 100 = 500 acessos à disco.
Caso a exigência de S caber em memória principal não
puder ser atendida, um algoritmo de junção à parte deve
ser executado para junção tr à Ss.
Caso as relações não estejam ordenadas mas possuam
índices, o merge-junção pode ser executado usando os
índices.
Junção Sort-merge (Navathe)
Se os registros de R e S estiverem classificados (ordenados)
fisicamente pelos atributos de junção A e B, respectivamente,
poderemos implementar a junção da maneira mais eficiente
possível.
Ambos os arquivos são varridos simultaneamente na ordem dos
atributos de junção, fazendo a correspondência dos registros que
possuem os mesmos valores para A e B.
Se os arquivos não estiverem classificados, eles deverão ser
classificados primeiro por meio de uma ordenação externa.
Pares de blocos de arquivos são ordenadamente copiados para
buffers de memória, e os registros de cada arquivos são varridos
apenas uma vez (a menos que A e B não sejam atributos chaves e,
nesse caso, o método precisa ser modificado).
Índices proporcionam a capacidade de acessar (varrer) os registros
na ordem dos atributos de junção, mas os registros de fato estão
fisicamente espalhados pelos blocos do arquivo.
Junção Sort-merge
A seguir, um esboço do algoritmo para Junção,
Projeção, União, Interseção e Diferença por
meio de sort-merge, quando R possui n tuplas e
S possui m tuplas.
T  R |X| A=B S
Ordenar as n tuplas de R baseando-se no atributo A;
Ordenar as m tuplas de S baseando-se no atributo B;
Inicializar i  1 , j  1;
Enquanto (i <= n) e (j <= m) faça
{
se Ri[A] > Sj[B]
se o valor do primeiro A é maior que o valor
então j j + 1
do primeiro B, avance em B;
senão se Ri[A] < Sj[B]
se o valor do primeiro A é menor que o valor
então i  i + 1
do primeiro B, avance em B;
senão
{
bloco do próximo slide
}
i i + 1; j  j + 1;
}
{
(* Ri[A] = Sj[B], portanto realizamos o output de uma tupla: resultado
da junção*)
output a tupla combinada <Ri[A], Sj[B]> em T;
(* output outras tuplas correspondentes a Ri se houver*)
l  j + 1;
enquanto (l<=m) and (Ri[A] = Sl[B]) faça
output a tupla combinada <Ri[A], Sl[B]> em T
ll+1
(* output outras tuplas correspondentes a S(j), se houver *)
k  i + 1;
enquanto (k<=n) and (Rk[A] = Sj[B]) faça
output a tupla combinada <Rk[A], Sj[B]> em T
k k + 1;
}
T π <lista de atributos> (R)
Criar uma tupla t[<lista de atributos>] em T’ para cada tupla t de R;
(*T’ contém o resultado da projeção ANTES da eliminação de duplicatas*)
Se <lista de atributos> incluir uma chave de R
então T  T’;
Senão
{
ordenar as tuplas de T’
inicializar i  1, j 2;
enquanto i <= n faça
{
output a tupla T’[i] em T;
enquanto T’[i] = T’[j] and j<= n faça
j j + 1; (* eliminar duplicatas)
i  j; j  j + 1;
}
}
TR∪S
Ordenar as tuplas de R e S utilizando os mesmos e únicos atributos de ordenação;
Inicializar i  1; j  1;
Enquanto (i <= n) e (j <= m) faça
{
se R(i) > S(j) então
{
output S(j) em T;
j  j + 1;
}
se R(i) < S(j) então
{
output R(i) em T;
i  i + 1;
}
else
j  j + 1; (*R(i)=S(j), portanto, pular uma das tuplas duplicatas*)
}
TR∩S
Ordenar as tuplas de R e S utilizando os mesmos e únicos atributos de ordenação;
Inicializar i  1; j  1;
Enquanto (i <= n) e (j <= m) faça
{
se R(i) > S(j) então
{
j  j + 1;
}
else se R(i) < S(j) então
{
i  i + 1;
}
else
{
output R(i) em T; (*R(i)=S(j), portanto, fazemos o output da tupla*)
i  i + 1; j  j + 1;
}
}
TR-S
Ordenar as tuplas de R e S utilizando os mesmos e únicos atributos de ordenação;
Inicializar i  1; j  1;
Enquanto (i <= n) e (j <= m) faça
{
se R(i) > S(j) então
{
j  j + 1;
}
else se R(i) < S(j) então
{
output R(i) em T; (*R(i) não tem S(j) correspondente)
i  i + 1;
}
else
i  i + 1; j  + 1
}
Merge-junção - Considerações
Em relação ao algoritmo apresentado por (Korth): O algoritmo exige
que a relação auxiliar caiba na memória principal. Modificações no
algoritmo devem ser feitas caso essa exigência não possa ser
atendida.
Dado que as relações estão na ordem de classificação, as tuplas
com o mesmo valor nos atributos de junção estão em ordem
consecutiva. Assim, cada tupla na ordem de classificação precisa
ser lida somente uma vez, e, como resultado, cada bloco também é
lido somente uma vez.
Em relação ao algoritmo do Navathe, tem-se que assumir que
conjuntos de tuplas com o mesmo valor no atributo de junção
precisam estar carregadas na memória ao mesmo tempo;
Então, para ambos, o número de acessos à disco é igual à soma do
número de blocos em ambos as relações, br + bs.
Implementação do Outer Join
A junção externa pode ser obtida por meio da
modificação dos algoritmos de junção, como a
junção de laços aninhados, sort-merge ou de
junção hash;
Ou, de forma alternativa e simplificada, por meio
da execução de uma combinação de
operadores da álgebra relacional.
Implementação do Outer Join
Por exemplo, considere a consulta:
select unome, pnome, dnome
from empregado left outer join departamento on
dno=dnumero;
Essa operação de junção externa é equivalente à
seguinte seqüência de operaçoes da álgebra relacional:
Implementação do Outer Join
Calcule a junção interna entre as tabelas.
Temp1  πunome, pnome, dnome (empregado |X| departamento)
Encontre as tuplas de empregado que não aparecem no
resultado da junção.
Temp2  πunome, pnome (empregado) - πunome, pnome (Temp1)
Implementação do Outer Join
Complete cada tupla da relação Temp2 com valor null
para o campo dnome.
Temp2  Temp2 X ‘NULL’
Aplique a operação union em Temp1 e Temp2 para
produzir o resultado do left outer join.
Resultado  Temp1 υ Temp2
O custo dessa junção externa é a soma dos custos da
junção interna, das projeções e da união realizadas.
Junções Complexas
Junção com condição conjuntiva:
r |X| θ ∧ θ ∧ ... θn s
1
2
As junções nas condições individuais podem ser
resolvidas, por exemplo, pelo algoritmo de junção por laços
aninhados:
r |X|θ s, r |X|θ 2 s, r |X| θ n s e assim por diante.
1
A junção global por ser realizada calculando, primeiro o
resultado de uma dessas junções mais simples e depois
testando (a esse resultado) as tuplas produzidas pelas
outras junções.
Junções Complexas
Junção com condição disjuntiva:
r |X| θ 1 ∨ θ 2 ∨ ... θ n s
Neste caso, a junção pode ser calculada como a
união dos registros nas junções individuais.
Junções Complexas
Suponha r1 r2 ...
rn em que as junções estão expressas
sem ordem. Com n = 3, há 12 ordens de junção diferentes:
r1
r2
r3
r1
r2
r3
(r2
(r1
(r1
(r3
(r3
(r2
(r2
(r1
(r1
(r3
(r3
(r2
r3)
r3)
r2)
r2)
r1)
r1)
r3)
r3)
r2)
r2)
r1)
r1)
r1
r2
r3
r1
r2
r3
Junções Complexas
Em geral, com n relações, há (2(n-1))! / (n-1)!
Ordens de junção diferentes. Exemplos: Com n
= 5 o n° é 1680 e com n = 7, o n° é 665.280.
Felizmente, não é necessário gerar todas as
expressões equivalentes a uma determinada
expressão.
Uma desvantagem da otimização baseada no
custo é o custo da própria otimização.
Junções Complexas
Duas árvores de consulta (junção) profundas
à esquerda
Junções Complexas
O otimizador escolherá a árvore que possuir o
menor custo estimado.
Com árvores profundas a esquerda, o filho à
direita é considerado ser a relação interna, para
o caso da execução de laços aninhados.
A idéia-chave sob o ponto de vista do otimizador
em relação à ordem das junções é encontrar
uma ordem que irá reduzir o tamanho dos
resultados intermediários.
Junções Complexas
Considere uma junção envolvendo três relações:
empréstimo |X| depositante |X| cliente
Neste caso, além da escolha da estratégia para o processamento
da junção, tem-se ainda que escolher qual junção calcular primeiro.
Vejamos algumas estratégias:
Estratégia 1: calcule a junção depositante |X| cliente usando
qualquer técnicas. Usando o resultado intermediário, calcule:
empréstimo |X| (depositante |X| cliente);
Estratégia 2: faça como na Estratégia 1, mas calcule primeiro
empréstimo |X| depositante, e então faça a junção do resultado
com cliente.
Outra ordem de junções pode ser feita.
Junções Complexas
Estratégia
3: Em vez de executar duas junções,
execute o par de junções, da seguinte forma:
Construa dois índices:
Um para o número_empréstimo em empréstimo;
Um para o nome_cliente em cliente.
Considere cada tupla t em depositante. Para cada t, procure
as tuplas correspondentes em cliente e as tuplas
correspondentes em empréstimo.
Assim, cada tupla de depositante é examinada exatamente
uma vez.
O custo relativo desse procedimento depende da
forma como as relações estão armazenadas, da
distribuição de valores dentro das colunas e da
presença de índices.
Eliminação de Duplicidade
Pode-se implementar a eliminação de duplicidade usando a
classificação.
As tuplas idênticas aparecerão adjacentes umas às outras após a
classificação, e todas, exceto uma cópia, podem ser removidas.
No sort-merge, as duplicatas encontradas enquanto um temporário
está sendo criado podem ser removidas antes que ele seja escrito
no disco, reduzindo, assim, o número de transferências de blocos.
Assim, pode-se dizer que o custo de eliminar as duplicatas é o
custo de classificar uma relação.
Devido ao custo relativamente alto da eliminação de duplicidade, as
linguagens de consulta comerciais exigem um pedido explícito do
usuário para remover duplicatas; caso contrário, as duplicatas são
mantidas.
Operação de Projeção
Pode-se executar a projeção por meio da execução da
projeção em cada tupla, resultando uma relação que
poderia ter registros duplicados, e então, remover os
registros duplicados.
Se os atributos na lista de projeção incluem as chaves
da relação (primária e/ou candidatas), nenhuma
duplicata existirá.
O tamanho de um projeção da forma ΠA(r) é calculado
como V(A,r), uma vez que a projeção elimina as
duplicatas.
Transformações de Expressões
Relacionais
Uma consulta pode ser expressa de diversas
maneiras diferentes, com diferentes custos de
avaliação.
Equivalência de Expressões;
Regras de Equivalência;
Exemplos de Transformações;
Ordenamento de Junções.
Otimização Algébrica
Objetivo do passo de transformação
Entrada: Árvore da consulta inicial;
Saída: Árvore da consulta otimizada (pode
manter a mesma árvore).
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.
Equivalência de Expressões
Considerando as tabelas a seguir e suas
instâncias, encontre os nomes de todos os
clientes que possuem uma conta em qualquer
agência localizada no Brooklyn.
πnome_cliente ( σcidade_agência = “Brooklyn” (agência |X| (conta |X|
depositante)))
Para resolver esta expressão, seguindo a forma como
ela está escrita, é necessário criar uma relação
intermediária grande (a junção das três relações, como
posto no slide 86).
agência
nome_agência
cidade_agência
fundos
Downtown
Brooklyn
900000
Redwood
Palo Alto
210000
Perrydige
Horseneck
170000
Mianus
Horseneck
40000
Round Hill
Horseneck
8000000
Pownal
Bennington
30000
North Town
Rye
370000
Brighton
Brooklyn
710000
cliente
nome_cliente
rua_cliente
cidade_cliente
Jones
Main
Harrison
Smith
North
Rye
Hayes
Main
Harrison
Curry
North
Rye
Lindsay
Park
Pittfield
Turner
Putnam
Stamford
Williams
Nassau
Princeton
Adams
Spring
Pittsfield
Johnson
Alma
Palo Alto
Glenn
Sand Hill
Woodside
Brooks
Senator
Brooklyn
Green
Walnut
Stamford
nome_cliente
número_conta
Johnson
A-101
nome_agência
número_conta
saldo
Smith
A-215
Downtown
A-101
500
Hayes
A-102
Mianus
A-215
700
Turner
A-305
Perryridge
A-102
400
Johnson
A-201
Round Hill
A-305
350
Jones
A-217
Bringhton
A-201
900
Lindsay
A-222
Redwood
A-222
700
Bringhton
A-217
750
depositante
conta
Junção (conta |X| depositante)
nome_agência
número_conta
saldo
nome_cliente
número_conta
Downtown
A-101
500
Johnson
A-101
Mianus
A-215
700
Smith
A-215
Perryridge
A-102
400
Hayes
A-102
Round Hill
A-305
350
Turner
A-305
Bringhton
A-201
900
Johson
A-201
Redwood
A-222
700
Lindsay
A-222
Bringhton
A-217
750
Jones
A-217
Junção (agência |X| (conta |X| depositante))
nome_agência
número_conta
saldo
nome_cliente
nome_agência
cidade_agência
fundos
Downtown
A-101
500
Johnson
Downtown
Brooklyn
900000
Mianus
A-215
700
Smith
Mianus
Horseneck
40000
Perryridge
A-102
400
Hayes
Perrydige
Horseneck
170000
Round Hill
A-305
350
Turner
Round Hill
Horseneck
8000000
Bringhton
A-201
900
Johson
Brighton
Brooklyn
710000
Redwood
A-222
700
Lindsay
Redwood
Palo Alto
210000
Bringhton
A-217
750
Jones
Brighton
Brooklyn
710000
Equivalência de Expressões
Entretanto, somente as tuplas que pertencem às
agências localizadas no “Brooklyn” são interessantes.
Reescrevendo a consulta, consegue-se eliminar a
necessidade de considerar as tuplas que não têm
cidade_agência = “Brooklyn”, reduzindo o tamanho do
resultado intermediário:
πnome_cliente (( σcidade_agência = “Brooklyn” (agência)) |X| (conta |X|
depositante))
Junção (conta |X| depositante)
nome_agência
número_conta
saldo
nome_cliente
número_conta
Downtown
A-101
500
Johnson
A-101
Mianus
A-215
700
Smith
A-215
Perryridge
A-102
400
Hayes
A-102
Round Hill
A-305
350
Turner
A-305
Bringhton
A-201
900
Johnson
A-201
Redwood
A-222
700
Lindsay
A-222
Bringhton
A-217
750
Jones
A-217
σcidade_agência = “Brooklyn” (agência)
nome_agência
cidade_agência
fundos
Downtown
Brooklyn
900000
Brighton
Brooklyn
710000
(σcidade_agência = “Brooklyn” (agência)) |X| (conta |X| depositante)
nome_agência
número_conta
saldo
nome_cliente
cidade_agência
fundos
Downtown
A-101
500
Johnson
Brooklyn
900000
Bringhton
A-201
900
Johnson
Brooklyn
710000
Bringhton
A-217
750
Jones
Brooklyn
710000
Equivalência de Expressões
πnome_cliente
πnome_cliente
σcidade_agência = “Brooklyn”
|X|
σcidade_agência = “Brooklyn”
|X|
|X|
agência
conta
agência
conta
|X|
depositante
depositante
(a) Árvore da expressão inicial
(b) Árvore da expressão transformada
Equivalência de Expressões
Dada uma expressão de álgebra relacional, é função do
otimizador de consulta propor um plano de avaliação da
consulta que gere o mesmo resultado da expressão
fornecida e que seja uma maneira menos onerosa de
gerar o resultado (ou que, pelo menos, não seja muito
mais cara que a maneira mais barata).
Para isso o otimizador precisa gerar planos alternativos
que produzam o mesmo resultado da expressão dada e
escolher o menos caro.
Regras de Equivalência Algébrica
Uma regra de equivalência diz que expressões de duas formas são
equivalentes se podemos transformar uma na outra preservando a
equivalência.
Preservar a equivalência significa que as relações geradas pelas
duas expressões têm o mesmo conjunto de atributos e contêm o
mesmo conjunto de tuplas, embora seus atributos possam estar
ordenados de forma diferente.
As regras de equivalência são usadas pelo otimizador para
transformar expressões em outras logicamente equivalentes.
Assuma que:
θ: denota predicados;
L: denotas listas de atributos;
E: denota expressões da álgebra relacional.
Regras de Equivalência Algébrica
1. Operações de seleção conjuntivas podem ser quebradas
em uma seqüência de seleções individuais (cascata de σ).
σθ1 ∧ θ2 (E) = σ θ1 (σ θ2 (E))
2. Operações de seleção são comutativas.
σ θ1 (σ θ2 (E)) = σ θ2 (σ θ1 (E))
3. Apenas as operações finais em uma seqüência de
operações de projeção são necessárias, as outras podem
ser omitidas (cascata de π).
πL1 (π L2 (...(π Ln(E))...)) = π L1(E)
Regras de Equivalência Algébrica
4. Seleções podem ser combinadas com produtos
cartesianos e junções teta.
σθ (E1 X E2) = E1 |X|θ E2
5. Operações de junção teta são comutativas.
E1 |X|θ E2 = E2 |X|θ E1
6. Operações de junção natural são associativas.
(E1 |X| E2) |X| E3 = E1 |X| (E2 |X| E3)
7. Comutatividade de π e |X| (ou X): similar à 6.
Regras de Equivalência Algébrica
8. Comutatividade de Operações de Conjunto
R∪S ≡ S∪R
e
R∩S ≡ S∩R
- A operação “” não é comutativa.
9. Associatividade de Operações Produtórias e de Conjunto
(“οX”)
(R “οX” S) “οX” T ≡ R “οX” (S “οX” T)
- Por “οX” entenda-se: X ou X θ ou
- A operação “” não é associativa.
ou ∪ ou ∩.
Regras de Equivalência Algébrica
9. Associatividade de Operações Produtórias e de Conjunto
(“οX”)
(R “οX” S) “οX” T ≡ R “οX” (S “οX” T)
Observação: Predicados de junção devem ser
devidamente ajustados na associatividade de operações
produtórias. Exemplo: Seja θ1 um predicado sobre
atributos de R e S, θ2 um predicado sobre atributos de S
e T, e θ3 um predicado sobre atributos de R e T. Então,
(R “X” θ1 S) “X” θ2 ∧ θ3 T ≡ R “X” θ1 ∧ θ3 (S “X” θ2 T)
Regras de Equivalência Algébrica
10. Comutatividade de Seleção e Operações de Conjunto
(“ο”)
σc (R “ο” S) ≡ (σc (R)) “ο” (σc (S))
- Por “ο” entenda-se: ∪ ou ∩ ou 
11. Comutatividade de Projeção e União
πlistaAtributos (R ∪ S) ≡ (πlistaAtributos (R)) ∪ (πlistaAtributos (S))
- As operações “” e “∩” não são comutativas.
Regras de Equivalência Algébrica
12. Fusão de Seleções e Operações Produtórias
(a)
σc (R X S) ≡ R X θ = σ
(b)
σc (R X S) ≡ R
(c)
R X θ = σc S ≡ R
c
c
S
c
S
S
ou
ou
Exemplos de Transformações
Exemplo 1:
πnome_cliente ( σcidade_agência = “Brooklyn” (agência |X| (conta |X| depositante)))
πnome_cliente (( σcidade_agência = “Brooklyn” (agência)) |X| (conta |X| depositante))
Exemplo 2:
πnome_cliente ( σcidade_agência = “Brooklyn” ∧ saldo > 1000 (agência |X| (conta |X| depositante)))
πnome_cliente ( σcidade_agência = “Brooklyn” ∧ saldo > 1000 ((agência |X| conta) |X| depositante))
πnome_cliente ( σcidade_agência = “Brooklyn” ∧ saldo > 1000 (agência |X| conta)) |X| depositante)
Exemplo3: Examinando uma subexpressão interna:
σcidade_agência = “Brooklyn” ∧ saldo > 1000 (agência |X| conta))
σcidade_agência = “Brooklyn” (σ saldo > 1000 (agência |X| conta))
σcidade_agência = “Brooklyn” (agência) |X| σ saldo > 1000 (conta)
Exemplo 4: Usando projeções
πnome_cliente (( σcidade_agência = “Brooklyn” (agência) |X| conta) |X| depositante)
πnome_cliente((πnúmero_conta(( σcidade_agência = “Brooklyn” (agência)) |X| conta)) |X| depositante)
Ordenando Junções
Uma boa ordenação de operações de junção é importante para reduzir o tamanho
dos resultados intermediários.
πnome_cliente (( σcidade_agência = “Brooklyn” (agência)) |X| conta |X| depositante)
Poderíamos executar conta |X| depositante primeiro e, então, fazer a junção do
resultado com:
σcidade_agência = “Brooklyn” (agência).
Entretanto, conta |X| depositante provavelmente é uma relação grande, já que contém
uma tupla para cada conta. Em contrapartida,
σcidade_agência = “Brooklyn” (agência) |X| conta
é, provavelmente, uma relação pequena.
Para confirmar, observe que, como o banco tem um grande número de agências
amplamente distribuídas, é provável que apenas uma fração pequena dos clientes do
banco tenha conta em agências localizadas no Brooklyn. Assim, a expressão precedente
resulta em uma tupla para cada conta mantida em uma agência localizada no Brooklyn.
Então, a relação temporária que precisa ser armazenada é menor que a que se obteria
fazendo primeiro conta |X| depositante.
Otimização Heurística
Uma árvore de consulta pode ser transformada passo a
passo em outra árvore de consulta mais eficiente.
Entretanto é preciso assegurar que os passos de
transformação sempre levem a uma árvore de consulta
equivalente.
Determinadas regras de transformação preservam essa
equivalência.
Algoritmo de Otimização Algébrica
Passo1:
A regra 1, ao ser usada, quebra quaisquer
operações SELECT com condições conjuntivas em
uma cascata de operações SELECT, permitindo
um maior grau de liberdade para transferir
operações SELECT para ramos diferentes e
abaixo na árvore.
Passo2:
Usando as regras 2, 4, 6, e 10 relativas à
comutatividade do SELECT com outras operações,
move cada operação SELECT o mais longe para
baixo na árvores, que forem permitido pelos
atributos envolvidos na condição de seleção.
Algoritmo de Otimização Algébrica
Passo 3:
Usando as regras 5 e 9, relativas à comutatividade e
associatividade de operações binárias, rearraja os
nós folhas da árvore utilizando o seguinte critério:
Posiciona as relações do nó folha com operações de
SELECT mais restritivas, de forma que elas possam ser
executadas o quanto antes.
Algoritmo de Otimização Algébrica
Passo 4:
Usando a regra 12, combina uma operação de
PRODUTO CARTESIANO com uma operação
SELECT subseqüente na árvore, gerando uma
operação JOIN se a condição representa uma
condição de junção.
Passo 5:
Usando as regras 3, 4, 7 e 11, relativas à cascata de
PROJECT e à comutação de PROJECT com outras
operações, quebra e transfere as listas de atributos
de projeção para baixo na árvore.
Algoritmo de Otimização Algébrica
Passo 6:
Identifica subárvores que representam grupos de
operações que podem ser executadas por um único
algoritmo (execuções em pipeline).
Como exemplo, considere a consulta:
select unome
from Empregado, Trabalha_Em, Projeto
where pnome = ‘Aquarius’ and pnumero = pno and
essn = ssn and datanasc > ’31-12-1957’;
Exemplo:
Passos na conversão de uma
árvore de consulta durante a
otimização heurística. (a) Árvore
de consulta inicial (canônica) para
a consulta. (b) Transferência das
operações SELECT para baixo na
árvore de consulta. (continua)
Exemplo:
Passos na conversão de uma
árvore de consulta durante a
otimização heurística. (c)
Aplicação, em primeiro lugar, da
operação SELECT mais restritiva.
(d) Substituindo PRODUTO
CARTESIANO e SELECT por
operações JOIN.
Exemplo:
Passos na conversão de uma
árvore de consulta durante a
otimização heurística. (e)
Transferência das operações
PROJECT para baixo na árvore
de consulta.
A Escolha de Planos de Avaliação
A geração de expressões é apenas parte do processo
de otimização de consultas.
Um plano de avaliação define exatamente qual algoritmo
será usado para cada operação e como a execução das
operações é coordenada.
π nome_cliente (classificar para remover duplicatas)
|X| (hash-junção)
|X| (merge_junção)
σcidade_agência = Brooklyn
σ(use o índice 1)
agência
depositante
σ saldo < 1000
(use a varredura linear)
conta
Interação de Técnicas de Avaliação
Um modo de escolher um plano de avaliação para uma expressão de
consulta é simplesmente escolher o algoritmo mais barato para avaliar
cada operação. E, olhando para os níveis da árvore, escolhe-se qualquer
ordenamento para a execução das operações, desde que as operações
nas camadas mais baixas da árvore sejam executadas antes das
operações nas camadas mais altas.
Entretanto, essa estratégia pode não ser a melhor. Embora uma mergejunção, sob certas condições, possa ser mais cara que uma hash-junção,
ela consegue prover um resultado classificado que torna mais barata a
avaliação de uma operação posterior (como uma eliminação de duplicatas
ou uma outra merge-junção).
Para escolher o melhor algoritmo global, se deve considerar até mesmo os
algoritmos que não são os melhores para as operações individuais.
Abordagens para escolha do melhor plano de avaliação:
Baseada no custo de todos os planos;
Heurística.
Otimização Baseada em Custo
O otimizador baseado no custo gera uma faixa de planos de
avaliação a partir de uma determinada consulta usando as regras
de equivalência e escolhe aquele de menor custo.
Para uma consulta complexa, o número de planos diferentes por ser
muito grande.
Diferentes técnicas podem ser usadas para diminuir o número de
planos a serem avaliados:
Quando se examina os planos para uma expressão, é possível
terminar após examinar apenas uma parte da expressão, se for
determinado que o plano mais barato para aquela parte já está
mais caro que a avaliação mais barata para uma expressão
completa já examinada.
Otimização Heurística
Regras heurística são utilizadas para
transformar consultas da álgebra relacional;
No otimizador heurístico, a estratégia mais
eficiente para cada operação é escolhida.
Estrutura dos Otimizadores de Consulta
Na prática, a maioria dos otimizadores de consultas combinam
estratégias baseadas em custo com estratégias heurísticas.
Alguns SGBDs consideram a probabilidade de já haver no
buffer a página que contém o dado que se está precisando
(isso é mais um dado estatístico e pode resultar em estimativas
de custos menores).
É possível usar a estratégia heurísticas de dividir as consultas
em sub-consultas que não utilizem mais de duas tabelas.
Transforma consultas em SQL em outras consultas em SQL
que utilizam junções onde for possível facilita a transformação
da consulta em SQL em uma consulta em álgebra relacional.
Otimização em PostgreSQL
Seguem alguns breves comentários sobre otimização e
desempenho em PostgreSQL.
Para otimização e desempenho, PostgreSQL utiliza-se
dos comandos vacuum, analyze e explain.
Otimização em PostgreSQL
VACUUM O comando Vacuum tanto recupera
espaço em disco, quanto otimiza o desempenho do
banco e previne contra perda de dados muito antigos,
devido ao recomeço do ID das transações. Portanto,
deve ser utilizado constantemente, pois também
atualiza as estatísticas dos dados utilizados pelo
planejador de comandos.
Na linha de comando:
vacuumdb -faze ou vacuumdb -fazq.
Otimização em PostgreSQL
Exemplo de uso do vacuum:
Em uma tabela:
VACUUM VERBOSE ANALYZE nometabela;
Em um banco de dados completo:
Somente VACUUM ou VACUUM FULL ANALYZE;
Recomendações:
Para a maioria das instalações executar o comando VACUUM
ANALYZE para todo o banco de dados, de vez em quando, em horário
de pouca utilização.
Quando for excluída a maioria dos registros de uma tabela, sugere-se a
execução do comando VACUUM FULL. Contudo, este comando gera
um forte bloqueio nas tabelas em que é executado.
Otimização em PostgreSQL
ANALYZE O comando ANALYZE coleta estatísticas
sobre o conteúdo das tabelas do banco de dados e armazena os
resultados na tabela do sistema pg_statistic. Posteriormente, o
planejador de comandos utiliza estas estatísticas para ajudar a
determinar o plano de execução mais eficiente. Caso estas
estatísticas não sejam atualizadas com freqüência, pode ser
comprometido o desempenho do banco de dados, por uma
escolha errada do plano de execução dos comandos.
Normalmente, operações DELETE ou UPDATE não removem
os registros automaticamente (somente após a execução do
vacuum isso acontece).
Otimização em PostgreSQL
No PostgreSQL, pode ser utilizado o comando
explain para ver o plano (conjunto executável de
instruções) criado pelo sistema para qualquer
comando.
O comando explain traz informações sobre custo,
como tamanho da tupla, custo estimado de execução,
entre outros.
Exemplo de uso do explain:
EXPLAIN SELECT * FROM NOMETABELA;
Otimização em PostgreSQL
EXPLAIN ANALYZE Executa a consulta e
mostra o tempo real acumulado dentro de cada
nó do plano de execução, junto com os custos
estimados que o comando explain simples
mostraria.
Referências Bibliográficas
Sistemas de Banco de Dados. (Cap. 12) Abraham
Silberchatz, Henry F. Korth e S. Sudarshan. 3ª Edição.
Makron Books, 1999.
Sistemas de Banco de Dados. (Cap. 15) Ramez
Elsmari, Shamkant B. Navathe. 4ª Edição. Pearson
Addison Wesley, 2005.
Manuais do PostgreSQL.