PaperlayerView exact revision on arXiv

Source-linked AI summary

Benchmarking Learned Indexes

Ryan Marcus, Andreas Kipf, Alexander van Renen, Mihail Stoian, Sanchit Misra, Alfons Kemper, Thomas Neumann, Tim Kraska

arXiv:2006.12804v2cs.DB

TL;DR

Learned indexes lacked fair comparisons because implementations, datasets, and standardized benchmarks were limited. The paper addresses this with an open benchmark of tuned learned and traditional structures on real-world read-only in-memory workloads, finding learned structures broadly strong across tested conditions.

  • Problem

    Prior evaluations faced limited open implementations, inadequate datasets, and no standardized benchmark for fair comparisons of learned indexes.

  • Method

    The paper provides an open-source RMI implementation, real-world datasets and workloads, and a benchmark comparing tuned learned and traditional index structures.

  • Results

    Learned structures showed Pareto-dominant performance/size behavior across tested read-only in-memory dense-array settings, with cache misses the largest explanatory factor.

  • Takeaways & Limitations

    The benchmark supports evaluating learned indexes against strong baselines across dataset sizes, key sizes, caching conditions, memory fences, and multithreading.

  • Takeaways & Limitations

    The study covers only read-only workloads and tests each index structure in isolation rather than within broader applications.

Abstract

from arXiv · show

Recent advancements in learned index structures propose replacing existing index structures, like B-Trees, with approximate learned models. In this work, we present a unified benchmark that compares well-tuned implementations of three learned index structures against several state-of-the-art "traditional" baselines. Using four real-world datasets, we demonstrate that learned index structures can indeed outperform non-learned indexes in read-only in-memory workloads over a dense array. We also investigate the impact of caching, pipelining, dataset size, and key size. We study the performance profile of learned index structures, and build an explanation for why learned models achieve such good performance. Finally, we investigate other important properties of learned index structures, such as their performance in multi-threaded systems and their build times.

1. INTRODUCTION

The paper addresses criticism of learned indexes by introducing an open, fair benchmark and evaluating tuned learned and traditional structures across realistic conditions. It finds learned approaches perform well across settings, while identifying cache misses as the strongest—though incomplete—performance explanation.

  • Motivation: Learned indexes were criticized because open implementations, suitable datasets, and standardized benchmarks were lacking.Reimplementations and weak baselines could make comparisons misleading.
  • Contributions: The benchmark provides an open-source RMI implementation, real-world datasets and workloads, and tuned learned and traditional index implementations.The suite is designed to avoid comparisons against weak baselines.
  • Benchmark results: In warm-cache tight-loop experiments, RMIs, PGM indexes, and RS indexes offered better performance/size tradeoffs than several state-of-the-art traditional structures.The analysis also varies dataset size, key size, and search technique.
  • Performance explanation: Cache misses were the strongest explanatory variable, but no single metric fully explained performance, and branch misses did not explain the learned-index advantage.This contradicts the earlier claim that branch misses explain the advantage.
  • Benchmark results: The study examines learned and traditional indexes under memory fences, cold caches, and multithreading, finding learned approaches performed well in all scenarios.These settings test behavior beyond an idealized tight-loop environment.
  • Limitations: The benchmark covers only read-only workloads and isolated index operations, limiting its coverage of broader applications and mixed read/write systems.The authors present it as a foundation for future mixed-workload benchmarks and writable learned indexes.

2. FORMULATION & DEFINITIONS

The paper models indexing over sorted, randomly accessible arrays as mapping lookup keys to bounded search ranges. Learned indexes approximate the array’s CDF to predict positions, after which a last-mile search locates the lower bound.

  • 2. FORMULATION & DEFINITIONS: An index structure maps an integer lookup key x to a search bound (lo, hi) in a zero-indexed sorted array D.The data model assumes integer keys and fast random access, such as an array.
  • 2. FORMULATION & DEFINITIONS: A valid bound contains the lower bound: the smallest key in D greater than or equal to lookup key x.This defines correctness for any possible lookup key.
  • 2. FORMULATION & DEFINITIONS: For keys greater than or equal to the largest key, the lower bound is defined as |D|, one beyond the array’s last position.This is the paper’s special-case convention and matches the C++ standard.
  • 2. FORMULATION & DEFINITIONS: Approximate indexes return a search range rather than an exact key position, a view that applies to both B-Trees and learned indexes.The exact lower-bound position is then found within the returned range.
  • 2.1 Approximating the CDF: The CDF view maps each key to its relative position in a sorted array, corresponding to the proportion of keys less than that key.Figure 2 presents this relationship for example data.
  • 2.1 Approximating the CDF: Given the dataset CDF, multiplying CDF_D(x) by |D| yields the lower-bound position; learned indexes approximate this function with models such as linear regressions.Approximation error means the predicted position is not always exact but can be bounded.
  • 2.1 Approximating the CDF: An approximate CDF index estimates a key’s position and converts the estimate and its maximum error into a search bound.The paper expresses this construction through IA(x).
  • 2.1 Approximating the CDF: An RMI uses a coarse first-stage model to select a refined second-stage model, while its stages progressively improve the CDF prediction.The depicted two-stage example combines a linear model with one of several cubic models.

