1use super::range_select_apply::{apply_select_wrappers, SelectWrapperState};
9use super::sparql_ast::{BindingRow, ExpressionId, SparqlQueryContext, VariableId, MAX_VARIABLES};
10use super::sparql_executor::{
11 execute_range_triple_page_into, execute_range_volume_set_triple_page_into,
12 Q42RangeNestedLoopJoinPage, Q42RangeSparqlCursor, Q42RangeTriplePattern,
13 Q42RangeVolumeSetSparqlCursor,
14};
15use super::sparql_planner::{ExecutionPlan, PhysicalOperatorType};
16use crate::NQuin;
17
18#[derive(Clone, Copy, Debug, Eq, PartialEq)]
19pub struct Q42RangeOptionalPlan {
20 pub left: Q42RangeTriplePattern,
21 pub right: Q42RangeTriplePattern,
22 pub projection: [VariableId; MAX_VARIABLES],
23 pub projection_count: u8,
24 pub filters: [ExpressionId; 8],
25 pub filter_count: u8,
26 pub limit: u64,
27 pub offset: u64,
28}
29
30#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
31pub struct Q42RangeOptionalState {
32 pub left_scan: Q42RangeSparqlCursor,
33 pub right_scan: Q42RangeSparqlCursor,
34 pub left_count: usize,
35 pub left_index: usize,
36 pub left_exhausted: bool,
37 pub right_active: bool,
38 pub left_row_matched: bool,
39 pub wrappers: SelectWrapperState,
40}
41
42#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
43pub struct Q42RangeVolumeSetOptionalState {
44 pub left_scan: Q42RangeVolumeSetSparqlCursor,
45 pub right_scan: Q42RangeVolumeSetSparqlCursor,
46 pub left_count: usize,
47 pub left_index: usize,
48 pub left_exhausted: bool,
49 pub right_active: bool,
50 pub left_row_matched: bool,
51 pub wrappers: SelectWrapperState,
52}
53
54impl Q42RangeOptionalPlan {
55 pub fn from_execution_plan(plan: &ExecutionPlan) -> Result<Self, String> {
57 if plan.operator_count == 0 || plan.root_operator as usize >= plan.operator_count as usize {
58 return Err("range OPTIONAL requires a non-empty execution plan".into());
59 }
60 let mut operator = plan.root_operator;
61 let mut projection = [0; MAX_VARIABLES];
62 let mut projection_count = 0;
63 let mut filters = [0; 8];
64 let mut filter_count = 0usize;
65 let mut limit = u64::MAX;
66 let mut offset = 0;
67 loop {
68 match plan.operators[operator as usize].operator_type {
69 PhysicalOperatorType::Project {
70 input,
71 vars,
72 var_count,
73 } => {
74 if projection_count != 0 {
75 return Err("range OPTIONAL does not support nested projections".into());
76 }
77 projection = vars;
78 projection_count = var_count;
79 operator = input;
80 }
81 PhysicalOperatorType::Limit {
82 input,
83 limit: configured,
84 offset: configured_offset,
85 } => {
86 if limit != u64::MAX || offset != 0 {
87 return Err("range OPTIONAL does not support nested limits".into());
88 }
89 limit = configured;
90 offset = configured_offset;
91 operator = input;
92 }
93 PhysicalOperatorType::Filter { input, expression } => {
94 if filter_count == filters.len() {
95 return Err(
96 "range OPTIONAL supports at most eight stacked FILTER operators".into(),
97 );
98 }
99 filters[filter_count] = expression;
100 filter_count += 1;
101 operator = input;
102 }
103 PhysicalOperatorType::Optional { left, right } => {
104 return Ok(Self {
105 left: triple_scan(plan, left)?,
106 right: triple_scan(plan, right)?,
107 projection,
108 projection_count,
109 filters,
110 filter_count: filter_count as u8,
111 limit,
112 offset,
113 });
114 }
115 _ => {
116 return Err(
117 "range OPTIONAL supports Project/Filter/Limit over Optional(TripleScan, TripleScan)"
118 .into(),
119 );
120 }
121 }
122 }
123 }
124}
125
126fn triple_scan(plan: &ExecutionPlan, operator: u16) -> Result<Q42RangeTriplePattern, String> {
127 let Some(entry) = plan.operators.get(operator as usize) else {
128 return Err("range OPTIONAL input operator is out of bounds".into());
129 };
130 match entry.operator_type {
131 PhysicalOperatorType::TripleScan {
132 subject,
133 predicate,
134 object,
135 } => Ok(Q42RangeTriplePattern {
136 subject,
137 predicate,
138 object,
139 }),
140 _ => Err("range OPTIONAL currently requires TripleScan inputs".into()),
141 }
142}
143
144pub fn execute_range_optional_page_into<S: crate::q42_volume::Q42RangeSource>(
146 volume: &crate::q42_volume::Q42RangeVolume<S>,
147 plan: Q42RangeOptionalPlan,
148 ctx: &SparqlQueryContext,
149 state: &mut Q42RangeOptionalState,
150 compressed: &mut [u8],
151 decoded: &mut [u8],
152 quin_scratch: &mut [NQuin],
153 left_rows: &mut [BindingRow],
154 right_rows: &mut [BindingRow],
155 join_out: &mut [BindingRow],
156 out: &mut [BindingRow],
157) -> Result<Q42RangeNestedLoopJoinPage, String> {
158 if quin_scratch.is_empty()
159 || left_rows.len() < quin_scratch.len()
160 || right_rows.len() < quin_scratch.len()
161 || join_out.len() < quin_scratch.len()
162 {
163 return Err("range OPTIONAL requires row buffers at least as large as Quin scratch".into());
164 }
165 let mut returned = 0usize;
166 loop {
167 if returned == out.len() {
168 return Ok(Q42RangeNestedLoopJoinPage {
169 returned,
170 done: false,
171 });
172 }
173 if state.wrappers.emitted >= plan.limit {
174 return Ok(Q42RangeNestedLoopJoinPage {
175 returned,
176 done: true,
177 });
178 }
179 let scratch_len = quin_scratch.len();
180 let produced = fill_optional_page(
181 |pattern, input, cursor, rows| {
182 execute_range_triple_page_into(
183 volume,
184 pattern.subject,
185 pattern.predicate,
186 pattern.object,
187 None,
188 ctx,
189 input,
190 cursor,
191 compressed,
192 decoded,
193 quin_scratch,
194 rows,
195 )
196 .map(|page| (page.returned, page.next_cursor))
197 },
198 plan,
199 scratch_len,
200 &mut state.left_scan,
201 &mut state.right_scan,
202 &mut state.left_count,
203 &mut state.left_index,
204 &mut state.left_exhausted,
205 &mut state.right_active,
206 &mut state.left_row_matched,
207 left_rows,
208 right_rows,
209 join_out,
210 )?;
211 let applied = apply_select_wrappers(
212 ctx,
213 &plan.filters,
214 plan.filter_count,
215 plan.projection,
216 plan.projection_count,
217 plan.limit,
218 plan.offset,
219 &mut state.wrappers,
220 &join_out[..produced.returned],
221 &mut out[returned..],
222 )?;
223 returned += applied.returned;
224 if produced.done || applied.limit_reached {
225 return Ok(Q42RangeNestedLoopJoinPage {
226 returned,
227 done: true,
228 });
229 }
230 if applied.returned == 0 {
231 continue;
232 }
233 if returned > 0 {
234 return Ok(Q42RangeNestedLoopJoinPage {
235 returned,
236 done: false,
237 });
238 }
239 }
240}
241
242pub fn execute_range_volume_set_optional_page_into<S: crate::q42_volume::Q42RangeSource>(
244 volumes: &crate::q42_volume::Q42RangeVolumeSet<S>,
245 plan: Q42RangeOptionalPlan,
246 ctx: &SparqlQueryContext,
247 state: &mut Q42RangeVolumeSetOptionalState,
248 compressed: &mut [u8],
249 decoded: &mut [u8],
250 quin_scratch: &mut [NQuin],
251 left_rows: &mut [BindingRow],
252 right_rows: &mut [BindingRow],
253 join_out: &mut [BindingRow],
254 out: &mut [BindingRow],
255) -> Result<Q42RangeNestedLoopJoinPage, String> {
256 if quin_scratch.is_empty()
257 || left_rows.len() < quin_scratch.len()
258 || right_rows.len() < quin_scratch.len()
259 || join_out.len() < quin_scratch.len()
260 {
261 return Err("range OPTIONAL requires row buffers at least as large as Quin scratch".into());
262 }
263 let mut returned = 0usize;
264 loop {
265 if returned == out.len() {
266 return Ok(Q42RangeNestedLoopJoinPage {
267 returned,
268 done: false,
269 });
270 }
271 if state.wrappers.emitted >= plan.limit {
272 return Ok(Q42RangeNestedLoopJoinPage {
273 returned,
274 done: true,
275 });
276 }
277 let scratch_len = quin_scratch.len();
278 let produced = fill_optional_page(
279 |pattern, input, cursor, rows| {
280 execute_range_volume_set_triple_page_into(
281 volumes,
282 pattern.subject,
283 pattern.predicate,
284 pattern.object,
285 None,
286 ctx,
287 input,
288 cursor,
289 compressed,
290 decoded,
291 quin_scratch,
292 rows,
293 )
294 .map(|page| (page.returned, page.next_cursor))
295 },
296 plan,
297 scratch_len,
298 &mut state.left_scan,
299 &mut state.right_scan,
300 &mut state.left_count,
301 &mut state.left_index,
302 &mut state.left_exhausted,
303 &mut state.right_active,
304 &mut state.left_row_matched,
305 left_rows,
306 right_rows,
307 join_out,
308 )?;
309 let applied = apply_select_wrappers(
310 ctx,
311 &plan.filters,
312 plan.filter_count,
313 plan.projection,
314 plan.projection_count,
315 plan.limit,
316 plan.offset,
317 &mut state.wrappers,
318 &join_out[..produced.returned],
319 &mut out[returned..],
320 )?;
321 returned += applied.returned;
322 if produced.done || applied.limit_reached {
323 return Ok(Q42RangeNestedLoopJoinPage {
324 returned,
325 done: true,
326 });
327 }
328 if applied.returned == 0 {
329 continue;
330 }
331 if returned > 0 {
332 return Ok(Q42RangeNestedLoopJoinPage {
333 returned,
334 done: false,
335 });
336 }
337 }
338}
339
340fn fill_optional_page<C, F>(
341 mut page_fn: F,
342 plan: Q42RangeOptionalPlan,
343 scratch_len: usize,
344 left_scan: &mut C,
345 right_scan: &mut C,
346 left_count: &mut usize,
347 left_index: &mut usize,
348 left_exhausted: &mut bool,
349 right_active: &mut bool,
350 left_row_matched: &mut bool,
351 left_rows: &mut [BindingRow],
352 right_rows: &mut [BindingRow],
353 out: &mut [BindingRow],
354) -> Result<Q42RangeNestedLoopJoinPage, String>
355where
356 C: Copy + Default,
357 F: FnMut(
358 Q42RangeTriplePattern,
359 &BindingRow,
360 C,
361 &mut [BindingRow],
362 ) -> Result<(usize, Option<C>), String>,
363{
364 let mut returned = 0usize;
365 loop {
366 if returned + scratch_len > out.len() {
367 return Ok(Q42RangeNestedLoopJoinPage {
368 returned,
369 done: false,
370 });
371 }
372 if *left_index >= *left_count {
373 if *left_exhausted {
374 return Ok(Q42RangeNestedLoopJoinPage {
375 returned,
376 done: true,
377 });
378 }
379 let (count, next) = page_fn(plan.left, &BindingRow::default(), *left_scan, left_rows)?;
380 *left_count = count;
381 *left_index = 0;
382 *left_scan = next.unwrap_or_default();
383 *left_exhausted = next.is_none();
384 *right_active = false;
385 *left_row_matched = false;
386 if *left_count == 0 {
387 if *left_exhausted {
388 return Ok(Q42RangeNestedLoopJoinPage {
389 returned,
390 done: true,
391 });
392 }
393 continue;
394 }
395 }
396 let input = left_rows[*left_index];
397 if !*right_active {
398 *left_row_matched = false;
399 }
400 let (count, next) = page_fn(
401 plan.right,
402 &input,
403 if *right_active {
404 *right_scan
405 } else {
406 C::default()
407 },
408 right_rows,
409 )?;
410 out[returned..returned + count].copy_from_slice(&right_rows[..count]);
411 returned += count;
412 if count > 0 {
413 *left_row_matched = true;
414 }
415 match next {
416 Some(cursor) => {
417 *right_scan = cursor;
418 *right_active = true;
419 }
420 None => {
421 if !*left_row_matched {
422 if returned == out.len() {
423 return Ok(Q42RangeNestedLoopJoinPage {
424 returned,
425 done: false,
426 });
427 }
428 out[returned] = input;
429 returned += 1;
430 }
431 *left_index += 1;
432 *right_scan = C::default();
433 *right_active = false;
434 *left_row_matched = false;
435 }
436 }
437 if returned + scratch_len > out.len() {
438 return Ok(Q42RangeNestedLoopJoinPage {
439 returned,
440 done: false,
441 });
442 }
443 }
444}
445
446#[cfg(test)]
447mod tests {
448 use super::*;
449 use crate::q42_volume::{write_unified_volume, LocalFileRangeSource, Q42RangeVolume};
450
451 fn test_volume(quins: &[NQuin]) -> (tempfile::TempDir, Q42RangeVolume<LocalFileRangeSource>) {
452 let dir = tempfile::TempDir::new().unwrap();
453 let path = dir.path().join("optional.q42");
454 let lo = quins.iter().map(|q| q.object).min().unwrap_or(0);
455 let hi = quins.iter().map(|q| q.object).max().unwrap_or(0);
456 write_unified_volume(
457 &path,
458 &std::collections::HashMap::new(),
459 &[(lo, hi)],
460 &[quins.to_vec()],
461 )
462 .unwrap();
463 let source = LocalFileRangeSource::open(&path).unwrap();
464 let volume = Q42RangeVolume::open(source).unwrap();
465 (dir, volume)
466 }
467
468 fn quin(s: u64, p: u64, o: u64) -> NQuin {
469 NQuin {
470 subject: s,
471 predicate: p,
472 object: o,
473 context: 0,
474 metadata: 0,
475 parity: 0,
476 }
477 }
478
479 #[test]
480 fn peels_project_from_optional_tree() {
481 let mut plan = ExecutionPlan::new();
482 let left = plan
483 .add_operator(
484 PhysicalOperatorType::TripleScan {
485 subject: 0,
486 predicate: 20,
487 object: 1,
488 },
489 1,
490 )
491 .unwrap();
492 let right = plan
493 .add_operator(
494 PhysicalOperatorType::TripleScan {
495 subject: 1,
496 predicate: 40,
497 object: 2,
498 },
499 1,
500 )
501 .unwrap();
502 let optional = plan
503 .add_operator(PhysicalOperatorType::Optional { left, right }, 1)
504 .unwrap();
505 let mut vars = [0; MAX_VARIABLES];
506 vars[0] = 0;
507 plan.root_operator = plan
508 .add_operator(
509 PhysicalOperatorType::Project {
510 input: optional,
511 vars,
512 var_count: 1,
513 },
514 1,
515 )
516 .unwrap();
517 let compiled = Q42RangeOptionalPlan::from_execution_plan(&plan).unwrap();
518 assert_eq!(compiled.projection_count, 1);
519 assert_eq!(compiled.left.predicate, 20);
520 assert_eq!(compiled.right.predicate, 40);
521 }
522
523 #[test]
524 fn unmatched_left_row_is_kept() {
525 let required = quin(10, 20, 30);
526 let unmatched = quin(11, 20, 31);
527 let optional = quin(30, 40, 50);
528 let (_dir, volume) = test_volume(&[required, unmatched, optional]);
529 let mut ctx = SparqlQueryContext::new();
530 ctx.variable_count = 2;
531 let plan = Q42RangeOptionalPlan {
532 left: Q42RangeTriplePattern {
533 subject: 0,
534 predicate: 20,
535 object: 1,
536 },
537 right: Q42RangeTriplePattern {
538 subject: 1,
539 predicate: 40,
540 object: 50,
541 },
542 projection: [0; MAX_VARIABLES],
543 projection_count: 0,
544 filters: [0; 8],
545 filter_count: 0,
546 limit: u64::MAX,
547 offset: 0,
548 };
549 let mut compressed = [0u8; crate::q42_volume::MAX_COMPRESSED_SUPERBLOCK_SIZE];
550 let mut decoded = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
551 let mut quins = [NQuin::default(); 4];
552 let mut left_rows = [BindingRow::default(); 4];
553 let mut right_rows = [BindingRow::default(); 4];
554 let mut join_out = [BindingRow::default(); 4];
555 let mut out = [BindingRow::default(); 4];
556 let mut state = Q42RangeOptionalState::default();
557 let mut rows = Vec::new();
558 loop {
559 let page = execute_range_optional_page_into(
560 &volume,
561 plan,
562 &ctx,
563 &mut state,
564 &mut compressed,
565 &mut decoded,
566 &mut quins,
567 &mut left_rows,
568 &mut right_rows,
569 &mut join_out,
570 &mut out,
571 )
572 .unwrap();
573 rows.extend_from_slice(&out[..page.returned]);
574 if page.done {
575 break;
576 }
577 }
578 assert_eq!(rows.len(), 2);
579 let subjects: Vec<u64> = rows.iter().filter_map(|row| row.get(0)).collect();
580 assert!(subjects.contains(&10));
581 assert!(subjects.contains(&11));
582 let matched = rows.iter().find(|row| row.get(0) == Some(10)).unwrap();
583 assert_eq!(matched.get(1), Some(30));
584 let kept = rows.iter().find(|row| row.get(0) == Some(11)).unwrap();
585 assert_eq!(kept.get(1), Some(31));
586 }
587
588 #[test]
589 fn empty_left_yields_no_rows() {
590 let only_right = quin(30, 40, 50);
591 let (_dir, volume) = test_volume(&[only_right]);
592 let mut ctx = SparqlQueryContext::new();
593 ctx.variable_count = 1;
594 let plan = Q42RangeOptionalPlan {
595 left: Q42RangeTriplePattern {
596 subject: 0,
597 predicate: 20,
598 object: 99,
599 },
600 right: Q42RangeTriplePattern {
601 subject: 0,
602 predicate: 40,
603 object: 50,
604 },
605 projection: [0; MAX_VARIABLES],
606 projection_count: 0,
607 filters: [0; 8],
608 filter_count: 0,
609 limit: u64::MAX,
610 offset: 0,
611 };
612 let mut compressed = [0u8; crate::q42_volume::MAX_COMPRESSED_SUPERBLOCK_SIZE];
613 let mut decoded = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
614 let mut quins = [NQuin::default(); 2];
615 let mut left_rows = [BindingRow::default(); 2];
616 let mut right_rows = [BindingRow::default(); 2];
617 let mut join_out = [BindingRow::default(); 2];
618 let mut out = [BindingRow::default(); 2];
619 let mut state = Q42RangeOptionalState::default();
620 let page = execute_range_optional_page_into(
621 &volume,
622 plan,
623 &ctx,
624 &mut state,
625 &mut compressed,
626 &mut decoded,
627 &mut quins,
628 &mut left_rows,
629 &mut right_rows,
630 &mut join_out,
631 &mut out,
632 )
633 .unwrap();
634 assert!(page.done);
635 assert_eq!(page.returned, 0);
636 }
637}