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(all(test, feature = "http"))]
558pub(crate) fn with_plan_limits<T>(
559    probe_floor: f64,
560    stream_seed: f64,
561    hash_build: f64,
562    f: impl FnOnce() -> T,
563) -> T {
564    let saved = TEST_LIMITS.with(|c| c.get());
565    TEST_LIMITS.with(|c| {
566        c.set(Some(PlanLimits {
567            probe_floor,
568            stream_seed,
569            hash_build,
570        }))
571    });
572    let out = f();
573    TEST_LIMITS.with(|c| c.set(saved));
574    out
575}
576
577/// The planner's size thresholds, gathered so tests can shrink them and drive
578/// every join path over a graph small enough to check by hand.
579#[derive(Clone, Copy)]
580struct PlanLimits {
581    probe_floor: f64,
582    stream_seed: f64,
583    hash_build: f64,
584}
585
586#[cfg(test)]
587thread_local! {
588    static TEST_LIMITS: std::cell::Cell<Option<PlanLimits>> = const { std::cell::Cell::new(None) };
589}
590
591fn limits() -> PlanLimits {
592    #[cfg(test)]
593    if let Some(l) = TEST_LIMITS.with(|c| c.get()) {
594        return l;
595    }
596    PlanLimits {
597        probe_floor: PROBE_SCAN_FLOOR,
598        stream_seed: STREAM_SEED_ROWS,
599        hash_build: HASH_BUILD_ROWS,
600    }
601}
602
603/// A BGP whose most selective pattern is estimated above this many matches is
604/// **streamed** rather than joined into a materialized prefix
605/// ([`BgpSolutions`]): every later pattern is then joined per row (probe) or
606/// against a small materialized pattern (hash), so resident memory no longer
607/// follows the largest pattern. `?s dcite:doi ?d . ?s dcite:fromSnapshot ?x`
608/// materialized 109 M rows before joining and ran a 16 GB container out of
609/// memory.
610const STREAM_SEED_ROWS: f64 = (1u64 << 21) as f64;
611
612/// On the streaming path, a later pattern estimated at no more than this many
613/// matches is scanned once into a hash table; a larger one is probed per row.
614const HASH_BUILD_ROWS: f64 = (1u64 << 20) as f64;
615
616/// Tile-directory cardinality estimates ([`GraphIndex::estimate_matches`]) for
617/// each lowered pattern. A variable an outer seed row binds is a constant at
618/// run time but unknown now: it scales the estimate by the same default
619/// selectivities [`pattern_estimates`] falls back to. An unsatisfiable
620/// constant estimates 0.
621fn tile_estimates(
622    ctx: &Ctx,
623    index: &GraphIndex,
624    lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
625    seed: &std::collections::HashSet<usize>,
626) -> Vec<f64> {
627    const SEL_SUBJECT: f64 = 0.001;
628    const SEL_OBJECT: f64 = 0.02;
629    const SEL_PREDICATE: f64 = 0.05;
630    let dict = ctx.rete.dictionary();
631    let total = ctx.rete.index_triples(index);
632    let seeded = |x: &SlotTerm| matches!(x, SlotTerm::Var(v) if seed.contains(v));
633    // A seeded subject/object of a constant predicate takes that predicate's
634    // MEASURED selectivity from `query_stats` (the SCHEMA section, kind 9, or
635    // a resident pyramid-meta) instead of the fixed default. The tile
636    // directory cannot see a value that only exists at run time, so this is
637    // the one estimate here the statistics improve. They are read only when
638    // some pattern needs them: one small range, once per session, on a lazy
639    // open — never for a query whose patterns have no seeded position.
640    let needs_stats = lowered
641        .iter()
642        .any(|t| matches!(t.1, SlotTerm::Pred(_)) && (seeded(&t.0) || seeded(&t.2)));
643    let stats: std::collections::HashMap<u32, &crate::meta::PredStat> = if needs_stats {
644        ctx.rete
645            .planner_stats(true)
646            .iter()
647            .map(|s| (s.predicate, s))
648            .collect()
649    } else {
650        std::collections::HashMap::new()
651    };
652    // Each pattern is estimated on every permutation that leads with a bound id,
653    // reading the directory leaves its run starts and ends in: fault them all
654    // for all the patterns at once, not one permutation after another.
655    let patterns: Vec<Pattern> = lowered
656        .iter()
657        .filter_map(|t| {
658            Some((
659                const_subject(&t.0, dict)?,
660                const_predicate(&t.1)?,
661                const_object(&t.2, dict)?,
662            ))
663        })
664        .collect();
665    index.prefault_estimate_leaves(&patterns);
666    lowered
667        .iter()
668        .map(|t| {
669            let (Some(s), Some(p), Some(o)) = (
670                const_subject(&t.0, dict),
671                const_predicate(&t.1),
672                const_object(&t.2, dict),
673            ) else {
674                return 0.0;
675            };
676            let mut est = index.estimate_matches((s, p, o), total);
677            if est == 0.0 {
678                return 0.0;
679            }
680            let st = match t.1 {
681                SlotTerm::Pred(pid) => stats.get(&pid).copied(),
682                _ => None,
683            };
684            if seeded(&t.0) {
685                est *= match st {
686                    Some(st) if st.distinct_subjects > 0 => 1.0 / st.distinct_subjects as f64,
687                    _ => SEL_SUBJECT,
688                };
689            }
690            if seeded(&t.1) {
691                est *= SEL_PREDICATE;
692            }
693            if seeded(&t.2) {
694                est *= match st {
695                    Some(st) if st.distinct_objects > 0 => 1.0 / st.distinct_objects as f64,
696                    _ => SEL_OBJECT,
697                };
698            }
699            est.max(1.0)
700        })
701        .collect()
702}
703
704/// Remote (lazy) probe bounds. Over HTTP byte-range reads, a per-row probe is a
705/// network round-trip, so we probe far more reluctantly than in memory: only when
706/// scanning the next pattern would be a *broad* read (a whole-predicate scan,
707/// [`pattern_is_selective`] is false), or the prefix is tiny enough that a handful
708/// of probes is trivial either way. A pattern that carries its own bound
709/// subject/object routes to a narrow index range — cheaper to scan once and
710/// hash-join than to probe per prefix row. Probing a large prefix is always a
711/// loss remotely, so it is capped.
712const REMOTE_PROBE_MIN: usize = 8;
713const REMOTE_PROBE_MAX: usize = 1024;
714
715/// The remote probe budget, widened by the reader's concurrency: a serial
716/// sync-XHR reader (a phone without the COI pool) pays one full round trip per
717/// probe, so its budget stays at [`REMOTE_PROBE_MAX`]; a reader overlapping
718/// 16 range reads (the CLI's thread pool, the asyncified fetch variant, the
719/// COI fetch-worker pool) amortizes ~16 probes per round trip and gets a
720/// proportionally larger budget before the one-pass scan wins again.
721fn remote_probe_max(index: &GraphIndex) -> usize {
722    REMOTE_PROBE_MAX * index.read_concurrency().clamp(1, 16)
723}
724
725/// The rows a first [`Windowed`] window holds: few enough that a `LIMIT 1` or an
726/// `ASK` that stops after one row costs at most a few parallel reads.
727const WINDOW_START_ROWS: usize = 256;
728
729/// The most rows one [`Windowed`] window holds. The window doubles from
730/// [`WINDOW_START_ROWS`] (times four) up to this; the tile and byte bound of
731/// [`ProbeBatch`] cuts it shorter where the rows' tiles are many or large.
732const WINDOW_MAX_ROWS: usize = 1 << 16;
733
734/// Rows pulled and routed together while a window fills: their directory
735/// leaves are faulted in one read.
736const WINDOW_CHUNK_ROWS: usize = 256;
737
738/// How a row becomes the pattern its probe will run.
739type ProbePattern<'a> = Box<dyn Fn(&Row) -> Option<Pattern> + 'a>;
740
741/// A stream of rows about to be **probed** against a remote index, handed on
742/// unchanged and in order, with each window's tiles faulted in one coalesced,
743/// parallel read ([`GraphIndex::probe_batch_fault`]) just before the window is
744/// consumed.
745///
746/// A probe join over a lazy reader otherwise faults one tile per probe, one
747/// round trip at a time (the lazy streaming join did exactly that), or — when
748/// the whole prefix was prefetched at once — faulted more tiles than the tile
749/// cache holds, so the early ones were evicted before their probes ran and
750/// came back one request each (G50a: 15,539 requests at 0.12 s for a 221,817
751/// row prefix). A window grows until its tiles fill a [`ProbeBatch`] (tiles and
752/// stored bytes, within the cache budget), so the reader's fan-out is used (up
753/// to `read_concurrency` requests in flight) and memory stays bounded; it
754/// starts small and grows fourfold, so a demand-bounded consumer reads only a little
755/// past what it uses.
756///
757/// A local index has nothing to fault: the stream passes through untouched.
758pub(crate) struct Windowed<'a> {
759    index: &'a GraphIndex,
760    upstream: Box<dyn Iterator<Item = Row> + 'a>,
761    /// `None`: pass through (a local index).
762    pat_of: Option<ProbePattern<'a>>,
763    /// Pulled from upstream, not yet in a window.
764    pending: std::collections::VecDeque<Row>,
765    /// The window whose tiles were requested (or are resident): ready to probe.
766    ready: std::collections::VecDeque<Row>,
767    /// The next window's row cap.
768    size: usize,
769}
770
771/// Fault `rows`' probe tiles a window at a time as they are consumed.
772pub(crate) fn windowed<'a>(
773    index: &'a GraphIndex,
774    upstream: impl Iterator<Item = Row> + 'a,
775    pat_of: impl Fn(&Row) -> Option<Pattern> + 'a,
776) -> Windowed<'a> {
777    Windowed {
778        index,
779        upstream: Box::new(upstream),
780        pat_of: index.is_remote().then(|| {
781            let f: ProbePattern<'a> = Box::new(pat_of);
782            f
783        }),
784        pending: std::collections::VecDeque::new(),
785        ready: std::collections::VecDeque::new(),
786        size: WINDOW_START_ROWS,
787    }
788}
789
790impl Windowed<'_> {
791    /// Fill `ready` with the next window and fault its tiles.
792    fn refill(&mut self, pat_of: &dyn Fn(&Row) -> Option<Pattern>) {
793        let mut batch = ProbeBatch::default();
794        'window: while self.ready.len() < self.size {
795            let chunk = WINDOW_CHUNK_ROWS.min(self.size - self.ready.len());
796            while self.pending.len() < chunk {
797                match self.upstream.next() {
798                    Some(r) => self.pending.push_back(r),
799                    None => break,
800                }
801            }
802            if self.pending.is_empty() {
803                break;
804            }
805            let chunk = chunk.min(self.pending.len());
806            // One batched read for the chunk's directory leaves.
807            let pats: Vec<Pattern> = self.pending.iter().take(chunk).filter_map(pat_of).collect();
808            self.index.prefault_leaves(&pats);
809            for _ in 0..chunk {
810                if let Some(p) = pat_of(&self.pending[0]) {
811                    if !self.index.probe_batch_add(&mut batch, p) {
812                        break 'window; // the window is full: this row opens the next
813                    }
814                }
815                let row = self.pending.pop_front().expect("chunk rows are pending");
816                self.ready.push_back(row);
817            }
818        }
819        self.index.probe_batch_fault(batch);
820        self.size = (self.size * 4).min(WINDOW_MAX_ROWS);
821    }
822}
823
824impl Iterator for Windowed<'_> {
825    type Item = Row;
826
827    fn next(&mut self) -> Option<Row> {
828        // Taken out so `refill` can borrow `self` mutably, and put back.
829        let Some(pat_of) = self.pat_of.take() else {
830            return self.upstream.next();
831        };
832        if self.ready.is_empty() {
833            self.refill(pat_of.as_ref());
834        }
835        self.pat_of = Some(pat_of);
836        self.ready.pop_front()
837    }
838}
839
840/// The probe pattern a lowered triple pattern runs for `base`: every term the
841/// row binds is a constant. `None` when a bound value cannot take its role (the
842/// probe is empty), so there is nothing to fault.
843fn bgp_probe_pattern<'a>(
844    ctx: &'a Ctx<'_>,
845    t: (SlotTerm, SlotTerm, SlotTerm),
846) -> impl Fn(&Row) -> Option<Pattern> + 'a {
847    move |base| match (
848        probe_subject(ctx, &t.0, base),
849        probe_predicate(ctx, &t.1, base),
850        probe_object(ctx, &t.2, base),
851    ) {
852        (Some(s), Some(p), Some(o)) => Some((s, p, o)),
853        _ => None,
854    }
855}
856
857/// `rows` as the seeds of a [`ProbePlan`], with the tiles its FIRST pattern
858/// will route to faulted a window ahead ([`Windowed`]). Only the first pattern
859/// is prefetchable (later ones bind from earlier probe results), and only rows
860/// whose seed binds that pattern's subject or object are included: a
861/// predicate-only pattern routes to the predicate's WHOLE span, which for the
862/// fat sides this path serves would prefetch the very extent the probe strategy
863/// exists to avoid.
864pub(crate) fn plan_windowed<'q>(
865    ctx: &'q Ctx<'q>,
866    index: &'q GraphIndex,
867    plan: &ProbePlan,
868    rows: Box<dyn Iterator<Item = Row> + 'q>,
869) -> Box<dyn Iterator<Item = Row> + 'q> {
870    let Some(&t) = plan.pats.first() else {
871        return rows;
872    };
873    if !index.is_remote() {
874        return rows;
875    }
876    let pat = bgp_probe_pattern(ctx, t);
877    let mut win = windowed(index, rows, move |base| {
878        pat(base).filter(|(s, _, o)| s.is_some() || o.is_some())
879    });
880    // A window is pulled whole before its first row comes out. Under a demand
881    // bound the first one holds no more than the bound: a sparse left side
882    // (a selective filter over a scan) otherwise has to yield 256 rows before
883    // a `LIMIT 25` sees the first (G33).
884    if let Some(demand) = ctx.limit_hint.get() {
885        win.size = win.size.min(demand.max(1));
886    }
887    Box::new(win)
888}
889
890/// Batch-fault the tiles that probing `patterns` from `subject_ids` (each
891/// bound onto the subject variable `sv`) will route to — one coalesced read
892/// per section instead of one round trip per candidate. Purely a cache
893/// warmer: correctness is untouched, and a local index is a no-op. Used by
894/// the FILTER-CONTAINS pushdown before it probes its candidate subjects.
895pub(crate) fn prefetch_subject_probes(
896    ctx: &Ctx,
897    index: &GraphIndex,
898    patterns: &[TriplePattern],
899    sv: &str,
900    subject_ids: &[u32],
901) {
902    if !index.is_remote() {
903        return;
904    }
905    let Some(lowered) = lower(patterns, ctx) else {
906        return;
907    };
908    let Some(slot) = ctx.slots.slot(sv) else {
909        return;
910    };
911    let dict = ctx.rete.dictionary();
912    let mut pats: Vec<Pattern> = Vec::new();
913    for &sid in subject_ids {
914        let mut base = ctx.slots.empty_row();
915        base[slot] = Some(Val::Id(dict.subject_node(sid) as i64));
916        for t in &lowered {
917            if !matches!(t.0, SlotTerm::Var(i) if i == slot) {
918                continue;
919            }
920            if let (Some(s), Some(p), Some(o)) = (
921                probe_subject(ctx, &t.0, &base),
922                probe_predicate(ctx, &t.1, &base),
923                probe_object(ctx, &t.2, &base),
924            ) {
925                pats.push((s, p, o));
926            }
927        }
928    }
929    index.prefetch_probe_tiles(&pats);
930}
931
932/// A pattern whose own constant terms (a bound subject or object) already route
933/// it to a narrow index range — a few coalesced range reads to scan in full.
934fn pattern_is_selective(t: &(SlotTerm, SlotTerm, SlotTerm)) -> bool {
935    matches!(t.0, SlotTerm::Node(_)) || matches!(t.2, SlotTerm::Node(_))
936}
937
938/// The (deduped) slots a lowered pattern binds.
939fn pattern_slots(t: &(SlotTerm, SlotTerm, SlotTerm)) -> Vec<usize> {
940    let mut slots: Vec<usize> = Vec::new();
941    for term in [&t.0, &t.1, &t.2] {
942        if let SlotTerm::Var(i) = term {
943            if !slots.contains(i) {
944                slots.push(*i);
945            }
946        }
947    }
948    slots
949}
950
951/// How many scanned triples [`canon_ahead`] pulls before canonicalizing their
952/// predicates together.
953const CANON_AHEAD: usize = 64;
954
955/// `triples`, with the predicates of each run of [`CANON_AHEAD`] of them
956/// canonicalized in one batch before the first row of the run is built.
957///
958/// A pattern with a variable predicate canonicalizes every new predicate it
959/// meets ([`pred_val`]): its term is looked up as a node, up to three chunk
960/// reads, each a round trip on a lazy open, one new predicate after another.
961/// Looking the run's predicates up together costs the round trips of one
962/// ([`crate::row::Resolver::prefetch_canon`]). Anything but a variable
963/// predicate over a faulting dictionary passes straight through.
964fn canon_ahead<'a, 'c>(
965    ctx: &'a Ctx<'c>,
966    t: &(SlotTerm, SlotTerm, SlotTerm),
967    triples: impl Iterator<Item = Triple> + 'a,
968) -> Box<dyn Iterator<Item = Triple> + 'a> {
969    if !matches!(t.1, SlotTerm::Var(_)) || !ctx.rete.dictionary().faults_chunks() {
970        return Box::new(triples);
971    }
972    // Which of the subject and object the query will decode as it ends: a
973    // projected variable of this pattern (see [`Ctx::decode_ahead`]).
974    let decoded = |term: &SlotTerm| match term {
975        SlotTerm::Var(i) => ctx.decodes_slot(*i),
976        _ => false,
977    };
978    Box::new(CanonAhead {
979        ctx,
980        triples,
981        run: std::collections::VecDeque::new(),
982        decode: (decoded(&t.0), decoded(&t.2)),
983        ahead: 0,
984    })
985}
986
987struct CanonAhead<'a, 'c, I> {
988    ctx: &'a Ctx<'c>,
989    triples: I,
990    run: std::collections::VecDeque<Triple>,
991    /// Is the subject, the object, decoded by the query's final projection?
992    decode: (bool, bool),
993    /// Rows whose terms were already prefetched, across every run: the
994    /// decode-ahead is capped by the query's demand once, not once per run.
995    ahead: usize,
996}
997
998impl<I: Iterator<Item = Triple>> Iterator for CanonAhead<'_, '_, I> {
999    type Item = Triple;
1000
1001    fn next(&mut self) -> Option<Triple> {
1002        if self.run.is_empty() {
1003            self.run.extend(self.triples.by_ref().take(CANON_AHEAD));
1004            let preds: Vec<u32> = self.run.iter().map(|t| t.1).collect();
1005            // The rows the query will decode are these ones (up to its LIMIT):
1006            // their terms go out with the canonicalization lookups, one batch
1007            // for both, where the decode after the last row was two more
1008            // dependent reads (leaves, then chunks) on a leafed dictionary.
1009            let dict = self.ctx.rete.dictionary();
1010            let take = self
1011                .ctx
1012                .decode_rows()
1013                .saturating_sub(self.ahead)
1014                .min(self.run.len());
1015            self.ahead += take;
1016            let mut nodes: Vec<u32> = Vec::new();
1017            for t in self.run.iter().take(take) {
1018                if self.decode.0 {
1019                    nodes.push(dict.subject_node(t.0));
1020                }
1021                if self.decode.1 {
1022                    nodes.push(dict.object_node(t.2));
1023                }
1024            }
1025            self.ctx.resolver.prefetch_canon(&preds, &nodes);
1026        }
1027        self.run.pop_front()
1028    }
1029}
1030
1031/// The row value of a matched triple's predicate `p_id`, for a pattern whose
1032/// predicate slot is `slot`. Only a variable predicate binds it, so only then
1033/// is it canonicalized (a predicate that is also a node becomes the node id):
1034/// that is a dictionary lookup of the predicate as a node, memoized per query,
1035/// but up to three dependent chunk reads on a lazy open for each new predicate
1036/// — reads a constant predicate never needed. Otherwise the value is unused.
1037fn pred_val(ctx: &Ctx, slot: &SlotTerm, p_id: u32) -> i64 {
1038    match slot {
1039        SlotTerm::Var(_) => ctx.resolver.canon_id(pred_tag(p_id)),
1040        _ => pred_tag(p_id),
1041    }
1042}
1043
1044/// Build a solution row for one scanned triple, enforcing repeated variables
1045/// *within* the pattern (e.g. `?x p ?x`). `None` = the triple doesn't satisfy
1046/// a repeated variable.
1047fn triple_row(
1048    ctx: &Ctx,
1049    t: &(SlotTerm, SlotTerm, SlotTerm),
1050    (s_id, p_id, o_id): (u32, u32, u32),
1051) -> Option<Row> {
1052    // A query under a memory ceiling ([`crate::guard`]) stops between rows.
1053    crate::guard::check();
1054    let dict = ctx.rete.dictionary();
1055    let s_val = dict.subject_node(s_id) as i64;
1056    let p_val = pred_val(ctx, &t.1, p_id);
1057    let o_val = dict.object_node(o_id) as i64;
1058    let mut row = ctx.slots.empty_row();
1059    for (term, val) in [(&t.0, s_val), (&t.1, p_val), (&t.2, o_val)] {
1060        if let SlotTerm::Var(i) = term {
1061            match row[*i] {
1062                Some(Val::Id(existing)) if existing != val => return None,
1063                Some(_) => {}
1064                None => row[*i] = Some(Val::Id(val)),
1065            }
1066        }
1067    }
1068    Some(row)
1069}
1070
1071/// Lazily scan one lowered pattern as a stream of solution rows. The scan
1072/// constrains only the pattern's constant terms (bound variables are joined in
1073/// afterwards, not pushed into the scan). `None` = a constant is unsatisfiable
1074/// (unknown to the dictionary or in an impossible role), which empties the BGP.
1075fn scan_rows<'q>(
1076    ctx: &'q Ctx<'q>,
1077    index: &'q GraphIndex,
1078    t: (SlotTerm, SlotTerm, SlotTerm),
1079) -> Option<impl Iterator<Item = Row> + 'q> {
1080    let dict = ctx.rete.dictionary();
1081    let (sid, pid, oid) = (
1082        const_subject(&t.0, dict)?,
1083        const_predicate(&t.1)?,
1084        const_object(&t.2, dict)?,
1085    );
1086    Some(
1087        canon_ahead(ctx, &t, index.scan_iter((sid, pid, oid)))
1088            .filter_map(move |triple| triple_row(ctx, &t, triple)),
1089    )
1090}
1091
1092/// `GRAPH ?g { one pattern }` over a quad-index file: every match of the
1093/// pattern in any graph as a row that also binds slot `gslot` to the graph,
1094/// streamed from one pass over the tiles (no view per graph). `None` when this
1095/// does not apply (not a single pattern, the graph variable also inside the
1096/// pattern, a file without a quad index): the caller falls back to walking the
1097/// graphs. A constant the dictionary cannot place gives an empty stream.
1098pub(crate) fn quad_scan_rows<'q>(
1099    ctx: &'q Ctx<'q>,
1100    patterns: &[TriplePattern],
1101    gslot: usize,
1102) -> Option<Box<dyn Iterator<Item = Row> + 'q>> {
1103    let [p] = patterns else {
1104        return None;
1105    };
1106    if [&p.s, &p.p, &p.o]
1107        .iter()
1108        .any(|t| matches!(t, PatternTerm::Var(v) if ctx.slots.slot(v) == Some(gslot)))
1109    {
1110        return None;
1111    }
1112    let dict = ctx.rete.dictionary();
1113    let Some(lowered) = lower(patterns, ctx) else {
1114        return Some(Box::new(std::iter::empty()));
1115    };
1116    let t = lowered[0];
1117    let (Some(sid), Some(pid), Some(oid)) = (
1118        const_subject(&t.0, dict),
1119        const_predicate(&t.1),
1120        const_object(&t.2, dict),
1121    ) else {
1122        return Some(Box::new(std::iter::empty()));
1123    };
1124    let scan = ctx.rete.named_quad_scan((sid, pid, oid))?;
1125    Some(Box::new(scan.filter_map(move |(g, triple)| {
1126        let mut row = triple_row(ctx, &t, triple)?;
1127        row[gslot] = Some(Val::Id(dict.subject_node(g) as i64));
1128        Some(row)
1129    })))
1130}
1131
1132/// A triple pattern as the dictionary ids of its constants (subject, predicate, object).
1133pub(crate) type ScanPattern = (Option<u32>, Option<u32>, Option<u32>);
1134
1135/// The pattern of a BGP that best narrows a scan over every graph, as the
1136/// dictionary ids of its constants: the one with the most constants, a bound
1137/// subject or object weighing more than a bound predicate. `None` when no
1138/// pattern has a constant, or one cannot be placed in the dictionary.
1139pub(crate) fn driver_pattern(ctx: &Ctx, patterns: &[TriplePattern]) -> Option<ScanPattern> {
1140    let dict = ctx.rete.dictionary();
1141    let lowered = lower(patterns, ctx)?;
1142    let mut best: Option<(u32, ScanPattern)> = None;
1143    for t in &lowered {
1144        let (sid, pid, oid) = (
1145            const_subject(&t.0, dict)?,
1146            const_predicate(&t.1)?,
1147            const_object(&t.2, dict)?,
1148        );
1149        let score =
1150            3 * u32::from(sid.is_some()) + u32::from(pid.is_some()) + 3 * u32::from(oid.is_some());
1151        if score > 0 && best.is_none_or(|(b, _)| score > b) {
1152            best = Some((score, (sid, pid, oid)));
1153        }
1154    }
1155    best.map(|(_, pat)| pat)
1156}
1157
1158/// Scan one lowered pattern into a materialized relation, returning the rows
1159/// and the slots the pattern binds. `None` = a constant is unsatisfiable.
1160fn pattern_rows(
1161    ctx: &Ctx,
1162    index: &GraphIndex,
1163    t: &(SlotTerm, SlotTerm, SlotTerm),
1164) -> Option<(Vec<Row>, Vec<usize>)> {
1165    let slots = pattern_slots(t);
1166    let mut rel: Vec<Row> = Vec::new();
1167    let dict = ctx.rete.dictionary();
1168    let (sid, pid, oid) = (
1169        const_subject(&t.0, dict)?,
1170        const_predicate(&t.1)?,
1171        const_object(&t.2, dict)?,
1172    );
1173    // Stream the matches with the lazy cursor — the hash join is
1174    // order-independent, so no canonical re-sort is needed here.
1175    for triple in canon_ahead(ctx, t, index.scan_iter((sid, pid, oid))) {
1176        if let Some(row) = triple_row(ctx, t, triple) {
1177            rel.push(row);
1178        }
1179    }
1180    Some((rel, slots))
1181}
1182
1183/// A per-pattern cardinality estimate, smaller = cheaper to scan. The base is
1184/// the **exact** per-predicate triple count (sum of the summary quotient graph's
1185/// super-edge counts) when the predicate is bound, else the whole-graph total.
1186/// A bound subject/object (a constant, or a variable already bound by `seed`)
1187/// then scales it down by that predicate's **measured selectivity** from the
1188/// `query_stats` block — `1 / distinct_subjects` for a bound subject (so
1189/// `<s> <p> ?o` ≈ the average objects per subject; exactly 1 for a functional
1190/// predicate), `1 / distinct_objects` for a bound object. Files built before the
1191/// `query_stats` block fall back to fixed default selectivities. `None` when the
1192/// file carries no pyramid summary at all — ordering then uses the constant-count
1193/// heuristic.
1194fn pattern_estimates(
1195    ctx: &Ctx,
1196    index: &GraphIndex,
1197    lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1198    seed: &std::collections::HashSet<usize>,
1199) -> Option<Vec<f64>> {
1200    // Only use the summary when it's already in memory — never fault it just to
1201    // plan (the lazy remote path defers the pyramid by design).
1202    let pyr = ctx.rete.pyramid_if_loaded()?;
1203    let mut pred: std::collections::HashMap<u32, u64> = std::collections::HashMap::new();
1204    for e in &pyr.summary {
1205        *pred.entry(e.predicate).or_insert(0) += e.count as u64;
1206    }
1207    // Measured per-predicate distinct subjects/objects: the SCHEMA section
1208    // (kind 9) — where a file built since it existed keeps them, its
1209    // pyramid-meta holding only the community summary — else the pyramid-meta's
1210    // query-stats block; empty on files built before either → the default
1211    // selectivities. The pyramid is resident here, so the (small) section is
1212    // too on a resident open, and costs one range once on a lazy one.
1213    let stats: std::collections::HashMap<u32, &crate::meta::PredStat> = ctx
1214        .rete
1215        .planner_stats(true)
1216        .iter()
1217        .map(|s| (s.predicate, s))
1218        .collect();
1219    // The active graph's own size: a pattern inside `GRAPH <g>` cannot match more
1220    // triples than `g` holds, whatever the file-wide predicate count says.
1221    let graph_total = ctx.rete.index_triples(index).max(1) as f64;
1222    let total = graph_total;
1223    let num_preds = pred.len().max(1) as f64;
1224    // Defaults used only when query_stats has no entry for the predicate.
1225    const SEL_SUBJECT: f64 = 0.001;
1226    const SEL_OBJECT: f64 = 0.02;
1227    let node_bound = |t: &SlotTerm| match t {
1228        SlotTerm::Node(_) => true,
1229        SlotTerm::Var(v) => seed.contains(v),
1230        SlotTerm::Pred(_) => false,
1231    };
1232    Some(
1233        lowered
1234            .iter()
1235            .map(|t| {
1236                // Base from the predicate: exact total for a constant predicate,
1237                // the average predicate total for a seed-bound predicate variable
1238                // (the value is known to the probe but not at plan time), else the
1239                // whole graph. `st` is the measured stats for a constant predicate.
1240                let (base, st) = match t.1 {
1241                    SlotTerm::Pred(p) => {
1242                        (*pred.get(&p).unwrap_or(&0) as f64, stats.get(&p).copied())
1243                    }
1244                    SlotTerm::Var(v) if seed.contains(&v) => (total / num_preds, None),
1245                    _ => (total, None),
1246                };
1247                let mut est = base.min(graph_total).max(1.0);
1248                if node_bound(&t.0) {
1249                    est *= match st {
1250                        Some(s) if s.distinct_subjects > 0 => 1.0 / s.distinct_subjects as f64,
1251                        _ => SEL_SUBJECT,
1252                    };
1253                }
1254                if node_bound(&t.2) {
1255                    est *= match st {
1256                        Some(s) if s.distinct_objects > 0 => 1.0 / s.distinct_objects as f64,
1257                        _ => SEL_OBJECT,
1258                    };
1259                }
1260                est.max(1.0)
1261            })
1262            .collect(),
1263    )
1264}
1265
1266/// The minimum, over a BGP's patterns, of [`pattern_scan_bytes`] — the
1267/// cheapest single-pattern scan the hash-join path would at least perform to
1268/// materialize this BGP. `None` = a constant term is unknown to the
1269/// dictionary (the BGP is unsatisfiable; the caller short-circuits anyway).
1270/// Unlike [`pattern_estimates`], this needs no pyramid summary, so it works on
1271/// remote-lazy files — exactly where the answer matters most.
1272pub(crate) fn bgp_min_scan_bytes(
1273    ctx: &Ctx,
1274    index: &GraphIndex,
1275    patterns: &[TriplePattern],
1276) -> Option<u64> {
1277    let lowered = lower(patterns, ctx)?;
1278    lowered
1279        .iter()
1280        .map(|t| pattern_scan_bytes(ctx, index, t))
1281        .min()
1282}
1283
1284/// One pattern's cheapest scan extent in BYTES — what `rete cost` previews
1285/// (the planner's gates use row estimates instead): for each permutation, sum the
1286/// encoded lengths of the tiles a scan of this pattern would route to (all
1287/// tiles covering the bound leading key, or the whole section when the leading
1288/// key is unbound), and take the minimum. Tile *counts* are useless here — a
1289/// broad predicate can sit inside one giant tile — but the directory's byte
1290/// lengths expose it. Reads only resident metadata, never tile data.
1291///
1292/// A bound term routes by its id **in the role its position has**: a tile's
1293/// leading range is in subject-, predicate- or object-id space, not in the
1294/// unified node space a lowered constant carries. Routing the node id instead
1295/// was off by one for subjects and off by the whole subject-only block for an
1296/// object-only term (every literal), so `?id :value "10.1234/x"` could cost
1297/// "0 bytes" and pass the merge-join gate against a fat partner, which the
1298/// merge then materialized in full. A constant that has no id in the role
1299/// (never a subject, say) matches nothing: 0 bytes is then exact.
1300fn pattern_scan_bytes(ctx: &Ctx, index: &GraphIndex, t: &(SlotTerm, SlotTerm, SlotTerm)) -> u64 {
1301    let dict = ctx.rete.dictionary();
1302    match (
1303        const_subject(&t.0, dict),
1304        const_predicate(&t.1),
1305        const_object(&t.2, dict),
1306    ) {
1307        (Some(s), Some(p), Some(o)) => routed_scan_bytes(index, (s, p, o)),
1308        _ => 0,
1309    }
1310}
1311
1312/// [`pattern_scan_bytes`] for a pattern already in role-id space.
1313pub(crate) fn routed_scan_bytes(index: &GraphIndex, pattern: Pattern) -> u64 {
1314    let sections = index.tile_sections();
1315    let mut best = u64::MAX;
1316    // Only the permutations the FILE carries: an absent section is an empty
1317    // `Vec<Tile>`, and summing its (zero) tile lengths would report a free scan
1318    // for the one permutation that cannot be scanned at all.
1319    for perm in index.perms().iter() {
1320        let tiles = sections[perm.section_index()];
1321        // A leafed (0x06) directory answers from its root without faulting a
1322        // leaf: a cost estimate must not cost a round trip.
1323        best = best.min(match perm.order_pattern(pattern)[0] {
1324            Some(id) => tiles.routed_bytes(id),
1325            None => tiles.total_bytes(),
1326        });
1327    }
1328    best
1329}
1330
1331/// Estimated matches above which a join side counts as "fat": materializing
1332/// (or, on a remote index, fetching) a million rows to build a hash/merge side
1333/// is past the point where probing it per surviving row wins. Shared by the
1334/// merge-seed asymmetry gate here and the force-probe gates in `sparql::eval`.
1335///
1336/// A ROW estimate ([`GraphIndex::estimate_matches`]: routed tiles × rows per
1337/// tile), not a byte figure. Tiles are cut by their encoded size before
1338/// compression, so the estimate does not move when only the compression does;
1339/// the compressed tile bytes this gate used to read did — at zstd level 19,
1340/// two OpenCitations queries crossed the old 2 MiB line and ran 3–7× slower
1341/// with up to 6× the memory — and they differed between a resident open
1342/// (decoded sizes) and a lazy one (compressed sizes) of the same file.
1343pub(crate) const FAT_SCAN_ROWS: f64 = (1u64 << 20) as f64;
1344
1345/// Would a merge join of `ta` and `tb` materialize a fat side next to a
1346/// pinpoint one? (One side above [`FAT_SCAN_ROWS`] and at least four times the
1347/// other.) Then the hybrid loop — scan the small side, probe the fat one — is
1348/// strictly better, and the merge seed is declined.
1349fn merge_seed_lopsided(
1350    ctx: &Ctx,
1351    index: &GraphIndex,
1352    ta: &(SlotTerm, SlotTerm, SlotTerm),
1353    tb: &(SlotTerm, SlotTerm, SlotTerm),
1354) -> bool {
1355    let est = tile_estimates(ctx, index, &[*ta, *tb], &std::collections::HashSet::new());
1356    let (lo, hi) = (est[0].min(est[1]), est[0].max(est[1]));
1357    hi >= FAT_SCAN_ROWS && hi / 4.0 >= lo
1358}
1359
1360/// Order pattern indices for a left-deep join: cheapest (smallest estimated
1361/// cardinality) first, always preferring a pattern that shares a variable with
1362/// the already-joined set so the join stays connected and intermediate relations
1363/// stay small. Cardinality comes from [`pattern_estimates`]; with no summary it
1364/// falls back to a most-constants-first heuristic. Pure reordering — `hash_join`
1365/// is order-independent, so the result multiset is unchanged.
1366fn selectivity_order(
1367    ctx: &Ctx,
1368    index: &GraphIndex,
1369    lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1370) -> Vec<usize> {
1371    selectivity_order_seeded(ctx, index, lowered, &std::collections::HashSet::new())
1372}
1373
1374/// [`selectivity_order`] with a set of slots already bound by an outer seed
1375/// row: those variables count as already connected (and, in the no-summary
1376/// fallback, as constants for selectivity).
1377fn selectivity_order_seeded(
1378    ctx: &Ctx,
1379    index: &GraphIndex,
1380    lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1381    seed: &std::collections::HashSet<usize>,
1382) -> Vec<usize> {
1383    // Exact per-predicate statistics when the pyramid is resident; otherwise
1384    // (the lazy path, and files built without a pyramid) the tile-directory
1385    // estimate, which needs no fetch. That one also counts a class's own
1386    // instances (`?s a :C` routes to the tiles of `:C`), so the
1387    // class-enumeration rule below, a stand-in for exactly that missing
1388    // number, applies only to the pyramid figures, whose `rdf:type`
1389    // selectivity is an average over classes.
1390    let (estimates, per_class) = match pattern_estimates(ctx, index, lowered, seed) {
1391        Some(e) => (Some(e), false),
1392        None => (Some(tile_estimates(ctx, index, lowered, seed)), true),
1393    };
1394    let consts = |t: &(SlotTerm, SlotTerm, SlotTerm)| {
1395        [&t.0, &t.1, &t.2]
1396            .into_iter()
1397            .filter(|x| match x {
1398                SlotTerm::Var(v) => seed.contains(v),
1399                _ => true,
1400            })
1401            .count()
1402    };
1403    let vars = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Vec<usize> {
1404        [&t.0, &t.1, &t.2]
1405            .into_iter()
1406            .filter_map(|x| match x {
1407                SlotTerm::Var(v) => Some(*v),
1408                _ => None,
1409            })
1410            .collect()
1411    };
1412    // Higher score = picked sooner. With summary stats that's the negated
1413    // estimate (smaller cardinality wins); without, the constant count (old
1414    // behaviour, byte-identical ordering for pyramid-less files).
1415    let score = |i: usize| -> f64 {
1416        match &estimates {
1417            Some(e) => -e[i],
1418            None => consts(&lowered[i]) as f64,
1419        }
1420    };
1421    // A `?s rdf:type <Class>` with an as-yet-unbound subject is a **class
1422    // enumeration**: it matches every instance of the class, so it is almost never
1423    // the most selective place to *start* a join (a popular class has thousands of
1424    // instances), even though it has two bound positions and so looks selective to
1425    // the constant-count heuristic. Deprioritize it as a seed; once its subject is
1426    // bound by another pattern it becomes a cheap per-row type *check* (the hybrid
1427    // join probes it), so pushing it later costs nothing. Robust and stats-free.
1428    let type_pid = ctx.rete.dictionary().predicate_id(crate::file::RDF_TYPE);
1429    let is_class_enum = |i: usize, bound: &std::collections::HashSet<usize>| -> bool {
1430        let t = &lowered[i];
1431        !per_class
1432            && type_pid.is_some_and(|tp| matches!(t.1, SlotTerm::Pred(p) if p == tp))
1433            && matches!(t.2, SlotTerm::Node(_))
1434            && matches!(t.0, SlotTerm::Var(v) if !bound.contains(&v))
1435    };
1436    let n = lowered.len();
1437    let mut remaining: Vec<usize> = (0..n).collect();
1438    let mut order: Vec<usize> = Vec::with_capacity(n);
1439    let mut bound: std::collections::HashSet<usize> = seed.clone();
1440    while !remaining.is_empty() {
1441        // Pick the remaining pattern with the best (connected, not-a-class-enum,
1442        // score) key; ties go to the lowest original index for a stable order.
1443        let best = *remaining
1444            .iter()
1445            .max_by(|&&a, &&b| {
1446                let connected = |i: usize| vars(&lowered[i]).iter().any(|v| bound.contains(v));
1447                connected(a)
1448                    .cmp(&connected(b))
1449                    .then_with(|| is_class_enum(b, &bound).cmp(&is_class_enum(a, &bound)))
1450                    .then_with(|| {
1451                        score(a)
1452                            .partial_cmp(&score(b))
1453                            .unwrap_or(std::cmp::Ordering::Equal)
1454                    })
1455                    .then_with(|| b.cmp(&a))
1456            })
1457            .unwrap();
1458        for v in vars(&lowered[best]) {
1459            bound.insert(v);
1460        }
1461        order.push(best);
1462        remaining.retain(|&i| i != best);
1463    }
1464    order
1465}
1466
1467/// Does the BGP have at least one solution against `index`? A single pattern
1468/// with all-distinct variables streams the index and stops at the first match
1469/// (no materialization); anything else falls back to the full evaluator and
1470/// tests non-emptiness (still benefiting from the lazy per-pattern scan). Used
1471/// by `ASK`.
1472pub(crate) fn bgp_exists(ctx: &Ctx, index: &GraphIndex, patterns: &[TriplePattern]) -> bool {
1473    let dict = ctx.rete.dictionary();
1474    let Some(lowered) = lower(patterns, ctx) else {
1475        return false;
1476    };
1477    if let [t] = lowered.as_slice() {
1478        // The fast path can't enforce a variable repeated across positions
1479        // (e.g. `?x p ?x`) — that needs the row builder — so only take it when
1480        // the pattern's variables are all distinct.
1481        let names: Vec<usize> = [&t.0, &t.1, &t.2]
1482            .into_iter()
1483            .filter_map(|x| match x {
1484                SlotTerm::Var(v) => Some(*v),
1485                _ => None,
1486            })
1487            .collect();
1488        let distinct = names
1489            .iter()
1490            .enumerate()
1491            .all(|(i, v)| !names[i + 1..].contains(v));
1492        if distinct {
1493            return match (
1494                const_subject(&t.0, dict),
1495                const_predicate(&t.1),
1496                const_object(&t.2, dict),
1497            ) {
1498                (Some(s), Some(p), Some(o)) => index.scan_iter((s, p, o)).next().is_some(),
1499                _ => false,
1500            };
1501        }
1502    }
1503    !eval_bgp_rows(ctx, index, patterns).is_empty()
1504}
1505
1506/// A lazy left-deep BGP join that yields solution rows one at a time, so a
1507/// consumer under `LIMIT`/`OFFSET` (or `.next()` for ASK) can stop early —
1508/// stopping also stops the underlying index scan.
1509///
1510/// The all-but-last patterns are joined eagerly into a `prefix` **hash table**
1511/// (they are the most selective, so this is the small side); the *last* (least
1512/// selective) pattern is then **streamed** from the index cursor, probing the
1513/// prefix — the big scan is never materialized, and a `LIMIT` above stops it
1514/// after a handful of triples. Yields the same solution multiset as
1515/// [`eval_bgp_rows`] (the join is order-independent), just incrementally.
1516pub(crate) struct BgpSolutions<'q> {
1517    scan: Option<Box<dyn Iterator<Item = Row> + 'q>>,
1518    prefix: Vec<Row>,
1519    /// Prefix row indices keyed by the shared-slot values.
1520    buckets: HashMap<Vec<Val>, Vec<usize>>,
1521    shared: Vec<usize>,
1522    cartesian: bool,
1523    /// The prefix is the all-unbound seed row (single-pattern BGP): scanned
1524    /// rows are already complete solutions — pass them through unmerged.
1525    seed_only: bool,
1526    cur_scan: Option<Row>,
1527    /// Reused candidate buffer (avoids a Vec allocation per scanned row).
1528    matches: Vec<usize>,
1529    mi: usize,
1530}
1531
1532impl<'q> BgpSolutions<'q> {
1533    /// Yield `rows` as complete solutions (no prefix merge).
1534    fn passthrough(rows: Box<dyn Iterator<Item = Row> + 'q>) -> Self {
1535        BgpSolutions {
1536            scan: Some(rows),
1537            prefix: Vec::new(),
1538            buckets: HashMap::new(),
1539            shared: Vec::new(),
1540            cartesian: false,
1541            seed_only: true,
1542            cur_scan: None,
1543            matches: Vec::new(),
1544            mi: 0,
1545        }
1546    }
1547
1548    /// The fully streaming join, for a BGP whose most selective pattern is
1549    /// itself large ([`STREAM_SEED_ROWS`]). Nothing proportional to it is ever
1550    /// held: the seed pattern streams from its index cursor (or, when the next
1551    /// pattern is just as large and shares its subject variable, both stream
1552    /// through a merge join), and each later pattern joins per row — through
1553    /// a hash table when the pattern is small ([`HASH_BUILD_ROWS`]), by an
1554    /// index probe otherwise. Same solution multiset as the materializing
1555    /// path; only the row order differs.
1556    fn streaming(
1557        ctx: &'q Ctx<'q>,
1558        index: &'q GraphIndex,
1559        lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1560        order: &[usize],
1561        est: &[f64],
1562    ) -> Self {
1563        let (mut stream, mut bound, skip): (Box<dyn Iterator<Item = Row> + 'q>, Vec<usize>, usize) =
1564            match (est[order[1]] > limits().stream_seed)
1565                .then(|| merge_stream(ctx, index, lowered[order[0]], lowered[order[1]]))
1566                .flatten()
1567            {
1568                Some((m, slots)) => (m, slots, 2),
1569                None => {
1570                    let t = lowered[order[0]];
1571                    let Some(scan) = scan_rows(ctx, index, t) else {
1572                        return Self::empty();
1573                    };
1574                    (Box::new(scan), pattern_slots(&t), 1)
1575                }
1576            };
1577        for &i in &order[skip..] {
1578            let t = lowered[i];
1579            let slots = pattern_slots(&t);
1580            let shared: Vec<usize> = slots
1581                .iter()
1582                .copied()
1583                .filter(|s| bound.contains(s))
1584                .collect();
1585            if !shared.is_empty() && est[i] > limits().hash_build {
1586                // Each window of streamed rows has its probes' tiles faulted
1587                // together ([`Windowed`]); one at a time, a probe join over a
1588                // remote file was bound by round-trip latency.
1589                stream = Box::new(
1590                    windowed(index, stream, bgp_probe_pattern(ctx, t))
1591                        .flat_map(move |base| probe_rows(ctx, index, t, base)),
1592                );
1593            } else {
1594                // Small (or unconnected) pattern: scan it once into a table
1595                // keyed on the shared slots and join every streamed row to it.
1596                let Some((rel, _)) = pattern_rows(ctx, index, &t) else {
1597                    return Self::empty();
1598                };
1599                let mut table: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
1600                for r in rel {
1601                    let key: Vec<Val> = shared.iter().map(|&s| r[s].clone().unwrap()).collect();
1602                    table.entry(key).or_default().push(r);
1603                }
1604                let fill = slots.clone();
1605                stream = Box::new(stream.flat_map(move |base| {
1606                    let key: Vec<Val> = shared.iter().map(|&s| base[s].clone().unwrap()).collect();
1607                    let out: Vec<Row> = table
1608                        .get(&key)
1609                        .map(|rs| {
1610                            rs.iter()
1611                                .map(|r| {
1612                                    let mut row = base.clone();
1613                                    for &s in &fill {
1614                                        row[s] = r[s].clone();
1615                                    }
1616                                    row
1617                                })
1618                                .collect()
1619                        })
1620                        .unwrap_or_default();
1621                    out.into_iter()
1622                }));
1623            }
1624            for s in slots {
1625                if !bound.contains(&s) {
1626                    bound.push(s);
1627                }
1628            }
1629        }
1630        Self::passthrough(stream)
1631    }
1632
1633    /// An iterator that yields nothing (an unsatisfiable BGP).
1634    fn empty() -> Self {
1635        BgpSolutions {
1636            scan: None,
1637            prefix: Vec::new(),
1638            buckets: HashMap::new(),
1639            shared: Vec::new(),
1640            cartesian: false,
1641            seed_only: false,
1642            cur_scan: None,
1643            matches: Vec::new(),
1644            mi: 0,
1645        }
1646    }
1647
1648    pub(crate) fn new(ctx: &'q Ctx<'q>, index: &'q GraphIndex, patterns: &[TriplePattern]) -> Self {
1649        // An empty BGP has exactly one (empty) solution.
1650        if patterns.is_empty() {
1651            return BgpSolutions {
1652                scan: Some(Box::new(std::iter::once(ctx.slots.empty_row()))),
1653                prefix: vec![ctx.slots.empty_row()],
1654                buckets: HashMap::new(),
1655                shared: Vec::new(),
1656                cartesian: true,
1657                seed_only: true,
1658                cur_scan: None,
1659                matches: Vec::new(),
1660                mi: 0,
1661            };
1662        }
1663        // Lower all patterns; an unknown constant term ⇒ no solutions.
1664        let Some(lowered) = lower(patterns, ctx) else {
1665            return Self::empty();
1666        };
1667        // Join all but the *last* (least selective) pattern eagerly into the
1668        // prefix; a single pattern leaves the seed row as the prefix.
1669        let (order, scan_est) = plan_order(ctx, index, &lowered);
1670        // Even the most selective pattern is big: materializing it as the
1671        // prefix would hold every one of its rows. Stream the whole join.
1672        if order.len() >= 2 && scan_est[order[0]] > limits().stream_seed {
1673            return Self::streaming(ctx, index, &lowered, &order, &scan_est);
1674        }
1675        let (&last_i, prefix_is) = order.split_last().unwrap();
1676        let prefix_pats: Vec<TriplePattern> =
1677            prefix_is.iter().map(|&i| patterns[i].clone()).collect();
1678        let prefix = eval_bgp_rows(ctx, index, &prefix_pats);
1679        if prefix.is_empty() {
1680            return Self::empty();
1681        }
1682
1683        // Hash-join key = slots shared by the prefix and the last pattern (BGP
1684        // rows bind every slot of their pattern set, so the prefix's bound set
1685        // can be read off its first row).
1686        let shared: Vec<usize> = pattern_slots(&lowered[last_i])
1687            .into_iter()
1688            .filter(|&s| prefix[0][s].is_some())
1689            .collect();
1690
1691        // A few prefix rows against a big last pattern: look each one up
1692        // instead of scanning the pattern. `?r :relationSubject <doi> . ?r ?p
1693        // ?o` has four prefix rows and a last pattern that is the whole graph.
1694        // The last pattern is an unbound class (`?x rdf:type ?c`) whose subject
1695        // the prefix binds: each row's types are one SPO lookup, and the prefix
1696        // is already resident, so probing costs no memory the scan would not.
1697        // It wins until the rows outnumber the statements the scan would read
1698        // (the usual sixteenth gives way to one).
1699        let class_probe = !shared.is_empty()
1700            && scan_est[last_i] >= limits().probe_floor
1701            && (prefix.len() as f64) <= scan_est[last_i]
1702            && is_unbound_class(ctx, &lowered[last_i], &shared);
1703        if !shared.is_empty() && (probe_beats_scan(prefix.len(), scan_est[last_i]) || class_probe) {
1704            let t = lowered[last_i];
1705            let stream = windowed(index, prefix.into_iter(), bgp_probe_pattern(ctx, t))
1706                .flat_map(move |base| probe_rows(ctx, index, t, base));
1707            return Self::passthrough(Box::new(stream));
1708        }
1709
1710        // Stream the last pattern with the lazy index cursor.
1711        let Some(scan) = scan_rows(ctx, index, lowered[last_i]) else {
1712            return Self::empty();
1713        };
1714        let cartesian = shared.is_empty();
1715        // A single-pattern BGP joins against the all-unbound seed: scanned rows
1716        // are already complete solutions.
1717        let seed_only = prefix.len() == 1 && prefix[0].iter().all(Option::is_none);
1718        let mut buckets: HashMap<Vec<Val>, Vec<usize>> = HashMap::new();
1719        if !cartesian {
1720            for (i, r) in prefix.iter().enumerate() {
1721                let key: Vec<Val> = shared.iter().map(|&s| r[s].clone().unwrap()).collect();
1722                buckets.entry(key).or_default().push(i);
1723            }
1724        }
1725        BgpSolutions {
1726            scan: Some(Box::new(scan)),
1727            prefix,
1728            buckets,
1729            shared,
1730            cartesian,
1731            seed_only,
1732            cur_scan: None,
1733            matches: Vec::new(),
1734            mi: 0,
1735        }
1736    }
1737}
1738
1739impl Iterator for BgpSolutions<'_> {
1740    type Item = Row;
1741
1742    fn next(&mut self) -> Option<Row> {
1743        // Single-pattern fast path: pass scanned rows through unmerged.
1744        if self.seed_only {
1745            return self.scan.as_mut()?.next();
1746        }
1747        loop {
1748            // Emit the next prefix match for the current scanned row.
1749            if self.mi < self.matches.len() {
1750                let pi = self.matches[self.mi];
1751                self.mi += 1;
1752                let mut merged = self.prefix[pi].clone();
1753                for (slot, v) in self.cur_scan.as_ref().unwrap().iter().enumerate() {
1754                    if v.is_some() {
1755                        merged[slot] = v.clone();
1756                    }
1757                }
1758                return Some(merged);
1759            }
1760            // Pull the next row from the index scan and gather its matches
1761            // (into the reused buffer — no allocation per scanned row).
1762            let s = self.scan.as_mut()?.next()?;
1763            self.matches.clear();
1764            if self.cartesian {
1765                self.matches.extend(0..self.prefix.len());
1766            } else {
1767                let key: Vec<Val> = self.shared.iter().map(|&i| s[i].clone().unwrap()).collect();
1768                if let Some(c) = self.buckets.get(&key) {
1769                    self.matches.extend_from_slice(c);
1770                }
1771            }
1772            self.mi = 0;
1773            self.cur_scan = Some(s);
1774        }
1775    }
1776}
1777
1778/// A **streaming** merge join of two patterns that share exactly one variable,
1779/// in the subject position of both: each side streams from a permutation
1780/// sorted on subject ([`GraphIndex::scan_iter_sorted_on`]) and only the
1781/// current subject's rows are held. Restricted to the subject column because a
1782/// subject's rows are its out-edges, a small run; an object run (every
1783/// instance of a class) can be the whole pattern. `None` when the shape does
1784/// not qualify; the caller then streams the first pattern alone.
1785#[allow(clippy::type_complexity)]
1786fn merge_stream<'q>(
1787    ctx: &'q Ctx<'q>,
1788    index: &'q GraphIndex,
1789    ta: (SlotTerm, SlotTerm, SlotTerm),
1790    tb: (SlotTerm, SlotTerm, SlotTerm),
1791) -> Option<(Box<dyn Iterator<Item = Row> + 'q>, Vec<usize>)> {
1792    let sa = pattern_slots(&ta);
1793    let sb = pattern_slots(&tb);
1794    let shared: Vec<usize> = sa.iter().copied().filter(|s| sb.contains(s)).collect();
1795    let [v] = shared[..] else {
1796        return None;
1797    };
1798    if !matches!(ta.0, SlotTerm::Var(i) if i == v) || !matches!(tb.0, SlotTerm::Var(i) if i == v) {
1799        return None;
1800    }
1801    let dict = ctx.rete.dictionary();
1802    let lower = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Option<Pattern> {
1803        Some((
1804            const_subject(&t.0, dict)?,
1805            const_predicate(&t.1)?,
1806            const_object(&t.2, dict)?,
1807        ))
1808    };
1809    let side = |t: (SlotTerm, SlotTerm, SlotTerm)| -> Option<KeyedRows<'q>> {
1810        let it = index.scan_iter_sorted_on(lower(&t)?, 0)?;
1811        let keyed: Box<dyn Iterator<Item = (u32, Row)> + 'q> =
1812            Box::new(it.filter_map(move |tri| triple_row(ctx, &t, tri).map(|r| (tri.0, r))));
1813        Some(keyed.peekable())
1814    };
1815    let a = side(ta)?;
1816    let b = side(tb)?;
1817    let mut slots = sa;
1818    for s in sb {
1819        if !slots.contains(&s) {
1820            slots.push(s);
1821        }
1822    }
1823    Some((
1824        Box::new(MergeStream {
1825            a,
1826            b,
1827            ra: Vec::new(),
1828            rb: Vec::new(),
1829            i: 0,
1830            j: 0,
1831        }),
1832        slots,
1833    ))
1834}
1835
1836type KeyedRows<'q> = std::iter::Peekable<Box<dyn Iterator<Item = (u32, Row)> + 'q>>;
1837
1838/// The two-pointer merge behind [`merge_stream`]: `ra`/`rb` hold the current
1839/// equal-key runs and `(i, j)` walks their cross product lazily.
1840struct MergeStream<'q> {
1841    a: KeyedRows<'q>,
1842    b: KeyedRows<'q>,
1843    ra: Vec<Row>,
1844    rb: Vec<Row>,
1845    i: usize,
1846    j: usize,
1847}
1848
1849impl Iterator for MergeStream<'_> {
1850    type Item = Row;
1851
1852    fn next(&mut self) -> Option<Row> {
1853        loop {
1854            while self.i < self.ra.len() {
1855                if self.j < self.rb.len() {
1856                    let j = self.j;
1857                    self.j += 1;
1858                    if let Some(m) = crate::row::merge_rows(&self.ra[self.i], &self.rb[j]) {
1859                        return Some(m);
1860                    }
1861                } else {
1862                    self.i += 1;
1863                    self.j = 0;
1864                }
1865            }
1866            let ka = self.a.peek()?.0;
1867            let kb = self.b.peek()?.0;
1868            match ka.cmp(&kb) {
1869                std::cmp::Ordering::Less => {
1870                    self.a.next();
1871                }
1872                std::cmp::Ordering::Greater => {
1873                    self.b.next();
1874                }
1875                std::cmp::Ordering::Equal => {
1876                    self.ra.clear();
1877                    self.rb.clear();
1878                    while let Some((_, r)) = self.a.next_if(|(k, _)| *k == ka) {
1879                        self.ra.push(r);
1880                    }
1881                    while let Some((_, r)) = self.b.next_if(|(k, _)| *k == ka) {
1882                        self.rb.push(r);
1883                    }
1884                    self.i = 0;
1885                    self.j = 0;
1886                }
1887            }
1888        }
1889    }
1890}
1891
1892// --- index-nested-loop probing ------------------------------------------------
1893//
1894// Under a small, known demand (LIMIT/ASK — see `Ctx::limit_hint`), scanning
1895// every pattern once to hash-join is mostly wasted work: the consumer wants a
1896// handful of rows. The probe path instead streams the seed/first pattern and,
1897// per row, *probes* each next pattern through the index with the row's bound
1898// values substituted as scan constants — so producing k solutions touches
1899// O(k · patterns) index groups instead of every pattern's full extent. Same
1900// solution multiset as the hash join (joins are order-independent); only the
1901// evaluation order differs.
1902
1903/// Index-scan constant for a subject position given a partially-bound row.
1904/// Outer `None` = unsatisfiable for this row; inner `None` = wildcard.
1905fn probe_subject(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
1906    let dict = ctx.rete.dictionary();
1907    match t {
1908        SlotTerm::Node(n) => dict.node_as_subject_id(*n).map(Some),
1909        SlotTerm::Pred(_) => None,
1910        SlotTerm::Var(i) => match &base[*i] {
1911            None => Some(None),
1912            Some(Val::Id(v)) if *v >= 0 => dict.node_as_subject_id(*v as u32).map(Some),
1913            // A predicate-tagged or computed value can never be a subject.
1914            Some(_) => None,
1915        },
1916    }
1917}
1918
1919/// Index-scan constant for an object position (see [`probe_subject`]).
1920fn probe_object(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
1921    let dict = ctx.rete.dictionary();
1922    match t {
1923        SlotTerm::Node(n) => dict.node_as_object_id(*n).map(Some),
1924        SlotTerm::Pred(_) => None,
1925        SlotTerm::Var(i) => match &base[*i] {
1926            None => Some(None),
1927            Some(Val::Id(v)) if *v >= 0 => dict.node_as_object_id(*v as u32).map(Some),
1928            Some(_) => None,
1929        },
1930    }
1931}
1932
1933/// Index-scan constant for a predicate position (see [`probe_subject`]).
1934fn probe_predicate(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
1935    let dict = ctx.rete.dictionary();
1936    match t {
1937        SlotTerm::Pred(p) => Some(Some(*p)),
1938        SlotTerm::Node(_) => None,
1939        SlotTerm::Var(i) => match &base[*i] {
1940            None => Some(None),
1941            Some(Val::Id(v)) if *v < 0 => Some(Some((-v - 1) as u32)),
1942            // Canonicalized to a node id — the term may still be a predicate.
1943            Some(Val::Id(v)) => ctx
1944                .resolver
1945                .term(*v)
1946                .and_then(|t| dict.predicate_id(&t))
1947                .map(Some),
1948            Some(Val::Str(_)) => None,
1949        },
1950    }
1951}
1952
1953/// Probe one pattern with a partially-bound row: every bound variable becomes
1954/// an index-scan constant, and each matching triple extends a clone of the row
1955/// (repeated unbound variables stay consistent).
1956fn probe_rows<'q>(
1957    ctx: &'q Ctx<'q>,
1958    index: &'q GraphIndex,
1959    t: (SlotTerm, SlotTerm, SlotTerm),
1960    base: Row,
1961) -> Box<dyn Iterator<Item = Row> + 'q> {
1962    let (Some(sid), Some(pid), Some(oid)) = (
1963        probe_subject(ctx, &t.0, &base),
1964        probe_predicate(ctx, &t.1, &base),
1965        probe_object(ctx, &t.2, &base),
1966    ) else {
1967        return Box::new(std::iter::empty());
1968    };
1969    let dict = ctx.rete.dictionary();
1970    // A variable predicate is canonicalized a run at a time ([`canon_ahead`]):
1971    // one new predicate after another was a dictionary round trip each.
1972    Box::new(
1973        canon_ahead(ctx, &t, index.scan_iter((sid, pid, oid))).filter_map(
1974            move |(s_id, p_id, o_id)| {
1975                let s_val = dict.subject_node(s_id) as i64;
1976                let p_val = pred_val(ctx, &t.1, p_id);
1977                let o_val = dict.object_node(o_id) as i64;
1978                let mut row = base.clone();
1979                for (term, val) in [(&t.0, s_val), (&t.1, p_val), (&t.2, o_val)] {
1980                    if let SlotTerm::Var(i) = term {
1981                        match row[*i] {
1982                            Some(Val::Id(existing)) if existing != val => return None,
1983                            Some(Val::Id(_)) => {}
1984                            Some(Val::Str(_)) => return None,
1985                            None => row[*i] = Some(Val::Id(val)),
1986                        }
1987                    }
1988                }
1989                Some(row)
1990            },
1991        ),
1992    )
1993}
1994
1995/// A lowered, probe-ordered BGP, reusable across many seed rows.
1996pub(crate) struct ProbePlan {
1997    pats: Vec<(SlotTerm, SlotTerm, SlotTerm)>,
1998}
1999
2000impl ProbePlan {
2001    /// Lower and order `patterns` for probing from rows that bind (at least)
2002    /// the slots in `seed_mask`. `None` = a constant term is unknown, making
2003    /// the BGP unsatisfiable for every seed.
2004    pub(crate) fn new(
2005        ctx: &Ctx,
2006        index: &GraphIndex,
2007        patterns: &[TriplePattern],
2008        seed_mask: &[bool],
2009    ) -> Option<Self> {
2010        let lowered = lower(patterns, ctx)?;
2011        let seed: std::collections::HashSet<usize> = seed_mask
2012            .iter()
2013            .enumerate()
2014            .filter_map(|(i, b)| b.then_some(i))
2015            .collect();
2016        let order = selectivity_order_seeded(ctx, index, &lowered, &seed);
2017        Some(ProbePlan {
2018            pats: order.into_iter().map(|i| lowered[i]).collect(),
2019        })
2020    }
2021}
2022
2023/// Depth-first index-nested-loop join over a [`ProbePlan`], starting from a
2024/// seed row. Fully lazy: pulling k rows probes O(k · patterns) index groups.
2025pub(crate) struct ProbeJoin<'q> {
2026    ctx: &'q Ctx<'q>,
2027    index: &'q GraphIndex,
2028    pats: Vec<(SlotTerm, SlotTerm, SlotTerm)>,
2029    stack: Vec<Box<dyn Iterator<Item = Row> + 'q>>,
2030}
2031
2032impl<'q> ProbeJoin<'q> {
2033    /// Probe a whole BGP from scratch (the seed is the all-unbound row).
2034    /// `None` = unsatisfiable.
2035    pub(crate) fn new(
2036        ctx: &'q Ctx<'q>,
2037        index: &'q GraphIndex,
2038        patterns: &[TriplePattern],
2039    ) -> Option<Self> {
2040        let plan = ProbePlan::new(ctx, index, patterns, &vec![false; ctx.slots.len()])?;
2041        Some(Self::from_plan(ctx, index, &plan, ctx.slots.empty_row()))
2042    }
2043
2044    /// Probe a pre-lowered plan from one seed row.
2045    pub(crate) fn from_plan(
2046        ctx: &'q Ctx<'q>,
2047        index: &'q GraphIndex,
2048        plan: &ProbePlan,
2049        seed: Row,
2050    ) -> Self {
2051        let pats = plan.pats.clone();
2052        let first = probe_rows(ctx, index, pats[0], seed);
2053        ProbeJoin {
2054            ctx,
2055            index,
2056            pats,
2057            stack: vec![first],
2058        }
2059    }
2060}
2061
2062impl Iterator for ProbeJoin<'_> {
2063    type Item = Row;
2064
2065    fn next(&mut self) -> Option<Row> {
2066        loop {
2067            let depth = self.stack.len();
2068            match self.stack.last_mut()?.next() {
2069                Some(row) => {
2070                    if depth == self.pats.len() {
2071                        return Some(row);
2072                    }
2073                    let it = probe_rows(self.ctx, self.index, self.pats[depth], row);
2074                    self.stack.push(it);
2075                }
2076                None => {
2077                    self.stack.pop();
2078                    if self.stack.is_empty() {
2079                        return None;
2080                    }
2081                }
2082            }
2083        }
2084    }
2085}
2086
2087/// Hash-join two BGP relations on the slots they share. Every left row binds
2088/// exactly the slots accumulated so far and every right row binds the current
2089/// pattern's slots, so the shared set is uniform across rows.
2090fn hash_join(
2091    left: Vec<Row>,
2092    left_bound: &[usize],
2093    right: Vec<Row>,
2094    right_slots: &[usize],
2095) -> Vec<Row> {
2096    // Fast path: the all-unbound seed row joins to `right` unchanged.
2097    if left.len() == 1 && left_bound.is_empty() {
2098        return right;
2099    }
2100    if left.is_empty() || right.is_empty() {
2101        return Vec::new();
2102    }
2103    let shared: Vec<usize> = right_slots
2104        .iter()
2105        .copied()
2106        .filter(|s| left_bound.contains(s))
2107        .collect();
2108    let fill = |l: &Row, r: &Row| -> Row {
2109        let mut out = l.clone();
2110        for &s in right_slots {
2111            out[s] = r[s].clone();
2112        }
2113        out
2114    };
2115    if shared.is_empty() {
2116        // No shared variable: Cartesian product. In a connected BGP this only
2117        // arises for a fully-ground pattern (deduped index ⇒ one matching row),
2118        // so it acts as an existence filter rather than multiplying rows.
2119        let mut out = Vec::with_capacity(left.len() * right.len());
2120        for l in &left {
2121            for r in &right {
2122                out.push(fill(l, r));
2123            }
2124        }
2125        return out;
2126    }
2127    let key_of = |b: &Row| -> Vec<Val> { shared.iter().map(|&s| b[s].clone().unwrap()).collect() };
2128    // A hash join is symmetric on the shared key, so build the **smaller** side's
2129    // hash table and probe with the larger — same result set, fewer inserts and a
2130    // smaller table. (The old code always built `right`; after cardinality-based
2131    // ordering the accumulating `left` is usually the small selective side, so
2132    // building it instead is the common win.) Whichever side is built, the output
2133    // row carries every bound slot of both.
2134    let mut out = Vec::new();
2135    if right.len() <= left.len() {
2136        let mut buckets: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
2137        for r in right {
2138            buckets.entry(key_of(&r)).or_default().push(r);
2139        }
2140        for l in &left {
2141            if let Some(rs) = buckets.get(&key_of(l)) {
2142                for r in rs {
2143                    out.push(fill(l, r));
2144                }
2145            }
2146        }
2147    } else {
2148        // Build the left side; fill the left's own slots into each probed right.
2149        let mut buckets: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
2150        for l in left {
2151            buckets.entry(key_of(&l)).or_default().push(l);
2152        }
2153        for r in &right {
2154            if let Some(ls) = buckets.get(&key_of(r)) {
2155                for l in ls {
2156                    let mut row = r.clone();
2157                    for &s in left_bound {
2158                        if let Some(v) = &l[s] {
2159                            row[s] = Some(v.clone());
2160                        }
2161                    }
2162                    out.push(row);
2163                }
2164            }
2165        }
2166    }
2167    out
2168}
2169
2170// Constant-only index constraints. A variable scans as a wildcard (`Some(None)`)
2171// — it is resolved later by the hash join, not pushed into the scan. The outer
2172// `None` means "unsatisfiable" (a constant in an impossible role, or unknown to
2173// the dictionary), which empties the whole BGP. Inner `None` = "wildcard".
2174fn const_subject(t: &SlotTerm, d: &crate::Dictionary) -> Option<Option<u32>> {
2175    match t {
2176        SlotTerm::Node(n) => d.node_as_subject_id(*n).map(Some),
2177        SlotTerm::Pred(_) => None, // a predicate term can't be a subject
2178        SlotTerm::Var(_) => Some(None),
2179    }
2180}
2181
2182fn const_object(t: &SlotTerm, d: &crate::Dictionary) -> Option<Option<u32>> {
2183    match t {
2184        SlotTerm::Node(n) => d.node_as_object_id(*n).map(Some),
2185        SlotTerm::Pred(_) => None,
2186        SlotTerm::Var(_) => Some(None),
2187    }
2188}
2189
2190fn const_predicate(t: &SlotTerm) -> Option<Option<u32>> {
2191    match t {
2192        SlotTerm::Pred(p) => Some(Some(*p)),
2193        SlotTerm::Node(_) => None, // a node term can't be a predicate
2194        SlotTerm::Var(_) => Some(None),
2195    }
2196}
2197
2198#[cfg(test)]
2199mod tests {
2200    use super::*;
2201    use crate::dictionary::DictionaryBuilder;
2202    use crate::file::write_file_v05 as write_file;
2203    use crate::index::GraphIndexBuilder;
2204
2205    fn rete_from(triples: &[(&str, &str, &str)]) -> Vec<u8> {
2206        let mut db = DictionaryBuilder::new();
2207        for (s, p, o) in triples {
2208            db.observe(s, p, o);
2209        }
2210        let dict = db.build();
2211        let mut ib = GraphIndexBuilder::new();
2212        for (s, p, o) in triples {
2213            ib.push(dict.encode(s, p, o).unwrap());
2214        }
2215        write_file(&dict, &ib.build(), false, &[], 0)
2216    }
2217
2218    fn pat(s: &str, p: &str, o: &str) -> TriplePattern {
2219        TriplePattern {
2220            s: PatternTerm::parse(s),
2221            p: PatternTerm::parse(p),
2222            o: PatternTerm::parse(o),
2223        }
2224    }
2225
2226    /// The scan-bytes figure (`rete cost`'s preview, and through 0.3.7 the
2227    /// merge-join and fat-side gates) routes a bound term by its id IN ITS
2228    /// ROLE. It used to route the unified node id,
2229    /// which for an object-only term (any literal) is shifted past the whole
2230    /// subject-only block: `?s :value "lit"` found no OPS tile at all, cost
2231    /// "0 bytes", and so let a merge join materialize its partner in full —
2232    /// on OpenCitations, every DOI identifier of a 2.9 B-triple file, behind
2233    /// `?id :hasLiteralValue "10.…" ; :usesIdentifierScheme :doi`.
2234    #[test]
2235    fn scan_bytes_route_a_literal_by_its_object_id() {
2236        let value = "<http://ex/value>";
2237        let owned: Vec<(String, String)> = (0..400)
2238            .map(|i| (format!("<http://ex/s{i:03}>"), format!("\"lit {i:03}\"")))
2239            .collect();
2240        let mut db = DictionaryBuilder::new();
2241        for (s, o) in &owned {
2242            db.observe(s, value, o);
2243        }
2244        let dict = db.build();
2245        let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2246        for (s, o) in &owned {
2247            ib.push(dict.encode(s, value, o).unwrap());
2248        }
2249        let rete = Rete::open(&write_file(&dict, &ib.build(), false, &[], 0)).unwrap();
2250        let index = rete.default_index();
2251        // The whole predicate, the most a bound object could ever cost.
2252        let whole = routed_scan_bytes(index, (None, rete.dictionary().predicate_id(value), None));
2253        for (_, lit) in owned.iter().step_by(57) {
2254            let q = [pat("?s", value, lit)];
2255            let mut slots = Slots::new();
2256            collect_pattern_slots(&q, &mut slots);
2257            let ctx = Ctx::new(&rete, slots);
2258            let got = bgp_min_scan_bytes(&ctx, index, &q).unwrap();
2259            assert!(got > 0, "{lit} routed to no tile");
2260            assert!(
2261                got < whole,
2262                "{lit} routed to the whole predicate ({got} of {whole})"
2263            );
2264        }
2265    }
2266
2267    /// The planner's size gates read ROW estimates, which do not depend on how
2268    /// the tiles are compressed. The same file opened resident (tile sizes are
2269    /// the decoded images) and lazily (tile sizes are the compressed frames)
2270    /// reports different bytes but must take the same decisions — the byte
2271    /// gates this replaced flipped plans when only the zstd level changed.
2272    #[test]
2273    fn plan_gates_do_not_move_with_the_compression() {
2274        let mut owned: Vec<(String, String, String)> = Vec::new();
2275        for i in 0..3000 {
2276            let s = format!("<http://ex/s{i}>");
2277            owned.push((
2278                s.clone(),
2279                "<http://ex/kind>".into(),
2280                format!("<http://ex/K{}>", i % 7),
2281            ));
2282            owned.push((s.clone(), "<http://ex/value>".into(), format!("\"v {i}\"")));
2283            if i % 50 == 0 {
2284                owned.push((s, "<http://ex/rare>".into(), "<http://ex/R>".into()));
2285            }
2286        }
2287        let mut db = DictionaryBuilder::new();
2288        for (s, p, o) in &owned {
2289            db.observe(s, p, o);
2290        }
2291        let dict = db.build();
2292        let mut ib = GraphIndexBuilder::new().with_tile_budget(1024);
2293        for (s, p, o) in &owned {
2294            ib.push(dict.encode(s, p, o).unwrap());
2295        }
2296        let bytes = write_file(&dict, &ib.build(), false, &[], 0);
2297        let leaked: &'static [u8] = Box::leak(bytes.clone().into_boxed_slice());
2298        let resident = Rete::open(&bytes).unwrap();
2299        let lazy = Rete::open_ranged_lazy(crate::reader::SliceReader::new(leaked)).unwrap();
2300        let shapes: Vec<Vec<TriplePattern>> = vec![
2301            vec![
2302                pat("?s", "<http://ex/rare>", "<http://ex/R>"),
2303                pat("?s", "<http://ex/value>", "?v"),
2304            ],
2305            vec![
2306                pat("?s", "<http://ex/kind>", "<http://ex/K3>"),
2307                pat("?s", "<http://ex/value>", "?v"),
2308            ],
2309            vec![
2310                pat("?s", "<http://ex/kind>", "?k"),
2311                pat("?s", "<http://ex/value>", "?v"),
2312            ],
2313            vec![
2314                pat("?s", "<http://ex/value>", "\"v 7\""),
2315                pat("?s", "<http://ex/kind>", "?k"),
2316            ],
2317        ];
2318        let decisions = |rete: &Rete| -> Vec<(Vec<u64>, bool, Option<u64>)> {
2319            shapes
2320                .iter()
2321                .map(|q| {
2322                    let mut slots = Slots::new();
2323                    collect_pattern_slots(q, &mut slots);
2324                    let ctx = Ctx::new(rete, slots);
2325                    let index = rete.default_index();
2326                    let lowered = lower(q, &ctx).unwrap();
2327                    let est = tile_estimates(&ctx, index, &lowered, &Default::default());
2328                    let lopsided = merge_seed_lopsided(&ctx, index, &lowered[0], &lowered[1]);
2329                    let min = bgp_min_estimate(&ctx, index, q).map(|e| e as u64);
2330                    (est.iter().map(|e| *e as u64).collect(), lopsided, min)
2331                })
2332                .collect()
2333        };
2334        assert_eq!(decisions(&resident), decisions(&lazy));
2335        // ... while the byte figures the gates used to read do differ.
2336        #[cfg(feature = "compression")]
2337        {
2338            let bytes_of = |rete: &Rete| {
2339                let q = &shapes[2];
2340                let mut slots = Slots::new();
2341                collect_pattern_slots(q, &mut slots);
2342                let ctx = Ctx::new(rete, slots);
2343                bgp_min_scan_bytes(&ctx, rete.default_index(), q)
2344            };
2345            assert_ne!(bytes_of(&resident), bytes_of(&lazy));
2346        }
2347    }
2348
2349    /// A fat predicate must look fat whichever layout stores the directory.
2350    /// On format 0x06 the tile directory is two-level and a leaf that is not
2351    /// resident is estimated from the root alone; it used to count as ONE
2352    /// tile, so a 2-million-row `rdfs:label` read as ~7 thousand rows on 0x06
2353    /// and 2 million on 0x05 — and the OPTIONAL joined to a 1000-row left side
2354    /// was hash-joined (the whole predicate materialized: 14.5 GB on a 8 B
2355    /// triple file) instead of probed per row. The same file in both layouts
2356    /// must give estimates of the same order, and the probe decision must be
2357    /// the same one.
2358    #[test]
2359    fn a_fat_predicate_estimates_alike_in_both_layouts() {
2360        let mut owned: Vec<(String, String, String)> = Vec::new();
2361        for i in 0..120_000 {
2362            let s = format!("<http://ex/s{i:06}>");
2363            owned.push((s.clone(), "<http://ex/kind>".into(), "<http://ex/K>".into()));
2364            owned.push((s, "<http://ex/value>".into(), format!("\"v {i}\"")));
2365        }
2366        let mut db = DictionaryBuilder::new();
2367        for (s, p, o) in &owned {
2368            db.observe(s, p, o);
2369        }
2370        let dict = db.build();
2371        let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2372        for (s, p, o) in &owned {
2373            ib.push(dict.encode(s, p, o).unwrap());
2374        }
2375        let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2376        let v6: &'static [u8] = Box::leak(
2377            crate::v06::write::convert_image(&v5, Default::default())
2378                .unwrap()
2379                .into_boxed_slice(),
2380        );
2381        let leaked5: &'static [u8] = Box::leak(v5.clone().into_boxed_slice());
2382        let flat = Rete::open_ranged_lazy(crate::reader::SliceReader::new(leaked5)).unwrap();
2383        let leafed = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v6)).unwrap();
2384        let q = [pat("?s", "<http://ex/value>", "?v")];
2385        let figures = |rete: &Rete| {
2386            let mut slots = Slots::new();
2387            collect_pattern_slots(&q, &mut slots);
2388            let ctx = Ctx::new(rete, slots);
2389            let index = rete.default_index();
2390            let total = bgp_total_estimate(&ctx, index, &q).unwrap();
2391            (total, probe_row_budget(total))
2392        };
2393        let (est5, budget5) = figures(&flat);
2394        let (est6, budget6) = figures(&leafed);
2395        assert!(est5 >= 70_000.0, "flat estimate {est5}");
2396        assert!(
2397            est6 >= est5 / 2.0 && est6 <= est5 * 2.0,
2398            "0x06 estimates {est6} where 0x05 estimates {est5}"
2399        );
2400        // The decision: a 1000-row left side probes in both.
2401        assert!(budget5.is_some_and(|b| b >= 1000), "{budget5:?}");
2402        assert!(budget6.is_some_and(|b| b >= 1000), "{budget6:?}");
2403    }
2404
2405    /// A selective object on a fat leading predicate must estimate small in
2406    /// both layouts: `?s rdf:type <rare class>` is a few tiles of a predicate
2407    /// that fills thousands, and the planner seeds the join from it. On 0x06 a
2408    /// leaf that is not resident used to be estimated without the bound object
2409    /// (the whole of `rdf:type`) or by the ids' average share of its leaf
2410    /// (skewed ids put a rare class beside a huge one).
2411    #[test]
2412    fn a_rare_object_of_a_fat_predicate_estimates_small_in_both_layouts() {
2413        let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2414        let mut owned: Vec<(String, String, String)> = Vec::new();
2415        for i in 0..120_000 {
2416            let s = format!("<http://ex/s{i:06}>");
2417            owned.push((s.clone(), ty.into(), "<http://ex/Common>".into()));
2418            owned.push((s.clone(), "<http://ex/other>".into(), format!("\"o {i}\"")));
2419            if i % 3000 == 0 {
2420                owned.push((s, ty.into(), "<http://ex/Rare>".into()));
2421            }
2422        }
2423        let mut db = DictionaryBuilder::new();
2424        for (s, p, o) in &owned {
2425            db.observe(s, p, o);
2426        }
2427        let dict = db.build();
2428        let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2429        for (s, p, o) in &owned {
2430            ib.push(dict.encode(s, p, o).unwrap());
2431        }
2432        let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2433        let v6: &'static [u8] = Box::leak(
2434            crate::v06::write::convert_image(&v5, Default::default())
2435                .unwrap()
2436                .into_boxed_slice(),
2437        );
2438        let leaked5: &'static [u8] = Box::leak(v5.into_boxed_slice());
2439        let figures = |rete: &Rete| {
2440            let est = |q: &[TriplePattern]| {
2441                let mut slots = Slots::new();
2442                collect_pattern_slots(q, &mut slots);
2443                let ctx = Ctx::new(rete, slots);
2444                bgp_min_estimate(&ctx, rete.default_index(), q).unwrap()
2445            };
2446            (
2447                est(&[pat("?s", ty, "<http://ex/Rare>")]),
2448                est(&[pat("?s", ty, "<http://ex/Common>")]),
2449                est(&[pat("?s", "<http://ex/other>", "?x")]),
2450            )
2451        };
2452        for (name, bytes) in [("0x05", leaked5), ("0x06", v6)] {
2453            let rete = Rete::open_ranged_lazy(crate::reader::SliceReader::new(bytes)).unwrap();
2454            let (rare, common, other) = figures(&rete);
2455            assert!(rare * 20.0 < other, "{name}: rare {rare} vs other {other}");
2456            assert!(
2457                rare * 20.0 < common,
2458                "{name}: rare {rare} vs common {common}"
2459            );
2460        }
2461    }
2462
2463    /// A probe prefetch covers a bounded window of its patterns — at most
2464    /// [`PROBE_WINDOW_TILES`] tiles — and leaves the rest for the next call, so
2465    /// a long list of probes never faults more tiles than the cache holds (the
2466    /// whole list at once evicted the early tiles before their probes ran, and
2467    /// each came back as a request of its own: G50a). What a window covers is
2468    /// resident: probing it reads nothing more.
2469    #[test]
2470    fn a_probe_prefetch_window_is_bounded_and_warm() {
2471        use crate::reader::{CountingReader, SliceReader};
2472        let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2473        let mut owned: Vec<(String, String, String)> = Vec::new();
2474        for i in 0..20_000 {
2475            let s = format!("<http://ex/s{i:06}>");
2476            owned.push((s.clone(), ty.into(), format!("<http://ex/C{}>", i % 7)));
2477            owned.push((s, "<http://ex/other>".into(), format!("\"o {}\"", i % 5000)));
2478        }
2479        let mut db = DictionaryBuilder::new();
2480        for (s, p, o) in &owned {
2481            db.observe(s, p, o);
2482        }
2483        let dict = db.build();
2484        let mut ib = GraphIndexBuilder::new().with_tile_budget(128);
2485        for (s, p, o) in &owned {
2486            ib.push(dict.encode(s, p, o).unwrap());
2487        }
2488        let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2489        let v6 = crate::v06::write::convert_image(&v5, Default::default()).unwrap();
2490        let leaked: &'static [u8] = Box::leak(v6.into_boxed_slice());
2491        let reader = std::sync::Arc::new(CountingReader::new(SliceReader::new(leaked)));
2492        let rete = Rete::open_ranged_lazy(reader.clone()).unwrap();
2493        let index = rete.default_index();
2494        // A cache far smaller than the tiles the probes touch: a prefetch of every
2495        // probe at once would evict its own early tiles.
2496        index.set_cache_cap(1 << 20);
2497        // Every third subject, as the probes of a long join.
2498        let pats: Vec<Pattern> = (0..20_000)
2499            .step_by(3)
2500            .map(|i| {
2501                let (s, _, _) = dict
2502                    .encode(&format!("<http://ex/s{i:06}>"), ty, "<http://ex/C0>")
2503                    .unwrap();
2504                (Some(s), None, None)
2505            })
2506            .collect();
2507        let mut from = 0;
2508        let mut windows = 0;
2509        while from < pats.len() {
2510            let n = index.prefetch_probe_tiles(&pats[from..]);
2511            assert!(n >= 1, "a window always makes progress");
2512            assert!(
2513                n < pats.len() - from || windows > 0,
2514                "the first window is cut"
2515            );
2516            let before = reader.requests();
2517            for &p in &pats[from..from + n] {
2518                assert!(index.scan_iter(p).next().is_some());
2519            }
2520            assert_eq!(reader.requests(), before, "a covered probe reads nothing");
2521            from += n;
2522            windows += 1;
2523        }
2524        assert!(windows > 1, "{windows} window(s) for {} probes", pats.len());
2525    }
2526
2527    /// The run of tiles holding a leading id is the same in both layouts, for
2528    /// every id and every permutation, and a leafed lookup does not walk the
2529    /// leaf tile by tile (a probe join runs it per row: 94,700 probes took 126 s
2530    /// on a 0x06 file against 1.3 s on its 0x05 copy).
2531    #[test]
2532    fn a_tile_span_is_the_same_in_both_layouts() {
2533        let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2534        let mut owned: Vec<(String, String, String)> = Vec::new();
2535        for i in 0..30_000 {
2536            let s = format!("<http://ex/s{i:06}>");
2537            owned.push((s.clone(), ty.into(), format!("<http://ex/C{}>", i % 7)));
2538            owned.push((s, "<http://ex/other>".into(), format!("\"o {}\"", i % 5000)));
2539        }
2540        let mut db = DictionaryBuilder::new();
2541        for (s, p, o) in &owned {
2542            db.observe(s, p, o);
2543        }
2544        let dict = db.build();
2545        let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2546        for (s, p, o) in &owned {
2547            ib.push(dict.encode(s, p, o).unwrap());
2548        }
2549        let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2550        let v6 = crate::v06::write::convert_image(&v5, Default::default()).unwrap();
2551        let (v5, v6): (&'static [u8], &'static [u8]) = (
2552            Box::leak(v5.into_boxed_slice()),
2553            Box::leak(v6.into_boxed_slice()),
2554        );
2555        let flat = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v5)).unwrap();
2556        let leafed = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v6)).unwrap();
2557        let (fi, li) = (flat.default_index(), leafed.default_index());
2558        let mut checked = 0;
2559        for perm in fi.perms().iter() {
2560            let si = perm.section_index();
2561            for a in (0..dict.term_count() + 2).step_by(97) {
2562                assert_eq!(
2563                    fi.tile_span(si, Some(a)),
2564                    li.tile_span(si, Some(a)),
2565                    "section {si}, id {a}"
2566                );
2567                checked += 1;
2568            }
2569            assert_eq!(fi.tile_span(si, None), li.tile_span(si, None));
2570        }
2571        assert!(checked > 100);
2572    }
2573
2574    /// Every join path the planner can pick — materialized prefix, probed last
2575    /// pattern, streamed seed with hashed or probed later patterns, streaming
2576    /// merge join — returns the same solution multiset. The thresholds are
2577    /// shrunk so a 400-triple graph takes each path.
2578    #[test]
2579    fn every_join_path_returns_the_same_solutions() {
2580        let mut owned: Vec<(String, String, String)> = Vec::new();
2581        let mut x: u64 = 7;
2582        let mut next = |m: u64| {
2583            x = x
2584                .wrapping_mul(6364136223846793005)
2585                .wrapping_add(1442695040888963407);
2586            (x >> 33) % m
2587        };
2588        for i in 0..60 {
2589            let s = format!("s{i}");
2590            owned.push((s.clone(), "a".into(), format!("C{}", next(3))));
2591            for p in 0..4 {
2592                for _ in 0..next(3) {
2593                    owned.push((s.clone(), format!("p{p}"), format!("s{}", next(60))));
2594                }
2595            }
2596        }
2597        let triples: Vec<(&str, &str, &str)> = owned
2598            .iter()
2599            .map(|(s, p, o)| (s.as_str(), p.as_str(), o.as_str()))
2600            .collect();
2601        let bytes = rete_from(&triples);
2602        let rete = Rete::open(&bytes).unwrap();
2603        let queries: Vec<Vec<TriplePattern>> = vec![
2604            vec![pat("?s", "p0", "?a"), pat("?s", "p1", "?b")],
2605            vec![pat("?s", "a", "C1"), pat("?s", "p0", "?a")],
2606            vec![pat("?s", "p0", "?a"), pat("?a", "p2", "?b")],
2607            vec![pat("s5", "p0", "?a"), pat("?a", "?p", "?o")],
2608            vec![pat("?s", "p0", "?x"), pat("?s", "p1", "?x")],
2609            vec![
2610                pat("?s", "p3", "?o"),
2611                pat("?o", "a", "C0"),
2612                pat("?s", "p1", "?z"),
2613            ],
2614            vec![
2615                pat("?s", "p0", "?a"),
2616                pat("?s", "p1", "?b"),
2617                pat("?b", "p2", "?c"),
2618            ],
2619        ];
2620        let run = |limits: Option<PlanLimits>| -> Vec<Vec<Vec<(String, String)>>> {
2621            TEST_LIMITS.with(|c| c.set(limits));
2622            let out = queries
2623                .iter()
2624                .map(|q| {
2625                    let mut slots = crate::row::Slots::new();
2626                    collect_pattern_slots(q, &mut slots);
2627                    let ctx = Ctx::new(&rete, slots);
2628                    let mut rows: Vec<Vec<(String, String)>> =
2629                        BgpSolutions::new(&ctx, rete.default_index(), q)
2630                            .map(|r| row_to_binding(&ctx, &r).into_iter().collect())
2631                            .collect();
2632                    rows.sort();
2633                    rows
2634                })
2635                .collect();
2636            TEST_LIMITS.with(|c| c.set(None));
2637            out
2638        };
2639        let reference = run(None);
2640        assert!(reference.iter().all(|r| !r.is_empty()), "{reference:?}");
2641        for (name, l) in [
2642            (
2643                "probe everything",
2644                PlanLimits {
2645                    probe_floor: 0.0,
2646                    stream_seed: f64::MAX,
2647                    hash_build: f64::MAX,
2648                },
2649            ),
2650            (
2651                "stream + hash",
2652                PlanLimits {
2653                    probe_floor: f64::MAX,
2654                    stream_seed: 0.0,
2655                    hash_build: f64::MAX,
2656                },
2657            ),
2658            (
2659                "stream + probe",
2660                PlanLimits {
2661                    probe_floor: f64::MAX,
2662                    stream_seed: 0.0,
2663                    hash_build: 0.0,
2664                },
2665            ),
2666            (
2667                "stream, all paths",
2668                PlanLimits {
2669                    probe_floor: 0.0,
2670                    stream_seed: 0.0,
2671                    hash_build: 30.0,
2672                },
2673            ),
2674        ] {
2675            assert_eq!(run(Some(l)), reference, "{name}");
2676        }
2677    }
2678
2679    #[test]
2680    fn single_pattern_binds_variable() {
2681        let bytes = rete_from(&[("Alice", "knows", "Bob"), ("Bob", "knows", "Carol")]);
2682        let rete = Rete::open(&bytes).unwrap();
2683        let sols = eval_bgp(&rete, &[pat("Alice", "knows", "?y")]);
2684        assert_eq!(sols.len(), 1);
2685        assert_eq!(sols[0]["y"], "Bob");
2686    }
2687
2688    #[test]
2689    fn two_hop_join_on_shared_variable() {
2690        // Alice -> Bob -> Carol, plus a dead-end branch.
2691        let bytes = rete_from(&[
2692            ("Alice", "knows", "Bob"),
2693            ("Bob", "knows", "Carol"),
2694            ("Carol", "knows", "Dave"),
2695            ("Alice", "knows", "Eve"), // Eve knows no one -> no 2-hop
2696        ]);
2697        let rete = Rete::open(&bytes).unwrap();
2698        let sols = eval_bgp(&rete, &[pat("?x", "knows", "?y"), pat("?y", "knows", "?z")]);
2699        // Alice-Bob-Carol, Bob-Carol-Dave.
2700        let mut got: Vec<_> = sols
2701            .iter()
2702            .map(|b| (b["x"].clone(), b["y"].clone(), b["z"].clone()))
2703            .collect();
2704        got.sort();
2705        assert_eq!(
2706            got,
2707            vec![
2708                ("Alice".into(), "Bob".into(), "Carol".into()),
2709                ("Bob".into(), "Carol".into(), "Dave".into()),
2710            ]
2711        );
2712    }
2713
2714    #[test]
2715    fn repeated_variable_within_pattern() {
2716        // A mutual/self relation: only Bob knows himself.
2717        let bytes = rete_from(&[("Alice", "knows", "Bob"), ("Bob", "knows", "Bob")]);
2718        let rete = Rete::open(&bytes).unwrap();
2719        let sols = eval_bgp(&rete, &[pat("?x", "knows", "?x")]);
2720        assert_eq!(sols.len(), 1);
2721        assert_eq!(sols[0]["x"], "Bob");
2722    }
2723
2724    #[test]
2725    fn no_solutions_yields_empty() {
2726        let bytes = rete_from(&[("Alice", "knows", "Bob")]);
2727        let rete = Rete::open(&bytes).unwrap();
2728        assert!(eval_bgp(&rete, &[pat("Alice", "likes", "?y")]).is_empty());
2729    }
2730
2731    /// A LUBM-Q7-shaped snowflake: a popular class enumeration (`?x a Student`)
2732    /// plus a selective adjacency seed (`<Prof> teacherOf ?y`). Exercises both the
2733    /// **class-enum seed deprioritization** (the join must not start from the huge
2734    /// `a Student` extent) and the **probe-the-tail hybrid** (the type checks are
2735    /// applied late, per row). The answer must equal a brute-force computation
2736    /// regardless of how the join is ordered/probed.
2737    #[test]
2738    fn snowflake_type_and_adjacency_matches_reference() {
2739        const TYPE: &str = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2740        let mut triples: Vec<(String, String, String)> = Vec::new();
2741        // 60 students, each a Student and taking 2 courses (c{i%5}, c{(i+1)%5}).
2742        for i in 0..60 {
2743            let s = format!("S{i}");
2744            triples.push((s.clone(), TYPE.into(), "Student".into()));
2745            triples.push((s.clone(), "takesCourse".into(), format!("c{}", i % 5)));
2746            triples.push((s, "takesCourse".into(), format!("c{}", (i + 1) % 5)));
2747        }
2748        // 5 courses; the professor teaches only c0 and c2.
2749        for j in 0..5 {
2750            triples.push((format!("c{j}"), TYPE.into(), "Course".into()));
2751        }
2752        triples.push(("Prof".into(), "teacherOf".into(), "c0".into()));
2753        triples.push(("Prof".into(), "teacherOf".into(), "c2".into()));
2754
2755        let refs: Vec<(&str, &str, &str)> = triples
2756            .iter()
2757            .map(|(s, p, o)| (s.as_str(), p.as_str(), o.as_str()))
2758            .collect();
2759        let bytes = rete_from(&refs);
2760        let rete = Rete::open(&bytes).unwrap();
2761
2762        let got: std::collections::BTreeSet<(String, String)> = eval_bgp(
2763            &rete,
2764            &[
2765                pat("?x", TYPE, "Student"),
2766                pat("?y", TYPE, "Course"),
2767                pat("?x", "takesCourse", "?y"),
2768                pat("Prof", "teacherOf", "?y"),
2769            ],
2770        )
2771        .into_iter()
2772        .map(|b| (b["x"].clone(), b["y"].clone()))
2773        .collect();
2774
2775        // Brute force: students taking a course the professor teaches (c0 or c2).
2776        let taught = ["c0", "c2"];
2777        let mut want = std::collections::BTreeSet::new();
2778        for i in 0..60 {
2779            for c in [i % 5, (i + 1) % 5] {
2780                let course = format!("c{c}");
2781                if taught.contains(&course.as_str()) {
2782                    want.insert((format!("S{i}"), course));
2783                }
2784            }
2785        }
2786        assert_eq!(got, want, "snowflake join must match the brute-force set");
2787        assert!(!want.is_empty(), "sanity: the reference set is non-empty");
2788    }
2789
2790    /// A subject-subject join (`?x a ?av . ?x b ?bv`) is the same-role shape the
2791    /// merge join handles: both patterns sort on the subject column. With multiple
2792    /// `a` and `b` values per subject it must emit the full cross product per
2793    /// subject (equal-key run handling) and drop subjects missing either side.
2794    #[test]
2795    fn merge_join_subject_star_cross_product() {
2796        let bytes = rete_from(&[
2797            ("x", "a", "a1"),
2798            ("x", "a", "a2"),
2799            ("x", "b", "b1"),
2800            ("x", "b", "b2"),
2801            ("y", "a", "a3"),
2802            ("y", "b", "b3"),
2803            ("z", "a", "a4"), // z has no `b` → contributes no join row
2804        ]);
2805        let rete = Rete::open(&bytes).unwrap();
2806        let mut got: Vec<(String, String, String)> =
2807            eval_bgp(&rete, &[pat("?x", "a", "?av"), pat("?x", "b", "?bv")])
2808                .iter()
2809                .map(|m| (m["x"].clone(), m["av"].clone(), m["bv"].clone()))
2810                .collect();
2811        got.sort();
2812        let mut want: Vec<(String, String, String)> = [
2813            ("x", "a1", "b1"),
2814            ("x", "a1", "b2"),
2815            ("x", "a2", "b1"),
2816            ("x", "a2", "b2"),
2817            ("y", "a3", "b3"),
2818        ]
2819        .into_iter()
2820        .map(|(a, b, c)| (a.to_string(), b.to_string(), c.to_string()))
2821        .collect();
2822        want.sort();
2823        assert_eq!(got, want, "same-role merge must equal the brute-force join");
2824    }
2825}