gilnett / learned_index_lab

# Learned Index Lab: Modern Search Paradigms in Rust
A clean, zero-dependency Rust implementation and comparative benchmark suite of **Piecewise Geometric Model (PGM) Learned Index Structures**.
This repository evaluates mathematical function approximations of Empirical Cumulative Distribution Functions (CDFs) against standard pointer trees (`BTreeMap`), contiguous binary search (`slice::binary_search`), and cache-conscious breadth-first search (`EytzingerSearch`).
> [!NOTE]
> **Academic Attribution**: Learned Indexes were originated by Kraska et al. (MIT/Google, SIGMOD 2018). The PGM-index was invented and proven by Paolo Ferragina and Giorgio Vinciguerra (University of Pisa, PVLDB 2020). The Eytzinger layout was formalized by Paul-Virak Khuong and Pat Morin (ACM JEA 2017). This repository is an independent, clean-room implementation in pure safe Rust.
---
## Architectural Comparison (4 Search Paradigms)
| Dimension | Standard `BTreeMap` | Flat `slice::binary_search` | `EytzingerSearch` (Breadth-First) | `PGM-Index` (Learned Model) |
| :--- | :--- | :--- | :--- | :--- |
| **Data Layout** | Heap node hierarchy | Contiguous sorted slice | 1-based complete binary tree array | Compact array of $(a, b, k_0)$ segments |
| **Lookup Mechanism** | 4–6 pointer hops across heap | $\sim 20$ binary jumps across RAM | Branchless arithmetic traversal (`k = 2k + bit`) | In-register ALU prediction + bounded local scan |
| **Cache Locality** | Poor (scattered heap nodes) | Medium (strided binary jumps) | High (upper tree levels in L1/L2) | **Highest** (segments fit entirely in L1/L2) |
| **Index Overhead** | $\sim 45.78\text{ MB}$ per $10^6$ keys | $0\text{ KB}$ (in-situ data only) | $7.63\text{ MB}$ per $10^6$ keys (duplicate layout) | **3.1 KB – 48.1 KB** (-99.9% vs BTree) |
| **Primary Strength** | Dynamic in-place mutations | Zero extra memory | Branchless search, cache friendly | **Sub-microsecond lookups, extreme compression** |
---
## Benchmark Summary (v0.3.0 Consolidated Results)
Measured on x86_64 hardware in `--release` mode. Consolidated average across all 3 workload distributions (30 independent runs per target structure with a 32MB L1-L3 CPU cache eviction barrier between phases):
| Cible / Target | Build Time | Hit Latency | Miss Latency | Lower Bound | Index Memory | Moyenne Totale Latence | Speedup vs BTree |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| **BTreeMap** | 84.12 ms | 314.4 ns | 331.4 ns | 350.0 ns | 45.78 MB | 331.9 ns | 1.00x |
| **Flat Slice** | 0.00 ms | 282.7 ns | 272.9 ns | 275.3 ns | 0.00 KB | 277.0 ns | 1.20x |
| **Eytzinger** | 6.30 ms | 163.7 ns | 160.9 ns | **169.2 ns** | 7.63 MB | **164.6 ns** | **2.02x** |
| **PGM-Index** | 6.82 ms | **153.0 ns** | **154.1 ns** | 208.6 ns | **21.1 KB** | 171.9 ns | **1.93x** |
> Detailed breakdown per distribution (Dense Time-Series, Uniform Sparse, and Heavy-Tailed Lognormal) is available in docs/benchmarks/statistical_benchmarks.md.
---
## Reproducibility & Verification
Th