query: index-walk range semi-join for correlated range probes, plus four join-chain fixes (BSBM Explore Q5) - #1815

fluree-db-query/src/range_semijoin.rs:625 — 🔴 blocking. The POST walk silently drops every xsd:decimal (and out-of-i64 integer) value, so the fold returns fewer rows than the chain it replaces.

Both walk passes gate on OType::is_numeric() — here for a homogeneous leaflet and again at :745 for the row-by-row mixed path — and that predicate is documented as "integer or float, inline only" (o_type.rs:329–333). NUM_BIG_OVERFLOW (0x800B) is outside both ranges, and the indexer routes every typed xsd:decimal to that arena (o_type.rs:93–96, "no stored row carries this o_type"), along with BigInt. So a leaflet or row holding a decimal is continued before it can reach the decode-and-compare path that key_bounds explicitly leaves for it ("None: the kind is not range-keyed (arena decimals), so rows are compared by decoded value instead"). The probe path does handle them — WalkValue::from_binding yields Other(binding) and value_passes re-evaluates the original filter — so the walk and the probe lane disagree with each other and with the generic pipeline.

Claude caught this with a differential probe against set_fast_paths_disabled(true): adding one product ex:DEC with ex:n1 "150.5"^^xsd:decimal (inside the ±120 window) to the PR's fixture, the Q5 shape returns 35 rows generically and 34 under the fold — ["ex:DEC","dec_in"] missing — with every batch stamped proceed. Same loss under a double-valued anchor and under SELECT ?product (COUNT(DISTINCT ?label) AS ?c) … GROUP BY ?product. Financial data is exactly where correlated range windows show up, and it is exactly where values are typed decimal.

Fix: admit the arena in both gates so those leaflets take the mixed path (key_bounds already returns None for NumBigArena, decode_set = mixed already carries OType/PId, and the mixed loop already does decode_value_v3 → bounds.matches → WalkValue::Other(materialized_object_binding(...))):

let walkable = |ot: OType| ot.is_numeric() || ot == OType::NUM_BIG_OVERFLOW;
// :625  if !walkable(o_type) { continue; }
// :745  if !walkable(OType::from_u16(ot)) { continue; }

And please add a decimal-valued product (in-window and out-of-window) to it_range_semijoin.rs's products() — the fixture's only non-integer value is the string "abc", which is why this passed.

Addressed in e400a8c

Both gates now admit NUM_BIG_OVERFLOW. Added in/out-of-window decimal and large-integer coverage. Also widened integer walk keys outward for decimal bounds beyond f64 integer precision, with a regression test.

fluree-db-query/src/execute/where_plan.rs:3362 — 🔴 blocking. A constant FILTER on the folded value variable is dropped whenever the pushdown consumed it, so the fold returns rows the filter should have removed.

extract_bounds_from_filters (pushdown.rs:18–47) turns FILTER(?s1 > 150) into pushdown.object_bounds[?s1] and records the filter in consumed_indices; it does this independently of the correlated filter on the same variable. collect_range_semijoin_folds then counts readers of ?v excluding consumed filters, so the correlated range is the sole reader, the probe folds, and the two places the constant bound could still be applied are both bypassed: the folded triple never reaches build_scan_or_join(…, &pushdown.object_bounds, …) (:1628), and apply_deferred_patterns skips consumed filters by design. The RangeSemiJoinCondition carries only the correlated bounds.

Claude caught this: the PR's Q5 shape plus FILTER (?s1 > 150) returns 9 rows generically and 34 under the fold (25 extra — ex:A at 150, ex:G at 120, ex:K at 110/130, ex:N19, the double anchor, nineteen bulk products), on the walked path and on the probe path (pure-novelty view) alike, because the loss is at plan time.

