2019/10/17 by Christian Riegger, Tobias Vinçon, Tobias Vincon +6
Computer Science · #Advanced Data Storage Technologies #Algorithms and Data Compression #Databases (cs.DB) #FOS: Computer and information sciences #Parallel Computing and Optimization Techniques #cs.DB
paper · pdf · doi:10.48550/arxiv.1910.08023
arxiv created 2019/10/17 · openalex publication_date 2019/10/17 · arxiv updated 2019/10/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Modern mixed (HTAP) workloads execute fast update-transactions and long-running analytical queries on the same dataset and system. In multi-version (MVCC) systems, such workloads result in many short-lived versions and long version-chains as well as in increased and frequent maintenance overhead. Consequently, the index pressure increases significantly. Firstly, the frequent modifications cause frequent creation of new versions, yielding a surge in index maintenance overhead. Secondly and more importantly, index-scans incur extra I/O overhead to determine, which of the resulting tuple-versions are visible to the executing transaction (visibility-check) as current designs only store version/timestamp information in the base table -- not in the index. Such index-only visibility-check is critical for HTAP workloads on large datasets. In this paper we propose the Multi-Version Partitioned B-Tree (MV-PBT) as a version-aware index structure, supporting index-only visibility checks and flash-friendly I/O patterns. The experimental evaluation indicates a 2x improvement for analytical queries and 15% higher transactional throughput under HTAP workloads (CH-Benchmark). MV-PBT offers 40% higher transactional throughput compared to WiredTiger's LSM-Tree implementation under YCSB.