Learned Index Lab: Piecewise Geometric Model (PGM-Index) in Rust

A zero-dependency, production-grade implementation of Piecewise Geometric Model (PGM) Learned Index Structures in pure Rust.

This repository demonstrates the paradigm shift away from traditional comparison-based pointer hierarchies (such as B-Trees and LSM block indexes) to mathematical function approximations of Empirical Cumulative Distribution Functions (CDFs) with provable $\epsilon$ error bounds.

---

Table of Contents

• Overview & The Paradigm Shift
• Mathematical Foundation
  • Optimal Streaming Piecewise Linear Approximation (PLA)
  • Bounded Local Search
• Why It Outperforms Traditional B-Trees
• Statistical Benchmark Suite (10-Run Rigorous Analysis)
  • 1. Dense Sequential Time-Series Data
  • 2. Uniform Sparse Random Keys
  • 3. Clustered Heavy-Tailed Lognormal Distribution
• Real-World Production Applications
• Quickstart & Code Example
• Reproducibility & Verification
• Resources & References
• License

---

Overview & The Paradigm Shift

For more than 50 years, database indexing has relied on tree-based data structures (B-Tree, B+Tree, LSM-Tree). While mature, B-Trees possess inherent physical constraints on modern CPU architectures:

1. Pointer Chasing: Navigating down a tree requires sequential memory dereferences across disparate memory addresses, causing recurring L1/L2/L3 cache misses.
2. High Memory Overhead: Tree nodes require significant metadata per key (child pointers, balance factors, keys, values), consuming 30–50 bytes per entry.
3. Branch Misprediction: Binary comparisons at each node introduce branch penalties on deeply pipelined modern CPUs.

Learned Indexes (originally introduced by Kraska et al., MIT / Google) reframe indexing as a regression problem: Given a sorted sequence of keys $K = (k_0, k_1, \dots, k_{N-1})$, the position of any key $k$ in memory corresponds to the scaled Empirical Cumulative Distribution Function:

$$\text{Pos}(k) \approx N \times \text{CDF}(k)$$

Rather than allocating deep node hierarchies, a PGM-Index partitions the data into a minimal set of linear segments $y = ax + b$, guaranteeing that the true position of any indexed key is within a strict error window $[y - \epsilon, y + \epsilon]$.

---

Mathematical Foundation

Optimal Streaming Piecewise Linear Approximation (PLA)

The index builder executes in a single streaming pass ($O(N)$ time, $O(1)$ extra space).

For a segment starting at point $(x_0, y_0)$ and a given maximum error tolerance $\epsilon$: Each subsequent point $(x_i, y_i)$ restricts the feasible slope interval $[s_{\min}, s_{\max}]$:

$$s_{\min} = \max_{j} \left[ \frac{(y_j - \epsilon) - y_0}{x_j - x_0} \right]$$

$$s_{\max} = \min_{j} \left[ \frac{(y_j + \epsilon) - y_0}{x_j - x_0} \right]$$

As long as $s_{\min} \le s_{\max}$, all points observed so far can be represented by a single straight line with error at most $\epsilon$. Once $s_{\min} > s_{\max}$, the segment is finalized with slope $s = \frac{s_{\min} + s_{\max}}{2}$, and a new segment starts.

Bounded Local Search

During point lookup:

1. The responsible segment is found via a rapid binary search across the segment array ($O(\log S)$ where $S \ll N$).
2. The position estimate is computed directly via ALU instructions: $$\text{Pos}_{\text{approx}} = \text{round}(y_0 + s \cdot (k - x_0))$$
3. The exact match is retrieved via a local binary search bounded strictly inside: $$[\max(0, \text{Pos}{\text{approx}} - \epsilon), \min(N - 1, \text{Pos}{\text{approx}} + \epsilon)]$$

• Time Complexity: $O(\log S + \log \epsilon)$
• Space Complexity: $O(S)$ where $S \approx \frac{N}{\text{compression ratio}}$
• Correctness: 100% exact (0 false positives, 0 false negatives).

---

Why It Outperforms Traditional B-Trees

---

Statistical Benchmark Suite (10-Run Rigorous Analysis)

All benchmarks were measured locally on x86_64 hardware using Rust 1.99 in --release mode. Each scenario was executed over 10 consecutive runs with distinct randomized seeds to eliminate CPU scheduling noise and warm-cache anomalies.

