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(all(test, feature = "http"))]
558pub(crate) fn with_plan_limits<T>(
559 probe_floor: f64,
560 stream_seed: f64,
561 hash_build: f64,
562 f: impl FnOnce() -> T,
563) -> T {
564 let saved = TEST_LIMITS.with(|c| c.get());
565 TEST_LIMITS.with(|c| {
566 c.set(Some(PlanLimits {
567 probe_floor,
568 stream_seed,
569 hash_build,
570 }))
571 });
572 let out = f();
573 TEST_LIMITS.with(|c| c.set(saved));
574 out
575}
576
577#[derive(Clone, Copy)]
580struct PlanLimits {
581 probe_floor: f64,
582 stream_seed: f64,
583 hash_build: f64,
584}
585
586#[cfg(test)]
587thread_local! {
588 static TEST_LIMITS: std::cell::Cell<Option<PlanLimits>> = const { std::cell::Cell::new(None) };
589}
590
591fn limits() -> PlanLimits {
592 #[cfg(test)]
593 if let Some(l) = TEST_LIMITS.with(|c| c.get()) {
594 return l;
595 }
596 PlanLimits {
597 probe_floor: PROBE_SCAN_FLOOR,
598 stream_seed: STREAM_SEED_ROWS,
599 hash_build: HASH_BUILD_ROWS,
600 }
601}
602
603const STREAM_SEED_ROWS: f64 = (1u64 << 21) as f64;
611
612const HASH_BUILD_ROWS: f64 = (1u64 << 20) as f64;
615
616fn tile_estimates(
622 ctx: &Ctx,
623 index: &GraphIndex,
624 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
625 seed: &std::collections::HashSet<usize>,
626) -> Vec<f64> {
627 const SEL_SUBJECT: f64 = 0.001;
628 const SEL_OBJECT: f64 = 0.02;
629 const SEL_PREDICATE: f64 = 0.05;
630 let dict = ctx.rete.dictionary();
631 let total = ctx.rete.index_triples(index);
632 let seeded = |x: &SlotTerm| matches!(x, SlotTerm::Var(v) if seed.contains(v));
633 let needs_stats = lowered
641 .iter()
642 .any(|t| matches!(t.1, SlotTerm::Pred(_)) && (seeded(&t.0) || seeded(&t.2)));
643 let stats: std::collections::HashMap<u32, &crate::meta::PredStat> = if needs_stats {
644 ctx.rete
645 .planner_stats(true)
646 .iter()
647 .map(|s| (s.predicate, s))
648 .collect()
649 } else {
650 std::collections::HashMap::new()
651 };
652 let patterns: Vec<Pattern> = lowered
656 .iter()
657 .filter_map(|t| {
658 Some((
659 const_subject(&t.0, dict)?,
660 const_predicate(&t.1)?,
661 const_object(&t.2, dict)?,
662 ))
663 })
664 .collect();
665 index.prefault_estimate_leaves(&patterns);
666 lowered
667 .iter()
668 .map(|t| {
669 let (Some(s), Some(p), Some(o)) = (
670 const_subject(&t.0, dict),
671 const_predicate(&t.1),
672 const_object(&t.2, dict),
673 ) else {
674 return 0.0;
675 };
676 let mut est = index.estimate_matches((s, p, o), total);
677 if est == 0.0 {
678 return 0.0;
679 }
680 let st = match t.1 {
681 SlotTerm::Pred(pid) => stats.get(&pid).copied(),
682 _ => None,
683 };
684 if seeded(&t.0) {
685 est *= match st {
686 Some(st) if st.distinct_subjects > 0 => 1.0 / st.distinct_subjects as f64,
687 _ => SEL_SUBJECT,
688 };
689 }
690 if seeded(&t.1) {
691 est *= SEL_PREDICATE;
692 }
693 if seeded(&t.2) {
694 est *= match st {
695 Some(st) if st.distinct_objects > 0 => 1.0 / st.distinct_objects as f64,
696 _ => SEL_OBJECT,
697 };
698 }
699 est.max(1.0)
700 })
701 .collect()
702}
703
704const REMOTE_PROBE_MIN: usize = 8;
713const REMOTE_PROBE_MAX: usize = 1024;
714
715fn remote_probe_max(index: &GraphIndex) -> usize {
722 REMOTE_PROBE_MAX * index.read_concurrency().clamp(1, 16)
723}
724
725const WINDOW_START_ROWS: usize = 256;
728
729const WINDOW_MAX_ROWS: usize = 1 << 16;
733
734const WINDOW_CHUNK_ROWS: usize = 256;
737
738type ProbePattern<'a> = Box<dyn Fn(&Row) -> Option<Pattern> + 'a>;
740
741pub(crate) struct Windowed<'a> {
759 index: &'a GraphIndex,
760 upstream: Box<dyn Iterator<Item = Row> + 'a>,
761 pat_of: Option<ProbePattern<'a>>,
763 pending: std::collections::VecDeque<Row>,
765 ready: std::collections::VecDeque<Row>,
767 size: usize,
769}
770
771pub(crate) fn windowed<'a>(
773 index: &'a GraphIndex,
774 upstream: impl Iterator<Item = Row> + 'a,
775 pat_of: impl Fn(&Row) -> Option<Pattern> + 'a,
776) -> Windowed<'a> {
777 Windowed {
778 index,
779 upstream: Box::new(upstream),
780 pat_of: index.is_remote().then(|| {
781 let f: ProbePattern<'a> = Box::new(pat_of);
782 f
783 }),
784 pending: std::collections::VecDeque::new(),
785 ready: std::collections::VecDeque::new(),
786 size: WINDOW_START_ROWS,
787 }
788}
789
790impl Windowed<'_> {
791 fn refill(&mut self, pat_of: &dyn Fn(&Row) -> Option<Pattern>) {
793 let mut batch = ProbeBatch::default();
794 'window: while self.ready.len() < self.size {
795 let chunk = WINDOW_CHUNK_ROWS.min(self.size - self.ready.len());
796 while self.pending.len() < chunk {
797 match self.upstream.next() {
798 Some(r) => self.pending.push_back(r),
799 None => break,
800 }
801 }
802 if self.pending.is_empty() {
803 break;
804 }
805 let chunk = chunk.min(self.pending.len());
806 let pats: Vec<Pattern> = self.pending.iter().take(chunk).filter_map(pat_of).collect();
808 self.index.prefault_leaves(&pats);
809 for _ in 0..chunk {
810 if let Some(p) = pat_of(&self.pending[0]) {
811 if !self.index.probe_batch_add(&mut batch, p) {
812 break 'window; }
814 }
815 let row = self.pending.pop_front().expect("chunk rows are pending");
816 self.ready.push_back(row);
817 }
818 }
819 self.index.probe_batch_fault(batch);
820 self.size = (self.size * 4).min(WINDOW_MAX_ROWS);
821 }
822}
823
824impl Iterator for Windowed<'_> {
825 type Item = Row;
826
827 fn next(&mut self) -> Option<Row> {
828 let Some(pat_of) = self.pat_of.take() else {
830 return self.upstream.next();
831 };
832 if self.ready.is_empty() {
833 self.refill(pat_of.as_ref());
834 }
835 self.pat_of = Some(pat_of);
836 self.ready.pop_front()
837 }
838}
839
840fn bgp_probe_pattern<'a>(
844 ctx: &'a Ctx<'_>,
845 t: (SlotTerm, SlotTerm, SlotTerm),
846) -> impl Fn(&Row) -> Option<Pattern> + 'a {
847 move |base| match (
848 probe_subject(ctx, &t.0, base),
849 probe_predicate(ctx, &t.1, base),
850 probe_object(ctx, &t.2, base),
851 ) {
852 (Some(s), Some(p), Some(o)) => Some((s, p, o)),
853 _ => None,
854 }
855}
856
857pub(crate) fn plan_windowed<'q>(
865 ctx: &'q Ctx<'q>,
866 index: &'q GraphIndex,
867 plan: &ProbePlan,
868 rows: Box<dyn Iterator<Item = Row> + 'q>,
869) -> Box<dyn Iterator<Item = Row> + 'q> {
870 let Some(&t) = plan.pats.first() else {
871 return rows;
872 };
873 if !index.is_remote() {
874 return rows;
875 }
876 let pat = bgp_probe_pattern(ctx, t);
877 let mut win = windowed(index, rows, move |base| {
878 pat(base).filter(|(s, _, o)| s.is_some() || o.is_some())
879 });
880 if let Some(demand) = ctx.limit_hint.get() {
885 win.size = win.size.min(demand.max(1));
886 }
887 Box::new(win)
888}
889
890pub(crate) fn prefetch_subject_probes(
896 ctx: &Ctx,
897 index: &GraphIndex,
898 patterns: &[TriplePattern],
899 sv: &str,
900 subject_ids: &[u32],
901) {
902 if !index.is_remote() {
903 return;
904 }
905 let Some(lowered) = lower(patterns, ctx) else {
906 return;
907 };
908 let Some(slot) = ctx.slots.slot(sv) else {
909 return;
910 };
911 let dict = ctx.rete.dictionary();
912 let mut pats: Vec<Pattern> = Vec::new();
913 for &sid in subject_ids {
914 let mut base = ctx.slots.empty_row();
915 base[slot] = Some(Val::Id(dict.subject_node(sid) as i64));
916 for t in &lowered {
917 if !matches!(t.0, SlotTerm::Var(i) if i == slot) {
918 continue;
919 }
920 if let (Some(s), Some(p), Some(o)) = (
921 probe_subject(ctx, &t.0, &base),
922 probe_predicate(ctx, &t.1, &base),
923 probe_object(ctx, &t.2, &base),
924 ) {
925 pats.push((s, p, o));
926 }
927 }
928 }
929 index.prefetch_probe_tiles(&pats);
930}
931
932fn pattern_is_selective(t: &(SlotTerm, SlotTerm, SlotTerm)) -> bool {
935 matches!(t.0, SlotTerm::Node(_)) || matches!(t.2, SlotTerm::Node(_))
936}
937
938fn pattern_slots(t: &(SlotTerm, SlotTerm, SlotTerm)) -> Vec<usize> {
940 let mut slots: Vec<usize> = Vec::new();
941 for term in [&t.0, &t.1, &t.2] {
942 if let SlotTerm::Var(i) = term {
943 if !slots.contains(i) {
944 slots.push(*i);
945 }
946 }
947 }
948 slots
949}
950
951const CANON_AHEAD: usize = 64;
954
955fn canon_ahead<'a, 'c>(
965 ctx: &'a Ctx<'c>,
966 t: &(SlotTerm, SlotTerm, SlotTerm),
967 triples: impl Iterator<Item = Triple> + 'a,
968) -> Box<dyn Iterator<Item = Triple> + 'a> {
969 if !matches!(t.1, SlotTerm::Var(_)) || !ctx.rete.dictionary().faults_chunks() {
970 return Box::new(triples);
971 }
972 let decoded = |term: &SlotTerm| match term {
975 SlotTerm::Var(i) => ctx.decodes_slot(*i),
976 _ => false,
977 };
978 Box::new(CanonAhead {
979 ctx,
980 triples,
981 run: std::collections::VecDeque::new(),
982 decode: (decoded(&t.0), decoded(&t.2)),
983 ahead: 0,
984 })
985}
986
987struct CanonAhead<'a, 'c, I> {
988 ctx: &'a Ctx<'c>,
989 triples: I,
990 run: std::collections::VecDeque<Triple>,
991 decode: (bool, bool),
993 ahead: usize,
996}
997
998impl<I: Iterator<Item = Triple>> Iterator for CanonAhead<'_, '_, I> {
999 type Item = Triple;
1000
1001 fn next(&mut self) -> Option<Triple> {
1002 if self.run.is_empty() {
1003 self.run.extend(self.triples.by_ref().take(CANON_AHEAD));
1004 let preds: Vec<u32> = self.run.iter().map(|t| t.1).collect();
1005 let dict = self.ctx.rete.dictionary();
1010 let take = self
1011 .ctx
1012 .decode_rows()
1013 .saturating_sub(self.ahead)
1014 .min(self.run.len());
1015 self.ahead += take;
1016 let mut nodes: Vec<u32> = Vec::new();
1017 for t in self.run.iter().take(take) {
1018 if self.decode.0 {
1019 nodes.push(dict.subject_node(t.0));
1020 }
1021 if self.decode.1 {
1022 nodes.push(dict.object_node(t.2));
1023 }
1024 }
1025 self.ctx.resolver.prefetch_canon(&preds, &nodes);
1026 }
1027 self.run.pop_front()
1028 }
1029}
1030
1031fn pred_val(ctx: &Ctx, slot: &SlotTerm, p_id: u32) -> i64 {
1038 match slot {
1039 SlotTerm::Var(_) => ctx.resolver.canon_id(pred_tag(p_id)),
1040 _ => pred_tag(p_id),
1041 }
1042}
1043
1044fn triple_row(
1048 ctx: &Ctx,
1049 t: &(SlotTerm, SlotTerm, SlotTerm),
1050 (s_id, p_id, o_id): (u32, u32, u32),
1051) -> Option<Row> {
1052 crate::guard::check();
1054 let dict = ctx.rete.dictionary();
1055 let s_val = dict.subject_node(s_id) as i64;
1056 let p_val = pred_val(ctx, &t.1, p_id);
1057 let o_val = dict.object_node(o_id) as i64;
1058 let mut row = ctx.slots.empty_row();
1059 for (term, val) in [(&t.0, s_val), (&t.1, p_val), (&t.2, o_val)] {
1060 if let SlotTerm::Var(i) = term {
1061 match row[*i] {
1062 Some(Val::Id(existing)) if existing != val => return None,
1063 Some(_) => {}
1064 None => row[*i] = Some(Val::Id(val)),
1065 }
1066 }
1067 }
1068 Some(row)
1069}
1070
1071fn scan_rows<'q>(
1076 ctx: &'q Ctx<'q>,
1077 index: &'q GraphIndex,
1078 t: (SlotTerm, SlotTerm, SlotTerm),
1079) -> Option<impl Iterator<Item = Row> + 'q> {
1080 let dict = ctx.rete.dictionary();
1081 let (sid, pid, oid) = (
1082 const_subject(&t.0, dict)?,
1083 const_predicate(&t.1)?,
1084 const_object(&t.2, dict)?,
1085 );
1086 Some(
1087 canon_ahead(ctx, &t, index.scan_iter((sid, pid, oid)))
1088 .filter_map(move |triple| triple_row(ctx, &t, triple)),
1089 )
1090}
1091
1092pub(crate) fn quad_scan_rows<'q>(
1099 ctx: &'q Ctx<'q>,
1100 patterns: &[TriplePattern],
1101 gslot: usize,
1102) -> Option<Box<dyn Iterator<Item = Row> + 'q>> {
1103 let [p] = patterns else {
1104 return None;
1105 };
1106 if [&p.s, &p.p, &p.o]
1107 .iter()
1108 .any(|t| matches!(t, PatternTerm::Var(v) if ctx.slots.slot(v) == Some(gslot)))
1109 {
1110 return None;
1111 }
1112 let dict = ctx.rete.dictionary();
1113 let Some(lowered) = lower(patterns, ctx) else {
1114 return Some(Box::new(std::iter::empty()));
1115 };
1116 let t = lowered[0];
1117 let (Some(sid), Some(pid), Some(oid)) = (
1118 const_subject(&t.0, dict),
1119 const_predicate(&t.1),
1120 const_object(&t.2, dict),
1121 ) else {
1122 return Some(Box::new(std::iter::empty()));
1123 };
1124 let scan = ctx.rete.named_quad_scan((sid, pid, oid))?;
1125 Some(Box::new(scan.filter_map(move |(g, triple)| {
1126 let mut row = triple_row(ctx, &t, triple)?;
1127 row[gslot] = Some(Val::Id(dict.subject_node(g) as i64));
1128 Some(row)
1129 })))
1130}
1131
1132pub(crate) type ScanPattern = (Option<u32>, Option<u32>, Option<u32>);
1134
1135pub(crate) fn driver_pattern(ctx: &Ctx, patterns: &[TriplePattern]) -> Option<ScanPattern> {
1140 let dict = ctx.rete.dictionary();
1141 let lowered = lower(patterns, ctx)?;
1142 let mut best: Option<(u32, ScanPattern)> = None;
1143 for t in &lowered {
1144 let (sid, pid, oid) = (
1145 const_subject(&t.0, dict)?,
1146 const_predicate(&t.1)?,
1147 const_object(&t.2, dict)?,
1148 );
1149 let score =
1150 3 * u32::from(sid.is_some()) + u32::from(pid.is_some()) + 3 * u32::from(oid.is_some());
1151 if score > 0 && best.is_none_or(|(b, _)| score > b) {
1152 best = Some((score, (sid, pid, oid)));
1153 }
1154 }
1155 best.map(|(_, pat)| pat)
1156}
1157
1158fn pattern_rows(
1161 ctx: &Ctx,
1162 index: &GraphIndex,
1163 t: &(SlotTerm, SlotTerm, SlotTerm),
1164) -> Option<(Vec<Row>, Vec<usize>)> {
1165 let slots = pattern_slots(t);
1166 let mut rel: Vec<Row> = Vec::new();
1167 let dict = ctx.rete.dictionary();
1168 let (sid, pid, oid) = (
1169 const_subject(&t.0, dict)?,
1170 const_predicate(&t.1)?,
1171 const_object(&t.2, dict)?,
1172 );
1173 for triple in canon_ahead(ctx, t, index.scan_iter((sid, pid, oid))) {
1176 if let Some(row) = triple_row(ctx, t, triple) {
1177 rel.push(row);
1178 }
1179 }
1180 Some((rel, slots))
1181}
1182
1183fn pattern_estimates(
1195 ctx: &Ctx,
1196 index: &GraphIndex,
1197 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1198 seed: &std::collections::HashSet<usize>,
1199) -> Option<Vec<f64>> {
1200 let pyr = ctx.rete.pyramid_if_loaded()?;
1203 let mut pred: std::collections::HashMap<u32, u64> = std::collections::HashMap::new();
1204 for e in &pyr.summary {
1205 *pred.entry(e.predicate).or_insert(0) += e.count as u64;
1206 }
1207 let stats: std::collections::HashMap<u32, &crate::meta::PredStat> = ctx
1214 .rete
1215 .planner_stats(true)
1216 .iter()
1217 .map(|s| (s.predicate, s))
1218 .collect();
1219 let graph_total = ctx.rete.index_triples(index).max(1) as f64;
1222 let total = graph_total;
1223 let num_preds = pred.len().max(1) as f64;
1224 const SEL_SUBJECT: f64 = 0.001;
1226 const SEL_OBJECT: f64 = 0.02;
1227 let node_bound = |t: &SlotTerm| match t {
1228 SlotTerm::Node(_) => true,
1229 SlotTerm::Var(v) => seed.contains(v),
1230 SlotTerm::Pred(_) => false,
1231 };
1232 Some(
1233 lowered
1234 .iter()
1235 .map(|t| {
1236 let (base, st) = match t.1 {
1241 SlotTerm::Pred(p) => {
1242 (*pred.get(&p).unwrap_or(&0) as f64, stats.get(&p).copied())
1243 }
1244 SlotTerm::Var(v) if seed.contains(&v) => (total / num_preds, None),
1245 _ => (total, None),
1246 };
1247 let mut est = base.min(graph_total).max(1.0);
1248 if node_bound(&t.0) {
1249 est *= match st {
1250 Some(s) if s.distinct_subjects > 0 => 1.0 / s.distinct_subjects as f64,
1251 _ => SEL_SUBJECT,
1252 };
1253 }
1254 if node_bound(&t.2) {
1255 est *= match st {
1256 Some(s) if s.distinct_objects > 0 => 1.0 / s.distinct_objects as f64,
1257 _ => SEL_OBJECT,
1258 };
1259 }
1260 est.max(1.0)
1261 })
1262 .collect(),
1263 )
1264}
1265
1266pub(crate) fn bgp_min_scan_bytes(
1273 ctx: &Ctx,
1274 index: &GraphIndex,
1275 patterns: &[TriplePattern],
1276) -> Option<u64> {
1277 let lowered = lower(patterns, ctx)?;
1278 lowered
1279 .iter()
1280 .map(|t| pattern_scan_bytes(ctx, index, t))
1281 .min()
1282}
1283
1284fn pattern_scan_bytes(ctx: &Ctx, index: &GraphIndex, t: &(SlotTerm, SlotTerm, SlotTerm)) -> u64 {
1301 let dict = ctx.rete.dictionary();
1302 match (
1303 const_subject(&t.0, dict),
1304 const_predicate(&t.1),
1305 const_object(&t.2, dict),
1306 ) {
1307 (Some(s), Some(p), Some(o)) => routed_scan_bytes(index, (s, p, o)),
1308 _ => 0,
1309 }
1310}
1311
1312pub(crate) fn routed_scan_bytes(index: &GraphIndex, pattern: Pattern) -> u64 {
1314 let sections = index.tile_sections();
1315 let mut best = u64::MAX;
1316 for perm in index.perms().iter() {
1320 let tiles = sections[perm.section_index()];
1321 best = best.min(match perm.order_pattern(pattern)[0] {
1324 Some(id) => tiles.routed_bytes(id),
1325 None => tiles.total_bytes(),
1326 });
1327 }
1328 best
1329}
1330
1331pub(crate) const FAT_SCAN_ROWS: f64 = (1u64 << 20) as f64;
1344
1345fn merge_seed_lopsided(
1350 ctx: &Ctx,
1351 index: &GraphIndex,
1352 ta: &(SlotTerm, SlotTerm, SlotTerm),
1353 tb: &(SlotTerm, SlotTerm, SlotTerm),
1354) -> bool {
1355 let est = tile_estimates(ctx, index, &[*ta, *tb], &std::collections::HashSet::new());
1356 let (lo, hi) = (est[0].min(est[1]), est[0].max(est[1]));
1357 hi >= FAT_SCAN_ROWS && hi / 4.0 >= lo
1358}
1359
1360fn selectivity_order(
1367 ctx: &Ctx,
1368 index: &GraphIndex,
1369 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1370) -> Vec<usize> {
1371 selectivity_order_seeded(ctx, index, lowered, &std::collections::HashSet::new())
1372}
1373
1374fn selectivity_order_seeded(
1378 ctx: &Ctx,
1379 index: &GraphIndex,
1380 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1381 seed: &std::collections::HashSet<usize>,
1382) -> Vec<usize> {
1383 let (estimates, per_class) = match pattern_estimates(ctx, index, lowered, seed) {
1391 Some(e) => (Some(e), false),
1392 None => (Some(tile_estimates(ctx, index, lowered, seed)), true),
1393 };
1394 let consts = |t: &(SlotTerm, SlotTerm, SlotTerm)| {
1395 [&t.0, &t.1, &t.2]
1396 .into_iter()
1397 .filter(|x| match x {
1398 SlotTerm::Var(v) => seed.contains(v),
1399 _ => true,
1400 })
1401 .count()
1402 };
1403 let vars = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Vec<usize> {
1404 [&t.0, &t.1, &t.2]
1405 .into_iter()
1406 .filter_map(|x| match x {
1407 SlotTerm::Var(v) => Some(*v),
1408 _ => None,
1409 })
1410 .collect()
1411 };
1412 let score = |i: usize| -> f64 {
1416 match &estimates {
1417 Some(e) => -e[i],
1418 None => consts(&lowered[i]) as f64,
1419 }
1420 };
1421 let type_pid = ctx.rete.dictionary().predicate_id(crate::file::RDF_TYPE);
1429 let is_class_enum = |i: usize, bound: &std::collections::HashSet<usize>| -> bool {
1430 let t = &lowered[i];
1431 !per_class
1432 && type_pid.is_some_and(|tp| matches!(t.1, SlotTerm::Pred(p) if p == tp))
1433 && matches!(t.2, SlotTerm::Node(_))
1434 && matches!(t.0, SlotTerm::Var(v) if !bound.contains(&v))
1435 };
1436 let n = lowered.len();
1437 let mut remaining: Vec<usize> = (0..n).collect();
1438 let mut order: Vec<usize> = Vec::with_capacity(n);
1439 let mut bound: std::collections::HashSet<usize> = seed.clone();
1440 while !remaining.is_empty() {
1441 let best = *remaining
1444 .iter()
1445 .max_by(|&&a, &&b| {
1446 let connected = |i: usize| vars(&lowered[i]).iter().any(|v| bound.contains(v));
1447 connected(a)
1448 .cmp(&connected(b))
1449 .then_with(|| is_class_enum(b, &bound).cmp(&is_class_enum(a, &bound)))
1450 .then_with(|| {
1451 score(a)
1452 .partial_cmp(&score(b))
1453 .unwrap_or(std::cmp::Ordering::Equal)
1454 })
1455 .then_with(|| b.cmp(&a))
1456 })
1457 .unwrap();
1458 for v in vars(&lowered[best]) {
1459 bound.insert(v);
1460 }
1461 order.push(best);
1462 remaining.retain(|&i| i != best);
1463 }
1464 order
1465}
1466
1467pub(crate) fn bgp_exists(ctx: &Ctx, index: &GraphIndex, patterns: &[TriplePattern]) -> bool {
1473 let dict = ctx.rete.dictionary();
1474 let Some(lowered) = lower(patterns, ctx) else {
1475 return false;
1476 };
1477 if let [t] = lowered.as_slice() {
1478 let names: Vec<usize> = [&t.0, &t.1, &t.2]
1482 .into_iter()
1483 .filter_map(|x| match x {
1484 SlotTerm::Var(v) => Some(*v),
1485 _ => None,
1486 })
1487 .collect();
1488 let distinct = names
1489 .iter()
1490 .enumerate()
1491 .all(|(i, v)| !names[i + 1..].contains(v));
1492 if distinct {
1493 return match (
1494 const_subject(&t.0, dict),
1495 const_predicate(&t.1),
1496 const_object(&t.2, dict),
1497 ) {
1498 (Some(s), Some(p), Some(o)) => index.scan_iter((s, p, o)).next().is_some(),
1499 _ => false,
1500 };
1501 }
1502 }
1503 !eval_bgp_rows(ctx, index, patterns).is_empty()
1504}
1505
1506pub(crate) struct BgpSolutions<'q> {
1517 scan: Option<Box<dyn Iterator<Item = Row> + 'q>>,
1518 prefix: Vec<Row>,
1519 buckets: HashMap<Vec<Val>, Vec<usize>>,
1521 shared: Vec<usize>,
1522 cartesian: bool,
1523 seed_only: bool,
1526 cur_scan: Option<Row>,
1527 matches: Vec<usize>,
1529 mi: usize,
1530}
1531
1532impl<'q> BgpSolutions<'q> {
1533 fn passthrough(rows: Box<dyn Iterator<Item = Row> + 'q>) -> Self {
1535 BgpSolutions {
1536 scan: Some(rows),
1537 prefix: Vec::new(),
1538 buckets: HashMap::new(),
1539 shared: Vec::new(),
1540 cartesian: false,
1541 seed_only: true,
1542 cur_scan: None,
1543 matches: Vec::new(),
1544 mi: 0,
1545 }
1546 }
1547
1548 fn streaming(
1557 ctx: &'q Ctx<'q>,
1558 index: &'q GraphIndex,
1559 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1560 order: &[usize],
1561 est: &[f64],
1562 ) -> Self {
1563 let (mut stream, mut bound, skip): (Box<dyn Iterator<Item = Row> + 'q>, Vec<usize>, usize) =
1564 match (est[order[1]] > limits().stream_seed)
1565 .then(|| merge_stream(ctx, index, lowered[order[0]], lowered[order[1]]))
1566 .flatten()
1567 {
1568 Some((m, slots)) => (m, slots, 2),
1569 None => {
1570 let t = lowered[order[0]];
1571 let Some(scan) = scan_rows(ctx, index, t) else {
1572 return Self::empty();
1573 };
1574 (Box::new(scan), pattern_slots(&t), 1)
1575 }
1576 };
1577 for &i in &order[skip..] {
1578 let t = lowered[i];
1579 let slots = pattern_slots(&t);
1580 let shared: Vec<usize> = slots
1581 .iter()
1582 .copied()
1583 .filter(|s| bound.contains(s))
1584 .collect();
1585 if !shared.is_empty() && est[i] > limits().hash_build {
1586 stream = Box::new(
1590 windowed(index, stream, bgp_probe_pattern(ctx, t))
1591 .flat_map(move |base| probe_rows(ctx, index, t, base)),
1592 );
1593 } else {
1594 let Some((rel, _)) = pattern_rows(ctx, index, &t) else {
1597 return Self::empty();
1598 };
1599 let mut table: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
1600 for r in rel {
1601 let key: Vec<Val> = shared.iter().map(|&s| r[s].clone().unwrap()).collect();
1602 table.entry(key).or_default().push(r);
1603 }
1604 let fill = slots.clone();
1605 stream = Box::new(stream.flat_map(move |base| {
1606 let key: Vec<Val> = shared.iter().map(|&s| base[s].clone().unwrap()).collect();
1607 let out: Vec<Row> = table
1608 .get(&key)
1609 .map(|rs| {
1610 rs.iter()
1611 .map(|r| {
1612 let mut row = base.clone();
1613 for &s in &fill {
1614 row[s] = r[s].clone();
1615 }
1616 row
1617 })
1618 .collect()
1619 })
1620 .unwrap_or_default();
1621 out.into_iter()
1622 }));
1623 }
1624 for s in slots {
1625 if !bound.contains(&s) {
1626 bound.push(s);
1627 }
1628 }
1629 }
1630 Self::passthrough(stream)
1631 }
1632
1633 fn empty() -> Self {
1635 BgpSolutions {
1636 scan: None,
1637 prefix: Vec::new(),
1638 buckets: HashMap::new(),
1639 shared: Vec::new(),
1640 cartesian: false,
1641 seed_only: false,
1642 cur_scan: None,
1643 matches: Vec::new(),
1644 mi: 0,
1645 }
1646 }
1647
1648 pub(crate) fn new(ctx: &'q Ctx<'q>, index: &'q GraphIndex, patterns: &[TriplePattern]) -> Self {
1649 if patterns.is_empty() {
1651 return BgpSolutions {
1652 scan: Some(Box::new(std::iter::once(ctx.slots.empty_row()))),
1653 prefix: vec![ctx.slots.empty_row()],
1654 buckets: HashMap::new(),
1655 shared: Vec::new(),
1656 cartesian: true,
1657 seed_only: true,
1658 cur_scan: None,
1659 matches: Vec::new(),
1660 mi: 0,
1661 };
1662 }
1663 let Some(lowered) = lower(patterns, ctx) else {
1665 return Self::empty();
1666 };
1667 let (order, scan_est) = plan_order(ctx, index, &lowered);
1670 if order.len() >= 2 && scan_est[order[0]] > limits().stream_seed {
1673 return Self::streaming(ctx, index, &lowered, &order, &scan_est);
1674 }
1675 let (&last_i, prefix_is) = order.split_last().unwrap();
1676 let prefix_pats: Vec<TriplePattern> =
1677 prefix_is.iter().map(|&i| patterns[i].clone()).collect();
1678 let prefix = eval_bgp_rows(ctx, index, &prefix_pats);
1679 if prefix.is_empty() {
1680 return Self::empty();
1681 }
1682
1683 let shared: Vec<usize> = pattern_slots(&lowered[last_i])
1687 .into_iter()
1688 .filter(|&s| prefix[0][s].is_some())
1689 .collect();
1690
1691 let class_probe = !shared.is_empty()
1700 && scan_est[last_i] >= limits().probe_floor
1701 && (prefix.len() as f64) <= scan_est[last_i]
1702 && is_unbound_class(ctx, &lowered[last_i], &shared);
1703 if !shared.is_empty() && (probe_beats_scan(prefix.len(), scan_est[last_i]) || class_probe) {
1704 let t = lowered[last_i];
1705 let stream = windowed(index, prefix.into_iter(), bgp_probe_pattern(ctx, t))
1706 .flat_map(move |base| probe_rows(ctx, index, t, base));
1707 return Self::passthrough(Box::new(stream));
1708 }
1709
1710 let Some(scan) = scan_rows(ctx, index, lowered[last_i]) else {
1712 return Self::empty();
1713 };
1714 let cartesian = shared.is_empty();
1715 let seed_only = prefix.len() == 1 && prefix[0].iter().all(Option::is_none);
1718 let mut buckets: HashMap<Vec<Val>, Vec<usize>> = HashMap::new();
1719 if !cartesian {
1720 for (i, r) in prefix.iter().enumerate() {
1721 let key: Vec<Val> = shared.iter().map(|&s| r[s].clone().unwrap()).collect();
1722 buckets.entry(key).or_default().push(i);
1723 }
1724 }
1725 BgpSolutions {
1726 scan: Some(Box::new(scan)),
1727 prefix,
1728 buckets,
1729 shared,
1730 cartesian,
1731 seed_only,
1732 cur_scan: None,
1733 matches: Vec::new(),
1734 mi: 0,
1735 }
1736 }
1737}
1738
1739impl Iterator for BgpSolutions<'_> {
1740 type Item = Row;
1741
1742 fn next(&mut self) -> Option<Row> {
1743 if self.seed_only {
1745 return self.scan.as_mut()?.next();
1746 }
1747 loop {
1748 if self.mi < self.matches.len() {
1750 let pi = self.matches[self.mi];
1751 self.mi += 1;
1752 let mut merged = self.prefix[pi].clone();
1753 for (slot, v) in self.cur_scan.as_ref().unwrap().iter().enumerate() {
1754 if v.is_some() {
1755 merged[slot] = v.clone();
1756 }
1757 }
1758 return Some(merged);
1759 }
1760 let s = self.scan.as_mut()?.next()?;
1763 self.matches.clear();
1764 if self.cartesian {
1765 self.matches.extend(0..self.prefix.len());
1766 } else {
1767 let key: Vec<Val> = self.shared.iter().map(|&i| s[i].clone().unwrap()).collect();
1768 if let Some(c) = self.buckets.get(&key) {
1769 self.matches.extend_from_slice(c);
1770 }
1771 }
1772 self.mi = 0;
1773 self.cur_scan = Some(s);
1774 }
1775 }
1776}
1777
1778#[allow(clippy::type_complexity)]
1786fn merge_stream<'q>(
1787 ctx: &'q Ctx<'q>,
1788 index: &'q GraphIndex,
1789 ta: (SlotTerm, SlotTerm, SlotTerm),
1790 tb: (SlotTerm, SlotTerm, SlotTerm),
1791) -> Option<(Box<dyn Iterator<Item = Row> + 'q>, Vec<usize>)> {
1792 let sa = pattern_slots(&ta);
1793 let sb = pattern_slots(&tb);
1794 let shared: Vec<usize> = sa.iter().copied().filter(|s| sb.contains(s)).collect();
1795 let [v] = shared[..] else {
1796 return None;
1797 };
1798 if !matches!(ta.0, SlotTerm::Var(i) if i == v) || !matches!(tb.0, SlotTerm::Var(i) if i == v) {
1799 return None;
1800 }
1801 let dict = ctx.rete.dictionary();
1802 let lower = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Option<Pattern> {
1803 Some((
1804 const_subject(&t.0, dict)?,
1805 const_predicate(&t.1)?,
1806 const_object(&t.2, dict)?,
1807 ))
1808 };
1809 let side = |t: (SlotTerm, SlotTerm, SlotTerm)| -> Option<KeyedRows<'q>> {
1810 let it = index.scan_iter_sorted_on(lower(&t)?, 0)?;
1811 let keyed: Box<dyn Iterator<Item = (u32, Row)> + 'q> =
1812 Box::new(it.filter_map(move |tri| triple_row(ctx, &t, tri).map(|r| (tri.0, r))));
1813 Some(keyed.peekable())
1814 };
1815 let a = side(ta)?;
1816 let b = side(tb)?;
1817 let mut slots = sa;
1818 for s in sb {
1819 if !slots.contains(&s) {
1820 slots.push(s);
1821 }
1822 }
1823 Some((
1824 Box::new(MergeStream {
1825 a,
1826 b,
1827 ra: Vec::new(),
1828 rb: Vec::new(),
1829 i: 0,
1830 j: 0,
1831 }),
1832 slots,
1833 ))
1834}
1835
1836type KeyedRows<'q> = std::iter::Peekable<Box<dyn Iterator<Item = (u32, Row)> + 'q>>;
1837
1838struct MergeStream<'q> {
1841 a: KeyedRows<'q>,
1842 b: KeyedRows<'q>,
1843 ra: Vec<Row>,
1844 rb: Vec<Row>,
1845 i: usize,
1846 j: usize,
1847}
1848
1849impl Iterator for MergeStream<'_> {
1850 type Item = Row;
1851
1852 fn next(&mut self) -> Option<Row> {
1853 loop {
1854 while self.i < self.ra.len() {
1855 if self.j < self.rb.len() {
1856 let j = self.j;
1857 self.j += 1;
1858 if let Some(m) = crate::row::merge_rows(&self.ra[self.i], &self.rb[j]) {
1859 return Some(m);
1860 }
1861 } else {
1862 self.i += 1;
1863 self.j = 0;
1864 }
1865 }
1866 let ka = self.a.peek()?.0;
1867 let kb = self.b.peek()?.0;
1868 match ka.cmp(&kb) {
1869 std::cmp::Ordering::Less => {
1870 self.a.next();
1871 }
1872 std::cmp::Ordering::Greater => {
1873 self.b.next();
1874 }
1875 std::cmp::Ordering::Equal => {
1876 self.ra.clear();
1877 self.rb.clear();
1878 while let Some((_, r)) = self.a.next_if(|(k, _)| *k == ka) {
1879 self.ra.push(r);
1880 }
1881 while let Some((_, r)) = self.b.next_if(|(k, _)| *k == ka) {
1882 self.rb.push(r);
1883 }
1884 self.i = 0;
1885 self.j = 0;
1886 }
1887 }
1888 }
1889 }
1890}
1891
1892fn probe_subject(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
1906 let dict = ctx.rete.dictionary();
1907 match t {
1908 SlotTerm::Node(n) => dict.node_as_subject_id(*n).map(Some),
1909 SlotTerm::Pred(_) => None,
1910 SlotTerm::Var(i) => match &base[*i] {
1911 None => Some(None),
1912 Some(Val::Id(v)) if *v >= 0 => dict.node_as_subject_id(*v as u32).map(Some),
1913 Some(_) => None,
1915 },
1916 }
1917}
1918
1919fn probe_object(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
1921 let dict = ctx.rete.dictionary();
1922 match t {
1923 SlotTerm::Node(n) => dict.node_as_object_id(*n).map(Some),
1924 SlotTerm::Pred(_) => None,
1925 SlotTerm::Var(i) => match &base[*i] {
1926 None => Some(None),
1927 Some(Val::Id(v)) if *v >= 0 => dict.node_as_object_id(*v as u32).map(Some),
1928 Some(_) => None,
1929 },
1930 }
1931}
1932
1933fn probe_predicate(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
1935 let dict = ctx.rete.dictionary();
1936 match t {
1937 SlotTerm::Pred(p) => Some(Some(*p)),
1938 SlotTerm::Node(_) => None,
1939 SlotTerm::Var(i) => match &base[*i] {
1940 None => Some(None),
1941 Some(Val::Id(v)) if *v < 0 => Some(Some((-v - 1) as u32)),
1942 Some(Val::Id(v)) => ctx
1944 .resolver
1945 .term(*v)
1946 .and_then(|t| dict.predicate_id(&t))
1947 .map(Some),
1948 Some(Val::Str(_)) => None,
1949 },
1950 }
1951}
1952
1953fn probe_rows<'q>(
1957 ctx: &'q Ctx<'q>,
1958 index: &'q GraphIndex,
1959 t: (SlotTerm, SlotTerm, SlotTerm),
1960 base: Row,
1961) -> Box<dyn Iterator<Item = Row> + 'q> {
1962 let (Some(sid), Some(pid), Some(oid)) = (
1963 probe_subject(ctx, &t.0, &base),
1964 probe_predicate(ctx, &t.1, &base),
1965 probe_object(ctx, &t.2, &base),
1966 ) else {
1967 return Box::new(std::iter::empty());
1968 };
1969 let dict = ctx.rete.dictionary();
1970 Box::new(
1973 canon_ahead(ctx, &t, index.scan_iter((sid, pid, oid))).filter_map(
1974 move |(s_id, p_id, o_id)| {
1975 let s_val = dict.subject_node(s_id) as i64;
1976 let p_val = pred_val(ctx, &t.1, p_id);
1977 let o_val = dict.object_node(o_id) as i64;
1978 let mut row = base.clone();
1979 for (term, val) in [(&t.0, s_val), (&t.1, p_val), (&t.2, o_val)] {
1980 if let SlotTerm::Var(i) = term {
1981 match row[*i] {
1982 Some(Val::Id(existing)) if existing != val => return None,
1983 Some(Val::Id(_)) => {}
1984 Some(Val::Str(_)) => return None,
1985 None => row[*i] = Some(Val::Id(val)),
1986 }
1987 }
1988 }
1989 Some(row)
1990 },
1991 ),
1992 )
1993}
1994
1995pub(crate) struct ProbePlan {
1997 pats: Vec<(SlotTerm, SlotTerm, SlotTerm)>,
1998}
1999
2000impl ProbePlan {
2001 pub(crate) fn new(
2005 ctx: &Ctx,
2006 index: &GraphIndex,
2007 patterns: &[TriplePattern],
2008 seed_mask: &[bool],
2009 ) -> Option<Self> {
2010 let lowered = lower(patterns, ctx)?;
2011 let seed: std::collections::HashSet<usize> = seed_mask
2012 .iter()
2013 .enumerate()
2014 .filter_map(|(i, b)| b.then_some(i))
2015 .collect();
2016 let order = selectivity_order_seeded(ctx, index, &lowered, &seed);
2017 Some(ProbePlan {
2018 pats: order.into_iter().map(|i| lowered[i]).collect(),
2019 })
2020 }
2021}
2022
2023pub(crate) struct ProbeJoin<'q> {
2026 ctx: &'q Ctx<'q>,
2027 index: &'q GraphIndex,
2028 pats: Vec<(SlotTerm, SlotTerm, SlotTerm)>,
2029 stack: Vec<Box<dyn Iterator<Item = Row> + 'q>>,
2030}
2031
2032impl<'q> ProbeJoin<'q> {
2033 pub(crate) fn new(
2036 ctx: &'q Ctx<'q>,
2037 index: &'q GraphIndex,
2038 patterns: &[TriplePattern],
2039 ) -> Option<Self> {
2040 let plan = ProbePlan::new(ctx, index, patterns, &vec![false; ctx.slots.len()])?;
2041 Some(Self::from_plan(ctx, index, &plan, ctx.slots.empty_row()))
2042 }
2043
2044 pub(crate) fn from_plan(
2046 ctx: &'q Ctx<'q>,
2047 index: &'q GraphIndex,
2048 plan: &ProbePlan,
2049 seed: Row,
2050 ) -> Self {
2051 let pats = plan.pats.clone();
2052 let first = probe_rows(ctx, index, pats[0], seed);
2053 ProbeJoin {
2054 ctx,
2055 index,
2056 pats,
2057 stack: vec![first],
2058 }
2059 }
2060}
2061
2062impl Iterator for ProbeJoin<'_> {
2063 type Item = Row;
2064
2065 fn next(&mut self) -> Option<Row> {
2066 loop {
2067 let depth = self.stack.len();
2068 match self.stack.last_mut()?.next() {
2069 Some(row) => {
2070 if depth == self.pats.len() {
2071 return Some(row);
2072 }
2073 let it = probe_rows(self.ctx, self.index, self.pats[depth], row);
2074 self.stack.push(it);
2075 }
2076 None => {
2077 self.stack.pop();
2078 if self.stack.is_empty() {
2079 return None;
2080 }
2081 }
2082 }
2083 }
2084 }
2085}
2086
2087fn hash_join(
2091 left: Vec<Row>,
2092 left_bound: &[usize],
2093 right: Vec<Row>,
2094 right_slots: &[usize],
2095) -> Vec<Row> {
2096 if left.len() == 1 && left_bound.is_empty() {
2098 return right;
2099 }
2100 if left.is_empty() || right.is_empty() {
2101 return Vec::new();
2102 }
2103 let shared: Vec<usize> = right_slots
2104 .iter()
2105 .copied()
2106 .filter(|s| left_bound.contains(s))
2107 .collect();
2108 let fill = |l: &Row, r: &Row| -> Row {
2109 let mut out = l.clone();
2110 for &s in right_slots {
2111 out[s] = r[s].clone();
2112 }
2113 out
2114 };
2115 if shared.is_empty() {
2116 let mut out = Vec::with_capacity(left.len() * right.len());
2120 for l in &left {
2121 for r in &right {
2122 out.push(fill(l, r));
2123 }
2124 }
2125 return out;
2126 }
2127 let key_of = |b: &Row| -> Vec<Val> { shared.iter().map(|&s| b[s].clone().unwrap()).collect() };
2128 let mut out = Vec::new();
2135 if right.len() <= left.len() {
2136 let mut buckets: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
2137 for r in right {
2138 buckets.entry(key_of(&r)).or_default().push(r);
2139 }
2140 for l in &left {
2141 if let Some(rs) = buckets.get(&key_of(l)) {
2142 for r in rs {
2143 out.push(fill(l, r));
2144 }
2145 }
2146 }
2147 } else {
2148 let mut buckets: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
2150 for l in left {
2151 buckets.entry(key_of(&l)).or_default().push(l);
2152 }
2153 for r in &right {
2154 if let Some(ls) = buckets.get(&key_of(r)) {
2155 for l in ls {
2156 let mut row = r.clone();
2157 for &s in left_bound {
2158 if let Some(v) = &l[s] {
2159 row[s] = Some(v.clone());
2160 }
2161 }
2162 out.push(row);
2163 }
2164 }
2165 }
2166 }
2167 out
2168}
2169
2170fn const_subject(t: &SlotTerm, d: &crate::Dictionary) -> Option<Option<u32>> {
2175 match t {
2176 SlotTerm::Node(n) => d.node_as_subject_id(*n).map(Some),
2177 SlotTerm::Pred(_) => None, SlotTerm::Var(_) => Some(None),
2179 }
2180}
2181
2182fn const_object(t: &SlotTerm, d: &crate::Dictionary) -> Option<Option<u32>> {
2183 match t {
2184 SlotTerm::Node(n) => d.node_as_object_id(*n).map(Some),
2185 SlotTerm::Pred(_) => None,
2186 SlotTerm::Var(_) => Some(None),
2187 }
2188}
2189
2190fn const_predicate(t: &SlotTerm) -> Option<Option<u32>> {
2191 match t {
2192 SlotTerm::Pred(p) => Some(Some(*p)),
2193 SlotTerm::Node(_) => None, SlotTerm::Var(_) => Some(None),
2195 }
2196}
2197
2198#[cfg(test)]
2199mod tests {
2200 use super::*;
2201 use crate::dictionary::DictionaryBuilder;
2202 use crate::file::write_file_v05 as write_file;
2203 use crate::index::GraphIndexBuilder;
2204
2205 fn rete_from(triples: &[(&str, &str, &str)]) -> Vec<u8> {
2206 let mut db = DictionaryBuilder::new();
2207 for (s, p, o) in triples {
2208 db.observe(s, p, o);
2209 }
2210 let dict = db.build();
2211 let mut ib = GraphIndexBuilder::new();
2212 for (s, p, o) in triples {
2213 ib.push(dict.encode(s, p, o).unwrap());
2214 }
2215 write_file(&dict, &ib.build(), false, &[], 0)
2216 }
2217
2218 fn pat(s: &str, p: &str, o: &str) -> TriplePattern {
2219 TriplePattern {
2220 s: PatternTerm::parse(s),
2221 p: PatternTerm::parse(p),
2222 o: PatternTerm::parse(o),
2223 }
2224 }
2225
2226 #[test]
2235 fn scan_bytes_route_a_literal_by_its_object_id() {
2236 let value = "<http://ex/value>";
2237 let owned: Vec<(String, String)> = (0..400)
2238 .map(|i| (format!("<http://ex/s{i:03}>"), format!("\"lit {i:03}\"")))
2239 .collect();
2240 let mut db = DictionaryBuilder::new();
2241 for (s, o) in &owned {
2242 db.observe(s, value, o);
2243 }
2244 let dict = db.build();
2245 let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2246 for (s, o) in &owned {
2247 ib.push(dict.encode(s, value, o).unwrap());
2248 }
2249 let rete = Rete::open(&write_file(&dict, &ib.build(), false, &[], 0)).unwrap();
2250 let index = rete.default_index();
2251 let whole = routed_scan_bytes(index, (None, rete.dictionary().predicate_id(value), None));
2253 for (_, lit) in owned.iter().step_by(57) {
2254 let q = [pat("?s", value, lit)];
2255 let mut slots = Slots::new();
2256 collect_pattern_slots(&q, &mut slots);
2257 let ctx = Ctx::new(&rete, slots);
2258 let got = bgp_min_scan_bytes(&ctx, index, &q).unwrap();
2259 assert!(got > 0, "{lit} routed to no tile");
2260 assert!(
2261 got < whole,
2262 "{lit} routed to the whole predicate ({got} of {whole})"
2263 );
2264 }
2265 }
2266
2267 #[test]
2273 fn plan_gates_do_not_move_with_the_compression() {
2274 let mut owned: Vec<(String, String, String)> = Vec::new();
2275 for i in 0..3000 {
2276 let s = format!("<http://ex/s{i}>");
2277 owned.push((
2278 s.clone(),
2279 "<http://ex/kind>".into(),
2280 format!("<http://ex/K{}>", i % 7),
2281 ));
2282 owned.push((s.clone(), "<http://ex/value>".into(), format!("\"v {i}\"")));
2283 if i % 50 == 0 {
2284 owned.push((s, "<http://ex/rare>".into(), "<http://ex/R>".into()));
2285 }
2286 }
2287 let mut db = DictionaryBuilder::new();
2288 for (s, p, o) in &owned {
2289 db.observe(s, p, o);
2290 }
2291 let dict = db.build();
2292 let mut ib = GraphIndexBuilder::new().with_tile_budget(1024);
2293 for (s, p, o) in &owned {
2294 ib.push(dict.encode(s, p, o).unwrap());
2295 }
2296 let bytes = write_file(&dict, &ib.build(), false, &[], 0);
2297 let leaked: &'static [u8] = Box::leak(bytes.clone().into_boxed_slice());
2298 let resident = Rete::open(&bytes).unwrap();
2299 let lazy = Rete::open_ranged_lazy(crate::reader::SliceReader::new(leaked)).unwrap();
2300 let shapes: Vec<Vec<TriplePattern>> = vec![
2301 vec![
2302 pat("?s", "<http://ex/rare>", "<http://ex/R>"),
2303 pat("?s", "<http://ex/value>", "?v"),
2304 ],
2305 vec![
2306 pat("?s", "<http://ex/kind>", "<http://ex/K3>"),
2307 pat("?s", "<http://ex/value>", "?v"),
2308 ],
2309 vec![
2310 pat("?s", "<http://ex/kind>", "?k"),
2311 pat("?s", "<http://ex/value>", "?v"),
2312 ],
2313 vec![
2314 pat("?s", "<http://ex/value>", "\"v 7\""),
2315 pat("?s", "<http://ex/kind>", "?k"),
2316 ],
2317 ];
2318 let decisions = |rete: &Rete| -> Vec<(Vec<u64>, bool, Option<u64>)> {
2319 shapes
2320 .iter()
2321 .map(|q| {
2322 let mut slots = Slots::new();
2323 collect_pattern_slots(q, &mut slots);
2324 let ctx = Ctx::new(rete, slots);
2325 let index = rete.default_index();
2326 let lowered = lower(q, &ctx).unwrap();
2327 let est = tile_estimates(&ctx, index, &lowered, &Default::default());
2328 let lopsided = merge_seed_lopsided(&ctx, index, &lowered[0], &lowered[1]);
2329 let min = bgp_min_estimate(&ctx, index, q).map(|e| e as u64);
2330 (est.iter().map(|e| *e as u64).collect(), lopsided, min)
2331 })
2332 .collect()
2333 };
2334 assert_eq!(decisions(&resident), decisions(&lazy));
2335 #[cfg(feature = "compression")]
2337 {
2338 let bytes_of = |rete: &Rete| {
2339 let q = &shapes[2];
2340 let mut slots = Slots::new();
2341 collect_pattern_slots(q, &mut slots);
2342 let ctx = Ctx::new(rete, slots);
2343 bgp_min_scan_bytes(&ctx, rete.default_index(), q)
2344 };
2345 assert_ne!(bytes_of(&resident), bytes_of(&lazy));
2346 }
2347 }
2348
2349 #[test]
2359 fn a_fat_predicate_estimates_alike_in_both_layouts() {
2360 let mut owned: Vec<(String, String, String)> = Vec::new();
2361 for i in 0..120_000 {
2362 let s = format!("<http://ex/s{i:06}>");
2363 owned.push((s.clone(), "<http://ex/kind>".into(), "<http://ex/K>".into()));
2364 owned.push((s, "<http://ex/value>".into(), format!("\"v {i}\"")));
2365 }
2366 let mut db = DictionaryBuilder::new();
2367 for (s, p, o) in &owned {
2368 db.observe(s, p, o);
2369 }
2370 let dict = db.build();
2371 let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2372 for (s, p, o) in &owned {
2373 ib.push(dict.encode(s, p, o).unwrap());
2374 }
2375 let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2376 let v6: &'static [u8] = Box::leak(
2377 crate::v06::write::convert_image(&v5, Default::default())
2378 .unwrap()
2379 .into_boxed_slice(),
2380 );
2381 let leaked5: &'static [u8] = Box::leak(v5.clone().into_boxed_slice());
2382 let flat = Rete::open_ranged_lazy(crate::reader::SliceReader::new(leaked5)).unwrap();
2383 let leafed = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v6)).unwrap();
2384 let q = [pat("?s", "<http://ex/value>", "?v")];
2385 let figures = |rete: &Rete| {
2386 let mut slots = Slots::new();
2387 collect_pattern_slots(&q, &mut slots);
2388 let ctx = Ctx::new(rete, slots);
2389 let index = rete.default_index();
2390 let total = bgp_total_estimate(&ctx, index, &q).unwrap();
2391 (total, probe_row_budget(total))
2392 };
2393 let (est5, budget5) = figures(&flat);
2394 let (est6, budget6) = figures(&leafed);
2395 assert!(est5 >= 70_000.0, "flat estimate {est5}");
2396 assert!(
2397 est6 >= est5 / 2.0 && est6 <= est5 * 2.0,
2398 "0x06 estimates {est6} where 0x05 estimates {est5}"
2399 );
2400 assert!(budget5.is_some_and(|b| b >= 1000), "{budget5:?}");
2402 assert!(budget6.is_some_and(|b| b >= 1000), "{budget6:?}");
2403 }
2404
2405 #[test]
2412 fn a_rare_object_of_a_fat_predicate_estimates_small_in_both_layouts() {
2413 let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2414 let mut owned: Vec<(String, String, String)> = Vec::new();
2415 for i in 0..120_000 {
2416 let s = format!("<http://ex/s{i:06}>");
2417 owned.push((s.clone(), ty.into(), "<http://ex/Common>".into()));
2418 owned.push((s.clone(), "<http://ex/other>".into(), format!("\"o {i}\"")));
2419 if i % 3000 == 0 {
2420 owned.push((s, ty.into(), "<http://ex/Rare>".into()));
2421 }
2422 }
2423 let mut db = DictionaryBuilder::new();
2424 for (s, p, o) in &owned {
2425 db.observe(s, p, o);
2426 }
2427 let dict = db.build();
2428 let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2429 for (s, p, o) in &owned {
2430 ib.push(dict.encode(s, p, o).unwrap());
2431 }
2432 let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2433 let v6: &'static [u8] = Box::leak(
2434 crate::v06::write::convert_image(&v5, Default::default())
2435 .unwrap()
2436 .into_boxed_slice(),
2437 );
2438 let leaked5: &'static [u8] = Box::leak(v5.into_boxed_slice());
2439 let figures = |rete: &Rete| {
2440 let est = |q: &[TriplePattern]| {
2441 let mut slots = Slots::new();
2442 collect_pattern_slots(q, &mut slots);
2443 let ctx = Ctx::new(rete, slots);
2444 bgp_min_estimate(&ctx, rete.default_index(), q).unwrap()
2445 };
2446 (
2447 est(&[pat("?s", ty, "<http://ex/Rare>")]),
2448 est(&[pat("?s", ty, "<http://ex/Common>")]),
2449 est(&[pat("?s", "<http://ex/other>", "?x")]),
2450 )
2451 };
2452 for (name, bytes) in [("0x05", leaked5), ("0x06", v6)] {
2453 let rete = Rete::open_ranged_lazy(crate::reader::SliceReader::new(bytes)).unwrap();
2454 let (rare, common, other) = figures(&rete);
2455 assert!(rare * 20.0 < other, "{name}: rare {rare} vs other {other}");
2456 assert!(
2457 rare * 20.0 < common,
2458 "{name}: rare {rare} vs common {common}"
2459 );
2460 }
2461 }
2462
2463 #[test]
2470 fn a_probe_prefetch_window_is_bounded_and_warm() {
2471 use crate::reader::{CountingReader, SliceReader};
2472 let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2473 let mut owned: Vec<(String, String, String)> = Vec::new();
2474 for i in 0..20_000 {
2475 let s = format!("<http://ex/s{i:06}>");
2476 owned.push((s.clone(), ty.into(), format!("<http://ex/C{}>", i % 7)));
2477 owned.push((s, "<http://ex/other>".into(), format!("\"o {}\"", i % 5000)));
2478 }
2479 let mut db = DictionaryBuilder::new();
2480 for (s, p, o) in &owned {
2481 db.observe(s, p, o);
2482 }
2483 let dict = db.build();
2484 let mut ib = GraphIndexBuilder::new().with_tile_budget(128);
2485 for (s, p, o) in &owned {
2486 ib.push(dict.encode(s, p, o).unwrap());
2487 }
2488 let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2489 let v6 = crate::v06::write::convert_image(&v5, Default::default()).unwrap();
2490 let leaked: &'static [u8] = Box::leak(v6.into_boxed_slice());
2491 let reader = std::sync::Arc::new(CountingReader::new(SliceReader::new(leaked)));
2492 let rete = Rete::open_ranged_lazy(reader.clone()).unwrap();
2493 let index = rete.default_index();
2494 index.set_cache_cap(1 << 20);
2497 let pats: Vec<Pattern> = (0..20_000)
2499 .step_by(3)
2500 .map(|i| {
2501 let (s, _, _) = dict
2502 .encode(&format!("<http://ex/s{i:06}>"), ty, "<http://ex/C0>")
2503 .unwrap();
2504 (Some(s), None, None)
2505 })
2506 .collect();
2507 let mut from = 0;
2508 let mut windows = 0;
2509 while from < pats.len() {
2510 let n = index.prefetch_probe_tiles(&pats[from..]);
2511 assert!(n >= 1, "a window always makes progress");
2512 assert!(
2513 n < pats.len() - from || windows > 0,
2514 "the first window is cut"
2515 );
2516 let before = reader.requests();
2517 for &p in &pats[from..from + n] {
2518 assert!(index.scan_iter(p).next().is_some());
2519 }
2520 assert_eq!(reader.requests(), before, "a covered probe reads nothing");
2521 from += n;
2522 windows += 1;
2523 }
2524 assert!(windows > 1, "{windows} window(s) for {} probes", pats.len());
2525 }
2526
2527 #[test]
2532 fn a_tile_span_is_the_same_in_both_layouts() {
2533 let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2534 let mut owned: Vec<(String, String, String)> = Vec::new();
2535 for i in 0..30_000 {
2536 let s = format!("<http://ex/s{i:06}>");
2537 owned.push((s.clone(), ty.into(), format!("<http://ex/C{}>", i % 7)));
2538 owned.push((s, "<http://ex/other>".into(), format!("\"o {}\"", i % 5000)));
2539 }
2540 let mut db = DictionaryBuilder::new();
2541 for (s, p, o) in &owned {
2542 db.observe(s, p, o);
2543 }
2544 let dict = db.build();
2545 let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2546 for (s, p, o) in &owned {
2547 ib.push(dict.encode(s, p, o).unwrap());
2548 }
2549 let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2550 let v6 = crate::v06::write::convert_image(&v5, Default::default()).unwrap();
2551 let (v5, v6): (&'static [u8], &'static [u8]) = (
2552 Box::leak(v5.into_boxed_slice()),
2553 Box::leak(v6.into_boxed_slice()),
2554 );
2555 let flat = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v5)).unwrap();
2556 let leafed = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v6)).unwrap();
2557 let (fi, li) = (flat.default_index(), leafed.default_index());
2558 let mut checked = 0;
2559 for perm in fi.perms().iter() {
2560 let si = perm.section_index();
2561 for a in (0..dict.term_count() + 2).step_by(97) {
2562 assert_eq!(
2563 fi.tile_span(si, Some(a)),
2564 li.tile_span(si, Some(a)),
2565 "section {si}, id {a}"
2566 );
2567 checked += 1;
2568 }
2569 assert_eq!(fi.tile_span(si, None), li.tile_span(si, None));
2570 }
2571 assert!(checked > 100);
2572 }
2573
2574 #[test]
2579 fn every_join_path_returns_the_same_solutions() {
2580 let mut owned: Vec<(String, String, String)> = Vec::new();
2581 let mut x: u64 = 7;
2582 let mut next = |m: u64| {
2583 x = x
2584 .wrapping_mul(6364136223846793005)
2585 .wrapping_add(1442695040888963407);
2586 (x >> 33) % m
2587 };
2588 for i in 0..60 {
2589 let s = format!("s{i}");
2590 owned.push((s.clone(), "a".into(), format!("C{}", next(3))));
2591 for p in 0..4 {
2592 for _ in 0..next(3) {
2593 owned.push((s.clone(), format!("p{p}"), format!("s{}", next(60))));
2594 }
2595 }
2596 }
2597 let triples: Vec<(&str, &str, &str)> = owned
2598 .iter()
2599 .map(|(s, p, o)| (s.as_str(), p.as_str(), o.as_str()))
2600 .collect();
2601 let bytes = rete_from(&triples);
2602 let rete = Rete::open(&bytes).unwrap();
2603 let queries: Vec<Vec<TriplePattern>> = vec![
2604 vec![pat("?s", "p0", "?a"), pat("?s", "p1", "?b")],
2605 vec![pat("?s", "a", "C1"), pat("?s", "p0", "?a")],
2606 vec![pat("?s", "p0", "?a"), pat("?a", "p2", "?b")],
2607 vec![pat("s5", "p0", "?a"), pat("?a", "?p", "?o")],
2608 vec![pat("?s", "p0", "?x"), pat("?s", "p1", "?x")],
2609 vec![
2610 pat("?s", "p3", "?o"),
2611 pat("?o", "a", "C0"),
2612 pat("?s", "p1", "?z"),
2613 ],
2614 vec![
2615 pat("?s", "p0", "?a"),
2616 pat("?s", "p1", "?b"),
2617 pat("?b", "p2", "?c"),
2618 ],
2619 ];
2620 let run = |limits: Option<PlanLimits>| -> Vec<Vec<Vec<(String, String)>>> {
2621 TEST_LIMITS.with(|c| c.set(limits));
2622 let out = queries
2623 .iter()
2624 .map(|q| {
2625 let mut slots = crate::row::Slots::new();
2626 collect_pattern_slots(q, &mut slots);
2627 let ctx = Ctx::new(&rete, slots);
2628 let mut rows: Vec<Vec<(String, String)>> =
2629 BgpSolutions::new(&ctx, rete.default_index(), q)
2630 .map(|r| row_to_binding(&ctx, &r).into_iter().collect())
2631 .collect();
2632 rows.sort();
2633 rows
2634 })
2635 .collect();
2636 TEST_LIMITS.with(|c| c.set(None));
2637 out
2638 };
2639 let reference = run(None);
2640 assert!(reference.iter().all(|r| !r.is_empty()), "{reference:?}");
2641 for (name, l) in [
2642 (
2643 "probe everything",
2644 PlanLimits {
2645 probe_floor: 0.0,
2646 stream_seed: f64::MAX,
2647 hash_build: f64::MAX,
2648 },
2649 ),
2650 (
2651 "stream + hash",
2652 PlanLimits {
2653 probe_floor: f64::MAX,
2654 stream_seed: 0.0,
2655 hash_build: f64::MAX,
2656 },
2657 ),
2658 (
2659 "stream + probe",
2660 PlanLimits {
2661 probe_floor: f64::MAX,
2662 stream_seed: 0.0,
2663 hash_build: 0.0,
2664 },
2665 ),
2666 (
2667 "stream, all paths",
2668 PlanLimits {
2669 probe_floor: 0.0,
2670 stream_seed: 0.0,
2671 hash_build: 30.0,
2672 },
2673 ),
2674 ] {
2675 assert_eq!(run(Some(l)), reference, "{name}");
2676 }
2677 }
2678
2679 #[test]
2680 fn single_pattern_binds_variable() {
2681 let bytes = rete_from(&[("Alice", "knows", "Bob"), ("Bob", "knows", "Carol")]);
2682 let rete = Rete::open(&bytes).unwrap();
2683 let sols = eval_bgp(&rete, &[pat("Alice", "knows", "?y")]);
2684 assert_eq!(sols.len(), 1);
2685 assert_eq!(sols[0]["y"], "Bob");
2686 }
2687
2688 #[test]
2689 fn two_hop_join_on_shared_variable() {
2690 let bytes = rete_from(&[
2692 ("Alice", "knows", "Bob"),
2693 ("Bob", "knows", "Carol"),
2694 ("Carol", "knows", "Dave"),
2695 ("Alice", "knows", "Eve"), ]);
2697 let rete = Rete::open(&bytes).unwrap();
2698 let sols = eval_bgp(&rete, &[pat("?x", "knows", "?y"), pat("?y", "knows", "?z")]);
2699 let mut got: Vec<_> = sols
2701 .iter()
2702 .map(|b| (b["x"].clone(), b["y"].clone(), b["z"].clone()))
2703 .collect();
2704 got.sort();
2705 assert_eq!(
2706 got,
2707 vec![
2708 ("Alice".into(), "Bob".into(), "Carol".into()),
2709 ("Bob".into(), "Carol".into(), "Dave".into()),
2710 ]
2711 );
2712 }
2713
2714 #[test]
2715 fn repeated_variable_within_pattern() {
2716 let bytes = rete_from(&[("Alice", "knows", "Bob"), ("Bob", "knows", "Bob")]);
2718 let rete = Rete::open(&bytes).unwrap();
2719 let sols = eval_bgp(&rete, &[pat("?x", "knows", "?x")]);
2720 assert_eq!(sols.len(), 1);
2721 assert_eq!(sols[0]["x"], "Bob");
2722 }
2723
2724 #[test]
2725 fn no_solutions_yields_empty() {
2726 let bytes = rete_from(&[("Alice", "knows", "Bob")]);
2727 let rete = Rete::open(&bytes).unwrap();
2728 assert!(eval_bgp(&rete, &[pat("Alice", "likes", "?y")]).is_empty());
2729 }
2730
2731 #[test]
2738 fn snowflake_type_and_adjacency_matches_reference() {
2739 const TYPE: &str = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2740 let mut triples: Vec<(String, String, String)> = Vec::new();
2741 for i in 0..60 {
2743 let s = format!("S{i}");
2744 triples.push((s.clone(), TYPE.into(), "Student".into()));
2745 triples.push((s.clone(), "takesCourse".into(), format!("c{}", i % 5)));
2746 triples.push((s, "takesCourse".into(), format!("c{}", (i + 1) % 5)));
2747 }
2748 for j in 0..5 {
2750 triples.push((format!("c{j}"), TYPE.into(), "Course".into()));
2751 }
2752 triples.push(("Prof".into(), "teacherOf".into(), "c0".into()));
2753 triples.push(("Prof".into(), "teacherOf".into(), "c2".into()));
2754
2755 let refs: Vec<(&str, &str, &str)> = triples
2756 .iter()
2757 .map(|(s, p, o)| (s.as_str(), p.as_str(), o.as_str()))
2758 .collect();
2759 let bytes = rete_from(&refs);
2760 let rete = Rete::open(&bytes).unwrap();
2761
2762 let got: std::collections::BTreeSet<(String, String)> = eval_bgp(
2763 &rete,
2764 &[
2765 pat("?x", TYPE, "Student"),
2766 pat("?y", TYPE, "Course"),
2767 pat("?x", "takesCourse", "?y"),
2768 pat("Prof", "teacherOf", "?y"),
2769 ],
2770 )
2771 .into_iter()
2772 .map(|b| (b["x"].clone(), b["y"].clone()))
2773 .collect();
2774
2775 let taught = ["c0", "c2"];
2777 let mut want = std::collections::BTreeSet::new();
2778 for i in 0..60 {
2779 for c in [i % 5, (i + 1) % 5] {
2780 let course = format!("c{c}");
2781 if taught.contains(&course.as_str()) {
2782 want.insert((format!("S{i}"), course));
2783 }
2784 }
2785 }
2786 assert_eq!(got, want, "snowflake join must match the brute-force set");
2787 assert!(!want.is_empty(), "sanity: the reference set is non-empty");
2788 }
2789
2790 #[test]
2795 fn merge_join_subject_star_cross_product() {
2796 let bytes = rete_from(&[
2797 ("x", "a", "a1"),
2798 ("x", "a", "a2"),
2799 ("x", "b", "b1"),
2800 ("x", "b", "b2"),
2801 ("y", "a", "a3"),
2802 ("y", "b", "b3"),
2803 ("z", "a", "a4"), ]);
2805 let rete = Rete::open(&bytes).unwrap();
2806 let mut got: Vec<(String, String, String)> =
2807 eval_bgp(&rete, &[pat("?x", "a", "?av"), pat("?x", "b", "?bv")])
2808 .iter()
2809 .map(|m| (m["x"].clone(), m["av"].clone(), m["bv"].clone()))
2810 .collect();
2811 got.sort();
2812 let mut want: Vec<(String, String, String)> = [
2813 ("x", "a1", "b1"),
2814 ("x", "a1", "b2"),
2815 ("x", "a2", "b1"),
2816 ("x", "a2", "b2"),
2817 ("y", "a3", "b3"),
2818 ]
2819 .into_iter()
2820 .map(|(a, b, c)| (a.to_string(), b.to_string(), c.to_string()))
2821 .collect();
2822 want.sort();
2823 assert_eq!(got, want, "same-role merge must equal the brute-force join");
2824 }
2825}