1use super::range_join_select::Q42RangeJoinSelectPlan;
7use super::range_select_apply::{apply_select_wrappers, SelectWrapperState};
8use super::sparql_ast::{
9 BindingRow, ExpressionId, SparqlQueryContext, VariableId, MAX_BINDINGS, MAX_VARIABLES,
10};
11use super::sparql_executor::{
12 execute_range_triple_page_into, execute_range_volume_set_triple_page_into,
13 Q42RangeNestedLoopJoinPage, Q42RangeNestedLoopJoinPlan, Q42RangeSparqlCursor,
14 Q42RangeTriplePattern, Q42RangeVolumeSetSparqlCursor,
15};
16use super::sparql_planner::{ExecutionPlan, PhysicalOperatorType};
17use crate::NQuin;
18
19#[derive(Clone, Copy, Debug, Eq, PartialEq)]
20pub struct Q42RangeHashJoinSlot {
21 pub key: u64,
22 pub row: BindingRow,
23 pub occupied: bool,
24}
25
26impl Default for Q42RangeHashJoinSlot {
27 fn default() -> Self {
28 Self {
29 key: 0,
30 row: BindingRow::default(),
31 occupied: false,
32 }
33 }
34}
35
36#[derive(Clone, Copy, Debug, Eq, PartialEq)]
37pub struct Q42RangeHashJoinPlan {
38 pub left: Q42RangeTriplePattern,
39 pub right: Q42RangeTriplePattern,
40 pub join_var: VariableId,
41 pub projection: [VariableId; MAX_VARIABLES],
42 pub projection_count: u8,
43 pub filters: [ExpressionId; 8],
44 pub filter_count: u8,
45 pub limit: u64,
46 pub offset: u64,
47}
48
49impl Q42RangeHashJoinPlan {
50 pub fn as_join_select(&self) -> Q42RangeJoinSelectPlan {
52 Q42RangeJoinSelectPlan {
53 join: Q42RangeNestedLoopJoinPlan {
54 left: self.left,
55 right: self.right,
56 },
57 projection: self.projection,
58 projection_count: self.projection_count,
59 filters: self.filters,
60 filter_count: self.filter_count,
61 limit: self.limit,
62 offset: self.offset,
63 }
64 }
65
66 pub fn from_execution_plan(plan: &ExecutionPlan) -> Result<Self, String> {
68 if plan.operator_count == 0 || plan.root_operator as usize >= plan.operator_count as usize {
69 return Err("range HashJoin requires a non-empty execution plan".into());
70 }
71 let mut operator = plan.root_operator;
72 let mut projection = [0; MAX_VARIABLES];
73 let mut projection_count = 0;
74 let mut filters = [0; 8];
75 let mut filter_count = 0usize;
76 let mut limit = u64::MAX;
77 let mut offset = 0;
78 loop {
79 match plan.operators[operator as usize].operator_type {
80 PhysicalOperatorType::Project {
81 input,
82 vars,
83 var_count,
84 } => {
85 if projection_count != 0 {
86 return Err("range HashJoin does not support nested projections".into());
87 }
88 projection = vars;
89 projection_count = var_count;
90 operator = input;
91 }
92 PhysicalOperatorType::Limit {
93 input,
94 limit: configured,
95 offset: configured_offset,
96 } => {
97 if limit != u64::MAX || offset != 0 {
98 return Err("range HashJoin does not support nested limits".into());
99 }
100 limit = configured;
101 offset = configured_offset;
102 operator = input;
103 }
104 PhysicalOperatorType::Filter { input, expression } => {
105 if filter_count == filters.len() {
106 return Err(
107 "range HashJoin supports at most eight stacked FILTER operators".into(),
108 );
109 }
110 filters[filter_count] = expression;
111 filter_count += 1;
112 operator = input;
113 }
114 PhysicalOperatorType::HashJoin {
115 left,
116 right,
117 join_var,
118 }
119 | PhysicalOperatorType::NestedLoopJoin {
120 left,
121 right,
122 join_var,
123 } => {
124 return Ok(Self {
125 left: triple_scan(plan, left)?,
126 right: triple_scan(plan, right)?,
127 join_var,
128 projection,
129 projection_count,
130 filters,
131 filter_count: filter_count as u8,
132 limit,
133 offset,
134 });
135 }
136 _ => {
137 return Err(
138 "range HashJoin supports Project/Filter/Limit over HashJoin or NestedLoopJoin(TripleScan, TripleScan)"
139 .into(),
140 );
141 }
142 }
143 }
144 }
145}
146
147#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
148pub struct Q42RangeHashJoinState {
149 pub built: bool,
150 pub build_is_right: bool,
151 pub probe_scan: Q42RangeSparqlCursor,
152 pub probe_count: usize,
153 pub probe_index: usize,
154 pub probe_exhausted: bool,
155 pub match_offset: usize,
156 pub wrappers: SelectWrapperState,
157}
158
159#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
160pub struct Q42RangeVolumeSetHashJoinState {
161 pub built: bool,
162 pub build_is_right: bool,
163 pub probe_scan: Q42RangeVolumeSetSparqlCursor,
164 pub probe_count: usize,
165 pub probe_index: usize,
166 pub probe_exhausted: bool,
167 pub match_offset: usize,
168 pub wrappers: SelectWrapperState,
169}
170
171fn triple_scan(plan: &ExecutionPlan, operator: u16) -> Result<Q42RangeTriplePattern, String> {
172 let Some(entry) = plan.operators.get(operator as usize) else {
173 return Err("range HashJoin input operator is out of bounds".into());
174 };
175 match entry.operator_type {
176 PhysicalOperatorType::TripleScan {
177 subject,
178 predicate,
179 object,
180 } => Ok(Q42RangeTriplePattern {
181 subject,
182 predicate,
183 object,
184 }),
185 _ => Err("range HashJoin currently requires TripleScan inputs".into()),
186 }
187}
188
189fn cap_error(count: usize, cap: usize) -> String {
190 format!(
191 "range HashJoin build side ({count} rows) exceeds caller cap ({cap}); planner must keep NestedLoopJoin"
192 )
193}
194
195fn term_var(term: u64, ctx: &SparqlQueryContext) -> Option<VariableId> {
196 if (term as usize) < ctx.variable_count {
197 Some(term as VariableId)
198 } else {
199 None
200 }
201}
202
203fn pattern_vars(pattern: Q42RangeTriplePattern, ctx: &SparqlQueryContext) -> ([VariableId; 3], u8) {
204 let mut vars = [0; 3];
205 let mut count = 0u8;
206 for term in [pattern.subject, pattern.predicate, pattern.object] {
207 if let Some(var) = term_var(term, ctx) {
208 if !vars[..count as usize].contains(&var) {
209 vars[count as usize] = var;
210 count += 1;
211 }
212 }
213 }
214 (vars, count)
215}
216
217fn shared_join_vars(
218 left: Q42RangeTriplePattern,
219 right: Q42RangeTriplePattern,
220 ctx: &SparqlQueryContext,
221 join_var: VariableId,
222) -> ([VariableId; 3], u8) {
223 let (left_vars, left_n) = pattern_vars(left, ctx);
224 let (right_vars, right_n) = pattern_vars(right, ctx);
225 let mut shared = [0; 3];
226 let mut count = 0u8;
227 let left_slice = &left_vars[..left_n as usize];
228 let right_slice = &right_vars[..right_n as usize];
229 if left_slice.contains(&join_var) && right_slice.contains(&join_var) {
230 shared[0] = join_var;
231 count = 1;
232 }
233 for var in left_slice {
234 if right_slice.contains(var) && !shared[..count as usize].contains(var) && count < 3 {
235 shared[count as usize] = *var;
236 count += 1;
237 }
238 }
239 (shared, count)
240}
241
242fn join_key(row: &BindingRow, vars: &[VariableId]) -> u64 {
243 for var in vars {
244 if let Some(value) = row.get(*var) {
245 return value;
246 }
247 }
248 0
249}
250
251fn rows_compatible(left: &BindingRow, right: &BindingRow) -> bool {
252 for slot in 0..MAX_BINDINGS {
253 if let (Some(a), Some(b)) = (left.slots[slot], right.slots[slot]) {
254 if a != b {
255 return false;
256 }
257 }
258 }
259 true
260}
261
262fn merge_rows(left: &BindingRow, right: &BindingRow) -> BindingRow {
263 let mut joined = BindingRow::new();
264 for slot in 0..MAX_BINDINGS {
265 joined.slots[slot] = left.slots[slot].or(right.slots[slot]);
266 }
267 joined
268}
269
270fn insert_slot(
271 table: &mut [Q42RangeHashJoinSlot],
272 key: u64,
273 row: BindingRow,
274) -> Result<(), String> {
275 if table.is_empty() {
276 return Err(cap_error(1, 0));
277 }
278 let cap = table.len();
279 let start = (key as usize) % cap;
280 for step in 0..cap {
281 let slot = &mut table[(start + step) % cap];
282 if !slot.occupied {
283 slot.occupied = true;
284 slot.key = key;
285 slot.row = row;
286 return Ok(());
287 }
288 }
289 Err(cap_error(cap + 1, cap))
290}
291
292fn count_side<C, F>(
293 mut page_fn: F,
294 pattern: Q42RangeTriplePattern,
295 scratch: &mut [BindingRow],
296) -> Result<usize, String>
297where
298 C: Copy + Default,
299 F: FnMut(Q42RangeTriplePattern, C, &mut [BindingRow]) -> Result<(usize, Option<C>), String>,
300{
301 let mut cursor = C::default();
302 let mut total = 0usize;
303 loop {
304 let (count, next) = page_fn(pattern, cursor, scratch)?;
305 total = total.saturating_add(count);
306 match next {
307 Some(next_cursor) => cursor = next_cursor,
308 None => return Ok(total),
309 }
310 }
311}
312
313fn build_side<C, F>(
314 mut page_fn: F,
315 pattern: Q42RangeTriplePattern,
316 key_vars: &[VariableId],
317 table: &mut [Q42RangeHashJoinSlot],
318 scratch: &mut [BindingRow],
319) -> Result<usize, String>
320where
321 C: Copy + Default,
322 F: FnMut(Q42RangeTriplePattern, C, &mut [BindingRow]) -> Result<(usize, Option<C>), String>,
323{
324 let mut cursor = C::default();
325 let mut inserted = 0usize;
326 loop {
327 let (count, next) = page_fn(pattern, cursor, scratch)?;
328 for row in &scratch[..count] {
329 insert_slot(table, join_key(row, key_vars), *row)?;
330 inserted += 1;
331 }
332 match next {
333 Some(next_cursor) => cursor = next_cursor,
334 None => return Ok(inserted),
335 }
336 }
337}
338
339fn emit_matches(
340 table: &[Q42RangeHashJoinSlot],
341 probe: &BindingRow,
342 key_vars: &[VariableId],
343 match_offset: &mut usize,
344 out: &mut [BindingRow],
345) -> usize {
346 if table.is_empty() {
347 *match_offset = 0;
348 return 0;
349 }
350 let key = join_key(probe, key_vars);
351 let cap = table.len();
352 let start = (key as usize) % cap;
353 let mut returned = 0usize;
354 while *match_offset < cap && returned < out.len() {
355 let slot = &table[(start + *match_offset) % cap];
356 *match_offset += 1;
357 if !slot.occupied {
358 *match_offset = cap;
359 break;
360 }
361 if slot.key != key || !rows_compatible(probe, &slot.row) {
362 continue;
363 }
364 out[returned] = merge_rows(probe, &slot.row);
365 returned += 1;
366 }
367 returned
368}
369
370fn emit_matches_accel(
371 table: &[Q42RangeHashJoinSlot],
372 probes: &[BindingRow],
373 key_vars: &[VariableId],
374 out: &mut [BindingRow],
375) -> usize {
376 let mut build_keys = Vec::new();
377 let mut build_rows = Vec::new();
378 for slot in table {
379 if slot.occupied {
380 build_keys.push(slot.key);
381 build_rows.push(slot.row);
382 }
383 }
384 let probe_keys: Vec<u64> = probes.iter().map(|r| join_key(r, key_vars)).collect();
385 let mut pairs = vec![(0u32, 0u32); out.len()];
386 let joined = crate::query::graph_accel::hash_join_u64(&build_keys, &probe_keys, &mut pairs);
387 let mut n = 0usize;
388 for &(pi, bi) in &pairs[..joined.written] {
389 if n >= out.len() {
390 break;
391 }
392 let probe = &probes[pi as usize];
393 let built = &build_rows[bi as usize];
394 if !rows_compatible(probe, built) {
395 continue;
396 }
397 out[n] = merge_rows(probe, built);
398 n += 1;
399 }
400 n
401}
402
403pub fn execute_range_hash_join_page_into<S: crate::q42_volume::Q42RangeSource>(
405 volume: &crate::q42_volume::Q42RangeVolume<S>,
406 plan: Q42RangeHashJoinPlan,
407 ctx: &SparqlQueryContext,
408 state: &mut Q42RangeHashJoinState,
409 table: &mut [Q42RangeHashJoinSlot],
410 compressed: &mut [u8],
411 decoded: &mut [u8],
412 quin_scratch: &mut [NQuin],
413 probe_rows: &mut [BindingRow],
414 join_out: &mut [BindingRow],
415 out: &mut [BindingRow],
416) -> Result<Q42RangeNestedLoopJoinPage, String> {
417 let mut page_fn =
418 |pattern: Q42RangeTriplePattern, cursor: Q42RangeSparqlCursor, rows: &mut [BindingRow]| {
419 execute_range_triple_page_into(
420 volume,
421 pattern.subject,
422 pattern.predicate,
423 pattern.object,
424 None,
425 ctx,
426 &BindingRow::default(),
427 cursor,
428 compressed,
429 decoded,
430 quin_scratch,
431 rows,
432 )
433 .map(|page| (page.returned, page.next_cursor))
434 };
435 if !state.built {
436 let left_n = count_side(&mut page_fn, plan.left, probe_rows)?;
437 let right_n = count_side(&mut page_fn, plan.right, probe_rows)?;
438 let build_is_right = right_n <= left_n;
439 let build_n = if build_is_right { right_n } else { left_n };
440 if build_n > table.len() {
441 return Err(cap_error(build_n, table.len()));
442 }
443 let build_pattern = if build_is_right {
444 plan.right
445 } else {
446 plan.left
447 };
448 let (key_vars, key_n) = shared_join_vars(plan.left, plan.right, ctx, plan.join_var);
449 build_side(
450 &mut page_fn,
451 build_pattern,
452 &key_vars[..key_n as usize],
453 table,
454 probe_rows,
455 )?;
456 state.built = true;
457 state.build_is_right = build_is_right;
458 state.probe_scan = Q42RangeSparqlCursor::default();
459 state.probe_exhausted = false;
460 state.probe_count = 0;
461 state.probe_index = 0;
462 state.match_offset = 0;
463 }
464 let probe_pattern = if state.build_is_right {
465 plan.left
466 } else {
467 plan.right
468 };
469 let mut returned = 0usize;
470 loop {
471 if returned == out.len() {
472 return Ok(Q42RangeNestedLoopJoinPage {
473 returned,
474 done: false,
475 });
476 }
477 if state.wrappers.emitted >= plan.limit {
478 return Ok(Q42RangeNestedLoopJoinPage {
479 returned,
480 done: true,
481 });
482 }
483 if state.probe_index >= state.probe_count {
484 if state.probe_exhausted {
485 return Ok(Q42RangeNestedLoopJoinPage {
486 returned,
487 done: true,
488 });
489 }
490 let (count, next) = page_fn(probe_pattern, state.probe_scan, probe_rows)?;
491 state.probe_count = count;
492 state.probe_index = 0;
493 state.match_offset = 0;
494 state.probe_scan = next.unwrap_or_default();
495 state.probe_exhausted = next.is_none();
496 if state.probe_count == 0 {
497 if state.probe_exhausted {
498 return Ok(Q42RangeNestedLoopJoinPage {
499 returned,
500 done: true,
501 });
502 }
503 continue;
504 }
505 }
506 let (key_vars, key_n) = shared_join_vars(plan.left, plan.right, ctx, plan.join_var);
507 if state.probe_index == 0
508 && state.match_offset == 0
509 && state.probe_count >= 32
510 && table.iter().filter(|s| s.occupied).count() >= 32
511 {
512 let produced = emit_matches_accel(
513 table,
514 &probe_rows[..state.probe_count],
515 &key_vars[..key_n as usize],
516 join_out,
517 );
518 state.probe_index = state.probe_count;
519 let applied = apply_select_wrappers(
520 ctx,
521 &plan.filters,
522 plan.filter_count,
523 plan.projection,
524 plan.projection_count,
525 plan.limit,
526 plan.offset,
527 &mut state.wrappers,
528 &join_out[..produced],
529 &mut out[returned..],
530 )?;
531 returned += applied.returned;
532 if applied.limit_reached || returned == out.len() {
533 return Ok(Q42RangeNestedLoopJoinPage {
534 returned,
535 done: applied.limit_reached,
536 });
537 }
538 continue;
539 }
540 let probe = probe_rows[state.probe_index];
541 let produced = emit_matches(
542 table,
543 &probe,
544 &key_vars[..key_n as usize],
545 &mut state.match_offset,
546 join_out,
547 );
548 let applied = apply_select_wrappers(
549 ctx,
550 &plan.filters,
551 plan.filter_count,
552 plan.projection,
553 plan.projection_count,
554 plan.limit,
555 plan.offset,
556 &mut state.wrappers,
557 &join_out[..produced],
558 &mut out[returned..],
559 )?;
560 returned += applied.returned;
561 if state.match_offset >= table.len() || table.is_empty() {
562 state.probe_index += 1;
563 state.match_offset = 0;
564 }
565 if applied.limit_reached {
566 return Ok(Q42RangeNestedLoopJoinPage {
567 returned,
568 done: true,
569 });
570 }
571 if returned == out.len() {
572 return Ok(Q42RangeNestedLoopJoinPage {
573 returned,
574 done: false,
575 });
576 }
577 }
578}
579
580pub fn execute_range_volume_set_hash_join_page_into<S: crate::q42_volume::Q42RangeSource>(
582 volumes: &crate::q42_volume::Q42RangeVolumeSet<S>,
583 plan: Q42RangeHashJoinPlan,
584 ctx: &SparqlQueryContext,
585 state: &mut Q42RangeVolumeSetHashJoinState,
586 table: &mut [Q42RangeHashJoinSlot],
587 compressed: &mut [u8],
588 decoded: &mut [u8],
589 quin_scratch: &mut [NQuin],
590 probe_rows: &mut [BindingRow],
591 join_out: &mut [BindingRow],
592 out: &mut [BindingRow],
593) -> Result<Q42RangeNestedLoopJoinPage, String> {
594 let mut page_fn = |pattern: Q42RangeTriplePattern,
595 cursor: Q42RangeVolumeSetSparqlCursor,
596 rows: &mut [BindingRow]| {
597 execute_range_volume_set_triple_page_into(
598 volumes,
599 pattern.subject,
600 pattern.predicate,
601 pattern.object,
602 None,
603 ctx,
604 &BindingRow::default(),
605 cursor,
606 compressed,
607 decoded,
608 quin_scratch,
609 rows,
610 )
611 .map(|page| (page.returned, page.next_cursor))
612 };
613 if !state.built {
614 let left_n = count_side(&mut page_fn, plan.left, probe_rows)?;
615 let right_n = count_side(&mut page_fn, plan.right, probe_rows)?;
616 let build_is_right = right_n <= left_n;
617 let build_n = if build_is_right { right_n } else { left_n };
618 if build_n > table.len() {
619 return Err(cap_error(build_n, table.len()));
620 }
621 let build_pattern = if build_is_right {
622 plan.right
623 } else {
624 plan.left
625 };
626 let (key_vars, key_n) = shared_join_vars(plan.left, plan.right, ctx, plan.join_var);
627 build_side(
628 &mut page_fn,
629 build_pattern,
630 &key_vars[..key_n as usize],
631 table,
632 probe_rows,
633 )?;
634 state.built = true;
635 state.build_is_right = build_is_right;
636 state.probe_scan = Q42RangeVolumeSetSparqlCursor::default();
637 state.probe_exhausted = false;
638 state.probe_count = 0;
639 state.probe_index = 0;
640 state.match_offset = 0;
641 }
642 let probe_pattern = if state.build_is_right {
643 plan.left
644 } else {
645 plan.right
646 };
647 let mut returned = 0usize;
648 loop {
649 if returned == out.len() {
650 return Ok(Q42RangeNestedLoopJoinPage {
651 returned,
652 done: false,
653 });
654 }
655 if state.wrappers.emitted >= plan.limit {
656 return Ok(Q42RangeNestedLoopJoinPage {
657 returned,
658 done: true,
659 });
660 }
661 if state.probe_index >= state.probe_count {
662 if state.probe_exhausted {
663 return Ok(Q42RangeNestedLoopJoinPage {
664 returned,
665 done: true,
666 });
667 }
668 let (count, next) = page_fn(probe_pattern, state.probe_scan, probe_rows)?;
669 state.probe_count = count;
670 state.probe_index = 0;
671 state.match_offset = 0;
672 state.probe_scan = next.unwrap_or_default();
673 state.probe_exhausted = next.is_none();
674 if state.probe_count == 0 {
675 if state.probe_exhausted {
676 return Ok(Q42RangeNestedLoopJoinPage {
677 returned,
678 done: true,
679 });
680 }
681 continue;
682 }
683 }
684 let (key_vars, key_n) = shared_join_vars(plan.left, plan.right, ctx, plan.join_var);
685 if state.probe_index == 0
686 && state.match_offset == 0
687 && state.probe_count >= 32
688 && table.iter().filter(|s| s.occupied).count() >= 32
689 {
690 let produced = emit_matches_accel(
691 table,
692 &probe_rows[..state.probe_count],
693 &key_vars[..key_n as usize],
694 join_out,
695 );
696 state.probe_index = state.probe_count;
697 let applied = apply_select_wrappers(
698 ctx,
699 &plan.filters,
700 plan.filter_count,
701 plan.projection,
702 plan.projection_count,
703 plan.limit,
704 plan.offset,
705 &mut state.wrappers,
706 &join_out[..produced],
707 &mut out[returned..],
708 )?;
709 returned += applied.returned;
710 if applied.limit_reached || returned == out.len() {
711 return Ok(Q42RangeNestedLoopJoinPage {
712 returned,
713 done: applied.limit_reached,
714 });
715 }
716 continue;
717 }
718 let probe = probe_rows[state.probe_index];
719 let produced = emit_matches(
720 table,
721 &probe,
722 &key_vars[..key_n as usize],
723 &mut state.match_offset,
724 join_out,
725 );
726 let applied = apply_select_wrappers(
727 ctx,
728 &plan.filters,
729 plan.filter_count,
730 plan.projection,
731 plan.projection_count,
732 plan.limit,
733 plan.offset,
734 &mut state.wrappers,
735 &join_out[..produced],
736 &mut out[returned..],
737 )?;
738 returned += applied.returned;
739 if state.match_offset >= table.len() || table.is_empty() {
740 state.probe_index += 1;
741 state.match_offset = 0;
742 }
743 if applied.limit_reached {
744 return Ok(Q42RangeNestedLoopJoinPage {
745 returned,
746 done: true,
747 });
748 }
749 if returned == out.len() {
750 return Ok(Q42RangeNestedLoopJoinPage {
751 returned,
752 done: false,
753 });
754 }
755 }
756}
757
758#[cfg(test)]
759mod tests {
760 use super::*;
761 use crate::q42_volume::{write_unified_volume, LocalFileRangeSource, Q42RangeVolume};
762
763 fn quin(s: u64, p: u64, o: u64) -> NQuin {
764 NQuin {
765 subject: s,
766 predicate: p,
767 object: o,
768 context: 0,
769 metadata: 0,
770 parity: 0,
771 }
772 }
773
774 fn test_volume(quins: &[NQuin]) -> (tempfile::TempDir, Q42RangeVolume<LocalFileRangeSource>) {
775 let dir = tempfile::TempDir::new().unwrap();
776 let path = dir.path().join("hash-join.q42");
777 let lo = quins.iter().map(|q| q.object).min().unwrap_or(0);
778 let hi = quins.iter().map(|q| q.object).max().unwrap_or(0);
779 write_unified_volume(
780 &path,
781 &std::collections::HashMap::new(),
782 &[(lo, hi)],
783 &[quins.to_vec()],
784 )
785 .unwrap();
786 let source = LocalFileRangeSource::open(&path).unwrap();
787 (dir, Q42RangeVolume::open(source).unwrap())
788 }
789
790 fn join_plan() -> Q42RangeHashJoinPlan {
791 Q42RangeHashJoinPlan {
792 left: Q42RangeTriplePattern {
793 subject: 0,
794 predicate: 20,
795 object: 1,
796 },
797 right: Q42RangeTriplePattern {
798 subject: 1,
799 predicate: 40,
800 object: 2,
801 },
802 join_var: 1,
803 projection: [0; MAX_VARIABLES],
804 projection_count: 0,
805 filters: [0; 8],
806 filter_count: 0,
807 limit: u64::MAX,
808 offset: 0,
809 }
810 }
811
812 #[test]
813 fn accepts_nested_loop_join_tree() {
814 let mut plan = ExecutionPlan::new();
815 let left = plan
816 .add_operator(
817 PhysicalOperatorType::TripleScan {
818 subject: 0,
819 predicate: 20,
820 object: 1,
821 },
822 1,
823 )
824 .unwrap();
825 let right = plan
826 .add_operator(
827 PhysicalOperatorType::TripleScan {
828 subject: 1,
829 predicate: 40,
830 object: 2,
831 },
832 1,
833 )
834 .unwrap();
835 plan.root_operator = plan
836 .add_operator(
837 PhysicalOperatorType::NestedLoopJoin {
838 left,
839 right,
840 join_var: 1,
841 },
842 1,
843 )
844 .unwrap();
845 let compiled = Q42RangeHashJoinPlan::from_execution_plan(&plan).unwrap();
846 assert_eq!(compiled.join_var, 1);
847 assert_eq!(compiled.right.predicate, 40);
848 }
849
850 #[test]
851 fn hashes_smaller_side_and_joins() {
852 let left = quin(10, 20, 30);
853 let right = quin(30, 40, 50);
854 let extra = quin(31, 40, 51);
855 let (_dir, volume) = test_volume(&[left, right, extra]);
856 let mut ctx = SparqlQueryContext::new();
857 ctx.variable_count = 3;
858 let mut table = [Q42RangeHashJoinSlot::default(); 8];
859 let mut compressed = [0u8; crate::q42_volume::MAX_COMPRESSED_SUPERBLOCK_SIZE];
860 let mut decoded = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
861 let mut quins = [NQuin::default(); 4];
862 let mut probe_rows = [BindingRow::default(); 4];
863 let mut join_out = [BindingRow::default(); 4];
864 let mut out = [BindingRow::default(); 4];
865 let mut state = Q42RangeHashJoinState::default();
866 let page = execute_range_hash_join_page_into(
867 &volume,
868 join_plan(),
869 &ctx,
870 &mut state,
871 &mut table,
872 &mut compressed,
873 &mut decoded,
874 &mut quins,
875 &mut probe_rows,
876 &mut join_out,
877 &mut out,
878 )
879 .unwrap();
880 assert!(page.done);
881 assert_eq!(page.returned, 1);
882 assert_eq!(out[0].get(0), Some(10));
883 assert_eq!(out[0].get(1), Some(30));
884 assert_eq!(out[0].get(2), Some(50));
885 assert!(!state.build_is_right);
886 }
887
888 #[test]
889 fn cap_exceeded_tells_planner_to_keep_nested_loop() {
890 let left_a = quin(10, 20, 30);
891 let left_b = quin(11, 20, 32);
892 let right_a = quin(30, 40, 50);
893 let right_b = quin(32, 40, 51);
894 let (_dir, volume) = test_volume(&[left_a, left_b, right_a, right_b]);
895 let mut ctx = SparqlQueryContext::new();
896 ctx.variable_count = 3;
897 let mut table = [Q42RangeHashJoinSlot::default(); 1];
898 let mut compressed = [0u8; crate::q42_volume::MAX_COMPRESSED_SUPERBLOCK_SIZE];
899 let mut decoded = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
900 let mut quins = [NQuin::default(); 4];
901 let mut probe_rows = [BindingRow::default(); 4];
902 let mut join_out = [BindingRow::default(); 4];
903 let mut out = [BindingRow::default(); 4];
904 let mut state = Q42RangeHashJoinState::default();
905 let err = execute_range_hash_join_page_into(
906 &volume,
907 join_plan(),
908 &ctx,
909 &mut state,
910 &mut table,
911 &mut compressed,
912 &mut decoded,
913 &mut quins,
914 &mut probe_rows,
915 &mut join_out,
916 &mut out,
917 )
918 .unwrap_err();
919 assert!(
920 err.contains("planner must keep NestedLoopJoin"),
921 "unexpected error: {err}"
922 );
923 assert!(!state.built);
924 }
925
926 #[test]
927 fn empty_table_is_a_cap_error() {
928 let left = quin(10, 20, 30);
929 let right = quin(30, 40, 50);
930 let (_dir, volume) = test_volume(&[left, right]);
931 let mut ctx = SparqlQueryContext::new();
932 ctx.variable_count = 3;
933 let mut table = [];
934 let mut compressed = [0u8; crate::q42_volume::MAX_COMPRESSED_SUPERBLOCK_SIZE];
935 let mut decoded = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
936 let mut quins = [NQuin::default(); 2];
937 let mut probe_rows = [BindingRow::default(); 2];
938 let mut join_out = [BindingRow::default(); 2];
939 let mut out = [BindingRow::default(); 2];
940 let mut state = Q42RangeHashJoinState::default();
941 let err = execute_range_hash_join_page_into(
942 &volume,
943 join_plan(),
944 &ctx,
945 &mut state,
946 &mut table,
947 &mut compressed,
948 &mut decoded,
949 &mut quins,
950 &mut probe_rows,
951 &mut join_out,
952 &mut out,
953 )
954 .unwrap_err();
955 assert!(err.contains("NestedLoopJoin"));
956 }
957}