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/// `GRAPH ?g { one pattern }` over a quad-index file: every match of the
1094/// pattern in any graph as a row that also binds slot `gslot` to the graph,
1095/// streamed from one pass over the tiles (no view per graph). `None` when this
1096/// does not apply (not a single pattern, the graph variable also inside the
1097/// pattern, a file without a quad index): the caller falls back to walking the
1098/// graphs. A constant the dictionary cannot place gives an empty stream.
1099pub(crate) fn quad_scan_rows<'q>(
1100    ctx: &'q Ctx<'q>,
1101    patterns: &[TriplePattern],
1102    gslot: usize,
1103) -> Option<Box<dyn Iterator<Item = Row> + 'q>> {
1104    let [p] = patterns else {
1105        return None;
1106    };
1107    if [&p.s, &p.p, &p.o]
1108        .iter()
1109        .any(|t| matches!(t, PatternTerm::Var(v) if ctx.slots.slot(v) == Some(gslot)))
1110    {
1111        return None;
1112    }
1113    let dict = ctx.rete.dictionary();
1114    let Some(lowered) = lower(patterns, ctx) else {
1115        return Some(Box::new(std::iter::empty()));
1116    };
1117    let t = lowered[0];
1118    let (Some(sid), Some(pid), Some(oid)) = (
1119        const_subject(&t.0, dict),
1120        const_predicate(&t.1),
1121        const_object(&t.2, dict),
1122    ) else {
1123        return Some(Box::new(std::iter::empty()));
1124    };
1125    let scan = ctx.rete.named_quad_scan((sid, pid, oid))?;
1126    Some(Box::new(scan.filter_map(move |(g, triple)| {
1127        let mut row = triple_row(ctx, &t, triple)?;
1128        row[gslot] = Some(Val::Id(dict.subject_node(g) as i64));
1129        Some(row)
1130    })))
1131}
1132
1133mod class_probe;
1134pub(crate) use class_probe::class_probe_rows;
1135pub use class_probe::set_class_route;
1136
1137/// A triple pattern as the dictionary ids of its constants (subject, predicate, object).
1138pub(crate) type ScanPattern = (Option<u32>, Option<u32>, Option<u32>);
1139
1140/// The pattern of a BGP that best narrows a scan over every graph, as the
1141/// dictionary ids of its constants: the one with the most constants, a bound
1142/// subject or object weighing more than a bound predicate. `None` when no
1143/// pattern has a constant, or one cannot be placed in the dictionary.
1144pub(crate) fn driver_pattern(ctx: &Ctx, patterns: &[TriplePattern]) -> Option<ScanPattern> {
1145    let dict = ctx.rete.dictionary();
1146    let lowered = lower(patterns, ctx)?;
1147    let mut best: Option<(u32, ScanPattern)> = None;
1148    for t in &lowered {
1149        let (sid, pid, oid) = (
1150            const_subject(&t.0, dict)?,
1151            const_predicate(&t.1)?,
1152            const_object(&t.2, dict)?,
1153        );
1154        let score =
1155            3 * u32::from(sid.is_some()) + u32::from(pid.is_some()) + 3 * u32::from(oid.is_some());
1156        if score > 0 && best.is_none_or(|(b, _)| score > b) {
1157            best = Some((score, (sid, pid, oid)));
1158        }
1159    }
1160    best.map(|(_, pat)| pat)
1161}
1162
1163/// Scan one lowered pattern into a materialized relation, returning the rows
1164/// and the slots the pattern binds. `None` = a constant is unsatisfiable.
1165fn pattern_rows(
1166    ctx: &Ctx,
1167    index: &GraphIndex,
1168    t: &(SlotTerm, SlotTerm, SlotTerm),
1169) -> Option<(Vec<Row>, Vec<usize>)> {
1170    let slots = pattern_slots(t);
1171    let mut rel: Vec<Row> = Vec::new();
1172    let dict = ctx.rete.dictionary();
1173    let (sid, pid, oid) = (
1174        const_subject(&t.0, dict)?,
1175        const_predicate(&t.1)?,
1176        const_object(&t.2, dict)?,
1177    );
1178    // Stream the matches with the lazy cursor — the hash join is
1179    // order-independent, so no canonical re-sort is needed here.
1180    for triple in canon_ahead(ctx, t, index.scan_iter((sid, pid, oid))) {
1181        if let Some(row) = triple_row(ctx, t, triple) {
1182            rel.push(row);
1183        }
1184    }
1185    Some((rel, slots))
1186}
1187
1188/// A per-pattern cardinality estimate, smaller = cheaper to scan. The base is
1189/// the **exact** per-predicate triple count (sum of the summary quotient graph's
1190/// super-edge counts) when the predicate is bound, else the whole-graph total.
1191/// A bound subject/object (a constant, or a variable already bound by `seed`)
1192/// then scales it down by that predicate's **measured selectivity** from the
1193/// `query_stats` block — `1 / distinct_subjects` for a bound subject (so
1194/// `<s> <p> ?o` ≈ the average objects per subject; exactly 1 for a functional
1195/// predicate), `1 / distinct_objects` for a bound object. Files built before the
1196/// `query_stats` block fall back to fixed default selectivities. `None` when the
1197/// file carries no pyramid summary at all — ordering then uses the constant-count
1198/// heuristic.
1199fn pattern_estimates(
1200    ctx: &Ctx,
1201    index: &GraphIndex,
1202    lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1203    seed: &std::collections::HashSet<usize>,
1204) -> Option<Vec<f64>> {
1205    // Only use the summary when it's already in memory — never fault it just to
1206    // plan (the lazy remote path defers the pyramid by design).
1207    let pyr = ctx.rete.pyramid_if_loaded()?;
1208    let mut pred: std::collections::HashMap<u32, u64> = std::collections::HashMap::new();
1209    for e in &pyr.summary {
1210        *pred.entry(e.predicate).or_insert(0) += e.count as u64;
1211    }
1212    // Measured per-predicate distinct subjects/objects: the SCHEMA section
1213    // (kind 9) — where a file built since it existed keeps them, its
1214    // pyramid-meta holding only the community summary — else the pyramid-meta's
1215    // query-stats block; empty on files built before either → the default
1216    // selectivities. The pyramid is resident here, so the (small) section is
1217    // too on a resident open, and costs one range once on a lazy one.
1218    let stats: std::collections::HashMap<u32, &crate::meta::PredStat> = ctx
1219        .rete
1220        .planner_stats(true)
1221        .iter()
1222        .map(|s| (s.predicate, s))
1223        .collect();
1224    // The active graph's own size: a pattern inside `GRAPH <g>` cannot match more
1225    // triples than `g` holds, whatever the file-wide predicate count says.
1226    let graph_total = ctx.rete.index_triples(index).max(1) as f64;
1227    let total = graph_total;
1228    let num_preds = pred.len().max(1) as f64;
1229    // Defaults used only when query_stats has no entry for the predicate.
1230    const SEL_SUBJECT: f64 = 0.001;
1231    const SEL_OBJECT: f64 = 0.02;
1232    let node_bound = |t: &SlotTerm| match t {
1233        SlotTerm::Node(_) => true,
1234        SlotTerm::Var(v) => seed.contains(v),
1235        SlotTerm::Pred(_) => false,
1236    };
1237    Some(
1238        lowered
1239            .iter()
1240            .map(|t| {
1241                // Base from the predicate: exact total for a constant predicate,
1242                // the average predicate total for a seed-bound predicate variable
1243                // (the value is known to the probe but not at plan time), else the
1244                // whole graph. `st` is the measured stats for a constant predicate.
1245                let (base, st) = match t.1 {
1246                    SlotTerm::Pred(p) => {
1247                        (*pred.get(&p).unwrap_or(&0) as f64, stats.get(&p).copied())
1248                    }
1249                    SlotTerm::Var(v) if seed.contains(&v) => (total / num_preds, None),
1250                    _ => (total, None),
1251                };
1252                let mut est = base.min(graph_total).max(1.0);
1253                if node_bound(&t.0) {
1254                    est *= match st {
1255                        Some(s) if s.distinct_subjects > 0 => 1.0 / s.distinct_subjects as f64,
1256                        _ => SEL_SUBJECT,
1257                    };
1258                }
1259                if node_bound(&t.2) {
1260                    est *= match st {
1261                        Some(s) if s.distinct_objects > 0 => 1.0 / s.distinct_objects as f64,
1262                        _ => SEL_OBJECT,
1263                    };
1264                }
1265                est.max(1.0)
1266            })
1267            .collect(),
1268    )
1269}
1270
1271/// The minimum, over a BGP's patterns, of [`pattern_scan_bytes`] — the
1272/// cheapest single-pattern scan the hash-join path would at least perform to
1273/// materialize this BGP. `None` = a constant term is unknown to the
1274/// dictionary (the BGP is unsatisfiable; the caller short-circuits anyway).
1275/// Unlike [`pattern_estimates`], this needs no pyramid summary, so it works on
1276/// remote-lazy files — exactly where the answer matters most.
1277pub(crate) fn bgp_min_scan_bytes(
1278    ctx: &Ctx,
1279    index: &GraphIndex,
1280    patterns: &[TriplePattern],
1281) -> Option<u64> {
1282    let lowered = lower(patterns, ctx)?;
1283    lowered
1284        .iter()
1285        .map(|t| pattern_scan_bytes(ctx, index, t))
1286        .min()
1287}
1288
1289/// One pattern's cheapest scan extent in BYTES — what `rete cost` previews
1290/// (the planner's gates use row estimates instead): for each permutation, sum the
1291/// encoded lengths of the tiles a scan of this pattern would route to (all
1292/// tiles covering the bound leading key, or the whole section when the leading
1293/// key is unbound), and take the minimum. Tile *counts* are useless here — a
1294/// broad predicate can sit inside one giant tile — but the directory's byte
1295/// lengths expose it. Reads only resident metadata, never tile data.
1296///
1297/// A bound term routes by its id **in the role its position has**: a tile's
1298/// leading range is in subject-, predicate- or object-id space, not in the
1299/// unified node space a lowered constant carries. Routing the node id instead
1300/// was off by one for subjects and off by the whole subject-only block for an
1301/// object-only term (every literal), so `?id :value "10.1234/x"` could cost
1302/// "0 bytes" and pass the merge-join gate against a fat partner, which the
1303/// merge then materialized in full. A constant that has no id in the role
1304/// (never a subject, say) matches nothing: 0 bytes is then exact.
1305fn pattern_scan_bytes(ctx: &Ctx, index: &GraphIndex, t: &(SlotTerm, SlotTerm, SlotTerm)) -> u64 {
1306    let dict = ctx.rete.dictionary();
1307    match (
1308        const_subject(&t.0, dict),
1309        const_predicate(&t.1),
1310        const_object(&t.2, dict),
1311    ) {
1312        (Some(s), Some(p), Some(o)) => routed_scan_bytes(index, (s, p, o)),
1313        _ => 0,
1314    }
1315}
1316
1317/// [`pattern_scan_bytes`] for a pattern already in role-id space.
1318pub(crate) fn routed_scan_bytes(index: &GraphIndex, pattern: Pattern) -> u64 {
1319    let sections = index.tile_sections();
1320    let mut best = u64::MAX;
1321    // Only the permutations the FILE carries: an absent section is an empty
1322    // `Vec<Tile>`, and summing its (zero) tile lengths would report a free scan
1323    // for the one permutation that cannot be scanned at all.
1324    for perm in index.perms().iter() {
1325        let tiles = sections[perm.section_index()];
1326        // A leafed (0x06) directory answers from its root without faulting a
1327        // leaf: a cost estimate must not cost a round trip.
1328        best = best.min(match perm.order_pattern(pattern)[0] {
1329            // A bound subject of a clustered file is one tile of an unknown run.
1330            Some(_) if index.cluster_runs(perm.section_index()).is_some() => {
1331                index.clustered_subject_bytes(perm.section_index())
1332            }
1333            Some(id) => tiles.routed_bytes(id),
1334            None => tiles.total_bytes(),
1335        });
1336    }
1337    best
1338}
1339
1340/// Estimated matches above which a join side counts as "fat": materializing
1341/// (or, on a remote index, fetching) a million rows to build a hash/merge side
1342/// is past the point where probing it per surviving row wins. Shared by the
1343/// merge-seed asymmetry gate here and the force-probe gates in `sparql::eval`.
1344///
1345/// A ROW estimate ([`GraphIndex::estimate_matches`]: routed tiles × rows per
1346/// tile), not a byte figure. Tiles are cut by their encoded size before
1347/// compression, so the estimate does not move when only the compression does;
1348/// the compressed tile bytes this gate used to read did — at zstd level 19,
1349/// two OpenCitations queries crossed the old 2 MiB line and ran 3–7× slower
1350/// with up to 6× the memory — and they differed between a resident open
1351/// (decoded sizes) and a lazy one (compressed sizes) of the same file.
1352pub(crate) const FAT_SCAN_ROWS: f64 = (1u64 << 20) as f64;
1353
1354/// Would a merge join of `ta` and `tb` materialize a fat side next to a
1355/// pinpoint one? (One side above [`FAT_SCAN_ROWS`] and at least four times the
1356/// other.) Then the hybrid loop — scan the small side, probe the fat one — is
1357/// strictly better, and the merge seed is declined.
1358fn merge_seed_lopsided(
1359    ctx: &Ctx,
1360    index: &GraphIndex,
1361    ta: &(SlotTerm, SlotTerm, SlotTerm),
1362    tb: &(SlotTerm, SlotTerm, SlotTerm),
1363) -> bool {
1364    let est = tile_estimates(ctx, index, &[*ta, *tb], &std::collections::HashSet::new());
1365    let (lo, hi) = (est[0].min(est[1]), est[0].max(est[1]));
1366    hi >= FAT_SCAN_ROWS && hi / 4.0 >= lo
1367}
1368
1369/// Order pattern indices for a left-deep join: cheapest (smallest estimated
1370/// cardinality) first, always preferring a pattern that shares a variable with
1371/// the already-joined set so the join stays connected and intermediate relations
1372/// stay small. Cardinality comes from [`pattern_estimates`]; with no summary it
1373/// falls back to a most-constants-first heuristic. Pure reordering — `hash_join`
1374/// is order-independent, so the result multiset is unchanged.
1375fn selectivity_order(
1376    ctx: &Ctx,
1377    index: &GraphIndex,
1378    lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1379) -> Vec<usize> {
1380    selectivity_order_seeded(ctx, index, lowered, &std::collections::HashSet::new())
1381}
1382
1383/// [`selectivity_order`] with a set of slots already bound by an outer seed
1384/// row: those variables count as already connected (and, in the no-summary
1385/// fallback, as constants for selectivity).
1386fn selectivity_order_seeded(
1387    ctx: &Ctx,
1388    index: &GraphIndex,
1389    lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1390    seed: &std::collections::HashSet<usize>,
1391) -> Vec<usize> {
1392    // Exact per-predicate statistics when the pyramid is resident; otherwise
1393    // (the lazy path, and files built without a pyramid) the tile-directory
1394    // estimate, which needs no fetch. That one also counts a class's own
1395    // instances (`?s a :C` routes to the tiles of `:C`), so the
1396    // class-enumeration rule below, a stand-in for exactly that missing
1397    // number, applies only to the pyramid figures, whose `rdf:type`
1398    // selectivity is an average over classes.
1399    let (estimates, per_class) = match pattern_estimates(ctx, index, lowered, seed) {
1400        Some(e) => (Some(e), false),
1401        None => (Some(tile_estimates(ctx, index, lowered, seed)), true),
1402    };
1403    let consts = |t: &(SlotTerm, SlotTerm, SlotTerm)| {
1404        [&t.0, &t.1, &t.2]
1405            .into_iter()
1406            .filter(|x| match x {
1407                SlotTerm::Var(v) => seed.contains(v),
1408                _ => true,
1409            })
1410            .count()
1411    };
1412    let vars = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Vec<usize> {
1413        [&t.0, &t.1, &t.2]
1414            .into_iter()
1415            .filter_map(|x| match x {
1416                SlotTerm::Var(v) => Some(*v),
1417                _ => None,
1418            })
1419            .collect()
1420    };
1421    // Higher score = picked sooner. With summary stats that's the negated
1422    // estimate (smaller cardinality wins); without, the constant count (old
1423    // behaviour, byte-identical ordering for pyramid-less files).
1424    let score = |i: usize| -> f64 {
1425        match &estimates {
1426            Some(e) => -e[i],
1427            None => consts(&lowered[i]) as f64,
1428        }
1429    };
1430    // A `?s rdf:type <Class>` with an as-yet-unbound subject is a **class
1431    // enumeration**: it matches every instance of the class, so it is almost never
1432    // the most selective place to *start* a join (a popular class has thousands of
1433    // instances), even though it has two bound positions and so looks selective to
1434    // the constant-count heuristic. Deprioritize it as a seed; once its subject is
1435    // bound by another pattern it becomes a cheap per-row type *check* (the hybrid
1436    // join probes it), so pushing it later costs nothing. Robust and stats-free.
1437    let type_pid = ctx.rete.dictionary().predicate_id(crate::file::RDF_TYPE);
1438    let is_class_enum = |i: usize, bound: &std::collections::HashSet<usize>| -> bool {
1439        let t = &lowered[i];
1440        !per_class
1441            && type_pid.is_some_and(|tp| matches!(t.1, SlotTerm::Pred(p) if p == tp))
1442            && matches!(t.2, SlotTerm::Node(_))
1443            && matches!(t.0, SlotTerm::Var(v) if !bound.contains(&v))
1444    };
1445    let n = lowered.len();
1446    let mut remaining: Vec<usize> = (0..n).collect();
1447    let mut order: Vec<usize> = Vec::with_capacity(n);
1448    let mut bound: std::collections::HashSet<usize> = seed.clone();
1449    while !remaining.is_empty() {
1450        // Pick the remaining pattern with the best (connected, not-a-class-enum,
1451        // score) key; ties go to the lowest original index for a stable order.
1452        let best = *remaining
1453            .iter()
1454            .max_by(|&&a, &&b| {
1455                let connected = |i: usize| vars(&lowered[i]).iter().any(|v| bound.contains(v));
1456                connected(a)
1457                    .cmp(&connected(b))
1458                    .then_with(|| is_class_enum(b, &bound).cmp(&is_class_enum(a, &bound)))
1459                    .then_with(|| {
1460                        score(a)
1461                            .partial_cmp(&score(b))
1462                            .unwrap_or(std::cmp::Ordering::Equal)
1463                    })
1464                    .then_with(|| b.cmp(&a))
1465            })
1466            .unwrap();
1467        for v in vars(&lowered[best]) {
1468            bound.insert(v);
1469        }
1470        order.push(best);
1471        remaining.retain(|&i| i != best);
1472    }
1473    order
1474}
1475
1476/// Does the BGP have at least one solution against `index`? A single pattern
1477/// with all-distinct variables streams the index and stops at the first match
1478/// (no materialization); anything else falls back to the full evaluator and
1479/// tests non-emptiness (still benefiting from the lazy per-pattern scan). Used
1480/// by `ASK`.
1481pub(crate) fn bgp_exists(ctx: &Ctx, index: &GraphIndex, patterns: &[TriplePattern]) -> bool {
1482    let dict = ctx.rete.dictionary();
1483    let Some(lowered) = lower(patterns, ctx) else {
1484        return false;
1485    };
1486    if let [t] = lowered.as_slice() {
1487        // The fast path can't enforce a variable repeated across positions
1488        // (e.g. `?x p ?x`) — that needs the row builder — so only take it when
1489        // the pattern's variables are all distinct.
1490        let names: Vec<usize> = [&t.0, &t.1, &t.2]
1491            .into_iter()
1492            .filter_map(|x| match x {
1493                SlotTerm::Var(v) => Some(*v),
1494                _ => None,
1495            })
1496            .collect();
1497        let distinct = names
1498            .iter()
1499            .enumerate()
1500            .all(|(i, v)| !names[i + 1..].contains(v));
1501        if distinct {
1502            return match (
1503                const_subject(&t.0, dict),
1504                const_predicate(&t.1),
1505                const_object(&t.2, dict),
1506            ) {
1507                (Some(s), Some(p), Some(o)) => index.scan_iter((s, p, o)).next().is_some(),
1508                _ => false,
1509            };
1510        }
1511    }
1512    !eval_bgp_rows(ctx, index, patterns).is_empty()
1513}
1514
1515/// A lazy left-deep BGP join that yields solution rows one at a time, so a
1516/// consumer under `LIMIT`/`OFFSET` (or `.next()` for ASK) can stop early —
1517/// stopping also stops the underlying index scan.
1518///
1519/// The all-but-last patterns are joined eagerly into a `prefix` **hash table**
1520/// (they are the most selective, so this is the small side); the *last* (least
1521/// selective) pattern is then **streamed** from the index cursor, probing the
1522/// prefix — the big scan is never materialized, and a `LIMIT` above stops it
1523/// after a handful of triples. Yields the same solution multiset as
1524/// [`eval_bgp_rows`] (the join is order-independent), just incrementally.
1525pub(crate) struct BgpSolutions<'q> {
1526    scan: Option<Box<dyn Iterator<Item = Row> + 'q>>,
1527    prefix: Vec<Row>,
1528    /// Prefix row indices keyed by the shared-slot values.
1529    buckets: HashMap<Vec<Val>, Vec<usize>>,
1530    shared: Vec<usize>,
1531    cartesian: bool,
1532    /// The prefix is the all-unbound seed row (single-pattern BGP): scanned
1533    /// rows are already complete solutions — pass them through unmerged.
1534    seed_only: bool,
1535    cur_scan: Option<Row>,
1536    /// Reused candidate buffer (avoids a Vec allocation per scanned row).
1537    matches: Vec<usize>,
1538    mi: usize,
1539}
1540
1541impl<'q> BgpSolutions<'q> {
1542    /// Yield `rows` as complete solutions (no prefix merge).
1543    fn passthrough(rows: Box<dyn Iterator<Item = Row> + 'q>) -> Self {
1544        BgpSolutions {
1545            scan: Some(rows),
1546            prefix: Vec::new(),
1547            buckets: HashMap::new(),
1548            shared: Vec::new(),
1549            cartesian: false,
1550            seed_only: true,
1551            cur_scan: None,
1552            matches: Vec::new(),
1553            mi: 0,
1554        }
1555    }
1556
1557    /// The fully streaming join, for a BGP whose most selective pattern is
1558    /// itself large ([`STREAM_SEED_ROWS`]). Nothing proportional to it is ever
1559    /// held: the seed pattern streams from its index cursor (or, when the next
1560    /// pattern is just as large and shares its subject variable, both stream
1561    /// through a merge join), and each later pattern joins per row — through
1562    /// a hash table when the pattern is small ([`HASH_BUILD_ROWS`]), by an
1563    /// index probe otherwise. Same solution multiset as the materializing
1564    /// path; only the row order differs.
1565    fn streaming(
1566        ctx: &'q Ctx<'q>,
1567        index: &'q GraphIndex,
1568        lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1569        order: &[usize],
1570        est: &[f64],
1571    ) -> Self {
1572        let (mut stream, mut bound, skip): (Box<dyn Iterator<Item = Row> + 'q>, Vec<usize>, usize) =
1573            match (est[order[1]] > limits().stream_seed)
1574                .then(|| merge_stream(ctx, index, lowered[order[0]], lowered[order[1]]))
1575                .flatten()
1576            {
1577                Some((m, slots)) => (m, slots, 2),
1578                None => {
1579                    let t = lowered[order[0]];
1580                    let Some(scan) = scan_rows(ctx, index, t) else {
1581                        return Self::empty();
1582                    };
1583                    (Box::new(scan), pattern_slots(&t), 1)
1584                }
1585            };
1586        for &i in &order[skip..] {
1587            let t = lowered[i];
1588            let slots = pattern_slots(&t);
1589            let shared: Vec<usize> = slots
1590                .iter()
1591                .copied()
1592                .filter(|s| bound.contains(s))
1593                .collect();
1594            if !shared.is_empty() && est[i] > limits().hash_build {
1595                // Each window of streamed rows has its probes' tiles faulted
1596                // together ([`Windowed`]); one at a time, a probe join over a
1597                // remote file was bound by round-trip latency.
1598                stream = Box::new(
1599                    windowed(index, stream, bgp_probe_pattern(ctx, t))
1600                        .flat_map(move |base| probe_rows(ctx, index, t, base)),
1601                );
1602            } else {
1603                // Small (or unconnected) pattern: scan it once into a table
1604                // keyed on the shared slots and join every streamed row to it.
1605                let Some((rel, _)) = pattern_rows(ctx, index, &t) else {
1606                    return Self::empty();
1607                };
1608                let mut table: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
1609                for r in rel {
1610                    let key: Vec<Val> = shared.iter().map(|&s| r[s].clone().unwrap()).collect();
1611                    table.entry(key).or_default().push(r);
1612                }
1613                let fill = slots.clone();
1614                stream = Box::new(stream.flat_map(move |base| {
1615                    let key: Vec<Val> = shared.iter().map(|&s| base[s].clone().unwrap()).collect();
1616                    let out: Vec<Row> = table
1617                        .get(&key)
1618                        .map(|rs| {
1619                            rs.iter()
1620                                .map(|r| {
1621                                    let mut row = base.clone();
1622                                    for &s in &fill {
1623                                        row[s] = r[s].clone();
1624                                    }
1625                                    row
1626                                })
1627                                .collect()
1628                        })
1629                        .unwrap_or_default();
1630                    out.into_iter()
1631                }));
1632            }
1633            for s in slots {
1634                if !bound.contains(&s) {
1635                    bound.push(s);
1636                }
1637            }
1638        }
1639        Self::passthrough(stream)
1640    }
1641
1642    /// An iterator that yields nothing (an unsatisfiable BGP).
1643    fn empty() -> Self {
1644        BgpSolutions {
1645            scan: None,
1646            prefix: Vec::new(),
1647            buckets: HashMap::new(),
1648            shared: Vec::new(),
1649            cartesian: false,
1650            seed_only: false,
1651            cur_scan: None,
1652            matches: Vec::new(),
1653            mi: 0,
1654        }
1655    }
1656
1657    pub(crate) fn new(ctx: &'q Ctx<'q>, index: &'q GraphIndex, patterns: &[TriplePattern]) -> Self {
1658        // An empty BGP has exactly one (empty) solution.
1659        if patterns.is_empty() {
1660            return BgpSolutions {
1661                scan: Some(Box::new(std::iter::once(ctx.slots.empty_row()))),
1662                prefix: vec![ctx.slots.empty_row()],
1663                buckets: HashMap::new(),
1664                shared: Vec::new(),
1665                cartesian: true,
1666                seed_only: true,
1667                cur_scan: None,
1668                matches: Vec::new(),
1669                mi: 0,
1670            };
1671        }
1672        // Lower all patterns; an unknown constant term ⇒ no solutions.
1673        let Some(lowered) = lower(patterns, ctx) else {
1674            return Self::empty();
1675        };
1676        // Join all but the *last* (least selective) pattern eagerly into the
1677        // prefix; a single pattern leaves the seed row as the prefix.
1678        let (order, scan_est) = plan_order(ctx, index, &lowered);
1679        // Even the most selective pattern is big: materializing it as the
1680        // prefix would hold every one of its rows. Stream the whole join.
1681        if order.len() >= 2 && scan_est[order[0]] > limits().stream_seed {
1682            return Self::streaming(ctx, index, &lowered, &order, &scan_est);
1683        }
1684        let (&last_i, prefix_is) = order.split_last().unwrap();
1685        let prefix_pats: Vec<TriplePattern> =
1686            prefix_is.iter().map(|&i| patterns[i].clone()).collect();
1687        let prefix = eval_bgp_rows(ctx, index, &prefix_pats);
1688        if prefix.is_empty() {
1689            return Self::empty();
1690        }
1691
1692        // Hash-join key = slots shared by the prefix and the last pattern (BGP
1693        // rows bind every slot of their pattern set, so the prefix's bound set
1694        // can be read off its first row).
1695        let shared: Vec<usize> = pattern_slots(&lowered[last_i])
1696            .into_iter()
1697            .filter(|&s| prefix[0][s].is_some())
1698            .collect();
1699
1700        // A few prefix rows against a big last pattern: look each one up
1701        // instead of scanning the pattern. `?r :relationSubject <doi> . ?r ?p
1702        // ?o` has four prefix rows and a last pattern that is the whole graph.
1703        // The last pattern is an unbound class (`?x rdf:type ?c`) whose subject
1704        // the prefix binds: each row's types are one SPO lookup, and the prefix
1705        // is already resident, so probing costs no memory the scan would not.
1706        // It wins until the rows outnumber the statements the scan would read
1707        // (the usual sixteenth gives way to one).
1708        let class_probe = !shared.is_empty()
1709            && scan_est[last_i] >= limits().probe_floor
1710            && (prefix.len() as f64) <= scan_est[last_i]
1711            && is_unbound_class(ctx, &lowered[last_i], &shared);
1712        if !shared.is_empty() && (probe_beats_scan(prefix.len(), scan_est[last_i]) || class_probe) {
1713            let t = lowered[last_i];
1714            let stream = windowed(index, prefix.into_iter(), bgp_probe_pattern(ctx, t))
1715                .flat_map(move |base| probe_rows(ctx, index, t, base));
1716            return Self::passthrough(Box::new(stream));
1717        }
1718
1719        // Stream the last pattern with the lazy index cursor.
1720        let Some(scan) = scan_rows(ctx, index, lowered[last_i]) else {
1721            return Self::empty();
1722        };
1723        let cartesian = shared.is_empty();
1724        // A single-pattern BGP joins against the all-unbound seed: scanned rows
1725        // are already complete solutions.
1726        let seed_only = prefix.len() == 1 && prefix[0].iter().all(Option::is_none);
1727        let mut buckets: HashMap<Vec<Val>, Vec<usize>> = HashMap::new();
1728        if !cartesian {
1729            for (i, r) in prefix.iter().enumerate() {
1730                let key: Vec<Val> = shared.iter().map(|&s| r[s].clone().unwrap()).collect();
1731                buckets.entry(key).or_default().push(i);
1732            }
1733        }
1734        BgpSolutions {
1735            scan: Some(Box::new(scan)),
1736            prefix,
1737            buckets,
1738            shared,
1739            cartesian,
1740            seed_only,
1741            cur_scan: None,
1742            matches: Vec::new(),
1743            mi: 0,
1744        }
1745    }
1746}
1747
1748impl Iterator for BgpSolutions<'_> {
1749    type Item = Row;
1750
1751    fn next(&mut self) -> Option<Row> {
1752        // Single-pattern fast path: pass scanned rows through unmerged.
1753        if self.seed_only {
1754            return self.scan.as_mut()?.next();
1755        }
1756        loop {
1757            // Emit the next prefix match for the current scanned row.
1758            if self.mi < self.matches.len() {
1759                let pi = self.matches[self.mi];
1760                self.mi += 1;
1761                let mut merged = self.prefix[pi].clone();
1762                for (slot, v) in self.cur_scan.as_ref().unwrap().iter().enumerate() {
1763                    if v.is_some() {
1764                        merged[slot] = v.clone();
1765                    }
1766                }
1767                return Some(merged);
1768            }
1769            // Pull the next row from the index scan and gather its matches
1770            // (into the reused buffer — no allocation per scanned row).
1771            let s = self.scan.as_mut()?.next()?;
1772            self.matches.clear();
1773            if self.cartesian {
1774                self.matches.extend(0..self.prefix.len());
1775            } else {
1776                let key: Vec<Val> = self.shared.iter().map(|&i| s[i].clone().unwrap()).collect();
1777                if let Some(c) = self.buckets.get(&key) {
1778                    self.matches.extend_from_slice(c);
1779                }
1780            }
1781            self.mi = 0;
1782            self.cur_scan = Some(s);
1783        }
1784    }
1785}
1786
1787/// A **streaming** merge join of two patterns that share exactly one variable,
1788/// in the subject position of both: each side streams from a permutation
1789/// sorted on subject ([`GraphIndex::scan_iter_sorted_on`]) and only the
1790/// current subject's rows are held. Restricted to the subject column because a
1791/// subject's rows are its out-edges, a small run; an object run (every
1792/// instance of a class) can be the whole pattern. `None` when the shape does
1793/// not qualify; the caller then streams the first pattern alone.
1794#[allow(clippy::type_complexity)]
1795fn merge_stream<'q>(
1796    ctx: &'q Ctx<'q>,
1797    index: &'q GraphIndex,
1798    ta: (SlotTerm, SlotTerm, SlotTerm),
1799    tb: (SlotTerm, SlotTerm, SlotTerm),
1800) -> Option<(Box<dyn Iterator<Item = Row> + 'q>, Vec<usize>)> {
1801    let sa = pattern_slots(&ta);
1802    let sb = pattern_slots(&tb);
1803    let shared: Vec<usize> = sa.iter().copied().filter(|s| sb.contains(s)).collect();
1804    let [v] = shared[..] else {
1805        return None;
1806    };
1807    if !matches!(ta.0, SlotTerm::Var(i) if i == v) || !matches!(tb.0, SlotTerm::Var(i) if i == v) {
1808        return None;
1809    }
1810    let dict = ctx.rete.dictionary();
1811    let lower = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Option<Pattern> {
1812        Some((
1813            const_subject(&t.0, dict)?,
1814            const_predicate(&t.1)?,
1815            const_object(&t.2, dict)?,
1816        ))
1817    };
1818    let side = |t: (SlotTerm, SlotTerm, SlotTerm)| -> Option<KeyedRows<'q>> {
1819        let it = index.scan_iter_sorted_on(lower(&t)?, 0)?;
1820        let keyed: Box<dyn Iterator<Item = (u32, Row)> + 'q> =
1821            Box::new(it.filter_map(move |tri| triple_row(ctx, &t, tri).map(|r| (tri.0, r))));
1822        Some(keyed.peekable())
1823    };
1824    let a = side(ta)?;
1825    let b = side(tb)?;
1826    let mut slots = sa;
1827    for s in sb {
1828        if !slots.contains(&s) {
1829            slots.push(s);
1830        }
1831    }
1832    Some((
1833        Box::new(MergeStream {
1834            a,
1835            b,
1836            ra: Vec::new(),
1837            rb: Vec::new(),
1838            i: 0,
1839            j: 0,
1840        }),
1841        slots,
1842    ))
1843}
1844
1845type KeyedRows<'q> = std::iter::Peekable<Box<dyn Iterator<Item = (u32, Row)> + 'q>>;
1846
1847/// The two-pointer merge behind [`merge_stream`]: `ra`/`rb` hold the current
1848/// equal-key runs and `(i, j)` walks their cross product lazily.
1849struct MergeStream<'q> {
1850    a: KeyedRows<'q>,
1851    b: KeyedRows<'q>,
1852    ra: Vec<Row>,
1853    rb: Vec<Row>,
1854    i: usize,
1855    j: usize,
1856}
1857
1858impl Iterator for MergeStream<'_> {
1859    type Item = Row;
1860
1861    fn next(&mut self) -> Option<Row> {
1862        loop {
1863            while self.i < self.ra.len() {
1864                if self.j < self.rb.len() {
1865                    let j = self.j;
1866                    self.j += 1;
1867                    if let Some(m) = crate::row::merge_rows(&self.ra[self.i], &self.rb[j]) {
1868                        return Some(m);
1869                    }
1870                } else {
1871                    self.i += 1;
1872                    self.j = 0;
1873                }
1874            }
1875            let ka = self.a.peek()?.0;
1876            let kb = self.b.peek()?.0;
1877            match ka.cmp(&kb) {
1878                std::cmp::Ordering::Less => {
1879                    self.a.next();
1880                }
1881                std::cmp::Ordering::Greater => {
1882                    self.b.next();
1883                }
1884                std::cmp::Ordering::Equal => {
1885                    self.ra.clear();
1886                    self.rb.clear();
1887                    while let Some((_, r)) = self.a.next_if(|(k, _)| *k == ka) {
1888                        self.ra.push(r);
1889                    }
1890                    while let Some((_, r)) = self.b.next_if(|(k, _)| *k == ka) {
1891                        self.rb.push(r);
1892                    }
1893                    self.i = 0;
1894                    self.j = 0;
1895                }
1896            }
1897        }
1898    }
1899}
1900
1901// --- index-nested-loop probing ------------------------------------------------
1902//
1903// Under a small, known demand (LIMIT/ASK — see `Ctx::limit_hint`), scanning
1904// every pattern once to hash-join is mostly wasted work: the consumer wants a
1905// handful of rows. The probe path instead streams the seed/first pattern and,
1906// per row, *probes* each next pattern through the index with the row's bound
1907// values substituted as scan constants — so producing k solutions touches
1908// O(k · patterns) index groups instead of every pattern's full extent. Same
1909// solution multiset as the hash join (joins are order-independent); only the
1910// evaluation order differs.
1911
1912/// Index-scan constant for a subject position given a partially-bound row.
1913/// Outer `None` = unsatisfiable for this row; inner `None` = wildcard.
1914fn probe_subject(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
1915    let dict = ctx.rete.dictionary();
1916    match t {
1917        SlotTerm::Node(n) => dict.node_as_subject_id(*n).map(Some),
1918        SlotTerm::Pred(_) => None,
1919        SlotTerm::Var(i) => match &base[*i] {
1920            None => Some(None),
1921            Some(Val::Id(v)) if *v >= 0 => dict.node_as_subject_id(*v as u32).map(Some),
1922            // A predicate-tagged or computed value can never be a subject.
1923            Some(_) => None,
1924        },
1925    }
1926}
1927
1928/// Index-scan constant for an object position (see [`probe_subject`]).
1929fn probe_object(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
1930    let dict = ctx.rete.dictionary();
1931    match t {
1932        SlotTerm::Node(n) => dict.node_as_object_id(*n).map(Some),
1933        SlotTerm::Pred(_) => None,
1934        SlotTerm::Var(i) => match &base[*i] {
1935            None => Some(None),
1936            Some(Val::Id(v)) if *v >= 0 => dict.node_as_object_id(*v as u32).map(Some),
1937            Some(_) => None,
1938        },
1939    }
1940}
1941
1942/// Index-scan constant for a predicate position (see [`probe_subject`]).
1943fn probe_predicate(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
1944    let dict = ctx.rete.dictionary();
1945    match t {
1946        SlotTerm::Pred(p) => Some(Some(*p)),
1947        SlotTerm::Node(_) => None,
1948        SlotTerm::Var(i) => match &base[*i] {
1949            None => Some(None),
1950            Some(Val::Id(v)) if *v < 0 => Some(Some((-v - 1) as u32)),
1951            // Canonicalized to a node id — the term may still be a predicate.
1952            Some(Val::Id(v)) => ctx
1953                .resolver
1954                .term(*v)
1955                .and_then(|t| dict.predicate_id(&t))
1956                .map(Some),
1957            Some(Val::Str(_)) => None,
1958        },
1959    }
1960}
1961
1962/// Probe one pattern with a partially-bound row: every bound variable becomes
1963/// an index-scan constant, and each matching triple extends a clone of the row
1964/// (repeated unbound variables stay consistent).
1965fn probe_rows<'q>(
1966    ctx: &'q Ctx<'q>,
1967    index: &'q GraphIndex,
1968    t: (SlotTerm, SlotTerm, SlotTerm),
1969    base: Row,
1970) -> Box<dyn Iterator<Item = Row> + 'q> {
1971    let (Some(sid), Some(pid), Some(oid)) = (
1972        probe_subject(ctx, &t.0, &base),
1973        probe_predicate(ctx, &t.1, &base),
1974        probe_object(ctx, &t.2, &base),
1975    ) else {
1976        return Box::new(std::iter::empty());
1977    };
1978    let dict = ctx.rete.dictionary();
1979    // A variable predicate is canonicalized a run at a time ([`canon_ahead`]):
1980    // one new predicate after another was a dictionary round trip each.
1981    Box::new(
1982        canon_ahead(ctx, &t, index.scan_iter((sid, pid, oid))).filter_map(
1983            move |(s_id, p_id, o_id)| {
1984                let s_val = dict.subject_node(s_id) as i64;
1985                let p_val = pred_val(ctx, &t.1, p_id);
1986                let o_val = dict.object_node(o_id) as i64;
1987                let mut row = base.clone();
1988                for (term, val) in [(&t.0, s_val), (&t.1, p_val), (&t.2, o_val)] {
1989                    if let SlotTerm::Var(i) = term {
1990                        match row[*i] {
1991                            Some(Val::Id(existing)) if existing != val => return None,
1992                            Some(Val::Id(_)) => {}
1993                            Some(Val::Str(_)) => return None,
1994                            None => row[*i] = Some(Val::Id(val)),
1995                        }
1996                    }
1997                }
1998                Some(row)
1999            },
2000        ),
2001    )
2002}
2003
2004/// A lowered, probe-ordered BGP, reusable across many seed rows.
2005pub(crate) struct ProbePlan {
2006    pats: Vec<(SlotTerm, SlotTerm, SlotTerm)>,
2007}
2008
2009impl ProbePlan {
2010    /// Lower and order `patterns` for probing from rows that bind (at least)
2011    /// the slots in `seed_mask`. `None` = a constant term is unknown, making
2012    /// the BGP unsatisfiable for every seed.
2013    pub(crate) fn new(
2014        ctx: &Ctx,
2015        index: &GraphIndex,
2016        patterns: &[TriplePattern],
2017        seed_mask: &[bool],
2018    ) -> Option<Self> {
2019        let lowered = lower(patterns, ctx)?;
2020        let seed: std::collections::HashSet<usize> = seed_mask
2021            .iter()
2022            .enumerate()
2023            .filter_map(|(i, b)| b.then_some(i))
2024            .collect();
2025        let order = selectivity_order_seeded(ctx, index, &lowered, &seed);
2026        Some(ProbePlan {
2027            pats: order.into_iter().map(|i| lowered[i]).collect(),
2028        })
2029    }
2030}
2031
2032/// Depth-first index-nested-loop join over a [`ProbePlan`], starting from a
2033/// seed row. Fully lazy: pulling k rows probes O(k · patterns) index groups.
2034pub(crate) struct ProbeJoin<'q> {
2035    ctx: &'q Ctx<'q>,
2036    index: &'q GraphIndex,
2037    pats: Vec<(SlotTerm, SlotTerm, SlotTerm)>,
2038    stack: Vec<Box<dyn Iterator<Item = Row> + 'q>>,
2039}
2040
2041impl<'q> ProbeJoin<'q> {
2042    /// Probe a whole BGP from scratch (the seed is the all-unbound row).
2043    /// `None` = unsatisfiable.
2044    pub(crate) fn new(
2045        ctx: &'q Ctx<'q>,
2046        index: &'q GraphIndex,
2047        patterns: &[TriplePattern],
2048    ) -> Option<Self> {
2049        let plan = ProbePlan::new(ctx, index, patterns, &vec![false; ctx.slots.len()])?;
2050        Some(Self::from_plan(ctx, index, &plan, ctx.slots.empty_row()))
2051    }
2052
2053    /// Probe a pre-lowered plan from one seed row.
2054    pub(crate) fn from_plan(
2055        ctx: &'q Ctx<'q>,
2056        index: &'q GraphIndex,
2057        plan: &ProbePlan,
2058        seed: Row,
2059    ) -> Self {
2060        let pats = plan.pats.clone();
2061        let first = probe_rows(ctx, index, pats[0], seed);
2062        ProbeJoin {
2063            ctx,
2064            index,
2065            pats,
2066            stack: vec![first],
2067        }
2068    }
2069}
2070
2071impl Iterator for ProbeJoin<'_> {
2072    type Item = Row;
2073
2074    fn next(&mut self) -> Option<Row> {
2075        loop {
2076            let depth = self.stack.len();
2077            match self.stack.last_mut()?.next() {
2078                Some(row) => {
2079                    if depth == self.pats.len() {
2080                        return Some(row);
2081                    }
2082                    let it = probe_rows(self.ctx, self.index, self.pats[depth], row);
2083                    self.stack.push(it);
2084                }
2085                None => {
2086                    self.stack.pop();
2087                    if self.stack.is_empty() {
2088                        return None;
2089                    }
2090                }
2091            }
2092        }
2093    }
2094}
2095
2096/// Hash-join two BGP relations on the slots they share. Every left row binds
2097/// exactly the slots accumulated so far and every right row binds the current
2098/// pattern's slots, so the shared set is uniform across rows.
2099fn hash_join(
2100    left: Vec<Row>,
2101    left_bound: &[usize],
2102    right: Vec<Row>,
2103    right_slots: &[usize],
2104) -> Vec<Row> {
2105    // Fast path: the all-unbound seed row joins to `right` unchanged.
2106    if left.len() == 1 && left_bound.is_empty() {
2107        return right;
2108    }
2109    if left.is_empty() || right.is_empty() {
2110        return Vec::new();
2111    }
2112    let shared: Vec<usize> = right_slots
2113        .iter()
2114        .copied()
2115        .filter(|s| left_bound.contains(s))
2116        .collect();
2117    let fill = |l: &Row, r: &Row| -> Row {
2118        let mut out = l.clone();
2119        for &s in right_slots {
2120            out[s] = r[s].clone();
2121        }
2122        out
2123    };
2124    if shared.is_empty() {
2125        // No shared variable: Cartesian product. In a connected BGP this only
2126        // arises for a fully-ground pattern (deduped index ⇒ one matching row),
2127        // so it acts as an existence filter rather than multiplying rows.
2128        let mut out = Vec::with_capacity(left.len() * right.len());
2129        for l in &left {
2130            for r in &right {
2131                out.push(fill(l, r));
2132            }
2133        }
2134        return out;
2135    }
2136    let key_of = |b: &Row| -> Vec<Val> { shared.iter().map(|&s| b[s].clone().unwrap()).collect() };
2137    // A hash join is symmetric on the shared key, so build the **smaller** side's
2138    // hash table and probe with the larger — same result set, fewer inserts and a
2139    // smaller table. (The old code always built `right`; after cardinality-based
2140    // ordering the accumulating `left` is usually the small selective side, so
2141    // building it instead is the common win.) Whichever side is built, the output
2142    // row carries every bound slot of both.
2143    let mut out = Vec::new();
2144    if right.len() <= left.len() {
2145        let mut buckets: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
2146        for r in right {
2147            buckets.entry(key_of(&r)).or_default().push(r);
2148        }
2149        for l in &left {
2150            if let Some(rs) = buckets.get(&key_of(l)) {
2151                for r in rs {
2152                    out.push(fill(l, r));
2153                }
2154            }
2155        }
2156    } else {
2157        // Build the left side; fill the left's own slots into each probed right.
2158        let mut buckets: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
2159        for l in left {
2160            buckets.entry(key_of(&l)).or_default().push(l);
2161        }
2162        for r in &right {
2163            if let Some(ls) = buckets.get(&key_of(r)) {
2164                for l in ls {
2165                    let mut row = r.clone();
2166                    for &s in left_bound {
2167                        if let Some(v) = &l[s] {
2168                            row[s] = Some(v.clone());
2169                        }
2170                    }
2171                    out.push(row);
2172                }
2173            }
2174        }
2175    }
2176    out
2177}
2178
2179// Constant-only index constraints. A variable scans as a wildcard (`Some(None)`)
2180// — it is resolved later by the hash join, not pushed into the scan. The outer
2181// `None` means "unsatisfiable" (a constant in an impossible role, or unknown to
2182// the dictionary), which empties the whole BGP. Inner `None` = "wildcard".
2183fn const_subject(t: &SlotTerm, d: &crate::Dictionary) -> Option<Option<u32>> {
2184    match t {
2185        SlotTerm::Node(n) => d.node_as_subject_id(*n).map(Some),
2186        SlotTerm::Pred(_) => None, // a predicate term can't be a subject
2187        SlotTerm::Var(_) => Some(None),
2188    }
2189}
2190
2191fn const_object(t: &SlotTerm, d: &crate::Dictionary) -> Option<Option<u32>> {
2192    match t {
2193        SlotTerm::Node(n) => d.node_as_object_id(*n).map(Some),
2194        SlotTerm::Pred(_) => None,
2195        SlotTerm::Var(_) => Some(None),
2196    }
2197}
2198
2199fn const_predicate(t: &SlotTerm) -> Option<Option<u32>> {
2200    match t {
2201        SlotTerm::Pred(p) => Some(Some(*p)),
2202        SlotTerm::Node(_) => None, // a node term can't be a predicate
2203        SlotTerm::Var(_) => Some(None),
2204    }
2205}
2206
2207#[cfg(test)]
2208mod tests {
2209    use super::*;
2210    use crate::dictionary::DictionaryBuilder;
2211    use crate::file::write_file_v05 as write_file;
2212    use crate::index::GraphIndexBuilder;
2213
2214    fn rete_from(triples: &[(&str, &str, &str)]) -> Vec<u8> {
2215        let mut db = DictionaryBuilder::new();
2216        for (s, p, o) in triples {
2217            db.observe(s, p, o);
2218        }
2219        let dict = db.build();
2220        let mut ib = GraphIndexBuilder::new();
2221        for (s, p, o) in triples {
2222            ib.push(dict.encode(s, p, o).unwrap());
2223        }
2224        write_file(&dict, &ib.build(), false, &[], 0)
2225    }
2226
2227    fn pat(s: &str, p: &str, o: &str) -> TriplePattern {
2228        TriplePattern {
2229            s: PatternTerm::parse(s),
2230            p: PatternTerm::parse(p),
2231            o: PatternTerm::parse(o),
2232        }
2233    }
2234
2235    /// The scan-bytes figure (`rete cost`'s preview, and through 0.3.7 the
2236    /// merge-join and fat-side gates) routes a bound term by its id IN ITS
2237    /// ROLE. It used to route the unified node id,
2238    /// which for an object-only term (any literal) is shifted past the whole
2239    /// subject-only block: `?s :value "lit"` found no OPS tile at all, cost
2240    /// "0 bytes", and so let a merge join materialize its partner in full —
2241    /// on OpenCitations, every DOI identifier of a 2.9 B-triple file, behind
2242    /// `?id :hasLiteralValue "10.…" ; :usesIdentifierScheme :doi`.
2243    #[test]
2244    fn scan_bytes_route_a_literal_by_its_object_id() {
2245        let value = "<http://ex/value>";
2246        let owned: Vec<(String, String)> = (0..400)
2247            .map(|i| (format!("<http://ex/s{i:03}>"), format!("\"lit {i:03}\"")))
2248            .collect();
2249        let mut db = DictionaryBuilder::new();
2250        for (s, o) in &owned {
2251            db.observe(s, value, o);
2252        }
2253        let dict = db.build();
2254        let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2255        for (s, o) in &owned {
2256            ib.push(dict.encode(s, value, o).unwrap());
2257        }
2258        let rete = Rete::open(&write_file(&dict, &ib.build(), false, &[], 0)).unwrap();
2259        let index = rete.default_index();
2260        // The whole predicate, the most a bound object could ever cost.
2261        let whole = routed_scan_bytes(index, (None, rete.dictionary().predicate_id(value), None));
2262        for (_, lit) in owned.iter().step_by(57) {
2263            let q = [pat("?s", value, lit)];
2264            let mut slots = Slots::new();
2265            collect_pattern_slots(&q, &mut slots);
2266            let ctx = Ctx::new(&rete, slots);
2267            let got = bgp_min_scan_bytes(&ctx, index, &q).unwrap();
2268            assert!(got > 0, "{lit} routed to no tile");
2269            assert!(
2270                got < whole,
2271                "{lit} routed to the whole predicate ({got} of {whole})"
2272            );
2273        }
2274    }
2275
2276    /// The planner's size gates read ROW estimates, which do not depend on how
2277    /// the tiles are compressed. The same file opened resident (tile sizes are
2278    /// the decoded images) and lazily (tile sizes are the compressed frames)
2279    /// reports different bytes but must take the same decisions — the byte
2280    /// gates this replaced flipped plans when only the zstd level changed.
2281    #[test]
2282    fn plan_gates_do_not_move_with_the_compression() {
2283        let mut owned: Vec<(String, String, String)> = Vec::new();
2284        for i in 0..3000 {
2285            let s = format!("<http://ex/s{i}>");
2286            owned.push((
2287                s.clone(),
2288                "<http://ex/kind>".into(),
2289                format!("<http://ex/K{}>", i % 7),
2290            ));
2291            owned.push((s.clone(), "<http://ex/value>".into(), format!("\"v {i}\"")));
2292            if i % 50 == 0 {
2293                owned.push((s, "<http://ex/rare>".into(), "<http://ex/R>".into()));
2294            }
2295        }
2296        let mut db = DictionaryBuilder::new();
2297        for (s, p, o) in &owned {
2298            db.observe(s, p, o);
2299        }
2300        let dict = db.build();
2301        let mut ib = GraphIndexBuilder::new().with_tile_budget(1024);
2302        for (s, p, o) in &owned {
2303            ib.push(dict.encode(s, p, o).unwrap());
2304        }
2305        let bytes = write_file(&dict, &ib.build(), false, &[], 0);
2306        let leaked: &'static [u8] = Box::leak(bytes.clone().into_boxed_slice());
2307        let resident = Rete::open(&bytes).unwrap();
2308        let lazy = Rete::open_ranged_lazy(crate::reader::SliceReader::new(leaked)).unwrap();
2309        let shapes: Vec<Vec<TriplePattern>> = vec![
2310            vec![
2311                pat("?s", "<http://ex/rare>", "<http://ex/R>"),
2312                pat("?s", "<http://ex/value>", "?v"),
2313            ],
2314            vec![
2315                pat("?s", "<http://ex/kind>", "<http://ex/K3>"),
2316                pat("?s", "<http://ex/value>", "?v"),
2317            ],
2318            vec![
2319                pat("?s", "<http://ex/kind>", "?k"),
2320                pat("?s", "<http://ex/value>", "?v"),
2321            ],
2322            vec![
2323                pat("?s", "<http://ex/value>", "\"v 7\""),
2324                pat("?s", "<http://ex/kind>", "?k"),
2325            ],
2326        ];
2327        let decisions = |rete: &Rete| -> Vec<(Vec<u64>, bool, Option<u64>)> {
2328            shapes
2329                .iter()
2330                .map(|q| {
2331                    let mut slots = Slots::new();
2332                    collect_pattern_slots(q, &mut slots);
2333                    let ctx = Ctx::new(rete, slots);
2334                    let index = rete.default_index();
2335                    let lowered = lower(q, &ctx).unwrap();
2336                    let est = tile_estimates(&ctx, index, &lowered, &Default::default());
2337                    let lopsided = merge_seed_lopsided(&ctx, index, &lowered[0], &lowered[1]);
2338                    let min = bgp_min_estimate(&ctx, index, q).map(|e| e as u64);
2339                    (est.iter().map(|e| *e as u64).collect(), lopsided, min)
2340                })
2341                .collect()
2342        };
2343        assert_eq!(decisions(&resident), decisions(&lazy));
2344        // ... while the byte figures the gates used to read do differ.
2345        #[cfg(feature = "compression")]
2346        {
2347            let bytes_of = |rete: &Rete| {
2348                let q = &shapes[2];
2349                let mut slots = Slots::new();
2350                collect_pattern_slots(q, &mut slots);
2351                let ctx = Ctx::new(rete, slots);
2352                bgp_min_scan_bytes(&ctx, rete.default_index(), q)
2353            };
2354            assert_ne!(bytes_of(&resident), bytes_of(&lazy));
2355        }
2356    }
2357
2358    /// A fat predicate must look fat whichever layout stores the directory.
2359    /// On format 0x06 the tile directory is two-level and a leaf that is not
2360    /// resident is estimated from the root alone; it used to count as ONE
2361    /// tile, so a 2-million-row `rdfs:label` read as ~7 thousand rows on 0x06
2362    /// and 2 million on 0x05 — and the OPTIONAL joined to a 1000-row left side
2363    /// was hash-joined (the whole predicate materialized: 14.5 GB on a 8 B
2364    /// triple file) instead of probed per row. The same file in both layouts
2365    /// must give estimates of the same order, and the probe decision must be
2366    /// the same one.
2367    #[test]
2368    fn a_fat_predicate_estimates_alike_in_both_layouts() {
2369        let mut owned: Vec<(String, String, String)> = Vec::new();
2370        for i in 0..120_000 {
2371            let s = format!("<http://ex/s{i:06}>");
2372            owned.push((s.clone(), "<http://ex/kind>".into(), "<http://ex/K>".into()));
2373            owned.push((s, "<http://ex/value>".into(), format!("\"v {i}\"")));
2374        }
2375        let mut db = DictionaryBuilder::new();
2376        for (s, p, o) in &owned {
2377            db.observe(s, p, o);
2378        }
2379        let dict = db.build();
2380        let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2381        for (s, p, o) in &owned {
2382            ib.push(dict.encode(s, p, o).unwrap());
2383        }
2384        let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2385        let v6: &'static [u8] = Box::leak(
2386            crate::v06::write::convert_image(&v5, Default::default())
2387                .unwrap()
2388                .into_boxed_slice(),
2389        );
2390        let leaked5: &'static [u8] = Box::leak(v5.clone().into_boxed_slice());
2391        let flat = Rete::open_ranged_lazy(crate::reader::SliceReader::new(leaked5)).unwrap();
2392        let leafed = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v6)).unwrap();
2393        let q = [pat("?s", "<http://ex/value>", "?v")];
2394        let figures = |rete: &Rete| {
2395            let mut slots = Slots::new();
2396            collect_pattern_slots(&q, &mut slots);
2397            let ctx = Ctx::new(rete, slots);
2398            let index = rete.default_index();
2399            let total = bgp_total_estimate(&ctx, index, &q).unwrap();
2400            (total, probe_row_budget(total))
2401        };
2402        let (est5, budget5) = figures(&flat);
2403        let (est6, budget6) = figures(&leafed);
2404        assert!(est5 >= 70_000.0, "flat estimate {est5}");
2405        assert!(
2406            est6 >= est5 / 2.0 && est6 <= est5 * 2.0,
2407            "0x06 estimates {est6} where 0x05 estimates {est5}"
2408        );
2409        // The decision: a 1000-row left side probes in both.
2410        assert!(budget5.is_some_and(|b| b >= 1000), "{budget5:?}");
2411        assert!(budget6.is_some_and(|b| b >= 1000), "{budget6:?}");
2412    }
2413
2414    /// A selective object on a fat leading predicate must estimate small in
2415    /// both layouts: `?s rdf:type <rare class>` is a few tiles of a predicate
2416    /// that fills thousands, and the planner seeds the join from it. On 0x06 a
2417    /// leaf that is not resident used to be estimated without the bound object
2418    /// (the whole of `rdf:type`) or by the ids' average share of its leaf
2419    /// (skewed ids put a rare class beside a huge one).
2420    #[test]
2421    fn a_rare_object_of_a_fat_predicate_estimates_small_in_both_layouts() {
2422        let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2423        let mut owned: Vec<(String, String, String)> = Vec::new();
2424        for i in 0..120_000 {
2425            let s = format!("<http://ex/s{i:06}>");
2426            owned.push((s.clone(), ty.into(), "<http://ex/Common>".into()));
2427            owned.push((s.clone(), "<http://ex/other>".into(), format!("\"o {i}\"")));
2428            if i % 3000 == 0 {
2429                owned.push((s, ty.into(), "<http://ex/Rare>".into()));
2430            }
2431        }
2432        let mut db = DictionaryBuilder::new();
2433        for (s, p, o) in &owned {
2434            db.observe(s, p, o);
2435        }
2436        let dict = db.build();
2437        let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2438        for (s, p, o) in &owned {
2439            ib.push(dict.encode(s, p, o).unwrap());
2440        }
2441        let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2442        let v6: &'static [u8] = Box::leak(
2443            crate::v06::write::convert_image(&v5, Default::default())
2444                .unwrap()
2445                .into_boxed_slice(),
2446        );
2447        let leaked5: &'static [u8] = Box::leak(v5.into_boxed_slice());
2448        let figures = |rete: &Rete| {
2449            let est = |q: &[TriplePattern]| {
2450                let mut slots = Slots::new();
2451                collect_pattern_slots(q, &mut slots);
2452                let ctx = Ctx::new(rete, slots);
2453                bgp_min_estimate(&ctx, rete.default_index(), q).unwrap()
2454            };
2455            (
2456                est(&[pat("?s", ty, "<http://ex/Rare>")]),
2457                est(&[pat("?s", ty, "<http://ex/Common>")]),
2458                est(&[pat("?s", "<http://ex/other>", "?x")]),
2459            )
2460        };
2461        for (name, bytes) in [("0x05", leaked5), ("0x06", v6)] {
2462            let rete = Rete::open_ranged_lazy(crate::reader::SliceReader::new(bytes)).unwrap();
2463            let (rare, common, other) = figures(&rete);
2464            assert!(rare * 20.0 < other, "{name}: rare {rare} vs other {other}");
2465            assert!(
2466                rare * 20.0 < common,
2467                "{name}: rare {rare} vs common {common}"
2468            );
2469        }
2470    }
2471
2472    /// A probe prefetch covers a bounded window of its patterns — at most
2473    /// [`PROBE_WINDOW_TILES`] tiles — and leaves the rest for the next call, so
2474    /// a long list of probes never faults more tiles than the cache holds (the
2475    /// whole list at once evicted the early tiles before their probes ran, and
2476    /// each came back as a request of its own: G50a). What a window covers is
2477    /// resident: probing it reads nothing more.
2478    #[test]
2479    fn a_probe_prefetch_window_is_bounded_and_warm() {
2480        use crate::reader::{CountingReader, SliceReader};
2481        let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2482        let mut owned: Vec<(String, String, String)> = Vec::new();
2483        for i in 0..20_000 {
2484            let s = format!("<http://ex/s{i:06}>");
2485            owned.push((s.clone(), ty.into(), format!("<http://ex/C{}>", i % 7)));
2486            owned.push((s, "<http://ex/other>".into(), format!("\"o {}\"", i % 5000)));
2487        }
2488        let mut db = DictionaryBuilder::new();
2489        for (s, p, o) in &owned {
2490            db.observe(s, p, o);
2491        }
2492        let dict = db.build();
2493        let mut ib = GraphIndexBuilder::new().with_tile_budget(128);
2494        for (s, p, o) in &owned {
2495            ib.push(dict.encode(s, p, o).unwrap());
2496        }
2497        let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2498        let v6 = crate::v06::write::convert_image(&v5, Default::default()).unwrap();
2499        let leaked: &'static [u8] = Box::leak(v6.into_boxed_slice());
2500        let reader = std::sync::Arc::new(CountingReader::new(SliceReader::new(leaked)));
2501        let rete = Rete::open_ranged_lazy(reader.clone()).unwrap();
2502        let index = rete.default_index();
2503        // A cache far smaller than the tiles the probes touch: a prefetch of every
2504        // probe at once would evict its own early tiles.
2505        index.set_cache_cap(1 << 20);
2506        // Every third subject, as the probes of a long join.
2507        let pats: Vec<Pattern> = (0..20_000)
2508            .step_by(3)
2509            .map(|i| {
2510                let (s, _, _) = dict
2511                    .encode(&format!("<http://ex/s{i:06}>"), ty, "<http://ex/C0>")
2512                    .unwrap();
2513                (Some(s), None, None)
2514            })
2515            .collect();
2516        let mut from = 0;
2517        let mut windows = 0;
2518        while from < pats.len() {
2519            let n = index.prefetch_probe_tiles(&pats[from..]);
2520            assert!(n >= 1, "a window always makes progress");
2521            assert!(
2522                n < pats.len() - from || windows > 0,
2523                "the first window is cut"
2524            );
2525            let before = reader.requests();
2526            for &p in &pats[from..from + n] {
2527                assert!(index.scan_iter(p).next().is_some());
2528            }
2529            assert_eq!(reader.requests(), before, "a covered probe reads nothing");
2530            from += n;
2531            windows += 1;
2532        }
2533        assert!(windows > 1, "{windows} window(s) for {} probes", pats.len());
2534    }
2535
2536    /// The run of tiles holding a leading id is the same in both layouts, for
2537    /// every id and every permutation, and a leafed lookup does not walk the
2538    /// leaf tile by tile (a probe join runs it per row: 94,700 probes took 126 s
2539    /// on a 0x06 file against 1.3 s on its 0x05 copy).
2540    #[test]
2541    fn a_tile_span_is_the_same_in_both_layouts() {
2542        let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2543        let mut owned: Vec<(String, String, String)> = Vec::new();
2544        for i in 0..30_000 {
2545            let s = format!("<http://ex/s{i:06}>");
2546            owned.push((s.clone(), ty.into(), format!("<http://ex/C{}>", i % 7)));
2547            owned.push((s, "<http://ex/other>".into(), format!("\"o {}\"", i % 5000)));
2548        }
2549        let mut db = DictionaryBuilder::new();
2550        for (s, p, o) in &owned {
2551            db.observe(s, p, o);
2552        }
2553        let dict = db.build();
2554        let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2555        for (s, p, o) in &owned {
2556            ib.push(dict.encode(s, p, o).unwrap());
2557        }
2558        let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2559        let v6 = crate::v06::write::convert_image(&v5, Default::default()).unwrap();
2560        let (v5, v6): (&'static [u8], &'static [u8]) = (
2561            Box::leak(v5.into_boxed_slice()),
2562            Box::leak(v6.into_boxed_slice()),
2563        );
2564        let flat = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v5)).unwrap();
2565        let leafed = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v6)).unwrap();
2566        let (fi, li) = (flat.default_index(), leafed.default_index());
2567        let mut checked = 0;
2568        for perm in fi.perms().iter() {
2569            let si = perm.section_index();
2570            for a in (0..dict.term_count() + 2).step_by(97) {
2571                assert_eq!(
2572                    fi.tile_span(si, Some(a)),
2573                    li.tile_span(si, Some(a)),
2574                    "section {si}, id {a}"
2575                );
2576                checked += 1;
2577            }
2578            assert_eq!(fi.tile_span(si, None), li.tile_span(si, None));
2579        }
2580        assert!(checked > 100);
2581    }
2582
2583    /// Every join path the planner can pick — materialized prefix, probed last
2584    /// pattern, streamed seed with hashed or probed later patterns, streaming
2585    /// merge join — returns the same solution multiset. The thresholds are
2586    /// shrunk so a 400-triple graph takes each path.
2587    #[test]
2588    fn every_join_path_returns_the_same_solutions() {
2589        let mut owned: Vec<(String, String, String)> = Vec::new();
2590        let mut x: u64 = 7;
2591        let mut next = |m: u64| {
2592            x = x
2593                .wrapping_mul(6364136223846793005)
2594                .wrapping_add(1442695040888963407);
2595            (x >> 33) % m
2596        };
2597        for i in 0..60 {
2598            let s = format!("s{i}");
2599            owned.push((s.clone(), "a".into(), format!("C{}", next(3))));
2600            for p in 0..4 {
2601                for _ in 0..next(3) {
2602                    owned.push((s.clone(), format!("p{p}"), format!("s{}", next(60))));
2603                }
2604            }
2605        }
2606        let triples: Vec<(&str, &str, &str)> = owned
2607            .iter()
2608            .map(|(s, p, o)| (s.as_str(), p.as_str(), o.as_str()))
2609            .collect();
2610        let bytes = rete_from(&triples);
2611        let rete = Rete::open(&bytes).unwrap();
2612        let queries: Vec<Vec<TriplePattern>> = vec![
2613            vec![pat("?s", "p0", "?a"), pat("?s", "p1", "?b")],
2614            vec![pat("?s", "a", "C1"), pat("?s", "p0", "?a")],
2615            vec![pat("?s", "p0", "?a"), pat("?a", "p2", "?b")],
2616            vec![pat("s5", "p0", "?a"), pat("?a", "?p", "?o")],
2617            vec![pat("?s", "p0", "?x"), pat("?s", "p1", "?x")],
2618            vec![
2619                pat("?s", "p3", "?o"),
2620                pat("?o", "a", "C0"),
2621                pat("?s", "p1", "?z"),
2622            ],
2623            vec![
2624                pat("?s", "p0", "?a"),
2625                pat("?s", "p1", "?b"),
2626                pat("?b", "p2", "?c"),
2627            ],
2628        ];
2629        let run = |limits: Option<PlanLimits>| -> Vec<Vec<Vec<(String, String)>>> {
2630            TEST_LIMITS.with(|c| c.set(limits));
2631            let out = queries
2632                .iter()
2633                .map(|q| {
2634                    let mut slots = crate::row::Slots::new();
2635                    collect_pattern_slots(q, &mut slots);
2636                    let ctx = Ctx::new(&rete, slots);
2637                    let mut rows: Vec<Vec<(String, String)>> =
2638                        BgpSolutions::new(&ctx, rete.default_index(), q)
2639                            .map(|r| row_to_binding(&ctx, &r).into_iter().collect())
2640                            .collect();
2641                    rows.sort();
2642                    rows
2643                })
2644                .collect();
2645            TEST_LIMITS.with(|c| c.set(None));
2646            out
2647        };
2648        let reference = run(None);
2649        assert!(reference.iter().all(|r| !r.is_empty()), "{reference:?}");
2650        for (name, l) in [
2651            (
2652                "probe everything",
2653                PlanLimits {
2654                    probe_floor: 0.0,
2655                    stream_seed: f64::MAX,
2656                    hash_build: f64::MAX,
2657                },
2658            ),
2659            (
2660                "stream + hash",
2661                PlanLimits {
2662                    probe_floor: f64::MAX,
2663                    stream_seed: 0.0,
2664                    hash_build: f64::MAX,
2665                },
2666            ),
2667            (
2668                "stream + probe",
2669                PlanLimits {
2670                    probe_floor: f64::MAX,
2671                    stream_seed: 0.0,
2672                    hash_build: 0.0,
2673                },
2674            ),
2675            (
2676                "stream, all paths",
2677                PlanLimits {
2678                    probe_floor: 0.0,
2679                    stream_seed: 0.0,
2680                    hash_build: 30.0,
2681                },
2682            ),
2683        ] {
2684            assert_eq!(run(Some(l)), reference, "{name}");
2685        }
2686    }
2687
2688    #[test]
2689    fn single_pattern_binds_variable() {
2690        let bytes = rete_from(&[("Alice", "knows", "Bob"), ("Bob", "knows", "Carol")]);
2691        let rete = Rete::open(&bytes).unwrap();
2692        let sols = eval_bgp(&rete, &[pat("Alice", "knows", "?y")]);
2693        assert_eq!(sols.len(), 1);
2694        assert_eq!(sols[0]["y"], "Bob");
2695    }
2696
2697    #[test]
2698    fn two_hop_join_on_shared_variable() {
2699        // Alice -> Bob -> Carol, plus a dead-end branch.
2700        let bytes = rete_from(&[
2701            ("Alice", "knows", "Bob"),
2702            ("Bob", "knows", "Carol"),
2703            ("Carol", "knows", "Dave"),
2704            ("Alice", "knows", "Eve"), // Eve knows no one -> no 2-hop
2705        ]);
2706        let rete = Rete::open(&bytes).unwrap();
2707        let sols = eval_bgp(&rete, &[pat("?x", "knows", "?y"), pat("?y", "knows", "?z")]);
2708        // Alice-Bob-Carol, Bob-Carol-Dave.
2709        let mut got: Vec<_> = sols
2710            .iter()
2711            .map(|b| (b["x"].clone(), b["y"].clone(), b["z"].clone()))
2712            .collect();
2713        got.sort();
2714        assert_eq!(
2715            got,
2716            vec![
2717                ("Alice".into(), "Bob".into(), "Carol".into()),
2718                ("Bob".into(), "Carol".into(), "Dave".into()),
2719            ]
2720        );
2721    }
2722
2723    #[test]
2724    fn repeated_variable_within_pattern() {
2725        // A mutual/self relation: only Bob knows himself.
2726        let bytes = rete_from(&[("Alice", "knows", "Bob"), ("Bob", "knows", "Bob")]);
2727        let rete = Rete::open(&bytes).unwrap();
2728        let sols = eval_bgp(&rete, &[pat("?x", "knows", "?x")]);
2729        assert_eq!(sols.len(), 1);
2730        assert_eq!(sols[0]["x"], "Bob");
2731    }
2732
2733    #[test]
2734    fn no_solutions_yields_empty() {
2735        let bytes = rete_from(&[("Alice", "knows", "Bob")]);
2736        let rete = Rete::open(&bytes).unwrap();
2737        assert!(eval_bgp(&rete, &[pat("Alice", "likes", "?y")]).is_empty());
2738    }
2739
2740    /// A LUBM-Q7-shaped snowflake: a popular class enumeration (`?x a Student`)
2741    /// plus a selective adjacency seed (`<Prof> teacherOf ?y`). Exercises both the
2742    /// **class-enum seed deprioritization** (the join must not start from the huge
2743    /// `a Student` extent) and the **probe-the-tail hybrid** (the type checks are
2744    /// applied late, per row). The answer must equal a brute-force computation
2745    /// regardless of how the join is ordered/probed.
2746    #[test]
2747    fn snowflake_type_and_adjacency_matches_reference() {
2748        const TYPE: &str = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2749        let mut triples: Vec<(String, String, String)> = Vec::new();
2750        // 60 students, each a Student and taking 2 courses (c{i%5}, c{(i+1)%5}).
2751        for i in 0..60 {
2752            let s = format!("S{i}");
2753            triples.push((s.clone(), TYPE.into(), "Student".into()));
2754            triples.push((s.clone(), "takesCourse".into(), format!("c{}", i % 5)));
2755            triples.push((s, "takesCourse".into(), format!("c{}", (i + 1) % 5)));
2756        }
2757        // 5 courses; the professor teaches only c0 and c2.
2758        for j in 0..5 {
2759            triples.push((format!("c{j}"), TYPE.into(), "Course".into()));
2760        }
2761        triples.push(("Prof".into(), "teacherOf".into(), "c0".into()));
2762        triples.push(("Prof".into(), "teacherOf".into(), "c2".into()));
2763
2764        let refs: Vec<(&str, &str, &str)> = triples
2765            .iter()
2766            .map(|(s, p, o)| (s.as_str(), p.as_str(), o.as_str()))
2767            .collect();
2768        let bytes = rete_from(&refs);
2769        let rete = Rete::open(&bytes).unwrap();
2770
2771        let got: std::collections::BTreeSet<(String, String)> = eval_bgp(
2772            &rete,
2773            &[
2774                pat("?x", TYPE, "Student"),
2775                pat("?y", TYPE, "Course"),
2776                pat("?x", "takesCourse", "?y"),
2777                pat("Prof", "teacherOf", "?y"),
2778            ],
2779        )
2780        .into_iter()
2781        .map(|b| (b["x"].clone(), b["y"].clone()))
2782        .collect();
2783
2784        // Brute force: students taking a course the professor teaches (c0 or c2).
2785        let taught = ["c0", "c2"];
2786        let mut want = std::collections::BTreeSet::new();
2787        for i in 0..60 {
2788            for c in [i % 5, (i + 1) % 5] {
2789                let course = format!("c{c}");
2790                if taught.contains(&course.as_str()) {
2791                    want.insert((format!("S{i}"), course));
2792                }
2793            }
2794        }
2795        assert_eq!(got, want, "snowflake join must match the brute-force set");
2796        assert!(!want.is_empty(), "sanity: the reference set is non-empty");
2797    }
2798
2799    /// A subject-subject join (`?x a ?av . ?x b ?bv`) is the same-role shape the
2800    /// merge join handles: both patterns sort on the subject column. With multiple
2801    /// `a` and `b` values per subject it must emit the full cross product per
2802    /// subject (equal-key run handling) and drop subjects missing either side.
2803    #[test]
2804    fn merge_join_subject_star_cross_product() {
2805        let bytes = rete_from(&[
2806            ("x", "a", "a1"),
2807            ("x", "a", "a2"),
2808            ("x", "b", "b1"),
2809            ("x", "b", "b2"),
2810            ("y", "a", "a3"),
2811            ("y", "b", "b3"),
2812            ("z", "a", "a4"), // z has no `b` → contributes no join row
2813        ]);
2814        let rete = Rete::open(&bytes).unwrap();
2815        let mut got: Vec<(String, String, String)> =
2816            eval_bgp(&rete, &[pat("?x", "a", "?av"), pat("?x", "b", "?bv")])
2817                .iter()
2818                .map(|m| (m["x"].clone(), m["av"].clone(), m["bv"].clone()))
2819                .collect();
2820        got.sort();
2821        let mut want: Vec<(String, String, String)> = [
2822            ("x", "a1", "b1"),
2823            ("x", "a1", "b2"),
2824            ("x", "a2", "b1"),
2825            ("x", "a2", "b2"),
2826            ("y", "a3", "b3"),
2827        ]
2828        .into_iter()
2829        .map(|(a, b, c)| (a.to_string(), b.to_string(), c.to_string()))
2830        .collect();
2831        want.sort();
2832        assert_eq!(got, want, "same-role merge must equal the brute-force join");
2833    }
2834}