SPARQL planner and executor optimizations

Why. SPARQL join, union, optional, minus, filter, and extend all have identities on the empty table (zero rows) and the empty singleton (one row, zero columns — Sparopt’s encoding of { }). Folding them avoids walking dead subtrees.

Problem. A join against VALUES {} or a FILTER(false) would otherwise still scan the other side.

Algebra (join). Empty annihilates; the empty singleton is the join identity:

Algebra (optional / minus / extend / slice / group / distinct).

SPARQL. { } becomes Sparopt’s empty singleton (VALUES with no variables and one empty row). Waratah later lowers that to PlanNode::Unit and drops it from a multi-leaf join pipeline. VALUES { } (zero rows) is not the identity: it wipes a join.

Waratah does see this: comments in lower_values distinguish the two VALUES shapes.

Why. A filter whose effective boolean value (EBV) is known at plan time is either a no-op or an empty result.

Problem. FILTER(true) and nested FILTER(A) { FILTER(B) { … } } add operators that do not change cardinality.

Algebra.

AND/OR constructors also fold EBV: true && E → E, false && E → false, true || E → true, false || E → E. NOT NOT on a boolean-typed expression unwraps.

Why. IN is a convenience form of equality disjunction. Normalizing it lets later = constant-fold and filter-push use one code path.

Problem. A special-case IN evaluator would duplicate equality logic.

SPARQL before.

SPARQL / algebra after.

Why. Comparing two ground IRIs or two identical literals does not need runtime evaluation.

Problem. FILTER(<a> = <a>) would otherwise sit on the plan as a real predicate.

Algebra.

Why. SPARQL value equality (=) on IRIs and blank nodes is the same as term identity. Rewriting to sameTerm lets type inference treat the comparison as identity.

Problem. Leaving IRI = as value equality would force the slower literal-aware = path.

Algebra. If neither side can be a literal (and, with SPARQL 1.2, neither can be a triple term), Equal(L, R) becomes SameTerm(L, R). Comparisons that might involve literals stay Equal.

Waratah later uses a stricter identity fold of its own (section 2.4): even after this rewrite, numeric = is not folded into hexastore slots.

Why. Type inference knows whether a variable is always bound, never bound, or maybe unbound.

Problem. BOUND(?x) after a required triple pattern is always true; after a variable that never appears it is always false.

Algebra.

Why. EXISTS { } is true; EXISTS of an empty table is false.

Algebra.

Why. A ground boolean condition selects one branch at plan time.

Algebra.

Why. A VALUES column that is UNDEF in every row does not bind anything.

Problem. Extra UNDEF columns inflate join keys and projection lists.

Algebra. Values drops columns (and the matching cell in every row) where no row has a defined term.

Why. Nested UNION is associative; an empty arm contributes no solutions.

Algebra.

Sparopt also hash-orders UNION / AND / OR argument lists for a canonical form. That is a normalize-for-equality rewrite, not a cost-based one.

Why. During normalize, if a FILTER or EXTEND expression is inferred to be always UNDEF, it cannot produce a useful value.

Algebra.

The Extend case is marked TODO: valid? in Sparopt — Waratah may still see a dropped BIND if Sparopt fires it.

Why. Inner joins are associative and commutative. Evaluating a selective pattern first keeps intermediate results small.

Problem. Left-to-right BGP order from the query text often starts with a broad ?s ?p ?o or an unbound type scan.

How. Flatten the inner-join tree into a list of children. Repeatedly:

Size estimates are a fixed heuristic, not Waratah sketches. Examples from Sparopt’s estimate_triple_pattern_size:

SPARQL before (parser / left-to-right join):

Algebra after Sparopt (typical). The more-bound weather pattern is smaller (P+O bound ≈ 10_000 vs only P bound ≈ 1_000_000), so it becomes the left child:

Waratah interaction. For a flat tree of BGPs and VALUES, Waratah rebuilds this order from sketches or a bound-slot fallback (section 2.2). Sparopt’s order still matters for non-flat trees (joins mixed with FILTER, OPTIONAL, UNION, non-ground BIND).

Why. A filter that only uses variables bound by one join child can run on that child before the join, shrinking the build/probe side.

Problem. A filter sitting above a join evaluates after both sides are produced.

SPARQL before.

Algebra after (schematic). ?w is bound only on the weather pattern, so the conjunct is pushed into that child (and, after Waratah’s identity fold, becomes a ground object slot — section 2.4):

Push rules:

Covered in the LeftJoin row above. SPARQL:

can become a LeftJoin whose expression is true and whose right child is Filter(scan, ?o = "x"). Waratah then folds that identity filter into the optional scan (section 2.4).

These still exist in the crate:

Waratah rejects top-level REDUCED, ORDER BY (also inside sub-SELECTs), MINUS, and SERVICE as unsupported shapes. Top-level DISTINCT is supported: it is peeled in prepare_algebra and drives the liveness marks / leaf collapse (section 2.9). Nested SELECT is supported (section 2.12).

Where. push_values_into_union / distribute_values_over_union in waratah_compute/src/plan.rs, immediately after Sparopt.

Why. Join distributes over union: Join(V, Union(A, B)) ≡ Union(Join(V, A), Join(V, B)). Copying a small VALUES table into each arm lets that arm’s scan see the join key locally (and later broadcast or ground it). A ground BIND(<iri> AS ?x) over { } is the same as a one-row VALUES, so it is rewritten first so the same distribute path applies.

Problem. Join(Values, Union(scan₁, scan₂)) executes as "build the union of two unbound scans, then probe with the small table." Each scan can miss a selective hexastore prefix. After the push, each arm is Join(Values, scan) and can broadcast the VALUES terms into that scan.

SPARQL before.

Algebra before (after Sparopt, schematic).

Algebra after.

The same rewrite fires for nested UNION (a copy per arm). Ground BIND:

Algebra. Extend(EmptySingleton, ?b, <brisbane>) → Values { ?b → brisbane }, then the VALUES push above.

Not rewritten. BIND(?x AS ?y) after a scan stays Extend. Only a BIND whose inner pattern is the join identity ({ } / unit VALUES) and whose expression is a ground IRI or literal becomes VALUES.

Where. order_pipeline_leaves / lower_pipeline (pre-sort + lowering fold) and reassociate_inner_joins (post-identity-folding rebuild), all in waratah_compute/src/plan.rs. EXPLAIN Level 1 (optimised / optimised-sparql) does not apply sketch BGP order — it is Sparopt
VALUES-into-UNION on the restored GraphPattern. Level 2 (planned / planned-sparql / estimate) prints the lowered PlanNode order.

Why. Sparopt’s sizes are a static table. Waratah has a local waratah_stats/src/profile.rs StatsProfile: exact predicate counts, exact rdf:type class counts, subject/object Count-Min Sketches, and per-predicate HyperLogLog distinct S/P and P/O. The planner must pick scan order in microseconds without a storage RPC.