3. LEARNED INDEX STRUCTURES

Learned indexes approximate a dataset’s CDF to return bounded search ranges, using distinct model organizations and lookup strategies. The paper evaluates RMIs, RadixSpline, and PGM indexes, emphasizing their structural and tuning differences.

  • 3.1 Recursive model indexes (RMI): RMIs combine a first-stage model with multiple second-stage models to refine CDF predictions for different data buckets.The first stage selects a second-stage model using a scaled CDF estimate; CDFShop tunes the models and branching factor.
  • 3.2 Radix spline indexes (RS): RadixSpline uses a linear CDF spline and radix table, then interpolates between spline points to estimate a key’s position.The radix table indexes key prefixes and narrows the spline-point search; RS has two tuning parameters: spline error and radix bits.
  • 3.3 Piecewise geometric model indexes (PGM): PGM recursively stacks error-bounded piecewise linear regressions over data segments and their partition boundaries.Each regression uses the fewest pieces needed for a preset maximum error, and lookup searches successive index layers.
  • 3.4 Discussion: All three learned structures approximate the CDF, but RMIs offer greater model flexibility while RS and PGM are simpler to tune.RS and PGM use two tuning knobs, whereas automatically optimizing an RMI requires a more involved process.
  • 3.4 Discussion: RS can use a cheaper radix-table lookup than PGM’s upper-level search when both provide comparable narrowing, but its range is not guaranteed to be narrow.A wide radix-derived range can make RS spend significant time searching for the appropriate bottom-layer model.

4. EXPERIMENTS

The experiments examine learned indexes across performance tradeoffs, explanatory factors, CPU interactions, multithreading, and build times. Learned structures are competitive in several settings, but their advantages vary by effect and construction cost.

  • Pareto analysis: Pareto analysis finds that all three learned index variants can offer better performance/size tradeoffs than several state-of-the-art traditional indexes.The comparison uses warm-cache, tight-loop workloads and extends across dataset sizes, key sizes, and search techniques.
  • Explanatory analysis: No single metric fully explains learned-index performance, although cache misses are the most important explanatory variable identified.Cache misses alone are insufficient for a statistically significant explanation, and branch misses do not explain the observed advantage.
  • CPU interactions: Learned indexes benefit disproportionately from CPU cache effects and operator reordering.The paper analyzes how cache behavior and execution ordering interact with index performance.
  • Multithreading: Learned structures achieve comparatively high multithreaded throughput, possibly because they incur fewer cache misses per lookup.The stated explanation remains qualified as possible rather than established causation.
  • Build times: RMIs are slower to build than PGM and RS indexes, and no learned structure yet builds as fast as insert-optimized traditional indexes.The build-time comparison distinguishes among learned structures and against traditional structures optimized for insertion.

4.1 Setup

The benchmark evaluates tuned learned and traditional indexes on real-world key distributions using isolated in-memory lookup workloads. It measures approximate-index behavior across datasets, structures, and size/performance tradeoffs.

  • Hardware: Experiments run on a machine with 256 GB of RAM and an Intel Xeon Gold 6230 CPU at 2.10 GHz.
  • Indexes: The evaluation includes RMIs, PGM, RadixSpline, and tree indexes including BTree, IBTree, ART, FAST, FST, and Wormhole.Learned implementations are tuned by their original authors; tree size/performance tradeoffs are tuned by inserting data subsets.
  • Datasets: Four real-world datasets each contain 200 million unsigned 64-bit integer keys, with additional experiments using larger and 32-bit datasets.The datasets represent Amazon book popularity, Facebook user IDs, OpenStreetMap cell IDs, and Wikipedia edit timestamps.
  • Workload: Each lookup includes payload validation by summing generated 8-byte values associated with keys.
  • Dataset distributions: Although the datasets’ CDFs appear smooth at broad scale, each contains substantial structure and noise at finer scale.The face dataset also contains approximately 100 large outlier keys that are omitted from the plotted CDF.
  • Workload: The benchmark generates 10M random lookup keys per dataset and requires returned search bounds to contain each lookup key’s lower bound.The study uses real-world distributions because synthetic data can be either unlearnable random noise or trivially learnable known distributions.

