Digital Symposium Collection 2000

GHOST: Fine Granularity Buffering of Indexes Cheng Hian Goh, Beng Chin Ooi, D. Sim, and Kian-Lee Tan   View Paper (PDF)   Return to Caching Techniques Note: The quality of the PDF contained herein reflects that of the material supplied to the DiSC'00 Production Team. Abstract Buffering has all along been an important strategy for exploiting the cost/performance ratio of disk versus random-access memory. The buffering of disk pages belonging to a database has been well-studied, but literature that deals specifically with index buffering is scare. This is surprising given the significance of indexes (especially B+-tree like indexes) in modern DBMSs. In this paper, we describe a dual buffering scheme for indexes, called GHOST, in which part of the buffer is used to maintain popularly used "paths" of the B+-tree index, while the remainder is devoted to maintaining a Splay-tree with pointers to leaf pages containing frequently used leaf pages. This scheme allows us to maintain pointers to leaf nodes long after the paths leading to the leaf nodes have been replaced, thus maintaining "ghost" paths to the nodes. In addition to describing the search and maintenance operations for the GHOST buffering scheme, we also conduct a series of experiments in which it is shown that GHOST outperforms the best existing schemes (ILRU and OLRU) by impressive margins for almost all pragmatic query workloads. References Note: References link to DBLP on the Web. [1] ... [2] Rudolf Bayer , Edward M. McCreight : Organization and Maintenance of Large Ordered Indices. Acta Informatica 1 : 173-189(1972) [3] Stefan Berchtold , Christian Böhm , Hans-Peter Kriegel : The Pyramid-Tree: Breaking the Curse of Dimensionality. SIGMOD Conference 1998 : 142-153 [4] Chee Yong Chan , Beng Chin Ooi , Hongjun Lu : Extensible Buffer Management of Indexes. VLDB 1992 : 444-454 [5] Hong-Tai Chou , David J. DeWitt : An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB 1985 : 127-141 [6] Douglas Comer : The Ubiquitous B-Tree. Computing Surveys 11(2) : 121-137(1979) [7] Wolfgang Effelsberg , Theo Härder : Principles of Database Buffer Management. TODS 9(4) : 560-595(1984) [8] Leonidas J. Guibas , Robert Sedgewick : A Dichromatic Framework for Balanced Trees. FOCS 1978 : 8-21 [9] Antonin Guttman : R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984 : 47-57 [10] Elizabeth J. O'Neil , Patrick E. O'Neil , Gerhard Weikum : The LRU-K Page Replacement Algorithm For Database Disk Buffering. SIGMOD Conference 1993 : 297-306 [11] Beng Chin Ooi , Cheng Hian Goh , Kian-Lee Tan : Fast High-Dimensional Data Search in Incomplete Databases. VLDB 1998 : 357-367 [12] Giovanni Maria Sacco : Index Access with a Finite Buffer. VLDB 1987 : 301-309 [13] Giovanni Maria Sacco , Mario Schkolnick : A Mechanism for Managing the Buffer Pool in a Relational Database System Using the Hot Set Model. VLDB 1982 : 257-262 [14] Daniel Dominic Sleator , Robert Endre Tarjan : Self-Adjusting Binary Search Trees. JACM 32(3) : 652-686(1985) [15] S. Bing Yao : Approximating the Number of Accesses in Database Organizations. CACM 20(4) : 260-261(1977) BIBTEX @inproceedings{DBLP:conf/vldb/GohOST99,   author    = {Cheng Hian Goh and                 Beng Chin Ooi and                 D. Sim and                 Kian-Lee Tan},    editor    = {Malcolm P. Atkinson and                 Maria E. Orlowska and                 Patrick Valduriez and                 Stanley B. Zdonik and                 Michael L. Brodie},    title     = {GHOST: Fine Granularity Buffering of Indexes},    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     = {339-350},    crossref  = {DBLP:conf/vldb/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM