Bancos de Dados II
Otimização de Consultas
Parte II
Lineu Antonio de Lima Santos
Estimando Estatísticas de
Resultados de Expressões
• O custo de uma operação depende do tamanho
e de outras estatísticas de suas entradas
• As estatísticas sobre relações e índices são
armazenadas no catálogo do SGBD
• Estatísticas não são muito precisas, pois são
baseadas em suposições que podem não ser
exatas
– A experiência nos mostra que mesmo assim os
planos com os menores custos estimados realmente
têm custos de execução reais que são os menores
ou perto disso
2
Informações Estatísticas para
Estimativa de Custo
• O Catálogo do SGBD armazena as seguintes
informações estatísticas
•
•
•
•
nr: número de tuplas em uma relação r.
br: número de blocos contendo tuplas de r.
lr: tamanho de uma tupla de r em bytes.
fr: fator de blocagem de r — ou seja, o número de tuplas de r
que cabem em um bloco.
• V(A, r): número de valores distintos que aparecem em r para
o atributo A; igual ao tamanho de ∏A(r).
• Se as tuplas de r forem armazenadas fisicamente juntas em
um arquivo, então:




n r 
br =
f r 
3
Informações Estatísticas para
Estimativa de Custo
• O catálogo do SGBD também guarda as
estatísticas sobre índices
– Alturas dos índices de árvore B+
– Número de páginas de folha de índices
• As estatísticas são atualizadas
periodicamente e não no momento da
atualização do estado do banco de dados
para evitar sobrecarga
– UPDATE STATISTICS no SQL Server
4
Estimativa de Tamanho da Seleção
• O tamanho do resultado de uma seleção
depende do predicado de seleção
• σA = a (r)
– Se considerarmos a distribuição uniforme de
valores o resultado da seleção pode ser
estimado como tendo
• nr/V(A,r) tuplas
5
Estimativa de Tamanho da Seleção
• σA <= v (r)
– Se o valor de (v) estiver disponível no momento da
estimativa de custo, uma estimativa mais precisa
poderá ser feita
• Supondo os valores mínimos e máximos de A armazenados
no catálogo (min(A,r) e max(A,r))
• Supondo uma distribuição uniforme de valores
• O número de registros estimado é
nr .
v − min( A, r )
max( A, r ) − min( A, r )
– Se o valor de (v) não estiver disponível
• nr/2
6
Estimativa de Tamanho da Seleção
• A seletividade de uma condição θi é a probabilidade de que uma tupla
na relação r satisfaça θi . Se si é o número de tuplas que satisfazem
em r, a seletividade de θi é dada por si /nr.
• Conjunção: σθ1∧ θ2∧. . . ∧ θn (r). A estimativa para o número de tuplas no
resultado é:
s ∗ s2 ∗ . . . ∗ sn
nr ∗ 1
n rn
• Disjunção:σθ1∨ θ2 ∨. . . ∨ θn (r). Número estimado de tuplas:

s1
s2
sn 
n r ∗  1 − (1 −
) ∗ (1 −
) ∗ ... ∗ (1 −
) 
nr
nr
nr 

• Negação: σ¬θ(r). Número estimado de tuplas:
nr – tamanho(σθ(r))
7
Estimativa de Tamanho da Junção
• O produto Cartesiano r x s contém nr .ns tuplas; cada tupla
ocupa lr + ls bytes.
• Se R ∩ S = ∅, então r
s é o mesmo que r x s.
• Se R ∩ S é uma chave para R, então uma tupla de s se
juntará com no máximo uma tupla de r
• portanto, o número de tuplas em r
de tuplas em s.
s não é maior que o número
• Se R ∩ S em S é uma chave estrangeira em S referenciando
R, então o número de tuplas em r
s é exatamente o
mesmo que o número de tuplas em s.
• O caso para R ∩ S sendo uma chave estrangeira
referenciando S é simétrico.
8
Estimativa de Tamanho da Junção
• Se R ∩ S = {A} não é uma chave para R ou S.
• Se considerarmos que cada tupla t em R produz tuplas em R
número de tuplas em R
S é estimado em:
nr ∗ ns
V ( A, s )
S, o
Se o contrário for verdadeiro, a estimativa obtida será:
nr ∗ ns
V ( A, r )
A menor destas duas estimativas provavelmente é a mais precisa.
9
Plano de Avaliação
• Um plano de avaliação define exatamente qual algoritmo é
usado para cada operação, e como a execução das operações é
coordenada.
10
Escolha dos Planos de Avaliação
• Precisa considerar a interação das técnicas de avaliação quando
escolher planos de avaliação: a escolha do algoritmo mais barato
para cada operação independentemente pode não gerar o melhor
algoritmo geral. Por exemplo:
• junção merge pode ser mais dispendiosa que a junção de hash,
mas pode oferecer uma saída classificada que reduz o custo
para um nível de agregação externo.
• a junção de loop aninhado oferece oportunidade para pipelining
• Otimizadores de consulta práticos incorporam elementos das
duas técnicas gerais a seguir:
• Pesquisar todos os planos e escolher o melhor plano com base
no custo.
• Usar heurística para escolher um plano.
11
Otimização Baseada em Custo
• Considere encontrar a melhor ordem de junção para
r1 r2 ... rn
• Existem (2(n – 1))!/(n – 1)! ordens de junção
diferentes para a expressão acima. Com n = 7, o
número é 665280, com n = 10, o número é maior que
176 bilhões!
• Não é preciso gerar todas as ordens de junção.
Usando a programação dinâmica, a ordem de junção
de menor custo para qualquer subconjunto de {r1, r2,
... rn} é calculada apenas uma vez e armazenada
para uso futuro.
12
Otimização Heurística
• A otimização baseada em custo é dispendiosa, mesmo com a
programação dinâmica.
• Os sistemas podem usar heurísticas para reduzir o número
de escolhas que precisam ser feitas com base no custo.
• A otimização heurística transforma a árvore de consulta
usando um conjunto de regras que normalmente (mas não
em todos os casos) melhoram o desempenho da execução:
• Realizar a seleção cedo (reduz o número de tuplas)
• Realizar a projeção cedo (reduz o número de atributo)
• Realizar as operações de seleção e junção mais restritivas antes de outras
operações semelhantes.
• Alguns sistemas utilizam apenas heurísticas, outros combinam heurísticas
com otimização parcial baseada em custo.
13