Otimização de Consultas em SQL
Parte II - Planos Alternativos - Estimativa
de Custos dos Planos de Execução
AULA 19
Profa. Sandra de Amo
Programa de Pós-Graduação em CC - UFU
Sistemas de Banco de Dados - 2012-2
Catálogo do Sistema
Informações armazenadas no catálogo, necessárias no processo de otimização:

Informações gerais:








Tamanho do buffer pool (espaço livre)
Tamanho de uma página em disco
Informações sobre as tabelas
Informações sobre índices
Informações sobre visões
Estatísticas sobre tabelas e indices: atualizadas periodicamente
Informações sobre usuários: contas, autorizações de acesso (escrita,
leitura), etc.
Alguns SGBDs mais sofisticados:


Histogramas sobre a distribuição dos valores de cada atributo.
A partir destas informações é possivel ter informação mais acurada sobre o
tamanho dos resultados de uma operação, sobre a seletividade de um método
de acesso, etc.
Informações sobre tabelas, índices e
visões

Tabelas





Indices



Nome da tabela, nome ou identificador do arquivo, estrutura de
arquivo (heap, ordenado, hash)
Nome e tipo de cada atributo
Nome dos índices existentes para cada tabela
As restrições de integridade (chaves primárias, chaves candidatas,
chaves estrangeiras, etc) para cada tabela
O nome do índice e sua estrutura (hash, b+tree)
A chave do índice
Visões

Nome da visão e sua definição (o código da consulta SQL que a
define)
Estatísticas sobre tabelas e indices:







NTuples (R) = Número de tuplas da tabela R
NPages(R) = Número de páginas da tabela R
NKeys(I) = número de chaves distintas do Indice I
INPages(I) = número de páginas do indice I
(no caso de B+tree = número de folhas)
IHeight(I) = Altura do Indice (no caso de B+tree)
ILow(I) = menor valor de chave do indice I
IHigh(I) = maior valor de chave do indice I
Como o catálogo é armazenado :
Coleção de Tabelas
Exemplo



Tabela do catálogo:



Sailors(sid:integer, sname:string, rating:integer, age:real)
Reservas(sid:integer, bid:integer, day:dates, rname:string)
Attribute_Cat(atname:string, relname:string, type:string,
position:integer)
Catálogo pode ser consultado usando SQL !
Escolha das tabelas do catálogo e seus esquemas
depende do implementador do SGBD.
Uma tabela do catálogo
atname
relname
type
position
atname
Attribute_Cat
string
1
relname
Attribute_Cat
string
2
type
Attribute_Cat
string
3
position
Attribute_Cat
integer
4
sid
Sailors
integer
1
sname
Sailors
string
2
rating
Sailors
integer
3
age
Sailors
real
4
sid
Reservas
integer
1
bid
Reservas
integer
2
day
Reservas
dates
3
rname
Reservas
string
4
Plano de Execução
Π sname
SELECT S.sname
FROM Reservas R, Sailors S
WHERE R.sid = S.sid
AND R.bid = 100
AND S.rating > 5
σ bid=100 and rating > 5
sid=sid
Reservas
Sailors
Complementando o plano: como será
implementado ?
Π sname
On-the-fly
σ bid=100 and rating > 5
sid=sid
Reservas
(scan)
Tabela externa
On-the-fly
Simple Nested Loops página a página
Sailors
(scan)
Tabela interna
Pipeline versus Tabelas Materializadas



Pipeline : resultado de uma operação é
transferido para a próxima operação sem a
criação de uma tabela em disco.
Economia de custos de armazenamento e de
leitura posterior
Sempre que o algoritmo do operador para o
qual é transferido o resultado permitir, a
técnica de pipeline é utilizada.
Exercício


Diga se é possível utilizar a estratégia de
pipeline para implementar um duplo join
utilizando o algoritmo NLJ/p-p para os dois
Joins
A B C
Em caso afirmativo, explique como funciona
o algoritmo.
Estimativa de Custos de um Plano de
Execução
Para cada nó da árvore N da árvore, seja Op(N)
a operação associada a N.
Tarefas do Estimador de Custos
 Estimar do custo de Op(N)
 Estimar o tamanho do resultado de Op(N)
