PostgreSQL Índices

PostgreSQLÍndices

Nuno CamposN.º 51431

Nuno Campos - N.º 514312

Índice

Introdução Tipos de Índices

– B-Tree– R-Tree– Hash– GiST

Classes de Operadores Índices Compostos Índices Únicos Índices em Expressões Índices Parciais Examinar a Utilização do Índice


Introdução

PostgreSQL actualiza índice quando uma tabela é modificada

Trabalho extra para operações de manipulação de dados

Índices não essenciais ou não utilizados devem ser removidos

postgresql-8.1.0\src\– \backend\access\ - Métodos de acesso aos dados

\gist\ – definição de métodos de acesso \hash\ – métodos dos índices hash \index\ – usado por todos os tipos de índices \nbtree\ – algoritmo Lehman and Yao's de gestão de b+tree \rtree\ - métodos usados em r-tree’s

– \backend\catalog – Rotinas de criação e manipulação de índices

http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/access/gist


Tipos de Índices (B-Tree)

B+Tree

Utiliza-se em igualdades e intervalos

Usa Algoritmos de Lehman e Yao com alterações:– Chaves de tamanho variável– Trinco nas leituras a nível da página– Ligação entre nós folhas é bidireccional


Tipos de Índices (R-Tree)

Divide espaço com caixas aninhadas hierarquicamente (pode haver sobreposição)

Árvore com nós folhas à mesma profundidade

Adequados para consultas a dados espaciais

Optimizador considera o uso de uma R-Tree para comparações envolvendo:– << (Está à esquerda?)– &< (Não se estende à direita de?)– &> (Não se estende à esquerda de?)– >> (Está à direita?)– @ (Está contido ou sobre?)– ~= (O mesmo que?)– && (Sobrepõem-se?)


Tipos de Índices (Hash)

Algoritmo de Hashing Linear desenvolvido por W. Litwin

Optimizador considera o uso de Hash para comparações de igualdades.

No PostgreSQL, os índices Hash:– Desempenho semelhante a B-Trees– Tamanho e tempo de construção piores– Utilização desencorajada.


Tipos de Índices (GiST)

GiST – Generalized Search Tree

Estrutura em árvore

Implementação de esquemas de índices

Desenvolvimento de tipos de dados próprios


Classes de Operadores

Pode ser especificada para cada coluna do índice

Identifica os operadores a serem usados pelo índice para cada coluna

Cada classe inclui funções para o tipo respectivo

Usualmente a classe de operadores padrão é suficiente


Índices Compostos

Índice com mais de um atributo

SELECT nome FROM teste2 WHERE principal = constante AND secundario = constante;

CREATE INDEX idx_teste2_princ_sec ON teste2 (principal, secundario);

PostgreSQL– B-Tree, GiST– src\include\pg_config_manual.h (INDEX_MAX_KEYS 32)


Índices Únicos

Obrigam à unicidade do valor de uma coluna

CREATE UNIQUE INDEX nome …

Permite interromper a procura de valores múltiplos quando estes não existem

PostgreSQL– Apenas índices B-Tree podem ser declarados únicos– Índice criado automáticamente quando é definida:

Uma restrição de unicidade Uma chave primária


Índices em Expressões

Índices sobre expressões em vez de colunas

Útil para acesso a tabelas resultantes de cálculos

CREATE INDEX idx_teste1_lower_col1 ON teste1 (lower(col1));

Dispendioso manter expressões de índice porque– Expressão computada para cada tuplo inserido– Expressão computada para cada tuplo actualizado


Índices parciais

Índice construído sobre subconjunto da tabela– Definido por expressão condicional – predicado

Índice contém entradas para linhas que satisfazem predicado

Evita indexar valores frequentes

Reduz tamanho do índice

Acelera consultas e actualizações


Examinar a utilização do índice

ANALYZE– Recolhe estatísticas sobre a distribuição de

valores nas tabelas– Necessária para estimar tuplos devolvidos

EXPLAIN– Exame de utilização de um índice– Devem ser usados dados reais


Referências

Efficient Locking for Concurrent Operations on B-Trees, Lehman e Yao, 1981

Database Systems and Concepts, Silbertchatz, Korth and Sudarshan, 5ª edição, 2005

http://www.postgresql.org http://www.bluerwhite.org/btree/ http://nlhgis.nlh.no/gis/applets/rtree2/jdk1.1/help.html http://en.wikipedia.org/wiki/Hash_function http://

www.mcs.vuw.ac.nz/technical/software/PostgreSQL/gist.html

http://www.postgresql.org/

http://www.bluerwhite.org/btree/

http://nlhgis.nlh.no/gis/applets/rtree2/jdk1.1/help.html

http://en.wikipedia.org/wiki/Hash_function

http://www.mcs.vuw.ac.nz/technical/software/PostgreSQL/gist.html




Exemplo B+Tree


Exemplo R-Tree

Devolver as imagens com x < 5 e y <10


Exemplo Hashing Linear (1)

Inserir 10 tuplos com valores de Hash:– 0011, 0010, 0100, 0001, 1000, 1110, 0101, 1010, 0111, 1100– Factor de carregamento (fc) – máximo 0,70

Inserir cinco valores (fc = 5/8 = 0,625)0 1 2 3

01001000 0001 0010 0011

0 1 2 3

n – apontador para bucket a dividir, quando chega à posição 3, volta ao inicio



Quando inserimos o 6º valor

Fc = 6/8 = 0,75 divisão de bucket n = 0

Fc = 6/10 = 0,6; n = 1

01001000 0001 0010

1110 0011

0 1 2 3

0 1 2 3 4

1000 0001 00101110 0011 0100



Quando inserimos 0101, fc = 7/10 = 0,7

Quando inserimos 1010, fc = 8/10 = 0,8

1000 00010101

00101110 0011 0100

0 1 2 3 4

1000 00010101

00101110 0011 0100

1010overflow



Divide n = 1; fc = 8/12 = 0,66

Inserir 0111; fc = 9/12 = 0,75; ocorre divisão para n = 2

0 1 2 3 4 5

1000 0001 00101110 0011 0100

1010 overflow

0101

1000 0001 00101010

00110111 0100 0101 1110

0 1 2 3 4 5 6

Documents

PostgreSQL Índices