learned_index_lab README

README проекта с github.com/gilnett/learned_index_lab. Одним файлом markdown: README.md.

Learned Index Lab: Modern Search Paradigms in Rust

CI Crates.io Docs.rs License: Apache-2.0 Buy Me a Coffee GitHub Sponsors

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

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

Benchmark Summary (v0.4.0 Consolidated Results)

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.


Reproducibility & Verification

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

Documentation Index


References

Technical Articles & Deep Dives

Seminal Research Papers

Reference Codebases & Implementations

Industry Storage Engines & Analytical Systems


License

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

learned_index_lab (gilnett/learned_index_lab)

Ищем в базе…

Что это такое?Это реализация PGM-индекса (Piecewise Geometric Model learned index) на чистом Rust без внешних зависимостей, а также набор бенчмарков, который сравнивает её со стандартным BTreeMap, бинарным поиском по плоскому срезу и раскладкой Eytzinger, учитывающей особенности кэша.
Это крейт, который можно подключить к своему коду, или только отчёт с бенчмарками?И то, и другое: в репозитории есть настоящая реализация PGM-индекса, которую можно использовать, а также полноценный стенд сравнительных бенчмарков, который измеряет её против трёх других структур поиска.
Как самому запустить бенчмарки?Склонируйте репозиторий и соберите и запустите его в режиме release, так как все опубликованные цифры были измерены с --release на целевом железе.
Нужны ли мне внешние крейты, чтобы это использовать?Нет, это явно сделано как реализация на чистом Rust без внешних зависимостей.
Это официальная реализация PGM-индекса от его авторов?Нет. Это независимая реимплементация с нуля («clean-room») на безопасном Rust, отдельная от официальной эталонной реализации на C++ от команды Пизанского университета.
Насколько PGM-Index экономнее по памяти по сравнению с BTreeMap?Для миллиона ключей PGM-Index занимает около 21,1 КБ, тогда как BTreeMap — примерно 45,78 МБ, то есть экономия составляет более 99,9%.
Насколько он быстрее обычного поиска в BTreeMap?В сводном бенчмарке версии v0.3.0 PGM-Index показал скорость поиска примерно в 1,93 раза выше, чем у BTreeMap, раскладка Eytzinger — в 2,02 раза, а бинарный поиск по плоскому массиву — лишь в 1,20 раза.
На каких распределениях ключей тестируется бенчмарк?Три типа нагрузки: Dense Time-Series, Uniform Sparse и Heavy-Tailed Lognormal. Каждый запускается 30 независимых раз с барьером вытеснения кэша 32 МБ между этапами.
Кто впервые предложил идею PGM-индекса?Learned indexes были представлены Краской и соавторами (MIT/Google, SIGMOD 2018), а сам PGM-индекс изобрели Паоло Феррагина и Джорджо Виньерра в Пизанском университете (PVLDB 2020).
Какие есть похожие проекты?bbtree, goose, ANE, ir, spinel, explaindb, kividb, conc
Автор
gilnett
Размер
0.2 MB
Звёзды
166
Возраст
1 мес
Коммиты · 90 дней