Online Index Rebuild Nagavamsi Ponnekanti and Hanuma Kodavalla   View Paper (PDF)   Return to Industrial Sessions Abstract In this paper we present an efficient method to do online rebuild of a B+-tree index. This method has been implemented in Sybase Adaptive Server Enterprise (ASE) Version 12.0. It provides high concurrency, does minimal amount of logging, has good performance and does not deadlock with other index operations. It copies the index rows to newly allocated pages in the key order so that good space utilization and clustering are achieved. The old pages are deallocated during the process. Our algorithm differs from the previously published online index rebuild algorithms in two ways. It rebuilds multiple leaf pages and then propagates the changes to higher levels. Also, while propagating the leaf level changes to higher levels, level 11 pages are reorganized, eliminating the need for a separate pass. Our performance study shows that our approach results in significant reduction in logging and CPU time. Also, our approach uses the same concurrency control mechanism as split and shrink operations, which made it attractive for implementation. References Note: References link to DBLP on the Web. [Com79] Douglas Comer : The Ubiquitous B-Tree. Computing Surveys 11(2) : 121-137(1979) [GR93] Jim Gray , Andreas Reuter : Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2 Contents [LY81] Philip L. Lehman , S. Bing Yao : Efficient Locking for Concurrent Operations on B-Trees. TODS 6(4) : 650-670(1981) [MF92] C. Mohan , Frank Levine : ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging. SIGMOD Conference 1992 : 371-380 [SBC97] Gary H. Sockut , Thomas A. Beavin , Chung-C. Chang : A Method for On-Line Reorganization of a Database. IBM Systems Journal 36(3) : 411-436(1997) [Smi90] ... [ZS96] Chendong Zou , Betty Salzberg : On-line Reorganization of Sparsely-populated B+trees. SIGMOD Conf. 1996 : 115-124 BIBTEX @inproceedings{DBLP:conf/sigmod/PonnekantiK00,   author    = {Nagavamsi Ponnekanti and                 Hanuma Kodavalla},    editor    = {Weidong Chen and                 Jeffrey F. Naughton and                 Philip A. Bernstein},    title     = {Online Index Rebuild},    booktitle = {Proceedings of the 2000 ACM SIGMOD International Conference on                 Management of Data, May 16-18, 2000, Dallas, Texas, USA},    journal   = {SIGMOD Record},    publisher = {ACM},    volume    = {29},    number    = {2},    year      = {2000},    isbn      = {1-58113-218-2},    pages     = {529-538},    crossref  = {DBLP:conf/sigmod/2000},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.