Learning index still cooking...
I go through a lot of indexes while benchmarking and profiling amber, and sometimes end
up building my own - I wrote about one here. At
some point I ran into the so-called
learned index,
and it impressed me. The idea is simple and elegant: instead of building a tree or a hash
on top of sorted keys, you look at the (key, position) pairs as points on a graph and fit
a function through them - linear, piecewise-linear, or just bolt on a small LLM. The whole
index compresses down to a handful of coefficients, and a lookup becomes computing
f(key) ≈ position instead of walking a data structure. The model almost never
predicts the exact position, so right after the prediction there's a short local search to
correct it. The index basically turns from a structure into a function.
So naturally I went straight for an experiment and added such an index to amber - instead of, or alongside, the existing binary interval index. The idea is interesting, but in practice the learning index doesn't so much beat binary search as tie with it - a bit faster on some datasets, a bit slower on others, some of it within measurement noise. What you actually pay for is build cost: it's consistently the highest of all candidates, sometimes twice the binary index's build time. So for roughly the same lookup, you're overpaying on construction - and until that bill comes down, this index is still cooking.
The question
What do we want from an immutable index over the time ranges of sealed segments? The
correct answer is to answer exactly one question - "which segments overlap
[from, to)" - and to do it fast. The current implementation in amber scans
every segment and sorts the matches - correct, but linear in the number of segments. So
let's look at two candidates that promise sublinear lookup:
First, an exact binary interval search over segments sorted by MinTS, with a
monotonic prefix maximum of MaxTS.
And second, today's protagonist - a bounded piecewise-linear rank model in the spirit of
PGM-index and RadixSpline, which predicts a search corridor and refines it with an exact
lower-bound search. From here on, called piecewise_linear.
The experiment's methodology follows the cautions in the paper above (a genuinely fun read, recommended): lookup and position refinement are measured separately, build cost and index size are tracked separately, different CDF shapes are run separately, and range-scan cost is never confused with boundary-search cost.
Correctness guarantee
Both candidates have to return exactly the same segment IDs as the linear scan, regardless
of insertion order, duplicate timestamps, gaps, overlaps, or int64 boundaries.
For the learned model this works as follows: the model only predicts a bounded search
corridor, and an exact lower-bound search refines it. If that corridor invariant is ever
violated, the implementation falls back to a global binary search. So a model error can
cost time - it can never drop a matching segment.
The experiment passed:
- the full 45-case matrix with 59,610 oracle queries;
- deterministic tests for duplicate timestamps, gaps, overlaps, shuffled insertion order, and
int64boundaries; - randomized tests on overlapping intervals;
- a Go fuzz target whose seed corpus runs in the normal test suite.
A separate fuzz campaign ran 240,412 executions without a single mismatch. Across the full matrix: zero fallbacks from learned search to binary.
Datasets and workload
Each dataset is deterministic and is generated at 10k, 100k, and 1M segments:
| Dataset | Purpose |
|---|---|
monotonic | smooth timestamp CDF |
bursty | dense bursts, abrupt small and large gaps, variable widths |
gaps | regular large holes in event time |
late_arrivals | old timestamps and long overlapping segment intervals |
out_of_order | monotonic event time inserted in shuffled order |
Query mix: 60% point/narrow hits, 25% ranges of up to 32 segment starts, 10% gap-adjacent
queries, 5% misses. out_of_order intentionally has the same post-sort lookup
distribution as monotonic - this isolates the cost of sorting during bulk
build.
The binary interval index sorts by MinTS and stores both MinTS
and a monotonic prefix maximum of MaxTS. It finds the safe window:
lo = lower_bound(prefixMax, query.From)
hi = upper_bound(minTS, query.To)
Every interval in [lo, hi) is then checked exactly. Long overlapping
intervals from late_arrivals can widen this window, but can't produce a false
negative.
Results
The table below is the median of three fixed-iteration Go benchmarks at 1M segments. It's the comparison for sub-microsecond operations; lower is better.
| Dataset | Linear scan | Binary interval | Piecewise linear | Learned vs binary |
|---|---|---|---|---|
| monotonic | 8,338 µs | 0.703 µs | 0.327 µs | 2.15× faster |
| bursty | 8,290 µs | 1.074 µs | 1.169 µs | 1.09× slower |
| gaps | 8,342 µs | 0.738 µs | 0.329 µs | 2.24× faster |
| late arrivals | 8,264 µs | 166.636 µs | 168.748 µs | 1.01× slower |
| out of order | 8,344 µs | 0.693 µs | 0.495 µs | 1.40× faster |
The model genuinely speeds up the boundary search itself: 84-133 ns versus 130-165 ns for
binary search at 1M keys. On smooth distributions (monotonic, gaps, out_of_order) that
shows up in the full lookup too - 1.4-2.24× faster. On bursty and
late_arrivals the edge disappears - but the results there are within
measurement noise. So on those two datasets, call it parity.
Candidate-scan amplification explains the late_arrivals result:
| Dataset | 10k segments | 100k segments | 1M segments |
|---|---|---|---|
| monotonic | 5.16 | 5.08 | 4.81 |
| bursty | 24.62 | 24.67 | 24.44 |
| gaps | 5.16 | 5.08 | 4.81 |
| late arrivals | 4,726.17 | 12,130.82 | 11,963.00 |
| out of order | 5.16 | 5.08 | 4.81 |
Binary and learned variants scan exactly the same safe window. A different predictor can't
fix the amplification on late_arrivals - that needs a different interval data
structure, or tighter segment time ranges.
Build cost and index size
At 1M segments, median cold build times were:
| Dataset | Clone for linear | Binary interval | Piecewise linear |
|---|---|---|---|
| monotonic | 7.26 ms | 17.15 ms | 39.33 ms |
| bursty | 7.11 ms | 18.79 ms | 38.18 ms |
| gaps | 7.26 ms | 17.03 ms | 42.61 ms |
| late arrivals | 7.72 ms | 167.98 ms | 176.54 ms |
| out of order | 7.77 ms | 258.55 ms | 283.51 ms |
The shared range array is estimated at 40 bytes per segment. Binary interval metadata adds 16 bytes per segment. The learned prototype adds roughly another 0.22-0.44 bytes per segment on top of that for its models.
Conclusion
We didn't get much of a win here: lookup is parity at best, and in a couple of cases it's squarely within measurement noise. Build cost is the one place where the story is unambiguous - the learned model builds slower than the binary index on every dataset, no exceptions, and on smooth data it's 2-2.5× slower. For our case that doesn't pencil out yet - overpaying on construction for an index that's merely not worse than its neighbor is a bad trade. Still, it was fun to experiment with, and the idea earned it. Who knows, maybe we'll come back to it down the road...