DEV Community: gilnett

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

gilnett — Sun, 18 Oct 2026 13:45:12 +0000

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:

The segment array is tiny (3 KB to 48 KB) and stays resident in L1/L2 cache.
The initial binary search over segments takes only 6 to 9 jumps in fast cache.
The arithmetic calculation calculates the candidate offset immediately.
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:

Finding the first key >= target (predecessor / lower bound).
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());
}

Why We've Been Indexing Data Wrong for 50 Years: Replacing B-Trees with Math in Rust

gilnett — Fri, 16 Oct 2026 00:25:27 +0000

Why We've Been Indexing Data Wrong for 50 Years: Replacing B-Trees with Math in Rust

For half a century, database engineering has rested on an unspoken consensus: if you need to index sorted data, you use a B-Tree. From relational engines like PostgreSQL and SQLite to modern key-value stores like RocksDB, B-Trees and their variants have been the default choice since the early 1970s.

They are robust, well-understood, and battle-tested. But in the 50 years since their invention, computer architecture has fundamentally transformed.

Processors have become astonishingly fast, while RAM latency has barely kept pace. This divergence—often called the memory wall—means the way B-Trees navigate data is increasingly at odds with how modern silicon actually works.

I spent the past few days implementing and benchmarking a theoretical alternative in pure Rust: a Piecewise Geometric Model (PGM) Learned Index. Here is what I learned about why it works, how it breaks the traditional model, and what it implies for modern software systems.

The Silent Bottleneck: Pointer Chasing

To understand why B-Trees struggle on modern hardware, you have to look at what happens at the CPU cache level during a lookup.

A B-Tree organizes data into hierarchical nodes linked by memory pointers. When searching for a key:

The CPU loads the root node from RAM into cache.
It scans the node to find the appropriate child branch.
It follows a pointer to another memory location in RAM, usually causing a cache miss.
It repeats this process four to six times until reaching the target leaf.

On a modern CPU, an arithmetic calculation takes a fraction of a nanosecond. Loading an un-cached line from main memory takes around 50 to 100 nanoseconds.

During a B-Tree search, your processor spends almost none of its time "thinking"—it spends nearly all of its time waiting for memory buses to deliver data across disparate RAM addresses. This phenomenon is known as pointer chasing.

Furthermore, maintaining this tree structure requires substantial metadata: child pointers, node capacities, and balancing flags. In practice, the index metadata alone often takes up more memory than the actual keys being indexed.

The Paradigm Shift: Data is a Function

What is a sorted list of numbers?

Traditionally, we treat sorted data as an opaque collection of distinct items that must be compared one by one. But mathematically, a sorted array is simply a curve: a Cumulative Distribution Function (CDF).

If you have an array of a million sorted items, the position of any item is roughly proportional to its value.

In 2018, researchers at MIT and Google (Kraska et al.) asked a provocative question:

Why are we traversing an artificial tree of pointers when we could simply approximate the curve with a mathematical equation?

If you know the slope of the data, you don't need a tree. You can compute the memory address directly using basic algebra:

y = ax + b

How a PGM-Index Actually Works

Pure machine learning models like neural networks are often too slow and lack strict precision guarantees—you cannot afford to "guess roughly" where a database record lives.

This is where the Piecewise Geometric Model (PGM) comes in. It does not use neural networks; it uses formal geometry.

1. The Error Corridor (ε)

Instead of forcing a single complex curve over the entire dataset, a PGM index draws a series of simple linear segments over the data.

As it scans through the sorted keys in a single pass, it maintains a narrow "corridor" of width ε (for example, 16 or 32 items wide). As long as the incoming data points stay within this corridor, the same straight line continues. The moment the data bends too far, the segment is sealed, and a new straight line begins.

2. Direct ALU Calculation

When you query a key:

The CPU checks which segment covers the key (a trivial lookup across a tiny array of segments).
It evaluates the linear equation y = ax + b using single-cycle arithmetic instructions on the CPU ALU.
The result is guaranteed by construction to be within ± ε of the true location.
The CPU performs a tiny local search within that bounded window.

Because that local window is so small, the entire search window is already loaded in the CPU's L1 cache line. The CPU never has to stall waiting for random memory jumps.

What This Implies in the Real World

Replacing pointer traversal with affine approximations changes the fundamental economics of indexing:

1. Radical Memory Shrinkage

In traditional database architectures, storing an index for a million items requires dozens of megabytes of pointer allocations.

With a PGM index, smooth or predictable data (such as timestamps, auto-increment IDs, or sequential keys) can be modeled by just a few dozen linear equations. An index that previously consumed tens of megabytes shrinks down to a few kilobytes.