Fix — the minimal one is to refuse the fold when the pushdown already owns bounds on ?v; the fuller one intersects those bounds into the condition (lower/upper as constant expressions with the pushdown's strictness) so the shape still folds:

// in collect_range_semijoin_folds, alongside the read_elsewhere check
if pushdown_bounds.contains_key(v) {
    continue;
}

(pushdown_consumed is already threaded in; passing &pushdown.object_bounds next to it is a one-line signature change.) And a FILTER (?s1 > 150) variant belongs in the fixture — it is the most natural way a user tightens a Q5-shaped query.

Addressed in e400a8c

Applied the minimal guard: a pushed-down constant bound keeps its enforcing join. Added >, >=, <, <=, and = variants on indexed and novelty views; reproduced the extra-row failure on the pre-fix commit.

fluree-db-query/src/range_semijoin.rs:885 — 🔴 CRITICAL (performance). Wherever the batched probe lane declines, the fold re-plans and re-opens an operator tree per driving row, and measures 4.2× slower than the chain it replaced.

probe_batch computes subject_probe_lane_plan and, on Decline (:803, :807), leaves probed = None; every kept row then takes the _ => arm at :870–872 into row_passes_exactly, which calls build_where_operators_seeded (full block collection, reorder, pushdown extraction, operator construction) and open per row. The index path does the same for unbound subjects at :1137. The lane declines for: no binary store at all (an un-indexed or novelty-only ledger — and the planner deliberately folds there, since the ≥256 driving-row gate needs stats), a non-root policy (fast_path_common.rs:2601 declines before anything else), multi-ledger, and eager_materialization (reasoning, federated). None of those are knowable at plan time, so the fold happens and the fallback pays per row. The nested loop degrades to a per-row scan in the same contexts, not a per-row plan.

Claude measured it with the fold alone toggled (all other fast paths on): the PR's fixture Q5 shape on the pure-novelty view, 5 runs each, twice: generic 177 ms / 180 ms, fold 757 ms / 761 ms; the range semijoin exhausted event reads probed=1521 fallback=1772 walked=0 probe_batches=6. Indexed, the same shape is 2.1× faster (19–20 ms vs 42 ms), so the operator is doing its job where the lane serves — the regression is confined to the declined contexts, but "restricting policy" is every non-root Solo user, and the body's "so the lane never costs more than the chain it replaced" does not hold there.

Fix: make the declined fallback batch-level rather than row-level — seed one chain per batch (SeedOperator::from_batch(&batch) over the probe + filter, projecting the subject), drain it once, and mark kept subjects — which is the generic, overlay- and policy-correct pipeline planned once per batch. Independently, refusing the fold when ctx.stats.is_none() would remove the un-indexed case outright (no stats ⇒ no index ⇒ no walk possible anyway), though that changes the "pure novelty" assertion in the test.

Addressed in e400a8c

The generic probe/filter is now planned once per fallback batch. A private row ID preserves separate bounds for repeated subjects and handles initially unbound subjects. In contexts where the fast probe lane cannot serve, the existing Distinct removes duplicate driving rows under the fold’s multiplicity-insensitive license.

Local 1,500-product correlated-Q5 fixtures improved from 29.1–32.6 ms to 6.72–7.56 ms on novelty and from 46.3–46.6 ms to 16.3–18.9 ms with non-root policy. Tests cover differing bounds, unbound/poisoned/missing subjects, and subject-denying policy. The PR body includes methodology and the generic-pipeline diagnostic.

fluree-db-query/src/range_semijoin.rs:602 — 🟡 question. This is more of a question than a suggestion: does the walk actually fire on Q5 at 10M/100M? The cap is max(4k, 16 × cumulative driving rows), so on the first batch it is 16× one batch, and BSBM's ±120 window over productPropertyNumeric1 (uniform 1..2000) covers ~12% of all products — ~1.2M rows at 10M, ~12M at 100M. Unless the first batch carries ≥75k rows, the first walk caps, walk_off latches, and the whole query runs on probe_batch. If that is what happened in the 100M runs, the measured gain is the probe lane's (which is still real: deduped subject probes, no row materialization, no re-dedup) and the ~600 lines of walk are exercised only at the fixture's scale. The range semijoin index built by POST walk debug event would settle it; if the walk doesn't fire at scale we may want the cap to lean on the planner's driving estimate (known at fold time) rather than rows seen so far.

Added actual runtime routing checks to the correlated benchmark in e400a8c. At 10k generated products both conditions walk (four condition-batches); at 100k one walks and one probes (13 each), before and after these fixes.

Your cap concern is valid. I have not rerun the production 10M/100M datasets and cannot attribute those historical gains to POST walks. I left the cap conservative, and updated the PR body to distinguish the historical results from the new local routing and timing evidence. Using the planner estimate to authorize larger walks should be a separate measured change.

fluree-db-query/src/range_semijoin.rs:1073 — 🟡 question. I don't think this bites Q5 (one anchor ⇒ one envelope ⇒ one walk), but a batch whose envelope isn't covered rebuilds the index from scratch over index.envelope ∪ batch_envelope, with a cap that grows as 16 × cumulative rows. A driving stream whose bounds drift monotonically (a variable anchor whose value arrives in scan order) would re-walk the cumulative envelope every batch — roughly Σ k·w over batches, quadratic in batch count — and charge fuel for each rebuild. I tried to provoke it with a 1,200-product self-join and got a single walk because the hash join scrambled the order, so this is unverified. Walking only the delta (the part of the new envelope the old one doesn't cover) or latching walk_off after a handful of rebuilds would be cheap insurance if you agree it's a real shape.

Addressed in e400a8c

Each condition now allows at most four walk attempts, then latches over to probes. A deterministic ten-batch expanding-envelope test verifies four successful walks and exact results from the later probe batches.

fluree-db-query/src/execute/where_plan.rs:1643 — ⚪ nit / question. Folded triples never reach hash_planner.before_step, and RangeSemiJoinOperator::estimated_rows returns the child's estimate, so the label probe behind the fold is costed against the pre-semi-join stream. Not wrong, and I don't think it changes Q5's plan, but the fold exists to exploit a selectivity the planner then can't see; folding step_est × (range width / value range) in would be cheap if stats have what's needed.

I would defer this one. Keeping the child estimate is conservative and does not affect correctness; deriving useful correlated-range selectivity needs more than assuming a uniform value distribution. These fixes leave that estimate unchanged, and the PR body calls out the limitation.

fluree-db-api/tests/it_range_semijoin.rs:396 — ⚪ nit. The test sets FLUREE_RANGE_SEMIJOIN_WALK_FLOOR at the top and notes it is the only test in the binary, because walk_row_floor() is a process-wide OnceLock. That is fine today; a one-line comment at the [[test]] entry in Cargo.toml saying "keep this binary single-test" would stop the next contributor from adding a second test and getting a flaky floor.

Addressed in e400a8c

fluree-db-query/src/distinct.rs:180 — praise. The Cow scratch key is exactly right: cleared per row, hashed as the stored Vec<Binding> hashes (Cow<B> hashes as B; both Vecs length-prefix), compared element-wise, and only materialized for a vacant entry. A duplicate costs a hash and a probe and nothing else. Verified by reading against hashbrown's rehash path.

fluree-db-query/src/eval/helpers.rs:196 — praise. Trying fast_eq_ne_for_iri_bindings before the LRU is a pure reorder: it is the same function the uncached path already calls first (compare.rs:384), and the LRU only ever cached that path's answer, so =/!= against unbound, literal-vs-IRI and blank nodes are unchanged.

fluree-db-query/src/execute/where_plan.rs:3298 — praise. The liveness analysis behind the fold is careful and I could not break the license: COUNT(*) and bag projections refuse it; a projected, ordered, OPTIONAL-read, twice-filtered, re-joined or COUNT(DISTINCT ?s1)-read value keeps that probe a real join while the still-dead sibling folds; UNION and MINUS bodies come out identical to the generic pipeline. Double-vs-integer bounds at strict boundaries, an infinite upper bound and one-sided correlated ranges all matched too.