Banco de Dados. Otimização de consultas. Prof. Joao Eduardo Ferreira Prof. Osvaldo Kotaro Takai. Última atualização: 15 de maio de PDF
Download "Banco de Dados. Otimização de consultas. Prof. Joao Eduardo Ferreira Prof. Osvaldo Kotaro Takai. Última atualização: 15 de maio de 2006"
Rayssa Santana Angelim
1 Banco de Dados Otimização de consultas Última atualização: 15 de maio de 2006 Prof. Joao Eduardo Ferreira Prof. Osvaldo Kotaro Takai
2 Introdução Consulta em linguagem de alto nível Análise e validação Forma intermediária da Consulta Otimizador de consultas Plano de execução Gerador de código de consulta Código para se executar a consulta (compilado ou interpretado) Processamento em tempo de execução do BD Resultado da Consulta
3 Passos para otimização de consultas Tradução de consultas SQL Álgebra relacional Algoritmos básicos para execução de consultas: - ordenação externa - seleção - junção - projeção e conjunto - agregação Heurística na otimização de consultas Estimativa de custos
4 Tradução SQL Álgebra relacional Em SQL: SELECT SOBRENOME, NOME FROM EMPREGADO WHERE SALARIO > (SELECT MAX (SALÁRIO) FROM EMPREGADO WHERE NUD=5); Consulta aninhada não correlacionada Em Álgebra Relacional: I MAX SALARIO (σ NUD=5 (EMPREGADO) π ( SOBRENOME, NOME σ Salário > c (EMPREGADO)) obs.: consulta aninhada correlacionada: variável tupla do bloco externo aparece na cláusula WHERE do bloco interno.
5 Ordenação externa cláusula ORDER BY arquivos grandes FASE 1: Quebra-Ordenação interna (sort) gera runs (fragmentos ordenados do arquivo original) ordena runs grava runs b = numero de blocos do arquivo n b = espaço disponível de buffer n r = número de runs iniciais n r = b/n b Complexidade ordem = 2 * b (leitura e escrita)
6 Ordenação externa FASE 2: Intercalação (merge) n passagens pela intercalação; grau de intercalação g m (numero que runs intercaladas em cada passagem) (n b 1) < g m <n r número de passagens pelos blocos = log g m (n r ) Complexidade todo processo: (2 * b) + (log g m (b/ n b ))
7 Operação Select Algoritmos básicos Pesquisa linear Pesquisa binária Utilização de índice primário (ou chave hash) Utilização de índice primário: <, <=, >, >= Utilização de índice cluster Utilização de índice secundário (arvore B + )
8 Operação Select Algoritmos complexos Seleção conjuntiva usando índice individual Seleção conjuntiva usando índice composto Seleção conjuntiva por meio da intersecção de ponteiros de registro - conceito de seletividade = tuplas selecionadas/existentes - o otimizador deve escolher o caminho de acesso que recupere o menor número de registros de modo mais eficiente quantificar custos
9 Operação Join Junção de loop aninhado Junção de loop único Junção merge-sort Junção hash
10 Operação Project e de Conjunto Se incluir a chave, a implementação é trivial, pois as tuplas sempre serão distintas; Caso contrário, tuplas replicadas deverão ser eliminadas usando ordenação, com uso do operador DISTINCT; Produto cartesiano: deve-se evitar; UNION, INTERSECTION, DIFFERENCE Váriações das técnicas merge-sort (união compatível de conjuntos ordenados)
11 Operação Agregação MIN, MAX utilizam índices; COUNT, AVERAGE e SUM utilizam índices densos (uma entrada de índice para todo registro no arquivo original) GROUP BY: utiliza índice cluster
12 Heurística para otimização de consultas Árvores de consulta; Otimização de árvores de consulta; Árvores de consulta e planos de execução;
13 Árvores de consulta Para todo projeto localizado em 'Stafford', listar o número do projeto, o número do departamento responsável, o sobrenome, endereço e data de nascimento do gerente responsável pelo departamento. Em SQL: SELECT PNUMERO, DNUM, SNOME, DATANASC, ENDERECO FROM PROJETO AS P, DEPARTAMENTO AS D, EMPREGADO AS E WHERE P.DNUM=D.DNUMERO AND D.GERNSS=E.SSN AND P.LOCALIZACAO='Stafford ; Em Álgebra Relacional: STAFFORD_PROJS σ P.LOCALIZAÇÃO = 'Stafford' (PROJETO) CONTR_DEPT (STAFFORD_PROJS x P.DNUM = D.DNUMERO DEPARTAMENTO) PROJ_DEPT_MGR (CONTR_DEPT x D.GERNSS =E.NSS EMPREGADO) RESULT π P.NUMERO, P.DNUM, E.SNOME, E.ENDERECO, E.DATANASC (PROJ_DEPT_MGR)
14 Árvore de consulta - inicial π p P.NUMERO, P.DNUM, E.SNOME, E.ENDERECO, E.DATANASC σ P.DNUM = D.DNUMERO AND D.GERNSS =E.NSS AND P.LOCALIZAÇÃO = 'Stafford' x x E P D
15 Árvore de consulta - otimizada π p P.NUMERO, P.DNUM, E.SNOME, E.ENDERECO, E.DATANASC (3) x D.GERNSS =E.NSS (2) x P.DNUM = D.DNUMERO E (1) σ P.LOCALIZAÇÃO = 'Stafford' D P
16 Regras Gerais
17 Regras Gerais Cascata de seleção Cascata de projeção Comutatividade de join Comutatividade projeção e join Comutatividade operações de conjunto Associatividade
18 Estimativa de custos Componentes de Custo; Informações do Catálogo em função de Custo Exemplo de consulta baseada na otimização de custos.
19 Noções de Tuning Índices; produto cartesiano; cache. Estatísticas armazenamento: tabelas, índice, log, cache; Estatísticas E/S: atividade leituragravação(paginação) Estatísticas: processamento de consultas/transações Estatísticas de índices: níveis de índice x páginas folhas
20 Noções de Tuning Evitar excessiva contenção de registros; Minimizar custos adicionais (cópia/logging); Escalonamento de processos; Relação disco x memória RAM
21 FIM Referencia bibliográfica: - Elmasri, R.; Navathe, S.B. Fundamentals of Database Systems, 4th ed. Addison-Wesley, Reading, Mass., Ramakrishnan, R.; Gehrke, J., Database Management Systems, 2 nd ed., McGraw-Hill, 2000.
PROCESSAMENTO DE CONSULTAS EM BANCOS DE DADOS DE DIFERENTES TECNOLOGIAS
UNIVERSIDADE FEDERAL DE SANTA CATARINA PROGRAMA DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO ANA CRISTINA DE OLIVEIRA CIRINO COD ATO PROCESSAMENTO DE CONSULTAS EM BANCOS DE DADOS DE DIFERENTES TECNOLOGIAS
Processamento e Otimização de Consultas. Msc. Simone Dominico Orientador: Dr. Eduardo Cunha de Almeida PPGINF - UFPR
Processamento e Otimização de Consultas Msc. Simone Dominico Orientador: Dr. Eduardo Cunha de Almeida PPGINF - UFPR Conteúdo Processamento de consultas; Introdução Etapas no Processamento de Consultas