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 })
984}
985
986struct CanonAhead<'a, 'c, I> {
987 ctx: &'a Ctx<'c>,
988 triples: I,
989 run: std::collections::VecDeque<Triple>,
990 decode: (bool, bool),
992}
993
994impl<I: Iterator<Item = Triple>> Iterator for CanonAhead<'_, '_, I> {
995 type Item = Triple;
996
997 fn next(&mut self) -> Option<Triple> {
998 if self.run.is_empty() {
999 self.run.extend(self.triples.by_ref().take(CANON_AHEAD));
1000 let preds: Vec<u32> = self.run.iter().map(|t| t.1).collect();
1001 let dict = self.ctx.rete.dictionary();
1006 let take = self.ctx.decode_rows().min(self.run.len());
1007 let mut nodes: Vec<u32> = Vec::new();
1008 for t in self.run.iter().take(take) {
1009 if self.decode.0 {
1010 nodes.push(dict.subject_node(t.0));
1011 }
1012 if self.decode.1 {
1013 nodes.push(dict.object_node(t.2));
1014 }
1015 }
1016 self.ctx.resolver.prefetch_canon(&preds, &nodes);
1017 }
1018 self.run.pop_front()
1019 }
1020}
1021
1022fn pred_val(ctx: &Ctx, slot: &SlotTerm, p_id: u32) -> i64 {
1029 match slot {
1030 SlotTerm::Var(_) => ctx.resolver.canon_id(pred_tag(p_id)),
1031 _ => pred_tag(p_id),
1032 }
1033}
1034
1035fn triple_row(
1039 ctx: &Ctx,
1040 t: &(SlotTerm, SlotTerm, SlotTerm),
1041 (s_id, p_id, o_id): (u32, u32, u32),
1042) -> Option<Row> {
1043 crate::guard::check();
1045 let dict = ctx.rete.dictionary();
1046 let s_val = dict.subject_node(s_id) as i64;
1047 let p_val = pred_val(ctx, &t.1, p_id);
1048 let o_val = dict.object_node(o_id) as i64;
1049 let mut row = ctx.slots.empty_row();
1050 for (term, val) in [(&t.0, s_val), (&t.1, p_val), (&t.2, o_val)] {
1051 if let SlotTerm::Var(i) = term {
1052 match row[*i] {
1053 Some(Val::Id(existing)) if existing != val => return None,
1054 Some(_) => {}
1055 None => row[*i] = Some(Val::Id(val)),
1056 }
1057 }
1058 }
1059 Some(row)
1060}
1061
1062fn scan_rows<'q>(
1067 ctx: &'q Ctx<'q>,
1068 index: &'q GraphIndex,
1069 t: (SlotTerm, SlotTerm, SlotTerm),
1070) -> Option<impl Iterator<Item = Row> + 'q> {
1071 let dict = ctx.rete.dictionary();
1072 let (sid, pid, oid) = (
1073 const_subject(&t.0, dict)?,
1074 const_predicate(&t.1)?,
1075 const_object(&t.2, dict)?,
1076 );
1077 Some(
1078 canon_ahead(ctx, &t, index.scan_iter((sid, pid, oid)))
1079 .filter_map(move |triple| triple_row(ctx, &t, triple)),
1080 )
1081}
1082
1083pub(crate) fn quad_scan_rows<'q>(
1090 ctx: &'q Ctx<'q>,
1091 patterns: &[TriplePattern],
1092 gslot: usize,
1093) -> Option<Box<dyn Iterator<Item = Row> + 'q>> {
1094 let [p] = patterns else {
1095 return None;
1096 };
1097 if [&p.s, &p.p, &p.o]
1098 .iter()
1099 .any(|t| matches!(t, PatternTerm::Var(v) if ctx.slots.slot(v) == Some(gslot)))
1100 {
1101 return None;
1102 }
1103 let dict = ctx.rete.dictionary();
1104 let Some(lowered) = lower(patterns, ctx) else {
1105 return Some(Box::new(std::iter::empty()));
1106 };
1107 let t = lowered[0];
1108 let (Some(sid), Some(pid), Some(oid)) = (
1109 const_subject(&t.0, dict),
1110 const_predicate(&t.1),
1111 const_object(&t.2, dict),
1112 ) else {
1113 return Some(Box::new(std::iter::empty()));
1114 };
1115 let scan = ctx.rete.named_quad_scan((sid, pid, oid))?;
1116 Some(Box::new(scan.filter_map(move |(g, triple)| {
1117 let mut row = triple_row(ctx, &t, triple)?;
1118 row[gslot] = Some(Val::Id(dict.subject_node(g) as i64));
1119 Some(row)
1120 })))
1121}
1122
1123pub(crate) type ScanPattern = (Option<u32>, Option<u32>, Option<u32>);
1125
1126pub(crate) fn driver_pattern(ctx: &Ctx, patterns: &[TriplePattern]) -> Option<ScanPattern> {
1131 let dict = ctx.rete.dictionary();
1132 let lowered = lower(patterns, ctx)?;
1133 let mut best: Option<(u32, ScanPattern)> = None;
1134 for t in &lowered {
1135 let (sid, pid, oid) = (
1136 const_subject(&t.0, dict)?,
1137 const_predicate(&t.1)?,
1138 const_object(&t.2, dict)?,
1139 );
1140 let score =
1141 3 * u32::from(sid.is_some()) + u32::from(pid.is_some()) + 3 * u32::from(oid.is_some());
1142 if score > 0 && best.is_none_or(|(b, _)| score > b) {
1143 best = Some((score, (sid, pid, oid)));
1144 }
1145 }
1146 best.map(|(_, pat)| pat)
1147}
1148
1149fn pattern_rows(
1152 ctx: &Ctx,
1153 index: &GraphIndex,
1154 t: &(SlotTerm, SlotTerm, SlotTerm),
1155) -> Option<(Vec<Row>, Vec<usize>)> {
1156 let slots = pattern_slots(t);
1157 let mut rel: Vec<Row> = Vec::new();
1158 let dict = ctx.rete.dictionary();
1159 let (sid, pid, oid) = (
1160 const_subject(&t.0, dict)?,
1161 const_predicate(&t.1)?,
1162 const_object(&t.2, dict)?,
1163 );
1164 for triple in canon_ahead(ctx, t, index.scan_iter((sid, pid, oid))) {
1167 if let Some(row) = triple_row(ctx, t, triple) {
1168 rel.push(row);
1169 }
1170 }
1171 Some((rel, slots))
1172}
1173
1174fn pattern_estimates(
1186 ctx: &Ctx,
1187 index: &GraphIndex,
1188 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1189 seed: &std::collections::HashSet<usize>,
1190) -> Option<Vec<f64>> {
1191 let pyr = ctx.rete.pyramid_if_loaded()?;
1194 let mut pred: std::collections::HashMap<u32, u64> = std::collections::HashMap::new();
1195 for e in &pyr.summary {
1196 *pred.entry(e.predicate).or_insert(0) += e.count as u64;
1197 }
1198 let stats: std::collections::HashMap<u32, &crate::meta::PredStat> = ctx
1205 .rete
1206 .planner_stats(true)
1207 .iter()
1208 .map(|s| (s.predicate, s))
1209 .collect();
1210 let graph_total = ctx.rete.index_triples(index).max(1) as f64;
1213 let total = graph_total;
1214 let num_preds = pred.len().max(1) as f64;
1215 const SEL_SUBJECT: f64 = 0.001;
1217 const SEL_OBJECT: f64 = 0.02;
1218 let node_bound = |t: &SlotTerm| match t {
1219 SlotTerm::Node(_) => true,
1220 SlotTerm::Var(v) => seed.contains(v),
1221 SlotTerm::Pred(_) => false,
1222 };
1223 Some(
1224 lowered
1225 .iter()
1226 .map(|t| {
1227 let (base, st) = match t.1 {
1232 SlotTerm::Pred(p) => {
1233 (*pred.get(&p).unwrap_or(&0) as f64, stats.get(&p).copied())
1234 }
1235 SlotTerm::Var(v) if seed.contains(&v) => (total / num_preds, None),
1236 _ => (total, None),
1237 };
1238 let mut est = base.min(graph_total).max(1.0);
1239 if node_bound(&t.0) {
1240 est *= match st {
1241 Some(s) if s.distinct_subjects > 0 => 1.0 / s.distinct_subjects as f64,
1242 _ => SEL_SUBJECT,
1243 };
1244 }
1245 if node_bound(&t.2) {
1246 est *= match st {
1247 Some(s) if s.distinct_objects > 0 => 1.0 / s.distinct_objects as f64,
1248 _ => SEL_OBJECT,
1249 };
1250 }
1251 est.max(1.0)
1252 })
1253 .collect(),
1254 )
1255}
1256
1257pub(crate) fn bgp_min_scan_bytes(
1264 ctx: &Ctx,
1265 index: &GraphIndex,
1266 patterns: &[TriplePattern],
1267) -> Option<u64> {
1268 let lowered = lower(patterns, ctx)?;
1269 lowered
1270 .iter()
1271 .map(|t| pattern_scan_bytes(ctx, index, t))
1272 .min()
1273}
1274
1275fn pattern_scan_bytes(ctx: &Ctx, index: &GraphIndex, t: &(SlotTerm, SlotTerm, SlotTerm)) -> u64 {
1292 let dict = ctx.rete.dictionary();
1293 match (
1294 const_subject(&t.0, dict),
1295 const_predicate(&t.1),
1296 const_object(&t.2, dict),
1297 ) {
1298 (Some(s), Some(p), Some(o)) => routed_scan_bytes(index, (s, p, o)),
1299 _ => 0,
1300 }
1301}
1302
1303pub(crate) fn routed_scan_bytes(index: &GraphIndex, pattern: Pattern) -> u64 {
1305 let sections = index.tile_sections();
1306 let mut best = u64::MAX;
1307 for perm in index.perms().iter() {
1311 let tiles = sections[perm.section_index()];
1312 best = best.min(match perm.order_pattern(pattern)[0] {
1315 Some(id) => tiles.routed_bytes(id),
1316 None => tiles.total_bytes(),
1317 });
1318 }
1319 best
1320}
1321
1322pub(crate) const FAT_SCAN_ROWS: f64 = (1u64 << 20) as f64;
1335
1336fn merge_seed_lopsided(
1341 ctx: &Ctx,
1342 index: &GraphIndex,
1343 ta: &(SlotTerm, SlotTerm, SlotTerm),
1344 tb: &(SlotTerm, SlotTerm, SlotTerm),
1345) -> bool {
1346 let est = tile_estimates(ctx, index, &[*ta, *tb], &std::collections::HashSet::new());
1347 let (lo, hi) = (est[0].min(est[1]), est[0].max(est[1]));
1348 hi >= FAT_SCAN_ROWS && hi / 4.0 >= lo
1349}
1350
1351fn selectivity_order(
1358 ctx: &Ctx,
1359 index: &GraphIndex,
1360 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1361) -> Vec<usize> {
1362 selectivity_order_seeded(ctx, index, lowered, &std::collections::HashSet::new())
1363}
1364
1365fn selectivity_order_seeded(
1369 ctx: &Ctx,
1370 index: &GraphIndex,
1371 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1372 seed: &std::collections::HashSet<usize>,
1373) -> Vec<usize> {
1374 let (estimates, per_class) = match pattern_estimates(ctx, index, lowered, seed) {
1382 Some(e) => (Some(e), false),
1383 None => (Some(tile_estimates(ctx, index, lowered, seed)), true),
1384 };
1385 let consts = |t: &(SlotTerm, SlotTerm, SlotTerm)| {
1386 [&t.0, &t.1, &t.2]
1387 .into_iter()
1388 .filter(|x| match x {
1389 SlotTerm::Var(v) => seed.contains(v),
1390 _ => true,
1391 })
1392 .count()
1393 };
1394 let vars = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Vec<usize> {
1395 [&t.0, &t.1, &t.2]
1396 .into_iter()
1397 .filter_map(|x| match x {
1398 SlotTerm::Var(v) => Some(*v),
1399 _ => None,
1400 })
1401 .collect()
1402 };
1403 let score = |i: usize| -> f64 {
1407 match &estimates {
1408 Some(e) => -e[i],
1409 None => consts(&lowered[i]) as f64,
1410 }
1411 };
1412 let type_pid = ctx.rete.dictionary().predicate_id(crate::file::RDF_TYPE);
1420 let is_class_enum = |i: usize, bound: &std::collections::HashSet<usize>| -> bool {
1421 let t = &lowered[i];
1422 !per_class
1423 && type_pid.is_some_and(|tp| matches!(t.1, SlotTerm::Pred(p) if p == tp))
1424 && matches!(t.2, SlotTerm::Node(_))
1425 && matches!(t.0, SlotTerm::Var(v) if !bound.contains(&v))
1426 };
1427 let n = lowered.len();
1428 let mut remaining: Vec<usize> = (0..n).collect();
1429 let mut order: Vec<usize> = Vec::with_capacity(n);
1430 let mut bound: std::collections::HashSet<usize> = seed.clone();
1431 while !remaining.is_empty() {
1432 let best = *remaining
1435 .iter()
1436 .max_by(|&&a, &&b| {
1437 let connected = |i: usize| vars(&lowered[i]).iter().any(|v| bound.contains(v));
1438 connected(a)
1439 .cmp(&connected(b))
1440 .then_with(|| is_class_enum(b, &bound).cmp(&is_class_enum(a, &bound)))
1441 .then_with(|| {
1442 score(a)
1443 .partial_cmp(&score(b))
1444 .unwrap_or(std::cmp::Ordering::Equal)
1445 })
1446 .then_with(|| b.cmp(&a))
1447 })
1448 .unwrap();
1449 for v in vars(&lowered[best]) {
1450 bound.insert(v);
1451 }
1452 order.push(best);
1453 remaining.retain(|&i| i != best);
1454 }
1455 order
1456}
1457
1458pub(crate) fn bgp_exists(ctx: &Ctx, index: &GraphIndex, patterns: &[TriplePattern]) -> bool {
1464 let dict = ctx.rete.dictionary();
1465 let Some(lowered) = lower(patterns, ctx) else {
1466 return false;
1467 };
1468 if let [t] = lowered.as_slice() {
1469 let names: Vec<usize> = [&t.0, &t.1, &t.2]
1473 .into_iter()
1474 .filter_map(|x| match x {
1475 SlotTerm::Var(v) => Some(*v),
1476 _ => None,
1477 })
1478 .collect();
1479 let distinct = names
1480 .iter()
1481 .enumerate()
1482 .all(|(i, v)| !names[i + 1..].contains(v));
1483 if distinct {
1484 return match (
1485 const_subject(&t.0, dict),
1486 const_predicate(&t.1),
1487 const_object(&t.2, dict),
1488 ) {
1489 (Some(s), Some(p), Some(o)) => index.scan_iter((s, p, o)).next().is_some(),
1490 _ => false,
1491 };
1492 }
1493 }
1494 !eval_bgp_rows(ctx, index, patterns).is_empty()
1495}
1496
1497pub(crate) struct BgpSolutions<'q> {
1508 scan: Option<Box<dyn Iterator<Item = Row> + 'q>>,
1509 prefix: Vec<Row>,
1510 buckets: HashMap<Vec<Val>, Vec<usize>>,
1512 shared: Vec<usize>,
1513 cartesian: bool,
1514 seed_only: bool,
1517 cur_scan: Option<Row>,
1518 matches: Vec<usize>,
1520 mi: usize,
1521}
1522
1523impl<'q> BgpSolutions<'q> {
1524 fn passthrough(rows: Box<dyn Iterator<Item = Row> + 'q>) -> Self {
1526 BgpSolutions {
1527 scan: Some(rows),
1528 prefix: Vec::new(),
1529 buckets: HashMap::new(),
1530 shared: Vec::new(),
1531 cartesian: false,
1532 seed_only: true,
1533 cur_scan: None,
1534 matches: Vec::new(),
1535 mi: 0,
1536 }
1537 }
1538
1539 fn streaming(
1548 ctx: &'q Ctx<'q>,
1549 index: &'q GraphIndex,
1550 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1551 order: &[usize],
1552 est: &[f64],
1553 ) -> Self {
1554 let (mut stream, mut bound, skip): (Box<dyn Iterator<Item = Row> + 'q>, Vec<usize>, usize) =
1555 match (est[order[1]] > limits().stream_seed)
1556 .then(|| merge_stream(ctx, index, lowered[order[0]], lowered[order[1]]))
1557 .flatten()
1558 {
1559 Some((m, slots)) => (m, slots, 2),
1560 None => {
1561 let t = lowered[order[0]];
1562 let Some(scan) = scan_rows(ctx, index, t) else {
1563 return Self::empty();
1564 };
1565 (Box::new(scan), pattern_slots(&t), 1)
1566 }
1567 };
1568 for &i in &order[skip..] {
1569 let t = lowered[i];
1570 let slots = pattern_slots(&t);
1571 let shared: Vec<usize> = slots
1572 .iter()
1573 .copied()
1574 .filter(|s| bound.contains(s))
1575 .collect();
1576 if !shared.is_empty() && est[i] > limits().hash_build {
1577 stream = Box::new(
1581 windowed(index, stream, bgp_probe_pattern(ctx, t))
1582 .flat_map(move |base| probe_rows(ctx, index, t, base)),
1583 );
1584 } else {
1585 let Some((rel, _)) = pattern_rows(ctx, index, &t) else {
1588 return Self::empty();
1589 };
1590 let mut table: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
1591 for r in rel {
1592 let key: Vec<Val> = shared.iter().map(|&s| r[s].clone().unwrap()).collect();
1593 table.entry(key).or_default().push(r);
1594 }
1595 let fill = slots.clone();
1596 stream = Box::new(stream.flat_map(move |base| {
1597 let key: Vec<Val> = shared.iter().map(|&s| base[s].clone().unwrap()).collect();
1598 let out: Vec<Row> = table
1599 .get(&key)
1600 .map(|rs| {
1601 rs.iter()
1602 .map(|r| {
1603 let mut row = base.clone();
1604 for &s in &fill {
1605 row[s] = r[s].clone();
1606 }
1607 row
1608 })
1609 .collect()
1610 })
1611 .unwrap_or_default();
1612 out.into_iter()
1613 }));
1614 }
1615 for s in slots {
1616 if !bound.contains(&s) {
1617 bound.push(s);
1618 }
1619 }
1620 }
1621 Self::passthrough(stream)
1622 }
1623
1624 fn empty() -> Self {
1626 BgpSolutions {
1627 scan: None,
1628 prefix: Vec::new(),
1629 buckets: HashMap::new(),
1630 shared: Vec::new(),
1631 cartesian: false,
1632 seed_only: false,
1633 cur_scan: None,
1634 matches: Vec::new(),
1635 mi: 0,
1636 }
1637 }
1638
1639 pub(crate) fn new(ctx: &'q Ctx<'q>, index: &'q GraphIndex, patterns: &[TriplePattern]) -> Self {
1640 if patterns.is_empty() {
1642 return BgpSolutions {
1643 scan: Some(Box::new(std::iter::once(ctx.slots.empty_row()))),
1644 prefix: vec![ctx.slots.empty_row()],
1645 buckets: HashMap::new(),
1646 shared: Vec::new(),
1647 cartesian: true,
1648 seed_only: true,
1649 cur_scan: None,
1650 matches: Vec::new(),
1651 mi: 0,
1652 };
1653 }
1654 let Some(lowered) = lower(patterns, ctx) else {
1656 return Self::empty();
1657 };
1658 let (order, scan_est) = plan_order(ctx, index, &lowered);
1661 if order.len() >= 2 && scan_est[order[0]] > limits().stream_seed {
1664 return Self::streaming(ctx, index, &lowered, &order, &scan_est);
1665 }
1666 let (&last_i, prefix_is) = order.split_last().unwrap();
1667 let prefix_pats: Vec<TriplePattern> =
1668 prefix_is.iter().map(|&i| patterns[i].clone()).collect();
1669 let prefix = eval_bgp_rows(ctx, index, &prefix_pats);
1670 if prefix.is_empty() {
1671 return Self::empty();
1672 }
1673
1674 let shared: Vec<usize> = pattern_slots(&lowered[last_i])
1678 .into_iter()
1679 .filter(|&s| prefix[0][s].is_some())
1680 .collect();
1681
1682 let class_probe = !shared.is_empty()
1691 && scan_est[last_i] >= limits().probe_floor
1692 && (prefix.len() as f64) <= scan_est[last_i]
1693 && is_unbound_class(ctx, &lowered[last_i], &shared);
1694 if !shared.is_empty() && (probe_beats_scan(prefix.len(), scan_est[last_i]) || class_probe) {
1695 let t = lowered[last_i];
1696 let stream = windowed(index, prefix.into_iter(), bgp_probe_pattern(ctx, t))
1697 .flat_map(move |base| probe_rows(ctx, index, t, base));
1698 return Self::passthrough(Box::new(stream));
1699 }
1700
1701 let Some(scan) = scan_rows(ctx, index, lowered[last_i]) else {
1703 return Self::empty();
1704 };
1705 let cartesian = shared.is_empty();
1706 let seed_only = prefix.len() == 1 && prefix[0].iter().all(Option::is_none);
1709 let mut buckets: HashMap<Vec<Val>, Vec<usize>> = HashMap::new();
1710 if !cartesian {
1711 for (i, r) in prefix.iter().enumerate() {
1712 let key: Vec<Val> = shared.iter().map(|&s| r[s].clone().unwrap()).collect();
1713 buckets.entry(key).or_default().push(i);
1714 }
1715 }
1716 BgpSolutions {
1717 scan: Some(Box::new(scan)),
1718 prefix,
1719 buckets,
1720 shared,
1721 cartesian,
1722 seed_only,
1723 cur_scan: None,
1724 matches: Vec::new(),
1725 mi: 0,
1726 }
1727 }
1728}
1729
1730impl Iterator for BgpSolutions<'_> {
1731 type Item = Row;
1732
1733 fn next(&mut self) -> Option<Row> {
1734 if self.seed_only {
1736 return self.scan.as_mut()?.next();
1737 }
1738 loop {
1739 if self.mi < self.matches.len() {
1741 let pi = self.matches[self.mi];
1742 self.mi += 1;
1743 let mut merged = self.prefix[pi].clone();
1744 for (slot, v) in self.cur_scan.as_ref().unwrap().iter().enumerate() {
1745 if v.is_some() {
1746 merged[slot] = v.clone();
1747 }
1748 }
1749 return Some(merged);
1750 }
1751 let s = self.scan.as_mut()?.next()?;
1754 self.matches.clear();
1755 if self.cartesian {
1756 self.matches.extend(0..self.prefix.len());
1757 } else {
1758 let key: Vec<Val> = self.shared.iter().map(|&i| s[i].clone().unwrap()).collect();
1759 if let Some(c) = self.buckets.get(&key) {
1760 self.matches.extend_from_slice(c);
1761 }
1762 }
1763 self.mi = 0;
1764 self.cur_scan = Some(s);
1765 }
1766 }
1767}
1768
1769#[allow(clippy::type_complexity)]
1777fn merge_stream<'q>(
1778 ctx: &'q Ctx<'q>,
1779 index: &'q GraphIndex,
1780 ta: (SlotTerm, SlotTerm, SlotTerm),
1781 tb: (SlotTerm, SlotTerm, SlotTerm),
1782) -> Option<(Box<dyn Iterator<Item = Row> + 'q>, Vec<usize>)> {
1783 let sa = pattern_slots(&ta);
1784 let sb = pattern_slots(&tb);
1785 let shared: Vec<usize> = sa.iter().copied().filter(|s| sb.contains(s)).collect();
1786 let [v] = shared[..] else {
1787 return None;
1788 };
1789 if !matches!(ta.0, SlotTerm::Var(i) if i == v) || !matches!(tb.0, SlotTerm::Var(i) if i == v) {
1790 return None;
1791 }
1792 let dict = ctx.rete.dictionary();
1793 let lower = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Option<Pattern> {
1794 Some((
1795 const_subject(&t.0, dict)?,
1796 const_predicate(&t.1)?,
1797 const_object(&t.2, dict)?,
1798 ))
1799 };
1800 let side = |t: (SlotTerm, SlotTerm, SlotTerm)| -> Option<KeyedRows<'q>> {
1801 let it = index.scan_iter_sorted_on(lower(&t)?, 0)?;
1802 let keyed: Box<dyn Iterator<Item = (u32, Row)> + 'q> =
1803 Box::new(it.filter_map(move |tri| triple_row(ctx, &t, tri).map(|r| (tri.0, r))));
1804 Some(keyed.peekable())
1805 };
1806 let a = side(ta)?;
1807 let b = side(tb)?;
1808 let mut slots = sa;
1809 for s in sb {
1810 if !slots.contains(&s) {
1811 slots.push(s);
1812 }
1813 }
1814 Some((
1815 Box::new(MergeStream {
1816 a,
1817 b,
1818 ra: Vec::new(),
1819 rb: Vec::new(),
1820 i: 0,
1821 j: 0,
1822 }),
1823 slots,
1824 ))
1825}
1826
1827type KeyedRows<'q> = std::iter::Peekable<Box<dyn Iterator<Item = (u32, Row)> + 'q>>;
1828
1829struct MergeStream<'q> {
1832 a: KeyedRows<'q>,
1833 b: KeyedRows<'q>,
1834 ra: Vec<Row>,
1835 rb: Vec<Row>,
1836 i: usize,
1837 j: usize,
1838}
1839
1840impl Iterator for MergeStream<'_> {
1841 type Item = Row;
1842
1843 fn next(&mut self) -> Option<Row> {
1844 loop {
1845 while self.i < self.ra.len() {
1846 if self.j < self.rb.len() {
1847 let j = self.j;
1848 self.j += 1;
1849 if let Some(m) = crate::row::merge_rows(&self.ra[self.i], &self.rb[j]) {
1850 return Some(m);
1851 }
1852 } else {
1853 self.i += 1;
1854 self.j = 0;
1855 }
1856 }
1857 let ka = self.a.peek()?.0;
1858 let kb = self.b.peek()?.0;
1859 match ka.cmp(&kb) {
1860 std::cmp::Ordering::Less => {
1861 self.a.next();
1862 }
1863 std::cmp::Ordering::Greater => {
1864 self.b.next();
1865 }
1866 std::cmp::Ordering::Equal => {
1867 self.ra.clear();
1868 self.rb.clear();
1869 while let Some((_, r)) = self.a.next_if(|(k, _)| *k == ka) {
1870 self.ra.push(r);
1871 }
1872 while let Some((_, r)) = self.b.next_if(|(k, _)| *k == ka) {
1873 self.rb.push(r);
1874 }
1875 self.i = 0;
1876 self.j = 0;
1877 }
1878 }
1879 }
1880 }
1881}
1882
1883fn probe_subject(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
1897 let dict = ctx.rete.dictionary();
1898 match t {
1899 SlotTerm::Node(n) => dict.node_as_subject_id(*n).map(Some),
1900 SlotTerm::Pred(_) => None,
1901 SlotTerm::Var(i) => match &base[*i] {
1902 None => Some(None),
1903 Some(Val::Id(v)) if *v >= 0 => dict.node_as_subject_id(*v as u32).map(Some),
1904 Some(_) => None,
1906 },
1907 }
1908}
1909
1910fn probe_object(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
1912 let dict = ctx.rete.dictionary();
1913 match t {
1914 SlotTerm::Node(n) => dict.node_as_object_id(*n).map(Some),
1915 SlotTerm::Pred(_) => None,
1916 SlotTerm::Var(i) => match &base[*i] {
1917 None => Some(None),
1918 Some(Val::Id(v)) if *v >= 0 => dict.node_as_object_id(*v as u32).map(Some),
1919 Some(_) => None,
1920 },
1921 }
1922}
1923
1924fn probe_predicate(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
1926 let dict = ctx.rete.dictionary();
1927 match t {
1928 SlotTerm::Pred(p) => Some(Some(*p)),
1929 SlotTerm::Node(_) => None,
1930 SlotTerm::Var(i) => match &base[*i] {
1931 None => Some(None),
1932 Some(Val::Id(v)) if *v < 0 => Some(Some((-v - 1) as u32)),
1933 Some(Val::Id(v)) => ctx
1935 .resolver
1936 .term(*v)
1937 .and_then(|t| dict.predicate_id(&t))
1938 .map(Some),
1939 Some(Val::Str(_)) => None,
1940 },
1941 }
1942}
1943
1944fn probe_rows<'q>(
1948 ctx: &'q Ctx<'q>,
1949 index: &'q GraphIndex,
1950 t: (SlotTerm, SlotTerm, SlotTerm),
1951 base: Row,
1952) -> Box<dyn Iterator<Item = Row> + 'q> {
1953 let (Some(sid), Some(pid), Some(oid)) = (
1954 probe_subject(ctx, &t.0, &base),
1955 probe_predicate(ctx, &t.1, &base),
1956 probe_object(ctx, &t.2, &base),
1957 ) else {
1958 return Box::new(std::iter::empty());
1959 };
1960 let dict = ctx.rete.dictionary();
1961 Box::new(
1964 canon_ahead(ctx, &t, index.scan_iter((sid, pid, oid))).filter_map(
1965 move |(s_id, p_id, o_id)| {
1966 let s_val = dict.subject_node(s_id) as i64;
1967 let p_val = pred_val(ctx, &t.1, p_id);
1968 let o_val = dict.object_node(o_id) as i64;
1969 let mut row = base.clone();
1970 for (term, val) in [(&t.0, s_val), (&t.1, p_val), (&t.2, o_val)] {
1971 if let SlotTerm::Var(i) = term {
1972 match row[*i] {
1973 Some(Val::Id(existing)) if existing != val => return None,
1974 Some(Val::Id(_)) => {}
1975 Some(Val::Str(_)) => return None,
1976 None => row[*i] = Some(Val::Id(val)),
1977 }
1978 }
1979 }
1980 Some(row)
1981 },
1982 ),
1983 )
1984}
1985
1986pub(crate) struct ProbePlan {
1988 pats: Vec<(SlotTerm, SlotTerm, SlotTerm)>,
1989}
1990
1991impl ProbePlan {
1992 pub(crate) fn new(
1996 ctx: &Ctx,
1997 index: &GraphIndex,
1998 patterns: &[TriplePattern],
1999 seed_mask: &[bool],
2000 ) -> Option<Self> {
2001 let lowered = lower(patterns, ctx)?;
2002 let seed: std::collections::HashSet<usize> = seed_mask
2003 .iter()
2004 .enumerate()
2005 .filter_map(|(i, b)| b.then_some(i))
2006 .collect();
2007 let order = selectivity_order_seeded(ctx, index, &lowered, &seed);
2008 Some(ProbePlan {
2009 pats: order.into_iter().map(|i| lowered[i]).collect(),
2010 })
2011 }
2012}
2013
2014pub(crate) struct ProbeJoin<'q> {
2017 ctx: &'q Ctx<'q>,
2018 index: &'q GraphIndex,
2019 pats: Vec<(SlotTerm, SlotTerm, SlotTerm)>,
2020 stack: Vec<Box<dyn Iterator<Item = Row> + 'q>>,
2021}
2022
2023impl<'q> ProbeJoin<'q> {
2024 pub(crate) fn new(
2027 ctx: &'q Ctx<'q>,
2028 index: &'q GraphIndex,
2029 patterns: &[TriplePattern],
2030 ) -> Option<Self> {
2031 let plan = ProbePlan::new(ctx, index, patterns, &vec![false; ctx.slots.len()])?;
2032 Some(Self::from_plan(ctx, index, &plan, ctx.slots.empty_row()))
2033 }
2034
2035 pub(crate) fn from_plan(
2037 ctx: &'q Ctx<'q>,
2038 index: &'q GraphIndex,
2039 plan: &ProbePlan,
2040 seed: Row,
2041 ) -> Self {
2042 let pats = plan.pats.clone();
2043 let first = probe_rows(ctx, index, pats[0], seed);
2044 ProbeJoin {
2045 ctx,
2046 index,
2047 pats,
2048 stack: vec![first],
2049 }
2050 }
2051}
2052
2053impl Iterator for ProbeJoin<'_> {
2054 type Item = Row;
2055
2056 fn next(&mut self) -> Option<Row> {
2057 loop {
2058 let depth = self.stack.len();
2059 match self.stack.last_mut()?.next() {
2060 Some(row) => {
2061 if depth == self.pats.len() {
2062 return Some(row);
2063 }
2064 let it = probe_rows(self.ctx, self.index, self.pats[depth], row);
2065 self.stack.push(it);
2066 }
2067 None => {
2068 self.stack.pop();
2069 if self.stack.is_empty() {
2070 return None;
2071 }
2072 }
2073 }
2074 }
2075 }
2076}
2077
2078fn hash_join(
2082 left: Vec<Row>,
2083 left_bound: &[usize],
2084 right: Vec<Row>,
2085 right_slots: &[usize],
2086) -> Vec<Row> {
2087 if left.len() == 1 && left_bound.is_empty() {
2089 return right;
2090 }
2091 if left.is_empty() || right.is_empty() {
2092 return Vec::new();
2093 }
2094 let shared: Vec<usize> = right_slots
2095 .iter()
2096 .copied()
2097 .filter(|s| left_bound.contains(s))
2098 .collect();
2099 let fill = |l: &Row, r: &Row| -> Row {
2100 let mut out = l.clone();
2101 for &s in right_slots {
2102 out[s] = r[s].clone();
2103 }
2104 out
2105 };
2106 if shared.is_empty() {
2107 let mut out = Vec::with_capacity(left.len() * right.len());
2111 for l in &left {
2112 for r in &right {
2113 out.push(fill(l, r));
2114 }
2115 }
2116 return out;
2117 }
2118 let key_of = |b: &Row| -> Vec<Val> { shared.iter().map(|&s| b[s].clone().unwrap()).collect() };
2119 let mut out = Vec::new();
2126 if right.len() <= left.len() {
2127 let mut buckets: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
2128 for r in right {
2129 buckets.entry(key_of(&r)).or_default().push(r);
2130 }
2131 for l in &left {
2132 if let Some(rs) = buckets.get(&key_of(l)) {
2133 for r in rs {
2134 out.push(fill(l, r));
2135 }
2136 }
2137 }
2138 } else {
2139 let mut buckets: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
2141 for l in left {
2142 buckets.entry(key_of(&l)).or_default().push(l);
2143 }
2144 for r in &right {
2145 if let Some(ls) = buckets.get(&key_of(r)) {
2146 for l in ls {
2147 let mut row = r.clone();
2148 for &s in left_bound {
2149 if let Some(v) = &l[s] {
2150 row[s] = Some(v.clone());
2151 }
2152 }
2153 out.push(row);
2154 }
2155 }
2156 }
2157 }
2158 out
2159}
2160
2161fn const_subject(t: &SlotTerm, d: &crate::Dictionary) -> Option<Option<u32>> {
2166 match t {
2167 SlotTerm::Node(n) => d.node_as_subject_id(*n).map(Some),
2168 SlotTerm::Pred(_) => None, SlotTerm::Var(_) => Some(None),
2170 }
2171}
2172
2173fn const_object(t: &SlotTerm, d: &crate::Dictionary) -> Option<Option<u32>> {
2174 match t {
2175 SlotTerm::Node(n) => d.node_as_object_id(*n).map(Some),
2176 SlotTerm::Pred(_) => None,
2177 SlotTerm::Var(_) => Some(None),
2178 }
2179}
2180
2181fn const_predicate(t: &SlotTerm) -> Option<Option<u32>> {
2182 match t {
2183 SlotTerm::Pred(p) => Some(Some(*p)),
2184 SlotTerm::Node(_) => None, SlotTerm::Var(_) => Some(None),
2186 }
2187}
2188
2189#[cfg(test)]
2190mod tests {
2191 use super::*;
2192 use crate::dictionary::DictionaryBuilder;
2193 use crate::file::write_file_v05 as write_file;
2194 use crate::index::GraphIndexBuilder;
2195
2196 fn rete_from(triples: &[(&str, &str, &str)]) -> Vec<u8> {
2197 let mut db = DictionaryBuilder::new();
2198 for (s, p, o) in triples {
2199 db.observe(s, p, o);
2200 }
2201 let dict = db.build();
2202 let mut ib = GraphIndexBuilder::new();
2203 for (s, p, o) in triples {
2204 ib.push(dict.encode(s, p, o).unwrap());
2205 }
2206 write_file(&dict, &ib.build(), false, &[], 0)
2207 }
2208
2209 fn pat(s: &str, p: &str, o: &str) -> TriplePattern {
2210 TriplePattern {
2211 s: PatternTerm::parse(s),
2212 p: PatternTerm::parse(p),
2213 o: PatternTerm::parse(o),
2214 }
2215 }
2216
2217 #[test]
2226 fn scan_bytes_route_a_literal_by_its_object_id() {
2227 let value = "<http://ex/value>";
2228 let owned: Vec<(String, String)> = (0..400)
2229 .map(|i| (format!("<http://ex/s{i:03}>"), format!("\"lit {i:03}\"")))
2230 .collect();
2231 let mut db = DictionaryBuilder::new();
2232 for (s, o) in &owned {
2233 db.observe(s, value, o);
2234 }
2235 let dict = db.build();
2236 let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2237 for (s, o) in &owned {
2238 ib.push(dict.encode(s, value, o).unwrap());
2239 }
2240 let rete = Rete::open(&write_file(&dict, &ib.build(), false, &[], 0)).unwrap();
2241 let index = rete.default_index();
2242 let whole = routed_scan_bytes(index, (None, rete.dictionary().predicate_id(value), None));
2244 for (_, lit) in owned.iter().step_by(57) {
2245 let q = [pat("?s", value, lit)];
2246 let mut slots = Slots::new();
2247 collect_pattern_slots(&q, &mut slots);
2248 let ctx = Ctx::new(&rete, slots);
2249 let got = bgp_min_scan_bytes(&ctx, index, &q).unwrap();
2250 assert!(got > 0, "{lit} routed to no tile");
2251 assert!(
2252 got < whole,
2253 "{lit} routed to the whole predicate ({got} of {whole})"
2254 );
2255 }
2256 }
2257
2258 #[test]
2264 fn plan_gates_do_not_move_with_the_compression() {
2265 let mut owned: Vec<(String, String, String)> = Vec::new();
2266 for i in 0..3000 {
2267 let s = format!("<http://ex/s{i}>");
2268 owned.push((
2269 s.clone(),
2270 "<http://ex/kind>".into(),
2271 format!("<http://ex/K{}>", i % 7),
2272 ));
2273 owned.push((s.clone(), "<http://ex/value>".into(), format!("\"v {i}\"")));
2274 if i % 50 == 0 {
2275 owned.push((s, "<http://ex/rare>".into(), "<http://ex/R>".into()));
2276 }
2277 }
2278 let mut db = DictionaryBuilder::new();
2279 for (s, p, o) in &owned {
2280 db.observe(s, p, o);
2281 }
2282 let dict = db.build();
2283 let mut ib = GraphIndexBuilder::new().with_tile_budget(1024);
2284 for (s, p, o) in &owned {
2285 ib.push(dict.encode(s, p, o).unwrap());
2286 }
2287 let bytes = write_file(&dict, &ib.build(), false, &[], 0);
2288 let leaked: &'static [u8] = Box::leak(bytes.clone().into_boxed_slice());
2289 let resident = Rete::open(&bytes).unwrap();
2290 let lazy = Rete::open_ranged_lazy(crate::reader::SliceReader::new(leaked)).unwrap();
2291 let shapes: Vec<Vec<TriplePattern>> = vec![
2292 vec![
2293 pat("?s", "<http://ex/rare>", "<http://ex/R>"),
2294 pat("?s", "<http://ex/value>", "?v"),
2295 ],
2296 vec![
2297 pat("?s", "<http://ex/kind>", "<http://ex/K3>"),
2298 pat("?s", "<http://ex/value>", "?v"),
2299 ],
2300 vec![
2301 pat("?s", "<http://ex/kind>", "?k"),
2302 pat("?s", "<http://ex/value>", "?v"),
2303 ],
2304 vec![
2305 pat("?s", "<http://ex/value>", "\"v 7\""),
2306 pat("?s", "<http://ex/kind>", "?k"),
2307 ],
2308 ];
2309 let decisions = |rete: &Rete| -> Vec<(Vec<u64>, bool, Option<u64>)> {
2310 shapes
2311 .iter()
2312 .map(|q| {
2313 let mut slots = Slots::new();
2314 collect_pattern_slots(q, &mut slots);
2315 let ctx = Ctx::new(rete, slots);
2316 let index = rete.default_index();
2317 let lowered = lower(q, &ctx).unwrap();
2318 let est = tile_estimates(&ctx, index, &lowered, &Default::default());
2319 let lopsided = merge_seed_lopsided(&ctx, index, &lowered[0], &lowered[1]);
2320 let min = bgp_min_estimate(&ctx, index, q).map(|e| e as u64);
2321 (est.iter().map(|e| *e as u64).collect(), lopsided, min)
2322 })
2323 .collect()
2324 };
2325 assert_eq!(decisions(&resident), decisions(&lazy));
2326 #[cfg(feature = "compression")]
2328 {
2329 let bytes_of = |rete: &Rete| {
2330 let q = &shapes[2];
2331 let mut slots = Slots::new();
2332 collect_pattern_slots(q, &mut slots);
2333 let ctx = Ctx::new(rete, slots);
2334 bgp_min_scan_bytes(&ctx, rete.default_index(), q)
2335 };
2336 assert_ne!(bytes_of(&resident), bytes_of(&lazy));
2337 }
2338 }
2339
2340 #[test]
2350 fn a_fat_predicate_estimates_alike_in_both_layouts() {
2351 let mut owned: Vec<(String, String, String)> = Vec::new();
2352 for i in 0..120_000 {
2353 let s = format!("<http://ex/s{i:06}>");
2354 owned.push((s.clone(), "<http://ex/kind>".into(), "<http://ex/K>".into()));
2355 owned.push((s, "<http://ex/value>".into(), format!("\"v {i}\"")));
2356 }
2357 let mut db = DictionaryBuilder::new();
2358 for (s, p, o) in &owned {
2359 db.observe(s, p, o);
2360 }
2361 let dict = db.build();
2362 let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2363 for (s, p, o) in &owned {
2364 ib.push(dict.encode(s, p, o).unwrap());
2365 }
2366 let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2367 let v6: &'static [u8] = Box::leak(
2368 crate::v06::write::convert_image(&v5, Default::default())
2369 .unwrap()
2370 .into_boxed_slice(),
2371 );
2372 let leaked5: &'static [u8] = Box::leak(v5.clone().into_boxed_slice());
2373 let flat = Rete::open_ranged_lazy(crate::reader::SliceReader::new(leaked5)).unwrap();
2374 let leafed = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v6)).unwrap();
2375 let q = [pat("?s", "<http://ex/value>", "?v")];
2376 let figures = |rete: &Rete| {
2377 let mut slots = Slots::new();
2378 collect_pattern_slots(&q, &mut slots);
2379 let ctx = Ctx::new(rete, slots);
2380 let index = rete.default_index();
2381 let total = bgp_total_estimate(&ctx, index, &q).unwrap();
2382 (total, probe_row_budget(total))
2383 };
2384 let (est5, budget5) = figures(&flat);
2385 let (est6, budget6) = figures(&leafed);
2386 assert!(est5 >= 70_000.0, "flat estimate {est5}");
2387 assert!(
2388 est6 >= est5 / 2.0 && est6 <= est5 * 2.0,
2389 "0x06 estimates {est6} where 0x05 estimates {est5}"
2390 );
2391 assert!(budget5.is_some_and(|b| b >= 1000), "{budget5:?}");
2393 assert!(budget6.is_some_and(|b| b >= 1000), "{budget6:?}");
2394 }
2395
2396 #[test]
2403 fn a_rare_object_of_a_fat_predicate_estimates_small_in_both_layouts() {
2404 let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2405 let mut owned: Vec<(String, String, String)> = Vec::new();
2406 for i in 0..120_000 {
2407 let s = format!("<http://ex/s{i:06}>");
2408 owned.push((s.clone(), ty.into(), "<http://ex/Common>".into()));
2409 owned.push((s.clone(), "<http://ex/other>".into(), format!("\"o {i}\"")));
2410 if i % 3000 == 0 {
2411 owned.push((s, ty.into(), "<http://ex/Rare>".into()));
2412 }
2413 }
2414 let mut db = DictionaryBuilder::new();
2415 for (s, p, o) in &owned {
2416 db.observe(s, p, o);
2417 }
2418 let dict = db.build();
2419 let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2420 for (s, p, o) in &owned {
2421 ib.push(dict.encode(s, p, o).unwrap());
2422 }
2423 let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2424 let v6: &'static [u8] = Box::leak(
2425 crate::v06::write::convert_image(&v5, Default::default())
2426 .unwrap()
2427 .into_boxed_slice(),
2428 );
2429 let leaked5: &'static [u8] = Box::leak(v5.into_boxed_slice());
2430 let figures = |rete: &Rete| {
2431 let est = |q: &[TriplePattern]| {
2432 let mut slots = Slots::new();
2433 collect_pattern_slots(q, &mut slots);
2434 let ctx = Ctx::new(rete, slots);
2435 bgp_min_estimate(&ctx, rete.default_index(), q).unwrap()
2436 };
2437 (
2438 est(&[pat("?s", ty, "<http://ex/Rare>")]),
2439 est(&[pat("?s", ty, "<http://ex/Common>")]),
2440 est(&[pat("?s", "<http://ex/other>", "?x")]),
2441 )
2442 };
2443 for (name, bytes) in [("0x05", leaked5), ("0x06", v6)] {
2444 let rete = Rete::open_ranged_lazy(crate::reader::SliceReader::new(bytes)).unwrap();
2445 let (rare, common, other) = figures(&rete);
2446 assert!(rare * 20.0 < other, "{name}: rare {rare} vs other {other}");
2447 assert!(
2448 rare * 20.0 < common,
2449 "{name}: rare {rare} vs common {common}"
2450 );
2451 }
2452 }
2453
2454 #[test]
2461 fn a_probe_prefetch_window_is_bounded_and_warm() {
2462 use crate::reader::{CountingReader, SliceReader};
2463 let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2464 let mut owned: Vec<(String, String, String)> = Vec::new();
2465 for i in 0..20_000 {
2466 let s = format!("<http://ex/s{i:06}>");
2467 owned.push((s.clone(), ty.into(), format!("<http://ex/C{}>", i % 7)));
2468 owned.push((s, "<http://ex/other>".into(), format!("\"o {}\"", i % 5000)));
2469 }
2470 let mut db = DictionaryBuilder::new();
2471 for (s, p, o) in &owned {
2472 db.observe(s, p, o);
2473 }
2474 let dict = db.build();
2475 let mut ib = GraphIndexBuilder::new().with_tile_budget(128);
2476 for (s, p, o) in &owned {
2477 ib.push(dict.encode(s, p, o).unwrap());
2478 }
2479 let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2480 let v6 = crate::v06::write::convert_image(&v5, Default::default()).unwrap();
2481 let leaked: &'static [u8] = Box::leak(v6.into_boxed_slice());
2482 let reader = std::sync::Arc::new(CountingReader::new(SliceReader::new(leaked)));
2483 let rete = Rete::open_ranged_lazy(reader.clone()).unwrap();
2484 let index = rete.default_index();
2485 index.set_cache_cap(1 << 20);
2488 let pats: Vec<Pattern> = (0..20_000)
2490 .step_by(3)
2491 .map(|i| {
2492 let (s, _, _) = dict
2493 .encode(&format!("<http://ex/s{i:06}>"), ty, "<http://ex/C0>")
2494 .unwrap();
2495 (Some(s), None, None)
2496 })
2497 .collect();
2498 let mut from = 0;
2499 let mut windows = 0;
2500 while from < pats.len() {
2501 let n = index.prefetch_probe_tiles(&pats[from..]);
2502 assert!(n >= 1, "a window always makes progress");
2503 assert!(
2504 n < pats.len() - from || windows > 0,
2505 "the first window is cut"
2506 );
2507 let before = reader.requests();
2508 for &p in &pats[from..from + n] {
2509 assert!(index.scan_iter(p).next().is_some());
2510 }
2511 assert_eq!(reader.requests(), before, "a covered probe reads nothing");
2512 from += n;
2513 windows += 1;
2514 }
2515 assert!(windows > 1, "{windows} window(s) for {} probes", pats.len());
2516 }
2517
2518 #[test]
2523 fn a_tile_span_is_the_same_in_both_layouts() {
2524 let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2525 let mut owned: Vec<(String, String, String)> = Vec::new();
2526 for i in 0..30_000 {
2527 let s = format!("<http://ex/s{i:06}>");
2528 owned.push((s.clone(), ty.into(), format!("<http://ex/C{}>", i % 7)));
2529 owned.push((s, "<http://ex/other>".into(), format!("\"o {}\"", i % 5000)));
2530 }
2531 let mut db = DictionaryBuilder::new();
2532 for (s, p, o) in &owned {
2533 db.observe(s, p, o);
2534 }
2535 let dict = db.build();
2536 let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2537 for (s, p, o) in &owned {
2538 ib.push(dict.encode(s, p, o).unwrap());
2539 }
2540 let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2541 let v6 = crate::v06::write::convert_image(&v5, Default::default()).unwrap();
2542 let (v5, v6): (&'static [u8], &'static [u8]) = (
2543 Box::leak(v5.into_boxed_slice()),
2544 Box::leak(v6.into_boxed_slice()),
2545 );
2546 let flat = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v5)).unwrap();
2547 let leafed = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v6)).unwrap();
2548 let (fi, li) = (flat.default_index(), leafed.default_index());
2549 let mut checked = 0;
2550 for perm in fi.perms().iter() {
2551 let si = perm.section_index();
2552 for a in (0..dict.term_count() + 2).step_by(97) {
2553 assert_eq!(
2554 fi.tile_span(si, Some(a)),
2555 li.tile_span(si, Some(a)),
2556 "section {si}, id {a}"
2557 );
2558 checked += 1;
2559 }
2560 assert_eq!(fi.tile_span(si, None), li.tile_span(si, None));
2561 }
2562 assert!(checked > 100);
2563 }
2564
2565 #[test]
2570 fn every_join_path_returns_the_same_solutions() {
2571 let mut owned: Vec<(String, String, String)> = Vec::new();
2572 let mut x: u64 = 7;
2573 let mut next = |m: u64| {
2574 x = x
2575 .wrapping_mul(6364136223846793005)
2576 .wrapping_add(1442695040888963407);
2577 (x >> 33) % m
2578 };
2579 for i in 0..60 {
2580 let s = format!("s{i}");
2581 owned.push((s.clone(), "a".into(), format!("C{}", next(3))));
2582 for p in 0..4 {
2583 for _ in 0..next(3) {
2584 owned.push((s.clone(), format!("p{p}"), format!("s{}", next(60))));
2585 }
2586 }
2587 }
2588 let triples: Vec<(&str, &str, &str)> = owned
2589 .iter()
2590 .map(|(s, p, o)| (s.as_str(), p.as_str(), o.as_str()))
2591 .collect();
2592 let bytes = rete_from(&triples);
2593 let rete = Rete::open(&bytes).unwrap();
2594 let queries: Vec<Vec<TriplePattern>> = vec![
2595 vec![pat("?s", "p0", "?a"), pat("?s", "p1", "?b")],
2596 vec![pat("?s", "a", "C1"), pat("?s", "p0", "?a")],
2597 vec![pat("?s", "p0", "?a"), pat("?a", "p2", "?b")],
2598 vec![pat("s5", "p0", "?a"), pat("?a", "?p", "?o")],
2599 vec![pat("?s", "p0", "?x"), pat("?s", "p1", "?x")],
2600 vec![
2601 pat("?s", "p3", "?o"),
2602 pat("?o", "a", "C0"),
2603 pat("?s", "p1", "?z"),
2604 ],
2605 vec![
2606 pat("?s", "p0", "?a"),
2607 pat("?s", "p1", "?b"),
2608 pat("?b", "p2", "?c"),
2609 ],
2610 ];
2611 let run = |limits: Option<PlanLimits>| -> Vec<Vec<Vec<(String, String)>>> {
2612 TEST_LIMITS.with(|c| c.set(limits));
2613 let out = queries
2614 .iter()
2615 .map(|q| {
2616 let mut slots = crate::row::Slots::new();
2617 collect_pattern_slots(q, &mut slots);
2618 let ctx = Ctx::new(&rete, slots);
2619 let mut rows: Vec<Vec<(String, String)>> =
2620 BgpSolutions::new(&ctx, rete.default_index(), q)
2621 .map(|r| row_to_binding(&ctx, &r).into_iter().collect())
2622 .collect();
2623 rows.sort();
2624 rows
2625 })
2626 .collect();
2627 TEST_LIMITS.with(|c| c.set(None));
2628 out
2629 };
2630 let reference = run(None);
2631 assert!(reference.iter().all(|r| !r.is_empty()), "{reference:?}");
2632 for (name, l) in [
2633 (
2634 "probe everything",
2635 PlanLimits {
2636 probe_floor: 0.0,
2637 stream_seed: f64::MAX,
2638 hash_build: f64::MAX,
2639 },
2640 ),
2641 (
2642 "stream + hash",
2643 PlanLimits {
2644 probe_floor: f64::MAX,
2645 stream_seed: 0.0,
2646 hash_build: f64::MAX,
2647 },
2648 ),
2649 (
2650 "stream + probe",
2651 PlanLimits {
2652 probe_floor: f64::MAX,
2653 stream_seed: 0.0,
2654 hash_build: 0.0,
2655 },
2656 ),
2657 (
2658 "stream, all paths",
2659 PlanLimits {
2660 probe_floor: 0.0,
2661 stream_seed: 0.0,
2662 hash_build: 30.0,
2663 },
2664 ),
2665 ] {
2666 assert_eq!(run(Some(l)), reference, "{name}");
2667 }
2668 }
2669
2670 #[test]
2671 fn single_pattern_binds_variable() {
2672 let bytes = rete_from(&[("Alice", "knows", "Bob"), ("Bob", "knows", "Carol")]);
2673 let rete = Rete::open(&bytes).unwrap();
2674 let sols = eval_bgp(&rete, &[pat("Alice", "knows", "?y")]);
2675 assert_eq!(sols.len(), 1);
2676 assert_eq!(sols[0]["y"], "Bob");
2677 }
2678
2679 #[test]
2680 fn two_hop_join_on_shared_variable() {
2681 let bytes = rete_from(&[
2683 ("Alice", "knows", "Bob"),
2684 ("Bob", "knows", "Carol"),
2685 ("Carol", "knows", "Dave"),
2686 ("Alice", "knows", "Eve"), ]);
2688 let rete = Rete::open(&bytes).unwrap();
2689 let sols = eval_bgp(&rete, &[pat("?x", "knows", "?y"), pat("?y", "knows", "?z")]);
2690 let mut got: Vec<_> = sols
2692 .iter()
2693 .map(|b| (b["x"].clone(), b["y"].clone(), b["z"].clone()))
2694 .collect();
2695 got.sort();
2696 assert_eq!(
2697 got,
2698 vec![
2699 ("Alice".into(), "Bob".into(), "Carol".into()),
2700 ("Bob".into(), "Carol".into(), "Dave".into()),
2701 ]
2702 );
2703 }
2704
2705 #[test]
2706 fn repeated_variable_within_pattern() {
2707 let bytes = rete_from(&[("Alice", "knows", "Bob"), ("Bob", "knows", "Bob")]);
2709 let rete = Rete::open(&bytes).unwrap();
2710 let sols = eval_bgp(&rete, &[pat("?x", "knows", "?x")]);
2711 assert_eq!(sols.len(), 1);
2712 assert_eq!(sols[0]["x"], "Bob");
2713 }
2714
2715 #[test]
2716 fn no_solutions_yields_empty() {
2717 let bytes = rete_from(&[("Alice", "knows", "Bob")]);
2718 let rete = Rete::open(&bytes).unwrap();
2719 assert!(eval_bgp(&rete, &[pat("Alice", "likes", "?y")]).is_empty());
2720 }
2721
2722 #[test]
2729 fn snowflake_type_and_adjacency_matches_reference() {
2730 const TYPE: &str = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2731 let mut triples: Vec<(String, String, String)> = Vec::new();
2732 for i in 0..60 {
2734 let s = format!("S{i}");
2735 triples.push((s.clone(), TYPE.into(), "Student".into()));
2736 triples.push((s.clone(), "takesCourse".into(), format!("c{}", i % 5)));
2737 triples.push((s, "takesCourse".into(), format!("c{}", (i + 1) % 5)));
2738 }
2739 for j in 0..5 {
2741 triples.push((format!("c{j}"), TYPE.into(), "Course".into()));
2742 }
2743 triples.push(("Prof".into(), "teacherOf".into(), "c0".into()));
2744 triples.push(("Prof".into(), "teacherOf".into(), "c2".into()));
2745
2746 let refs: Vec<(&str, &str, &str)> = triples
2747 .iter()
2748 .map(|(s, p, o)| (s.as_str(), p.as_str(), o.as_str()))
2749 .collect();
2750 let bytes = rete_from(&refs);
2751 let rete = Rete::open(&bytes).unwrap();
2752
2753 let got: std::collections::BTreeSet<(String, String)> = eval_bgp(
2754 &rete,
2755 &[
2756 pat("?x", TYPE, "Student"),
2757 pat("?y", TYPE, "Course"),
2758 pat("?x", "takesCourse", "?y"),
2759 pat("Prof", "teacherOf", "?y"),
2760 ],
2761 )
2762 .into_iter()
2763 .map(|b| (b["x"].clone(), b["y"].clone()))
2764 .collect();
2765
2766 let taught = ["c0", "c2"];
2768 let mut want = std::collections::BTreeSet::new();
2769 for i in 0..60 {
2770 for c in [i % 5, (i + 1) % 5] {
2771 let course = format!("c{c}");
2772 if taught.contains(&course.as_str()) {
2773 want.insert((format!("S{i}"), course));
2774 }
2775 }
2776 }
2777 assert_eq!(got, want, "snowflake join must match the brute-force set");
2778 assert!(!want.is_empty(), "sanity: the reference set is non-empty");
2779 }
2780
2781 #[test]
2786 fn merge_join_subject_star_cross_product() {
2787 let bytes = rete_from(&[
2788 ("x", "a", "a1"),
2789 ("x", "a", "a2"),
2790 ("x", "b", "b1"),
2791 ("x", "b", "b2"),
2792 ("y", "a", "a3"),
2793 ("y", "b", "b3"),
2794 ("z", "a", "a4"), ]);
2796 let rete = Rete::open(&bytes).unwrap();
2797 let mut got: Vec<(String, String, String)> =
2798 eval_bgp(&rete, &[pat("?x", "a", "?av"), pat("?x", "b", "?bv")])
2799 .iter()
2800 .map(|m| (m["x"].clone(), m["av"].clone(), m["bv"].clone()))
2801 .collect();
2802 got.sort();
2803 let mut want: Vec<(String, String, String)> = [
2804 ("x", "a1", "b1"),
2805 ("x", "a1", "b2"),
2806 ("x", "a2", "b1"),
2807 ("x", "a2", "b2"),
2808 ("y", "a3", "b3"),
2809 ]
2810 .into_iter()
2811 .map(|(a, b, c)| (a.to_string(), b.to_string(), c.to_string()))
2812 .collect();
2813 want.sort();
2814 assert_eq!(got, want, "same-role merge must equal the brute-force join");
2815 }
2816}