Otimização de Consultas em SQL
Parte I - Planos de Execução e
Equivalências de Expressões da Álgebra
Relacional
AULA 19
Profa. Sandra de Amo
Programa de Pós-Graduação em CC - UFU
Sistemas de Banco de Dados - 2012-2
Principais etapas do processo




Transformar os blocos simples SQL em
expressões da álgebra relacional
Enumerar os possíveis planos de execução da
expressão da álgebra relacional
correspondendo à consulta
Estimar o custo de cada plano
Escolher o plano com menor custo
Esquema Geral do Otimizador
Bloco SQL simples
usuário
Consulta SQL
SQL Parser
Transforma em Algebra
Coleção de blocos simples
B1, B2, ...., Bn
Plano canônico
Cria planos alternativos
Otimizador
Planos alternativos
Estima custos
Melhor Plano de execução
Melhor Plano de execução
Decompor consulta em blocos simples

Um bloco SQL simples é um comando sem
subconsultas aninhadas, onde aparece





somente um SELECT,
somente um FROM
no máximo um WHERE (em FNC)
no máximo um GROUP BY
no máximo um HAVING
Bloco simples

SELECT <lista atributos>
FROM <lista relações>
WHERE <condição em FNC>
GROUP BY
HAVING
Exemplo
R(sid,bid,day,rname) : RESERVA
S(sid,sname,rating,age) : SAILORS
B(bid,bname, color) : BOAT

Para cada sailor com o mais alto status (rating) e que
fez pelo menos 2 reservas de barcos vermelhos, dê
seu identificador e a data mais recente em que fez
reserva de barco vermelho.
Exemplo (continuação)
SELECT DISTINCT S.sid, Min (R.day)
FROM Sailors S, Reservas R, Boats B
WHERE S.sid = R.sid AND R.bid = B.bid
AND B.color = ‘red’
AND S.rating = (SELECT MAX (S2.rating)
FROM Sailors S2 )
GROUP BY S.sid
HAVING COUNT (*) > 1
Exemplo (continuação)


Bloco 1 : bloco interno
SELECT MAX (S2.rating) FROM Sailors S2
Resultado : Relação temporária T(A)
Bloco 2 : bloco externo
SELECT DISTINCT S.sid, Min (R.day)
FROM Sailors S, Reservas R, Boats B, T
WHERE S.sid = R.sid AND R.bid = B.bid
AND B.color = ‘red’ AND S.rating = T.A
GROUP BY S.sid
HAVING COUNT (*) > 1
Bloco SQL  Expressão algébrica
ΠA,B,..., MIN (C)
Projeção sobre os atributos do SELECT
Having ....
Group by ...
σ condições do WHERE
Seleção sobre as condições do WHERE
R1 X R2 X ... X Rn
Produto Cartesiano das relações do FROM
Plano de Execução “Canônico”
ΠA,B,...,C
A,B,...,Min(C)
ΠA,B,...,C
Having ....
Group by A
σ condições do WHERE
σ
R1 X R2 X ... X Rn
X
 Resultado R é ordenado
 O GROUP BY é executado
sobre o resultado R ordenado.
R1
 O HAVING é aplicado para eliminar
certos grupos.
 Funções de agregação são executadas sobre
os grupos finais
R2
Rn
O que é um plano de execução ?

Plano de execução correspondente à uma
expressão algébrica E


Sequência de operações equivalente à expressão
E, isto é, produzindo o mesmo resultado que E.
Para cada operação da sequência (projeção,
seleção, junção), um algoritmo é especificado
para implementar tal operação.
Exemplo
Π
σ
Projeção com ordenação
Π
Projeção com ordenação
Seleção usando indice
B+tree no atributo A
σ
Seleção usando indice Hash
no atributo B
X Hash Join
R
S
X Sort Merge Join
R
S
Planos Alternativos

Transformar a expressão algébrica “canônica”
(Π σ x ) em outra expressão equivalente.

Utilizar algoritmos alternativos para
implementar as operações algébricas
Exemplo
R(sid,bid,day,rname) : RESERVA
S(sid,sname,rating,age) : SAILORS
B(bid,bname, color) : BOAT

