Otimização de Consultas em SQL
Parte I - Planos de Execução
AULA 24 – Parte I
Profa. Sandra de Amo
GBC053 – BCC
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
O que é plano de execução canônico?

É o plano de execução correspondente
exatamente à consulta SQL recebida pelo
processador de consultas.
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= plano canônico da consulta
ΠDay
Select R.Day
From R, B
Where R.Bid = B.Bid
AND
B.Color = ‘Vermelho’
σcolor = ‘vermelho’
R
B
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
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’ )
Otimização de Consultas em SQL
Equivalência de Expressões da Algebra
Relacional
AULA 24 – Parte II
Profa. Sandra de Amo
GBC053 – BCC
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
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ício
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.
R
R
A
B
A
S
B
a1
b1
a1
b1
c1
a1
a1
b2
a1
b2
c2
a2
b2
C
A=
A
B
σ B=b1( R)
A
B
a1
b1
σ B=b1( R
S
S)
C
A
B
A=
B C
b1
b1 c1
a1
b1
b1 c1
a1
b1
b2 c2
a1
b2
b1 c1
a1
b2
b2 c2
B
σ B=b1( R)
S
A
B
A=
B
a1
b1
b1
c1
a1
b1
b2
c2
C