Transactions on the multiversion B+-tree

ABSTRACT

The multiversion B⁺-tree (MVBT) by Becker et al. assumes a single-data-item update model in which each new version created for a data item is given a timestamp that is unique across the entire MVBT. In this paper, we extend the MVBT model with multi-action transactions such that all (final) data-item versions created by a transaction are given the same timestamp. We show that the MVBT algorithms can be modified to work in a setting in which multiple readonly transactions and a single updating transaction operate concurrently in snapshot isolation on the MVBT, without compromising the asymptotically optimal time complexity of key inserts, key deletes, and key-range scans on any version. The structural consistency and balance of the MVBT is guaranteed by short-duration latching of pages, redo-only logging of structure modifications (version splits, key splits and page merges), and redo-undo logging of key insertions and deletions. The redo pass of our ARIES-based restart-recovery algorithm always produces a structurally consistent and balanced MVBT on which any undo action by a backward-rolling updating transaction can be performed logically if a physical undo is not possible. The standard steal-and-no-force buffering policy is assumed.

REFERENCES

• 1: Bruno Becker , Stephan Gschwind , Thomas Ohler , Bernhard Seeger , Peter Widmayer, An asymptotically optimal multiversion B-tree, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.264-275, December 1996 [doi>10.1007/s007780050028]
• 2: Hal Berenson , Phil Bernstein , Jim Gray , Jim Melton , Elizabeth O'Neil , Patrick O'Neil, A critique of ANSI SQL isolation levels, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.1-10, May 22-25, 1995, San Jose, California, United States
• 3: Malcolm C Easton, Key-sequence data sets on indelible storage, IBM Journal of Research and Development, v.30 n.3, p.230-241, May 1986
• 4: Alan Fekete , Dimitrios Liarokapis , Elizabeth O'Neil , Patrick O'Neil , Dennis Shasha, Making snapshot isolation serializable, ACM Transactions on Database Systems (TODS), v.30 n.2, p.492-528, June 2005 [doi>10.1145/1071610.1071615]
• 5: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 6: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 7: Ibrahim Jaluta , Seppo Sippu , Eljas Soisalon-Soininen, Concurrency control and recovery for balanced B-link trees, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.2, p.257-277, April 2005 [doi>10.1007/s00778-004-0140-6]
• 8: Ibrahim Jaluta , Seppo Sippu , Eljas Soisalon-Soininen, B-tree concurrency control and recovery in page-server database systems, ACM Transactions on Database Systems (TODS), v.31 n.1, p.82-132, March 2006 [doi>10.1145/1132863.1132866]
• 9: Khaled Jouini , Geneviève Jomier, Indexing multiversion databases, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321574]
• 10: George Kollios , Vassilis J. Tsotras, Hashing Methods for Temporal Data, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.902-919, July 2002 [doi>10.1109/TKDE.2002.1019221]
• 11: David Lomet , Roger Barga , Mohamed F. Mokbel , German Shegalov , Rui Wang , Yunyue Zhu, Immortal DB: transaction time support for SQL server, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066295]
• 12: David Lomet , Roger Barga , Mohamed F. Mokbel , German Shegalov, Transaction Time Support Inside a Database Engine, Proceedings of the 22nd International Conference on Data Engineering, p.35, April 03-07, 2006 [doi>10.1109/ICDE.2006.162]
• 13: David Lomet , Betty Salzberg, Access methods for multiversion data, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.315-324, June 1989, Portland, Oregon, United States
• 14: C. Mohan , Don Haderle , Bruce Lindsay , Hamid Pirahesh , Peter Schwarz, ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging, ACM Transactions on Database Systems (TODS), v.17 n.1, p.94-162, March 1992 [doi>10.1145/128765.128770]
• 15: 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
• 16: Gultekin Ozsoyoglu , Richard Thomas Snodgrass, Temporal and Real-Time Databases: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.7 n.4, p.513-532, August 1995 [doi>10.1109/69.404027]
• 17: Kerttu Pollari-Malmi , Jarmo Ruuth , Eljas Soisalon-Soininen, Concurrency Control for B-Trees with Differential Indices, Proceedings of the 2000 International Symposium on Database Engineering & Applications, p.287-295, September 18-20, 2000
• 18: B. Salzberg, L. Jiang, D. Lomet, M. Barrena, J. Shan, and E. Kanoulas. A framework for access methods for versioned data. In Proceedings of the 9th International Conference on Extending Database Technology, pages 730--747, 2004.
• 19: Betty Salzberg , Vassilis J. Tsotras, Comparison of access methods for time-evolving data, ACM Computing Surveys (CSUR), v.31 n.2, p.158-221, June 1999 [doi>10.1145/319806.319816]