LITune: A New Paradigm in Tuning Learned Indexes

Demo Video of LITune Tuning Process

Abstract

Learned Index Structures (LIS) have significantly advanced data management by leveraging machine learning models to optimize data indexing. However, designing these structures often involves critical trade-offs, making it challenging for both designers and end-users to find an optimal balance tailored to specific workloads and scenarios. While some indexes offer adjustable parameters that demand intensive manual tuning, others rely on fixed configurations based on heuristic auto-tuners or expert knowledge, which may not consistently deliver optimal performance. This paper introduces LITune, a novel framework for end-to-end automatic tuning of Learned Index Structures. LITune employs an adaptive training pipeline equipped with a tailor-made Deep Reinforcement Learning (DRL) approach to ensure stable and efficient tuning. To accommodate long-term dynamics arising from online tuning, we further enhance LITune with an on-the-fly updating mechanism termed the O2 system. These innovations allow LITune to effectively capture state transitions in online tuning scenarios and dynamically adjust to changing data distributions and workloads, marking a significant improvement over other tuning methods. Our experimental results demonstrate that LITune achieves up to a 98% reduction in runtime and a 17-fold increase in throughput compared to default parameter settings given a selected Learned Index instance. These findings highlight LITune's effectiveness and its potential to facilitate broader adoption of LIS in real-world applications.

1. Observation and Motivation of Our Work

The intersection of data management and machine learning has given rise to learned index structures. These indexes integrate machine learning, replacing traditional algorithmic components, to capture data distributions and optimize search times. Notable examples include RMI [1], ALEX [2], and PGM [3], which have become subjects of extensive research.

The effective design of a learned index involves deliberate trade-offs to achieve optimal performance for varying workloads. For instance, ALEX favors combined search and update performance by introducing gaps at the expense of space efficiency [2]. On the other hand, the dynamic PGM Index prioritizes update efficiency over search performance [3]. These design trade-offs lead to more complex structures with configurable parameters. Tuning these parameters is the key to balancing trade-offs that ensure higher performance over traditional indexes.

Beyond the primary parameters, learned indexes like ALEX have more subtle tunable factors that are often overlooked for simplicity. These parameters affect various aspects of the index performance, from operation cost to the structure of the index. Adjusting them in real-world scenarios can lead to substantial performance improvements, though it requires a more complex tuning process.

Figure 1: Combined performance surfaces and speedups. — **Figure 1.** (a) shows the performance surface of a learned index (ALEX) under wild exploration of the parameter space. (b) highlights the optimal performance speedup achieved by LITune compared to default expert-selected parameters. (c) illustrates the continuous tuning performance of our system alongside other out-of-the-box methods under default configurations. (d) compares the tuning stability and costs across methods to reach their respective optimal performance levels.

Selecting the right tuning approach for learned indexes involves navigating a myriad of parameter configurations. In practice, parameterized indexes can exhibit vastly different performance due to parameter choices (see Figure 1(a)). This variability underscores the complexities and potential performance swings when considering the full spectrum of high-dimensional and continuous parameter configurations. Moreover, unlike algorithmic indexes such as B+trees that perform well out of the box, learned indexes are distribution-dependent and typically lack automatic tuning resources. Thus, a high-quality tuner is necessary to identify optimal solutions within a limited budget.

Figure 2: Parameter value distributions and impact scores. — **Figure 2.** Selected parameter value distributions and their impact scores across different workloads when tuning on ALEX. Heatmap colors represent normalized optimal parameter values, while percentages indicate each parameter's individual tuning impact.

By fine-tuning these parameters, we can achieve significant performance improvements. Figure 1(b) emphasizes the substantial performance gains (measured by query runtime speedup) achieved by our tuning system over the SOSD dataset. Moreover, real-world usage often involves dynamic workloads, as illustrated in Figure 1(c), underscoring the need for adaptive tuning. Another challenge is safe tuning. Aggressive parameter exploration can lead to system instability, as shown in Figure 1(d). These observations highlight the necessity of a tailor-made tuning system like LITune rather than relying on out-of-box methods.

Besides, our empirical experiments demonstrate that parameter interactions in learned indexes exhibit complex, workload-dependent relationships with no dominant parameters. As shown in Figure 2, where colors represent normalized parameter values and percentages show impact scores (ratio of individual-parameter to full-parameter tuning improvements), no parameter consistently exerts greater influence, with all impact scores falling between 10-25%. This heterogeneous distribution of parameter values across workloads, coupled with the balanced impact scores, indicates that performance optimization requires holistic parameter tuning rather than focusing on individual parameters. These are key motivations of our proposed system in our paper: LITune.

[1] Kraska et al. “The Case for Learned Index Structures.” SIGMOD, 2018.
[2] Ding et al. “ALEX: An Updatable Adaptive Learned Index.” SIGMOD, 2020.
[3] Ferragina and Vinciguerra. “PGM-Index: Learning-Compliant Hash Indexes.” 2020.

