High-Performance Extensible
Indexing
Publicado em 1999 na 25th VLDB Conference
Por: Marcel Kornacker
Apresentado por:
Gustavo Augusto e Ivan Silva
TABD 23/04/12
Introdução
Métodos eficientes de acesso à árvores de
procura são cruciais para qualquer base de
dados.
Em tradicionais DBMS relacionais , árvores
B+ são suficientes para queries com tipos de
dados standards do SQL
Mas para “extensive object-relational
database management systems“ (ORDBMSs)
novos métodos são necessários.
Introdução (continuação)
As ORDBMSs são feitas para suportar
aplicações como
•
•
•
•
Servidores web dinâmicos
Sistemas de informação geográfica
Ferramentas CAD
Etc...
Para essas aplicações novos métodos de
acesso (AM) . Entrentanto fazer um AM não é
trivial, pois é necessário um vasto conhecimento
em protocolos de concorrência e recuperação
Introdução (problema)
No estado da arte comercial, há o “Oracle’s
Extensible Indexing Interface” e o “Informix
Dynamic Server with Universal Data Option”
(IDS/UDO).
Introdução (proposta)
Generalized Search Tree(GiST)
Índice
•
•
•
•
•
•
Descrição do GiST
Arquitetura e implementação do GiST
Implementation Issues
Concurrency control and Recovery
Performance Measurements
Summary
Descrição do GiST
• GiST é uma arvore equilibrada que fornece algoritmos
“template” para navegação entre estruturas de árvores
através de page splits e deletes.
• Como todas as outras árvores de indexação, o GiST
guarda pares (key, RID) nas folhas. RIDs (Record
Identifiers) apontam para os registos na pagina de
dados.
• Paginas internas contêm pares (predicado, apontador
da pagina filho) onde o predicado avalia TRUE para
cada chave dentro ou abaixo da pagina filho associada
Descrição do GiST
• Exemplos de bases que seguem essas
propriedades:
– Árvores B+
– Árvores R
• Além desses requerimentos estruturais, o GiST
não impõe nenhum requerimento extra sobre
os dados chave guardados na arvore ou sobre
a organização dos mesmos dentro e entre as
paginas permitindo dados multidimencionais.
Descrição do GiST
• O GiST suporta as operações standard de índices:
– Search: com um predicado, retorna todas as folhas
com entradas que satisfaçam o predicado
– Insert: adiciona um par (key, RID) à árvore
– Delete: remove um determinado par da árvore
• Entretanto é necessário uma ajuda de funções
externas fornecidas pelo desenvolvedor do AM
• E.g. no search, é necessário definir uma funçao consistent()
• E.g. No delete, é necessário definir uma função union()
Arquitetura e implementação do GiST
Ao implementar uma arquitetura extensão de
AM baseada em GiST certos problemas
precisam ser tratadas:
• User Defined Functions(UDF)
• Costumização do formato de armazenamento
e das paginas internas
Arquitetura e implementação do GiST
A arquitetura é dividada
em 3 partes
• GiST core(11functions)
• AM extension
• Data type adapter
Arquitetura e implementação do GiST
A arquitetura é dividada
em 3 partes
• GiST core(11functions)
• AM extension
• Data type adapter
Arquitetura e implementação do GiST
A arquitetura é dividada
em 3 partes
• GiST core(11functions)
• AM extension
• Data type adapter
Arquitetura e implementação do GiST
• s
Arquitetura e implementação do GiST
• As operações search, insert e delete mudam
de forma a usar as funçoes de interface do
GiST core.
• Essas novas operações optimizam o número
de chamadas UDF.
Implementation Issues
A implementação da extensão GiST AM inclui
controlo de concurrencia e recuperação.
Análise performance
• Concurrency control
– O protocolo de ”locking” que permite a procura e
actualizações de forma concurrente nas arvores é feita
usando uma adaptação da técnica de ”B-link tree”.
– Todas as páginas estão ligadas umas às outras.
– Para alem do link, cada página tem um PSN (page number
sequence).
– Em cada ”page split” o actual PSN da página vai para o
ramo da direita e um novo PSN é atribuído ao ramo da
esquerda.
– O Log é apenas efectuado
a cada 100 incrementos para
garantir eficiência.
Recovery
• O protocolo de ”logging” do GiST suporta alta concurrencia nas
arvores de procura, dividindo-os em ”content-changing (item
insertion and deletion at the leaf level)” e ”structuremodifying parts (page splits, parent entry updates, page
deletions)”.
• A API implementada não modifica em nada a implementação
base Informix Dynamic Server with Universal Data Option
(IDS/UDO).
Performance Measurements
• GiST-based R-trees VS built-in R-trees
– Software engineering benefits
– higher performance
– Performance comparation involves
individual search and insert
– Search built-in: 1359 UDF calls
– Search GiST-based: 80 UDF calls
–
–
–
–
Insert built-in: 182 UDF calls
Insert GiST-based: 4 UDF calls
Insert built-in W/split: 704 UDF calls
Insert GiST-based W/split: 66 UDF...
Summary
• Modelo GiST-based como extenção da implementação IDS/UDO.
• Clara separação das funcionalidades de uma AM e os algoritmos
genéricos de ”search” e ”update”.
• 1. Não tem que se preocupar com concurrencias nem protocolos de
recuperação
• 2. AM está ligeiramente integrado na BD do ponto de vista operacional, o
que garante tanta fiabilidade quando as built-in.
• Redução das linhas de implementação.
• Melhoramento na performance entre os 14 e 40%.