Repository navigation
perf: checkpoint() is O(graph size) and flat in dirty bytes — it rebuilds all four covering indexes every call #315
Description
Summary
checkpoint() costs the same whether one fact is dirty or five thousand, and that cost scales with the total size of the graph rather than with what changed. For a workload that checkpoints periodically during a long write run, total cost is N_checkpoints × avg_graph_size — a super-linear term in the run.
Measured downstream in temporal_reasoning (project-minigraf/temporal_reasoning#241), where it was the single largest call site in at-scale ingestion: ~0.69 s per checkpoint against a 126 MB graph, roughly half of total ingestion wall clock.
Measurements
Standalone harness, checkpoint immediately after N dirty facts, same graph:
| facts in graph | graph MB | checkpoint after 1 dirty fact | checkpoint after 5,000 dirty facts |
|---|---|---|---|
| 5,000 | 1.7 | 7.2 ms | 10.3 ms |
| 20,000 | 6.6 | 33.1 ms | 37.6 ms |
| 50,000 | 16.5 | 80.8 ms | 82.0 ms |
~4.9 ms/MB of graph, essentially independent of dirty volume. Extrapolates to ~617 ms at 126 MB, which reproduces the 0.69 s/call figure observed in a completely separate harness.
The flatness is the striking part: at 50,000 facts, checkpointing after one fact costs 98% of what checkpointing after 5,000 costs.
Mechanism
Minigraf::do_checkpoint (src/db.rs:592) unconditionally calls pfs.force_dirty() and then pfs.save().
PersistentFactStorage::save (src/storage/persistent_facts.rs:842) then streams every entry of all four covering indexes off disk before rebuilding them:
let committed_eavt: Vec<(EavtKey, FactRef)> = if curr_header.eavt_root_page != 0 {
stream_all_entries(curr_header.eavt_root_page, &*backend, &self.page_cache)?
} …
// same for aevt, avet, vaetSo each checkpoint reads and rewrites EAVT + AEVT + AVET + VAET in full. The index rebuild dominates, which is exactly why the cost is proportional to graph size and flat in dirty bytes.
Why this matters
Any caller that checkpoints more than once over a growing graph pays N × size. The natural cadence — checkpoint per logical unit of work — is the worst case, and the cost grows as the graph does, so it degrades precisely as a dataset becomes interesting.
Two things make it easy to reach for that cadence:
- Checkpointing looks like a durability boundary. It is not — writes are already crash-durable via
<db>.wal, and a handle compacts on clean close. Verified by hard-killing a process (os._exit(9)) with 30,000 uncheckpointed facts: all 30,000 recovered on reopen. Batching trades reopen latency (~45 ms/MB of outstanding WAL), not data safety. - Nothing in the docs signals that the call is O(total size) rather than O(delta).
What we did downstream, and why it is a workaround
temporal_reasoning now holds checkpointing to a duty-cycle budget: after a checkpoint costing d seconds, the next is suppressed until d × (1/duty − 1) has elapsed. Because the wait scales with d, the fraction stays fixed as the graph grows, which removes the super-linear term rather than dividing it by a constant. Measured −22.9% on a same-day A/B over 629 commits, at 4.58% realised duty against a 5% budget.
That works, but every embedder needs to rediscover it, and it only rations a cost that is arguably avoidable.
Suggested direction
The question this issue exists to answer: must per-checkpoint cost grow with graph size, or is the full index rebuild avoidable?
Options worth weighing:
- Incremental index maintenance — apply only the delta to the on-disk B+trees instead of streaming and rebuilding all four. Biggest win, biggest change; the B+tree is already page-structured, so a targeted node update seems plausible.
- Drop the unconditional
force_dirty()— it exists for the WAL-replay path (facts loaded into memory without the write path being exercised). Scoping it to that case would let the existingdirtyshort-circuit do its job on the common path. - Document the complexity if it is inherent. Even without a code change, stating that
checkpoint()is O(graph size) and flat in dirty bytes — and that it is not a durability boundary — would stop callers reaching for a per-unit cadence.
Not urgent for us; the duty-cycle budget contains it. Filing because the mechanism is now understood and the measurements exist, rather than leaving it as downstream folklore.
Aside
The comment above the wal_entry_count == 0 && !pfs.is_dirty() guard in do_checkpoint cites "same-process double-opens (same PID bypasses the stale-lock check)" as one of the edge cases it closes. That is no longer reachable as of #304/#314 — a same-process second open is now refused outright. The guard is still worth keeping for the other cases; the rationale just needs a trim.
Filed from project-minigraf/temporal_reasoning#241, which is closed in favour of this.
Activity
perf: checkpoint copies untouched index leaves instead of rebuilding …
adityamukho commentedon Sep 26, 2026
Mitigated by #402. Checkpoint after one new fact now takes 26.3 ms on a 100k-fact file (was 246 ms) and 4.0 ms at 10k facts (was 23.9 ms). Index leaves that receive no new entries are copied verbatim instead of being decoded and re-encoded, and unchanged fact pages are no longer re-hashed. The
checkpoint()docs now state that a checkpoint is not a durability boundary, and the outdated guard comment is trimmed as the Aside suggested.On file format v7, checkpoint cost still grows with graph size, because index pages are copied on every checkpoint. Checkpoints proportional to the change alone need copy-on-write pages. That is tracked in #374 for v3.0.0; see #374 (comment).
docs(roadmap): make v2.0.2 the final v2.x release, split v3.0.0/v3.1.0 (
Merge pull request #412 from project-minigraf/merge/main-into-v3
release: v2.0.2 — final planned v2.x release