Estimativa do Tamanho do Resultado
SELECT <lista de atributos>
FROM < lista de relações R1,...,Rk >
WHERE <cond1 ^ cond2 ^....^condn>



Número máximo de tuplas no resultado =
M1.M2....Mk, onde Mi = tamanho de Ri
Cláusula WHERE atua como um redutor desta
estimativa
Cada condição do WHERE tem o seu fator de
redução próprio
Fatores de Redução

R.A = valor



Fator de redução = 1/NKeys(I), caso exista um indice I
com chave A para a relação R
Fator de redução = 1/10, caso contrário (ou utiliza-se
estatísticas mantidas no catálogo sobre a distribuição dos
valores dos atributos)
R.A = R.B



Fator de redução = 1/Max(NKeys(IA),NKeys(IB)) se
existe indices IA e IB com chave A e B respectivamente.
Fator de redução = 1/NKeys(I) se somente um dos
atributos é chave de um indice I
Fator de redução = 1/10 caso contrário.
Fatores de Redução

R.A > valor



Fator de redução = (High(I) – valor) / High(I) – Low(I)
caso exista um indice I com chave A para a relação R
Fator de redução = fração < ½ caso não exista indice ou
se o valor não é aritmético
R.A IN (Lista de valores)

Fator de redução =


N*(fator de redução de R.A = valor), onde N = núm. de itens
Fator de redução = fração < ½ caso não exista índice ou
se o valor não é aritmético.
Fatores de Redução

R.A IN (Subconsulta)

Fator de redução: M/N onde



NOT (Cond)


M = tamanho do resultado da Subconsulta
N = número de valores do atributo R.A
Fator de redução: (1 – Fator de Redução(Cond))
Fator de Redução da Projeção = fração
equivalente ao tamanho dos atributos que não
são projetados.
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
4
3
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
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
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
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: 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
Histograma por profundidade
9
Qual a estimativa da quantidade de tuplas com AGE > 13 ?
Distribuição histograma = 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
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).
Planos para Consultas Aninhadas
SELECT S.sname
FROM Sailors S
WHERE S.rating = (SELECT MAX (S2.rating)
FROM Sailors S2)

Subconsulta interna: SELECT MAX (S2.rating)
FROM Sailors S2
Executada uma única vez, produzindo um número X

SELECT S.sname
FROM Sailors S
WHERE S.rating = X
Planos para Consultas Aninhadas
SELECT S.sname
FROM Sailors S
WHERE S.sid IN (SELECT R.sid
FROM Reserves R
WHERE R.bid = 103)

Estratégia de execução comum
Subconsulta interna é avaliada e materializada (T)
Faz-se um Join
Sailors = relação externa
T = relação interna (subconsulta sempre é relação interna)

Alguns SGBDs têm estratégias mais sofisticadas:

Pode tranformar T em relação externa do Join e Sailors na interna, caso for
mais vantajoso, por exemplo, se Sailors possui indice Hash no atributo sid
Tratamento de Consultas Aninhadas
Correlatas
SELECT S.sname
FROM Sailors S
WHERE EXISTS (SELECT *
FROM Reserves R
WHERE R.bid = 103 AND S.sid = R.sid)
 Consulta externa e interna são correlatas: atributo sid da
externa aparece na consulta interna.
 Não é possível avaliar a consulta interna uma única vez.
 Estratégia típica de execução: consulta interna é calculada
para cada tupla de S
Aninhadas versus não-aninhadas