Problem. Starting with ?person rdf:type :Person (millions of rows) then joining to a rare hometown scans far more data than the reverse.

How. Two stages. At lowering, a flat inner-join of BGPs and VALUES is collected into leaves, sorted by (produced_row_count_estimate asc, bound_slots desc) (VALUES use (row_count, bound_slots = 3); empty-profile fallback (3 − bound_slots) × 1_000_000), and folded left-to-right through join_nodes. After identity folding and the plugin rewrites, reassociate_inner_joins flattens every ≥3-operand inner-Join spine and rebuilds it with fold_nodes_cost_based: seed = the first pre-sorted operand, then repeatedly attach the remaining operand with the smallest finalize_inner_join_meta output. Cartesian candidates compete on the same scale (|L|·|R| when no always-bound variable is shared) — no connected-first rule, so a cheap cartesian legitimately beats an expensive connected join. Filter-split pools are whole again here (a saturated identity filter node is gone); a plugin CustomNode cluster is ONE pool operand when its op carries the CustomOpCost stamp and no pins — the "custom cluster operand", whose selectivity seats against every other arm of the spine — while unpriced or pinned clusters keep the whole spine frozen; OPTIONAL/UNION arms and surviving filters still bound association. Left-deep from a fixed seed; wrong picks cost performance, never results.

SPARQL.

After (when sketches say the hometown pattern is smaller). Left leaf is the Brisbane pattern (route to O); the type scan is the probe side.

Without a profile, the same query still puts "Sunny" / a bound object first because it has more bound slots (selective_pattern_is_scanned_first).

Where. lower_pattern threads IncomingBound into order_pipeline_leaves. Distinct counts come from join_key_domain_for_node bounded by left.produced_row_count_estimate(). There is no GraphPattern domain twin: EXPLAIN planned / estimate show this order on PlanNode; Level 1 does not reorder OPTIONAL BGPs.

Why. The OPTIONAL right is a bind join: left always-bound vars (?rack) will be allow-listed on any scan that has them in a slot. Leaf order that pretends those vars are unbound starts with ?server a :Server (exact class count / P+O bound) and scans every Server. Costing only one typical key (|P| / distinct objects) hides a large rack list behind a small per-key row multiplicity.

Problem. OPTIONAL { ?y a :Y ; :locatedIn ?x } with ?x required on the left costed :locatedIn ?x as predicate-only, then as a single-key row estimate. Sparopt 0.3.6 (sep-0006 off) does the same. Oxigraph LATERAL is not used. Execution already allow-lists all distinct left values in one scan.

How. Right-side leaves see incoming ∪ left.always_bound with a distinct count per name (None = bound but unknown → keep the per-key row estimate). A slot whose variable is in that set counts as bound for sketches (HLL |P| / distinct O or |P| / distinct S, no dummy CMS term) and for the empty-profile (3 − bound_slots) × 1_000_000 fallback (not scaled by domain). With a profile, a one-end extra slot with a known domain is costed as min(|P|, row multiplicity × distinct incoming). Over BROADCAST_ROW_THRESHOLD (24_576) distinct keys the executor will not push a new allow-list (enforce_push_threshold on OPTIONAL), so the planner costs that probe as unbound |P|. Sort key is (produced_row_count_estimate asc, bound_slots including incoming desc, incoming_slots desc) so a type pattern and an incoming-bound property that tie on the first two keys still put the FK first. Encoded scan patterns stay variables. Nested OPTIONAL { t1 . t2 . OPTIONAL { … } } passes the outer key into the nested left BGP as well. Maybe-unbound vars from an OPTIONAL left do not leak into a later OPTIONAL right.

SPARQL.

Plan after. Inner join driver is :locatedIn ?rack when the left is small (optional_fk_pattern_ordered_before_type_with_profile). A large rack list with a small :Server class reverses that (optional_large_incoming_domain_lets_small_type_scan_drive). restamp_broadcast_marks claims the FK scan (marks broadcast) at the planning boundary afterward.

Where. join_nodes → JoinStrategy::from_cardinalities_and_domains. Threshold: BROADCAST_ROW_THRESHOLD = 24_576.

Why. The physical operator should match intermediate size. A 12-row city list should not hash-build a million-row livesIn scan; two huge sides should not sit in one monolithic hash table if they can be bucketed.

Problem. A single hash-join implementation either over-scans storage (no allow-list) or over-partitions tiny joins.

How. Estimated left/right row counts, optionally replaced by HLL join-key domains bounded to min(domain, rows):

A small HLL domain can pick Broadcast even when row estimates are large (hll_domain_selects_broadcast_despite_large_row_estimates). Small VALUES as the left of a scan also hints Broadcast (small_values_sorts_left_of_a_scan_and_hints_broadcast). When both children of a Join bind the same key, join_key_domain_for_node uses the smaller child domain (intersection upper bound), not the first known child, so a later join can still broadcast (join_intersection_domain_selects_broadcast_not_first_child). Union arms combine domains by sum, and one unknown arm contributes its row estimate when it hosts the key (dom ≤ rows, a sound upper bound) instead of discarding the known arm’s sketch; both unknown stays the bare-scan None.

This is a plan annotation, not an algebra shape change.

Where. fold_identity_filters after lowering. Walks Join, Union, LeftJoin, Filter, Extend, Slice, Group.

Why. A hexastore prefix on a bound object is orders of magnitude cheaper than scanning ?s :p ?o and applying FILTER(?o = <iri>) in compute. Encoded-term identity matches SPARQL sameTerm and a subset of = (IRI, plain/lang string, boolean). Numeric = is value equality (1 vs 1.0e0) and must not be folded.

Problem. Post-scan FILTER after a wide unbound scan; also, a FILTER sitting on a UNION would otherwise not ground either arm’s pattern.

SPARQL before.

Plan after. No Filter node. Scan still projects ?o, but pattern.object is the encoded "Sunny" literal (routes to O / OPSG).