4.2 Pareto analysis

The Pareto analysis compares index lookup performance against memory size across datasets, key widths, dataset sizes, and search techniques. Learned indexes often offer strong performance/size tradeoffs, but dataset structure, implementation details, and workload constraints materially affect the result.

  • Dataset-dependent tradeoffs: Learned structures are Pareto optimal up to 100MB on amzn and wiki, and throughout the evaluated size range on face.On osm, both learned and traditional structures rarely outperform RBS because the dataset lacks local structure and is difficult to model.
  • Implementation effects: PGM performs significantly worse than RMI on three of four datasets because the compared RMI implementation lacked key model and execution optimizations.The result underscores the importance of tuned implementations and common benchmarks.
  • Tree behavior: Tree indexes become less effective beyond a certain size, with a nearly 1GB ART index on amzn slower than a 100MB ART index.At larger sizes, binary search over a small densely packed array can outperform further tree traversal.
  • RBS behavior: RBS can be highly competitive because a radix-table lookup obtains a search bound with one cache miss, whereas skewed keys can make the table ineffective.Its bound quality depends on prefix distribution, making it especially sensitive to dataset characteristics.
  • Hashing comparison: 114ns versus 180ns: CuckooMap achieves lower point-lookup latency than RMI, but uses over 1GB rather than 48MB of memory.Hashing is favored when range lookups and memory footprint are not concerns.
  • Dataset size: Learned indexes scale to 800M amzn keys with only logarithmic slowdown, consistent with the final binary search over the predicted search bound.An average bound of 128 keys requires seven binary-search steps, with dataset doubling adding logarithmic work.
  • Key size: 32-bit keys leave learned-index performance nearly unchanged, while trees and FAST improve because twice as many keys fit in each cache line.FAST can process 16 32-bit values per operator rather than 8 64-bit values using AVX-512 streaming operations.
  • Search function: Binary search is consistently faster than linear search, while interpolation search is similar on amzn and improves average performance by approximately 2%.Figure 11 evaluates these techniques for learned indexes and RBS on osm and amzn.

4.3 Explaining the performance

No single structural or performance metric explains lookup time across learned and traditional indexes. Cache misses, branch misses, and instruction counts jointly explain most observed variation, with cache misses the strongest contributor.

  • Performance metrics: At equal size, RMIs reached 220ns on amzn versus 650ns for a BTree, showing size alone is insufficient.
  • Performance metrics: At equal log2 error of 7, RMI reached 250ns on amzn versus 480ns for PGM, demonstrating an inference-time trade-off.Both structures produced the same average search-bound size, but RMI looked up faster.
  • Performance metrics: 95% of lookup-time variance was explained by regression on cache misses, branch misses, and instruction count.The reported regression had R2 = 0.955.
  • Statistical explanation: Cache misses had the largest explanatory power, while branch misses and instruction count also contributed significantly.The standardized coefficients were 0.85 for cache misses, −0.28 for branch misses, and 0.50 for instruction count.
  • Mechanism: RMI inference requires at most two cache misses, whereas full BTrees generally require at least one cache miss per tree level.For RMIs, most cache misses occur during the last-mile search.
  • Implications: Current learned indexes prioritize fast inference, but multi-stage RMIs did not achieve sufficient accuracy to exploit more cache misses for precise cache-line targeting.The paper identifies this as a possible direction for future work.
  • Compression perspective: Evaluating learned indexes as pure compression is insufficient because superior size-to-error ratios may lose to faster inference.Compression-only analysis becomes more relevant when storage is arbitrarily slow and search time is dominated by search-bound size.

4.4 CPU interactions

