Workload-Aware Learned Tree Index Optimizes Database Query Throughput by Prioritizing Hot Keys

Researchers Hongtao Sun, Chen Jason Zhang, Xinyu Zhang, Peng Cheng, Libin Zheng, Jian Yin, and Lei Chen have introduced WALDEN, an acronym for Workload-Aware Learned Tree Index, designed to boost database query performance by prioritizing frequently accessed data records. In contemporary database management systems, learned indexes treat indexing structures as machine learning models, mapping search keys directly to their physical storage positions. However, conventional learned indexes concentrate almost entirely on improving model regression accuracy, treating all keys as equally significant. In practical database deployments, query workloads exhibit substantial skew, meaning access frequencies vary drastically across individual keys. To exploit this operational reality, WALDEN incorporates historical query access patterns into the tree construction process, assigning weights to keys and placing high-frequency entries into shallower tree levels. Evaluations on synthetic workloads across real benchmark datasets demonstrate that WALDEN outperforms state-of-the-art learned indexes, delivering average throughput improvements ranging from 9.7 percent to 500 percent.

The fundamental motivation behind learned indexing stems from memory and latency overheads associated with classic tree structures like the ubiquitous B+tree. Widely utilized across mainstream database platforms including Oracle, MySQL, and PostgreSQL, the B+tree faces operational bottlenecks as dataset sizes expand exponentially. Prior research indicates that B+tree structures can consume up to 55 percent of total system memory during standard online transaction processing workloads, such as TPC-C, in state-of-the-art in-memory database management systems. In response, earlier pioneering work by Kraska and colleagues introduced the learned index concept, using machine learning models to approximate cumulative key distributions and predict storage offsets directly. Subsequent indexing architectures, including PGM, ALEX, LIPP, NFL, DILI, and SALI, introduced diverse regression methods, piecewise error bounds, and distribution transforms. Yet, despite their varying mechanisms, these models remain workload-blind, uniformly optimizing key access time across all entries rather than expediting lookups for heavily accessed keys.

Real-world query traces confirm that access frequencies are rarely uniform across the key space. For example, check-in data from the Gowalla social network reveals that location latitude coordinates experience prominent workload clustering between latitudes 25 to 50 and 50 to 75, while large numbers of neighboring coordinates receive zero user queries. The investigators emphasize that local key density does not correlate with query frequency; dense spatial regions can exhibit low query activity, while sparse regions may experience heavy demand. To demonstrate how query priority directly affects index efficiency, the researchers examine an illustrative scenario involving fifteen queries distributed across six keys, where keys A through E are queried once and key F is queried ten times. In a workload-blind tree index where all keys reside at the second level, traversing the tree incurs an aggregate traversal cost of 30. Moving the heavily accessed key F one level higher reduces total traversal cost to 22, underscoring the latency benefits of shallow placement.

WALDEN builds directly upon the design of LIPP, an updatable learned tree index whose theoretical strengths and empirical performance have been validated across previous comparative studies. LIPP constructs a multi-level hierarchical structure consisting of segments, where each segment contains an array of nodes, a bit vector tracking allocation status, and a monotonically increasing linear model that calculates exact key positions. Segment nodes are partitioned into empty nodes representing unallocated memory, data nodes storing an individual key and payload, and pointer nodes that route queries toward lower segments whenever key collisions occur. Unlike alternative learned index structures such as PGM or ALEX, which necessitate exhaustive secondary scans or exponential searches around model predictions, LIPP predicts the precise node location without extra search overhead. LIPP determines its linear model parameters—specifically slope A and intercept b—by minimizing a metric termed the conflict degree, defined as the maximum number of keys mapped to any single position in a node array of length L.

To transition from uniform assumptions to a workload-aware framework, WALDEN models incoming queries as a formal workload recording the access frequency of each key. Because raw query tallies can introduce extreme frequency spikes for popular records while assigning zero values to untouched keys, using raw counts directly would distort index modeling. WALDEN addresses this challenge by training a probabilistic distribution model, specifically a Gaussian mixture model, to fit the normalized query access ratios across all keys. Each key is subsequently assigned a positive numerical weight defined as one plus the product of the fitted probability and an adjustable scaling parameter lambda. The addition of the constant one acts as a smoothing factor, ensuring that infrequently queried keys or keys with limited training observations do not collapse to zero weight. This statistical formulation allows WALDEN to assign smooth priority metrics to keys, establishing a mathematically sound basis for optimizing internal tree placement without neglecting cold records.

Building upon this weighting scheme, the researchers developed the Weighted Minimum Collision Degree algorithm, or WMCD, which generalizes LIPP’s original model specification method to accommodate weighted keys. In WALDEN, the weighted maximum collision degree, denoted as C, represents the maximum aggregate weight of all keys mapped to a single node slot within a segment. By sorting keys in ascending order, the authors established upper and lower bounding constraints on model slope A and intercept b to prevent accumulated weights at border and interior positions from exceeding C. The optimization problem is thereby transformed into a verification condition evaluated across all keys. Rather than executing a computationally demanding brute-force search requiring quadratic time complexity, the WMCD algorithm starts with C set to one and traverses keys linearly, incrementing C and adjusting bounding parameters only when an inequality check fails. This single-pass verification design reduces overall computational time complexity to O(cN) while maintaining a minimal space complexity of O(1).

