Abstract
Immortal DB is a transaction time database system designed to enable high performance for temporal applications. It is built into a commercial database engine, Microsoft SQL Server. This paper describes how we integrated a temporal indexing technique, the TSB-tree, into Immortal DB to serve as the core access method. The TSB-tree provides high performance access and update for both current and historical data. A main challenge was integrating TSB-tree functionality while preserving original B+tree functionality, including concurrency control and recovery. We discuss the overall architecture, including our unique treatment of index terms, and practical issues such as uncommitted data and log management. Performance is a primary concern. To increase performance, versions are locally delta compressed, exploiting the commonality between adjacent versions of the same record. This technique is also applied to index terms in index pages. There is a tradeoff between query performance and storage space. We discuss optimizing performance regarding this tradeoff throughout the paper. The result of our efforts is a high-performance transaction time database system built into an RDBMS engine, which has not been achieved before. We include a thorough experimental study and analysis that confirms the very good performance that it achieves.
- T. Abdessalem and G. Jomier: VQL: A Query Language for Multiversion Databases. International Workshop on Database Programming Languages, 160--179, 1998. Google ScholarDigital Library
- C.-H. Ang and K.-P. Tan: The Interval B+tree. Information Processing Letters, 53, 2, 85--89, 1995. Google ScholarDigital Library
- G. Arumugam and M. Thangaraj: An efficient multiversion access control in a Temporal Object Oriented Database. Journal of Object Technology. 2006.Google Scholar
- aTempo: aTempo. http://www.atempo.com/Google Scholar
- B. Becker, S. Gschwind, T. Ohler, B. Seeger, and P. Widmayer: An Asymptotically Optimal Multiversion B+tree. VLDB J. 5, 4, 264--275, 1996. Google ScholarDigital Library
- H. Berenson, P. Bernstein, J. Gray, J. Melton, E. O'Neil, and P. O'Neil: A Critique of ANSI SQL Isolation Levels. SIGMOD, 1--10. 1995. Google ScholarDigital Library
- P. Bernstein, V. Hadzilacos, and N. Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley, 1987. Google ScholarDigital Library
- A. Björnerstedt and C. Hultén: Version control in an Object-oriented Architecture. Object-Oriented Concepts, Databases, and Applications, 451--485, 1989. Google ScholarDigital Library
- T. Bozkaya and M. Ozsoyoglu: Indexing Valid Time Intervals. DEXA,. 541--550, 1998. Google ScholarDigital Library
- S. Chien, V. Tsotras, C. Zaniolo, and D. Zhang: Efficient Complex Query Support for Multiversion XML Documents. EDBT, 161--178, 2002. Google ScholarDigital Library
- J. Clifford, C. Dyreson, T. Isakowitz, C. Jensen, R. Snodgrass: On the Semantics of "Now" in Databases, ACM TODS 22, 2, 171--214, 1997. Google ScholarDigital Library
- C. Dyreson: Temporal Coalescing with Now Granularity, and Incomplete Information. SIGMOD 169--180, 2003. Google ScholarDigital Library
- M. Easton: Key-Sequence Data Sets on Inedible Storage. IBM J. R & D 30, 3, 230--241, 1986. Google ScholarDigital Library
- R. Elmasri, G. Wun, and V. Kouramajian: The Time Index and the Monotonic B+ tree. In {42} Chapter 18, 433--456, 1993.Google Scholar
- S. Gukal, E. Omiecinski, and U. Ramachandran: An Efficient Transient Versioning Method. British National Conference on Databases. 155--171, 1995. Google ScholarDigital Library
- H. Gunadhi and A. Segev: Efficient Indexing Methods for Temporal Relations, IEEE TKDE 5, 3, 496--509, 1993. Google ScholarDigital Library
- A. Guttman: R-trees: a dynamic index structure for spatial searching, SIGMOD, 47--57, 1984. Google ScholarDigital Library
- M. Hadjieleftheriou, G. Kollios, V. Tsotras, and D. Gunopulos: Efficient Indexing of Spatiotemporal Objects. EDBT, 251--268, 2002. Google ScholarDigital Library
- L. Hobbs, K. England. Rdb: A Comprehensive Guide. Digital Press, 1995. Google ScholarDigital Library
- IBM: IBM Data Propagator. http://www306.ibm.com/software/data/integration/replicationGoogle Scholar
- C. Jensen and R. Snodgrass: Temporal Data Management. IEEE TKDE, 11, 1, 36--44, 1999. Google ScholarDigital Library
- C. Jensen and D. Lomet: Transaction Timestamping in (Temporal) Databases. VLDB, 441--450, 2001. Google ScholarDigital Library
- K. Jouini, and G. Jomier: Indexing multiversion databases. CIKM, 915--918, 2007. Google ScholarDigital Library
- N. Kline: An Update of the Temporal Database Bibliography, SIGMOD Record, 22, 4, 66--80, 1993. Google ScholarDigital Library
- V. Kouramajian et al: The Time Index+: An Incremental Access Structure for Temporal Databases. CKIM, 296--303, 1994 Google ScholarDigital Library
- D. Lomet, R. Barga, M. Mokbel, G. Shegalov, R. Wang, and Y. Zhu: Immortal DB: Transaction Time Support for Sql Server. SIGMOD, 939--941, 2005. Google ScholarDigital Library
- D. Lomet, R. Barga, M. Mokbel, G. Shegalov, R. Wang, and Y. Zhu: Transaction Time Support Inside a Database Engine. ICDE, 35, 2006. Google ScholarDigital Library
- D. Lomet and B. Salzberg: Access Methods for Multiversion Data. SIGMOD, 315--324, 1989. Google ScholarDigital Library
- D. Lomet and B. Salzberg: The Performance of a Multiversion Access Method. SIGMOD, 353--363, 1990. Google ScholarDigital Library
- D. Lomet and B. Salzberg: Exploiting A History Database for Backup. VLDB, 380--390, 1993. Google ScholarDigital Library
- D. Lomet, R. Snodgrass, and C. Jensen: Using the Lock Manager to Choose Timestamps. IDEAS, 357--368, 2005. Google ScholarDigital Library
- D. Lomet, Z. Vagena, and R. Barga: Recovery from "Bad" User Transactions. SIGMOD, 337--346, 2006. Google ScholarDigital Library
- Lumigent: Lumigent Log Explorer. http://www.ssw.com.au/ssw/LogExplorer/Google Scholar
- Oracle: Oracle Flashback Technology. http//www.oracle.com/technology/deploy/availability/htdocs/ Flasflahback_Overview.htm, 2005Google Scholar
- G. Ozsoyoglu and R. Snodgrass: Temporal and Real-Time Databases: A Survey. IEEE TKDE, 7, 4, 513--532, 1995. Google ScholarDigital Library
- C. Plattner, A. Wapf, and G. Alonso: Searching in Time. SIGMOD, 754--756, 2006. Google ScholarDigital Library
- B. Salzberg and V. Tsotras: Comparison of access methods for time-evolving data. ACM Comput. Surv. 31, 2, 158--221, 1999. Google ScholarDigital Library
- M. Sao: Bibliography on Temporal Databases. SIGMOD Record, 20, 1, 14--23, 1991. Google ScholarDigital Library
- H. Shen, B-C Ooi, and H. Lu: The TP-Index: A Dynamic and Efficient Indexing Mechanism for Temporal Databases. ICDE, 274--281, 1994 Google ScholarDigital Library
- SQL Server: Inside Microsoft SQL Server 2005: The Storage Engine, MS Press, 2005.Google Scholar
- M. Stonebraker. The Design of the POSTGRES Storage System. VLDB, 289--300, 1987. Google ScholarDigital Library
- U. Tansel, J. Clifford, S. Gadia, A. Segev, and R. Snodgrass: Temporal Databases: Theory, Design, and Implementation. Benjamin/Cummings, 1993. Google ScholarDigital Library
- K. Torp, R. Snodgrass, C. Jensen. Effective Timestamping in Databases. VLDB J., 8, 4, 267--288, 2000. Google ScholarDigital Library
- V. Tsotras and A. Kumar: Temporal Database Bibliography Update. SIGMOD Record, 25, 1, 41--51, 1996.Google ScholarDigital Library
- V. Tsotras and N. Kangelaris. The Snapshot Index, An I/O Optimal Access Method for Timeslice Queries. Information Systems, 3, 20, pp. 237--260, 1995. Google ScholarDigital Library
- R. Wrembel and T. Morzy: Managing and Querying Versions of Multiversion Data Warehouse. EDBT, 1121--1124, 2006. Google ScholarDigital Library
Index Terms
- Transaction time indexing with version compression
Recommendations
Compression and Indexing Based on BWT: A Survey
WISA '13: Proceedings of the 2013 10th Web Information System and Application ConferenceBurrows-Wheeler Transform (BWT) is a new data transform method, firstly introduced by Burrows and Wheeler in 1994 and used in a lossless data compression algorithm. In the original version of data compression algorithm based on BWT, Burrows and Wheeler ...
Improving Transaction-Time DBMS Performance and Functionality
ICDE '09: Proceedings of the 2009 IEEE International Conference on Data EngineeringImmortal DB is a transaction time database system that is built into a commercial database system rather than being layered on top. This enables it to have performance that is very close to the performance of an unversioned current time database system. ...
Multi-version indexing and modern hardware technologies: a survey of present indexing approaches
iiWAS '17: Proceedings of the 19th International Conference on Information Integration and Web-based Applications & ServicesCharacteristics of modern computing and storage technologies fundamentally differ from traditional hardware. There is a need to optimally leverage their performance, endurance and energy consumption characteristics. Therefore, existing architectures and ...
Comments