Artigo SQL Magazine 16 - Introdução ao Funcionamento do Otimizador de um SGBDR

Este artigo explica, de forma geral, o funcionamento de um otimizador de um SGBDR.

O otimizador de um Sistema de Gerenciamento de Banco de Dados Relacionais (SGBDR) é responsável por analisar uma consulta SQL e escolher qual a forma mais eficiente de executá-la. A escolha leva em considerações diversas informações internas do banco de dados. Este artigo explica, de forma geral, o funcionamento de um otimizador.

A Figura 1 representa os passos envolvidos na busca de informações. No passo 1, o usuário faz uma requisição de informações através do comando SELECT. Recebido o comando, o SGBDR irá procurar no disco as informações solicitadas (passo 2). Encontrando-as ou não, o SGBDR sempre retorna uma resposta para o usuário (passo 3). Detalharemos agora o passo 2 deste processo, focando especialmente o otimizador e os mecanismos utilizados por ele. Exemplos práticos serão demonstrados com os SGBDR InterBase e PostgreSQL.

Figura 1. Etapas do processo de consulta-resposta em um SGBDR

Otimização em SGBDRs e Sistemas não Relacionais

Em bancos de dados não relacionais (Cobol, Clipper, Dbase, etc), fica a cargo do programador o processo de otimização de acesso, ou seja, ele é que determina como as informações devem ser acessadas. Nos SGBDRs, o otimizador leva em conta informações atuais do banco no momento da consulta para determinar o melhor plano de acesso aos dados.

Saiba mais: Cursos de SQL e Banco de Dados

A otimização em um SGBDR pode ser feita porque em SQL não se expressa “como” a consulta deve ser executada, mas sim “o que” se pretende recuperar, permitindo que o otimizador escolha o “como” da maneira mais adequada em determinado momento.

O Catálogo do Sistema em um SGBDR

O catálogo do sistema (metadado) mantém todas as informações referentes aos dados armazenados no SGBD, como informações sobre tabelas, índices, visões, procedimentos armazenados, etc. incluindo tanto descrições estáticas como dinâmicas. Alguns dos dados estáticos armazenados no catálogo do sistema são:

Sobre Tabelas:

Sobre Visões:

Já os dados dinâmicos armazenados no catálogo incluem:

Sobre Tabelas:

Sobre Índices:

A Figura 2 apresenta o software IBConsole do SGBD InterBase. Nela podemos visualizar as tabelas do catálogo do InterBase juntamente com as demais tabelas criadas pelo usuário. Note que os nomes das tabelas do catálogo nesse SGBDR são iniciadas por RDB$.

Em destaque na Figura 3 temos a tabela RDB$RELATIONS, responsável por guardar os nomes de todas as tabelas do SGBD (RDB$RELATION_NAME), inclusive as do catálogo do sistema, entre outras informações.

Para quem usa PostgreSQL, o catálogo do sistema pode ser visto digitando no prompt do programa psql o comando \dS. Um exemplo do resultado deste comando pode ser observado na Figura 4. Nas informações obtidas pelo comando, destaca-se, para o contexto deste artigo, a tabela pg_statistic, onde são armazenadas as estatísticas utilizadas pelo otimizador.

Figura 2. Tabelas do catálogo do sistema do InterBase
Figura 3. Campos e valores da tabela RDB$RELATIONS
Figura 4. Tabelas, visões e outros elementos que formam o catálogo do sistema do PostgreSQL

Estruturas de Índices

Um dos pontos mais importantes do processo de otimização de consultas é o uso de índices. Um índice é uma estrutura de dados desenvolvida para agilizar a busca de informações. Quando criamos um índice, o SGBD faz uma cópia do conteúdo dos campos indexados, organizando-os segundo uma estrutura de dados pré-definida, sendo que as estruturas mais utilizadas são as Árvores B+ e as funções Hash.

Árvores B+

A estrutura de árvore B+ é a mais utilizada dentre as estruturas de índices, pois mantém sua eficiência mesmo sob pesada carga de inserções e remoções de dados. O nome árvore vem da semelhança da estrutura do índice com árvore de cabeça para baixo, onde a raiz está localizada no topo da estrutura e é usada como ponto inicial nos processos de buscas.

