20
PostgreSQL Índices Nuno Campos N.º 51431

PostgreSQL Índices

Embed Size (px)

DESCRIPTION

PostgreSQL Índices. Nuno Campos N.º 51431. Í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. - PowerPoint PPT Presentation

Citation preview

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

Nuno Campos - N.º 514313

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

Nuno Campos - N.º 514314

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

Nuno Campos - N.º 514315

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?)

Nuno Campos - N.º 514316

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.

Nuno Campos - N.º 514317

Tipos de Índices (GiST)

GiST – Generalized Search Tree

Estrutura em árvore

Implementação de esquemas de índices

Desenvolvimento de tipos de dados próprios

Nuno Campos - N.º 514318

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

Nuno Campos - N.º 514319

Í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)

Nuno Campos - N.º 5143110

Í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

Nuno Campos - N.º 5143111

Í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

Nuno Campos - N.º 5143112

Í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

Nuno Campos - N.º 5143113

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

Nuno Campos - N.º 5143114

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

Nuno Campos - N.º 5143115

Exemplo B+Tree

Nuno Campos - N.º 5143116

Exemplo R-Tree

Devolver as imagens com x < 5 e y <10

Nuno Campos - N.º 5143117

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

Nuno Campos - N.º 5143118

Exemplo Hashing Linear (2)

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

Nuno Campos - N.º 5143119

Exemplo Hashing Linear (3)

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

Nuno Campos - N.º 5143120

Exemplo Hashing Linear (4)

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