UTFPR - Universidade Tecnológica Federal do Paraná Processamento e otimização de consultas Leyza Baldo Dorini 04/Nov/2009 Programação da aula Introdução: processamento e otimização de consultas Etapas: – – – Tradução Transformação Definição do plano de execução Introdução • Os SGBDs são responsáveis por uma série de tarefas que antes ficavam sob responsabilidade do programador. Dentre estas – – – Processamento e otimização de consultas Gerenciamento de transações Recuperação de falhas Processamento de consultas • Refere-se ao conjunto de atividades envolvidas na extração de dados de um BD. Tais atividades envolvem: – Tradução de linguagens de alto nível em expressões que sejam mais adequadas para serem utilizadas no nível físico do sistema de arquivos Uma variedade de transformações para otimização de consultas Avaliação/execução de consultas – – Processamento de consultas Processamento de consultas Tradução: é responsável pelas etapas de: 1. análise léxica (identifica cláusulas SQL e nomes) 2. análise sintática (validação da gramática-regras sintáticas) 3. análise semântica (nomes usados de acordo com a estrutura do esquema) 4. conversão para uma árvore algébrica da consulta (recebe a consulta em linguagem de alto nível (consulta SQL, p. ex.), e retorna uma representação interna (árvore algébrica da consulta) Processamento de consultas • Transformação: é responsável pela geração da árvore algébrica otimizada a partir da árvore algébrica da consulta. A árvore algébrica otimizada é uma árvore de consulta equivalente (chega ao mesmo resultado, mas que processa de forma mais eficiente). Também chamada de fase de Otimização Algébrica. Processamento de consultas Definição do plano de execução: é a fase de análise de alternativas de definição de estratégias de acesso (escolha de algoritmos para implementação de operações). Leva em conta a existência de índices, estimativas sobre os dados (tamanho de tabelas, etc, ...). Gera uma árvore com indicação de estratégias de acesso. Processamento de consultas Gerador de código: recebe a árvore com indicação de estratégias de acesso (plano de execução) e gera código executável correspondente. Processador run time: recebe o código executável, processa a consulta e retorna os resultados ao usuário. Otimização de consultas A otimização de consultas é feita basicamente em duas etapas: • Otimização Algébrica (ou baseada em regras ou heurística) • Plano de execução (ou baseada em custos) Otimização de consultas: otimização algébrica • Otimização algébrica – É responsável por gerar uma árvore algébrica otimizada, equivalente à árvore inicial da consulta, mas que processa mais rapidamente. Recebe como entrada a árvore da consulta inicial, e gera na saída uma árvore da consulta otimizada. Tem como base as regras de equivalência algébrica e o algoritmo de otimização algébrica – – Otimização de consultas: otimização algébrica • Otimização algébrica (considerações): – As regras de equivalência algébrica devem ser conhecidas pelo otimizador para que possam ser geradas transformações válidas; O algoritmo de otimização algébrica indica a ordem de aplicação das regras e de outros processamentos de otimização. – Otimização de consultas: plano de execução • Tem como objetivo analisar alternativas de processamento e escolher a melhor alternativa dentre as estimadas. Para avaliar o custo de uma alternativa, analisa estimativas sobre os dados (tamanho das tabelas, existência de índices, seletividade, ...) e o respectivo custo dos algoritmos de processamento de operações algébricas. • Processamento de consultas • Em resumo: – – – Tradução Transformação Criação de plano (estratégia) de acesso • A princípio, vamos ver de maneira global. Depois, veremos os detalhes envolvidos em cada etapa. Processamento de consultas PC: tradução PC: tradução • O primeiro passo consiste em traduzir a consulta expressada em uma linguagem de alto nível (ex: SQL) para uma forma mais adequada para ser utilizada como representação interna de uma consulta ao sistema. PC: tradução Consulta SQL – Adequada para uso humano; – Não adequada ao processamento pelo SGBD: • descreve uma sequência de passos (procedimento) a ser seguida; • Não descreve uma estratégia eficiente para a implementação de cada passo no que tange o acesso em nível físico (arquivos do BD). PC: tradução • Exemplo de representação adequada: baseada na álgebra relacional, criando uma árvore (algébrica) da consulta. Ex: SELECT m.crm, m.nome, a.andar FROM Medicos m, Ambulatorio a WHERE m.espec = “ortopedia” AND a.andar = 2 AND m.nro = a.nro • A árvore é a estrutura que representa o mapeamento da consulta para a álgebra relacional PC: tradução • Os nós internos representam operações algébricas e os nós folha as relações do BD ou resultados intermediários Neste passo, o analisador sintático também verifica a sintaxe da consulta do usuários, se os nomes das relações existem, etc • PC: tradução (visão geral) • De forma geral, uma consulta SQL é traduzida em uma expressão equivalente da álgebra relacional estendida – e é representada em uma estrutura de dados de árvore de consulta – que é então otimizada Em geral, as consultas SQL são decompostas em blocos de consultas, que formam as unidades básicas que podem ser traduzidas em operadores algébricos otimizados • PC: tradução • Um bloco de consulta contém uma única expressão SELECT-FROM-WHERE, bem como cláusulas GROUP BY e HAVING, se elas forem partes do bloco Por isso, consultas consultas aninhadas dentro de uma consulta são identificadas por blocos separados (não-correlacionadas é + fácil) Como a SQL inclui operadores de agregacão (MAX, MIN...) eles também devem estar incluídos na álgebra relacional estendida • • PC: tradução • Considere a seguinte consulta SQL: SELECT LNAME, FNAME FROM EMPLOYEE WHERE SALARY > (SELECT (MAX) SALARY FROM EMPLOYEE WHERE DNO = 5); PC: tradução • Essa consulta inclui uma subconsulta aninhada, seria decomposta em 2 blocos. – Bloco interno (SELECT (MAX) SALARY FROM EMPLOYEE – Bloco externo WHERE DNO = 5) SELECT LNAME, FNAME FROM EMPLOYEE WHERE SALARY > c PC: tradução SELECT FROM WHERE LNAME, FNAME EMPLOYEE SALARY > ( SELECT FROM WHERE MAX (SALARY) EMPLOYEE DNO = 5); SELECT FROM WHERE LNAME, FNAME EMPLOYEE SALARY > C SELECT FROM WHERE MAX (SALARY) EMPLOYEE DNO = 5 πLNAME, FNAME (σSALARY>C(EMPLOYEE)) ℱMAX SALARY (σDNO=5 (EMPLOYEE)) PC: transformação PC: transformação • A base é composta por: – Regras de equivalência algébrica: devem ser conhecidas pelo otimizador para que possam ser geradas transformações válidas Algoritmo de otimização algébrica indica a ordem de aplicação das regras e de outros procedimentos de otimização Entrada: árvore da consulta inicial; Saída: árvore da consulta otimizada (pode manter a mesma árvore). – Transformação: – – Transformações de Expressões Relacionais • Uma consulta pode ser expressa de diversas maneiras diferentes, com diferentes custos de avaliação. – Equivalêcia de Expressões; – Regras de Equivalência; – Exemplos de Transformações; Equivalência de expressões: exemplo • Considerando as tabelas a seguir e suas instâncias, encontre os nomes de todos os clientes que possuem uma conta em qualquer agência localizada no Brooklyn. Para resolver esta expressão, seguindo a forma como ela está escrita, é necessário criar uma relação intermediária grande Equivalência de expressões Equivalência de expressões Equivalência de expressões • Entretanto, somente as tuplas que pertencem a agências localizadas no “Brooklyn” são interessantes. Reescrevendo a consulta, consegue-se eliminar a necessidade de considerar as tuplas que não têm cidade_agência = “Brooklyn”, reduzindo o tamanho do resultado intermediário: • Equivalência de expressões Equivalência de expressões Equivalência de expressões • Dada uma expressão de álgebra relacional, a função do otimizador de consulta propor um plano de avaliação da consulta que gere o mesmo resultado da expressão fornecida e que seja uma maneira menos onerosa de gerar o resultado (ou que, pelo menos, não seja muito mais cara que a maneira mais barata). Para isso o otimizador precisa gerar planos alternativosque produzam o mesmo resultado da expressão dada e escolher o menos caro. • Regras de Equivalência Algébrica • Uma regra de equivalência diz que expressões de duas formas são equivalentes se podemos transformar uma na outra preservando a equivalência. Preservar a equivalência significa que as relações geradas pelas duas expressões têm o mesmo conjunto de atributos e contêm o mesmo conjunto de tuplas, embora seus atributos possam estar ordenados de forma diferente. • Regras de Equivalência Algébrica • As regras de equivalência são usadas pelo otimizador para transformar expressões em outras logicamente equivalentes. Assuma que: – – – θ: denota predicados; L: denotas listas de atributos; E: denota expressões da álgebra relacional. • Exemplos de transformações Otimização Heurística • Uma árvore de consulta pode ser transformada passo a passo em outra árvore de consulta mais eficiente. Entretanto é preciso assegurar que os passos de transformação sempre levem a uma árvore de consulta equivalente. Determinadas regras de transformação preservam essa equivalência. • • Resumindo... • • • • Determinar a árvore algébrica inicial correspondente a esta consulta Fazer seleções o mais cedo possível Converter produtos cartesianos seguidos de seleção em junção Fazer projeções o mais cedo possível PC: definição do plano de acesso (execução) PC: definição do plano de acesso (execução) • Análise de alternativas de definição de estratégias de acesso: escolha de algoritmos para implementação de operações, existência de índices, estimativas sobre os dados (tamanho de tabelas, por exemplo) Considera algoritmos predefinidos para implementação de passos do processamento e estimativas sobre os dados • A Escolha de Planos de Avaliação • Em outras palavras... – – A geração de expressões é apenas parte do processo de otimização de consultas. Um plano de avaliação define exatamente qual algoritmo será usado para cada operação e como a execução das operações é coordenada. A Escolha de Planos de Avaliação Próxima aula... • Veremos otimização baseada em custos com mais detalhes!! Otimização baseada em custo • O otimizador baseado no custo gera uma faixa de planos de avaliação a partir de uma determinada consulta usando as regras de equivalência e escolhe aquele de menor custo. Para uma consulta complexa, o número de planos diferentes por ser muito grande. • PC: otimizador de consultas • A transformação e a definição do plano de execução compõem o otimizador de consultas Otimização de consultas • Em resumo, a otimização de consultas é o processo de selecionar o plano de execução mais eficiente enttre as muitas estratégias possíveis Isso evita que o usuário tenha que fornecer a melhor consulta Em resumo: otimização de consultas é o processo de melhoria da estratégia de processamento • • • Exercício!!!