DEPA-Delta Shifting and Distribution Shaping for Efficient Adaptive Indexing

In dynamic environments, such as exploratory data analysis where the query and data workload changes frequently, the absence of prior knowledge about the workload poses a significant challenge in defining appropriate indices for a database. Frequent changes in the workload demand prompt response times for queries to increase user satisfaction, making it crucial to adapt the index dynamically. To address these challenges, adaptive indexing has emerged as a promising solution. The fundamental idea is to build the index incrementally during query processing. However, state-of-the-art adaptive indexing approaches under-utilize hardware resources, while progressive indexes sacrifice adaptivity to the workload. In this paper, we propose two novel techniques, namely Delta Shift Partitioning and Distribution Shaping Partitioning, that achieve tenfold better performance than the competitors without compromising the adaptivity of the index. Through low-level tuning and efficient hardware implementation, our proposed methods offer an optimal and adaptive solution to address the challenges of real-time query processing in dynamic workloads.