AULA: Processamento e Otimizacao de Consultas (Cap. 12-15 : Ramakrishnan)
===============================================
1. O Catalogo do Sistema (ou Dicionario de Dados)
------------------------
Contém informações sobre o SGBD e das bases de dados (metadados).
. do SGBD: tamanho do buffer, tamanho da página
. de cada tabela: - nome da tabela, nome do arquivo, estrutura do arquivo
- para cada atributo: nome, tipo, ordem
- para cada índice: nome, estrutura, chave de pesquisa
- restrições de integridade
. de cada visão: nome e definição
. informações sobre autorização de acesso
Contém estatísticas utilizadas para otimização de consultas.
- cardinalidade da relação: NTuplas(R)
- tamanho da relação: tamanho em páginas NPaginas(R)
- cardinalidade do índice: quantidade de valores distintos da chave de
pesquisa - NChaves(I)
- tamanho do índice: tamanho em páginas INPaginas(I) - para árvores B+,
este valor corresponde ao número de páginas folha.
- altura do índice: IAltura(I) para árvores B+
- domínio do índice: menor e maior valores da chave de pesquisa
IMenor(I), IMaior(I)
As informações do catálogo são também armazenadas em tabelas. Por exemplo,
informações sobre atributos podem ser mantidos em uma relação Cat_Atributos
com o seguinte esquema:
Cat_Atributos( nome_atrib, nome_rel, tipo, posicao)
Avaliação de Operações
----------------------
- a escolha do algoritmo depende de: tamanho das tabelas, existência de
índices, ordenação das tuplas, tamanho do buffer, política de reposição do
buffer
- Métodos de Acesso: as diferentes formas nas quais as tuplas de uma
relação podem ser recuperadas. Técnicas:
. Indexado: através da utilização de um índice
. Iterativo: recuperação de todas as tuplas da relação, uma por uma
. Particionado: agrupamento de tuplas por uma chave de ordenação,
geralmente através de hash ou algoritmo de ordenação
Para utilizar o método indexado é necessário que o índice "case" com a
condição de seleção. Considere uma seleção na forma normal conjuntiva
(CNF), onde cada termo está na forma "atrib op valor".
- um índice com tabela hash casa com a condição se todos os termos forem
da forma "atrib = valor" e todos os atributos da seleção fazem parte da
chave de pesquisa do índice
- um índice em árvore casa com uma condição em CNF se os atributos nos
termos formam um prefixo da chave de pesquisa do índice. Por exemplo,
e são prefixos da chave , mas e não são.
Os termos que casam com o índice são chamados de "conjuntivos primários"
da seleção.
-------------------
SELETIVIDADE do método de acesso:
corresponde ao número do páginas (de índice e de dados) recuperadas para
obter todas as tuplas desejadas. O método MAIS SELETIVO é aquele que
recupera o menor número de páginas.
Exemplo 1: condição idAviao=100 and idPiloto=5 (da tabela Reserva)
tabela hash (H) com chave de pesquisa
seletividade = NPaginas(Reserva) * (1 / NChaves(H))
-------------------
O FATOR DE REDUÇÃO é a fração do
número de tuplas de uma relação que satisfazem uma determinada condição.
Exemplo 2: condição data > 16/10/2005
árvore B+ (A) com chave de pesquisa
fator de redução = (IMaior(A) - 16/10/2005) / (IMaior(A)-IMenor(A))
Algoritmos para Operações Relacionais:
-------------------------------------
Esquema exemplo: Reserva( idPiloto, idAviao, data, tipoReserva)
-----------------------
Piloto ( idPiloto, nome, idade, nivel)
--------
Base de dados:
. cada página contém 100 tuplas de Reserva, com total de 1000 páginas
(ou seja, total de 100.000 tuplas)
. cada página contém 80 tuplas de Piloto, com total de 500 páginas
(ou seja, total de 40.000 tuplas)
1. Seleção
----------
- condição: selecao_{ nome < 'C*'} (Piloto)
- se não existir um índice sobre o atributo nome: scan da relação Piloto
- se existir índice B+ sobre o atributo nome:
. considerando que existem 40.000 tuplas em Piloto (ou 500 páginas),
com distribuição uniforme de valores: aprox. 10% das tuplas estão no
resultado.
. quantidade de I/O com o índice clusterizado: 50
. quantidade de I/O com o índice não clusterizado: 4.000 no pior caso
Regra geral:
-----------
se o número de tuplas a serem recuperadas é maior que 5% do total é
melhor fazer um scan sobre a relação do que utilizar um índice não
clusterizado.
- disjunção:
. scan da relação, união de resultados (com ou sem ordenação da
entradas por id da página)
. transformação em união de consultas, ou se forem termos sobre o mesmo
atributo transformação em uma condição envolvendo IN, ou bitmaps
2. Projeção
-----------
- pode ser implementada fazendo um scan da relação ou de um índice caso
exista um que contenha todos os atributos da operação
- a parte com maior custo é a remoção de duplicações. Isto é implementado
utilizando particionamento (ordenação ou hashing).
. particionamento utilizando hashing: apropriado quando o tamanho do
buffer não é muito pequeno com relação ao tamanho da relação (cada
partição deve caber no buffer) e a distribuição com a função hash e'
relativamente uniforme.
- no caso de ordenação, a operação pode ser otimizada combinando a
primeira passada do algoritmos de ordenação com a eliminação dos
atributos que não estão no resultado da projeção.
- no caso de existir um índice com os atributos da projeção basta
recuperar todas as entradas do índice e eliminar as duplicações. Esta
tarefa é fácil, pois as duplicações estão em posições adjacentes no
índice.
3. Junção
---------
- geralmente a operação mais cara de ser realizada
- considere a operação Reserva junção Piloto
- se existir um índice sobre idPiloto na relação Piloto:
. podemos utilizar "index nested loop join": scan da relação Reserva e
para cada tupla, faz a busca utilizando o índice.
custo: 1000 I/O para fazer scan de Reserva +
1.2 * 100.000 I/O para busca utilizando hash
(1.2 é o custo típico para tabelas hash) +
1 * 100.000 I/O para busca do registro de dados
(se o índice não for clusterizado) =
221.000 I/O
. se o índice não existir podemos utilizar o "sort-merge join":
primeiro ordena-se cada uma das relações e depois executa-se o merge.
custo de ordenação de Reserva supondo buffer de 100 páginas
passo 1: 1000 páginas Reserva / 100 páginas de buffer =
10 grupos de 100 páginas ordenadas
passo 2: merge de 10 grupos ordenados
Em cada passo há leitura e gravação das páginas de Reserva,
portanto: custo= 2 * 1000 páginas * 2 passos = 4000 I/O
custo de ordenação de Piloto supondo buffer de 100 páginas
passo 1: 500 páginas Piloto / 100 de buffer =
5 grupos de 100 páginas ordenadas
passo 2: merge de 5 grupos ordenados
Em cada passo há leitura e gravação de 500 páginas, portanto:
custo = 2 * 500 páginas * 2 passos = 2000 I/O
custo do merge de Reserva e Piloto:
1000 páginas de Reserva + 500 páginas de Piloto = 1500
custo total do sort-merge = 4000 + 2000 + 1500 = 7500 I/O
Em geral, o custo do sort-merge e' (quantidade de I/Os):
2*n (log_{b-1}( n/b) + 1), onde
n é o número de páginas da relação e b e' o tamanho do buffer.
. (2*n) porque cada passo le e escreve todas as páginas
. primeiro passo: 2*n (daí vem o +1)
. o número de passos e' log_{{b-1}( n / b) porque depois do
primeiro passo existem n / b conjuntos ordenados e em cada
subsequente são juntados (b-1) conjuntos porque 1 pagina é a de
saída.
. o custo to sort-merge join é bem menor do que o index nested loop.
Porém, a vantagem do segundo é que ele é incremental. Ou seja, se
existir alguma seleção sobre a relação Reserva antes de fazer a junção,
podemos evitar o processamento da junção de toda a relação. Por
exemplo, se estivermos interessados apenas nas reservas no avião com
idAviao = 501, podemos primeiro realizar a seleção e apenas buscar na
relação Piloto aqueles que reservaram tal avião (utilizando o índice)
ao invés de ordenar toda a relação Piloto para então fazer a junção.
4. Outras Opearações
--------------------
group by, having: utiliza ordenação
operações de conjunto (união, diferença e interseção): o maior custo
corresponde a eliminação de duplicações como na projeção
OTIMIZAÇÃO DE CONSULTAS
=======================
consulta em ling. de alto nivel (SQL - declarativa)
|
v
+------------------------+
|exame,analise,validacao |
+------------------------+
|
v
forma intermediaria (árvore de consulta)
|
v
+------------------------+
|otimizador de consulta |
| | +-------------+
| gerador estimativa| | gerenciador |
| de planos de custo --------> | do catálogo |
| de plano | +-------------+
+------------------------+
|
v
plano de execucao
|
v
+-------------------------+
| processador de consulta |
+-------------------------+
|
v
resultado da consulta
- o otimizador faz o planejamento da estrategia de execucao:
obter a estrategia otima pode consumir muito tempo
- um plano de execução de consulta é uma árvore de álgebra relacional,
onde cada nodo é anotado ou com o método de acesso para acesso a uma
relação ou com o algoritmo utilizado para executar a operação da álgebra
relacional.
Exemplo: select p.nome
from Reserva r, Piloto p
where r.idPiloto = p.idPiloto and
r.idAviao = 100 and p.nivel > 5
em A.R: projecao_{nome}
(selecao_{idAviao=100 ^ nivel > 5}
(Reserva juncao_{idPiloto = idPiloto} Piloto))
plano de execução:
projecao_{nome} (on-the-fly)
|
|
selecao_{idAviao=100 ^ nivel > 5} (on-the-fly): pipeline
| do resultado da operação
| abaixo
|
juncao_{idPiloto = idPiloto} (nested-loop)
/ \
/ \
(scan) Reserva Piloto (scan)
por convenção por convenção
esta é a tabela esta é a tabela
EXTERNA do INTERNA do
nested loop nested loop
- on-the-fly: pipeline do resultado da operação abaixo na árvore. Caso
contrário, o resultado da operação abaixo é primeiro MATERIALIZADA (ou
seja, armazenada em uma relação temporária).
- custo do plano acima: 1000 páginas de Reserva +
1000 * 500 (para cada página de Reserva, lê-se
todas as páginas de Piloto)
= 501.000 I/Os
- Alternativa 1: fazer as seleções primeiro para diminuir o tamanho das
tabelas
projecao_{nome} (on-the-fly)
|
|
juncao_{idPiloto = idPiloto} (sort-merge join)
/ \
/ \
selecao_{idAviao=100} selecao_{nivel > 5}
(scan- escreve | | (scan- escreve em T2)
em T1) | |
| |
(scan) Reserva Piloto (scan)
custo = scan de Reserva com seleção, supondo que existem 100 aviões e
distribuição uniforme: 1000 (entrada) + 10 (saida)
scan de Piloto com seleção, supondo que existem 10 níveis e
distribuição uniforme: 500 (entrada) + 250 (saida)
sort-merge, considerando buffer de 5 páginas:
ordenação de T1 (em dois passos): 2 * 2 * 10 = 40
ordenação de T2 (em quatro passos): 2 * 4 * 250 = 2000
merge: 10 + 250 = 260
total = 4060 I/Os
Alternativa 2: utilizar block-nested loop:
No buffer de 5 páginas, 3 são utilizadas para ler as páginas de T1
e para cada grupo (de 3) o arquivo T2 é lido (utilizando uma única
página) e quando houver registros que satisfaçam a condição de junção
um registro combinando ambos é escrito na página de saída.
custo: da seleção (igual a alternativa anterior): 1760
leitura de T1: 10
junção com T2: (10 páginas de T1 / 3 páginas do buffer) * 250
páginas de T2
total= 2770 I/Os
Alternativa 3: fazer também as projeções a medida que faz as seleções para
diminuir o tamanho dos registros para fazer a junção
Alternativa 4: na presença de índices
. suponha que existe um índice hash clusterizado em idAviao sobre Reserva
. suponha que existe um índice hash em idPiloto em Piloto
projecao_{nome} (on-the-fly)
|
|
selecao_{nivel > 5} (on-the-fly)
|
|
|
juncao_{idPiloto = idPiloto} (index nested loop com pipeline)
(com indice, / \
sem escrever) / \
selecao_{idAviao=100} Piloto (hash em idPiloto)
|
|
(hash em Reserva
idAviao)
custo: selecao em Reserva: 100.000 tuplas com distribuição uniforme entre
100 aviões, totaliza 1000 tuplas resultantes em 10 páginas (já
que o índice é clusterizado - 10 I/Os
junção: para cada uma das 1000 tuplas, buscar no índice hash (1.2
I/O) e o registro de dados: 1000 * (1.2 + 1)
total: 2210 I/Os
FUNCIONAMENTO DE UM OTIMIZADOR DE CONSULTAS TÍPICO
--------------------------------------------------
1. enumeração de planos de consultas alternativos que sejam equivalentes,
utilizando equivalências de expressões da álgebra relacional.
. seleções e produto cartesiano podem ser combinados em junções
. junções podem ser reordenadas
. seleções e projeções podem ser utilizadas para diminuir o tamanho das
relações
. em geral os otimizadores de consulta só consideram left-deep plans
para fazer as junções
==> além de diminuir o espaço de busca, elas permitem que a consulta
seja toda executada utilizando pipeline (fully pipelined plans)
2. cálculo da estimativa de custo de cada plano
Equivalências em Álgebra Relacional
-----------------------------------
(Seção 15.3 do livro do Ramakrishnan)