1use std::collections::{BTreeMap, HashMap};
18
19use crate::file::Rete;
20use crate::index::{GraphIndex, Pattern, ProbeBatch};
21use crate::row::{Ctx, Row, Slots, Val};
22use crate::triples::Triple;
23
24#[derive(Debug, Clone, PartialEq, Eq)]
26pub enum PatternTerm {
27 Var(String),
28 Const(String),
29}
30
31impl PatternTerm {
32 pub fn parse(token: &str) -> Self {
34 if let Some(name) = token.strip_prefix('?') {
35 PatternTerm::Var(name.to_string())
36 } else {
37 PatternTerm::Const(token.to_string())
38 }
39 }
40}
41
42#[derive(Debug, Clone)]
44pub struct TriplePattern {
45 pub s: PatternTerm,
46 pub p: PatternTerm,
47 pub o: PatternTerm,
48}
49
50pub type Binding = BTreeMap<String, String>;
52
53#[derive(Clone, Copy)]
64enum SlotTerm {
65 Var(usize),
66 Node(u32),
67 Pred(u32),
68}
69
70fn pred_tag(p: u32) -> i64 {
71 -(p as i64) - 1
72}
73
74pub(crate) fn collect_pattern_slots(patterns: &[TriplePattern], slots: &mut Slots) {
76 for p in patterns {
77 for t in [&p.s, &p.p, &p.o] {
78 if let PatternTerm::Var(v) = t {
79 slots.add(v);
80 }
81 }
82 }
83}
84
85fn lower(patterns: &[TriplePattern], ctx: &Ctx) -> Option<Vec<(SlotTerm, SlotTerm, SlotTerm)>> {
88 let dict = ctx.rete.dictionary();
89 let node = |t: &PatternTerm| -> Option<SlotTerm> {
90 match t {
91 PatternTerm::Var(v) => ctx.slots.slot(v).map(SlotTerm::Var),
92 PatternTerm::Const(c) => dict.node_of_term(c).map(SlotTerm::Node),
93 }
94 };
95 let pred = |t: &PatternTerm| -> Option<SlotTerm> {
96 match t {
97 PatternTerm::Var(v) => ctx.slots.slot(v).map(SlotTerm::Var),
98 PatternTerm::Const(c) => dict.predicate_id(c).map(SlotTerm::Pred),
99 }
100 };
101 let mut lowered = Vec::with_capacity(patterns.len());
102 for p in patterns {
103 lowered.push((node(&p.s)?, pred(&p.p)?, node(&p.o)?));
104 }
105 Some(lowered)
106}
107
108pub fn eval_bgp(rete: &Rete, patterns: &[TriplePattern]) -> Vec<Binding> {
111 let mut slots = Slots::new();
112 collect_pattern_slots(patterns, &mut slots);
113 let ctx = Ctx::new(rete, slots);
114 eval_bgp_rows(&ctx, rete.default_index(), patterns)
115 .into_iter()
116 .map(|row| row_to_binding(&ctx, &row))
117 .collect()
118}
119
120pub(crate) fn row_to_binding(ctx: &Ctx, row: &Row) -> Binding {
123 let mut b = Binding::new();
124 for (i, v) in row.iter().enumerate() {
125 if let Some(val) = v {
126 if let Some(t) = ctx.resolver.str_once(val) {
127 b.insert(ctx.slots.name(i).to_string(), t);
128 }
129 }
130 }
131 b
132}
133
134fn plan_order(
145 ctx: &Ctx,
146 index: &GraphIndex,
147 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
148) -> (Vec<usize>, Vec<f64>) {
149 if lowered.len() == 1 {
150 return (vec![0], vec![0.0]);
151 }
152 let order = selectivity_order(ctx, index, lowered);
153 let scan_est = tile_estimates(ctx, index, lowered, &std::collections::HashSet::new());
154 (order, scan_est)
155}
156
157pub(crate) fn eval_bgp_rows(ctx: &Ctx, index: &GraphIndex, patterns: &[TriplePattern]) -> Vec<Row> {
160 if patterns.is_empty() {
162 return vec![ctx.slots.empty_row()];
163 }
164 let Some(lowered) = lower(patterns, ctx) else {
166 return Vec::new();
167 };
168
169 let (order, scan_est) = plan_order(ctx, index, &lowered);
173 let mut rows: Vec<Row> = vec![ctx.slots.empty_row()];
174 let mut bound: Vec<usize> = Vec::new();
175 let mut merged: [bool; 2] = [false, false];
176
177 if order.len() >= 2 {
182 if let Some((rel, slots)) =
183 try_merge_join(ctx, index, &lowered[order[0]], &lowered[order[1]])
184 {
185 rows = rel;
186 bound = slots;
187 merged = [true, true];
188 }
189 }
190
191 for (k, &idx) in order.iter().enumerate() {
192 if k < 2 && merged[k] {
193 continue; }
195 let t = lowered[idx];
196 let shares_bound = pattern_slots(&t).iter().any(|s| bound.contains(s));
206 let do_probe = !bound.is_empty()
217 && shares_bound
218 && !rows.is_empty()
219 && (probe_beats_scan(rows.len(), scan_est[idx])
220 || if index.is_remote() {
221 rows.len() <= remote_probe_max(index)
222 && (rows.len() <= REMOTE_PROBE_MIN || !pattern_is_selective(&t))
223 } else {
224 rows.len() <= BGP_PROBE_THRESHOLD
225 });
226 if do_probe {
227 let taken = std::mem::take(&mut rows);
228 let mut next: Vec<Row> = Vec::with_capacity(taken.len());
235 for base in windowed(index, taken.into_iter(), bgp_probe_pattern(ctx, t)) {
236 next.extend(probe_rows(ctx, index, t, base));
237 }
238 rows = next;
239 } else {
240 let Some((rel, rel_slots)) = pattern_rows(ctx, index, &t) else {
241 return Vec::new();
242 };
243 rows = hash_join(rows, &bound, rel, &rel_slots);
244 }
245 for s in pattern_slots(&t) {
246 if !bound.contains(&s) {
247 bound.push(s);
248 }
249 }
250 if rows.is_empty() {
251 break;
252 }
253 }
254 rows
255}
256
257fn try_merge_join(
269 ctx: &Ctx,
270 index: &GraphIndex,
271 ta: &(SlotTerm, SlotTerm, SlotTerm),
272 tb: &(SlotTerm, SlotTerm, SlotTerm),
273) -> Option<(Vec<Row>, Vec<usize>)> {
274 let dict = ctx.rete.dictionary();
275 let sa = pattern_slots(ta);
276 let sb = pattern_slots(tb);
277 let shared: Vec<usize> = sa.iter().copied().filter(|s| sb.contains(s)).collect();
278 if shared.len() != 1 {
279 return None;
280 }
281 let v = shared[0];
282 let col_of = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Option<usize> {
283 [&t.0, &t.1, &t.2]
284 .iter()
285 .position(|x| matches!(x, SlotTerm::Var(i) if *i == v))
286 };
287 let ca = col_of(ta)?;
288 let cb = col_of(tb)?;
289 if ca != cb {
290 return None; }
292 if merge_seed_lopsided(ctx, index, ta, tb) {
302 return None;
303 }
304 let lower = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Option<Pattern> {
305 Some((
306 const_subject(&t.0, dict)?,
307 const_predicate(&t.1)?,
308 const_object(&t.2, dict)?,
309 ))
310 };
311 let collect = |t: &(SlotTerm, SlotTerm, SlotTerm), col: usize| -> Option<Vec<(u32, Row)>> {
314 let pat = lower(t)?;
315 let mut out = Vec::new();
316 for tri in canon_ahead(ctx, t, index.scan_iter_sorted_on(pat, col)?) {
317 if let Some(r) = triple_row(ctx, t, tri) {
318 out.push(([tri.0, tri.1, tri.2][col], r));
319 }
320 }
321 Some(out)
322 };
323 let rows_a = collect(ta, ca)?;
324 let rows_b = collect(tb, cb)?;
325
326 let mut out: Vec<Row> = Vec::new();
327 let (mut i, mut j) = (0usize, 0usize);
328 while i < rows_a.len() && j < rows_b.len() {
329 match rows_a[i].0.cmp(&rows_b[j].0) {
330 std::cmp::Ordering::Less => i += 1,
331 std::cmp::Ordering::Greater => j += 1,
332 std::cmp::Ordering::Equal => {
333 let key = rows_a[i].0;
334 let (i0, j0) = (i, j);
335 while i < rows_a.len() && rows_a[i].0 == key {
336 i += 1;
337 }
338 while j < rows_b.len() && rows_b[j].0 == key {
339 j += 1;
340 }
341 for (_, ra) in &rows_a[i0..i] {
342 for (_, rb) in &rows_b[j0..j] {
343 let mut row = ra.clone();
346 let mut ok = true;
347 for (slot, val) in rb.iter().enumerate() {
348 if let Some(val) = val {
349 match &row[slot] {
350 Some(existing) if existing != val => {
351 ok = false;
352 break;
353 }
354 _ => row[slot] = Some(val.clone()),
355 }
356 }
357 }
358 if ok {
359 out.push(row);
360 }
361 }
362 }
363 }
364 }
365 }
366 let mut slots = pattern_slots(ta);
367 for s in pattern_slots(tb) {
368 if !slots.contains(&s) {
369 slots.push(s);
370 }
371 }
372 Some((out, slots))
373}
374
375const BGP_PROBE_THRESHOLD: usize = 512;
383
384const PROBE_SCAN_FLOOR: f64 = 65_536.0;
389
390const PROBE_RATIO: f64 = 16.0;
395
396fn probe_beats_scan(rows: usize, scan_est: f64) -> bool {
399 scan_est >= limits().probe_floor && (rows as f64) * PROBE_RATIO <= scan_est
400}
401
402pub(crate) fn probe_row_budget(est: f64) -> Option<usize> {
407 (est >= limits().probe_floor).then(|| (est / PROBE_RATIO) as usize)
408}
409
410pub(crate) fn bgp_min_estimate(
414 ctx: &Ctx,
415 index: &GraphIndex,
416 patterns: &[TriplePattern],
417) -> Option<f64> {
418 let lowered = lower(patterns, ctx)?;
419 tile_estimates(ctx, index, &lowered, &std::collections::HashSet::new())
420 .into_iter()
421 .reduce(f64::min)
422}
423
424pub(crate) fn bgp_total_estimate(
432 ctx: &Ctx,
433 index: &GraphIndex,
434 patterns: &[TriplePattern],
435) -> Option<f64> {
436 let lowered = lower(patterns, ctx)?;
437 Some(
438 tile_estimates(ctx, index, &lowered, &std::collections::HashSet::new())
439 .into_iter()
440 .sum(),
441 )
442}
443
444fn is_unbound_class(ctx: &Ctx, t: &(SlotTerm, SlotTerm, SlotTerm), shared: &[usize]) -> bool {
447 let type_pid = ctx.rete.dictionary().predicate_id(crate::file::RDF_TYPE);
448 matches!(
449 t,
450 (SlotTerm::Var(x), SlotTerm::Pred(p), SlotTerm::Var(c))
451 if Some(*p) == type_pid && shared.contains(x) && !shared.contains(c) && x != c
452 )
453}
454
455fn fat_enough(est: f64) -> bool {
459 #[cfg(test)]
460 if TEST_LIMITS.with(|c| c.get()).is_some() {
461 return est >= limits().probe_floor;
462 }
463 est >= FAT_SCAN_ROWS
464}
465
466pub(crate) struct CorrelatedProbe {
473 plan: Option<ProbePlan>,
475 slots: Vec<usize>,
477}
478
479impl CorrelatedProbe {
480 pub(crate) fn new(
484 ctx: &Ctx,
485 index: &GraphIndex,
486 patterns: &[TriplePattern],
487 seed: &[bool],
488 ) -> Option<Self> {
489 if patterns.is_empty() {
490 return None;
491 }
492 let mut slots: Vec<usize> = Vec::new();
493 for p in patterns {
494 for t in [&p.s, &p.p, &p.o] {
495 if let PatternTerm::Var(v) = t {
496 if let Some(i) = ctx.slots.slot(v) {
497 if !slots.contains(&i) {
498 slots.push(i);
499 }
500 }
501 }
502 }
503 }
504 if !slots.iter().any(|&i| seed[i]) {
505 return None;
506 }
507 let Some(est) = bgp_min_estimate(ctx, index, patterns) else {
509 return Some(CorrelatedProbe { plan: None, slots });
510 };
511 if !fat_enough(est) {
512 return None;
513 }
514 Some(CorrelatedProbe {
515 plan: ProbePlan::new(ctx, index, patterns, seed),
516 slots,
517 })
518 }
519
520 pub(crate) fn shares(&self, row: &Row) -> bool {
522 self.slots.iter().any(|&i| row[i].is_some())
523 }
524
525 pub(crate) fn probe(&self, ctx: &Ctx, index: &GraphIndex, row: &Row) -> bool {
529 match &self.plan {
530 None => false,
531 Some(plan) => ProbeJoin::from_plan(ctx, index, plan, row.clone())
532 .next()
533 .is_some(),
534 }
535 }
536}
537
538#[cfg(test)]
541pub(crate) fn with_probe_floor<T>(floor: f64, f: impl FnOnce() -> T) -> T {
542 let saved = TEST_LIMITS.with(|c| c.get());
543 TEST_LIMITS.with(|c| {
544 c.set(Some(PlanLimits {
545 probe_floor: floor,
546 ..limits()
547 }))
548 });
549 let out = f();
550 TEST_LIMITS.with(|c| c.set(saved));
551 out
552}
553
554#[cfg(test)]
558#[allow(dead_code)]
559pub(crate) fn with_plan_limits<T>(
560 probe_floor: f64,
561 stream_seed: f64,
562 hash_build: f64,
563 f: impl FnOnce() -> T,
564) -> T {
565 let saved = TEST_LIMITS.with(|c| c.get());
566 TEST_LIMITS.with(|c| {
567 c.set(Some(PlanLimits {
568 probe_floor,
569 stream_seed,
570 hash_build,
571 }))
572 });
573 let out = f();
574 TEST_LIMITS.with(|c| c.set(saved));
575 out
576}
577
578#[derive(Clone, Copy)]
581struct PlanLimits {
582 probe_floor: f64,
583 stream_seed: f64,
584 hash_build: f64,
585}
586
587#[cfg(test)]
588thread_local! {
589 static TEST_LIMITS: std::cell::Cell<Option<PlanLimits>> = const { std::cell::Cell::new(None) };
590}
591
592fn limits() -> PlanLimits {
593 #[cfg(test)]
594 if let Some(l) = TEST_LIMITS.with(|c| c.get()) {
595 return l;
596 }
597 PlanLimits {
598 probe_floor: PROBE_SCAN_FLOOR,
599 stream_seed: STREAM_SEED_ROWS,
600 hash_build: HASH_BUILD_ROWS,
601 }
602}
603
604const STREAM_SEED_ROWS: f64 = (1u64 << 21) as f64;
612
613const HASH_BUILD_ROWS: f64 = (1u64 << 20) as f64;
616
617fn tile_estimates(
623 ctx: &Ctx,
624 index: &GraphIndex,
625 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
626 seed: &std::collections::HashSet<usize>,
627) -> Vec<f64> {
628 const SEL_SUBJECT: f64 = 0.001;
629 const SEL_OBJECT: f64 = 0.02;
630 const SEL_PREDICATE: f64 = 0.05;
631 let dict = ctx.rete.dictionary();
632 let total = ctx.rete.index_triples(index);
633 let seeded = |x: &SlotTerm| matches!(x, SlotTerm::Var(v) if seed.contains(v));
634 let needs_stats = lowered
642 .iter()
643 .any(|t| matches!(t.1, SlotTerm::Pred(_)) && (seeded(&t.0) || seeded(&t.2)));
644 let stats: std::collections::HashMap<u32, &crate::meta::PredStat> = if needs_stats {
645 ctx.rete
646 .planner_stats(true)
647 .iter()
648 .map(|s| (s.predicate, s))
649 .collect()
650 } else {
651 std::collections::HashMap::new()
652 };
653 let patterns: Vec<Pattern> = lowered
657 .iter()
658 .filter_map(|t| {
659 Some((
660 const_subject(&t.0, dict)?,
661 const_predicate(&t.1)?,
662 const_object(&t.2, dict)?,
663 ))
664 })
665 .collect();
666 index.prefault_estimate_leaves(&patterns);
667 lowered
668 .iter()
669 .map(|t| {
670 let (Some(s), Some(p), Some(o)) = (
671 const_subject(&t.0, dict),
672 const_predicate(&t.1),
673 const_object(&t.2, dict),
674 ) else {
675 return 0.0;
676 };
677 let mut est = index.estimate_matches((s, p, o), total);
678 if est == 0.0 {
679 return 0.0;
680 }
681 let st = match t.1 {
682 SlotTerm::Pred(pid) => stats.get(&pid).copied(),
683 _ => None,
684 };
685 if seeded(&t.0) {
686 est *= match st {
687 Some(st) if st.distinct_subjects > 0 => 1.0 / st.distinct_subjects as f64,
688 _ => SEL_SUBJECT,
689 };
690 }
691 if seeded(&t.1) {
692 est *= SEL_PREDICATE;
693 }
694 if seeded(&t.2) {
695 est *= match st {
696 Some(st) if st.distinct_objects > 0 => 1.0 / st.distinct_objects as f64,
697 _ => SEL_OBJECT,
698 };
699 }
700 est.max(1.0)
701 })
702 .collect()
703}
704
705const REMOTE_PROBE_MIN: usize = 8;
714const REMOTE_PROBE_MAX: usize = 1024;
715
716fn remote_probe_max(index: &GraphIndex) -> usize {
723 REMOTE_PROBE_MAX * index.read_concurrency().clamp(1, 16)
724}
725
726const WINDOW_START_ROWS: usize = 256;
729
730const WINDOW_MAX_ROWS: usize = 1 << 16;
734
735const WINDOW_CHUNK_ROWS: usize = 256;
738
739type ProbePattern<'a> = Box<dyn Fn(&Row) -> Option<Pattern> + 'a>;
741
742pub(crate) struct Windowed<'a> {
760 index: &'a GraphIndex,
761 upstream: Box<dyn Iterator<Item = Row> + 'a>,
762 pat_of: Option<ProbePattern<'a>>,
764 pending: std::collections::VecDeque<Row>,
766 ready: std::collections::VecDeque<Row>,
768 size: usize,
770}
771
772pub(crate) fn windowed<'a>(
774 index: &'a GraphIndex,
775 upstream: impl Iterator<Item = Row> + 'a,
776 pat_of: impl Fn(&Row) -> Option<Pattern> + 'a,
777) -> Windowed<'a> {
778 Windowed {
779 index,
780 upstream: Box::new(upstream),
781 pat_of: index.is_remote().then(|| {
782 let f: ProbePattern<'a> = Box::new(pat_of);
783 f
784 }),
785 pending: std::collections::VecDeque::new(),
786 ready: std::collections::VecDeque::new(),
787 size: WINDOW_START_ROWS,
788 }
789}
790
791impl Windowed<'_> {
792 fn refill(&mut self, pat_of: &dyn Fn(&Row) -> Option<Pattern>) {
794 let mut batch = ProbeBatch::default();
795 'window: while self.ready.len() < self.size {
796 let chunk = WINDOW_CHUNK_ROWS.min(self.size - self.ready.len());
797 while self.pending.len() < chunk {
798 match self.upstream.next() {
799 Some(r) => self.pending.push_back(r),
800 None => break,
801 }
802 }
803 if self.pending.is_empty() {
804 break;
805 }
806 let chunk = chunk.min(self.pending.len());
807 let pats: Vec<Pattern> = self.pending.iter().take(chunk).filter_map(pat_of).collect();
809 self.index.prefault_leaves(&pats);
810 for _ in 0..chunk {
811 if let Some(p) = pat_of(&self.pending[0]) {
812 if !self.index.probe_batch_add(&mut batch, p) {
813 break 'window; }
815 }
816 let row = self.pending.pop_front().expect("chunk rows are pending");
817 self.ready.push_back(row);
818 }
819 }
820 self.index.probe_batch_fault(batch);
821 self.size = (self.size * 4).min(WINDOW_MAX_ROWS);
822 }
823}
824
825impl Iterator for Windowed<'_> {
826 type Item = Row;
827
828 fn next(&mut self) -> Option<Row> {
829 let Some(pat_of) = self.pat_of.take() else {
831 return self.upstream.next();
832 };
833 if self.ready.is_empty() {
834 self.refill(pat_of.as_ref());
835 }
836 self.pat_of = Some(pat_of);
837 self.ready.pop_front()
838 }
839}
840
841fn bgp_probe_pattern<'a>(
845 ctx: &'a Ctx<'_>,
846 t: (SlotTerm, SlotTerm, SlotTerm),
847) -> impl Fn(&Row) -> Option<Pattern> + 'a {
848 move |base| match (
849 probe_subject(ctx, &t.0, base),
850 probe_predicate(ctx, &t.1, base),
851 probe_object(ctx, &t.2, base),
852 ) {
853 (Some(s), Some(p), Some(o)) => Some((s, p, o)),
854 _ => None,
855 }
856}
857
858pub(crate) fn plan_windowed<'q>(
866 ctx: &'q Ctx<'q>,
867 index: &'q GraphIndex,
868 plan: &ProbePlan,
869 rows: Box<dyn Iterator<Item = Row> + 'q>,
870) -> Box<dyn Iterator<Item = Row> + 'q> {
871 let Some(&t) = plan.pats.first() else {
872 return rows;
873 };
874 if !index.is_remote() {
875 return rows;
876 }
877 let pat = bgp_probe_pattern(ctx, t);
878 let mut win = windowed(index, rows, move |base| {
879 pat(base).filter(|(s, _, o)| s.is_some() || o.is_some())
880 });
881 if let Some(demand) = ctx.limit_hint.get() {
886 win.size = win.size.min(demand.max(1));
887 }
888 Box::new(win)
889}
890
891pub(crate) fn prefetch_subject_probes(
897 ctx: &Ctx,
898 index: &GraphIndex,
899 patterns: &[TriplePattern],
900 sv: &str,
901 subject_ids: &[u32],
902) {
903 if !index.is_remote() {
904 return;
905 }
906 let Some(lowered) = lower(patterns, ctx) else {
907 return;
908 };
909 let Some(slot) = ctx.slots.slot(sv) else {
910 return;
911 };
912 let dict = ctx.rete.dictionary();
913 let mut pats: Vec<Pattern> = Vec::new();
914 for &sid in subject_ids {
915 let mut base = ctx.slots.empty_row();
916 base[slot] = Some(Val::Id(dict.subject_node(sid) as i64));
917 for t in &lowered {
918 if !matches!(t.0, SlotTerm::Var(i) if i == slot) {
919 continue;
920 }
921 if let (Some(s), Some(p), Some(o)) = (
922 probe_subject(ctx, &t.0, &base),
923 probe_predicate(ctx, &t.1, &base),
924 probe_object(ctx, &t.2, &base),
925 ) {
926 pats.push((s, p, o));
927 }
928 }
929 }
930 index.prefetch_probe_tiles(&pats);
931}
932
933fn pattern_is_selective(t: &(SlotTerm, SlotTerm, SlotTerm)) -> bool {
936 matches!(t.0, SlotTerm::Node(_)) || matches!(t.2, SlotTerm::Node(_))
937}
938
939fn pattern_slots(t: &(SlotTerm, SlotTerm, SlotTerm)) -> Vec<usize> {
941 let mut slots: Vec<usize> = Vec::new();
942 for term in [&t.0, &t.1, &t.2] {
943 if let SlotTerm::Var(i) = term {
944 if !slots.contains(i) {
945 slots.push(*i);
946 }
947 }
948 }
949 slots
950}
951
952const CANON_AHEAD: usize = 64;
955
956fn canon_ahead<'a, 'c>(
966 ctx: &'a Ctx<'c>,
967 t: &(SlotTerm, SlotTerm, SlotTerm),
968 triples: impl Iterator<Item = Triple> + 'a,
969) -> Box<dyn Iterator<Item = Triple> + 'a> {
970 if !matches!(t.1, SlotTerm::Var(_)) || !ctx.rete.dictionary().faults_chunks() {
971 return Box::new(triples);
972 }
973 let decoded = |term: &SlotTerm| match term {
976 SlotTerm::Var(i) => ctx.decodes_slot(*i),
977 _ => false,
978 };
979 Box::new(CanonAhead {
980 ctx,
981 triples,
982 run: std::collections::VecDeque::new(),
983 decode: (decoded(&t.0), decoded(&t.2)),
984 ahead: 0,
985 })
986}
987
988struct CanonAhead<'a, 'c, I> {
989 ctx: &'a Ctx<'c>,
990 triples: I,
991 run: std::collections::VecDeque<Triple>,
992 decode: (bool, bool),
994 ahead: usize,
997}
998
999impl<I: Iterator<Item = Triple>> Iterator for CanonAhead<'_, '_, I> {
1000 type Item = Triple;
1001
1002 fn next(&mut self) -> Option<Triple> {
1003 if self.run.is_empty() {
1004 self.run.extend(self.triples.by_ref().take(CANON_AHEAD));
1005 let preds: Vec<u32> = self.run.iter().map(|t| t.1).collect();
1006 let dict = self.ctx.rete.dictionary();
1011 let take = self
1012 .ctx
1013 .decode_rows()
1014 .saturating_sub(self.ahead)
1015 .min(self.run.len());
1016 self.ahead += take;
1017 let mut nodes: Vec<u32> = Vec::new();
1018 for t in self.run.iter().take(take) {
1019 if self.decode.0 {
1020 nodes.push(dict.subject_node(t.0));
1021 }
1022 if self.decode.1 {
1023 nodes.push(dict.object_node(t.2));
1024 }
1025 }
1026 self.ctx.resolver.prefetch_canon(&preds, &nodes);
1027 }
1028 self.run.pop_front()
1029 }
1030}
1031
1032fn pred_val(ctx: &Ctx, slot: &SlotTerm, p_id: u32) -> i64 {
1039 match slot {
1040 SlotTerm::Var(_) => ctx.resolver.canon_id(pred_tag(p_id)),
1041 _ => pred_tag(p_id),
1042 }
1043}
1044
1045fn triple_row(
1049 ctx: &Ctx,
1050 t: &(SlotTerm, SlotTerm, SlotTerm),
1051 (s_id, p_id, o_id): (u32, u32, u32),
1052) -> Option<Row> {
1053 crate::guard::check();
1055 let dict = ctx.rete.dictionary();
1056 let s_val = dict.subject_node(s_id) as i64;
1057 let p_val = pred_val(ctx, &t.1, p_id);
1058 let o_val = dict.object_node(o_id) as i64;
1059 let mut row = ctx.slots.empty_row();
1060 for (term, val) in [(&t.0, s_val), (&t.1, p_val), (&t.2, o_val)] {
1061 if let SlotTerm::Var(i) = term {
1062 match row[*i] {
1063 Some(Val::Id(existing)) if existing != val => return None,
1064 Some(_) => {}
1065 None => row[*i] = Some(Val::Id(val)),
1066 }
1067 }
1068 }
1069 Some(row)
1070}
1071
1072fn scan_rows<'q>(
1077 ctx: &'q Ctx<'q>,
1078 index: &'q GraphIndex,
1079 t: (SlotTerm, SlotTerm, SlotTerm),
1080) -> Option<impl Iterator<Item = Row> + 'q> {
1081 let dict = ctx.rete.dictionary();
1082 let (sid, pid, oid) = (
1083 const_subject(&t.0, dict)?,
1084 const_predicate(&t.1)?,
1085 const_object(&t.2, dict)?,
1086 );
1087 Some(
1088 canon_ahead(ctx, &t, index.scan_iter((sid, pid, oid)))
1089 .filter_map(move |triple| triple_row(ctx, &t, triple)),
1090 )
1091}
1092
1093struct SharedPrefix {
1097 rows: Vec<Row>,
1098 buckets: HashMap<Vec<Val>, Vec<usize>>,
1100 shared: Vec<usize>,
1101}
1102
1103type SharedTable = Option<HashMap<Vec<Val>, Vec<Row>>>;
1106
1107pub(crate) fn shard_bgp_rows<'q>(
1127 ctx: &'q Ctx<'q>,
1128 index: &'q GraphIndex,
1129 patterns: &[TriplePattern],
1130 part: crate::row::ShardPart,
1131) -> Option<Box<dyn Iterator<Item = Row> + 'q>> {
1132 if patterns.is_empty() {
1133 return None;
1134 }
1135 let lowered = lower(patterns, ctx)?;
1136 let node = part.0;
1137 let dict = ctx.rete.dictionary();
1138 let cut_scan =
1140 |t: (SlotTerm, SlotTerm, SlotTerm)| -> Option<Box<dyn Iterator<Item = Row> + 'q>> {
1141 let (sid, pid, oid) = (
1142 const_subject(&t.0, dict)?,
1143 const_predicate(&t.1)?,
1144 const_object(&t.2, dict)?,
1145 );
1146 let cut = |start: usize, end: usize| ctx.shard.applied(part, start, end);
1147 let triples = index.scan_iter_cut((sid, pid, oid), &cut);
1148 Some(Box::new(
1149 canon_ahead(ctx, &t, triples).filter_map(move |triple| triple_row(ctx, &t, triple)),
1150 ))
1151 };
1152 if lowered.len() == 1 {
1153 return cut_scan(lowered[0]);
1154 }
1155 let (order, est) = plan_order(ctx, index, &lowered);
1156
1157 if est[order[0]] > limits().stream_seed {
1159 let seed = lowered[order[0]];
1160 let merged = est[order[1]] > limits().stream_seed
1164 && merge_stream(ctx, index, seed, lowered[order[1]], None).is_some();
1165 let (mut stream, mut bound, skip) = if merged {
1166 let n = part.2.max(1);
1167 let pat = (
1168 const_subject(&seed.0, dict)?,
1169 const_predicate(&seed.1)?,
1170 const_object(&seed.2, dict)?,
1171 );
1172 let cuts = ctx
1174 .shard
1175 .shared(node, 1_000_000 + n, || index.sorted_cuts(pat, 0, n));
1176 let (cuts, tiles) = (*cuts).as_ref()?;
1177 let _ = ctx.shard.applied(part, 0, *tiles);
1178 let i = part.1;
1179 let lo = if i == 0 {
1180 0
1181 } else {
1182 cuts.get(i - 1).copied().unwrap_or(u32::MAX)
1183 };
1184 let hi = match cuts.get(i) {
1185 Some(&c) => u64::from(c),
1186 None if i >= cuts.len() => u64::MAX,
1188 None => 0,
1189 };
1190 let (lo, hi) = if i > cuts.len() { (0, 0) } else { (lo, hi) };
1193 let (stream, slots) =
1194 merge_stream(ctx, index, seed, lowered[order[1]], Some((lo, hi)))?;
1195 (stream, slots, 2)
1196 } else {
1197 (cut_scan(seed)?, pattern_slots(&seed), 1)
1198 };
1199 for &i in &order[skip..] {
1200 let t = lowered[i];
1201 let slots = pattern_slots(&t);
1202 let shared: Vec<usize> = slots
1203 .iter()
1204 .copied()
1205 .filter(|s| bound.contains(s))
1206 .collect();
1207 if !shared.is_empty() && est[i] > limits().hash_build {
1208 stream = Box::new(
1209 windowed(index, stream, bgp_probe_pattern(ctx, t))
1210 .flat_map(move |base| probe_rows(ctx, index, t, base)),
1211 );
1212 } else {
1213 let key_slots = shared.clone();
1214 let table = ctx.shard.shared(node, 1 + i, || -> SharedTable {
1215 let (rel, _) = pattern_rows(ctx, index, &t)?;
1216 let mut table: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
1217 for r in rel {
1218 let key: Vec<Val> =
1219 key_slots.iter().map(|&s| r[s].clone().unwrap()).collect();
1220 table.entry(key).or_default().push(r);
1221 }
1222 Some(table)
1223 });
1224 if table.is_none() {
1225 return Some(Box::new(std::iter::empty()));
1227 }
1228 let fill = slots.clone();
1229 stream = Box::new(stream.flat_map(move |base| {
1230 let key: Vec<Val> = shared.iter().map(|&s| base[s].clone().unwrap()).collect();
1231 let out: Vec<Row> = (*table)
1232 .as_ref()
1233 .and_then(|t| t.get(&key))
1234 .map(|rs| {
1235 rs.iter()
1236 .map(|r| {
1237 let mut row = base.clone();
1238 for &s in &fill {
1239 row[s] = r[s].clone();
1240 }
1241 row
1242 })
1243 .collect()
1244 })
1245 .unwrap_or_default();
1246 out.into_iter()
1247 }));
1248 }
1249 for s in slots {
1250 if !bound.contains(&s) {
1251 bound.push(s);
1252 }
1253 }
1254 }
1255 return Some(stream);
1256 }
1257
1258 let (&last_i, prefix_is) = order.split_last()?;
1260 let last = lowered[last_i];
1261 let last_pat = (
1264 const_subject(&last.0, dict)?,
1265 const_predicate(&last.1)?,
1266 const_object(&last.2, dict)?,
1267 );
1268 if index.scan_plan(last_pat).tiles_routed < 2 {
1269 return None;
1270 }
1271 let prefix = ctx.shard.shared(node, 0, || {
1272 let prefix_pats: Vec<TriplePattern> =
1273 prefix_is.iter().map(|&i| patterns[i].clone()).collect();
1274 let rows = eval_bgp_rows(ctx, index, &prefix_pats);
1275 let shared: Vec<usize> = match rows.first() {
1276 Some(first) => pattern_slots(&last)
1277 .into_iter()
1278 .filter(|&s| first[s].is_some())
1279 .collect(),
1280 None => Vec::new(),
1281 };
1282 let mut buckets: HashMap<Vec<Val>, Vec<usize>> = HashMap::new();
1283 if !shared.is_empty() {
1284 for (i, r) in rows.iter().enumerate() {
1285 let key: Vec<Val> = shared.iter().map(|&s| r[s].clone().unwrap()).collect();
1286 buckets.entry(key).or_default().push(i);
1287 }
1288 }
1289 SharedPrefix {
1290 rows,
1291 buckets,
1292 shared,
1293 }
1294 });
1295 if prefix.rows.is_empty() {
1296 return None;
1297 }
1298 let shared = &prefix.shared;
1299 let class_probe = !shared.is_empty()
1300 && est[last_i] >= limits().probe_floor
1301 && (prefix.rows.len() as f64) <= est[last_i]
1302 && is_unbound_class(ctx, &last, shared);
1303 if !shared.is_empty() && (probe_beats_scan(prefix.rows.len(), est[last_i]) || class_probe) {
1304 let (lo, hi) = ctx.shard.applied_rows(part, prefix.rows.len());
1306 let mine: Vec<Row> = prefix.rows[lo..hi].to_vec();
1307 return Some(Box::new(
1308 windowed(index, mine.into_iter(), bgp_probe_pattern(ctx, last))
1309 .flat_map(move |base| probe_rows(ctx, index, last, base)),
1310 ));
1311 }
1312 let scan = cut_scan(last)?;
1314 let mut matches: Vec<usize> = Vec::new();
1315 Some(Box::new(scan.flat_map(move |s| {
1316 matches.clear();
1317 if prefix.shared.is_empty() {
1318 matches.extend(0..prefix.rows.len());
1319 } else {
1320 let key: Vec<Val> = prefix
1321 .shared
1322 .iter()
1323 .map(|&i| s[i].clone().unwrap())
1324 .collect();
1325 if let Some(c) = prefix.buckets.get(&key) {
1326 matches.extend_from_slice(c);
1327 }
1328 }
1329 let out: Vec<Row> = matches
1330 .iter()
1331 .map(|&pi| {
1332 let mut merged = prefix.rows[pi].clone();
1333 for (slot, v) in s.iter().enumerate() {
1334 if v.is_some() {
1335 merged[slot] = v.clone();
1336 }
1337 }
1338 merged
1339 })
1340 .collect();
1341 out.into_iter()
1342 })))
1343}
1344
1345pub(crate) fn quad_scan_rows<'q>(
1352 ctx: &'q Ctx<'q>,
1353 patterns: &[TriplePattern],
1354 gslot: usize,
1355 part: Option<crate::row::ShardPart>,
1356) -> Option<Box<dyn Iterator<Item = Row> + 'q>> {
1357 let [p] = patterns else {
1358 return None;
1359 };
1360 if [&p.s, &p.p, &p.o]
1361 .iter()
1362 .any(|t| matches!(t, PatternTerm::Var(v) if ctx.slots.slot(v) == Some(gslot)))
1363 {
1364 return None;
1365 }
1366 let dict = ctx.rete.dictionary();
1367 let Some(lowered) = lower(patterns, ctx) else {
1368 return Some(Box::new(std::iter::empty()));
1369 };
1370 let t = lowered[0];
1371 let (Some(sid), Some(pid), Some(oid)) = (
1372 const_subject(&t.0, dict),
1373 const_predicate(&t.1),
1374 const_object(&t.2, dict),
1375 ) else {
1376 return Some(Box::new(std::iter::empty()));
1377 };
1378 let mut scan = ctx.rete.named_quad_scan((sid, pid, oid))?;
1379 if let Some(part) = part {
1382 let (start, end) = scan.tile_range();
1383 let (lo, hi) = ctx.shard.applied(part, start, end);
1384 scan.restrict(lo, hi);
1385 }
1386 Some(Box::new(scan.filter_map(move |(g, triple)| {
1387 let mut row = triple_row(ctx, &t, triple)?;
1388 row[gslot] = Some(Val::Id(dict.subject_node(g) as i64));
1389 Some(row)
1390 })))
1391}
1392
1393mod class_probe;
1394pub(crate) use class_probe::class_probe_rows;
1395pub use class_probe::set_class_route;
1396
1397pub(crate) type ScanPattern = (Option<u32>, Option<u32>, Option<u32>);
1399
1400pub(crate) fn driver_pattern(ctx: &Ctx, patterns: &[TriplePattern]) -> Option<ScanPattern> {
1405 let dict = ctx.rete.dictionary();
1406 let lowered = lower(patterns, ctx)?;
1407 let mut best: Option<(u32, ScanPattern)> = None;
1408 for t in &lowered {
1409 let (sid, pid, oid) = (
1410 const_subject(&t.0, dict)?,
1411 const_predicate(&t.1)?,
1412 const_object(&t.2, dict)?,
1413 );
1414 let score =
1415 3 * u32::from(sid.is_some()) + u32::from(pid.is_some()) + 3 * u32::from(oid.is_some());
1416 if score > 0 && best.is_none_or(|(b, _)| score > b) {
1417 best = Some((score, (sid, pid, oid)));
1418 }
1419 }
1420 best.map(|(_, pat)| pat)
1421}
1422
1423fn pattern_rows(
1426 ctx: &Ctx,
1427 index: &GraphIndex,
1428 t: &(SlotTerm, SlotTerm, SlotTerm),
1429) -> Option<(Vec<Row>, Vec<usize>)> {
1430 let slots = pattern_slots(t);
1431 let mut rel: Vec<Row> = Vec::new();
1432 let dict = ctx.rete.dictionary();
1433 let (sid, pid, oid) = (
1434 const_subject(&t.0, dict)?,
1435 const_predicate(&t.1)?,
1436 const_object(&t.2, dict)?,
1437 );
1438 for triple in canon_ahead(ctx, t, index.scan_iter((sid, pid, oid))) {
1441 if let Some(row) = triple_row(ctx, t, triple) {
1442 rel.push(row);
1443 }
1444 }
1445 Some((rel, slots))
1446}
1447
1448fn pattern_estimates(
1460 ctx: &Ctx,
1461 index: &GraphIndex,
1462 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1463 seed: &std::collections::HashSet<usize>,
1464) -> Option<Vec<f64>> {
1465 let pyr = ctx.rete.pyramid_if_loaded()?;
1468 let mut pred: std::collections::HashMap<u32, u64> = std::collections::HashMap::new();
1469 for e in &pyr.summary {
1470 *pred.entry(e.predicate).or_insert(0) += e.count as u64;
1471 }
1472 let stats: std::collections::HashMap<u32, &crate::meta::PredStat> = ctx
1479 .rete
1480 .planner_stats(true)
1481 .iter()
1482 .map(|s| (s.predicate, s))
1483 .collect();
1484 let graph_total = ctx.rete.index_triples(index).max(1) as f64;
1487 let total = graph_total;
1488 let num_preds = pred.len().max(1) as f64;
1489 const SEL_SUBJECT: f64 = 0.001;
1491 const SEL_OBJECT: f64 = 0.02;
1492 let node_bound = |t: &SlotTerm| match t {
1493 SlotTerm::Node(_) => true,
1494 SlotTerm::Var(v) => seed.contains(v),
1495 SlotTerm::Pred(_) => false,
1496 };
1497 Some(
1498 lowered
1499 .iter()
1500 .map(|t| {
1501 let (base, st) = match t.1 {
1506 SlotTerm::Pred(p) => {
1507 (*pred.get(&p).unwrap_or(&0) as f64, stats.get(&p).copied())
1508 }
1509 SlotTerm::Var(v) if seed.contains(&v) => (total / num_preds, None),
1510 _ => (total, None),
1511 };
1512 let mut est = base.min(graph_total).max(1.0);
1513 if node_bound(&t.0) {
1514 est *= match st {
1515 Some(s) if s.distinct_subjects > 0 => 1.0 / s.distinct_subjects as f64,
1516 _ => SEL_SUBJECT,
1517 };
1518 }
1519 if node_bound(&t.2) {
1520 est *= match st {
1521 Some(s) if s.distinct_objects > 0 => 1.0 / s.distinct_objects as f64,
1522 _ => SEL_OBJECT,
1523 };
1524 }
1525 est.max(1.0)
1526 })
1527 .collect(),
1528 )
1529}
1530
1531pub(crate) fn bgp_min_scan_bytes(
1538 ctx: &Ctx,
1539 index: &GraphIndex,
1540 patterns: &[TriplePattern],
1541) -> Option<u64> {
1542 let lowered = lower(patterns, ctx)?;
1543 lowered
1544 .iter()
1545 .map(|t| pattern_scan_bytes(ctx, index, t))
1546 .min()
1547}
1548
1549fn pattern_scan_bytes(ctx: &Ctx, index: &GraphIndex, t: &(SlotTerm, SlotTerm, SlotTerm)) -> u64 {
1566 let dict = ctx.rete.dictionary();
1567 match (
1568 const_subject(&t.0, dict),
1569 const_predicate(&t.1),
1570 const_object(&t.2, dict),
1571 ) {
1572 (Some(s), Some(p), Some(o)) => routed_scan_bytes(index, (s, p, o)),
1573 _ => 0,
1574 }
1575}
1576
1577pub(crate) fn routed_scan_bytes(index: &GraphIndex, pattern: Pattern) -> u64 {
1579 if let Some(u) = index.union() {
1580 return u.routed_bytes(pattern);
1581 }
1582 let sections = index.tile_sections();
1583 let mut best = u64::MAX;
1584 for perm in index.perms().iter() {
1588 let tiles = sections[perm.section_index()];
1589 best = best.min(match perm.order_pattern(pattern)[0] {
1592 Some(_) if index.cluster_runs(perm.section_index()).is_some() => {
1594 index.clustered_subject_bytes(perm.section_index())
1595 }
1596 Some(id) => tiles.routed_bytes(id),
1597 None => tiles.total_bytes(),
1598 });
1599 }
1600 best
1601}
1602
1603pub(crate) const FAT_SCAN_ROWS: f64 = (1u64 << 20) as f64;
1616
1617fn merge_seed_lopsided(
1622 ctx: &Ctx,
1623 index: &GraphIndex,
1624 ta: &(SlotTerm, SlotTerm, SlotTerm),
1625 tb: &(SlotTerm, SlotTerm, SlotTerm),
1626) -> bool {
1627 let est = tile_estimates(ctx, index, &[*ta, *tb], &std::collections::HashSet::new());
1628 let (lo, hi) = (est[0].min(est[1]), est[0].max(est[1]));
1629 hi >= FAT_SCAN_ROWS && hi / 4.0 >= lo
1630}
1631
1632fn selectivity_order(
1639 ctx: &Ctx,
1640 index: &GraphIndex,
1641 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1642) -> Vec<usize> {
1643 selectivity_order_seeded(ctx, index, lowered, &std::collections::HashSet::new())
1644}
1645
1646fn selectivity_order_seeded(
1650 ctx: &Ctx,
1651 index: &GraphIndex,
1652 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1653 seed: &std::collections::HashSet<usize>,
1654) -> Vec<usize> {
1655 let (estimates, per_class) = match pattern_estimates(ctx, index, lowered, seed) {
1663 Some(e) => (Some(e), false),
1664 None => (Some(tile_estimates(ctx, index, lowered, seed)), true),
1665 };
1666 let consts = |t: &(SlotTerm, SlotTerm, SlotTerm)| {
1667 [&t.0, &t.1, &t.2]
1668 .into_iter()
1669 .filter(|x| match x {
1670 SlotTerm::Var(v) => seed.contains(v),
1671 _ => true,
1672 })
1673 .count()
1674 };
1675 let vars = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Vec<usize> {
1676 [&t.0, &t.1, &t.2]
1677 .into_iter()
1678 .filter_map(|x| match x {
1679 SlotTerm::Var(v) => Some(*v),
1680 _ => None,
1681 })
1682 .collect()
1683 };
1684 let score = |i: usize| -> f64 {
1688 match &estimates {
1689 Some(e) => -e[i],
1690 None => consts(&lowered[i]) as f64,
1691 }
1692 };
1693 let type_pid = ctx.rete.dictionary().predicate_id(crate::file::RDF_TYPE);
1701 let is_class_enum = |i: usize, bound: &std::collections::HashSet<usize>| -> bool {
1702 let t = &lowered[i];
1703 !per_class
1704 && type_pid.is_some_and(|tp| matches!(t.1, SlotTerm::Pred(p) if p == tp))
1705 && matches!(t.2, SlotTerm::Node(_))
1706 && matches!(t.0, SlotTerm::Var(v) if !bound.contains(&v))
1707 };
1708 let n = lowered.len();
1709 let mut remaining: Vec<usize> = (0..n).collect();
1710 let mut order: Vec<usize> = Vec::with_capacity(n);
1711 let mut bound: std::collections::HashSet<usize> = seed.clone();
1712 while !remaining.is_empty() {
1713 let best = *remaining
1716 .iter()
1717 .max_by(|&&a, &&b| {
1718 let connected = |i: usize| vars(&lowered[i]).iter().any(|v| bound.contains(v));
1719 connected(a)
1720 .cmp(&connected(b))
1721 .then_with(|| is_class_enum(b, &bound).cmp(&is_class_enum(a, &bound)))
1722 .then_with(|| {
1723 score(a)
1724 .partial_cmp(&score(b))
1725 .unwrap_or(std::cmp::Ordering::Equal)
1726 })
1727 .then_with(|| b.cmp(&a))
1728 })
1729 .unwrap();
1730 for v in vars(&lowered[best]) {
1731 bound.insert(v);
1732 }
1733 order.push(best);
1734 remaining.retain(|&i| i != best);
1735 }
1736 order
1737}
1738
1739pub(crate) fn bgp_exists(ctx: &Ctx, index: &GraphIndex, patterns: &[TriplePattern]) -> bool {
1745 let dict = ctx.rete.dictionary();
1746 let Some(lowered) = lower(patterns, ctx) else {
1747 return false;
1748 };
1749 if let [t] = lowered.as_slice() {
1750 let names: Vec<usize> = [&t.0, &t.1, &t.2]
1754 .into_iter()
1755 .filter_map(|x| match x {
1756 SlotTerm::Var(v) => Some(*v),
1757 _ => None,
1758 })
1759 .collect();
1760 let distinct = names
1761 .iter()
1762 .enumerate()
1763 .all(|(i, v)| !names[i + 1..].contains(v));
1764 if distinct {
1765 return match (
1766 const_subject(&t.0, dict),
1767 const_predicate(&t.1),
1768 const_object(&t.2, dict),
1769 ) {
1770 (Some(s), Some(p), Some(o)) => index.scan_iter((s, p, o)).next().is_some(),
1771 _ => false,
1772 };
1773 }
1774 }
1775 !eval_bgp_rows(ctx, index, patterns).is_empty()
1776}
1777
1778pub(crate) struct BgpSolutions<'q> {
1789 scan: Option<Box<dyn Iterator<Item = Row> + 'q>>,
1790 prefix: Vec<Row>,
1791 buckets: HashMap<Vec<Val>, Vec<usize>>,
1793 shared: Vec<usize>,
1794 cartesian: bool,
1795 seed_only: bool,
1798 cur_scan: Option<Row>,
1799 matches: Vec<usize>,
1801 mi: usize,
1802}
1803
1804impl<'q> BgpSolutions<'q> {
1805 fn passthrough(rows: Box<dyn Iterator<Item = Row> + 'q>) -> Self {
1807 BgpSolutions {
1808 scan: Some(rows),
1809 prefix: Vec::new(),
1810 buckets: HashMap::new(),
1811 shared: Vec::new(),
1812 cartesian: false,
1813 seed_only: true,
1814 cur_scan: None,
1815 matches: Vec::new(),
1816 mi: 0,
1817 }
1818 }
1819
1820 fn streaming(
1829 ctx: &'q Ctx<'q>,
1830 index: &'q GraphIndex,
1831 lowered: &[(SlotTerm, SlotTerm, SlotTerm)],
1832 order: &[usize],
1833 est: &[f64],
1834 ) -> Self {
1835 let (mut stream, mut bound, skip): (Box<dyn Iterator<Item = Row> + 'q>, Vec<usize>, usize) =
1836 match (est[order[1]] > limits().stream_seed)
1837 .then(|| merge_stream(ctx, index, lowered[order[0]], lowered[order[1]], None))
1838 .flatten()
1839 {
1840 Some((m, slots)) => (m, slots, 2),
1841 None => {
1842 let t = lowered[order[0]];
1843 let Some(scan) = scan_rows(ctx, index, t) else {
1844 return Self::empty();
1845 };
1846 (Box::new(scan), pattern_slots(&t), 1)
1847 }
1848 };
1849 for &i in &order[skip..] {
1850 let t = lowered[i];
1851 let slots = pattern_slots(&t);
1852 let shared: Vec<usize> = slots
1853 .iter()
1854 .copied()
1855 .filter(|s| bound.contains(s))
1856 .collect();
1857 if !shared.is_empty() && est[i] > limits().hash_build {
1858 stream = Box::new(
1862 windowed(index, stream, bgp_probe_pattern(ctx, t))
1863 .flat_map(move |base| probe_rows(ctx, index, t, base)),
1864 );
1865 } else {
1866 let Some((rel, _)) = pattern_rows(ctx, index, &t) else {
1869 return Self::empty();
1870 };
1871 let mut table: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
1872 for r in rel {
1873 let key: Vec<Val> = shared.iter().map(|&s| r[s].clone().unwrap()).collect();
1874 table.entry(key).or_default().push(r);
1875 }
1876 let fill = slots.clone();
1877 stream = Box::new(stream.flat_map(move |base| {
1878 let key: Vec<Val> = shared.iter().map(|&s| base[s].clone().unwrap()).collect();
1879 let out: Vec<Row> = table
1880 .get(&key)
1881 .map(|rs| {
1882 rs.iter()
1883 .map(|r| {
1884 let mut row = base.clone();
1885 for &s in &fill {
1886 row[s] = r[s].clone();
1887 }
1888 row
1889 })
1890 .collect()
1891 })
1892 .unwrap_or_default();
1893 out.into_iter()
1894 }));
1895 }
1896 for s in slots {
1897 if !bound.contains(&s) {
1898 bound.push(s);
1899 }
1900 }
1901 }
1902 Self::passthrough(stream)
1903 }
1904
1905 fn empty() -> Self {
1907 BgpSolutions {
1908 scan: None,
1909 prefix: Vec::new(),
1910 buckets: HashMap::new(),
1911 shared: Vec::new(),
1912 cartesian: false,
1913 seed_only: false,
1914 cur_scan: None,
1915 matches: Vec::new(),
1916 mi: 0,
1917 }
1918 }
1919
1920 pub(crate) fn new(ctx: &'q Ctx<'q>, index: &'q GraphIndex, patterns: &[TriplePattern]) -> Self {
1921 if patterns.is_empty() {
1923 return BgpSolutions {
1924 scan: Some(Box::new(std::iter::once(ctx.slots.empty_row()))),
1925 prefix: vec![ctx.slots.empty_row()],
1926 buckets: HashMap::new(),
1927 shared: Vec::new(),
1928 cartesian: true,
1929 seed_only: true,
1930 cur_scan: None,
1931 matches: Vec::new(),
1932 mi: 0,
1933 };
1934 }
1935 let Some(lowered) = lower(patterns, ctx) else {
1937 return Self::empty();
1938 };
1939 let (order, scan_est) = plan_order(ctx, index, &lowered);
1942 if order.len() >= 2 && scan_est[order[0]] > limits().stream_seed {
1945 return Self::streaming(ctx, index, &lowered, &order, &scan_est);
1946 }
1947 let (&last_i, prefix_is) = order.split_last().unwrap();
1948 let prefix_pats: Vec<TriplePattern> =
1949 prefix_is.iter().map(|&i| patterns[i].clone()).collect();
1950 let prefix = eval_bgp_rows(ctx, index, &prefix_pats);
1951 if prefix.is_empty() {
1952 return Self::empty();
1953 }
1954
1955 let shared: Vec<usize> = pattern_slots(&lowered[last_i])
1959 .into_iter()
1960 .filter(|&s| prefix[0][s].is_some())
1961 .collect();
1962
1963 let class_probe = !shared.is_empty()
1972 && scan_est[last_i] >= limits().probe_floor
1973 && (prefix.len() as f64) <= scan_est[last_i]
1974 && is_unbound_class(ctx, &lowered[last_i], &shared);
1975 if !shared.is_empty() && (probe_beats_scan(prefix.len(), scan_est[last_i]) || class_probe) {
1976 let t = lowered[last_i];
1977 let stream = windowed(index, prefix.into_iter(), bgp_probe_pattern(ctx, t))
1978 .flat_map(move |base| probe_rows(ctx, index, t, base));
1979 return Self::passthrough(Box::new(stream));
1980 }
1981
1982 let Some(scan) = scan_rows(ctx, index, lowered[last_i]) else {
1984 return Self::empty();
1985 };
1986 let cartesian = shared.is_empty();
1987 let seed_only = prefix.len() == 1 && prefix[0].iter().all(Option::is_none);
1990 let mut buckets: HashMap<Vec<Val>, Vec<usize>> = HashMap::new();
1991 if !cartesian {
1992 for (i, r) in prefix.iter().enumerate() {
1993 let key: Vec<Val> = shared.iter().map(|&s| r[s].clone().unwrap()).collect();
1994 buckets.entry(key).or_default().push(i);
1995 }
1996 }
1997 BgpSolutions {
1998 scan: Some(Box::new(scan)),
1999 prefix,
2000 buckets,
2001 shared,
2002 cartesian,
2003 seed_only,
2004 cur_scan: None,
2005 matches: Vec::new(),
2006 mi: 0,
2007 }
2008 }
2009}
2010
2011impl Iterator for BgpSolutions<'_> {
2012 type Item = Row;
2013
2014 fn next(&mut self) -> Option<Row> {
2015 if self.seed_only {
2017 return self.scan.as_mut()?.next();
2018 }
2019 loop {
2020 if self.mi < self.matches.len() {
2022 let pi = self.matches[self.mi];
2023 self.mi += 1;
2024 let mut merged = self.prefix[pi].clone();
2025 for (slot, v) in self.cur_scan.as_ref().unwrap().iter().enumerate() {
2026 if v.is_some() {
2027 merged[slot] = v.clone();
2028 }
2029 }
2030 return Some(merged);
2031 }
2032 let s = self.scan.as_mut()?.next()?;
2035 self.matches.clear();
2036 if self.cartesian {
2037 self.matches.extend(0..self.prefix.len());
2038 } else {
2039 let key: Vec<Val> = self.shared.iter().map(|&i| s[i].clone().unwrap()).collect();
2040 if let Some(c) = self.buckets.get(&key) {
2041 self.matches.extend_from_slice(c);
2042 }
2043 }
2044 self.mi = 0;
2045 self.cur_scan = Some(s);
2046 }
2047 }
2048}
2049
2050#[allow(clippy::type_complexity)]
2058fn merge_stream<'q>(
2059 ctx: &'q Ctx<'q>,
2060 index: &'q GraphIndex,
2061 ta: (SlotTerm, SlotTerm, SlotTerm),
2062 tb: (SlotTerm, SlotTerm, SlotTerm),
2063 between: Option<(u32, u64)>,
2066) -> Option<(Box<dyn Iterator<Item = Row> + 'q>, Vec<usize>)> {
2067 let sa = pattern_slots(&ta);
2068 let sb = pattern_slots(&tb);
2069 let shared: Vec<usize> = sa.iter().copied().filter(|s| sb.contains(s)).collect();
2070 let [v] = shared[..] else {
2071 return None;
2072 };
2073 if !matches!(ta.0, SlotTerm::Var(i) if i == v) || !matches!(tb.0, SlotTerm::Var(i) if i == v) {
2074 return None;
2075 }
2076 let dict = ctx.rete.dictionary();
2077 let lower = |t: &(SlotTerm, SlotTerm, SlotTerm)| -> Option<Pattern> {
2078 Some((
2079 const_subject(&t.0, dict)?,
2080 const_predicate(&t.1)?,
2081 const_object(&t.2, dict)?,
2082 ))
2083 };
2084 let side = |t: (SlotTerm, SlotTerm, SlotTerm)| -> Option<KeyedRows<'q>> {
2085 let it: Box<dyn Iterator<Item = Triple> + 'q> = match between {
2086 Some((lo, hi)) => Box::new(index.scan_iter_sorted_between(lower(&t)?, 0, lo, hi)?),
2087 None => Box::new(index.scan_iter_sorted_on(lower(&t)?, 0)?),
2088 };
2089 let keyed: Box<dyn Iterator<Item = (u32, Row)> + 'q> =
2090 Box::new(it.filter_map(move |tri| triple_row(ctx, &t, tri).map(|r| (tri.0, r))));
2091 Some(keyed.peekable())
2092 };
2093 let a = side(ta)?;
2094 let b = side(tb)?;
2095 let mut slots = sa;
2096 for s in sb {
2097 if !slots.contains(&s) {
2098 slots.push(s);
2099 }
2100 }
2101 Some((
2102 Box::new(MergeStream {
2103 a,
2104 b,
2105 ra: Vec::new(),
2106 rb: Vec::new(),
2107 i: 0,
2108 j: 0,
2109 }),
2110 slots,
2111 ))
2112}
2113
2114type KeyedRows<'q> = std::iter::Peekable<Box<dyn Iterator<Item = (u32, Row)> + 'q>>;
2115
2116struct MergeStream<'q> {
2119 a: KeyedRows<'q>,
2120 b: KeyedRows<'q>,
2121 ra: Vec<Row>,
2122 rb: Vec<Row>,
2123 i: usize,
2124 j: usize,
2125}
2126
2127impl Iterator for MergeStream<'_> {
2128 type Item = Row;
2129
2130 fn next(&mut self) -> Option<Row> {
2131 loop {
2132 while self.i < self.ra.len() {
2133 if self.j < self.rb.len() {
2134 let j = self.j;
2135 self.j += 1;
2136 if let Some(m) = crate::row::merge_rows(&self.ra[self.i], &self.rb[j]) {
2137 return Some(m);
2138 }
2139 } else {
2140 self.i += 1;
2141 self.j = 0;
2142 }
2143 }
2144 let ka = self.a.peek()?.0;
2145 let kb = self.b.peek()?.0;
2146 match ka.cmp(&kb) {
2147 std::cmp::Ordering::Less => {
2148 self.a.next();
2149 }
2150 std::cmp::Ordering::Greater => {
2151 self.b.next();
2152 }
2153 std::cmp::Ordering::Equal => {
2154 self.ra.clear();
2155 self.rb.clear();
2156 while let Some((_, r)) = self.a.next_if(|(k, _)| *k == ka) {
2157 self.ra.push(r);
2158 }
2159 while let Some((_, r)) = self.b.next_if(|(k, _)| *k == ka) {
2160 self.rb.push(r);
2161 }
2162 self.i = 0;
2163 self.j = 0;
2164 }
2165 }
2166 }
2167 }
2168}
2169
2170fn probe_subject(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
2184 let dict = ctx.rete.dictionary();
2185 match t {
2186 SlotTerm::Node(n) => dict.node_as_subject_id(*n).map(Some),
2187 SlotTerm::Pred(_) => None,
2188 SlotTerm::Var(i) => match &base[*i] {
2189 None => Some(None),
2190 Some(Val::Id(v)) if *v >= 0 => dict.node_as_subject_id(*v as u32).map(Some),
2191 Some(_) => None,
2193 },
2194 }
2195}
2196
2197fn probe_object(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
2199 let dict = ctx.rete.dictionary();
2200 match t {
2201 SlotTerm::Node(n) => dict.node_as_object_id(*n).map(Some),
2202 SlotTerm::Pred(_) => None,
2203 SlotTerm::Var(i) => match &base[*i] {
2204 None => Some(None),
2205 Some(Val::Id(v)) if *v >= 0 => dict.node_as_object_id(*v as u32).map(Some),
2206 Some(_) => None,
2207 },
2208 }
2209}
2210
2211fn probe_predicate(ctx: &Ctx, t: &SlotTerm, base: &Row) -> Option<Option<u32>> {
2213 let dict = ctx.rete.dictionary();
2214 match t {
2215 SlotTerm::Pred(p) => Some(Some(*p)),
2216 SlotTerm::Node(_) => None,
2217 SlotTerm::Var(i) => match &base[*i] {
2218 None => Some(None),
2219 Some(Val::Id(v)) if *v < 0 => Some(Some((-v - 1) as u32)),
2220 Some(Val::Id(v)) => ctx
2222 .resolver
2223 .term(*v)
2224 .and_then(|t| dict.predicate_id(&t))
2225 .map(Some),
2226 Some(Val::Str(_)) => None,
2227 },
2228 }
2229}
2230
2231fn probe_rows<'q>(
2235 ctx: &'q Ctx<'q>,
2236 index: &'q GraphIndex,
2237 t: (SlotTerm, SlotTerm, SlotTerm),
2238 base: Row,
2239) -> Box<dyn Iterator<Item = Row> + 'q> {
2240 let (Some(sid), Some(pid), Some(oid)) = (
2241 probe_subject(ctx, &t.0, &base),
2242 probe_predicate(ctx, &t.1, &base),
2243 probe_object(ctx, &t.2, &base),
2244 ) else {
2245 return Box::new(std::iter::empty());
2246 };
2247 let dict = ctx.rete.dictionary();
2248 Box::new(
2251 canon_ahead(ctx, &t, index.scan_iter((sid, pid, oid))).filter_map(
2252 move |(s_id, p_id, o_id)| {
2253 let s_val = dict.subject_node(s_id) as i64;
2254 let p_val = pred_val(ctx, &t.1, p_id);
2255 let o_val = dict.object_node(o_id) as i64;
2256 let mut row = base.clone();
2257 for (term, val) in [(&t.0, s_val), (&t.1, p_val), (&t.2, o_val)] {
2258 if let SlotTerm::Var(i) = term {
2259 match row[*i] {
2260 Some(Val::Id(existing)) if existing != val => return None,
2261 Some(Val::Id(_)) => {}
2262 Some(Val::Str(_)) => return None,
2263 None => row[*i] = Some(Val::Id(val)),
2264 }
2265 }
2266 }
2267 Some(row)
2268 },
2269 ),
2270 )
2271}
2272
2273pub(crate) struct ProbePlan {
2275 pats: Vec<(SlotTerm, SlotTerm, SlotTerm)>,
2276}
2277
2278impl ProbePlan {
2279 pub(crate) fn new(
2283 ctx: &Ctx,
2284 index: &GraphIndex,
2285 patterns: &[TriplePattern],
2286 seed_mask: &[bool],
2287 ) -> Option<Self> {
2288 let lowered = lower(patterns, ctx)?;
2289 let seed: std::collections::HashSet<usize> = seed_mask
2290 .iter()
2291 .enumerate()
2292 .filter_map(|(i, b)| b.then_some(i))
2293 .collect();
2294 let order = selectivity_order_seeded(ctx, index, &lowered, &seed);
2295 Some(ProbePlan {
2296 pats: order.into_iter().map(|i| lowered[i]).collect(),
2297 })
2298 }
2299}
2300
2301pub(crate) struct ProbeJoin<'q> {
2304 ctx: &'q Ctx<'q>,
2305 index: &'q GraphIndex,
2306 pats: Vec<(SlotTerm, SlotTerm, SlotTerm)>,
2307 stack: Vec<Box<dyn Iterator<Item = Row> + 'q>>,
2308}
2309
2310impl<'q> ProbeJoin<'q> {
2311 pub(crate) fn new(
2314 ctx: &'q Ctx<'q>,
2315 index: &'q GraphIndex,
2316 patterns: &[TriplePattern],
2317 ) -> Option<Self> {
2318 let plan = ProbePlan::new(ctx, index, patterns, &vec![false; ctx.slots.len()])?;
2319 Some(Self::from_plan(ctx, index, &plan, ctx.slots.empty_row()))
2320 }
2321
2322 pub(crate) fn from_plan(
2324 ctx: &'q Ctx<'q>,
2325 index: &'q GraphIndex,
2326 plan: &ProbePlan,
2327 seed: Row,
2328 ) -> Self {
2329 let pats = plan.pats.clone();
2330 let first = probe_rows(ctx, index, pats[0], seed);
2331 ProbeJoin {
2332 ctx,
2333 index,
2334 pats,
2335 stack: vec![first],
2336 }
2337 }
2338}
2339
2340impl Iterator for ProbeJoin<'_> {
2341 type Item = Row;
2342
2343 fn next(&mut self) -> Option<Row> {
2344 loop {
2345 let depth = self.stack.len();
2346 match self.stack.last_mut()?.next() {
2347 Some(row) => {
2348 if depth == self.pats.len() {
2349 return Some(row);
2350 }
2351 let it = probe_rows(self.ctx, self.index, self.pats[depth], row);
2352 self.stack.push(it);
2353 }
2354 None => {
2355 self.stack.pop();
2356 if self.stack.is_empty() {
2357 return None;
2358 }
2359 }
2360 }
2361 }
2362 }
2363}
2364
2365fn hash_join(
2369 left: Vec<Row>,
2370 left_bound: &[usize],
2371 right: Vec<Row>,
2372 right_slots: &[usize],
2373) -> Vec<Row> {
2374 if left.len() == 1 && left_bound.is_empty() {
2376 return right;
2377 }
2378 if left.is_empty() || right.is_empty() {
2379 return Vec::new();
2380 }
2381 let shared: Vec<usize> = right_slots
2382 .iter()
2383 .copied()
2384 .filter(|s| left_bound.contains(s))
2385 .collect();
2386 let fill = |l: &Row, r: &Row| -> Row {
2387 let mut out = l.clone();
2388 for &s in right_slots {
2389 out[s] = r[s].clone();
2390 }
2391 out
2392 };
2393 if shared.is_empty() {
2394 let mut out = Vec::with_capacity(left.len() * right.len());
2398 for l in &left {
2399 for r in &right {
2400 out.push(fill(l, r));
2401 }
2402 }
2403 return out;
2404 }
2405 let key_of = |b: &Row| -> Vec<Val> { shared.iter().map(|&s| b[s].clone().unwrap()).collect() };
2406 let mut out = Vec::new();
2413 if right.len() <= left.len() {
2414 let mut buckets: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
2415 for r in right {
2416 buckets.entry(key_of(&r)).or_default().push(r);
2417 }
2418 for l in &left {
2419 if let Some(rs) = buckets.get(&key_of(l)) {
2420 for r in rs {
2421 out.push(fill(l, r));
2422 }
2423 }
2424 }
2425 } else {
2426 let mut buckets: HashMap<Vec<Val>, Vec<Row>> = HashMap::new();
2428 for l in left {
2429 buckets.entry(key_of(&l)).or_default().push(l);
2430 }
2431 for r in &right {
2432 if let Some(ls) = buckets.get(&key_of(r)) {
2433 for l in ls {
2434 let mut row = r.clone();
2435 for &s in left_bound {
2436 if let Some(v) = &l[s] {
2437 row[s] = Some(v.clone());
2438 }
2439 }
2440 out.push(row);
2441 }
2442 }
2443 }
2444 }
2445 out
2446}
2447
2448fn const_subject(t: &SlotTerm, d: &crate::Dictionary) -> Option<Option<u32>> {
2453 match t {
2454 SlotTerm::Node(n) => d.node_as_subject_id(*n).map(Some),
2455 SlotTerm::Pred(_) => None, SlotTerm::Var(_) => Some(None),
2457 }
2458}
2459
2460fn const_object(t: &SlotTerm, d: &crate::Dictionary) -> Option<Option<u32>> {
2461 match t {
2462 SlotTerm::Node(n) => d.node_as_object_id(*n).map(Some),
2463 SlotTerm::Pred(_) => None,
2464 SlotTerm::Var(_) => Some(None),
2465 }
2466}
2467
2468fn const_predicate(t: &SlotTerm) -> Option<Option<u32>> {
2469 match t {
2470 SlotTerm::Pred(p) => Some(Some(*p)),
2471 SlotTerm::Node(_) => None, SlotTerm::Var(_) => Some(None),
2473 }
2474}
2475
2476#[cfg(test)]
2477mod tests {
2478 use super::*;
2479 use crate::dictionary::DictionaryBuilder;
2480 use crate::file::write_file_v05 as write_file;
2481 use crate::index::GraphIndexBuilder;
2482
2483 fn rete_from(triples: &[(&str, &str, &str)]) -> Vec<u8> {
2484 let mut db = DictionaryBuilder::new();
2485 for (s, p, o) in triples {
2486 db.observe(s, p, o);
2487 }
2488 let dict = db.build();
2489 let mut ib = GraphIndexBuilder::new();
2490 for (s, p, o) in triples {
2491 ib.push(dict.encode(s, p, o).unwrap());
2492 }
2493 write_file(&dict, &ib.build(), false, &[], 0)
2494 }
2495
2496 fn pat(s: &str, p: &str, o: &str) -> TriplePattern {
2497 TriplePattern {
2498 s: PatternTerm::parse(s),
2499 p: PatternTerm::parse(p),
2500 o: PatternTerm::parse(o),
2501 }
2502 }
2503
2504 #[test]
2513 fn scan_bytes_route_a_literal_by_its_object_id() {
2514 let value = "<http://ex/value>";
2515 let owned: Vec<(String, String)> = (0..400)
2516 .map(|i| (format!("<http://ex/s{i:03}>"), format!("\"lit {i:03}\"")))
2517 .collect();
2518 let mut db = DictionaryBuilder::new();
2519 for (s, o) in &owned {
2520 db.observe(s, value, o);
2521 }
2522 let dict = db.build();
2523 let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2524 for (s, o) in &owned {
2525 ib.push(dict.encode(s, value, o).unwrap());
2526 }
2527 let rete = Rete::open(&write_file(&dict, &ib.build(), false, &[], 0)).unwrap();
2528 let index = rete.default_index();
2529 let whole = routed_scan_bytes(index, (None, rete.dictionary().predicate_id(value), None));
2531 for (_, lit) in owned.iter().step_by(57) {
2532 let q = [pat("?s", value, lit)];
2533 let mut slots = Slots::new();
2534 collect_pattern_slots(&q, &mut slots);
2535 let ctx = Ctx::new(&rete, slots);
2536 let got = bgp_min_scan_bytes(&ctx, index, &q).unwrap();
2537 assert!(got > 0, "{lit} routed to no tile");
2538 assert!(
2539 got < whole,
2540 "{lit} routed to the whole predicate ({got} of {whole})"
2541 );
2542 }
2543 }
2544
2545 #[test]
2551 fn plan_gates_do_not_move_with_the_compression() {
2552 let mut owned: Vec<(String, String, String)> = Vec::new();
2553 for i in 0..3000 {
2554 let s = format!("<http://ex/s{i}>");
2555 owned.push((
2556 s.clone(),
2557 "<http://ex/kind>".into(),
2558 format!("<http://ex/K{}>", i % 7),
2559 ));
2560 owned.push((s.clone(), "<http://ex/value>".into(), format!("\"v {i}\"")));
2561 if i % 50 == 0 {
2562 owned.push((s, "<http://ex/rare>".into(), "<http://ex/R>".into()));
2563 }
2564 }
2565 let mut db = DictionaryBuilder::new();
2566 for (s, p, o) in &owned {
2567 db.observe(s, p, o);
2568 }
2569 let dict = db.build();
2570 let mut ib = GraphIndexBuilder::new().with_tile_budget(1024);
2571 for (s, p, o) in &owned {
2572 ib.push(dict.encode(s, p, o).unwrap());
2573 }
2574 let bytes = write_file(&dict, &ib.build(), false, &[], 0);
2575 let leaked: &'static [u8] = Box::leak(bytes.clone().into_boxed_slice());
2576 let resident = Rete::open(&bytes).unwrap();
2577 let lazy = Rete::open_ranged_lazy(crate::reader::SliceReader::new(leaked)).unwrap();
2578 let shapes: Vec<Vec<TriplePattern>> = vec![
2579 vec![
2580 pat("?s", "<http://ex/rare>", "<http://ex/R>"),
2581 pat("?s", "<http://ex/value>", "?v"),
2582 ],
2583 vec![
2584 pat("?s", "<http://ex/kind>", "<http://ex/K3>"),
2585 pat("?s", "<http://ex/value>", "?v"),
2586 ],
2587 vec![
2588 pat("?s", "<http://ex/kind>", "?k"),
2589 pat("?s", "<http://ex/value>", "?v"),
2590 ],
2591 vec![
2592 pat("?s", "<http://ex/value>", "\"v 7\""),
2593 pat("?s", "<http://ex/kind>", "?k"),
2594 ],
2595 ];
2596 let decisions = |rete: &Rete| -> Vec<(Vec<u64>, bool, Option<u64>)> {
2597 shapes
2598 .iter()
2599 .map(|q| {
2600 let mut slots = Slots::new();
2601 collect_pattern_slots(q, &mut slots);
2602 let ctx = Ctx::new(rete, slots);
2603 let index = rete.default_index();
2604 let lowered = lower(q, &ctx).unwrap();
2605 let est = tile_estimates(&ctx, index, &lowered, &Default::default());
2606 let lopsided = merge_seed_lopsided(&ctx, index, &lowered[0], &lowered[1]);
2607 let min = bgp_min_estimate(&ctx, index, q).map(|e| e as u64);
2608 (est.iter().map(|e| *e as u64).collect(), lopsided, min)
2609 })
2610 .collect()
2611 };
2612 assert_eq!(decisions(&resident), decisions(&lazy));
2613 #[cfg(feature = "compression")]
2615 {
2616 let bytes_of = |rete: &Rete| {
2617 let q = &shapes[2];
2618 let mut slots = Slots::new();
2619 collect_pattern_slots(q, &mut slots);
2620 let ctx = Ctx::new(rete, slots);
2621 bgp_min_scan_bytes(&ctx, rete.default_index(), q)
2622 };
2623 assert_ne!(bytes_of(&resident), bytes_of(&lazy));
2624 }
2625 }
2626
2627 #[test]
2637 fn a_fat_predicate_estimates_alike_in_both_layouts() {
2638 let mut owned: Vec<(String, String, String)> = Vec::new();
2639 for i in 0..120_000 {
2640 let s = format!("<http://ex/s{i:06}>");
2641 owned.push((s.clone(), "<http://ex/kind>".into(), "<http://ex/K>".into()));
2642 owned.push((s, "<http://ex/value>".into(), format!("\"v {i}\"")));
2643 }
2644 let mut db = DictionaryBuilder::new();
2645 for (s, p, o) in &owned {
2646 db.observe(s, p, o);
2647 }
2648 let dict = db.build();
2649 let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2650 for (s, p, o) in &owned {
2651 ib.push(dict.encode(s, p, o).unwrap());
2652 }
2653 let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2654 let v6: &'static [u8] = Box::leak(
2655 crate::v06::write::convert_image(&v5, Default::default())
2656 .unwrap()
2657 .into_boxed_slice(),
2658 );
2659 let leaked5: &'static [u8] = Box::leak(v5.clone().into_boxed_slice());
2660 let flat = Rete::open_ranged_lazy(crate::reader::SliceReader::new(leaked5)).unwrap();
2661 let leafed = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v6)).unwrap();
2662 let q = [pat("?s", "<http://ex/value>", "?v")];
2663 let figures = |rete: &Rete| {
2664 let mut slots = Slots::new();
2665 collect_pattern_slots(&q, &mut slots);
2666 let ctx = Ctx::new(rete, slots);
2667 let index = rete.default_index();
2668 let total = bgp_total_estimate(&ctx, index, &q).unwrap();
2669 (total, probe_row_budget(total))
2670 };
2671 let (est5, budget5) = figures(&flat);
2672 let (est6, budget6) = figures(&leafed);
2673 assert!(est5 >= 70_000.0, "flat estimate {est5}");
2674 assert!(
2675 est6 >= est5 / 2.0 && est6 <= est5 * 2.0,
2676 "0x06 estimates {est6} where 0x05 estimates {est5}"
2677 );
2678 assert!(budget5.is_some_and(|b| b >= 1000), "{budget5:?}");
2680 assert!(budget6.is_some_and(|b| b >= 1000), "{budget6:?}");
2681 }
2682
2683 #[test]
2690 fn a_rare_object_of_a_fat_predicate_estimates_small_in_both_layouts() {
2691 let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2692 let mut owned: Vec<(String, String, String)> = Vec::new();
2693 for i in 0..120_000 {
2694 let s = format!("<http://ex/s{i:06}>");
2695 owned.push((s.clone(), ty.into(), "<http://ex/Common>".into()));
2696 owned.push((s.clone(), "<http://ex/other>".into(), format!("\"o {i}\"")));
2697 if i % 3000 == 0 {
2698 owned.push((s, ty.into(), "<http://ex/Rare>".into()));
2699 }
2700 }
2701 let mut db = DictionaryBuilder::new();
2702 for (s, p, o) in &owned {
2703 db.observe(s, p, o);
2704 }
2705 let dict = db.build();
2706 let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2707 for (s, p, o) in &owned {
2708 ib.push(dict.encode(s, p, o).unwrap());
2709 }
2710 let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2711 let v6: &'static [u8] = Box::leak(
2712 crate::v06::write::convert_image(&v5, Default::default())
2713 .unwrap()
2714 .into_boxed_slice(),
2715 );
2716 let leaked5: &'static [u8] = Box::leak(v5.into_boxed_slice());
2717 let figures = |rete: &Rete| {
2718 let est = |q: &[TriplePattern]| {
2719 let mut slots = Slots::new();
2720 collect_pattern_slots(q, &mut slots);
2721 let ctx = Ctx::new(rete, slots);
2722 bgp_min_estimate(&ctx, rete.default_index(), q).unwrap()
2723 };
2724 (
2725 est(&[pat("?s", ty, "<http://ex/Rare>")]),
2726 est(&[pat("?s", ty, "<http://ex/Common>")]),
2727 est(&[pat("?s", "<http://ex/other>", "?x")]),
2728 )
2729 };
2730 for (name, bytes) in [("0x05", leaked5), ("0x06", v6)] {
2731 let rete = Rete::open_ranged_lazy(crate::reader::SliceReader::new(bytes)).unwrap();
2732 let (rare, common, other) = figures(&rete);
2733 assert!(rare * 20.0 < other, "{name}: rare {rare} vs other {other}");
2734 assert!(
2735 rare * 20.0 < common,
2736 "{name}: rare {rare} vs common {common}"
2737 );
2738 }
2739 }
2740
2741 #[test]
2748 fn a_probe_prefetch_window_is_bounded_and_warm() {
2749 use crate::reader::{CountingReader, SliceReader};
2750 let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2751 let mut owned: Vec<(String, String, String)> = Vec::new();
2752 for i in 0..20_000 {
2753 let s = format!("<http://ex/s{i:06}>");
2754 owned.push((s.clone(), ty.into(), format!("<http://ex/C{}>", i % 7)));
2755 owned.push((s, "<http://ex/other>".into(), format!("\"o {}\"", i % 5000)));
2756 }
2757 let mut db = DictionaryBuilder::new();
2758 for (s, p, o) in &owned {
2759 db.observe(s, p, o);
2760 }
2761 let dict = db.build();
2762 let mut ib = GraphIndexBuilder::new().with_tile_budget(128);
2763 for (s, p, o) in &owned {
2764 ib.push(dict.encode(s, p, o).unwrap());
2765 }
2766 let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2767 let v6 = crate::v06::write::convert_image(&v5, Default::default()).unwrap();
2768 let leaked: &'static [u8] = Box::leak(v6.into_boxed_slice());
2769 let reader = std::sync::Arc::new(CountingReader::new(SliceReader::new(leaked)));
2770 let rete = Rete::open_ranged_lazy(reader.clone()).unwrap();
2771 let index = rete.default_index();
2772 index.set_cache_cap(1 << 20);
2775 let pats: Vec<Pattern> = (0..20_000)
2777 .step_by(3)
2778 .map(|i| {
2779 let (s, _, _) = dict
2780 .encode(&format!("<http://ex/s{i:06}>"), ty, "<http://ex/C0>")
2781 .unwrap();
2782 (Some(s), None, None)
2783 })
2784 .collect();
2785 let mut from = 0;
2786 let mut windows = 0;
2787 while from < pats.len() {
2788 let n = index.prefetch_probe_tiles(&pats[from..]);
2789 assert!(n >= 1, "a window always makes progress");
2790 assert!(
2791 n < pats.len() - from || windows > 0,
2792 "the first window is cut"
2793 );
2794 let before = reader.requests();
2795 for &p in &pats[from..from + n] {
2796 assert!(index.scan_iter(p).next().is_some());
2797 }
2798 assert_eq!(reader.requests(), before, "a covered probe reads nothing");
2799 from += n;
2800 windows += 1;
2801 }
2802 assert!(windows > 1, "{windows} window(s) for {} probes", pats.len());
2803 }
2804
2805 #[test]
2810 fn a_tile_span_is_the_same_in_both_layouts() {
2811 let ty = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
2812 let mut owned: Vec<(String, String, String)> = Vec::new();
2813 for i in 0..30_000 {
2814 let s = format!("<http://ex/s{i:06}>");
2815 owned.push((s.clone(), ty.into(), format!("<http://ex/C{}>", i % 7)));
2816 owned.push((s, "<http://ex/other>".into(), format!("\"o {}\"", i % 5000)));
2817 }
2818 let mut db = DictionaryBuilder::new();
2819 for (s, p, o) in &owned {
2820 db.observe(s, p, o);
2821 }
2822 let dict = db.build();
2823 let mut ib = GraphIndexBuilder::new().with_tile_budget(256);
2824 for (s, p, o) in &owned {
2825 ib.push(dict.encode(s, p, o).unwrap());
2826 }
2827 let v5 = write_file(&dict, &ib.build(), false, &[], 0);
2828 let v6 = crate::v06::write::convert_image(&v5, Default::default()).unwrap();
2829 let (v5, v6): (&'static [u8], &'static [u8]) = (
2830 Box::leak(v5.into_boxed_slice()),
2831 Box::leak(v6.into_boxed_slice()),
2832 );
2833 let flat = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v5)).unwrap();
2834 let leafed = Rete::open_ranged_lazy(crate::reader::SliceReader::new(v6)).unwrap();
2835 let (fi, li) = (flat.default_index(), leafed.default_index());
2836 let mut checked = 0;
2837 for perm in fi.perms().iter() {
2838 let si = perm.section_index();
2839 for a in (0..dict.term_count() + 2).step_by(97) {
2840 assert_eq!(
2841 fi.tile_span(si, Some(a)),
2842 li.tile_span(si, Some(a)),
2843 "section {si}, id {a}"
2844 );
2845 checked += 1;
2846 }
2847 assert_eq!(fi.tile_span(si, None), li.tile_span(si, None));
2848 }
2849 assert!(checked > 100);
2850 }
2851
2852 #[test]
2857 fn every_join_path_returns_the_same_solutions() {
2858 let mut owned: Vec<(String, String, String)> = Vec::new();
2859 let mut x: u64 = 7;
2860 let mut next = |m: u64| {
2861 x = x
2862 .wrapping_mul(6364136223846793005)
2863 .wrapping_add(1442695040888963407);
2864 (x >> 33) % m
2865 };
2866 for i in 0..60 {
2867 let s = format!("s{i}");
2868 owned.push((s.clone(), "a".into(), format!("C{}", next(3))));
2869 for p in 0..4 {
2870 for _ in 0..next(3) {
2871 owned.push((s.clone(), format!("p{p}"), format!("s{}", next(60))));
2872 }
2873 }
2874 }
2875 let triples: Vec<(&str, &str, &str)> = owned
2876 .iter()
2877 .map(|(s, p, o)| (s.as_str(), p.as_str(), o.as_str()))
2878 .collect();
2879 let bytes = rete_from(&triples);
2880 let rete = Rete::open(&bytes).unwrap();
2881 let queries: Vec<Vec<TriplePattern>> = vec![
2882 vec![pat("?s", "p0", "?a"), pat("?s", "p1", "?b")],
2883 vec![pat("?s", "a", "C1"), pat("?s", "p0", "?a")],
2884 vec![pat("?s", "p0", "?a"), pat("?a", "p2", "?b")],
2885 vec![pat("s5", "p0", "?a"), pat("?a", "?p", "?o")],
2886 vec![pat("?s", "p0", "?x"), pat("?s", "p1", "?x")],
2887 vec![
2888 pat("?s", "p3", "?o"),
2889 pat("?o", "a", "C0"),
2890 pat("?s", "p1", "?z"),
2891 ],
2892 vec![
2893 pat("?s", "p0", "?a"),
2894 pat("?s", "p1", "?b"),
2895 pat("?b", "p2", "?c"),
2896 ],
2897 ];
2898 let run = |limits: Option<PlanLimits>| -> Vec<Vec<Vec<(String, String)>>> {
2899 TEST_LIMITS.with(|c| c.set(limits));
2900 let out = queries
2901 .iter()
2902 .map(|q| {
2903 let mut slots = crate::row::Slots::new();
2904 collect_pattern_slots(q, &mut slots);
2905 let ctx = Ctx::new(&rete, slots);
2906 let mut rows: Vec<Vec<(String, String)>> =
2907 BgpSolutions::new(&ctx, rete.default_index(), q)
2908 .map(|r| row_to_binding(&ctx, &r).into_iter().collect())
2909 .collect();
2910 rows.sort();
2911 rows
2912 })
2913 .collect();
2914 TEST_LIMITS.with(|c| c.set(None));
2915 out
2916 };
2917 let reference = run(None);
2918 assert!(reference.iter().all(|r| !r.is_empty()), "{reference:?}");
2919 for (name, l) in [
2920 (
2921 "probe everything",
2922 PlanLimits {
2923 probe_floor: 0.0,
2924 stream_seed: f64::MAX,
2925 hash_build: f64::MAX,
2926 },
2927 ),
2928 (
2929 "stream + hash",
2930 PlanLimits {
2931 probe_floor: f64::MAX,
2932 stream_seed: 0.0,
2933 hash_build: f64::MAX,
2934 },
2935 ),
2936 (
2937 "stream + probe",
2938 PlanLimits {
2939 probe_floor: f64::MAX,
2940 stream_seed: 0.0,
2941 hash_build: 0.0,
2942 },
2943 ),
2944 (
2945 "stream, all paths",
2946 PlanLimits {
2947 probe_floor: 0.0,
2948 stream_seed: 0.0,
2949 hash_build: 30.0,
2950 },
2951 ),
2952 ] {
2953 assert_eq!(run(Some(l)), reference, "{name}");
2954 }
2955 }
2956
2957 #[test]
2962 fn the_shards_of_a_bgp_add_up_to_it_on_every_join_path() {
2963 let mut owned: Vec<(String, String, String)> = Vec::new();
2964 let mut x: u64 = 11;
2965 let mut next = |m: u64| {
2966 x = x
2967 .wrapping_mul(6364136223846793005)
2968 .wrapping_add(1442695040888963407);
2969 (x >> 33) % m
2970 };
2971 for i in 0..400 {
2972 let s = format!("s{i:03}");
2973 owned.push((s.clone(), "a".into(), format!("C{}", next(3))));
2974 for p in 0..4 {
2975 for _ in 0..next(3) {
2976 owned.push((s.clone(), format!("p{p}"), format!("s{:03}", next(400))));
2977 }
2978 }
2979 }
2980 let mut db = DictionaryBuilder::new();
2981 for (s, p, o) in &owned {
2982 db.observe(s, p, o);
2983 }
2984 let dict = db.build();
2985 let mut ib = GraphIndexBuilder::new().with_tile_budget(96);
2986 for (s, p, o) in &owned {
2987 ib.push(dict.encode(s, p, o).unwrap());
2988 }
2989 let bytes = write_file(&dict, &ib.build(), false, &[], 0);
2990 let rete = Rete::open(&bytes).unwrap();
2991 let queries: Vec<Vec<TriplePattern>> = vec![
2992 vec![pat("?s", "p0", "?a")],
2993 vec![pat("?s", "p0", "?a"), pat("?s", "p1", "?b")],
2994 vec![pat("?s", "a", "C1"), pat("?s", "p0", "?a")],
2995 vec![pat("?s", "p0", "?a"), pat("?a", "p2", "?b")],
2996 vec![pat("?s", "p0", "?x"), pat("?s", "p1", "?x")],
2997 vec![
2998 pat("?s", "p3", "?o"),
2999 pat("?o", "a", "C0"),
3000 pat("?s", "p1", "?z"),
3001 ],
3002 vec![
3003 pat("?s", "p0", "?a"),
3004 pat("?s", "p1", "?b"),
3005 pat("?b", "p2", "?c"),
3006 ],
3007 ];
3008 const NODE: usize = 1;
3010 let mut sliced = 0usize;
3011 let mut merged = 0usize;
3012 for (name, limits) in [
3013 ("defaults", None),
3014 (
3015 "probe everything",
3016 Some(PlanLimits {
3017 probe_floor: 0.0,
3018 stream_seed: f64::MAX,
3019 hash_build: f64::MAX,
3020 }),
3021 ),
3022 (
3023 "stream + hash",
3024 Some(PlanLimits {
3025 probe_floor: f64::MAX,
3026 stream_seed: 0.0,
3027 hash_build: f64::MAX,
3028 }),
3029 ),
3030 (
3031 "stream + probe",
3032 Some(PlanLimits {
3033 probe_floor: f64::MAX,
3034 stream_seed: 0.0,
3035 hash_build: 0.0,
3036 }),
3037 ),
3038 ] {
3039 TEST_LIMITS.with(|c| c.set(limits));
3040 for q in &queries {
3041 let mut slots = crate::row::Slots::new();
3042 collect_pattern_slots(q, &mut slots);
3043 let ctx = Ctx::new(&rete, slots);
3044 let index = rete.default_index();
3045 let whole: Vec<Row> = BgpSolutions::new(&ctx, index, q).collect();
3046 assert!(!whole.is_empty(), "{name}: {q:?}");
3047 for n in [1usize, 2, 5, 13] {
3048 ctx.shard
3049 .set_plan(vec![NODE], Vec::new(), Vec::new(), Default::default());
3050 let mut parts: Vec<Row> = Vec::new();
3051 let mut ok = true;
3052 for i in 0..n {
3053 ctx.shard.begin(Some((i, n)));
3054 match shard_bgp_rows(&ctx, index, q, (NODE, i, n)) {
3055 Some(rows) => parts.extend(rows),
3056 None => ok = false,
3057 }
3058 }
3059 ctx.shard.clear();
3060 if !ok {
3061 continue;
3062 }
3063 sliced += 1;
3064 assert_eq!(parts, whole, "{name}, {n} shards: {q:?}");
3065 }
3066 if limits.is_some_and(|l| l.stream_seed == 0.0) && q.len() == 2 {
3069 let lowered = lower(q, &ctx).unwrap();
3070 if merge_stream(&ctx, index, lowered[0], lowered[1], None).is_some() {
3071 merged += 1;
3072 }
3073 }
3074 }
3075 TEST_LIMITS.with(|c| c.set(None));
3076 }
3077 assert!(sliced > 60, "{sliced} sliced cases");
3078 assert!(merged >= 2, "{merged} merge joins");
3079 }
3080
3081 #[test]
3082 fn single_pattern_binds_variable() {
3083 let bytes = rete_from(&[("Alice", "knows", "Bob"), ("Bob", "knows", "Carol")]);
3084 let rete = Rete::open(&bytes).unwrap();
3085 let sols = eval_bgp(&rete, &[pat("Alice", "knows", "?y")]);
3086 assert_eq!(sols.len(), 1);
3087 assert_eq!(sols[0]["y"], "Bob");
3088 }
3089
3090 #[test]
3091 fn two_hop_join_on_shared_variable() {
3092 let bytes = rete_from(&[
3094 ("Alice", "knows", "Bob"),
3095 ("Bob", "knows", "Carol"),
3096 ("Carol", "knows", "Dave"),
3097 ("Alice", "knows", "Eve"), ]);
3099 let rete = Rete::open(&bytes).unwrap();
3100 let sols = eval_bgp(&rete, &[pat("?x", "knows", "?y"), pat("?y", "knows", "?z")]);
3101 let mut got: Vec<_> = sols
3103 .iter()
3104 .map(|b| (b["x"].clone(), b["y"].clone(), b["z"].clone()))
3105 .collect();
3106 got.sort();
3107 assert_eq!(
3108 got,
3109 vec![
3110 ("Alice".into(), "Bob".into(), "Carol".into()),
3111 ("Bob".into(), "Carol".into(), "Dave".into()),
3112 ]
3113 );
3114 }
3115
3116 #[test]
3117 fn repeated_variable_within_pattern() {
3118 let bytes = rete_from(&[("Alice", "knows", "Bob"), ("Bob", "knows", "Bob")]);
3120 let rete = Rete::open(&bytes).unwrap();
3121 let sols = eval_bgp(&rete, &[pat("?x", "knows", "?x")]);
3122 assert_eq!(sols.len(), 1);
3123 assert_eq!(sols[0]["x"], "Bob");
3124 }
3125
3126 #[test]
3127 fn no_solutions_yields_empty() {
3128 let bytes = rete_from(&[("Alice", "knows", "Bob")]);
3129 let rete = Rete::open(&bytes).unwrap();
3130 assert!(eval_bgp(&rete, &[pat("Alice", "likes", "?y")]).is_empty());
3131 }
3132
3133 #[test]
3140 fn snowflake_type_and_adjacency_matches_reference() {
3141 const TYPE: &str = "<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>";
3142 let mut triples: Vec<(String, String, String)> = Vec::new();
3143 for i in 0..60 {
3145 let s = format!("S{i}");
3146 triples.push((s.clone(), TYPE.into(), "Student".into()));
3147 triples.push((s.clone(), "takesCourse".into(), format!("c{}", i % 5)));
3148 triples.push((s, "takesCourse".into(), format!("c{}", (i + 1) % 5)));
3149 }
3150 for j in 0..5 {
3152 triples.push((format!("c{j}"), TYPE.into(), "Course".into()));
3153 }
3154 triples.push(("Prof".into(), "teacherOf".into(), "c0".into()));
3155 triples.push(("Prof".into(), "teacherOf".into(), "c2".into()));
3156
3157 let refs: Vec<(&str, &str, &str)> = triples
3158 .iter()
3159 .map(|(s, p, o)| (s.as_str(), p.as_str(), o.as_str()))
3160 .collect();
3161 let bytes = rete_from(&refs);
3162 let rete = Rete::open(&bytes).unwrap();
3163
3164 let got: std::collections::BTreeSet<(String, String)> = eval_bgp(
3165 &rete,
3166 &[
3167 pat("?x", TYPE, "Student"),
3168 pat("?y", TYPE, "Course"),
3169 pat("?x", "takesCourse", "?y"),
3170 pat("Prof", "teacherOf", "?y"),
3171 ],
3172 )
3173 .into_iter()
3174 .map(|b| (b["x"].clone(), b["y"].clone()))
3175 .collect();
3176
3177 let taught = ["c0", "c2"];
3179 let mut want = std::collections::BTreeSet::new();
3180 for i in 0..60 {
3181 for c in [i % 5, (i + 1) % 5] {
3182 let course = format!("c{c}");
3183 if taught.contains(&course.as_str()) {
3184 want.insert((format!("S{i}"), course));
3185 }
3186 }
3187 }
3188 assert_eq!(got, want, "snowflake join must match the brute-force set");
3189 assert!(!want.is_empty(), "sanity: the reference set is non-empty");
3190 }
3191
3192 #[test]
3197 fn merge_join_subject_star_cross_product() {
3198 let bytes = rete_from(&[
3199 ("x", "a", "a1"),
3200 ("x", "a", "a2"),
3201 ("x", "b", "b1"),
3202 ("x", "b", "b2"),
3203 ("y", "a", "a3"),
3204 ("y", "b", "b3"),
3205 ("z", "a", "a4"), ]);
3207 let rete = Rete::open(&bytes).unwrap();
3208 let mut got: Vec<(String, String, String)> =
3209 eval_bgp(&rete, &[pat("?x", "a", "?av"), pat("?x", "b", "?bv")])
3210 .iter()
3211 .map(|m| (m["x"].clone(), m["av"].clone(), m["bv"].clone()))
3212 .collect();
3213 got.sort();
3214 let mut want: Vec<(String, String, String)> = [
3215 ("x", "a1", "b1"),
3216 ("x", "a1", "b2"),
3217 ("x", "a2", "b1"),
3218 ("x", "a2", "b2"),
3219 ("y", "a3", "b3"),
3220 ]
3221 .into_iter()
3222 .map(|(a, b, c)| (a.to_string(), b.to_string(), c.to_string()))
3223 .collect();
3224 want.sort();
3225 assert_eq!(got, want, "same-role merge must equal the brute-force join");
3226 }
3227}