Online B-tree merging

ABSTRACT

Many scenarios involve merging of two B-tree indexes, both covering the same key range. Increasing demand for continuous availability and high performance requires that such merging be done online, with minimal interference to normal user transactions. In this paper we present an online B-tree merging method, in which the merging of leaf pages in two B-trees are piggybacked lazily with normal user transactions, thus making the merging I/O efficient and allowing user transactions to access only one index instead of both. The concurrency control mechanism is designed to interfere as little as possible with ongoing user transactions. Merging is made forward recoverable by following a conventional logging protocol, with a few extensions. Should a system failure occur, both indexes being merged can be recovered to a consistent state and no merging work is lost. Experiments and analysis show the I/O savings and the performance, and compare variations on the basic algorithm.

REFERENCES

• 1: Kiran J. Achyutuni , Edward Omiecinski , Shamkant B. Navathe, Two techniques for on-line index modification in shared nothing parallel databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.125-136, June 04-06, 1996, Montreal, Quebec, Canada
• 2: R. Bayer and M. Schkolnick. Concurrency of Operations on B-Trees. Acta Inf., 9:1--21, 1977.
• 3: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 4: Andreas Gärtner , Alfons Kemper , Donald Kossmann , Bernhard Zeller, Efficient Bulk Deletes in Relational Databases, Proceedings of the 17th International Conference on Data Engineering, p.183-192, April 02-06, 2001
• 5: G. Graefe. Sorting And Indexing With Partitioned B-Trees. In Biennial Conference on Innovative Data System Research, 2003.
• 6: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 7: H. V. Jagadish , P. P. S. Narayan , S. Seshadri , S. Sudarshan , Rama Kanneganti, Incremental Organization for Data Recording and Warehousing, Proceedings of the 23rd International Conference on Very Large Data Bases, p.16-25, August 25-29, 1997
• 8: Theodore Johnson , Dennis Shasha, A framework for the performance analysis of concurrent B-tree algorithms, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.273-287, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298580]
• 9: Mong Li Lee , Masaru Kitsuregawa , Beng Chin Ooi , Kian-Lee Tan , Anirban Mondal, Towards self-tuning data placement in parallel database systems, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.225-236, May 15-18, 2000, Dallas, Texas, United States
• 10: Philip L. Lehman , s. Bing Yao, Efficient locking for concurrent operations on B-trees, ACM Transactions on Database Systems (TODS), v.6 n.4, p.650-670, Dec. 1981 [doi>10.1145/319628.319663]
• 11: David Lomet, Simple, Robust and Highly Concurrent B-trees with Node Deletion, Proceedings of the 20th International Conference on Data Engineering, p.18, March 30-April 02, 2004
• 12: David Lomet , Betty Salzberg, Access method concurrency with recovery, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.351-360, June 02-05, 1992, San Diego, California, United States
• 13: David Lomet , Betty Salzberg, Concurrency and recovery for index trees, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.3, p.224-240, August 1997 [doi>10.1007/s007780050042]
• 14: C. Mohan, ARIES/KVL: a key-value locking method for concurrency control of multiaction transactions operating on B-tree indexes, Proceedings of the sixteenth international conference on Very large databases, p.392-405, September 1990, Brisbane, Australia
• 15: C. Mohan , Frank Levine, ARIES/IM: an efficient and high concurrency index management method using write-ahead logging, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.371-380, June 02-05, 1992, San Diego, California, United States
• 16: C. Mohan , Inderpal Narang, Algorithms for creating indexes for very large tables without quiescing updates, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.361-370, June 02-05, 1992, San Diego, California, United States
• 17: Peter Muth , Patrick E. O'Neil , Achim Pick , Gerhard Weikum, Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method, Proceedings of the 24rd International Conference on Very Large Data Bases, p.452-463, August 24-27, 1998
• 18: Nagavamsi Ponnekanti , Hanuma Kodavalla, Online index rebuild, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.529-538, May 15-18, 2000, Dallas, Texas, United States
• 19: Herb Schwetman, CSIM19: CSIM19: a powerful tool for building system models, Proceedings of the 33nd conference on Winter simulation, December 09-12, 2001, Arlington, Virginia
• 20: V. Srinivasan , Michael J. Carey, Performance of B⁺ tree concurrency control algorithms, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.4, p.361-406, October 1993 [doi>10.1007/BF01263046]
• 21: Chendong Zou , Betty Salzberg, On-line reorganization of sparsely-populated B+-trees, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.115-124, June 04-06, 1996, Montreal, Quebec, Canada
• 22: Chendong Zou , Betty Salzberg, Safely and Efficiently Updating References During On-line Reorganization, Proceedings of the 24rd International Conference on Very Large Data Bases, p.512-522, August 24-27, 1998