Transaction time indexing with version compression

David B. Lomet, Mingsheng Hong, Rimma V. Nehme, Rui Zhang

TL;DR

This paper introduces Immortal DB, a transaction time database system integrated into Microsoft SQL Server, that achieves high performance for temporal queries by using a novel TSB-tree index and efficient version compression. This work bridges the gap between theoretical temporal database concepts and practical, high-performance RDBMS implementations.

What Problem Does This Paper Address?

Transaction time databases are crucial for applications requiring historical data access (e.g., auditing, legal compliance), but their adoption has been hampered by poor performance, especially for historical queries. Traditional approaches often involve complex layering on top of existing databases or specialized systems that are difficult to integrate. The core challenge is to provide efficient access to both current and historical data within a standard RDBMS framework, preserving existing functionality like concurrency control and recovery, while also optimizing for temporal access patterns.

Methods

The paper details the integration of a Time-Split B+tree (TSB-tree) into the SQL Server storage engine. Unlike standard B+trees, the TSB-tree supports indexing by both key and time. Key novelties include:

  • TSB-tree Indexing: This tree performs both key splits (like a B+tree) and time splits. Time splits are prioritized to ensure good density of records within time ranges for "as of" queries.
  • Version Compression: To reduce storage and improve query performance, versions of data records and index terms are compressed using a backward delta compression scheme. This compression is local to a page, meaning decompression only requires information within that page.
  • Index Term Treatment: Index terms are treated as versioned records themselves, allowing for efficient management of temporal index information.
  • Integration with SQL Server: The TSB-tree is built upon SQL Server's existing B+tree implementation, preserving its concurrency control and recovery mechanisms. This integration allows current queries to largely use existing B+tree code, minimizing performance impact on non-temporal operations.
  • Splitting Policies: The paper discusses strategies for data and index page splitting, including the "WOB-tree split policy," which ensures a minimum storage utilization for any version. A key splitting threshold is introduced to control the trade-off between query performance and storage space.

Datasets

Not discussed in the paper. The authors describe experimental setups using synthetic data generated with specific update/insert ratios and key distributions.

Key Insights and Ideas

  • Integrating Temporal Indexing into RDBMS is Feasible and Beneficial: The paper demonstrates that a specialized temporal index (TSB-tree) can be effectively integrated into a commercial RDBMS (SQL Server) without sacrificing core database functionalities, leading to significant performance gains for temporal queries.
  • Delta Compression is Key for Temporal Data: Exploiting the commonality between adjacent versions of records and index terms through delta compression dramatically reduces storage requirements and improves query performance by reducing the number of pages that need to be accessed.
  • Trade-off Management is Crucial: The paper highlights the inherent trade-off between query performance (especially for "as of" queries) and storage space. The TSB-tree's splitting policies and the key splitting threshold are mechanisms to manage this trade-off.
  • Index Terms as Versioned Entities: Treating index terms as versioned entities, similar to data records, is a clever way to manage the temporal indexing structure efficiently and consistently.

Key Results

  • High Performance: The Immortal DB system, with its TSB-tree and compression, achieves very good performance for temporal queries, approaching that of a conventional unversioned database.
  • Storage Efficiency: Version compression significantly reduces the storage needed for historical data. For example, with a compression ratio of 0.162 (10:1), the Multiversion Total Utilization (MVTU) increased from 0.54 (uncompressed) to 2.86 in experiments.
  • SVCU Analysis: The Single Version Current Utilization (SVCU) analysis and experiments show that the key splitting threshold effectively limits SVCUmax, with minor differences between analytical predictions and experimental results.
  • MVTU Analysis: The analysis for Multiversion Total Utilization (MVTU) closely matches experimental results, demonstrating the effectiveness of compression in improving storage efficiency, especially at higher update rates.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that there's a trade-off between SVCU and MVTU, and optimizing for one might negatively impact the other.
  • While the TSB-tree aims to be close to SQL Server's B+tree performance, some overhead for temporal functionality is unavoidable.
  • The analysis for MVTU is more limited, applying primarily to the end points of the update ratio range.
  • Future Work:
    • Further narrowing the performance gap between transaction time and current time functionality for both updates and range queries.
  • Exploring additional optimization opportunities.
  • Enhancing the utility of Immortal DB, including implementing recovery from bad user transactions and using historical versions for data backup.

Summary updated

BibTeX
@article{lomet2008transaction,
  author = {David B. Lomet and Mingsheng Hong and Rimma V. Nehme and Rui Zhang},
  title = {{Transaction time indexing with version compression}},
  journal = {Proc. VLDB Endow.},
  year = {2008},
  doi = {10.14778/1453856.1453951},
}
Figure