项目的 README,来自 github.com/gilnett/learned_index_lab。合并为一个 markdown 文件:README.md。
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.
| Structure | Layout | Lookup | Cache Locality | Index Metadata (1M keys) | Total Process Memory |
|---|---|---|---|---|---|
Flat Slice |
Contiguous slice | Binary search ($O(\log N)$) | Medium (stride jumps across RAM) | 0.00 KB | 7.63 MB |
Eytzinger |
1-based array | Branchless traversal | High (root levels L1-pinned) | 7.63 MB | 15.26 MB |
PgmIndex |
Linear segments | ALU projection + local scan | High (when segments <= L2 cache) | 3.1 KB - 1.50 MB | 7.63 MB - 9.13 MB |
MultilevelPgmIndex |
Recursive PGM tree | Top-down arithmetic ($O(h \log \epsilon)$) | High (bounded descent) | 2.0 KB - 1.32 MB | 7.63 MB - 8.95 MB |
BTreeMap |
Heap nodes | Pointer hops ($O(\log N)$) | Low (scattered heap nodes) | ~45.78 MB (embedded) | 45.78 MB |
Measured on x86_64 hardware in --release mode. Consolidated average across all 6 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 Metadata | Moyenne Totale Latence | Speedup vs BTree |
|---|---|---|---|---|---|---|---|
| BTreeMap | 52.08 ms | 178.8 ns | 181.3 ns | 180.7 ns | 45.78 MB | 180.3 ns | 1.00x |
| Flat Slice | 0.00 ms | 140.9 ns | 113.4 ns | 122.4 ns | 0.00 KB | 125.6 ns | 1.27x |
| Eytzinger | 5.37 ms | 122.0 ns | 116.2 ns | 121.1 ns | 7.63 MB | 119.7 ns | 1.47x |
| PGM-Index | 4.78 ms | 115.5 ns | 107.2 ns | 146.7 ns | 330.6 KB | 123.1 ns | 1.55x |
| Multilevel PGM | 4.61 ms | 149.7 ns | 141.7 ns | 206.1 ns | 274.5 KB | 165.8 ns | 1.19x |
[!NOTE] Trade-Off Summary Across Real-World & Synthetic Workloads:
- PGM-Index is fastest on smooth/continuous distributions (up to 2.09x vs BTree), reducing metadata by up to 14,700x (~5.7x total resident RAM).
- BTreeMap wins decisively on irregular, heavily fragmented, or extreme Pareto power-law distributions (e.g. SOSD Books: 2.87x faster than PGM), where non-linearity degrades linear segment count.
- Eytzinger delivers the lowest and most consistent overall average latency (119.7 ns) without mathematical approximation error.
Detailed breakdown per distribution (Synthetic and SOSD real-world benchmarks) is available in docs/benchmarks/statistical_benchmarks.md.
The v0.4.0 test suite and benchmark harness support strict single-threaded isolation, SOSD real-world suites, and modular target selection:
# Clone the repository
git clone https://github.com/gilnett/learned_index_lab.git
cd learned_index_lab
# Run the unit test suite with thread isolation
cargo test --release -- --test-threads=1
# Execute the full 10-run release benchmark across all 5 targets
cargo run --release
# Run isolated benchmarks on specific targets (including Multilevel PGM)
cargo run --release -- --target multilevel,pgm --runs 10
cargo run --release -- --target pgm,multilevel --suite sosd
# Run the batch ingestion and rebuild benchmark (SSTable merge vs BTree in-place)
cargo run --release -- --batch --batch-size 100000
find), predecessor search (lower_bound), and zero-copy contiguous range scans (range).Arc<PgmIndex>.N/S compression metrics, and production checklist.lower_bound), slice scans, and expanding benchmark baselines.Licensed under the Apache License, Version 2.0 (LICENSE or http://www.apache.org/licenses/LICENSE-2.0).