Avaliação de Desempenho no Acesso a Dados
Utilizando Índices Multidimensionais
Sérgio Luís Dill, Regis Schuch, Paulo Sérgio Sausen,
Edson Luiz Padoin, Mauricio de Campos
Departamento de Tecnologia – UNIJUÍ - Ijuí, RS - Brasil
{dill,Regis.schuch,sausen, padoin, mauricio}@unijui.edu.br
Abstract. This paper presents a case study whose main purpose is evaluating
traditional index performance compared to multidimensional index
performance. Such evaluation is carried out by executing several queries over
a sample database specially build for that purpose. Our goal is identify the
types of queries that present performance improvements by exploring
multidimensional indexes. We also measure the disk space needed for both
types of indexes.
Categoria do Trabalho: Trabalho de Graduação.
Resumo. Este artigo apresenta em estudo de caso que tem como objetivo
avaliar o desempenho de índices tradicionais com índices multidimensionais.
Para isso, um ambiente de teste foi construído de maneira que diferentes tipos
de consultas possam ser executados sobre a base de dados explorando os
diferentes índices para acessar os dados. Pretende-se identificar os tipos de
consultas que apresentam ganhos de desempenho com utilização dos novos
tipos de índices bem como avaliar o espaço em disco utilizado por estes tipos
de índices.
1. Introdução
À medida que os bancos de dados tornam-se cada vez maiores resultantes do
contínuo crescimento no volume de dados armazenados, a importância e necessidade de
acessos eficientes aos dados torna-se um desafio para o Administrador de Banco de
Dados (DBA). Modernos Sistemas de Gerência de Bancos de Dados (SGBDs) oferecem
uma vasta gama de recursos e funcionalidades que podem ser exploradas pelo DBA para
melhorar o desempenho global do banco de dados. Um destes recursos que o DBA
pode explorar é a possibilidade de criação de índices sobre as relações. Os índices
podem melhorar o desempenho das consultas uma vez que oferecem um caminho
alternativo de acesso aos dados.
Tradicionalmente, os SGBDs permitem que o DBA crie vários índices sobre as
relações sendo que, apenas um destes índices, pode ser atribuído a propriedade de
índice cluster. Entretanto, as últimas versões dos principais SGBDs tornaram possível a
criação de índices multidimensionais. Índices multidimensionais permitem que os dados
possam ser agrupados fisicamente no disco considerando várias dimensões
simultaneamente.
Por outro lado, a criação de índices em relações tem duas desvantagens.
Primeiro, índices são estruturas redundantes e portanto aumentam o tamanho do banco
de dados. Segundo, as operações de atualização tornam-se mais lentas uma vez que a
cada atualização, os índices adicionais também precisam ser atualizados e mantidos.
Assim, o DBA precisa estar atento e consciente das vantagens e desvantagens que cada
índice representa para o banco de dados.
Este artigo tem como objetivo avaliar o desempenho de índices tradicionais e de
índices multidimensionais bem como o espaço em disco utilizado. Para tanto, o texto
está organizado da seguinte forma: Na Seção 2 apresenta-se uma visão geral sobre
indexação em bancos de dados bem como uma descrição das vantagens e limitações de
cada tipo. Na seção 3, desenvolve-se um estudo de caso que avalia o desempenho de
índices multidimensionais. Para avaliar o desempenho, define-se um conjunto de
consultas que exploram os diferentes índices para acessar o banco de dados. Na Seção 4
apresentam-se os resultados do estudo de caso e ao final, apresentam-se as conclusões
do trabalho e sugestões de trabalhos futuros.
2. Indexação
Índices são estruturas de acesso auxiliares associadas às relações e que têm por objetivo
aumentar o desempenho na execução de consultas. Tipicamente, um índice permite que
um registro seja encontrado sem que seja necessário acessar toda a relação (arquivo de
dados).
Quando uma relação não possui índices definidos, o SGBD deve percorrer toda
a relação para localizar os dados desejados. Isso pode tornar o tempo de resposta de
consultas sobre relações com milhares de tuplas oneroso, sendo que a finalidade de um
índice é permitir a rápida determinação do endereço de um registro do arquivo, dada um
argumento de pesquisa. O endereço identifica a posição onde está armazenada a tupla,
na memória secundária [MOLINA,2002].
Há vários métodos de indexação utilizados comumente pelos SGBDs, como
árvores B, hashes e listas encadeadas, porém a estrutura de índice árvore B+ é a mais
utilizada das diversas estruturas de índices. Isto porque ela mantêm sua eficiência, à
medida que novas inserções, atualizações ou remoções de dados ocorrem. Um índice
árvore B+ tem a forma de uma árvore balanceada na qual todos os caminhos da raiz da
árvore até uma de suas folhas são do mesmo comprimento [SILBERSCHATZ, 1999].
2.1. Índice Cluster
O arquivo do índice cluster é um arquivo ordenado e composto por dois campos.
O primeiro campo corresponde à chave usada para a indexação e o segundo campo é um
ponteiro para a tupla correspondente no arquivo de dados. A Figura 1 ilustra uma
representação de um índice cluster onde o arquivo de dados está ordenado de acordo
com a chave do índice (atributo mês). A coluna RID representa o ponteiro que armazena
a localização física do registro no arquivo de dados.
Uma limitação das relações tradicionais reside no fato de que elas podem estar
fisicamente ordenadas considerando apenas um índice, ou seja, uma dimensão. Quando
um novo índice é definido sobre a relação, este não terá a propriedade de ser índice
cluster. [BHATTACHARJEE, 2003].
Dados da Relação
Índice(Mes)
RID
RID
312
1
1
312
2858
3336
93561
377
313
2
2
313
2858
3340
93575
377
314
3
3
314
2858
3357
93585
377
315
4
4
315
2858
3367
93615
377
316
5
5
316
2858
3369
93625
377
317
6
6
317
2858
3363
93635
377
318
7
7
318
2858
3473
93640
377
MES
MES
ORC
LOT
TURMA CURSO
Figura 1. Exemplo de uma relação com um índice cluster.
A Figura 2 mostra a relação e a adição de um novo índice (no atributo LOT).
Observa-se que a ordem dos dados não corresponde ao ordenamento da chave do novo
índice. Entretanto, é possível mudar o índice cluster de uma relação através do processo
de reorganização. Neste processo pode-se selecionar o índice para ordenar fisicamente
os dados. Isto significa que caso o segundo índice (LOT) fosse selecionado para ser o
índice cluster, o primeiro (MÊS) automaticamente perderia a propriedade de ser índice
cluster.
Dados da Relação
Índice (MÊS)
RID
RID
312
1
1
313
2
2
313
2858
3357
314
3
3
314
2858
315
4
4
315
316
5
5
317
6
318
7
MES
MÊS
ORC
LOT
Índice (LOT)
TURMA CURSO
RID
LOT
377
6
3336
93575
377
3
3340
3340
93585
377
2
3357
2858
3367
93615
377
4
3367
316
2858
3473
93625
377
7
3369
6
317
2858
3336
93635
377
1
3363
7
318
2858
3369
93640
377
5
3473
312
2858
3363
93561
Figura 2. Uma Relação com um índice cluster e outro índice não cluster.
A Seção 2.2 apresenta a técnica para criação de índices multidimensionais que
foi desenvolvida para ter-se a possibilidade de organizar fisicamente os dados
considerando mais de uma dimensão (atributo) eliminando assim a limitação das
relações tradicionais que podem ter os dados organizados fisicamente a partir de
somente um índice.
2.2. Índice Cluster Multidimensional
Um índice cluster multidimensional (MDC) permite que os dados de uma relação sejam
fisicamente ordenados a partir da combinação de atributos. Além disso, pode reduzir
igualmente a sobrecarga da manutenção de dados, como operações de manutenção de
reorganização e índice durante as operações de inserção, atualização e exclusão, e ainda
uma diminuição nas operações de I/O. [ZIKOPOULOS, 2003]. Apresenta-se a seguir
alguns conceitos que são utilizados para a aplicação de índices multidimensionais.
•
Dimensão - Uma dimensão MDC é um índice cluster em uma relação MDC. Uma
dimensão é formada por um conjunto de colunas de uma relação. A dimensão
permite que os dados da relação sejam fisicamente ordenados a partir de mais de
uma coluna da relação (dimensão) simultaneamente.
•
Slice - Um slice é um conjunto de blocos que contêm páginas de dados que possuem
valor igual em um atributo da dimensão da relação MDC.
•
Célula Lógica - Qualquer combinação única de valores dimensionais compõe uma
célula lógica
•
Página – Unidade de armazenamento do banco de dados. Um banco de dados pode
ter páginas de diversos tamanhos sendo que 4KB, 8KB, 16KB e 32KB são os mais
comuns.
•
Bloco - Conjunto de páginas consecutivas no disco.
•
Tamanho ou Fator de Bloco – Especifica o número de páginas armazenadas em
um bloco. Representa uma medida importante uma vez que determina como os
dados serão organizados no disco. Em cada bloco, somente serão inseridas tuplas
com um determinado valor de dimensão. Não é uma boa solução definir um fator de
bloco alto para uma dimensão com alta cardinalidade, pois haverá grande
desperdício de espaço uma vez que muitas páginas dentro do bloco podem ficar
vazias.
•
Índice de Bloco - Um índice de bloco é uma nova estrutura de índices semelhante a
um índice registro tradicional, exceto que no nível folha, as chaves apontam para
blocos ao invés registros.
A Figura 3 apresenta uma relação MDC com duas dimensões, a dimensão MÊS e
a dimensão ORC. Esta Figura possui 12 retângulos, os quais representam as células da
relação. Cada retângulo possui desenhos com os cantos arredondados que representam
os blocos onde os dados estão armazenados. Por exemplo, o bloco número 1 contém
dados referentes ao mês 312 (Jan) e a unidade orçamentária 2858. Os blocos 1, 6, 12, 9,
19, 39, 41, 42 e 11 contêm dados referentes ao slice da dimensão ORC com valor 2858.
Figura 3. Relação de dados MDC organizada pelas dimensões mês e orc
2.3. Escolha dos índices Multidimensionais
Algumas considerações são importantes na definição das dimensões que irão compor o
índice multidimensional. Considerando a Tabela 1, vários atributos são candidatos para
serem utilizados como dimensões. O principal aspecto que o DBA deve considerar para
determinar quais dimensões devem ser selecionadas para compor um índice é a
identificação das consultas que podem se beneficiar através do uso deste índice MDC.
Neste sentido, elaboramos um conjunto de consultas que podem servir de guia para o
DBA. Estas consultas estão agrupadas e descritas na Seção 3.2 e serão utilizadas realizar
a avaliação de desempenho.
Outro aspecto a ser considerado no projeto de índices multidimensionais está na
densidade das células com base nos dados inseridos na relação. A densidade da célula
pode ser obtida através do produto cartesiano das cardinalidades de cada uma das
dimensões utilizadas no índice.
RH MÊS ITEM PROG LOT GEST ORC TURMA PROJ CURSO COMP HORAS
3
312
5
599 3336
2858 2850
93561
100
377
5660
5,25
4
312
5
599 3469
2858 2850
93575
200
377
5660
10,50
4
312
5
599 3469
2858 2850
93585
2
377
5660
10,50
3
313
5
599 3336
2858 2850
93615
4
377
5660
10,50
3
313
5
599 3336
2858 2850
93625
7
377
5660
10,50
4
313
69
579 3469
2862 2850
90
31,85
....
Tabela 1: Primeiras 8 (de 313.312) linhas da tabela MDC
Para exemplificar o cálculo da densidade da célula e o conseqüente número de
células resultantes, considere a Tabela 1 com as seguintes características.
• Atributo MÊS com cardinalidade 24, ou seja, existem 24 valores
possíveis para o domínio deste atributo.
• Atributo LOT com cardinalidade 211, ou seja, há 211 unidades de lotação
possíveis.
• Atributo ORC com cardinalidade 34, ou seja, há 34 diferentes unidades
orçamentárias.
A definição de um índice multidimensional sobre os atributos MÊS e LOT teria
um máximo de 5064 células (24 * 211) possíveis. Considerando que cada valor
diferente de célula usa uma página diferente para ser armazenada, poderá haver
desperdício de espaço caso a densidade da célula seja baixa. Entretanto, a definição de
um índice multidimensional sobre os atributos MÊS e ORC teria um máximo de 816
células possíveis.
3. Estudo de caso
O estudo caso tem o objetivo de avaliar o desempenho de índices MDC. Para realizar o
estudo de caso, definiu-se um ambiente computacional e definiu-se um conjunto de
consultas a serem avaliadas sobre a base de dados contendo as relações.
3.1. Configuração do Ambiente computacional e da base de dados
A execução das consultas SQL foi realizada em um computador, modelo notebook, com
processador Intel® Core Duo 1.66 GHz com 1GB de RAM e HD SATA de 5400 RPM
de 120 GB rodando o Sistema Operacional Ubuntu GNU/Linux 8.04, SGBD DB2
instalado sobre um sistema de arquivos do tipo“ext3” com blocos de dados de 4KB.
As Listagens 1a e 1b mostram as instruções SQL para a criação das relações
utilizadas no estudo de caso. Verifica-se que a estrutura das relações é idêntica. A
relação MDC utiliza um índice multidimensional enquanto que a relação denominada
NaoMDC utiliza índices tradicionais. Ambas as relações foram criadas em espaços de
relações com tamanho de página de dados de 4KB. Após a criação das tabelas, efetuouse a carga de dados totalizando 313.312 tuplas (exatamente os mesmos dados em cada
relação).
** Criação da Relação MDC
** Criação da Relação NaoMDC
CREATE
TABLE MDC (
RH
integer not null,
Mes
integer not null,
item
integer not null,
prog
integer not null,
Lot
integer not null,
Gest
integer not null,
orc
integer not null,
turma
integer,
Proj
integer,
curso
integer,
Comp
integer,
horas
decimal(13,5))
ORGANIZE BY (Mes, orc)
CREATE
RH
Mes
item
prog
Lot
Gest
orc
turma
Proj
curso
Comp
horas
TABLE NaoMDC (
integer not null,
integer not null,
integer not null,
integer not null,
integer not null,
integer not null,
integer not null,
integer,
integer,
integer,
integer,
decimal(13,5))
create index Ind3 on MDC (lot);
create index Ind1 on NaoMDC (Mes);
create index Ind2 on NaoMDC (Orc);
create index Ind3 on NaoMDC (Lot);
Listagem 1a: Instrução SQL para
Listagem 1b: Instrução SQL para
criação de uma relação MDC
criação de uma relação tradicional
3.2. Definição das consultas
A Tabela 2 apresenta as consultas SQL que serão utilizadas para avaliar o desempenho.
Cada consulta explora um determinado tipo de acesso. Por exemplo, a consulta C1,
encontra as tuplas que satisfazem um critério de busca pontual conforme especificado na
cláusula WHERE (mes = 315). Abaixo, segue uma descrição dos tipos de consultas
usadas neste trabalho.
• Point Query – A condição de pesquisa deste tipo consulta baseia-se em um
determinado valor de atributo o qual seja indexado. Este atributo é parte do índice
multidimensional.
•
One Dimension Range Query – A condição de pesquisa deste tipo de consulta
inlcui uma faixa de valores de um determinado atributo. Neste exemplo, a consulta
qualifica as tuplas cujo valor para o atributo mes está na faixa de 315 a 323.
•
Two Dimension Range Query - A condição de pesquisa deste tipo de consulta
inlcui uma faixa de valores para dois determinados atributos. Neste exemplo, a
consulta qualifica as tuplas cujo valor para o atributo mes está na faixa de 315 a 323
e cujos valores para o atributo LOT esteja entre 2800 a 3000.
•
Query on a CELL - Seleciona dados de uma célula em específico. Recupera os
valores de uma combinação única de valores dimensionais, em tuplas que possuem
exatamente os mesmos valores para cada atributo do índice MDC ou índice
tradicional.
•
INDEX ANDing - Executa uma consulta que utiliza como condição where um
intervalo de valores utilizando um dos atributos que compõem a dimensão e outro
intervalo de valores utilizando um atributo que compõem outro índice.
•
INDEX ORing - Executa uma consulta que utiliza como condição um intervalo de
valores condicionado num dos atributos que compõem a dimensão ou(mais) um
intervalo de valores condicionando outro atributo que compõem um índice.
•
Full Table Scan – Executa um comando que percorre toda a relação, ou parte dela,
retornando dados. Nesta, a condição de pesquisa não esta relacionada com os
índices e sim com a leitura total ou parcial da relação, recupera todos os registros do
arquivo e testa se os valores dos atributos satisfazem a condição de seleção ou não.
•
Table Scan With block Predicate - Seleciona dados a partir de uma condição de
pesquisa baseada na exclusão de um bloco de dados.
Instrução SQL
Consulta
Tipo
C1
Point Query
C2
One Dimension
Range Query
select sum(horas) from
mdc
where mes > 315 and mes < 323
C3
Two Dimension
Range Query
select sum(horas) from
mdc
(mes > 315 and mes < 323) and
(orc > 2800 and orc < 3000)
C4
Query on a
CELL
C5
C6
C7
C8
select sum(horas)
from
mdc where
mes = 315
where
select mes, lot, horas from
mes = 313 and orc = 2426
mdc
where
INDEX
ANDing
select mes, lot, horas from
(mes > 313 and mes < 326) AND
(lot > 2426 and lot < 3000)
mdc
where
INDEX
ORing
select rh
from mdc where
(lot > 2800 and lot < 2850) OR
(mes > 315 AND mes < 328)
Full
Table Scan
Table Scan
With block
Predicate
select sum(horas)
from mdc where
gest
<
3000
select mês,lot, horas
from
mdc where
mes not in(326)
Tabela 2: Consultas SQL utilizadas para avaliar o desempenho dos índices.
4. Resultados
A análise dos resultados do estudo de caso pode ser dividida em duas etapas
considerando os diferentes recursos utilizados. A primeira etapa avalia o desempenho
das consultas executadas sobre a base de dados. O desempenho foi medido a partir da
coleta do tempo necessário para a execução de cada consulta. Primeiramente a consulta
foi executada sobre a relação MDC e em seguida sobre a relação NaoMDC. A segunda
etapa avalia o espaço de armazenamento necessário para cada tipo de relação.
4.1. Desempenho das Consultas
Para obter o tempo de execução de uma consulta com precisão maior, antes de cada
execução, o SGBD era parado (stop) e iniciado (start) novamente. Este procedimento
garante que possíveis dados que poderiam estar armazenados nos buffers são eliminados
obrigando assim que cada consulta faria a leitura dos dados a partir do disco rígido.
Outro aspecto a ser considerado diz respeito ao tempo necessário para a exibição dos
resultados. Assim, direcionou-se a saída de cada comando para /etc/null eliminando
assim o tempo para que o sistema exibisse o resultado. Desta forma, garante-se que o
tempo obtido refere-se somente ao tempo de processamento da consulta, independente
da quantidade de linhas que esta consulta produz. A Tabela 3 apresenta o tempo (em
segundos) gasto na execução de cada consulta considerando uma média de 5 execuções.
Número da
Consulta
C1
C2
C3
C4
C5
C6
C7
C8
Tempo (segundos)
Tuplas
Qualificadas
MDC
NaoMDC
0,036
0,391
13296
0,094
0,109
97338
0,016
0,141
40090
0,047
0,078
68
12,718
12,516
107394
13,203
24,938
261358
0,234
0,297
247686
35,515
36,625
300358
Tuplas
Retornadas
1
1
1
68
107394
261358
247686
300358
Tabela 3: Tempo, em segundos, utilizado pelas consultas.
Para facilitar o processo de análise, dividiu-se as consultas em dois grupos os
quais são mostrados na Figura 1a e 1b. A Figura 1a mostra as consultas cujo tempo de
resposta está abaixo de 1 segundo. A Figura 1b mostra as consultas cujo tempo de
resposta é superior a 1 Segundo..
Analisando os dados dos gráficos verifica-se que em geral as consultas
executadas sobre a relação MDC (com índices multidimensionais) obtiveram um tempo
de resposta menor. Das 8 consultas executadas, em 7 a relação com índices MDC obteve
resultados melhores que a relação com índices tradicionais.
Na consulta C1, a relação MDC obteve grande vantagem em comparada à
relação tradicional. Nesta a relação tradicional necessitou de tempo superior a 10 vezes
o tempo necessário pela relação MDC.
Figura 1b. Tempo de respostas
das consultas C5, C6, C8.
Figura 1a. Tempo de resposta das
consultas C1, C2, C3, C4 e C7.
Da mesma forma na consulta C3, a relação com índices MDC obteve grande
vantagem sobre a relação com índices tradicionais sendo aproximadamente 8 vezes mais
rápida. A Consulta C6 também teve um desempenho significativamente melhor na
relação MDC. Ela retornou em praticamente a metade do tempo que a consulta feita
sobre a relação tradicional (NaoMDC).
Nas consultas C2, C4, C7 e C8, novamente a relação MDC executou as
consultas mais rapidamente que a relação com índices tradicionais. Apesar da diferença
não ser tão significativa quanto nas consultas anteriores.
A única consulta que a relação com índices tradicionais executou em menor
tempo foi a consulta C5. Mesmo assim a diferença encontrada foi inferior a 2%.
4.2. Espaço de armazenamento
Consultou-se os metadados do SGBD para verificar o espaço em disco que foi gasto
para armazenar os arquivos de dados e índices para as relações analisadas. A Tabela 4
apresenta relações e a quantidade de páginas de dados e índices alocadas.
Relação
MDC
NaoMDC
Dados
Número de
Espaço em
Páginas
Megabyte
6.476
5.598
25,30
21,87
Índices
Número de
Espaço em
Páginas
Megabyte
536
1.545
2,09
6,04
Tabela 4: Espaço em disco alocado pelas relações.
Analisando a quantidade de páginas de dados utilizados pelas relações, verificase que a relação MDC gasta mais espaço (6.476 páginas de 4KB) comparado a relação
NaoMDC (5.598 páginas de 4KB). Entretanto, a relação MDC é muito mais econômica
em termos de espaço no que tange aos índices. A relação MDC usou apenas 536 páginas
enquanto que a NaoMDC usou 1.545 páginas. A Figura 2 apresenta uma comparação do
espaço, em Megabytes, necessários para armazenar os dados e os índices. Verifica-se
que os dados da relação MDC gasta 25,3 megabytes enquanto que os dados da relação
NaoMDC gasta 21,87 megabytes. Por outro lado, nota-se que o espaço utilizado pelos
índices multidimensionais (2,09 MB) é bastante inferior ao espaço gasto pelos índices
tradicionais (6,04 MB).
Figura 2. Quantidade de espaço em disco ocupado pelas relações.
5. Conclusão
Este artigo apresentou um estudo de caso para avaliar o desempenho de índices
tradicionais e índices multidimensionais bem como o espaço em disco utilizado por
estas diferentes estruturas de índices. Através do estudo de caso notou-se dois aspectos
importantes. O primeiro mostra claramente que as consultas que exploram os índices
multidimensionais têm desempenho superior, comparadas as relações tradicionais.
Foram avaliadas oito diferentes consultas sobre as relações sendo que em 7 as relações
MDC obtiveram desempenho superior. O segundo ponto observado no estudo de caso
refere-se ao espaço em disco gasto por ambas as relações. Observa-se que as relações
MDC gastam mais espaço em disco para os dados, mas gastam menos espaço em disco
para armazenar os índices. A partir destes pontos, conclui-se que o desempenho superior
das consultas obtidas sobre a relação MDC está estreitamente ligado a forma com os
dados e índices estão estruturados fisicamente no disco.
Referências
BHATTACHARJEE,
Bishwaranjan;
CRANSTON,
Leslie;
MALKEMUS,
Tim;
PADMANABHAN, Sriram. Boosting Query Performance: Multidimensional Clustering.
Nova Iorque: DBMagazine, Quarter 2, 2003.
DELAMARE,
Leandro.
“Introdução
ao
http://www.devmedia.com.br/articles/viewcomp.asp?comp=7774.
DB2”`,
2008,
MOLINA, Hector Garcia; ULLMAN, Jeffrey D.; WIDOM, Jennifer. Database Systems – The
complete book. Prentice Hall, 2002.
NAVATHE; ELMASRI. Sistema de Banco de Dados: Fundamentos e Aplicações. Terceira
Edição. Editora LTC, 2002, P 795.
ZIKOPOULOS, Paul C.; BAKLARZ, George; DEROOS, Dirk; MELNYK, Roman. DB2(R)
Version 8: The Official Guide. Prentice Hall PTR, 2003. P 384.
SILBERSCHATZ, Abraham; KORTH, Henry F.; SUDARSHAN, S. Sistema de Banco de
Dados. Editora Makron Books, 1999. P 765.
WELGAN, Robert. Comparing Query Performance: MDC vs. Non-MDC Tables. Beaverton:
DB2Magazine, Quarter 2, 2003.