Benchmark

Synthetic social graph, 139,093 triples (20k people in ~200 communities, ~5 knows edges each + age/name literals). Generated by scripts/gen_graph.py, measured by scripts/bench.sh, run in the dev container (release build, Rust 1.92). Query timings use the compiled binary directly (target/release/rete), so they exclude cargo overhead.

Size

.rete is ~2.3× the size of gzip while being queryable in place and over HTTP ranges (gzip answers no query without a full download + scan). As of format v0.4 it stores all six permutation indexes (SPO/POS/OSP/SOP/PSO/OPS) — each triple stored 6× — plus the dictionary and the small pyramid summary; that is what roughly doubled the file versus the earlier three-permutation v0.3 (715,959 bytes), and the payoff is that any triple pattern — not just the three canonical leads — resolves to a contiguous scan with its bound components leading, which also unlocks sort-merge joins. Per-community tiles remain out of the default file because they duplicate every triple; exact single-pattern range routing fetches one selected permutation payload instead of the whole index container, while physical community-tile directories are the next storage step.

Build

Result: 3 pyramid levels, 137,512 quads, 40,063 terms. (Caching the dictionary section metadata cut build time ~3.4× — see finding 1.)

Build memory (big graphs)

The build's peak RAM is dominated by the raw string statements (every term an owned String, heavily duplicated), which are redundant with the dictionary once interned. Stream-parsing the file (the whole text is never resident) and dropping the string statements right after encoding them to id-triples — before the pyramid + index phases — cuts the peak. On a 3 M-triple / 189 MB N-Triples build (synthetic, scripts-style entities with type/label/edges):

Output is byte-identical. Reproduce the phase-by-phase heap profile with cargo run --release -p rete-bench -- --build-mem <file.nt> — it snapshots the live heap (exact, via a counting allocator) after parse, dictionary, encode, the drop, pyramid, index, and write.

Build time (big graphs)

The build is dominated by the Louvain community pyramid — ~91% of wall-clock on the 3 M-triple build. Its local-moving inner loop now uses a reusable dense scratch (community → edge-weight + touched-list reset) instead of a per-node HashMap, with unchanged accumulation order and candidate scan, so the partition and the file content hash are byte-identical. Set RETE_BUILD_TIMING=1 on rete build for the per-phase breakdown.

A parallel Louvain would not be byte-identical (the partition depends on the sequential move order), so the pyramid stays single-threaded; the six index permutations and the dictionary/permutation sorts already use all cores (rayon).

Query result serialization (the WASM hot path)

A query's result is returned to the browser as a JSON string. Writing that envelope directly into a String (rete_core::results_envelope_json) instead of building a serde_json::Value tree and stringifying it dominates the cost on a large result. On a 500k-row SELECT (27 MB JSON), profiled with cargo run --release -p rete-bench -- --query-mem:

~13× less peak heap, ~10× faster, byte-identical JSON (a unit test pins the escaping to serde_json). For reference the query itself (eval_query) was 290 MiB / 344 ms — i.e. the old serializer cost more than the query. On the bounded WASM heap the 670 MiB peak was an OOM risk for big results.

Query latency (end-to-end: open + decompress + evaluate)

5-run averages of the compiled binary in the dev container (includes process startup each run; format v0.4, six permutations).

Every dictionary lookup and triple-block decode is bounds-checked (slice.get(..)? instead of raw indexing) so the reader cannot panic on malformed input — a few percent on the resolution-heavy hot path, and worth it (see finding 5). Resolution-light queries (triple pattern, summary) are unaffected.

HTTP range

A point query over HTTP is bounded, PMTiles-style. The full SPARQL URL path still opens the broad index section, but query-url and rete cost now have an exact single-pattern route: header + dictionary + one selected permutation payload. The progressive path is cheaper still for summary-safe queries: fetching just the coarse community graph (summary-url) reads only the header + dictionary + summary — e.g. 2.2 KB of a 15.6 KB file (14%) in 3 requests, the index never fetched — the "overview first, drill down later" promise.

Scaling

At 347,884 triples (2.5× the table above) everything scales ~linearly, with no pathological blowup: build 890 ms, triple query 54 ms, property path 103 ms, GROUP BY 261 ms, predicate totals 26 ms (summary stays cheap regardless of size), file 3.31 MB (same ~6.4× vs raw / ~2.3× vs gzip ratios as the table above).

