1use crate::lexicon::generate_embedded_triple_id;
6use crate::rdf_star::is_virtual_id;
7use crate::sparql_aggregates::{AggregationContext, GroupKey};
8use crate::sparql_ast::*;
9use crate::sparql_filter::{EvalResult, ExpressionEvaluator};
10use crate::sparql_planner::*;
11use crate::NQuin;
12
13#[cfg(not(target_arch = "wasm32"))]
14mod range_q42_exec {
15 use super::*;
16
17 #[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
21 pub struct Q42RangeSparqlCursor {
22 pub scan: crate::q42_volume::Q42RangeQueryCursor,
23 }
24
25 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
26 pub struct Q42RangeSparqlPage {
27 pub returned: usize,
28 pub next_cursor: Option<Q42RangeSparqlCursor>,
29 }
30
31 #[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
32 pub struct Q42RangeVolumeSetSparqlCursor {
33 pub scan: crate::q42_volume::Q42VolumeSetQueryCursor,
34 }
35
36 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
37 pub struct Q42RangeVolumeSetSparqlPage {
38 pub returned: usize,
39 pub next_cursor: Option<Q42RangeVolumeSetSparqlCursor>,
40 }
41
42 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
47 pub struct Q42RangeTripleSelectPlan {
48 pub subject: u64,
49 pub predicate: u64,
50 pub object: u64,
51 pub projection: [VariableId; MAX_VARIABLES],
52 pub projection_count: u8,
53 pub filters: [ExpressionId; 8],
54 pub filter_count: u8,
55 pub limit: u64,
56 pub offset: u64,
57 }
58
59 #[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
60 pub struct Q42RangeTripleSelectCursor {
61 pub scan: Q42RangeSparqlCursor,
62 pub skipped: u64,
63 pub emitted: u64,
64 }
65
66 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
67 pub struct Q42RangeTripleSelectPage {
68 pub returned: usize,
69 pub next_cursor: Option<Q42RangeTripleSelectCursor>,
70 }
71
72 #[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
73 pub struct Q42RangeVolumeSetTripleSelectCursor {
74 pub scan: Q42RangeVolumeSetSparqlCursor,
75 pub skipped: u64,
76 pub emitted: u64,
77 }
78
79 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
80 pub struct Q42RangeVolumeSetTripleSelectPage {
81 pub returned: usize,
82 pub next_cursor: Option<Q42RangeVolumeSetTripleSelectCursor>,
83 }
84
85 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
86 pub struct Q42RangeTriplePattern {
87 pub subject: u64,
88 pub predicate: u64,
89 pub object: u64,
90 }
91
92 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
93 pub struct Q42RangeNestedLoopJoinPlan {
94 pub left: Q42RangeTriplePattern,
95 pub right: Q42RangeTriplePattern,
96 }
97
98 #[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
99 pub struct Q42RangeNestedLoopJoinState {
100 pub left_scan: Q42RangeSparqlCursor,
101 pub right_scan: Q42RangeSparqlCursor,
102 pub left_count: usize,
103 pub left_index: usize,
104 pub left_exhausted: bool,
105 pub right_active: bool,
106 }
107
108 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
109 pub struct Q42RangeNestedLoopJoinPage {
110 pub returned: usize,
111 pub done: bool,
112 }
113
114 #[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
118 pub struct Q42RangeVolumeSetNestedLoopJoinState {
119 pub left_scan: Q42RangeVolumeSetSparqlCursor,
120 pub right_scan: Q42RangeVolumeSetSparqlCursor,
121 pub left_count: usize,
122 pub left_index: usize,
123 pub left_exhausted: bool,
124 pub right_active: bool,
125 }
126
127 impl Q42RangeNestedLoopJoinPlan {
128 pub fn from_execution_plan(plan: &ExecutionPlan) -> Result<Self, String> {
130 Self::from_join_root(plan, plan.root_operator)
131 }
132
133 pub fn from_join_root(plan: &ExecutionPlan, root: OperatorId) -> Result<Self, String> {
135 if plan.operator_count == 0 || root as usize >= plan.operator_count as usize {
136 return Err("range join requires a non-empty execution plan".to_string());
137 }
138 let PhysicalOperatorType::NestedLoopJoin { left, right, .. } =
139 plan.operators[root as usize].operator_type
140 else {
141 return Err("range join currently requires a NestedLoopJoin".to_string());
142 };
143 let triple = |operator: OperatorId| -> Result<Q42RangeTriplePattern, String> {
144 let Some(entry) = plan.operators.get(operator as usize) else {
145 return Err("range join input operator is out of bounds".to_string());
146 };
147 match entry.operator_type {
148 PhysicalOperatorType::TripleScan {
149 subject,
150 predicate,
151 object,
152 } => Ok(Q42RangeTriplePattern {
153 subject,
154 predicate,
155 object,
156 }),
157 _ => Err("range join currently requires TripleScan inputs".to_string()),
158 }
159 };
160 Ok(Self {
161 left: triple(left)?,
162 right: triple(right)?,
163 })
164 }
165 }
166
167 pub fn execute_range_nested_loop_join_page_into<S: crate::q42_volume::Q42RangeSource>(
172 volume: &crate::q42_volume::Q42RangeVolume<S>,
173 plan: Q42RangeNestedLoopJoinPlan,
174 ctx: &SparqlQueryContext,
175 state: &mut Q42RangeNestedLoopJoinState,
176 compressed: &mut [u8],
177 decoded: &mut [u8],
178 quin_scratch: &mut [NQuin],
179 left_rows: &mut [BindingRow],
180 right_rows: &mut [BindingRow],
181 out: &mut [BindingRow],
182 ) -> Result<Q42RangeNestedLoopJoinPage, String> {
183 if quin_scratch.is_empty()
184 || left_rows.len() < quin_scratch.len()
185 || right_rows.len() < quin_scratch.len()
186 || out.len() < quin_scratch.len()
187 {
188 return Err(
189 "range nested-loop join requires row buffers at least as large as Quin scratch"
190 .to_string(),
191 );
192 }
193 let mut returned = 0usize;
194 loop {
195 if returned + quin_scratch.len() > out.len() {
196 return Ok(Q42RangeNestedLoopJoinPage {
197 returned,
198 done: false,
199 });
200 }
201 if state.left_index >= state.left_count {
202 if state.left_exhausted {
203 return Ok(Q42RangeNestedLoopJoinPage {
204 returned,
205 done: true,
206 });
207 }
208 let page = execute_range_triple_page_into(
209 volume,
210 plan.left.subject,
211 plan.left.predicate,
212 plan.left.object,
213 None,
214 ctx,
215 &BindingRow::default(),
216 state.left_scan,
217 compressed,
218 decoded,
219 quin_scratch,
220 left_rows,
221 )?;
222 state.left_count = page.returned;
223 state.left_index = 0;
224 state.left_scan = page.next_cursor.unwrap_or_default();
225 state.left_exhausted = page.next_cursor.is_none();
226 state.right_active = false;
227 if state.left_count == 0 {
228 if state.left_exhausted {
229 return Ok(Q42RangeNestedLoopJoinPage {
230 returned,
231 done: true,
232 });
233 }
234 continue;
235 }
236 }
237 let input = left_rows[state.left_index];
238 let page = execute_range_triple_page_into(
239 volume,
240 plan.right.subject,
241 plan.right.predicate,
242 plan.right.object,
243 None,
244 ctx,
245 &input,
246 if state.right_active {
247 state.right_scan
248 } else {
249 Q42RangeSparqlCursor::default()
250 },
251 compressed,
252 decoded,
253 quin_scratch,
254 right_rows,
255 )?;
256 out[returned..returned + page.returned].copy_from_slice(&right_rows[..page.returned]);
257 returned += page.returned;
258 match page.next_cursor {
259 Some(next) => {
260 state.right_scan = next;
261 state.right_active = true;
262 }
263 None => {
264 state.left_index += 1;
265 state.right_scan = Q42RangeSparqlCursor::default();
266 state.right_active = false;
267 }
268 }
269 if returned + quin_scratch.len() > out.len() {
270 return Ok(Q42RangeNestedLoopJoinPage {
271 returned,
272 done: false,
273 });
274 }
275 }
276 }
277
278 pub fn execute_range_volume_set_nested_loop_join_page_into<
283 S: crate::q42_volume::Q42RangeSource,
284 >(
285 volumes: &crate::q42_volume::Q42RangeVolumeSet<S>,
286 plan: Q42RangeNestedLoopJoinPlan,
287 ctx: &SparqlQueryContext,
288 state: &mut Q42RangeVolumeSetNestedLoopJoinState,
289 compressed: &mut [u8],
290 decoded: &mut [u8],
291 quin_scratch: &mut [NQuin],
292 left_rows: &mut [BindingRow],
293 right_rows: &mut [BindingRow],
294 out: &mut [BindingRow],
295 ) -> Result<Q42RangeNestedLoopJoinPage, String> {
296 if quin_scratch.is_empty()
297 || left_rows.len() < quin_scratch.len()
298 || right_rows.len() < quin_scratch.len()
299 || out.len() < quin_scratch.len()
300 {
301 return Err(
302 "range nested-loop join requires row buffers at least as large as Quin scratch"
303 .to_string(),
304 );
305 }
306 let mut returned = 0usize;
307 loop {
308 if returned + quin_scratch.len() > out.len() {
309 return Ok(Q42RangeNestedLoopJoinPage {
310 returned,
311 done: false,
312 });
313 }
314 if state.left_index >= state.left_count {
315 if state.left_exhausted {
316 return Ok(Q42RangeNestedLoopJoinPage {
317 returned,
318 done: true,
319 });
320 }
321 let page = execute_range_volume_set_triple_page_into(
322 volumes,
323 plan.left.subject,
324 plan.left.predicate,
325 plan.left.object,
326 None,
327 ctx,
328 &BindingRow::default(),
329 state.left_scan,
330 compressed,
331 decoded,
332 quin_scratch,
333 left_rows,
334 )?;
335 state.left_count = page.returned;
336 state.left_index = 0;
337 state.left_scan = page.next_cursor.unwrap_or_default();
338 state.left_exhausted = page.next_cursor.is_none();
339 state.right_active = false;
340 if state.left_count == 0 {
341 if state.left_exhausted {
342 return Ok(Q42RangeNestedLoopJoinPage {
343 returned,
344 done: true,
345 });
346 }
347 continue;
348 }
349 }
350 let input = left_rows[state.left_index];
351 let page = execute_range_volume_set_triple_page_into(
352 volumes,
353 plan.right.subject,
354 plan.right.predicate,
355 plan.right.object,
356 None,
357 ctx,
358 &input,
359 if state.right_active {
360 state.right_scan
361 } else {
362 Q42RangeVolumeSetSparqlCursor::default()
363 },
364 compressed,
365 decoded,
366 quin_scratch,
367 right_rows,
368 )?;
369 out[returned..returned + page.returned].copy_from_slice(&right_rows[..page.returned]);
370 returned += page.returned;
371 match page.next_cursor {
372 Some(next) => {
373 state.right_scan = next;
374 state.right_active = true;
375 }
376 None => {
377 state.left_index += 1;
378 state.right_scan = Q42RangeVolumeSetSparqlCursor::default();
379 state.right_active = false;
380 }
381 }
382 if returned + quin_scratch.len() > out.len() {
383 return Ok(Q42RangeNestedLoopJoinPage {
384 returned,
385 done: false,
386 });
387 }
388 }
389 }
390
391 impl Q42RangeTripleSelectPlan {
392 pub fn from_execution_plan(plan: &ExecutionPlan) -> Result<Self, String> {
395 if plan.operator_count == 0
396 || plan.root_operator as usize >= plan.operator_count as usize
397 {
398 return Err("range SPARQL requires a non-empty execution plan".to_string());
399 }
400 let mut operator = plan.root_operator;
401 let mut projection = [0; MAX_VARIABLES];
402 let mut projection_count = 0;
403 let mut filters = [0; 8];
404 let mut filter_count = 0usize;
405 let mut limit = u64::MAX;
406 let mut offset = 0;
407 loop {
408 match plan.operators[operator as usize].operator_type {
409 PhysicalOperatorType::Project { input, vars, var_count } => {
410 if projection_count != 0 { return Err("range SPARQL does not support nested projections".to_string()); }
411 projection = vars;
412 projection_count = var_count;
413 operator = input;
414 }
415 PhysicalOperatorType::Limit { input, limit: configured, offset: configured_offset } => {
416 if limit != u64::MAX || offset != 0 { return Err("range SPARQL does not support nested limits".to_string()); }
417 limit = configured;
418 offset = configured_offset;
419 operator = input;
420 }
421 PhysicalOperatorType::Filter { input, expression } => {
422 if filter_count == filters.len() {
423 return Err("range SPARQL supports at most eight stacked FILTER operators".to_string());
424 }
425 filters[filter_count] = expression;
426 filter_count += 1;
427 operator = input;
428 }
429 PhysicalOperatorType::TripleScan { subject, predicate, object } => {
430 return Ok(Self { subject, predicate, object, projection, projection_count, filters, filter_count: filter_count as u8, limit, offset });
431 }
432 _ => return Err("range SPARQL currently supports one TripleScan with optional PROJECT and LIMIT/OFFSET".to_string()),
433 }
434 }
435 }
436 }
437
438 pub fn execute_range_triple_select_page_into<S: crate::q42_volume::Q42RangeSource>(
440 volume: &crate::q42_volume::Q42RangeVolume<S>,
441 plan: Q42RangeTripleSelectPlan,
442 ctx: &SparqlQueryContext,
443 cursor: Q42RangeTripleSelectCursor,
444 compressed: &mut [u8],
445 decoded: &mut [u8],
446 quin_scratch: &mut [NQuin],
447 out: &mut [BindingRow],
448 ) -> Result<Q42RangeTripleSelectPage, String> {
449 let source_page = execute_range_triple_page_into(
450 volume,
451 plan.subject,
452 plan.predicate,
453 plan.object,
454 None,
455 ctx,
456 &BindingRow::default(),
457 cursor.scan,
458 compressed,
459 decoded,
460 quin_scratch,
461 out,
462 )?;
463 let mut returned = 0usize;
464 let mut skipped = cursor.skipped;
465 let mut emitted = cursor.emitted;
466 for index in 0..source_page.returned {
467 let mut accepted = true;
468 for filter in plan.filters.iter().take(plan.filter_count as usize) {
469 if !matches!(
470 ExpressionEvaluator::evaluate(*filter, ctx, &out[index]),
471 Ok(EvalResult::Boolean(true))
472 ) {
473 accepted = false;
474 break;
475 }
476 }
477 if !accepted {
478 continue;
479 }
480 if skipped < plan.offset {
481 skipped += 1;
482 continue;
483 }
484 if emitted >= plan.limit {
485 return Ok(Q42RangeTripleSelectPage {
486 returned,
487 next_cursor: None,
488 });
489 }
490 let mut row = out[index];
491 if plan.projection_count != 0 {
492 let mut projected = BindingRow::default();
493 for variable in plan.projection.iter().take(plan.projection_count as usize) {
494 if let Some(value) = row.get(*variable) {
495 projected.set(*variable, value);
496 }
497 }
498 row = projected;
499 }
500 out[returned] = row;
501 returned += 1;
502 emitted += 1;
503 }
504 Ok(Q42RangeTripleSelectPage {
505 returned,
506 next_cursor: if emitted >= plan.limit {
507 None
508 } else {
509 source_page
510 .next_cursor
511 .map(|scan| Q42RangeTripleSelectCursor {
512 scan,
513 skipped,
514 emitted,
515 })
516 },
517 })
518 }
519
520 pub fn execute_range_volume_set_triple_select_page_into<
523 S: crate::q42_volume::Q42RangeSource,
524 >(
525 volumes: &crate::q42_volume::Q42RangeVolumeSet<S>,
526 plan: Q42RangeTripleSelectPlan,
527 ctx: &SparqlQueryContext,
528 cursor: Q42RangeVolumeSetTripleSelectCursor,
529 compressed: &mut [u8],
530 decoded: &mut [u8],
531 quin_scratch: &mut [NQuin],
532 out: &mut [BindingRow],
533 ) -> Result<Q42RangeVolumeSetTripleSelectPage, String> {
534 let source_page = execute_range_volume_set_triple_page_into(
535 volumes,
536 plan.subject,
537 plan.predicate,
538 plan.object,
539 None,
540 ctx,
541 &BindingRow::default(),
542 cursor.scan,
543 compressed,
544 decoded,
545 quin_scratch,
546 out,
547 )?;
548 let mut returned = 0usize;
549 let mut skipped = cursor.skipped;
550 let mut emitted = cursor.emitted;
551 for index in 0..source_page.returned {
552 let mut accepted = true;
553 for filter in plan.filters.iter().take(plan.filter_count as usize) {
554 if !matches!(
555 ExpressionEvaluator::evaluate(*filter, ctx, &out[index]),
556 Ok(EvalResult::Boolean(true))
557 ) {
558 accepted = false;
559 break;
560 }
561 }
562 if !accepted {
563 continue;
564 }
565 if skipped < plan.offset {
566 skipped += 1;
567 continue;
568 }
569 if emitted >= plan.limit {
570 return Ok(Q42RangeVolumeSetTripleSelectPage {
571 returned,
572 next_cursor: None,
573 });
574 }
575 let mut row = out[index];
576 if plan.projection_count != 0 {
577 let mut projected = BindingRow::default();
578 for variable in plan.projection.iter().take(plan.projection_count as usize) {
579 if let Some(value) = row.get(*variable) {
580 projected.set(*variable, value);
581 }
582 }
583 row = projected;
584 }
585 out[returned] = row;
586 returned += 1;
587 emitted += 1;
588 }
589 Ok(Q42RangeVolumeSetTripleSelectPage {
590 returned,
591 next_cursor: if emitted >= plan.limit {
592 None
593 } else {
594 source_page
595 .next_cursor
596 .map(|scan| Q42RangeVolumeSetTripleSelectCursor {
597 scan,
598 skipped,
599 emitted,
600 })
601 },
602 })
603 }
604
605 pub fn execute_range_triple_page_into<S: crate::q42_volume::Q42RangeSource>(
610 volume: &crate::q42_volume::Q42RangeVolume<S>,
611 subject: u64,
612 predicate: u64,
613 object: u64,
614 context: Option<u64>,
615 ctx: &SparqlQueryContext,
616 input: &BindingRow,
617 cursor: Q42RangeSparqlCursor,
618 compressed: &mut [u8],
619 decoded: &mut [u8],
620 quin_scratch: &mut [NQuin],
621 out: &mut [BindingRow],
622 ) -> Result<Q42RangeSparqlPage, String> {
623 if quin_scratch.is_empty() || out.is_empty() {
624 return Err("range SPARQL page requires non-empty Quin and row buffers".to_string());
625 }
626 let bound = |term: u64| match term_is_var(term, ctx) {
627 Some(variable) => input.get(variable),
628 None => Some(term),
629 };
630 let pattern = crate::q42_volume::Q42RangeQueryPattern {
631 subject: bound(subject),
632 predicate: bound(predicate),
633 object: bound(object),
634 context,
635 };
636 let page = volume
637 .execute_query_page_into(
638 crate::q42_volume::Q42RangeQueryPlan::for_pattern(pattern),
639 cursor.scan,
640 compressed,
641 decoded,
642 quin_scratch,
643 )
644 .map_err(|error| format!("range Q42 triple scan: {error}"))?;
645 let mut returned = 0usize;
646 for quin in &quin_scratch[..page.returned] {
647 let mut row = *input;
648 if !bind_var(&mut row, subject, quin.subject, ctx)
649 || !bind_var(&mut row, predicate, quin.predicate, ctx)
650 || !bind_var(&mut row, object, quin.object, ctx)
651 {
652 continue;
653 }
654 if returned == out.len() {
655 return Err(
656 "range SPARQL row buffer is smaller than Quin scratch buffer".to_string(),
657 );
658 }
659 out[returned] = row;
660 returned += 1;
661 }
662 Ok(Q42RangeSparqlPage {
663 returned,
664 next_cursor: page.next_cursor.map(|scan| Q42RangeSparqlCursor { scan }),
665 })
666 }
667
668 pub fn execute_range_volume_set_triple_page_into<S: crate::q42_volume::Q42RangeSource>(
672 volumes: &crate::q42_volume::Q42RangeVolumeSet<S>,
673 subject: u64,
674 predicate: u64,
675 object: u64,
676 context: Option<u64>,
677 ctx: &SparqlQueryContext,
678 input: &BindingRow,
679 cursor: Q42RangeVolumeSetSparqlCursor,
680 compressed: &mut [u8],
681 decoded: &mut [u8],
682 quin_scratch: &mut [NQuin],
683 out: &mut [BindingRow],
684 ) -> Result<Q42RangeVolumeSetSparqlPage, String> {
685 if quin_scratch.is_empty() || out.is_empty() {
686 return Err("range SPARQL page requires non-empty Quin and row buffers".to_string());
687 }
688 let bound = |term: u64| match term_is_var(term, ctx) {
689 Some(variable) => input.get(variable),
690 None => Some(term),
691 };
692 let page = volumes
693 .execute_query_page_into(
694 crate::q42_volume::Q42RangeQueryPlan::for_pattern(
695 crate::q42_volume::Q42RangeQueryPattern {
696 subject: bound(subject),
697 predicate: bound(predicate),
698 object: bound(object),
699 context,
700 },
701 ),
702 cursor.scan,
703 compressed,
704 decoded,
705 quin_scratch,
706 )
707 .map_err(|error| format!("range Q42 volume-set triple scan: {error}"))?;
708 let mut returned = 0usize;
709 for quin in &quin_scratch[..page.returned] {
710 let mut row = *input;
711 if !bind_var(&mut row, subject, quin.subject, ctx)
712 || !bind_var(&mut row, predicate, quin.predicate, ctx)
713 || !bind_var(&mut row, object, quin.object, ctx)
714 {
715 continue;
716 }
717 if returned == out.len() {
718 return Err(
719 "range SPARQL row buffer is smaller than Quin scratch buffer".to_string(),
720 );
721 }
722 out[returned] = row;
723 returned += 1;
724 }
725 Ok(Q42RangeVolumeSetSparqlPage {
726 returned,
727 next_cursor: page
728 .next_cursor
729 .map(|scan| Q42RangeVolumeSetSparqlCursor { scan }),
730 })
731 }
732} #[cfg(not(target_arch = "wasm32"))]
735pub use range_q42_exec::*;
736
737#[inline]
740fn term_is_var(term: u64, ctx: &SparqlQueryContext) -> Option<VariableId> {
741 let id = term as usize;
742 if id < ctx.variable_count {
743 Some(term as VariableId)
744 } else {
745 None
746 }
747}
748
749#[inline]
752fn bind_var(row: &mut BindingRow, term: u64, value: u64, ctx: &SparqlQueryContext) -> bool {
753 if let Some(var) = term_is_var(term, ctx) {
754 match row.get(var) {
755 Some(bound) if bound != value => false,
756 _ => {
757 row.set(var, value);
758 true
759 }
760 }
761 } else {
762 term == value
763 }
764}
765
766pub struct QueryExecutor<'a> {
768 pub quins: &'a [NQuin],
769 resolver: Option<crate::sparql_ast::TextResolver<'a>>,
773}
774
775impl<'a> QueryExecutor<'a> {
776 pub fn new(quins: &'a [NQuin]) -> Self {
778 Self {
779 quins,
780 resolver: None,
781 }
782 }
783
784 pub fn with_resolver(
786 quins: &'a [NQuin],
787 resolver: crate::sparql_ast::TextResolver<'a>,
788 ) -> Self {
789 Self {
790 quins,
791 resolver: Some(resolver),
792 }
793 }
794
795 pub fn execute(
797 &self,
798 plan: &ExecutionPlan,
799 ctx: &SparqlQueryContext,
800 ) -> Result<Vec<BindingRow>, String> {
801 if plan.operator_count == 0 {
802 return Err("Empty execution plan".to_string());
803 }
804 let mut results = Vec::new();
805 let mut row = BindingRow::new();
806
807 if self.execute_operator(plan.root_operator, plan, ctx, &mut row, &mut results)? {
808 return Ok(results);
809 }
810
811 Ok(results)
812 }
813
814 pub fn execute_ask(
816 &self,
817 plan: &ExecutionPlan,
818 ctx: &SparqlQueryContext,
819 ) -> Result<bool, String> {
820 let mut results = Vec::new();
821 let mut row = BindingRow::new();
822
823 self.execute_operator(plan.root_operator, plan, ctx, &mut row, &mut results)?;
824
825 Ok(!results.is_empty())
826 }
827
828 fn collect_template_triples(
834 pattern_id: PatternId,
835 ctx: &SparqlQueryContext,
836 out: &mut Vec<(u64, u64, u64)>,
837 ) {
838 match ctx.patterns.get(pattern_id as usize) {
839 Some(Pattern::Triple {
840 subject,
841 predicate,
842 object,
843 }) => out.push((*subject, *predicate, *object)),
844 Some(Pattern::Group { start_idx, len }) => {
845 for i in *start_idx..(*start_idx + *len) {
846 Self::collect_template_triples(i, ctx, out);
847 }
848 }
849 _ => {}
850 }
851 }
852
853 pub fn execute_construct(
862 &self,
863 plan: &ExecutionPlan,
864 ctx: &SparqlQueryContext,
865 template_pattern: PatternId,
866 ) -> Result<Vec<BindingRow>, String> {
867 let solutions = self.execute(plan, ctx)?;
868
869 let mut templates: Vec<(u64, u64, u64)> = Vec::new();
870 Self::collect_template_triples(template_pattern, ctx, &mut templates);
871
872 let resolve = |term: u64, row: &BindingRow| -> Option<u64> {
873 match term_is_var(term, ctx) {
874 Some(var) => row.get(var), None => Some(term), }
877 };
878
879 let mut seen = std::collections::HashSet::new();
880 let mut out = Vec::new();
881 for sol in &solutions {
882 for &(s, p, o) in &templates {
883 let (sv, pv, ov) = match (resolve(s, sol), resolve(p, sol), resolve(o, sol)) {
884 (Some(sv), Some(pv), Some(ov)) => (sv, pv, ov),
885 _ => continue,
886 };
887 if seen.insert((sv, pv, ov)) {
888 let mut row = BindingRow::new();
889 row.set(0, sv);
890 row.set(1, pv);
891 row.set(2, ov);
892 out.push(row);
893 }
894 }
895 }
896 Ok(out)
897 }
898
899 pub fn execute_describe(
906 &self,
907 plan: &ExecutionPlan,
908 ctx: &SparqlQueryContext,
909 describe: &DescribeQuery,
910 ) -> Result<Vec<BindingRow>, String> {
911 let solutions = if describe.root_pattern.is_some() {
914 self.execute(plan, ctx)?
915 } else {
916 Vec::new()
917 };
918
919 let mut resources: Vec<u64> = Vec::new();
920 let add = |r: u64, resources: &mut Vec<u64>| {
921 if !resources.contains(&r) {
922 resources.push(r);
923 }
924 };
925
926 if describe.var_count == 0 {
927 for sol in &solutions {
929 for var in 0..ctx.variable_count as VariableId {
930 if let Some(v) = sol.get(var) {
931 add(v, &mut resources);
932 }
933 }
934 }
935 } else {
936 for i in 0..describe.var_count as usize {
937 let term = describe.vars_or_ids[i];
938 match term_is_var(term, ctx) {
939 Some(var) => {
940 for sol in &solutions {
941 if let Some(v) = sol.get(var) {
942 add(v, &mut resources);
943 }
944 }
945 }
946 None => add(term, &mut resources),
947 }
948 }
949 }
950
951 let mut seen = std::collections::HashSet::new();
952 let mut out = Vec::new();
953 for &r in &resources {
954 for q in self.quins {
955 if q.subject == r && seen.insert((q.subject, q.predicate, q.object)) {
956 let mut row = BindingRow::new();
957 row.set(0, q.subject);
958 row.set(1, q.predicate);
959 row.set(2, q.object);
960 out.push(row);
961 }
962 }
963 }
964 Ok(out)
965 }
966
967 fn execute_operator(
971 &self,
972 op_id: OperatorId,
973 plan: &ExecutionPlan,
974 ctx: &SparqlQueryContext,
975 row: &mut BindingRow,
976 results: &mut Vec<BindingRow>,
977 ) -> Result<bool, String> {
978 let operator = plan
979 .operators
980 .get(op_id as usize)
981 .ok_or("Operator ID out of bounds")?;
982
983 match operator.operator_type {
984 PhysicalOperatorType::SubjectScan { subject } => {
985 self.execute_subject_scan(subject, ctx, row, results)
986 }
987 PhysicalOperatorType::PredicateScan { predicate } => {
988 self.execute_predicate_scan(predicate, ctx, row, results)
989 }
990 PhysicalOperatorType::ObjectScan { object } => {
991 self.execute_object_scan(object, ctx, row, results)
992 }
993 PhysicalOperatorType::TripleScan {
994 subject,
995 predicate,
996 object,
997 } => self.execute_triple_scan(subject, predicate, object, ctx, row, results),
998 PhysicalOperatorType::HashJoin {
999 left,
1000 right,
1001 join_var,
1002 } => self.execute_hash_join(left, right, join_var, plan, ctx, row, results),
1003 PhysicalOperatorType::NestedLoopJoin {
1004 left,
1005 right,
1006 join_var,
1007 } => self.execute_nested_loop_join(left, right, join_var, plan, ctx, row, results),
1008 PhysicalOperatorType::Filter { input, expression } => {
1009 self.execute_filter(input, expression, plan, ctx, row, results)
1010 }
1011 PhysicalOperatorType::Bind {
1012 input,
1013 var,
1014 expression,
1015 } => self.execute_bind(input, var, expression, plan, ctx, row, results),
1016 PhysicalOperatorType::Project {
1017 input,
1018 vars,
1019 var_count,
1020 } => self.execute_project(input, vars, var_count, plan, ctx, row, results),
1021 PhysicalOperatorType::Limit {
1022 input,
1023 limit,
1024 offset,
1025 } => self.execute_limit(input, limit, offset, plan, ctx, row, results),
1026 PhysicalOperatorType::Sort {
1027 input,
1028 order_by,
1029 order_count,
1030 ascending,
1031 } => self.execute_sort(
1032 input,
1033 &order_by,
1034 order_count,
1035 &ascending,
1036 plan,
1037 ctx,
1038 row,
1039 results,
1040 ),
1041 PhysicalOperatorType::Union { left, right } => {
1042 self.execute_union(left, right, plan, ctx, row, results)
1043 }
1044 PhysicalOperatorType::Optional { left, right } => {
1045 self.execute_optional(left, right, plan, ctx, row, results)
1046 }
1047 PhysicalOperatorType::AntiJoin { left, right } => {
1048 self.execute_anti_join(left, right, plan, ctx, row, results)
1049 }
1050 PhysicalOperatorType::Distinct { input } => {
1051 self.execute_distinct(input, plan, ctx, row, results)
1052 }
1053 PhysicalOperatorType::SubSelect { query_id } => {
1054 self.execute_sub_select(query_id, ctx, row, results)
1055 }
1056 PhysicalOperatorType::GroupBy {
1057 input,
1058 group_vars,
1059 group_var_count,
1060 aggregates,
1061 aggregate_count,
1062 } => self.execute_group_by(
1063 input,
1064 group_vars,
1065 group_var_count,
1066 aggregates,
1067 aggregate_count,
1068 plan,
1069 ctx,
1070 row,
1071 results,
1072 ),
1073 PhysicalOperatorType::Having { input, expression } => {
1074 self.execute_having(input, expression, plan, ctx, row, results)
1075 }
1076 PhysicalOperatorType::PropertyPath {
1077 subject,
1078 path_id,
1079 object,
1080 } => self.execute_property_path(subject, path_id, object, ctx, row, results),
1081 PhysicalOperatorType::Graph {
1082 graph_var_or_id,
1083 inner,
1084 } => self.execute_graph(graph_var_or_id, inner, plan, ctx, row, results),
1085 PhysicalOperatorType::Service {
1086 endpoint_did_id,
1087 inner_pattern,
1088 } => self.execute_service(endpoint_did_id, inner_pattern, plan, ctx, row, results),
1089 PhysicalOperatorType::AsOf {
1090 input,
1091 timestamp_ms,
1092 mode,
1093 } => self.execute_as_of(input, timestamp_ms, mode, plan, ctx, row, results),
1094 PhysicalOperatorType::StarTripleScan {
1095 inner_subject,
1096 inner_predicate,
1097 inner_object,
1098 outer_predicate,
1099 outer_object,
1100 } => self.execute_star_triple_scan(
1101 inner_subject,
1102 inner_predicate,
1103 inner_object,
1104 outer_predicate,
1105 outer_object,
1106 ctx,
1107 row,
1108 results,
1109 ),
1110 }
1111 }
1112
1113 fn execute_subject_scan(
1115 &self,
1116 subject: u64,
1117 _ctx: &SparqlQueryContext,
1118 _row: &mut BindingRow,
1119 results: &mut Vec<BindingRow>,
1120 ) -> Result<bool, String> {
1121 for quin in self.quins {
1123 if quin.subject == subject {
1124 let mut new_row = BindingRow::new();
1127 new_row.slots[0] = Some(quin.subject);
1128 new_row.slots[1] = Some(quin.predicate);
1129 new_row.slots[2] = Some(quin.object);
1130 results.push(new_row);
1131 }
1132 }
1133 Ok(!results.is_empty())
1134 }
1135
1136 fn execute_predicate_scan(
1139 &self,
1140 predicate: u64,
1141 _ctx: &SparqlQueryContext,
1142 _row: &mut BindingRow,
1143 results: &mut Vec<BindingRow>,
1144 ) -> Result<bool, String> {
1145 for quin in self.quins {
1146 if quin.predicate == predicate {
1147 let mut new_row = BindingRow::new();
1148 new_row.slots[0] = Some(quin.subject);
1149 new_row.slots[1] = Some(quin.predicate);
1150 new_row.slots[2] = Some(quin.object);
1151 results.push(new_row);
1152 }
1153 }
1154 Ok(!results.is_empty())
1155 }
1156
1157 fn execute_object_scan(
1159 &self,
1160 object: u64,
1161 _ctx: &SparqlQueryContext,
1162 _row: &mut BindingRow,
1163 results: &mut Vec<BindingRow>,
1164 ) -> Result<bool, String> {
1165 for quin in self.quins {
1166 if quin.object == object {
1167 let mut new_row = BindingRow::new();
1168 new_row.slots[0] = Some(quin.subject);
1169 new_row.slots[1] = Some(quin.predicate);
1170 new_row.slots[2] = Some(quin.object);
1171 results.push(new_row);
1172 }
1173 }
1174 Ok(!results.is_empty())
1175 }
1176
1177 fn execute_triple_scan(
1180 &self,
1181 subject: u64,
1182 predicate: u64,
1183 object: u64,
1184 ctx: &SparqlQueryContext,
1185 row: &mut BindingRow,
1186 results: &mut Vec<BindingRow>,
1187 ) -> Result<bool, String> {
1188 for quin in self.quins {
1189 let mut candidate = *row;
1190 if !bind_var(&mut candidate, subject, quin.subject, ctx) {
1191 continue;
1192 }
1193 if !bind_var(&mut candidate, predicate, quin.predicate, ctx) {
1194 continue;
1195 }
1196 if !bind_var(&mut candidate, object, quin.object, ctx) {
1197 continue;
1198 }
1199 results.push(candidate);
1200 }
1201 Ok(!results.is_empty())
1202 }
1203
1204 fn execute_star_triple_scan(
1207 &self,
1208 inner_subject: u64,
1209 inner_predicate: u64,
1210 inner_object: u64,
1211 outer_predicate: u64,
1212 outer_object: u64,
1213 ctx: &SparqlQueryContext,
1214 row: &mut BindingRow,
1215 results: &mut Vec<BindingRow>,
1216 ) -> Result<bool, String> {
1217 for quin in self.quins {
1218 if !is_virtual_id(quin.subject) {
1219 continue;
1220 }
1221 let mut candidate = *row;
1222 if !bind_var(&mut candidate, outer_predicate, quin.predicate, ctx) {
1223 continue;
1224 }
1225 if !bind_var(&mut candidate, outer_object, quin.object, ctx) {
1226 continue;
1227 }
1228
1229 if let (Some(s), Some(p), Some(o)) = (
1230 term_is_var(inner_subject, ctx),
1231 term_is_var(inner_predicate, ctx),
1232 term_is_var(inner_object, ctx),
1233 ) {
1234 if let Some(components) = self.lookup_star_components(quin.subject) {
1235 candidate.set(s, components[0]);
1236 candidate.set(p, components[1]);
1237 candidate.set(o, components[2]);
1238 results.push(candidate);
1239 }
1240 } else {
1241 let expected_vid = generate_embedded_triple_id(
1242 if term_is_var(inner_subject, ctx).is_some() {
1243 0
1244 } else {
1245 inner_subject
1246 },
1247 if term_is_var(inner_predicate, ctx).is_some() {
1248 0
1249 } else {
1250 inner_predicate
1251 },
1252 if term_is_var(inner_object, ctx).is_some() {
1253 0
1254 } else {
1255 inner_object
1256 },
1257 );
1258 if quin.subject == expected_vid
1259 && bind_var(&mut candidate, outer_predicate, quin.predicate, ctx)
1260 && bind_var(&mut candidate, outer_object, quin.object, ctx)
1261 {
1262 results.push(candidate);
1263 }
1264 }
1265 }
1266 Ok(!results.is_empty())
1267 }
1268
1269 fn lookup_star_components(&self, virtual_id: u64) -> Option<[u64; 3]> {
1272 for quin in self.quins {
1273 let candidate = generate_embedded_triple_id(quin.subject, quin.predicate, quin.object);
1274 if candidate == virtual_id {
1275 return Some([quin.subject, quin.predicate, quin.object]);
1276 }
1277 }
1278 None
1279 }
1280
1281 fn execute_hash_join(
1284 &self,
1285 left: OperatorId,
1286 right: OperatorId,
1287 join_var: VariableId,
1288 plan: &ExecutionPlan,
1289 ctx: &SparqlQueryContext,
1290 _row: &mut BindingRow,
1291 results: &mut Vec<BindingRow>,
1292 ) -> Result<bool, String> {
1293 let mut left_results = Vec::new();
1294 let mut left_row = BindingRow::new();
1295 self.execute_operator(left, plan, ctx, &mut left_row, &mut left_results)?;
1296
1297 let mut right_results = Vec::new();
1298 let mut right_row = BindingRow::new();
1299 self.execute_operator(right, plan, ctx, &mut right_row, &mut right_results)?;
1300
1301 left_results
1303 .sort_unstable_by(|a, b| a.slots[join_var as usize].cmp(&b.slots[join_var as usize]));
1304 right_results
1305 .sort_unstable_by(|a, b| a.slots[join_var as usize].cmp(&b.slots[join_var as usize]));
1306
1307 let mut i = 0;
1308 let mut j = 0;
1309
1310 while i < left_results.len() && j < right_results.len() {
1311 let left_val = left_results[i].slots[join_var as usize];
1312 let right_val = right_results[j].slots[join_var as usize];
1313
1314 if left_val < right_val {
1319 i += 1;
1320 } else if left_val > right_val {
1321 j += 1;
1322 } else {
1323 let mut left_end = i + 1;
1324 while left_end < left_results.len()
1325 && left_results[left_end].slots[join_var as usize] == left_val
1326 {
1327 left_end += 1;
1328 }
1329
1330 let mut right_end = j + 1;
1331 while right_end < right_results.len()
1332 && right_results[right_end].slots[join_var as usize] == right_val
1333 {
1334 right_end += 1;
1335 }
1336
1337 for l in &left_results[i..left_end] {
1338 for r in &right_results[j..right_end] {
1339 let mut compatible = true;
1340 for k in 0..MAX_BINDINGS {
1341 if let (Some(a), Some(b)) = (l.slots[k], r.slots[k]) {
1342 if a != b {
1343 compatible = false;
1344 break;
1345 }
1346 }
1347 }
1348
1349 if compatible {
1350 let mut joined = BindingRow::new();
1351 for k in 0..MAX_BINDINGS {
1352 joined.slots[k] = l.slots[k].or(r.slots[k]);
1353 }
1354 results.push(joined);
1355 }
1356 }
1357 }
1358
1359 i = left_end;
1360 j = right_end;
1361 }
1362 }
1363
1364 Ok(!results.is_empty())
1365 }
1366
1367 fn execute_nested_loop_join(
1370 &self,
1371 left: OperatorId,
1372 right: OperatorId,
1373 _join_var: VariableId,
1374 plan: &ExecutionPlan,
1375 ctx: &SparqlQueryContext,
1376 _row: &mut BindingRow,
1377 results: &mut Vec<BindingRow>,
1378 ) -> Result<bool, String> {
1379 let mut left_results = Vec::new();
1380 let mut left_row = BindingRow::new();
1381 self.execute_operator(left, plan, ctx, &mut left_row, &mut left_results)?;
1382
1383 let mut right_results = Vec::new();
1384 let mut right_row = BindingRow::new();
1385 self.execute_operator(right, plan, ctx, &mut right_row, &mut right_results)?;
1386
1387 for l in &left_results {
1389 for r in &right_results {
1390 let mut compatible = true;
1391 for i in 0..MAX_BINDINGS {
1392 if let (Some(a), Some(b)) = (l.slots[i], r.slots[i]) {
1393 if a != b {
1394 compatible = false;
1395 break;
1396 }
1397 }
1398 }
1399
1400 if compatible {
1401 let mut joined = BindingRow::new();
1402 for i in 0..MAX_BINDINGS {
1403 joined.slots[i] = l.slots[i].or(r.slots[i]);
1404 }
1405 results.push(joined);
1406 }
1407 }
1408 }
1409
1410 Ok(!results.is_empty())
1411 }
1412
1413 fn execute_filter(
1415 &self,
1416 input: OperatorId,
1417 expression: ExpressionId,
1418 plan: &ExecutionPlan,
1419 ctx: &SparqlQueryContext,
1420 row: &mut BindingRow,
1421 results: &mut Vec<BindingRow>,
1422 ) -> Result<bool, String> {
1423 let mut input_results = Vec::new();
1424 self.execute_operator(input, plan, ctx, row, &mut input_results)?;
1425
1426 for input_row in input_results {
1430 if self.eval_filter_bool(expression, ctx, &input_row)? {
1431 results.push(input_row);
1432 }
1433 }
1434
1435 Ok(!results.is_empty())
1436 }
1437
1438 fn expr_contains_exists(expr_id: ExpressionId, ctx: &SparqlQueryContext) -> bool {
1443 match ctx.expressions.get(expr_id as usize) {
1444 Some(Expression::Exists { .. }) => true,
1445 Some(Expression::UnaryOp { expr, .. }) => Self::expr_contains_exists(*expr, ctx),
1446 Some(Expression::BinaryOp { left, right, .. }) => {
1447 Self::expr_contains_exists(*left, ctx) || Self::expr_contains_exists(*right, ctx)
1448 }
1449 _ => false,
1450 }
1451 }
1452
1453 fn eval_exists(
1457 &self,
1458 pattern: PatternId,
1459 ctx: &SparqlQueryContext,
1460 row: &BindingRow,
1461 ) -> Result<bool, String> {
1462 let mut sub_plan = ExecutionPlan::new();
1463 let op = QueryPlanner::plan_pattern(pattern, ctx, &mut sub_plan)?;
1464 sub_plan.root_operator = op;
1465 let mut seed = *row;
1466 let mut local = Vec::new();
1467 self.execute_operator(op, &sub_plan, ctx, &mut seed, &mut local)?;
1468 Ok(!local.is_empty())
1469 }
1470
1471 fn eval_filter_bool(
1475 &self,
1476 expr_id: ExpressionId,
1477 ctx: &SparqlQueryContext,
1478 row: &BindingRow,
1479 ) -> Result<bool, String> {
1480 let expr = *ctx
1481 .expressions
1482 .get(expr_id as usize)
1483 .ok_or("Expression ID out of bounds")?;
1484 match expr {
1485 Expression::Exists { pattern, negated } => {
1486 Ok(self.eval_exists(pattern, ctx, row)? ^ negated)
1487 }
1488 Expression::UnaryOp {
1489 op: UnaryOp::Not,
1490 expr,
1491 } if Self::expr_contains_exists(expr, ctx) => {
1492 Ok(!self.eval_filter_bool(expr, ctx, row)?)
1493 }
1494 Expression::BinaryOp {
1495 op: BinaryOp::And,
1496 left,
1497 right,
1498 } if Self::expr_contains_exists(left, ctx)
1499 || Self::expr_contains_exists(right, ctx) =>
1500 {
1501 Ok(self.eval_filter_bool(left, ctx, row)?
1502 && self.eval_filter_bool(right, ctx, row)?)
1503 }
1504 Expression::BinaryOp {
1505 op: BinaryOp::Or,
1506 left,
1507 right,
1508 } if Self::expr_contains_exists(left, ctx)
1509 || Self::expr_contains_exists(right, ctx) =>
1510 {
1511 Ok(self.eval_filter_bool(left, ctx, row)?
1512 || self.eval_filter_bool(right, ctx, row)?)
1513 }
1514 _ => {
1515 let r =
1516 ExpressionEvaluator::evaluate_with_resolver(expr_id, ctx, row, self.resolver)?;
1517 Ok(r.as_bool())
1518 }
1519 }
1520 }
1521
1522 fn execute_bind(
1525 &self,
1526 input: OperatorId,
1527 var: VariableId,
1528 expression: ExpressionId,
1529 plan: &ExecutionPlan,
1530 ctx: &SparqlQueryContext,
1531 row: &mut BindingRow,
1532 results: &mut Vec<BindingRow>,
1533 ) -> Result<bool, String> {
1534 let mut input_results = Vec::new();
1535 self.execute_operator(input, plan, ctx, row, &mut input_results)?;
1536
1537 for mut input_row in input_results {
1538 match ExpressionEvaluator::evaluate_with_resolver(
1545 expression,
1546 ctx,
1547 &input_row,
1548 self.resolver,
1549 ) {
1550 Ok(EvalResult::Numeric(n)) | Ok(EvalResult::Iri(n)) | Ok(EvalResult::String(n)) => {
1551 input_row.set(var, n);
1552 }
1553 Ok(EvalResult::Boolean(b)) => {
1554 input_row.set(var, b as u64);
1555 }
1556 Ok(EvalResult::Float(f)) => {
1557 input_row.set(var, f.to_bits());
1559 }
1560 Err(_) => { }
1561 }
1562 results.push(input_row);
1563 }
1564
1565 Ok(!results.is_empty())
1566 }
1567
1568 fn execute_project(
1570 &self,
1571 input: OperatorId,
1572 vars: [VariableId; MAX_VARIABLES],
1573 var_count: u8,
1574 plan: &ExecutionPlan,
1575 ctx: &SparqlQueryContext,
1576 row: &mut BindingRow,
1577 results: &mut Vec<BindingRow>,
1578 ) -> Result<bool, String> {
1579 let mut input_results = Vec::new();
1586 self.execute_operator(input, plan, ctx, row, &mut input_results)?;
1587 for in_row in input_results {
1588 let mut projected = BindingRow::new();
1589 for &v in vars.iter().take(var_count as usize) {
1590 if let Some(val) = in_row.get(v) {
1591 projected.set(v, val);
1592 }
1593 }
1594 results.push(projected);
1595 }
1596 Ok(!results.is_empty())
1597 }
1598
1599 fn execute_limit(
1601 &self,
1602 input: OperatorId,
1603 limit: u64,
1604 offset: u64,
1605 plan: &ExecutionPlan,
1606 ctx: &SparqlQueryContext,
1607 row: &mut BindingRow,
1608 results: &mut Vec<BindingRow>,
1609 ) -> Result<bool, String> {
1610 let mut all_results = Vec::new();
1611 self.execute_operator(input, plan, ctx, row, &mut all_results)?;
1612
1613 let start = offset as usize;
1615 let end = if limit == u64::MAX {
1616 all_results.len()
1617 } else {
1618 (start + limit as usize).min(all_results.len())
1619 };
1620
1621 if start < all_results.len() {
1622 results.extend_from_slice(&all_results[start..end]);
1623 }
1624
1625 Ok(!results.is_empty())
1626 }
1627
1628 fn execute_sort(
1631 &self,
1632 input: OperatorId,
1633 order_by: &[ExpressionId; MAX_ORDER_CONDITIONS],
1634 order_count: u8,
1635 ascending: &[bool; MAX_ORDER_CONDITIONS],
1636 plan: &ExecutionPlan,
1637 ctx: &SparqlQueryContext,
1638 row: &mut BindingRow,
1639 results: &mut Vec<BindingRow>,
1640 ) -> Result<bool, String> {
1641 let start_len = results.len();
1642 self.execute_operator(input, plan, ctx, row, results)?;
1643
1644 let slice = &mut results[start_len..];
1646
1647 slice.sort_unstable_by(|a, b| {
1648 for i in 0..order_count as usize {
1649 let expr = order_by[i];
1650 let asc = ascending[i];
1651
1652 let val_a =
1653 ExpressionEvaluator::evaluate_with_resolver(expr, ctx, a, self.resolver)
1654 .unwrap_or(crate::sparql_filter::EvalResult::Numeric(0));
1655 let val_b =
1656 ExpressionEvaluator::evaluate_with_resolver(expr, ctx, b, self.resolver)
1657 .unwrap_or(crate::sparql_filter::EvalResult::Numeric(0));
1658
1659 let cmp = val_a.total_cmp(&val_b);
1660 if cmp != std::cmp::Ordering::Equal {
1661 return if asc { cmp } else { cmp.reverse() };
1662 }
1663 }
1664 std::cmp::Ordering::Equal
1665 });
1666
1667 Ok(!results.is_empty())
1668 }
1669
1670 fn execute_union(
1672 &self,
1673 left: OperatorId,
1674 right: OperatorId,
1675 plan: &ExecutionPlan,
1676 ctx: &SparqlQueryContext,
1677 row: &mut BindingRow,
1678 results: &mut Vec<BindingRow>,
1679 ) -> Result<bool, String> {
1680 let _start_len = results.len();
1681
1682 self.execute_operator(left, plan, ctx, row, results)?;
1684
1685 self.execute_operator(right, plan, ctx, row, results)?;
1687
1688 Ok(!results.is_empty())
1691 }
1692
1693 fn execute_optional(
1696 &self,
1697 left: OperatorId,
1698 right: OperatorId,
1699 plan: &ExecutionPlan,
1700 ctx: &SparqlQueryContext,
1701 row: &mut BindingRow,
1702 results: &mut Vec<BindingRow>,
1703 ) -> Result<bool, String> {
1704 let mut left_results = Vec::new();
1706 let mut right_results = Vec::new();
1707 self.execute_operator(left, plan, ctx, row, &mut left_results)?;
1708
1709 for left_result in left_results {
1711 right_results.clear();
1712 let mut right_row = left_result; let right_matched =
1714 self.execute_operator(right, plan, ctx, &mut right_row, &mut right_results)?;
1715
1716 if right_matched && !right_results.is_empty() {
1717 results.extend_from_slice(&right_results);
1719 } else {
1720 results.push(left_result);
1722 }
1723 }
1724
1725 Ok(!results.is_empty())
1726 }
1727
1728 fn execute_anti_join(
1734 &self,
1735 left: OperatorId,
1736 right: OperatorId,
1737 plan: &ExecutionPlan,
1738 ctx: &SparqlQueryContext,
1739 row: &mut BindingRow,
1740 results: &mut Vec<BindingRow>,
1741 ) -> Result<bool, String> {
1742 let mut left_results = Vec::new();
1743 self.execute_operator(left, plan, ctx, row, &mut left_results)?;
1744
1745 let mut right_results = Vec::new();
1747 let mut right_row = BindingRow::new();
1748 self.execute_operator(right, plan, ctx, &mut right_row, &mut right_results)?;
1749
1750 for l in left_results {
1751 let excluded = right_results.iter().any(|r| {
1752 let mut compatible = true;
1753 let mut shares = false;
1754 for k in 0..MAX_BINDINGS {
1755 if let (Some(a), Some(b)) = (l.slots[k], r.slots[k]) {
1756 shares = true;
1757 if a != b {
1758 compatible = false;
1759 break;
1760 }
1761 }
1762 }
1763 compatible && shares
1764 });
1765 if !excluded {
1766 results.push(l);
1767 }
1768 }
1769
1770 Ok(!results.is_empty())
1771 }
1772
1773 fn execute_sub_select(
1779 &self,
1780 query_id: u16,
1781 ctx: &SparqlQueryContext,
1782 row: &BindingRow,
1783 results: &mut Vec<BindingRow>,
1784 ) -> Result<bool, String> {
1785 let subquery = *ctx
1786 .subqueries
1787 .get(query_id as usize)
1788 .ok_or("Subquery ID out of bounds")?;
1789 let sub_plan = QueryPlanner::plan(&subquery, ctx)?;
1790 let sub_rows = self.execute(&sub_plan, ctx)?;
1791
1792 for sub_row in sub_rows {
1793 let mut merged = *row;
1794 let mut compatible = true;
1795 for var in 0..ctx.variable_count as VariableId {
1796 if let Some(v) = sub_row.get(var) {
1797 match merged.get(var) {
1798 Some(existing) if existing != v => {
1799 compatible = false;
1800 break;
1801 }
1802 _ => merged.set(var, v),
1803 }
1804 }
1805 }
1806 if compatible {
1807 results.push(merged);
1808 }
1809 }
1810 Ok(!results.is_empty())
1811 }
1812
1813 fn execute_distinct(
1815 &self,
1816 input: OperatorId,
1817 plan: &ExecutionPlan,
1818 ctx: &SparqlQueryContext,
1819 row: &mut BindingRow,
1820 results: &mut Vec<BindingRow>,
1821 ) -> Result<bool, String> {
1822 let start_len = results.len();
1823 self.execute_operator(input, plan, ctx, row, results)?;
1824
1825 let slice = &mut results[start_len..];
1826 slice.sort_unstable();
1827
1828 if results.len() > start_len {
1829 let mut write_idx = start_len + 1;
1830 for read_idx in (start_len + 1)..results.len() {
1831 if results[read_idx] != results[write_idx - 1] {
1832 results[write_idx] = results[read_idx];
1833 write_idx += 1;
1834 }
1835 }
1836 results.truncate(write_idx);
1837 }
1838
1839 Ok(!results.is_empty())
1840 }
1841
1842 fn execute_group_by(
1845 &self,
1846 input: OperatorId,
1847 group_vars: [VariableId; MAX_VARIABLES],
1848 group_var_count: u8,
1849 aggregates: [crate::sparql_planner::AggregateSpec; 16],
1850 aggregate_count: u8,
1851 plan: &ExecutionPlan,
1852 ctx: &SparqlQueryContext,
1853 row: &mut BindingRow,
1854 results: &mut Vec<BindingRow>,
1855 ) -> Result<bool, String> {
1856 let mut all_results = Vec::new();
1857 self.execute_operator(input, plan, ctx, row, &mut all_results)?;
1858
1859 let mut agg_ctx = AggregationContext::new(&aggregates, aggregate_count);
1861
1862 for result in &all_results {
1863 let mut key = GroupKey::new();
1864 for i in 0..group_var_count as usize {
1865 let var_id = group_vars[i];
1866 if let Some(value) = result.get(var_id) {
1867 key.set(var_id, value);
1868 }
1869 }
1870
1871 let group_idx = agg_ctx.find_or_create_group(key)?;
1872 agg_ctx.add_values_to_group(group_idx, result);
1873 }
1874
1875 for i in 0..agg_ctx.group_count as usize {
1877 let (key, accumulators) = &agg_ctx.groups[i];
1878 let mut result_row = BindingRow::new();
1879 for j in 0..key.var_count as usize {
1880 result_row.slots[j] = Some(key.values[j]);
1881 }
1882
1883 for j in 0..aggregate_count as usize {
1885 if let Some(result_val) = accumulators[j].get_result() {
1886 let out_var = aggregates[j].output_var;
1887 result_row.slots[out_var as usize] = Some(result_val);
1888 }
1889 }
1890 results.push(result_row);
1891 }
1892
1893 Ok(!results.is_empty())
1894 }
1895
1896 fn execute_having(
1899 &self,
1900 input: OperatorId,
1901 expression: ExpressionId,
1902 plan: &ExecutionPlan,
1903 ctx: &SparqlQueryContext,
1904 row: &mut BindingRow,
1905 results: &mut Vec<BindingRow>,
1906 ) -> Result<bool, String> {
1907 let mut all_results = Vec::new();
1908 self.execute_operator(input, plan, ctx, row, &mut all_results)?;
1909
1910 for result in all_results {
1912 if self.eval_filter_bool(expression, ctx, &result)? {
1913 results.push(result);
1914 }
1915 }
1916
1917 Ok(!results.is_empty())
1918 }
1919
1920 fn execute_property_path(
1923 &self,
1924 subject: u64,
1925 path_id: PathId,
1926 object: u64,
1927 ctx: &SparqlQueryContext,
1928 row: &mut BindingRow,
1929 results: &mut Vec<BindingRow>,
1930 ) -> Result<bool, String> {
1931 let path = ctx
1932 .paths
1933 .get(path_id as usize)
1934 .ok_or("Path ID out of bounds")?;
1935
1936 match path {
1937 crate::sparql_ast::Path::Predicate(pred) => {
1938 self.execute_triple_scan(subject, *pred, object, ctx, row, results)
1940 }
1941 crate::sparql_ast::Path::Inverse(inner_id) => {
1942 self.execute_property_path(object, *inner_id, subject, ctx, row, results)
1944 }
1945 crate::sparql_ast::Path::Sequence { left, right } => {
1946 let mut intermediate_results = Vec::new();
1948 self.execute_property_path(subject, *left, 0, ctx, row, &mut intermediate_results)?;
1949
1950 for inter_result in intermediate_results {
1951 let intermediate_val = inter_result.slots[0].unwrap_or(0);
1952 self.execute_property_path(
1953 intermediate_val,
1954 *right,
1955 object,
1956 ctx,
1957 row,
1958 results,
1959 )?;
1960 }
1961 Ok(!results.is_empty())
1962 }
1963 crate::sparql_ast::Path::Alternative { left, right } => {
1964 let mut left_results = Vec::new();
1966 let mut right_results = Vec::new();
1967
1968 self.execute_property_path(subject, *left, object, ctx, row, &mut left_results)?;
1969 self.execute_property_path(subject, *right, object, ctx, row, &mut right_results)?;
1970
1971 results.extend_from_slice(&left_results);
1972 results.extend_from_slice(&right_results);
1973 Ok(!results.is_empty())
1974 }
1975 crate::sparql_ast::Path::ZeroOrMore(inner_id) => {
1976 let mut reached = self.path_transitive_hops(subject, *inner_id, ctx, row)?;
1980 reached.insert(subject);
1981 Self::emit_path_nodes(reached, object, results);
1982 Ok(!results.is_empty())
1983 }
1984 crate::sparql_ast::Path::OneOrMore(inner_id) => {
1985 let reached = self.path_transitive_hops(subject, *inner_id, ctx, row)?;
1989 Self::emit_path_nodes(reached, object, results);
1990 Ok(!results.is_empty())
1991 }
1992 crate::sparql_ast::Path::ZeroOrOne(inner_id) => {
1993 if subject == object {
1996 let mut direct_row = BindingRow::new();
1997 direct_row.slots[0] = Some(subject);
1998 results.push(direct_row);
1999 }
2000
2001 self.execute_property_path(subject, *inner_id, object, ctx, row, results)
2003 }
2004 }
2005 }
2006
2007 fn path_transitive_hops(
2012 &self,
2013 subject: u64,
2014 path_id: PathId,
2015 ctx: &SparqlQueryContext,
2016 row: &mut BindingRow,
2017 ) -> Result<std::collections::HashSet<u64>, String> {
2018 use std::collections::HashSet;
2019 let mut reached: HashSet<u64> = HashSet::new();
2020 let mut expanded: HashSet<u64> = HashSet::new();
2021 let mut frontier: Vec<u64> = vec![subject];
2022 while let Some(node) = frontier.pop() {
2023 if !expanded.insert(node) {
2024 continue; }
2026 let mut hops = Vec::new();
2027 self.execute_property_path(node, path_id, 0, ctx, row, &mut hops)?;
2028 for hop in hops {
2029 let next = hop.slots[0].unwrap_or(0);
2030 reached.insert(next);
2031 frontier.push(next);
2032 }
2033 }
2034 Ok(reached)
2035 }
2036
2037 fn emit_path_nodes(
2040 nodes: impl IntoIterator<Item = u64>,
2041 object: u64,
2042 results: &mut Vec<BindingRow>,
2043 ) {
2044 for node in nodes {
2045 if object == 0 || node == object {
2046 let mut r = BindingRow::new();
2047 r.slots[0] = Some(node);
2048 results.push(r);
2049 }
2050 }
2051 }
2052
2053 fn execute_graph(
2056 &self,
2057 graph_var_or_id: u64,
2058 inner: OperatorId,
2059 plan: &ExecutionPlan,
2060 ctx: &SparqlQueryContext,
2061 row: &mut BindingRow,
2062 results: &mut Vec<BindingRow>,
2063 ) -> Result<bool, String> {
2064 if let Some(graph_var) = term_is_var(graph_var_or_id, ctx) {
2068 let mut contexts: Vec<u64> = Vec::new();
2069 for q in self.quins {
2070 if q.context != 0 && !contexts.contains(&q.context) {
2071 contexts.push(q.context);
2072 }
2073 }
2074
2075 let mut matched = false;
2076 for gctx in contexts {
2077 let graph_quins = crate::query_engine::filter_by_context(self.quins, gctx);
2078 if graph_quins.is_empty() {
2079 continue;
2080 }
2081 let temp_executor = QueryExecutor {
2082 quins: &graph_quins,
2083 resolver: self.resolver,
2084 };
2085 let mut seed = *row;
2088 seed.set(graph_var, gctx);
2089 let mut local = Vec::new();
2090 if temp_executor.execute_operator(inner, plan, ctx, &mut seed, &mut local)? {
2091 matched = true;
2092 }
2093 for mut r in local {
2094 r.set(graph_var, gctx);
2095 results.push(r);
2096 }
2097 }
2098 return Ok(matched);
2099 }
2100
2101 let graph_id = graph_var_or_id;
2103
2104 let graph_quins = crate::query_engine::filter_by_context(self.quins, graph_id);
2106
2107 if graph_quins.is_empty() {
2108 return Ok(false);
2109 }
2110
2111 let temp_executor = QueryExecutor {
2114 quins: &graph_quins,
2115 resolver: self.resolver,
2116 };
2117
2118 temp_executor.execute_operator(inner, plan, ctx, row, results)
2120 }
2121
2122 fn execute_service(
2128 &self,
2129 endpoint_did_id: u64,
2130 inner: OperatorId,
2131 plan: &ExecutionPlan,
2132 ctx: &SparqlQueryContext,
2133 row: &mut BindingRow,
2134 results: &mut Vec<BindingRow>,
2135 ) -> Result<bool, String> {
2136 let is_did = (endpoint_did_id & 0x8000_0000_0000_0000) != 0;
2138
2139 if !is_did {
2140 return Err("Invalid DID: missing 0x8 prefix".to_string());
2141 }
2142
2143 let is_local = endpoint_did_id == 0x8000_0000_0000_0000
2145 || self
2146 .quins
2147 .first()
2148 .is_some_and(|q| q.context == (endpoint_did_id & 0x7FFF_FFFF_FFFF_FFFF));
2149
2150 if is_local {
2151 self.execute_operator(inner, plan, ctx, row, results)
2152 } else {
2153 Err(format!(
2154 "SPARQL SERVICE federation to remote endpoint DID 0x{:016x} is not wired to local executor (fails closed; use FederatedQueryHandler with configured endpoint URL)",
2155 endpoint_did_id
2156 ))
2157 }
2158 }
2159
2160 fn execute_as_of(
2164 &self,
2165 input: OperatorId,
2166 timestamp_ms: u64,
2167 mode: TemporalMode,
2168 plan: &ExecutionPlan,
2169 ctx: &SparqlQueryContext,
2170 row: &mut BindingRow,
2171 results: &mut Vec<BindingRow>,
2172 ) -> Result<bool, String> {
2173 let mut inner_results = Vec::new();
2174 self.execute_operator(input, plan, ctx, row, &mut inner_results)?;
2175
2176 for candidate in inner_results {
2177 let subject_opt = candidate.slots.iter().find_map(|s| *s);
2178 let passes = if let Some(subject) = subject_opt {
2179 self.check_temporal_constraint(subject, timestamp_ms, mode)
2180 } else {
2181 true
2182 };
2183 if passes {
2184 results.push(candidate);
2185 }
2186 }
2187 Ok(!results.is_empty())
2188 }
2189
2190 fn check_temporal_constraint(
2195 &self,
2196 subject: u64,
2197 timestamp_ms: u64,
2198 mode: TemporalMode,
2199 ) -> bool {
2200 use crate::kml_bridge::T_CONTEXT;
2201 use crate::sparql_filter::prov_predicates;
2202
2203 match mode {
2204 TemporalMode::AsOf => {
2205 let gen_time = self
2206 .quins
2207 .iter()
2208 .find(|q| {
2209 q.subject == subject
2210 && q.predicate == prov_predicates::GENERATED_AT_TIME
2211 && q.context == T_CONTEXT
2212 })
2213 .map(|q| q.object);
2214 gen_time.map(|t| t <= timestamp_ms).unwrap_or(true)
2215 }
2216 TemporalMode::AtTime => {
2217 let start = self
2218 .quins
2219 .iter()
2220 .find(|q| {
2221 q.subject == subject
2222 && q.predicate == prov_predicates::STARTED_AT_TIME
2223 && q.context == T_CONTEXT
2224 })
2225 .map(|q| q.object);
2226 let end = self
2227 .quins
2228 .iter()
2229 .find(|q| {
2230 q.subject == subject
2231 && q.predicate == prov_predicates::ENDED_AT_TIME
2232 && q.context == T_CONTEXT
2233 })
2234 .map(|q| q.object);
2235 start.map(|t| t <= timestamp_ms).unwrap_or(true)
2236 && end.map(|t| timestamp_ms <= t).unwrap_or(true)
2237 }
2238 }
2239 }
2240}
2241
2242pub fn unpack_virtual_triple(
2244 virtual_id: u64,
2245 lexicon: &crate::q42_lex::Q42LexMmap<'_>,
2246 row: &mut crate::sparql_ast::BindingRow,
2247 s_var_idx: Option<u8>,
2248 p_var_idx: Option<u8>,
2249 o_var_idx: Option<u8>,
2250) -> Result<(), String> {
2251 if let Some([s_id, p_id, o_id]) = lexicon.lookup_embedded_triple(virtual_id) {
2252 if let Some(s_idx) = s_var_idx {
2253 row.slots[s_idx as usize] = Some(s_id);
2254 }
2255 if let Some(p_idx) = p_var_idx {
2256 row.slots[p_idx as usize] = Some(p_id);
2257 }
2258 if let Some(o_idx) = o_var_idx {
2259 row.slots[o_idx as usize] = Some(o_id);
2260 }
2261 Ok(())
2262 } else {
2263 Err("Virtual ID not found in lexicon or invalid".to_string())
2264 }
2265}
2266
2267#[cfg(test)]
2268mod tests {
2269 use super::*;
2270
2271 #[test]
2272 fn test_executor_creation() {
2273 let quins = vec![];
2274 let executor = QueryExecutor::new(&quins);
2275 assert_eq!(executor.quins.len(), 0);
2276 }
2277
2278 #[test]
2279 fn test_execute_empty_plan() {
2280 let quins = vec![];
2281 let executor = QueryExecutor::new(&quins);
2282 let plan = ExecutionPlan::new();
2283 let ctx = SparqlQueryContext::new();
2284
2285 let result = executor.execute(&plan, &ctx);
2286 assert!(result.is_err());
2288 }
2289
2290 #[cfg(not(target_arch = "wasm32"))]
2291 #[test]
2292 fn range_triple_page_uses_q42_bidx_without_resident_graph() {
2293 let dir = tempfile::TempDir::new().unwrap();
2294 let path = dir.path().join("range.q42");
2295 let quin = NQuin {
2296 subject: 101,
2297 predicate: 202,
2298 object: 303,
2299 context: 0,
2300 metadata: 0,
2301 parity: 0,
2302 };
2303 crate::q42_volume::write_unified_volume(
2304 &path,
2305 &std::collections::HashMap::new(),
2306 &[(quin.object, quin.object)],
2307 &[vec![quin]],
2308 )
2309 .unwrap();
2310 let source = crate::q42_volume::LocalFileRangeSource::open(&path).unwrap();
2311 let volume = crate::q42_volume::Q42RangeVolume::open(source).unwrap();
2312 let context = SparqlQueryContext::new();
2313 let mut compressed = [0u8; crate::q42_volume::MAX_COMPRESSED_SUPERBLOCK_SIZE];
2314 let mut decoded = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
2315 let mut quins = [NQuin::default(); 1];
2316 let mut rows = [BindingRow::default(); 1];
2317 let page = execute_range_triple_page_into(
2318 &volume,
2319 quin.subject,
2320 quin.predicate,
2321 quin.object,
2322 None,
2323 &context,
2324 &BindingRow::default(),
2325 Q42RangeSparqlCursor::default(),
2326 &mut compressed,
2327 &mut decoded,
2328 &mut quins,
2329 &mut rows,
2330 )
2331 .unwrap();
2332 assert_eq!(page.returned, 1);
2333 assert_eq!(rows[0].slots[0], None);
2334 }
2335
2336 #[cfg(not(target_arch = "wasm32"))]
2337 #[test]
2338 fn range_nested_loop_join_resumes_without_a_resident_graph() {
2339 let dir = tempfile::TempDir::new().unwrap();
2340 let path = dir.path().join("range-join.q42");
2341 let left = NQuin {
2342 subject: 10,
2343 predicate: 20,
2344 object: 30,
2345 context: 0,
2346 metadata: 0,
2347 parity: 0,
2348 };
2349 let right = NQuin {
2350 subject: 30,
2351 predicate: 40,
2352 object: 50,
2353 context: 0,
2354 metadata: 0,
2355 parity: 0,
2356 };
2357 crate::q42_volume::write_unified_volume(
2358 &path,
2359 &std::collections::HashMap::new(),
2360 &[(left.object, right.object)],
2361 &[vec![left, right]],
2362 )
2363 .unwrap();
2364 let source = crate::q42_volume::LocalFileRangeSource::open(&path).unwrap();
2365 let volume = crate::q42_volume::Q42RangeVolume::open(source).unwrap();
2366 let mut context = SparqlQueryContext::new();
2367 context.variable_count = 1;
2368 let plan = Q42RangeNestedLoopJoinPlan {
2369 left: Q42RangeTriplePattern {
2370 subject: left.subject,
2371 predicate: left.predicate,
2372 object: 0,
2373 },
2374 right: Q42RangeTriplePattern {
2375 subject: 0,
2376 predicate: right.predicate,
2377 object: right.object,
2378 },
2379 };
2380 let mut compressed = [0u8; crate::q42_volume::MAX_COMPRESSED_SUPERBLOCK_SIZE];
2381 let mut decoded = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
2382 let mut quins = [NQuin::default(); 1];
2383 let mut left_rows = [BindingRow::default(); 1];
2384 let mut right_rows = [BindingRow::default(); 1];
2385 let mut out = [BindingRow::default(); 1];
2386 let mut state = Q42RangeNestedLoopJoinState::default();
2387
2388 let first = execute_range_nested_loop_join_page_into(
2389 &volume,
2390 plan,
2391 &context,
2392 &mut state,
2393 &mut compressed,
2394 &mut decoded,
2395 &mut quins,
2396 &mut left_rows,
2397 &mut right_rows,
2398 &mut out,
2399 )
2400 .unwrap();
2401 assert_eq!(first.returned, 1);
2402 assert_eq!(out[0].slots[0], Some(right.subject));
2403 assert!(!first.done);
2404
2405 let final_page = execute_range_nested_loop_join_page_into(
2406 &volume,
2407 plan,
2408 &context,
2409 &mut state,
2410 &mut compressed,
2411 &mut decoded,
2412 &mut quins,
2413 &mut left_rows,
2414 &mut right_rows,
2415 &mut out,
2416 )
2417 .unwrap();
2418 assert_eq!(final_page.returned, 0);
2419 assert!(final_page.done);
2420 }
2421
2422 #[cfg(not(target_arch = "wasm32"))]
2423 #[test]
2424 fn range_volume_set_nested_loop_join_scans_manifest_children() {
2425 let dir = tempfile::TempDir::new().unwrap();
2426 let child_path = dir.path().join("child.q42");
2427 let root_path = dir.path().join("root.q42");
2428 let left = NQuin {
2429 subject: 10,
2430 predicate: 20,
2431 object: 30,
2432 context: 0,
2433 metadata: 0,
2434 parity: 0,
2435 };
2436 let right = NQuin {
2437 subject: 30,
2438 predicate: 40,
2439 object: 50,
2440 context: 0,
2441 metadata: 0,
2442 parity: 0,
2443 };
2444 crate::q42_volume::write_unified_volume(
2445 &child_path,
2446 &std::collections::HashMap::new(),
2447 &[(left.object, right.object)],
2448 &[vec![left, right]],
2449 )
2450 .unwrap();
2451 let manifest = crate::q42_volume::Q42VolumeManifest {
2452 generation: 1,
2453 segments: vec![crate::q42_volume::Q42VolumeManifest::segment_from_file(
2454 &child_path,
2455 "child.q42".to_string(),
2456 )
2457 .unwrap()],
2458 lexicon_segments: Vec::new(),
2459 };
2460 crate::q42_volume::write_volume_root(&root_path, &manifest).unwrap();
2461 let root_source = crate::q42_volume::LocalFileRangeSource::open(&root_path).unwrap();
2462 let root = crate::q42_volume::Q42RangeVolume::open(root_source).unwrap();
2463 let factory = |entry: &crate::q42_volume::Q42VolumeSegment| {
2464 crate::q42_volume::LocalFileRangeSource::open(&dir.path().join(&entry.locator))
2465 };
2466 let volumes = crate::q42_volume::Q42RangeVolumeSet::open_root(&root, &factory).unwrap();
2467 let mut context = SparqlQueryContext::new();
2468 context.variable_count = 1;
2469 let plan = Q42RangeNestedLoopJoinPlan {
2470 left: Q42RangeTriplePattern {
2471 subject: left.subject,
2472 predicate: left.predicate,
2473 object: 0,
2474 },
2475 right: Q42RangeTriplePattern {
2476 subject: 0,
2477 predicate: right.predicate,
2478 object: right.object,
2479 },
2480 };
2481 let mut compressed = [0u8; crate::q42_volume::MAX_COMPRESSED_SUPERBLOCK_SIZE];
2482 let mut decoded = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
2483 let mut quins = [NQuin::default(); 1];
2484 let mut left_rows = [BindingRow::default(); 1];
2485 let mut right_rows = [BindingRow::default(); 1];
2486 let mut out = [BindingRow::default(); 1];
2487 let mut state = Q42RangeVolumeSetNestedLoopJoinState::default();
2488 let page = execute_range_volume_set_nested_loop_join_page_into(
2489 &volumes,
2490 plan,
2491 &context,
2492 &mut state,
2493 &mut compressed,
2494 &mut decoded,
2495 &mut quins,
2496 &mut left_rows,
2497 &mut right_rows,
2498 &mut out,
2499 )
2500 .unwrap();
2501 assert_eq!(page.returned, 1);
2502 assert_eq!(out[0].slots[0], Some(right.subject));
2503 }
2504}