[DB Seminar] Fall 2018: Yihan Sun

Modern query-heavy applications of database systems especially require minimal delays to OLAP queries, as well as allowing the lasted OLTP updates to be visible in time. A popular mechanism for fast response to OLAP queries is to use snapshot isolation (SI) for multi-version concurrency control (MVCC), as it allows readers to make progress regardless of concurrent writers. Many other optimizations for OLAP queries include denormalization, materialization view and table partitioning. However, most existing solutions to these optimizations do not support efficient updates with SI or MVCC, and existing systems with SI and MVCC usually disallow, or can be inefficient to support these optimizations.

Our work proposes solutions for in-memory DBMSs to achieve fast responses to queries while allowing efficient updates. Our solution is based on a purely functional (no side-effect) data structure called J-Tree, with four main techniques: path-copying, tree-nesting, concat-based algorithms and batching. First, instead of version chains used in most previous work, J-Trees use path-copying to create versions. As such, J-Tree suffers from no delay for either read or write transactions and trivially achieves lock-free solutions for atomic updates. Second, J-Tree allows nested tree structures under SI and MVCC, which especially allows optimizations accelerating OLAP queries, such as table partitioning, denormalization and materialization views. Also, J-Tree adopts concat-based algorithms proposed in previous work, which allow efficient implementation of path-copying, as well as bring up parallelism in trees. Lastly, J-Tree achieves serializability by batching concurrent updates and committing them using a single global writer, which avoids write-write conflicts and in many cases, leads to higher throughput for updates.

We evaluated J-Trees on various benchmarks, and compare it with state-of-the-art data structures and DBMSs. Experiments show that J-Trees outperforms many concurrent data structures for OLTP workloads, and is 3-8x faster than existing DBMSs for OLAP workloads. For HTAP workloads, the average overhead in queries from adding one single-threaded update process is within 3%. The queries on J-Trees is still 3-8x faster than existing systems, and the throughput for OLTP transactions is slightly faster than existing systems.