Phase 8 (v0.20.0–v1.0.0) added cross-platform targets: Browser WASM, WASI, Android, iOS, Python, Node.js, Java, and C bindings. No changes were made to the native query or storage path. All benchmark numbers below are unchanged from Phase 7 (v0.19.0).

Live benchmark history: https://bencher.dev/perf/minigraf/plots

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. Throughput reporting (facts/sec, aggregate ops/sec), retraction benchmarks, prepared query benchmarks, and checkpoint@1M added in v0.20.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.

Some benchmarks also report throughput (elements/second, shown as K elem/s or elem/s):

• Batch inserts / retractions: throughput is facts/second — Throughput::Elements(100) over a 100-fact batch, enabling apples-to-apples comparison with single-fact inserts.
• Concurrent groups: throughput is aggregate ops/second across all threads combined — Throughput::Elements(n_threads) per Criterion iteration. This answers "does total system throughput scale with thread count?" independently of per-thread latency.

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.

batch_100 with Throughput::Elements(100) — reports facts/sec for a 100-fact batch at each DB scale (v0.20.1).

Throughput is essentially flat across DB sizes for both backends — confirms the O(1)-per-insert property of the WAL path. In-memory is ~10% faster than file-backed; the difference is WAL fsync overhead. At 1M facts, file-backed throughput is slightly higher than at 100K due to batch amortisation over a warmer path (OS page cache pre-warmed from the populate phase).

Measures (retract [...]) performance — a first-class bi-temporal operation that logically deletes facts by asserting asserted=false entries. Uses batch_100 (100 retractions per call) with Throughput::Elements(100) to report facts/sec.

Retraction throughput matches batch insert throughput (~130–148 K facts/sec) and is equally flat across DB sizes. The retraction path writes a asserted=false WAL entry per fact — structurally identical to an insert — so parity with insertion cost is expected. The slight decline at 1M reflects a larger in-memory pending index during the measurement window.

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.

PreparedQuery (parse-once/execute-many via db.prepare(...) + pq.execute(...)) moves parser overhead out of the hot path. Relevant for AI agents that issue the same query pattern repeatedly with different bind values (v0.20.1).

value_lookup scans all facts for a matching :val attribute (AVET index path); threshold_filter additionally evaluates an expression predicate on every binding. Both scale linearly with DB size. The parse step is paid once at prepare time and is not reflected in these numbers.

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).

100K and 1M variants added in v0.20.1 but not yet run on this machine (each iteration requires a fresh 100K/1M-fact WAL setup — setup cost dominates at sample_size(10)). Numbers will be added in the next benchmark pass.

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.

All threads operate concurrently. Throughput = aggregate ops/sec across all threads (v0.20.1).

At 10K, throughput scales nearly linearly from 4→8 threads (198→207 q/s, +4.5%), then plateaus at 16 threads — the in-memory RwLock becomes the bottleneck. At 100K, throughput stays flat across thread counts because per-query scan cost dominates lock overhead.

Mixed read/write workload shows higher aggregate throughput than pure readers at 10K — the single writer holds the write lock only during WAL append, allowing readers to proceed concurrently most of the time.

Writes are serialized by design (one writer at a time). Throughput measures total committed writes/sec across all competing threads.

Aggregate write throughput drops ~15% from 2→4 threads (lock contention overhead), then stays flat at 4–16 threads — confirms serialised writes with negligible per-thread overhead. serialized_writers at ≥4 threads was previously OOM-killed on this machine; v6 clearing facts from RAM after checkpoint fixed that.

File-backed DB — reads go through the LRU page cache; writes append to the WAL sidecar. Throughput = aggregate ops/sec across all threads (v0.20.1).

File-backed read throughput is ~15–25% lower than in-memory at equivalent thread counts, due to page-cache locking on cache misses. At 10K the 4→8 thread scaling degrades (164→141 q/s) — the page-cache RwLock becomes contended when all pages are hot and threads compete on every read. At 100K throughput stays roughly flat (page-cache warm after first scan iteration).

Mixed workload throughput at 10K stays flat 4→8 threads (165→164 q/s) vs. the degradation seen in pure-readers — the writer holding the write lock briefly gives readers a chance to be scheduled without cache contention.

File-backed write throughput (~68–77 K writes/sec) is ~30% lower than in-memory (~100–118 K/s) — the WAL fsync on each commit dominates. Throughput declines ~12% from 2→4 threads then stabilises, matching the in-memory contention pattern.

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 N simultaneous EAVT range scans against a fully committed (checkpointed) B+tree — no WAL involvement. Throughput = aggregate queries/sec across all threads (v0.20.1).

At 10K, throughput nearly doubles from 2→4 threads (85→162 q/s, +90%) — strong scaling on cache-warm pages. At 8 threads it drops back to 140 q/s — the per-page read Mutex becomes contended when all threads hit the same B+tree nodes simultaneously. At 100K the pattern repeats: 2→4 is +64%, then 4→8 degrades slightly as cold-page I/O serialisation limits further scaling.

The backend Mutex is held only for the duration of a single read_page call on a cache miss — cache-warm reads acquire no lock, allowing true parallel reads. Remaining contention at 8 threads reflects unavoidable cold-page I/O serialisation.

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