Just-In-Time Data Structures

Adaptive indexing is a promising alternative to classical of-fline index optimization. Under adaptive indexing, index creation and re-organization take place automatically and incrementally as a side-effect of query execution. Adaptive indexing implementations optimize the index’s structure by progressively rewriting it until it converges to a single ide-alized form such as a sorted array or B-Tree. However, the ideal representation changes over time: An adaptive index that is initially optimal for one workload becomes subopti-mal as the workload’s characteristics change. In this paper we generalize adaptive indexing, adding the ability to adjust the layout and behavior of the index to workload changes even after convergence. This radical just-in-time data structure approach to index construction and maintenance allows for indexes that dynamically adapt to changing workloads. Even with this generality, specializa-tion is still possible. A just-in-time data structure emulates classical adaptive indexing schemes when appropriate, while also being able to adopt a hybrid stance tailored to a specific workload. We show that our approach is feasible and enables indexes that quickly pivot between different behaviors. 1