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