PostgreSQL
Índices
Nuno Campos
N.º 51431
Índice


Introdução
Tipos de Índices
–
–
–
–






2
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
Nuno Campos - N.º 51431
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





–
3
\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
Nuno Campos - N.º 51431
Tipos de Índices (B-Tree)

B+Tree

Utiliza-se em igualdades e intervalos

Usa Algoritmos de Lehman e Yao com alterações:
–
–
–
4
Chaves de tamanho variável
Trinco nas leituras a nível da página
Ligação entre nós folhas é bidireccional
Nuno Campos - N.º 51431
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:
–
–
–
–
–
–
–
5
<< (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?)
Nuno Campos - N.º 51431
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:
–
–
–
6
Desempenho semelhante a B-Trees
Tamanho e tempo de construção piores
Utilização desencorajada.
Nuno Campos - N.º 51431
Tipos de Índices (GiST)
7

GiST – Generalized Search Tree

Estrutura em árvore

Implementação de esquemas de índices

Desenvolvimento de tipos de dados próprios
Nuno Campos - N.º 51431
Classes de Operadores
8

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
Nuno Campos - N.º 51431
Í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
–
–
9
B-Tree, GiST
src\include\pg_config_manual.h (INDEX_MAX_KEYS 32)
Nuno Campos - N.º 51431
Í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:


10
Uma restrição de unicidade
Uma chave primária
Nuno Campos - N.º 51431
Í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
–
–
11
Expressão computada para cada tuplo inserido
Expressão computada para cada tuplo actualizado
Nuno Campos - N.º 51431
Índices parciais

Índice construído sobre subconjunto da tabela
–
12
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
Nuno Campos - N.º 51431
Examinar a utilização do índice

ANALYZE
–
–

EXPLAIN
–
–
13
Recolhe estatísticas sobre a distribuição de
valores nas tabelas
Necessária para estimar tuplos devolvidos
Exame de utilização de um índice
Devem ser usados dados reais
Nuno Campos - N.º 51431
Referências







14
Efficient Locking for Concurrent Operations on BTrees, 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/Postgre
SQL/gist.html
Nuno Campos - N.º 51431
Exemplo B+Tree
15
Nuno Campos - N.º 51431
Exemplo R-Tree

16
Devolver as imagens com x < 5 e y <10
Nuno Campos - N.º 51431
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
n – apontador para bucket a dividir, quando chega à posição 3, volta ao inicio
0

17
1
2
3
Inserir cinco valores (fc = 5/8 = 0,625)
0100
1000
0
0001
0010
0011
1
2
3
Nuno Campos - N.º 51431
Exemplo Hashing Linear (2)

Quando inserimos o 6º valor
0100
1000
0


18
0001
1
0010
1110
2
0011
3
Fc = 6/8 = 0,75  divisão de bucket n = 0
1000
0001
0010
1110
0
1
2
Fc = 6/10 = 0,6; n = 1
0011
0100
3
4
Nuno Campos - N.º 51431
Exemplo Hashing Linear (3)

Quando inserimos 0101, fc = 7/10 = 0,7
1000
0

0001
0101
1
0010
1110
2
0011
0100
3
4
Quando inserimos 1010, fc = 8/10 = 0,8
1000
0001
0101
0010
1110
0011
0100
overflow
19
1010
Nuno Campos - N.º 51431
Exemplo Hashing Linear (4)

Divide n = 1; fc = 8/12 = 0,66
1000
0
0001
1
0010
1110
2
0011
3
0100
0101
4
5
1010 overflow

Inserir 0111; fc = 9/12 = 0,75; ocorre divisão para n = 2
1000
20
0
0001
1
0010
1010
2
0011
0111
3
0100
4
0101
5
1110
6
Nuno Campos - N.º 51431