Cache state and CPU instruction reordering materially affect measured lookup performance. Warm-cache tight loops can exaggerate results, while memory fences expose substantial differences in reordering benefits.

  • Caching: Warm-cache tight loops can exaggerate index performance because cached accesses are much faster than uncached accesses.Cached accesses take tens of nanoseconds, compared with approximately 100 nanoseconds for uncached accesses.
  • Caching: Warm measurements represent cached lookup sequences, whereas cold measurements flush the cache after every lookup.
  • Caching: With larger index sizes, cache state mattered more than index choice, although learned approaches retained dominant performance/size trade-offs in both conditions.
  • Instruction reordering: A memory fence caused approximately a 50% slowdown for RMI and RS, while BTree, FAST, and PGM were almost unaffected.The fence prevents reordering operations across consecutive lookups.
  • Instruction reordering: Fence sensitivity correlated with instruction count: lower-instruction indexes such as RMI and RS were more affected than higher-instruction structures such as BTrees.The paper suggests peephole reordering may be more effective over smaller instruction windows.
  • Evaluation guidance: The paper recommends memory-fence tests and application-specific evaluation because reordering benefits depend on workload structure.Tight loops with minimal computation may legitimately benefit from reordering.

4.5 Multithreading

Concurrent throughput depends strongly on cache behavior and instruction-level overlap, not simply single-thread latency or index size. FAST scaled best in the reported experiment, while RobinHash scaled worst.

  • Thread scaling: RobinHash had the lowest single-thread latency but failed to achieve the highest concurrent throughput, which even RBS exceeded.The experiment used a 20-core CPU supporting 40 simultaneous hyperthreads.
  • Cache behavior: RobinHash incurred far more cache misses per second than other techniques, diminishing its multithreading benefit.Threads become latency-bound while waiting for access to RAM.
  • Thread scaling: FAST achieved 32x throughput at 40 threads, compared with 27x for PGM and 20x for RobinHash.FAST combined few cache misses per second with streaming AVX-512 instructions that overlap computation and memory reads.
  • Cache behavior: Cache misses per second correlated with speedup but did not always determine it, as FAST outperformed PGM despite PGM having fewer misses.
  • Index size: Larger indexes generally achieved higher throughput than smaller ones, possibly because smaller models produced larger last-mile search bounds.The expected caching advantage of smaller structures was not observed.
  • Index size: PGM, BTree, RS, and ART lost throughput at large model sizes, whereas RMI did not show the same regression.The paper attributes this possibly to RMI requiring at most two cache misses per inference.

4.6 Build times

Build times vary substantially across index families and dataset sizes. Among learned structures, RS built fastest, while the largest-dataset times were 80 seconds for RMI, 38 seconds for PGM, and 20 seconds for RS.

  • Measurement scope: The reported times exclude tuning, and automatically tuning an RMI may take several minutes.
  • Traditional indexes: BTree, FST, and Wormhole had the fastest build times overall because they were designed to support fast updates.
  • Traditional indexes: FAST and RobinHash had the longest build times among non-learned indexes in the reported comparison.RobinHash’s high-load-factor configuration induces many swaps.
  • Learned indexes: 80 seconds, 38 seconds, and 20 seconds were the largest-dataset build times for RMI, PGM, and RS, respectively.
  • Measurement scope: Parallel build or insert capabilities of Wormhole and PGM were not evaluated.
  • Learned indexes: RS consistently built fastest among learned indexes because it scans the data once with constant time per element.
  • Learned indexes: PGM builds its initial layer in one pass and subsequent layers in passes over progressively smaller previous layers.

5. CONCLUSION AND FUTURE WORK

The benchmark finds learned indexes generally deliver better performance/size trade-offs than traditional indexes in read-only in-memory searches, across varied conditions. Their strongest performance/size comes with longer builds for RMIs, while future work includes end-to-end applications and update-focused comparisons.

  • Learned structures provided Pareto-dominant performance/size behavior for read-only in-memory searches over dense arrays.This dominance sometimes diminished but persisted across dataset sizes, key sizes, memory fences, cold caches, and multi-threading.
  • Cache misses played the largest explanatory role, although no single metric accounted for learned-index performance.
  • Learned structures generally required longer build times than insert-optimized traditional structures such as BTrees.
  • RMIs offered the strongest performance/size among learned structures but had the longest build times, while RS and PGM built faster with slightly slower lookups.
  • Future work includes measuring end-to-end application impact, combining radix tables with RMIs, and benchmarking learned structures supporting updates against traditional indexes.
Loading 2006.12804v2…