To handle dynamic database modifications and prevent structural degradation caused by frequent insertions, WALDEN incorporates specialized on-the-fly adjustment mechanisms. Insertions are executed through an in-place lookup process: if the target position contains an empty node, it transforms into a data node; if it already contains data, a new segment is generated, converting the original slot into a pointer node. Because repeated insertions can undermine tree balance, WALDEN evaluates five distinct adjustment criteria. Alongside three baseline rules derived from LIPP that monitor raw insertion counts, conflict ratios, and segment size bounds, WALDEN introduces two workload-aware rules. Rule 4 triggers an adjustment when the cumulative weight of inserted keys reaches at least beta times the segment’s baseline weight, set by default to 3. Rule 5 initiates adjustment when the ratio of conflicted key weights to inserted key weights exceeds an alpha threshold of 0.1. Once triggered, the RebuildSubtree procedure collects indexed keys, allocates extra empty nodes to absorb future writes, and recalculates optimal model parameters via WMCD.

Query workloads in production databases frequently drift over time, which can compromise the efficiency of workload-aware indexes if historical key weights diverge from current usage patterns. If keys that were rarely queried during index construction suddenly become popular, their placement in deep tree levels can cause severe latency penalties. To mitigate this degradation, WALDEN introduces an asynchronous background monitoring algorithm that evaluates workload distributions every tau operations, configured in experiments to 10 percent of dataset size. Using sliding windows of length S, set to 6 million queries, the algorithm compares recent queries against historical workload distributions using Kullback-Leibler divergence. When the divergence meets or exceeds one, the system updates its reference distribution through a weighted linear combination. If sustained shifts persist across successive observation windows, triggering a shift mark threshold eta, WALDEN learns a refreshed distribution model and initiates a background tree rebuild via lazy updates modeled after database replication, synchronizing concurrent operations without halting active query processing.

The authors conducted extensive comparative evaluations across five real-world benchmark datasets—LONGLAT, LONGITUDES, GOWALLA, OSM, and BOOK—supplemented by rounded dataset variants that simulate coarse user queries. The benchmarks evaluated read-only, read-heavy, read-write balanced, and write-heavy workloads against leading competitors including B+Tree, ALEX, LIPP, PGM, NFL, SALI, RMI, and Chameleon. In read-only scenarios, WALDEN achieved throughput improvements of up to 490 percent over RMI, 260 percent over PGM, 110 percent over NFL, 290 percent over B+Tree, 18.9 percent over ALEX, 408 percent over SALI, and 9.7 percent over LIPP. Across read-write workloads, WALDEN delivered throughput gains reaching 500 percent over PGM, 150 percent over NFL, 210 percent over B+Tree, 25.9 percent over ALEX, 287 percent over SALI, and 26.1 percent over LIPP. Although write operations incur minor throughput overhead due to node creation and subtree rebuilding, WALDEN maintained consistent advantages across skewed real-world workloads while exhibiting minor fitting challenges only on highly non-uniform datasets lacking duplicate keys, such as unrounded LONGLAT.

Supplementary analyses demonstrated WALDEN’s robust operational behavior across diverse synthetic distributions, including Zipfian and Normal workloads, where it achieved an average 45.1 percent throughput gain over LIPP. In dynamic shift evaluations, WALDEN maintained throughput advantages ranging from 13.1 percent to 78.9 percent over competing models, whereas ablation testing of WALDENnoD, which lacked shift detection, suffered severe throughput declines when distributions changed. Structural measurements indicated that WALDEN’s average tree height remained between 0.94 and 1.09 times that of LIPP, although its maximum tree height expanded to between 1.17 and 2.67 times LIPP in the worst case. While WALDEN incurs slightly higher memory usage from storing key weights and managing deeper pointer paths, its bulk-loading procedure required less than half the time of ALEX, RMI, and NFL. Having released their C++ implementation publicly on GitHub, the authors identified multi-threaded execution via item-level optimistic locking as an important avenue for future research, offering database systems an adaptable architecture that aligns index layout directly with real-world query demand.

Subject of Research: Workload-aware learned tree indexing in database management systems

Article Title: WALDEN: Workload-Aware Learned Tree Index

Article References: Sun, H., Zhang, C. J., Zhang, X., Cheng, P., Zheng, L., Yin, J., & Chen, L. (2026). WALDEN: Workload-Aware Learned Tree Index. Data Science and Engineering, 11(3), 538-559. https://doi.org/10.1007/s41019-025-00332-8

Image Credits: AI Generated

DOI: 10.1007/s41019-025-00332-8

Keywords: learned index, database management, tree index, query workload, data structures, workload awareness, indexing throughput, Gaussian mixture model, WALDEN, Workload-Aware, Learned, Tree