The pyramid: cost vs benefit

A .rete carries two pyramidal structures with very different economics. This measures both, against --no-pyramid, on a typed subClassOf ontology fixture (dev/gen_ontology_demo.py, scaled by entity count).

Bytes — file overhead, the growing super-edge summary, and what each read tier fetches over HTTP (q ±pyr = a node-selective query with / without the pyramid):

Time (release build; median) — what the pyramid costs to build (Louvain community detection + schema rollup, vs --no-pyramid) and how fast each read is:

What the numbers say:

• The community super-edge summary scales with the graph — in bytes (super-edges 1.4k → 8.6k; summary-url 17 KB → 116 KB) and in time (the Louvain build cost is super-linear: +19 ms → +999 ms, ~4× the --no-pyramid build at 137k triples).
• It gives node-selective lazy queries nothing — q +pyr and q −pyr are byte-for-byte identical (43,823 == 43,823, …). For pure selective serving the pyramid is overhead; --no-pyramid is smaller and builds far faster.
• The schema pyramid is the bounded one — its size and read cost track the ontology, not the graph, so the leveled type/relation legend stays cheap at any scale. The flat-cost champion is the card (card-url ≈ 33 KB and ≈ 20 ms read at every size — it skips the dictionary and super-edges entirely).

Rule of thumb: keep the pyramid for index-free overview / exploration; build with --no-pyramid when you only serve selective queries at scale (smaller file, ~4× faster build, identical query latency). See the Semantic zoom guide for the schema-pyramid side of this. Repro: dev/bench_pyramid_value.sh (bytes) and dev/bench_pyramid_time.sh (time).

Coherence checking: tier costs

How much of a remote .rete each coherence check actually fetches, as the graph grows. A synthetic medical ontology — a fixed T-Box with a planted unsatisfiable class (:Relapsed ⊑ :Healthy and ⊑ :Sick, which are owl:disjointWith) plus a few instance-level clashes — at increasing instance counts, measured through a CountingReader over the file image. Repro: cargo run --release --example coherence_bench [n …].

The three tiers find different defects, by design: Tier-0 finds the schema-level unsatisfiable class (1 point) from the ontology alone; Tier-1/Tier-2 also find the instance-level disjoint clashes (3 points). So Tier-0 is a fast "is the ontology coherent?" gate, and Tier-1/2 answer "is the data coherent?".

The headline: Tier-0 reads ~1–8 KB in 2 range requests at any graph size — 8.1 KB of a 48.8 MB file (0.017%), sub-0.1 ms. The check-an-ontology's-coherence-from- a-few-KB-of-a-multi-GB-file claim holds. Tier-1 (selective) is the practical instance-coherence check: it faults only the rdf:type + T-Box tiles — 346 KB of 9.4 MB at 100k, 1.4 MB of 48.8 MB at 500k — while Tier-2 reads the whole graph.

Three fixes this benchmark drove

• detect_inconsistencies was O(types²). The disjoint-class check looped over every pair of rdf:type triples in the whole graph (~4.3 s at 10k instances). Grouping each individual's class set first and checking only the pairs within one individual makes it ~linear: Tier-1 4320 ms → 54 ms, Tier-2 4607 ms → 186 ms at 10k. (The functional-property check had the same shape and got the same fix.)
• Tier-0 was reading the whole dictionary. check_schema went through SummaryView, which fetches the dictionary to label predicates — but coherence needs none of it (the schema pyramid carries its own class-string table). A dictionary-free read_schema_coherence_ranged cut Tier-0 from 20.9 KB → ~2 KB at 10k.
• Tier-0 then still scaled with the community summary. The schema pyramid is bounded by the ontology, but it shared the pyramid-meta section with the community super-edge summary, which grows with the entity count (every labelled node is a vertex) — so reading the whole pyramid-meta cost 6.7 MB at 100k, 36 MB at 500k. The fix: the writer now records the trailing schema block's byte length in the header (the 4 previously-reserved bytes), so a reader fetches only that block. Tier-0 dropped to a flat 8.1 KB — a ~4400× cut at 500k. Backward-compatible: a file without the header field (schema_meta_len == 0) falls back to the whole-section read, and a typeless file's header byte stays 0, so it remains byte-identical.

