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