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). Stable format generation 1 stores six permutation indexes by default (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). The payoff is sort-merge joins, not routing: SPO/POS/OSP already resolve any triple pattern to a contiguous scan with its bound components leading, at the same longest bound prefix the full six achieve, and the extra three only supply a stream already sorted on the join key. rete build --permutations 3 drops them and gets the smaller file back — measured below. 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; stable format generation 1, 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).

Billion-triple scale: bounded-memory queries (DataCite)

The 52 GB datacite.rete — 9.83 B unique triples, 1.885 B dictionary terms, the largest .rete built to date — is queryable on a small machine. Measured under hard Docker memory caps (--memory, swap disabled), file opened locally through the lazy range reader:

Aggregation folds rows through per-group accumulators (O(groups) resident) and the open path reads only section directories, so the memory that matters is the 256 MiB block cache plus the group table — not the file size, the dictionary, or the match count.

One diagnostic worth writing down: if every query on a large file OOMs, with wall time scaling linearly with the memory cap at a constant ~150 MB/s, the binary is reading the whole file — the lazy-local routing is missing (builds older than the 0.3.0 line; check strings <binary> | grep RETE_LOCAL_LAZY_ABOVE_MB). That slope is the cap filling at disk speed, not the query working.

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

The merge-join permutations: cost vs benefit

rete build --permutations 3 writes SPO, POS and OSP and drops SOP, PSO and OPS. Those three exist only to hand a sort-merge join two streams already sorted on the join key; the first three decide routing, and they tie the longest bound prefix on all eight triple-pattern shapes — so a 3-permutation file answers every query with the same rows, from the same tiles. The default is six.

Two datasets, each built both ways from its local source, --no-pyramid (the shape 89% of published bytes have — they came from the external builder, which writes none). tree-city-inventory is short-term-heavy: its dictionary is 11% of the file. davidrumsey is literal-heavy: 27%. That ratio is what decides the saving, and the published corpus sits between them.

Bytes — per-permutation section sizes, from the container framing:

Build — wall time and true peak RSS (/proc/<pid>/status VmHWM, polled; getrusage(RUSAGE_CHILDREN).ru_maxrss is the max over all reaped children and reported 707 MB against a true 96 MB):

The in-RAM builder permutes, sorts and tiles all six in parallel, so halving the work barely moves the wall clock — it moves the RAM. The external builder sorts them one at a time, so there the time saving is real. Both paths write byte-identical files.

Query — each dataset's own catalog example queries, plus two constructed two-pattern joins, run cold over HTTP against a local Range server (a fresh rete sparql-url per measurement, median of 3):

Every one of the 16 pairs returned the same row count.

What the numbers say:

• The merge join is worth something, and it is concentrated. Three of the sixteen queries — all tree-city, all the same shape — regress by 75%, 32% and 12%. The other thirteen are within ±10%, i.e. noise. There is no middle: a query either loses its merge seed or does not notice.
• The loss is CPU, not I/O. Every regressing query fetched fewer bytes and made fewer requests on the lean file. The hash table is what costs, so the gap would widen with faster storage and narrow over a slow link.
• The shape that loses it is ?s <p1> ?o1 . ?s <p2> ?o2 — two bound predicates sharing a subject. That needs a P*S order, and PSO is one of the three dropped. The object-shared twin needs POS, which is kept, and does not move. Exactly three of the twelve (bound-set, join-column) shapes lose their co-sorted stream; the other nine are unaffected.
• A lean file always fetches less, 2.0%–23.3% here — the tile directories of three absent sections are never read at open.
• Nothing else changes. Same rows, same routing, same tiles; the difference is a join strategy and ~40% of the bytes.

Rule of thumb: keep the default six for anything published, and for anything whose workload joins two bound predicates on a shared subject. Consider --permutations 3 for a lookup-and-follow workload — resolve an id, read its properties, follow a link — where the file is index-dominated and the storage or the transfer is what hurts. Measure first: rete cost reports the byte and request cost of a real query against either build.

Repro: dev/perms/{build_bench.sh,query_bench.py,sections.py,rangeserver.py} (gitignored; sources are data/tree-city-inventory/ and data/davidrumsey-maps/).

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 (the default), 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.