Concurrency Control for Adaptive Indexing

Goetz Graefe, Felix Halim, Stratos Idreos, Harumi A. Kuno, Stefan ManegoldarXiv 2012 · arXiv

Introduction

Modern database systems face a fundamental paradox: how to allow "read-only" queries to reorganize data on the fly without creating a massive traffic jam of locks and latches. The VLDB 2012 paper, "Concurrency Control for Adaptive Indexing," addresses this by exploring the intersection of adaptive indexing and multi-user concurrency.

The Concurrency Paradox in Adaptive Indexing

In traditional database environments, indexing is a static, "stop-the-world" event managed by a database administrator. Once built, queries simply consume the index. Adaptive indexing (such as "database cracking") shifts this paradigm by building and refining indexes incrementally as a side effect of query processing.

However, this creates a significant challenge in multi-user environments. If every query attempts to reorganize data to optimize its own performance, a logically read-only query becomes a physical write operation. Without specialized concurrency control, the overhead of managing these concurrent "writes" using traditional heavy-duty transactional locks could negate the performance gains of the index itself.

Proposed Methods

The authors propose a concurrency control framework tailored for the opportunistic nature of adaptive indexing. Their approach is built on several key pillars:

  1. Separation of Content vs. Structure: The system distinguishes between logical data content and physical index structure. Since adaptive indexing only modifies the structure, it avoids the need for heavy transactional locks.
  2. Latches over Locks: Instead of long-term transactional locks, the system uses short-term, in-memory latches.
  3. Optionality and Early Termination: Index optimization is treated as optional. If a query cannot acquire a latch, it simply skips the optimization and performs a standard scan. This ensures the system never deadlocks for an optional update.
  4. Piece-wise Latching: Rather than locking an entire column, the system latches only the specific "pieces" or key ranges currently being "cracked" or merged.
The incremental partitioning (cracking) process where data is refined based on query predicates.

Key Insights and Results

The most significant insight is the concept of "Self-Healing" Lock Granularity. As an adaptive index matures, it breaks data into smaller, more refined pieces. Consequently, the latches required for optimization become finer-grained. Over time, the probability of two queries contending for the same piece decreases, naturally improving concurrency.

Comparison of traditional and adaptive indexing, showing the reduction in concurrency conflicts as the index matures.

Experimental evaluations using MonetDB and synthetic workloads of 100 million tuples revealed:

  • Negligible Overhead: Administrative overhead for latch management is less than 1% of total execution time.
  • Linear Scalability: Throughput scales almost linearly with the number of concurrent clients, limited primarily by hardware CPU cores.
  • Adaptive Conflict Reduction: Experimental data confirmed that the number of concurrency conflicts drops sharply as the workload progresses and the index becomes more refined.

Conclusion and Future Work

The paper demonstrates that lightweight, opportunistic concurrency control allows adaptive indexing to thrive in multi-user environments. By treating index reorganization as separate "system transactions," the system can commit improvements even if a user's main transaction rolls back.

Future research directions include exploring "active" strategies where the system proactively refines indexes during low contention, and developing algorithms that dynamically switch between different adaptive indexing methods based on real-time concurrency patterns.

Summary updated

BibTeX
@misc{graefe2012concurrency,
  author = {Goetz Graefe and Felix Halim and Stratos Idreos and Harumi A. Kuno and Stefan Manegold},
  title = {{Concurrency Control for Adaptive Indexing}},
  year = {2012},
  eprint = {1203.6405},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1203.6405},
}

Loading related content...

Figure