Sistemas de Base de Dados
2011-2012
Análise de Sistemas de Base de Dados
Armazenamento e estruturas de indexação
Grupo 06:
Alexandre Pinote no 36917
Carlos Loureiro no 37770
Pedro Tiple no 37902
3 de Dezembro de 2011
Resumo
Este documento foi desenvolvido no contexto da cadeira Sistemas de Bases
de Dados, nele são descritos detalhes de funcionamento de 3 sistemas de
bases de dados.
As funcionalidades descritas incidem sobre o tema Armazenamento e
estruturas de indexação. É feita uma comparação de como os vários sistemas
funcionam em vários aspectos, no caso de existirem, são explicitados quais os
comandos ou parâmetros que permitem alterar o funcionamento do sistema.
Conteúdo
1 Introdução
3
2 Armazenamento
2.1 Controlo de Buffer Management
2.2 File System . . . . . . . . . . . .
2.3 Mecanismos de partições . . . . .
2.4 Organização dos tuplos . . . . . .
2.5 Registos de tamanho variável . .
2.6 Multitable Clustering . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3 Estruturas de indexação
3.1 Estruturas de indexação . . . . . . . . . . . . . . . .
3.1.1 PostgreSQL . . . . . . . . . . . . . . . . . . .
3.1.2 DB2 . . . . . . . . . . . . . . . . . . . . . . .
3.1.3 Oracle . . . . . . . . . . . . . . . . . . . . . .
3.2 Estruturas dos ı́ndices para organização de ficheiros .
3.3 Indexação com mais de um ficheiro para conjuntos de
3.4 Hashing . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 Estruturas temporariamente inconsistentes . . . . . .
4 Conclusão
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
atributos
. . . . .
. . . . .
4
4
5
8
11
13
14
16
16
16
17
17
18
19
20
21
23
1
Lista de Figuras
2.1
2.2
2.3
2.4
Hierarquia de armazenamento do DB2. . . . . . .
Hierarquia de armazenamento do Oracle. . . . . .
Ilustração de particionamento de tabelas no DB2.
Estrutura de uma página em DB2. . . . . . . . .
.
.
.
.
7
8
10
12
3.1
3.2
3.3
3.4
Organização de ficheiros no DB2. . . . . . . . . . . . . . . . .
Indexações particionadas no DB2. . . . . . . . . . . . . . . .
Ilustração da função de hash. . . . . . . . . . . . . . . . . . .
Ilustração do comando SET CONSTRAINTS onde é possı́vel
aplicar a clausula DEFERRABLE. . . . . . . . . . . . . . . .
18
19
21
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
22
Capı́tulo 1
Introdução
Sistemas de bases de dados são sistemas complexos que ainda nos dias de
hoje estão a ser melhoradas. Devido a diferentes requisitos e ideais, há
um número largo de sistemas de bases de dados actualmente em utilização.
Nesta realidade estudar sistemas de bases de dados implica o conhecimento
de mais do que um sistema, no entanto, é difı́cil ter um conhecimento aprofundado de todos eles devido às suas complexas diferenças e número elevado.
Actualmente o sistema de bases de dados de referência é o Oracle Database que é um sistema proprietário da Oracle, de modo a ter uma visão
de mais opções existentes no mercado faz sentido compará-lo com outro
sistema, que neste caso vai ser o DB2 da IBM.
Sistemas proprietários não é tudo o que está disponı́vel, existem vários
sistemas open source que exibem capacidades equivalentes ao dos grandes
sistemas, um exemplo é o PostgresSQL, este sistema é desenvolvido em comunidade aberta e está disponı́vel sem custos.
3
Capı́tulo 2
Armazenamento
2.1
Controlo de Buffer Management
De modo a que se reduza o número de leituras ao disco, os sistemas de bases
de dados usam buffers próprios para manter em memória informação que
possa vir a ser lida mais que uma vez. Estes buffers diferem das caches do
SO porque os buffers mantêm páginas da base de dados enquanto as caches
guardam blocos do disco.
PostgreSQL
Neste sistema o buffer é um vector simples em que cada entrada é um
buffer. Fazer uma procura no buffer é feito usando um processo chamado
clock-sweep que consiste em percorrer por ordem crescente as entradas do
vector. Cada buffer pode estar no estado pinned ou unpinned e limpo ou
sujo. Está no estado pinned quando está a ser referenciado por um ou mais
clientes, neste estado o buffer não pode ser reciclado no caso de ser preciso
um buffer novo. Sempre que novos dados são escritos para um buffer, este
passa a sujo que indica que deve ser escrito para o disco. Inicialmente
existem já buffers alocados e o valor por defeito são 32 megabytes alocados
para o total dos buffers, o tamanho destes pode ser alterado com o parâmetro
shared buffers(). A alocação de novos buffers consiste em verificar a lista de
buffers vazios que o sistema mantém e usar o primeiro livre, ou se estiverem
todos ocupados, escolhe um para libertar e coloca lá o novo. O processo de
escolha consiste em efectuar o clock-sweep previamente descrito à procura
do primeiro buffer com um estado diferente de pinned.
DB2
No sistema DB2 existem buffer pools que inicialmente têm espaço suficiente para 16 páginas, cada pool guarda páginas de tamanho 4 KB, 8 KB, 16
KB e 32 KB. A memória necessária para manter as buffer pools é alocada
quando a base de dados é activada usando os parâmetros definidos e sempre
4
que a base de dados é desactivada o espaço dos buffer pools é libertado.
As primeiras quatro pools são automaticamente criadas de modo a que
haja sempre uma buffer pool em qualquer circunstância e estas são apenas
usadas pelo sistema e não podem ser removidas.
A gestão das pools é feita pelo database manager, é este que tem a responsabilidade de verificar se já existe uma certa página no buffer e no caso
de não existir, ir buscá-la ao disco.
O número de páginas de uma dada pool cresce automaticamente no caso
de serem precisas mais páginas, no entanto é possı́vel aumentar o tamanho
de uma buffer pool usando o comando ALTER BUFFERPOOL. Novas buffer
pools podem ser criadas com CREATE BUFFERPOOL.
O sistema disponibiliza o comando db2mtrk que mostra a quantidade de
memória da base de dados que está alocada para buffer pools.
As páginas dos buffer pools podem estar em vários estados, a ser usada
ou não e suja ou limpa. Páginas em uso são páginas que estão a ser lida
ou actualizadas, se a página está a ser actualizada só pode ser acedida por
quem a está a actualizar, no entanto se estiver a ser lida, pode ser por mais
que um utilizador. No caso de ser necessário remover uma página do buffer,
a escolha da página para remoção é feita segundo os critérios: quando foi a
ultima vez que a página foi referênciada, qual a probabilidade de a página
voltar a ser refênciada, o tipo de dados que a página contem e se a página
foi alterada sem ser escrita para o disco.
Oracle
O Oracle usa buffers que estão organizados usando tabelas de endereçamento
e listas ligadas. Operações de pesquisa sobre todos os buffers fazem uso da
buffer address table que indexa os buffers por número do buffer.
Operações de pesquisa sobre buffers com um identificador de página
especifico usam a buffer hash table que está organizada em buckets de buffers,
em que cada buffer bucket contem uma lista ligada de todos os buffers que o
hash do seu id seja o mesmo que o id do bucket. Para libertar buffers, é usado
o algoritmo LRU(Least Recently Used ) que como o nome indica, liberta o
buffer que não é usado à mais tempo. A entidade que gere os buffers chamase Database Writer (DBWR), este processo tem três estruturas interna:
• cadeias de buffers;
• uma lista LRUW(a lista com os buffers ”sujos”);
• a lista LRU.
2.2
File System
Uma vez que os sistemas de bases de dados normalmente estão a funcionar
por cima de um sistema operativo, faz sentido usar o sistema de ficheiros
5
do mesmo, no entanto, por questões de segurança e optimização, pode ser
melhor implementar um sistema de ficheiros proprietário que está especificamente desenhado para atender às necessidades do sistema de bases de dados.
Usar o sistema de ficheiros do sistema operativo implica a necessidade de ter
compatibilidade com os vários SOs mais comuns mas simplifica o desenvolvimento da base de dados. Usando um sistema de ficheiros próprio garante
que a base de dados funciona com qualquer sistema operativo, no entanto
adiciona complexidade ao sistema da base de dados.
PostgreSQL
O PostgreSQL faz uso do sistema de ficheiros do sistema operativo para
manter as directorias e os ficheiros, dos quais existem vários.
Cada tabela e ı́ndice é mantido num ficheiro individual e sempre que um
destes ficheiros excede o tamanho de 1GB o mesmo é separado em segmentos
de até 1GB cada, deste modo garante-se compatibilidade com plataformas
que tenham limitações no tamanho máximo de ficheiros, o valor de 1GB é
definido pelo valor por defeito de um segmento e pode ser alterado com a
opção –with-segsize no momento de construção da base de dados.
De maneira a manter eficientemente espaços livres, cada tabela ou ı́ndice
tem associado um freespace map que representa os espaços livres de cada
tabela ou ı́ndice.
Tabelas com colunas que tenham entradas potencialmente muito grandes têm uma tabela TOAST(The Oversized-Attribute Storage Technique)
associada, no PostgreSQL são usadas páginas de tamanho fixo normalmente
com 8kb e não é permitido que um tuplo ocupe mais que uma página, dai
usar-se o TOAST, este vai comprimir ou partir campos grandes de mais em
mais que uma row.
DB2
O DB2 guarda a informação em áreas chamadas tablespaces que podem
ser System Managed Space ou Database Managed Space. No caso de um
System Managed Space o sistema de ficheiros do sistema operativo é usado
e as tabelas e as suas entradas são guardadas em directorias organizadas
hierarquicamente. Em Database Managed Space o sistema aloca inicialmente
espaço para guardar informação, este bloco que deve ocupar um espaço
razoavelmente grande é considerado um só ficheiro para o sistema operativo
e a estrutura do ficheiro é própria do DB2.
A criação de um novo tablespace é feito com o comando CREATE TABLESPACE e os seus parâmetros podem ser alterados com o comando ALTER TABLESPACE.
Ter mais que um tablespace pode ser útil porque no DB2, a informação é
guardada como páginas. Dependendo do tamanho das página de um tablespace e o tamanho de linhas nas suas tabelas, uma linha pode ocupar muitas
6
páginas, ou uma página pode conter muitas linhas. Armazenar uma linha,
ou muitas linhas, em uma única página, permite que toda a linha ou linhas
ao sejam lidas como uma única página de disco.
Tamanhos de página grandes são bons para armazenar tabelas com linhas muito longas ou tabelas usadas regularmente para acesso de dados
sequenciais. Por outro lado, armazenar linhas pequenas acedidas aleatoriamente em páginas grandes é uma utilização pouco eficiente das buffer pools.
Para permitir que diferentes tabelas sejam armazenadas com tamanhos de
página e tamanhos diferentes e para permitir que o buffer seja separado, é
melhor usar vários tablespaces com tamanhos diferentes.
Figura 2.1: Hierarquia de armazenamento do DB2.
Oracle
Na base de dados Oracle a informação é mantida de uma maneira muita
semelhante ao DB2, como se pode ver pela figura 2.2 a estrutura é igual
e a única coisa que se altera é o nome atribuido aos vários objectos. O
equivalente às páginas do DB2 são os blocos, os blocos mantêm informação
de linhas, dentro do bloco novas linhas crescem ”para cima”a partir do fim
do bloco. Quando uma nova entrada é introduzida e esta não cabe no bloco,
um novo bloco é criado e a informação é partida entre os dois blocos.
7
Figura 2.2: Hierarquia de armazenamento do Oracle.
2.3
Mecanismos de partições
Particionar uma base de dados, que consiste em dispersar os elementos que
constituem a base de dados ou as tabelas em partes independentes, pode
trazer vantagens em termos de performance, manutenção e disponibilidade.
Uma capacidade útil deste mecanismo é permitir distribuir a carga da base
de dados por vários nós, o que cria uma base de dados distribuı́da que introduz possivelmente redundância, evite um ponto central de falha e permite
uma maior escalabilidade do sistema.
PostgreSQL
Ainda que de um modo descrito pelo próprio PostgreSQL como simples,
este sistema suporta particionamento de tabelas. O benefı́cio de usar particionamento só se nota para tabelas bastante grandes, com um tamanho maior
que a quantidade de memória fı́sica disponı́vel. O particionamento é feito
através de herança de tabelas, cada partição tem de ser criada como filha
de uma única tabela pai, estando esta vazia e apenas serve para representar
o data set inteiro.
São suportadas as seguintes formas de particionamento:
• Particionamento por intervalo: a tabela é particionada em intervalos definidos por uma coluna chave ou grupo de colunas, sem
sobreposição entre intervalos.
• Particionamento de listas: a tabela é particionada por definição
explicita de quais valores chave aparecem em quais partições.
8
O particionamento é definido da seguinte forma:
• Cria-se a tabela mestre que vai ser herdade por todas as partições,
esta tabela não deve ter informação e não deve ter check constraints a
não se que se deseje que todas as partições as tenham;
• Cria-se várias tabelas filhas da tabela mestre, estas tabelas são as
partições;
• Adiciona-se restrições às partições que definem os valores chaves permitidos em cada tabela. Exemplo:
CHECK ( x = 1 )
CHECK ( county IN ( ’Oxfordshire’, ’Buckinghamshire’, ’Warwickshire’ ))
CHECK ( outletID >= 100 AND outletID < 200 )
• Para cada partição, cria-se um ı́ndice nas colunas chaves;
• Opcionalmente define-se triggers ou regras para redireccionar informação
inserida na tabela mestre para a partição correcta;
• Verificar que o parâmetro de configuração contraint exclusion não está
desactivado no ficheiro postgresql.conf porque se estiver, as procuras
não vão ser optimizadas.
DB2
O gestor da base de dados do DB2 permite particionar a base de dados
com bastante flexibilidade, permite escolher a maneira que a informação é
distribuı́da usando chaves de distribuição e em quantas partições as tabelas
são distribuı́das por meio de escolha de grupos de partições e tablespaces
sobre os quais se deve fazer a distribuição.
O sistema mantém um mapa de distribuição actualizável que especifica a
atribuição de chaves às várias partições, isto permite uma maior flexibilidade
de paralelização para tabelas grandes enquanto ao mesmo tempo permite
guardar tabelas pequenas em poucas partições.
As partições podem ser definidas no ficheiro db2nodes.cfg e o seu conteúdo
pode ser acedido fazendo um select da tabela DB PARTITIONS().
A chave de distribuição de cada tabela pode ser definida no momento de
criação ou com ALTER TABLE, se a chave de distribuição não for definida
o seu valor por defeito é a primeira coluna da chave primária.
Uma tabela particionada tem de ter pelo menos um campo que não seja
do tipo long ou LOB. As suas entradas são distribuı́das pelas partições do
seguinte modo: um algoritmo de hashing é aplicado a todas as colunas da
chave de distribuição e o resultado é o valor de ı́ndice do mapa de distribuição, com o valor que se encontra no ı́ndice gerado atribui-se a partição a
que a entrada faz parte.
9
Figura 2.3: Ilustração de particionamento de tabelas no DB2.
Oracle
No Oracle, partições não são uma funcionalidade base, é necessária uma
licença à parte que só está disponı́vel para a versão Enterprise Edition.
Os mecanismos de particionamento permitem particionar uma tabela em 1
milhão de partições.
São disponibilizados os seguintes tipos de particionamento:
• Range partitioning – diferentes ranges são atribuı́dos às várias partições.
Exemplo:
PARTITION BY RANGE(empno) (
partition e1 values less than (1000)
tablespace ts1,
partition e2 values less than (2000)
tablespace ts2,
partition e3 values less than (MAXVALUE) tablespace ts3
);
• Hash partitioning – uma chave hash é usada para atribuir entradas
pelas partições. Exemplo:
PARTITION BY HASH(empno)
10
PARTITIONS 3
STORE IN (empts1, empts2, empts3);
• Composite partitioning – particiona usando dois métodos de particionamento, faz uma partição inicial com o primeiro método e depois
cada partição nova é sub-particionada com o segundo método.
PARTITION BY RANGE(orderdate)
SUBPARTITION BY HASH(prod#) SUBPARTITIONS 4
( PARTITION q1 VALUES LESS THAN
(TO_DATE(’01-APR-2009’, ’DD-MON-YYYY’)),
PARTITION q2 VALUES LESS THAN
(TO_DATE(’01-JUL-2009’, ’DD-MON-YYYY’)),
PARTITION q3 VALUES LESS THAN
(TO_DATE(’01-OCT-2009’, ’DD-MON-YYYY’)),
PARTITION q4 VALUES LESS THAN (MAXVALUE)
);
• List partitioning – atribui listas de chaves de particionamento a cada
partição individualmente.
PARTITION BY LIST (deptno) (
PARTITION p10 VALUES (10),
PARTITION p20 VALUES (20),
PARTITION p30 VALUES (30,40)
);
• Interval partitioning – evolução do range partitioning em que se
uma nova entrada não corresponde a nenhum range, é criado uma
nova partição para guardar estas entradas.
• System partitioning – permite a uma aplicação controlar o particionamento da tabela.
• Reference partitioning – o método de particionamento é herdado
da tabela pai.
2.4
Organização dos tuplos
A maneira como os tuplos das tabelas são mantidos vai afectar directamente
e eficiência da base de dados, devido a isso é necessário escolher a melhor
organização possı́vel para os requisitos do sistema. Como os diferentes sistemas de bases de dados funcionam de maneiras diferentes, uma organização
pode ser vantajosa para um sistema e para outro não.
11
PostgreSQL
Como vimos na secção ”File System”o PostgreSQL mantém um freespace
map que sugere que a organização dos tuplos é em Heap, ou seja, os tuplos
são introduzidos no primeiro espaço livre no ficheiro da tabela. Esta organização elimina a necessidade de efectuar cálculos para descobrir onde deve
ser colocado o tuplo, mas no momento de leitura, toda a página tem de ser
percorrida para descobrir o tuplo desejado.
DB2
O DB2 organiza os tuplos dentro do ficheiro num heap, de cada vez que
um tuplo é adicionado, é procurado um espaço livre suficientemente grande
dentro da página, no caso de não haver espaço, uma nova página é criada.
A gestão dos espaços livres é feito da seguinte maneira, no cabeçalho
da página existe um apontador para o primeiro espaço livre contı́guo, um
apontador para o começo da ”cadeia de buracos”e o espaço total livre no
bloco.
Figura 2.4: Estrutura de uma página em DB2.
Oracle
De modo igual às duas bases de dados vistas anteriormente, o Oracle
organiza os tuplos em heap, dentro de um bloco os tuplos são introduzidos
”de baixo para cima”e no caso de se introduzir um tuplo que não caiba no
bloco, um novo é criado para o acomodar.
12
2.5
Registos de tamanho variável
Os sistemas de bases de dados usam um leque variado de tipos de atributos. Para isso os registos no sistema de base de dados têm de ter uma
certa implementação para permitir tamanhos fixos desses registos ou para
disponibilizar registos de tamanho variáveis.
PostgreSQL
O PostgreSQL permite registos de tamanho variável usando o TOAST
(The Overside-Attribute Storage Technique). Por defeito a estrutura do
sistema é implementada em slotted pages e um registo não pode passar o
tamanho da slotted page mas foi criado o TOAST para contornar isso. O
TOAST para contornar esta limitação vai comprimir os registos ou decompôlos em várias linhas sendo que existe uma tabela TOAST com apontadores
para linhas que não a original. Este processo é transparente para o utilizador
e existem várias técnicas que o TOAST usa para as diferentes colunas:
• PLAIN – neste tipo de técnica não é utilizada qualquer compressão
nem decomposição em mais linhas, é o tipo de estratégia usado para
colunas em que o TOAST não actua;
• EXTENDED – usa compressão e decomposição em várias linhas
• EXTERNAL – usa decomposição em várias linhas mas não compressão
• MAIN – usa compressão e não decomposição em outras linhas
DB2
Em DB2 são usadas páginas com tamanhos fixos sendo que têm 4 tamanhos: 4, 8, 16 e 32 Kb. Numa tabela podemos ter até 1012 colunas com
páginas de 32Kb. Quando aparecem registos de tamanho variável em DB2
a forma de os tratar pode ser diferente. No caso de ser LOB (Large object)
é usada uma técnica de criar uma nova página a cada 4, 8, 16 ou 32Mb
dependendo do tamanho de página. Estas páginas estão num local diferente
dos dados actuais. No caso de ser LF (Long Field ) os dados são guardados
em pequenos segmentos numa área de 32Kb. Dados como Long Varchar
ou Long VarGraphic, tal como LOB, usam alocação de novas páginas com
tamanho 4Kb.
Oracle
O Oracle tal como no DB2 implementa LOB ou Large Object. Em Oracle
este tipo de dados também é guardado no table space da tabela ou fora da
linha da tabela. São guardados fora da linha da tabela quando o utilizador
especifica que quer que assim seja recorrendo ao comando DISABLE STORAGE IN ROW quando se cria uma tabela, quando o tamanho do LOB
13
ultrapassa os 4000 bytes ou quando o tamanho já esteve acima dos 4000 bytes. Para o caso de nunca ter ultrapassado os 4000 bytes é armazenado na
própria linha da tabela. Os segmentos onde são armazenados os conteúdos
podem ser personalizáveis pelo comando STORE AS na criação da tabela.
Exemplo de sintaxe de um objecto LOB:
CREATE TABLE ContainsLOB_tab (n NUMBER, c CLOB)
lob (c) STORE AS BASICFILE segname (
TABLESPACE lobtbs1 CHUNK 4096
PCTVERSION 5
NOCACHE LOGGING
STORAGE (MAXEXTENTS 5)
);
2.6
Multitable Clustering
Os Multitable clusters são usados quando duas ou mais tabelas compartilham
a chave do mesmo cluster e as tabelas são frequentemente juntas na chave
de cluster.
PostgreSQL
Em PostGreSQL é possı́vel criar um cluster de acordo com uma indexação.
Para se criar um cluster usa-se a seguinte sintaxe:
CLUSTER [VERBOSE] table_name [ USING index_name ]
O parâmetro VERBOSE serve para mostrar um debug enquanto é feito o
clustering.
Não é possı́vel criar multitable clustering como em Oracle, mas é possı́vel
para uma uma única tabela.
DB2
Não foi encontrado na documentação do DB2 se é possı́vel ou não criar
multitable clustering. Ainda assim contém um método para criar clustering
multidimensional (MDC).
Oracle
No Oracle é possı́vel fazer multitable clustering por hash ou por index.
Para criar um multitable clustering deve-se começar por criar um cluster
por hash:
CREATE CLUSTER cluster_attr_part (atributo_partilhado NUMBER(10));
E no final da declaração de cada uma das tabelas que partilham o mesmo
atributo:
14
CLUSTER cluster_attr_part (atributo_partilhado);
Assim o Oracle pode aumentar a sua performance recorrendo a estes clusters
que guardam dados das suas tabelas.
15
Capı́tulo 3
Estruturas de indexação
3.1
Estruturas de indexação
3.1.1
PostgreSQL
Em PostgreSQL são suportadas várias estruturas de indexação tais como
B + -tree, Hash, GiST e GIN mas a que o PostgreSQL usa por defeito são as
B + -tree.
B + -tree
Tendo um certo atributo indexável, as B + -tree no PostGreSQL são capazes
de lidar com as seguintes comparações para esse atributo:
< ; <= ; => ; = ; >
Também podem ser usadas B + -tree em comparações usando LIKE ou m̃as
tem de se usar strings em que o seu inı́cio seja constante e não % por exemplo.
As B + -tree podem também ser utilizadas para ordenar.
Hash
No PostgreSQL o hash é só automaticamente usado para comparações de
igualdade “=”. Para se criar uma indexação em hash corre-se o comando:
CREATE INDEX name ON table USING hash (column);
GiST
A indexação GiST ou Generalized Search Tree é essencialmente usada para
comparações de dados bidimensionais das quais:
<< ; & < ; & > ; >> ; << | ; & < | ; |& > ; | >> ; @ > ; < @ ; = ; &&
16
Uma das capacidades que o GiST tem é encontrar vizinhos próximos de um
ponto onde, por exemplo nesta query, ele vai encontrar os 5 pontos mais
próximos do ponto (10,10):
SELECT * FROM places
ORDER BY location <-> point ’(10,10)’ LIMIT 5;
GIN
A indexação GIN ou Generalized Inverted Index é usada onde os valores têm
mais de uma chave, ou seja, por exemplo array’s. Para isso o GIN consegue
tratar as seguintes comparações:
< @ ; @ > ; = ; &&
3.1.2
DB2
Em DB2 são suportadas as B + -tree para estrutura de indexação na maior
parte dos casos. Para criar uma indexação devemos seguir a seguinte sintaxe:
CREATE UNIQUE INDEX UNIQUE_NAME ON PROJECT(PROJNAME)
Em casos especı́ficos como geo-localização são utilizados também Spatial grid
indexes e Geodetic Voronoi indexes.
3.1.3
Oracle
É possı́vel usar no Oracle dois tipos de indexação: B + -tree e bitmaps. Para
criar indexações do tipo B + -tree usa-se a seguinte sintaxe:
CREATE [UNIQUE] INDEX nome_indexaçao
ON nome_tabela (coluna1, coluna2, ... ,coluna_n)
[ COMPUTE STATISTICS ];
UNIQUE indica que a combinação de valores da indexação têm de ser
únicos. COMPUTE STATISTICS é uma opção do comando bastante aconselhada porque permite aos optimizadores do Oracle reunirem estatı́sticas
enquanto criam a indexação. Estas estatı́sticas vão permitir aos optimizadores escolher a melhor execução de queries do SQL.
Para criar indexações do tipo bitmap usa-se a seguinte sintaxe:
CREATE BITMAP INDEX nome_bitmap ON nome_tabela (coluna);
Este comando vai permitir criar bitmaps. Os bitmaps vão criar arrays
bidimensionais com os valores de uma coluna para cada linha da tabela.
Assim, quando o Oracle precisar de retornar uma linha numa query, o Oracle
vai descomprimir o bitmap para a RAM e poderá ser rapidamente encontrar
a linha que deseja.
17
3.2
Estruturas dos ı́ndices para organização de ficheiros
PostgreSQL
Não foi encontrado na documentação do PostgreSQL se este utiliza as
estruturas dos ı́ndices para organização de ficheiros.
DB2
Usa também as B + -tree para organização de ficheiros de ı́ndice para a
localização de records das tabelas. Em DB2 existe um ı́ndice organizado
numa B + -tree sendo que nesse ı́ndice estão os RID (record ID). Os RID são
responsáveis por guardar a localização real dos dados, informação essa que
se expressa numa pagina e no slot.
Figura 3.1: Organização de ficheiros no DB2.
Na figura acima pode-se perceber facilmente como DB2 gere e usa organização de ficheiros. Existe uma B + -tree que tem o ı́ndice para as páginas
reais implementado que depois em cada pagina de ı́ndice contem o RID.
Oracle
Em Oracle, para a organização dos ficheiros, são usados Heaps e Hashing,
ao que as estruturas de indexação não são usadas para este fim.
18
3.3
Indexação com mais de um ficheiro para conjuntos de atributos
PostgreSQL
O PostgreSQL só suporta um ficheiro ı́ndex por atributos, não permite
que haja vários como em DB2.
DB2
O DB2 suporta indexações particionadas para conjuntos de atributos.
Quando criamos uma indexação temos uma opção disponı́vel PARTITIONED que serve para alocar a indexação na “table spaces” onde estão os
respectivos atributos. Para clarificar melhor a ideia o DB2 tem “table spaces”, que é onde as tabelas estão alocadas, sendo que essas tabelas podem
estar particionadas por vários table spaces ou não. No caso de estarem particionadas é possı́vel que o ı́ndice seja também particionado e cada parte
esteja no mesmo “table space” dos valores que ele indexa. Para se criar uma
indexação particionada utiliza-se a seguinte sintaxe:
CREATE INDEX StoreNum ON sales(store_num) PARTITIONED
Figura 3.2: Indexações particionadas no DB2.
19
Oracle
Tal como em DB2, as indexações podem ser particionadas. Em Oracle são
permitidas vários tipos de partições como locais e globais. As partições de
indexações locais referem-se a que uma dessas partições indexáveis vêm de
uma certa partição de uma tabela. As partições de indexações globais podem
referir-se a que uma dessas partições indexáveis vêm de várias partições da
tabela. Para criar indexações destes tipos seguimos a seguinte sintaxe:
CREATE INDEX invoices_idx ON invoices (invoice_date) LOCAL;
Ou
CREATE INDEX invoices_idx ON invoices (invoice_date);
Que correspondem a criar uma indexação particionada local e a uma indexação particionada global respectivamente.
3.4
Hashing
Existe duas técnicas de hashing, o hashing estático e dinâmico. O hashing
estático tem o número de páginas primárias no directório fixo. Assim,
quando um bucket 1 está cheio, é necessário um overflow bucket para armazenar qualquer registro adicional que seja para ser inserido no bucket cheio.
Este problema pode ser resolvido com um link para uma página de overflow, ou com uma lista ligada de páginas de overflow. A lista ligada pode ser
separada para cada bucket, ou é possı́vel usar a mesma lista para todos os
bucket em overflow. Ao procurar por um registo, o bucket original é acedido
primeiro, depois os overflow buckets. Desde que haja muitas chaves com
um hash para o mesmo bucket, encontrar um registro pode exigir o acesso a
várias páginas em disco, o que muito prejudica o desempenho. O problema
da procura longa de overflow bucket é resolvido por Hashing Dinâmico. Em
Hashing Dinâmico o tamanho do directório cresce com o número de colisões
para acomodar novos registros e evitar longas páginas de overflow. Hashing
Extensı́vel e lineares são duas técnicas de hashing dinâmico.
PostgreSQL
O algoritmo de hashing usado pelo PostgreSQL foi desenvolvido por W.
Litwin [1]. Este hashing é dinâmico, não possuindo qualquer rehashing que
permita a eliminação dos buckets de overflow. É de salientar que este tipo
de indexação é relativamente pior que a indexação por B + -tree. Para além
de um maior uso de recursos, este indexação por hash não suporta ı́ndices de
múltiplas colunas. Por tudo isto, o uso deste tipo de indexação é bastante
desencorajado, até mesmo pelos responsáveis pelo PostgreSQL.
1
O termo bucket refere-se a uma unidade de armazenamento que pode armazenar um
ou mais registos. Tipicamente um bucket é um bloco do disco.
20
DB2
O DB2 não suporta indexação por hash. Apesar disso o DB2 tem uma
forma de computar o id da linha da tabela através da chave primária em
tabelas apropriadas para o efeito (range clustered table).
Oracle
O Oracle não permite ı́ndices hash, permite apenas organização estática
hash.
Figura 3.3: Ilustração da função de hash.
3.5
Estruturas temporariamente inconsistentes
Existem Sistemas de Base de Dados que permitem que as suas estruturas
de dados estejam temporariamente inconsistentes. O estado inconsistente
das estruturas acontece principalmente quando há necessidade de adiar a
verificação de restrições de integridade, por exemplo, em transacções. Para
além de alguns sistemas permitirem desactivar as restrições no inicio das
transacções e activá-las automaticamente a quando o termino da transacção
ainda é possı́vel definir o relaxamento das restrições durante a criação de
uma tabela.
PostgreSQL
Este Sistema de Base de Dados permite o adiamento da verificação de
certas restrições de integridade usando a clausula DEFERRABLE. Quando
usada, a verificação da restrição é realizada no final da transacção (usando
o comando SET CONSTRAINTS ). Actualmente apenas as restrições UNIQUE, PRIMARY KEY, EXCLUDE e REFERENCES permitem o uso desta
clausula. Por defeito todas as restrições são verificadas em cada operação
(NOT DEFERRABLE ).
21
DB2
Este Sistema de Base de Dados permite o adiamento da verificação de
restrições de chaves estrangeiras mas é necessário o uso do utilitário LOAD.
Existe, no entanto, alguns produtos que disponibilizam a clausula DEFERRABLE para atrasar a verificação de restrições.
Oracle
No Oracle a funcionalidade de adiamento da verificação de restrições de
integridade é idêntico ao do PostgresSQL(Ver acima).
Figura 3.4: Ilustração do comando SET CONSTRAINTS onde é possı́vel
aplicar a clausula DEFERRABLE.
22
Capı́tulo 4
Conclusão
No âmbito de estudar um tema entre vários sistemas de bases de dados, foi
possı́vel compreender que existem diferentes implementações para as mesmas
funcionalidades nos sistemas. No nosso tema notou-se uma variação maior
porque comparámos dois sistemas bastantes diferentes, principalmente por
um ser open-source e o outro não. Também por este motivo verificámos que
a documentação encontrada é completamente diferente sendo que a documentação open-source está mais simples também devido ao seu sistema de
base de dados ser mais simples. De uma forma geral conseguimos perceber
as ideias base da matéria dada nas aulas com diferentes implementações não
só direccionadas para o Oracle.
23
Bibliografia
[1] Witold Litwin, Linear Hashing: A new Algorithm for Files and Tables
Addressing. ICOD, 1980
[2] http://publib.boulder.ibm.com/infocenter/db2luw/v8/index.
jsp?topic=/com.ibm.db2.udb.doc/core/r0008305.html
[3] http://www.postgresql.org/docs/9.1/static/indexes-types.
html
[4] http://publib.boulder.ibm.com/infocenter/db2luw/v9r8/
index.jsp?topic=%2Fcom.ibm.db2.luw.admin.perf.doc%2Fdoc%
2Fc0005393.html
[5] http://publib.boulder.ibm.com/infocenter/db2luw/v9r8/
index.jsp?topic=%2Fcom.ibm.db2.luw.admin.perf.doc%2Fdoc%
2Fc0005391.html
[6] http://www.postgresql.org/docs/manuals/
[7] http://www.westnet.com/~gsmith/gregsmith/content/
postgresql/PostgreSQLBufferManagement.htm
[8] http://publib.boulder.ibm.com/infocenter/db2luw/v9r8/
index.jsp?topic=%2Fcom.ibm.db2.luw.admin.perf.doc%2Fdoc%
2Fc0005393.html
[9] http://www.devx.com/getHelpOn/10MinuteSolution/16575/1954
[10] http://www.postgresql.org/docs/9.1/interactive/storage.
html
[11] http://www.postgresql.org/docs/9.1/interactive/
storage-file-layout.html
[12] http://en.wikibooks.org/wiki/Oracle_and_DB2,_Comparison_
and_Compatibility/Storage_Model/Physical_Storage/Oracle
[13] http://en.wikipedia.org/wiki/Partition_%28database%29
24
[14] http://publib.boulder.ibm.com/infocenter/db2luw/v9r5/
topic/com.ibm.db2.luw.admin.partition.doc/doc/c0004126.
html?resultof=%22partition%22%20%22partit%22
[15] http://www.postgresql.org/docs/current/static/
ddl-partitioning.html
[16] http://en.wikibooks.org/wiki/Oracle_and_DB2,_Comparison_
and_Compatibility/Storage_Model/Physical_Storage/DB2#Page
[17] http://www.postgresql.org/docs/9.1/static/storage-fsm.html
[18] http://en.wikibooks.org/wiki/Oracle_and_DB2,_Comparison_
and_Compatibility/Storage_Model/Physical_Storage/Oracle#
Block
[19] https://forums.oracle.com/forums/thread.jspa?threadID=
487488
[20] http://docs.oracle.com/cd/E11882_01/server.112/e17118/
statements_10003.htm
[21] http://www.orafaq.com/forum/t/66928/2/
[22] http://docs.oracle.com/cd/B19306_01/server.102/b14200/
clauses002.htm
[23] http://euler.vcsu.edu:7000/11719/
[24] http://www.orafaq.com/tuningguide/advanced%20objects.html
[25] http://www.orafaq.com/tuningguide/advanced%20objects.html
[26] http://publib.boulder.ibm.com/infocenter/db2luw/v8/index.
jsp?topic=/com.ibm.db2.udb.doc/admin/c0007201.htm
[27] http://en.wikibooks.org/wiki/Category:Oracle_and_DB2,
_Comparison_and_Compatibility
[28] http://en.wikipedia.org/wiki/Linear_hashing
[29] http://www.cs.sfu.ca/CourseCentral/354/zaiane/material/
notes/Chapter11/node1.html
[30] http://publib.boulder.ibm.com/infocenter/db2luw/v8/index.
jsp?topic=/com.ibm.db2.udb.doc/core/r0008305.htm
[31] http://ssdi.di.fct.unl.pt/sbd/func/teoricas
25