Tópico_3

Prévia do material em texto

1 
Tópico 3 
 
3. Otimização e processamento de consultas 
3.1. Etapas do processamento da consulta 
 
 
 
- Análise léxica, análise sintática e validação 
o Identificação dos símbolos da linguagem. 
o Verificação da sintaxe da consulta. 
o Verificação se os nomes dos atributos e relações são válidos no esquema do 
banco de dados específico que está sendo consultado. 
o O resultado desta etapa é uma representação interna da consulta em forma de 
uma estrutura de dados de árvore denominada árvore de consulta. 
- Otimizador de consulta 
o Nesta etapa o SGBD planeja uma estratégia de execução para recuperar o 
resultado da consulta. 
 2 
o A estratégia escolhida é razoavelmente eficiente para executar a consulta e 
nem sempre é a melhor pois encontrar a estratégia ótima pode consumir 
muito tempo. 
o Desta forma, “planejamento de uma estratégia de execução” é um nome 
mais adequado que “otimização de consulta”. 
- Gerador de código de consulta 
o Possui a tarefa de gerar o código de consulta para executar o plano escolhido 
na etapa anterior. 
- Processador em tempo de execução do banco de dados 
o Nesta etapa, o código da consulta é executado para produzir o resultado 
final. 
 
Árvore de consulta 
- Primeiro, uma consulta SQL é traduzida em uma expressão equivalente da álgebra 
relacional. Depois, esta expressão é representada por uma estrutura de dados de 
árvore de consulta, que é então otimizada. 
- Numa árvore de consulta, as relações de entrada da consulta são os nós-folhas e as 
operações da álgebra relacional são representados como nós internos. 
- Uma execução desta árvore consiste na execução de uma operação do nó interno 
quando os seus operandos estiverem disponíveis. 
- Em seguida, este nó interno é substituído pela relação resultante da execução da 
operação. 
- A execução termina quando o nó raiz é executado. 
 
 
 
- Exemplo: Recuperar o número do projeto, o número do departamento responsável e 
o último nome, endereço e data de nascimento do gerente do departamento. 
- SELECT P.pnumero, P.dnum, E.unome, E.endereco, E.datanasc 
FROM Projeto P, Departamento D, Empregado E 
 3 
WHERE P.dnum = D.dnumero AND D.gerssn = E.ssn AND 
P.plocalizacao = ‘Stafford’; 
- πpnumero, dnum, unome, endereco, datanasc (((σplocalizacao=’Stafford’ (Projeto)) 
dnum=dnumero (Departamento)) gerssn = ssn (Empregado)) 
 
 
3.2. Informações no catálogo do SGBD para a estimativa do 
custo 
- A otimização baseada em estimativa de custo consiste em comparar os custos de 
execução de uma consulta usando diferentes estratégias de execução e escolher 
aquela que possui o menor custo. 
- As informações que sejam necessárias para as funções de custo devem se manter 
atualizadas no catálogo para o otimizador estimar os custos de várias estratégias de 
execução. 
- Informações úteis: 
o Tamanho da tabela 
o Número de registros da tabela (r) 
o Número de blocos (b) 
o Métodos de acesso primário 
o Número de níveis (x) em um índice multinível 
o Número de valores distintos (d) de um atributo 
o Seletividade (sl) de um atributo: fração dos registros que satisfazem uma 
condição de igualdade baseada no atributo. 
o Cardinalidade da seleção (s): número médio de registros que irão satisfazer 
uma condição de seleção de igualdade baseada no atributo. s = sl * r. 
- Atributo chave: d = r; sl = 1/r; s=1 
- Atributo não chave: sl = 1/d; s=r/d 
 
 4 
3.3. Otimização baseada em heurísticas. 
- Funciona bem na maioria dos casos, mas não há garantias de que funcione bem em 
todos os casos possíveis. 
- As regras reordenam as operações em uma árvore de consultas. 
- Muitas expressões diferentes da álgebra relacional podem ser equivalentes, ou seja, 
podem corresponder à mesma consulta. 
- O analisador de consultas gerará uma árvore de consulta inicial sem realizar 
qualquer otimização. Esta árvore inicial é bastante ineficiente. 
- As regras de otimização de consulta heurística utilizam expressões de equivalência 
da álgebra relacional para transformar a árvore inicial na árvore final otimizada, que 
seja eficiente ao ser executada. 
- Exemplo de transformação: Encontrar os últimos nomes dos empregados nascidos 
após 1957 que trabalhem no projeto ‘Aquarius’. 
- SELECT E.unome 
FROM Empregado E, Trabalha_Em T, Projeto P 
WHERE P.pjnome = ‘Aquarius’ AND P.pnumero = T.pno AND T.essn = E.ssn 
AND E.datanasc > ’31-12-1957’ 
 
OBS: Nas figuras a seguir, trocar: 
 PNOME por PJNOME 
 NRP por PNO 
 
 
 
- Suposição: Projeto – 50 registros (100 bytes cada); Trabalha_Em – 2000 registros 
(50 bytes cada); Empregado – 500 registros (150 bytes cada) 
- Resultado do produto cartesiano: 50 milhões de registros com 300 bytes cada. 
- Devemos aplicar primeiramente as operações SELECT para reduzir o número de 
tuplas que aparecem no produto cartesiano. 
 
 5 
 
 
