Skip to main content

rete_core/
bgp.rs

1//! Basic Graph Pattern (BGP) evaluation — the core of SPARQL (SPEC.md §8,
2//! stage 1). A BGP is a set of triple patterns whose variables join on equality;
3//! evaluating it yields variable bindings.
4//!
5//! Evaluation is a left-deep **hash join**: each pattern is scanned from the
6//! index *once* (binding only its own constant terms), producing a relation of
7//! candidate rows; that relation is then joined against the running solution set
8//! on the variables they share. This is O(scan + matches) per pattern rather
9//! than the O(bindings × scan) of a per-binding nested-loop probe — the
10//! difference between sub-second and minutes once a pattern binds tens of
11//! thousands of rows. Correctness does not depend on pattern order.
12//!
13//! Solutions are slot `Row`s of tagged dictionary ids (see `crate::row`):
14//! joins hash and compare integers, and terms are resolved to strings only at
15//! the engine's projection boundary, never per intermediate row.
16
17use std::collections::{BTreeMap, HashMap};
18
19use crate::file::Rete;
20use crate::index::{GraphIndex, Pattern, ProbeBatch};
21use crate::row::{Ctx, Row, Slots, Val};
22use crate::triples::Triple;
23
24/// A term in a pattern: a named variable or a constant term token.
25#[derive(Debug, Clone, PartialEq, Eq)]
26pub enum PatternTerm {
27    Var(String),
28    Const(String),
29}
30
31impl PatternTerm {
32    /// `?x` → variable `x`; anything else → a constant.
33    pub fn parse(token: &str) -> Self {
34        if let Some(name) = token.strip_prefix('?') {
35            PatternTerm::Var(name.to_string())
36        } else {
37            PatternTerm::Const(token.to_string())
38        }
39    }
40}
41
42/// A triple pattern `(subject, predicate, object)` of [`PatternTerm`]s.
43#[derive(Debug, Clone)]
44pub struct TriplePattern {
45    pub s: PatternTerm,
46    pub p: PatternTerm,
47    pub o: PatternTerm,
48}
49
50/// A solution: variable name → bound term (the public, resolved form).
51pub type Binding = BTreeMap<String, String>;
52
53// --- integer join core ------------------------------------------------------
54//
55// Variables bind to a tagged i64: a node ID `n` is stored as `n` (>= 0), a
56// predicate ID `p` as `-(p+1)` (< 0). Nodes are the unified subject/object space
57// so a variable joins consistently across subject and object positions. A
58// predicate value whose term is also a node is canonicalized to the node id
59// (`Resolver::canon_id`), so cross-role joins match exactly when the term
60// strings match.
61
62/// A pattern position lowered to slot/integer space.
63#[derive(Clone, Copy)]
64enum SlotTerm {
65    Var(usize),
66    Node(u32),
67    Pred(u32),
68}
69
70fn pred_tag(p: u32) -> i64 {
71    -(p as i64) - 1
72}
73
74/// Register every variable in `patterns` with the slot map.
75pub(crate) fn collect_pattern_slots(patterns: &[TriplePattern], slots: &mut Slots) {
76    for p in patterns {
77        for t in [&p.s, &p.p, &p.o] {
78            if let PatternTerm::Var(v) = t {
79                slots.add(v);
80            }
81        }
82    }
83}
84
85/// Lower patterns to slot/integer space; `None` if a constant term is unknown
86/// (making the whole BGP unsatisfiable) or a variable has no slot.
87fn lower(patterns: &[TriplePattern], ctx: &Ctx) -> Option<Vec<(SlotTerm, SlotTerm, SlotTerm)>> {
88    let dict = ctx.rete.dictionary();
89    let node = |t: &PatternTerm| -> Option<SlotTerm> {
90        match t {
91            PatternTerm::Var(v) => ctx.slots.slot(v).map(SlotTerm::Var),
92            PatternTerm::Const(c) => dict.node_of_term(c).map(SlotTerm::Node),
93        }
94    };
95    let pred = |t: &PatternTerm| -> Option<SlotTerm> {
96        match t {
97            PatternTerm::Var(v) => ctx.slots.slot(v).map(SlotTerm::Var),
98            PatternTerm::Const(c) => dict.predicate_id(c).map(SlotTerm::Pred),
99        }
100    };
101    let mut lowered = Vec::with_capacity(patterns.len());
102    for p in patterns {
103        lowered.push((node(&p.s)?, pred(&p.p)?, node(&p.o)?));
104    }
105    Some(lowered)
106}
107
108/// Evaluate a BGP against the file's default graph, returning all solutions
109/// resolved to terms (the public convenience API).
110pub fn eval_bgp(rete: &Rete, patterns: &[TriplePattern]) -> Vec<Binding> {
111    let mut slots = Slots::new();
112    collect_pattern_slots(patterns, &mut slots);
113    let ctx = Ctx::new(rete, slots);
114    eval_bgp_rows(&ctx, rete.default_index(), patterns)
115        .into_iter()
116        .map(|row| row_to_binding(&ctx, &row))
117        .collect()
118}
119
120/// Resolve a row to a named-term binding (every bound slot). Uses the uncached
121/// decode — this is the output boundary, where terms are typically seen once.
122pub(crate) fn row_to_binding(ctx: &Ctx, row: &Row) -> Binding {
123    let mut b = Binding::new();
124    for (i, v) in row.iter().enumerate() {
125        if let Some(val) = v {
126            if let Some(t) = ctx.resolver.str_once(val) {
127                b.insert(ctx.slots.name(i).to_string(), t);
128            }
129        }
130    }
131    b
132}
133
134/// The join order of `lowered` and what a full scan of each pattern would
135/// produce (its own constants only, from the tile directory): the probe-vs-scan
136/// decisions compare the latter with the running result.
137///
138/// A single pattern has one order and nothing to compare its scan with, so it
139/// is not estimated at all. Estimating reads the tile-directory leaves of every
140/// permutation that leads with a bound id, one after another: on the 62 GB
141/// OpenCitations file `<br> ?p ?o` read two 520 KB leaves, the second of them
142/// for a permutation the scan never used, plus a dictionary chunk for
143/// `rdf:type`, each a dependent round trip.
144fn plan_order(
145    ctx: &Ctx,
146    index: &GraphIndex,
147    lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
148) -> (Vec<usize>, Vec<f64>) {
149    if lowered.len() == 1 {
150        return (vec![0], vec![0.0]);
151    }
152    let order = selectivity_order(ctx, index, lowered);
153    let scan_est = tile_estimates(ctx, index, lowered, &std::collections::HashSet::new());
154    (order, scan_est)
155}
156
157/// Evaluate a BGP to slot rows against a specific graph `index` (joins run on
158/// integer ids; the shared dictionary comes from `ctx`).
159pub(crate) fn eval_bgp_rows(ctx: &Ctx, index: &GraphIndex, patterns: &[TriplePattern]) -> Vec<Row> {
160    // An empty BGP has exactly one (empty) solution.
161    if patterns.is_empty() {
162        return vec![ctx.slots.empty_row()];
163    }
164    // Lower all patterns; a missing constant term makes the BGP empty.
165    let Some(lowered) = lower(patterns, ctx) else {
166        return Vec::new();
167    };
168
169    // Join the patterns most-constrained-first (and keeping the join connected),
170    // so intermediate relations stay small. Pure reordering: the hash join is
171    // order-independent, so the result is unchanged.
172    let (order, scan_est) = plan_order(ctx, index, &lowered);
173    let mut rows: Vec<Row> = vec![ctx.slots.empty_row()];
174    let mut bound: Vec<usize> = Vec::new();
175    let mut merged: [bool; 2] = [false, false];
176
177    // Merge-join seed: if the two cheapest patterns share a same-role variable the
178    // 6-permutation index can co-sort them on, join them with a linear two-pointer
179    // **merge** (no hash table) and skip both below. Falls back silently to the
180    // hash/probe path when the shape doesn't qualify.
181    if order.len() >= 2 {
182        if let Some((rel, slots)) =
183            try_merge_join(ctx, index, &lowered[order[0]], &lowered[order[1]])
184        {
185            rows = rel;
186            bound = slots;
187            merged = [true, true];
188        }
189    }
190
191    for (k, &idx) in order.iter().enumerate() {
192        if k < 2 && merged[k] {
193            continue; // already consumed by the merge seed
194        }
195        let t = lowered[idx];
196        // Hybrid join: once the running result is small and the next pattern shares
197        // an already-bound variable, **probe** it per row through the index instead
198        // of scanning its whole extent and hash-joining. A left-deep hash join
199        // otherwise materializes every pattern's full scan even when only a handful
200        // of rows survive — e.g. a `?x rdf:type C` over thousands of instances when
201        // the prefix already pinned ?x to 26 rows. Probing turns that O(scan) into
202        // O(rows × lookup). The full scan + hash join stays the path when the prefix
203        // is large (one scan beats many probes) or the pattern is a cartesian join
204        // (no shared bound variable to constrain the probe).
205        let shares_bound = pattern_slots(&t).iter().any(|s| bound.contains(s));
206        // Decide probe (per-row index lookup) vs scan + hash join. In memory a
207        // probe is a cheap lookup, so we probe up to a moderate prefix. Remotely
208        // each probe is a byte-range round-trip: probing a 500-row prefix is 500
209        // sequential fetches, while scanning a selectively-bound pattern is a few
210        // coalesced reads — so remotely we only probe a broad (whole-predicate)
211        // pattern, or a tiny prefix, and never a large one.
212        //
213        // Whatever the reader, probe when the scan would be far larger than
214        // the rows asking about it: 517 `?s a :Service` rows must not scan
215        // and materialize all 109 M `publicationYear` triples to keep 517.
216        let do_probe = !bound.is_empty()
217            && shares_bound
218            && !rows.is_empty()
219            && (probe_beats_scan(rows.len(), scan_est[idx])
220                || if index.is_remote() {
221                    rows.len() <= remote_probe_max(index)
222                        && (rows.len() <= REMOTE_PROBE_MIN || !pattern_is_selective(&t))
223                } else {
224                    rows.len() <= BGP_PROBE_THRESHOLD
225                });
226        if do_probe {
227            let taken = std::mem::take(&mut rows);
228            // Over a lazy reader each probe is a byte-range round trip, and they run
229            // one at a time. Fault the tiles each window of the batch will route to,
230            // together — one coalesced parallel read per section instead of N
231            // sequential ones — so the probes hit a warm tile cache. A window, not
232            // the whole batch: see [`Windowed`]. Passes the rows straight through
233            // for a local index (every tile is already resident).
234            let mut next: Vec<Row> = Vec::with_capacity(taken.len());
235            for base in windowed(index, taken.into_iter(), bgp_probe_pattern(ctx, t)) {
236                next.extend(probe_rows(ctx, index, t, base));
237            }
238            rows = next;
239        } else {
240            let Some((rel, rel_slots)) = pattern_rows(ctx, index, &t) else {
241                return Vec::new();
242            };
243            rows = hash_join(rows, &bound, rel, &rel_slots);
244        }
245        for s in pattern_slots(&t) {
246            if !bound.contains(&s) {
247                bound.push(s);
248            }
249        }
250        if rows.is_empty() {
251            break;
252        }
253    }
254    rows
255}
256
257/// Merge-join two base patterns that share **exactly one** variable sitting in the
258/// **same canonical position** (both subject, or both object) in each. That is the
259/// only shape rete's role-aware id spaces let a sort-merge align: the index sorts
260/// subject-ids and object-ids in independent spaces, so a cross-role (subject↔
261/// object) join's two streams are not co-sorted on the join value. Each side is
262/// streamed from the 6-permutation index already sorted on that column
263/// ([`GraphIndex::scan_iter_sorted_on`]), so the join is a linear two-pointer
264/// merge with no hash table — equal-key runs cross-product. Returns
265/// `(rows, bound_slots)`, or `None` when the shape/index can't support a merge and
266/// the caller should hash-join instead. The result multiset equals the hash
267/// join's (a join is order-independent).
268fn try_merge_join(
269    ctx: &Ctx,
270    index: &GraphIndex,
271    ta: &(SlotTerm, SlotTerm, SlotTerm),
272    tb: &(SlotTerm, SlotTerm, SlotTerm),
273) -> Option<(Vec<Row>, Vec<usize>)> {
274    let dict = ctx.rete.dictionary();
275    let sa = pattern_slots(ta);
276    let sb = pattern_slots(tb);
277    let shared: Vec<usize> = sa.iter().copied().filter(|s| sb.contains(s)).collect();
278    if shared.len() != 1 {
279        return None;
280    }
281    let v = shared[0];
282    let col_of = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Option<usize> {
283        [&t.0, &t.1, &t.2]
284            .iter()
285            .position(|x| matches!(x, SlotTerm::Var(i) if *i == v))
286    };
287    let ca = col_of(ta)?;
288    let cb = col_of(tb)?;
289    if ca != cb {
290        return None; // cross-role: the two role id-spaces aren't co-sorted
291    }
292    // A merge MATERIALIZES both sides in full (`collect` below builds a Vec per
293    // side). When one side is a pinpoint (a bound leading key routing to a few
294    // KB of tiles) and the other is fat (a broad predicate spanning megabytes),
295    // the linear merge costs building — and, on a remote index, FETCHING — the
296    // fat extent end-to-end: gigabytes over HTTP, and the 32-bit wasm OOM
297    // behind `?x wdt:P279 <C> . ?x rdfs:label ?l` on a 185M-triple remote
298    // graph. The hybrid loop handles that shape strictly better (scan the
299    // pinpoint side, probe the fat one per surviving row), so leave the merge
300    // seed to comparably-sized sides.
301    if merge_seed_lopsided(ctx, index, ta, tb) {
302        return None;
303    }
304    let lower = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Option<Pattern> {
305        Some((
306            const_subject(&t.0, dict)?,
307            const_predicate(&t.1)?,
308            const_object(&t.2, dict)?,
309        ))
310    };
311    // Materialize each side as `(join-key, row)`, already ascending in the join
312    // column (the index streams it sorted there).
313    let collect = |t: &(SlotTerm, SlotTerm, SlotTerm), col: usize| -> Option<Vec<(u32, Row)>> {
314        let pat = lower(t)?;
315        let mut out = Vec::new();
316        for tri in canon_ahead(ctx, t, index.scan_iter_sorted_on(pat, col)?) {
317            if let Some(r) = triple_row(ctx, t, tri) {
318                out.push(([tri.0, tri.1, tri.2][col], r));
319            }
320        }
321        Some(out)
322    };
323    let rows_a = collect(ta, ca)?;
324    let rows_b = collect(tb, cb)?;
325
326    let mut out: Vec<Row> = Vec::new();
327    let (mut i, mut j) = (0usize, 0usize);
328    while i < rows_a.len() && j < rows_b.len() {
329        match rows_a[i].0.cmp(&rows_b[j].0) {
330            std::cmp::Ordering::Less => i += 1,
331            std::cmp::Ordering::Greater => j += 1,
332            std::cmp::Ordering::Equal => {
333                let key = rows_a[i].0;
334                let (i0, j0) = (i, j);
335                while i < rows_a.len() && rows_a[i].0 == key {
336                    i += 1;
337                }
338                while j < rows_b.len() && rows_b[j].0 == key {
339                    j += 1;
340                }
341                for (_, ra) in &rows_a[i0..i] {
342                    for (_, rb) in &rows_b[j0..j] {
343                        // Combine the two rows; they agree on the shared slot `v`
344                        // (same key ⇒ same node value at the same column).
345                        let mut row = ra.clone();
346                        let mut ok = true;
347                        for (slot, val) in rb.iter().enumerate() {
348                            if let Some(val) = val {
349                                match &row[slot] {
350                                    Some(existing) if existing != val => {
351                                        ok = false;
352                                        break;
353                                    }
354                                    _ => row[slot] = Some(val.clone()),
355                                }
356                            }
357                        }
358                        if ok {
359                            out.push(row);
360                        }
361                    }
362                }
363            }
364        }
365    }
366    let mut slots = pattern_slots(ta);
367    for s in pattern_slots(tb) {
368        if !slots.contains(&s) {
369            slots.push(s);
370        }
371    }
372    Some((out, slots))
373}
374
375/// Probe the join tail (instead of full-scanning) once the running BGP result is
376/// at most this many rows: each remaining pattern that shares a bound variable is
377/// then resolved by `rows × index-lookup` rather than a whole-extent scan. Kept
378/// small so the probe count is always cheap in absolute terms — the dominant win
379/// is the large-scan-after-tiny-prefix case (a `?x a C` over thousands when the
380/// prefix already pinned ?x to a few dozen rows); a *moderately* large prefix
381/// keeps the one-pass scan + hash join, which beats thousands of probes.
382const BGP_PROBE_THRESHOLD: usize = 512;
383
384/// A pattern whose estimated scan is below this many triples is never worth
385/// planning around: scanning it is cheap whatever the other side holds. Keeps
386/// every small graph (the W3C suite, the playground datasets) on the joins it
387/// always used.
388const PROBE_SCAN_FLOOR: f64 = 65_536.0;
389
390/// Probe instead of scanning once the scan is at least this many times larger
391/// than the rows that would probe it. A probe is a tile-directory binary search
392/// plus a group lookup in an (often cached) tile; a scan pays per triple, and
393/// on the hash-join path also materializes every one of them.
394const PROBE_RATIO: f64 = 16.0;
395
396/// Is probing `rows` bound rows cheaper than scanning a pattern estimated at
397/// `scan_est` triples?
398fn probe_beats_scan(rows: usize, scan_est: f64) -> bool {
399    scan_est >= limits().probe_floor && (rows as f64) * PROBE_RATIO <= scan_est
400}
401
402/// The most rows that may probe a BGP whose cheapest pattern is estimated at
403/// `est` triples while probing still beats evaluating it whole
404/// ([`probe_beats_scan`]); `None` below the probe floor, where the BGP is
405/// cheap to evaluate either way.
406pub(crate) fn probe_row_budget(est: f64) -> Option<usize> {
407    (est >= limits().probe_floor).then(|| (est / PROBE_RATIO) as usize)
408}
409
410/// The smallest tile-directory estimate ([`GraphIndex::estimate_matches`])
411/// among a BGP's patterns — a floor on what evaluating it whole would scan.
412/// `None` when a constant is not in the file (the BGP matches nothing).
413pub(crate) fn bgp_min_estimate(
414    ctx: &Ctx,
415    index: &GraphIndex,
416    patterns: &[TriplePattern],
417) -> Option<f64> {
418    let lowered = lower(patterns, ctx)?;
419    tile_estimates(ctx, index, &lowered, &std::collections::HashSet::new())
420        .into_iter()
421        .reduce(f64::min)
422}
423
424/// The sum of the tile-directory estimates of a BGP's patterns: what evaluating
425/// it whole reads when each pattern is scanned once. [`bgp_min_estimate`] is
426/// only the cheapest pattern's share of that, so on a BGP of several mid-sized
427/// patterns (a journal's title, identifiers and their scheme: 38 k rows each
428/// under the probe floor, 5x that together) it stays under the floor and the
429/// BGP is materialized for a handful of left rows. `None` as for
430/// [`bgp_min_estimate`].
431pub(crate) fn bgp_total_estimate(
432    ctx: &Ctx,
433    index: &GraphIndex,
434    patterns: &[TriplePattern],
435) -> Option<f64> {
436    let lowered = lower(patterns, ctx)?;
437    Some(
438        tile_estimates(ctx, index, &lowered, &std::collections::HashSet::new())
439            .into_iter()
440            .sum(),
441    )
442}
443
444/// Is `t` the pattern `?x rdf:type ?c` with `?x` among the slots `shared` with
445/// the rows probing it, and `?c` not?
446fn is_unbound_class(ctx: &Ctx, t: &(SlotTerm, SlotTerm, SlotTerm), shared: &[usize]) -> bool {
447    let type_pid = ctx.rete.dictionary().predicate_id(crate::file::RDF_TYPE);
448    matches!(
449        t,
450        (SlotTerm::Var(x), SlotTerm::Pred(p), SlotTerm::Var(c))
451            if Some(*p) == type_pid && shared.contains(x) && !shared.contains(c) && x != c
452    )
453}
454
455/// Is a BGP whose cheapest pattern is estimated at `est` rows fat enough that
456/// probing it per outer row beats loading it? [`FAT_SCAN_ROWS`]; tests set the
457/// probe floor instead, to drive the path over a graph small enough to check.
458fn fat_enough(est: f64) -> bool {
459    #[cfg(test)]
460    if TEST_LIMITS.with(|c| c.get()).is_some() {
461        return est >= limits().probe_floor;
462    }
463    est >= FAT_SCAN_ROWS
464}
465
466/// A BGP probed once per outer row instead of evaluated whole: the shape of a
467/// correlated `FILTER (NOT) EXISTS` or `MINUS` over a BGP. Each outer row's
468/// bound variables become constants of the probe ([`ProbeJoin`]), so a fat
469/// BGP is never loaded; a row costs a few index lookups and stops at its
470/// first solution. A BGP below [`FAT_SCAN_ROWS`] is cheap to load once and
471/// index, so it keeps that plan: probing it would only fault scattered tiles.
472pub(crate) struct CorrelatedProbe {
473    /// `None`: a constant is not in the file, so no row has a solution.
474    plan: Option<ProbePlan>,
475    /// The variable slots the BGP mentions.
476    slots: Vec<usize>,
477}
478
479impl CorrelatedProbe {
480    /// `seed` marks the slots the outer rows certainly bind. `None` = evaluate
481    /// whole: the BGP is empty, shares no variable with the outer side, or is
482    /// not fat.
483    pub(crate) fn new(
484        ctx: &Ctx,
485        index: &GraphIndex,
486        patterns: &[TriplePattern],
487        seed: &[bool],
488    ) -> Option<Self> {
489        if patterns.is_empty() {
490            return None;
491        }
492        let mut slots: Vec<usize> = Vec::new();
493        for p in patterns {
494            for t in [&p.s, &p.p, &p.o] {
495                if let PatternTerm::Var(v) = t {
496                    if let Some(i) = ctx.slots.slot(v) {
497                        if !slots.contains(&i) {
498                            slots.push(i);
499                        }
500                    }
501                }
502            }
503        }
504        if !slots.iter().any(|&i| seed[i]) {
505            return None;
506        }
507        // An unknown constant empties the BGP for every row.
508        let Some(est) = bgp_min_estimate(ctx, index, patterns) else {
509            return Some(CorrelatedProbe { plan: None, slots });
510        };
511        if !fat_enough(est) {
512            return None;
513        }
514        Some(CorrelatedProbe {
515            plan: ProbePlan::new(ctx, index, patterns, seed),
516            slots,
517        })
518    }
519
520    /// Does `row` bind a variable of the BGP?
521    pub(crate) fn shares(&self, row: &Row) -> bool {
522        self.slots.iter().any(|&i| row[i].is_some())
523    }
524
525    /// Does the BGP, with `row`'s bindings substituted, have a solution?
526    /// Callers check [`Self::shares`] first: a row that binds none of the
527    /// BGP's variables would re-evaluate all of it.
528    pub(crate) fn probe(&self, ctx: &Ctx, index: &GraphIndex, row: &Row) -> bool {
529        match &self.plan {
530            None => false,
531            Some(plan) => ProbeJoin::from_plan(ctx, index, plan, row.clone())
532                .next()
533                .is_some(),
534        }
535    }
536}
537
538/// Run `f` with the probe floor set to `floor` (tests only), so a join's
539/// probe paths can be driven over a graph small enough to check by hand.
540#[cfg(test)]
541pub(crate) fn with_probe_floor<T>(floor: f64, f: impl FnOnce() -> T) -> T {
542    let saved = TEST_LIMITS.with(|c| c.get());
543    TEST_LIMITS.with(|c| {
544        c.set(Some(PlanLimits {
545            probe_floor: floor,
546            ..limits()
547        }))
548    });
549    let out = f();
550    TEST_LIMITS.with(|c| c.set(saved));
551    out
552}
553
554/// Run `f` with every planner threshold set (tests only): probe floor, the
555/// streaming seed size and the hash-build size. Lets a test elsewhere in the
556/// crate drive each join path over a graph small enough to build in a test.
557#[cfg(test)]
558#[allow(dead_code)]
559pub(crate) fn with_plan_limits<T>(
560    probe_floor: f64,
561    stream_seed: f64,
562    hash_build: f64,
563    f: impl FnOnce() -> T,
564) -> T {
565    let saved = TEST_LIMITS.with(|c| c.get());
566    TEST_LIMITS.with(|c| {
567        c.set(Some(PlanLimits {
568            probe_floor,
569            stream_seed,
570            hash_build,
571        }))
572    });
573    let out = f();
574    TEST_LIMITS.with(|c| c.set(saved));
575    out
576}
577
578/// The planner's size thresholds, gathered so tests can shrink them and drive
579/// every join path over a graph small enough to check by hand.
580#[derive(Clone, Copy)]
581struct PlanLimits {
582    probe_floor: f64,
583    stream_seed: f64,
584    hash_build: f64,
585}
586
587#[cfg(test)]
588thread_local! {
589    static TEST_LIMITS: std::cell::Cell<Option<PlanLimits>> = const { std::cell::Cell::new(None) };
590}
591
592fn limits() -> PlanLimits {
593    #[cfg(test)]
594    if let Some(l) = TEST_LIMITS.with(|c| c.get()) {
595        return l;
596    }
597    PlanLimits {
598        probe_floor: PROBE_SCAN_FLOOR,
599        stream_seed: STREAM_SEED_ROWS,
600        hash_build: HASH_BUILD_ROWS,
601    }
602}
603
604/// A BGP whose most selective pattern is estimated above this many matches is
605/// **streamed** rather than joined into a materialized prefix
606/// ([`BgpSolutions`]): every later pattern is then joined per row (probe) or
607/// against a small materialized pattern (hash), so resident memory no longer
608/// follows the largest pattern. `?s dcite:doi ?d . ?s dcite:fromSnapshot ?x`
609/// materialized 109 M rows before joining and ran a 16 GB container out of
610/// memory.
611const STREAM_SEED_ROWS: f64 = (1u64 << 21) as f64;
612
613/// On the streaming path, a later pattern estimated at no more than this many
614/// matches is scanned once into a hash table; a larger one is probed per row.
615const HASH_BUILD_ROWS: f64 = (1u64 << 20) as f64;
616
617/// Tile-directory cardinality estimates ([`GraphIndex::estimate_matches`]) for
618/// each lowered pattern. A variable an outer seed row binds is a constant at
619/// run time but unknown now: it scales the estimate by the same default
620/// selectivities [`pattern_estimates`] falls back to. An unsatisfiable
621/// constant estimates 0.
622fn tile_estimates(
623    ctx: &Ctx,
624    index: &GraphIndex,
625    lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
626    seed: &std::collections::HashSet<usize>,
627) -> Vec<f64> {
628    const SEL_SUBJECT: f64 = 0.001;
629    const SEL_OBJECT: f64 = 0.02;
630    const SEL_PREDICATE: f64 = 0.05;
631    let dict = ctx.rete.dictionary();
632    let total = ctx.rete.index_triples(index);
633    let seeded = |x: &SlotTerm| matches!(x, SlotTerm::Var(v) if seed.contains(v));
634    // A seeded subject/object of a constant predicate takes that predicate's
635    // MEASURED selectivity from `query_stats` (the SCHEMA section, kind 9, or
636    // a resident pyramid-meta) instead of the fixed default. The tile
637    // directory cannot see a value that only exists at run time, so this is
638    // the one estimate here the statistics improve. They are read only when
639    // some pattern needs them: one small range, once per session, on a lazy
640    // open — never for a query whose patterns have no seeded position.
641    let needs_stats = lowered
642        .iter()
643        .any(|t| matches!(t.1, SlotTerm::Pred(_)) && (seeded(&t.0) || seeded(&t.2)));
644    let stats: std::collections::HashMap<u32, &crate::meta::PredStat> = if needs_stats {
645        ctx.rete
646            .planner_stats(true)
647            .iter()
648            .map(|s| (s.predicate, s))
649            .collect()
650    } else {
651        std::collections::HashMap::new()
652    };
653    // Each pattern is estimated on every permutation that leads with a bound id,
654    // reading the directory leaves its run starts and ends in: fault them all
655    // for all the patterns at once, not one permutation after another.
656    let patterns: Vec<Pattern> = lowered
657        .iter()
658        .filter_map(|t| {
659            Some((
660                const_subject(&t.0, dict)?,
661                const_predicate(&t.1)?,
662                const_object(&t.2, dict)?,
663            ))
664        })
665        .collect();
666    index.prefault_estimate_leaves(&patterns);
667    lowered
668        .iter()
669        .map(|t| {
670            let (Some(s), Some(p), Some(o)) = (
671                const_subject(&t.0, dict),
672                const_predicate(&t.1),
673                const_object(&t.2, dict),
674            ) else {
675                return 0.0;
676            };
677            let mut est = index.estimate_matches((s, p, o), total);
678            if est == 0.0 {
679                return 0.0;
680            }
681            let st = match t.1 {
682                SlotTerm::Pred(pid) => stats.get(&pid).copied(),
683                _ => None,
684            };
685            if seeded(&t.0) {
686                est *= match st {
687                    Some(st) if st.distinct_subjects > 0 => 1.0 / st.distinct_subjects as f64,
688                    _ => SEL_SUBJECT,
689                };
690            }
691            if seeded(&t.1) {
692                est *= SEL_PREDICATE;
693            }
694            if seeded(&t.2) {
695                est *= match st {
696                    Some(st) if st.distinct_objects > 0 => 1.0 / st.distinct_objects as f64,
697                    _ => SEL_OBJECT,
698                };
699            }
700            est.max(1.0)
701        })
702        .collect()
703}
704
705/// Remote (lazy) probe bounds. Over HTTP byte-range reads, a per-row probe is a
706/// network round-trip, so we probe far more reluctantly than in memory: only when
707/// scanning the next pattern would be a *broad* read (a whole-predicate scan,
708/// [`pattern_is_selective`] is false), or the prefix is tiny enough that a handful
709/// of probes is trivial either way. A pattern that carries its own bound
710/// subject/object routes to a narrow index range — cheaper to scan once and
711/// hash-join than to probe per prefix row. Probing a large prefix is always a
712/// loss remotely, so it is capped.
713const REMOTE_PROBE_MIN: usize = 8;
714const REMOTE_PROBE_MAX: usize = 1024;
715
716/// The remote probe budget, widened by the reader's concurrency: a serial
717/// sync-XHR reader (a phone without the COI pool) pays one full round trip per
718/// probe, so its budget stays at [`REMOTE_PROBE_MAX`]; a reader overlapping
719/// 16 range reads (the CLI's thread pool, the asyncified fetch variant, the
720/// COI fetch-worker pool) amortizes ~16 probes per round trip and gets a
721/// proportionally larger budget before the one-pass scan wins again.
722fn remote_probe_max(index: &GraphIndex) -> usize {
723    REMOTE_PROBE_MAX * index.read_concurrency().clamp(1, 16)
724}
725
726/// The rows a first [`Windowed`] window holds: few enough that a `LIMIT 1` or an
727/// `ASK` that stops after one row costs at most a few parallel reads.
728const WINDOW_START_ROWS: usize = 256;
729
730/// The most rows one [`Windowed`] window holds. The window doubles from
731/// [`WINDOW_START_ROWS`] (times four) up to this; the tile and byte bound of
732/// [`ProbeBatch`] cuts it shorter where the rows' tiles are many or large.
733const WINDOW_MAX_ROWS: usize = 1 << 16;
734
735/// Rows pulled and routed together while a window fills: their directory
736/// leaves are faulted in one read.
737const WINDOW_CHUNK_ROWS: usize = 256;
738
739/// How a row becomes the pattern its probe will run.
740type ProbePattern<'a> = Box<dyn Fn(&Row) -> Option<Pattern> + 'a>;
741
742/// A stream of rows about to be **probed** against a remote index, handed on
743/// unchanged and in order, with each window's tiles faulted in one coalesced,
744/// parallel read ([`GraphIndex::probe_batch_fault`]) just before the window is
745/// consumed.
746///
747/// A probe join over a lazy reader otherwise faults one tile per probe, one
748/// round trip at a time (the lazy streaming join did exactly that), or — when
749/// the whole prefix was prefetched at once — faulted more tiles than the tile
750/// cache holds, so the early ones were evicted before their probes ran and
751/// came back one request each (G50a: 15,539 requests at 0.12 s for a 221,817
752/// row prefix). A window grows until its tiles fill a [`ProbeBatch`] (tiles and
753/// stored bytes, within the cache budget), so the reader's fan-out is used (up
754/// to `read_concurrency` requests in flight) and memory stays bounded; it
755/// starts small and grows fourfold, so a demand-bounded consumer reads only a little
756/// past what it uses.
757///
758/// A local index has nothing to fault: the stream passes through untouched.
759pub(crate) struct Windowed<'a> {
760    index: &'a GraphIndex,
761    upstream: Box<dyn Iterator<Item = Row> + 'a>,
762    /// `None`: pass through (a local index).
763    pat_of: Option<ProbePattern<'a>>,
764    /// Pulled from upstream, not yet in a window.
765    pending: std::collections::VecDeque<Row>,
766    /// The window whose tiles were requested (or are resident): ready to probe.
767    ready: std::collections::VecDeque<Row>,
768    /// The next window's row cap.
769    size: usize,
770}
771
772/// Fault `rows`' probe tiles a window at a time as they are consumed.
773pub(crate) fn windowed<'a>(
774    index: &'a GraphIndex,
775    upstream: impl Iterator<Item = Row> + 'a,
776    pat_of: impl Fn(&Row) -> Option<Pattern> + 'a,
777) -> Windowed<'a> {
778    Windowed {
779        index,
780        upstream: Box::new(upstream),
781        pat_of: index.is_remote().then(|| {
782            let f: ProbePattern<'a> = Box::new(pat_of);
783            f
784        }),
785        pending: std::collections::VecDeque::new(),
786        ready: std::collections::VecDeque::new(),
787        size: WINDOW_START_ROWS,
788    }
789}
790
791impl Windowed<'_> {
792    /// Fill `ready` with the next window and fault its tiles.
793    fn refill(&mut self, pat_of: &dyn Fn(&Row) -> Option<Pattern>) {
794        let mut batch = ProbeBatch::default();
795        'window: while self.ready.len() < self.size {
796            let chunk = WINDOW_CHUNK_ROWS.min(self.size - self.ready.len());
797            while self.pending.len() < chunk {
798                match self.upstream.next() {
799                    Some(r) => self.pending.push_back(r),
800                    None => break,
801                }
802            }
803            if self.pending.is_empty() {
804                break;
805            }
806            let chunk = chunk.min(self.pending.len());
807            // One batched read for the chunk's directory leaves.
808            let pats: Vec<Pattern> = self.pending.iter().take(chunk).filter_map(pat_of).collect();
809            self.index.prefault_leaves(&pats);
810            for _ in 0..chunk {
811                if let Some(p) = pat_of(&self.pending[0]) {
812                    if !self.index.probe_batch_add(&mut batch, p) {
813                        break 'window; // the window is full: this row opens the next
814                    }
815                }
816                let row = self.pending.pop_front().expect("chunk rows are pending");
817                self.ready.push_back(row);
818            }
819        }
820        self.index.probe_batch_fault(batch);
821        self.size = (self.size * 4).min(WINDOW_MAX_ROWS);
822    }
823}
824
825impl Iterator for Windowed<'_> {
826    type Item = Row;
827
828    fn next(&mut self) -> Option<Row> {
829        // Taken out so `refill` can borrow `self` mutably, and put back.
830        let Some(pat_of) = self.pat_of.take() else {
831            return self.upstream.next();
832        };
833        if self.ready.is_empty() {
834            self.refill(pat_of.as_ref());
835        }
836        self.pat_of = Some(pat_of);
837        self.ready.pop_front()
838    }
839}
840
841/// The probe pattern a lowered triple pattern runs for `base`: every term the
842/// row binds is a constant. `None` when a bound value cannot take its role (the
843/// probe is empty), so there is nothing to fault.
844fn bgp_probe_pattern<'a>(
845    ctx: &'a Ctx<'_>,
846    t: (SlotTerm, SlotTerm, SlotTerm),
847) -> impl Fn(&Row) -> Option<Pattern> + 'a {
848    move |base| match (
849        probe_subject(ctx, &t.0, base),
850        probe_predicate(ctx, &t.1, base),
851        probe_object(ctx, &t.2, base),
852    ) {
853        (Some(s), Some(p), Some(o)) => Some((s, p, o)),
854        _ => None,
855    }
856}
857
858/// `rows` as the seeds of a [`ProbePlan`], with the tiles its FIRST pattern
859/// will route to faulted a window ahead ([`Windowed`]). Only the first pattern
860/// is prefetchable (later ones bind from earlier probe results), and only rows
861/// whose seed binds that pattern's subject or object are included: a
862/// predicate-only pattern routes to the predicate's WHOLE span, which for the
863/// fat sides this path serves would prefetch the very extent the probe strategy
864/// exists to avoid.
865pub(crate) fn plan_windowed<'q>(
866    ctx: &'q Ctx<'q>,
867    index: &'q GraphIndex,
868    plan: &ProbePlan,
869    rows: Box<dyn Iterator<Item = Row> + 'q>,
870) -> Box<dyn Iterator<Item = Row> + 'q> {
871    let Some(&t) = plan.pats.first() else {
872        return rows;
873    };
874    if !index.is_remote() {
875        return rows;
876    }
877    let pat = bgp_probe_pattern(ctx, t);
878    let mut win = windowed(index, rows, move |base| {
879        pat(base).filter(|(s, _, o)| s.is_some() || o.is_some())
880    });
881    // A window is pulled whole before its first row comes out. Under a demand
882    // bound the first one holds no more than the bound: a sparse left side
883    // (a selective filter over a scan) otherwise has to yield 256 rows before
884    // a `LIMIT 25` sees the first (G33).
885    if let Some(demand) = ctx.limit_hint.get() {
886        win.size = win.size.min(demand.max(1));
887    }
888    Box::new(win)
889}
890
891/// Batch-fault the tiles that probing `patterns` from `subject_ids` (each
892/// bound onto the subject variable `sv`) will route to — one coalesced read
893/// per section instead of one round trip per candidate. Purely a cache
894/// warmer: correctness is untouched, and a local index is a no-op. Used by
895/// the FILTER-CONTAINS pushdown before it probes its candidate subjects.
896pub(crate) fn prefetch_subject_probes(
897    ctx: &Ctx,
898    index: &GraphIndex,
899    patterns: &[TriplePattern],
900    sv: &str,
901    subject_ids: &[u32],
902) {
903    if !index.is_remote() {
904        return;
905    }
906    let Some(lowered) = lower(patterns, ctx) else {
907        return;
908    };
909    let Some(slot) = ctx.slots.slot(sv) else {
910        return;
911    };
912    let dict = ctx.rete.dictionary();
913    let mut pats: Vec<Pattern> = Vec::new();
914    for &sid in subject_ids {
915        let mut base = ctx.slots.empty_row();
916        base[slot] = Some(Val::Id(dict.subject_node(sid) as i64));
917        for t in &lowered {
918            if !matches!(t.0, SlotTerm::Var(i) if i == slot) {
919                continue;
920            }
921            if let (Some(s), Some(p), Some(o)) = (
922                probe_subject(ctx, &t.0, &base),
923                probe_predicate(ctx, &t.1, &base),
924                probe_object(ctx, &t.2, &base),
925            ) {
926                pats.push((s, p, o));
927            }
928        }
929    }
930    index.prefetch_probe_tiles(&pats);
931}
932
933/// A pattern whose own constant terms (a bound subject or object) already route
934/// it to a narrow index range — a few coalesced range reads to scan in full.
935fn pattern_is_selective(t: &(SlotTerm, SlotTerm, SlotTerm)) -> bool {
936    matches!(t.0, SlotTerm::Node(_)) || matches!(t.2, SlotTerm::Node(_))
937}
938
939/// The (deduped) slots a lowered pattern binds.
940fn pattern_slots(t: &(SlotTerm, SlotTerm, SlotTerm)) -> Vec<usize> {
941    let mut slots: Vec<usize> = Vec::new();
942    for term in [&t.0, &t.1, &t.2] {
943        if let SlotTerm::Var(i) = term {
944            if !slots.contains(i) {
945                slots.push(*i);
946            }
947        }
948    }
949    slots
950}
951
952/// How many scanned triples [`canon_ahead`] pulls before canonicalizing their
953/// predicates together.
954const CANON_AHEAD: usize = 64;
955
956/// `triples`, with the predicates of each run of [`CANON_AHEAD`] of them
957/// canonicalized in one batch before the first row of the run is built.
958///
959/// A pattern with a variable predicate canonicalizes every new predicate it
960/// meets ([`pred_val`]): its term is looked up as a node, up to three chunk
961/// reads, each a round trip on a lazy open, one new predicate after another.
962/// Looking the run's predicates up together costs the round trips of one
963/// ([`crate::row::Resolver::prefetch_canon`]). Anything but a variable
964/// predicate over a faulting dictionary passes straight through.
965fn canon_ahead<'a, 'c>(
966    ctx: &'a Ctx<'c>,
967    t: &(SlotTerm, SlotTerm, SlotTerm),
968    triples: impl Iterator<Item = Triple> + 'a,
969) -> Box<dyn Iterator<Item = Triple> + 'a> {
970    if !matches!(t.1, SlotTerm::Var(_)) || !ctx.rete.dictionary().faults_chunks() {
971        return Box::new(triples);
972    }
973    // Which of the subject and object the query will decode as it ends: a
974    // projected variable of this pattern (see [`Ctx::decode_ahead`]).
975    let decoded = |term: &SlotTerm| match term {
976        SlotTerm::Var(i) => ctx.decodes_slot(*i),
977        _ => false,
978    };
979    Box::new(CanonAhead {
980        ctx,
981        triples,
982        run: std::collections::VecDeque::new(),
983        decode: (decoded(&t.0), decoded(&t.2)),
984        ahead: 0,
985    })
986}
987
988struct CanonAhead<'a, 'c, I> {
989    ctx: &'a Ctx<'c>,
990    triples: I,
991    run: std::collections::VecDeque<Triple>,
992    /// Is the subject, the object, decoded by the query's final projection?
993    decode: (bool, bool),
994    /// Rows whose terms were already prefetched, across every run: the
995    /// decode-ahead is capped by the query's demand once, not once per run.
996    ahead: usize,
997}
998
999impl<I: Iterator<Item = Triple>> Iterator for CanonAhead<'_, '_, I> {
1000    type Item = Triple;
1001
1002    fn next(&mut self) -> Option<Triple> {
1003        if self.run.is_empty() {
1004            self.run.extend(self.triples.by_ref().take(CANON_AHEAD));
1005            let preds: Vec<u32> = self.run.iter().map(|t| t.1).collect();
1006            // The rows the query will decode are these ones (up to its LIMIT):
1007            // their terms go out with the canonicalization lookups, one batch
1008            // for both, where the decode after the last row was two more
1009            // dependent reads (leaves, then chunks) on a leafed dictionary.
1010            let dict = self.ctx.rete.dictionary();
1011            let take = self
1012                .ctx
1013                .decode_rows()
1014                .saturating_sub(self.ahead)
1015                .min(self.run.len());
1016            self.ahead += take;
1017            let mut nodes: Vec<u32> = Vec::new();
1018            for t in self.run.iter().take(take) {
1019                if self.decode.0 {
1020                    nodes.push(dict.subject_node(t.0));
1021                }
1022                if self.decode.1 {
1023                    nodes.push(dict.object_node(t.2));
1024                }
1025            }
1026            self.ctx.resolver.prefetch_canon(&preds, &nodes);
1027        }
1028        self.run.pop_front()
1029    }
1030}
1031
1032/// The row value of a matched triple's predicate `p_id`, for a pattern whose
1033/// predicate slot is `slot`. Only a variable predicate binds it, so only then
1034/// is it canonicalized (a predicate that is also a node becomes the node id):
1035/// that is a dictionary lookup of the predicate as a node, memoized per query,
1036/// but up to three dependent chunk reads on a lazy open for each new predicate
1037/// — reads a constant predicate never needed. Otherwise the value is unused.
1038fn pred_val(ctx: &Ctx, slot: &SlotTerm, p_id: u32) -> i64 {
1039    match slot {
1040        SlotTerm::Var(_) => ctx.resolver.canon_id(pred_tag(p_id)),
1041        _ => pred_tag(p_id),
1042    }
1043}
1044
1045/// Build a solution row for one scanned triple, enforcing repeated variables
1046/// *within* the pattern (e.g. `?x p ?x`). `None` = the triple doesn't satisfy
1047/// a repeated variable.
1048fn triple_row(
1049    ctx: &Ctx,
1050    t: &(SlotTerm, SlotTerm, SlotTerm),
1051    (s_id, p_id, o_id): (u32, u32, u32),
1052) -> Option<Row> {
1053    // A query under a memory ceiling ([`crate::guard`]) stops between rows.
1054    crate::guard::check();
1055    let dict = ctx.rete.dictionary();
1056    let s_val = dict.subject_node(s_id) as i64;
1057    let p_val = pred_val(ctx, &t.1, p_id);
1058    let o_val = dict.object_node(o_id) as i64;
1059    let mut row = ctx.slots.empty_row();
1060    for (term, val) in [(&t.0, s_val), (&t.1, p_val), (&t.2, o_val)] {
1061        if let SlotTerm::Var(i) = term {
1062            match row[*i] {
1063                Some(Val::Id(existing)) if existing != val => return None,
1064                Some(_) => {}
1065                None => row[*i] = Some(Val::Id(val)),
1066            }
1067        }
1068    }
1069    Some(row)
1070}
1071
1072/// Lazily scan one lowered pattern as a stream of solution rows. The scan
1073/// constrains only the pattern's constant terms (bound variables are joined in
1074/// afterwards, not pushed into the scan). `None` = a constant is unsatisfiable
1075/// (unknown to the dictionary or in an impossible role), which empties the BGP.
1076fn scan_rows<'q>(
1077    ctx: &'q Ctx<'q>,
1078    index: &'q GraphIndex,
1079    t: (SlotTerm, SlotTerm, SlotTerm),
1080) -> Option<impl Iterator<Item = Row> + 'q> {
1081    let dict = ctx.rete.dictionary();
1082    let (sid, pid, oid) = (
1083        const_subject(&t.0, dict)?,
1084        const_predicate(&t.1)?,
1085        const_object(&t.2, dict)?,
1086    );
1087    Some(
1088        canon_ahead(ctx, &t, index.scan_iter((sid, pid, oid)))
1089            .filter_map(move |triple| triple_row(ctx, &t, triple)),
1090    )
1091}
1092
1093/// What a multi-pattern BGP joins its streamed pattern against: every pattern
1094/// but the last, joined, and bucketed on the slots the last one shares.
1095/// Built once for all shards of a grouped query run on several threads.
1096struct SharedPrefix {
1097    rows: Vec<Row>,
1098    /// Prefix row indices keyed by the shared-slot values.
1099    buckets: HashMap<Vec<Val>, Vec<usize>>,
1100    shared: Vec<usize>,
1101}
1102
1103/// A small pattern of a streaming BGP, as a table keyed on the slots it
1104/// shares with the rows streamed so far. `None`: the pattern is unsatisfiable.
1105type SharedTable = Option<HashMap<Vec<Val>, Vec<Row>>>;
1106
1107/// A BGP as shard `part` of a grouped query run on several threads
1108/// ([`crate::row::Shard`]): the rows [`BgpSolutions::new`] yields, in its
1109/// order, for one slice of the work.
1110///
1111/// It takes the decisions `BgpSolutions::new` takes, from the same estimates,
1112/// and slices whatever that would stream:
1113///
1114/// - one pattern: the scan's tiles;
1115/// - a large most-selective pattern (the streaming join): that pattern's
1116///   tiles, every later pattern joined per row as there, its hash table (when
1117///   it is a small pattern) built once for all shards;
1118/// - otherwise the prefix (every pattern but the last, joined) is built once
1119///   for all shards, and the slice is of the last pattern's tiles, or of the
1120///   prefix rows when they look the last pattern up instead of scanning it.
1121///
1122/// `None` when the BGP cannot be sliced (two large patterns merge-joined on
1123/// their subject, an unsatisfiable constant, an empty prefix): the caller
1124/// evaluates it whole, the shard is not counted as applied, and the query
1125/// runs on one thread.
1126pub(crate) fn shard_bgp_rows<'q>(
1127    ctx: &'q Ctx<'q>,
1128    index: &'q GraphIndex,
1129    patterns: &[TriplePattern],
1130    part: crate::row::ShardPart,
1131) -> Option<Box<dyn Iterator<Item = Row> + 'q>> {
1132    if patterns.is_empty() {
1133        return None;
1134    }
1135    let lowered = lower(patterns, ctx)?;
1136    let node = part.0;
1137    let dict = ctx.rete.dictionary();
1138    // The pattern's scan, cut to this shard's slice of its tiles.
1139    let cut_scan =
1140        |t: (SlotTerm, SlotTerm, SlotTerm)| -> Option<Box<dyn Iterator<Item = Row> + 'q>> {
1141            let (sid, pid, oid) = (
1142                const_subject(&t.0, dict)?,
1143                const_predicate(&t.1)?,
1144                const_object(&t.2, dict)?,
1145            );
1146            let cut = |start: usize, end: usize| ctx.shard.applied(part, start, end);
1147            let triples = index.scan_iter_cut((sid, pid, oid), &cut);
1148            Some(Box::new(
1149                canon_ahead(ctx, &t, triples).filter_map(move |triple| triple_row(ctx, &t, triple)),
1150            ))
1151        };
1152    if lowered.len() == 1 {
1153        return cut_scan(lowered[0]);
1154    }
1155    let (order, est) = plan_order(ctx, index, &lowered);
1156
1157    // The streaming join: the seed pattern's scan is sliced.
1158    if est[order[0]] > limits().stream_seed {
1159        let seed = lowered[order[0]];
1160        // Two large patterns that share their subject are merge-joined, both
1161        // streams in subject order: the slice is a range of subjects, the
1162        // same on both sides, cut where the seed's tiles are.
1163        let merged = est[order[1]] > limits().stream_seed
1164            && merge_stream(ctx, index, seed, lowered[order[1]], None).is_some();
1165        let (mut stream, mut bound, skip) = if merged {
1166            let n = part.2.max(1);
1167            let pat = (
1168                const_subject(&seed.0, dict)?,
1169                const_predicate(&seed.1)?,
1170                const_object(&seed.2, dict)?,
1171            );
1172            // By shard count: the measuring pass and the run may differ in it.
1173            let cuts = ctx
1174                .shard
1175                .shared(node, 1_000_000 + n, || index.sorted_cuts(pat, 0, n));
1176            let (cuts, tiles) = (*cuts).as_ref()?;
1177            let _ = ctx.shard.applied(part, 0, *tiles);
1178            let i = part.1;
1179            let lo = if i == 0 {
1180                0
1181            } else {
1182                cuts.get(i - 1).copied().unwrap_or(u32::MAX)
1183            };
1184            let hi = match cuts.get(i) {
1185                Some(&c) => u64::from(c),
1186                // The last slice, and any past a short list of cuts.
1187                None if i >= cuts.len() => u64::MAX,
1188                None => 0,
1189            };
1190            // A slice past the cuts but not the last one holds nothing: the
1191            // last slice took everything from the final cut on.
1192            let (lo, hi) = if i > cuts.len() { (0, 0) } else { (lo, hi) };
1193            let (stream, slots) =
1194                merge_stream(ctx, index, seed, lowered[order[1]], Some((lo, hi)))?;
1195            (stream, slots, 2)
1196        } else {
1197            (cut_scan(seed)?, pattern_slots(&seed), 1)
1198        };
1199        for &i in &order[skip..] {
1200            let t = lowered[i];
1201            let slots = pattern_slots(&t);
1202            let shared: Vec<usize> = slots
1203                .iter()
1204                .copied()
1205                .filter(|s| bound.contains(s))
1206                .collect();
1207            if !shared.is_empty() && est[i] > limits().hash_build {
1208                stream = Box::new(
1209                    windowed(index, stream, bgp_probe_pattern(ctx, t))
1210                        .flat_map(move |base| probe_rows(ctx, index, t, base)),
1211                );
1212            } else {
1213                let key_slots = shared.clone();
1214                let table = ctx.shard.shared(node, 1 + i, || -> SharedTable {
1215                    let (rel, _) = pattern_rows(ctx, index, &t)?;
1216                    let mut table: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
1217                    for r in rel {
1218                        let key: Vec<Val> =
1219                            key_slots.iter().map(|&s| r[s].clone().unwrap()).collect();
1220                        table.entry(key).or_default().push(r);
1221                    }
1222                    Some(table)
1223                });
1224                if table.is_none() {
1225                    // An unsatisfiable pattern: no solution in any shard.
1226                    return Some(Box::new(std::iter::empty()));
1227                }
1228                let fill = slots.clone();
1229                stream = Box::new(stream.flat_map(move |base| {
1230                    let key: Vec<Val> = shared.iter().map(|&s| base[s].clone().unwrap()).collect();
1231                    let out: Vec<Row> = (*table)
1232                        .as_ref()
1233                        .and_then(|t| t.get(&key))
1234                        .map(|rs| {
1235                            rs.iter()
1236                                .map(|r| {
1237                                    let mut row = base.clone();
1238                                    for &s in &fill {
1239                                        row[s] = r[s].clone();
1240                                    }
1241                                    row
1242                                })
1243                                .collect()
1244                        })
1245                        .unwrap_or_default();
1246                    out.into_iter()
1247                }));
1248            }
1249            for s in slots {
1250                if !bound.contains(&s) {
1251                    bound.push(s);
1252                }
1253            }
1254        }
1255        return Some(stream);
1256    }
1257
1258    // The materializing join: the prefix is built once for all shards.
1259    let (&last_i, prefix_is) = order.split_last()?;
1260    let last = lowered[last_i];
1261    // A last pattern that routes to one tile is a query too small to split:
1262    // say so before the prefix is built here, and again by the single thread.
1263    let last_pat = (
1264        const_subject(&last.0, dict)?,
1265        const_predicate(&last.1)?,
1266        const_object(&last.2, dict)?,
1267    );
1268    if index.scan_plan(last_pat).tiles_routed < 2 {
1269        return None;
1270    }
1271    let prefix = ctx.shard.shared(node, 0, || {
1272        let prefix_pats: Vec<TriplePattern> =
1273            prefix_is.iter().map(|&i| patterns[i].clone()).collect();
1274        let rows = eval_bgp_rows(ctx, index, &prefix_pats);
1275        let shared: Vec<usize> = match rows.first() {
1276            Some(first) => pattern_slots(&last)
1277                .into_iter()
1278                .filter(|&s| first[s].is_some())
1279                .collect(),
1280            None => Vec::new(),
1281        };
1282        let mut buckets: HashMap<Vec<Val>, Vec<usize>> = HashMap::new();
1283        if !shared.is_empty() {
1284            for (i, r) in rows.iter().enumerate() {
1285                let key: Vec<Val> = shared.iter().map(|&s| r[s].clone().unwrap()).collect();
1286                buckets.entry(key).or_default().push(i);
1287            }
1288        }
1289        SharedPrefix {
1290            rows,
1291            buckets,
1292            shared,
1293        }
1294    });
1295    if prefix.rows.is_empty() {
1296        return None;
1297    }
1298    let shared = &prefix.shared;
1299    let class_probe = !shared.is_empty()
1300        && est[last_i] >= limits().probe_floor
1301        && (prefix.rows.len() as f64) <= est[last_i]
1302        && is_unbound_class(ctx, &last, shared);
1303    if !shared.is_empty() && (probe_beats_scan(prefix.rows.len(), est[last_i]) || class_probe) {
1304        // The prefix rows look the last pattern up: slice the rows.
1305        let (lo, hi) = ctx.shard.applied_rows(part, prefix.rows.len());
1306        let mine: Vec<Row> = prefix.rows[lo..hi].to_vec();
1307        return Some(Box::new(
1308            windowed(index, mine.into_iter(), bgp_probe_pattern(ctx, last))
1309                .flat_map(move |base| probe_rows(ctx, index, last, base)),
1310        ));
1311    }
1312    // The last pattern is scanned, and each of its rows joined to the prefix.
1313    let scan = cut_scan(last)?;
1314    let mut matches: Vec<usize> = Vec::new();
1315    Some(Box::new(scan.flat_map(move |s| {
1316        matches.clear();
1317        if prefix.shared.is_empty() {
1318            matches.extend(0..prefix.rows.len());
1319        } else {
1320            let key: Vec<Val> = prefix
1321                .shared
1322                .iter()
1323                .map(|&i| s[i].clone().unwrap())
1324                .collect();
1325            if let Some(c) = prefix.buckets.get(&key) {
1326                matches.extend_from_slice(c);
1327            }
1328        }
1329        let out: Vec<Row> = matches
1330            .iter()
1331            .map(|&pi| {
1332                let mut merged = prefix.rows[pi].clone();
1333                for (slot, v) in s.iter().enumerate() {
1334                    if v.is_some() {
1335                        merged[slot] = v.clone();
1336                    }
1337                }
1338                merged
1339            })
1340            .collect();
1341        out.into_iter()
1342    })))
1343}
1344
1345/// `GRAPH ?g { one pattern }` over a quad-index file: every match of the
1346/// pattern in any graph as a row that also binds slot `gslot` to the graph,
1347/// streamed from one pass over the tiles (no view per graph). `None` when this
1348/// does not apply (not a single pattern, the graph variable also inside the
1349/// pattern, a file without a quad index): the caller falls back to walking the
1350/// graphs. A constant the dictionary cannot place gives an empty stream.
1351pub(crate) fn quad_scan_rows<'q>(
1352    ctx: &'q Ctx<'q>,
1353    patterns: &[TriplePattern],
1354    gslot: usize,
1355    part: Option<crate::row::ShardPart>,
1356) -> Option<Box<dyn Iterator<Item = Row> + 'q>> {
1357    let [p] = patterns else {
1358        return None;
1359    };
1360    if [&p.s, &p.p, &p.o]
1361        .iter()
1362        .any(|t| matches!(t, PatternTerm::Var(v) if ctx.slots.slot(v) == Some(gslot)))
1363    {
1364        return None;
1365    }
1366    let dict = ctx.rete.dictionary();
1367    let Some(lowered) = lower(patterns, ctx) else {
1368        return Some(Box::new(std::iter::empty()));
1369    };
1370    let t = lowered[0];
1371    let (Some(sid), Some(pid), Some(oid)) = (
1372        const_subject(&t.0, dict),
1373        const_predicate(&t.1),
1374        const_object(&t.2, dict),
1375    ) else {
1376        return Some(Box::new(std::iter::empty()));
1377    };
1378    let mut scan = ctx.rete.named_quad_scan((sid, pid, oid))?;
1379    // A shard of a grouped query run on several threads: its slice of the
1380    // tiles ([`crate::row::Shard`]).
1381    if let Some(part) = part {
1382        let (start, end) = scan.tile_range();
1383        let (lo, hi) = ctx.shard.applied(part, start, end);
1384        scan.restrict(lo, hi);
1385    }
1386    Some(Box::new(scan.filter_map(move |(g, triple)| {
1387        let mut row = triple_row(ctx, &t, triple)?;
1388        row[gslot] = Some(Val::Id(dict.subject_node(g) as i64));
1389        Some(row)
1390    })))
1391}
1392
1393mod class_probe;
1394pub(crate) use class_probe::class_probe_rows;
1395pub use class_probe::set_class_route;
1396
1397/// A triple pattern as the dictionary ids of its constants (subject, predicate, object).
1398pub(crate) type ScanPattern = (Option<u32>, Option<u32>, Option<u32>);
1399
1400/// The pattern of a BGP that best narrows a scan over every graph, as the
1401/// dictionary ids of its constants: the one with the most constants, a bound
1402/// subject or object weighing more than a bound predicate. `None` when no
1403/// pattern has a constant, or one cannot be placed in the dictionary.
1404pub(crate) fn driver_pattern(ctx: &Ctx, patterns: &[TriplePattern]) -> Option<ScanPattern> {
1405    let dict = ctx.rete.dictionary();
1406    let lowered = lower(patterns, ctx)?;
1407    let mut best: Option<(u32, ScanPattern)> = None;
1408    for t in &lowered {
1409        let (sid, pid, oid) = (
1410            const_subject(&t.0, dict)?,
1411            const_predicate(&t.1)?,
1412            const_object(&t.2, dict)?,
1413        );
1414        let score =
1415            3 * u32::from(sid.is_some()) + u32::from(pid.is_some()) + 3 * u32::from(oid.is_some());
1416        if score > 0 && best.is_none_or(|(b, _)| score > b) {
1417            best = Some((score, (sid, pid, oid)));
1418        }
1419    }
1420    best.map(|(_, pat)| pat)
1421}
1422
1423/// Scan one lowered pattern into a materialized relation, returning the rows
1424/// and the slots the pattern binds. `None` = a constant is unsatisfiable.
1425fn pattern_rows(
1426    ctx: &Ctx,
1427    index: &GraphIndex,
1428    t: &(SlotTerm, SlotTerm, SlotTerm),
1429) -> Option<(Vec<Row>, Vec<usize>)> {
1430    let slots = pattern_slots(t);
1431    let mut rel: Vec<Row> = Vec::new();
1432    let dict = ctx.rete.dictionary();
1433    let (sid, pid, oid) = (
1434        const_subject(&t.0, dict)?,
1435        const_predicate(&t.1)?,
1436        const_object(&t.2, dict)?,
1437    );
1438    // Stream the matches with the lazy cursor — the hash join is
1439    // order-independent, so no canonical re-sort is needed here.
1440    for triple in canon_ahead(ctx, t, index.scan_iter((sid, pid, oid))) {
1441        if let Some(row) = triple_row(ctx, t, triple) {
1442            rel.push(row);
1443        }
1444    }
1445    Some((rel, slots))
1446}
1447
1448/// A per-pattern cardinality estimate, smaller = cheaper to scan. The base is
1449/// the **exact** per-predicate triple count (sum of the summary quotient graph's
1450/// super-edge counts) when the predicate is bound, else the whole-graph total.
1451/// A bound subject/object (a constant, or a variable already bound by `seed`)
1452/// then scales it down by that predicate's **measured selectivity** from the
1453/// `query_stats` block — `1 / distinct_subjects` for a bound subject (so
1454/// `<s> <p> ?o` ≈ the average objects per subject; exactly 1 for a functional
1455/// predicate), `1 / distinct_objects` for a bound object. Files built before the
1456/// `query_stats` block fall back to fixed default selectivities. `None` when the
1457/// file carries no pyramid summary at all — ordering then uses the constant-count
1458/// heuristic.
1459fn pattern_estimates(
1460    ctx: &Ctx,
1461    index: &GraphIndex,
1462    lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1463    seed: &std::collections::HashSet<usize>,
1464) -> Option<Vec<f64>> {
1465    // Only use the summary when it's already in memory — never fault it just to
1466    // plan (the lazy remote path defers the pyramid by design).
1467    let pyr = ctx.rete.pyramid_if_loaded()?;
1468    let mut pred: std::collections::HashMap<u32, u64> = std::collections::HashMap::new();
1469    for e in &pyr.summary {
1470        *pred.entry(e.predicate).or_insert(0) += e.count as u64;
1471    }
1472    // Measured per-predicate distinct subjects/objects: the SCHEMA section
1473    // (kind 9) — where a file built since it existed keeps them, its
1474    // pyramid-meta holding only the community summary — else the pyramid-meta's
1475    // query-stats block; empty on files built before either → the default
1476    // selectivities. The pyramid is resident here, so the (small) section is
1477    // too on a resident open, and costs one range once on a lazy one.
1478    let stats: std::collections::HashMap<u32, &crate::meta::PredStat> = ctx
1479        .rete
1480        .planner_stats(true)
1481        .iter()
1482        .map(|s| (s.predicate, s))
1483        .collect();
1484    // The active graph's own size: a pattern inside `GRAPH <g>` cannot match more
1485    // triples than `g` holds, whatever the file-wide predicate count says.
1486    let graph_total = ctx.rete.index_triples(index).max(1) as f64;
1487    let total = graph_total;
1488    let num_preds = pred.len().max(1) as f64;
1489    // Defaults used only when query_stats has no entry for the predicate.
1490    const SEL_SUBJECT: f64 = 0.001;
1491    const SEL_OBJECT: f64 = 0.02;
1492    let node_bound = |t: &SlotTerm| match t {
1493        SlotTerm::Node(_) => true,
1494        SlotTerm::Var(v) => seed.contains(v),
1495        SlotTerm::Pred(_) => false,
1496    };
1497    Some(
1498        lowered
1499            .iter()
1500            .map(|t| {
1501                // Base from the predicate: exact total for a constant predicate,
1502                // the average predicate total for a seed-bound predicate variable
1503                // (the value is known to the probe but not at plan time), else the
1504                // whole graph. `st` is the measured stats for a constant predicate.
1505                let (base, st) = match t.1 {
1506                    SlotTerm::Pred(p) => {
1507                        (*pred.get(&p).unwrap_or(&0) as f64, stats.get(&p).copied())
1508                    }
1509                    SlotTerm::Var(v) if seed.contains(&v) => (total / num_preds, None),
1510                    _ => (total, None),
1511                };
1512                let mut est = base.min(graph_total).max(1.0);
1513                if node_bound(&t.0) {
1514                    est *= match st {
1515                        Some(s) if s.distinct_subjects > 0 => 1.0 / s.distinct_subjects as f64,
1516                        _ => SEL_SUBJECT,
1517                    };
1518                }
1519                if node_bound(&t.2) {
1520                    est *= match st {
1521                        Some(s) if s.distinct_objects > 0 => 1.0 / s.distinct_objects as f64,
1522                        _ => SEL_OBJECT,
1523                    };
1524                }
1525                est.max(1.0)
1526            })
1527            .collect(),
1528    )
1529}
1530
1531/// The minimum, over a BGP's patterns, of [`pattern_scan_bytes`] — the
1532/// cheapest single-pattern scan the hash-join path would at least perform to
1533/// materialize this BGP. `None` = a constant term is unknown to the
1534/// dictionary (the BGP is unsatisfiable; the caller short-circuits anyway).
1535/// Unlike [`pattern_estimates`], this needs no pyramid summary, so it works on
1536/// remote-lazy files — exactly where the answer matters most.
1537pub(crate) fn bgp_min_scan_bytes(
1538    ctx: &Ctx,
1539    index: &GraphIndex,
1540    patterns: &[TriplePattern],
1541) -> Option<u64> {
1542    let lowered = lower(patterns, ctx)?;
1543    lowered
1544        .iter()
1545        .map(|t| pattern_scan_bytes(ctx, index, t))
1546        .min()
1547}
1548
1549/// One pattern's cheapest scan extent in BYTES — what `rete cost` previews
1550/// (the planner's gates use row estimates instead): for each permutation, sum the
1551/// encoded lengths of the tiles a scan of this pattern would route to (all
1552/// tiles covering the bound leading key, or the whole section when the leading
1553/// key is unbound), and take the minimum. Tile *counts* are useless here — a
1554/// broad predicate can sit inside one giant tile — but the directory's byte
1555/// lengths expose it. Reads only resident metadata, never tile data.
1556///
1557/// A bound term routes by its id **in the role its position has**: a tile's
1558/// leading range is in subject-, predicate- or object-id space, not in the
1559/// unified node space a lowered constant carries. Routing the node id instead
1560/// was off by one for subjects and off by the whole subject-only block for an
1561/// object-only term (every literal), so `?id :value "10.1234/x"` could cost
1562/// "0 bytes" and pass the merge-join gate against a fat partner, which the
1563/// merge then materialized in full. A constant that has no id in the role
1564/// (never a subject, say) matches nothing: 0 bytes is then exact.
1565fn pattern_scan_bytes(ctx: &Ctx, index: &GraphIndex, t: &(SlotTerm, SlotTerm, SlotTerm)) -> u64 {
1566    let dict = ctx.rete.dictionary();
1567    match (
1568        const_subject(&t.0, dict),
1569        const_predicate(&t.1),
1570        const_object(&t.2, dict),
1571    ) {
1572        (Some(s), Some(p), Some(o)) => routed_scan_bytes(index, (s, p, o)),
1573        _ => 0,
1574    }
1575}
1576
1577/// [`pattern_scan_bytes`] for a pattern already in role-id space.
1578pub(crate) fn routed_scan_bytes(index: &GraphIndex, pattern: Pattern) -> u64 {
1579    if let Some(u) = index.union() {
1580        return u.routed_bytes(pattern);
1581    }
1582    let sections = index.tile_sections();
1583    let mut best = u64::MAX;
1584    // Only the permutations the FILE carries: an absent section is an empty
1585    // `Vec<Tile>`, and summing its (zero) tile lengths would report a free scan
1586    // for the one permutation that cannot be scanned at all.
1587    for perm in index.perms().iter() {
1588        let tiles = sections[perm.section_index()];
1589        // A leafed (0x06) directory answers from its root without faulting a
1590        // leaf: a cost estimate must not cost a round trip.
1591        best = best.min(match perm.order_pattern(pattern)[0] {
1592            // A bound subject of a clustered file is one tile of an unknown run.
1593            Some(_) if index.cluster_runs(perm.section_index()).is_some() => {
1594                index.clustered_subject_bytes(perm.section_index())
1595            }
1596            Some(id) => tiles.routed_bytes(id),
1597            None => tiles.total_bytes(),
1598        });
1599    }
1600    best
1601}
1602
1603/// Estimated matches above which a join side counts as "fat": materializing
1604/// (or, on a remote index, fetching) a million rows to build a hash/merge side
1605/// is past the point where probing it per surviving row wins. Shared by the
1606/// merge-seed asymmetry gate here and the force-probe gates in `sparql::eval`.
1607///
1608/// A ROW estimate ([`GraphIndex::estimate_matches`]: routed tiles × rows per
1609/// tile), not a byte figure. Tiles are cut by their encoded size before
1610/// compression, so the estimate does not move when only the compression does;
1611/// the compressed tile bytes this gate used to read did — at zstd level 19,
1612/// two OpenCitations queries crossed the old 2 MiB line and ran 3–7× slower
1613/// with up to 6× the memory — and they differed between a resident open
1614/// (decoded sizes) and a lazy one (compressed sizes) of the same file.
1615pub(crate) const FAT_SCAN_ROWS: f64 = (1u64 << 20) as f64;
1616
1617/// Would a merge join of `ta` and `tb` materialize a fat side next to a
1618/// pinpoint one? (One side above [`FAT_SCAN_ROWS`] and at least four times the
1619/// other.) Then the hybrid loop — scan the small side, probe the fat one — is
1620/// strictly better, and the merge seed is declined.
1621fn merge_seed_lopsided(
1622    ctx: &Ctx,
1623    index: &GraphIndex,
1624    ta: &(SlotTerm, SlotTerm, SlotTerm),
1625    tb: &(SlotTerm, SlotTerm, SlotTerm),
1626) -> bool {
1627    let est = tile_estimates(ctx, index, &[*ta, *tb], &std::collections::HashSet::new());
1628    let (lo, hi) = (est[0].min(est[1]), est[0].max(est[1]));
1629    hi >= FAT_SCAN_ROWS && hi / 4.0 >= lo
1630}
1631
1632/// Order pattern indices for a left-deep join: cheapest (smallest estimated
1633/// cardinality) first, always preferring a pattern that shares a variable with
1634/// the already-joined set so the join stays connected and intermediate relations
1635/// stay small. Cardinality comes from [`pattern_estimates`]; with no summary it
1636/// falls back to a most-constants-first heuristic. Pure reordering — `hash_join`
1637/// is order-independent, so the result multiset is unchanged.
1638fn selectivity_order(
1639    ctx: &Ctx,
1640    index: &GraphIndex,
1641    lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1642) -> Vec<usize> {
1643    selectivity_order_seeded(ctx, index, lowered, &std::collections::HashSet::new())
1644}
1645
1646/// [`selectivity_order`] with a set of slots already bound by an outer seed
1647/// row: those variables count as already connected (and, in the no-summary
1648/// fallback, as constants for selectivity).
1649fn selectivity_order_seeded(
1650    ctx: &Ctx,
1651    index: &GraphIndex,
1652    lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1653    seed: &std::collections::HashSet<usize>,
1654) -> Vec<usize> {
1655    // Exact per-predicate statistics when the pyramid is resident; otherwise
1656    // (the lazy path, and files built without a pyramid) the tile-directory
1657    // estimate, which needs no fetch. That one also counts a class's own
1658    // instances (`?s a :C` routes to the tiles of `:C`), so the
1659    // class-enumeration rule below, a stand-in for exactly that missing
1660    // number, applies only to the pyramid figures, whose `rdf:type`
1661    // selectivity is an average over classes.
1662    let (estimates, per_class) = match pattern_estimates(ctx, index, lowered, seed) {
1663        Some(e) => (Some(e), false),
1664        None => (Some(tile_estimates(ctx, index, lowered, seed)), true),
1665    };
1666    let consts = |t: &(SlotTerm, SlotTerm, SlotTerm)| {
1667        [&t.0, &t.1, &t.2]
1668            .into_iter()
1669            .filter(|x| match x {
1670                SlotTerm::Var(v) => seed.contains(v),
1671                _ => true,
1672            })
1673            .count()
1674    };
1675    let vars = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Vec<usize> {
1676        [&t.0, &t.1, &t.2]
1677            .into_iter()
1678            .filter_map(|x| match x {
1679                SlotTerm::Var(v) => Some(*v),
1680                _ => None,
1681            })
1682            .collect()
1683    };
1684    // Higher score = picked sooner. With summary stats that's the negated
1685    // estimate (smaller cardinality wins); without, the constant count (old
1686    // behaviour, byte-identical ordering for pyramid-less files).
1687    let score = |i: usize| -> f64 {
1688        match &estimates {
1689            Some(e) => -e[i],
1690            None => consts(&lowered[i]) as f64,
1691        }
1692    };
1693    // A `?s rdf:type <Class>` with an as-yet-unbound subject is a **class
1694    // enumeration**: it matches every instance of the class, so it is almost never
1695    // the most selective place to *start* a join (a popular class has thousands of
1696    // instances), even though it has two bound positions and so looks selective to
1697    // the constant-count heuristic. Deprioritize it as a seed; once its subject is
1698    // bound by another pattern it becomes a cheap per-row type *check* (the hybrid
1699    // join probes it), so pushing it later costs nothing. Robust and stats-free.
1700    let type_pid = ctx.rete.dictionary().predicate_id(crate::file::RDF_TYPE);
1701    let is_class_enum = |i: usize, bound: &std::collections::HashSet<usize>| -> bool {
1702        let t = &lowered[i];
1703        !per_class
1704            && type_pid.is_some_and(|tp| matches!(t.1, SlotTerm::Pred(p) if p == tp))
1705            && matches!(t.2, SlotTerm::Node(_))
1706            && matches!(t.0, SlotTerm::Var(v) if !bound.contains(&v))
1707    };
1708    let n = lowered.len();
1709    let mut remaining: Vec<usize> = (0..n).collect();
1710    let mut order: Vec<usize> = Vec::with_capacity(n);
1711    let mut bound: std::collections::HashSet<usize> = seed.clone();
1712    while !remaining.is_empty() {
1713        // Pick the remaining pattern with the best (connected, not-a-class-enum,
1714        // score) key; ties go to the lowest original index for a stable order.
1715        let best = *remaining
1716            .iter()
1717            .max_by(|&&a, &&b| {
1718                let connected = |i: usize| vars(&lowered[i]).iter().any(|v| bound.contains(v));
1719                connected(a)
1720                    .cmp(&connected(b))
1721                    .then_with(|| is_class_enum(b, &bound).cmp(&is_class_enum(a, &bound)))
1722                    .then_with(|| {
1723                        score(a)
1724                            .partial_cmp(&score(b))
1725                            .unwrap_or(std::cmp::Ordering::Equal)
1726                    })
1727                    .then_with(|| b.cmp(&a))
1728            })
1729            .unwrap();
1730        for v in vars(&lowered[best]) {
1731            bound.insert(v);
1732        }
1733        order.push(best);
1734        remaining.retain(|&i| i != best);
1735    }
1736    order
1737}
1738
1739/// Does the BGP have at least one solution against `index`? A single pattern
1740/// with all-distinct variables streams the index and stops at the first match
1741/// (no materialization); anything else falls back to the full evaluator and
1742/// tests non-emptiness (still benefiting from the lazy per-pattern scan). Used
1743/// by `ASK`.
1744pub(crate) fn bgp_exists(ctx: &Ctx, index: &GraphIndex, patterns: &[TriplePattern]) -> bool {
1745    let dict = ctx.rete.dictionary();
1746    let Some(lowered) = lower(patterns, ctx) else {
1747        return false;
1748    };
1749    if let [t] = lowered.as_slice() {
1750        // The fast path can't enforce a variable repeated across positions
1751        // (e.g. `?x p ?x`) — that needs the row builder — so only take it when
1752        // the pattern's variables are all distinct.
1753        let names: Vec<usize> = [&t.0, &t.1, &t.2]
1754            .into_iter()
1755            .filter_map(|x| match x {
1756                SlotTerm::Var(v) => Some(*v),
1757                _ => None,
1758            })
1759            .collect();
1760        let distinct = names
1761            .iter()
1762            .enumerate()
1763            .all(|(i, v)| !names[i + 1..].contains(v));
1764        if distinct {
1765            return match (
1766                const_subject(&t.0, dict),
1767                const_predicate(&t.1),
1768                const_object(&t.2, dict),
1769            ) {
1770                (Some(s), Some(p), Some(o)) => index.scan_iter((s, p, o)).next().is_some(),
1771                _ => false,
1772            };
1773        }
1774    }
1775    !eval_bgp_rows(ctx, index, patterns).is_empty()
1776}
1777
1778/// A lazy left-deep BGP join that yields solution rows one at a time, so a
1779/// consumer under `LIMIT`/`OFFSET` (or `.next()` for ASK) can stop early —
1780/// stopping also stops the underlying index scan.
1781///
1782/// The all-but-last patterns are joined eagerly into a `prefix` **hash table**
1783/// (they are the most selective, so this is the small side); the *last* (least
1784/// selective) pattern is then **streamed** from the index cursor, probing the
1785/// prefix — the big scan is never materialized, and a `LIMIT` above stops it
1786/// after a handful of triples. Yields the same solution multiset as
1787/// [`eval_bgp_rows`] (the join is order-independent), just incrementally.
1788pub(crate) struct BgpSolutions<'q> {
1789    scan: Option<Box<dyn Iterator<Item = Row> + 'q>>,
1790    prefix: Vec<Row>,
1791    /// Prefix row indices keyed by the shared-slot values.
1792    buckets: HashMap<Vec<Val>, Vec<usize>>,
1793    shared: Vec<usize>,
1794    cartesian: bool,
1795    /// The prefix is the all-unbound seed row (single-pattern BGP): scanned
1796    /// rows are already complete solutions — pass them through unmerged.
1797    seed_only: bool,
1798    cur_scan: Option<Row>,
1799    /// Reused candidate buffer (avoids a Vec allocation per scanned row).
1800    matches: Vec<usize>,
1801    mi: usize,
1802}
1803
1804impl<'q> BgpSolutions<'q> {
1805    /// Yield `rows` as complete solutions (no prefix merge).
1806    fn passthrough(rows: Box<dyn Iterator<Item = Row> + 'q>) -> Self {
1807        BgpSolutions {
1808            scan: Some(rows),
1809            prefix: Vec::new(),
1810            buckets: HashMap::new(),
1811            shared: Vec::new(),
1812            cartesian: false,
1813            seed_only: true,
1814            cur_scan: None,
1815            matches: Vec::new(),
1816            mi: 0,
1817        }
1818    }
1819
1820    /// The fully streaming join, for a BGP whose most selective pattern is
1821    /// itself large ([`STREAM_SEED_ROWS`]). Nothing proportional to it is ever
1822    /// held: the seed pattern streams from its index cursor (or, when the next
1823    /// pattern is just as large and shares its subject variable, both stream
1824    /// through a merge join), and each later pattern joins per row — through
1825    /// a hash table when the pattern is small ([`HASH_BUILD_ROWS`]), by an
1826    /// index probe otherwise. Same solution multiset as the materializing
1827    /// path; only the row order differs.
1828    fn streaming(
1829        ctx: &'q Ctx<'q>,
1830        index: &'q GraphIndex,
1831        lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1832        order: &[usize],
1833        est: &[f64],
1834    ) -> Self {
1835        let (mut stream, mut bound, skip): (Box<dyn Iterator<Item = Row> + 'q>, Vec<usize>, usize) =
1836            match (est[order[1]] > limits().stream_seed)
1837                .then(|| merge_stream(ctx, index, lowered[order[0]], lowered[order[1]], None))
1838                .flatten()
1839            {
1840                Some((m, slots)) => (m, slots, 2),
1841                None => {
1842                    let t = lowered[order[0]];
1843                    let Some(scan) = scan_rows(ctx, index, t) else {
1844                        return Self::empty();
1845                    };
1846                    (Box::new(scan), pattern_slots(&t), 1)
1847                }
1848            };
1849        for &i in &order[skip..] {
1850            let t = lowered[i];
1851            let slots = pattern_slots(&t);
1852            let shared: Vec<usize> = slots
1853                .iter()
1854                .copied()
1855                .filter(|s| bound.contains(s))
1856                .collect();
1857            if !shared.is_empty() && est[i] > limits().hash_build {
1858                // Each window of streamed rows has its probes' tiles faulted
1859                // together ([`Windowed`]); one at a time, a probe join over a
1860                // remote file was bound by round-trip latency.
1861                stream = Box::new(
1862                    windowed(index, stream, bgp_probe_pattern(ctx, t))
1863                        .flat_map(move |base| probe_rows(ctx, index, t, base)),
1864                );
1865            } else {
1866                // Small (or unconnected) pattern: scan it once into a table
1867                // keyed on the shared slots and join every streamed row to it.
1868                let Some((rel, _)) = pattern_rows(ctx, index, &t) else {
1869                    return Self::empty();
1870                };
1871                let mut table: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
1872                for r in rel {
1873                    let key: Vec<Val> = shared.iter().map(|&s| r[s].clone().unwrap()).collect();
1874                    table.entry(key).or_default().push(r);
1875                }
1876                let fill = slots.clone();
1877                stream = Box::new(stream.flat_map(move |base| {
1878                    let key: Vec<Val> = shared.iter().map(|&s| base[s].clone().unwrap()).collect();
1879                    let out: Vec<Row> = table
1880                        .get(&key)
1881                        .map(|rs| {
1882                            rs.iter()
1883                                .map(|r| {
1884                                    let mut row = base.clone();
1885                                    for &s in &fill {
1886                                        row[s] = r[s].clone();
1887                                    }
1888                                    row
1889                                })
1890                                .collect()
1891                        })
1892                        .unwrap_or_default();
1893                    out.into_iter()
1894                }));
1895            }
1896            for s in slots {
1897                if !bound.contains(&s) {
1898                    bound.push(s);
1899                }
1900            }
1901        }
1902        Self::passthrough(stream)
1903    }
1904
1905    /// An iterator that yields nothing (an unsatisfiable BGP).
1906    fn empty() -> Self {
1907        BgpSolutions {
1908            scan: None,
1909            prefix: Vec::new(),
1910            buckets: HashMap::new(),
1911            shared: Vec::new(),
1912            cartesian: false,
1913            seed_only: false,
1914            cur_scan: None,
1915            matches: Vec::new(),
1916            mi: 0,
1917        }
1918    }
1919
1920    pub(crate) fn new(ctx: &'q Ctx<'q>, index: &'q GraphIndex, patterns: &[TriplePattern]) -> Self {
1921        // An empty BGP has exactly one (empty) solution.
1922        if patterns.is_empty() {
1923            return BgpSolutions {
1924                scan: Some(Box::new(std::iter::once(ctx.slots.empty_row()))),
1925                prefix: vec![ctx.slots.empty_row()],
1926                buckets: HashMap::new(),
1927                shared: Vec::new(),
1928                cartesian: true,
1929                seed_only: true,
1930                cur_scan: None,
1931                matches: Vec::new(),
1932                mi: 0,
1933            };
1934        }
1935        // Lower all patterns; an unknown constant term ⇒ no solutions.
1936        let Some(lowered) = lower(patterns, ctx) else {
1937            return Self::empty();
1938        };
1939        // Join all but the *last* (least selective) pattern eagerly into the
1940        // prefix; a single pattern leaves the seed row as the prefix.
1941        let (order, scan_est) = plan_order(ctx, index, &lowered);
1942        // Even the most selective pattern is big: materializing it as the
1943        // prefix would hold every one of its rows. Stream the whole join.
1944        if order.len() >= 2 && scan_est[order[0]] > limits().stream_seed {
1945            return Self::streaming(ctx, index, &lowered, &order, &scan_est);
1946        }
1947        let (&last_i, prefix_is) = order.split_last().unwrap();
1948        let prefix_pats: Vec<TriplePattern> =
1949            prefix_is.iter().map(|&i| patterns[i].clone()).collect();
1950        let prefix = eval_bgp_rows(ctx, index, &prefix_pats);
1951        if prefix.is_empty() {
1952            return Self::empty();
1953        }
1954
1955        // Hash-join key = slots shared by the prefix and the last pattern (BGP
1956        // rows bind every slot of their pattern set, so the prefix's bound set
1957        // can be read off its first row).
1958        let shared: Vec<usize> = pattern_slots(&lowered[last_i])
1959            .into_iter()
1960            .filter(|&s| prefix[0][s].is_some())
1961            .collect();
1962
1963        // A few prefix rows against a big last pattern: look each one up
1964        // instead of scanning the pattern. `?r :relationSubject <doi> . ?r ?p
1965        // ?o` has four prefix rows and a last pattern that is the whole graph.
1966        // The last pattern is an unbound class (`?x rdf:type ?c`) whose subject
1967        // the prefix binds: each row's types are one SPO lookup, and the prefix
1968        // is already resident, so probing costs no memory the scan would not.
1969        // It wins until the rows outnumber the statements the scan would read
1970        // (the usual sixteenth gives way to one).
1971        let class_probe = !shared.is_empty()
1972            && scan_est[last_i] >= limits().probe_floor
1973            && (prefix.len() as f64) <= scan_est[last_i]
1974            && is_unbound_class(ctx, &lowered[last_i], &shared);
1975        if !shared.is_empty() && (probe_beats_scan(prefix.len(), scan_est[last_i]) || class_probe) {
1976            let t = lowered[last_i];
1977            let stream = windowed(index, prefix.into_iter(), bgp_probe_pattern(ctx, t))
1978                .flat_map(move |base| probe_rows(ctx, index, t, base));
1979            return Self::passthrough(Box::new(stream));
1980        }
1981
1982        // Stream the last pattern with the lazy index cursor.
1983        let Some(scan) = scan_rows(ctx, index, lowered[last_i]) else {
1984            return Self::empty();
1985        };
1986        let cartesian = shared.is_empty();
1987        // A single-pattern BGP joins against the all-unbound seed: scanned rows
1988        // are already complete solutions.
1989        let seed_only = prefix.len() == 1 && prefix[0].iter().all(Option::is_none);
1990        let mut buckets: HashMap<Vec<Val>, Vec<usize>> = HashMap::new();
1991        if !cartesian {
1992            for (i, r) in prefix.iter().enumerate() {
1993                let key: Vec<Val> = shared.iter().map(|&s| r[s].clone().unwrap()).collect();
1994                buckets.entry(key).or_default().push(i);
1995            }
1996        }
1997        BgpSolutions {
1998            scan: Some(Box::new(scan)),
1999            prefix,
2000            buckets,
2001            shared,
2002            cartesian,
2003            seed_only,
2004            cur_scan: None,
2005            matches: Vec::new(),
2006            mi: 0,
2007        }
2008    }
2009}
2010
2011impl Iterator for BgpSolutions<'_> {
2012    type Item = Row;
2013
2014    fn next(&mut self) -> Option<Row> {
2015        // Single-pattern fast path: pass scanned rows through unmerged.
2016        if self.seed_only {
2017            return self.scan.as_mut()?.next();
2018        }
2019        loop {
2020            // Emit the next prefix match for the current scanned row.
2021            if self.mi < self.matches.len() {
2022                let pi = self.matches[self.mi];
2023                self.mi += 1;
2024                let mut merged = self.prefix[pi].clone();
2025                for (slot, v) in self.cur_scan.as_ref().unwrap().iter().enumerate() {
2026                    if v.is_some() {
2027                        merged[slot] = v.clone();
2028                    }
2029                }
2030                return Some(merged);
2031            }
2032            // Pull the next row from the index scan and gather its matches
2033            // (into the reused buffer — no allocation per scanned row).
2034            let s = self.scan.as_mut()?.next()?;
2035            self.matches.clear();
2036            if self.cartesian {
2037                self.matches.extend(0..self.prefix.len());
2038            } else {
2039                let key: Vec<Val> = self.shared.iter().map(|&i| s[i].clone().unwrap()).collect();
2040                if let Some(c) = self.buckets.get(&key) {
2041                    self.matches.extend_from_slice(c);
2042                }
2043            }
2044            self.mi = 0;
2045            self.cur_scan = Some(s);
2046        }
2047    }
2048}
2049
2050/// A **streaming** merge join of two patterns that share exactly one variable,
2051/// in the subject position of both: each side streams from a permutation
2052/// sorted on subject ([`GraphIndex::scan_iter_sorted_on`]) and only the
2053/// current subject's rows are held. Restricted to the subject column because a
2054/// subject's rows are its out-edges, a small run; an object run (every
2055/// instance of a class) can be the whole pattern. `None` when the shape does
2056/// not qualify; the caller then streams the first pattern alone.
2057#[allow(clippy::type_complexity)]
2058fn merge_stream<'q>(
2059    ctx: &'q Ctx<'q>,
2060    index: &'q GraphIndex,
2061    ta: (SlotTerm, SlotTerm, SlotTerm),
2062    tb: (SlotTerm, SlotTerm, SlotTerm),
2063    // Only the subjects `lo <= s < hi`: a slice of the join, for a shard of a
2064    // grouped query run on several threads.
2065    between: Option<(u32, u64)>,
2066) -> Option<(Box<dyn Iterator<Item = Row> + 'q>, Vec<usize>)> {
2067    let sa = pattern_slots(&ta);
2068    let sb = pattern_slots(&tb);
2069    let shared: Vec<usize> = sa.iter().copied().filter(|s| sb.contains(s)).collect();
2070    let [v] = shared[..] else {
2071        return None;
2072    };
2073    if !matches!(ta.0, SlotTerm::Var(i) if i == v) || !matches!(tb.0, SlotTerm::Var(i) if i == v) {
2074        return None;
2075    }
2076    let dict = ctx.rete.dictionary();
2077    let lower = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Option<Pattern> {
2078        Some((
2079            const_subject(&t.0, dict)?,
2080            const_predicate(&t.1)?,
2081            const_object(&t.2, dict)?,
2082        ))
2083    };
2084    let side = |t: (SlotTerm, SlotTerm, SlotTerm)| -> Option<KeyedRows<'q>> {
2085        let it: Box<dyn Iterator<Item = Triple> + 'q> = match between {
2086            Some((lo, hi)) => Box::new(index.scan_iter_sorted_between(lower(&t)?, 0, lo, hi)?),
2087            None => Box::new(index.scan_iter_sorted_on(lower(&t)?, 0)?),
2088        };
2089        let keyed: Box<dyn Iterator<Item = (u32, Row)> + 'q> =
2090            Box::new(it.filter_map(move |tri| triple_row(ctx, &t, tri).map(|r| (tri.0, r))));
2091        Some(keyed.peekable())
2092    };
2093    let a = side(ta)?;
2094    let b = side(tb)?;
2095    let mut slots = sa;
2096    for s in sb {
2097        if !slots.contains(&s) {
2098            slots.push(s);
2099        }
2100    }
2101    Some((
2102        Box::new(MergeStream {
2103            a,
2104            b,
2105            ra: Vec::new(),
2106            rb: Vec::new(),
2107            i: 0,
2108            j: 0,
2109        }),
2110        slots,
2111    ))
2112}
2113
2114type KeyedRows<'q> = std::iter::Peekable<Box<dyn Iterator<Item = (u32, Row)> + 'q>>;
2115
2116/// The two-pointer merge behind [`merge_stream`]: `ra`/`rb` hold the current
2117/// equal-key runs and `(i, j)` walks their cross product lazily.
2118struct MergeStream<'q> {
2119    a: KeyedRows<'q>,
2120    b: KeyedRows<'q>,
2121    ra: Vec<Row>,
2122    rb: Vec<Row>,
2123    i: usize,
2124    j: usize,
2125}
2126
2127impl Iterator for MergeStream<'_> {
2128    type Item = Row;
2129
2130    fn next(&mut self) -> Option<Row> {
2131        loop {
2132            while self.i < self.ra.len() {
2133                if self.j < self.rb.len() {
2134                    let j = self.j;
2135                    self.j += 1;
2136                    if let Some(m) = crate::row::merge_rows(&self.ra[self.i], &self.rb[j]) {
2137                        return Some(m);
2138                    }
2139                } else {
2140                    self.i += 1;
2141                    self.j = 0;
2142                }
2143            }
2144            let ka = self.a.peek()?.0;
2145            let kb = self.b.peek()?.0;
2146            match ka.cmp(&kb) {
2147                std::cmp::Ordering::Less => {
2148                    self.a.next();
2149                }
2150                std::cmp::Ordering::Greater => {
2151                    self.b.next();
2152                }
2153                std::cmp::Ordering::Equal => {
2154                    self.ra.clear();
2155                    self.rb.clear();
2156                    while let Some((_, r)) = self.a.next_if(|(k, _)| *k == ka) {
2157                        self.ra.push(r);
2158                    }
2159                    while let Some((_, r)) = self.b.next_if(|(k, _)| *k == ka) {
2160                        self.rb.push(r);
2161                    }
2162                    self.i = 0;
2163                    self.j = 0;
2164                }
2165            }
2166        }
2167    }
2168}
2169
2170// --- index-nested-loop probing ------------------------------------------------
2171//
2172// Under a small, known demand (LIMIT/ASK — see `Ctx::limit_hint`), scanning
2173// every pattern once to hash-join is mostly wasted work: the consumer wants a
2174// handful of rows. The probe path instead streams the seed/first pattern and,
2175// per row, *probes* each next pattern through the index with the row's bound
2176// values substituted as scan constants — so producing k solutions touches
2177// O(k · patterns) index groups instead of every pattern's full extent. Same
2178// solution multiset as the hash join (joins are order-independent); only the
2179// evaluation order differs.
2180
2181/// Index-scan constant for a subject position given a partially-bound row.
2182/// Outer `None` = unsatisfiable for this row; inner `None` = wildcard.
2183fn probe_subject(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
2184    let dict = ctx.rete.dictionary();
2185    match t {
2186        SlotTerm::Node(n) => dict.node_as_subject_id(*n).map(Some),
2187        SlotTerm::Pred(_) => None,
2188        SlotTerm::Var(i) => match &base[*i] {
2189            None => Some(None),
2190            Some(Val::Id(v)) if *v >= 0 => dict.node_as_subject_id(*v as u32).map(Some),
2191            // A predicate-tagged or computed value can never be a subject.
2192            Some(_) => None,
2193        },
2194    }
2195}
2196
2197/// Index-scan constant for an object position (see [`probe_subject`]).
2198fn probe_object(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
2199    let dict = ctx.rete.dictionary();
2200    match t {
2201        SlotTerm::Node(n) => dict.node_as_object_id(*n).map(Some),
2202        SlotTerm::Pred(_) => None,
2203        SlotTerm::Var(i) => match &base[*i] {
2204            None => Some(None),
2205            Some(Val::Id(v)) if *v >= 0 => dict.node_as_object_id(*v as u32).map(Some),
2206            Some(_) => None,
2207        },
2208    }
2209}
2210
2211/// Index-scan constant for a predicate position (see [`probe_subject`]).
2212fn probe_predicate(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
2213    let dict = ctx.rete.dictionary();
2214    match t {
2215        SlotTerm::Pred(p) => Some(Some(*p)),
2216        SlotTerm::Node(_) => None,
2217        SlotTerm::Var(i) => match &base[*i] {
2218            None => Some(None),
2219            Some(Val::Id(v)) if *v < 0 => Some(Some((-v - 1) as u32)),
2220            // Canonicalized to a node id — the term may still be a predicate.
2221            Some(Val::Id(v)) => ctx
2222                .resolver
2223                .term(*v)
2224                .and_then(|t| dict.predicate_id(&t))
2225                .map(Some),
2226            Some(Val::Str(_)) => None,
2227        },
2228    }
2229}
2230
2231/// Probe one pattern with a partially-bound row: every bound variable becomes
2232/// an index-scan constant, and each matching triple extends a clone of the row
2233/// (repeated unbound variables stay consistent).
2234fn probe_rows<'q>(
2235    ctx: &'q Ctx<'q>,
2236    index: &'q GraphIndex,
2237    t: (SlotTerm, SlotTerm, SlotTerm),
2238    base: Row,
2239) -> Box<dyn Iterator<Item = Row> + 'q> {
2240    let (Some(sid), Some(pid), Some(oid)) = (
2241        probe_subject(ctx, &t.0, &base),
2242        probe_predicate(ctx, &t.1, &base),
2243        probe_object(ctx, &t.2, &base),
2244    ) else {
2245        return Box::new(std::iter::empty());
2246    };
2247    let dict = ctx.rete.dictionary();
2248    // A variable predicate is canonicalized a run at a time ([`canon_ahead`]):
2249    // one new predicate after another was a dictionary round trip each.
2250    Box::new(
2251        canon_ahead(ctx, &t, index.scan_iter((sid, pid, oid))).filter_map(
2252            move |(s_id, p_id, o_id)| {
2253                let s_val = dict.subject_node(s_id) as i64;
2254                let p_val = pred_val(ctx, &t.1, p_id);
2255                let o_val = dict.object_node(o_id) as i64;
2256                let mut row = base.clone();
2257                for (term, val) in [(&t.0, s_val), (&t.1, p_val), (&t.2, o_val)] {
2258                    if let SlotTerm::Var(i) = term {
2259                        match row[*i] {
2260                            Some(Val::Id(existing)) if existing != val => return None,
2261                            Some(Val::Id(_)) => {}
2262                            Some(Val::Str(_)) => return None,
2263                            None => row[*i] = Some(Val::Id(val)),
2264                        }
2265                    }
2266                }
2267                Some(row)
2268            },
2269        ),
2270    )
2271}
2272
2273/// A lowered, probe-ordered BGP, reusable across many seed rows.
2274pub(crate) struct ProbePlan {
2275    pats: Vec<(SlotTerm, SlotTerm, SlotTerm)>,
2276}
2277
2278impl ProbePlan {
2279    /// Lower and order `patterns` for probing from rows that bind (at least)
2280    /// the slots in `seed_mask`. `None` = a constant term is unknown, making
2281    /// the BGP unsatisfiable for every seed.
2282    pub(crate) fn new(
2283        ctx: &Ctx,
2284        index: &GraphIndex,
2285        patterns: &[TriplePattern],
2286        seed_mask: &[bool],
2287    ) -> Option<Self> {
2288        let lowered = lower(patterns, ctx)?;
2289        let seed: std::collections::HashSet<usize> = seed_mask
2290            .iter()
2291            .enumerate()
2292            .filter_map(|(i, b)| b.then_some(i))
2293            .collect();
2294        let order = selectivity_order_seeded(ctx, index, &lowered, &seed);
2295        Some(ProbePlan {
2296            pats: order.into_iter().map(|i| lowered[i]).collect(),
2297        })
2298    }
2299}
2300
2301/// Depth-first index-nested-loop join over a [`ProbePlan`], starting from a
2302/// seed row. Fully lazy: pulling k rows probes O(k · patterns) index groups.
2303pub(crate) struct ProbeJoin<'q> {
2304    ctx: &'q Ctx<'q>,
2305    index: &'q GraphIndex,
2306    pats: Vec<(SlotTerm, SlotTerm, SlotTerm)>,
2307    stack: Vec<Box<dyn Iterator<Item = Row> + 'q>>,
2308}
2309
2310impl<'q> ProbeJoin<'q> {
2311    /// Probe a whole BGP from scratch (the seed is the all-unbound row).
2312    /// `None` = unsatisfiable.
2313    pub(crate) fn new(
2314        ctx: &'q Ctx<'q>,
2315        index: &'q GraphIndex,
2316        patterns: &[TriplePattern],
2317    ) -> Option<Self> {
2318        let plan = ProbePlan::new(ctx, index, patterns, &vec![false; ctx.slots.len()])?;
2319        Some(Self::from_plan(ctx, index, &plan, ctx.slots.empty_row()))
2320    }
2321
2322    /// Probe a pre-lowered plan from one seed row.
2323    pub(crate) fn from_plan(
2324        ctx: &'q Ctx<'q>,
2325        index: &'q GraphIndex,
2326        plan: &ProbePlan,
2327        seed: Row,
2328    ) -> Self {
2329        let pats = plan.pats.clone();
2330        let first = probe_rows(ctx, index, pats[0], seed);
2331        ProbeJoin {
2332            ctx,
2333            index,
2334            pats,
2335            stack: vec![first],
2336        }
2337    }
2338}
2339
2340impl Iterator for ProbeJoin<'_> {
2341    type Item = Row;
2342
2343    fn next(&mut self) -> Option<Row> {
2344        loop {
2345            let depth = self.stack.len();
2346            match self.stack.last_mut()?.next() {
2347                Some(row) => {
2348                    if depth == self.pats.len() {
2349                        return Some(row);
2350                    }
2351                    let it = probe_rows(self.ctx, self.index, self.pats[depth], row);
2352                    self.stack.push(it);
2353                }
2354                None => {
2355                    self.stack.pop();
2356                    if self.stack.is_empty() {
2357                        return None;
2358                    }
2359                }
2360            }
2361        }
2362    }
2363}
2364
2365/// Hash-join two BGP relations on the slots they share. Every left row binds
2366/// exactly the slots accumulated so far and every right row binds the current
2367/// pattern's slots, so the shared set is uniform across rows.
2368fn hash_join(
2369    left: Vec<Row>,
2370    left_bound: &[usize],
2371    right: Vec<Row>,
2372    right_slots: &[usize],
2373) -> Vec<Row> {
2374    // Fast path: the all-unbound seed row joins to `right` unchanged.
2375    if left.len() == 1 && left_bound.is_empty() {
2376        return right;
2377    }
2378    if left.is_empty() || right.is_empty() {
2379        return Vec::new();
2380    }
2381    let shared: Vec<usize> = right_slots
2382        .iter()
2383        .copied()
2384        .filter(|s| left_bound.contains(s))
2385        .collect();
2386    let fill = |l: &Row, r: &Row| -> Row {
2387        let mut out = l.clone();
2388        for &s in right_slots {
2389            out[s] = r[s].clone();
2390        }
2391        out
2392    };
2393    if shared.is_empty() {
2394        // No shared variable: Cartesian product. In a connected BGP this only
2395        // arises for a fully-ground pattern (deduped index ⇒ one matching row),
2396        // so it acts as an existence filter rather than multiplying rows.
2397        let mut out = Vec::with_capacity(left.len() * right.len());
2398        for l in &left {
2399            for r in &right {
2400                out.push(fill(l, r));
2401            }
2402        }
2403        return out;
2404    }
2405    let key_of = |b: &Row| -> Vec<Val> { shared.iter().map(|&s| b[s].clone().unwrap()).collect() };
2406    // A hash join is symmetric on the shared key, so build the **smaller** side's
2407    // hash table and probe with the larger — same result set, fewer inserts and a
2408    // smaller table. (The old code always built `right`; after cardinality-based
2409    // ordering the accumulating `left` is usually the small selective side, so
2410    // building it instead is the common win.) Whichever side is built, the output
2411    // row carries every bound slot of both.
2412    let mut out = Vec::new();
2413    if right.len() <= left.len() {
2414        let mut buckets: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
2415        for r in right {
2416            buckets.entry(key_of(&r)).or_default().push(r);
2417        }
2418        for l in &left {
2419            if let Some(rs) = buckets.get(&key_of(l)) {
2420                for r in rs {
2421                    out.push(fill(l, r));
2422                }
2423            }
2424        }
2425    } else {
2426        // Build the left side; fill the left's own slots into each probed right.
2427        let mut buckets: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
2428        for l in left {
2429            buckets.entry(key_of(&l)).or_default().push(l);
2430        }
2431        for r in &right {
2432            if let Some(ls) = buckets.get(&key_of(r)) {
2433                for l in ls {
2434                    let mut row = r.clone();
2435                    for &s in left_bound {
2436                        if let Some(v) = &l[s] {
2437                            row[s] = Some(v.clone());
2438                        }
2439                    }
2440                    out.push(row);
2441                }
2442            }
2443        }
2444    }
2445    out
2446}
2447
2448// Constant-only index constraints. A variable scans as a wildcard (`Some(None)`)
2449// — it is resolved later by the hash join, not pushed into the scan. The outer
2450// `None` means "unsatisfiable" (a constant in an impossible role, or unknown to
2451// the dictionary), which empties the whole BGP. Inner `None` = "wildcard".
2452fn const_subject(t: &SlotTerm, d: &crate::Dictionary) -> Option<Option<u32>> {
2453    match t {
2454        SlotTerm::Node(n) => d.node_as_subject_id(*n).map(Some),
2455        SlotTerm::Pred(_) => None, // a predicate term can't be a subject
2456        SlotTerm::Var(_) => Some(None),
2457    }
2458}
2459
2460fn const_object(t: &SlotTerm, d: &crate::Dictionary) -> Option<Option<u32>> {
2461    match t {
2462        SlotTerm::Node(n) => d.node_as_object_id(*n).map(Some),
2463        SlotTerm::Pred(_) => None,
2464        SlotTerm::Var(_) => Some(None),
2465    }
2466}
2467
2468fn const_predicate(t: &SlotTerm) -> Option<Option<u32>> {
2469    match t {
2470        SlotTerm::Pred(p) => Some(Some(*p)),
2471        SlotTerm::Node(_) => None, // a node term can't be a predicate
2472        SlotTerm::Var(_) => Some(None),
2473    }
2474}
2475
2476#[cfg(test)]
2477mod tests {
2478    use super::*;
2479    use crate::dictionary::DictionaryBuilder;
2480    use crate::file::write_file_v05 as write_file;
2481    use crate::index::GraphIndexBuilder;
2482
2483    fn rete_from(triples: &[(&str, &str, &str)]) -> Vec<u8> {
2484        let mut db = DictionaryBuilder::new();
2485        for (s, p, o) in triples {
2486            db.observe(s, p, o);
2487        }
2488        let dict = db.build();
2489        let mut ib = GraphIndexBuilder::new();
2490        for (s, p, o) in triples {
2491            ib.push(dict.encode(s, p, o).unwrap());
2492        }
2493        write_file(&dict, &ib.build(), false, &[], 0)
2494    }
2495
2496    fn pat(s: &str, p: &str, o: &str) -> TriplePattern {
2497        TriplePattern {
2498            s: PatternTerm::parse(s),
2499            p: PatternTerm::parse(p),
2500            o: PatternTerm::parse(o),
2501        }
2502    }
2503
2504    /// The scan-bytes figure (`rete cost`'s preview, and through 0.3.7 the
2505    /// merge-join and fat-side gates) routes a bound term by its id IN ITS
2506    /// ROLE. It used to route the unified node id,
2507    /// which for an object-only term (any literal) is shifted past the whole
2508    /// subject-only block: `?s :value "lit"` found no OPS tile at all, cost
2509    /// "0 bytes", and so let a merge join materialize its partner in full —
2510    /// on OpenCitations, every DOI identifier of a 2.9 B-triple file, behind
2511    /// `?id :hasLiteralValue "10.…" ; :usesIdentifierScheme :doi`.
2512    #[test]
2513    fn scan_bytes_route_a_literal_by_its_object_id() {
2514        let value = "<http://ex/value>";
2515        let owned: Vec<(String, String)> = (0..400)
2516            .map(|i| (format!("<http://ex/s{i:03}>"), format!("\"lit {i:03}\"")))
2517            .collect();
2518        let mut db = DictionaryBuilder::new();
2519        for (s, o) in &owned {
2520            db.observe(s, value, o);
2521        }
2522        let dict = db.build();
2523        let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2524        for (s, o) in &owned {
2525            ib.push(dict.encode(s, value, o).unwrap());
2526        }
2527        let rete = Rete::open(&write_file(&dict, &ib.build(), false, &[], 0)).unwrap();
2528        let index = rete.default_index();
2529        // The whole predicate, the most a bound object could ever cost.
2530        let whole = routed_scan_bytes(index, (None, rete.dictionary().predicate_id(value), None));
2531        for (_, lit) in owned.iter().step_by(57) {
2532            let q = [pat("?s", value, lit)];
2533            let mut slots = Slots::new();
2534            collect_pattern_slots(&q, &mut slots);
2535            let ctx = Ctx::new(&rete, slots);
2536            let got = bgp_min_scan_bytes(&ctx, index, &q).unwrap();
2537            assert!(got > 0, "{lit} routed to no tile");
2538            assert!(
2539                got < whole,
2540                "{lit} routed to the whole predicate ({got} of {whole})"
2541            );
2542        }
2543    }
2544
2545    /// The planner's size gates read ROW estimates, which do not depend on how
2546    /// the tiles are compressed. The same file opened resident (tile sizes are
2547    /// the decoded images) and lazily (tile sizes are the compressed frames)
2548    /// reports different bytes but must take the same decisions — the byte
2549    /// gates this replaced flipped plans when only the zstd level changed.
2550    #[test]
2551    fn plan_gates_do_not_move_with_the_compression() {
2552        let mut owned: Vec<(String, String, String)> = Vec::new();
2553        for i in 0..3000 {
2554            let s = format!("<http://ex/s{i}>");
2555            owned.push((
2556                s.clone(),
2557                "<http://ex/kind>".into(),
2558                format!("<http://ex/K{}>", i % 7),
2559            ));
2560            owned.push((s.clone(), "<http://ex/value>".into(), format!("\"v {i}\"")));
2561            if i % 50 == 0 {
2562                owned.push((s, "<http://ex/rare>".into(), "<http://ex/R>".into()));
2563            }
2564        }
2565        let mut db = DictionaryBuilder::new();
2566        for (s, p, o) in &owned {
2567            db.observe(s, p, o);
2568        }
2569        let dict = db.build();
2570        let mut ib = GraphIndexBuilder::new().with_tile_budget(1024);
2571        for (s, p, o) in &owned {
2572            ib.push(dict.encode(s, p, o).unwrap());
2573        }
2574        let bytes = write_file(&dict, &ib.build(), false, &[], 0);
2575        let leaked: &'static [u8] = Box::leak(bytes.clone().into_boxed_slice());
2576        let resident = Rete::open(&bytes).unwrap();
2577        let lazy = Rete::open_ranged_lazy(crate::reader::SliceReader::new(leaked)).unwrap();
2578        let shapes: Vec<Vec<TriplePattern>> = vec![
2579            vec![
2580                pat("?s", "<http://ex/rare>", "<http://ex/R>"),
2581                pat("?s", "<http://ex/value>", "?v"),
2582            ],
2583            vec![
2584                pat("?s", "<http://ex/kind>", "<http://ex/K3>"),
2585                pat("?s", "<http://ex/value>", "?v"),
2586            ],
2587            vec![
2588                pat("?s", "<http://ex/kind>", "?k"),
2589                pat("?s", "<http://ex/value>", "?v"),
2590            ],
2591            vec![
2592                pat("?s", "<http://ex/value>", "\"v 7\""),
2593                pat("?s", "<http://ex/kind>", "?k"),
2594            ],
2595        ];
2596        let decisions = |rete: &Rete| -> Vec<(Vec<u64>, bool, Option<u64>)> {
2597            shapes
2598                .iter()
2599                .map(|q| {
2600                    let mut slots = Slots::new();
2601                    collect_pattern_slots(q, &mut slots);
2602                    let ctx = Ctx::new(rete, slots);
2603                    let index = rete.default_index();
2604                    let lowered = lower(q, &ctx).unwrap();
2605                    let est = tile_estimates(&ctx, index, &lowered, &Default::default());
2606                    let lopsided = merge_seed_lopsided(&ctx, index, &lowered[0], &lowered[1]);
2607                    let min = bgp_min_estimate(&ctx, index, q).map(|e| e as u64);
2608                    (est.iter().map(|e| *e as u64).collect(), lopsided, min)
2609                })
2610                .collect()
2611        };
2612        assert_eq!(decisions(&resident), decisions(&lazy));
2613        // ... while the byte figures the gates used to read do differ.
2614        #[cfg(feature = "compression")]
2615        {
2616            let bytes_of = |rete: &Rete| {
2617                let q = &shapes[2];
2618                let mut slots = Slots::new();
2619                collect_pattern_slots(q, &mut slots);
2620                let ctx = Ctx::new(rete, slots);
2621                bgp_min_scan_bytes(&ctx, rete.default_index(), q)
2622            };
2623            assert_ne!(bytes_of(&resident), bytes_of(&lazy));
2624        }
2625    }
2626
2627    /// A fat predicate must look fat whichever layout stores the directory.
2628    /// On format 0x06 the tile directory is two-level and a leaf that is not
2629    /// resident is estimated from the root alone; it used to count as ONE
2630    /// tile, so a 2-million-row `rdfs:label` read as ~7 thousand rows on 0x06
2631    /// and 2 million on 0x05 — and the OPTIONAL joined to a 1000-row left side
2632    /// was hash-joined (the whole predicate materialized: 14.5 GB on a 8 B
2633    /// triple file) instead of probed per row. The same file in both layouts
2634    /// must give estimates of the same order, and the probe decision must be
2635    /// the same one.
2636    #[test]
2637    fn a_fat_predicate_estimates_alike_in_both_layouts() {
2638        let mut owned: Vec<(String, String, String)> = Vec::new();
2639        for i in 0..120_000 {
2640            let s = format!("<http://ex/s{i:06}>");
2641            owned.push((s.clone(), "<http://ex/kind>".into(), "<http://ex/K>".into()));
2642            owned.push((s, "<http://ex/value>".into(), format!("\"v {i}\"")));
2643        }
2644        let mut db = DictionaryBuilder::new();
2645        for (s, p, o) in &owned {
2646            db.observe(s, p, o);
2647        }
2648        let dict = db.build();
2649        let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2650        for (s, p, o) in &owned {
2651            ib.push(dict.encode(s, p, o).unwrap());
2652        }
2653        let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2654        let v6: &'static [u8] = Box::leak(
2655            crate::v06::write::convert_image(&v5, Default::default())
2656                .unwrap()
2657                .into_boxed_slice(),
2658        );
2659        let leaked5: &'static [u8] = Box::leak(v5.clone().into_boxed_slice());
2660        let flat = Rete::open_ranged_lazy(crate::reader::SliceReader::new(leaked5)).unwrap();
2661        let leafed = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v6)).unwrap();
2662        let q = [pat("?s", "<http://ex/value>", "?v")];
2663        let figures = |rete: &Rete| {
2664            let mut slots = Slots::new();
2665            collect_pattern_slots(&q, &mut slots);
2666            let ctx = Ctx::new(rete, slots);
2667            let index = rete.default_index();
2668            let total = bgp_total_estimate(&ctx, index, &q).unwrap();
2669            (total, probe_row_budget(total))
2670        };
2671        let (est5, budget5) = figures(&flat);
2672        let (est6, budget6) = figures(&leafed);
2673        assert!(est5 >= 70_000.0, "flat estimate {est5}");
2674        assert!(
2675            est6 >= est5 / 2.0 && est6 <= est5 * 2.0,
2676            "0x06 estimates {est6} where 0x05 estimates {est5}"
2677        );
2678        // The decision: a 1000-row left side probes in both.
2679        assert!(budget5.is_some_and(|b| b >= 1000), "{budget5:?}");
2680        assert!(budget6.is_some_and(|b| b >= 1000), "{budget6:?}");
2681    }
2682
2683    /// A selective object on a fat leading predicate must estimate small in
2684    /// both layouts: `?s rdf:type <rare class>` is a few tiles of a predicate
2685    /// that fills thousands, and the planner seeds the join from it. On 0x06 a
2686    /// leaf that is not resident used to be estimated without the bound object
2687    /// (the whole of `rdf:type`) or by the ids' average share of its leaf
2688    /// (skewed ids put a rare class beside a huge one).
2689    #[test]
2690    fn a_rare_object_of_a_fat_predicate_estimates_small_in_both_layouts() {
2691        let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2692        let mut owned: Vec<(String, String, String)> = Vec::new();
2693        for i in 0..120_000 {
2694            let s = format!("<http://ex/s{i:06}>");
2695            owned.push((s.clone(), ty.into(), "<http://ex/Common>".into()));
2696            owned.push((s.clone(), "<http://ex/other>".into(), format!("\"o {i}\"")));
2697            if i % 3000 == 0 {
2698                owned.push((s, ty.into(), "<http://ex/Rare>".into()));
2699            }
2700        }
2701        let mut db = DictionaryBuilder::new();
2702        for (s, p, o) in &owned {
2703            db.observe(s, p, o);
2704        }
2705        let dict = db.build();
2706        let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2707        for (s, p, o) in &owned {
2708            ib.push(dict.encode(s, p, o).unwrap());
2709        }
2710        let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2711        let v6: &'static [u8] = Box::leak(
2712            crate::v06::write::convert_image(&v5, Default::default())
2713                .unwrap()
2714                .into_boxed_slice(),
2715        );
2716        let leaked5: &'static [u8] = Box::leak(v5.into_boxed_slice());
2717        let figures = |rete: &Rete| {
2718            let est = |q: &[TriplePattern]| {
2719                let mut slots = Slots::new();
2720                collect_pattern_slots(q, &mut slots);
2721                let ctx = Ctx::new(rete, slots);
2722                bgp_min_estimate(&ctx, rete.default_index(), q).unwrap()
2723            };
2724            (
2725                est(&[pat("?s", ty, "<http://ex/Rare>")]),
2726                est(&[pat("?s", ty, "<http://ex/Common>")]),
2727                est(&[pat("?s", "<http://ex/other>", "?x")]),
2728            )
2729        };
2730        for (name, bytes) in [("0x05", leaked5), ("0x06", v6)] {
2731            let rete = Rete::open_ranged_lazy(crate::reader::SliceReader::new(bytes)).unwrap();
2732            let (rare, common, other) = figures(&rete);
2733            assert!(rare * 20.0 < other, "{name}: rare {rare} vs other {other}");
2734            assert!(
2735                rare * 20.0 < common,
2736                "{name}: rare {rare} vs common {common}"
2737            );
2738        }
2739    }
2740
2741    /// A probe prefetch covers a bounded window of its patterns — at most
2742    /// [`PROBE_WINDOW_TILES`] tiles — and leaves the rest for the next call, so
2743    /// a long list of probes never faults more tiles than the cache holds (the
2744    /// whole list at once evicted the early tiles before their probes ran, and
2745    /// each came back as a request of its own: G50a). What a window covers is
2746    /// resident: probing it reads nothing more.
2747    #[test]
2748    fn a_probe_prefetch_window_is_bounded_and_warm() {
2749        use crate::reader::{CountingReader, SliceReader};
2750        let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2751        let mut owned: Vec<(String, String, String)> = Vec::new();
2752        for i in 0..20_000 {
2753            let s = format!("<http://ex/s{i:06}>");
2754            owned.push((s.clone(), ty.into(), format!("<http://ex/C{}>", i % 7)));
2755            owned.push((s, "<http://ex/other>".into(), format!("\"o {}\"", i % 5000)));
2756        }
2757        let mut db = DictionaryBuilder::new();
2758        for (s, p, o) in &owned {
2759            db.observe(s, p, o);
2760        }
2761        let dict = db.build();
2762        let mut ib = GraphIndexBuilder::new().with_tile_budget(128);
2763        for (s, p, o) in &owned {
2764            ib.push(dict.encode(s, p, o).unwrap());
2765        }
2766        let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2767        let v6 = crate::v06::write::convert_image(&v5, Default::default()).unwrap();
2768        let leaked: &'static [u8] = Box::leak(v6.into_boxed_slice());
2769        let reader = std::sync::Arc::new(CountingReader::new(SliceReader::new(leaked)));
2770        let rete = Rete::open_ranged_lazy(reader.clone()).unwrap();
2771        let index = rete.default_index();
2772        // A cache far smaller than the tiles the probes touch: a prefetch of every
2773        // probe at once would evict its own early tiles.
2774        index.set_cache_cap(1 << 20);
2775        // Every third subject, as the probes of a long join.
2776        let pats: Vec<Pattern> = (0..20_000)
2777            .step_by(3)
2778            .map(|i| {
2779                let (s, _, _) = dict
2780                    .encode(&format!("<http://ex/s{i:06}>"), ty, "<http://ex/C0>")
2781                    .unwrap();
2782                (Some(s), None, None)
2783            })
2784            .collect();
2785        let mut from = 0;
2786        let mut windows = 0;
2787        while from < pats.len() {
2788            let n = index.prefetch_probe_tiles(&pats[from..]);
2789            assert!(n >= 1, "a window always makes progress");
2790            assert!(
2791                n < pats.len() - from || windows > 0,
2792                "the first window is cut"
2793            );
2794            let before = reader.requests();
2795            for &p in &pats[from..from + n] {
2796                assert!(index.scan_iter(p).next().is_some());
2797            }
2798            assert_eq!(reader.requests(), before, "a covered probe reads nothing");
2799            from += n;
2800            windows += 1;
2801        }
2802        assert!(windows > 1, "{windows} window(s) for {} probes", pats.len());
2803    }
2804
2805    /// The run of tiles holding a leading id is the same in both layouts, for
2806    /// every id and every permutation, and a leafed lookup does not walk the
2807    /// leaf tile by tile (a probe join runs it per row: 94,700 probes took 126 s
2808    /// on a 0x06 file against 1.3 s on its 0x05 copy).
2809    #[test]
2810    fn a_tile_span_is_the_same_in_both_layouts() {
2811        let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2812        let mut owned: Vec<(String, String, String)> = Vec::new();
2813        for i in 0..30_000 {
2814            let s = format!("<http://ex/s{i:06}>");
2815            owned.push((s.clone(), ty.into(), format!("<http://ex/C{}>", i % 7)));
2816            owned.push((s, "<http://ex/other>".into(), format!("\"o {}\"", i % 5000)));
2817        }
2818        let mut db = DictionaryBuilder::new();
2819        for (s, p, o) in &owned {
2820            db.observe(s, p, o);
2821        }
2822        let dict = db.build();
2823        let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2824        for (s, p, o) in &owned {
2825            ib.push(dict.encode(s, p, o).unwrap());
2826        }
2827        let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2828        let v6 = crate::v06::write::convert_image(&v5, Default::default()).unwrap();
2829        let (v5, v6): (&'static [u8], &'static [u8]) = (
2830            Box::leak(v5.into_boxed_slice()),
2831            Box::leak(v6.into_boxed_slice()),
2832        );
2833        let flat = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v5)).unwrap();
2834        let leafed = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v6)).unwrap();
2835        let (fi, li) = (flat.default_index(), leafed.default_index());
2836        let mut checked = 0;
2837        for perm in fi.perms().iter() {
2838            let si = perm.section_index();
2839            for a in (0..dict.term_count() + 2).step_by(97) {
2840                assert_eq!(
2841                    fi.tile_span(si, Some(a)),
2842                    li.tile_span(si, Some(a)),
2843                    "section {si}, id {a}"
2844                );
2845                checked += 1;
2846            }
2847            assert_eq!(fi.tile_span(si, None), li.tile_span(si, None));
2848        }
2849        assert!(checked > 100);
2850    }
2851
2852    /// Every join path the planner can pick — materialized prefix, probed last
2853    /// pattern, streamed seed with hashed or probed later patterns, streaming
2854    /// merge join — returns the same solution multiset. The thresholds are
2855    /// shrunk so a 400-triple graph takes each path.
2856    #[test]
2857    fn every_join_path_returns_the_same_solutions() {
2858        let mut owned: Vec<(String, String, String)> = Vec::new();
2859        let mut x: u64 = 7;
2860        let mut next = |m: u64| {
2861            x = x
2862                .wrapping_mul(6364136223846793005)
2863                .wrapping_add(1442695040888963407);
2864            (x >> 33) % m
2865        };
2866        for i in 0..60 {
2867            let s = format!("s{i}");
2868            owned.push((s.clone(), "a".into(), format!("C{}", next(3))));
2869            for p in 0..4 {
2870                for _ in 0..next(3) {
2871                    owned.push((s.clone(), format!("p{p}"), format!("s{}", next(60))));
2872                }
2873            }
2874        }
2875        let triples: Vec<(&str, &str, &str)> = owned
2876            .iter()
2877            .map(|(s, p, o)| (s.as_str(), p.as_str(), o.as_str()))
2878            .collect();
2879        let bytes = rete_from(&triples);
2880        let rete = Rete::open(&bytes).unwrap();
2881        let queries: Vec<Vec<TriplePattern>> = vec![
2882            vec![pat("?s", "p0", "?a"), pat("?s", "p1", "?b")],
2883            vec![pat("?s", "a", "C1"), pat("?s", "p0", "?a")],
2884            vec![pat("?s", "p0", "?a"), pat("?a", "p2", "?b")],
2885            vec![pat("s5", "p0", "?a"), pat("?a", "?p", "?o")],
2886            vec![pat("?s", "p0", "?x"), pat("?s", "p1", "?x")],
2887            vec![
2888                pat("?s", "p3", "?o"),
2889                pat("?o", "a", "C0"),
2890                pat("?s", "p1", "?z"),
2891            ],
2892            vec![
2893                pat("?s", "p0", "?a"),
2894                pat("?s", "p1", "?b"),
2895                pat("?b", "p2", "?c"),
2896            ],
2897        ];
2898        let run = |limits: Option<PlanLimits>| -> Vec<Vec<Vec<(String, String)>>> {
2899            TEST_LIMITS.with(|c| c.set(limits));
2900            let out = queries
2901                .iter()
2902                .map(|q| {
2903                    let mut slots = crate::row::Slots::new();
2904                    collect_pattern_slots(q, &mut slots);
2905                    let ctx = Ctx::new(&rete, slots);
2906                    let mut rows: Vec<Vec<(String, String)>> =
2907                        BgpSolutions::new(&ctx, rete.default_index(), q)
2908                            .map(|r| row_to_binding(&ctx, &r).into_iter().collect())
2909                            .collect();
2910                    rows.sort();
2911                    rows
2912                })
2913                .collect();
2914            TEST_LIMITS.with(|c| c.set(None));
2915            out
2916        };
2917        let reference = run(None);
2918        assert!(reference.iter().all(|r| !r.is_empty()), "{reference:?}");
2919        for (name, l) in [
2920            (
2921                "probe everything",
2922                PlanLimits {
2923                    probe_floor: 0.0,
2924                    stream_seed: f64::MAX,
2925                    hash_build: f64::MAX,
2926                },
2927            ),
2928            (
2929                "stream + hash",
2930                PlanLimits {
2931                    probe_floor: f64::MAX,
2932                    stream_seed: 0.0,
2933                    hash_build: f64::MAX,
2934                },
2935            ),
2936            (
2937                "stream + probe",
2938                PlanLimits {
2939                    probe_floor: f64::MAX,
2940                    stream_seed: 0.0,
2941                    hash_build: 0.0,
2942                },
2943            ),
2944            (
2945                "stream, all paths",
2946                PlanLimits {
2947                    probe_floor: 0.0,
2948                    stream_seed: 0.0,
2949                    hash_build: 30.0,
2950                },
2951            ),
2952        ] {
2953            assert_eq!(run(Some(l)), reference, "{name}");
2954        }
2955    }
2956
2957    /// The shards of a BGP ([`shard_bgp_rows`]) add up to the BGP: for every
2958    /// join path and every shard count, the slices' rows one after the other
2959    /// are the rows of [`BgpSolutions::new`], in its order. The file is cut
2960    /// into small tiles so that a slice is a real part of a scan.
2961    #[test]
2962    fn the_shards_of_a_bgp_add_up_to_it_on_every_join_path() {
2963        let mut owned: Vec<(String, String, String)> = Vec::new();
2964        let mut x: u64 = 11;
2965        let mut next = |m: u64| {
2966            x = x
2967                .wrapping_mul(6364136223846793005)
2968                .wrapping_add(1442695040888963407);
2969            (x >> 33) % m
2970        };
2971        for i in 0..400 {
2972            let s = format!("s{i:03}");
2973            owned.push((s.clone(), "a".into(), format!("C{}", next(3))));
2974            for p in 0..4 {
2975                for _ in 0..next(3) {
2976                    owned.push((s.clone(), format!("p{p}"), format!("s{:03}", next(400))));
2977                }
2978            }
2979        }
2980        let mut db = DictionaryBuilder::new();
2981        for (s, p, o) in &owned {
2982            db.observe(s, p, o);
2983        }
2984        let dict = db.build();
2985        let mut ib = GraphIndexBuilder::new().with_tile_budget(96);
2986        for (s, p, o) in &owned {
2987            ib.push(dict.encode(s, p, o).unwrap());
2988        }
2989        let bytes = write_file(&dict, &ib.build(), false, &[], 0);
2990        let rete = Rete::open(&bytes).unwrap();
2991        let queries: Vec<Vec<TriplePattern>> = vec![
2992            vec![pat("?s", "p0", "?a")],
2993            vec![pat("?s", "p0", "?a"), pat("?s", "p1", "?b")],
2994            vec![pat("?s", "a", "C1"), pat("?s", "p0", "?a")],
2995            vec![pat("?s", "p0", "?a"), pat("?a", "p2", "?b")],
2996            vec![pat("?s", "p0", "?x"), pat("?s", "p1", "?x")],
2997            vec![
2998                pat("?s", "p3", "?o"),
2999                pat("?o", "a", "C0"),
3000                pat("?s", "p1", "?z"),
3001            ],
3002            vec![
3003                pat("?s", "p0", "?a"),
3004                pat("?s", "p1", "?b"),
3005                pat("?b", "p2", "?c"),
3006            ],
3007        ];
3008        // A plan node's address, as the evaluator would name this BGP.
3009        const NODE: usize = 1;
3010        let mut sliced = 0usize;
3011        let mut merged = 0usize;
3012        for (name, limits) in [
3013            ("defaults", None),
3014            (
3015                "probe everything",
3016                Some(PlanLimits {
3017                    probe_floor: 0.0,
3018                    stream_seed: f64::MAX,
3019                    hash_build: f64::MAX,
3020                }),
3021            ),
3022            (
3023                "stream + hash",
3024                Some(PlanLimits {
3025                    probe_floor: f64::MAX,
3026                    stream_seed: 0.0,
3027                    hash_build: f64::MAX,
3028                }),
3029            ),
3030            (
3031                "stream + probe",
3032                Some(PlanLimits {
3033                    probe_floor: f64::MAX,
3034                    stream_seed: 0.0,
3035                    hash_build: 0.0,
3036                }),
3037            ),
3038        ] {
3039            TEST_LIMITS.with(|c| c.set(limits));
3040            for q in &queries {
3041                let mut slots = crate::row::Slots::new();
3042                collect_pattern_slots(q, &mut slots);
3043                let ctx = Ctx::new(&rete, slots);
3044                let index = rete.default_index();
3045                let whole: Vec<Row> = BgpSolutions::new(&ctx, index, q).collect();
3046                assert!(!whole.is_empty(), "{name}: {q:?}");
3047                for n in [1usize, 2, 5, 13] {
3048                    ctx.shard
3049                        .set_plan(vec![NODE], Vec::new(), Vec::new(), Default::default());
3050                    let mut parts: Vec<Row> = Vec::new();
3051                    let mut ok = true;
3052                    for i in 0..n {
3053                        ctx.shard.begin(Some((i, n)));
3054                        match shard_bgp_rows(&ctx, index, q, (NODE, i, n)) {
3055                            Some(rows) => parts.extend(rows),
3056                            None => ok = false,
3057                        }
3058                    }
3059                    ctx.shard.clear();
3060                    if !ok {
3061                        continue;
3062                    }
3063                    sliced += 1;
3064                    assert_eq!(parts, whole, "{name}, {n} shards: {q:?}");
3065                }
3066                // The two-pattern star streams as a merge join when both
3067                // patterns are large: that path is one of those sliced.
3068                if limits.is_some_and(|l| l.stream_seed == 0.0) && q.len() == 2 {
3069                    let lowered = lower(q, &ctx).unwrap();
3070                    if merge_stream(&ctx, index, lowered[0], lowered[1], None).is_some() {
3071                        merged += 1;
3072                    }
3073                }
3074            }
3075            TEST_LIMITS.with(|c| c.set(None));
3076        }
3077        assert!(sliced > 60, "{sliced} sliced cases");
3078        assert!(merged >= 2, "{merged} merge joins");
3079    }
3080
3081    #[test]
3082    fn single_pattern_binds_variable() {
3083        let bytes = rete_from(&[("Alice", "knows", "Bob"), ("Bob", "knows", "Carol")]);
3084        let rete = Rete::open(&bytes).unwrap();
3085        let sols = eval_bgp(&rete, &[pat("Alice", "knows", "?y")]);
3086        assert_eq!(sols.len(), 1);
3087        assert_eq!(sols[0]["y"], "Bob");
3088    }
3089
3090    #[test]
3091    fn two_hop_join_on_shared_variable() {
3092        // Alice -> Bob -> Carol, plus a dead-end branch.
3093        let bytes = rete_from(&[
3094            ("Alice", "knows", "Bob"),
3095            ("Bob", "knows", "Carol"),
3096            ("Carol", "knows", "Dave"),
3097            ("Alice", "knows", "Eve"), // Eve knows no one -> no 2-hop
3098        ]);
3099        let rete = Rete::open(&bytes).unwrap();
3100        let sols = eval_bgp(&rete, &[pat("?x", "knows", "?y"), pat("?y", "knows", "?z")]);
3101        // Alice-Bob-Carol, Bob-Carol-Dave.
3102        let mut got: Vec<_> = sols
3103            .iter()
3104            .map(|b| (b["x"].clone(), b["y"].clone(), b["z"].clone()))
3105            .collect();
3106        got.sort();
3107        assert_eq!(
3108            got,
3109            vec![
3110                ("Alice".into(), "Bob".into(), "Carol".into()),
3111                ("Bob".into(), "Carol".into(), "Dave".into()),
3112            ]
3113        );
3114    }
3115
3116    #[test]
3117    fn repeated_variable_within_pattern() {
3118        // A mutual/self relation: only Bob knows himself.
3119        let bytes = rete_from(&[("Alice", "knows", "Bob"), ("Bob", "knows", "Bob")]);
3120        let rete = Rete::open(&bytes).unwrap();
3121        let sols = eval_bgp(&rete, &[pat("?x", "knows", "?x")]);
3122        assert_eq!(sols.len(), 1);
3123        assert_eq!(sols[0]["x"], "Bob");
3124    }
3125
3126    #[test]
3127    fn no_solutions_yields_empty() {
3128        let bytes = rete_from(&[("Alice", "knows", "Bob")]);
3129        let rete = Rete::open(&bytes).unwrap();
3130        assert!(eval_bgp(&rete, &[pat("Alice", "likes", "?y")]).is_empty());
3131    }
3132
3133    /// A LUBM-Q7-shaped snowflake: a popular class enumeration (`?x a Student`)
3134    /// plus a selective adjacency seed (`<Prof> teacherOf ?y`). Exercises both the
3135    /// **class-enum seed deprioritization** (the join must not start from the huge
3136    /// `a Student` extent) and the **probe-the-tail hybrid** (the type checks are
3137    /// applied late, per row). The answer must equal a brute-force computation
3138    /// regardless of how the join is ordered/probed.
3139    #[test]
3140    fn snowflake_type_and_adjacency_matches_reference() {
3141        const TYPE: &str = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
3142        let mut triples: Vec<(String, String, String)> = Vec::new();
3143        // 60 students, each a Student and taking 2 courses (c{i%5}, c{(i+1)%5}).
3144        for i in 0..60 {
3145            let s = format!("S{i}");
3146            triples.push((s.clone(), TYPE.into(), "Student".into()));
3147            triples.push((s.clone(), "takesCourse".into(), format!("c{}", i % 5)));
3148            triples.push((s, "takesCourse".into(), format!("c{}", (i + 1) % 5)));
3149        }
3150        // 5 courses; the professor teaches only c0 and c2.
3151        for j in 0..5 {
3152            triples.push((format!("c{j}"), TYPE.into(), "Course".into()));
3153        }
3154        triples.push(("Prof".into(), "teacherOf".into(), "c0".into()));
3155        triples.push(("Prof".into(), "teacherOf".into(), "c2".into()));
3156
3157        let refs: Vec<(&str, &str, &str)> = triples
3158            .iter()
3159            .map(|(s, p, o)| (s.as_str(), p.as_str(), o.as_str()))
3160            .collect();
3161        let bytes = rete_from(&refs);
3162        let rete = Rete::open(&bytes).unwrap();
3163
3164        let got: std::collections::BTreeSet<(String, String)> = eval_bgp(
3165            &rete,
3166            &[
3167                pat("?x", TYPE, "Student"),
3168                pat("?y", TYPE, "Course"),
3169                pat("?x", "takesCourse", "?y"),
3170                pat("Prof", "teacherOf", "?y"),
3171            ],
3172        )
3173        .into_iter()
3174        .map(|b| (b["x"].clone(), b["y"].clone()))
3175        .collect();
3176
3177        // Brute force: students taking a course the professor teaches (c0 or c2).
3178        let taught = ["c0", "c2"];
3179        let mut want = std::collections::BTreeSet::new();
3180        for i in 0..60 {
3181            for c in [i % 5, (i + 1) % 5] {
3182                let course = format!("c{c}");
3183                if taught.contains(&course.as_str()) {
3184                    want.insert((format!("S{i}"), course));
3185                }
3186            }
3187        }
3188        assert_eq!(got, want, "snowflake join must match the brute-force set");
3189        assert!(!want.is_empty(), "sanity: the reference set is non-empty");
3190    }
3191
3192    /// A subject-subject join (`?x a ?av . ?x b ?bv`) is the same-role shape the
3193    /// merge join handles: both patterns sort on the subject column. With multiple
3194    /// `a` and `b` values per subject it must emit the full cross product per
3195    /// subject (equal-key run handling) and drop subjects missing either side.
3196    #[test]
3197    fn merge_join_subject_star_cross_product() {
3198        let bytes = rete_from(&[
3199            ("x", "a", "a1"),
3200            ("x", "a", "a2"),
3201            ("x", "b", "b1"),
3202            ("x", "b", "b2"),
3203            ("y", "a", "a3"),
3204            ("y", "b", "b3"),
3205            ("z", "a", "a4"), // z has no `b` → contributes no join row
3206        ]);
3207        let rete = Rete::open(&bytes).unwrap();
3208        let mut got: Vec<(String, String, String)> =
3209            eval_bgp(&rete, &[pat("?x", "a", "?av"), pat("?x", "b", "?bv")])
3210                .iter()
3211                .map(|m| (m["x"].clone(), m["av"].clone(), m["bv"].clone()))
3212                .collect();
3213        got.sort();
3214        let mut want: Vec<(String, String, String)> = [
3215            ("x", "a1", "b1"),
3216            ("x", "a1", "b2"),
3217            ("x", "a2", "b1"),
3218            ("x", "a2", "b2"),
3219            ("y", "a3", "b3"),
3220        ]
3221        .into_iter()
3222        .map(|(a, b, c)| (a.to_string(), b.to_string(), c.to_string()))
3223        .collect();
3224        want.sort();
3225        assert_eq!(got, want, "same-role merge must equal the brute-force join");
3226    }
3227}