Essa estrutura é composta por páginas, ou nós, divididas em dois grupos: páginas internas e folhas. As páginas internas são usadas para guiar o processo de busca até as páginas folhas, e estas últimas contêm o valor da chave de busca e a localização da página de dados no disco referente ao registro procurado.

Em cada página da árvore B+ de ordem N, o número de chaves é de no mínimo [INT (N/2)] –1 e no máximo N-1 chaves. De acordo com estas propriedades, uma árvore B+ de ordem N=8 tem no máximo 7 e no mínimo 3 chaves por página.

É importante frisar que na avaliação de custo de uma consulta que use uma árvore B+, considera-se o custo de recuperar uma página do disco e trazê-la para a memória RAM.

A Figura 5 mostra uma árvore B+ com 3 níveis e de ordem N=4. Todas as páginas folhas aparecem no nível 3. Em cada página, as chaves de busca ocorrem em ordem crescente, permitindo utilizar o algoritmo de busca binária [Nota 1] na procura da chave dos registros lidos para a memória.

Figura 5. Exemplo de uma árvore B+ usada como índice em um SGBD
Nota 1: O algoritmo de busca binária é um método de busca de informações em vetores ordenados que possui excelente desempenho. A lógica de seu funcionamento é a seguinte:
  1. Encontra-se a posição central do vetor (meio do vetor).
  2. Compara-se o valor localizado na posição central do vetor com o valor procurado.
  3. Se o valor procurado for menor que o valor da posição central, a metade do vetor que possui valores maiores do que o procurado é descartada, restando apenas a outra metade. O processo ocorre de forma inversa se o valor procurado for maior que o valor da posição central.
  4. Estes passos são executados sucessivamente até que se encontre o valor procurado ou que não haja mais possibilidade de divisão do vetor, significando que o valor procurado não se encontra no vetor.

Função Hash

Além da árvore B+, usa-se também a técnica de hashing (função de dispersão ou espalhamento) como estrutura de indexação. Esta técnica fornece acesso direto a um registro armazenado através do uso de uma função que aplicada sobre o atributo indexado, fornece um endereço utilizado como base de armazenamento e recuperação de registros em uma tabela conhecida como tabela hashing. O funcionamento da técnica segue alguns passos básicos:

Para um funcionamento ideal da técnica de hashing, é necessário escolher uma função de espalhamento que evite ao máximo o mapeamento das chaves de busca para um mesmo endereço da tabela hashing, o que caracteriza uma colisão de endereço. Toda colisão deve ser tratada e o tratamento gera um gasto extra de recurso do SGBD.

Na Figura 6 temos a seguinte situação: a tabela da esquerda representa uma tabela hashing com 13 posições ou buckets, e na tabela da direita temos uma tabela de cliente contendo 5 registros. Considere que cada registro de cliente ocupe uma página em disco (o que normalmente não ocorre). Note que existem mais buckets na tabela hashing do que registros na tabela cliente. Isto é necessário para se evitar colisões das chaves, pois, quanto maior for o número de buckets menos provável é a ocorrência de colisões.

Cada endereço dos buckets na tabela hashing é calculado pela função hash: endereço_hash = Resto da divisão(chave/13). Suponha que uma tabela contenha os seguintes valores nas chaves: 100, 200, 300, 400, 500. Aplicando a função hash são obtidos respectivamente os endereços 9, 5, 1, 10 e 6.

Tabela hashing Tabela de cliente

End.Hash Chave End.Página End.Página Chave Nome Cidade
1 300 &1015 &1011 200 Cliente C Cidade C
2 &1012 400 Cliente E Cidade E
3 &1013 100 Cliente A Cidade A
4 &1014 500 Cliente B Cidade B
5 200 &1011 &1015 300 Cliente D Cidade D
6 500 &1014
7
8
9 100 &1013
10 400 &1012
11
12
13
Tabela 1. Exemplo de uma tabela hashing usada como índice em um SGBD
Nota: Tenha em mente que para cada índice declarado sobre uma tabela, é criado uma estrutura de árvore B+ ou uma tabela de espalhamento, que devem ser atualizados toda vez que ocorrem inserções e remoções de registros nesta tabela, o que pode causar perda de eficiência em alguns casos.

Seletividade de Atributos

Um outro conceito importante que afeta a decisão sobre usar ou não um índice é a seletividade do atributo. A seletividade estima, em média, a porcentagem dos registros que deverão aparecer na resposta dado um determinado atributo. Ela pode ser calculada pela função:

Seletividade (atributo)= 1 - (registros-na-resposta-filtrada-pelo-atributo / total-de-registros)

Quanto mais próximo de 1, melhor é a seletividade de um atributo. Vejamos um exemplo: suponha uma tabela de clientes com 500 clientes. Vamos realizar uma consulta pelo CPF. Sabemos que o CPF não se repete e que existe um índice sobre este campo. Então teremos:

Seletividade(CPF) = 1 – (1/500) = 0,998

Isto indica que CPF é um excelente atributo para realização de consultas através do uso do índice, pois cada valor de CPF descarta quase todos os registros da tabela. Agora vamos realizar uma consulta pelo atributo cidade, sabendo que existem clientes de 110 cidades diferentes e que também existe um índice sobre esse campo.

Seletividade(Cidade) = 1 – (110/500) = 0.78;

Esta pesquisa retornará em média mais de 20% dos registros. Isto pode indicar para o otimizador não utilizar o índice sobre o campo cidade e sim fazer uma varredura total sobre a tabela.

Vamos a um exemplo prático utilizando o PostgreSQL. Para saber como a consulta será realizada, usaremos o comando explain, que indica o plano de acesso adotado pelo SGBD na execução da consulta. Existem as seguintes formas possíveis de acesso aos dados:

Considere a tabela cliente composta pelos campos:

Cliente = {nome_cliente, rua_cli, cidade, obs1, obs2, obs3}

A tabela possui um total de 100.000 registros armazenados. Foi criado um índice de árvore B+ sobre o campo cidade, onde existem 95000 registros com valores iguais a “Sao Paulo” e 5000 registros com valores iguais a “Fernandopolis”. Além disto, também existe um índice B+ sobre o campo chave nome_cliente.

Agora considere a seguinte consulta:

select nome_cliente from cliente where cidade = “Sao Paulo”;

Uma vez que 95% dos registros possuem o campo cidade igual a “Sao Paulo”, o uso do índice torna-se dispendioso, indicando para o otimizador que é mais econômico fazer uma varredura em toda a tabela cliente (isto pode ser observado pelo detalhamento Seq Scan on cliente da Figura 7) do que utilizar o índice sobre o campo indexado.

Figura 7. Exemplo de uma consulta em que não foi utilizado o índice sobre o atributo indexado

Agora vamos considerar a consulta:

select nome_cliente from cliente where cidade = “Fernandopolis”;

Uma vez que somente 5% dos registros possuem o valor “Fernandopolis" para o atributo cidade, é interessante para o otimizador fazer o uso do índice para resolver esta consulta. Observe na Figura 8 que otimizador faz o uso do índice para encontrar os valores dos registros iguais a “Fernandopolis” (explicado pelo detalhamento Index Scan using idx_cidade on cliente, onde idx_cidade é nome do índice).

Figura 8. Exemplo de uma consulta em que foi utilizado o índice sobre o atributo indexado

As fases de execução de uma consulta

Até aqui vimos alguns dos conceitos utilizados pelo otimizador de um SGBDR. Agora vamos analisar as fases necessárias para a execução de uma consulta. Uma consulta expressa em SQL geralmente pode ser executada de diferentes maneiras. Em um SGBDR, é de responsabilidade do otimizador transformar a consulta definida pelo usuário (select) em uma representação equivalente que possa ser computada mais eficientemente.

Uma consulta passa por quatro etapas, que vai desde a análise sintática dos comandos até sua execução. Mostradas na Figura 9, as quatro etapas são:

A seguir vamos analisar em detalhes cada uma destas quatro etapas. Para isso, consideraremos que exista uma base de dados armazenando a tabela cliente, definida abaixo.

cliente={Codigo, Nome, Telefone, Rua, Numero, Cidade}
Figura 9. Etapas necessárias para a execução de uma consulta

Fase 1 - Análise sintática e léxica da consulta

Nesta fase é realizada a análise léxica e sintática da consulta (parsing). É aqui que o otimizador valida sintaticamente uma expressão SQL. Por exemplo, considere a consulta

SELECT c.nome FROM cliente c;

O analisador sabe, por exemplo, que após a palavra from obrigatoriamente deve vir um nome de uma tabela (ou visão) existente no banco de dados. Se alguma das tabelas cliente ou pedido não existir, ele retornará uma mensagem informando o erro. As consultas validadas nesta fase são encaminhadas para a fase 2.