Uma consulta aninhada frequentemente é equivalente a uma
não aninhada.
Consultas aninhadas correlatas frequentemente têm uma
versão sem correlação.
Um otimizador tipico é capaz de encontrar um bom plano de
execução se dispõe de uma versão não-aninhada ou sem
correlações.
Boa parte dos otimizadores não são capazes de transformar
consultas aninhadas em não aninhadas ou de eliminar
correlações.
Assim, fica a cargo do usuário formular a consulta de modo a
evitar aninhamentos e/ou correlações.
EXERCÍCIOS
Cálculo de Custos de
Planos de Execução
Cálculo de Custos de Planos de
Execução
Exercício1 :
Calcule o custo deste plano
Π sname
On-the-fly
R : 1000 páginas
σ bid=100 and rating > 5
S : 500 páginas
R: 100 tuplas por página
S: 80 tuplas por página
Reservas
(scan)
Tabela externa
sid=sid
On-the-fly
Simple Nested Loops página a página
Sailors
(scan)
Tabela interna
“Empurrando” seleções para baixo na
árvore de execução
Exercicio 2:
Calcule o custo deste plano
Π sname
On-the-fly
Número de valores para bid = 100
Rating varia de 1 a 10
Uniformemente distribuidos
sid=sid Sorte-Merge Join
Numero de páginas no buffer = 5
Scan, write to Temp1
σ
bid=100
Reservas
(scan)
Tabela externa
σ rating > 5
Scan, write to Temp2
Sailors
(scan)
Tabela interna
“Empurrando” seleções para baixo na
árvore de execução
Exercicio 3 :
Calcule o custo deste plano
Π sname
On-the-fly
Número de valores para bid = 100
Rating varia de 1 a 10
Uniformemente distribuidos
sid=sid Block Nested Looping Join
Numero de páginas no buffer = 5
Scan, write to Temp1
σ
bid=100
Reservas
(scan)
Tabela externa
σ rating > 5
Scan, write to Temp2
Sailors
(scan)
Tabela interna
“Empurrando” projeções para baixo na
árvore de execução
Exercicio 4 :
Calcule o custo deste plano
Π sname
On-the-fly
Número de valores para bid = 100
Rating varia de 1 a 10
Uniformemente distribuídos
Número de páginas no buffer = 5
On-the-fly
Scan, write to Temp1
sid=sid Block Nested Looping Join
Π sid
Π sid,sname
σ bid=100
σ rating > 5
Reservas
(scan)
Tabela externa
On-the-fly
Scan, write to Temp2
Sailors
(scan)
Tabela interna
Nem sempre “empurrar seleções
abaixo do join é vantajoso”
Exercício 5 :
Calcule o custo deste plano
Π sname
On-the-fly
Número de valores para bid = 100
Rating varia de 1 a 10
Uniformemente distribuídos
Número de páginas no buffer = 5
σ rating > 5
sid=sid
On-the-fly
σbid=100
(tem índice hash em bid, Reservas
agrupado e estático)
Tabela externa
On-the-fly
Index Nested Loops com pipeline
Sailors (tem índice hash em sid, não
necessariamente agrupado)
Tabela interna
Nem sempre execuções em pipeline são
mais vantajosas que as materializadas
Exercício 6 :
Calcule o custo deste plano
•Número de valores para bid = 100
•Rating varia de 1 a 10
uniformemente distribuídos
• Número de páginas no buffer = 5
• Todos os marinheiros fizeram reservas
de barcos.
• Reservas distribuidas uniformemente
entre os marinheiros.
• Todos os barcos foram reservados um
mesmo número de vezes
Scan, write to Temp
ordena por sid
Π sname
On-the-fly
σ rating > 5
sid=sid
σbid=100
(tem índice hash em bid, Reservas
agrupado e estático)
Tabela externa
On-the-fly
Index Nested Loops
Sailors (tem índice hash em sid)
Tabela interna
Seleção por atributo chave “empurrada” abaixo
do Join é muito vantajosa.
Exercício 7 :
Calcule o custo deste plano
•Número de valores para bid = 100
•Rating varia de 1 a 10
uniformemente distribuídos
• Número de páginas no buffer = 5
• Todos os marinheiros fizeram reservas
de barcos.
• Reservas distribuidas uniformemente
entre os marinheiros.
• (bid,day) é chave de Reservas
On-the-fly
On-the-fly
(tem índice hash em bid,
agrupado e estático)
Π sname
On-the-fly
σ rating > 5
sid=sid
On-the-fly
Index Nested Loops com pipeline
σday = 09/09/82
σ bid=100
Sailors (tem índice hash em sid)
Tabela interna
Reservas
Tabela externa
Compare com o custo do plano
do exercicio 1.