Proceedings of the VLDB Endowment · 2019 · 33 citations · 65 references
ComputingComputer ScienceComputer SystemsData StructuresDatabasesParallel AlgorithmsConcurrency ControlDatabase ManagementParallel Data StructuresParallel DatabasesQuery ProcessingSnapshot ManagementDatabase Management SystemsIndex StructuresIndexesMulti-version Concurrency ControlOlap BenchmarkingParallel Concurrency ControlParallel Database SystemsSnapshot Isolation
Modern data-driven applications require that databases support fast analytical queries while undergoing rapid updates---often referred to as Hybrid Transactional Analytical Processing (HTAP). Achieving fast queries and updates in a database management system (DBMS) is challenging since optimizations to improve analytical queries can cause overhead for updates. One solution is to use snapshot isolation (SI) for multi-version concurrency control (MVCC) to allow readers to make progress regardless of concurrent writers. In this paper, we propose the Parallel Binary Tree (P-Tree) index structure to achieve SI and MVCC for multicore in-memory HTAP DBMSs. At their core, P-Trees are based on pure (immutable) data structures that use path-copying for updates for fast multi-versioning. They support tree nesting to improve OLAP performance while still allowing for efficient updates. The data structure also enables parallel algorithms for bulk operations on indexes and their underlying tables. We evaluate P-Trees on OLTP and OLAP benchmarks, and compare them with state-of-the-art data structures and DBMSs. Our experiments show that P-Trees outperform many concurrent data structures for the YCSB workload, and is 4--9 x faster than existing DBMSs for analytical queries, while also achieving reasonable throughput for simultaneous transactional updates.
65
Bounds on Multiprocessing Timing Anomalies
Ron Graham · SIAM Journal on Applied Mathematics · 1969 · 2.4K citations
A critique of ANSI SQL isolation levels
Hal Berenson, Phil Bernstein, Jim Gray et al. · 1995 · 865 citations · Full text
The Parallel Evaluation of General Arithmetic Expressions
Richard P. Brent · Journal of the ACM · 1974 · 818 citations · Full text