Skip to main content

qualia_core_db/sparql_library/
range_bind.rs

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