Processamento e Otimização de Consultas em SGBDs

Processamento e Otimização de Consultas Prof Daniel Cosme Mendonça Maia Internamente os SGBD utilizam técnicas para processar otimizar e executar consultas de alto nível Toda consulta SQL precisa ser lida analisada e validada A varredura leitura identifica os tokens de consulta como palavras chave SQL nomes de atributos e nomes de relação O Analisador sintático verifica a sintaxe da consulta e o processo de validação verifica se todos os nomes de atributo e relação são válidos no esquema de BD Uma representação interna da consulta é criada como uma estrutura em árvore ou em grafo árvore de consultagrafo de consulta O SGBD precisa idealizar uma estratégia de execução ou plano de execução para recuperar os resultados da consulta com base nos arquivos do banco de dados O processo de escolha de uma estratégia adequada para processamento de consultas é conhecido como otimização de consultas O módulo otimizador de consulta tem a tarefa de produzir um bom plano de execução e o gerador de código dá origem ao código para executar esse plano O processador em tempo de execução do BD tem a tarefa de executar o código da consulta seja no modo interpretado ou compilado para produzir o resultado da consulta Se houver um erro uma mensagem de erro é gerada pelo processador O termo otimização deve ser considerado como um plano de uma boa estratégia de execução de consulta Em bancos de dados que possuem níveis mais baixos de consulta o programador deve escolher uma estratégia de execução de consulta enquanto escreve o programa de banco de dados Já os SGBDs que utilizam linguagem de consulta de alto nível como SQL é processo de otimização de consultas é necessário Traduzindo consultas SQL para álgebra relacional Uma consulta SQL é primeiro traduzida para uma expressão equivalente da álgebra relacional estendida representada como uma estrutura de dados de árvore de consulta que é então otimizada Normalmente as consultas SQL são decompostas em blocos de consulta que formam as unidades básicas que podem ser traduzidas em operadores algébricos e otimizadas Exemplo SELECT Unome Pnome FROM Funcionario WHERE Salario SELECT MAXSalario FROM Funcionario WHERE Dnr 5 A consulta inclui uma subconsulta aninhada e portanto seria decomposta em dois blocos O bloco mais interno é recupera salário mais alto do departamento 5 SELECT MAXSalario FROM Funcionario WHERE Dnr 5 E o bloco mais externo é recupera o primeiro e último nome dos funcionários que recebem mais que o maior salário do departamento 5 SELECT Unome Pnome FROM Funcionario WHERE Salario c Representação das consultas em expressão da álgebra relacional estendida 𝑓𝑀𝐴𝑋𝑆𝑎𝑙𝑎𝑟𝑖𝑜𝜎𝐷𝑛𝑟5 𝐹𝑢𝑛𝑐𝑖𝑜𝑛𝑎𝑟𝑖𝑜 𝜋𝑈𝑛𝑜𝑚𝑒𝑃𝑛𝑜𝑚𝑒𝜎𝑆𝑎𝑙𝑎𝑟𝑖𝑜𝑐 𝐹𝑢𝑛𝑐𝑖𝑜𝑛𝑎𝑟𝑖𝑜 O otimizador de consulta então escolheria um plano de execução para cada bloco de consulta Neste caso o bloco interno precisa ser avaliado somente uma vez para produzir o salário máximo dos funcionários do departamento 5 isso se dá o nome de consulta aninhada sem correlação com a consulta externa Heurística na otimização da consulta As regras heurísticas modificam a representação interna de uma consulta para melhorar seu desempenho A varredura e o analisador de uma consulta SQL gera primeiro uma estrutura de dados que corresponde a uma representação inicial de consulta árvore de consulta para então ser otimizada com regras heurísticas Isso leva a uma representação de consulta otimizada Uma das principais regras heurísticas é aplicar operações de SELEÇÃO e PROJEÇÃO antes de aplicar a JUNÇÃO ou outras operações binárias pois essas operações reduzem o tamanho do arquivo antes de uma junção ou outra operação binária Uma árvore de consulta é uma estrutura de dados de árvore que corresponde uma expressão da álgebra relacional Ela representa as relações tabelas de entrada da consulta como nós folha da árvore e representa as operações da álgebra relacional como nós internos Uma execução da árvore de consulta consiste na execução de uma operação de nó interno sempre que seus operandos estão disponíveis e depois na substituição desse nó interno pela relação que resulta da execução da operação A ordem de execução das operações começa nos nós folha que representa as relações do banco de dados de entrada para a consulta e termina no nó raiz que representa a operação final da consulta A execução termina quando a operação do nó raiz é executada e produz a relação de resultado para a consulta Muitas expressões diferentes da álgebra relacional podem ser equivalentes assim como podemos ter árvores de consultas diferentes para representar a mesma consulta O analisador de consulta geralmente irá gerar uma árvore de consulta inicial padrão para corresponder a uma consulta SQL sem realizar qualquer otimização Por exemplo para uma consulta SELEÇÃO PROJEÇÃO e JUNÇÃO o produto cartesiano das relações especificadas na claúsula FROM é aplicado primeiro depois as condições de seleção e junção da cláusula WHERE são aplicadas seguidas pela projeção nos atributos da cláusula SELEÇÃO Essa árvore de consulta inicial também é chama de árvore de consulta canônica que é uma representação de uma expressão da álgebra relacional que é muito ineficaz se executada diretamente por causa das operações do produto cartesiano X A árvore representada pela Figura anterior está em uma forma padrão simples que pode ser facilmente criada com base na consulta SQL No entanto ela nunca será executada O otimizador de consulta heurística transformará essa árvore de consulta inicial em uma árvore de consulta final equivalente que é eficiente para se executar O otimizador de consultas deve incluir regras para equivalência entre expressões da álgebra relacional que podem ser aplicadas para transformar a árvore inicial na árvore de consulta otimizada final Exemplo de transformação de uma consulta Considere a seguinte consulta no banco de dados ache os sobrenomes dos funcionários nascidos após 1957 que trabalham em um projeto chamado Aquarius Consulta SQL SELECT Unome FROM Funcionario TrabalhaEm Projeto WHERE Projnome Aquarius AND Projnumero Pnr AND FCpf Cpf AND DataNasc 31121957 A árvore inicial para a consulta seria a seguinte A execução da árvore inicial cria um arquivo muito grande contendo o PRODUTO CARTESIANO dos arquivos Funcionario TrabalhaEm e Projeto inteiros Por isso essa árvore nunca é executada mas sim transformada em uma árvore equivalente eficiente para se executar Essa consulta em particular somente precisa de um registro da relação Projeto para o projeto Aquarius e apenas os registros de Funcionario pra aqueles cuja data de nascimento se dá após 31121957 A figura a seguir mostra uma árvore melhorada que primeiro aplica as operações de SELEÇÃO para reduzir o número de tuplas registros que aparecem no PRODUTO CARTESIANO Outra melhoria é alcançada trocando as posições das relações Funcionario e Projeto na árvore Isso usa a informação de que Projnumero é um atributo de chave da relação Projeto e portanto a operação SELEÇÃO na relação PROJETO recuperará um único registro É possível melhorar ainda mais a árvore de consulta ao substituir qualquer operação de PRODUTO CARTESIANO que seja acompanhada por uma condição de junção por uma operação de JUNÇÃO Outra melhoria é manter apenas os atributos necessários pelas operações subsequentes nas relações intermediárias incluindo operações de PROJEÇÃO o mais cedo possível na árvore de consulta isso reduz os atributos colunas das relações intermediárias enquanto as operações SELEÇÃO reduzem o número de tuplas registros Assim a árvore foi transformada passo a passo em uma árvore de consulta equivalente que é mais eficiente de se executar Porém temos que garantir que as etapas de transformação sempre levem a uma árvore de consulta equivalente Para isso o otimizador de consulta precisa saber quais regras de transformação preservam essa equivalência Heurísticas Básicas Aplicar as operações que reduzem o tamanho dos resultados intermediários operações de seleção reduzem o número de tuplas operações de projeção reduzem o número de atributos Aplicar as operações de seleção e de junção mais restritivas reordenar os nós folha da árvore de consulta evitar a operação de produto cartesiano ajustar o restante da árvore de forma apropriada Exercícios Complementares 1 As árvores apresentadas a seguir são equivalentes Qual a mais eficiente SELECT CRM nome numero andar FROM Médicos Ambulatórios WHERE especialidade ortopedia AND andar 2 AND numero num 2 Baseandose nas relações especificadas a seguir apresente a correta sintaxe das expressões algébricas descritas nos itens a b e c além das relações resultantes da aplicação destas expressões sobre estas relações a Seleção de funcionários que ganham mais de mil reais b Qual o nome do supervisor e nome de seus respectivos funcionários supervisionados c Lista do nome de funcionário e nome do projeto dos funcionários no departamento de Informática 3 A partir da expressão de álgebra relacional do item C do exercício anterior faça a árvore de consulta inicial canônica e usando as regras de transformação derive a árvore de consulta para que corresponda à sequência de operações da álgebra relacional mais eficiente para a sua execução 4 Considere a consulta abaixo SELECT ENOME FROM EMPREGADO E ALOCACAO A PROJETO P WHERE NOMEPROJ BD1 AND PNUM APNUM AND EMAT AMAT AND DATANASC 10101974 Faça os seguintes passos Passo 1 Montar a árvore de consulta Passo 2 Descer as seleções Passo 3 Aplicar primeiro as seleções mais restritivas Passo 4 Trocar produto cartesiano por junção Passo 5 Descer as projeções Estratégias Práticas de Otimização de Consultas Reduzir o número de campos na PROJEÇÃO Utilização de Junções JOINS evitando a operação de produto cartesiano Criação de índices o Campos buscados frequentemente o Campos que recebem comparação MIN MAX COUNT GROUP BY Materiais Base Estudar httpswwwmacorattinet1306sqlarcbhtm httpwikiicmcuspbrimagesaa6SCC578920131procconsultaspdf httphomepagesdccufmgbrlaendermaterialibdparte7pdf Cap19 Livro Sistemas de Banco de Dados Elmasri Navathe