sparql-query · git:20260726.5521577 · 2026-07-26 · sha256 e708e6be4417e069
sparql-query git:20260726.5521577A
Immutable. This exact content is served forever at /api/v1/blob/e708e6be4417e069.
---
name: sparql-query
description: Run SPARQL 1.1/1.2 queries (SELECT/ASK/CONSTRUCT/DESCRIBE) and UPDATE against the sparq RDF engine in Rust — load RDF into a sparq_core::Graph, then use sparq_engine::{query, ask, query_json, count, construct, describe, update}; covers property paths, RDF 1.2 triple terms, aggregates/subqueries, custom extension functions (query_with_functions / FunctionRegistry), prepared queries, query budgets/timeouts, named-graph dataset views, and EXPLAIN. Use when an agent or developer needs to embed/execute SPARQL over sparq.
---
# sparq SPARQL query surface
`sparq-engine` is the SPARQL query/update engine over `sparq-core::Graph` (a dictionary-encoded,
permutation-indexed in-memory RDF store). You load RDF into a `Graph`, then call free functions in
`sparq_engine` to run SELECT/ASK/CONSTRUCT/DESCRIBE and SPARQL Update. Results come back either as a
typed `QueryResult` (rows of `Option<oxrdf::Term>`) or directly as a SPARQL-1.1-JSON string.
## Quickstart
`Cargo.toml`:
```toml
[dependencies]
sparq-core = "0.1"
sparq-engine = "0.1" # default features: parallel, regex, digest
oxrdf = { version = "0.3", features = ["rdf-12"] } # only if you build Terms yourself
```
```rust
use sparq_core::Graph;
let ttl = r#"@prefix ex: <http://ex/> .
ex:alice ex:knows ex:bob ; ex:age 30 ; ex:name "Alice" .
ex:bob ex:knows ex:carol ; ex:age 25 ; ex:name "Bob" ."#;
// Load RDF: "turtle" | "ntriples" | "nquads" | "trig".
let g = Graph::load_str(ttl, "turtle").unwrap();
// SELECT -> typed rows.
let r = sparq_engine::query(
&g,
"PREFIX ex: <http://ex/> SELECT ?s ?age WHERE { ?s ex:age ?age . FILTER(?age > 28) }",
).unwrap();
for row in &r.rows {
// r.vars: Vec<Variable> in column order; each row cell is Option<oxrdf::Term> (None = unbound).
println!("{:?}", row[0].as_ref().map(|t| t.to_string()));
}
// SELECT straight to a SPARQL 1.1 JSON results string (skips per-cell Term allocation).
let json = sparq_engine::query_json(&g, "SELECT (COUNT(*) AS ?n) WHERE { ?s ?p ?o }").unwrap();
// ASK -> bool (early-exits: pattern evaluated under an implicit LIMIT 1).
let yes = sparq_engine::ask(&g, "PREFIX ex: <http://ex/> ASK { ex:alice ex:knows ?x }").unwrap();
```
`Graph::load_str` ignores graph names in TriG/N-Quads (folds into the default graph). To keep named
graphs (so `GRAPH <g> {…}` / `GRAPH ?g {…}` work), use `Graph::load_dataset(text, "nquads"|"trig")`.
## Key APIs
All entry points take `&Graph` + `&str` and return `Result<_, String>` (parse + eval errors are
`String`). The result types:
- `sparq_core::strdist::edit_distance(&str, &str) -> usize` computes character-based
Levenshtein distance for vocabulary and dictionary suggestion ranking.
- `pub struct QueryResult { pub vars: Vec<oxrdf::Variable>, pub rows: Vec<Vec<Option<oxrdf::Term>>> }`
— `len()` / `is_empty()` count solution rows. The layout is **columnar** (the `vars` header is
stored once, not per cell); index a cell as `result.rows[row][col]` where `col` is the position of
the variable in `result.vars`, `None` = unbound.
- *(opt-in `query-solution` feature, OFF by default)* `result.solutions()` gives an
**Oxigraph-shaped** per-solution view — an iterator of borrowed, zero-copy `QuerySolution` values
(one per row, sharing the `vars` header; no second materialisation, no cloned terms). Each matches
Oxigraph's `QuerySolution`: `sol.get(var) -> Option<&Term>` (by `&str` name with or without a
leading `?`, by `oxrdf::VariableRef`/`&Variable`, or by positional `usize`; `None` = absent or
unbound), `sol.iter()` over the bound `(VariableRef, &Term)` pairs (unbound cells skipped),
`&sol[var]` (panicking `Index`), plus `variables()` / `values()` / `len()` / `is_empty()`. Use it
for ergonomic Rust Oxigraph interop / migration; the underlying `{vars, rows}` layout is unchanged.
- `pub struct QueryBudget { pub deadline: Option<Instant> /*native only*/, pub max_rows: Option<usize>, pub max_bytes: Option<usize>, pub cancel: Option<Arc<AtomicBool>> }`
— `QueryBudget::unlimited()` is the no-op default. `max_rows` caps the working-set ROW count;
`max_bytes` (`sq-s5is`) is the byte-accounted companion — it prices row WIDTH
(`rows × vars × size_of::<Id>()`) plus the bytes of query-computed (BIND/aggregate/CONSTRUCT)
literals, so a few very wide rows or a huge computed literal is bounded where the row cap is
blind. Both are coarse cooperative ceilings (checked at operator entry / per outer loop), a
conservative LOWER bound on heap — not an exact RSS quota; whichever trips first aborts with
`query budget exceeded (max-rows|max-bytes)`. `with_cancel(Arc<AtomicBool>)` adds a cross-thread
cancellation handle; a `Relaxed` store of `true` aborts cooperatively at the next coarse poll with
`query budget exceeded (cancelled)`. `cancelled_by(flag)` creates an otherwise-unlimited budget.
SELECT/ASK entry points (each has `_prepared`, `_with_budget`, and `_view` variants):
- `query(&Graph, &str) -> Result<QueryResult, String>` — SELECT (also accepts ASK, returning the
unit-row encoding: 0 vars, one empty row iff satisfiable).
- `query_json(&Graph, &str) -> Result<String, String>` — SELECT/ASK as SPARQL-1.1 JSON.
- `query_json_chunks_with_budget(&Graph, &str, &QueryBudget) -> Result<Vec<String>, String>` —
streamed JSON (concatenation is byte-identical to `query_json`; for HTTP bodies).
- `query_json_stream_with_budget(&Graph, &str, &QueryBudget, sink)` (+ the
`query_json_stream_prepared_with_budget` no-re-parse variant over a `PreparedQuery`) —
emits each JSON chunk to `sink` AS produced (TTFB streaming; the HTTP server's read path).
- `ask(&Graph, &str) -> Result<bool, String>` — requires an ASK query.
- `count(&Graph, &str) -> Result<usize, String>` — solution count without materialising terms.
Graph-valued forms (return `Vec<oxrdf::Triple>`; `*_ntriples` returns a serialised `String`):
- `construct` / `describe` / `construct_or_describe` (form-agnostic) / `construct_ntriples`
/ `triples_to_ntriples(&[Triple]) -> String`.
Update (data lives in the default + named graphs):
- `update(&Graph, &str) -> Result<Graph, String>` — returns a NEW graph (O(n) rebuild).
- `update_in_place(&mut Graph, &str) -> Result<(), String>` — incremental delta-overlay, O(batch);
WAL-durable for directory-backed graphs. NON-atomic on error: a failing op leaves the earlier
ops' partial prefix applied (request-level atomicity is the caller's responsibility).
- `update_in_place_atomic(&mut Graph, &str) -> Result<(), String>` (+ `_with_budget`) — request-ATOMIC
delta-overlay: forks, applies, and commits back ONLY if every op succeeds (else `graph` is left at
its pre-request state). Use this for SPARQL-1.1 all-or-nothing semantics from a direct library
consumer without writing your own fork/seal recovery.
- `update_in_place_capturing(&mut Graph, &str, &QueryBudget) -> Result<Vec<UpdateEffect>, String>`
+ `apply_effects(&mut Graph, &[UpdateEffect])` — apply once, capturing the RESOLVED delta, then
replay it onto a second (e.g. durable mirror) graph WITHOUT re-executing the text. Use this when
mirroring a sequence of updates so non-deterministic functions (`NOW()`/`RAND()`/`UUID()`/`BNODE()`)
and `LOAD <remote>` are not re-rolled on the second graph (the server's `--persist` path uses it).
Prepared (parse/plan once, execute many):
- `PreparedQuery::parse(&str) -> Result<PreparedQuery, String>` (also `FromStr`, and
`From<spargebra::Query>` for programmatically built algebra); `query_prepared`, `ask_prepared`,
`count_prepared`, `construct_prepared`, `describe_prepared` (+ `_with_budget`).
- *(opt-in `params`)* **Parameterized prepared queries — safe value binding (SPARQL-injection
mitigation, #901).** `PreparedQuery::bind(name, oxrdf::Term) -> Result<PreparedQuery, String>`
and `PreparedUpdate::{parse, bind}` + `update_prepared` / `update_in_place_prepared`
(+ `_with_budget`). `bind` substitutes a typed value into a free placeholder variable via a pure
**algebra rewrite** (`Variable` -> term node), NEVER string concatenation, so a hostile bound
value cannot alter query structure. Convenience term constructors: `params::value::{iri, string,
lang_string, typed, blank}`. Fail-closed (rejects an unknown placeholder, a `BIND`/aggregate/
`VALUES` output, or a blank node in a predicate/graph slot). The placeholder name may be written
`who`, `?who`, or `$who`. **Always prefer this over building a query string from untrusted input.**
Extension functions (SPARQL 17.6) and dataset views:
- `FunctionRegistry::new()` + `.register(iri, |args: &[Term]| -> Result<Term, String>)`;
`query_with_functions(&Graph, &str, &FunctionRegistry)` (+ `_and_budget`); `with_functions(®, ||
…)` scopes the registry over ANY other entry point.
- `DatasetView { base: &Graph, named: Arc<FxHashSet<Term>>, default: DefaultGraphMode }`;
`query_view` / `ask_view` / `count_view` / `query_json_view` (+ `_with_budget`), or
`with_view(&v, || …)`.
- *(opt-in `window-functions`)* `CustomAggregateRegistry::new()` + `.register(iri, |members:
&[Option<Term>]| -> Result<Option<Term>, String>)`; `query_with_aggregates(&Graph, &str, ®)`
(+ `_and_budget`) parses+installs, `with_aggregates(®, || …)` scopes it. Window functions:
`window::{WindowSpec, WindowFunction, WindowAggregate, WindowFrame, FrameUnit, FrameBound, SortKey,
apply_window}` (programmatic pass), or `query_over(&Graph, &str)` (+ `_with_budget`) for the inline
`OVER(…)` query syntax (a source rewrite over the engine; covers `ROW_NUMBER`/`RANK`/`DENSE_RANK`,
the windowed aggregates `COUNT`/`SUM`/`AVG`/`MIN`/`MAX` (sq-imj8), the offset/positional
`LAG`/`LEAD(?x[, n[, default]])` and `NTILE(n)` (sq-hqhc), `PARTITION BY`/`ORDER BY`,
`ROWS`/`RANGE` frames, and a reusable named `WINDOW w AS (…)` clause (sq-hqhc)).
Introspection: `explain(&Graph, &str)` (plan-only) and `explain_analyze(&Graph, &str)` (plan + per-
operator execution trace) return human-readable TEXT (the default).
Structured EXPLAIN *(opt-in `explain-json` feature, OFF by default)* — a MACHINE-READABLE plan:
`explain_plan(&Graph, &str)` and `explain_plan_analyze(&Graph, &str)` return a typed `PlanNode` tree
(`operator`, `estimated` cardinality on BGP nodes, and — after ANALYZE — `actual` rows, wall `nanos`,
and the per-operator **q-error** = `max(est/actual, actual/est)`; 1.0 is a perfect estimate, larger is
worse in either direction). `PlanNode::to_json()` emits a hand-written JSON projection (no serde dep);
`PlanNode::max_q_error()` is the whole-plan worst. `SlowQueryRing::new(n)` is a bounded ring keeping the
N worst-by-wall-time analyzed plans (`record` / `push` / `slowest` / `to_json`) for an ops slow-query
view. Honest boundaries: only BGP nodes carry an estimate (the only operators the planner sizes);
q-error is `None` when either side is 0; `nanos` are always 0 on wasm32.
Persistent planner statistics *(opt-in `persistent-stats`, OFF by default)* are rebuilt explicitly
with `stats::analyze(&graph, saved_store_dir)`. This atomically writes a deterministic `stats.bin`
beside the saved/mmap store containing per-predicate cardinalities and equi-depth subject/object
value histograms. Load it without scanning indexes using `StatsCatalog::load(dir)`, then install it
around queries with `with_stats_catalog(&Arc::new(catalog), || query(&graph, sparql))`. The catalog
changes join estimates/order only; query results are unchanged. `AnalyzeMetrics` exposes stable
triple/predicate/bucket/byte counts for operational checks.
## Common recipes
**Aggregates, GROUP BY / HAVING, subqueries** — standard SPARQL 1.1; no special API:
```rust
sparq_engine::query(&g,
"SELECT ?p (COUNT(*) AS ?c) WHERE { ?s ?p ?o } GROUP BY ?p HAVING (COUNT(*) >= 2)").unwrap();
// COUNT/SUM/AVG/MIN/MAX/GROUP_CONCAT/SAMPLE; SUM/AVG skip unbound members.
sparq_engine::query(&g,
"SELECT ?s WHERE { { SELECT ?s WHERE { ?s <http://ex/age> ?a } ORDER BY DESC(?a) LIMIT 1 } }").unwrap();
```
*Aggregates over an EMPTY result* (SPARQL 1.1 §18.5.1, pinned by the engine's
`aggregate_empty_semantics` tests and the W3C `agg-empty-group-*` conformance cases):
- **No `GROUP BY`** ⇒ the whole result is ONE implicit group, so you get exactly **one** row
even when nothing matched. In it: `COUNT(*)`/`COUNT(?x)`/`SUM(?x)`/`AVG(?x)` are
**`"0"^^xsd:integer`** (a *bound* `0`), `GROUP_CONCAT(?x)` is the empty string `""`, and
`MIN`/`MAX`/`SAMPLE` are **unbound** (an empty-set error surfaces as an unbound cell).
Mind the split: `SUM`/`AVG` over empty are `0`, not unbound — so `COALESCE(SUM(?x), 0)`
returns `0` because `SUM` already returned a bound `0`.
- **With `GROUP BY`** ⇒ an empty input has **zero groups**, so you get **zero** rows (the
single-implicit-group rule applies only when no `GROUP BY` is written).
**Property paths** (all 8 operators: `/ | ^ * + ?` and `!(…)` negated sets) — write them inline:
```rust
sparq_engine::query(&g,
"PREFIX ex: <http://ex/> SELECT ?x WHERE { ex:alice ex:knows+ ?x }").unwrap(); // transitive
```
**Materialized full paths** (opt-in `paths` feature) — unlike standard SPARQL property paths,
this programmatic API returns every intermediate node and edge. `Shortest` returns all tied
minimum-length paths per endpoint pair; `All` requires a finite `max_length` and returns simple
paths up to that bound. Set `cyclic: true` to request only non-empty paths returning to their start.
```rust
// Cargo.toml: sparq-engine = { version = "0.1", features = ["paths"] }
use oxrdf::{NamedNode, Term};
use sparq_engine::{enumerate_paths, PathMode, PathSpec, Via};
let paths = enumerate_paths(&g, &PathSpec {
mode: PathMode::Shortest,
cyclic: false,
start: Some(Term::NamedNode(NamedNode::new("http://ex/alice")?)),
end: Some(Term::NamedNode(NamedNode::new("http://ex/bob")?)),
via: Via::Predicate(NamedNode::new("http://ex/knows")?),
max_length: None,
})?;
assert!(paths.iter().all(|path| path.nodes.len() == path.edges.len() + 1));
# Ok::<(), Box<dyn std::error::Error>>(())
```
`PathSpec::via` also accepts `Via::Pattern`, whose SPARQL group graph pattern must bind the
reserved `?from` and `?to` endpoint variables. The pattern is evaluated once to materialize the
edge relation. In the dedicated syntax, write `VIA { ?from ex:knows/ex:memberOf ?to }`. Because a
pattern has no single predicate term, each returned `?edge` is the canonicalized pattern source as
an `xsd:string` literal (and therefore contains no blank nodes).
The same feature exposes a dedicated non-standard query form through `query_paths` and
`explain_paths`. It is intentionally rejected by the ordinary `query` entry point:
```rust
let result = sparq_engine::query_paths(&g,
"PREFIX ex: <http://ex/> PATHS SHORTEST START ?s = ex:alice END ?e = ex:bob VIA ex:knows")?;
// Columns: ?s ?e ?pathIndex ?hopIndex ?node ?edge; one row per traversed hop.
let plan = sparq_engine::explain_paths(&g,
"PREFIX ex: <http://ex/> PATHS SHORTEST START ?s = ex:alice END ?e = ex:bob VIA ex:knows")?;
assert!(plan.starts_with("Paths mode=shortest"));
# Ok::<(), Box<dyn std::error::Error>>(())
```
**RDF 1.2 triple terms** (`<<( s p o )>>`) — stored structurally; patterns with variables
inside the triple term match. Load with the `rdf-12` feature enabled on oxrdf/oxttl (default in
this workspace). In Turtle/TriG you can write the reified triple `<< s p o >>` (the
`reifiedTriple` sugar; subject or object position, optionally `<< s p o ~ reifier >>`) or the
annotation block `s p o {| … |}` (which also **asserts** the base triple); both desugar to the
standard `rdf:reifies <<( s p o )>>` form. The triple term `<<( s p o )>>` itself (the `tripleTerm`
production) is **object-position only** (RDF 1.2). See the SPARQL 1.2 triple-term
functions `TRIPLE`/`isTRIPLE`/`SUBJECT`/`PREDICATE`/`OBJECT` for constructing/decomposing them.
```rust
let g = Graph::load_str(
r#"@prefix ex: <http://ex/> . << ex:alice ex:age 30 >> ex:certainty 0.9 ."#, "turtle").unwrap();
sparq_engine::query(&g,
"PREFIX ex: <http://ex/> SELECT ?s ?o ?c WHERE { << ?s ex:age ?o >> ex:certainty ?c }").unwrap();
// Annotation-block form (asserts ex:alice ex:age 30 AND records the certainty reifier):
let g2 = Graph::load_str(
r#"@prefix ex: <http://ex/> . ex:alice ex:age 30 {| ex:certainty 0.9 |} ."#, "turtle").unwrap();
```
**Custom extension functions** — register Rust closures under function IRIs, then `query_with_functions`:
```rust
use oxrdf::{Literal, Term};
use sparq_engine::{query_with_functions, FunctionRegistry};
let mut reg = FunctionRegistry::new();
reg.register("http://ex/fn#double", |args: &[Term]| {
let [Term::Literal(l)] = args else { return Err("double() expects 1 literal".into()) };
let n: i64 = l.value().parse().map_err(|e| format!("double(): {e}"))?;
Ok(Term::Literal(Literal::from(n * 2)))
});
let r = query_with_functions(&g,
"PREFIX fn: <http://ex/fn#> SELECT ?d WHERE { ?s <http://ex/age> ?a . BIND(fn:double(?a) AS ?d) }",
®).unwrap();
// To use the registry with ANOTHER entry point: with_functions(®, || sparq_engine::ask(&g, q))
```
**Custom aggregate registry** (opt-in `window-functions` feature) — register a Rust closure as a
named aggregate IRI, then call it from a real SPARQL `GROUP BY`. Unlike a scalar extension function,
the closure FOLDS the group's per-member values (`None` ≡ unbound for that member) into one term:
```rust
// Cargo.toml: sparq-engine = { version = "0.1", features = ["window-functions"] }
use oxrdf::{Literal, Term};
use sparq_engine::{query_with_aggregates, CustomAggregateRegistry};
let mut reg = CustomAggregateRegistry::new();
reg.register("http://ex/agg#product", |members: &[Option<Term>]| {
let mut acc: i64 = 1;
for m in members { if let Some(Term::Literal(l)) = m { acc *= l.value().parse::<i64>().map_err(|e| e.to_string())?; } }
Ok(Some(Term::Literal(Literal::from(acc))))
});
let r = query_with_aggregates(&g,
"PREFIX ex: <http://ex/> PREFIX agg: <http://ex/agg#> \
SELECT ?d (agg:product(?s) AS ?p) WHERE { ?x ex:dept ?d ; ex:sales ?s } GROUP BY ?d",
®).unwrap();
// query_with_aggregates DECLARES every registry IRI to the parser (so `agg:product(?s)` parses as an
// aggregate, not a scalar call) AND installs the registry for evaluation. `with_aggregates(®, ||..)`
// is the scoped form (composes with with_functions / with_view).
// CAVEAT: a `DISTINCT` custom aggregate (`agg:product(DISTINCT ?s)`) does not currently PARSE in the
// vendored spargebra (a parser limitation, tracked as a follow-up bead); non-DISTINCT works.
```
**`MULTIPLICITY()` inside an aggregate** (no feature needed; default build) — a **NON-STANDARD
extension** exposing the SPARQL 1.2 algebra's `multiplicity(μ|Ω)` device (which replaced the informal
`card[Ω](μ)`). It is a zero-argument builtin valid ONLY inside an aggregate's argument expression: it
evaluates to the bag cardinality of the current group member's solution within its group multiset.
W3C SPARQL 1.2 defines `multiplicity` only as an algebra/semantics device — there is **no callable
`multiplicity()` builtin in the rec and no conformance test for it** — so this is a sparq extension,
not a 1.2-conformance feature.
```rust
// A sub-SELECT projecting away the subject collapses several rows to identical solutions
// (bag semantics), so the group's distinct member carries a multiplicity > 1.
let g = Graph::load_str(
"@prefix ex: <http://ex/> . ex:a ex:v 10 . ex:b ex:v 10 . ex:c ex:v 10 . ex:d ex:v 20 . ex:e ex:v 20 .",
"turtle").unwrap();
// SUM(?x * MULTIPLICITY()) folds the DISTINCT solutions {10(×3), 20(×2)} = 10·3 + 20·2 = 70,
// which equals plain SUM(?x) over the bag {10,10,10,20,20}. This is the whole point of the device.
let r = sparq_engine::query(&g,
"PREFIX ex: <http://ex/> SELECT (SUM(?x * MULTIPLICITY()) AS ?w) WHERE { SELECT ?x WHERE { ?s ex:v ?x } }").unwrap();
```
Semantics: when an aggregate argument calls `MULTIPLICITY()`, sparq folds the group's **distinct**
solutions, each weighted by its bag cardinality (per the Set-Function algebra), so a value occurring
`k` times contributes `k·x`, not `k²·x`. Outside an aggregate (e.g. a plain `BIND`) `MULTIPLICITY()`
is an expression error → unbound. An aggregate that never mentions it is byte-for-byte unchanged.
**Window functions** (opt-in `window-functions` feature) — **NON-STANDARD extension**: SPARQL has no
W3C-REC `OVER (PARTITION BY … ORDER BY …)` syntax, so sparq exposes windowing two ways, both following
the SQL:2003 window model (the surface Stardog / AnzoGraph expose) and neither touching the engine's
W3C-conformance SPARQL surface.
*(a) Programmatic pass over a `QueryResult`* — the full surface. Run an ordinary SELECT, then apply a
`WindowSpec` (`ROW_NUMBER` / `RANK` / `DENSE_RANK`; the offset/positional `Lag` / `Lead` / `Ntile`
(sq-hqhc); or a windowed aggregate over the whole partition, or — sq-imj8 — over an explicit
`ROWS`/`RANGE` frame). One column is appended; row order is preserved:
```rust
use sparq_engine::window::{apply_window, SortKey, WindowFunction, WindowSpec};
use oxrdf::Variable;
let result = sparq_engine::query(&g, "SELECT ?emp ?dept ?sales WHERE { … }").unwrap();
let spec = WindowSpec {
partition_by: vec![Variable::new("dept").unwrap()],
order_by: vec![SortKey::desc(Variable::new("sales").unwrap())],
function: WindowFunction::Rank, // RANK() over (PARTITION BY ?dept ORDER BY ?sales DESC)
frame: None, // a frame applies only to an Aggregate (None = whole partition)
new_var: Variable::new("rank").unwrap(),
};
let ranked = apply_window(&result, &spec).unwrap(); // ?rank appended; RANK has gaps after ties
// Windowed aggregate over a FRAME (sq-imj8): a running total is
// WindowFunction::Aggregate { agg: WindowAggregate::Sum, of }
// + frame: Some(WindowFrame::rows_running()) // ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
// `WindowFrame { unit: FrameUnit::Rows|Range, start, end }` with `FrameBound::{UnboundedPreceding,
// Preceding(n), CurrentRow, Following(n), UnboundedFollowing}`; RANGE bounds are peer-group based
// (no numeric RANGE offset). `frame: None` keeps the whole-partition default.
```
*(b) Inline `OVER(…)` query syntax* (sq-h564) — write the window directly in the SELECT projection and
run it with `query_over` / `query_over_with_budget`. This is a **source rewrite in front of the engine**
(it does NOT change the vendored `spargebra` parser): `query_over` lifts each `(FN() OVER (…) AS ?out)`
item out of the projection, runs the window-stripped SELECT through the ordinary engine, applies the
programmatic pass above, then reprojects. **Covered subset:** the ranking functions `ROW_NUMBER()`,
`RANK()`, `DENSE_RANK()`, the windowed aggregates `COUNT(?x)` / `SUM(?x)` / `AVG(?x)` / `MIN(?x)` /
`MAX(?x)` (sq-imj8 — single `?var` argument; case-insensitive), and the offset/positional functions
`LAG(?x[, n[, default]])` / `LEAD(…)` / `NTILE(n)` (sq-hqhc). A spec can be reused via a named
`WINDOW w AS (…)` clause and `OVER w` (sq-hqhc). `PARTITION BY ?v …`, `ORDER BY` over
projected variables **or computed expressions** (sq-c1jv) — e.g. `ORDER BY (?a + ?b)`, `DESC(?sales + 0)`,
`STRLEN(?s)`; each expression is bound to a fresh helper var in the rewritten inner SELECT and dropped
from the output — in both `DESC(…)` and `… DESC` spellings, an explicit `ROWS`/`RANGE` frame on an
aggregate (sq-imj8 — `ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`, `ROWS n PRECEDING`,
`RANGE BETWEEN … AND CURRENT ROW`, etc.), multiple window columns, and `SELECT *`. A query with no
`OVER` clause is run unchanged (so `query_over` is a strict superset of `query` for non-window queries):
```rust
// Cargo.toml: sparq-engine = { version = "0.1", features = ["window-functions"] }
let r = sparq_engine::query_over(&g,
"PREFIX ex: <http://ex/> \
SELECT ?emp (ROW_NUMBER() OVER (PARTITION BY ?dept ORDER BY DESC(?sales)) AS ?rn) \
WHERE { ?emp ex:dept ?dept ; ex:sales ?sales }").unwrap(); // ?rn = per-?dept rank, descending by ?sales
```
**Inline-OVER caveats (HONEST):** the `OVER` surface (and the `WINDOW` clause) is a sparq extension, not
W3C SPARQL, recognised ONLY on the `query_over` entry point (a `(… OVER …)` clause / `WINDOW` clause is
still a parse error on `query`/the standard surface). A ranking function call must be empty
(`ROW_NUMBER()`); a windowed aggregate takes a single `?var` argument (`SUM(?x)`); `LAG`/`LEAD` take a
bare `?var` plus an optional integer offset and a constant default, `NTILE` a positive integer; the
`AS ?out` alias is required. The `OVER` operand is either an inline `(…)` spec or a name bound by a
trailing `WINDOW name AS (…)` clause. `ORDER BY` keys may be projected variables OR computed expressions
(sq-c1jv) but `PARTITION BY` keys must be projected variables. A `ROWS`/`RANGE` frame is valid only on an
aggregate (a frame on a ranking or offset function errors), and `RANGE` supports only the peer-group
bounds (`UNBOUNDED …` / `CURRENT ROW`), not a numeric `RANGE n PRECEDING` offset. **Deferred
(programmatic API only, beaded):** a `DISTINCT` windowed aggregate (`COUNT(DISTINCT ?x) OVER …`), an
aggregate / `LAG`/`LEAD` argument over a computed-expression, numeric `RANGE` offsets, and `PARTITION BY`
over a computed expression.
**Budgets / timeouts / ASK-style early exit** — a `QueryBudget` is checked cooperatively at coarse
sites; tripping it fails with `"query budget exceeded (timeout)"` / `"... (max-rows)"` /
`"... (max-bytes)"` / `"... (cancelled)"`:
```rust
use sparq_engine::QueryBudget;
use std::sync::{Arc, atomic::AtomicBool};
let cancel = Arc::new(AtomicBool::new(false));
let budget = QueryBudget {
max_rows: Some(10_000),
max_bytes: Some(64 << 20), // byte-accounted companion (sq-s5is); None = off
#[cfg(not(target_arch = "wasm32"))]
deadline: Some(std::time::Instant::now() + std::time::Duration::from_secs(2)),
..QueryBudget::unlimited()
}.with_cancel(Arc::clone(&cancel));
let r = sparq_engine::query_with_budget(&g, "SELECT * WHERE { ?s ?p ?o }", &budget);
// Another thread may call cancel.store(true, std::sync::atomic::Ordering::Relaxed).
// For existence checks prefer ask()/ASK — it streams under an implicit LIMIT 1 (cheapest early exit).
```
**Named-graph dataset view** (zero-copy restriction; a non-visible graph is indistinguishable from
an absent one):
```rust
use std::sync::Arc;
use oxrdf::{NamedNode, Term};
use sparq_engine::{DatasetView, DefaultGraphMode, FxHashSet, query_view};
let store = Graph::load_dataset(nquads, "nquads").unwrap();
let visible: Arc<FxHashSet<Term>> =
Arc::new([Term::NamedNode(NamedNode::new("http://ex/g1").unwrap())].into_iter().collect());
let v = DatasetView { base: &store, named: visible, default: DefaultGraphMode::StoreDefault };
let r = query_view(&v, "SELECT ?s WHERE { GRAPH ?g { ?s ?p ?o } }").unwrap(); // only g1 visible
```
## Gotchas / feature flags / prerequisites
- **Errors are `String`** — both SPARQL parse errors and evaluation/type errors. SPARQL is parsed by
(a vendored) `spargebra` with `sparql-12` + `sep-0006`.
- **Only SELECT/ASK** go through `query`/`query_json`/`count`; CONSTRUCT/DESCRIBE have their own
functions, and a form mismatch is a clean `Err` (e.g. `ask()` on a SELECT).
- **Numeric FILTER comparisons are VALUE-EXACT, incl. high-precision `xsd:decimal`** (`sq-lr2ii`).
A single-pattern `?v OP const` numeric FILTER is normally pushed into the scan and decided via the
O(1) f64 `numerics` cache (`extract_sargable`). Because an f64 cannot represent a decimal with
`> 15` significant digits exactly (e.g. `"1.000000000000000001"^^xsd:decimal` shares the f64 `1.0`
with the integer `1`), that fast path is **declined** whenever the graph holds such a decimal
(`Graph::has_high_precision_decimal`) OR the constant itself has `> 15` significant digits — the
comparison then falls back to the exact evaluator (`=`/`<`/`>`/`<=`/`>=` decided by exact decimal
string arithmetic, matching the `BIND((?v = c) AS ?b)` expression path). The decline is
graph-wide/conservative (correctness first): a graph carrying one high-precision decimal skips the
numeric-pushdown optimisation for all its numeric FILTERs, never the wrong answer.
- **`SELECT *`** never exposes blank-node "variables" (`_:x` in a pattern is an existential var).
- **Non-deterministic builtins** (`sq-98w7z.1`) — `NOW()` is **query-constant** per SPARQL 1.1
§17.4.5.1: every evaluation within one execution (across rows, parallel workers, `EXISTS`
re-entry, sub-selects) returns the same `xsd:dateTime`, pinned at execution start and re-sampled
by the next execution (each UPDATE operation's WHERE is its own execution; second granularity).
`RAND()` stays fresh per call, drawn from a per-thread splitmix64 PRNG seeded once from OS
entropy — NOT cryptographic (SPARQL imposes no such requirement); don't derive secrets from it.
`UUID()`/`STRUUID()`/no-arg `BNODE()` are likewise fresh per call — the engine never memoises a
non-deterministic builtin (the allow/deny policy is spelled out in `eval_function_inner`).
`REGEX()`/`REPLACE()` memoise the compiled `(pattern, flags)` per thread (capped at 64 entries),
so a constant-pattern FILTER compiles once instead of per row; an invalid pattern/flag is still a
per-row type error — the failure outcome is memoised, the semantics are unchanged.
- **`update` vs `update_in_place` vs `update_in_place_atomic`** — `update` returns a fresh `Graph`
(input borrowed, untouched, atomic by construction); `update_in_place(&mut g, …)` mutates via the
delta overlay (call `Graph::compact` periodically) but is NON-atomic on error; `update_in_place_atomic`
forks-and-seals so an in-place mutation is all-or-nothing. `LOAD` only resolves `file://`; set the
base dir with `with_load_base(path, || update(...))`.
- **SPARQL `SERVICE` federation** is the non-default `service` cargo feature (pulls `ureq`; off on
wasm). Internally the SERVICE client (HTTP transport, SPARQL-Results JSON/XML parse, bound-join
batching, SSRF egress policy) is housed in the `sparq-engine-service` sub-crate (`publish = false`,
[OPUS-4.8] sq-6vshe.4, seam A2 of the facade split) and re-exported through the facade — the
`service` feature name and the `sparq_engine::with_service_egress_allow` / `…egress_policy` /
`…SERVICE_EGRESS_REFUSED_MARKER` / `…allowlist_entry_permits` paths below are unchanged and remain
the supported surface.
When enabled, outbound `SERVICE` fetches go through a **default-deny SSRF egress filter**:
an endpoint that resolves to a loopback / RFC1918 / link-local (incl. the `169.254.169.254`
cloud-metadata IP) / unique-local / unspecified address is refused (checked on the *resolved* IP,
so DNS rebinding can't bypass it). To federate to a trusted internal endpoint, allowlist its host
for the scope: `with_service_egress_allow([host.to_string()], || query(&g, q))`. Public endpoints
need no opt-in. An allowlist entry may be **host-level** (`127.0.0.1` — every port) or
**port-scoped** (`127.0.0.1:8053`, `[::1]:8053`, `.example.org:443` — that host on THAT port ONLY,
rejecting every other port) (`sq-a7jw4`): a port-scoped entry is strictly NARROWER, so an
in-process loopback harness can permit exactly `127.0.0.1:<ephemeral>` without re-opening the whole
loopback host. The port checked is the authority's port (its explicit `:port` or the scheme default),
which is exactly the dialled port — so port-scoping applies to the connect target and the resolved
IP is still re-vetted (no wildcard port; tightens, never loosens). Every egress-refusal error string
carries the stable
`sparq_engine::SERVICE_EGRESS_REFUSED_MARKER` substring (`sq-iu0c`), so a network-exposed host can
`contains()`-classify a blocked `SERVICE` as an authorization-policy refusal (e.g. HTTP `403`)
rather than a server fault — `sparq-server` does exactly this.
- **`SERVICE` bind-join (`VALUES` pushdown)** — when a `SERVICE` sub-query is the right side of a
join (or `OPTIONAL`) whose join variables are already bound by the left side, sparq pushes a
*block* of those bindings into the remote query as a `VALUES` clause (the brTPF/FedX "bound join")
instead of fetching the whole remote relation and joining locally. For a selective join this slashes
the rows the endpoint returns and the data transferred. It is **on by default** — a
correctness-preserving optimisation of the existing `SERVICE` path (the answer is identical to the
unbound-then-local-join path; `SILENT`, `OPTIONAL`/left-join, multi-var and empty-binding edge cases
are all preserved) — and **falls back to the verbatim forward** when it can't apply (no bound join
var, a join key bound to a blank node). The only tuning knob is the block
size (distinct binding tuples per remote request): **opt-in** via
`with_service_bound_join_block_size(n, || query(&g, q))` or the `SPARQ_SERVICE_BIND_BLOCK` env var
(default ~50). The knob never changes results — only the remote-request count vs per-request size.
- **`SERVICE ?ep` variable endpoint** (`sq-d4p`) — a `SERVICE ?ep { P }` whose endpoint variable is
bound by the surrounding query is evaluated per SPARQL 1.1: the bind-join path partitions the
already-bound left rows by their `?ep` value and dispatches one bind-join **per distinct endpoint
IRI**, tagging each remote row with `?ep = <that endpoint>` so the surrounding join re-attaches it
to exactly the left rows that named that endpoint. A left row whose `?ep` is unbound or not an IRI
names no valid endpoint and contributes no federated answer. A **top-level** `SERVICE ?ep` with
nothing to bind it still errors (or, under `SILENT`, yields the join identity). (No new public API —
this is a behavioural addition on the `service` feature.)
- **Per-query `SERVICE ?ep` remote-request cap** (`sq-b93pv`) — a `SERVICE ?ep` whose endpoint
variable binds to **many distinct endpoint IRIs** fans out into one remote dispatch per distinct
endpoint, so a hostile / high-cardinality `?ep` can amplify one client query into a burst of
outbound calls (the amplification the per-host egress allowlist does not bound). The **opt-in**
`with_service_remote_request_cap(n, || query(&g, q))` (or the `SPARQ_SERVICE_REMOTE_CAP` env var)
caps the number of distinct endpoints one `SERVICE ?ep` evaluation may dial; exceeding it is a
typed refusal **enforced PRE-HTTP** (at eval time, before any socket opens — a true pre-dispatch
bound, not a post-hoc cancellation) carrying the stable `sparq_engine::SERVICE_REMOTE_CAP_MARKER`
substring (so a server can classify it like the egress marker). It is **not** swallowed by
`SILENT` (a resource-policy refusal, not an unreachable endpoint — the same stance the query
budget takes). **Default is uncapped**, so a concrete-IRI `SERVICE <…>` and a normal-cardinality
`SERVICE ?ep` are unchanged.
- **Per-query `SERVICE` timeout** (`sq-d4p`) — the SERVICE HTTP transport's socket timeout is now
bounded by the active `QueryBudget` deadline (it caps at `min(remaining-until-deadline, default)`
with a small non-zero floor), so a `SERVICE` fetch under a tight `deadline` no longer blocks for the
full default on an unresponsive endpoint.
- **Streaming / bounded `SERVICE` result consumption** (`sq-my8wd.4` / `sq-my8wd.5`) — remote
SPARQL-Results bodies (JSON and XML) are parsed INCREMENTALLY: each solution row is interned to
compact id-level bindings as it is parsed and the owned terms are dropped, so the engine never
holds a whole-document JSON DOM or a term-level copy of the remote relation. Peak memory per
`SERVICE` response is dominated by the id-level relation the join itself needs — a
large/adversarial remote result can no longer amplify to a large multiple of its wire size.
Behaviour-neutral by test: a frozen DOM-reference oracle pins identical rows, multiplicity, ORDER
and errors (`service.rs` `streaming_equivalence` tests).
**Reader-seam transport** (`sq-my8wd.5`): the `sparq-engine-service` crate's `ReaderTransport`
trait extends the `Transport` seam so the HTTP body is NEVER buffered into a full `String` —
`HttpTransport` implements it by returning the ureq response body reader directly. The
`TransportAsReader<'t, T>` adapter wraps any `Transport` implementation as a `ReaderTransport`
(useful for test mocks). The `eval_remote_into_read` function is the reader-seam entry point —
it is used internally by the engine's `exec.rs` SERVICE evaluator. These three items
(`ReaderTransport`, `TransportAsReader`, `eval_remote_into_read`) live in
`sparq_engine_service::service` and are not re-exported through the `sparq-engine` facade (they
are implementation-internal); test transports continue to implement `Transport` and are wrapped
via `TransportAsReader` so the streaming path is exercised without rewriting every canned mock.
[OPUS-4.8] [FABLE-5]
- **`SERVICE` evaluation is W3C-conformance-tested end-to-end** (`sq-ddpgx`, epic sq-my8wd) — the
W3C SPARQL 1.1 `sparql11/service` evaluation suite runs against the engine's REAL `ureq` transport
through an in-process **loopback** harness: each `qt:serviceData` block is served by a real
`sparq_server::serve` endpoint on an ephemeral `127.0.0.1:0` port (the well-known endpoint IRIs are
rewritten to the bound URLs), so the whole federated path — HTTP, content negotiation,
SPARQL-Results parsing, the bind-join over the wire — is exercised, not a mock. It is the
`sparq-conformance` crate's opt-in **`service`** feature (a ratcheted floor in the central scoreboard;
`SILENT`-swallow vs non-`SILENT`-propagate against a closed port is pinned directly). Honest scope: a
variable `SERVICE ?ep` and a nested non-`SILENT` `SERVICE` are documented divergences (the loopback
fixture serves a plain graph with onward federation disabled), tracked-not-asserted under sq-my8wd.
- **Window functions + custom aggregate registry** are the non-default `window-functions` cargo
feature. **Window functions are a NON-STANDARD extension** — there is no W3C-REC SPARQL `OVER`
syntax. sparq exposes them as a programmatic pass over a `QueryResult` (the SQL:2003 model
Stardog/AnzoGraph expose), `ROW_NUMBER`/`RANK`/`DENSE_RANK`, the offset/positional
`LAG`/`LEAD`/`NTILE` (sq-hqhc), + a windowed aggregate over the whole partition or an explicit
`ROWS`/`RANGE` frame (sq-imj8),
AND as an inline `OVER(…)` query syntax via the dedicated `query_over` entry point (a *source rewrite*
in front of the engine — it does NOT change the vendored parser, so the standard `query`/`ask`/… surface
stays exactly SPARQL 1.1 and conformance is unaffected; `OVER` is a parse error everywhere except
`query_over`). The inline syntax covers the three ranking functions, the windowed aggregates
`COUNT`/`SUM`/`AVG`/`MIN`/`MAX` with `PARTITION BY`/`ORDER BY` and `ROWS`/`RANGE` frames (sq-imj8), the
offset/positional `LAG`/`LEAD`/`NTILE` and a reusable named `WINDOW w AS (…)` clause (sq-hqhc);
`DISTINCT`/computed-expression function arguments, numeric `RANGE` offsets and a computed-expression
`PARTITION BY` are inline-deferred (use the programmatic API). The custom-aggregate side DOES ride real SPARQL `GROUP BY` (a declared aggregate
IRI is part of the SPARQL 1.1 extension grammar). When the feature is off, zero window/aggregate-registry
code compiles and the default build is byte-identical (no new dependencies). See the recipes above.
- **Parameterized prepared queries (SPARQL-injection mitigation)** are the non-default `params`
cargo feature (bead `sq-rp3um`, #901). When you build a query/update from untrusted input, do NOT
concatenate it into the string — parse a *template* once and `bind` typed values. Binding is a
pure algebra rewrite (`Variable` -> term node), so a hostile value is matched as DATA and can
never inject syntax. Covers SELECT/ASK/CONSTRUCT/DESCRIBE + UPDATE; `bind` is **fail-closed**.
```rust
// Cargo.toml: sparq-engine = { version = "0.1", features = ["params"] }
use sparq_engine::{params::value, query_prepared, update_prepared, PreparedQuery, PreparedUpdate};
// A hostile literal: under string concat this would break out and inject an UPDATE.
let hostile = r#"Bob" } INSERT DATA { <http://ex/evil> <http://ex/p> <http://ex/o> } #"#;
let pq = PreparedQuery::parse("SELECT ?s WHERE { ?s <http://ex/name> ?nameVal }")?
.bind("nameVal", value::string(hostile))?; // carried as one literal — matches nothing
let _ = query_prepared(&graph, &pq)?;
// Bind an IRI into a subject/predicate slot (the IRI constructor validates it):
let pq = PreparedQuery::parse("SELECT ?o WHERE { ?who <http://ex/name> ?o }")?
.bind("who", value::iri("http://ex/alice")?)?;
let _ = query_prepared(&graph, &pq)?;
// UPDATE templates bind the same way (DELETE/INSERT/WHERE):
let pu = PreparedUpdate::parse("INSERT { <http://ex/x> <http://ex/note> ?n } WHERE { }")?
.bind("n", value::string(hostile))?; // exactly one op — no injected DROP/INSERT
let _g2 = update_prepared(&graph, &pu)?;
# Ok::<(), String>(())
```
- **Vectorized columnar primitives** are the non-default `vectorized` cargo feature (M4 plan, bead
`sq-hvfe`): the `chunk` module's `DataChunk` (a column-major, vector-at-a-time id-level batch),
a **decode kernel** (`DataChunk::decode_numeric_column` → a contiguous `Vec<f64>` value column,
`f64::NAN` sentinel for a non-numeric cell, with a gather-free fast path for an all-inline-integer
column — the SIMD enabler, M4 Phase 2 `sq-pntvh.2`), a numeric FILTER comparison kernel
(`DataChunk::select_numeric` → a `SelVec`), a **compare-over-decoded-column** kernel
(`DataChunk::select_decoded`, the branchless auto-vectorising compare that consumes the decode
kernel's output — M4 Phase 3 `sq-pntvh.3`), and a selection/gather kernel
(`DataChunk::apply_selection`). When off, zero columnar code compiles and the default native + wasm
builds are byte-identical (no new dependencies; no `unsafe`).
**`query`/`query_json`/etc. return byte-identical results whether the feature is on or off** — it
is a perf optimisation, never a semantics change. The first evaluator wiring landed in Phase 3
(`sq-pntvh.3`): a **columnar residual-FILTER seam** inside `apply_filter` (Seam A) that, for an
eligible single sargable-numeric residual `?v OP const`, decodes the column once and runs the
**hybrid tri-mask** (`src/chunk_select.rs`, bead `sq-y5ew5`): each lane is classified Confident
(finite f64, `v != c` — f64 verdict is unambiguous by the monotone-rounding lemma), Tie (`v == c`
as f64), or Unknown (NaN sentinel for non-numeric / unbound / local-vocab ids). Tie + Unknown lanes
are **delegated** to the full scalar `eval_expr` predicate (which handles the exact-lexical recheck
for ties); confident-passes and delegated-passes are merged in ascending order. This is provably
byte-identical by construction (design record §3). The seam **declines** entirely to the row path
for temporal or non-sargable filters, batches below `VEC_MIN_BATCH`, and is **disabled whenever the
`zk` trace is armed** so the row path records the complete FILTER obligation set. The M4 wiring
roadmap + coexistence model is `research/vector-at-a-time-m4.md` (epic `sq-pntvh`); its acceptance
gate landed first (Phase 1, `sq-pntvh.1`): the differential BYTE-IDENTITY harness
`crates/sparq-engine/tests/vectorized_byte_identity.rs` (the columnar kernel's serialised survivors
are byte-identical to the row `FILTER` operator over the *same batch*, order-exact — a Phase-1
finding: cross-query byte-identity is unsound because a sargable filter re-plans the scan, so the
invariant is operator-level not full-query), the seam-level differential in
`crates/sparq-engine/src/exec.rs` (`mod columnar_filter_seam`), plus the native FILTER/aggregate
baseline bench `crates/sparq-engine/examples/bench_vectorized.rs` (`metric_us`, registered
`vectorized-eval-micro`, `featured = false`) later phases measure their speedup against.
**Phase 5 (`sq-pntvh.5`) adds the shared dispatcher seam** (`src/vec_dispatch.rs`): a single module
that owns the I1–I5 decline hierarchy and the I5 probe counters shared by every current and future
seam. `VEC_MIN_BATCH` (256) is the minimum batch size below which the scalar path is cheaper;
`VEC_MORSEL` (2048) is the decode-buffer size for morsel-by-morsel `apply_filter` execution — each
morsel extracts only the one filter column (O(rows × 1), not a full-width transpose). The decline
hierarchy (in order): I2 = ZK-trace armed (scalar records the full obligation set); I3 = budget
armed (fallback rule — the debit schedule is not uniform-per-row); operator shape check (only a
simple sargable `?v OP const` numeric comparison, finite constant); `VEC_MIN_BATCH` batch-size gate.
The aggregate seam (Seam B, `group_aggregate` → `columnar_aggregate`) is also wired through the
same I2/I3/`VEC_MIN_BATCH` checks. **I5 probe counters (test-facing / unstable)**:
`reset_stats()` / `stats_snapshot()` / `VecStats` let acceptance tests assert the seams are
non-vacuous (`chunks_built >= 1` for an eligible operator, `rows_delegated > 0` when tie/unknown
lanes exist). Thread-local counters are used (not global atomics) so parallel test threads don't
interfere. The counters are **not semver-stable** — external callers must not build stable logic on
them; they exist only for the acceptance gate in `tests/differentials/vectorized_byte_identity.rs`
(T1–T4) and `tests/differentials/chunk_select_tri_mask.rs` (sq-y5ew5 T1–T5).
- **Sideways information passing (SIP) — correlated graph-pattern join** is a DEFAULT-ON,
semantics-preserving optimisation (bead `sq-7d3dj.30.3`; research/sp2bench-complex-shape-deficit.md
§2.2). When a `Join(A, B)` is evaluated and the already-evaluated side `A` is **small** (≤ 64 rows),
the executor evaluates the big child `B` **correlated** on A's bindings instead of cold: for each
distinct binding of A's variables that are **certainly bound** in `B` and bound to an **IRI** in `A`,
that IRI is substituted as a constant into `B`'s patterns — pushing *into UNION branches, BGP scans,
property paths and filters* — so a scan seeds from the constant rather than running blind. Results are
recombined preserving **multiplicity** (bag semantics). It is **conservative**: it fires only for
IRI-valued correlation variables that are certain in `B` (never a variable that a solution may leave
unbound — e.g. inside an OPTIONAL right side, or MINUS, or a projecting sub-`SELECT`), and any
scope/threshold failure falls back to the **cold** evaluation bit-for-bit. The answer is identical
either way (proven on-vs-off by `tests/sip_join.rs`, incl. an anti-vacuity trace assertion that the
correlated child actually collapsed). SP2Bench q08/q12b: the 1-row `?erdoes` side seeds the Union's
`?document dc:creator ?erdoes` scan instead of a whole-corpus creator self-join. Payoff on complex-shape
workloads is a measurable hypothesis for the canonical perf host, not a baked-in number.
- **Correlated (theta) anti-join for `OPTIONAL … FILTER(!bound)`** is a DEFAULT-ON,
semantics-preserving optimisation (bead `sq-7d3dj.30.9`, SP2Bench q06). The negation idiom
`Filter(!bound(?nb), LeftJoin(A, B, F))` — where `?nb` is **certain** in `B` and **absent** from `A` —
is exactly an anti-join: a left row survives iff **no** `b ∈ B` is compatible with it **and** makes the
OPTIONAL condition `F` effectively **true**. The default-off `algebra-rewrite` pass turns the simpler
`F = None` case into `Minus`, but declines when `F` references **outer** variables (q06's
`?author = ?author2 && ?yr2 < ?yr`), so the cold `left_outer_join` scans the whole corpus. This
eval-time path instead splits `F` into var-to-var **correlation** conjuncts `?outer θ ?inner` (with
`?inner` certain in `B`) and a residual theta (`?yr2 < ?yr`), and picks between two strategies. The
correlation relation `θ` may be value `=`, `sameTerm`, or a single-variable `?a IN (?b)` membership
(which desugars to `?a = ?b`); a constant / multi-element `IN` list stays in the residual (`sq-3cmr4`).
**Large** correlation cardinality → a **hash anti-join**: evaluate `B` **once**, partition it by the
`?inner` id, then probe each left row's bucket — one `B` scan, O(|A|+|B|) (SP2Bench q06's win); for a
**very large** anchor side the per-left-row probe is **fanned out over cores** with rayon under the
`parallel` feature, and only the boolean verdicts are parallelised so the result stays byte-identical
to the serial probe (`sq-f1emb`). **Small** cardinality → **SIP-seed**: seed the outer correlation term
sideways into `B` so each distinct correlation evaluates a tiny `B'`. Either way the residual theta is
re-checked verbatim per candidate with full 3-valued semantics (a **type error ⇒ no match**, so the
outer row **survives** — never spuriously eliminated). The relation `θ` is **load-bearing**: value `=`,
`sameTerm` and id-equality differ on value-equal id-distinct literals (`"1"` vs `"01"`). Id-hashing is
exact for a value-`=` correlation only on **IRI and blank-node** keys (for both, SPARQL `=` coincides
with term identity — per SPARQL 1.1 §17.4.1.7 RDFterm-equal, `=` on two distinct non-literal terms
returns **false**, a type error arising only when both arguments are literals, and false and error alike
mean **no match**, which an id non-match reproduces); a **literal**-valued `=` correlation (the
`sq-lr2ii` value-equality class) routes through a **value-correct** scan that re-checks with SPARQL `=`.
A **`sameTerm`** correlation is **term identity** for every kind, so a literal key is itself id-probeable
and any value-correct scan re-checks with `sameTerm`, never `=`. Each surviving row is emitted **once**
(multiplicity preserved), and any shape/scope miss (e.g. `?nb` also bound on the left, or no seedable
correlation) **declines** to the identical prior plan. Proven on-vs-off by `tests/theta_antijoin.rs`
(type-error-survives, literal value-equality, blank-node, large-cardinality hash, `sameTerm`/`IN`
correlation + a `=`-vs-`sameTerm` divergence witness, a `PAR_THRESHOLD`-crossing parallel probe, and a
randomised differential rotating all three relations across both strategies); toggle/stats behind
`theta_antijoin_testing`. The opt-in **`antijoin-static-decline`** feature (OFF by default, bead
`sq-7d3dj.30.20`) removes a redundant re-evaluation on the **no-seedable-correlation** decline path:
when the recogniser's shape gate matches but the OPTIONAL condition is a bare `!bound` (no var-to-var
correlation to seed — SP2Bench **q07**'s nested levels), the un-featured path evaluates the mandatory
left side, discovers `correlations.is_empty()`, and declines — after which the cold `Filter{LeftJoin}`
fallback **re-evaluates that same (dominant) left side**. The feature adds a purely **static** pre-check
(`in_scope_vars(left)` + `certain_vars(right)`, no graph access) that declines **before** the left side
is touched, so it is evaluated **once**. Pure evaluation-ordering, **bag-result-equivalent** to off
(`tests/antijoin_static_decline_differential.rs`, both feature states + the W3C ratchet); off,
byte-identical, no new deps.
- **Id-level term-identity FILTER fast path** is the non-default `id-filter-fastpath` cargo feature
(bead `sq-7d3dj.30.11`). It removes the per-row term MATERIALIZATION the compiled FILTER evaluator
otherwise performs for `=`/`!=`, by two id-level short-circuits: **(a)** a static term-kind analysis
(`nonliteral_vars`) proves a variable is bound ONLY in BGP subject/predicate slots — never a BGP
object, a property-PATH endpoint (a path object can be a literal; a `Reverse`/zero-length subject
end too), a quoted-triple inner slot, a `BIND`/`VALUES` binding, or any variable of an un-analysed
construct (`SERVICE`/`Lateral`/sub-`SELECT` inner vars are all poisoned to literal-risk) — and so
can never be a literal — for two such operands (or a constant IRI)
SPARQL `=` is exactly dictionary-id equality and `!=` id inequality (the canonicalising dict gives
each IRI/bnode one id); **(b)** EQUAL ids of ANY kind are the same term, so `=` short-circuits `true`
and `!=` `false` (mirroring the `sameTerm` decision the exact path already takes — safe even for
ill-typed literals, which return a boolean not a type error). UNEQUAL ids of possibly-LITERAL
operands (numeric promotion `"1"^^integer` = `"1.0"^^decimal`, whitespace-padded lexicals — the
`sq-lr2ii` class) and `=` cases that can be a TYPE ERROR fall through to the exact value path
unchanged. Result-identical whether on or off — a differential test pairs every id kind (IRIs,
bnodes, numeric-promotion pairs, language-tagged, ill-typed literals) and asserts the fast verdict
equals the exact `term_of` + `values_equal` oracle row-for-row. When off, the fast-path column-set
machinery does not compile and the feature-OFF path is BEHAVIOUR-identical to the prior default build
(no new dependencies; no `unsafe`) — the bytes are NOT identical, because the always-compiled
EXISTS-re-entry refactor (splitting `eval_exists` into a thin wrapper + an always-compiled
`eval_exists_inner`) MOVED bytes and shifted panic locations; this byte-move is declared in
`bench/feature-off-declarations/1785.json` per the feature-OFF-declaration mechanism.
**Predicate-range widening (`sq-1ivw7`)** closes #1785's honest null result on the q08/q12b shape,
whose FILTER variables (`?author`, `?erdoes`) appear only as `dc:creator` OBJECT positions (which
the position-only analysis declined). The widened analysis credits an OBJECT-position variable as
non-literal when its predicate is a CONSTANT IRI whose object column has NO literal in the CURRENT
store snapshot — computed at query-execution time by `Graph::predicate_has_literal_object` (an
overlay-aware, early-exit scan of the predicate's objects; `dict::is_literal_id` classifies each
object id, with inline integers always literal). The requirement is NO LITERALS, not IRI-only:
bnode ids are identity-comparable exactly like IRIs for `=`/`!=` (distinct non-literals compare
FALSE per §17.4.1.7), so a bnode-object predicate still fires. Any literal object for the predicate,
or a VARIABLE predicate, or MIXED use of the variable (also an object of a literal-having predicate)
→ decline. **Graph scoping (soundness):** the credit is scoped to ONE graph's object column, so an
object variable bound under a `GRAPH <g>`/`GRAPH ?g` block stays literal-risk at an OUTER dispatch —
a FILTER sitting outside the GRAPH block classifies against the default graph, but the object is
bound from a self-contained named sub-graph with its own store/dict, so crediting it off the default
column would be unsound (a named-graph literal would be id-compared). The inside-GRAPH dispatch is
correct and unaffected (it evaluates against the named sub-graph, so its own classifier scans the
right store). `Graph::predicate_has_literal_object` answers for the receiver graph only.
**Snapshot soundness:** a prepared query in sparq is parse-only (`PreparedQuery` carries
algebra, no plan); each evaluation borrows an immutable `&Graph` snapshot (a server request pins a
generation), so the check is re-run against the LIVE graph every eval — an UPDATE inserting a
literal object publishes a new snapshot the next query re-checks; the verdict never outlives its
snapshot (there is no plan/inference cache across snapshots; the result cache is keyed by
`(query, version)`). The same snapshot-aware column set is now also installed at the FUSED
conjunctive residual-FILTER sites (`eval_flat_conjunctive`, `eval_bgp_binary_capped`), drain-safe
via `with_idfast_nonlit_cols` (the set drains on the first consuming `apply_filter`, so a nested
EXISTS on a different `Bindings` layout sees the empty default). A differential test witnesses the
q08 shape now compiles `?a = ?b` to `IdEqNonLit` (fires), an update-then-requery flips the credit,
and the end-to-end answer is an independent recompute.
- **DISTINCT-projection loose (skip) index scan** is a DEFAULT-ON, semantics-preserving optimisation
(bead `sq-7d3dj.30.4`; research/sp2bench-complex-shape-deficit.md §2.3). For `SELECT DISTINCT ?p`
over a BGP / **UNION** of BGPs where `?p` is the **single** projected variable, the executor
enumerates the DISTINCT `?p` values **directly** from an existing permutation sorted by `?p` — a
loose/skip scan that gallops (binary-search) past each value's block — instead of materialising every
full-width join row and de-duplicating post-hoc. It is the general form of qlever's "pattern trick"
over sparq's six permutations, and builds **NO new index**. Two branch shapes are enumerated: a single
BGP triple (every distinct `?p` is a solution) and an **anchor + probe** pair joined on one variable.
For the anchor+probe branch the executor picks between two equivalent semi-join strategies by anchor
cardinality (bead `sq-7d3dj.30.10`): a **small** anchor uses the per-member *pattern trick* (bind the
join column to each anchor member, skip-enumerate its few `?p`, stopping once the `?p` universe is
covered); a **large** anchor uses a per-`?p`-block existence scan whose `[P, J]`-ordered block is first
**clipped to the anchor's id window** and then intersected by galloping the **shorter** of block/anchor
(an O(1) id-range-disjointness fast reject still precedes it). The **sorted anchor set is cached across
UNION branches** (q09's two branches share one anchor, built once). A **global already-seen `?p` set**
makes later branches near-free. It is **conservative**: it fires only for that exact single-variable
DISTINCT shape and only when a built permutation exposes the required column order (the compact/wasm
index {SPO, POS, OSP} lacks PSO, so a subject-side probe declines there); every other shape — REDUCED,
multi-variable projections, filters, three-pattern branches, `?p` used as the join variable, a pattern
with a variable repeated across S/P/O (`?x ?p ?x`), and any pattern embedding an RDF 1.2 quoted-triple
term (`<<?s ?p "o">> …`, decomposed by the general BGP planner) — falls back to the full
materialise-then-dedup path **bit-for-bit** (never erroring). The answer is DISTINCT-set identical
either way (proven on-vs-off by `tests/distinct_pushdown.rs`, incl. a q09-shaped anti-vacuity assertion
that the scanned rows collapse to a small fraction of the full join). SP2Bench q09: the 2-branch
`DISTINCT ?predicate` over persons answers a handful of predicates without materialising the ~77 k-row
join. Payoff on the canonical perf host is a measurable hypothesis, not a baked-in number.
- **Characteristic-set anchor-incidence prune** is the OPT-IN `cs-anchor-incidence` cargo feature (OFF
by default; bead `sq-jnb1e`) that accelerates the LARGE-anchor block scan above. For q09 the block
scan still proves each candidate predicate P relates NO anchor member by clipping and galloping P's
join-value block — for the value-typed predicates (`dc:title`, `foaf:homepage`, `rdfs:seeAlso`, 17k–27k
distinct objects each) that is a large no-hit scan (~250 k rows examined to answer 4 predicates). With
the feature on, the executor precomputes, per anchor join position, the SET of predicates that relate
SOME anchor member (one range-restricted scan over the anchor's id window), so a candidate P absent from
that set is pruned by an O(1) membership test instead of the block scan — QLever's "pattern-trick"
metadata answer, over sparq's permutations. It is a characteristic-set INCIDENCE summary (which
predicates touch a type at which position), distinct from the `cs-planner` predicate-set cardinality CS.
RESULT-IDENTICAL: the incidence set is EXACT on the base index, so it only ever prunes a
provably-empty existence check; a P in the set still takes the exact block scan, and the answer is
bit-for-bit the feature-off answer (differential on-vs-off in `tests/distinct_pushdown.rs`, incl. a
randomised straddle, a large no-hit-block prune, and answer-safety corners). It fires only when the
probe constrains **only** the projected predicate and the join variable (else it declines to the exact
scan), and **conservatively DECLINES on a graph with a pending-update overlay** (the derived set is built
against the base index; incremental maintenance is out of scope), so a query after an UPDATE simply
falls back to the exact scan. Off, zero incidence code compiles and no new deps. Payoff on the canonical
perf host is a measurable hypothesis, not a baked-in number.
- **ASK / LIMIT first-solutions early exit through joins** is a DEFAULT-ON, semantics-preserving
optimisation (bead `sq-7d3dj.30.8`; research/sp2bench-complex-shape-deficit.md §5). `ASK` is
evaluated under an implicit `LIMIT 1`, and any `LIMIT k` (no ORDER BY / DISTINCT / aggregation
above it) now stops early for JOIN shapes, not just single-pattern scans: a conjunctive BGP (+
FILTERs) is driven in growing **seed-scan blocks** (1024 → 64 k → rest) through the same greedy
binary join chain, counting a row toward the cap only after **every** residual FILTER has passed
(a first candidate eliminated by a late FILTER never fires the exit); `UNION` evaluates its left
branch first and skips the right when the cap is already met; `OPTIONAL` caps its left side (no
left row is ever dropped by OPTIONAL); `Join(A, B)` probes with a capped `A` through the SIP
correlated path and falls back when the probe misses. Under ASK the plan is additionally
simplified where provably emptiness-neutral: `ORDER BY` and `DISTINCT` are stripped along the top
modifier spine only — NEVER below a `Slice` (`DISTINCT` under `OFFSET` changes the visible count)
and NEVER touching aggregation/HAVING (an empty-group aggregate still yields a solution). It is
**conservative**: cyclic (LFTJ) BGPs, quoted-triple patterns, MINUS, property paths, GRAPH,
bare FILTERs over non-conjunctive groups, and an armed zk-trace recorder all fall back to full
evaluation bit-for-bit. The boolean is identical to the unoptimized path on every query (oracle
differential + budget-bounded revert-witness in `tests/ask_early_exit.rs`: an ASK over a join
whose full materialisation exceeds a row budget must still answer instead of tripping it).
Honest boundary: an ASK whose answer is `false` still sweeps the whole seed (bounded at ~3x the
single-pass scans by the three-block schedule), and the right side of `OPTIONAL` is still
evaluated in full. Payoff (SP2Bench q12a/q12b-class) is a measurable hypothesis for the canonical
perf host, not a baked-in number.
- **Exact-bitmap semi-join reducer** is the non-default `semijoin-bitmap` cargo feature (M4 plan,
survey §A3, bead `sq-gr8mb`; CIDR'26 "Not Yannakakis"). When a binary BGP join scans the next
pattern, the executor first builds a membership filter over the already-materialised side's
connecting-variable ids — a flat **bitmap** over the dense `u32` ids (the dictionary assigns dense
ids, so the bitmap is a perfect-hash, zero-false-positive membership test) or an exact **hash set**
when the keys are sparse+huge — and passes it to the scan, which DROPS a row whose join key cannot
match **before** that row enters the join. This is a transparent PERFORMANCE optimisation: the
filter is membership-exact, so it removes only rows the join would have dropped anyway and the
RESULT is byte-identical to the feature-off path — `query`/`query_json`/etc. return the SAME answers
whether it is on or off (proven by the on-vs-off equivalence suite `tests/semijoin_differential.rs`);
only fewer rows are scanned. Its payoff on star/snowflake workloads is a measurable hypothesis for
the canonical perf host, not a baked-in number. When off, zero of this code compiles and the default
native + wasm builds are byte-identical (no new dependencies — sparq-core + rustc-hash are already
direct deps; no `unsafe`).
- **Yannakakis full-semijoin prepass** is the non-default `yannakakis` cargo feature (survey §A4, bead
`sq-5zf8i`; arxiv 2504.03279 + research/optimization-techniques.md §1.1/§2(a2)) — the complementary
bottom-up reducer to `semijoin-bitmap` (which it IMPLIES, reusing the same exact `KeyFilter`). Where
the A3 reducer prefilters one scan against the accumulated result *during* the join loop, the
Yannakakis prepass runs *before* the main join: it materialises each relation of an **acyclic** BGP
once, then sweeps the join tree bottom-up (leaf→root) and top-down (root→leaf), semijoining each
relation against its neighbours so that no "dangling" tuple (one that joins with nothing downstream)
is ever materialised by the join — directly cutting the intermediate-result blow-up. Routing reuses
the executor's existing GYO acyclicity test (`bgp_is_cyclic`/`bgp_uses_binary`): **acyclic ⇒
semijoin-reduce then join; cyclic ⇒ existing LFTJ, unchanged**. A semijoin is a pure FILTER (removes
only rows the final join would itself drop), so the RESULT is **identical** to the feature-off binary
plan — `query`/`query_json`/etc. return the SAME answers (proven by the on-vs-off equivalence suite
`tests/yannakakis_differential.rs` over chain/star/snowflake/cyclic/empty/no-reduction shapes). The
prepass is **cost-gated** — skipped when the intermediates are already tiny (a pure-overhead guard) —
so a tiny BGP transparently uses the ordinary binary plan. Payoff on chain/snowflake workloads is a
measurable hypothesis for the canonical perf host (bead `sq-0g6g`), not a baked-in number. When off,
zero of this code compiles and the default native + wasm builds are byte-identical (no new deps; no
`unsafe`).
- **DP join-order enumerator (DPccp)** is the `dp-planner` cargo feature (bead `sq-iywur`;
Moerkotte & Neumann, VLDB 2006; made default-on for `sparq-cli` by bead `sq-7d3dj.30.5`).
It enumerates every **connected-subgraph / connected-complement pair** of the BGP join graph
and fills a DP table `best[S]` = the minimum-`Cout` **bushy** join tree over pattern set `S`,
finding a provably `Cout`-optimal order (seeded from the SAME index-range/characteristic-set
cardinality estimator GOO uses) — with **zero cross products** between patterns that share no
variable. When the feature is compiled (as in `sparq-cli`), DPccp fires **by default** for
any BGP with ≥ 3 patterns within the subgraph budget — no install call required. To opt out
for one scope (restores greedy GOO), or to set an explicit budget, use the scoped helpers:
```rust
// Cargo.toml: sparq-engine = { version = "0.1", features = ["dp-planner"] }
// Default-on — no install required; DPccp fires for BGPs with ≥3 patterns within budget.
let rows = sparq_engine::query(&graph, sparql)?;
// Explicit opt-out (restores greedy GOO for this scope):
let greedy = sparq_engine::without_dp_planner(|| sparq_engine::query(&graph, sparql))?;
// Explicit install at a custom budget:
let rows = sparq_engine::with_dp_planner_budget(1024, || sparq_engine::query(&graph, sparql))?;
```
It is **ORDER-ONLY**: a BGP is a commutative/associative natural join, so every tree yields the SAME
bindings — the DP changes join order, never the answer (proven by the on-vs-off differential suite
`tests/dp_planner_differential.rs`, which runs in BOTH feature states). DPccp is worst-case
exponential, so the enumerator counts connected subgraphs first and **falls back to greedy GOO** when
the count exceeds `DpConfig::max_subgraphs`, on a **disconnected** BGP (a cross-product query or an
all-constant pattern), and for BGPs with fewer than 3 patterns (for n≤2, greedy is already optimal
and carries less overhead than the full enumeration path). Cyclic BGPs already route to LFTJ, so the
DP only ever governs binary-plan BGPs. Its payoff on adversarial BGP shapes is a measurable hypothesis
for the canonical perf host, not a baked-in number. Hypergraph **DPhyp** and interesting-orders-in-
the-DP-table are NOT implemented. When off, zero DP code compiles, the default build is byte-identical,
and no new dependencies are added (no `unsafe`).
- **Membership-cluster pre-materialisation** is the non-default `cluster-materialize` cargo feature
([FABLE-5] bead `sq-7d3dj.30.14`; SP2Bench q07, research/sp2bench-complex-shape-deficit.md §5). It
targets the container-membership idiom `?bag ?member ?doc` — a pattern with an UNBOUND predicate (the
`rdf:_n` bag members are ordinary triples, so no single bound-predicate scan enumerates a whole bag).
When such a pattern sits in a BGP next to a small BOUND-predicate anchor it shares exactly one variable
with (q07's `?doc2 dcterms:references ?bag`), greedy GOO bind-joins the ~250k-row unbound-predicate
relation per driver binding through the widest permutation. With the feature on, `cluster::detect`
spots the shape and the executor evaluates the `{anchor, membership}` pair **standalone** (the anchor
bounds the shared variable to a small set → a few-thousand-row relation) and **natural-joins** it to the
rest. It is **ORDER-ONLY**: a BGP is a commutative/associative natural join, so partitioning into two
connected sub-BGPs and joining yields the SAME row bag as greedy — both sub-BGPs are evaluated
UNCORRELATED, so there is no sideways-information hazard (only one evaluation of the cluster; the
materialised relation is the full union-compatible superset), and natural join preserves multiplicity
exactly (no dedup). `detect` **DECLINES** (unchanged greedy plan) on any non-matching shape — not
exactly one membership pattern, an anchor variable that leaks into the rest, a pushed-down scan filter
on a cluster pattern, or the cost gate unmet. Proven by `tests/cluster_materialize_differential.rs`
(randomised shapes + nested-OPTIONAL + multiplicity + a non-vacuous mutation check, run in BOTH feature
states). The end-to-end q07 win is a measured hypothesis for the canonical perf host (bead
`sq-7d3dj.30.6`), not a baked-in number. When off, zero of this code compiles, the default native +
wasm builds are byte-identical, and no new dependencies are added (no `unsafe`).
- **Pre-execution algebra rewrite pass** is the `algebra-rewrite` cargo feature — non-default in the
sparq-engine LIBRARY, but lit BY DEFAULT in the shipped `sparq-cli` + `sparq-server` binaries and in
the conformance/differential-fuzz harnesses ([FABLE-5] sq-7d3dj.30.13), so it is what real users and
the canonical benchmarks execute (bead
`sq-7d3dj.30.1`; design record `research/sp2bench-complex-shape-deficit.md` §2.1/§2.5/§4). With it ON,
`PreparedQuery::parse` (the single seam every string query entry point funnels through) and the two
EXPLAIN parse sites run the parsed `spargebra` algebra through `sparq_engine::rewrite::rewrite_query`
BEFORE evaluation. Two rewrites: **(a) equality substitution** — a `FILTER(?v = <iri>)` (also
`<iri> = ?v` / `sameTerm(?v, <iri>)`) whose `?v` occurs in the group's triple patterns folds the IRI
constant INTO those patterns (turning a post-join FILTER over every enumerated row into a
constant-seeded indexed scan; `?v` is re-bound via `Extend` so it stays in scope), and **(b)
anti-join** — `FILTER(!bound(?v), LeftJoin(A, B))` becomes `Minus(A, B)` when `?v` is certain in `B`,
absent from `A`, and `A`/`B` share a certain variable. **IRI-only:** rewrite (a) fires ONLY for
`NamedNode` constants (`=` on IRIs is term-identity, so the substitution is exact); a **literal**
equality (`?v = 1`, `?v = "1"^^xsd:decimal`) is NEVER rewritten — this is the deliberate avoidance
contract for the open value-equality/decimal bug `sq-lr2ii`. Every rewrite is **bag-result-equivalent**
(`query`/`ask`/`count`/`query_json` return the SAME answers on vs off — proven by
`tests/rewrite_pass.rs` plus the W3C conformance ratchet, which CI runs with the feature ON — the
`sparq-conformance` harness lights it, and the nightly sparq-vs-oxigraph differential fuzzer covers
the `FILTER(?v = <iri>)` trigger shape ON too since sq-7d3dj.30.13), and a shape that does
not exactly meet a rewrite's conditions is left **verbatim** (conservative). Note `From<Query>` does
NOT rewrite (it takes an already-built algebra as-is). When off, zero rewrite code compiles, the
default native + wasm builds are byte-identical, and no new dependencies are added (no `unsafe`).
- **Equality-FILTER → value join** is the non-default `value-join` cargo feature (bead
`sq-7d3dj.30.7`; the SP2Bench q05a/q12a star-intersection shape). With it ON, a conjunctive group
whose triple patterns form variable-DISJOINT connected components glued only by a top-level
`FILTER(?a = ?b)` conjunct evaluates each component separately and joins them with a hash join
keyed on the equality, instead of materialising the cross product and evaluating `=` per row.
**SPARQL `=` is VALUE equality, not term identity** (`"01"^^xsd:integer = "1.0"^^xsd:decimal` is
TRUE across two dictionary ids; incompatible types are a type error; high-precision
`xsd:decimal`s sharing an `f64` must stay unequal — `sq-lr2ii`), so a plain id-keyed join would
be wrong. Soundness is two-layer: the per-term-class key never misses an `=`-TRUE pair (id for
IRI/bnode/unknown classes, the `numeric_value` cache's canonicalised `f64` for numerics, value
for `xsd:string`/language-tagged/boolean), rows with no provable key (local-vocab ids, triple
terms, value-comparable temporals, numeric-datatype lexicals the numeric cache rejected — the
evaluator's trimming fallback can still pair those) pair through the EXACT evaluator, and the
original FILTER is re-applied verbatim over the joined rows — the exact recheck that eliminates any key collision
through the same `sq-lr2ii` machinery that runs today. Anything not provably eligible — a filter
with any function call (`RAND`/`BNODE` are row-nondeterministic, custom functions can error),
quoted-triple patterns, an armed query budget or `zk` trace, no cross-component equality —
DECLINES to the verbatim plan. Result-identical on eligible shapes (per-term-class kill-switch
differentials in `exec::eqjoin::tests` + an independent `!(?a != ?b)` oracle in
`tests/eqjoin_value_join.rs`, both run by the `opt-in sparq-engine (value-join)` CI leg). When
off, zero of this code compiles, the conjunctive path is byte-identical, no new dependencies.
- **Materialised-view / query-result cache** is the non-default `result-cache` cargo feature (bead
`sq-a9cn`): `ResultCache::new(capacity)` is a bounded, version-aware LRU that stores a SELECT/ASK
`QueryResult` keyed by `(parsed query algebra, caller graph-version)`; serve a query through
`cache.get_or_eval(&graph, &query, version, &budget)` (returns an `Arc<QueryResult>`). It re-serves
the same read query against a slowly-changing graph without re-executing. **Soundness contract**:
the engine evaluates against a borrowed `&Graph` and can't see mutations, so the **caller bumps the
`u64` version on every mutation** (`apply_delta`/`update`/reload) — a hit is only returned for the
current version. **Non-deterministic queries are never stored** — `NOW`/`RAND`/`UUID`/`STRUUID`/
`BNODE`, a remote `SERVICE`, or any custom function / aggregate; `is_cacheable(&query)` reports this
conservatively, and `get_or_eval` evaluates those fresh every time. Keying on the parsed algebra
makes the cache insensitive to whitespace / comments / prefix spelling. `cache.stats()` exposes
hit/miss/entry counts; `cache.clear()` drops all entries. When off, zero cache code compiles, the
default build is byte-identical, and no new dependencies are added.
```rust
// Cargo.toml: sparq-engine = { version = "0.1", features = ["result-cache"] }
use sparq_engine::{PreparedQuery, QueryBudget, ResultCache};
let cache = ResultCache::new(256); // up to 256 distinct results, LRU
let q = PreparedQuery::parse("SELECT ?s WHERE { ?s ?p ?o }")?.into_query();
let mut version = 0u64;
let r1 = cache.get_or_eval(&graph, &q, version, &QueryBudget::unlimited())?; // miss
let r2 = cache.get_or_eval(&graph, &q, version, &QueryBudget::unlimited())?; // hit (same Arc)
// ... mutate the graph, then bump the epoch so the next read re-evaluates:
version += 1;
let r3 = cache.get_or_eval(&graph, &q, version, &QueryBudget::unlimited())?; // miss (fresh)
# Ok::<(), String>(())
```
- **Sharing one `Graph` across server threads** — a `sparq_core::Graph` (and its read-only
`GraphSnapshot`) is **`Send + Sync`** (guaranteed by a compile-time assertion in `sparq-core`), so
it can be shared across the async handlers of an axum/actix/tower server directly with
`Arc<RwLock<Graph>>`. To skip that boilerplate, enable the non-default **`shared` cargo feature**
on `sparq-core` (bead `sq-yj76l`, gh #1121) for `shared::SharedGraph` — a cheaply-cloneable handle
(`SharedGraph::new(graph)` / `.clone()` is an `Arc` bump) with three access paths: `.snapshot()`
hands out a cheap immutable point-in-time `GraphSnapshot` you query **lock-free** for the request
(the recommended read-heavy path — the write lock is held only for the O(overlay) snapshot clone),
while `.read()` / `.write()` give RAII `RwLock` guards for ad-hoc locked access. It is `std::sync`
only (no new dependency) and off by default, so the lean default / wasm build pays nothing.
```rust
// Cargo.toml: sparq-core = { version = "0.1", features = ["shared"] }
use sparq_core::shared::SharedGraph;
let shared = SharedGraph::new(graph); // drop into axum `State`, clone per handler
let snap = shared.snapshot(); // cheap immutable view; query it lock-free
let _n = snap.len();
shared.write().apply_delta(&[], &[])?; // exclusive write lock only for the mutation
# Ok::<(), String>(())
```
- **MVCC / ACID transaction isolation** is the non-default `txn` cargo feature (bead `sq-it1x`):
`txn::TransactionManager::new(graph)` owns one logical graph and hands out **snapshot-isolation**
read transactions (`begin_read()` → a cheap point-in-time view that derefs to `&Graph`, immune to
later commits) and serialized **write** transactions (`begin_write()` → a copy-on-write fork).
`WriteTxn::update(sparql)` applies SPARQL `UPDATE`s to the private fork (read-your-own-writes via
`w.graph()`); `commit()` returns the new `u64` version, or `CommitError::Conflict` under
**first-committer-wins** if a concurrent writer published an overlapping write set since the txn
began (the whole body is then discarded — atomic rollback). A stale but *non*-conflicting writer's
resolved delta is replayed onto the current generation, so no commit is lost. For a single writer
the conflict check never fires (SI = serializability); durability is inherited from a directory-
backed graph's WAL. Built on the COW delta-overlay substrate; when off, zero txn code compiles and
the default build is byte-identical (no new deps).
```rust
// Cargo.toml: sparq-engine = { version = "0.1", features = ["txn"] }
use sparq_engine::txn::{CommitError, TransactionManager};
let m = TransactionManager::new(graph);
// Snapshot-isolation read: this view never changes underneath us.
let snap = m.begin_read();
let _n = sparq_engine::count(&snap, "SELECT * WHERE { ?s ?p ?o }")?;
// Write txn: fork, mutate the private copy, commit (first-committer-wins).
let mut w = m.begin_write();
w.update("INSERT DATA { <http://ex/s> <http://ex/p> <http://ex/o> }")?;
match w.commit() {
Ok(version) => println!("committed as v{version}"),
Err(CommitError::Conflict { .. }) => { /* retry against the new state */ }
}
# Ok::<(), String>(())
```
- **Default cargo features** (`parallel`, `regex`, `digest`): `regex` powers REGEX/REPLACE; `digest`
powers MD5/SHA*; `parallel` enables rayon scan/join/sort/aggregate. The **wasm** crate
(`sparq-wasm`) disables defaults, so on `wasm32-unknown-unknown` REGEX/hash builtins and
`QueryBudget::deadline` are absent (`max_rows` still works); UUID()/STRUUID() are native-only.
- **Composition**: `with_functions` and `with_view` install thread-locally (propagated into rayon
workers), nest in either order, and uninstall on return/unwind. The registry is cheap to clone
(`Arc`-shared) — build once, reuse across queries/threads.
- **Performance**: `query_json` avoids per-cell `Term` allocation; `count` avoids materialisation;
prefer `PreparedQuery` when running one query against many graphs (e.g. continuous/RSP queries).
- **CLI/HTTP alternative**: `sparq-cli` and `sparq-server` (W3C SPARQL Protocol, `?explain=`,
result formats JSON/XML/CSV/TSV, `/metrics`) wrap this same surface if you don't want to embed.
- **Apache Arrow columnar import/export** is the opt-in `sparq-arrow` crate (separate leaf crate +
its own `arrow` feature, both OFF the default build — the `arrow-*` deps NEVER reach
`sparq-core`/`sparq-engine`/wasm). `sparq_arrow::to_record_batch(&QueryResult) -> RecordBatch`
projects a SELECT result into one Arrow **struct column per variable**, and
`sparq_arrow::from_record_batch(&RecordBatch) -> Result<QueryResult, ArrowError>` is its
checked inverse —
`Struct<kind, value, datatype, language, direction>` (all nullable `Utf8`; the field names are
`sparq_arrow::RDF_TERM_FIELDS`). Faithful & round-trippable: an **unbound** binding is a `null`
struct slot (distinct from a bound empty string); `xsd:string` is written **explicitly** (not
elided). Honest v1 boundaries — **no numeric narrowing** (`42^^xsd:integer` is the string `"42"`
+ a datatype field, not an `Int64`; a typed-column view is a follow-up) and **triple terms are
stringified** to N-Triples in `value`. Import rejects malformed schemas, term kinds, and
incompatible field combinations instead of guessing. The intended on-ramp into
Polars/DuckDB/pandas; a
`sparq-py` `Graph.query_arrow() -> pyarrow.Table` PyO3 binding is a follow-up (bead `sq-lt1ml`).
## See also
- `rust-parallel-parsing` / `fused-decompress-parse` — fast/compressed RDF ingest into a `Graph`.
- `hdt-format` — loading `.hdt` archives into a `Graph` (`sparq-hdt`).
- `sparq-arrow` — opt-in Apache Arrow columnar import/export between a SELECT `QueryResult`
and a `RecordBatch` (one struct column per variable) for dataframe interoperability.
- `sparql-formal-semantics` — the algebra/semantics reference for the SPARQL fragment.
- `noir-circuit-patterns` / `verifiable-credentials-zk` / `mpc-protocols` — the ZK/MPC estate built
on the `zk` trace seam (non-default `zk` feature; consumed by `sparq-zk`).