Geração de Planos de Execução Planos para Consultas Aninhadas
AULA 28
Profa. Sandra de Amo
GBC053 – BCC
Consultas com uma única relação no
FROM

Quando não se tem nenhum índice nos
atributos aparecendo no WHERE




SCAN para selecionar as tuplas satisfazendo a condição
do WHERE
Ao mesmo tempo (on the fly) aplica-se a projeção nos
atributos do SELECT
Grava-se o resultado
Ordena-se o resultado para implementar o GROUP BY e
eliminar duplicatas (caso for solicitado na consulta –
DISTINCT)
Consultas com uma única relação no
FROM

Quando se tem índices nos atributos aparecendo no
WHERE (em FNC)




Gera plano(s) utilizando o(s) índice(s) referente(s) ao(s) atributo(s)
com maior fator de redução.
Gera plano(s) utilizando os indices para cada atributo que os tenha,
ordena os rids por page ids e faz-se a intersecção dos pages ids
Projeções são executadas on the fly.
Em caso de Group By (ou de DISTINCT) : grava-se o resultado
obtido após a seleção, ordena-se as tuplas e executa o agrupamento,
eliminando-se duplicatas se for o caso.
Consultas com várias relações no
FROM

Só considera os planos com profundidade à
esquerda.
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).
Enumeração dos planos com
profundidade à esquerda
Passo 1: Enumera-se todos os planos de 1 única relação Ri, considerando-se todas as
possíveis seleções sobre atributos de Ri que podem ser feitas antes dos Join, além de
projeções de atributos não mencionados no SELECT ou nos Joins ou no restante dos
atributos do WHERE que não foram “empurrados”para dentro do Join.
Escolhe-se os melhores planos de 1 única relação.
Passo 2: Gera-se todos os planos de 2 relações, considerando-se todas as combinações
de planos obtidos no passo 1
Sempre que o algoritmo do JOIN permitir, a relação externa não é materializada, e o
JOIN é executado em pipeline
Caso o método de JOIN é um INDEX NESTED LOOP JOIN, considera-se planos
para a relação interna que não envolvam indices em atributos diferentes do atributo de
junção.
Escolhe-se os melhores planos de 2 relações.
Passo 3: Gera-se todos os planos com 3 relações, combinando-se cada plano otimal
obtido no passo 2 com cada plano otimal obtido no Passo 1.
Passo 4: assim por diante…
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
Planos para Consultas Aninhadas
SELECT S.sname
FROM Sailors S
WHERE S.sid IN (SELECT R.sid
FROM Reserves R
WHERE R.bid = 103)

O Plano de execução canônico para esta consulta é o mesmo plano (otimizado)
produzido pelo otimizador para a consulta:
SELECT S.sname
FROM Reservas R, Sailors S
WHERE R.Sid = S.Sid AND R.bid = 103)


Um bom programador pode “guiar” o otimizador, dirigindo-o para o melhor plano
de execução.
Um bom programador pode forçar o otimizador a produzir um plano que não seria
produzido automaticamente.
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 programador formular a consulta de
modo a evitar aninhamentos e/ou correlações.
FIM
Boa Prova Final e Boas Férias !!!