Boston University
Automatic tuning of log-structured merge trees under uncertain environments
Abstract
dc:description.abstractLog-structured merge (LSM) trees are the foundation of many database systems in multiple domains due to their inherent flexibility by exposing a rich design space to their maintainers. While this flexibility is beneficial, the large design space introduces complexity when seeking the optimal LSM tree configuration for a particular application. Coined as the tuning problem, recent work focuses on tuning database instances for an expected workload, assuming that future workloads are similar. However, these approaches often recommend hyper-optimized configurations that exhibit performance cliffs as workloads evolve. Additionally, these methods are often expensive, requiring multiple database executions for testing, and therefore struggle to scale when tuning multiple database instances across a diverse set of applications. In this thesis, we propose augmenting the tuning problem to consider uncertainty and provide machine learning techniques to recommend tunings at scale. We first address uncertainty by introducing a robust LSM tuning paradigm called ENDURE. In this setting, we assume the expected input workload may not exactly match the workload the database experiences on deployment; rather, the executed workload may be close to the initial assumption. Therefore, ENDURE provides a tuning that maximizes the worst-case throughput over a neighborhood around the expected workload. To address the scalability problem, we introduce AXE, a learned task decomposition approach for tuning LSM trees, which splits the problem into two subtasks: one to model the relationship between workload-configuration pairs and performance, and the other to navigate the cost surface to recommend optimal tunings. We show that our paradigm is a more efficient method for identifying near-optimal configurations and scales to more tuning knobs in the harder robust tuning problem. Our method allows designers to either learn from prior work on analytical models or from data traces for new, unseen databases.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy
- Level thesis:degree_level
- doctoral
- Discipline thesis:degree_discipline
- Computer Science
- Grantor
- Boston University
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Huynh, Andy
- Advisor dc:contributor.advisor
-
- Athanassoulis, Manos
- ORCID dc:identifier.orcid
Subjects
dc:subject × 6Rights
dc:rights- Statement dc:rights
-
- Attribution-ShareAlike 4.0 International
- Licence dc:rights.uri
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/2144/53740