Skip to main content

qualia_core_db/sparql_library/
range_optional.rs

1//! Range-native SPARQL OPTIONAL (left join) over paged TripleScans.
2//!
3//! Each left row is emitted even when the right pattern produces no match.
4//! Matching uses the existing range triple kernel so already-bound variables
5//! stay compatible. Project / Filter / Limit wrappers are peeled, not
6//! materialised.
7
8use 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    /// Builds `Q42RangeOptionalPlan` from `execution_plan`.
56    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
144/// Executes a range-optional into `out`.
145pub 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
242/// Executes a volume-set range-optional into `out`.
243pub 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}