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

Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Para efetuar o download você precisa estar logado. Clique aqui para efetuar o login
Confirmar voto
0
 (1)  (0)

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

capaSQL16.JPG

Clique aqui para ler todos os artigos desta edição

Introdução ao Funcionamento do Otimizador de um SGBDR

 

por Evandro de Araújo Jardini e Caetano Traina Jr.

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ção 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.

 

image002.gif 

 

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.

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:

o        Seu nome e a estrutura física interna no arquivo da base de dados.

o        Nome dos atributos, o tipo de dado e tamanho de cada um.

o        Os nomes dos índices sobre cada tabela.

o        As restrições (chave primária, chave estrangeira, checks) sobre a tabela.

o        Índices

o        O nome do índice e a estrutura de organização (árvore B+, Hash, etc).

o        Os atributos de busca usados.

·         Sobre Visões

o        A definição e o nome da visão.

 

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

 

Sobre Tabelas:

·         Tamanho: o número de páginas em disco que cada relação ocupa.

·         A taxa de ocupação dos registros nas páginas em disco.

Sobre Índices:

·         Seletividade: o número de valores chaves distintos para cada índice.

·         Tamanho: o número de páginas de cada índice.

·         Altura: o número de níveis não-folha para cada índice de árvore B+, isto se existirem tabelas utilizando este tipo de índice.

·         Faixa: os valores mínimo e o máximo da chave para cada índice.

 

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.

 

image004.jpg 

 

Figura 2. Tabelas do catálogo do sistema do InterBase.

 

image006.jpg

 

Figura 3. Campos e valores da tabela RDB$RELATIONS.

 

image008.jpg 

 

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 (ver nota 1) na procura da chave dos registros lidos para a memória.

 

image010.jpg 

 

"

A exibição deste artigo foi interrompida :(
Este post está disponível para assinantes MVP

 
Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Receba nossas novidades
Ficou com alguma dúvida?