Otimização de Consultas em SQL
Histogramas – Estimativas mais
acuradas do fator de redução
AULA 26
Profa. Sandra de Amo
GBC053 – BCC
2012-2
Histogramas


Estimativas do fator de redução: supõem que
os valores dos atributos são distribuídos
uniformemente.
Histogramas:


Técnica mais sofisticada e acurada para estimar o
fator de redução
Necessita que estatísticas sobre a variação dos
valores dos atributos sejam armazenadas no
catálogo e atualizadas periodicamente.
9
8
Histograma
Distribuição real
3
4
3
4
3
2
2
2
1
2
1
1
0
0
3
0
1
1
2
3
4
5
3
3
3
3
3
2
3
4
Distribuição uniforme
5
6
3
6
8
7
3
7
3
8
10
9
3
9
3
10
11
3
11
12
3
12
14
13
3
13
3
14
Histograma

45 tuplas, 15 valores



Distribuição uniforme: 3 tuplas para cada valor
Distribuição não-uniforme: número de tuplas para
cada valor pode variar bastante
Histograma: estrutura mantida pelo SGBD
em seu catálogo que dá uma estimativa do
número de tuplas por faixa de valor
Histogramas
Supõe-se um conjunto de N tuplas, com valores variando de v1 a
v2.
Supõe-se que para cada valor v, v1 ≤ v ≤ v2 temos o número de
tuplas N(v) com este valor
Estimativas do número de tuplas com valor x:
 Estimativa exata : N(x)
 Estimativa usando distribuição uniforme: Média aritméticas
dos valores
Histogramas por Largura
Histograma por largura :

particiona-se o conjunto de valores em K grupos, com o mesmo número
de valores cada um.

Para cada grupo de valores, determina a média do número de tuplas do
grupo
Como estimar N(x) usando um histograma por Largura

Estimativa do número de tuplas com valor x = média do número de tuplas
do grupo ao qual x pertence.
9
8
Histograma por largura
4
3
3
3
2
2
4
1
2
2
1
1
0
0
1
2
3
4
5
6
7
8
9
10
11
5
12
14
13
5
5
12
13
5
2.67
1.33
0
1
2
3
4
1
5
6
7
8
9
10
11
14
Uso do Histograma por largura
Qual a estimativa da quantidade de tuplas com AGE > 13 ?
Distribuição uniforme: 3 tuplas
3
3
3
2
1
0
3
3
3
3
3
3
6
5
4
Distribuição histograma por largura: 5 tuplas
3
7
3
8
3
3
10
9
3
11
3
12
5
13
3
14
5
5
12
13
5
2.67
1.33
0
1
2
3
4
1
5
6
7
8
9
10
11
14
Histogramas em Profundidade
Histograma em Profundidade :


particiona-se o conjunto de valores em X grupos, com aproximadamente
o mesmo número de tuplas em cada um.
Para cada grupo de valores, determina a média do número de tuplas para
cada valor do grupo.
Como estimar N(x) usando um histograma por Comprimento


Verifica em que grupo de valores o valor x se encaixa.
N(x) = média do número de tuplas associado aos valores deste grupo.
Histograma por profundidade
9
6
6
2.67
1.80
1.75
0
1
2
8 tuplas
3
4
7 tuplas
5
6
7
8
12 tuplas
9
10
11
12
9 tuplas
13
14
9 tuplas
Histograma por profundidade
Qual a estimativa da quantidade de tuplas com AGE > 13 ?
Distribuição uniforme: 3 tuplas
9
Distribuição histograma por largura: 5 tuplas
Distribuição histograma por profundidade = 9 tuplas
6
6
2.67
1.80
1.75
0
1
2
8 tuplas
3
4
7 tuplas
5
6
7
8
12 tuplas
9
10
11
12
9 tuplas
13
14
9 tuplas
Exercicio 1
100 tuplas, 20 valores variando de 1 a 98
1
3
58
2
4
10
60
7
6
4
63
3
10
3
65
4
22
8
76
3
31
9
78
7
35
2
80
2
43
5
84
4
47
7
93
3
53
8
98
6
1. Descrever uma distribuição uniforme para
estes dados.
2. Fazer um histograma por largura .
3. Estimar o número de tuplas com
valores > 30, supondo uma distribuição uniforme
dos dados.
4. Estimar o número de tuplas com
valores > 30, supondo uma distribuição de acordo
com o histograma por largura.
Exercicio 2
100 tuplas, 20 valores variando de 1 a 98
1
3
58
2
4
10
60
7
6
4
63
3
10
3
65
4
22
8
76
3
31
9
78
7
35
2
80
2
43
5
84
4
47
7
93
3
53
8
98
6
1. Fazer um histograma por profundidade .
2. Estimar o número de tuplas com
valores > 30, supondo uma distribuição de acordo
com o histograma por largura.
Histogramas comprimidos


Histogramas por profundidade produzem melhores
estimativas do que histogramas por largura
Histogramas comprimidos



Mantém contadores para valores mais frequentes (por
exemplo idade = 7 e idade = 14)
Para os outros valores, mantém um histograma por
profundidade (de preferência) ou por largura.
Muitos SGBDs utilizam histograma por
profundidade, alguns utilizam mesmo histogramas
comprimidos.
Planos de execução para múltiplos
“Join”
A
B
C
D
PLANO POR PROFUNDIDADE À
ESQUERDA
D
A
D
C
C
A
B
PLANOS LINEARES
A
B
B C
PLANO BUSHY
D
Planos por profundidade à esquerda

São os únicos a serem considerados:




Quanto maior o número de joins maior o número de planos
alternativos. Por isto opta-se por considerar somente os left-deep.
Planos left-deep permitem utilizar estratégia pipeline à esquerda com
a relação externa. A relação interna é sempre uma relação de base
(materializada).
Repare que não é possível utilizar pipeline à direita de um join. É
sempre necessário que a relação interna esteja disponível em sua
integralidade, pois é varrida diversas vezes.
No caso de planos left-deep, este problema não acontece, pois o filho
à direita de um Join é sempre uma relação de base (materializada).