Transaction Time Indexing with Version Compression

David Lomet, Mingsheng Hong, Rimma Nehme, and Rui Zhang


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.


Publication typeInproceedings
Published inVLDB Conference
PublisherVery Large Data Bases Endowment Inc.
> Publications > Transaction Time Indexing with Version Compression