1use std::collections::{BTreeMap, HashMap};
18
19use crate::file::Rete;
20use crate::index::{GraphIndex, Pattern, ProbeBatch};
21use crate::row::{Ctx, Row, Slots, Val};
22use crate::triples::Triple;
23
24#[derive(Debug, Clone, PartialEq, Eq)]
26pub enum PatternTerm {
27 Var(String),
28 Const(String),
29}
30
31impl PatternTerm {
32 pub fn parse(token: &str) -> Self {
34 if let Some(name) = token.strip_prefix('?') {
35 PatternTerm::Var(name.to_string())
36 } else {
37 PatternTerm::Const(token.to_string())
38 }
39 }
40}
41
42#[derive(Debug, Clone)]
44pub struct TriplePattern {
45 pub s: PatternTerm,
46 pub p: PatternTerm,
47 pub o: PatternTerm,
48}
49
50pub type Binding = BTreeMap<String, String>;
52
53#[derive(Clone, Copy)]
64enum SlotTerm {
65 Var(usize),
66 Node(u32),
67 Pred(u32),
68}
69
70fn pred_tag(p: u32) -> i64 {
71 -(p as i64) - 1
72}
73
74pub(crate) fn collect_pattern_slots(patterns: &[TriplePattern], slots: &mut Slots) {
76 for p in patterns {
77 for t in [&p.s, &p.p, &p.o] {
78 if let PatternTerm::Var(v) = t {
79 slots.add(v);
80 }
81 }
82 }
83}
84
85fn lower(patterns: &[TriplePattern], ctx: &Ctx) -> Option<Vec<(SlotTerm, SlotTerm, SlotTerm)>> {
88 let dict = ctx.rete.dictionary();
89 let node = |t: &PatternTerm| -> Option<SlotTerm> {
90 match t {
91 PatternTerm::Var(v) => ctx.slots.slot(v).map(SlotTerm::Var),
92 PatternTerm::Const(c) => dict.node_of_term(c).map(SlotTerm::Node),
93 }
94 };
95 let pred = |t: &PatternTerm| -> Option<SlotTerm> {
96 match t {
97 PatternTerm::Var(v) => ctx.slots.slot(v).map(SlotTerm::Var),
98 PatternTerm::Const(c) => dict.predicate_id(c).map(SlotTerm::Pred),
99 }
100 };
101 let mut lowered = Vec::with_capacity(patterns.len());
102 for p in patterns {
103 lowered.push((node(&p.s)?, pred(&p.p)?, node(&p.o)?));
104 }
105 Some(lowered)
106}
107
108pub fn eval_bgp(rete: &Rete, patterns: &[TriplePattern]) -> Vec<Binding> {
111 let mut slots = Slots::new();
112 collect_pattern_slots(patterns, &mut slots);
113 let ctx = Ctx::new(rete, slots);
114 eval_bgp_rows(&ctx, rete.default_index(), patterns)
115 .into_iter()
116 .map(|row| row_to_binding(&ctx, &row))
117 .collect()
118}
119
120pub(crate) fn row_to_binding(ctx: &Ctx, row: &Row) -> Binding {
123 let mut b = Binding::new();
124 for (i, v) in row.iter().enumerate() {
125 if let Some(val) = v {
126 if let Some(t) = ctx.resolver.str_once(val) {
127 b.insert(ctx.slots.name(i).to_string(), t);
128 }
129 }
130 }
131 b
132}
133
134fn plan_order(
145 ctx: &Ctx,
146 index: &GraphIndex,
147 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
148) -> (Vec<usize>, Vec<f64>) {
149 if lowered.len() == 1 {
150 return (vec![0], vec![0.0]);
151 }
152 let order = selectivity_order(ctx, index, lowered);
153 let scan_est = tile_estimates(ctx, index, lowered, &std::collections::HashSet::new());
154 (order, scan_est)
155}
156
157pub(crate) fn eval_bgp_rows(ctx: &Ctx, index: &GraphIndex, patterns: &[TriplePattern]) -> Vec<Row> {
160 if patterns.is_empty() {
162 return vec![ctx.slots.empty_row()];
163 }
164 let Some(lowered) = lower(patterns, ctx) else {
166 return Vec::new();
167 };
168
169 let (order, scan_est) = plan_order(ctx, index, &lowered);
173 let mut rows: Vec<Row> = vec![ctx.slots.empty_row()];
174 let mut bound: Vec<usize> = Vec::new();
175 let mut merged: [bool; 2] = [false, false];
176
177 if order.len() >= 2 {
182 if let Some((rel, slots)) =
183 try_merge_join(ctx, index, &lowered[order[0]], &lowered[order[1]])
184 {
185 rows = rel;
186 bound = slots;
187 merged = [true, true];
188 }
189 }
190
191 for (k, &idx) in order.iter().enumerate() {
192 if k < 2 && merged[k] {
193 continue; }
195 let t = lowered[idx];
196 let shares_bound = pattern_slots(&t).iter().any(|s| bound.contains(s));
206 let do_probe = !bound.is_empty()
217 && shares_bound
218 && !rows.is_empty()
219 && (probe_beats_scan(rows.len(), scan_est[idx])
220 || if index.is_remote() {
221 rows.len() <= remote_probe_max(index)
222 && (rows.len() <= REMOTE_PROBE_MIN || !pattern_is_selective(&t))
223 } else {
224 rows.len() <= BGP_PROBE_THRESHOLD
225 });
226 if do_probe {
227 let taken = std::mem::take(&mut rows);
228 let mut next: Vec<Row> = Vec::with_capacity(taken.len());
235 for base in windowed(index, taken.into_iter(), bgp_probe_pattern(ctx, t)) {
236 next.extend(probe_rows(ctx, index, t, base));
237 }
238 rows = next;
239 } else {
240 let Some((rel, rel_slots)) = pattern_rows(ctx, index, &t) else {
241 return Vec::new();
242 };
243 rows = hash_join(rows, &bound, rel, &rel_slots);
244 }
245 for s in pattern_slots(&t) {
246 if !bound.contains(&s) {
247 bound.push(s);
248 }
249 }
250 if rows.is_empty() {
251 break;
252 }
253 }
254 rows
255}
256
257fn try_merge_join(
269 ctx: &Ctx,
270 index: &GraphIndex,
271 ta: &(SlotTerm, SlotTerm, SlotTerm),
272 tb: &(SlotTerm, SlotTerm, SlotTerm),
273) -> Option<(Vec<Row>, Vec<usize>)> {
274 let dict = ctx.rete.dictionary();
275 let sa = pattern_slots(ta);
276 let sb = pattern_slots(tb);
277 let shared: Vec<usize> = sa.iter().copied().filter(|s| sb.contains(s)).collect();
278 if shared.len() != 1 {
279 return None;
280 }
281 let v = shared[0];
282 let col_of = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Option<usize> {
283 [&t.0, &t.1, &t.2]
284 .iter()
285 .position(|x| matches!(x, SlotTerm::Var(i) if *i == v))
286 };
287 let ca = col_of(ta)?;
288 let cb = col_of(tb)?;
289 if ca != cb {
290 return None; }
292 if merge_seed_lopsided(ctx, index, ta, tb) {
302 return None;
303 }
304 let lower = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Option<Pattern> {
305 Some((
306 const_subject(&t.0, dict)?,
307 const_predicate(&t.1)?,
308 const_object(&t.2, dict)?,
309 ))
310 };
311 let collect = |t: &(SlotTerm, SlotTerm, SlotTerm), col: usize| -> Option<Vec<(u32, Row)>> {
314 let pat = lower(t)?;
315 let mut out = Vec::new();
316 for tri in canon_ahead(ctx, t, index.scan_iter_sorted_on(pat, col)?) {
317 if let Some(r) = triple_row(ctx, t, tri) {
318 out.push(([tri.0, tri.1, tri.2][col], r));
319 }
320 }
321 Some(out)
322 };
323 let rows_a = collect(ta, ca)?;
324 let rows_b = collect(tb, cb)?;
325
326 let mut out: Vec<Row> = Vec::new();
327 let (mut i, mut j) = (0usize, 0usize);
328 while i < rows_a.len() && j < rows_b.len() {
329 match rows_a[i].0.cmp(&rows_b[j].0) {
330 std::cmp::Ordering::Less => i += 1,
331 std::cmp::Ordering::Greater => j += 1,
332 std::cmp::Ordering::Equal => {
333 let key = rows_a[i].0;
334 let (i0, j0) = (i, j);
335 while i < rows_a.len() && rows_a[i].0 == key {
336 i += 1;
337 }
338 while j < rows_b.len() && rows_b[j].0 == key {
339 j += 1;
340 }
341 for (_, ra) in &rows_a[i0..i] {
342 for (_, rb) in &rows_b[j0..j] {
343 let mut row = ra.clone();
346 let mut ok = true;
347 for (slot, val) in rb.iter().enumerate() {
348 if let Some(val) = val {
349 match &row[slot] {
350 Some(existing) if existing != val => {
351 ok = false;
352 break;
353 }
354 _ => row[slot] = Some(val.clone()),
355 }
356 }
357 }
358 if ok {
359 out.push(row);
360 }
361 }
362 }
363 }
364 }
365 }
366 let mut slots = pattern_slots(ta);
367 for s in pattern_slots(tb) {
368 if !slots.contains(&s) {
369 slots.push(s);
370 }
371 }
372 Some((out, slots))
373}
374
375const BGP_PROBE_THRESHOLD: usize = 512;
383
384const PROBE_SCAN_FLOOR: f64 = 65_536.0;
389
390const PROBE_RATIO: f64 = 16.0;
395
396fn probe_beats_scan(rows: usize, scan_est: f64) -> bool {
399 scan_est >= limits().probe_floor && (rows as f64) * PROBE_RATIO <= scan_est
400}
401
402pub(crate) fn probe_row_budget(est: f64) -> Option<usize> {
407 (est >= limits().probe_floor).then(|| (est / PROBE_RATIO) as usize)
408}
409
410pub(crate) fn bgp_min_estimate(
414 ctx: &Ctx,
415 index: &GraphIndex,
416 patterns: &[TriplePattern],
417) -> Option<f64> {
418 let lowered = lower(patterns, ctx)?;
419 tile_estimates(ctx, index, &lowered, &std::collections::HashSet::new())
420 .into_iter()
421 .reduce(f64::min)
422}
423
424pub(crate) fn bgp_total_estimate(
432 ctx: &Ctx,
433 index: &GraphIndex,
434 patterns: &[TriplePattern],
435) -> Option<f64> {
436 let lowered = lower(patterns, ctx)?;
437 Some(
438 tile_estimates(ctx, index, &lowered, &std::collections::HashSet::new())
439 .into_iter()
440 .sum(),
441 )
442}
443
444fn is_unbound_class(ctx: &Ctx, t: &(SlotTerm, SlotTerm, SlotTerm), shared: &[usize]) -> bool {
447 let type_pid = ctx.rete.dictionary().predicate_id(crate::file::RDF_TYPE);
448 matches!(
449 t,
450 (SlotTerm::Var(x), SlotTerm::Pred(p), SlotTerm::Var(c))
451 if Some(*p) == type_pid && shared.contains(x) && !shared.contains(c) && x != c
452 )
453}
454
455fn fat_enough(est: f64) -> bool {
459 #[cfg(test)]
460 if TEST_LIMITS.with(|c| c.get()).is_some() {
461 return est >= limits().probe_floor;
462 }
463 est >= FAT_SCAN_ROWS
464}
465
466pub(crate) struct CorrelatedProbe {
473 plan: Option<ProbePlan>,
475 slots: Vec<usize>,
477}
478
479impl CorrelatedProbe {
480 pub(crate) fn new(
484 ctx: &Ctx,
485 index: &GraphIndex,
486 patterns: &[TriplePattern],
487 seed: &[bool],
488 ) -> Option<Self> {
489 if patterns.is_empty() {
490 return None;
491 }
492 let mut slots: Vec<usize> = Vec::new();
493 for p in patterns {
494 for t in [&p.s, &p.p, &p.o] {
495 if let PatternTerm::Var(v) = t {
496 if let Some(i) = ctx.slots.slot(v) {
497 if !slots.contains(&i) {
498 slots.push(i);
499 }
500 }
501 }
502 }
503 }
504 if !slots.iter().any(|&i| seed[i]) {
505 return None;
506 }
507 let Some(est) = bgp_min_estimate(ctx, index, patterns) else {
509 return Some(CorrelatedProbe { plan: None, slots });
510 };
511 if !fat_enough(est) {
512 return None;
513 }
514 Some(CorrelatedProbe {
515 plan: ProbePlan::new(ctx, index, patterns, seed),
516 slots,
517 })
518 }
519
520 pub(crate) fn shares(&self, row: &Row) -> bool {
522 self.slots.iter().any(|&i| row[i].is_some())
523 }
524
525 pub(crate) fn probe(&self, ctx: &Ctx, index: &GraphIndex, row: &Row) -> bool {
529 match &self.plan {
530 None => false,
531 Some(plan) => ProbeJoin::from_plan(ctx, index, plan, row.clone())
532 .next()
533 .is_some(),
534 }
535 }
536}
537
538#[cfg(test)]
541pub(crate) fn with_probe_floor<T>(floor: f64, f: impl FnOnce() -> T) -> T {
542 let saved = TEST_LIMITS.with(|c| c.get());
543 TEST_LIMITS.with(|c| {
544 c.set(Some(PlanLimits {
545 probe_floor: floor,
546 ..limits()
547 }))
548 });
549 let out = f();
550 TEST_LIMITS.with(|c| c.set(saved));
551 out
552}
553
554#[cfg(test)]
558#[allow(dead_code)]
559pub(crate) fn with_plan_limits<T>(
560 probe_floor: f64,
561 stream_seed: f64,
562 hash_build: f64,
563 f: impl FnOnce() -> T,
564) -> T {
565 let saved = TEST_LIMITS.with(|c| c.get());
566 TEST_LIMITS.with(|c| {
567 c.set(Some(PlanLimits {
568 probe_floor,
569 stream_seed,
570 hash_build,
571 }))
572 });
573 let out = f();
574 TEST_LIMITS.with(|c| c.set(saved));
575 out
576}
577
578#[derive(Clone, Copy)]
581struct PlanLimits {
582 probe_floor: f64,
583 stream_seed: f64,
584 hash_build: f64,
585}
586
587#[cfg(test)]
588thread_local! {
589 static TEST_LIMITS: std::cell::Cell<Option<PlanLimits>> = const { std::cell::Cell::new(None) };
590}
591
592fn limits() -> PlanLimits {
593 #[cfg(test)]
594 if let Some(l) = TEST_LIMITS.with(|c| c.get()) {
595 return l;
596 }
597 PlanLimits {
598 probe_floor: PROBE_SCAN_FLOOR,
599 stream_seed: STREAM_SEED_ROWS,
600 hash_build: HASH_BUILD_ROWS,
601 }
602}
603
604const STREAM_SEED_ROWS: f64 = (1u64 << 21) as f64;
612
613const HASH_BUILD_ROWS: f64 = (1u64 << 20) as f64;
616
617fn tile_estimates(
623 ctx: &Ctx,
624 index: &GraphIndex,
625 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
626 seed: &std::collections::HashSet<usize>,
627) -> Vec<f64> {
628 const SEL_SUBJECT: f64 = 0.001;
629 const SEL_OBJECT: f64 = 0.02;
630 const SEL_PREDICATE: f64 = 0.05;
631 let dict = ctx.rete.dictionary();
632 let total = ctx.rete.index_triples(index);
633 let seeded = |x: &SlotTerm| matches!(x, SlotTerm::Var(v) if seed.contains(v));
634 let needs_stats = lowered
642 .iter()
643 .any(|t| matches!(t.1, SlotTerm::Pred(_)) && (seeded(&t.0) || seeded(&t.2)));
644 let stats: std::collections::HashMap<u32, &crate::meta::PredStat> = if needs_stats {
645 ctx.rete
646 .planner_stats(true)
647 .iter()
648 .map(|s| (s.predicate, s))
649 .collect()
650 } else {
651 std::collections::HashMap::new()
652 };
653 let patterns: Vec<Pattern> = lowered
657 .iter()
658 .filter_map(|t| {
659 Some((
660 const_subject(&t.0, dict)?,
661 const_predicate(&t.1)?,
662 const_object(&t.2, dict)?,
663 ))
664 })
665 .collect();
666 index.prefault_estimate_leaves(&patterns);
667 lowered
668 .iter()
669 .map(|t| {
670 let (Some(s), Some(p), Some(o)) = (
671 const_subject(&t.0, dict),
672 const_predicate(&t.1),
673 const_object(&t.2, dict),
674 ) else {
675 return 0.0;
676 };
677 let mut est = index.estimate_matches((s, p, o), total);
678 if est == 0.0 {
679 return 0.0;
680 }
681 let st = match t.1 {
682 SlotTerm::Pred(pid) => stats.get(&pid).copied(),
683 _ => None,
684 };
685 if seeded(&t.0) {
686 est *= match st {
687 Some(st) if st.distinct_subjects > 0 => 1.0 / st.distinct_subjects as f64,
688 _ => SEL_SUBJECT,
689 };
690 }
691 if seeded(&t.1) {
692 est *= SEL_PREDICATE;
693 }
694 if seeded(&t.2) {
695 est *= match st {
696 Some(st) if st.distinct_objects > 0 => 1.0 / st.distinct_objects as f64,
697 _ => SEL_OBJECT,
698 };
699 }
700 est.max(1.0)
701 })
702 .collect()
703}
704
705const REMOTE_PROBE_MIN: usize = 8;
714const REMOTE_PROBE_MAX: usize = 1024;
715
716fn remote_probe_max(index: &GraphIndex) -> usize {
723 REMOTE_PROBE_MAX * index.read_concurrency().clamp(1, 16)
724}
725
726const WINDOW_START_ROWS: usize = 256;
729
730const WINDOW_MAX_ROWS: usize = 1 << 16;
734
735const WINDOW_CHUNK_ROWS: usize = 256;
738
739type ProbePattern<'a> = Box<dyn Fn(&Row) -> Option<Pattern> + 'a>;
741
742pub(crate) struct Windowed<'a> {
760 index: &'a GraphIndex,
761 upstream: Box<dyn Iterator<Item = Row> + 'a>,
762 pat_of: Option<ProbePattern<'a>>,
764 pending: std::collections::VecDeque<Row>,
766 ready: std::collections::VecDeque<Row>,
768 size: usize,
770}
771
772pub(crate) fn windowed<'a>(
774 index: &'a GraphIndex,
775 upstream: impl Iterator<Item = Row> + 'a,
776 pat_of: impl Fn(&Row) -> Option<Pattern> + 'a,
777) -> Windowed<'a> {
778 Windowed {
779 index,
780 upstream: Box::new(upstream),
781 pat_of: index.is_remote().then(|| {
782 let f: ProbePattern<'a> = Box::new(pat_of);
783 f
784 }),
785 pending: std::collections::VecDeque::new(),
786 ready: std::collections::VecDeque::new(),
787 size: WINDOW_START_ROWS,
788 }
789}
790
791impl Windowed<'_> {
792 fn refill(&mut self, pat_of: &dyn Fn(&Row) -> Option<Pattern>) {
794 let mut batch = ProbeBatch::default();
795 'window: while self.ready.len() < self.size {
796 let chunk = WINDOW_CHUNK_ROWS.min(self.size - self.ready.len());
797 while self.pending.len() < chunk {
798 match self.upstream.next() {
799 Some(r) => self.pending.push_back(r),
800 None => break,
801 }
802 }
803 if self.pending.is_empty() {
804 break;
805 }
806 let chunk = chunk.min(self.pending.len());
807 let pats: Vec<Pattern> = self.pending.iter().take(chunk).filter_map(pat_of).collect();
809 self.index.prefault_leaves(&pats);
810 for _ in 0..chunk {
811 if let Some(p) = pat_of(&self.pending[0]) {
812 if !self.index.probe_batch_add(&mut batch, p) {
813 break 'window; }
815 }
816 let row = self.pending.pop_front().expect("chunk rows are pending");
817 self.ready.push_back(row);
818 }
819 }
820 self.index.probe_batch_fault(batch);
821 self.size = (self.size * 4).min(WINDOW_MAX_ROWS);
822 }
823}
824
825impl Iterator for Windowed<'_> {
826 type Item = Row;
827
828 fn next(&mut self) -> Option<Row> {
829 let Some(pat_of) = self.pat_of.take() else {
831 return self.upstream.next();
832 };
833 if self.ready.is_empty() {
834 self.refill(pat_of.as_ref());
835 }
836 self.pat_of = Some(pat_of);
837 self.ready.pop_front()
838 }
839}
840
841fn bgp_probe_pattern<'a>(
845 ctx: &'a Ctx<'_>,
846 t: (SlotTerm, SlotTerm, SlotTerm),
847) -> impl Fn(&Row) -> Option<Pattern> + 'a {
848 move |base| match (
849 probe_subject(ctx, &t.0, base),
850 probe_predicate(ctx, &t.1, base),
851 probe_object(ctx, &t.2, base),
852 ) {
853 (Some(s), Some(p), Some(o)) => Some((s, p, o)),
854 _ => None,
855 }
856}
857
858pub(crate) fn plan_windowed<'q>(
866 ctx: &'q Ctx<'q>,
867 index: &'q GraphIndex,
868 plan: &ProbePlan,
869 rows: Box<dyn Iterator<Item = Row> + 'q>,
870) -> Box<dyn Iterator<Item = Row> + 'q> {
871 let Some(&t) = plan.pats.first() else {
872 return rows;
873 };
874 if !index.is_remote() {
875 return rows;
876 }
877 let pat = bgp_probe_pattern(ctx, t);
878 let mut win = windowed(index, rows, move |base| {
879 pat(base).filter(|(s, _, o)| s.is_some() || o.is_some())
880 });
881 if let Some(demand) = ctx.limit_hint.get() {
886 win.size = win.size.min(demand.max(1));
887 }
888 Box::new(win)
889}
890
891pub(crate) fn prefetch_subject_probes(
897 ctx: &Ctx,
898 index: &GraphIndex,
899 patterns: &[TriplePattern],
900 sv: &str,
901 subject_ids: &[u32],
902) {
903 if !index.is_remote() {
904 return;
905 }
906 let Some(lowered) = lower(patterns, ctx) else {
907 return;
908 };
909 let Some(slot) = ctx.slots.slot(sv) else {
910 return;
911 };
912 let dict = ctx.rete.dictionary();
913 let mut pats: Vec<Pattern> = Vec::new();
914 for &sid in subject_ids {
915 let mut base = ctx.slots.empty_row();
916 base[slot] = Some(Val::Id(dict.subject_node(sid) as i64));
917 for t in &lowered {
918 if !matches!(t.0, SlotTerm::Var(i) if i == slot) {
919 continue;
920 }
921 if let (Some(s), Some(p), Some(o)) = (
922 probe_subject(ctx, &t.0, &base),
923 probe_predicate(ctx, &t.1, &base),
924 probe_object(ctx, &t.2, &base),
925 ) {
926 pats.push((s, p, o));
927 }
928 }
929 }
930 index.prefetch_probe_tiles(&pats);
931}
932
933fn pattern_is_selective(t: &(SlotTerm, SlotTerm, SlotTerm)) -> bool {
936 matches!(t.0, SlotTerm::Node(_)) || matches!(t.2, SlotTerm::Node(_))
937}
938
939fn pattern_slots(t: &(SlotTerm, SlotTerm, SlotTerm)) -> Vec<usize> {
941 let mut slots: Vec<usize> = Vec::new();
942 for term in [&t.0, &t.1, &t.2] {
943 if let SlotTerm::Var(i) = term {
944 if !slots.contains(i) {
945 slots.push(*i);
946 }
947 }
948 }
949 slots
950}
951
952const CANON_AHEAD: usize = 64;
955
956fn canon_ahead<'a, 'c>(
966 ctx: &'a Ctx<'c>,
967 t: &(SlotTerm, SlotTerm, SlotTerm),
968 triples: impl Iterator<Item = Triple> + 'a,
969) -> Box<dyn Iterator<Item = Triple> + 'a> {
970 if !matches!(t.1, SlotTerm::Var(_)) || !ctx.rete.dictionary().faults_chunks() {
971 return Box::new(triples);
972 }
973 let decoded = |term: &SlotTerm| match term {
976 SlotTerm::Var(i) => ctx.decodes_slot(*i),
977 _ => false,
978 };
979 Box::new(CanonAhead {
980 ctx,
981 triples,
982 run: std::collections::VecDeque::new(),
983 decode: (decoded(&t.0), decoded(&t.2)),
984 ahead: 0,
985 })
986}
987
988struct CanonAhead<'a, 'c, I> {
989 ctx: &'a Ctx<'c>,
990 triples: I,
991 run: std::collections::VecDeque<Triple>,
992 decode: (bool, bool),
994 ahead: usize,
997}
998
999impl<I: Iterator<Item = Triple>> Iterator for CanonAhead<'_, '_, I> {
1000 type Item = Triple;
1001
1002 fn next(&mut self) -> Option<Triple> {
1003 if self.run.is_empty() {
1004 self.run.extend(self.triples.by_ref().take(CANON_AHEAD));
1005 let preds: Vec<u32> = self.run.iter().map(|t| t.1).collect();
1006 let dict = self.ctx.rete.dictionary();
1011 let take = self
1012 .ctx
1013 .decode_rows()
1014 .saturating_sub(self.ahead)
1015 .min(self.run.len());
1016 self.ahead += take;
1017 let mut nodes: Vec<u32> = Vec::new();
1018 for t in self.run.iter().take(take) {
1019 if self.decode.0 {
1020 nodes.push(dict.subject_node(t.0));
1021 }
1022 if self.decode.1 {
1023 nodes.push(dict.object_node(t.2));
1024 }
1025 }
1026 self.ctx.resolver.prefetch_canon(&preds, &nodes);
1027 }
1028 self.run.pop_front()
1029 }
1030}
1031
1032fn pred_val(ctx: &Ctx, slot: &SlotTerm, p_id: u32) -> i64 {
1039 match slot {
1040 SlotTerm::Var(_) => ctx.resolver.canon_id(pred_tag(p_id)),
1041 _ => pred_tag(p_id),
1042 }
1043}
1044
1045fn triple_row(
1049 ctx: &Ctx,
1050 t: &(SlotTerm, SlotTerm, SlotTerm),
1051 (s_id, p_id, o_id): (u32, u32, u32),
1052) -> Option<Row> {
1053 crate::guard::check();
1055 let dict = ctx.rete.dictionary();
1056 let s_val = dict.subject_node(s_id) as i64;
1057 let p_val = pred_val(ctx, &t.1, p_id);
1058 let o_val = dict.object_node(o_id) as i64;
1059 let mut row = ctx.slots.empty_row();
1060 for (term, val) in [(&t.0, s_val), (&t.1, p_val), (&t.2, o_val)] {
1061 if let SlotTerm::Var(i) = term {
1062 match row[*i] {
1063 Some(Val::Id(existing)) if existing != val => return None,
1064 Some(_) => {}
1065 None => row[*i] = Some(Val::Id(val)),
1066 }
1067 }
1068 }
1069 Some(row)
1070}
1071
1072fn scan_rows<'q>(
1077 ctx: &'q Ctx<'q>,
1078 index: &'q GraphIndex,
1079 t: (SlotTerm, SlotTerm, SlotTerm),
1080) -> Option<impl Iterator<Item = Row> + 'q> {
1081 let dict = ctx.rete.dictionary();
1082 let (sid, pid, oid) = (
1083 const_subject(&t.0, dict)?,
1084 const_predicate(&t.1)?,
1085 const_object(&t.2, dict)?,
1086 );
1087 Some(
1088 canon_ahead(ctx, &t, index.scan_iter((sid, pid, oid)))
1089 .filter_map(move |triple| triple_row(ctx, &t, triple)),
1090 )
1091}
1092
1093pub(crate) fn quad_scan_rows<'q>(
1100 ctx: &'q Ctx<'q>,
1101 patterns: &[TriplePattern],
1102 gslot: usize,
1103) -> Option<Box<dyn Iterator<Item = Row> + 'q>> {
1104 let [p] = patterns else {
1105 return None;
1106 };
1107 if [&p.s, &p.p, &p.o]
1108 .iter()
1109 .any(|t| matches!(t, PatternTerm::Var(v) if ctx.slots.slot(v) == Some(gslot)))
1110 {
1111 return None;
1112 }
1113 let dict = ctx.rete.dictionary();
1114 let Some(lowered) = lower(patterns, ctx) else {
1115 return Some(Box::new(std::iter::empty()));
1116 };
1117 let t = lowered[0];
1118 let (Some(sid), Some(pid), Some(oid)) = (
1119 const_subject(&t.0, dict),
1120 const_predicate(&t.1),
1121 const_object(&t.2, dict),
1122 ) else {
1123 return Some(Box::new(std::iter::empty()));
1124 };
1125 let scan = ctx.rete.named_quad_scan((sid, pid, oid))?;
1126 Some(Box::new(scan.filter_map(move |(g, triple)| {
1127 let mut row = triple_row(ctx, &t, triple)?;
1128 row[gslot] = Some(Val::Id(dict.subject_node(g) as i64));
1129 Some(row)
1130 })))
1131}
1132
1133mod class_probe;
1134pub(crate) use class_probe::class_probe_rows;
1135pub use class_probe::set_class_route;
1136
1137pub(crate) type ScanPattern = (Option<u32>, Option<u32>, Option<u32>);
1139
1140pub(crate) fn driver_pattern(ctx: &Ctx, patterns: &[TriplePattern]) -> Option<ScanPattern> {
1145 let dict = ctx.rete.dictionary();
1146 let lowered = lower(patterns, ctx)?;
1147 let mut best: Option<(u32, ScanPattern)> = None;
1148 for t in &lowered {
1149 let (sid, pid, oid) = (
1150 const_subject(&t.0, dict)?,
1151 const_predicate(&t.1)?,
1152 const_object(&t.2, dict)?,
1153 );
1154 let score =
1155 3 * u32::from(sid.is_some()) + u32::from(pid.is_some()) + 3 * u32::from(oid.is_some());
1156 if score > 0 && best.is_none_or(|(b, _)| score > b) {
1157 best = Some((score, (sid, pid, oid)));
1158 }
1159 }
1160 best.map(|(_, pat)| pat)
1161}
1162
1163fn pattern_rows(
1166 ctx: &Ctx,
1167 index: &GraphIndex,
1168 t: &(SlotTerm, SlotTerm, SlotTerm),
1169) -> Option<(Vec<Row>, Vec<usize>)> {
1170 let slots = pattern_slots(t);
1171 let mut rel: Vec<Row> = Vec::new();
1172 let dict = ctx.rete.dictionary();
1173 let (sid, pid, oid) = (
1174 const_subject(&t.0, dict)?,
1175 const_predicate(&t.1)?,
1176 const_object(&t.2, dict)?,
1177 );
1178 for triple in canon_ahead(ctx, t, index.scan_iter((sid, pid, oid))) {
1181 if let Some(row) = triple_row(ctx, t, triple) {
1182 rel.push(row);
1183 }
1184 }
1185 Some((rel, slots))
1186}
1187
1188fn pattern_estimates(
1200 ctx: &Ctx,
1201 index: &GraphIndex,
1202 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1203 seed: &std::collections::HashSet<usize>,
1204) -> Option<Vec<f64>> {
1205 let pyr = ctx.rete.pyramid_if_loaded()?;
1208 let mut pred: std::collections::HashMap<u32, u64> = std::collections::HashMap::new();
1209 for e in &pyr.summary {
1210 *pred.entry(e.predicate).or_insert(0) += e.count as u64;
1211 }
1212 let stats: std::collections::HashMap<u32, &crate::meta::PredStat> = ctx
1219 .rete
1220 .planner_stats(true)
1221 .iter()
1222 .map(|s| (s.predicate, s))
1223 .collect();
1224 let graph_total = ctx.rete.index_triples(index).max(1) as f64;
1227 let total = graph_total;
1228 let num_preds = pred.len().max(1) as f64;
1229 const SEL_SUBJECT: f64 = 0.001;
1231 const SEL_OBJECT: f64 = 0.02;
1232 let node_bound = |t: &SlotTerm| match t {
1233 SlotTerm::Node(_) => true,
1234 SlotTerm::Var(v) => seed.contains(v),
1235 SlotTerm::Pred(_) => false,
1236 };
1237 Some(
1238 lowered
1239 .iter()
1240 .map(|t| {
1241 let (base, st) = match t.1 {
1246 SlotTerm::Pred(p) => {
1247 (*pred.get(&p).unwrap_or(&0) as f64, stats.get(&p).copied())
1248 }
1249 SlotTerm::Var(v) if seed.contains(&v) => (total / num_preds, None),
1250 _ => (total, None),
1251 };
1252 let mut est = base.min(graph_total).max(1.0);
1253 if node_bound(&t.0) {
1254 est *= match st {
1255 Some(s) if s.distinct_subjects > 0 => 1.0 / s.distinct_subjects as f64,
1256 _ => SEL_SUBJECT,
1257 };
1258 }
1259 if node_bound(&t.2) {
1260 est *= match st {
1261 Some(s) if s.distinct_objects > 0 => 1.0 / s.distinct_objects as f64,
1262 _ => SEL_OBJECT,
1263 };
1264 }
1265 est.max(1.0)
1266 })
1267 .collect(),
1268 )
1269}
1270
1271pub(crate) fn bgp_min_scan_bytes(
1278 ctx: &Ctx,
1279 index: &GraphIndex,
1280 patterns: &[TriplePattern],
1281) -> Option<u64> {
1282 let lowered = lower(patterns, ctx)?;
1283 lowered
1284 .iter()
1285 .map(|t| pattern_scan_bytes(ctx, index, t))
1286 .min()
1287}
1288
1289fn pattern_scan_bytes(ctx: &Ctx, index: &GraphIndex, t: &(SlotTerm, SlotTerm, SlotTerm)) -> u64 {
1306 let dict = ctx.rete.dictionary();
1307 match (
1308 const_subject(&t.0, dict),
1309 const_predicate(&t.1),
1310 const_object(&t.2, dict),
1311 ) {
1312 (Some(s), Some(p), Some(o)) => routed_scan_bytes(index, (s, p, o)),
1313 _ => 0,
1314 }
1315}
1316
1317pub(crate) fn routed_scan_bytes(index: &GraphIndex, pattern: Pattern) -> u64 {
1319 let sections = index.tile_sections();
1320 let mut best = u64::MAX;
1321 for perm in index.perms().iter() {
1325 let tiles = sections[perm.section_index()];
1326 best = best.min(match perm.order_pattern(pattern)[0] {
1329 Some(_) if index.cluster_runs(perm.section_index()).is_some() => {
1331 index.clustered_subject_bytes(perm.section_index())
1332 }
1333 Some(id) => tiles.routed_bytes(id),
1334 None => tiles.total_bytes(),
1335 });
1336 }
1337 best
1338}
1339
1340pub(crate) const FAT_SCAN_ROWS: f64 = (1u64 << 20) as f64;
1353
1354fn merge_seed_lopsided(
1359 ctx: &Ctx,
1360 index: &GraphIndex,
1361 ta: &(SlotTerm, SlotTerm, SlotTerm),
1362 tb: &(SlotTerm, SlotTerm, SlotTerm),
1363) -> bool {
1364 let est = tile_estimates(ctx, index, &[*ta, *tb], &std::collections::HashSet::new());
1365 let (lo, hi) = (est[0].min(est[1]), est[0].max(est[1]));
1366 hi >= FAT_SCAN_ROWS && hi / 4.0 >= lo
1367}
1368
1369fn selectivity_order(
1376 ctx: &Ctx,
1377 index: &GraphIndex,
1378 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1379) -> Vec<usize> {
1380 selectivity_order_seeded(ctx, index, lowered, &std::collections::HashSet::new())
1381}
1382
1383fn selectivity_order_seeded(
1387 ctx: &Ctx,
1388 index: &GraphIndex,
1389 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1390 seed: &std::collections::HashSet<usize>,
1391) -> Vec<usize> {
1392 let (estimates, per_class) = match pattern_estimates(ctx, index, lowered, seed) {
1400 Some(e) => (Some(e), false),
1401 None => (Some(tile_estimates(ctx, index, lowered, seed)), true),
1402 };
1403 let consts = |t: &(SlotTerm, SlotTerm, SlotTerm)| {
1404 [&t.0, &t.1, &t.2]
1405 .into_iter()
1406 .filter(|x| match x {
1407 SlotTerm::Var(v) => seed.contains(v),
1408 _ => true,
1409 })
1410 .count()
1411 };
1412 let vars = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Vec<usize> {
1413 [&t.0, &t.1, &t.2]
1414 .into_iter()
1415 .filter_map(|x| match x {
1416 SlotTerm::Var(v) => Some(*v),
1417 _ => None,
1418 })
1419 .collect()
1420 };
1421 let score = |i: usize| -> f64 {
1425 match &estimates {
1426 Some(e) => -e[i],
1427 None => consts(&lowered[i]) as f64,
1428 }
1429 };
1430 let type_pid = ctx.rete.dictionary().predicate_id(crate::file::RDF_TYPE);
1438 let is_class_enum = |i: usize, bound: &std::collections::HashSet<usize>| -> bool {
1439 let t = &lowered[i];
1440 !per_class
1441 && type_pid.is_some_and(|tp| matches!(t.1, SlotTerm::Pred(p) if p == tp))
1442 && matches!(t.2, SlotTerm::Node(_))
1443 && matches!(t.0, SlotTerm::Var(v) if !bound.contains(&v))
1444 };
1445 let n = lowered.len();
1446 let mut remaining: Vec<usize> = (0..n).collect();
1447 let mut order: Vec<usize> = Vec::with_capacity(n);
1448 let mut bound: std::collections::HashSet<usize> = seed.clone();
1449 while !remaining.is_empty() {
1450 let best = *remaining
1453 .iter()
1454 .max_by(|&&a, &&b| {
1455 let connected = |i: usize| vars(&lowered[i]).iter().any(|v| bound.contains(v));
1456 connected(a)
1457 .cmp(&connected(b))
1458 .then_with(|| is_class_enum(b, &bound).cmp(&is_class_enum(a, &bound)))
1459 .then_with(|| {
1460 score(a)
1461 .partial_cmp(&score(b))
1462 .unwrap_or(std::cmp::Ordering::Equal)
1463 })
1464 .then_with(|| b.cmp(&a))
1465 })
1466 .unwrap();
1467 for v in vars(&lowered[best]) {
1468 bound.insert(v);
1469 }
1470 order.push(best);
1471 remaining.retain(|&i| i != best);
1472 }
1473 order
1474}
1475
1476pub(crate) fn bgp_exists(ctx: &Ctx, index: &GraphIndex, patterns: &[TriplePattern]) -> bool {
1482 let dict = ctx.rete.dictionary();
1483 let Some(lowered) = lower(patterns, ctx) else {
1484 return false;
1485 };
1486 if let [t] = lowered.as_slice() {
1487 let names: Vec<usize> = [&t.0, &t.1, &t.2]
1491 .into_iter()
1492 .filter_map(|x| match x {
1493 SlotTerm::Var(v) => Some(*v),
1494 _ => None,
1495 })
1496 .collect();
1497 let distinct = names
1498 .iter()
1499 .enumerate()
1500 .all(|(i, v)| !names[i + 1..].contains(v));
1501 if distinct {
1502 return match (
1503 const_subject(&t.0, dict),
1504 const_predicate(&t.1),
1505 const_object(&t.2, dict),
1506 ) {
1507 (Some(s), Some(p), Some(o)) => index.scan_iter((s, p, o)).next().is_some(),
1508 _ => false,
1509 };
1510 }
1511 }
1512 !eval_bgp_rows(ctx, index, patterns).is_empty()
1513}
1514
1515pub(crate) struct BgpSolutions<'q> {
1526 scan: Option<Box<dyn Iterator<Item = Row> + 'q>>,
1527 prefix: Vec<Row>,
1528 buckets: HashMap<Vec<Val>, Vec<usize>>,
1530 shared: Vec<usize>,
1531 cartesian: bool,
1532 seed_only: bool,
1535 cur_scan: Option<Row>,
1536 matches: Vec<usize>,
1538 mi: usize,
1539}
1540
1541impl<'q> BgpSolutions<'q> {
1542 fn passthrough(rows: Box<dyn Iterator<Item = Row> + 'q>) -> Self {
1544 BgpSolutions {
1545 scan: Some(rows),
1546 prefix: Vec::new(),
1547 buckets: HashMap::new(),
1548 shared: Vec::new(),
1549 cartesian: false,
1550 seed_only: true,
1551 cur_scan: None,
1552 matches: Vec::new(),
1553 mi: 0,
1554 }
1555 }
1556
1557 fn streaming(
1566 ctx: &'q Ctx<'q>,
1567 index: &'q GraphIndex,
1568 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1569 order: &[usize],
1570 est: &[f64],
1571 ) -> Self {
1572 let (mut stream, mut bound, skip): (Box<dyn Iterator<Item = Row> + 'q>, Vec<usize>, usize) =
1573 match (est[order[1]] > limits().stream_seed)
1574 .then(|| merge_stream(ctx, index, lowered[order[0]], lowered[order[1]]))
1575 .flatten()
1576 {
1577 Some((m, slots)) => (m, slots, 2),
1578 None => {
1579 let t = lowered[order[0]];
1580 let Some(scan) = scan_rows(ctx, index, t) else {
1581 return Self::empty();
1582 };
1583 (Box::new(scan), pattern_slots(&t), 1)
1584 }
1585 };
1586 for &i in &order[skip..] {
1587 let t = lowered[i];
1588 let slots = pattern_slots(&t);
1589 let shared: Vec<usize> = slots
1590 .iter()
1591 .copied()
1592 .filter(|s| bound.contains(s))
1593 .collect();
1594 if !shared.is_empty() && est[i] > limits().hash_build {
1595 stream = Box::new(
1599 windowed(index, stream, bgp_probe_pattern(ctx, t))
1600 .flat_map(move |base| probe_rows(ctx, index, t, base)),
1601 );
1602 } else {
1603 let Some((rel, _)) = pattern_rows(ctx, index, &t) else {
1606 return Self::empty();
1607 };
1608 let mut table: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
1609 for r in rel {
1610 let key: Vec<Val> = shared.iter().map(|&s| r[s].clone().unwrap()).collect();
1611 table.entry(key).or_default().push(r);
1612 }
1613 let fill = slots.clone();
1614 stream = Box::new(stream.flat_map(move |base| {
1615 let key: Vec<Val> = shared.iter().map(|&s| base[s].clone().unwrap()).collect();
1616 let out: Vec<Row> = table
1617 .get(&key)
1618 .map(|rs| {
1619 rs.iter()
1620 .map(|r| {
1621 let mut row = base.clone();
1622 for &s in &fill {
1623 row[s] = r[s].clone();
1624 }
1625 row
1626 })
1627 .collect()
1628 })
1629 .unwrap_or_default();
1630 out.into_iter()
1631 }));
1632 }
1633 for s in slots {
1634 if !bound.contains(&s) {
1635 bound.push(s);
1636 }
1637 }
1638 }
1639 Self::passthrough(stream)
1640 }
1641
1642 fn empty() -> Self {
1644 BgpSolutions {
1645 scan: None,
1646 prefix: Vec::new(),
1647 buckets: HashMap::new(),
1648 shared: Vec::new(),
1649 cartesian: false,
1650 seed_only: false,
1651 cur_scan: None,
1652 matches: Vec::new(),
1653 mi: 0,
1654 }
1655 }
1656
1657 pub(crate) fn new(ctx: &'q Ctx<'q>, index: &'q GraphIndex, patterns: &[TriplePattern]) -> Self {
1658 if patterns.is_empty() {
1660 return BgpSolutions {
1661 scan: Some(Box::new(std::iter::once(ctx.slots.empty_row()))),
1662 prefix: vec![ctx.slots.empty_row()],
1663 buckets: HashMap::new(),
1664 shared: Vec::new(),
1665 cartesian: true,
1666 seed_only: true,
1667 cur_scan: None,
1668 matches: Vec::new(),
1669 mi: 0,
1670 };
1671 }
1672 let Some(lowered) = lower(patterns, ctx) else {
1674 return Self::empty();
1675 };
1676 let (order, scan_est) = plan_order(ctx, index, &lowered);
1679 if order.len() >= 2 && scan_est[order[0]] > limits().stream_seed {
1682 return Self::streaming(ctx, index, &lowered, &order, &scan_est);
1683 }
1684 let (&last_i, prefix_is) = order.split_last().unwrap();
1685 let prefix_pats: Vec<TriplePattern> =
1686 prefix_is.iter().map(|&i| patterns[i].clone()).collect();
1687 let prefix = eval_bgp_rows(ctx, index, &prefix_pats);
1688 if prefix.is_empty() {
1689 return Self::empty();
1690 }
1691
1692 let shared: Vec<usize> = pattern_slots(&lowered[last_i])
1696 .into_iter()
1697 .filter(|&s| prefix[0][s].is_some())
1698 .collect();
1699
1700 let class_probe = !shared.is_empty()
1709 && scan_est[last_i] >= limits().probe_floor
1710 && (prefix.len() as f64) <= scan_est[last_i]
1711 && is_unbound_class(ctx, &lowered[last_i], &shared);
1712 if !shared.is_empty() && (probe_beats_scan(prefix.len(), scan_est[last_i]) || class_probe) {
1713 let t = lowered[last_i];
1714 let stream = windowed(index, prefix.into_iter(), bgp_probe_pattern(ctx, t))
1715 .flat_map(move |base| probe_rows(ctx, index, t, base));
1716 return Self::passthrough(Box::new(stream));
1717 }
1718
1719 let Some(scan) = scan_rows(ctx, index, lowered[last_i]) else {
1721 return Self::empty();
1722 };
1723 let cartesian = shared.is_empty();
1724 let seed_only = prefix.len() == 1 && prefix[0].iter().all(Option::is_none);
1727 let mut buckets: HashMap<Vec<Val>, Vec<usize>> = HashMap::new();
1728 if !cartesian {
1729 for (i, r) in prefix.iter().enumerate() {
1730 let key: Vec<Val> = shared.iter().map(|&s| r[s].clone().unwrap()).collect();
1731 buckets.entry(key).or_default().push(i);
1732 }
1733 }
1734 BgpSolutions {
1735 scan: Some(Box::new(scan)),
1736 prefix,
1737 buckets,
1738 shared,
1739 cartesian,
1740 seed_only,
1741 cur_scan: None,
1742 matches: Vec::new(),
1743 mi: 0,
1744 }
1745 }
1746}
1747
1748impl Iterator for BgpSolutions<'_> {
1749 type Item = Row;
1750
1751 fn next(&mut self) -> Option<Row> {
1752 if self.seed_only {
1754 return self.scan.as_mut()?.next();
1755 }
1756 loop {
1757 if self.mi < self.matches.len() {
1759 let pi = self.matches[self.mi];
1760 self.mi += 1;
1761 let mut merged = self.prefix[pi].clone();
1762 for (slot, v) in self.cur_scan.as_ref().unwrap().iter().enumerate() {
1763 if v.is_some() {
1764 merged[slot] = v.clone();
1765 }
1766 }
1767 return Some(merged);
1768 }
1769 let s = self.scan.as_mut()?.next()?;
1772 self.matches.clear();
1773 if self.cartesian {
1774 self.matches.extend(0..self.prefix.len());
1775 } else {
1776 let key: Vec<Val> = self.shared.iter().map(|&i| s[i].clone().unwrap()).collect();
1777 if let Some(c) = self.buckets.get(&key) {
1778 self.matches.extend_from_slice(c);
1779 }
1780 }
1781 self.mi = 0;
1782 self.cur_scan = Some(s);
1783 }
1784 }
1785}
1786
1787#[allow(clippy::type_complexity)]
1795fn merge_stream<'q>(
1796 ctx: &'q Ctx<'q>,
1797 index: &'q GraphIndex,
1798 ta: (SlotTerm, SlotTerm, SlotTerm),
1799 tb: (SlotTerm, SlotTerm, SlotTerm),
1800) -> Option<(Box<dyn Iterator<Item = Row> + 'q>, Vec<usize>)> {
1801 let sa = pattern_slots(&ta);
1802 let sb = pattern_slots(&tb);
1803 let shared: Vec<usize> = sa.iter().copied().filter(|s| sb.contains(s)).collect();
1804 let [v] = shared[..] else {
1805 return None;
1806 };
1807 if !matches!(ta.0, SlotTerm::Var(i) if i == v) || !matches!(tb.0, SlotTerm::Var(i) if i == v) {
1808 return None;
1809 }
1810 let dict = ctx.rete.dictionary();
1811 let lower = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Option<Pattern> {
1812 Some((
1813 const_subject(&t.0, dict)?,
1814 const_predicate(&t.1)?,
1815 const_object(&t.2, dict)?,
1816 ))
1817 };
1818 let side = |t: (SlotTerm, SlotTerm, SlotTerm)| -> Option<KeyedRows<'q>> {
1819 let it = index.scan_iter_sorted_on(lower(&t)?, 0)?;
1820 let keyed: Box<dyn Iterator<Item = (u32, Row)> + 'q> =
1821 Box::new(it.filter_map(move |tri| triple_row(ctx, &t, tri).map(|r| (tri.0, r))));
1822 Some(keyed.peekable())
1823 };
1824 let a = side(ta)?;
1825 let b = side(tb)?;
1826 let mut slots = sa;
1827 for s in sb {
1828 if !slots.contains(&s) {
1829 slots.push(s);
1830 }
1831 }
1832 Some((
1833 Box::new(MergeStream {
1834 a,
1835 b,
1836 ra: Vec::new(),
1837 rb: Vec::new(),
1838 i: 0,
1839 j: 0,
1840 }),
1841 slots,
1842 ))
1843}
1844
1845type KeyedRows<'q> = std::iter::Peekable<Box<dyn Iterator<Item = (u32, Row)> + 'q>>;
1846
1847struct MergeStream<'q> {
1850 a: KeyedRows<'q>,
1851 b: KeyedRows<'q>,
1852 ra: Vec<Row>,
1853 rb: Vec<Row>,
1854 i: usize,
1855 j: usize,
1856}
1857
1858impl Iterator for MergeStream<'_> {
1859 type Item = Row;
1860
1861 fn next(&mut self) -> Option<Row> {
1862 loop {
1863 while self.i < self.ra.len() {
1864 if self.j < self.rb.len() {
1865 let j = self.j;
1866 self.j += 1;
1867 if let Some(m) = crate::row::merge_rows(&self.ra[self.i], &self.rb[j]) {
1868 return Some(m);
1869 }
1870 } else {
1871 self.i += 1;
1872 self.j = 0;
1873 }
1874 }
1875 let ka = self.a.peek()?.0;
1876 let kb = self.b.peek()?.0;
1877 match ka.cmp(&kb) {
1878 std::cmp::Ordering::Less => {
1879 self.a.next();
1880 }
1881 std::cmp::Ordering::Greater => {
1882 self.b.next();
1883 }
1884 std::cmp::Ordering::Equal => {
1885 self.ra.clear();
1886 self.rb.clear();
1887 while let Some((_, r)) = self.a.next_if(|(k, _)| *k == ka) {
1888 self.ra.push(r);
1889 }
1890 while let Some((_, r)) = self.b.next_if(|(k, _)| *k == ka) {
1891 self.rb.push(r);
1892 }
1893 self.i = 0;
1894 self.j = 0;
1895 }
1896 }
1897 }
1898 }
1899}
1900
1901fn probe_subject(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
1915 let dict = ctx.rete.dictionary();
1916 match t {
1917 SlotTerm::Node(n) => dict.node_as_subject_id(*n).map(Some),
1918 SlotTerm::Pred(_) => None,
1919 SlotTerm::Var(i) => match &base[*i] {
1920 None => Some(None),
1921 Some(Val::Id(v)) if *v >= 0 => dict.node_as_subject_id(*v as u32).map(Some),
1922 Some(_) => None,
1924 },
1925 }
1926}
1927
1928fn probe_object(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
1930 let dict = ctx.rete.dictionary();
1931 match t {
1932 SlotTerm::Node(n) => dict.node_as_object_id(*n).map(Some),
1933 SlotTerm::Pred(_) => None,
1934 SlotTerm::Var(i) => match &base[*i] {
1935 None => Some(None),
1936 Some(Val::Id(v)) if *v >= 0 => dict.node_as_object_id(*v as u32).map(Some),
1937 Some(_) => None,
1938 },
1939 }
1940}
1941
1942fn probe_predicate(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
1944 let dict = ctx.rete.dictionary();
1945 match t {
1946 SlotTerm::Pred(p) => Some(Some(*p)),
1947 SlotTerm::Node(_) => None,
1948 SlotTerm::Var(i) => match &base[*i] {
1949 None => Some(None),
1950 Some(Val::Id(v)) if *v < 0 => Some(Some((-v - 1) as u32)),
1951 Some(Val::Id(v)) => ctx
1953 .resolver
1954 .term(*v)
1955 .and_then(|t| dict.predicate_id(&t))
1956 .map(Some),
1957 Some(Val::Str(_)) => None,
1958 },
1959 }
1960}
1961
1962fn probe_rows<'q>(
1966 ctx: &'q Ctx<'q>,
1967 index: &'q GraphIndex,
1968 t: (SlotTerm, SlotTerm, SlotTerm),
1969 base: Row,
1970) -> Box<dyn Iterator<Item = Row> + 'q> {
1971 let (Some(sid), Some(pid), Some(oid)) = (
1972 probe_subject(ctx, &t.0, &base),
1973 probe_predicate(ctx, &t.1, &base),
1974 probe_object(ctx, &t.2, &base),
1975 ) else {
1976 return Box::new(std::iter::empty());
1977 };
1978 let dict = ctx.rete.dictionary();
1979 Box::new(
1982 canon_ahead(ctx, &t, index.scan_iter((sid, pid, oid))).filter_map(
1983 move |(s_id, p_id, o_id)| {
1984 let s_val = dict.subject_node(s_id) as i64;
1985 let p_val = pred_val(ctx, &t.1, p_id);
1986 let o_val = dict.object_node(o_id) as i64;
1987 let mut row = base.clone();
1988 for (term, val) in [(&t.0, s_val), (&t.1, p_val), (&t.2, o_val)] {
1989 if let SlotTerm::Var(i) = term {
1990 match row[*i] {
1991 Some(Val::Id(existing)) if existing != val => return None,
1992 Some(Val::Id(_)) => {}
1993 Some(Val::Str(_)) => return None,
1994 None => row[*i] = Some(Val::Id(val)),
1995 }
1996 }
1997 }
1998 Some(row)
1999 },
2000 ),
2001 )
2002}
2003
2004pub(crate) struct ProbePlan {
2006 pats: Vec<(SlotTerm, SlotTerm, SlotTerm)>,
2007}
2008
2009impl ProbePlan {
2010 pub(crate) fn new(
2014 ctx: &Ctx,
2015 index: &GraphIndex,
2016 patterns: &[TriplePattern],
2017 seed_mask: &[bool],
2018 ) -> Option<Self> {
2019 let lowered = lower(patterns, ctx)?;
2020 let seed: std::collections::HashSet<usize> = seed_mask
2021 .iter()
2022 .enumerate()
2023 .filter_map(|(i, b)| b.then_some(i))
2024 .collect();
2025 let order = selectivity_order_seeded(ctx, index, &lowered, &seed);
2026 Some(ProbePlan {
2027 pats: order.into_iter().map(|i| lowered[i]).collect(),
2028 })
2029 }
2030}
2031
2032pub(crate) struct ProbeJoin<'q> {
2035 ctx: &'q Ctx<'q>,
2036 index: &'q GraphIndex,
2037 pats: Vec<(SlotTerm, SlotTerm, SlotTerm)>,
2038 stack: Vec<Box<dyn Iterator<Item = Row> + 'q>>,
2039}
2040
2041impl<'q> ProbeJoin<'q> {
2042 pub(crate) fn new(
2045 ctx: &'q Ctx<'q>,
2046 index: &'q GraphIndex,
2047 patterns: &[TriplePattern],
2048 ) -> Option<Self> {
2049 let plan = ProbePlan::new(ctx, index, patterns, &vec![false; ctx.slots.len()])?;
2050 Some(Self::from_plan(ctx, index, &plan, ctx.slots.empty_row()))
2051 }
2052
2053 pub(crate) fn from_plan(
2055 ctx: &'q Ctx<'q>,
2056 index: &'q GraphIndex,
2057 plan: &ProbePlan,
2058 seed: Row,
2059 ) -> Self {
2060 let pats = plan.pats.clone();
2061 let first = probe_rows(ctx, index, pats[0], seed);
2062 ProbeJoin {
2063 ctx,
2064 index,
2065 pats,
2066 stack: vec![first],
2067 }
2068 }
2069}
2070
2071impl Iterator for ProbeJoin<'_> {
2072 type Item = Row;
2073
2074 fn next(&mut self) -> Option<Row> {
2075 loop {
2076 let depth = self.stack.len();
2077 match self.stack.last_mut()?.next() {
2078 Some(row) => {
2079 if depth == self.pats.len() {
2080 return Some(row);
2081 }
2082 let it = probe_rows(self.ctx, self.index, self.pats[depth], row);
2083 self.stack.push(it);
2084 }
2085 None => {
2086 self.stack.pop();
2087 if self.stack.is_empty() {
2088 return None;
2089 }
2090 }
2091 }
2092 }
2093 }
2094}
2095
2096fn hash_join(
2100 left: Vec<Row>,
2101 left_bound: &[usize],
2102 right: Vec<Row>,
2103 right_slots: &[usize],
2104) -> Vec<Row> {
2105 if left.len() == 1 && left_bound.is_empty() {
2107 return right;
2108 }
2109 if left.is_empty() || right.is_empty() {
2110 return Vec::new();
2111 }
2112 let shared: Vec<usize> = right_slots
2113 .iter()
2114 .copied()
2115 .filter(|s| left_bound.contains(s))
2116 .collect();
2117 let fill = |l: &Row, r: &Row| -> Row {
2118 let mut out = l.clone();
2119 for &s in right_slots {
2120 out[s] = r[s].clone();
2121 }
2122 out
2123 };
2124 if shared.is_empty() {
2125 let mut out = Vec::with_capacity(left.len() * right.len());
2129 for l in &left {
2130 for r in &right {
2131 out.push(fill(l, r));
2132 }
2133 }
2134 return out;
2135 }
2136 let key_of = |b: &Row| -> Vec<Val> { shared.iter().map(|&s| b[s].clone().unwrap()).collect() };
2137 let mut out = Vec::new();
2144 if right.len() <= left.len() {
2145 let mut buckets: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
2146 for r in right {
2147 buckets.entry(key_of(&r)).or_default().push(r);
2148 }
2149 for l in &left {
2150 if let Some(rs) = buckets.get(&key_of(l)) {
2151 for r in rs {
2152 out.push(fill(l, r));
2153 }
2154 }
2155 }
2156 } else {
2157 let mut buckets: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
2159 for l in left {
2160 buckets.entry(key_of(&l)).or_default().push(l);
2161 }
2162 for r in &right {
2163 if let Some(ls) = buckets.get(&key_of(r)) {
2164 for l in ls {
2165 let mut row = r.clone();
2166 for &s in left_bound {
2167 if let Some(v) = &l[s] {
2168 row[s] = Some(v.clone());
2169 }
2170 }
2171 out.push(row);
2172 }
2173 }
2174 }
2175 }
2176 out
2177}
2178
2179fn const_subject(t: &SlotTerm, d: &crate::Dictionary) -> Option<Option<u32>> {
2184 match t {
2185 SlotTerm::Node(n) => d.node_as_subject_id(*n).map(Some),
2186 SlotTerm::Pred(_) => None, SlotTerm::Var(_) => Some(None),
2188 }
2189}
2190
2191fn const_object(t: &SlotTerm, d: &crate::Dictionary) -> Option<Option<u32>> {
2192 match t {
2193 SlotTerm::Node(n) => d.node_as_object_id(*n).map(Some),
2194 SlotTerm::Pred(_) => None,
2195 SlotTerm::Var(_) => Some(None),
2196 }
2197}
2198
2199fn const_predicate(t: &SlotTerm) -> Option<Option<u32>> {
2200 match t {
2201 SlotTerm::Pred(p) => Some(Some(*p)),
2202 SlotTerm::Node(_) => None, SlotTerm::Var(_) => Some(None),
2204 }
2205}
2206
2207#[cfg(test)]
2208mod tests {
2209 use super::*;
2210 use crate::dictionary::DictionaryBuilder;
2211 use crate::file::write_file_v05 as write_file;
2212 use crate::index::GraphIndexBuilder;
2213
2214 fn rete_from(triples: &[(&str, &str, &str)]) -> Vec<u8> {
2215 let mut db = DictionaryBuilder::new();
2216 for (s, p, o) in triples {
2217 db.observe(s, p, o);
2218 }
2219 let dict = db.build();
2220 let mut ib = GraphIndexBuilder::new();
2221 for (s, p, o) in triples {
2222 ib.push(dict.encode(s, p, o).unwrap());
2223 }
2224 write_file(&dict, &ib.build(), false, &[], 0)
2225 }
2226
2227 fn pat(s: &str, p: &str, o: &str) -> TriplePattern {
2228 TriplePattern {
2229 s: PatternTerm::parse(s),
2230 p: PatternTerm::parse(p),
2231 o: PatternTerm::parse(o),
2232 }
2233 }
2234
2235 #[test]
2244 fn scan_bytes_route_a_literal_by_its_object_id() {
2245 let value = "<http://ex/value>";
2246 let owned: Vec<(String, String)> = (0..400)
2247 .map(|i| (format!("<http://ex/s{i:03}>"), format!("\"lit {i:03}\"")))
2248 .collect();
2249 let mut db = DictionaryBuilder::new();
2250 for (s, o) in &owned {
2251 db.observe(s, value, o);
2252 }
2253 let dict = db.build();
2254 let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2255 for (s, o) in &owned {
2256 ib.push(dict.encode(s, value, o).unwrap());
2257 }
2258 let rete = Rete::open(&write_file(&dict, &ib.build(), false, &[], 0)).unwrap();
2259 let index = rete.default_index();
2260 let whole = routed_scan_bytes(index, (None, rete.dictionary().predicate_id(value), None));
2262 for (_, lit) in owned.iter().step_by(57) {
2263 let q = [pat("?s", value, lit)];
2264 let mut slots = Slots::new();
2265 collect_pattern_slots(&q, &mut slots);
2266 let ctx = Ctx::new(&rete, slots);
2267 let got = bgp_min_scan_bytes(&ctx, index, &q).unwrap();
2268 assert!(got > 0, "{lit} routed to no tile");
2269 assert!(
2270 got < whole,
2271 "{lit} routed to the whole predicate ({got} of {whole})"
2272 );
2273 }
2274 }
2275
2276 #[test]
2282 fn plan_gates_do_not_move_with_the_compression() {
2283 let mut owned: Vec<(String, String, String)> = Vec::new();
2284 for i in 0..3000 {
2285 let s = format!("<http://ex/s{i}>");
2286 owned.push((
2287 s.clone(),
2288 "<http://ex/kind>".into(),
2289 format!("<http://ex/K{}>", i % 7),
2290 ));
2291 owned.push((s.clone(), "<http://ex/value>".into(), format!("\"v {i}\"")));
2292 if i % 50 == 0 {
2293 owned.push((s, "<http://ex/rare>".into(), "<http://ex/R>".into()));
2294 }
2295 }
2296 let mut db = DictionaryBuilder::new();
2297 for (s, p, o) in &owned {
2298 db.observe(s, p, o);
2299 }
2300 let dict = db.build();
2301 let mut ib = GraphIndexBuilder::new().with_tile_budget(1024);
2302 for (s, p, o) in &owned {
2303 ib.push(dict.encode(s, p, o).unwrap());
2304 }
2305 let bytes = write_file(&dict, &ib.build(), false, &[], 0);
2306 let leaked: &'static [u8] = Box::leak(bytes.clone().into_boxed_slice());
2307 let resident = Rete::open(&bytes).unwrap();
2308 let lazy = Rete::open_ranged_lazy(crate::reader::SliceReader::new(leaked)).unwrap();
2309 let shapes: Vec<Vec<TriplePattern>> = vec![
2310 vec![
2311 pat("?s", "<http://ex/rare>", "<http://ex/R>"),
2312 pat("?s", "<http://ex/value>", "?v"),
2313 ],
2314 vec![
2315 pat("?s", "<http://ex/kind>", "<http://ex/K3>"),
2316 pat("?s", "<http://ex/value>", "?v"),
2317 ],
2318 vec![
2319 pat("?s", "<http://ex/kind>", "?k"),
2320 pat("?s", "<http://ex/value>", "?v"),
2321 ],
2322 vec![
2323 pat("?s", "<http://ex/value>", "\"v 7\""),
2324 pat("?s", "<http://ex/kind>", "?k"),
2325 ],
2326 ];
2327 let decisions = |rete: &Rete| -> Vec<(Vec<u64>, bool, Option<u64>)> {
2328 shapes
2329 .iter()
2330 .map(|q| {
2331 let mut slots = Slots::new();
2332 collect_pattern_slots(q, &mut slots);
2333 let ctx = Ctx::new(rete, slots);
2334 let index = rete.default_index();
2335 let lowered = lower(q, &ctx).unwrap();
2336 let est = tile_estimates(&ctx, index, &lowered, &Default::default());
2337 let lopsided = merge_seed_lopsided(&ctx, index, &lowered[0], &lowered[1]);
2338 let min = bgp_min_estimate(&ctx, index, q).map(|e| e as u64);
2339 (est.iter().map(|e| *e as u64).collect(), lopsided, min)
2340 })
2341 .collect()
2342 };
2343 assert_eq!(decisions(&resident), decisions(&lazy));
2344 #[cfg(feature = "compression")]
2346 {
2347 let bytes_of = |rete: &Rete| {
2348 let q = &shapes[2];
2349 let mut slots = Slots::new();
2350 collect_pattern_slots(q, &mut slots);
2351 let ctx = Ctx::new(rete, slots);
2352 bgp_min_scan_bytes(&ctx, rete.default_index(), q)
2353 };
2354 assert_ne!(bytes_of(&resident), bytes_of(&lazy));
2355 }
2356 }
2357
2358 #[test]
2368 fn a_fat_predicate_estimates_alike_in_both_layouts() {
2369 let mut owned: Vec<(String, String, String)> = Vec::new();
2370 for i in 0..120_000 {
2371 let s = format!("<http://ex/s{i:06}>");
2372 owned.push((s.clone(), "<http://ex/kind>".into(), "<http://ex/K>".into()));
2373 owned.push((s, "<http://ex/value>".into(), format!("\"v {i}\"")));
2374 }
2375 let mut db = DictionaryBuilder::new();
2376 for (s, p, o) in &owned {
2377 db.observe(s, p, o);
2378 }
2379 let dict = db.build();
2380 let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2381 for (s, p, o) in &owned {
2382 ib.push(dict.encode(s, p, o).unwrap());
2383 }
2384 let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2385 let v6: &'static [u8] = Box::leak(
2386 crate::v06::write::convert_image(&v5, Default::default())
2387 .unwrap()
2388 .into_boxed_slice(),
2389 );
2390 let leaked5: &'static [u8] = Box::leak(v5.clone().into_boxed_slice());
2391 let flat = Rete::open_ranged_lazy(crate::reader::SliceReader::new(leaked5)).unwrap();
2392 let leafed = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v6)).unwrap();
2393 let q = [pat("?s", "<http://ex/value>", "?v")];
2394 let figures = |rete: &Rete| {
2395 let mut slots = Slots::new();
2396 collect_pattern_slots(&q, &mut slots);
2397 let ctx = Ctx::new(rete, slots);
2398 let index = rete.default_index();
2399 let total = bgp_total_estimate(&ctx, index, &q).unwrap();
2400 (total, probe_row_budget(total))
2401 };
2402 let (est5, budget5) = figures(&flat);
2403 let (est6, budget6) = figures(&leafed);
2404 assert!(est5 >= 70_000.0, "flat estimate {est5}");
2405 assert!(
2406 est6 >= est5 / 2.0 && est6 <= est5 * 2.0,
2407 "0x06 estimates {est6} where 0x05 estimates {est5}"
2408 );
2409 assert!(budget5.is_some_and(|b| b >= 1000), "{budget5:?}");
2411 assert!(budget6.is_some_and(|b| b >= 1000), "{budget6:?}");
2412 }
2413
2414 #[test]
2421 fn a_rare_object_of_a_fat_predicate_estimates_small_in_both_layouts() {
2422 let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2423 let mut owned: Vec<(String, String, String)> = Vec::new();
2424 for i in 0..120_000 {
2425 let s = format!("<http://ex/s{i:06}>");
2426 owned.push((s.clone(), ty.into(), "<http://ex/Common>".into()));
2427 owned.push((s.clone(), "<http://ex/other>".into(), format!("\"o {i}\"")));
2428 if i % 3000 == 0 {
2429 owned.push((s, ty.into(), "<http://ex/Rare>".into()));
2430 }
2431 }
2432 let mut db = DictionaryBuilder::new();
2433 for (s, p, o) in &owned {
2434 db.observe(s, p, o);
2435 }
2436 let dict = db.build();
2437 let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2438 for (s, p, o) in &owned {
2439 ib.push(dict.encode(s, p, o).unwrap());
2440 }
2441 let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2442 let v6: &'static [u8] = Box::leak(
2443 crate::v06::write::convert_image(&v5, Default::default())
2444 .unwrap()
2445 .into_boxed_slice(),
2446 );
2447 let leaked5: &'static [u8] = Box::leak(v5.into_boxed_slice());
2448 let figures = |rete: &Rete| {
2449 let est = |q: &[TriplePattern]| {
2450 let mut slots = Slots::new();
2451 collect_pattern_slots(q, &mut slots);
2452 let ctx = Ctx::new(rete, slots);
2453 bgp_min_estimate(&ctx, rete.default_index(), q).unwrap()
2454 };
2455 (
2456 est(&[pat("?s", ty, "<http://ex/Rare>")]),
2457 est(&[pat("?s", ty, "<http://ex/Common>")]),
2458 est(&[pat("?s", "<http://ex/other>", "?x")]),
2459 )
2460 };
2461 for (name, bytes) in [("0x05", leaked5), ("0x06", v6)] {
2462 let rete = Rete::open_ranged_lazy(crate::reader::SliceReader::new(bytes)).unwrap();
2463 let (rare, common, other) = figures(&rete);
2464 assert!(rare * 20.0 < other, "{name}: rare {rare} vs other {other}");
2465 assert!(
2466 rare * 20.0 < common,
2467 "{name}: rare {rare} vs common {common}"
2468 );
2469 }
2470 }
2471
2472 #[test]
2479 fn a_probe_prefetch_window_is_bounded_and_warm() {
2480 use crate::reader::{CountingReader, SliceReader};
2481 let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2482 let mut owned: Vec<(String, String, String)> = Vec::new();
2483 for i in 0..20_000 {
2484 let s = format!("<http://ex/s{i:06}>");
2485 owned.push((s.clone(), ty.into(), format!("<http://ex/C{}>", i % 7)));
2486 owned.push((s, "<http://ex/other>".into(), format!("\"o {}\"", i % 5000)));
2487 }
2488 let mut db = DictionaryBuilder::new();
2489 for (s, p, o) in &owned {
2490 db.observe(s, p, o);
2491 }
2492 let dict = db.build();
2493 let mut ib = GraphIndexBuilder::new().with_tile_budget(128);
2494 for (s, p, o) in &owned {
2495 ib.push(dict.encode(s, p, o).unwrap());
2496 }
2497 let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2498 let v6 = crate::v06::write::convert_image(&v5, Default::default()).unwrap();
2499 let leaked: &'static [u8] = Box::leak(v6.into_boxed_slice());
2500 let reader = std::sync::Arc::new(CountingReader::new(SliceReader::new(leaked)));
2501 let rete = Rete::open_ranged_lazy(reader.clone()).unwrap();
2502 let index = rete.default_index();
2503 index.set_cache_cap(1 << 20);
2506 let pats: Vec<Pattern> = (0..20_000)
2508 .step_by(3)
2509 .map(|i| {
2510 let (s, _, _) = dict
2511 .encode(&format!("<http://ex/s{i:06}>"), ty, "<http://ex/C0>")
2512 .unwrap();
2513 (Some(s), None, None)
2514 })
2515 .collect();
2516 let mut from = 0;
2517 let mut windows = 0;
2518 while from < pats.len() {
2519 let n = index.prefetch_probe_tiles(&pats[from..]);
2520 assert!(n >= 1, "a window always makes progress");
2521 assert!(
2522 n < pats.len() - from || windows > 0,
2523 "the first window is cut"
2524 );
2525 let before = reader.requests();
2526 for &p in &pats[from..from + n] {
2527 assert!(index.scan_iter(p).next().is_some());
2528 }
2529 assert_eq!(reader.requests(), before, "a covered probe reads nothing");
2530 from += n;
2531 windows += 1;
2532 }
2533 assert!(windows > 1, "{windows} window(s) for {} probes", pats.len());
2534 }
2535
2536 #[test]
2541 fn a_tile_span_is_the_same_in_both_layouts() {
2542 let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2543 let mut owned: Vec<(String, String, String)> = Vec::new();
2544 for i in 0..30_000 {
2545 let s = format!("<http://ex/s{i:06}>");
2546 owned.push((s.clone(), ty.into(), format!("<http://ex/C{}>", i % 7)));
2547 owned.push((s, "<http://ex/other>".into(), format!("\"o {}\"", i % 5000)));
2548 }
2549 let mut db = DictionaryBuilder::new();
2550 for (s, p, o) in &owned {
2551 db.observe(s, p, o);
2552 }
2553 let dict = db.build();
2554 let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2555 for (s, p, o) in &owned {
2556 ib.push(dict.encode(s, p, o).unwrap());
2557 }
2558 let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2559 let v6 = crate::v06::write::convert_image(&v5, Default::default()).unwrap();
2560 let (v5, v6): (&'static [u8], &'static [u8]) = (
2561 Box::leak(v5.into_boxed_slice()),
2562 Box::leak(v6.into_boxed_slice()),
2563 );
2564 let flat = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v5)).unwrap();
2565 let leafed = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v6)).unwrap();
2566 let (fi, li) = (flat.default_index(), leafed.default_index());
2567 let mut checked = 0;
2568 for perm in fi.perms().iter() {
2569 let si = perm.section_index();
2570 for a in (0..dict.term_count() + 2).step_by(97) {
2571 assert_eq!(
2572 fi.tile_span(si, Some(a)),
2573 li.tile_span(si, Some(a)),
2574 "section {si}, id {a}"
2575 );
2576 checked += 1;
2577 }
2578 assert_eq!(fi.tile_span(si, None), li.tile_span(si, None));
2579 }
2580 assert!(checked > 100);
2581 }
2582
2583 #[test]
2588 fn every_join_path_returns_the_same_solutions() {
2589 let mut owned: Vec<(String, String, String)> = Vec::new();
2590 let mut x: u64 = 7;
2591 let mut next = |m: u64| {
2592 x = x
2593 .wrapping_mul(6364136223846793005)
2594 .wrapping_add(1442695040888963407);
2595 (x >> 33) % m
2596 };
2597 for i in 0..60 {
2598 let s = format!("s{i}");
2599 owned.push((s.clone(), "a".into(), format!("C{}", next(3))));
2600 for p in 0..4 {
2601 for _ in 0..next(3) {
2602 owned.push((s.clone(), format!("p{p}"), format!("s{}", next(60))));
2603 }
2604 }
2605 }
2606 let triples: Vec<(&str, &str, &str)> = owned
2607 .iter()
2608 .map(|(s, p, o)| (s.as_str(), p.as_str(), o.as_str()))
2609 .collect();
2610 let bytes = rete_from(&triples);
2611 let rete = Rete::open(&bytes).unwrap();
2612 let queries: Vec<Vec<TriplePattern>> = vec![
2613 vec![pat("?s", "p0", "?a"), pat("?s", "p1", "?b")],
2614 vec![pat("?s", "a", "C1"), pat("?s", "p0", "?a")],
2615 vec![pat("?s", "p0", "?a"), pat("?a", "p2", "?b")],
2616 vec![pat("s5", "p0", "?a"), pat("?a", "?p", "?o")],
2617 vec![pat("?s", "p0", "?x"), pat("?s", "p1", "?x")],
2618 vec![
2619 pat("?s", "p3", "?o"),
2620 pat("?o", "a", "C0"),
2621 pat("?s", "p1", "?z"),
2622 ],
2623 vec![
2624 pat("?s", "p0", "?a"),
2625 pat("?s", "p1", "?b"),
2626 pat("?b", "p2", "?c"),
2627 ],
2628 ];
2629 let run = |limits: Option<PlanLimits>| -> Vec<Vec<Vec<(String, String)>>> {
2630 TEST_LIMITS.with(|c| c.set(limits));
2631 let out = queries
2632 .iter()
2633 .map(|q| {
2634 let mut slots = crate::row::Slots::new();
2635 collect_pattern_slots(q, &mut slots);
2636 let ctx = Ctx::new(&rete, slots);
2637 let mut rows: Vec<Vec<(String, String)>> =
2638 BgpSolutions::new(&ctx, rete.default_index(), q)
2639 .map(|r| row_to_binding(&ctx, &r).into_iter().collect())
2640 .collect();
2641 rows.sort();
2642 rows
2643 })
2644 .collect();
2645 TEST_LIMITS.with(|c| c.set(None));
2646 out
2647 };
2648 let reference = run(None);
2649 assert!(reference.iter().all(|r| !r.is_empty()), "{reference:?}");
2650 for (name, l) in [
2651 (
2652 "probe everything",
2653 PlanLimits {
2654 probe_floor: 0.0,
2655 stream_seed: f64::MAX,
2656 hash_build: f64::MAX,
2657 },
2658 ),
2659 (
2660 "stream + hash",
2661 PlanLimits {
2662 probe_floor: f64::MAX,
2663 stream_seed: 0.0,
2664 hash_build: f64::MAX,
2665 },
2666 ),
2667 (
2668 "stream + probe",
2669 PlanLimits {
2670 probe_floor: f64::MAX,
2671 stream_seed: 0.0,
2672 hash_build: 0.0,
2673 },
2674 ),
2675 (
2676 "stream, all paths",
2677 PlanLimits {
2678 probe_floor: 0.0,
2679 stream_seed: 0.0,
2680 hash_build: 30.0,
2681 },
2682 ),
2683 ] {
2684 assert_eq!(run(Some(l)), reference, "{name}");
2685 }
2686 }
2687
2688 #[test]
2689 fn single_pattern_binds_variable() {
2690 let bytes = rete_from(&[("Alice", "knows", "Bob"), ("Bob", "knows", "Carol")]);
2691 let rete = Rete::open(&bytes).unwrap();
2692 let sols = eval_bgp(&rete, &[pat("Alice", "knows", "?y")]);
2693 assert_eq!(sols.len(), 1);
2694 assert_eq!(sols[0]["y"], "Bob");
2695 }
2696
2697 #[test]
2698 fn two_hop_join_on_shared_variable() {
2699 let bytes = rete_from(&[
2701 ("Alice", "knows", "Bob"),
2702 ("Bob", "knows", "Carol"),
2703 ("Carol", "knows", "Dave"),
2704 ("Alice", "knows", "Eve"), ]);
2706 let rete = Rete::open(&bytes).unwrap();
2707 let sols = eval_bgp(&rete, &[pat("?x", "knows", "?y"), pat("?y", "knows", "?z")]);
2708 let mut got: Vec<_> = sols
2710 .iter()
2711 .map(|b| (b["x"].clone(), b["y"].clone(), b["z"].clone()))
2712 .collect();
2713 got.sort();
2714 assert_eq!(
2715 got,
2716 vec![
2717 ("Alice".into(), "Bob".into(), "Carol".into()),
2718 ("Bob".into(), "Carol".into(), "Dave".into()),
2719 ]
2720 );
2721 }
2722
2723 #[test]
2724 fn repeated_variable_within_pattern() {
2725 let bytes = rete_from(&[("Alice", "knows", "Bob"), ("Bob", "knows", "Bob")]);
2727 let rete = Rete::open(&bytes).unwrap();
2728 let sols = eval_bgp(&rete, &[pat("?x", "knows", "?x")]);
2729 assert_eq!(sols.len(), 1);
2730 assert_eq!(sols[0]["x"], "Bob");
2731 }
2732
2733 #[test]
2734 fn no_solutions_yields_empty() {
2735 let bytes = rete_from(&[("Alice", "knows", "Bob")]);
2736 let rete = Rete::open(&bytes).unwrap();
2737 assert!(eval_bgp(&rete, &[pat("Alice", "likes", "?y")]).is_empty());
2738 }
2739
2740 #[test]
2747 fn snowflake_type_and_adjacency_matches_reference() {
2748 const TYPE: &str = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2749 let mut triples: Vec<(String, String, String)> = Vec::new();
2750 for i in 0..60 {
2752 let s = format!("S{i}");
2753 triples.push((s.clone(), TYPE.into(), "Student".into()));
2754 triples.push((s.clone(), "takesCourse".into(), format!("c{}", i % 5)));
2755 triples.push((s, "takesCourse".into(), format!("c{}", (i + 1) % 5)));
2756 }
2757 for j in 0..5 {
2759 triples.push((format!("c{j}"), TYPE.into(), "Course".into()));
2760 }
2761 triples.push(("Prof".into(), "teacherOf".into(), "c0".into()));
2762 triples.push(("Prof".into(), "teacherOf".into(), "c2".into()));
2763
2764 let refs: Vec<(&str, &str, &str)> = triples
2765 .iter()
2766 .map(|(s, p, o)| (s.as_str(), p.as_str(), o.as_str()))
2767 .collect();
2768 let bytes = rete_from(&refs);
2769 let rete = Rete::open(&bytes).unwrap();
2770
2771 let got: std::collections::BTreeSet<(String, String)> = eval_bgp(
2772 &rete,
2773 &[
2774 pat("?x", TYPE, "Student"),
2775 pat("?y", TYPE, "Course"),
2776 pat("?x", "takesCourse", "?y"),
2777 pat("Prof", "teacherOf", "?y"),
2778 ],
2779 )
2780 .into_iter()
2781 .map(|b| (b["x"].clone(), b["y"].clone()))
2782 .collect();
2783
2784 let taught = ["c0", "c2"];
2786 let mut want = std::collections::BTreeSet::new();
2787 for i in 0..60 {
2788 for c in [i % 5, (i + 1) % 5] {
2789 let course = format!("c{c}");
2790 if taught.contains(&course.as_str()) {
2791 want.insert((format!("S{i}"), course));
2792 }
2793 }
2794 }
2795 assert_eq!(got, want, "snowflake join must match the brute-force set");
2796 assert!(!want.is_empty(), "sanity: the reference set is non-empty");
2797 }
2798
2799 #[test]
2804 fn merge_join_subject_star_cross_product() {
2805 let bytes = rete_from(&[
2806 ("x", "a", "a1"),
2807 ("x", "a", "a2"),
2808 ("x", "b", "b1"),
2809 ("x", "b", "b2"),
2810 ("y", "a", "a3"),
2811 ("y", "b", "b3"),
2812 ("z", "a", "a4"), ]);
2814 let rete = Rete::open(&bytes).unwrap();
2815 let mut got: Vec<(String, String, String)> =
2816 eval_bgp(&rete, &[pat("?x", "a", "?av"), pat("?x", "b", "?bv")])
2817 .iter()
2818 .map(|m| (m["x"].clone(), m["av"].clone(), m["bv"].clone()))
2819 .collect();
2820 got.sort();
2821 let mut want: Vec<(String, String, String)> = [
2822 ("x", "a1", "b1"),
2823 ("x", "a1", "b2"),
2824 ("x", "a2", "b1"),
2825 ("x", "a2", "b2"),
2826 ("y", "a3", "b3"),
2827 ]
2828 .into_iter()
2829 .map(|(a, b, c)| (a.to_string(), b.to_string(), c.to_string()))
2830 .collect();
2831 want.sort();
2832 assert_eq!(got, want, "same-role merge must equal the brute-force join");
2833 }
2834}