- A seleção na tabela de Projeto deve trazer menos registros que a seleção da tabela 
de Empregado, portanto é melhor primeiro resolver a junção entre Projeto e 
Trabalha_Em. 
 
 
 
 6 
- Substituição de qualquer operação de produto cartesiano que seja seguida de uma 
condição de junção por apenas uma operação de junção. 
 
 
 
- Movimentação de operações de projeção para níveis mais baixos na árvore de 
consulta para reduzir os atributos das relações intermediárias. 
 
 
 
 
 7 
3.4. Otimização baseada em estimativas de custo. 
- Nesta abordagem, devemos limitar o número de estratégias de execução a ser 
considerado para que não seja gasto muito tempo fazendo as estimativas de custo. 
- Duas opções: 
o Consultas compiladas: otimização é feita em tempo de compilação e o 
código da estratégia de execução resultante é armazenado e executado 
diretamente em tempo de execução. 
o Consultas interpretadas: otimização é feita em tempo de execução. 
- As funções de custo utilizadas na otimização de consultas são estimativas e não 
funções exatas de custo. 
- O custo da execução de uma consulta inclui os seguintes componentes: 
o Custo de acesso ao armazenamento secundário(busca, leitura e escrita de 
blocos de dados); Custo de armazenamento (arquivos temporários); Custo de 
computação (operações sobre os buffers); Custo do uso de memória (número 
de buffers de memória necessários); Custo de comunicação (transporte dos 
resultados para a origem). 
- Como é difícil incluir todos esses componentes de custo em uma função de custo 
devido à dificuldade em atribuir pesos adequados aos componentes do custo, 
geralmente somente o acesso a disco é considerado. 
- Exemplo: 
SELECT P.pnumero, P.dnum, E.unome, E.endereco, E.datanasc 
FROM Projeto P, Departamento D, Empregado E 
WHERE P.dnum = D.dnumero AND D.gerssn = E.ssn AND 
P.plocalizacao = ‘Stafford’; 
- Informações: 
 
TABELA COLUNA NUM_DISTINTOS 
Projeto plocalizacao 200 
Projeto pnumero 2000 
Projeto dnum 50 
Empregado SSN 10000 
 
TABELA NUM_LINHAS BLOCOS 
Projeto 2000 100 
Departamento 50 5 
Empregado 10000 2000 
 
INDICE UNICIDADE NIVELB BLOCOS_FOLHAS CHAVES_DISTINTAS 
Proj_Ploc não_única 1 4 200 
Emp_SSN único 1 50 10000 
NivelB é o número de níveis sem o nível folha 
 
- Duas opções para executar a operação de seleção na tabela de Projeto 
(P.plocalizacao = ‘Stafford’) 
a) Varredura da tabela (busca linear) 
b) Utilização do índice Proj_Ploc 
 8 
 
a) Custo = 100 acessos a blocos 
b) seletividade (sl) = 1/200 
cardinalidade (s) = sl * r (número de registros); s = 2000/200 = 10 
Como o índice é não-único, o otimizador supõe uma distribuição de dados 
uniforme e estima o número de ponteiros para cada valor de plocalizacao 
como sendo igual a 10. 
O número de níveis no índice é 2 (raiz mais níveisfolha). 
Custo: 12 acessos a blocos (2 para o índice e 10 para os blocos de dados). 
- Custos para execução das junções: 
o Opções: 
a. Projeto  Departamento Empregado 
b. Departamento  Projeto Empregado 
c. Departamento  EmpregadoProjeto 
d. Empregado Departamento Projeto 
o Opção (a) 
- Supondo que a seleção já tenha sido aplicada à tabela de Projeto, a 
operação resultaria em 10 linhas. Como 1 bloco da tabela de Projeto 
possui 20 linhas (2000/10), a tabela resultante caberia em apenas 1 
bloco. Chamaremos esta tabela de Temp1. 
- Temp1  Departamento 
 Ler o bloco de Temp1 e cada um dos 5 blocos de 
Departamento uma vez. Custo: 6 acessos a bloco mais o custo 
de gravar a tabela temporária Temp2. Custo parcial = 7. 
 Tamanho de Temp2: cada registro de Temp1 se relacionará a 
apenas um registro de Departamento, uma vez que dnumero é 
chave primária. Portanto, Temp2 também terá 10 linhas. 
Suponha que sejam necessários 2 blocos para armazenar estes 
10 registros. 
- Temp2  Empregado 
 Podemos utilizar o índice Emp_SSN. 
 Ler cada bloco de Temp2 e buscar no índice o valor 
correspondente ao gerSSN. Cada consulta ao índice necessita 
de 1 acesso à raiz, um acesso à folha e um acesso ao bloco de 
dados. Portanto, 10 consultas exigem 30 acessos a blocos. 
Custo: 30 acessos a blocos mais 2 acessos a bloco a Temp2. 
Custo parcial = 32. 
- Custo Total: 7 + 32 = 39 acessos a blocos. 
o O otimizador estimará os custos das outras junções e escolherá aquela que 
apresente a menor estimativa.