Digital Symposium Collection 2000  

 
 
 
 
 
 

 



















High-Performance Extensible Indexing

Marcel Kornacker

  View Paper (PDF)  

Return to Query Systems

Abstract
Today's object-relational DBMSs (ORDBMSs) are designed to support novel application domains by providing an extensible architecture, supplemented by domain-specific database extensions supplied by external vendors. An important aspect of ORDBMSs is support for extensible indexing, which allows the core database server to be extended with external access methods (AMs). This paper describes a new approach to extensible indexing implemented in Informix Dynamic Server with Universal Data Option (IDS/UDO). The approach is is based on the generalized search tree, or GiST, which is a template index structure for abstract data types that supports an extensible set of queries. GiST encapsulates core database indexing functionality including search, update, concurrency control and recovery, and thereby relieves the external access method (AM) of the burden of dealing with these issues. The IDS/UDO implementation employs a newly designed GiST API that reduces the number of user defined function calls, which are typically expensive to execute, and at the same time makes GiST a more flexible data structure. Experiments show that GiST-based AM extensibility can offer substantially better performance than built-in AMs when indexing user-defined data types.


References

Note: References link to DBLP on the Web.

[Ben75]
Jon Louis Bentley : Multidimensional Binary Search Trees Used for Associative Searching. CACM 18(9) : 509-517(1975)
[Com79]
Douglas Comer : The Ubiquitous B-Tree. Computing Surveys 11(2) : 121-137(1979)
[GG98]
Volker Gaede , Oliver Günther : Multidimensional Access Methods. Computing Surveys 30(2) : 170-231(1998)
[Gut84]
Antonin Guttman : R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984 : 47-57
[HNP95]
Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer : Generalized Search Trees for Database Systems. VLDB 1995 : 562-573
[Inf98a]
...
[Inf98b]
...
[KMH97]
Marcel Kornacker , C. Mohan , Joseph M. Hellerstein : Concurrency and Recovery in Generalized Search Trees. SIGMOD Conference 1997 : 62-72
[LS90]
David B. Lomet , Betty Salzberg : The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance. TODS 15(4) : 625-658(1990)
[LS92]
David B. Lomet , Betty Salzberg : Access Method Concurrency with Recovery. SIGMOD Conference 1992 : 351-360
[MHL+92]
C. Mohan , Donald J. Haderle , Bruce G. Lindsay , Hamid Pirahesh , Peter Schwarz : ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. TODS 17(1) : 94-162(1992)
[Ora98]
...

Referenced by

  1. Michael J. Carey : Review - High-Performance Extensible Indexing. ACM SIGMOD Digital Review 2 : (2000)

BIBTEX

@inproceedings{DBLP:conf/vldb/Kornacker99,
  author    = {Marcel Kornacker},
   editor    = {Malcolm P. Atkinson and
                Maria E. Orlowska and
                Patrick Valduriez and
                Stanley B. Zdonik and
                Michael L. Brodie},
   title     = {High-Performance Extensible Indexing},
   booktitle = {VLDB'99, Proceedings of 25th International Conference on Very
                Large Data Bases, September 7-10, 1999, Edinburgh, Scotland,
                UK},
   publisher = {Morgan Kaufmann},
   year      = {1999},
   isbn      = {1-55860-615-5},
   pages     = {699-708},
   crossref  = {DBLP:conf/vldb/99},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


























Copyright(C) 2000 ACM