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