Transaction Time Indexing with Version Compression

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.