Fase 2 - Conversão da consulta para a forma relacional

O modelo relacional permite que consultas sejam expressas através de operadores sobre as relações. As tabelas são consideradas conjuntos de registros e, portanto, podem ser operadas pelos operadores de conjuntos como união (?), intersecção (?) e produto cartesiano (?). Além disso, podem ser filtradas por operadores de seleção (s), ou podem ser projetadas (p) em relações com menos atributos.

Para ilustrar este artigo, vamos usar apenas os operadores que envolvem uma única tabela de cada vez. Consideramos inicialmente o operador de seleção, representado por s?(condiçãoC)R (que pode ser lido como “Encontre todos os dados da relação R que atendam a condição C”) . Ele seleciona apenas os registros da relação R que atendem à condição C. Já um operador de projeção p?R (que pode ser lido como “Mostre os valores do atributos AI da relação R) retorna todos os registros da relação R, mas de cada registro recupera apenas os atributos indicados na lista AI de atributos.

Por tratar os algoritmos de manipulação de relações como operações bem definidas, o gerenciador pode usar as propriedades matemáticas desses operadores para escolher as melhores opções de consulta. Então, neste estágio, a consulta em SQL é convertida internamente para uma forma algébrica equivalente. Por exemplo, a consulta feita em SQL:

SELECT nome, telefone FROM cliente WHERE nome like(‘Pedro%’) AND cidade=‘São Carlos’;

pode ser expressa algebricamente, por exemplo, como:

p {nome, telefone} (s nome like(‘Pedro%’) (s cidade=’São Carlos’(cliente)))

Nessa representação interna, a tabela cliente é lida e filtrada pelo operador de seleção s cidade=’São Carlos’. O resultado é lido novamente e filtrado pelo operador s nome=’Pedro’. Finalmente, o resultado é projetado (p) em uma relação que tem apenas os atributos nome e telefone. Para facilitar a compreensão deste plano de consulta por parte do leitor, esta expressão será convertida em uma representação gráfica denominada árvore de consulta (Figura 10).

Figura 10. Árvore de Consulta referente à alternativa 1

Uma alternativa é expressar a consulta original como:

p {nome, telefone} (s (nome like(‘Pedro%’) ^cidade=’São Carlos’) (cliente))

