Processamento e otimização de consultas

Leyza Baldo Dorini04/Nov/2009

UTFPR - Universidade Tecnológica Federal do Paraná

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 consultasTraduçã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 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: otimização algébrica

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.andarFROM Medicos m, Ambulatorio aWHERE 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, FNAMEFROM EMPLOYEEWHERE 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) SALARYFROM EMPLOYEEWHERE DNO = 5)

– Bloco externoSELECT LNAME, FNAMEFROM EMPLOYEEWHERE SALARY > c

PC: traduçãoSELECT LNAME, FNAMEFROM EMPLOYEEWHERE SALARY > ( SELECT MAX (SALARY)

FROM EMPLOYEEWHERE DNO = 5);

SELECT MAX (SALARY)FROM EMPLOYEEWHERE DNO = 5

SELECT LNAME, FNAMEFROM EMPLOYEEWHERE SALARY > C

π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

Transformação:– Entrada: árvore da consulta inicial;– Saída: árvore da consulta otimizada (pode

manter a mesma árvore).

Transformações de ExpressõesRelacionais• Uma consulta pode ser expressa de diversasmaneiras diferentes, com diferentes custos deavaliaçã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 suasinstâncias, encontre os nomes de todos osclientes que possuem uma conta em qualqueragê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.

d

• 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!!!