Workload-Aware Contention-Management in Indexes for Hierarchical Data

Abstract

Queries in hierarchical databases (HDBs) often combine predicates referring to values of node properties with path predicates relating to the structure. We call these queries property-and-path (PP) queries. Usually, PP indexes are used to support these types of queries efficiently. In an environment in which HDBs are updated concurrently, we encounter conflicts which may lead to transaction aborts. We identify preventable aborts caused by conflicts in the index, while the operations in the actual database are executed without any problems. These index conflicts are due to the deletion of a path in the index concurrently taking place with an insertion underneath a node on the deleted path. We leverage recent workload information to detect and suspend the deletion of substructures in PP indexes that are likely to conflict with concurrent insertions. However, the suspension of these deletions has a detrimental effect on the query performance, which means this becomes a tradeoff between the number of transaction aborts and the speed of the query evaluation. We implement our approach in Apache Jackrabbit Oak and FOEDUS, experimentally investigate the tradeoff, and show how to balance the effects to maximize the transactional throughput for a given workload.