Skip to main content

qualia_core_db/sparql_library/
range_union.rs

1//! Range-native SPARQL UNION over two paged TripleScans.
2//!
3//! SPARQL UNION is a bag union: left pages are emitted first, then right
4//! pages. No deduplication. Project / Filter / Limit wrappers sit above the
5//! union and are applied per page.
6
7use 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    /// Builds `Q42RangeUnionPlan` from `execution_plan`.
49    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
137/// Executes a range-union into `out`.
138pub 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
219/// Executes a volume-set range-union into `out`.
220pub 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}