Live benchmark history: bencher.dev/console/projects/minigraf/perf

Benchmark results for Minigraf. Core query benchmarks were updated in v0.13.1 (Phase 7.4 — query path snapshot fix). New benchmark groups for window functions, temporal metadata, UDFs, count-distinct, and regex filter added in v0.17.0 (Phase 7.8). Negation, disjunction, aggregation, and expression benchmarks were first run on v0.13.0 and selectively re-run on v0.13.1.

Benchmarks were run with Criterion 0.8. Each benchmark group is described below.

All times are per-call latency — the time for a single operation (one insert, one query, one open, etc.), not a total or cumulative time.

Criterion measures this by running each operation repeatedly and computing a median:

1. Warm-up (3 s): the operation is run and discarded to let CPU caches and OS buffers reach steady state.
2. Measurement: Criterion collects N samples. For each sample it runs the operation M times (chosen automatically so the sample takes long enough to time accurately), records the total elapsed time, then divides by M to get a single per-call estimate.
3. Reported time: the median across all N samples. The median is used rather than the mean because it is robust to occasional slow outliers (OS scheduler jitter, CPU frequency scaling, etc.).

Sample counts vary by benchmark speed:

• Fast operations (inserts, ~µs): 100 samples (default) — thousands of iterations per sample.
• Slow operations (queries at large scale, recursion, concurrent scans): 10 samples — only a handful of iterations are feasible per sample.

The column headers (e.g. "1K facts", "10K facts") indicate the size of the database at the time the operation was measured, not how many operations were performed.

Measures per-fact insert latency at three dataset sizes (1K / 10K / 100K facts in the database at insert time).

Single-fact insert is constant across dataset sizes — the in-memory pending index is O(1) per insert.

File-backed insert latency is constant — writes go to the WAL sidecar, not the .graph file directly, so insert cost is independent of database size.

Measures single-query latency against databases pre-loaded with 1K / 10K / 100K / 1M facts.

10K point_entity updated in v0.13.1 (Phase 7.4 — snapshot fix, -61.5% vs pre-fix baseline of 22 ms, -45% vs Phase 6.5 v0.8.0). point_attribute and join_3pattern 10K numbers are from v0.8.0 and will be updated when re-benchmarked. 100K and 1M numbers are unchanged (from v0.8.0).

Query performance scales linearly with dataset size. The query executor resolves committed facts via the on-disk B+tree range scan and page cache, then filters in memory. Starting from Phase 7.4, the non-rules query path no longer rebuilds in-memory EAVT/AEVT/AVET/VAET indexes on each call — facts are passed as a pre-filtered Arc<[Fact]> slice. Range-scan selectivity is not yet exploited to skip non-matching facts — that optimisation is in the post-1.0 backlog (B+Tree Selective Lookup).

Time-travel queries have the same cost profile as plain queries — temporal filtering adds negligible overhead.

Recursive rule evaluation uses semi-naive fixed-point iteration. Deep chains scale super-linearly: each iteration must re-evaluate all intermediate facts. The semi-naive evaluator avoids redundant recomputation, but chain/depth_100 still requires ~100 iterations of growing intermediate tables.

Measures cold-open latency (loading a committed .graph file) and WAL replay latency.

Phase 6.5 improvement: v6 open no longer loads indexes into RAM. At 1M facts, open time dropped from 3.14 s → 1.31 s (2.4×). At 100K: 259 ms → 119 ms (2.2×). The remaining cost is dominated by WAL check plus page-cache warming on the first query.

At small sizes (1K), v6 open is slower than v5 (7.2 ms vs 1.83 ms) — the per-open overhead (header I/O, B+tree root setup, WAL check) is not amortised enough at 1K facts to overcome the benefit of not loading a tiny index.

Measures time to flush the WAL to committed .graph pages (including B+tree rebuild for all four indexes).

Checkpoint now includes a merge-sort of committed + pending entries and a B+tree rebuild across all four indexes (EAVT, AEVT, AVET, VAET). At 10K facts this is 11.8 ms — slightly faster than the v5 paged-blob serialisation (16.5 ms), as the B+tree writer makes fewer random-access passes.

Pre-loaded 10K-fact database. All threads operate concurrently.

serialized_writers at ≥4 threads was previously OOM-killed on this machine. With v6, facts are cleared from RAM after each checkpoint, so accumulated memory is much lower and all thread counts now complete.

Pre-loaded 10K-fact database.

Measures the post-filter pass overhead at different dataset sizes. 10% of entities carry a :banned true fact that the not clause filters on.

All 10K benchmarks were run with 100 samples. The O(N²) scaling is a known limitation of the current negation implementation (no hash-join in the inner filter loop).

10K not_scale updated in v0.13.1 (Phase 7.4 — snapshot fix, -12.1% vs pre-fix baseline of 7.95 s). not_join_scale and not_rule_body 10K numbers are from v0.13.0 and will be updated when re-benchmarked.

not_selectivity — fixed 10K DB, exclusion fraction swept from 0% to 100% (100 samples each):

The non-monotonic dip at 100%: when all entities are excluded, the negation check can short-circuit as soon as a matching banned fact is found (O(1) per binding), whereas the 0%–75% cases must exhaust the entire banned-entity scan before concluding "not found".

