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)