The entire index can live permanently inside the CPU cache, leaving your RAM free for actual application data.

2. Predictable Low Latency

Because lookups do not depend on walking an arbitrary tree structure, latency becomes deterministic. The CPU performs an ALU calculation, accesses contiguous memory, and finishes the search in a fraction of the time a traditional tree requires.

3. Lower Infrastructure Costs

Memory is the single most expensive hardware component in large-scale database clusters. Dividing index memory footprints by orders of magnitude allows database nodes to hold significantly more data per machine before needing to scale out or page to disk.

The Trade-offs: Where It Fits (and Where It Doesn't)

Learned indexes are not a silver bullet that replaces B-Trees everywhere:

Where they shine: Read-heavy workloads, append-only streams, and immutable storage blocks. In modern LSM-Tree storage engines like RocksDB or ClickHouse, data on disk is written once into immutable files (SSTables). Indexing these static blocks with a PGM index provides massive speed and memory benefits without any drawback.
Where B-Trees still hold ground: Highly dynamic, random-write workloads with frequent in-place insertions and deletions. Updating a geometric segment on every individual insert requires buffering or rebuild strategies that traditional self-balancing trees handle naturally.

Conclusion & Code

Building this in Rust confirmed that modern performance engineering is less about micro-optimizing instructions and more about aligning algorithmic design with the physical realities of memory hierarchies.

I packaged this implementation as an open-source, zero-dependency Rust crate with full reproducibility tests:

Repository: https://github.com/gilnett/learned_index_lab
Crate: https://crates.io/crates/learned_index_lab

If you are building storage engines, analytical query tools, or high-throughput systems, functional data structures like learned indexes are well worth exploring.

wstrace: Linux strace for Windows (in Rust, Zero Drivers)

gilnett — Sun, 11 Oct 2026 16:49:11 +0000

Ever missed Linux's strace when debugging on Windows?

Tools like Sysinternals Process Monitor (ProcMon) are great, but heavy, GUI-only, or reliant on drivers.

I built wstrace: a standalone system call and Win32 API monitor in Rust. It runs entirely in user-space using native ETW—zero kernel drivers required.

I just released v0.2.0. Here is what is new:

System-Wide Tracing (wstrace all): Monitor events across the entire system simultaneously.
Output Modes:
- Live Stream (-m stream): Fast stdout terminal stream like Linux strace.
- Interactive TUI (default): Real-time filtering, search, and clipboard export.
JSON Export (--export-json <file>): Save captured session traces to a JSON file.
Windows on ARM64 Support: Pre-compiled binaries available for both x64 and ARM64.

GitHub: github.com/gilnett/wstrace

Building wstrace: A Zero-Driver Windows System & API Monitor in Rust

gilnett — Fri, 09 Oct 2026 21:51:01 +0000

I built wstrace, a lightweight terminal-first Windows system and API monitor written in Rust.

I wanted a quick way to inspect Win32 APIs and syscalls directly from the terminal without needing to install or manage kernel drivers.

How it works

wstrace runs purely in user space by tapping into native Windows ETW (Event Tracing for Windows) and Win32 APIs. This keeps it safe, portable, and easy to run on any machine as a single .exe.

It supports two workflows:

Interactive TUI: Built with Ratatui to navigate processes, search events, and filter activity live.
Live stdout stream: Outputs directly to the terminal for scripting and CI/CD pipelines.


powershell
# Example 1: Stream live execution to terminal
wstrace -m stream run myapp.exe

# Example 2: Attach to a running process and export to JSON
wstrace -m stream --export-json trace.json attach -n myapp.exe

DEV Community: gilnett

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

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

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

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

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

3. Code Example: How It Works in Practice

Why We've Been Indexing Data Wrong for 50 Years: Replacing B-Trees with Math in Rust

Why We've Been Indexing Data Wrong for 50 Years: Replacing B-Trees with Math in Rust

The Silent Bottleneck: Pointer Chasing

The Paradigm Shift: Data is a Function

How a PGM-Index Actually Works

1. The Error Corridor (ε)

2. Direct ALU Calculation

What This Implies in the Real World

1. Radical Memory Shrinkage

2. Predictable Low Latency

3. Lower Infrastructure Costs

The Trade-offs: Where It Fits (and Where It Doesn't)

Conclusion & Code

wstrace: Linux strace for Windows (in Rust, Zero Drivers)

Building wstrace: A Zero-Driver Windows System & API Monitor in Rust

How it works

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