Concurrent updating transactions on versioned data

ABSTRACT

Modern database applications increasingly often require access to historical versions of the database. Storing such multiversion data in a single-version B⁺ -tree database index is inefficient, especially for key-range queries. In this article, we present an index structure called the concurrent multiversion B⁺ -tree (CMVBT) for efficiently storing and querying multiversion data.

The CMVBT structure uses an asymptotically optimal transactional multiversion B⁺ -tree (TMVBT) index as the main data storage. and a separate B⁺ -tree index called the versioned B⁺ -tree (VBT) to hold the updates of active transactions. The updates of committed transactions are moved, one transaction at a time, from the VBT into the TMVBT. This organization of two separate index structures allows us to maintain the asymptotic optimality guarantees of the TMVBT even in the presence of concurrent updating transactions.

We provide concurrent algorithms for updating and reading the CMVBT structure. Our CMVBT algorithms can be used with the standard snapshot isolation concurrency-control and ARIES-based recovery algorithms to allow multiple read-only and updating transactions, to operate concurrently on the structure. Transaction rollback is also supported for all updating transactions, either entirely or up to a preset savepoint.

REFERENCES

• 1: R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1(3):173--189, 1972.
• 2: R. Bayer and M. Schkolnick. Concurrency of operations on B-trees. Acta Informatica, 9(1):1--21, 1977.
• 3: B. Becker, S. Gschwind, T. Ohler, B. Seeger, and P. Widmayer. An asymptotically optimal multiversion B-tree. The VLDB Journal---The International Journal on Very Large Data Bases, 5(4):264--275, 1996.
• 4: H. Berenson, P. Bernstein, J. Gray, J. Melton, E. O'Neil, and P. O'Neil. A critique of ANSI SQL isolation levels. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 1--10. ACM New York, NY, USA, 1995.
• 5: D. Comer. Ubiquitous B-tree. ACM Computing Surveys, 11(2):121--137, 1979.
• 6: J. Gray and A. Reuter. Transaction processing: concepts and techniques. Morgan Kaufmann, 1993.
• 7: T. Haapasalo, I. Jaluta, B. Seeger, S. Sippu, and E. Soisalon-Soininen. Transactions on the multiversion B⁺ -tree. In Proceedings of the 12th International Conference on Extending Database Technology, pages 1064--1075, 2009.
• 8: T. Haapasalo, I. Jaluta, S. Sippu, and E. Soisalon-Soininen. Concurrency control and recovery for multiversion database structures. In Proceedings of the 2nd PhD Workshop on Information and Knowledge Management, pages 73--80, 2008.
• 9: I. Jaluta, S. Sippu, and E. Soisalon-Soininen. Concurrency control and recovery for balanced B-link trees. The VLDB Journal---The International Journal on Very Large Data Bases, 14(2):257--277, 2005.
• 10: I. Jaluta, S. Sippu, and E. Soisalon-Soininen. B-tree concurrency control and recovery in page-server database systems. ACM Transactions on Database Systems, 31(1):82--132, Mar 2006.
• 11: G. Kollios and V. Tsotras. Hashing methods for temporal data. IEEE Transactions on Knowledge and Data Engineering, 14(4):902--919, 2002.
• 12: S. Lang, J. Driscoll, and J. Jou. Batch insertion for tree structured file organizations---improving differential database representation. Information Systems, 11(2):167--175, 1986.
• 13: P. Lehman and B. Yao. Efficient locking for concurrent operations on B-trees. ACM Transactions on Database Systems, 6(4):650--670, Dec 1981.
• 14: D. Lomet, R. Barga, M. Mokbel, G. Shegalov, R. Wang, and Y. Zhu. Immortal DB: transaction time support for SQL server. In Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, pages 939--941, 2005.
• 15: D. Lomet, R. Barga, M. Mokbel, G. Shegalov, R. Wang, and Y. Zhu. Transaction time support inside a database engine. In Proceedings of the 22nd International Conference on Data Engineering, pages 35--46, 2006.
• 16: D. Lomet and B. Salzberg. Access methods for multiversion data. In Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, pages 315--324, 1989.
• 17: D. Lomet and B. Salzberg. The performance of a multiversion access method. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 353--363. ACM New York, NY, USA, 1990.
• 18: C. Mohan. ARIES/IM: an efficient and high concurrency index management method using write-ahead logging. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 371--380. ACM Press New York, NY, USA, 1992.
• 19: C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh, and P. Schwarz. ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging. ACM Transactions on Database Systems, 17(1):94--162, 1992.
• 20: C. Mohan and I. Narang. Algorithms for creating indexes for very large tables without quiescing updates. In Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, pages 361--370. ACM Press New York, NY, USA, 1992.
• 21: Oracle. Oracle Database Concepts 11g Release 1 (11.1). http://download.oracle.com/docs/cd/B28359_01/server.111/b28318/toc.htm, Apr 2009.
• 22: K. Pollari-Malmi, J. Ruuth, and E. Soisalon-Soininen. Concurrency control for B-trees with differential indices. In Proceedings of the International Database Engineering and Applications Symposium, pages 287--296, 2000.
• 23: P. Varman and R. Verma. An efficient multiversion access structure. IEEE Transactions on Knowledge and Data Engineering, 9(3):391--409, 1997.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Recovery and restart
      H.2.4 Systems
          Subjects: Concurrency; Transaction processing

General Terms:
Algorithms, Design

Keywords:
concurrency control, database indexing methods, recovery, temporal databases