Rethinking Learned Index and LSM-tree Integration

vldb26-2982 · Regular Research · Guangxun Zhao, Yongjie Zhu, Charles Jaranilla, Seehwan Yoo, Jongmoo Choi
Abstract

Learned indexes improve data access efficiency by accelerating lookups and reducing memory usage, but integrating them with write-optimized Log-Structured Merge-trees (LSM-trees) remains challenging due to frequent compactions and intensive updates. We analyze this integration and identify two key mismatches. First, learned indexes reshape the conventional SSTable sizing trade-off in LSM-trees. In conventional LSM-trees, SSTable size drives the read/write trade-off, and this trade-off is amplified by level asymmetry between write-intensive upper levels and read-intensive deeper levels. Learned indexes make lookups less sensitive to SSTable size, thereby changing the traditional trade-off. Second, learned indexes typically employ fixed error bounds that cannot adapt to key distribution shifts caused by LSM-tree compactions, resulting in inefficient index construction and degraded lookup performance across different levels. Wild Turkey addresses these mismatches with two complementary mechanisms. Level-Aware Compaction (LAC) introduces a level-specific SSTable sizing strategy that aligns compaction granularity with the distinct read/write characteristics of each level. Building on LAC, Wild-Learning is a reinforcement learning (RL)-based controller that adaptively tunes both the LAC-degree and the per-SSTable error bound in response to evolving data distributions and system conditions. Together, these mechanisms co-tune compaction behavior and learned index construction to balance read and write performance under changing workloads. On SOSD datasets and YCSB workloads, Wild Turkey achieves up to 2.01x higher write throughput, 1.52x higher read throughput, 36\% less write stall time, and 78.4\% fewer compactions compared to state-of-the-art LSM-tree and learned index integration.

Assigned reviewers

No reviewers assigned yet.

Candidates from the panel ranked by taxonomy affinity

#ReviewerMatchLoadWhy