Nesta representação interna, a tabela cliente é lida e filtrada pelo operador de seleção (s (nome=’Pedro’ ^ cidade=’São Carlos’), minimizando a quantidade de leituras e escritas intermediárias necessárias. A árvore de consulta referente a esta alternativa está representada na Figura 11.

Figura 11. Árvore de Consulta referente à alternativa 2

Fase 3 - Gerar planos de consultas e analisar o mais econômico

Este passo envolve a criação de um conjunto de planos de alternativos expressos em álgebra relacional, considerando aspectos como a existência de índices, distribuição de valores de dados (seletividade), agrupamento físico de dados armazenados, etc.

No exemplo anterior, além das duas alternativas já mostradas, outras menos óbvias são geradas tais como:

p {nome, telefone} (s (nome like(‘Pedro%’) ^ cidade=’São Carlos’) (p {nome, telefone, cidade} cliente))

Note que estas variações trazem uma otimização considerável, pois à medida que a tabela cliente é lida, apenas os atributos que serão utilizados posteriormente são passados para os próximos operadores, reduzindo a ocupação dos dados intermediários na memória. Assim, ao analisar o custo de cada maneira de executar a consulta, o otimizador escolherá esta última. A Figura 12 representa a árvore de consulta da alternativa 3.

Figura 12. Árvore de Consulta referente à alternativa 3

Fase 4 - Executar a consulta.

É neste estágio que a consulta escolhida será executada e o resultado, entregue para o usuário.

Exemplo Prático

Agora que já temos uma visão geral do funcionamento do otimizador de consulta de um SGBDR, vamos a alguns exemplos práticos. Os exemplos demonstram a escolha ou não do uso de índices na execução de consultas. A tabela usada é a mesma apresentada no exemplo de seletividade.

Exemplo 1:

Considere a seguinte consulta:

select * from cliente where nome_cliente = "nome1898";

As Figuras 13 e 14 apresentam o plano de acesso adotado pelo InterBase 6.5 e PostgreSQL 7.4.2, respectivamente. É importante saber que ambos os SGBDs estão com as estatísticas atualizadas.

Figura 13. Resultado de uma consulta onde o otimizador do InterBase utilizou o índice existente sobre o campo de busca
Figura 14. Resultado de uma consulta onde o otimizador do PostgreSQL utilizou o índice existente sobre o campo de busca

Comparando: Nota-se pelo resultado das Figuras 13 e 14 que foram utilizados os índices existentes sobre o campo usado na comparação. Nesta situação ambos otimizadores tiveram desempenho semelhante.

Agora um segundo exemplo onde procuramos os clientes que residem na cidade de São Paulo.

Exemplo 2:

Considere a seguinte consulta:

select * from cliente where cidade = "Sao Paulo";

É importante salientar que o campo cidade possui uma seletividade muito baixa, pois 95% dos registros possuem valor igual a ‘São Paulo’. As Figuras 15 e 16 apresentam o plano de acesso adotado pelo InterBase e PostgreSQL, respectivamente.

Figura 15. Plano de acesso do otimizador do Interbase utilizando o índice existente no campo de busca
Figura 16. Plano de acesso do otimizador do PostgreSQL

Comparando: Nesta consulta, o otimizador do PostgreSQL (observado na Figura 16), após fazer a análise, constatou que o custo de fazer uma varredura em toda a tabela de clientes é mais econômico que utilizar o índice existente sobre o campo cidade, tendo em vista que existe muita repetição do valor de cidade igual a ‘São Paulo’. Já o otimizador do InterBase (observado na Figura 15) escolheu o uso dos índices mesmo tendo a informação que a seletividade do índice cidade é baixa, devido à repetição do valor ‘São Paulo’. De acordo com estes dados, nota-se, para esta situação, que o otimizador do PostgreSQL obteve melhor desempenho que o otimizador do InterBase.

Conclusão

Este artigo apresentou os principais elementos envolvidos na execução de uma consulta realizada por um SGBDR. As sequências adotadas para representação no texto não são obrigatoriamente as mesmas para todos os SGBDs. Cada fabricante desenvolve seu otimizador da maneira mais conveniente, e este é um dos maiores diferenciais entre os diversos gerenciadores existentes: um gerenciador será tão mais eficiente quanto melhores e mais precisas forem as estratégias de busca descobertas e selecionadas por seu otimizador.

É importante salientar que em uma consulta, o principal fator de desempenho é o uso ou não de índices. Como foi mostrado, os índices melhoram sensivelmente a velocidade em que os dados são encontrados. Mas este benefício possui o custo da manutenção destes índices, o que torna inviável sua criação em excesso. A dica sugerida é que o DBA analise os índices existentes e verifique se estão sendo utilizados pelas consultas. Para os índices que não estiverem em uso, atualize suas estatísticas. Se ainda continuarem em desuso, converse com os programadores sobre a possibilidade da destruição destes índices. Da mesma forma, verifique a possibilidade de criação de índices para os atributos de busca nas sentenças mais usadas.

Bibliografia:
  1. Ramakrisnan, R.; Gehrke, J., Database Management Systems, McGraw-Hill, 2ª ed., 2000.
  2. Date, C.J., Introdução a Sistemas de Banco de Dados, Editora Campus, 7ª ed., 2000.
  3. Ziviane, N., Projeto de Algoritmos com implementação em Pascal e C, Editora Thomson Pioneira, 1993.
Saiu na DevMedia!
  • React com Redux:
    Redux é uma biblioteca JavaScript criada pelo Facebook para resolver um problema inerente de aplicações front-end conforme elas crescem em tamanho e complexidade.

Saiba mais sobre SQL e Banco de dados ;)

  • Curso de SQL:
    Neste curso conheceremos os primeiros comandos da linguagem SQL (Structured Query Language), utilizada na estruturação e consulta de bancos de dados relacionais como MySQL e SQL Server.
  • Curso de NoSQL:
    Neste curso apresentaremos os conceitos introdutórios do NoSQL, suas características e funcionamento. Veremos também um exemplo prático utilizando o NoSQL.
  • Guias de Banco de Dados:
    Aqui você encontra o Guia de estudo ideal para aprimorar seus conhecimentos nos principais Banco de Dados do mercado. Escolha o seu e bons estudos!

Artigos relacionados