Skip to main content

rete_core/
index.rs

1//! Permutation index set (SPO / POS / OSP) over integer triples (SPEC.md §6).
2//!
3//! The three orders together answer every triple-pattern shape: for any subset
4//! of bound `(s, p, o)` components, at least one permutation sorts those bound
5//! components into a leading prefix, turning the lookup into a range scan.
6//!
7//! Each permutation is **tiled** (format v0.2): consecutive runs of whole
8//! a-groups packed to a byte budget ([`INDEX_TILE_BUDGET`]), each tile a
9//! self-contained [`TripleBlock`]. A bound leading id routes to exactly one
10//! tile (binary search over the tile ranges), then jumps to its a-group via
11//! the tile's lazily-built [`GroupDirectory`]; unbound scans chain all tiles
12//! with per-tile zone-map pruning. On disk each tile is compressed
13//! independently, so a ranged reader can fetch just the tiles a query needs.
14//! v0.1 single-block sections are still read (one tile per permutation).
15
16use std::sync::Arc;
17
18use crate::chunk_cache::{CacheEntry, ChunkCache};
19use crate::triples::{GroupDirectory, Triple, TripleBlock, TripleBlockBuilder};
20
21/// A triple pattern: `None` is an unbound variable, `Some(id)` a bound term.
22pub type Pattern = (Option<u32>, Option<u32>, Option<u32>);
23
24/// The most tiles one probe-prefetch window faults ([`GraphIndex::prefetch_probe_tiles`]).
25pub(crate) const PROBE_WINDOW_TILES: usize = 1024;
26
27/// The tiles a window of upcoming probes will route to, gathered one pattern
28/// at a time ([`GraphIndex::probe_batch_add`]) so the window can grow until it
29/// is full, then faulted together ([`GraphIndex::probe_batch_fault`]).
30///
31/// Bounded in tiles ([`PROBE_WINDOW_TILES`]) and in stored bytes (an eighth
32/// of the tile cache, within 256 KiB–64 MiB): faulting every tile of a long probe
33/// list at once overran the cache, which evicted the early tiles before their
34/// probes ran, and each then came back as a request of its own, one round trip
35/// at a time (G50a).
36#[derive(Default)]
37pub(crate) struct ProbeBatch {
38    want: [std::collections::BTreeSet<usize>; NUM_PERMS],
39    tiles: usize,
40    bytes: u64,
41    /// Patterns accepted so far.
42    patterns: usize,
43}
44
45/// Default per-tile budget in (uncompressed) encoded bytes. Tiles are the
46/// independently-compressed, independently-fetchable units of a permutation
47/// section: ~64 KiB matches both zstd's sweet spot and one HTTP range read.
48/// The budget a build uses is [`crate::write_opts::tile_budget`] (`--tile-kib`).
49pub const INDEX_TILE_BUDGET: usize = crate::write_opts::DEFAULT_TILE_BUDGET_BYTES;
50
51/// Geometric tile-prefetch ramp for an unbound (multi-tile) scan (see
52/// [`GraphIndex::scan_iter`]). The first coalesced batch faults this many
53/// tiles; each subsequent batch doubles up to [`PREFETCH_WINDOW_MAX`]. Small
54/// enough that `LIMIT 1` fetches only a few tiles, large enough that a full
55/// scan still coalesces into a handful of range reads.
56const PREFETCH_WINDOW_START: usize = 4;
57const PREFETCH_WINDOW_MAX: usize = 512;
58
59/// Fetches one tile's (uncompressed) block image on demand: the bridge that
60/// lets a remote `GraphIndex` fault tiles in over a `RangeReader` without this
61/// module knowing about I/O. `None` = the fetch failed; the index records the
62/// failure ([`GraphIndex::load_incomplete`]) and the scan sees an empty tile —
63/// callers running over remote data MUST check the flag after evaluating.
64pub type TileLoader = Box<dyn Fn(usize, usize) -> Option<Vec<u8>> + Send + Sync>;
65
66/// Fetches **many** tiles of one section in one round trip: given the section
67/// and the (ascending) indices of the tiles wanted, returns each tile's
68/// uncompressed block image in the same order. The ranged reader implements
69/// this by coalescing byte-adjacent tile ranges into single range reads, so a
70/// full-section scan costs a handful of requests instead of one per tile.
71/// `None` = the batch failed as a whole; callers fall back to the per-tile
72/// [`TileLoader`] (which records per-tile failures).
73pub type TileBulkLoader = Box<dyn Fn(usize, &[usize]) -> Option<Vec<Vec<u8>>> + Send + Sync>;
74
75/// One tile of a permutation section: a fully self-contained [`TripleBlock`]
76/// over a consecutive run of whole a-groups, plus the leading-id range it
77/// covers (for routing without parsing or fetching) and its lazily-built group
78/// directory (for intra-tile point lookups). The block image itself may be
79/// local (built/decoded eagerly) or faulted in by the index's [`TileLoader`].
80pub struct Tile {
81    min_a: u32,
82    max_a: u32,
83    /// Optional **tile synopsis**: the inclusive min/max of the two non-leading
84    /// columns `(min_b, max_b, min_c, max_c)`, read from the directory trailer of
85    /// a synopsis-carrying file. Lets a scan prune this tile by a bound secondary
86    /// component *before* faulting it (remote reads). `None` = no synopsis (an
87    /// older file, or a locally-built/opened tile) — then nothing is pruned early
88    /// and the in-tile zone map prunes after the tile is in hand, as before.
89    pub(crate) syn: Option<(u32, u32, u32, u32)>,
90    /// Encoded byte length of this tile (compressed on-disk size for a remote
91    /// tile, in-memory image size for a local one; 0 = unknown). Feeds the join
92    /// planner's fatness gates without faulting any data.
93    len: u32,
94    /// Build-time staging only: a locally-built or locally-decoded tile's body
95    /// waits here until [`GraphIndex::from_sections`] moves it into the shared
96    /// [`ChunkCache`] (keyed by `(section, tile)`) and clears it. `None`
97    /// afterward, and for a remote tile whose body faults in through the loader.
98    /// The long-lived retention is the cache, not this field.
99    staged: Option<Vec<u8>>,
100}
101
102impl Tile {
103    fn local(min_a: u32, max_a: u32, bytes: Vec<u8>) -> Self {
104        let len = bytes.len().min(u32::MAX as usize) as u32;
105        Tile {
106            min_a,
107            max_a,
108            syn: None,
109            len,
110            staged: Some(bytes),
111        }
112    }
113
114    /// A remote tile's descriptor with its stored length.
115    pub(crate) fn remote_with_len(
116        min_a: u32,
117        max_a: u32,
118        syn: Option<(u32, u32, u32, u32)>,
119        len: u32,
120    ) -> Self {
121        Tile {
122            len,
123            ..Tile::remote(min_a, max_a, syn)
124        }
125    }
126
127    fn remote(min_a: u32, max_a: u32, syn: Option<(u32, u32, u32, u32)>) -> Self {
128        Tile {
129            min_a,
130            max_a,
131            syn,
132            len: 0,
133            staged: None,
134        }
135    }
136
137    /// Encoded byte length (see the field doc); falls back to a still-staged
138    /// body's size when the directory didn't provide one.
139    pub(crate) fn encoded_len(&self) -> u64 {
140        if self.len > 0 {
141            self.len as u64
142        } else {
143            self.staged.as_ref().map_or(0, |d| d.len() as u64)
144        }
145    }
146
147    /// Leading-component (permuted `a`) range this tile covers, inclusive.
148    pub fn leading_range(&self) -> (u32, u32) {
149        (self.min_a, self.max_a)
150    }
151
152    /// Could this tile hold a triple with the given bound non-leading components,
153    /// per its synopsis? `true` when there is no synopsis (can't rule it out) or
154    /// the bound `b`/`c` fall inside the recorded ranges. Conservative: a `false`
155    /// is a *proven* miss (the in-tile zone map would reject the same tile), so
156    /// skipping the fetch never drops a result.
157    pub(crate) fn syn_admits(&self, pb: Option<u32>, pc: Option<u32>) -> bool {
158        match self.syn {
159            None => true,
160            Some((min_b, max_b, min_c, max_c)) => {
161                let ok = |v: Option<u32>, lo: u32, hi: u32| v.is_none_or(|x| lo <= x && x <= hi);
162                ok(pb, min_b, max_b) && ok(pc, min_c, max_c)
163            }
164        }
165    }
166}
167
168/// Fetches stored leaf blocks of a two-level directory (format `0x06`, SPEC.md
169/// §4.4): absolute `(offset, len)` ranges in, their bytes out, in order — one
170/// batched read. `None` = the batch failed.
171pub type LeafFetch = Arc<dyn Fn(&[(u64, u64)]) -> Option<Vec<Vec<u8>>> + Send + Sync>;
172
173/// A two-level directory whose leaves fault on demand (a tile directory, a
174/// chunk directory): what [`ensure_leaves_across`] needs to fetch the leaves of
175/// several directories in **one** batched read instead of one read each.
176pub(crate) trait LeafDir {
177    /// Leaf `li`'s absolute stored range, when it exists and is not resident.
178    fn missing_leaf(&self, li: usize) -> Option<(u64, u64)>;
179    /// Decode `stored` as leaf `li` and keep it (recording a failure).
180    fn install_leaf(&self, li: usize, stored: &[u8]);
181    /// Record that a batch carrying this directory's leaves failed.
182    fn fail_leaves(&self);
183    /// The batched reader the directory's leaves come through.
184    fn leaf_fetch(&self) -> &LeafFetch;
185}
186
187/// Fault the not-yet-resident leaves `lis` of each directory in `dirs` in one
188/// batched read, through the first directory's fetcher. Every directory of one
189/// open reads through the same reader, so this is a single round trip where one
190/// read per directory was one per directory in sequence (a lookup that names
191/// terms in three dictionary sections, a pattern estimated on four
192/// permutations). A failed batch marks every directory it carried.
193pub(crate) fn ensure_leaves_across(dirs: &[(&dyn LeafDir, &[usize])]) {
194    let mut ranges: Vec<(u64, u64)> = Vec::new();
195    let mut slots: Vec<(usize, usize)> = Vec::new();
196    for (di, (dir, lis)) in dirs.iter().enumerate() {
197        // The same leaf can come many times over (a join probing 460 k subjects
198        // of one leaf): fetch each once.
199        let mut lis: Vec<usize> = lis.to_vec();
200        lis.sort_unstable();
201        lis.dedup();
202        for li in lis {
203            if let Some(r) = dir.missing_leaf(li) {
204                ranges.push(r);
205                slots.push((di, li));
206            }
207        }
208    }
209    let Some((first, _)) = dirs.first() else {
210        return;
211    };
212    if ranges.is_empty() {
213        return;
214    }
215    match (first.leaf_fetch())(&ranges) {
216        Some(blobs) if blobs.len() == slots.len() => {
217            for (&(di, li), b) in slots.iter().zip(&blobs) {
218                dirs[di].0.install_leaf(li, b);
219            }
220        }
221        _ => {
222            for &(di, _) in &slots {
223                dirs[di].0.fail_leaves();
224            }
225        }
226    }
227}
228
229/// One leaf of a permutation's tile directory, as the `0x06` root describes it.
230#[derive(Debug, Clone)]
231pub struct TileLeaf {
232    /// Index of the leaf's first tile in the permutation.
233    pub first: usize,
234    /// Tiles in the leaf.
235    pub n: usize,
236    /// Leading-id range of the leaf (first tile's min, last tile's max).
237    pub min_a: u32,
238    /// See `min_a`.
239    pub max_a: u32,
240    /// Absolute range of the stored leaf block.
241    pub leaf: (u64, u64),
242    /// Absolute offset of the leaf's first tile.
243    pub tile_base: u64,
244}
245
246/// A permutation's tile directory whose entries live in leaf blocks faulted
247/// on demand and kept for the session (format `0x06`). Routing narrows by the
248/// leaves' leading-id ranges first, so a bound lookup faults one leaf.
249/// A faulted tile-directory leaf: each tile and its absolute offset.
250type TileCell = std::sync::OnceLock<Box<[(Tile, u64)]>>;
251
252pub struct LeafedTiles {
253    leaves: Vec<TileLeaf>,
254    cells: Vec<TileCell>,
255    total: usize,
256    total_bytes: u64,
257    fetch: LeafFetch,
258    codec: u8,
259    /// Decompression bound on a leaf.
260    max_block: u64,
261    failed: std::sync::atomic::AtomicBool,
262}
263
264/// The tile standing in for one whose leaf could not be read: it routes
265/// nowhere and its synopsis admits nothing. The failure is recorded.
266static UNREADABLE_TILE: Tile = Tile {
267    min_a: u32::MAX,
268    max_a: u32::MAX,
269    syn: Some((1, 0, 1, 0)),
270    len: 0,
271    staged: None,
272};
273
274impl LeafDir for LeafedTiles {
275    fn missing_leaf(&self, li: usize) -> Option<(u64, u64)> {
276        (li < self.cells.len() && self.cells[li].get().is_none()).then(|| self.leaves[li].leaf)
277    }
278
279    fn install_leaf(&self, li: usize, stored: &[u8]) {
280        match self.decode_leaf(li, stored) {
281            Some(v) => {
282                let _ = self.cells[li].set(v);
283            }
284            None => self
285                .failed
286                .store(true, std::sync::atomic::Ordering::Relaxed),
287        }
288    }
289
290    fn fail_leaves(&self) {
291        self.failed
292            .store(true, std::sync::atomic::Ordering::Relaxed);
293    }
294
295    fn leaf_fetch(&self) -> &LeafFetch {
296        &self.fetch
297    }
298}
299
300impl LeafedTiles {
301    /// Bound every leaf decompression at `max` bytes (from the `0x06` root).
302    pub fn with_max_block(mut self, max: u64) -> Self {
303        self.max_block = max;
304        self
305    }
306
307    /// A leafed directory of `total` tiles and `total_bytes` stored bytes.
308    pub fn new(
309        leaves: Vec<TileLeaf>,
310        total: usize,
311        total_bytes: u64,
312        fetch: LeafFetch,
313        codec: u8,
314    ) -> Self {
315        let cells = leaves.iter().map(|_| std::sync::OnceLock::new()).collect();
316        LeafedTiles {
317            leaves,
318            cells,
319            total,
320            total_bytes,
321            fetch,
322            codec,
323            max_block: u64::MAX,
324            failed: std::sync::atomic::AtomicBool::new(false),
325        }
326    }
327
328    /// How many tiles hold leading id `a`, from the root alone and without
329    /// reading anything (the `rete cost` preview). A resident leaf is counted
330    /// exactly; one that is not is estimated from what the root records of it:
331    /// a leaf whose whole range is `a` holds `n` such tiles, and a leaf shared
332    /// with other ids holds its tiles' share of the range (at least one). Skewed
333    /// ids make the shared-leaf figure rough; [`Self::admitted_estimate`] reads
334    /// instead.
335    pub(crate) fn admitted_unfaulted(&self, a: u32) -> f64 {
336        let mut tiles = 0.0;
337        for (li, lf) in self.leaves.iter().enumerate() {
338            if a < lf.min_a || a > lf.max_a {
339                continue;
340            }
341            tiles += match self.cells[li].get() {
342                Some(v) => v
343                    .iter()
344                    .filter(|(t, _)| t.min_a <= a && a <= t.max_a)
345                    .count() as f64,
346                None if lf.min_a == lf.max_a => lf.n as f64,
347                None => {
348                    let width = (lf.max_a as f64 - lf.min_a as f64) + 1.0;
349                    (lf.n as f64 / width).max(1.0)
350                }
351            };
352        }
353        tiles
354    }
355
356    /// The `(first tile's min_b, last tile's max_b)` of leaf `li`, faulting it;
357    /// `None` when the leaf cannot be read or a tile carries no synopsis.
358    fn leaf_b_span(&self, li: usize) -> Option<(u32, u32)> {
359        self.ensure_leaves(&[li]);
360        let v = self.cells[li].get()?;
361        let first = v.first()?.0.syn?;
362        let last = v.last()?.0.syn?;
363        Some((first.0, last.1))
364    }
365
366    /// The leaves of the run of tiles holding leading id `a` that [`admitted_estimate`](Self::admitted_estimate)
367    /// counts exactly: the first and the last, when shared with other ids.
368    pub(crate) fn run_end_leaves(&self, a: u32) -> Vec<usize> {
369        let first = self.leaves.partition_point(|lf| lf.max_a < a);
370        let mut last = first;
371        while last < self.leaves.len() && self.leaves[last].min_a <= a {
372            last += 1;
373        }
374        let shared = |li: usize| !(self.leaves[li].min_a == a && self.leaves[li].max_a == a);
375        let mut out = Vec::new();
376        if first < last {
377            if shared(first) {
378                out.push(first);
379            }
380            if last - 1 != first && shared(last - 1) {
381                out.push(last - 1);
382            }
383        }
384        out
385    }
386
387    /// Exact count of leaf `li`'s tiles that hold `a` and admit `pb`/`pc`,
388    /// faulting the leaf; the unfaulted figure if it cannot be read.
389    fn count_in_leaf(&self, li: usize, a: u32, pb: Option<u32>, pc: Option<u32>) -> f64 {
390        self.ensure_leaves(&[li]);
391        match self.cells[li].get() {
392            Some(v) => v
393                .iter()
394                .filter(|(t, _)| t.min_a <= a && a <= t.max_a && t.syn_admits(pb, pc))
395                .count() as f64,
396            None => {
397                let lf = &self.leaves[li];
398                let width = (lf.max_a as f64 - lf.min_a as f64) + 1.0;
399                (lf.n as f64 / width).max(1.0)
400            }
401        }
402    }
403
404    /// The tiles that hold leading id `a` and admit the bound second and third
405    /// keys `pb`/`pc`, counted from the root plus a few leaf reads (all kept
406    /// for the session; the lookup that follows needs them anyway).
407    ///
408    /// The planner's row estimates stand on this, so it must neither say "one
409    /// tile" for a predicate that fills a leaf nor ignore a bound class:
410    /// `?s rdf:type <small class>` is a few tiles of an 851 M-row predicate.
411    /// - A leaf shared with other ids (at most two per id) is read and counted
412    ///   exactly, synopsis included.
413    /// - Leaves wholly inside `a` cost nothing when only `a` is bound (each is
414    ///   `n` tiles). With `pb` bound they are ordered by `pb` (tiles are cut in
415    ///   `(a, b, c)` order), so the admitted tiles are a contiguous run that two
416    ///   binary searches over the leaves' `b` spans bound: O(log leaves) reads,
417    ///   then the run's end leaves are counted exactly and the leaves between
418    ///   them are all `n`.
419    pub(crate) fn admitted_estimate(&self, a: u32, pb: Option<u32>, pc: Option<u32>) -> f64 {
420        let first = self.leaves.partition_point(|lf| lf.max_a < a);
421        let mut last = first;
422        while last < self.leaves.len() && self.leaves[last].min_a <= a {
423            last += 1;
424        }
425        if first >= last {
426            return 0.0;
427        }
428        let mut tiles = 0.0;
429        // Pure leaves are contiguous: every shared one is first or last.
430        let pure = |li: usize| self.leaves[li].min_a == a && self.leaves[li].max_a == a;
431        let (mut p0, mut p1) = (first, last);
432        if !pure(first) {
433            tiles += self.count_in_leaf(first, a, pb, pc);
434            p0 += 1;
435        }
436        if p1 > p0 && !pure(p1 - 1) {
437            tiles += self.count_in_leaf(p1 - 1, a, pb, pc);
438            p1 -= 1;
439        }
440        if p0 >= p1 {
441            return tiles;
442        }
443        // Wholly-`a` leaves p0..p1.
444        let Some(b) = pb else {
445            return tiles + self.leaves[p0..p1].iter().map(|l| l.n as f64).sum::<f64>();
446        };
447        // First leaf whose last tile reaches `b`; first leaf that starts past it.
448        let search = |past: bool| -> Option<usize> {
449            let (mut lo, mut hi) = (p0, p1);
450            while lo < hi {
451                let mid = lo + (hi - lo) / 2;
452                let (min_b, max_b) = self.leaf_b_span(mid)?;
453                if if past { min_b > b } else { max_b >= b } {
454                    hi = mid;
455                } else {
456                    lo = mid + 1;
457                }
458            }
459            Some(lo)
460        };
461        let (Some(f), Some(g)) = (search(false), search(true)) else {
462            // A leaf could not be read: no narrowing, count them all.
463            return tiles + self.leaves[p0..p1].iter().map(|l| l.n as f64).sum::<f64>();
464        };
465        if f >= g {
466            return tiles;
467        }
468        // Leaves f..g may hold `b`; those strictly between the ends are all `b`.
469        tiles += self.count_in_leaf(f, a, pb, pc);
470        if g - 1 > f {
471            tiles += self.count_in_leaf(g - 1, a, pb, pc);
472            tiles += self.leaves[f + 1..g - 1]
473                .iter()
474                .map(|l| l.n as f64)
475                .sum::<f64>();
476        }
477        tiles
478    }
479
480    fn leaf_of(&self, ti: usize) -> usize {
481        self.leaves
482            .partition_point(|l| l.first <= ti)
483            .saturating_sub(1)
484    }
485
486    fn decode_leaf(&self, li: usize, stored: &[u8]) -> Option<Box<[(Tile, u64)]>> {
487        let l = &self.leaves[li];
488        let raw = crate::file::decompress_bounded(self.codec, stored, self.max_block).ok()?;
489        let ents = crate::v06::decode_tile_leaf(&raw, l.n).ok()?;
490        let mut at = l.tile_base;
491        let mut out = Vec::with_capacity(ents.len());
492        for e in ents {
493            let mut t = Tile::remote(e.min_a, e.max_a, Some(e.syn));
494            t.len = e.clen.min(u32::MAX as u64) as u32;
495            out.push((t, at));
496            at = at.checked_add(e.clen)?;
497        }
498        Some(out.into_boxed_slice())
499    }
500
501    /// Fault every not-yet-resident leaf of `lis` in one batched read.
502    pub fn ensure_leaves(&self, lis: &[usize]) {
503        ensure_leaves_across(&[(self, lis)]);
504    }
505
506    /// Fault the leaves covering tiles `[start, end)`.
507    pub fn ensure_span(&self, start: usize, end: usize) {
508        if start >= end || start >= self.total {
509            return;
510        }
511        let a = self.leaf_of(start);
512        let b = self.leaf_of(end.min(self.total) - 1);
513        self.ensure_leaves(&(a..=b).collect::<Vec<_>>());
514    }
515
516    fn entry(&self, ti: usize) -> Option<&(Tile, u64)> {
517        if ti >= self.total {
518            return None;
519        }
520        let li = self.leaf_of(ti);
521        if self.cells[li].get().is_none() {
522            self.ensure_leaves(&[li]);
523        }
524        self.cells[li].get()?.get(ti - self.leaves[li].first)
525    }
526
527    /// Tile `ti`'s absolute stored range, faulting its leaf.
528    pub fn range(&self, ti: usize) -> Option<(u64, u64)> {
529        self.entry(ti).map(|(t, off)| (*off, t.len as u64))
530    }
531
532    /// Did a leaf fault fail?
533    pub fn load_failed(&self) -> bool {
534        self.failed.load(std::sync::atomic::Ordering::Relaxed)
535    }
536
537    /// Forget a recorded leaf-fault failure.
538    pub fn reset_load_failure(&self) {
539        self.failed
540            .store(false, std::sync::atomic::Ordering::Relaxed);
541    }
542
543    /// Bytes held by the leaves faulted so far.
544    fn resident_bytes(&self) -> u64 {
545        let n: usize = self
546            .cells
547            .iter()
548            .filter_map(|c| c.get())
549            .map(|v| v.len())
550            .sum();
551        (n * (std::mem::size_of::<Tile>() + 8)) as u64
552            + (self.leaves.len() * std::mem::size_of::<TileLeaf>()) as u64
553    }
554}
555
556/// A tile list produced on first use by a closure (see [`TileList::Deferred`]).
557pub struct DeferredTiles {
558    cell: std::sync::OnceLock<Vec<Tile>>,
559    /// Stored bytes the planner may assume before the descriptors exist.
560    approx_bytes: u64,
561    load: Box<dyn Fn() -> Option<Vec<Tile>> + Send + Sync>,
562    failed: std::sync::atomic::AtomicBool,
563}
564
565impl DeferredTiles {
566    /// Descriptors built by `load` on first use and kept. A failed load is recorded
567    /// (see [`GraphIndex::load_incomplete`]) and reads as no tiles until retried.
568    pub fn new(approx_bytes: u64, load: Box<dyn Fn() -> Option<Vec<Tile>> + Send + Sync>) -> Self {
569        DeferredTiles {
570            cell: std::sync::OnceLock::new(),
571            approx_bytes,
572            load,
573            failed: std::sync::atomic::AtomicBool::new(false),
574        }
575    }
576
577    fn get(&self) -> &[Tile] {
578        if let Some(v) = self.cell.get() {
579            return v;
580        }
581        match (self.load)() {
582            Some(v) => {
583                // A racing thread may have built it first; both are the same.
584                let _ = self.cell.set(v);
585                self.cell.get().map_or(&[][..], Vec::as_slice)
586            }
587            None => {
588                // Not cached: the next use retries.
589                self.failed
590                    .store(true, std::sync::atomic::Ordering::Relaxed);
591                &[]
592            }
593        }
594    }
595}
596
597/// A permutation's tile directory: resident in full (`0x05`, built indexes),
598/// or two-level with leaves faulted on demand (`0x06`).
599pub enum TileList {
600    /// Every tile descriptor resident.
601    Full(Vec<Tile>),
602    /// Root resident, leaves on demand.
603    Leafed(Arc<LeafedTiles>),
604    /// Descriptors built on first use (a quad-index view's slice of one order's
605    /// directory: an order a query never touches is never fetched).
606    Deferred(Arc<DeferredTiles>),
607}
608
609impl Default for TileList {
610    fn default() -> Self {
611        TileList::Full(Vec::new())
612    }
613}
614
615impl std::ops::Index<usize> for TileList {
616    type Output = Tile;
617    fn index(&self, ti: usize) -> &Tile {
618        match self {
619            TileList::Full(v) => &v[ti],
620            TileList::Deferred(d) => d.get().get(ti).unwrap_or(&UNREADABLE_TILE),
621            TileList::Leafed(l) => match l.entry(ti) {
622                Some((t, _)) => t,
623                None => {
624                    l.failed.store(true, std::sync::atomic::Ordering::Relaxed);
625                    &UNREADABLE_TILE
626                }
627            },
628        }
629    }
630}
631
632impl TileList {
633    /// Tiles known without building anything (0 for a deferred list that has
634    /// not been built).
635    fn known_len(&self) -> usize {
636        match self {
637            TileList::Deferred(d) => d.cell.get().map_or(0, Vec::len),
638            other => other.len(),
639        }
640    }
641
642    /// Number of tiles.
643    pub fn len(&self) -> usize {
644        match self {
645            TileList::Full(v) => v.len(),
646            TileList::Deferred(d) => d.get().len(),
647            TileList::Leafed(l) => l.total,
648        }
649    }
650
651    /// No tiles?
652    pub fn is_empty(&self) -> bool {
653        self.len() == 0
654    }
655
656    /// The resident descriptors of a full list (`None` for a leafed one).
657    pub fn as_full(&self) -> Option<&[Tile]> {
658        match self {
659            TileList::Full(v) => Some(v),
660            TileList::Deferred(d) => Some(d.get()),
661            TileList::Leafed(_) => None,
662        }
663    }
664
665    /// Every tile, in order, faulting all leaves first (one batch).
666    pub fn iter(&self) -> impl Iterator<Item = &Tile> {
667        if let TileList::Leafed(l) = self {
668            l.ensure_span(0, l.total);
669        }
670        (0..self.len()).map(move |i| &self[i])
671    }
672
673    /// The first tile, if any.
674    pub fn first(&self) -> Option<&Tile> {
675        (!self.is_empty()).then(|| &self[0])
676    }
677
678    /// The last tile, if any.
679    pub fn last(&self) -> Option<&Tile> {
680        (!self.is_empty()).then(|| &self[self.len() - 1])
681    }
682
683    /// Fault the leaves covering `[start, end)` in one batch (a no-op on a full
684    /// list).
685    pub fn ensure_span(&self, start: usize, end: usize) {
686        if let TileList::Leafed(l) = self {
687            l.ensure_span(start, end);
688        }
689    }
690
691    /// Index of the first tile whose `max_a >= a` (`len()` if none). A leafed
692    /// list narrows to the one leaf that can hold it before faulting.
693    pub fn first_max_ge(&self, a: u32) -> usize {
694        match self {
695            TileList::Full(v) => v.partition_point(|t| t.max_a < a),
696            TileList::Deferred(d) => d.get().partition_point(|t| t.max_a < a),
697            TileList::Leafed(l) => {
698                let li = l.leaves.partition_point(|lf| lf.max_a < a);
699                if li >= l.leaves.len() {
700                    return l.total;
701                }
702                let lf = &l.leaves[li];
703                l.ensure_leaves(&[li]);
704                // Binary search inside the faulted leaf: stepping with `self[i]`
705                // costs a leaf lookup per tile, and a lookup runs this per probe
706                // row (94,700 probes x a leaf of thousands of tiles was 126 s).
707                match l.cells[li].get() {
708                    Some(v) => lf.first + v.partition_point(|(t, _)| t.max_a < a),
709                    None => lf.first,
710                }
711            }
712        }
713    }
714
715    /// Index of the first tile whose `min_a > a` (`len()` if none): the end of
716    /// the run of tiles that can hold leading id `a`. Faults one leaf at most.
717    pub fn first_min_gt(&self, a: u32) -> usize {
718        match self {
719            TileList::Full(v) => v.partition_point(|t| t.min_a <= a),
720            TileList::Deferred(d) => d.get().partition_point(|t| t.min_a <= a),
721            TileList::Leafed(l) => {
722                let next = l.leaves.partition_point(|lf| lf.min_a <= a);
723                if next == 0 {
724                    return 0;
725                }
726                let li = next - 1;
727                let lf = &l.leaves[li];
728                l.ensure_leaves(&[li]);
729                match l.cells[li].get() {
730                    Some(v) => lf.first + v.partition_point(|(t, _)| t.min_a <= a),
731                    None => lf.first,
732                }
733            }
734        }
735    }
736
737    /// Stored bytes of every tile (from the root on a leafed list).
738    pub fn total_bytes(&self) -> u64 {
739        match self {
740            TileList::Full(v) => v.iter().map(Tile::encoded_len).sum(),
741            TileList::Deferred(d) => d.get().iter().map(Tile::encoded_len).sum(),
742            TileList::Leafed(l) => l.total_bytes,
743        }
744    }
745
746    /// Stored bytes of the tiles whose leading range holds `a`, **without
747    /// faulting**: exact where the leaf is resident, else the mean tile size times the
748    /// tiles the root says hold it — the planner's cost
749    /// estimate must not cost a round trip.
750    pub fn routed_bytes(&self, a: u32) -> u64 {
751        match self {
752            TileList::Full(v) => v
753                .iter()
754                .filter(|t| t.min_a <= a && a <= t.max_a)
755                .map(Tile::encoded_len)
756                .sum(),
757            // No fetch for an estimate: exact once built, else a rough size.
758            TileList::Deferred(d) => match d.cell.get() {
759                Some(v) => v
760                    .iter()
761                    .filter(|t| t.min_a <= a && a <= t.max_a)
762                    .map(Tile::encoded_len)
763                    .sum(),
764                None => d.approx_bytes,
765            },
766            TileList::Leafed(l) => {
767                let lis: Vec<usize> = l
768                    .leaves
769                    .iter()
770                    .enumerate()
771                    .filter(|(_, lf)| lf.min_a <= a && a <= lf.max_a)
772                    .map(|(i, _)| i)
773                    .collect();
774                if lis.is_empty() {
775                    return 0;
776                }
777                if lis.iter().all(|&li| l.cells[li].get().is_some()) {
778                    lis.iter()
779                        .flat_map(|&li| l.cells[li].get().into_iter().flat_map(|v| v.iter()))
780                        .filter(|(t, _)| t.min_a <= a && a <= t.max_a)
781                        .map(|(t, _)| t.encoded_len())
782                        .sum()
783                } else {
784                    // The mean tile size times the tiles the root says hold
785                    // `a`: a predicate filling many tiles is many tiles' bytes.
786                    let mean = l.total_bytes as f64 / l.total.max(1) as f64;
787                    (l.admitted_unfaulted(a).max(1.0) * mean) as u64
788                }
789            }
790        }
791    }
792
793    /// Is the leaf holding tile `ti` resident (always, for a full list)?
794    pub fn resident_at(&self, ti: usize) -> bool {
795        match self {
796            TileList::Full(_) => true,
797            TileList::Deferred(d) => d.cell.get().is_some(),
798            TileList::Leafed(l) => ti < l.total && l.cells[l.leaf_of(ti)].get().is_some(),
799        }
800    }
801
802    /// The absolute stored range of tile `ti` (leafed lists only).
803    pub fn range(&self, ti: usize) -> Option<(u64, u64)> {
804        match self {
805            TileList::Full(_) | TileList::Deferred(_) => None,
806            TileList::Leafed(l) => l.range(ti),
807        }
808    }
809
810    fn load_failed(&self) -> bool {
811        match self {
812            TileList::Leafed(l) => l.load_failed(),
813            TileList::Deferred(d) => d.failed.load(std::sync::atomic::Ordering::Relaxed),
814            TileList::Full(_) => false,
815        }
816    }
817
818    fn reset_load_failure(&self) {
819        match self {
820            TileList::Leafed(l) => l.reset_load_failure(),
821            TileList::Deferred(d) => d.failed.store(false, std::sync::atomic::Ordering::Relaxed),
822            TileList::Full(_) => {}
823        }
824    }
825
826    fn directory_bytes(&self) -> u64 {
827        match self {
828            TileList::Full(v) => (v.capacity() * std::mem::size_of::<Tile>()) as u64,
829            TileList::Deferred(d) => d
830                .cell
831                .get()
832                .map_or(0, |v| (v.capacity() * std::mem::size_of::<Tile>()) as u64),
833            TileList::Leafed(l) => l.resident_bytes(),
834        }
835    }
836}
837
838/// What a routed scan of one pattern will touch, from the tile directories
839/// alone — see [`GraphIndex::scan_plan`].
840#[derive(Debug, Clone, Copy, PartialEq, Eq)]
841pub struct ScanPlan {
842    /// The permutation the scan routes to (always inside [`PermSet::CORE`]).
843    pub permutation: IndexPermutation,
844    /// Tiles in that permutation's section — the denominator.
845    pub tiles_total: usize,
846    /// Tiles left after routing on the bound leading component.
847    pub tiles_routed: usize,
848    /// Tiles left after the synopsis prune — what the scan will actually fetch.
849    pub tiles_admitted: usize,
850    /// Encoded (on-disk) bytes of the admitted tiles: the index-side upper
851    /// bound on the scan's range reads.
852    pub tile_bytes: u64,
853    /// Encoded bytes of the whole section — what an unpruned scan would read.
854    pub section_bytes: u64,
855}
856
857/// Which stored permutation to scan. The full **six** orders (a SPARQL engine's
858/// classic set, as in QLever): together they sort the triples on *every* prefix
859/// of `(s, p, o)` columns, so for any bound-component prefix and any free
860/// component there is a permutation that routes on the prefix **and** yields the
861/// stream sorted on that free component — the precondition for a merge join.
862#[derive(Debug, Clone, Copy, PartialEq, Eq)]
863pub enum IndexPermutation {
864    Spo,
865    Sop,
866    Pso,
867    Pos,
868    Osp,
869    Ops,
870}
871
872/// The number of permutations the format can address (the width of every
873/// per-permutation array). How many a *given file* stores is its [`PermSet`].
874pub(crate) const NUM_PERMS: usize = 6;
875
876/// The six permutations in section order — the canonical iteration list. The
877/// original three (SPO, POS, OSP) lead, so a default scan's tie-break (and its
878/// provenance) is unchanged from the 3-permutation format; the three added orders
879/// (SOP, PSO, OPS) follow and exist to give a merge join a stream sorted on the
880/// join key.
881pub(crate) const ALL_PERMS: [IndexPermutation; NUM_PERMS] = [
882    IndexPermutation::Spo,
883    IndexPermutation::Pos,
884    IndexPermutation::Osp,
885    IndexPermutation::Sop,
886    IndexPermutation::Pso,
887    IndexPermutation::Ops,
888];
889
890/// **Which** permutations a file stores — a 6-bit set over
891/// [`IndexPermutation::section_index`], recorded in the header so a reader
892/// never has to assume six.
893///
894/// Every legal set is a superset of [`PermSet::CORE`] = {SPO, POS, OSP}. That
895/// is not a convention: those three **tie the longest bound prefix on all eight
896/// triple-pattern shapes**, so [`GraphIndex::best_permutation`] never selects
897/// outside them and a lean file routes every pattern exactly where a full one
898/// does — same tiles, same rows. What the other three (SOP, PSO, OPS) add is a
899/// *sort order*: they let [`GraphIndex::permutation_sorted_on`] hand a
900/// sort-merge join a co-sorted stream for three of the twelve
901/// (bound-set, join-column) shapes it otherwise has to hash-join. Absent, the
902/// merge seed declines and the hash path answers — the cost is a fast path,
903/// never correctness (`bgp::try_merge_join` already returns `Option`).
904///
905/// `CORE` is the smallest legal set, [`PermSet::ALL`] is the default and what
906/// every file written before this existed carries.
907#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
908pub struct PermSet(u8);
909
910impl Default for PermSet {
911    fn default() -> Self {
912        PermSet::ALL
913    }
914}
915
916impl PermSet {
917    /// All six permutations — the default, and what a `0` header byte means.
918    pub const ALL: PermSet = PermSet(0b0011_1111);
919    /// The three routing permutations {SPO, POS, OSP}: every pattern shape
920    /// routes as well as it does with six, no merge-join sort orders.
921    pub const CORE: PermSet = PermSet(0b0000_0111);
922
923    /// Parse a raw mask. `Err` when it is not a superset of [`PermSet::CORE`]
924    /// or addresses a permutation this build has no section index for — a
925    /// pattern would then route to a permutation the file does not carry, which
926    /// is the one failure mode that must never be silent.
927    pub fn from_bits(bits: u8) -> Result<PermSet, &'static str> {
928        if bits & !PermSet::ALL.0 != 0 {
929            return Err("permutation mask addresses more than six permutations");
930        }
931        if bits & PermSet::CORE.0 != PermSet::CORE.0 {
932            return Err("permutation mask must contain SPO, POS and OSP");
933        }
934        Ok(PermSet(bits))
935    }
936
937    /// The raw 6-bit mask.
938    pub fn bits(self) -> u8 {
939        self.0
940    }
941
942    /// Is `perm` stored in this file?
943    pub fn contains(self, perm: IndexPermutation) -> bool {
944        self.0 & (1 << perm.section_index()) != 0
945    }
946
947    /// How many permutation sections the file's index container holds.
948    pub fn len(self) -> usize {
949        self.0.count_ones() as usize
950    }
951
952    /// Never true: every legal set contains [`PermSet::CORE`]. Present because
953    /// a public `len` without it is a clippy error, and the honest answer is
954    /// more useful than an `allow`.
955    pub fn is_empty(self) -> bool {
956        false
957    }
958
959    /// The stored permutations in [`ALL_PERMS`] (= container) order.
960    pub fn iter(self) -> impl Iterator<Item = IndexPermutation> {
961        ALL_PERMS.into_iter().filter(move |p| self.contains(*p))
962    }
963
964    /// `perm`'s position **inside the index container**, which is its rank
965    /// among the stored permutations — not [`IndexPermutation::section_index`],
966    /// which is its slot in the format's fixed six-wide addressing. The two
967    /// coincide only for [`PermSet::ALL`].
968    pub fn position(self, perm: IndexPermutation) -> Option<usize> {
969        self.contains(perm)
970            .then(|| (self.0 & ((1u8 << perm.section_index()) - 1)).count_ones() as usize)
971    }
972
973    /// Names in container order, e.g. `["SPO", "POS", "OSP"]`.
974    pub fn names(self) -> Vec<&'static str> {
975        self.iter().map(|p| p.name()).collect()
976    }
977
978    /// Does this set carry the three merge-join orders?
979    pub fn has_merge_orders(self) -> bool {
980        self == PermSet::ALL
981    }
982}
983
984impl IndexPermutation {
985    /// Stable display name used in CLI diagnostics and provenance records.
986    pub fn name(self) -> &'static str {
987        match self {
988            IndexPermutation::Spo => "SPO",
989            IndexPermutation::Sop => "SOP",
990            IndexPermutation::Pso => "PSO",
991            IndexPermutation::Pos => "POS",
992            IndexPermutation::Osp => "OSP",
993            IndexPermutation::Ops => "OPS",
994        }
995    }
996
997    /// Section number inside the stored permutation container.
998    pub fn section_index(self) -> usize {
999        match self {
1000            IndexPermutation::Spo => 0,
1001            IndexPermutation::Pos => 1,
1002            IndexPermutation::Osp => 2,
1003            IndexPermutation::Sop => 3,
1004            IndexPermutation::Pso => 4,
1005            IndexPermutation::Ops => 5,
1006        }
1007    }
1008
1009    /// The canonical `(s, p, o)` roles in this permutation's `(a, b, c)` slots,
1010    /// as indices (0=s, 1=p, 2=o). The single source of truth for `forward` /
1011    /// `back` / `order_pattern`.
1012    pub(crate) const fn roles(self) -> [usize; 3] {
1013        match self {
1014            IndexPermutation::Spo => [0, 1, 2],
1015            IndexPermutation::Sop => [0, 2, 1],
1016            IndexPermutation::Pso => [1, 0, 2],
1017            IndexPermutation::Pos => [1, 2, 0],
1018            IndexPermutation::Osp => [2, 0, 1],
1019            IndexPermutation::Ops => [2, 1, 0],
1020        }
1021    }
1022
1023    /// Map a canonical `(s, p, o)` triple into this permutation's `(a, b, c)`.
1024    pub(crate) fn forward(self, t: Triple) -> Triple {
1025        let c = [t.0, t.1, t.2];
1026        let r = self.roles();
1027        (c[r[0]], c[r[1]], c[r[2]])
1028    }
1029
1030    /// Map a stored `(a, b, c)` back to canonical `(s, p, o)`.
1031    pub(crate) fn back(self, abc: Triple) -> Triple {
1032        let a = [abc.0, abc.1, abc.2];
1033        let r = self.roles();
1034        let mut out = [0u32; 3];
1035        out[r[0]] = a[0];
1036        out[r[1]] = a[1];
1037        out[r[2]] = a[2];
1038        (out[0], out[1], out[2])
1039    }
1040
1041    /// The pattern's bound components in this permutation's component order.
1042    pub(crate) fn order_pattern(self, p: Pattern) -> [Option<u32>; 3] {
1043        let c = [p.0, p.1, p.2];
1044        let r = self.roles();
1045        [c[r[0]], c[r[1]], c[r[2]]]
1046    }
1047
1048    /// Length of the leading run of bound components — higher is more selective.
1049    fn leading_bound(self, pat: Pattern) -> usize {
1050        self.order_pattern(pat)
1051            .iter()
1052            .take_while(|c| c.is_some())
1053            .count()
1054    }
1055}
1056
1057/// Build a [`GraphIndex`] from canonical `(s, p, o)` integer triples.
1058pub struct GraphIndexBuilder {
1059    triples: Vec<Triple>,
1060    tile_budget: usize,
1061    perms: PermSet,
1062    /// Report each finished permutation to [`crate::build_progress`].
1063    progress: bool,
1064}
1065
1066impl Default for GraphIndexBuilder {
1067    fn default() -> Self {
1068        Self {
1069            triples: Vec::new(),
1070            tile_budget: crate::write_opts::tile_budget(),
1071            perms: PermSet::ALL,
1072            progress: false,
1073        }
1074    }
1075}
1076
1077impl GraphIndexBuilder {
1078    pub fn new() -> Self {
1079        Self::default()
1080    }
1081
1082    /// Build directly from an owned triple vector — moves it in, avoiding the
1083    /// per-triple `push` copy when the caller already has the id-triples in a
1084    /// `Vec` (the assembly path, where they double as the pyramid input).
1085    pub fn from_triples(triples: Vec<Triple>) -> Self {
1086        Self {
1087            triples,
1088            ..Self::default()
1089        }
1090    }
1091
1092    /// Override the per-tile byte budget (tests use tiny budgets to force
1093    /// multi-tile sections on small data).
1094    pub fn with_tile_budget(mut self, bytes: usize) -> Self {
1095        self.tile_budget = bytes.max(1);
1096        self
1097    }
1098
1099    /// Build only the permutations in `perms` (default [`PermSet::ALL`]).
1100    /// Sections outside the set come out empty and are not written to the file.
1101    pub fn with_perms(mut self, perms: PermSet) -> Self {
1102        self.perms = perms;
1103        self
1104    }
1105
1106    /// Advance [`crate::build_progress`] by the triple count as each
1107    /// permutation is built (the in-RAM build's `index_permutations` phase).
1108    pub(crate) fn with_progress(mut self) -> Self {
1109        self.progress = true;
1110        self
1111    }
1112
1113    pub fn push(&mut self, t: Triple) {
1114        self.triples.push(t);
1115    }
1116
1117    /// Build the six permutations **one at a time** (each permutation's internal
1118    /// sort still uses every core), so only a single permuted copy of the triples
1119    /// is resident at once instead of all six concurrently. Trades the cross-
1120    /// permutation parallelism of [`Self::build`] for a much lower peak RAM — the
1121    /// large-graph low-memory path. Output is byte-identical to [`Self::build`].
1122    pub fn build_seq(self) -> GraphIndex {
1123        let triples = &self.triples;
1124        let budget = self.tile_budget;
1125        let progress = self.progress;
1126        let wanted: Vec<IndexPermutation> = self.perms.iter().collect();
1127        // Permute (parallel) + sort (parallel inside `build_tiles`) one permutation
1128        // at a time, so only a single permuted copy of the triples is resident — but
1129        // every core is still busy. Process permutations in batches of two to
1130        // overlap one permutation's tile-building with the next one's sort while
1131        // keeping the resident permuted copies to two. Byte-identical to `build`.
1132        let build_one = |perm: IndexPermutation| -> Vec<Tile> {
1133            #[cfg(feature = "parallel")]
1134            let permuted: Vec<Triple> = {
1135                use rayon::prelude::*;
1136                triples.par_iter().map(|&t| perm.forward(t)).collect()
1137            };
1138            #[cfg(not(feature = "parallel"))]
1139            let permuted: Vec<Triple> = triples.iter().map(|&t| perm.forward(t)).collect();
1140            let tiles = build_tiles(permuted, budget);
1141            if progress {
1142                crate::build_progress::advance(triples.len() as u64);
1143            }
1144            tiles
1145        };
1146        #[cfg(feature = "parallel")]
1147        let built: Vec<Vec<Tile>> = {
1148            use rayon::prelude::*;
1149            let mut built: Vec<Vec<Tile>> = Vec::with_capacity(wanted.len());
1150            for chunk in wanted.chunks(2) {
1151                built.extend(
1152                    chunk
1153                        .to_vec()
1154                        .into_par_iter()
1155                        .map(build_one)
1156                        .collect::<Vec<_>>(),
1157                );
1158            }
1159            built
1160        };
1161        #[cfg(not(feature = "parallel"))]
1162        let built: Vec<Vec<Tile>> = wanted.iter().copied().map(build_one).collect();
1163        GraphIndex::from_sections(scatter(&wanted, built), self.perms)
1164    }
1165
1166    pub fn build(self) -> GraphIndex {
1167        let wanted: Vec<IndexPermutation> = self.perms.iter().collect();
1168        let triples = &self.triples;
1169        let budget = self.tile_budget;
1170        let progress = self.progress;
1171        // The permutations are independent — permute + sort + tile each.
1172        let build_one = move |perm: IndexPermutation| -> Vec<Tile> {
1173            let permuted: Vec<Triple> = triples.iter().map(|&t| perm.forward(t)).collect();
1174            let tiles = build_tiles(permuted, budget);
1175            if progress {
1176                crate::build_progress::advance(triples.len() as u64);
1177            }
1178            tiles
1179        };
1180        // Build the permutations concurrently when the `parallel` feature is on
1181        // (they share no state); the per-permutation sort inside is also
1182        // parallel. Output is byte-identical to the serial path.
1183        #[cfg(feature = "parallel")]
1184        let built: Vec<Vec<Tile>> = {
1185            use rayon::iter::{IntoParallelIterator, ParallelIterator};
1186            wanted.clone().into_par_iter().map(build_one).collect()
1187        };
1188        #[cfg(not(feature = "parallel"))]
1189        let built: Vec<Vec<Tile>> = wanted.iter().copied().map(build_one).collect();
1190        GraphIndex::from_sections(scatter(&wanted, built), self.perms)
1191    }
1192}
1193
1194/// Place each built section at its permutation's fixed [`IndexPermutation::section_index`]
1195/// slot, leaving unbuilt permutations empty. The array stays six wide however
1196/// few permutations a file carries, so every `sections[perm.section_index()]`
1197/// in the engine keeps working unchanged.
1198fn scatter(wanted: &[IndexPermutation], built: Vec<Vec<Tile>>) -> [Vec<Tile>; NUM_PERMS] {
1199    let mut sections: [Vec<Tile>; NUM_PERMS] = Default::default();
1200    for (perm, tiles) in wanted.iter().zip(built) {
1201        sections[perm.section_index()] = tiles;
1202    }
1203    sections
1204}
1205
1206/// The encoded varint length of `v` (LEB128).
1207fn varint_len(mut v: u64) -> usize {
1208    let mut n = 1;
1209    while v >= 0x80 {
1210        v >>= 7;
1211        n += 1;
1212    }
1213    n
1214}
1215
1216/// Incremental encoded-size accounting for one a-group of a tiled section —
1217/// the running-delta chain of [`build_tiles`], streamable triple by triple.
1218/// Shared by the in-memory tiler here and the external build's streaming
1219/// tiler ([`crate::extbuild`]) so both choose IDENTICAL tile boundaries and
1220/// their outputs stay byte-identical.
1221pub(crate) struct GroupSizer {
1222    /// finalized contributions: the a-delta plus every closed b-run
1223    size: usize,
1224    num_b: u64,
1225    cur_b: u32,
1226    /// the open b-run's c count / last c
1227    num_c: u64,
1228    prev_c: u32,
1229    empty: bool,
1230}
1231
1232impl GroupSizer {
1233    /// Start a group for leading id `a` whose delta base is `prev_a` (the
1234    /// previous group's leading id; `a` again for a mid-group continuation).
1235    pub(crate) fn start(a: u32, prev_a: u32) -> Self {
1236        GroupSizer {
1237            size: varint_len((a - prev_a) as u64),
1238            num_b: 0,
1239            cur_b: 0,
1240            num_c: 0,
1241            prev_c: 0,
1242            empty: true,
1243        }
1244    }
1245
1246    /// Account one `(b, c)` of this group; returns the group's total encoded
1247    /// size so far (open count varints included).
1248    pub(crate) fn push(&mut self, b: u32, c: u32) -> usize {
1249        if self.empty || b != self.cur_b {
1250            if self.empty {
1251                self.size += varint_len(b as u64); // first b-run: delta from 0
1252            } else {
1253                self.size += varint_len(self.num_c); // close the previous b-run
1254                self.size += varint_len((b - self.cur_b) as u64);
1255            }
1256            self.cur_b = b;
1257            self.num_c = 0;
1258            self.prev_c = 0;
1259            self.num_b += 1;
1260            self.empty = false;
1261        }
1262        self.size += varint_len((c - self.prev_c) as u64);
1263        self.prev_c = c;
1264        self.num_c += 1;
1265        self.total()
1266    }
1267
1268    /// The group's total encoded size so far.
1269    pub(crate) fn total(&self) -> usize {
1270        self.size
1271            + if self.empty {
1272                0
1273            } else {
1274                varint_len(self.num_c)
1275            }
1276            + varint_len(self.num_b)
1277    }
1278}
1279
1280/// Split sorted, deduped permuted triples into size-targeted tiles: append
1281/// whole a-groups until the (estimated, near-exact) encoded size would exceed
1282/// `budget`, then flush — and additionally cut WITHIN an a-group whose own
1283/// running size exceeds the budget (a mega-group: one predicate or class
1284/// carrying a large share of the graph, e.g. a 2B-triple `cites` predicate in
1285/// POS). Split slices become consecutive tiles sharing the leading id — a
1286/// bound leading id routes to the whole run of covering tiles (see
1287/// [`GraphIndex::tile_span`]) — which bounds both builder memory and the
1288/// bytes a remote reader faults for one lookup. Boundary accounting lives in
1289/// [`GroupSizer`], shared with the external build for byte-identity.
1290fn build_tiles(mut triples: Vec<Triple>, budget: usize) -> Vec<Tile> {
1291    #[cfg(feature = "parallel")]
1292    {
1293        use rayon::slice::ParallelSliceMut;
1294        triples.par_sort_unstable();
1295    }
1296    #[cfg(not(feature = "parallel"))]
1297    triples.sort_unstable();
1298    triples.dedup();
1299    if triples.is_empty() {
1300        return Vec::new();
1301    }
1302
1303    let make_tile = |run: &[Triple]| -> Tile {
1304        let mut b = TripleBlockBuilder::new();
1305        for &t in run {
1306            b.push(t);
1307        }
1308        Tile::local(run[0].0, run[run.len() - 1].0, b.build())
1309    };
1310
1311    let mut tiles = Vec::new();
1312    let mut tile_start = 0usize;
1313    let mut tile_size = 0usize; // completed groups in the current tile
1314    let mut prev_a = 0u32;
1315    let mut i = 0usize;
1316    while i < triples.len() {
1317        let a = triples[i].0;
1318        let mut slice_start = i; // group start, or the last mid-group cut
1319        let mut sizer = GroupSizer::start(a, prev_a);
1320        let mut gtotal = 0usize;
1321        while i < triples.len() && triples[i].0 == a {
1322            gtotal = sizer.push(triples[i].1, triples[i].2);
1323            i += 1;
1324            if gtotal > budget {
1325                // Mega-group cut: everything buffered — completed groups plus
1326                // the slice measured so far — becomes one tile; the group
1327                // continues in a fresh chain with `a` as its own delta base.
1328                tiles.push(make_tile(&triples[tile_start..i]));
1329                tile_start = i;
1330                tile_size = 0;
1331                prev_a = a;
1332                slice_start = i;
1333                sizer = GroupSizer::start(a, a);
1334                gtotal = 0;
1335            }
1336        }
1337        if slice_start == i {
1338            continue; // the cut landed exactly on the group's end
1339        }
1340        if slice_start > tile_start && tile_size + gtotal > budget {
1341            tiles.push(make_tile(&triples[tile_start..slice_start]));
1342            tile_start = slice_start;
1343            tile_size = 0;
1344        }
1345        tile_size += gtotal;
1346        prev_a = a;
1347    }
1348    if tile_start < triples.len() {
1349        tiles.push(make_tile(&triples[tile_start..]));
1350    }
1351    tiles
1352}
1353
1354/// The six tiled permutation sections, queryable by triple pattern.
1355pub struct GraphIndex {
1356    /// Tiles per permutation (SPO, SOP, PSO, POS, OSP, OPS — see [`ALL_PERMS`]),
1357    /// ascending in their leading-id ranges; consecutive tiles may share a
1358    /// leading id when a mega-group was split (see [`build_tiles`]).
1359    pub(crate) sections: [TileList; NUM_PERMS],
1360    /// Which of those six slots this file actually carries. Sections outside
1361    /// the set are empty and must never be consulted — an empty section is
1362    /// indistinguishable from an empty *graph*, which is why the planner asks
1363    /// this rather than the section lengths.
1364    perms: PermSet,
1365    /// Faults in remote tiles on first scan (`None` for local indexes).
1366    loader: Option<TileLoader>,
1367    /// Optional batched fetch for multi-tile scans (`None` falls back to
1368    /// one [`TileLoader`] call per tile).
1369    bulk: Option<TileBulkLoader>,
1370    /// The batched fetch for tiles known to lie far apart (a window of probes):
1371    /// exact ranges, not rounded out to cache blocks or merged across wide
1372    /// gaps. `None` falls back to [`bulk`](Self::bulk).
1373    scattered: Option<TileBulkLoader>,
1374    /// Set when the loader failed for some tile: results may be incomplete and
1375    /// the caller must surface an error rather than the partial answer.
1376    load_failed: std::sync::atomic::AtomicBool,
1377    /// The reader's concurrent-range fan-out (1 = strictly sequential) — see
1378    /// [`set_read_concurrency`](Self::set_read_concurrency).
1379    read_concurrency: usize,
1380    /// Decompressed tile bodies live here, keyed by `(section, tile)`, faulted
1381    /// in on first scan and evictable. Phase 0 caps it at unlimited, so a
1382    /// scanned permutation stays resident exactly as it did in the old per-tile
1383    /// `OnceLock`s.
1384    cache: Arc<ChunkCache>,
1385    /// The number of triples this index holds, when known without reading a
1386    /// tile (0 = unknown). A named graph's view takes it from the quad
1387    /// directory, so the planner sizes patterns inside `GRAPH <g>` against the
1388    /// graph rather than the whole file — see [`Self::size_hint`].
1389    size_hint: std::sync::atomic::AtomicU64,
1390}
1391
1392impl GraphIndex {
1393    fn from_sections(mut sections: [Vec<Tile>; NUM_PERMS], perms: PermSet) -> Self {
1394        // Move every locally-built/decoded tile body into the shared cache and
1395        // clear its staging slot, so the descriptors hold routing metadata only.
1396        let cache = ChunkCache::unlimited_arc();
1397        for (si, tiles) in sections.iter_mut().enumerate() {
1398            for (ti, tile) in tiles.iter_mut().enumerate() {
1399                if let Some(body) = tile.staged.take() {
1400                    cache.insert((si as u8, ti as u32), Arc::from(body));
1401                }
1402            }
1403        }
1404        GraphIndex {
1405            sections: sections.map(TileList::Full),
1406            perms,
1407            loader: None,
1408            bulk: None,
1409            scattered: None,
1410            load_failed: std::sync::atomic::AtomicBool::new(false),
1411            read_concurrency: 1,
1412            cache,
1413            size_hint: std::sync::atomic::AtomicU64::new(0),
1414        }
1415    }
1416
1417    /// Rebuild from tiled sections: per permutation, `(min_a, max_a, block
1418    /// bytes)` per tile in ascending leading-id order — the v0.2 layout.
1419    /// Slots outside `perms` must be empty.
1420    pub fn from_tiles(sections: [Vec<(u32, u32, Vec<u8>)>; NUM_PERMS], perms: PermSet) -> Self {
1421        let sections = sections.map(|tiles| {
1422            tiles
1423                .into_iter()
1424                .map(|(min_a, max_a, bytes)| Tile::local(min_a, max_a, bytes))
1425                .collect()
1426        });
1427        Self::from_sections(sections, perms)
1428    }
1429
1430    /// The permutations this index carries.
1431    pub fn perms(&self) -> PermSet {
1432        self.perms
1433    }
1434
1435    /// Set the byte cap of this index's tile cache (bounded-export phase 2).
1436    /// `u64::MAX` (the open-time default) is unlimited — a scanned permutation
1437    /// stays resident exactly as before. A finite cap evicts least-recently-used
1438    /// tiles, so a full scan's tile residency is bounded.
1439    ///
1440    /// Only safe on an index whose tiles can be **re-faulted** (a remote/ranged
1441    /// index with a loader). A locally-built index has no loader — an evicted
1442    /// tile could never be reloaded — so the caller must not cap those; the
1443    /// bounded-export path caps only the ranged default-graph index and leaves
1444    /// resident named-graph indexes unlimited (released per slot instead).
1445    pub fn set_cache_cap(&self, cap: u64) {
1446        self.cache.set_cap(cap);
1447    }
1448
1449    /// The current tile-cache byte cap (`u64::MAX` = unlimited).
1450    pub fn cache_cap(&self) -> u64 {
1451        self.cache.cap()
1452    }
1453
1454    /// Does this index fault its tiles through a loader (a remote/ranged open)?
1455    /// Only such an index is safe to give a finite tile-cache cap: a locally
1456    /// decoded index has no loader, so an evicted tile could never be reloaded.
1457    pub fn is_lazy(&self) -> bool {
1458        self.loader.is_some()
1459    }
1460
1461    /// A snapshot of the tile cache's observability counters.
1462    pub fn cache_stats(&self) -> crate::chunk_cache::CacheStats {
1463        self.cache.stats()
1464    }
1465
1466    /// Heap bytes this index holds for as long as it is open, outside its tile
1467    /// cache: one descriptor per tile of every permutation the file carries
1468    /// (plus a tile's group directory, if a bound-leading lookup built one),
1469    /// and — on a ranged open — the two copies of the per-tile byte ranges the
1470    /// loaders capture. Grows with the tile count, never with what a scan
1471    /// touches.
1472    pub fn directory_bytes(&self) -> u64 {
1473        let tiles: u64 = self.sections.iter().map(|s| s.known_len() as u64).sum();
1474        let caps: u64 = self.sections.iter().map(TileList::directory_bytes).sum();
1475        let ranges = if self.loader.is_some() {
1476            2 * 24 * tiles
1477        } else {
1478            0
1479        };
1480        caps + ranges
1481    }
1482
1483    /// A **remote** index: only the tile directories (leading-id ranges per
1484    /// permutation, ascending) are known; tile payloads fault in through
1485    /// `loader` on first scan. Check [`load_incomplete`](Self::load_incomplete)
1486    /// after evaluating — a failed fetch must become an error, never a
1487    /// silently smaller result.
1488    #[allow(clippy::type_complexity)]
1489    pub fn from_remote_directories(
1490        directories: [Vec<(u32, u32, Option<(u32, u32, u32, u32)>)>; NUM_PERMS],
1491        perms: PermSet,
1492        loader: TileLoader,
1493    ) -> Self {
1494        let sections = directories.map(|dir| {
1495            TileList::Full(
1496                dir.into_iter()
1497                    .map(|(min_a, max_a, syn)| Tile::remote(min_a, max_a, syn))
1498                    .collect(),
1499            )
1500        });
1501        GraphIndex {
1502            sections,
1503            perms,
1504            loader: Some(loader),
1505            bulk: None,
1506            scattered: None,
1507            load_failed: std::sync::atomic::AtomicBool::new(false),
1508            read_concurrency: 1,
1509            cache: ChunkCache::unlimited_arc(),
1510            size_hint: std::sync::atomic::AtomicU64::new(0),
1511        }
1512    }
1513
1514    /// A remote index whose per-order tile lists are built on first use: an
1515    /// order the query never routes to costs nothing. `lists[si]` is `None` for
1516    /// an order the file does not carry. The loaders index the tiles the lists
1517    /// return.
1518    pub fn from_remote_deferred(
1519        lists: [Option<Arc<DeferredTiles>>; NUM_PERMS],
1520        perms: PermSet,
1521        loader: TileLoader,
1522    ) -> Self {
1523        GraphIndex {
1524            sections: lists.map(|l| match l {
1525                Some(l) => TileList::Deferred(l),
1526                None => TileList::Full(Vec::new()),
1527            }),
1528            perms,
1529            loader: Some(loader),
1530            bulk: None,
1531            scattered: None,
1532            load_failed: std::sync::atomic::AtomicBool::new(false),
1533            read_concurrency: 1,
1534            cache: ChunkCache::unlimited_arc(),
1535            size_hint: std::sync::atomic::AtomicU64::new(0),
1536        }
1537    }
1538
1539    /// Attach a batched tile fetcher (see [`TileBulkLoader`]): multi-tile
1540    /// scans prefetch their span through it instead of faulting tile by tile.
1541    pub fn with_bulk_loader(mut self, bulk: TileBulkLoader) -> Self {
1542        self.bulk = Some(bulk);
1543        self
1544    }
1545
1546    /// Attach the fetcher for scattered tiles ([`GraphIndex::probe_batch_fault`]):
1547    /// a probe window's tiles are far apart, so it asks for each one's exact
1548    /// range instead of the block-aligned, gap-merged spans a scan wants.
1549    pub fn with_scattered_loader(mut self, scattered: TileBulkLoader) -> Self {
1550        self.scattered = Some(scattered);
1551        self
1552    }
1553
1554    /// Record each remote tile's encoded (on-disk) byte length, per section —
1555    /// known to the ranged opener from the tile directory. Powers the join
1556    /// planner's fatness gates; never triggers a fetch.
1557    pub(crate) fn set_tile_lens(&mut self, lens: [Vec<u32>; NUM_PERMS]) {
1558        for (section, ls) in self.sections.iter_mut().zip(lens) {
1559            if let TileList::Full(section) = section {
1560                for (tile, l) in section.iter_mut().zip(ls) {
1561                    tile.len = l;
1562                }
1563            }
1564        }
1565    }
1566
1567    /// Record the reader's concurrent-range fan-out (see
1568    /// [`RangeReader::concurrency`](crate::reader::RangeReader::concurrency)) —
1569    /// the join planner widens its remote probe budget when round trips
1570    /// overlap instead of serializing.
1571    pub(crate) fn set_read_concurrency(&mut self, c: usize) {
1572        self.read_concurrency = c.max(1);
1573    }
1574
1575    /// Record how many triples this index holds (see [`Self::size_hint`]).
1576    pub(crate) fn set_size_hint(&self, triples: u64) {
1577        self.size_hint
1578            .store(triples, std::sync::atomic::Ordering::Relaxed);
1579    }
1580
1581    /// The triples this index holds, when it was told without a tile read
1582    /// (a quad-index view's graph count, a resident per-graph index).
1583    pub(crate) fn size_hint(&self) -> Option<u64> {
1584        match self.size_hint.load(std::sync::atomic::Ordering::Relaxed) {
1585            0 => None,
1586            n => Some(n),
1587        }
1588    }
1589
1590    /// The reader's concurrent-range fan-out (1 = strictly sequential).
1591    pub(crate) fn read_concurrency(&self) -> usize {
1592        self.read_concurrency
1593    }
1594
1595    /// Did any tile fetch fail since this index was opened — or since the last
1596    /// [`reset_load_failure`](Self::reset_load_failure)?
1597    pub fn load_incomplete(&self) -> bool {
1598        self.load_failed.load(std::sync::atomic::Ordering::Relaxed)
1599            || self.sections.iter().any(TileList::load_failed)
1600    }
1601
1602    /// Forget recorded fetch failures — the start-of-evaluation reset for a
1603    /// RESIDENT session, making the incompleteness verdict per-query instead of
1604    /// per-open (one transient network blip used to fail every later query on
1605    /// the session). Safe because failed tiles are never cached: the next scan
1606    /// simply retries them.
1607    pub fn reset_load_failure(&self) {
1608        self.load_failed
1609            .store(false, std::sync::atomic::Ordering::Relaxed);
1610        for s in &self.sections {
1611            s.reset_load_failure();
1612        }
1613    }
1614
1615    /// True for a remote/lazy index (tiles fault in over a `RangeReader`). The
1616    /// join planner uses this to pick read-aware strategies: here a per-row index
1617    /// probe is a network round-trip, not a memory lookup, so a left-deep scan +
1618    /// hash join often beats probing a moderately-sized prefix.
1619    pub fn is_remote(&self) -> bool {
1620        self.loader.is_some()
1621    }
1622
1623    /// Batch-fault the unloaded tiles in `[start, end)` of `section` through
1624    /// the bulk loader, if one is attached and at least two tiles are missing
1625    /// (a single missing tile costs the same either way). A failed batch is
1626    /// not an error here: the tiles stay unloaded and the per-tile loader
1627    /// retries each one (recording failures) when the scan reaches it.
1628    /// Fault, in one batch per permutation, the tile-directory leaves the
1629    /// bound leading ids of `patterns` route to (format `0x06`; a no-op on a
1630    /// resident directory).
1631    pub(crate) fn prefault_leaves(&self, patterns: &[Pattern]) {
1632        let mut want: [std::collections::BTreeSet<usize>; NUM_PERMS] = Default::default();
1633        for &pat in patterns {
1634            let perm = Self::best_permutation_in(self.perms, pat);
1635            let [pa, _, _] = perm.order_pattern(pat);
1636            let si = perm.section_index();
1637            if let (TileList::Leafed(l), Some(a)) = (&self.sections[si], pa) {
1638                // Leaves ascend by leading id: the run whose range holds `a`.
1639                let from = l.leaves.partition_point(|lf| lf.max_a < a);
1640                for (li, lf) in l.leaves.iter().enumerate().skip(from) {
1641                    if lf.min_a > a {
1642                        break;
1643                    }
1644                    want[si].insert(li);
1645                }
1646            }
1647        }
1648        for (si, lis) in want.iter().enumerate() {
1649            if let TileList::Leafed(l) = &self.sections[si] {
1650                if !lis.is_empty() {
1651                    l.ensure_leaves(&lis.iter().copied().collect::<Vec<_>>());
1652                }
1653            }
1654        }
1655    }
1656
1657    /// The absolute stored range of tile `(section, tile)` on a leafed
1658    /// (`0x06`) index, faulting its directory leaf.
1659    pub fn tile_range(&self, section: usize, tile: usize) -> Option<(u64, u64)> {
1660        self.sections.get(section)?.range(tile)
1661    }
1662
1663    /// A remote `0x06` index: per stored permutation a two-level tile
1664    /// directory, tiles faulted through `loader`/`bulk`.
1665    pub fn from_leafed(
1666        lists: [Option<Arc<LeafedTiles>>; NUM_PERMS],
1667        perms: PermSet,
1668        loader: TileLoader,
1669    ) -> Self {
1670        GraphIndex {
1671            sections: lists.map(|l| match l {
1672                Some(l) => TileList::Leafed(l),
1673                None => TileList::Full(Vec::new()),
1674            }),
1675            perms,
1676            loader: Some(loader),
1677            bulk: None,
1678            scattered: None,
1679            load_failed: std::sync::atomic::AtomicBool::new(false),
1680            read_concurrency: 1,
1681            cache: ChunkCache::unlimited_arc(),
1682            size_hint: std::sync::atomic::AtomicU64::new(0),
1683        }
1684    }
1685
1686    fn prefetch_span(&self, section: usize, start: usize, end: usize) {
1687        let missing: Vec<usize> = (start..end)
1688            .filter(|&ti| !self.tile_resident(section, ti))
1689            .collect();
1690        self.bulk_fault(section, &missing);
1691    }
1692
1693    /// Is tile `(section, tile)`'s body currently resident in the cache?
1694    fn tile_resident(&self, section: usize, tile: usize) -> bool {
1695        self.cache.contains((section as u8, tile as u32))
1696    }
1697
1698    /// Bulk-fault a set of (possibly scattered, ascending) missing tile indices in
1699    /// `section` through the bulk loader in one coalesced read, storing each image.
1700    /// No-op without a bulk loader or for fewer than two tiles (a single fault
1701    /// costs the same via the per-tile loader). A failed batch leaves the tiles
1702    /// unloaded for the per-tile loader to retry. Shared by the consecutive-span
1703    /// scan prefetch and the scattered batch-probe prefetch.
1704    fn bulk_fault(&self, section: usize, tiles: &[usize]) {
1705        self.fault_with(self.bulk.as_ref(), section, tiles);
1706    }
1707
1708    /// [`bulk_fault`](Self::bulk_fault) through `loader`.
1709    fn fault_with(&self, loader: Option<&TileBulkLoader>, section: usize, tiles: &[usize]) {
1710        if tiles.len() < 2 {
1711            return;
1712        }
1713        let Some(bulk) = loader else { return };
1714        if let Some(images) = bulk(section, tiles) {
1715            if images.len() == tiles.len() {
1716                for (&ti, img) in tiles.iter().zip(images) {
1717                    self.cache
1718                        .insert((section as u8, ti as u32), Arc::from(img));
1719                }
1720            }
1721        }
1722    }
1723
1724    /// Batch-fault the tiles a set of upcoming **probe** patterns will route to,
1725    /// before they are probed one at a time. Each probe (a bound leading id)
1726    /// routes to a single tile; gathered across the batch those tiles are
1727    /// scattered, so faulting them together turns N sequential remote round trips
1728    /// into a few coalesced parallel reads — the read-amplification win for a
1729    /// label-heavy join over a lazy reader. Honors the synopsis prune (never
1730    /// fetches a tile a bound secondary proves can't match). No-op for a local
1731    /// index or when fewer than two tiles per section need faulting.
1732    ///
1733    /// The batch is **bounded** ([`ProbeBatch`]): it covers the leading
1734    /// patterns whose tiles fit, and returns how many that is (at least one for
1735    /// a non-empty list; all of them for a local index). A caller with more
1736    /// patterns asks again for the rest after probing these.
1737    pub(crate) fn prefetch_probe_tiles(&self, patterns: &[Pattern]) -> usize {
1738        if self.bulk.is_none() {
1739            return patterns.len();
1740        }
1741        self.prefault_leaves(patterns);
1742        let mut batch = ProbeBatch::default();
1743        let mut covered = 0;
1744        for &pat in patterns {
1745            if !self.probe_batch_add(&mut batch, pat) {
1746                break;
1747            }
1748            covered += 1;
1749        }
1750        self.probe_batch_fault(batch);
1751        covered
1752    }
1753
1754    /// Add `pat`'s tiles to `batch` if the batch stays within its bounds
1755    /// (tiles, stored bytes); `false` leaves the batch as it was. The first
1756    /// pattern of a batch is always accepted: if it alone is wider than a
1757    /// batch (a bound predicate with nothing else routes to its whole span) it
1758    /// adds no tiles, and its own scan faults what it reads. The directory
1759    /// leaves of `pat` should be resident
1760    /// ([`prefault_leaves`](Self::prefault_leaves)), or this faults them one
1761    /// at a time.
1762    pub(crate) fn probe_batch_add(&self, batch: &mut ProbeBatch, pat: Pattern) -> bool {
1763        let perm = Self::best_permutation(pat);
1764        let [pa, pb, pc] = perm.order_pattern(pat);
1765        let si = perm.section_index();
1766        let (start, end) = self.tile_span(si, pa);
1767        // This pattern's tiles that are not already wanted or resident.
1768        let mut fresh: Vec<usize> = Vec::new();
1769        for ti in start..end {
1770            if self.sections[si][ti].syn_admits(pb, pc)
1771                && !self.tile_resident(si, ti)
1772                && !batch.want[si].contains(&ti)
1773            {
1774                fresh.push(ti);
1775            }
1776        }
1777        let fresh_bytes: u64 = fresh
1778            .iter()
1779            .map(|&ti| self.sections[si][ti].len as u64)
1780            .sum();
1781        if batch.tiles + fresh.len() > PROBE_WINDOW_TILES
1782            || batch.bytes + fresh_bytes > self.probe_window_bytes()
1783        {
1784            if batch.patterns > 0 {
1785                return false;
1786            }
1787            batch.patterns = 1;
1788            return true;
1789        }
1790        batch.tiles += fresh.len();
1791        batch.bytes += fresh_bytes;
1792        batch.want[si].extend(fresh);
1793        batch.patterns += 1;
1794        true
1795    }
1796
1797    /// Fault every tile of `batch`: per section one coalesced, parallel read.
1798    pub(crate) fn probe_batch_fault(&self, batch: ProbeBatch) {
1799        for (si, set) in batch.want.iter().enumerate() {
1800            let tiles: Vec<usize> = set.iter().copied().collect();
1801            self.fault_with(self.scattered.as_ref().or(self.bulk.as_ref()), si, &tiles);
1802        }
1803    }
1804
1805    /// The stored bytes one [`ProbeBatch`] may fault: an eighth of the tile
1806    /// cache's cap, within 256 KiB–64 MiB. A tile decodes to a few times its
1807    /// stored size and the window must stay resident until its probes have
1808    /// run, so a window that outgrew the cache would evict its own early
1809    /// tiles. With the CLI's default budget (a 128 MiB tile cache) that is
1810    /// 16 MiB: tens of coalesced requests, enough to keep the reader's
1811    /// fan-out busy.
1812    fn probe_window_bytes(&self) -> u64 {
1813        const KIB: u64 = 1 << 10;
1814        match self.cache.cap() {
1815            u64::MAX => 64 * KIB * KIB,
1816            cap => (cap / 8).clamp(256 * KIB, 64 * KIB * KIB),
1817        }
1818    }
1819
1820    /// The tile's cache entry, faulting its block image in through the loader if
1821    /// remote. Returns an owned [`CacheEntry`] handle (an `Arc`) the caller
1822    /// holds for the duration of one parse/scan — valid even if a later eviction
1823    /// drops the map slot (the handout invariant).
1824    ///
1825    /// A FAILED fetch records the failure and caches nothing (returns `None`),
1826    /// so a later evaluation retries the tile — a transient network error must
1827    /// not permanently poison a long-lived (resident) session. A local tile
1828    /// with no body returns an empty entry (constructed empty on purpose).
1829    fn tile_entry(&self, section: usize, tile: usize) -> Option<Arc<CacheEntry>> {
1830        // A query run under a memory ceiling ([`crate::guard`]) stops here.
1831        crate::guard::check();
1832        let key = (section as u8, tile as u32);
1833        if let Some(e) = self.cache.get(key) {
1834            return Some(e);
1835        }
1836        match &self.loader {
1837            Some(load) => match load(section, tile) {
1838                Some(bytes) => Some(self.cache.insert(key, Arc::from(bytes))),
1839                None => {
1840                    self.load_failed
1841                        .store(true, std::sync::atomic::Ordering::Relaxed);
1842                    None
1843                }
1844            },
1845            None => Some(self.cache.insert(key, Arc::from(Vec::new()))),
1846        }
1847    }
1848
1849    /// Tile `(section, tile)`'s a-group directory, held in its cache entry and
1850    /// built from `block` (that entry's parsed body) on first use. Its bytes
1851    /// are charged to the tile cache when built, so a capped cache bounds the
1852    /// directories too, and they are evicted with their tile.
1853    fn tile_dir<'e>(
1854        &self,
1855        section: usize,
1856        tile: usize,
1857        entry: &'e Arc<CacheEntry>,
1858        block: &TripleBlock<'_>,
1859    ) -> &'e GroupDirectory {
1860        let (dir, built) = entry.group_dir(|| block.group_directory());
1861        if built {
1862            self.cache.charge_extra(
1863                (section as u8, tile as u32),
1864                entry,
1865                dir.heap_bytes() + std::mem::size_of::<GroupDirectory>() as u64,
1866            );
1867        }
1868        dir
1869    }
1870
1871    /// The tile's decompressed block image as a shared handle, for the file
1872    /// writer (local indexes, all tiles resident). Empty on a miss.
1873    pub(crate) fn tile_body(&self, section: usize, tile: usize) -> Arc<[u8]> {
1874        self.tile_entry(section, tile)
1875            .map(|e| e.body_arc())
1876            .unwrap_or_else(|| Arc::from(Vec::new()))
1877    }
1878
1879    /// Total triple count (sum of the SPO tiles' zone counts). For a remote
1880    /// index this faults in the SPO tiles — prefer the header's quad count.
1881    pub fn triple_count(&self) -> u32 {
1882        self.prefetch_span(0, 0, self.sections[0].len());
1883        (0..self.sections[0].len())
1884            .filter_map(|ti| {
1885                let entry = self.tile_entry(0, ti)?;
1886                TripleBlock::parse(entry.body())
1887                    .ok()
1888                    .map(|b| b.zone().count)
1889            })
1890            // A hostile tile can claim any count: saturate, never overflow.
1891            .fold(0u32, u32::saturating_add)
1892    }
1893
1894    /// Stream **every** triple of one stored permutation in that section's own
1895    /// order, as `(a, b, c)` in the permutation's column order (SPO gives
1896    /// `(s, p, o)`, OSP gives `(o, s, p)`, …).
1897    ///
1898    /// The access a whole-graph pass needs — `rete recard`'s streaming card
1899    /// derivation reads SPO for out-degrees and OSP for in-degrees and literal
1900    /// objects — and one [`scan_iter`](Self::scan_iter) cannot give, because a
1901    /// fully unbound pattern always routes to SPO. Tiles fault with the same
1902    /// geometric prefetch as a scan and are decoded one at a time; nothing is
1903    /// retained beyond the tile cache, so memory follows its cap, not the
1904    /// section. A failed fault is recorded in
1905    /// [`load_incomplete`](Self::load_incomplete) and the tile is skipped, as
1906    /// everywhere else. Returns `false` when the file does not store `perm`.
1907    pub fn for_each_in_order(
1908        &self,
1909        perm: IndexPermutation,
1910        f: &mut dyn FnMut(u32, u32, u32),
1911    ) -> bool {
1912        if !self.perms.contains(perm) {
1913            return false;
1914        }
1915        let si = perm.section_index();
1916        let end = self.sections[si].len();
1917        let mut window = PREFETCH_WINDOW_START;
1918        for ti in 0..end {
1919            if !self.tile_resident(si, ti) {
1920                self.prefetch_span(si, ti, (ti + window).min(end));
1921                window = window.saturating_mul(2).min(PREFETCH_WINDOW_MAX);
1922            }
1923            if let Some(entry) = self.tile_entry(si, ti) {
1924                if let Ok(block) = TripleBlock::parse(entry.body()) {
1925                    for (a, b, c) in block.scan(None, None, None) {
1926                        f(a, b, c);
1927                    }
1928                }
1929            }
1930        }
1931        true
1932    }
1933
1934    /// The tiles of each permutation section (in `ALL_PERMS` order), for the
1935    /// file writer.
1936    pub fn tile_sections(&self) -> [&TileList; NUM_PERMS] {
1937        [
1938            &self.sections[0],
1939            &self.sections[1],
1940            &self.sections[2],
1941            &self.sections[3],
1942            &self.sections[4],
1943            &self.sections[5],
1944        ]
1945    }
1946
1947    /// The permutation selected for a pattern: the one with the longest bound
1948    /// prefix. Ties keep the canonical SPO order (then POS, then OSP), which
1949    /// makes provenance stable for unbound or equally selective shapes and routes
1950    /// a fully unbound pattern to the SPO block rather than fetching all three.
1951    ///
1952    /// Six-permutation shorthand for [`best_permutation_in`]. Its answer is
1953    /// always inside [`PermSet::CORE`] (see `perm_routing_never_leaves_core`),
1954    /// so a file with any legal [`PermSet`] routes identically — but call the
1955    /// `_in` form wherever the file's set is at hand, so that stays true by
1956    /// construction rather than by argument.
1957    ///
1958    /// [`best_permutation_in`]: GraphIndex::best_permutation_in
1959    pub fn best_permutation(pattern: Pattern) -> IndexPermutation {
1960        Self::best_permutation_in(PermSet::ALL, pattern)
1961    }
1962
1963    /// [`best_permutation`](GraphIndex::best_permutation) restricted to the
1964    /// permutations a file carries.
1965    pub fn best_permutation_in(perms: PermSet, pattern: Pattern) -> IndexPermutation {
1966        let mut best = IndexPermutation::Spo;
1967        let mut best_score = best.leading_bound(pattern);
1968        for perm in perms.iter() {
1969            let score = perm.leading_bound(pattern);
1970            if score > best_score {
1971                best = perm;
1972                best_score = score;
1973            }
1974        }
1975        best
1976    }
1977
1978    /// Choose a permutation that **routes** on `pattern`'s bound prefix *and*
1979    /// streams sorted on the canonical column `sort_col` (0=subject, 1=predicate,
1980    /// 2=object) — i.e. `sort_col` is the leading *free* component after the bound
1981    /// prefix. Returns `None` if `sort_col` is itself bound (then every row shares
1982    /// that value — any permutation is "sorted" on it) or no permutation qualifies.
1983    /// This is the precondition a merge join needs: both inputs sorted on the join
1984    /// key. Among qualifiers, the longest bound prefix (best routing) wins.
1985    ///
1986    /// Six-permutation shorthand for [`permutation_sorted_on_in`].
1987    ///
1988    /// [`permutation_sorted_on_in`]: GraphIndex::permutation_sorted_on_in
1989    pub fn permutation_sorted_on(pattern: Pattern, sort_col: usize) -> Option<IndexPermutation> {
1990        Self::permutation_sorted_on_in(PermSet::ALL, pattern, sort_col)
1991    }
1992
1993    /// [`permutation_sorted_on`](GraphIndex::permutation_sorted_on) restricted
1994    /// to the permutations a file carries — **and it will not trade routing for
1995    /// sort order**.
1996    ///
1997    /// A qualifier must match the bound prefix that
1998    /// [`best_permutation_in`](GraphIndex::best_permutation_in) achieves.
1999    /// With all six that costs nothing: every ordering of `(s, p, o)` exists, so
2000    /// "the bound components first, then `sort_col`" is always available at the
2001    /// maximal prefix. With [`PermSet::CORE`] it is what stops a merge join from
2002    /// buying its co-sorted stream with a **whole-section scan** — e.g.
2003    /// `?s :p ?o` sorted on `?s` has no `P*S` order left, and the only remaining
2004    /// sorted-on-subject stream is an unrouted SPO scan of the entire graph. The
2005    /// merge seed then declines and the hash/probe path answers, which is
2006    /// strictly the cheaper plan.
2007    pub fn permutation_sorted_on_in(
2008        perms: PermSet,
2009        pattern: Pattern,
2010        sort_col: usize,
2011    ) -> Option<IndexPermutation> {
2012        let bound = [
2013            pattern.0.is_some(),
2014            pattern.1.is_some(),
2015            pattern.2.is_some(),
2016        ];
2017        if bound[sort_col] {
2018            return None;
2019        }
2020        let routed = Self::best_permutation_in(perms, pattern).leading_bound(pattern);
2021        let mut best: Option<(IndexPermutation, usize)> = None;
2022        for perm in perms.iter() {
2023            let roles = perm.roles();
2024            let lead = perm.leading_bound(pattern);
2025            // The component at slot `lead` is the first free one; it must be the
2026            // sort column (so the stream is sorted on it after the bound prefix).
2027            if lead < 3 && roles[lead] == sort_col && best.map(|(_, s)| lead > s).unwrap_or(true) {
2028                best = Some((perm, lead));
2029            }
2030        }
2031        best.filter(|&(_, lead)| lead >= routed).map(|(p, _)| p)
2032    }
2033
2034    /// Match one already-decoded serialized permutation block (a single v0.1
2035    /// section or one v0.2 tile). This is the core primitive for range-routed
2036    /// readers: the caller fetches only the selected payload, then this scans
2037    /// it as if it came from a full [`GraphIndex`].
2038    pub fn match_serialized_block(
2039        bytes: &[u8],
2040        permutation: IndexPermutation,
2041        pattern: Pattern,
2042    ) -> Vec<Triple> {
2043        let [pa, pb, pc] = permutation.order_pattern(pattern);
2044        let mut out: Vec<Triple> = TripleBlock::parse(bytes)
2045            .ok()
2046            .filter(|b| b.zone().may_contain(pa, pb, pc))
2047            .map(|b| b.scan(pa, pb, pc))
2048            .into_iter()
2049            .flatten()
2050            .map(move |abc| permutation.back(abc))
2051            .collect();
2052        out.sort_unstable();
2053        out
2054    }
2055
2056    /// All triples matching `pattern`, returned in canonical `(s, p, o)` order.
2057    ///
2058    /// Thin eager wrapper over [`scan_iter`](Self::scan_iter): collect the lazy
2059    /// stream and restore the canonical sort (the stream is sorted in the chosen
2060    /// permutation's order, which differs from canonical once `perm.back`
2061    /// permutes the free components).
2062    pub fn match_pattern(&self, pattern: Pattern) -> Vec<Triple> {
2063        let mut out: Vec<Triple> = self.scan_iter(pattern).collect();
2064        out.sort_unstable();
2065        out
2066    }
2067
2068    /// Lazily stream the triples matching `pattern` in canonical `(s, p, o)`
2069    /// order *within the chosen permutation* — the streaming entry point for
2070    /// callers that can stop early (ASK, `LIMIT`, BGP probes) or that don't need
2071    /// the canonical re-sort. Decodes only the matching groups (see
2072    /// [`TripleBlock::scan`]); a malformed/absent block yields nothing rather
2073    /// than panicking. The permutation is chosen for the longest bound prefix.
2074    pub fn scan_iter(&self, pattern: Pattern) -> impl Iterator<Item = Triple> + '_ {
2075        self.scan_iter_with(pattern, Self::best_permutation(pattern))
2076    }
2077
2078    /// What [`scan_iter`](Self::scan_iter) *would* fetch for `pattern`, computed
2079    /// from the tile directories alone — **no tile is fetched, decoded, or even
2080    /// looked at**. This is the cost-preview half of the routed scan: it walks
2081    /// the same three decisions the scan makes (permutation, routed tile span,
2082    /// synopsis prune) and reports what survives, so a caller can say "this dump
2083    /// will pull 16 MB of index, not 376 MB" before starting it.
2084    ///
2085    /// It is a preview, not a promise: `tile_bytes` is an **upper bound** on the
2086    /// index bytes the scan reads (an admitted tile can still be rejected by its
2087    /// in-tile zone map once in hand, and a re-scan of an already-faulted tile
2088    /// reads nothing), and it says nothing about the dictionary, which is where
2089    /// a term-resolving dump's real cost usually lives.
2090    pub fn scan_plan(&self, pattern: Pattern) -> ScanPlan {
2091        let perm = Self::best_permutation_in(self.perms, pattern);
2092        let [_, pb, pc] = perm.order_pattern(pattern);
2093        let si = perm.section_index();
2094        let tiles = &self.sections[si];
2095        let (start, end) = self.tile_span(si, perm.order_pattern(pattern)[0]);
2096        let mut admitted = 0usize;
2097        let mut tile_bytes = 0u64;
2098        for ti in start..end {
2099            let t = &tiles[ti];
2100            if t.syn_admits(pb, pc) {
2101                admitted += 1;
2102                tile_bytes += t.encoded_len();
2103            }
2104        }
2105        ScanPlan {
2106            permutation: perm,
2107            tiles_total: tiles.len(),
2108            tiles_routed: end - start,
2109            tiles_admitted: admitted,
2110            tile_bytes,
2111            section_bytes: tiles.total_bytes(),
2112        }
2113    }
2114
2115    /// One bounded, **resumable** slice of `pattern`'s matches: the pull form of
2116    /// [`scan_iter`](Self::scan_iter), for a caller that cannot hold a borrow
2117    /// across calls.
2118    ///
2119    /// Returns `(triples, next_cursor, done)`; start at `cursor = 0` and feed the
2120    /// returned cursor back until `done`. The whole resume state is one opaque
2121    /// `u64` — `(tile index, next a-group id)` — so no iterator, no thread and no
2122    /// self-referential struct has to survive between calls. That is the shape a
2123    /// foreign-function boundary needs: a wasm module cannot suspend a Rust
2124    /// iterator mid-scan and hand control back to its host, but it can be handed
2125    /// a `u64` and told to carry on.
2126    ///
2127    /// `max_rows` is a **floor**, not a hard cut: a batch always ends on an
2128    /// a-group boundary of the chosen permutation, so no group is ever split
2129    /// across two calls and the overshoot is one group's fanout. Nothing is ever
2130    /// rescanned ([`TripleBlock::scan_resume`] jumps straight to the group
2131    /// through the tile's directory), so a full drain is O(n) overall — unlike
2132    /// `(offset, limit)`, which is O(n²/limit).
2133    ///
2134    /// Every call either yields at least one row or reports `done`, so a caller
2135    /// never has to guard against an empty non-final batch.
2136    ///
2137    /// **Order.** Rows arrive in the chosen permutation's order and each batch is
2138    /// re-sorted canonically, exactly as [`match_pattern`](Self::match_pattern)
2139    /// does for a whole result. For a fully unbound pattern (routed to SPO) that
2140    /// makes the concatenation of every batch identical to `match_pattern`'s
2141    /// output; for a bound pattern the *set* is identical but the canonical
2142    /// re-sort is per batch rather than global.
2143    ///
2144    /// **Memory** is O(`max_rows` + one a-group + the tiles faulted so far) —
2145    /// never O(matches). That is the whole point: an unbounded `(?s ?p ?o)` over
2146    /// a 26-million-quad graph used to materialize every match before the caller
2147    /// saw one row.
2148    pub fn scan_batch(
2149        &self,
2150        pattern: Pattern,
2151        cursor: u64,
2152        max_rows: usize,
2153    ) -> (Vec<Triple>, u64, bool) {
2154        let max_rows = max_rows.max(1);
2155        let perm = Self::best_permutation(pattern);
2156        let [pa, pb, pc] = perm.order_pattern(pattern);
2157        let si = perm.section_index();
2158        // Same routing as `scan_iter_with`: the tile directory alone decides the
2159        // span, so this is free on a lazy/remote open.
2160        let (start, end) = self.tile_span(si, pa);
2161        let mut ti = ((cursor >> 32) as usize).max(start);
2162        let mut from_a = cursor as u32;
2163        let mut out: Vec<Triple> = Vec::new();
2164        // Same geometric prefetch ramp as the streaming scan: a batch that stops
2165        // after one tile never fetches the ones behind it.
2166        let mut window = PREFETCH_WINDOW_START;
2167        while ti < end {
2168            // Synopsis pre-fault prune — no tile is fetched to reject it.
2169            if !self.sections[si][ti].syn_admits(pb, pc) {
2170                ti += 1;
2171                from_a = 0;
2172                continue;
2173            }
2174            if !self.tile_resident(si, ti) {
2175                self.prefetch_span(si, ti, (ti + window).min(end));
2176                window = window.saturating_mul(2).min(PREFETCH_WINDOW_MAX);
2177            }
2178            let entry = self.tile_entry(si, ti);
2179            let mut resume_at: Option<u32> = None;
2180            if let Some(block) = entry
2181                .as_deref()
2182                .and_then(|e| TripleBlock::parse(e.body()).ok())
2183                .filter(|b| b.zone().may_contain(pa, pb, pc))
2184            {
2185                let rows = match pa {
2186                    // A bound leading id is one a-group; it cannot be split
2187                    // inside a tile, only across tiles (a mega-group split), so
2188                    // there is nothing finer to resume at than the tile.
2189                    Some(a) => {
2190                        let dir = self.tile_dir(si, ti, entry.as_ref().unwrap(), &block);
2191                        block.scan_from(dir, a, pb, pc)
2192                    }
2193                    // Fresh tile: no directory needed, so a straight drain never
2194                    // pays for one.
2195                    None if from_a == 0 => block.scan(None, pb, pc),
2196                    None => {
2197                        let dir = self.tile_dir(si, ti, entry.as_ref().unwrap(), &block);
2198                        block.scan_resume(dir, from_a, pb, pc)
2199                    }
2200                };
2201                // Only a leading-unbound scan can be resumed mid-tile: with `pa`
2202                // bound there is one a-group and `scan_from` always restarts it
2203                // from the top, so cutting inside it would duplicate rows.
2204                let splittable = pa.is_none();
2205                let mut last_a: Option<u32> = None;
2206                for abc in rows {
2207                    // Full, and this row opens a new a-group ⇒ cut here and
2208                    // resume at this group. The row is dropped, not lost: the
2209                    // next call re-enters at exactly this id.
2210                    if splittable && out.len() >= max_rows && last_a != Some(abc.0) {
2211                        resume_at = Some(abc.0);
2212                        break;
2213                    }
2214                    last_a = Some(abc.0);
2215                    out.push(perm.back(abc));
2216                }
2217            }
2218            if let Some(a) = resume_at {
2219                out.sort_unstable();
2220                return (out, ((ti as u64) << 32) | a as u64, false);
2221            }
2222            ti += 1;
2223            from_a = 0;
2224            if out.len() >= max_rows {
2225                break;
2226            }
2227        }
2228        let done = ti >= end;
2229        out.sort_unstable();
2230        (out, (ti as u64) << 32, done)
2231    }
2232
2233    /// Stream `pattern`'s matches **sorted on the canonical column `sort_col`**
2234    /// (0=subject, 1=predicate, 2=object): the stream's `sort_col` values are
2235    /// ascending. Chooses a permutation that routes on the bound prefix *and*
2236    /// orders by `sort_col` ([`permutation_sorted_on`](Self::permutation_sorted_on));
2237    /// `None` when none qualifies (e.g. `sort_col` is itself bound). The
2238    /// precondition for feeding a [merge join](crate::bgp): both inputs sorted on
2239    /// the shared join key.
2240    pub(crate) fn scan_iter_sorted_on(
2241        &self,
2242        pattern: Pattern,
2243        sort_col: usize,
2244    ) -> Option<impl Iterator<Item = Triple> + '_> {
2245        Some(self.scan_iter_with(
2246            pattern,
2247            Self::permutation_sorted_on_in(self.perms, pattern, sort_col)?,
2248        ))
2249    }
2250
2251    /// Stream `pattern`'s matches using a **specific** permutation `perm`; the
2252    /// stream is sorted in `perm`'s `(a, b, c)` order. Shared core of `scan_iter`
2253    /// and `scan_iter_sorted_on`.
2254    fn scan_iter_with(
2255        &self,
2256        pattern: Pattern,
2257        perm: IndexPermutation,
2258    ) -> impl Iterator<Item = Triple> + '_ {
2259        // Route: a bound leading id binary-searches the tile directory to exactly
2260        // one tile (groups are never split across tiles); an unbound one chains
2261        // every tile's cursor. Within a tile, a bound leading scan jumps to its
2262        // a-group via the tile's lazily-built group directory — built on first
2263        // use, costing one walk of that (budget-sized) tile.
2264        let [pa, pb, pc] = perm.order_pattern(pattern);
2265        let si = perm.section_index();
2266        let (start, end) = self.tile_span(si, pa);
2267        // Coalesce tile faults, but ramp the prefetch window geometrically as
2268        // the scan advances rather than fetching the whole span up front: a
2269        // small `LIMIT` (which stops pulling early) then never faults tiles
2270        // past the rows it needs, while a full scan still batches into a
2271        // handful of coalesced reads (4, 8, 16, … tiles). A bound leading scan
2272        // spans a single tile, so the prefetch no-ops and it faults just that
2273        // one tile, unchanged.
2274        let window = std::cell::Cell::new(PREFETCH_WINDOW_START);
2275        (start..end)
2276            // Synopsis pre-fault prune: drop a routed tile the directory proves
2277            // can't match a bound secondary component, **without fetching it**
2278            // (the remote win — a negative/sparse lookup costs zero tile reads).
2279            // A bound leading id routes to a single tile, so this is where it
2280            // bites; a fully-unbound leading scan leaves `pb`/`pc` unbound, so
2281            // `syn_admits` keeps every tile, unchanged.
2282            .filter(move |&ti| self.sections[si][ti].syn_admits(pb, pc))
2283            .flat_map(move |ti| {
2284                // Fault in (if remote), parse (untrusted bytes ⇒ `None` on
2285                // malformed), and zone-prune per tile, then stream the
2286                // matching groups.
2287                if !self.tile_resident(si, ti) {
2288                    let w = window.get();
2289                    self.prefetch_span(si, ti, (ti + w).min(end));
2290                    window.set(w.saturating_mul(2).min(PREFETCH_WINDOW_MAX));
2291                }
2292                // A failed fetch is recorded by the index and scans as empty.
2293                let rows: Vec<Triple> = self.tile_rows(si, ti, pa, pb, pc).unwrap_or_default();
2294                rows.into_iter()
2295            })
2296            .map(move |abc| perm.back(abc))
2297    }
2298
2299    /// The rows of tile `ti` of section `si` matching `(pa, pb, pc)` (in that
2300    /// section's `a, b, c` order). The tile is decoded once and its matching
2301    /// rows materialized into an owned `Vec`, so the borrowed block/cursor never
2302    /// outlives the tile's cache handle (an `Arc` dropped on return); the buffer
2303    /// is bounded to one tile's rows. `None` = the tile could not be fetched
2304    /// (the failure is recorded, see [`Self::load_incomplete`]); a malformed or
2305    /// zone-pruned tile yields no rows.
2306    fn tile_rows(
2307        &self,
2308        si: usize,
2309        ti: usize,
2310        pa: Option<u32>,
2311        pb: Option<u32>,
2312        pc: Option<u32>,
2313    ) -> Option<Vec<Triple>> {
2314        let entry = self.tile_entry(si, ti)?;
2315        Some(
2316            TripleBlock::parse(entry.body())
2317                .ok()
2318                .filter(|b| b.zone().may_contain(pa, pb, pc))
2319                .map(|b| match pa {
2320                    Some(a) => {
2321                        let dir = self.tile_dir(si, ti, &entry, &b);
2322                        b.scan_from(dir, a, pb, pc).collect()
2323                    }
2324                    None => b.scan(pa, pb, pc).collect(),
2325                })
2326                .unwrap_or_default(),
2327        )
2328    }
2329
2330    /// Is the object of every triple with predicate `p` inside an object-id
2331    /// range `covers` accepts? Read off the predicate-leading tiles (POS, or PSO):
2332    /// a tile whose synopsis object range `covers` accepts is proven without
2333    /// being read — the synopsis bounds every row of the tile, whatever its
2334    /// predicate, so a tile shared with other predicates only makes the test
2335    /// stricter. The tiles left (no synopsis, or a range it does not accept) are
2336    /// read and their rows of `p` checked one by one: on a lazy index only when
2337    /// there are at most `max_read` of them, in one batch, else the answer is
2338    /// `false`; on a resident one always, in memory. `false` also when a tile
2339    /// cannot be read. An index without `p` proves it trivially.
2340    pub(crate) fn predicate_objects_within(
2341        &self,
2342        p: u32,
2343        covers: impl Fn(u32, u32) -> bool,
2344        max_read: usize,
2345    ) -> bool {
2346        // (perm, which synopsis/row column holds the object)
2347        let (perm, object_is_b) = if self.perms.contains(IndexPermutation::Pos) {
2348            (IndexPermutation::Pos, true)
2349        } else if self.perms.contains(IndexPermutation::Pso) {
2350            (IndexPermutation::Pso, false)
2351        } else {
2352            return false;
2353        };
2354        let si = perm.section_index();
2355        let (start, end) = self.tile_span(si, Some(p));
2356        let unproven: Vec<usize> = (start..end)
2357            .filter(|&ti| match self.sections[si][ti].syn {
2358                Some((min_b, max_b, min_c, max_c)) => {
2359                    let (lo, hi) = if object_is_b {
2360                        (min_b, max_b)
2361                    } else {
2362                        (min_c, max_c)
2363                    };
2364                    !covers(lo, hi)
2365                }
2366                None => true,
2367            })
2368            .collect();
2369        if unproven.is_empty() {
2370            return true;
2371        }
2372        if self.is_lazy() {
2373            if unproven.len() > max_read {
2374                return false;
2375            }
2376            let missing: Vec<usize> = unproven
2377                .iter()
2378                .copied()
2379                .filter(|&ti| !self.tile_resident(si, ti))
2380                .collect();
2381            self.bulk_fault(si, &missing);
2382        }
2383        for ti in unproven {
2384            let Some(rows) = self.tile_rows(si, ti, Some(p), None, None) else {
2385                return false;
2386            };
2387            let all = rows.iter().all(|&(_, b, c)| {
2388                let o = if object_is_b { b } else { c };
2389                covers(o, o)
2390            });
2391            if !all {
2392                return false;
2393            }
2394        }
2395        true
2396    }
2397
2398    /// Fault, in one batched read across every permutation, the directory leaves
2399    /// [`estimate_matches`](Self::estimate_matches) reads for `patterns`: for each
2400    /// permutation that leads with a bound id, the leaves its run of tiles starts
2401    /// and ends in (a leaf wholly inside the run is counted from the root). The
2402    /// estimate then reads them from memory instead of one permutation at a time.
2403    /// A no-op on a resident directory.
2404    pub(crate) fn prefault_estimate_leaves(&self, patterns: &[Pattern]) {
2405        let mut want: [std::collections::BTreeSet<usize>; NUM_PERMS] = Default::default();
2406        for &pattern in patterns {
2407            for perm in self.perms.iter() {
2408                let [Some(a), _, _] = perm.order_pattern(pattern) else {
2409                    continue;
2410                };
2411                let si = perm.section_index();
2412                if let TileList::Leafed(l) = &self.sections[si] {
2413                    want[si].extend(l.run_end_leaves(a));
2414                }
2415            }
2416        }
2417        let wanted: Vec<(usize, Vec<usize>)> = want
2418            .into_iter()
2419            .enumerate()
2420            .filter(|(_, lis)| !lis.is_empty())
2421            .map(|(si, lis)| (si, lis.into_iter().collect()))
2422            .collect();
2423        let across: Vec<(&dyn LeafDir, &[usize])> = wanted
2424            .iter()
2425            .filter_map(|(si, lis)| match &self.sections[*si] {
2426                TileList::Leafed(l) => Some((&**l as &dyn LeafDir, lis.as_slice())),
2427                _ => None,
2428            })
2429            .collect();
2430        ensure_leaves_across(&across);
2431    }
2432
2433    /// A planner estimate of how many triples match `pattern`, read off the
2434    /// tile directories alone — no tile is fetched or decoded, so it costs the
2435    /// same on a lazy 50 GB file as on a resident one. `total` is the number
2436    /// of triples the index holds (an upper bound is fine).
2437    ///
2438    /// For every carried permutation that leads with a bound component, the
2439    /// routed tiles the synopsis admits are counted; a tile holds about
2440    /// `total / tiles` triples, and the routed run is charged half a tile less
2441    /// than its length, since a key rarely starts and ends on tile boundaries.
2442    /// The smallest figure wins, so `?s a :Rare` (a few tiles of OPS) beats
2443    /// `?s :p ?o` (every tile of `:p` in PSO). Its resolution is one tile:
2444    /// patterns inside one tile tie, which is all a join order needs. A
2445    /// pattern with no bound component estimates `total`; one the synopsis
2446    /// rules out estimates 0.
2447    pub(crate) fn estimate_matches(&self, pattern: Pattern, total: u64) -> f64 {
2448        let mut best = total as f64;
2449        for perm in self.perms.iter() {
2450            let [pa, pb, pc] = perm.order_pattern(pattern);
2451            if pa.is_none() {
2452                continue;
2453            }
2454            let si = perm.section_index();
2455            let tiles = &self.sections[si];
2456            if tiles.is_empty() {
2457                return 0.0;
2458            }
2459            let per_tile = total as f64 / tiles.len() as f64;
2460            // A leafed list whose leaf is not resident must still be estimated
2461            // from the root alone (a cost estimate must not cost a read), and
2462            // must give the figure the same directory gives when laid out flat
2463            // (format 0x05) to within the unavoidable: a predicate that fills
2464            // thousands of tiles is thousands of tiles whichever layout stores
2465            // them. Counting "one tile" here made the planner see a 2 M-row
2466            // predicate as 7 k rows and hash-join it (see [`LeafedTiles::admitted_estimate`]).
2467            let admitted = match (tiles, pa) {
2468                (TileList::Leafed(l), Some(a))
2469                    if !l
2470                        .leaves
2471                        .iter()
2472                        .enumerate()
2473                        .filter(|(_, lf)| lf.min_a <= a && a <= lf.max_a)
2474                        .all(|(li, _)| l.cells[li].get().is_some()) =>
2475                {
2476                    l.admitted_estimate(a, pb, pc)
2477                }
2478                _ => {
2479                    let (start, end) = self.tile_span(si, pa);
2480                    (start..end)
2481                        .filter(|&ti| tiles[ti].syn_admits(pb, pc))
2482                        .count() as f64
2483                }
2484            };
2485            let est = if admitted <= 0.0 {
2486                0.0
2487            } else {
2488                (admitted - 0.5).max(0.5) * per_tile
2489            };
2490            best = best.min(est);
2491        }
2492        best
2493    }
2494
2495    /// The smallest leading id `>= a` present in permutation section `section`,
2496    /// or `None` past the last one. Routes by the tile directory, then reads the
2497    /// tile's own group directory — so it skips the ids a tile's *range* covers
2498    /// but its body does not hold. That matters where a range is conservative:
2499    /// a quad-index view's tile shared with other graphs is `0..=u32::MAX`, and
2500    /// stepping through it id by id would never finish. Faults the tiles it
2501    /// reads; a failed fault ends the search (`load_incomplete` says so).
2502    pub(crate) fn next_leading(&self, section: usize, a: u32) -> Option<u32> {
2503        let tiles = &self.sections[section];
2504        let mut ti = tiles.first_max_ge(a);
2505        while ti < tiles.len() {
2506            let from = a.max(tiles[ti].min_a);
2507            let entry = self.tile_entry(section, ti)?;
2508            if let Ok(block) = TripleBlock::parse(entry.body()) {
2509                let dir = self.tile_dir(section, ti, &entry, &block);
2510                if let Some(x) = dir.first_at_or_after(from) {
2511                    return Some(x);
2512                }
2513            }
2514            ti += 1;
2515        }
2516        None
2517    }
2518
2519    /// The tile index span a scan must visit: every tile when the leading
2520    /// component is unbound, else the run of tiles whose leading-id ranges
2521    /// cover it. Tile ranges are ascending; consecutive tiles may SHARE a
2522    /// leading id when a mega-group was split across tiles (see
2523    /// [`build_tiles`]), so the span is a range scan, not a single hit —
2524    /// files without splits still yield a span of at most one tile.
2525    pub(crate) fn tile_span(&self, section: usize, pa: Option<u32>) -> (usize, usize) {
2526        let tiles = &self.sections[section];
2527        match pa {
2528            None => {
2529                // An unbound scan visits every tile: fault every leaf at once.
2530                tiles.ensure_span(0, tiles.len());
2531                (0, tiles.len())
2532            }
2533            Some(a) => {
2534                let i = tiles.first_max_ge(a);
2535                let j = tiles.first_min_gt(a).max(i);
2536                // The callers walk the run: fault its leaves in one batch, as
2537                // the tile-by-tile walk this replaced did one by one.
2538                tiles.ensure_span(i, j);
2539                (i, j)
2540            }
2541        }
2542    }
2543}
2544
2545#[cfg(test)]
2546mod tests {
2547    use super::*;
2548
2549    fn graph() -> (GraphIndex, Vec<Triple>) {
2550        let data = vec![
2551            (1, 10, 100),
2552            (1, 10, 101),
2553            (1, 11, 100),
2554            (2, 10, 100),
2555            (2, 12, 200),
2556            (3, 11, 300),
2557        ];
2558        let mut b = GraphIndexBuilder::new();
2559        for &t in &data {
2560            b.push(t);
2561        }
2562        (b.build(), data)
2563    }
2564
2565    /// Brute-force reference for a pattern.
2566    fn reference(data: &[Triple], (s, p, o): Pattern) -> Vec<Triple> {
2567        let mut v: Vec<Triple> = data
2568            .iter()
2569            .copied()
2570            .filter(|&(a, b, c)| {
2571                s.is_none_or(|x| x == a) && p.is_none_or(|x| x == b) && o.is_none_or(|x| x == c)
2572            })
2573            .collect();
2574        v.sort_unstable();
2575        v
2576    }
2577
2578    /// The tile-directory estimate orders patterns the way their true sizes
2579    /// do, never fetches anything, and is exact at its extremes: unbound is the
2580    /// total, a key no tile can hold is zero.
2581    #[test]
2582    fn tile_estimates_rank_patterns_by_size() {
2583        // Predicate 1 on every subject, predicate 2 on a few; object 50 is a
2584        // "class" with 4000 instances, object 60 one with 3.
2585        let mut b = GraphIndexBuilder::new().with_tile_budget(256);
2586        let mut n = 0u64;
2587        for s in 0..4000u32 {
2588            b.push((s, 1, 50));
2589            b.push((s, 3, 1000 + s));
2590            n += 2;
2591            if s % 1000 == 0 {
2592                b.push((s, 2, 60));
2593                n += 1;
2594            }
2595        }
2596        let idx = b.build();
2597        let est = |p: Pattern| idx.estimate_matches(p, n);
2598        assert_eq!(est((None, None, None)), n as f64);
2599        assert!(est((None, Some(2), None)) < est((None, Some(1), None)));
2600        assert!(est((None, None, Some(60))) < est((None, None, Some(50))));
2601        assert!(est((Some(7), None, None)) < est((None, Some(3), None)));
2602        // A big predicate spans many tiles; the rare one fits in at most one.
2603        let per_tile = n as f64 / idx.tile_sections()[0].len() as f64;
2604        assert!(est((None, Some(2), None)) <= 1.5 * per_tile);
2605        assert!(est((None, Some(1), None)) > 10.0 * per_tile);
2606        // A leading id beyond every tile's range is provably absent.
2607        assert_eq!(est((Some(99_999), None, None)), 0.0);
2608        // An empty index estimates nothing for a bound pattern.
2609        let empty = GraphIndexBuilder::new().build();
2610        assert_eq!(empty.estimate_matches((Some(1), None, None), 0), 0.0);
2611    }
2612
2613    #[test]
2614    fn every_pattern_shape_matches_reference() {
2615        let (idx, data) = graph();
2616        let vals = |opts: &[u32]| {
2617            let mut v: Vec<Option<u32>> = opts.iter().map(|&x| Some(x)).collect();
2618            v.push(None);
2619            v
2620        };
2621        // Exercise all 8 bound/unbound shapes across representative values.
2622        for s in vals(&[1, 2, 9]) {
2623            for p in vals(&[10, 11, 99]) {
2624                for o in vals(&[100, 300, 999]) {
2625                    let pat = (s, p, o);
2626                    assert_eq!(
2627                        idx.match_pattern(pat),
2628                        reference(&data, pat),
2629                        "pattern {pat:?}"
2630                    );
2631                    // The lazy stream must match the eager result once sorted —
2632                    // same triples, just without the up-front canonical re-sort.
2633                    let mut streamed: Vec<Triple> = idx.scan_iter(pat).collect();
2634                    streamed.sort_unstable();
2635                    assert_eq!(streamed, reference(&data, pat), "scan_iter {pat:?}");
2636                }
2637            }
2638        }
2639    }
2640
2641    #[test]
2642    fn unbound_returns_everything_sorted() {
2643        let (idx, data) = graph();
2644        let mut sorted = data.clone();
2645        sorted.sort_unstable();
2646        assert_eq!(idx.match_pattern((None, None, None)), sorted);
2647    }
2648
2649    /// A tiny tile budget must split sections into many tiles — including
2650    /// MID-GROUP cuts (budget 1/16 makes every a-group oversized) — and every
2651    /// pattern shape must still match the brute-force reference: bound
2652    /// leading ids route to the run of covering tiles, unbound scans chain
2653    /// all tiles.
2654    #[test]
2655    fn multi_tile_sections_match_reference_every_shape() {
2656        // Enough distinct leading ids to split under a tiny budget.
2657        let mut data: Vec<Triple> = Vec::new();
2658        for s in 1..=40u32 {
2659            for p in [10u32, 11] {
2660                for o in [100u32, 100 + s] {
2661                    data.push((s, p, o));
2662                }
2663            }
2664        }
2665        for budget in [1usize, 16, 64, 1 << 20] {
2666            let mut b = GraphIndexBuilder::new().with_tile_budget(budget);
2667            for &t in &data {
2668                b.push(t);
2669            }
2670            let idx = b.build();
2671            let spo_tiles = idx.tile_sections()[0].len();
2672            if budget <= 16 {
2673                assert!(spo_tiles > 1, "budget {budget} should force tiling");
2674            }
2675            // Tile ranges must be ascending; a split mega-group may leave
2676            // consecutive tiles SHARING a leading id (never overlapping past it).
2677            for w in idx.tile_sections()[0].as_full().unwrap().windows(2) {
2678                assert!(w[0].leading_range().1 <= w[1].leading_range().0);
2679            }
2680            assert_eq!(idx.triple_count() as usize, data.len(), "budget {budget}");
2681
2682            let vals = |opts: &[u32]| {
2683                let mut v: Vec<Option<u32>> = opts.iter().map(|&x| Some(x)).collect();
2684                v.push(None);
2685                v
2686            };
2687            for _round in 0..2 {
2688                for s in vals(&[1, 20, 40, 99]) {
2689                    for p in vals(&[10, 11, 99]) {
2690                        for o in vals(&[100, 120, 999]) {
2691                            let pat = (s, p, o);
2692                            assert_eq!(
2693                                idx.match_pattern(pat),
2694                                reference(&data, pat),
2695                                "budget {budget} pattern {pat:?}"
2696                            );
2697                        }
2698                    }
2699                }
2700            }
2701        }
2702    }
2703
2704    /// The Crossref shape: ONE mega-predicate carrying most of the graph. At
2705    /// the real 64 KiB budget its P-leading a-group must be split across
2706    /// multiple tiles (bounding builder memory), and a bound leading id must
2707    /// route to the whole run of covering tiles with complete results.
2708    #[test]
2709    fn mega_group_splits_across_tiles_and_lookups_stay_complete() {
2710        let hot_p = 7u32;
2711        let mut data: Vec<Triple> = Vec::new();
2712        for i in 0..40_000u32 {
2713            data.push((1_000 + i % 200, hot_p, 50_000 + i));
2714        }
2715        data.push((1, 1, 1));
2716        data.push((2, 2, 2));
2717        let mut b = GraphIndexBuilder::new(); // default INDEX_TILE_BUDGET
2718        for &t in &data {
2719            b.push(t);
2720        }
2721        let idx = b.build();
2722
2723        // PSO (a = predicate): the hot_p group must span several tiles.
2724        let pso = ALL_PERMS
2725            .iter()
2726            .position(|p| matches!(p, IndexPermutation::Pso))
2727            .unwrap();
2728        let covering = idx.tile_sections()[pso]
2729            .iter()
2730            .filter(|t| {
2731                let (lo, hi) = t.leading_range();
2732                lo <= hot_p && hot_p <= hi
2733            })
2734            .count();
2735        assert!(
2736            covering > 1,
2737            "expected the hot predicate split across tiles, got {covering}"
2738        );
2739
2740        // Bound-p lookup must still return every triple of the mega-group —
2741        // probing bound objects in the FIRST, MIDDLE and LAST slices of the
2742        // split run (a mid-run object once returned 0 on the first split file).
2743        for pat in [
2744            (None, Some(hot_p), None),
2745            (Some(1_050), Some(hot_p), None),
2746            (None, Some(hot_p), Some(50_123)), // first slice
2747            (None, Some(hot_p), Some(70_000)), // middle of the run
2748            (None, Some(hot_p), Some(89_999)), // last slice
2749            (None, Some(hot_p), Some(49_000)), // below the range → empty
2750            (None, Some(hot_p), Some(95_000)), // above the range → empty
2751        ] {
2752            assert_eq!(idx.match_pattern(pat), reference(&data, pat), "{pat:?}");
2753        }
2754    }
2755
2756    /// Scans must yield identical results across the directory lifecycle: the
2757    /// first leading-bound scan walks linearly, the second builds the
2758    /// directory, and later ones jump through it — including absent ids
2759    /// (between, below, and above the stored groups).
2760    #[test]
2761    fn directory_backed_scans_match_reference_every_shape() {
2762        let (idx, data) = graph();
2763        let vals = |opts: &[u32]| {
2764            let mut v: Vec<Option<u32>> = opts.iter().map(|&x| Some(x)).collect();
2765            v.push(None);
2766            v
2767        };
2768        for round in 0..3 {
2769            for s in vals(&[1, 2, 3, 0, 9]) {
2770                for p in vals(&[10, 11, 12, 99]) {
2771                    for o in vals(&[100, 200, 300, 999]) {
2772                        let pat = (s, p, o);
2773                        let mut got: Vec<Triple> = idx.scan_iter(pat).collect();
2774                        got.sort_unstable();
2775                        assert_eq!(got, reference(&data, pat), "round {round} scan {pat:?}");
2776                    }
2777                }
2778            }
2779        }
2780    }
2781
2782    /// A tile synopsis must let a routed scan **skip the fetch** of a tile its
2783    /// secondary-column range rules out — and never skip one that could match.
2784    #[test]
2785    fn synopsis_prunes_the_routed_tile_before_fetch() {
2786        use std::sync::atomic::{AtomicUsize, Ordering::SeqCst};
2787        use std::sync::Arc;
2788
2789        // One real SPO tile: subject a=5, predicates b∈{10,11}, object c=100.
2790        let block = {
2791            let mut b = TripleBlockBuilder::new();
2792            b.push((5, 10, 100));
2793            b.push((5, 11, 100));
2794            b.build()
2795        };
2796        let fetches = Arc::new(AtomicUsize::new(0));
2797        let (blk, fc) = (block.clone(), fetches.clone());
2798        // The loader returns the (already-decompressed) tile image and counts calls.
2799        let loader: TileLoader = Box::new(move |_si, _ti| {
2800            fc.fetch_add(1, SeqCst);
2801            Some(blk.clone())
2802        });
2803        // Remote SPO directory: one tile, leading a∈[5,5], synopsis b∈[10,11], c∈[100,100].
2804        let dirs = [
2805            vec![(5u32, 5u32, Some((10u32, 11u32, 100u32, 100u32)))],
2806            Vec::new(),
2807            Vec::new(),
2808            Vec::new(),
2809            Vec::new(),
2810            Vec::new(),
2811        ];
2812        let idx = GraphIndex::from_remote_directories(dirs, PermSet::ALL, loader);
2813
2814        // Predicate 99 is outside the tile's b-range → prune, zero fetches, empty.
2815        assert!(idx.match_pattern((Some(5), Some(99), None)).is_empty());
2816        assert_eq!(fetches.load(SeqCst), 0, "synopsis must skip the fetch");
2817
2818        // Object 999 outside the tile's c-range → prune, still zero fetches.
2819        assert!(idx.match_pattern((Some(5), None, Some(999))).is_empty());
2820        assert_eq!(
2821            fetches.load(SeqCst),
2822            0,
2823            "secondary-c prune also skips the fetch"
2824        );
2825
2826        // Predicate 10 is in range → the tile is fetched and the match returned.
2827        assert_eq!(
2828            idx.match_pattern((Some(5), Some(10), None)),
2829            vec![(5, 10, 100)]
2830        );
2831        assert_eq!(
2832            fetches.load(SeqCst),
2833            1,
2834            "an admissible secondary still fetches"
2835        );
2836    }
2837
2838    /// Without a synopsis (`None`), nothing is pruned early — the tile is always
2839    /// fetched and the in-tile zone map does the (correct) pruning, as before.
2840    #[test]
2841    fn absent_synopsis_never_prunes() {
2842        use std::sync::atomic::{AtomicUsize, Ordering::SeqCst};
2843        use std::sync::Arc;
2844        let block = {
2845            let mut b = TripleBlockBuilder::new();
2846            b.push((5, 10, 100));
2847            b.build()
2848        };
2849        let fetches = Arc::new(AtomicUsize::new(0));
2850        let (blk, fc) = (block.clone(), fetches.clone());
2851        let loader: TileLoader = Box::new(move |_si, _ti| {
2852            fc.fetch_add(1, SeqCst);
2853            Some(blk.clone())
2854        });
2855        let dirs = [
2856            vec![(5u32, 5u32, None)],
2857            Vec::new(),
2858            Vec::new(),
2859            Vec::new(),
2860            Vec::new(),
2861            Vec::new(),
2862        ];
2863        let idx = GraphIndex::from_remote_directories(dirs, PermSet::ALL, loader);
2864        // Predicate 99 absent, but with no synopsis the tile is fetched (then the
2865        // zone map yields no match) — correctness preserved, just no fetch saved.
2866        assert!(idx.match_pattern((Some(5), Some(99), None)).is_empty());
2867        assert_eq!(fetches.load(SeqCst), 1, "no synopsis ⇒ no early prune");
2868    }
2869
2870    /// The eight triple-pattern shapes, as `(s, p, o)` boundness.
2871    fn all_patterns() -> Vec<Pattern> {
2872        (0..8u8)
2873            .map(|mask| {
2874                (
2875                    (mask & 1 != 0).then_some(1u32),
2876                    (mask & 2 != 0).then_some(2u32),
2877                    (mask & 4 != 0).then_some(3u32),
2878                )
2879            })
2880            .collect()
2881    }
2882
2883    /// The claim the whole option rests on: **{SPO, POS, OSP} ties the longest
2884    /// bound prefix on all eight pattern shapes**, so the other three never win
2885    /// routing — only sort order. Enumerated and printed rather than asserted in
2886    /// prose, because if it were ever false a lean file would answer a pattern
2887    /// from a worse index without anything failing.
2888    #[test]
2889    fn perm_routing_never_leaves_core() {
2890        for pat in all_patterns() {
2891            let best_all = ALL_PERMS
2892                .iter()
2893                .map(|p| p.leading_bound(pat))
2894                .max()
2895                .unwrap();
2896            let best_core = PermSet::CORE
2897                .iter()
2898                .map(|p| p.leading_bound(pat))
2899                .max()
2900                .unwrap();
2901            let scores: Vec<String> = ALL_PERMS
2902                .iter()
2903                .map(|p| format!("{}={}", p.name(), p.leading_bound(pat)))
2904                .collect();
2905            eprintln!(
2906                "s={} p={} o={} | {} | best6={best_all} best3={best_core} chosen={}",
2907                pat.0.is_some() as u8,
2908                pat.1.is_some() as u8,
2909                pat.2.is_some() as u8,
2910                scores.join(" "),
2911                GraphIndex::best_permutation(pat).name(),
2912            );
2913            assert_eq!(
2914                best_core, best_all,
2915                "the three routing permutations must tie the best of six on {pat:?}"
2916            );
2917            let chosen = GraphIndex::best_permutation(pat);
2918            assert!(
2919                PermSet::CORE.contains(chosen),
2920                "best_permutation chose {} for {pat:?}, outside the routing three",
2921                chosen.name()
2922            );
2923            assert_eq!(
2924                chosen,
2925                GraphIndex::best_permutation_in(PermSet::CORE, pat),
2926                "routing must be identical with three permutations and with six"
2927            );
2928        }
2929    }
2930
2931    /// Restricting the set may never make a merge join pick a *worse-routed*
2932    /// stream than the plain lookup would use: with six the co-sorted
2933    /// permutation always ties the best prefix, and with three the guard
2934    /// declines rather than buying sort order with a whole-section scan.
2935    #[test]
2936    fn sorted_permutation_never_sacrifices_routing() {
2937        let mut declined = Vec::new();
2938        for pat in all_patterns() {
2939            for col in 0..3usize {
2940                let routed_all = GraphIndex::best_permutation(pat).leading_bound(pat);
2941                if let Some(p) = GraphIndex::permutation_sorted_on(pat, col) {
2942                    assert_eq!(
2943                        p.leading_bound(pat),
2944                        routed_all,
2945                        "six permutations must always co-sort at the best prefix"
2946                    );
2947                    assert_eq!(p.roles()[p.leading_bound(pat)], col);
2948                }
2949                match GraphIndex::permutation_sorted_on_in(PermSet::CORE, pat, col) {
2950                    Some(p) => {
2951                        assert!(PermSet::CORE.contains(p));
2952                        assert_eq!(
2953                            p.leading_bound(pat),
2954                            GraphIndex::best_permutation_in(PermSet::CORE, pat).leading_bound(pat)
2955                        );
2956                    }
2957                    None => {
2958                        if GraphIndex::permutation_sorted_on(pat, col).is_some() {
2959                            declined.push((pat, col));
2960                        }
2961                    }
2962                }
2963            }
2964        }
2965        // Exactly the three shapes SOP / PSO / OPS exist for: one bound
2966        // component, sorted on a column no remaining order can lead with after
2967        // it — subject-bound sorted on object, predicate-bound sorted on
2968        // subject, object-bound sorted on predicate.
2969        for (pat, col) in &declined {
2970            let bound: Vec<usize> = (0..3)
2971                .filter(|&i| [pat.0, pat.1, pat.2][i].is_some())
2972                .collect();
2973            assert_eq!(
2974                bound.len(),
2975                1,
2976                "only single-bound shapes lose a merge order"
2977            );
2978            assert_ne!(bound[0], *col);
2979        }
2980        eprintln!("three-permutation merge-join declines: {declined:?}");
2981        assert_eq!(declined.len(), 3, "exactly three (bound, sort) shapes lost");
2982    }
2983
2984    #[test]
2985    fn perm_set_masks_and_positions() {
2986        assert_eq!(PermSet::ALL.len(), 6);
2987        assert_eq!(PermSet::CORE.len(), 3);
2988        assert_eq!(PermSet::CORE.bits(), 0b0000_0111);
2989        assert_eq!(PermSet::CORE.names(), vec!["SPO", "POS", "OSP"]);
2990        assert_eq!(
2991            PermSet::ALL.names(),
2992            vec!["SPO", "POS", "OSP", "SOP", "PSO", "OPS"]
2993        );
2994        // Container position is rank among the STORED permutations, which is
2995        // why the routing three had to lead ALL_PERMS.
2996        for (i, p) in PermSet::CORE.iter().enumerate() {
2997            assert_eq!(PermSet::CORE.position(p), Some(i));
2998            assert_eq!(p.section_index(), i);
2999        }
3000        assert_eq!(PermSet::CORE.position(IndexPermutation::Sop), None);
3001        assert_eq!(PermSet::ALL.position(IndexPermutation::Ops), Some(5));
3002        // Only supersets of the routing three are legal.
3003        assert!(PermSet::from_bits(0b0000_0111).is_ok());
3004        assert!(PermSet::from_bits(0b0011_1111).is_ok());
3005        assert!(PermSet::from_bits(0b0000_1111).is_ok());
3006        assert!(PermSet::from_bits(0b0000_0011).is_err());
3007        assert!(PermSet::from_bits(0b0011_1000).is_err());
3008        assert!(PermSet::from_bits(0b1000_0111).is_err());
3009    }
3010
3011    /// A lean index answers every pattern shape with exactly the rows a full
3012    /// one does — the property that makes the option safe at all.
3013    #[test]
3014    fn three_and_six_agree_on_every_pattern() {
3015        let triples: Vec<Triple> = (0..200u32)
3016            .map(|i| (i % 17 + 1, i % 5 + 1, i % 23 + 1))
3017            .collect();
3018        let six = GraphIndexBuilder::from_triples(triples.clone())
3019            .with_tile_budget(128)
3020            .build();
3021        let three = GraphIndexBuilder::from_triples(triples)
3022            .with_tile_budget(128)
3023            .with_perms(PermSet::CORE)
3024            .build();
3025        assert_eq!(six.perms(), PermSet::ALL);
3026        assert_eq!(three.perms(), PermSet::CORE);
3027        for perm in [
3028            IndexPermutation::Sop,
3029            IndexPermutation::Pso,
3030            IndexPermutation::Ops,
3031        ] {
3032            assert!(three.tile_sections()[perm.section_index()].is_empty());
3033        }
3034        for a in [None, Some(3u32)] {
3035            for b in [None, Some(2u32)] {
3036                for c in [None, Some(9u32)] {
3037                    let mut x = six.match_pattern((a, b, c));
3038                    let mut y = three.match_pattern((a, b, c));
3039                    x.sort_unstable();
3040                    y.sort_unstable();
3041                    assert_eq!(x, y, "pattern {:?} disagreed", (a, b, c));
3042                }
3043            }
3044        }
3045    }
3046}