Quais os dias em que foram reservados barcos
vermelhos ?
Plano 1
ΠDay
σcolor = ‘vermelho’
R
B
Select R.Day
From R, B
Where R.Bid = B.Bid
AND
B.Color = ‘Vermelho’
Plano 2 (otimizado)
ΠDay
R
Select R.Day
From R
Where R.Bid IN
ΠBid
σcolor = ‘vermelho’
B
( Select B.Bid
From B
Where B.Color =
‘Vermelho’ )
Equivalências de Expressões Algébricas

Seleção

σ c1 ^ c2 ^ ... ^ cn (R) = σ c1 (σ c2 (... (σ cn (R))...)
Vantagens: Permite realizar uma única seleção,
verificando todas as condições simultaneamente, em
vez de se executar n seleções separadamente em
sequência.

σ c1 (σ c2 (R) ) = σ c2 (σ c1 (R) )
As condições podem ser executadas em qualquer ordem.
Vantagem: executar a condição mais seletiva primeiro.
Equivalências de Expressões Algébricas

Projeção

Π X1 (R) = Π X1 (Π X2 (... (Π Xn (R))...)
Onde
 cada Xi é um conjunto de atributos
 Xi está contido em Xi+1

Exemplo: Π A (R) = Π A (ΠAB (Π ABC (R)))
Vantagem: Reduz o número de execuções do algoritmo
de projeção
Equivalências de Expressões Algébricas

Produto Cartesiano e Junção

Associativa
R
R

(S
(S
T) = (R
T) = (R
Comutativa
(R
(R
S) = (S
S) = (S
R)
R)
S)
S)
T
T
Exercicio


Mostre que
R (S T) = (T
R)
S
Conclusão:


A junção entre diversas relações pode ser feita em
qualquer ordem.
Propriedade importante na geração de planos
alternativos.
Equivalências de Expressões Algébricas

Seleção e Projeção

ΠX σc (R) = σc ΠX (R)
Onde todos os atributos aparecendo na condição c estão
contidos em X

Exercício: Mostrar que isto não é verdade caso
existam atributos de c que não aparecem em X
Equivalências de Expressões Algébricas

Seleção e Junção


R c S = σc (R S)
σc (R S) = (σc R
S)


se todos os atributos de c são atributos de R e não de S
σc (R

S) = (σc R
S)
se todos os atributos de c são atributos de R e não de S
Vantagens: junção pode ser feita entre relações menores.
Exercícios
Dê um exemplo para mostrar que as
propriedades não são válidas caso c contenha
atributos de ambas as relações R e S.
 Seja c = c1 ^c2 ^c3
c1 envolve atributos de R e S
c2 envolve atributos somente de R
c3 envolve atributos somente de S
Mostre que: σc (R S) = σc1(σc2 R σc3 S)

Equivalências de Expressões Algébricas

Projeção e Produto Cartesiano

ΠX (R



S) = (ΠY R
Y = atributos de X que aparecem em R
Z = atributos de X que aparecem em S
Exemplo: ΠAB (R


ΠZ S)
S) = (ΠA R
ΠB S)
onde R(AC) e S(BC)
Vantagem: Produto cartesiano pode ser feito entre
relações menores.
Equivalências de Expressões Algébricas

Projeção e Junção

ΠX (R




cS)
= (ΠY R
Π
c Z
S)
Os atributos envolvidos na condição de junção c devem aparecer
em X
Y = atributos de X que aparecem em R
Z = atributos de X que aparecem em S
Exemplo : R(ACD), S(BEC), X = {A, B, C},
condição de junção : C = 3
ΠABC (R cS) = (ΠA R c ΠB S)
Exercicio


Dê um exemplo para mostrar que a
propriedade não é válida caso Y contenha
atributos que não apareçam em X.
Dê um exemplo para mostrar que a
propriedade não é válida caso a condição de
junção c contenha atributos que não estão em
X
Equivalências de Expressões Algébricas

Distribuição Generalizada (Projeção e Junção)

ΠX (R



c
S) = ΠX (ΠY R
c
ΠZ S)
Y = atributos de R que aparecem em X ou c
Z = atributos de S que aparecem em Y ou c
Exemplo : R(ACD), S(BEC), X = {A, B},
condição de junção : C = 3
ΠAB (R S) = ΠAB (ΠAC R c ΠBC S)
c
Equivalências de Expressões Algébricas

União, Intersecção:



Associativa
Comutativa
Seleção e Projeção podem comutar com
União, Intersecção e Diferença