Measures or-expansion and or-join projection overhead. 25% of entities have :tag-a, 25% have :tag-b, 50% are untagged. All disjunction benchmarks use sample_size(10).

The 10K numbers reflect a known O(N²) characteristic in the current apply_or_clauses implementation: branches are evaluated over the full incoming binding set (seeded re-scan). or_rule_body avoids this because rules start from an empty binding, giving O(N) branch expansion.

10K or_scale updated in v0.13.1 (Phase 7.4 — change not statistically significant at p=0.36; disjunction is O(N²) and dominated by branch enumeration, not the index rebuild). Other 10K numbers are from v0.13.0.

or_selectivity — fixed 10K DB, fraction matching either branch swept from 0% to 100% (10 samples each):

Selectivity scales roughly linearly with match fraction: each additional 25% of matching entities adds ~20 s at 10K. This is consistent with the O(N × result_count) cost of branch union construction and deduplication.

Measures aggregation post-processing overhead. count_scale/sum_scale use the value-only fixture; grouped_count_scale/with_grouped_sum use a 10-department fixture (10 groups). All aggregation benchmarks use 100 samples.

10K count_scale updated in v0.13.1 (Phase 7.4 — snapshot fix, -64.7% vs pre-fix baseline of 27.5 ms). Other 10K numbers are from v0.13.0 and will be updated when re-benchmarked.

count and sum are O(N). grouped_count is slightly higher due to the two-pattern join ([?e :dept ?dept] × [?e :val ?v]). with_grouped_sum at 10K shows O(N²) scaling from the same two-pattern cross-product join — the planner currently lacks a hash-join step; this is tracked as a future optimisation.

Measures the expression evaluation pass overhead. filter_scale keeps half of entities; binding_scale binds a new variable for every row; binding_into_agg pipes the bound variable into a sum aggregate. All 100 samples; all show clean O(N) scaling.

Measures window function evaluation overhead (running aggregates, ranking functions). Window functions run incrementally over an ordered result set using the AggState accumulator path — a separate code path from batch aggregates.

Window functions are O(N log N) due to sorting overhead. Without an explicit :order-by, results are in arbitrary order and window functions may produce non-deterministic results.

Measures pseudo-attribute binding overhead (?tx-time, ?valid-from, ?valid-to). These require extra projection work per result row.

Temporal metadata adds ~1 column of projection overhead per row — negligible compared to the underlying query cost.

Measures the closure dispatch overhead for user-defined aggregates and predicates vs. built-in functions.

UDF dispatch adds ~1 function pointer indirection per aggregation step or predicate evaluation. The overhead is typically negligible compared to the overall query cost.

Measures regex evaluation overhead via the matches? predicate. Regexes are precompiled at parse time.

Measures wall-clock latency of N simultaneous EAVT range scans against a committed B+tree with 10K facts.

Scaling: 2→4 threads is ~1.5× (good), 4→8 threads is ~1.9× (improved from 2.2× before per-page locking). The backend Mutex is now held only for the duration of a single read_page call on a cache miss — on cache-warm pages no lock is acquired at all, allowing concurrent readers to proceed in parallel. Remaining contention at 8 threads reflects cold-page I/O serialisation, which is unavoidable and correct.

Peak heap consumption during examples/memory_profile (insert N facts + one query + checkpoint). Measured with heaptrack.

Phase 6.5 improvement: v6 no longer holds the full index in RAM after checkpoint — indexes live on disk and are paged in on demand via the LRU cache. At 1M facts, peak heap dropped from 1.33 GB → 1.05 GB (~21%). At 100K: 135.7 MB → 109.4 MB (~19%).

Phase 7.4 eliminated the per-query 4-index rebuild (load_fact loop — BTreeMap insertions for EAVT/AEVT/AVET/VAET) in the non-rules query path. filter_facts_for_query now returns an Arc<[Fact]> slice instead of constructing a FactStorage; the rules path still builds a FactStorage for StratifiedEvaluator.

Negation and disjunction improvements are smaller because those paths are O(N²) and dominated by the inner binding-loop cost, not the index rebuild. The rules-path index rebuild is tracked in the post-1.0 backlog.

• Query scan is O(facts): Queries resolve all facts matching the range scan, then filter in memory. The per-query index rebuild (EAVT/AEVT/AVET/VAET) was eliminated in Phase 7.4 for the non-rules path. Index-based predicate pushdown for sub-linear lookups is in the post-1.0 backlog (B+Tree Selective Lookup).
• Backend mutex held on cache-cold page reads: Concurrent B+tree scans serialise only when a page must be loaded from disk (cache miss). Cache-warm reads are fully parallel. Further per-page I/O parallelism is deferred to Phase 8.
• 1M recursion not benchmarked: chain/depth_100 takes 16 s; chain/depth_1000 was not run.

# Run all Criterion benchmarks (HTML report in target/criterion/)
cargo bench

# Run a specific group
cargo bench -- "insert"
cargo bench -- "concurrent_btree_scan"

# Run heaptrack memory profile (requires heaptrack installed)
cargo build --release --example memory_profile
heaptrack ./target/release/examples/memory_profile 100000
heaptrack_print -f heaptrack.memory_profile.*.zst --merge-backtraces=0