Comparison vs Oxigraph (real OpenCitations network)

Dataset: the real OpenCitations citation network for the AlphaFold paper (Nature 2021), enriched with disciplines, authors, venues and citation counts (539,246 triples loaded into both engines)

This pits rete (a queryable file) against Oxigraph (a full in-memory triplestore with a mature SPARQL planner). Honest summary: rete opens much faster because its indexes are prebuilt in the file, wins several scan/aggregate shapes, still loses where Oxigraph can stream, stop early, or apply a mature planner, and wins decisively on multi-source reachability.

This section is generated from docs/benchmark-opencitations.json with scripts/render_benchmark_doc.py. Latest run: 2026-06-15. Oxigraph 0.5, in-memory store (no RocksDB). Machine: 32 logical cores.

Load / open (one-time)

Process peak RSS after both loads (VmHWM): 207 MiB.

rete's "load" just maps a file whose dictionary + permutation indexes already exist on disk; Oxigraph parses the triples and builds its indexes on every startup. This is the format's core promise: publish once, open instantly, query in place.

SPARQL operator coverage (eager, lazy range-read, and Oxigraph)

24 queries spanning supported forms and operators, on three engines: rete eager (Rete::open, whole file in memory), rete lazy (Rete::open_ranged_lazy — a fresh cold open + HTTP-range-style reads per query, the path a browser/remote client runs), and Oxigraph (in-memory). Row counts are a cross-engine correctness check across the language surface, not just a speed race. Median ±sd of 5 warm runs. lazy fetched is the bytes that one query pulled from the file image — the rest is never touched.

24 / 24 identical row counts across SELECT/ASK/CONSTRUCT/DESCRIBE, algebra operators, filters/functions, property paths, and aggregates.

Reading the times honestly:

• rete now wins or ties the large majority of shapes: aggregates, GROUP BY, DISTINCT, path closures, sorted pagination (top-k), and large UNION/VALUES/MINUS results. The engine evaluates as a lazy pipeline over integer slot rows, switches to index-nested-loop probes under small LIMIT/ASK demand, and resolves terms only at projection. A hybrid BGP join also switches to per-row index probes mid-join once the running intermediate is small (so a star/snowflake's trailing ?x rdf:type C checks cost a few lookups, not a full-extent scan), and never seeds a join from a class enumeration — together cutting the LUBM snowflakes Q4 ~14x and Q7 ~12x. The index stores all six permutations (format v0.4), so any join key can be streamed pre-sorted for a sort-merge join; at these sizes the hash/probe joins already win, so the merge path is neutral here — it pays off at much larger scale, for ~2x the index payload.
• Oxigraph keeps an edge on REGEX scans whose pattern needs the real regex engine (rete's regex-lite has no literal prefilter; literal patterns use a substring fast path) and, by fractions of a millisecond, on ASK and the tightest LIMIT joins — floor effects, not the orders-of-magnitude gaps from before the engine rework.
• The lazy range-read engine — what a browser or remote client runs over HTTP — adds only a ~1 ms cold-open tax over eager while fetching single-digit-percent of the file per query (here ~50–205 KB of a 2.8 MB file), and still beats in-memory Oxigraph on most shapes. Querying a .rete where it sits (S3 / HTTP, no server) is not a latency compromise.

Batch transitive reachability - coauthor+ from 300 seeds

"From each seed author, who is reachable through co-authorship?" rete exposes this as a dedicated primitive (rete reach, batch_reach_*); on Oxigraph it is a coauthor+ property path evaluated per seed.

rete serial and parallel both reached 1,636,200 nodes; Oxigraph touched 1,636,200 result cells. The dedicated parallel primitive is a different abstraction level from a general SPARQL property path, so read this as: use the right tool for multi-source reach.

Reproduce

# In the dev container (Docker). The OpenCitations + synthetic-enrichment data
# comes from scripts/fetch_opencitations.py + scripts/enrich.py (-> enriched-all.nt).
# Sanitize malformed compound-DOI IRIs so both engines load identical data:
grep -vE "<[^>]* [^>]*>" data/opencitations/enriched-all.nt \
  > data/opencitations/enriched-clean.nt
./target/release/rete build data/opencitations/enriched-clean.nt \
  -o data/opencitations/enriched-clean.rete

cargo build --release -p rete-bench
./target/release/rete-bench --json data/opencitations/enriched-clean.rete \
  data/opencitations/enriched-clean.nt 300 > /tmp/bench.json
# preserve the curated dataset note + run date from the existing JSON:
uv run python scripts/merge_bench_metadata.py /tmp/bench.json \
  docs/benchmark-opencitations.json --date $(date +%F)
uv run python scripts/render_benchmark_doc.py docs/benchmark-opencitations.json \
  --input docs/BENCHMARK.md --output docs/BENCHMARK.md
cargo run -p docgen

The rete-bench crate pulls in Oxigraph only for this comparison; its in-memory store needs no RocksDB/clang, so default-features = false keeps the build light.

LUBM-style benchmark (standard 14 queries)

The LUBM data model and its 14 standard queries, on identical pre-materialized data in both engines. LUBM(1): 93,139 generated + 26,007 RDFS/OWL-RL-materialized = 118,680 triples (.rete: 555,581 bytes).

Read the caveats: the generator is a faithful reimplementation of UBA's documented cardinalities, not the official Java tool, so counts are not comparable to published LUBM figures; inference is rete's RDFS/OWL-RL subset, applied up front to the data both engines load — so restriction-defined classes (Q12's Chair) are empty on both sides by construction. The correctness anchor is cross-engine row parity: 14 / 14 queries agree.

Reproduce: cargo run --release -p rete-bench -- --json --lubm 1 > docs/benchmark-lubm.json then re-render this doc.

Parallelism

A prototype data-parallel query evaluator (rete-core feature parallel, module parallel.rs, behind rayon — off by default, never compiled into wasm) splits decomposable work across communities/seeds and harmonizes the partials. Every parallel workload ships with a serial reference that produces a bit-identical result; the benchmark asserts serial == parallel (RESULTS MATCH) before trusting any timing. Numbers below are from cargo run --release -p rete-core --example parallel_bench --features parallel in the dev container, best-of-N after a warm-up.

Machine: 32 cores (available_parallelism = 32, rayon = 32 threads).

137,499 triples (20k people, 184 communities)

343,844 triples (50k people, 346 communities) — 2.5× scale

Honest analysis

• Batch reachability is the clear win (14–15×). N independent single-source BFS traversals over a shared read-only adjacency map are embarrassingly parallel — one rayon task per seed, no shared mutable state, no merge step. This is the realistic use case: multi-source impact analysis ("what does each of these 512 nodes transitively reach?"). It does not hit linear 32× because the per-seed reach sets are huge (~20k–50k nodes each) and the work per seed varies, so memory bandwidth and load imbalance cap the gain — but a 14–15× wall-clock cut on a 32-core box is real and reproducible. This workload is shipped as a command: rete reach --parallel (see the CLI reference).
• Per-subject out-degree barely moves (1.01× at 137k, 1.63× at 344k). The per-community map-build parallelizes, but the harmonize — merging hundreds of BTreeMaps into one — is serial in the reduce and dominates when the per-tile work is tiny. It only starts to pay (1.63×) once each tile carries enough triples to amortize the merge. This is textbook Amdahl: the serial merge fraction caps the speedup.
• Predicate count is the "cheap scan" caveat, reported plainly. At 137k the whole scan is ~2 ms, so rayon's fork/join overhead is on the same order as the work and the speedup is noise-dominated (1.57×). It looks better than it should because the comparison isn't perfectly apples-to-apples: the serial reference walks the engine's index (match_ids, which materializes a Vec of every match), while the parallel side filters pre-tiled in-memory triples. Lesson: a sub-millisecond-per-core workload is not worth parallelizing — the tiling + dispatch overhead eats the gain, and any apparent win is fragile.
• This is CPU-side only. The HTTP/range query path is I/O-bound (latency is in the network round-trips, not the CPU), so threading the evaluator does not help there. And wasm has no threads at all — which is exactly why parallel is an opt-in native feature and the wasm crate builds with --no-default-features (verified: rayon is never compiled for wasm).

Conclusion on "split across communities + harmonize": it helps when (a) the per-partition work is substantial relative to fork/join + merge overhead, and (b) the harmonize step is cheap or itself parallel. Batch reachability nails both; per-community aggregations only pay off at scale once the serial merge is amortized; cheap single scans should stay serial.