Repository navigation
8000
perf: evaluate bbtree for v3 pending indexes #762
Description
Question
Would bbtree improve Minigraf's in-memory pending index performance enough to justify adopting it or borrowing its techniques? Investigate this in v3.next with Minigraf-shaped benchmarks; this issue does not propose changing the durable index format.
Findings so far
- The published bbtree results are worth taking seriously: the author provides a benchmark harness, raw runs, and before/after integrations. They have not been reproduced against Minigraf. Headline comparisons (up to 5x versus
std::BTreeMapfor in-memory operations and 160–2,500x first answer after restart) cannot be assumed to transfer to whole Datalog queries. - On
v3, committed EAVT/AEVT/AVET/VAET and DICT indexes are byte-keyed, 4 KiB, page-cache-backed B+trees. Checkpoints update touched paths with copy-on-write pages, per-page CRCs, and an atomic meta-page commit (src/storage/btree.rs,persistent_facts.rs). The bbtree-mmap API is read-only: changing its map produces a new file. Its first-query comparison loads/rebuildsstd::BTreeMapfrom disk, whereas Minigraf already reads indexes on demand. Minigraf's v3 performance envelope reports ~0.12 ms open and ~3 MiB RSS after opening a checkpointed 10M-fact file. - The realistic swap candidate is the pending store:
v3/src/storage/index.rshas twostd::BTreeMap<EavtKey/AevtKey, usize>indexes for uncheckpointed facts.bbtree::unsync::BBTreeMapis the relevant variant to compare. The shared/concurrent bbtree's scaling claims are less directly applicable because Minigraf maintains facts and pending indexes together under its snapshot locks. - The v3 performance envelope attributes expensive query shapes largely to materialization, DICT lookups, and execution work, with streaming-engine changes already addressing major cases. An in-memory map speedup therefore needs an end-to-end check; a microbenchmark alone cannot establish user-visible improvement.
- A committed-index replacement would have to preserve the single
.graphformat, bounded memory, cross-platform behavior, page checksums, copy-on-write durability, migrations, and snapshot semantics. It is not a drop-in dependency swap and would need separate evidence and a major-format plan.
Investigation
- Profile representative v3 writes, uncheckpointed lookups/ranges, WAL replay, and checkpoints to establish how much time and memory the pending maps consume. Stop if they are not a material bottleneck.
- In an isolated, test-only benchmark, compare
std::BTreeMapwithbbtree::unsync::BBTreeMapusing actual EAVT/AEVT key shapes and access patterns. Include small and large pending sets, random and clustered entities, inserts, bounded range scans, and checkpoint iteration. Account for key encoding/adapter costs and any bbtree-specific key optimization. - If the isolated result is promising, compare end-to-end transaction throughput, pending point/range query latency (p50/p99), checkpoint and WAL-replay time, peak RSS, and release binary size on the same fixture and build profile. Keep correctness checks against the existing reference/soak tests before considering adoption.
- Record the measurements, hardware, versions, and limitations. Recommend either no change, a focused pending-index change, or one specific idea to apply to Minigraf's existing page format. Do not infer a benefit for the committed tree from the in-memory or read-only mmap benchmarks.
Done when
Publish a short, reproducible report with profiles, comparisons, integration costs, and a decision. Any implementation should be a separate issue after the measured benefit and philosophy fit are clear.
This is a test-only investigation aligned with PHILOSOPHY.md's reliability-first, small-binary, portable, single-file design.
Activity