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):

Workload Distribution	Flat slice::binary_search	PGM-Index (v0.2.0)	Speedup vs. Slice
Dense Sequential Time-Series (ε = 32)	152.7 ns/op	63.5 ns/op	2.41x faster
Uniform Sparse Random (ε = 16)	150.9 ns/op	70.5 ns/op	2.14x faster
Clustered Heavy-Tailed Lognormal (ε = 16)	141.0 ns/op	48.6 ns/op	2.90x faster

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());
}