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