sameTerm(?c, http://ex/Brisbane) folds for any ground term. FILTER(?v = 1.0e0) stays a Filter.

UNION / join arms. ground_identity_term walks the subtree once and returns two facts: rewrote_scan (|| — prefix every Scan/Path slot) and producers_constrained (&& over producers of the variable; a child that does not produce it is ignored). The FILTER is dropped only when every producer emits the same term (and the variable is always-bound). Sparopt may first copy the filter into both UNION arms (section 1.13); Waratah then folds each copy independently.

Both arms are scans, so both ground ?c and both copies of the FILTER drop.

A VALUES arm that binds the same variable to a different constant is a producer that disagrees: the scan arm is still prefixed (rewrote_scan), but the FILTER stays on that VALUES arm (or above the UNION) so those rows cannot leak.

The same producers_constrained bit is used when folding an OPTIONAL early_filter into the right side (fold_left_join_early_into_right).

OPTIONAL. An identity filter inside the optional group folds into the right scan:

An outer FILTER(?w = "Sunny") after OPTIONAL must not fold away: ?w is maybe-unbound; grounding it would turn OPTIONAL into a required match. The scan is still grounded; the Filter node is kept.

Var-var sameTerm / identity-safe = via BIND or singleton VALUES. identity_safe_equality also accepts two variables when unique_ground_term finds a unique constant for one of them (ground BIND(<iri> AS ?c), or a VALUES cell that agrees in every row — including VALUES (?a ?b) { (<a> <b>) }, one cell per column). The other variable’s scan/path slot is grounded; the BIND/VALUES column is not rewritten onto the scan. Multi-row VALUES ?c { <a> <b> } is not folded (no unique term; a later join-key / allow-list rewrite). The same lookup runs on OPTIONAL early filters (fold_left_join_early_into_right), so OPTIONAL { ?b ?p ?o . BIND(<iri> AS ?c) FILTER(sameTerm(?b, ?c)) } grounds the right scan. Numeric FILTER(?v = ?c) after BIND(1.0e0 AS ?c) stays a Filter.

Plan after. No Filter. Extend ?c remains. Scan still projects ?b, but pattern.subject is CrowHill.

Where. ground_and_recost_broadcasted_arm when lowering LeftJoin and from join_nodes/refinalize_joins when the inner-join strategy is Broadcast (grounding only); restamp_broadcast_marks — the sole writer of the broadcast marks — re-derives them at every planning boundary (pre-order, outermost join’s claim wins).

Why. Broadcast is a bind join: the small left side’s join-key terms become an allow-list on the probe. OPTIONAL always works that way. Inner joins do too once join_nodes stamps Broadcast (including after a scan↔Union driver swap). EXPLAIN splits two annotations: broadcast is the runtime allow-list slot (one variable, one slot); grounded is plan-time prefix slots (variable names kept for projection; encoded terms already in the triple). When the left join key is one plan-time constant (one-row VALUES, ground BIND), OPTIONAL and inner Broadcast prefix that term into every matching probe Scan/Path slot and stamp grounded only. Multi-row VALUES stay unbound plus broadcast (unique_ground_term / ValuesOp::unique_term is None). Hash and Shuffle joins are not prefixed. Identity FILTER fold (2.4) also records grounded on every matching slot of a repeated variable (?b a ?b). Identity fold does not overwrite an already-prefixed slot with a different IRI; the FILTER stays.

Problem. OPTIONAL { ?s :p ?b } with BIND(<brisbane> AS ?b) would scan all :p triples unless ?b is bound into the object slot. The same gap on an inner Join(?tenant a :Tenant, Union(:hasTenant arms)) would still show unbound catalog cardinality on :hasTenant even though execution will push ?tenant.

SPARQL (OPTIONAL).

Plan after. Both UNION scans on the optional side get grounded: (?b → object) and pattern.object = brisbane. Estimated rows drop off the unbound ~3e6 fallback. Join strategy is still Broadcast; there is no broadcast annotation because the slot is already a plan-time constant.

SPARQL (inner Join).

Plan after (scan left, small type domain). Both :hasTenant scans get [broadcast ?tenant → object]; Server/VM type scans are unchanged (no ?tenant slot). Union left (small :hasTenant object domain): ?tenant a :Tenant gets [broadcast ?tenant → subject]. The Tenant BGP is not copied into the UNION arms.

SPARQL (inner Join, singleton VALUES).

Plan after. VALUES is the Broadcast left. The :livesIn scan still projects ?city and gets pattern.object = brisbane plus [grounded ?city → object] (no broadcast annotation). Two-row VALUES ?city { <brisbane> <sydney> } stays unbound object plus [broadcast ?city → object].

The same walk enters nested OPTIONAL and inner joins on the probe (explain_nested_optional_broadcasts_outer_key). Hash and Shuffle joins are not annotated.

Where. prefer_broadcast_for_small_slice / rewrite_scan_joins_to_broadcast; ASK via cap_ask_slice (function name kept verbatim from the source).

Why. Hash and shuffle build the entire right side before probing. If the query only needs one row (ASK, LIMIT 1), that build is wasted. Broadcast nested-loops left batches into an allow-listed right scan and can stop when the slice is full.

Problem. ASK { ?s :p ?o . ?s :q ?x } would otherwise hash-join two unbounded scans.

How. If OFFSET + LIMIT is in 1..=24_576 (ASK is limited to LIMIT 1, unless the query already said LIMIT 0), every inner join whose right child is a Scan (or Filter/Extend over a Scan) is rewritten to JoinStrategy::Broadcast.

SPARQL before / after. Same query text; only the join strategy changes:

Unbounded: Hash (no statistics). With LIMIT 1 or ASK { … }: Broadcast.

Inequality filters are not identity-folded, but Broadcast still sees through a Filter wrapper on the right scan (ask_inequality_filter_broadcasts_through_filter).

Where. split_filter in waratah_compute/src/expr/capability.rs.

Why. Most FILTERs (sameTerm, =, BOUND, !, &&, ||, isIRI, LANG, LANGMATCHES) can run on encoded GUIDs. STR, REGEX, … need the string registry. Splitting conjuncts keeps the common path off the network.

Problem. A single "always resolve" FILTER stage would registry-lookup every row.

Algebra / plan. Top-level && conjuncts are classified independently:

An || or ! tree that contains any AlwaysResolve conjunct moves entirely to residual (no partial OR across stages). Unsupported expressions error at plan time. Identity fold (2.4) consumes early conjuncts only.

Numeric + - * / and DATATYPE are early (MaybeEncoded / AlwaysEncoded): they run on native EncodedTerm variants. DATATYPE(?l + ?r) is not a separate type-inference pass — eval is bottom-up, so the add result’s enum variant is the promoted XSD type, and DATATYPE maps that to a well-known IRI hash (xsd:integer, …) without the string registry. Projecting BIND(DATATYPE(?x) AS ?d) decodes those hashes via well_known_iri.

LANG and LANGMATCHES are early MaybeEncoded (hashed language tags and long range strings still NeedsResolve). LANG of an inline language tag (SmallSmall / BigSmall) is a SmallStringLiteral; untagged literals yield "". Hashed tags (SmallBig / BigBig) and hashed ranges finish on the residual ground path. LANGMATCHES is RFC 4647 basic filtering (XPath fn:lang) — case-insensitive prefix, not string =. The usual LANGMATCHES(LANG(?v), "en") form composes the two functions; no planner rewrite.

Why. Sparopt encodes { } as a zero-column VALUES singleton (join identity). Leaving it in a pipeline would add a useless join with Unit.

Problem. Distinguishing that from VALUES {} (zero rows), which must wipe the join.

Plan. Unit VALUES → PlanNode::Unit, then stripped when other leaves exist. VALUES {} stays a zero-row Values node.

Where. annotate_liveness in waratah_compute/src/liveness.rs, after identity-FILTER fold and before refinalize_joins. The top-level distinct flag peeled in prepare_algebra seeds the walk.

Why. Aggregate, collapse, and SELECT DISTINCT decisions are per-variable, not per-query. A scan slot the query never observes is pure waste: it widens the TermId schema, inflates join schemas, and — for SELECT DISTINCT ?class — makes the scan emit one row per matching triple when the query only needs one row per distinct term. Conversely, treating a projection column as "distinct" when an aggregate needs its multiplicity would silently drop rows.

Problem. Until this pass, SELECT DISTINCT ?class WHERE { ?inst a ?class } planned like a plain ?inst a ?class scan (one row per type triple), and there was no way to say "the scan may drop duplicates on ?class" or "?inst need never materialize".

How. A top-down walk carries a required: var → BagMark map from the query projection (Insensitive under SELECT DISTINCT, else Sensitive; None = dead). Each operator propagates it:

Each ScanOp stores the marks (scan.marks, see EXPLAIN in section 3.14). A variable with no mark is dead: ScanOp::variables() omits it, so the column never enters the TermId schema (EncodedSolutions::from_scan builds only live columns). Slot names (scan.subject / scan.object, …) stay Some — later stages (identity fold checks, S=O equality, broadcast slot stamping) still need to know which slots a variable occupies.

SPARQL before / after (dead column).

?inst is a join key but never projected: both scans carry it in their patterns, but neither materializes an ?inst column. ?class on the label scan is dead the same way.

Marks are semantics, not heuristics. Insensitive flows only from SELECT DISTINCT / GROUP BY keys (and only when no multiplicity aggregate needs the input bag); expression variables under a surviving FILTER or BIND are forced Sensitive by require_expr_sensitive. The domain_scan gates (2.10) then refuse any shape the RPC cannot enforce on top of those marks, so the rewrite can only fire where storage’s answer is exact.

Where. Liveness gates in waratah_compute/src/liveness.rs (domain_scan_eligible); collapse keys on ScanOp (collapse_keys / will_collapse in waratah_compute/src/plan.rs); execution in fetch_whole_scan_solutions / scan_domain_page in waratah_compute/src/query.rs; the P-axis PredicateDomain RPC in waratah_proto/proto/waratah.proto and the POSG loop in waratah_storage/src/encode/domain.rs + rocksdb.rs / memory.rs.

Why (collapse). A bag-insensitive scan under SELECT DISTINCT still returns one row per matching triple; the Distinct node above collapses afterward. Collapsing at the leaf (compute-side DISTINCT ON over the insensitive keys, streamed across scan pages with a cross-page DistinctState) shrinks every batch that ever enters the join tree.

Why (domain scan). SELECT DISTINCT ?class WHERE { ?inst a ?class } has the degenerate shape "distinct objects of a predicate". The hexastore already stores that answer physically: under POSG, each P‖O prefix repeats per version/graph, so a scan that emits only the first visible object per P-prefix — then seeks past the rest of that object — produces the distinct (P, O) domain in one partition pass, touching O once instead of once per subject. Dead ?inst means the client never needed S at all; this is the one query shape where storage can answer DISTINCT by construction, with no dedup structure.

Problem. The general RPC cannot do this: ScanPattern keys include S (and the response row is a quad), so storage cannot know which column is the "distinct" one or safely skip S duplicates. A dedicated RPC that never returns S can.

RPC. PredicateDomain(PredicateDomainRequest) on the P partition only (S/O return UNIMPLEMENTED). Request: predicates (allow-list, NamedNode-only — validated and deduplicated by prepare_domain_predicates), snapshot_id, limit (counts emitted (P, O) pairs; 0 = unlimited), graph_name (present-but-empty = DefaultGraph), graph_filter_terms
graph_filter_allow (same block/allow-list semantics as ScanPattern), merge_default_graph, and an exclusive resume cursor start_after_predicate / start_after_object. Response: repeated PredicateDomainHit { predicate, object }.

Storage loop (POSG, both backends). For each allow-listed predicate in request order: seek P‖ (or the resume seek, below); walk versions; consider_domain_key picks the newest commit_ts ≤ snapshot version per logical quad (MVCC Put visible / Delete retires, exactly like ScanPattern), skipping already-decided quads via SnapshotScanState. On the first visible object: unconstrained G (empty block-list, no bound graph) emits O and never decodes G; constrained G (bound graph_name or non-empty filter) decodes the quad and applies domain_graph_allows — a Put whose G is rejected does not emit its O (another G may still own that (P, O)). After emitting, seek(byte_successor(P‖O)) jumps past every other S and version of that object; a Delete/rejected version just next()s within the same object.

Resume cursor. domain_resume_seek(predicate, start_after_p, start_after_o) per allow-listed predicate: sorts before the cursor ⇒ skip the whole predicate; equal predicate ⇒ seek byte_successor(P‖O); greater ⇒ normal prefix seek. The compute driver pages at SCAN_BATCH and loops to EOF (fetch_whole_scan_solutions always drains to EOF — a first non-empty page is not the end of a domain).

Plan gates (domain_scan_eligible). The rewrite fires only when every gate holds:

clear_broadcast_marks (join-order re-walk) clears domain_scan together with broadcast, so a re-planned subtree never keeps a stale rewrite.

Execution. domain_predicates builds the request’s predicate list (pattern slot, or the pushed broadcast terms — the liveness gate already limited that list to BROADCAST_ROW_THRESHOLD); from_domain_hits builds a solutions batch from the live P/O columns only. snapshot.scan_predicate_domain + retry/TraceEvent::ScanPage mirror the triple-scan path.

SPARQL before / after.

Before: scan every type triple (all subjects), then Distinct in compute. After: one P-axis PredicateDomain RPC; storage emits each distinct class once.

Costing (recost_scan / domain_scan_estimated_rows). A domain_scan estimates rows from the object HLL (objects_per_predicate for the predicate, when loaded); fall back to the pattern estimate. A plain bag-insensitive collapse scan takes min(pattern_rows, single-key domain) — the pattern estimate stays authoritative when other bound slots are selective (?class a <owl:Class>: the key ?class reads the global rdf:type subject HLL, the ground object reads the exact class map — min keeps 843, not 74M); a multi-key collapse keeps the pre-collapse row count (distinct pairs ≥ distinct first-key values, so a single-var HLL cannot bound it).

EXPLAIN output (estimate format). Scan lines print (domain_scan) and per-variable marks. Real output for the query above, no profile loaded:

~N is the row estimate (printed after ( of the operator it costs — inside (triple for scans); (domain ?v N | ?) is the join-key domain, ? = unknown without a profile; (bag_insensitive ?v) marks a collapse key; (dead ?v) a dropped column; (domain_scan) the rewrite. With a profile loaded, the scan estimate becomes the object HLL (distinct classes), not the type-triple count — see the costing note above.

distribute_values_over_union still has a TODO of the form:

That identity is legal when the ⊆ check holds, including when it is vacuous (V shares nothing with C). Blindly applying it to Sparopt’s nearest LeftJoin is not a performance win: if B does not join with V, the move is a cartesian on the OPTIONAL left and makes probes larger. Inner Join(L, LeftJoin(B2, C2)) also does not push V into a second OPTIONAL until the same local rewrite runs on that pair.

A correct GraphPattern pass (no sketches) would:

Do not implement the TODO as written. EXPLAIN Level 1 stays Sparopt
VALUES-into-UNION and does not include this pass.

Plan-level implementation (Part 3). delay_optional_through_join (waratah_compute/src/plan.rs) implements this condition set on the lowered PlanNode tree, where the sketch profile prices the decision: condition (1)'s two checks are the hash-keys-non-empty and §2.11-scope gates, (2) is the both-orientations match after the arm swap plus post-order bubbling, and (3) is satisfied by moving R (never copying) into the new required-side join built through join_nodes. See section 3.15. The GraphPattern-level pass above remains unimplemented — at plan level the delay covers the same shapes with estimates the algebra pass would lack.

Nested SELECT lowers to an opaque PlanNode::SubSelect { inner, variables } (lower_subselect). The boundary owns the sub-select’s modifier spine: spargebra wraps every sub-select as Slice?(Distinct?(Project(body))), and the lowering peels all four shapes so the boundary’s inner is Slice?(Distinct?(body)) in SPARQL order (Distinct strictly below Slice — the operators do not commute, so the nesting is load-bearing). The boundary is the scope barrier for everything above it:

Grounding pushdown (push_groundings_into_subselects, after push_values_into_union). A VALUES table joined next to a sub-SELECT is cloned into the subquery body whenever every VALUES variable is in the subquery’s SELECT list and the body spine is Slice-only; the clone joins below the bottom-most spine Slice (Project(Slice(Join(VALUES, body)))), so the inner scans pre-constrain before the subquery’s own LIMIT selects. Conformance: an unordered slice may select any n rows, so every answer of any-n-of(filter(B)) is a legal answer of filter(any-n-of(B)) — the same freedom Waratah already exercises for unordered OFFSET paging. A ground BIND sibling acts as a virtual one-row VALUES for the same insertion while the Extend stays in place (detaching it unconditionally would seed hash-key-less cross joins in plans with no subquery). VALUES are cloned, never moved.

Guards: Distinct / Reduced spines are skipped in v1 (dedup domain), Group spines are unsound to cross (groups and aggregate values are deterministic), and OPTIONAL sides are structural barriers (an outer Values must never filter an OPTIONAL’s input — that changes miss rows, not just surviving rows). FILTER conjuncts need no equivalent pass: Sparopt already pushes deterministic outer filters into subquery bodies, soundly and slice-aware.

Where. replace_filter_forced_joins in waratah_compute/src/optional_to_join.rs, after push_values_into_union and before lowering. prepare_algebra and lower_exists_clause both call it. A nested SELECT starts a fresh FILTER list (an outer FILTER does not rewrite an OPTIONAL inside the sub-select).

Why. Graph Explorer emits OPTIONAL { ?inst rdfs:label ?search1 } before { ?inst a :City }, then FILTER(STRSTARTS(STR(?search1), "Brisbane")). The optional’s left side is empty, so ?inst is not a hard join key and execution nested-loops every label row against every city.

What it does. For each OPTIONAL, list the variables that only that optional pattern binds. Remove any variable that another pattern under the same FILTER can also bind (an inner join copies that value in, so a failed optional can still reach the filter with the variable filled). If a FILTER condition above the OPTIONAL is false or an error when the variables still on the list are empty, replace the OPTIONAL with an inner join of the same two children. The FILTER stays.

v1 recognises STRSTARTS / CONTAINS / STRENDS / REGEX of STR(?v) or ?v, and isIRI / isLiteral / isBlank / isNumeric. OR, COALESCE, IF, BOUND, and NOT are left alone. The OPTIONAL’s own condition is not used.

SPARQL before.

After. The OPTIONAL is gone. ?inst is a hard join key between the label pattern and the city pattern. The FILTER is still there.

Not rewritten. { ?s :p ?o OPTIONAL { ?s :q ?x } ?x :r ?y FILTER(strstarts(str(?x), "a")) } — ?x :r ?y fills ?x before the FILTER runs. REGEX(COALESCE(STR(?search1), STR(?extractedLabel)), …) is not recognised.

Why. IRIs and long literals are large. Joins and filters compare 128-bit encoded terms. The string registry is a separate process.

Problem. Resolving strings before the join multiplies registry I/O by intermediate cardinality (including join keys the query never projects).

How. Scans return EncodedTerm columns. Joins, early FILTER, and aggregates stay on those buffers. resolve_strings runs for projected SELECT bindings, CONSTRUCT/DESCRIBE graph terms, and residual FILTER windows. ASK returns a boolean and never materializes bindings.

SPARQL. SELECT ?person ?weather WHERE { ?person :livesIn ?city . ?city :hasWeather ?weather } resolves ?person and ?weather only — not ?city.

Why. Tuple-at-a-time pull across gRPC would issue one RPC per row and destroy cache locality.

Problem. A Volcano iterator over a hexastore partition cannot batch prefix scans or TermId gather kernels.

How. Compute opens a demand-driven OpenNode tree and pulls next_batch (default SCAN_BATCH = 10_000 encoded rows) until a Slice is full. Joins use TermId columns (hash_join_columnar, shuffle_hash_join, left_hash_join_columnar). Eager nested joins use a separate JoinChunkSource path (not OpenNode) so one kernel call never holds a full cartesian or per-key row-multiplicity product. When the per-query memory budget is exceeded, Grace join / DISTINCT spill / external ORDER BY write the same column-major u32 page files.

No SPARQL rewrite — every multi-pattern query uses this engine.

Why. Stop producing solutions once the output budget is met.

Problem. Scanning and joining the full match set, then truncating, wastes work.

How. Outer PlanNode::Slice pulls batches, skips OFFSET rows, then accumulates LIMIT. With ORDER BY, Slice sits above PlanNode::Sort (sort-then-slice); LIMIT/OFFSET apply during in-RAM argsort or the external k-way merge. Without ORDER BY, OFFSET pages are not required to be stable across requests.

Lone scan. One storage RPC with limit = OFFSET + LIMIT visible Puts (MVCC-collapsed).

SPARQL.

Storage is asked for 13 matching Puts; compute drops the first 3.

LIMIT 0. Empty schema, no scan.

Why. Large scans must page without repeating rows or sending a huge single RPC.

Problem. Restarting a prefix scan from the beginning, or encoding a versioned RocksDB key as the client cursor.

How. start_after is an exclusive logical quad. Every commit_ts version of that quad is skipped. Used to refill OpenNode::Scan batches. Ignored when a broadcast filter_terms list is set (each allow-listed term is its own prefix scan).

Why. A small set of join keys should become extra bound slots on the right-hand hexastore scan, not a full partition walk plus a compute join.

Problem. ?person :livesIn ?city after five sunny cities would otherwise scan every livesIn triple.

How. Distinct join-key terms from the current left batch (≤ 24_576) become filter_slot + filter_terms. The partition binds each term and concatenates prefix scans. Object allow-lists re-route to O / OPSG even if the planned pattern still had that slot unbound (route_for). Nested pushes intersect (merge_broadcast_filters); an empty intersection is "no match", not "scan unfiltered".

Applies to inner Broadcast joins, OPTIONAL (when distinct keys fit the threshold), and VALUES-driven joins.

SPARQL.

After 2.2, the weather scan is left; execution broadcasts the city hashes into the livesIn scan. The complement is section 3.17: when a pushed list covers almost all of the probe’s key space, it is skipped instead of pushed.

Why. Join(Empty, R) and LeftJoin(Empty, R) cannot produce rows.

Problem. Scanning the right side after a failed required pattern.

How. If the left solution set is empty, skip the right tree and return an empty schema that still lists both sides' variables.

Why. Waratah partitions triples three ways (S / P / O). A bound object should hit the O node and the longest matching index prefix, not a cluster-wide scan.

Problem. Unbound ?s ?p ?o cannot be routed; a bound object on the S index would scan every subject.

How. select_target in waratah_router/src/route.rs:

Bound slots become the RocksDB key prefix; unbound slots are scanned inside that prefix.

SPARQL. ?s rdf:type http://ex/Person → O + TSG. ?city :hasWeather "Sunny" → O + OPSG.

Sketch-based axis choice is still a heuristic (router comment). Sketches already drive join order (2.2), not which of S/P/O owns a given bound term — that is determined by which slot is bound.

Why. Fingerprint equality is SIMD- and cache-friendly; OPTIONAL needs SPARQL left-join (Diff-once) semantics, including FILTER that cannot be decided on encoded terms.

How.

Why. Residual expressions need strings, but not for every column of every row at once.

How. Collect novel StrHash values for variables used by the residual expression, in windows of RESIDUAL_RESOLVE_WINDOW (65_536), merge into a query-local cache, then evaluate EBV on ground terms.

Why. Snapshot isolation without cluster-wide read locks.

How. Each hexastore key is encoded terms ‖ descending commit_ts with value op + visibility. A scan at snapshot T keeps the newest version with commit_ts ≤ T. Put is visible; Delete hides the quad. Visibility labels are stored but not enforced yet. Cluster timestamps currently come from the compute/dev path, not a Multi-Raft TSO.

Why. SPARQL FROM / FROM NAMED / protocol graph URIs and GRAPH patterns select a window of graphs without a G storage axis.

How. After parse + sparopt, compute builds a QueryDataset (protocol URIs override query-text FROM when any protocol URI is present; else FROM / FROM NAMED; else default_union). Bare BGP/path scans use the default window (RDF DefaultGraph, unbound G, a grounded IRI, or a G allow-list). GRAPH lowering is a graph scope on inner scans/paths, not a PlanNode::Graph and not a per-graph loop. Unbound GRAPH ?g (engine named set) leaves G unbound, sends a block-list {DefaultGraph} (graph_filter_allow = false), and projects ?g from result G slots. Enumerated FROM NAMED / VALUES ?g uses an allow-list (graph_filter_allow = true) or a grounded G (at most 10_000 terms). Point lookup requires S, P, O, and G bound. DESCRIBE scans honor the same default window. There is still no GSPO/GPSO axis; residual G tests sit on S/P/O prefixes.

Scan RPC graph_filter_allow defaults to false (block-list). Empty terms + block-list = block nothing (pattern.graph_name still applies). Empty terms + allow-list = allow nothing. Compute skip-RPCs empty allow-lists. Pushed or folded ?g values intersect the existing scan/path constraint (dataset window, {DefaultGraph} block-list, or a prior allow-list); a singleton is grounded only if it is still legal, and a disjoint intersection is an empty allow-list, not a cleared filter.

Merged SPARQL default graph (merge_default_graph). Several FROM IRIs or default_union is an RDF merge, not a bag of quads. At plan time GraphScope::Default plus AllGraphs / Allow sets ScanOp/PathOp.merge_default_graph. The scan RPC asks every hexastore axis (G is last in SPOG/SOPG/PSOG/POSG/OPSG/TSG) to emit each distinct S/P/O once, skip the whole start_after triple (any G), and rewrite result G to DefaultGraph before the response. Compute never projects G for those scans, so the rewrite is not user-visible. GRAPH leaves the flag off so graph identity stays on the wire. Path hops in merge-default mode therefore join on nodes (every hop G is DefaultGraph) and can traverse a :p b in g1 then b :p c in g2. Do not use a rewritten DefaultGraph quad as a full-key exclusive cursor: DefaultGraph encodes as zero bytes (lowest G) and would re-enter the same triple; storage compares S/P/O via same_triple instead. OFFSET+LIMIT on a lone merge-default scan counts distinct triples.

Why. Cardinality without sending rows across the wire — HTTP quad_count, and the common SPARQL shape SELECT (COUNT(*) AS ?c) WHERE { …one BGP… } (also bag COUNT(?v)).

How. The storage CountPattern RPC uses the same prefix / broadcast-filter / graph-window rules as scan, counting visible Puts, and returns one integer. Plan-time eliminate_pattern_count_groups (after head/domain eliminate) replaces an ungrouped Group whose body is a single unbound-GRAPH Scan and whose only aggregate is bag COUNT(*) or bag COUNT(?v) (variable on a scan slot) with PlanNode::PatternCount in waratah_compute/src/plan.rs. Execution calls count_pattern once; no solution mappings cross the wire. GROUP BY, COUNT(DISTINCT …), multi-aggregate Groups, joins, VALUES⋈scan, unbound GRAPH ?g, and broadcast-marked scans refuse and stay on HeadCounts / DomainCounts / the generic Group. Other aggregates (SUM, AVG, …) still fold in compute over scanned solutions (waratah_compute/src/aggregate.rs).

Why. The plan-time marks (2.9) and rewrite (2.10) only pay off if the leaf executor honors them: dead columns must never enter a TermId page, collapse must survive page boundaries, and domain scans must page to EOF.

How. execute_node and every join probe fetch whole scan-leaf results through fetch_whole_scan_solutions (waratah_compute/src/query.rs), which always drains to EOF:

SPARQL. SELECT DISTINCT ?class WHERE { ?inst a ?class } returns one row per distinct class; the intermediate never contains per-subject rows.

Why. The liveness/rewrite decisions are invisible in a plan dump unless printed.

How. estimate EXPLAIN lines print per scan: ~N inside (triple …), (domain ?v N | ?) per live unbound S/O end, (dead ?v), (bag_insensitive ?v), and (domain_scan), when the rewrite fired (don’t emit bag_sensitive, that is the implied default). Group/aggregate lines still print their own estimates, so a collapse that changed the leaf estimate is visible as the difference between the scan line and its parent.

Why. OPTIONALs keyed on the same required core are order-insensitive semantically but not operationally: putting the low-multiplicity optional first keeps the intermediate between the left joins small (measured −11% end-to-end on the class-hierarchy shape: ~27.6k intermediate rows and ~49k probes instead of ~398k / ~419k for the same 479k-row output). Symmetrically, a required pattern written AFTER an OPTIONAL joins the OPTIONAL’s inflated output; letting the required side finish first both shrinks that join and re-unites the required patterns for the arm swap / Broadcast grounding / ancestor costing the lowering-time fold could not give them (a LeftJoin is an association barrier there).

How. reorder_independent_optional_arms (waratah_compute/src/plan.rs, called from the refinalize_joins LeftJoin arm after children settle) flattens the LeftJoin spine LeftJoin(…​(core, A1), …, Ak) into core + arms (query order), finds the maximal TOP run of pairwise-independent arms (optional_pair_rotation_safe per ordered pair: both arms' join keys bound by the required core L alone, and the later arm’s scope — its traveling filters plus every variable mentioned in its subtree, collect_subtree_variables — contains nothing first-PRODUCED by the earlier arm, always- or maybe-bound — a maybe-bound output (e.g. from a nested OPTIONAL inside the earlier arm) read by the later arm’s FILTER evaluates differently across the swap, so it counts as a dependency; the earlier arm was lowered with the later one out of scope, so one direction suffices), and rebuilds that run in greedy stage order: repeatedly attach the arm whose estimate_left_join_rows stage (unmatched pass-through + uniform matched product) is smallest. Commits only when the greedy order differs from query order and its summed stages beat the query order’s by at least LEFTJOIN_REORDER_MARGIN_PERCENT (15%) — one margin on the whole reorder, a strict-improvement ratchet so the second refinalize round never flips it back (the old adjacent-pair rotation needed every single swap to clear the margin alone, which blocked multi-step improvements). Arms below the run stay in query order: a dependent pair is frozen in relative order, and only the arms above it — which never read what it first-produces — are free to move. Every arm torn down gets clear_broadcast_marks (claim-skip keeps stale marks, so only a cleaned scan lets the boundary restamp_broadcast_marks re-claim); the sub-chain below the run is untouched, marks and stamped metas included. For two arms this degenerates to exactly the old rotation’s decision on the same numbers.

delay_optional_through_join (same file, called from the refinalize_joins Join arm after the arm swap settles) rewrites Join(LeftJoin(L, O), R) → LeftJoin(Join(L, R), O) in either orientation. Gates, from section 2.11’s condition set: the outer join must have hash keys (vars(X) ∩ vars(B) ≠ ∅ — a cartesian R would become a cartesian on the OPTIONAL’s required side, where its rows also form the pass-through floor), the OPTIONAL’s keys are bound by L alone, and every variable crossing between the OPTIONAL’s scope (its subtree plus traveling filters) and R’s subtree is always-bound in L (vars(X) ∩ vars© ⊆ vars(B)) — the condition that makes the rewrite change only the ORDER rows merge in, never WHICH rows meet (the join key sets are identical on both sides of the rewrite). A set-wise output-vars check guards the boundary schema at runtime. The same LEFTJOIN_REORDER_MARGIN_PERCENT gates the summed-stage comparison (OPTIONAL stage + join against its output vs re-united required join + OPTIONAL probing it). The candidate Join(L, R) is built through join_nodes (from marks-cleared clones — the dissolved outer join may have claimed scans under L or R, and the boundary restamp is claim-skip, so re-derivation requires a cleaned scan; O is cleared the same way at commit) so it gets the constructor’s swap, grounding, and graph composition. Deeper nestings (Join(Join(LeftJoin(L,O),R1),R2)) bubble within one round via post-order.

Where. Dependent optionals keep query order: joining on the first optional’s variable, or a FILTER in the second optional referencing it, blocks the reorder. The delay blocks on the mirror conditions: R reading a variable the OPTIONAL first-binds (or its FILTER reading an R-bound variable), the OPTIONAL keyed outside the required side, no shared hash key, or no improvement within the margin.

Where. QueryCaches::scan_solutions / ScanMemoKey (waratah_compute/src/query/caches.rs, publish/admit API in query/scan/memo.rs); the fetch service in waratah_compute/src/query/scan/fetch.rs (fetch_whole — every whole read — and scan_pushed_stream_batch's completed-single-batch funnel publish); arm-boundary inheritance in eval_eager.rs (QueryCaches::arm_workspace / merge_arm_cache).

Why. The eager driver pipeline re-executes nested subtrees once per driver chunk. Without the memo, every chunk re-drains the same small relations (type scans, dictionary-ish arms) at full RPC cost; with it, the first drain amortizes across all remaining chunks.

What. A query-lifetime cache mapping a plain scan leaf’s full identity to its whole result: a scan whose result is cached is never fetched again during the query — an outer join’s page loop re-executing the same leaf is served from memory.

Key. ScanMemoKey = the encoded S/P/O/G pattern (the graph slot is part of the key — default-graph, GRAPH <g>, and different named graphs never collide) + default-graph merge mode + the live output schema (materialized_variables) + the repeat-slot pairs + MVCC snapshot. The schema and repeat components exist because a solutions entry bakes the publisher’s columns and from_scan's repeated-variable row filter in: the old quad memo renamed implicitly at consumer-side conversion, a solutions table cannot — ?dog :p ?city and ?cat :p ?city are different leaves, and so are ?a :p ?a and ?a :p ?dead. Runtime broadcast grounding (3.19) pins chunk terms into the pattern, so a grounded fetch keys on the effective pattern (ScanMemoKey::of_pattern) — distinct chunk terms occupy distinct entries.

Admission. Two gates, deliberately in one place per fetch path:

Budgets and visibility. Per-entry limit SCAN_MEMO_MAX_ENTRY_ROWS (24,576 rows, solution rows ≤ quad rows); query-wide total SCAN_MEMO_MAX_TOTAL_ROWS (245,760 rows; QueryCaches::memo_refused records refusals). Budgets are advisory inputs to the coverage policy (3.18), never correctness inputs. Memo deliveries log as scan-rpc[stream-batch-memo] (funnel hook) and scan-memo[solutions] (whole reads) and are deliberately not counted in the phases scans= RPC counter.

Arm boundaries. Parallel arms evaluate on a per-arm cache that inherits the query’s scan-memo state at creation (QueryCaches::arm_workspace — refusals and memo tables, the latter Arc-shared so inheritance is pointer clones) and merges refusals and memo tables back at arm end (merge_arm_cache). Without the inheritance, a refusal (or memoized table) found by one chunk’s arm would die with that arm’s workspace and the next chunk would re-learn it the expensive way.

Where. push_list_covers_domain, PushedKeys::combine (query/pushdown.rs), join_keys_scan_filter (query/scan_filters.rs).

What. When a driver chunk’s distinct join-key list covers ≥ 9/10 of the probe’s key space for that key, the list selects almost nothing — so the push is skipped and the join on that key applies the predicate downstream. This is the complement of section 3.5: the allow-list is pushed when it selects; it is skipped when it selects nothing.

Why. Pushing a covered list costs wire bytes plus a storage-side seek-union while filtering out at most ~1/c of the rows — and (3.18) the filtered fetch can never memoize, so keeping it defeats the scan memo on every chunk. Coverage is measured against the probe’s domain (probe_key_domains), never the driver’s: driver-side coverage is page saturation, not selectivity.

Invariants. A dropped push is a removed semi-join filter: the probe produces a superset and the hash join restores the semantics, so no drop decision can change results. Never applied to dependent-path arms (enforce_push_threshold = false — the list is a walk seed) or EXISTS-picker stacks (correlation batches are not relation filters). A one-term list is a point lookup, never covered — that case is runtime broadcast grounding (3.19).

Terms. A push is the driver chunk’s distinct join-key values sent to storage as an allow-list ("only rows whose key is one of these"). A dropped push (push coverage drop, 3.17) means not sending it: the probe is fetched unbound and the hash join applies the equality downstream — same rows, different plan. A dropped push amortizes when the full unbound fetch is paid once and reused: the eager pipeline re-executes the probe once per driver chunk, so the drop only wins if chunk 1’s unbound result is cached (scan memo, 3.16) and chunks 2..N are cache hits — the one-time cost is spread across N uses. If the memo cannot store the arm (over the entry limit), the drop buys nothing: N unbound fetches replace N nearly-full filtered fetches.

What. The guard deciding whether a covered push may actually drop, so dropping only happens when the unbound fetch amortizes:

Runtime correction. The plan-time verdicts read advisory estimates. The first unbound fetch reports the truth: if the memo refuses the arm (budgets are query-wide and dynamic), the key is recorded in QueryCaches::memo_refused and the join re-pushes from the next batch — an estimate miss costs exactly one full-arm fetch. Each join level applies the correction to its own right arm, so a subtree’s refusals are absorbed at the leaf’s own join. Parallel arms evaluate on a per-arm cache that inherits the query’s scan-memo state at creation and merges refusals and memo pages back at arm end (3.16) — without the inheritance, a refusal found by one chunk’s arm would die with that arm’s workspace and the next chunk would re-drain unbound.

Guards (revert-proofed). coverage_drop_reverts_after_memo_refusal (estimate too small), subtree_right_join_drops_covered_chunk_keys (subtree right, fetch-counted), and memo_refusal_repushes_optional_arm_under_chunked_join (OPTIONAL inside a re-executed union branch — also fails if the arm workspace stops inheriting/merging the refusal set) pin the guard; all fail on the pre-guard code.

OpenNode/Slice exception. The OpenNode/Slice path drop policy is deliberate, not an oversight: it denies case 2 (driver_rows = None), keeps subtree pushes, and never reads memo_refused. A dropped push there materializes the unbound right side once into the join’s built table and reuses it for every batch — a re-push after a refusal could not undo that fetch — so what keeping a push buys is per-batch selectivity for LIMIT early exit, and the path preserves that by declining to estimate-gate it.

Where. ground_single_term_broadcast (query/scan_filters.rs), ScanOp::with_pattern (plan.rs), ScanMemoKey::of_pattern (query/caches.rs); wiring inside the fetch service’s whole-read entry (fetch_whole — every merged-broadcast scan arm routes through it) and the driver fetch paths (fetch_whole, scan_pushed_stream_batch, driver_scan_needs_stream — the transport decision runs on the grounded shape so the latch and the fetch agree).

What. A one-term pushed broadcast never crosses the wire as a filter. ground_single_term_broadcast pins the term into the effective pattern’s slot (ScanOp::with_pattern clones the scan with the rewritten pattern) and the fetch goes out unfiltered — a prefix seek on the pinned term. This is the execution-time counterpart of section 2.5’s plan-time grounding: 2.5 grounds plan-time constants (ground BIND, singleton VALUES); 3.19 grounds runtime one-term broadcasts.

Why. A one-term list is a point lookup, never coverage-dropped, so without grounding it crosses the wire as a filter on every chunk and can never memoize (the memo key carries no filter slots). Grounded, the pinned term rides in the memo key (ScanMemoKey::of_pattern): a subtree re-executed under the same chunk term is served from cache, and different terms never share an entry.

Fences (anything else keeps the wire filter):

Where. stamp_build_once in waratah_compute/src/plan.rs; consumption in the eager join driver (query.rs / eval_eager.rs).

Why. The eager driver pipeline re-executes a subtree probe arm once per driver chunk (section 3.16’s scan memo covers plain scan leaves; a join subtree above the leaves has no memo entry). A Build-once stamp lets the executor materialize such an arm once and reuse it for every chunk — but a stale Build stamp under a keyed driver would repeat the arm’s whole read on every execution, so the verdict must be priced under the push geometry.

What. The stamp walk crosses a keyed join whose probe arm is a subtree on the per-page keyed road carrying a containing push context (ContainingPush in plan.rs: the runtime’s own broadcast key, recovered from the gather’s reorder order, plus the ancestor’s per-page matched bound) into the subtree. A contained join whose DRIVER hosts the pushed key prices its build-once verdict at min(standalone, matched_per_page) driver rows — the push-conditioned geometry: the subtree runs once per driver page, so the standalone multi-page stream never happens. The context crosses exactly the containers probe_scan_has_key walks (the modeled push-reachability topology) and stops at its boundaries (SubSelect, LeftJoin arms, plugin children); the once-roads (all-dropped coverage, empty driver) establish no context — the subtree executes once there and contained joins price standalone. The outermost keyed subtree probe wins (one context, no stack). The seat comparator’s own gather stays un-conditioned (a deferred leaf-walk; see scratch/open_todo.md item 7).