| 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:
[dependencies]
sparq-core = "0.1"
sparq-engine = "0.1"
oxrdf = { version = "0.3", features = ["rdf-12"] }
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" ."#;
let g = Graph::load_str(ttl, "turtle").unwrap();
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 {
println!("{:?}", row[0].as_ref().map(|t| t.to_string()));
}
let json = sparq_engine::query_json(&g, "SELECT (COUNT(*) AS ?n) WHERE { ?s ?p ?o }").unwrap();
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:
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.
Common recipes
Aggregates, GROUP BY / HAVING, subqueries — standard SPARQL 1.1; no special API:
sparq_engine::query(&g,
"SELECT ?p (COUNT(*) AS ?c) WHERE { ?s ?p ?o } GROUP BY ?p HAVING (COUNT(*) >= 2)").unwrap();
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:
sparq_engine::query(&g,
"PREFIX ex: <http://ex/> SELECT ?x WHERE { ex:alice ex:knows+ ?x }").unwrap();
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.
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:
let result = sparq_engine::query_paths(&g,
"PREFIX ex: <http://ex/> PATHS SHORTEST START ?s = ex:alice END ?e = ex:bob VIA ex:knows")?;
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.
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();
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:
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();
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:
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();
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.
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();
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:
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,
frame: None,
new_var: Variable::new("rank").unwrap(),
};
let ranked = apply_window(&result, &spec).unwrap();
(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):
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();
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)":
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),
#[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);
Named-graph dataset view (zero-copy restriction; a non-visible graph is indistinguishable from
an absent one):
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();
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.
use sparq_engine::{params::value, query_prepared, update_prepared, PreparedQuery, PreparedUpdate};
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))?;
let _ = query_prepared(&graph, &pq)?;
let pq = PreparedQuery::parse("SELECT ?o WHERE { ?who <http://ex/name> ?o }")?
.bind("who", value::iri("http://ex/alice")?)?;
let _ = query_prepared(&graph, &pq)?;
let pu = PreparedUpdate::parse("INSERT { <http://ex/x> <http://ex/note> ?n } WHERE { }")?
.bind("n", value::string(hostile))?;
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:
let rows = sparq_engine::query(&graph, sparql)?;
let greedy = sparq_engine::without_dp_planner(|| sparq_engine::query(&graph, sparql))?;
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:decimals 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.
use sparq_engine::{PreparedQuery, QueryBudget, ResultCache};
let cache = ResultCache::new(256);
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())?;
let r2 = cache.get_or_eval(&graph, &q, version, &QueryBudget::unlimited())?;
version += 1;
let r3 = cache.get_or_eval(&graph, &q, version, &QueryBudget::unlimited())?;
# 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.
use sparq_core::shared::SharedGraph;
let shared = SharedGraph::new(graph);
let snap = shared.snapshot();
let _n = snap.len();
shared.write().apply_delta(&[], &[])?;
# 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 UPDATEs 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).
use sparq_engine::txn::{CommitError, TransactionManager};
let m = TransactionManager::new(graph);
let snap = m.begin_read();
let _n = sparq_engine::count(&snap, "SELECT * WHERE { ?s ?p ?o }")?;
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 { .. }) => { }
}
# 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