2. LITune System

Unlike existing index tuning works that concentrate on a limited set of observable parameters, our work tackles the more complex challenge of tuning within a vast parameter space where parameters interact in non-independent ways. This complexity demands stable and efficient tuning strategies, especially in online and continuous learning contexts. Since parameter metrics are difficult to capture and do not readily lend themselves to strong heuristics, we focus on capturing stateful transitions and propose tailored end-to-end tuners.

Navigating complex parameter spaces poses significant challenges for traditional search strategies and advanced model-based approaches. Traditional methods (random search, grid search) fall short in large parameter spaces, while out-of-box frameworks (e.g., SMBO) become expensive when workloads shift. LITune offers online, stateful index tuning using deep reinforcement learning (DRL), mitigating the instabilities and aimless explorations of generic tuning methods.

At the core of LITune is a reinforcement learning approach designed to adapt to dynamic workloads beyond traditional cost models. We design a Markov Decision Process (MDP) framework, with the RL agent interacting with the environment to maximize rewards (system performance). LITune operates in two main phases: Training Stage and Online Tuning Stage. In the Training Stage, we generate a pre-trained model that can be deployed and continuously fine-tuned during the Online Tuning Stage. A context-aware RL system is used to prevent early terminations and ensure stable, high-performance configurations.

LITune System Overview — **Figure 3.** *LITune* system diagram illustrating the RL-based training and online tuning pipeline.

3. Key Features and Experimental Results

3.1 Highly Effective and adaptable tuning to various workloads

We showcase LITune's end-to-end performance on various workloads. The following charts highlight its effectiveness compared to default and other baseline tuning methods. LITune demonstrates strong End-to-End (E2E) performance across diverse datasets and workloads, leveraging Meta-RL, the ET-MDP solver, and O2 System components. Figure 4 highlights CARMI's notable optimization headroom, with over 90% runtime reduction (compared to 30-40% for ALEX). Complex datasets like MIX and OSM pose additional challenges, yet LITune consistently excels.

Performance Chart — **Figure 4.** LITune end-to-end runtime performance across multiple workloads.

Performance Table — **Table:** Detailed comparison table of average throughput and latency.

3.2 Safe and Stable Tuning

Exploring parameter spaces can enhance system performance but also introduces risks, especially when parameters significantly impact system reliability. LITune addresses this with a Safe-RL module, ensuring stable exploration and preventing catastrophic failures.

Figure 5 illustrates the benefits of our safety-aware design. Figures 5.(a)--(e) show how four methods explore two critical parameters: kMaxOutOfDomainKeys and kOutOfDomainToleranceFactor, which are crucial under specific configurations (fanoutSelectionMethod = 1, =splittingPolicyMethod = 1, allowSplittingUpwards = True). The red-highlighted Dangerous Zone in subfigure (a) marks parameter regions prone to causing system instabilities and degraded performance, emphasizing the need for a tuner like LITune. subfigure (f) presents the cumulative number of index system failures (e.g., infinite loops, memory issues) during tuning over five trials, highlighting the effectiveness of our safety design.

Figure 6 below compares training stability for LITune with and without Safe-RL. Without Safe-RL, reward signals exhibit high volatility due to system terminations from aggressive parameter exploration. In contrast, LITune with Safe-RL maintains stable improvement and achieves better final performance with fewer failures.

This stability also translates to better end-to-end performance. On average, LITune with Safe-RL achieves significantly lower runtime with much less variance, demonstrating that safer exploration leads to both better and more reliable tuning outcomes.

Safe and Stable Tuning Figure — **Figure 5.** Exploring Parameter Spaces Across Tuning Methods

Conclusion

LITune works effectively across various learned indexes, with impact varying based on parameter complexity and interactions. By approaching tuning as a black-box optimization problem, it identifies optimal configurations before analyzing them. While some redundant parameters are tolerable, maintaining manageable dimensionality is crucial. Currently relying on domain expertise for parameter selection, future work could automate this process. Techniques like checkpointing and configuration caching help reduce retraining costs as workloads change.

Despite its promise, LITune occasionally experiences convergence and stability challenges during training, indicating areas for further research to enhance reliability. Accelerating offline training through methods like parallelization could improve deployment efficiency. Overall, LITune 's innovative combination of Meta-RL and context-aware strategies establishes a new benchmark for improving system efficiency and query performance while maintaining stability through proactive risk management.

Questions & Feedback

Thank you for your feedback! We appreciate your input.

For paper-related inquiries, please contact the corresponding author directly.

BibTeX

@article{wang2025new,
  title={A New Paradigm in Tuning Learned Indexes: A Reinforcement Learning Enhanced Approach},
  author={Wang, Taiyi and Liang, Liang and Yang, Guang and Heinis, Thomas and Yoneki, Eiko},
  journal={arXiv preprint arXiv:2502.05001},
  year={2025}
}

LITune: A New Paradigm in Tuning Learned Indexes - A Reinforcement Learning Enhanced Approach