• Dataset Size: 1,000,000 keys (64-bit integers)
• Queries per Run: 100,000 queries (50% existing keys / hits, 50% non-existent keys / misses)

1. Dense Sequential Time-Series Data

Simulates monotonically increasing timestamps, network log sequences, or primary auto-increment keys.

Distribution: Dense Timestamp | Tolerance: epsilon = 32

• Compression Ratio: 1,000,000 keys compressed into 83 affine equations (12,048x factor).
• Index Memory: 45.78 MB (BTreeMap) $\to$ 3.1 KB (PGM-Index) (-99.99%).
• Hit Speedup: 3.00x faster average lookup.
• Miss Speedup: 13.3x faster negative rejection.

---

2. Uniform Sparse Random Keys

Simulates randomly distributed 64-bit object IDs, hashed identifiers, and sparse primary keys.

Distribution: Uniform Sparse Random | Tolerance: epsilon = 16

---

3. Clustered Heavy-Tailed Lognormal Distribution

Simulates real-world power-law distributions (web traffic requests, financial transaction sizes, file size distributions).

Distribution: Lognormal Clustered | Tolerance: epsilon = 16

---

Real-World Production Applications

1. Columnar OLAP Databases (ClickHouse, DuckDB, Parquet)

Analytical engines ingest massive sorted blocks. PGM-Index acts as a lightweight zone map replacement, locating record offsets across millions of rows with minimal CPU instruction overhead.

2. LSM-Tree Storage Engines (RocksDB, ScyllaDB, LevelDB)

In an LSM storage engine, SSTables written to NVMe are strictly immutable. Replacing traditional sparse block index tables with PGM segments allows billions of keys to be indexed entirely in host CPU cache or RAM, reducing NVMe read amplification to exactly 1 physical block I/O per query.

3. OS File Indexing & Cataloging

Fast local file indexers (e.g., Everything, NTFS USN Journal analyzers) can catalog tens of millions of records within a few megabytes of RAM while delivering sub-100ns path resolution.

4. High-Throughput Network Routing (FIB)

Forwarding Information Bases (FIB) at 100+ Gbps line rates require deterministic sub-microsecond packet IP classification where L1/L2 cache saturation would immediately induce packet drops.

---

Quickstart & Code Example

Add learned_index_lab to your Cargo.toml, or include pgm.rs directly in your project:

use pgm::PgmIndex;

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

    // 2. Build the PGM index with maximum error epsilon (e.g. 16 or 32)
    let pgm = PgmIndex::build(data, 16);

    // 3. Point lookup (O(log S + log epsilon))
    match pgm.find(1500) {
        Some(index) => println!("Found key at position: {}", index),
        None => println!("Key not present in dataset"),
    }

    // 4. Inspect memory overhead
    println!("Total segments created: {}", pgm.segments.len());
    println!("Index-only memory: {} bytes", pgm.index_only_bytes());
}

---

Reproducibility & Verification

To verify the test suite and run the full 10-run statistical benchmark on your own machine:

# Clone the repository
git clone https://github.com/gilnett/learned_index_lab.git
cd learned_index_lab

# Run unit tests covering edge cases, gaps, and duplicates
cargo test

# Execute the 10-run release benchmark suite
cargo run --release

---

Resources & References

Primary Article & Technical Deep Dive

• Why We've Been Indexing Data Wrong for 50 Years: Replacing B-Trees with Math in Rust: A comprehensive architectural breakdown exploring CPU cache dynamics, the memory wall, mathematical CDF approximation, and real-world system implications of replacing pointer hierarchies with linear functions.

Seminal Research Papers

• Kraska et al. (2018): "The Case for Learned Index Structures" (SIGMOD 2018) – arXiv:1712.01208. Seminal paper proving that sorted indexes can be modeled as cumulative distribution function (CDF) regressions.
• Ferragina & Vinciguerra (2020): "The PGM-index: a data-structure with a guarantee on space and time efficiency" (VLDB 2020) – arXiv:1911.05496. Establishes optimal piecewise linear approximation (PLA) under bounded error corridors $\epsilon$.
• Ferragina & Vinciguerra (2020): Reference C++ PGM implementation – GitHub: gvinciguerra/PGM-index.

---

License

Licensed under the Apache License, Version 2.0 (LICENSE or http://www.apache.org/licenses/LICENSE-2.0).