Estruturas De Índices No PostgreSQL

Organização de Arquivos e Índices no PostgreSQL

Introdução

Este trabalho tem como objetivo apresentar características do SGBD PostgreSQL quanto a sua organização de arquivos e índices. A versão utilizada para estudos foi a 9.2.4.

Organização Física do Banco de Dados

O PostgreSQL organize seus principais objetos em forma de arquivo, hierarquicamente. No topo da hierarquia, temos clusters; pode-se entendê-los como uma coleção de banco de dados. Cada cluster está organizado numa estrutura de diretórios e subdiretórios própria.

Existem três tabelas de sistema que são compartilhadas por todos os bancos de dados em um mesmo cluster:

1. pg_group – listagem de grupos de usuários;

2. pg_database – listagem de bancos de dados em um cluster;

3. pg_shadow – listagem de usuários válidos.

Cada cluster contém um ou mais bancos de dados. Cada banco de dados tem um nome que o identifica e é único por cluster. Bancos de dados, por sua vez, são uma coleção de Tabelas (possivelmente agrupada por esquemas), funções, visões, índices, e outros.

Cada banco de dados precisa ter um nome, ao contrário do cluster. Este nome pode não ser único, o que leva á necessidade de uso de schemas. Todos os objetos de um banco são únicos por schema.

Paginação

Dados no PostgreSQL encontram-se no diretório “data/base” dentro do caminho da instalação. Existem vários diretórios, um para cada banco de dados. Dentro de cada diretório, existem vários arquivos, todos relacionados a tabelas. Cada tabela do banco de dados tem seu próprio arquivo.

Cada arquivo/tabela pode conter até 1 GB de dados. Após este limite, um novo arquivo é criado. Cada arquivo é tratado em blocos de 8KB - uma página.

Buffer Management

Cada página possui um cabeçalho seguido de uma lista de itens de tamanho fixo que, na verdade, são ponteiros para tuplas na mesma página. As tuplas podem estar em qualquer lugar da página e não possuem tamanho fixo. Logo, uma página tem tuplas de vários tamanhos e uma estrutura de índice de tamanho fixo. Por sua vez, cada tupla possui um cabeçalho e um conjunto de valores – atributos das tuplas.

Quando determinada query é executada, o sistema lê as tabelas através do índice – ou não - e carrega as páginas correspondentes dentro de um buffer compartilhado. Neste buffer, que também fica em uma área de memória compartilhada, contém a maioria das páginas utilizadas. Este buffer é indexado pelo Buffer Descriptors que possui um Pin Count ( flag que sinaliza quando substituir ou não determinada página) e LWlock (flag de modificação da página).

A substituição ou não de determinada página é feita através de estatísticas de utilização. Toda vez que determinada página é acessada, um contador de uso é atualizado. De tempos em tempos, este contador é decrementado. Quando uma página tem seu contador zerado, esta pode ser substituída, liberando espaço no buffer.

PostgreSQL não utiliza a estratégia FIFO, preferindo usar estratégias estatísticas como LRU (least recently used) e HEAP, que de alguma forma funciona melhor, segundo o manual.

Mapa de Espaços Livres

PostgreSQL controla os espaços livre nas páginas – e em índices – através de uma estrutura chamada FSM – Free Space Map, ou mapa de espaços livres. FSM é organizado como uma árvore binária. Nas folhas estão armazenados os espaços livres de cada página/índice. Nos nós pais, estão armazenados o máximo de espaço livre na comparação entre os dois nós filhos, conforme a figura a seguir:

O percurso a ser percorrido nesta árvore é iniciado em uma das folhas. Por exemplo, se fosse necessário achar 3 espaços livres para armazenamento, percorreríamos a estrutura até achar o local mais adequado para armazenamento.

Índices

A utilização de índices em Sistemas Gerenciadores de Banco de Dados é um dos principais mecanismos que permitem a recuperação eficiente de dados. Índices são estruturas de dados que organizam o acesso a determinado conjunto de dados. Embora crucial na maioria dos casos, precisam ser utilizados de forma correta, pois, do contrário, podem piorar o desempenho. Isto acontece porque criar e manter índices gera sobrecarga no sistema como um todo. Os tipos de índices disponibilizados pelo PostgreSQL são: árvores B+ , HASH, GiST e GIN.

Árvore B+

Este tipo de índice é o padrão para o PostgreSQL. Apresenta uma ordenação aos dados persistidos, implicando, é claro, que os dados sejam ordenáveis de certa forma. Nesta estrutura, os dados encontram-se, de fato, apenas nas folhas; nos nós intermediários encontramos chaves de acesso. As folhas, por sua vez, estão todas conectadas, como numa lista encadeada. A figura abaixo apresenta um exemplo de árvore B+.

Árvores B+ aceitam queries que envolvem comparações em uma coluna indexada utilizando os seguintes operadores: <, <=, =, >=, >, BETWEEN, IN, IS NULL e IS NOT NULL.

