Learned Indexes in Rust v0.2: Answering Reddit, Adding Range Queries, and Beating slice::binary_search

A few days ago, I published an architectural deep dive exploring a provocative question: What if we could replace comparison-based database trees (like B-Trees) with pure mathematical functions in Rust?

The response from the community across Dev.to and Reddit (r/rust, r/compsci, r/database) was incredible. It sparked great discussions, valid skepticism, and direct questions that deserved real engineering answers rather than theoretical debates.

Today, I released learned_index_lab v0.2.0. Before diving into the technical answers, here is a quick refresher on what this project is and what it proves.

1. What is Learned Index Lab, and What Does It Prove?

For more than 50 years, database storage engines (B-Trees, B+Trees, LSM-Trees) have relied on comparison-based pointer hierarchies. While reliable, traversing tree nodes introduces severe hardware penalties on modern CPU architectures:

• Pointer Chasing: Every jump down a tree incurs memory dereferences across distant heap locations, triggering recurring L1/L2/L3 cache misses.
• High Memory Overhead: A standard BTreeMap consumes ~45 MB of node pointers, balancing factors, and metadata for every 1,000,000 keys.
• Branch Mispredictions: Repetitive binary branch decisions at each node stall deep CPU execution pipelines.

Originated by Kraska et al. (MIT / Google) and formalized by Ferragina & Vinciguerra (PVLDB 2020), Learned Indexes reframe indexing as a mathematical regression problem.

Given a sorted dataset, the index builder runs a single-pass streaming Piecewise Linear Approximation (PLA) that partitions the data into a tiny set of linear segments (y = ax + b). During lookup, the CPU executes an in-register arithmetic calculation predicting the exact position within a strict, provable error corridor [approx - ε, approx + ε], followed by a tightly bounded local search.

What the benchmarks prove:

• Zero data loss & 100% exact lookups (0 false positives, 0 false negatives).
• 99.97% memory reduction: Index metadata drops from 45.78 MB down to ~12 KB for 1,000,000 keys.
• 3x to 4.5x faster lookups compared to standard BTreeMap.

2. Why v0.2.0? Answering the Community's Questions

The discussions on Reddit and Dev.to raised two critical questions that shaped this release:

Question 1: "Why only compare against BTreeMap? What about a flat sorted slice using slice::binary_search?"

This was the most frequent critique, and it is 100% valid.

A contiguous, pre-sorted Vec<u64> indexed via slice::binary_search has 0 KB of extra memory overhead. It eliminates heap pointer indirection entirely. How does a PGM learned index hold up against standard library binary search on a flat slice?

To answer this conclusively, I integrated slice::binary_search as an explicit baseline across all 10-run, 1,000,000-key statistical benchmarks in src/main.rs.

The Results (Average across 10 randomized runs, 1M keys, 100k queries):

Why is PGM over 2x faster than a contiguous binary search?
A binary search over 1,000,000 keys requires ~log₂(10⁶) ≈ 20 comparisons. Because the jumps cut across 8 MB of contiguous memory, the first 14 to 16 jumps inevitably miss the L1/L2 CPU cache, forcing DRAM cache line fetches.

With PGM:

1. The segment array is tiny (3 KB to 48 KB) and stays resident in L1/L2 cache.
2. The initial binary search over segments takes only 6 to 9 jumps in fast cache.
3. The arithmetic calculation calculates the candidate offset immediately.
4. The final local search only inspects 2ε = 32 elements (a single 256-byte span fitting inside 4 cache lines).

Memory traffic is cut from ~20 cache line fetches down to 4, explaining the 2.1x–2.9x latency win.

Question 2: "Point lookups are cool, but real databases need Range Queries and Lower-Bound searches. Can PGM do that?"

Point lookups (find(key) -> Option<usize>) are only half the battle. Real-world analytical systems (ClickHouse zone maps, RocksDB SSTables, Parquet row groups) rely heavily on:

1. Finding the first key >= target (predecessor / lower bound).
2. Scanning a continuous slice of keys within an interval [A, B].

In v0.2.0, I implemented two zero-allocation APIs:

• lower_bound(&self, target: u64) -> usize: Calculates the predicted lower-bound offset in O(log S + log ε) time with an automatic fallback guarantee to partition_point should pathological bounds occur.
• range<R: RangeBounds<u64>>(&self, bounds: R) -> &[u64]: Accepts any standard Rust range bounds (.., a..b, a..=b, a.., ..b) and returns a zero-copy slice directly over the underlying sorted buffer.

3. Code Example: How It Works in Practice

Here is the updated v0.2.0 API in action:

rust
use learned_index_lab::PgmIndex;

fn main() {
    // 1. Prepare sorted dataset (e.g. sensor timestamps or primary IDs)
    let data: Vec<u64> = vec![
        100, 105, 110, 115, 120, 250, 500, 1000, 1500, 2000, 5000, 10000
    ];

    // 2. Build the PGM index with an error bound corridor (epsilon = 16)
    let pgm = PgmIndex::build(data, 16);

    // 3. Exact point lookup (O(log S + log epsilon))
    assert_eq!(pgm.find(1500), Some(8));

    // 4. Predecessor / Lower Bound search (first element >= 1200)
    let lb_idx = pgm.lower_bound(1200);
    println!("Lower bound for 1200 is at index {}: value {}", lb_idx, pgm.data[lb_idx]);
    // Output: index 8, value 1500

    // 5. Zero-copy range query over continuous slice
    let slice = pgm.range(110..=2000);
    println!("Keys in [110, 2000]: {:?}", slice);
    // Output: [110, 115, 120, 250, 500, 1000, 1500, 2000]

    // 6. Memory footprint inspection
    println!("Total segments: {}", pgm.segments.len());
    println!("Index metadata size: {} bytes", pgm.index_only_bytes());
}