Ainda mais, pode-se utilizar este tipo de índice para operadores que buscam padrões em textos, como LIKE - apenas se o padrão for uma constante e puder ser encontrado no início da string.

Estas árvores possuem entre n+1/2 e n subnós para cada nó não-folha nem raiz. Desta forma, existem apenas alguns nós intermediários e, portanto, um rápido acesso aos dados é possível (folhas).

Entretanto, Existem alguns problemas a serem resolvidos pelo SGBD. Existe um problema de concorrência na utilização deste tipo de índice. Sendo assim, para que determinado usuário possa utilizá-lo durante uma consulta, enquanto outro faz atualização em tabelas, o sistema prevê uma imagem fixa da estrutura, chamada de árvores B+ de alta concorrência. Esta solução prevê uma boa solução para o problema, introduzindo um pequeno overhead no algoritmo e na estrutura.

A utilização de árvores B+ é simples e não necessita de explicitação, uma vez que os índices no PostgreSQL são, por padrão, árvores B+, conforme o exemplo abaixo:

CREATE INDEX nome_do_indice ON nome_da_tabela (nome_da_coluna);

Índices Hash

Índices do tipo Hash são assim chamados porque utilizam a técnica de hashing – utilização de funções matemáticas para encontrar a posição de determinado dado. Tais funções usam a chave como parâmetro de cálculo. Para valores pontuais, o acesso pode ser realmente bastante rápido. Entretanto, este tipo de índice apresenta um problema inerente à técnica de hashing, chamada de colisão. Significa dizer que chaves diferentes podem apresenta um mesmo código hash. Índices Hash também não permitem a busca por faixas de valores, como nas árvores B+, devido à própria natureza do índice. Também não permitem a indexação multicoluna, além de consumir bastante recursos do sistema. O exemplo abaixo apresenta comando de criação deste tipo de índice:

CREATE INDEX nome_do_indice ON nome_da_tabela USING hash (nome_da_coluna);

Índices GiST e GIN

Estes dois tipos de índices significam, do inglês, Generalized Search Tree (GiST) e Generalized Inverted Index (GIN). Na verdade, não são mais um tipo de índice, mais uma infraestrutura de estratégias de índices, combinando árvores B+ e outros tipos de árvores, como árvores R, árvores hB e árvores RD.

GIN é um índice invertido, que indexa mais de uma chave ao mesmo tempo, comumente usado para arrays. Bastante utilizado para busca textual, onde são indexadas palavras que existem em determinado campo de uma tupla.

Já o índice GiST é chamado de lossy, o que significa a existência de falsos positivos na busca de dados. Logo, se faz necessário checar a tupla verdadeira para eliminar dúvidas. Isto ocorre porque o GiST também possui algum mecanismo de hashing, o que pode ocasionar colisão, assim como os índices hash. Isto causa perda de performance no índice. Os exemplos abaixo apresentam comandos de criação destes tipos de índices:

CREATE INDEX nome_do_indice ON nome_da_tabela USING gist (nome_da_coluna);

CREATE INDEX nome_do_indice ON nome_da_tabela USING gin (nome_da_coluna);

Utilizando índices para Organização de Arquivos.

PostgreSQL armazena os dados fisicamente em um heap, ou seja, não leva em consideração ordem, sem nenhum processo de clusterização a priori. Entretanto, é possível explicitar uma organização em um arquivo, baseando-se em um índice previamente criado. Para tanto, deve-se utilizar o comando CLUSTER. Desta forma, determinada tabela é reorganizada fisicamente, assim como está no índice.

Esta operação é chamada de clusterização é só ocorre uma única vez, no momento da utilização do comando. Isto significa dizer que demais operações que modifiquem os dados da tabela não serão refletidas na clusterização. Assim, se faz necessário que, de tempos em tempos, uma nova clusterização nas tabelas do banco seja efetuada.

É interessante também que se verifique o FILLFACTOR da tabela antes da clusterização, pois, caso seja dimensionado para menos que 100%, deixando um espaço nas páginas de dados, já que com espaço livre, novos dados são armazenados junto a dados consecutivos, possivelmente na mesma página.

Outras Considerações sobre Índices no PostgreSQL.

PostgreSQL permite a indexação multicoluna através dos índices do tipo árvore B+, Gist e GIN. Apenas os índices hash não permitem tal funcionalidade. A indexação multicoluna pode cobrir até 32 colunas, embora este limite pode ser parametrizado no código fonte do banco.

PostgreSQL também prevê a criação de índices com unicidade, ou seja, não permite a duplicação de dados em sua estrutura. Isto já ocorre automaticamente quando existe uma restrição do tipo UNIQUE sobre determinada coluna que se queira indexar, ou quando a tabela possui uma chave primária definida. Em outros caso, é necessário explicitar através do comando:

CREATE UNIQUE INDEX nome_do_indice ON nome_da_tabela (nome_da_coluna);

Por último, PostgreSQL também permite a criação de um índice parcial, que leva em consideração apenas um subconjunto de valores de determinada coluna.

...